Communication- Chapter 1

Question 1

Uniquely decipherable informal

Answer 1

there is at most one way to decode codewords into strings

Question 2

How to show a code is not uniquely decipherable

Answer 2

find a counter example

Question 3

How to show a code is uniquely decipherable

Answer 3

Suppose a string of bits corresponds to at least one sequence of codewords in C . It suffices to uniquely identify the first codeword in the string. If so we can process the remainder substring as a shorter string. Then take cases.

Question 4

How to tell if a code is instantaneous

Answer 4

• if a codeword is contained in another codeword not instantaneous

Question 5

Instantaneous

Answer 5

A code C is instanteous if every codeword c = x₁x₂…xₗ∈C can be identified as soon as its last bit xₗ is recieved

Question 6

Prefix Free Informal

Answer 6

given any codeword non of its prefixes appear anywhere in the code

Question 7

How to prove a code is not prefix free

Answer 7

find a contradiction

Question 8

How to prove a code is prefix free

Answer 8

for each code c₁ show that c₁ is not a prefix of any of the other codes

Question 9

The converse of McMillans Theorem…

Answer 9

does not hold.

Question 10

McMillans Theorem

Answer 10

Let C={c₁,…,cₘ} be a prefix-free code and lᵢ:=|cᵢ| for all i∈[m]. Then, the sum from i=1 to m of 2⁻ˡi ≤ 1

Question 11

McMillans Theorem is..

Answer 11

best possible

Question 12

How to use McMillans Theorem to show a code is not prefix-free

Answer 12

1. assume for a contradiction it is prefix free
2. calculate the sum
3. The value calculated in >1 then it would contradict McMillans theorem

Question 13

How to use Krafts Theorem to show there is a prefix free code for given lengths

Answer 13

1. substitute the lengths in the inequality
2. show this is ≤1
3. so by Krafts theorem there exists a prefix free code C with codewords of the given length

Question 14

considering codeword lengths li there exists a prefix free r-ary code iff …

(r-ary => the alphabet has r objects)

Answer 14

the sum from i=1 to m of r⁻ˡi less than or equal to 1

Question 15

(n,d)-code vs [n,k]-code

Answer 15

(n,d) is a code of length n with minimum hamming distance d.
[n,k] is a code with length n and dimension (size of basis, no rows in generator matrix). Or a code where the source has strings of length k and is encoded to strings of length n (block).

Question 16

A code that is uniquely decipherable but not prefix free

Answer 16

0,01

Question 17

Triangle Inequality for hamming distances

Answer 17

dₕ(x,z)≤dₕ(x,y)+dₕ(z,y)

Question 18

expected value of x

Answer 18

np

Question 19

variance squared of x

Answer 19

np(1-p)