Communication Chapter 2

Question 1

Noiseless Communication scheme

Answer 1

source -> source encoder (compressor) -> noiseless channel -> source decoder (extractor) -> destination

Question 2

random source model

Answer 2

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.

Question 3

H(P)=

Answer 3

H(P)= - the sum from i=1 to m of pᵢ log₂ pᵢ = H(S)

Question 4

H(S)=

Answer 4

H(S) = the sum from i=1 to m of pᵢ log (1/pᵢ) = H(P)

Question 5

How to find the binary entropy function

Answer 5

sub in the values of p into the formula

H(P)= - the sum from i=1 to m of pᵢ log₂ pᵢ

Question 6

High entropy =>

Answer 6

unpredictable

Question 7

Low entropy =>

Answer 7

predictable

Question 8

What range can the entropy be in

Answer 8

0≤H(P)≤logm

Question 9

When does H(P)=0

Answer 9

if p₁ = 1 and pᵢ = 0

Question 10

When does H(P) = logm

Answer 10

if pᵢ=1/m (i.e. equal chance for each)

Question 11

Gibbs Lemma

Answer 11

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ᵢ) (*)

Question 12

ENCODING

Answer 12

Takes the source and assigns each letter a codeword

Question 13

DECODING

Answer 13

Takes one of the codewords and maps it to the associated letter

Question 14

𝔼(ℓ(f))

Answer 14

𝔼(ℓ(f))= the sum from i=1 to m of pᵢ |f(sᵢ)|

Question 15

Shannons Noiseless Encoding Theorem

Answer 15

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.

Question 16

How to use Shannons Theorem to work out an optimal encoding

Answer 16

• Find a prefix-free code s.t. H(S)=𝔼(ℓ(f)) (this is best possible) so must be optimal

Question 17

Just because shannons inequality holds…

Answer 17

doesn’t mean f is an optimal prefix-free encoding

Question 18

Huffman coding creates…

Answer 18

a PREFIX FREE, OPTIMAL encoding

Question 19

How to see if a code is a huffman code

Answer 19

• 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

Question 20

How to work out the probability distribution from a Huffman code

Answer 20

• 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.

Question 21

Huffman encodings always have the lowest possible _______ amongst all _______

Answer 21

expected length, prefix-free encodings.

Question 22

a code is more efficient if….

Answer 22

it has a shorter expected length

Question 23

ℓ(f)

Answer 23

The random variable for the codeword f(s) where s is the letter produced by the source according to the probability distribution P.

Question 24

How to show an encoding is not optimal

Answer 24

• find a encoding that has smaller expected length

Question 25

How to show an encoding is optimal

Answer 25

show it is a huffman encoding.

Question 26

while Loop in Huffmans Procedure

Answer 26

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

Question 27

Set Up of Huffman Procedure

Answer 27

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.

Question 28

End of Huffman Procedure

Answer 28

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.