Communication Chapter 6 defs and theorems

Question 1

Linear [n,k]-code

Answer 1

A linear [n,k]-code is a subspace of 𝔽ⁿ₂ of dimension k.

Question 2

length of linear [n,k]-code

Answer 2

n

Question 3

dimension/rank of linear [n,k]-code

Answer 3

k

Question 4

Lemma 6.2. Hamming distance and weight.

Answer 4

For any x,y∈𝔽ⁿ₂ we have that dₕ(x,y)=w(x+y)

Question 5

Proposition 6.5. minimum hamming distance and minumum weight

.

Answer 5

If C is a linear code then the minimum hamming distance of C is the minimum weight of a codeword c∈C

Question 6

basis of a subspace

Answer 6

A basis of a subspace C⊆𝔽ⁿ₂ is a collection of vectors c₁,..,cₖ s.t.

(1) They are linearly independent
(2) They span C

Question 7

basis of a linear [n,k]-code

Answer 7

A basis of a linear [n,k]-code c is a set of k vectors c₁,…,cₖ∈C s.t. for all c∈C there exists λ₁,…,λₖ∈𝔽₂ s.t. c = λ₁c₁+…+λₖcₖ.

Question 8

lemma 6.7. Size of a linear code.

Answer 8

Every linear [n,k]-code C satisfies |C|=2ᵏ.

Question 9

generator matrix

Answer 9

Let C be a linear [n,k]-code and {c₁,…,cₖ} be an ordered basis of C. The associated generator matrix of C is a kxn matrix where rows correspond to c₁,…,cₖ.

Question 10

normal form

Answer 10

Given a linear [n,k]-code C a generator matrix B is in normal form if it is in the form B = (Iₖ|A) where Iₖ is the kxk identity matrix.

Question 11

equivilent

Answer 11

Two codes C₁ and C₂ are equivilent if there exists a generator matrix B₁ of C₁ and B₂ of C₂ s.t. B₁ can be obtained from B₂ by a permutation of the columns.

Question 12

Theorem 6.14. equivilent codes with normal form.

Answer 12

For every linear [n,k]-code C there exists an equivilent linear [n,k]-code C₀ that has a normal form.

Question 13

Parity check matrix

Answer 13

Let C be a linear [n,k]-code. A parity check matrix H of C is an (n-k)xn matrix such that C={c∈𝔽ⁿ₂: Hcᵀ = 0}

Question 14

Theorem 6.16. The parity check matrix from generator matrix.

Answer 14

Let C be a linear [n,k]-code and suppose C has normal form B₀=(Iₖ|A). Then H=(Aᵀ|Iₙ₋ₖ).

Question 15

Theorem 6.18. minimum hamming distance from parity check matrix.

Answer 15

Let C be a linear [n,k]-code with parity check matrix H. If r is the smallest integer for which there exists r linearly dependent columns in H, then dₕ(c)=r

Question 16

Hamming code of order r

Answer 16

Let r∈ℕ. The hamming code of order r is a linear code whose parity check matrix H has as its columns all 2ʳ-1 non-zero vectors of length r

Question 17

proposition 6.21. properties of hamming code of order r.

Answer 17

The hamming code of order r is a linear [n,k]-code C with

(i) n = 2ʳ-1 (length of codewords) k= 2ʳ-r-1 (dimension of codewords)
(ii) |C|=2²ʳ⁻ʳ⁻¹ and R(C) = 1 - r/(2ʳ-1)
(iii) dₕ(c)=3

Question 18

proposition 6.22. decoding hamming codes.

Answer 18

Let C be the hamming code of order r with parity check matrix H. For every x∈𝔽ⁿ₂ there exists a unique c∈C such that dₕ(x,c)≤1.
Moreover, if x is not in C and i is the position where x and c differ then Hxᵀ=hᵢ where hᵢ is the ith column of H

Question 19

Hamming decoding scheme for x∈𝔽ⁿ₂

Answer 19

1. calculate s=Hxᵀ
2. Decode it
   (a) is s=0 then x∈C so return x
   (b) if s≠0 then x is not in C and by prop 6.22 there exists i such that s=hᵢ so return x+eᵢ

Question 20

coset

Answer 20

Let C be a linear [n,k]-code with parity check matrix H. Then for any vector s∈𝔽ⁿ⁻ᵏ₂ we let the coset of s be defined as follows:
Q(s) := {x∈𝔽ⁿ₂: Hxᵀ =s}

Question 21

syndrome of x

Answer 21

If x∈Q(s), then we say s is the syndrome of x

Question 22

Equipartition

Answer 22

disjoint sets of the same size

Question 23

coset leader

Answer 23

For every s∈𝔽ⁿ⁻ᵏ₂ a coset leader q(s) is a vector in Q(s) with smallest weight. That is q(s)∈Q(s) satisfies w(q(s)) = min w(x) for all x∈Q(s).

Question 24

Theorem 6.27. Minimum Distance Decoding via a coset leader.

Answer 24

Let C be a linear [n,k]-code. If x∈Q(s) and q(s) is a coset leader of Q(s) then c=x+q(s)∈C and c is the nearest codeword to x.

Question 25

Syndrome Decoding Scheme for x∈𝔽ⁿ₂

Answer 25

1. Calculate the syndrome of x, Hxᵀ =s
2. Choose a coset leader q(s) of Q(s)
3. Decode x as x+q(s)

Question 26

Theorem 6.29. Gilbert-Var Shamov bound.

Answer 26

Let 2≤d≤n and let k be the largest integer that satisfies 2ᵏ<2ⁿ/bⁿₔ₋₁. Then, A(n,d)≥2ᵏ.