Part II
Linear codes
CHAPTER 2: Linear codes
ABSTRACT
Most of the important codes are special types of so-called linear codes.
Linear codes are of very large importance because they have
very concise description,
very nice properties,
very easy encoding
and,
in principle, easy to describe decoding.
prof. Jozef Gruska IV054 2. Linear codes 2/39
Linear codes
Linear codes are special sets of words of the length n over an alphabet {0, .., q − 1},
where q is a power of prime. Since now on sets of words Fn
q will be considered as vector
spaces V (n, q) of vectors of length n with elements from the set {0, .., q − 1} and
arithmetical operations will be taken modulo q.
Definition A subset C ⊆ V (n, q) is a linear code if
1 u + v ∈ C for all u, v ∈ C
2 au ∈ C for all u ∈ C, a ∈ GF(q)
Example Codes C1, C2, C3 introduced in Lecture 1 are linear codes.
Lemma A subset C ⊆ V (n, q) is a linear code if one of the following conditions is
satisfied
1 C is a subspace of V (n, q)
2 sum of any two codewords from C is in C (for the case q = 2)
If C is a k-dimensional subspace of V (n, q), then C is called [n, k]-code. It has qk
codewords. If minimal distance of C is d, then it is called [n, k, d] code.
Linear codes are also called ”group codes”.
prof. Jozef Gruska IV054 2. Linear codes 3/39
Exercise
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11}
C2 = {000, 011, 101, 110}
C3 = {00000, 01101, 10110, 11011}
C5 = {101, 111, 011}
C6 = {000, 001, 010, 011}
C7 = {0000, 1001, 0110, 1110}
How to create a linear code
Notation If S is a set of vectors of a vector space, then let S be the set of all linear
combinations of vectors from S.
Theorem For any subset S of a linear space, S is a linear space that consists of the
following words:
the zero word,
all words in S,
all sums of two or more words in S.
Example S = {0100, 0011, 1100}
S = {0000, 0100, 0011, 1100, 0111, 1011, 1000, 1111}.
prof. Jozef Gruska IV054 2. Linear codes 4/39
Basic properties of linear codes
Notation: w(x) (weight of x) denotes the number of non-zero entries of x.
Lemma If x, y ∈ V (n, q), then h(x, y) = w(x − y).
Proof x − y has non-zero entries in exactly those positions where x and y differ.
Theorem Let C be a linear code and let weight of C, notation w(C), be the smallest of
the weights of non-zero codewords of C. Then h(C) = w(C).
Proof There are x, y ∈ C such that h(C) = h(x, y). Hence h(C) = w(x − y) ≥ w(C).
On the other hand, for some x ∈ C
w(C) = w(x) = h(x, 0) ≥ h(C).
Consequence
If C is a code with m codewords, then in order to determine h(C) one has to make`m
2
´
= θ(m2
) comparisons in the worth case.
If C is a linear code, then in order to compute h(C), m − 1 comparisons are enough.
prof. Jozef Gruska IV054 2. Linear codes 5/39
Basic properties of linear codes
If C is a linear [n, k]-code, then it has a basis consisting of k codewords.
Example
Code
C4 = {0000000, 1111111, 1000101, 1100010,
0110001, 1011000, 0101100, 0010110,
0001011, 0111010, 0011101, 1001110,
0100111, 1010011, 1101001, 1110100}
has the basis
{1111111, 1000101, 1100010, 0110001}.
How many different bases has a linear code?
Theorem A binary linear code of dimension k has
1
k!
Qk−1
i=0 (2k
− 2i
)
bases.
prof. Jozef Gruska IV054 2. Linear codes 6/39
Advantages and disadvantages of linear codes I.
Advantages - big.
1 Minimal distance h(C) is easy to compute if C is a linear code.
2 Linear codes have simple specifications.
To specify a non-linear code usually all codewords have to be listed.
To specify a linear [n, k]-code it is enough to list k codewords )of a basis).
Definition A k × n matrix whose rows form a basis of a linear [n, k]-code (subspace) C is
said to be the generator matrix of C.
Example The generator matrix of the code
C2 =
8
>><
>>:
0 0 0
0 1 1
1 0 1
1 1 0
9
>>=
>>;
is
„
0 1 1
1 0 1
«
and of the code
C4 = is
0
B
B
@
1 1 1 1 1 1 1
1 0 0 0 1 0 1
1 1 0 0 0 1 0
0 1 1 0 0 0 1
1
C
C
A
3 There are simple encoding/decoding procedures for linear codes.
prof. Jozef Gruska IV054 2. Linear codes 7/39
Advantages and disadvantages of linear codes II.
Disadvantages of linear codes are small:
1 Linear q-codes are not defined unless q is a prime
power.
2 The restriction to linear codes might be a restriction to
weaker codes than sometimes desired.
prof. Jozef Gruska IV054 2. Linear codes 8/39
Equivalence of linear codes
Definition Two linear codes GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the positions of the code;
(b) multiplication of symbols appearing in a fixed position by a non-zero scalar.
Theorem Two k × n matrices generate equivalent linear [n, k]-codes over GF(q) if one
matrix can be obtained from the other by a sequence of the following operations:
(a) permutation of the rows
(b) multiplication of a row by a non-zero scalar
(c) addition of one row to another
(d) permutation of columns
(e) multiplication of a column by a non-zero scalar
Proof Operations (a) - (c) just replace one basis by another. Last two operations convert
a generator matrix to one of an equivalent code.
prof. Jozef Gruska IV054 2. Linear codes 9/39
Equivalence of linear codes
Theorem Let G be a generator matrix of an [n, k]-code. Rows of G are then linearly
independent .By operations (a) - (e) the matrix G can be transformed into the form:
[Ik |A] where Ik is the k × k identity matrix, and A is a k × (n − k) matrix.
Example
0
B
B
@
1 1 1 1 1 1 1
1 0 0 0 1 0 1
1 1 0 0 0 1 0
1 1 1 0 0 0 1
1
C
C
A →
0
B
B
@
1 1 1 1 1 1 1
0 1 1 1 0 1 0
0 0 1 1 1 0 1
0 0 0 1 1 1 0
1
C
C
A →
0
B
B
@
1 0 0 0 1 0 1
0 1 1 1 0 1 0
0 0 1 1 1 0 1
0 0 0 1 1 1 0
1
C
C
A →
0
B
B
@
1 0 0 0 1 0 1
0 1 0 0 1 1 1
0 0 1 1 1 0 1
0 0 0 1 1 1 0
1
C
C
A →
prof. Jozef Gruska IV054 2. Linear codes 10/39
Encoding with a linear code
is a vector × matrix multiplication
Let C be a linear [n, k]-code over GF(q) with a generator matrix G.
Theorem C has qk
codewords.
Proof Theorem follows from the fact that each codeword of C can be expressed uniquely
as a linear combination of the basis vectors.
Corollary The code C can be used to encode uniquely qk
messages.
Let us identify messages with elements V (k, q).
Encoding of a message u = (u1, . . . , uk ) with the code C:
u · G =
Pk
i=1 ui ri where r1, . . . , rk are rows of G.
Example Let C be a [7, 4]-code with the generator matrix
G=
2
6
6
4
1 0 0 0 1 0 1
0 1 0 0 1 1 1
0 0 1 0 1 1 0
0 0 0 1 0 1 1
3
7
7
5
A message (u1, u2, u3, u4) is encoded as:???
For example:
0 0 0 0 is encoded as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ?
1 0 0 0 is encoded as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ?
1 1 1 0 is encoded as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ?
prof. Jozef Gruska IV054 2. Linear codes 11/39
Uniqueness of encodings
with linear codes
Theorem If G = {wi }k
i=1 is a generator matrix of a binary linear code C of length n and
dimension k, then
v = uG
ranges over all 2k
codewords of C as u ranges over all 2k
words of length k.
Therefore
C = {uG|u ∈ {0, 1}k
}
Moreover
u1G = u2G
if and only if
u1 = u2.
Proof If u1G–u2G = 0, then
0 =
Pk
i=1 u1,i wi −
Pk
i=1 u2,i wi =
Pk
i=1(u1,i − u2,i )wi
And, therefore, since wi are linearly independent, u1 = u2.
prof. Jozef Gruska IV054 2. Linear codes 12/39
Decoding of linear codes
Decoding problem: If a codeword: x = x1 . . . xn is sent and the word y = y1 . . . yn is
received, then e = y–x = e1 . . . en is said to be the error vector. The decoder must
decide, from y, which x was sent, or, equivalently, which error e occurred.
To describe main Decoding method some technicalities have to be introduced
Definition Suppose C is an [n, k]-code over GF(q) and u ∈ V (n, q). Then the set
u + C = {u + x|x ∈ C}
is called a coset (u-coset) of C in V (n, q).
Example Let C = {0000, 1011, 0101, 1110}
Cosets:
0000 + C = C,
1000 + C = {1000, 0011, 1101, 0110},
0100 + C = {0100, 1111, 0001, 1010} = 0001 + C,
0010 + C = {0010, 1001, 0111, 1100}.
Are there some other cosets in this case?
Theorem Suppose C is a linear [n, k]-code over GF(q). Then
(a) every vector of V (n, k) is in some coset of C,
(b) every coset contains exactly qk
elements,
(c) two cosets are either disjoint or identical.
prof. Jozef Gruska IV054 2. Linear codes 13/39
Nearest neighbour decoding scheme:
Each vector having minimum weight in a coset is called a coset leader.
1. Design a (Slepian) standard array for an [n, k]-code C - that is a qn−k
× qk
array of
the form:
codewords coset leader codeword 2 . . . codeword 2k
coset leader + . . . +
. . . + + +
coset leader + . . . +
coset leader
Example
0000 1011 0101 1110
1000 0011 1101 0110
0100 1111 0001 1010
0010 1001 0111 1100
A word y is decoded as codeword of the first row of the column in which y occurs.
Error vectors which will be corrected are precisely coset leaders!
In practice, this decoding method is too slow and requires too much memory.
prof. Jozef Gruska IV054 2. Linear codes 14/39
Probability of good error correction
What is the probability that a received word will be decoded correctly - that is as the
codeword that was sent (for binary linear codes and binary symmetric channel)?
Probability of an error in the case of a given error vector of weight i is
pi
(1 − p)n−i
.
Therefore, it holds.
Theorem Let C be a binary [n, k]-code, and for i = 0, 1, . . . , n let αi be the number of
coset leaders of weight i. The probability Pcorr (C) that a received vector when decoded
by means of a standard array is the codeword which was sent is given by
Pcorr (C) =
Pn
i=0 αi pi
(1 − p)n−i
.
Example For the [4, 2]-code of the last example
α0 = 1, α1 = 3, α2 = α3 = α4 = 0.
Hence
Pcorr (C) = (1 − p)4
+ 3p(1 − p)3
= (1 − p)3
(1 + 2p).
If p = 0.01, then Pcorr = 0.9897
prof. Jozef Gruska IV054 2. Linear codes 15/39
Probability of good error detection
Suppose a binary linear code is used only for error detection.
The decoder will fail to detect errors which have occurred if the received word y is a
codeword different from the codeword x which was sent, i. e. if the error vector
e = y − x is itself a non-zero codeword.
The probability Pundetect (C) that an incorrect codeword is received is given by the
following result.
Theorem Let C be a binary [n, k]-code and let Ai denote the number of codewords of C
of weight i. Then, if C is used for error detection, the probability of an incorrect message
being received is
Pundetect (C) =
Pn
i=0 Ai pi
(1 − p)n−i
.
Example In the case of the [4, 2] code from the last example
A2 = 1 A3 = 2
Pundetect (C) = p2
(1 − p)2
+ 2p3
(1 − p) = p2
− p4
.
For p = 0.01
Pundetect (C) = 0.000099.
prof. Jozef Gruska IV054 2. Linear codes 16/39
Dual codes
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in V (n, q) is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In V (4, 2) : 1001 · 1001 = 0
In V (4, 3) : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal.
Properties If u, v, w ∈ V (n, q), λ, µ ∈ GF(q), then
u · v = v · u, (λu + µv) · w = λ(u · w) + µ(v · w).
Given a linear [n, k]-code C, then the dual code of C, denoted by C⊥
, is defined by
C⊥
= {v ∈ V (n, q) | v · u = 0 if u ∈ C}.
Lemma Suppose C is an [n, k]-code having a generator matrix G. Then for v ∈ V (n, q)
v ∈ C⊥
⇔ vG = 0,
where G denotes the transpose of the matrix G.
Proof Easy.
prof. Jozef Gruska IV054 2. Linear codes 17/39
PARITE CHECKS versus ORTHOGONALITY
For understanding of the role the parity checks play for linear codes, it is important to
understand relation between orthogonality and special parity checks.
If words x and y are orthogonal, then the word y has even number of ones (1’s) in the
positions determined by ones (1’s) in the word x.
This implies that if words x and y are orthogonal, then x is a parity check word for y and
y is a parity check word for x.
Exercise: Let the word
100001
be orthogonal to a set S of binary words of length 6. What can we say about the words
in S?
prof. Jozef Gruska IV054 2. Linear codes 18/39
EXAMPLE
For the [n, 1]-repetition code C, with the generator matrix
G = (1, 1, . . . , 1)
the dual code C⊥
is [n, n − 1]-code with the generator matrix G⊥
, described by
G⊥
=
0
B
B
@
1 1 0 0 . . . 0
1 0 1 0 . . . 0
. . .
1 0 0 0 . . . 1
1
C
C
A
prof. Jozef Gruska IV054 2. Linear codes 19/39
Parity check matrices
Example If
C5 =
0
B
B
@
0 0 0 0
1 1 0 0
0 0 1 1
1 1 1 1
1
C
C
A, then C⊥
5 = C5.
If
C6 =
0
B
B
@
0 0 0
1 1 0
0 1 1
1 0 1
1
C
C
A, then C⊥
6 =
„
0 0 0
1 1 1
«
.
Theorem Suppose C is a linear [n, k]-code over GF(q), then the dual code C⊥
is a linear
[n, n − k]-code.
Definition A parity-check matrix H for an [n, k]-code C is a generator matrix of C⊥
.
prof. Jozef Gruska IV054 2. Linear codes 20/39
Parity check matrices
Definition A parity-check matrix H for an [n, k]-code C is a generator matrix of C⊥
.
Theorem If H is parity-check matrix of C, then
C = {x ∈ V (n, q)|xH = 0},
and therefore any linear code is completely specified by a parity-check matrix.
Example Parity-check matrix for
C5 is
„
1 1 0 0
0 0 1 1
«
and for
C6 is
`
1 1 1
´
The rows of a parity check matrix are parity checks on codewords. They say that certain
linear combinations of elements of every codeword are zeros.
prof. Jozef Gruska IV054 2. Linear codes 21/39
Syndrome decoding
Theorem If G = [Ik |A] is the standard form generator matrix of an [n, k]-code C, then a
parity check matrix for C is H = [−A |In−k ].
Example
Generator matrix G =
˛
˛
˛
˛
˛
˛
˛
˛
I4
˛
˛
˛
˛
˛
˛
˛
˛
1 0 1
1 1 1
1 1 0
0 1 1
˛
˛
˛
˛
˛
˛
˛
˛
⇒ parity check m. H =
˛
˛
˛
˛
˛
˛
1 1 1 0
0 1 1 1
1 1 0 1
˛
˛
˛
˛
˛
˛
I3
˛
˛
˛
˛
˛
˛
Definition Suppose H is a parity-check matrix of an [n, k]-code C. Then for any
y ∈ V (n, q) the following word is called the syndrome of y:
S(y) = yH .
Lemma Two words have the same syndrom iff they are in the same coset.
Syndrom decoding Assume that a standard array of a code C is given and, in addition,
let in the last two columns the syndrom for each coset be given.
0 0 0 0
1 0 0 0
0 1 0 0
0 0 1 0
˛
˛
˛
˛
˛
˛
˛
˛
1 0 1 1
0 0 1 1
1 1 1 1
1 0 0 1
˛
˛
˛
˛
˛
˛
˛
˛
0 1 0 1
1 1 0 1
0 0 0 1
0 1 1 1
˛
˛
˛
˛
˛
˛
˛
˛
1 1 1 0
0 1 1 0
1 0 1 0
1 1 0 0
˛
˛
˛
˛
˛
˛
˛
˛
0 0
1 1
0 1
1 0
When a word y is received, compute S(y) = yH , locate S(y) in the “syndrom column”,
and then locate y in the same row and decode y as the codeword in the same column
and in the first row.
prof. Jozef Gruska IV054 2. Linear codes 22/39
KEY OBSERVATION for SYNDROM COMPUTATION
When preparing a “syndrome decoding” it is sufficient to store only two columns: one for
coset leaders and one for syndromes.
Example
coset leaders syndromes
l(z) z
0000 00
1000 11
0100 01
0010 10
Decoding procedure
Step 1 Given y compute S(y).
Step 2 Locate z = S(y) in the syndrome column.
Step 3 Decode y as y − l(z).
Example If y = 1111, then S(y) = 01 and the above decoding procedure produces
1111–0100 = 1011.
Syndrom decoding is much faster than searching for a nearest codeword to a received
word. However, for large codes it is still too inefficient to be practical.
In general, the problem of finding the nearest neighbour in a linear code is NP-complete.
Fortunately, there are important linear codes with really efficient decoding.
prof. Jozef Gruska IV054 2. Linear codes 23/39
Hamming codes
An important family of simple linear codes that are easy to encode and decode, are
so-called Hamming codes.
Definition Let r be an integer and H be an r × (2r
− 1) matrix columns of which are
non-zero distinct words from V (r, 2). The code having H as its parity-check matrix is
called binary Hamming code and denoted by Ham(r, 2).
Example
Ham(2, 2) = H =
»
1 1 0
1 0 1
–
⇒ G =
ˆ
1 1 1
˜
Ham(3, 2) = H =
2
4
0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 1 0 1 0 0 1
3
5 ⇒ G =
2
6
6
4
1 0 0 0 0 1 1
0 1 0 0 1 0 1
0 0 1 0 1 1 0
0 0 0 1 1 1 1
3
7
7
5
Theorem Hamming code Ham(r, 2)
is [2r
− 1, 2r
–1 − r]-code,
has minimum distance 3,
is a perfect code.
Properties of binary Hamming codes Coset leaders are precisely words of weight ≤ 1.
The syndrome of the word 0 . . . 010 . . . 0 with 1 in j-th position and 0 otherwise is the
transpose of the j-th column of H.
prof. Jozef Gruska IV054 2. Linear codes 24/39
Hamming codes - decoding
Decoding algorithm for the case the columns of H are arranged in the order of increasing
binary numbers the columns represent.
Step 1 Given y compute syndrome S(y) = yH .
Step 2 If S(y) = 0, then y is assumed to be the codeword sent.
Step 3 If S(y) = 0, then assuming a single error, S(y) gives the binary position of
the error.
prof. Jozef Gruska IV054 2. Linear codes 25/39
Example
For the Hamming code given by the parity-check matrix
H =
2
4
0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1
3
5
and the received word
y = 1101011,
we get syndrome
S(y) = 110
and therefore the error is in the sixth position.
Hamming code was discovered by Hamming (1950), Golay (1950).
It was conjectured for some time that Hamming codes and two so called Golay codes are
the only non-trivial perfect codes.
Comment
Hamming codes were originally used to deal with errors in long-distance telephon calls.
prof. Jozef Gruska IV054 2. Linear codes 26/39
ADVANTAGES of HAMMING CODES
Let a binary symmetric channel be used which with probability q correctly transfers a
binary symbol.
If a 4-bit message is transmitted through such a channel, then correct transmission of the
message occurs with probability q4
.
If Hamming (7, 4, 3) code is used to transmit a 4-bit message, then probability of correct
decoding is
q7
+ 7(1 − q)q6
.
In case q = 0.9 the probability of correct transmission is 0.6561 in the case no error
correction is used and 0.8503 in the case Hamming code is used - an essential
improvement.
prof. Jozef Gruska IV054 2. Linear codes 27/39
IMPORTANT CODES
Hamming (7, 4, 3)-code. It has 16 codewords of length 7. It can be used to send
27
= 128 messages and can be used to correct 1 error.
Golay (23, 12, 7)-code. It has 4 096 codewords. It can be used to transmit 8 388 608
messages and can correct 3 errors.
Quadratic residue (47, 24, 11)-code. It has
16 777 216 codewords
and can be used to transmit
140 737 488 355 238 messages
and correct 5 errors.
Hamming and Golay codes are the only non-trivial perfect codes.
prof. Jozef Gruska IV054 2. Linear codes 28/39
GOLAY CODES - DESCRIPTION
Golay codes G24 and G23 were used by Voyager I and Voyager II to transmit color pictures
of Jupiter and Saturn. Generation matrix for G24 has the form
G =
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1
0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 0
0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1
0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1
0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 1 0
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
G24 is (24, 12, 8)-code and the weights of all codewords are multiples of 4. G23 is obtained
from G24 by deleting last symbols of each codeword of G24. G23 is (23, 12, 7)-code.
prof. Jozef Gruska IV054 2. Linear codes 29/39
GOLAY CODES - CONSTRUCTION
Matrix G for Golay code G24 has actually a simple
and regular construction.
The first 12 columns are formed by a unitary
matrix I12, next column has all 1’s.
Rows of the last 11 columns are cyclic
permutations of the first row which has 1 at those
positions that are squares modulo 11, that is
0, 1, 3, 4, 5, 9.
prof. Jozef Gruska IV054 2. Linear codes 30/39
REED-MULLER CODES
Reed-Muller codes form a family of codes defined recursively with interesting properties
and easy decoding.
If D1 is a binary [n, k1, d1]-code and D2 is a binary [n, k2, d2]-code, a binary code C of
length 2n is defined as follows C = {u|u + v, where u ∈ D1, v ∈ D2}.
Lemma C is [2n, k1 + k2, min{2d1, d2}]-code and if Gi is a generator matrix for Di ,
i = 1, 2, then
»
G1 G2
0 G2
–
is a generator matrix for C.
Reed-Muller codes R(r, m), with 0 ≤ r ≤ m are binary codes of length n = 2m
.R(m, m)
is the whole set of words of length n, R(0, m) is the repetition code.
If 0 < r < m, then R(r + 1, m + 1) is obtained from codes R(r + 1, m) and R(r, m) by
the above construction.
Theorem The dimension of R(r, m) equals 1 +
`m
1
´
+ . . . +
`m
r
´
. The minimum weight of
R(r, m) equals 2m−r
. Codes R(m − r − 1, m) and R(r, m) are dual codes.
prof. Jozef Gruska IV054 2. Linear codes 31/39
Singleton Bound
Singleton bound: Let C be a q-ary (n, M, d)-code.
Then
M ≤ qn−d+1
.
Proof Take some d −1 coordinates and project all codewords to the resulting coordinates.
The resulting codewords are all different and therefore M cannot be larger than the
number of q-ary words of length n − d − 1.
Codes for which M = qn−d+1
are called MDS-codes (Maximum Distance Separable).
Corollary: If C is a q-ary linear [n, k, d]-code, then
k + d ≤ n + 1.
prof. Jozef Gruska IV054 2. Linear codes 32/39
Shortening and puncturing of linear codes
Let C be a q-ary linear [n, k, d]-code. Let
D = {(x1, . . . , xn−1)|(x1, . . . , xn−1, 0) ∈ C}.
Then D is a linear [n − 1, k − 1, d]-code - a shortening of the code C.
Corollary: If there is a q-ary [n, k, d]-code, then shortening yields a q-ary
[n − 1, k − 1, d]-code.
Let C be a q-ary [n, k, d]-code. Let
E = {(x1, . . . , xn−1)|(x1, . . . , xn−1, x) ∈ C, for some x ≤ q},
then E is a linear [n − 1, k, d − 1]-code - a puncturing of the code C.
Corollary: If there is a q-ary [n, k, d]-code with d > 1, then there is a q-ary
[n − 1, k, d − 1]-code.
prof. Jozef Gruska IV054 2. Linear codes 33/39
Reed-Solomon Codes
An important example of MDS-codes are q-ary Reed-Solomon codes RSC(k, q), for
k ≤ q.
They are codes generator matrix of which has rows labelled by polynomials Xi
,
0 ≤ i ≤ k − 1, columns by elements 0, 1, . . . , q − 1 and the element in a row labelled by a
polynomial p and in a column labelled by an element u is p(u).
RSC(k, q) code is [q, k, q − k + 1] code.
Example Generator matrix for RSC(3, 5) code is
2
4
1 1 1 1 1
0 1 2 3 4
0 1 4 4 1
3
5
Interesting property of Reed-Solomon codes:
RSC(k, q)⊥
= RSC(q − k, q).
Reed-Solomon codes are used in digital television, satellite communication, wireless
communication, barcodes, compact discs, DVD,. . . They are very good to correct burst
errors - such as ones caused by solar energy.
prof. Jozef Gruska IV054 2. Linear codes 34/39
Soccer Games Betting System
Ternary Golay code with parameters (11, 729, 5)
can be used to bet for results of 11 soccer games
with potential outcomes 1 (if home team wins), 2
(if guests win) and 3 (in case of a draw).
If 729 bets are made, then at least one bet has at
least 9 results correctly guessed.
In case one has to bet for 13 games, then one can
usually have two games with pretty sure outcomes
and for the rest one can use the above ternary
Golay code.prof. Jozef Gruska IV054 2. Linear codes 35/39
LDPC (Low-Density Parity Check) - codes
A LDPC code is a binary linear code whose parity check matrix is very sparse - it
contains only very few 1’s.
A linear [n, k] code is a regular [n, k, r, c] LDPC code if r << n, c << n − k and its
parity-check matrix has exactly r 1’s in each row and exactly c 1’s in each column.
In the last years LDPC codes are replacing in many important applications other types of
codes for the following reasons:
1 LDPC codes are in principle also very good channel codes, so called Shannon
capacity approaching codes, they allow the noise threshold to be set arbitrarily
close to the theoretical maximum - to Shannon limit - for symmetric channel.
2 Good LDPC codes can be decoded in time linear to their block length using special
(for example ”iterative belief propagation”) approximation techniques.
3 Some LDPC codes are well suited for implementations that make heavy use of
parallelism.
Parity-check matrices for LDPC codes are often (pseudo)-randomly generated, subject to
sparsity constrains. Such LDPC codes are proven to be good with a high probability.
prof. Jozef Gruska IV054 2. Linear codes 36/39
Discovery and applications of LDOC codes
LDPC codes were discovered in 1960 by R.C.
Gallager in his PhD thesis, but ignored till 1996
when linear time decoding methods were
discovered for some of them.
LDPC codes are used for: deep space
communication; digital video broadcasting;
10GBase-T Ethernet, which sends data at 10
gigabits per second over Twisted-pair cables;
Wi-Fi standard,....
prof. Jozef Gruska IV054 2. Linear codes 37/39
Tanner graph representation of LDPC codes
An [n, k] LDPC code can be represented by a bipartite graph between a set of n top
”variable-nodes (v-nodes)” and a set of bottom (n − k) ”constrain nodes (c-nodes)”.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
The corresponding parity check matrix has n − k rows and n columns and i-th column
has 1 in the j-th row exactly in case if i-th v-node is connected to j-th c-node.
H =
0
@
1 1 1 1 0 0
0 0 1 1 0 1
1 0 0 1 1 0
1
A
prof. Jozef Gruska IV054 2. Linear codes 38/39
Tanner graphs - continuation
Valid codewords for the LDPC-code with Tanner graph
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
with parity check matrix
H =
0
@
1 1 1 1 0 0
0 0 1 1 0 1
1 0 0 1 1 0
1
A
have to satisfy constrains
a1 + a2 + a3 + a4 = 0
a3 + a4 + a6 = 0
a1 + a4 + a5 = 0
prof. Jozef Gruska IV054 2. Linear codes 39/39