Basics in Coding Theory (Ikke et emne)

Question 1

Block code

Answer 1

A block code C is a set of M codewords
C = {c_1, c_2, … , c_M }
c_i = (c_{i0}, c_{i1}, … , c_{in−1} )
where the codewords are n-tuples and we refer to n as the length of the code. The elements c_{ij} belong to a finite alphabet of q symbols.

Question 2

Linear block code

Answer 2

A linear (n, k) block code C, is a k-dimensional subspace of the vector space V
The code is called linear since if C is a subspace we have
c_i ∈ C ∧ c_j ∈ C ⇒ c_i + c_j ∈ C
c_i ∈ C ∧ f ∈ F ⇒ f c_i ∈ C

Question 3

Generator matrix

Answer 3

A generator matrix G of an (n, k) code C is a k × n matrix whose rows are linearly independent. If the information is the vector u of length k, we can state the encoding rule as
c = uG
The same code, in the sense of a set of words or a vector space, may be described by different generator matrices or bases of the vector space. We usually just take one that is convenient for our purpose. Since G has rank k, we can obtain a convenient form of G by row operations in such a way that k columns form a k × k identity matrix I . We often assume that this matrix can be chosen as the first k columns and write the generator matrix as
G = (I, A)
This form of the generator matrix gives a systematic encoding of the information.

Question 4

Parity check matrix

Answer 4

A parity check, the vector h of length n, satisfies
Gh^T = 0
where h^T denotes the transpose of h.
A parity check matrix H for an (n, k) code C is an (n − k) × n matrix whose rows are linearly independent parity checks, thus
GH^T = 0
and
H = (−A^T , I).

Question 5

Hamming weight

Answer 5

The Hamming weight of a vector x, denoted wH (x), is equal to the number of nonzero coordinates.
In an (n, k) code the minimum distance is equal to the minimum weight of a nonzero codeword.

Question 6

t-error correcting

Answer 6

A code is t-error correcting if for any two codewords c_i ≠ c_j , and for any error patterns e_1 and e_2 of weight ≤ t, we have c_i + e_1 ≠ c_j + e_2.
An (n, k) code is t-error correcting if and only if t < d / 2 .

Question 7

Hamming distance

Answer 7

The Hamming distance between two vectors x and y, denoted d_H(x, y) is the number of coordinates where they differ.

The minimum distance of a code, d, is the minimum Hamming distance between any pair of different codewords.

In an (n, k) code the minimum distance is equal to the minimum weight of a nonzero codeword.

Let C be an (n, k) code with parity check matrix H . The minimum distance of C equals the minimum number of linearly dependent columns of H .

Question 8

Dual code

Answer 8

The code spanned by the rows of H is what is called the dual code C^⊥ defined by
C^⊥ = {x ∈ F^n |x · c = 0 ∀c ∈ C}
It is often convenient to talk about the rate of a code R = k/n . Thus the dual code has rate 1 − R.

Question 9

Biorthogonal code

Answer 9

A biorthogonal code is the dual of the binary extended Hamming code.
The biorthogonal code has length n = 2^m and dimension k = m + 1. It can be seen that the code consists of the all 0s vector, the all 1s vector and 2n − 2 vectors of weight n/2.