Communication Chapter 2 Flashcards
Noiseless Communication scheme
source -> source encoder (compressor) -> noiseless channel -> source decoder (extractor) -> destination
random source model
Let p = (p₁,..,pₘ) be a discrete probability distribution. A random source S={s₁,..,sₘ} has probability distrubution p={p₁,…,pₘ} if
(1) The random source produces letters one at a time
(2) The letter sᵢ in S is produced with probability pᵢ
(3) The letter is produced independently of the past.
H(P)=
H(P)= - the sum from i=1 to m of pᵢ log₂ pᵢ = H(S)
H(S)=
H(S) = the sum from i=1 to m of pᵢ log (1/pᵢ) = H(P)
How to find the binary entropy function
sub in the values of p into the formula
H(P)= - the sum from i=1 to m of pᵢ log₂ pᵢ
High entropy =>
unpredictable
Low entropy =>
predictable
What range can the entropy be in
0≤H(P)≤logm
When does H(P)=0
if p₁ = 1 and pᵢ = 0
When does H(P) = logm
if pᵢ=1/m (i.e. equal chance for each)
Gibbs Lemma
Let r₁,…,rₘ be a sequence of positive real numbers that have a sum less than or equal to one. Let p = (p₁,…,pₘ) be a probability distribution. Then,
H(P)≤ the sum from i=1 to m of pᵢ log (1/rᵢ) (*)
ENCODING
Takes the source and assigns each letter a codeword
DECODING
Takes one of the codewords and maps it to the associated letter
𝔼(ℓ(f))
𝔼(ℓ(f))= the sum from i=1 to m of pᵢ |f(sᵢ)|
Shannons Noiseless Encoding Theorem
Let S be a random source and f:S->{0,1}* be an optimal prefix-free encoding of S. Then, H(S)≤𝔼(ℓ(f))≤H(S)+1.
How to use Shannons Theorem to work out an optimal encoding
- Find a prefix-free code s.t. H(S)=𝔼(ℓ(f)) (this is best possible) so must be optimal
Just because shannons inequality holds…
doesn’t mean f is an optimal prefix-free encoding
Huffman coding creates…
a PREFIX FREE, OPTIMAL encoding
How to see if a code is a huffman code
- check it is prefix free
- check it is optimal (put into binary tree an check al vertices have exactly 2 children)
- work out probabilities and run the Huffman encoding algo through
How to work out the probability distribution from a Huffman code
- draw out the binary tree for the huffman code
- find inequalities for the probabilities based on the branching. Solve to find probabilities that satisfy these and add up to 1.
Huffman encodings always have the lowest possible _______ amongst all _______
expected length, prefix-free encodings.
a code is more efficient if….
it has a shorter expected length
ℓ(f)
The random variable for the codeword f(s) where s is the letter produced by the source according to the probability distribution P.
How to show an encoding is not optimal
- find a encoding that has smaller expected length
How to show an encoding is optimal
show it is a huffman encoding.
while Loop in Huffmans Procedure
WHILE |L|≥2 DO
- pick two vertices vᵢ₁ vᵢ₂ from L with the lowest probabilities
- create a new vertex vᵢ₁ᵢ₂ and assign the porbability pᵢ₁+pᵢ₂ to it
- Add the edge vᵢ₁ᵢ₂->vᵢ₁ with label 0 and the edge vᵢ₁ᵢ₂->vᵢ₂ with label 1 to the tree
- Delete vᵢ₁ and vᵢ₂ from L
END WHILE
Set Up of Huffman Procedure
Suppose S={s₁,..,sₘ} is a random source with probability distrubution p = (p₁,…,pₘ).
Let L={v₁,..,vₘ} be a se of vertices where vᵢ corresponds to sᵢ∈S.
Add the vertices of L into the tree.
End of Huffman Procedure
Now L={v}. we set r=v to be the root of our tree T
Now construct the encoding from the random source to our code for all i∈[m]. We construct fₕ(sᵢ) by concatenating the labels on the edges from the path from r to vᵢ in T.
