Communication Chapter 2 - definitions and theorems

Question 1

source alphabet

Answer 1

The source alphabet S is a finite set of symbols, known as letters, which we use to write our message.

Question 2

entropy

Answer 2

Given a probability distribution p = (p₁,…,pₘ) the binary entropy is defined as H(P)= - the sum from i=1 to m of pᵢ log₂ pᵢ.
Given a random source S with probability distrubution p we define the entropy of S as H(S)=H(P)

Question 3

Deterministic

Answer 3

you know how a function behaves, i.e. the function is predictable

Question 4

H(P)

Answer 4

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

Question 5

Gibbs lemma

Answer 5

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 6

Theorem. 0≤H(P)≤logm.

Answer 6

let p = (p₁,…,pₘ) be a probability distribution. Then, 0≤H(P)≤logm.

Question 7

Source Encoding Scheme

Answer 7

A Source Encoding Scheme (or simply encoding) of S is an injective map f:S->{0,1}* i.e. a map that assigns each letter of S a unique string in {0,1}*.

Question 8

Code associated to an encoding

Answer 8

The code associated to the encoding is the image of f in {0,1}* and is denoted by C=C(f).

Question 9

prefix-free encoding

Answer 9

The encoding is prefix-free if the associated code is prefix-free.

Question 10

codeword of S

Answer 10

For every s∈S f(s) is the codeword of s

Question 11

Source decoding Scheme

Answer 11

A source decoding scheme (or simply decoding) is a map g:{0,1}*->S s.t. s=g(f(s)) for all s∈S

Question 12

Expected length of f

Answer 12

Suppose S={s₁,..,sₘ} is a random source with probability distrubution p = (p₁,…,pₘ) and an encoding f:S->{0,1}*. Let ℓ(f) be the random variable for the codeword f(s) where s is the letter produced by the source according to the probability distrubution p. Then the expected length of f denoted 𝔼(ℓ(f)) is defined as the expected value of ℓ(f). That is,
𝔼(ℓ(f))= the sum from i=1 to m of pᵢ |f(sᵢ)|

Question 13

optimal

Answer 13

Given a random source S a prefix free encoding f of S is optimal if it minimises he value of 𝔼(ℓ(f)) amongst all prefix-free encodings of S.

Question 14

Shannons Noiseless Encoding Theorem

Answer 14

Let S be a random source and f:S->{0,1}* be an optimal prefix-free encoding of S. Then, H(S)≤𝔼(ℓ(f))

Question 15

Huffman encoding procedure

Answer 15

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

Question 16

Theorem. Huffman Algorithm.

Answer 16

Let S={s₁,..,sₘ} is a random source with probability distribution p = (p₁,…,pₘ). The huffman encoding fₕ is an optimal prefix-free encoding of S; that is, for all prefix-free encodings f of S we have 𝔼(ℓ(fₕ))≤𝔼(ℓ(f))

Question 17

Proposition. For Huffmans proof.

Answer 17

Let S={s₁,..,sₘ} is a random source with probability distribution p = (p₁,…,pₘ) and suppose that p₁≥…≥pₘ. Then there exists an optimal prefix-free encoding f* of S with ℓᵢ = |f*(sᵢ)| satisfying:

(a) ℓ₁≤…≤ℓₘ
b) ℓₘ = ℓₘ₋₁
(c) f(sₘ₋₁) and f(sₘ) only differ in their last bit