Communication - Chapter 5 - Defs and Theorems

Question 1

(n,d)-code

Answer 1

Let 1≤d≤n then an (n,d)-code C of length n and dₕ(C)≥d.

Question 2

(n,M,d)-code

Answer 2

Let 1≤d≤n then an (n,M,d)-code C is an (n,d)-code of size M.

Question 3

A(n,d)

Answer 3

For integer 1≤d≤n let A(n,d) be the largest M such that there exists an (n,M,d)-code.

Question 4

optimal (n,d)-code

Answer 4

An (n,d)-code is optimal if it has size A(n,d)

Question 5

sum code

Answer 5

Given a code C and xϵ𝔽₂ⁿ the sum code is defined as C + x := { c + x : cϵC}

Question 6

proposition 5.5. An optimal (n,d)-code always contains…

Answer 6

For every 1≤d≤n, there exists an optimal (n,d)-code C with (00…0)ϵC

Question 7

punctured code

Answer 7

Given a code C of length n and 1≤ℓ≤n the punctured code C(ℓ) of C is obtained from C by truncating the last ℓ bits of each codeword.
That is, C(ℓ) = {x₁x₂…xₙ₋ℓ: c=x₁x₂…xₙϵC}.

Question 8

weight

Answer 8

The weight of a string xϵ {0,1}ⁿ denoted w(x) is the number of ones in x.

Question 9

Parity Check

Answer 9

Given a code C, the parity check code Cbar of C is obtained by adding a 0 at the end of cϵC if w(c) is even or adding a 1 if w(c) is odd.
That is, Cbar = {x₁x₂…xₙxₙ₊₁ : c=x₁x₂…xₙϵC and xₙ₊₁=w(c)mod2}.

Question 10

proposition 5.11. dₕ(Cbar).

Answer 10

Given a code C.

(i) dₕ(Cbar) is even.
(ii) If dₕ(C) is odd then dₕ(Cbar) = dₕ(C) + 1.

Question 11

Theorem 5.12. size of largest (n+1,d+1)-code given the size of the larget (n,d)-code.

Answer 11

If d is odd then A(n,d)=A(n+1,d+1).

Question 12

Sphere Packing Bound

Answer 12

For 1≤d≤n we have A(n,d)≤2ⁿ/bⁿ⌊d-1/2⌋

Question 13

Sphere covering Bound

Answer 13

For 1≤d≤n we have A(n,d)≥2ⁿ/bⁿₔ₋₁

Question 14

Plotkins Bound

Answer 14

For 1≤d≤n with 2d>n we have A(n,d)≤2d/2d-n