Communication - Chapter 1 - Definitions And Theorems

Question 1

[n]

Answer 1

{1,2,3,…,n}

Question 2

Channel Alphabet

Answer 2

A channel alphabet is a finite set of symbols

Question 3

Binary Code

Answer 3

A binary code C is a finite subset of {0,1}*

Question 4

Codeword

Answer 4

The elements c∈C

Question 5

|c|

Answer 5

The length of the codeword c. I.e. the number of bits in the string representing c

Question 6

Uniquely Decipherable (first definition)

Answer 6

A code C is uniquely decipherable if given any n>=1 and string of x₁x₂…xₙ∈{0,1}ⁿ there exists at most one sequence c₁c₂…cₘ∈C s.t. x₁x₂…xₙ=c₁c₂…cₘ

Question 7

instantaneous

Answer 7

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 8

prefix

Answer 8

A string x∈{0,1}* is a prefix of x’∈{0,1}* if there exists a non-empty string y∈{0,1}* s.t. x’ = xy

Question 9

prefix free code

Answer 9

A code C is prefix free if no codeword C is a prefix of another codeword in C. That is, if c = x₁x₂…xₗ∈C => c = x₁x₂…xᵢ∉C for all i∈[l-1]

Question 10

Theorem. Instantaneous and Prefix Free

Answer 10

A code C is instantaneous iff it is prefix free

Question 11

Theorem. Instantaeous and Uniquely Decipherable

Answer 11

Suppose C is instantaneous. Then C is uniqely decipherable.

Question 12

Tree

Answer 12

A Tree is a connected graph with no cycles

Question 13

rooted Tree

Answer 13

A rooted tree T is a tree with a distinguished vertex r which is called the root of T

Question 14

Parent

Answer 14

Given v∈V(T){r} the parent of v is the neighbour of v on the unique path from r to v

Question 15

children

Answer 15

The neighbours of v that are not v’s parent are its children

Question 16

leaves

Answer 16

vertices with no children

Question 17

edge-labelled binary tree

Answer 17

An edge labelled binary tree is a binary tree where each edge of the tree is given a label from {0,1} so that the edges from v to its children are given different labels.

Question 18

binary tree

Answer 18

A binary tree is a tee where each vertex has at most 2 children

Question 19

Lemma. code associated to an edge labelled binary tree

Answer 19

The associated code C of an edge labelled binary tree with m leaves is a prefix free code of size m

Question 20

associated tree T of a prefix-free code C

Answer 20

Let C be a prefix free code of size m. Its associated tree has m leaves.

Question 21

Lemma. tree associated to a prefix free code

Answer 21

Let C be a prefix free code of size m. Its associated tree has m leaves.

Question 22

proposition. correspondence between codes and binary trees.

Answer 22

There is a one-to-one correspondence between prefix-free codes of size m and an edge-labelled binary tree with m leaves.

Question 23

McMillans Theorem.

Answer 23

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 24

Kraft’s Theorem

Answer 24

Let l₁,…,lₘ∈ℕ s.t. the sum from i=1 to m 2⁻ˡi ≤ 1. Then there exists a prefix free code C of size m whose codewords have lengths l₁,…,lₘ

Question 25

Corollary. latter version of krafts

Answer 25

Consider any l₁,…,lₘ∈ℕ. There exists a prefix-free code C with codewords of length l₁,…,lₘ iff the sum from i=1 to m 2⁻ˡi ≤ 1

Question 26

Uniquely Decipherable def 2

Answer 26

Equivalently, a code is UD if given any codewords, c₁c₂…cₘd₁…dₘ₂∈C if c₁c₂…cₘ = d₁…dₘ₂=> m₁=m₂ and dᵢ=cᵢ for all i∈[m₁]