Part III
Cyclic codes
CHAPTER 3: CYCLIC CODES and CHANNEL CODES
Cyclic codes are special linear codes of large interest and importance because
They posses a rich algebraic structure that can be utilized in a variety of ways.
They have extremely concise specifications.
They can be efficiently implemented using simple shift registers.
Most of the practically very important codes are cyclic.
Channel codes allow to encode streams of data (bits).
prof. Jozef Gruska IV054 3. Cyclic codes 2/39
IMPORTANT NOTE
In order to specify a binary code with 2k
codewords of length n one may need to write
down
2k
codewords of length n.
In order to specify a linear binary code of the dimension k with 2k
codewords of length n
it is sufficient to write down
k
codewords of length n.
In order to specify a binary cyclic code with 2k
codewords of length n it is sufficient to
write down
1
codeword of length n.
prof. Jozef Gruska IV054 3. Cyclic codes 3/39
BASIC DEFINITION AND EXAMPLES
Definition A code C is cyclic if
(i) C is a linear code;
(ii) any cyclic shift of a codeword is also a codeword, i.e. whenever a0, . . . an−1 ∈ C,
then also an−1a0 . . . an–2 ∈ C.
Example
(i) Code C = {000, 101, 011, 110} is cyclic.
(ii) Hamming code Ham(3, 2): with the generator matrix
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
is equivalent to a cyclic code.
(iii) The binary linear code {0000, 1001, 0110, 1111} is not cyclic, but it is equivalent to
a cyclic code.
(iv) Is Hamming code Ham(2, 3) with the generator matrix
»
1 0 1 1
0 1 1 2
–
(a) cyclic?
(b) equivalent to a cyclic code?
prof. Jozef Gruska IV054 3. Cyclic codes 4/39
FREQUENCY of CYCLIC CODES
Comparing with linear codes, cyclic codes are quite scarce. For example, there are 11 811
linear [7,3] binary codes, but only two of them are cyclic.
Trivial cyclic codes. For any field F and any integer n ≥ 3 there are always the following
cyclic codes of length n over F:
No-information code - code consisting of just one all-zero codeword.
Repetition code - code consisting of codewords (a, a, . . . ,a) for a ∈ F.
Single-parity-check code - code consisting of all codewords with parity 0.
No-parity code - code consisting of all codewords of length n
For some cases, for example for n = 19 and F = GF(2), the above four trivial cyclic
codes are the only cyclic codes.
prof. Jozef Gruska IV054 3. Cyclic codes 5/39
EXAMPLE of a CYCLIC CODE
The code with the generator matrix
G =
2
4
1 0 1 1 1 0 0
0 1 0 1 1 1 0
0 0 1 0 1 1 1
3
5
has codewords
c1 = 1011100
c1 + c2 = 1110010
c2 = 0101110
c1 + c3 = 1001011
c1 + c2 + c3 = 1100101
c3 = 0010111
c2 + c3 = 0111001
and it is cyclic because the right shifts have the following impacts
c1 → c2,
c1 + c2 → c2 + c3,
c2 → c3,
c1 + c3 → c1 + c2 + c3,
c1 + c2 + c3 → c1 + c2
c3 → c1 + c3
c2 + c3 → c1
prof. Jozef Gruska IV054 3. Cyclic codes 6/39
POLYNOMIALS over GF(q)
A codeword of a cyclic code is usually denoted
a0a1 . . . an−1
and to each such a codeword the polynomial
a0 + a1x + a2x2
+ . . . + an−1xn−1
will be associated.
NOTATION: Fq[x] denotes the set of all polynomials over GF(q).
deg(f (x)) = the largest m such that xm
has a non-zero coefficient in f (x).
Multiplication of polynomials If f (x), g(x) ∈ Fq[x], then
deg(f (x)g(x)) = deg(f (x)) + deg(g(x)).
Division of polynomials For every pair of polynomials a(x), b(x) = 0 in Fq[x] there exists
a unique pair of polynomials q(x), r(x) in Fq[x] such that
a(x) = q(x)b(x) + r(x), deg(r(x)) < deg(b(x)).
Example Divide x3
+ x + 1 by x2
+ x + 1 in F2[x].
Definition Let f (x) be a fixed polynomial in Fq[x]. Two polynomials g(x), h(x) are said
to be congruent modulo f (x), notation
g(x) ≡ h(x)(mod f (x)),
if g(x) − h(x) is divisible by f (x).
prof. Jozef Gruska IV054 3. Cyclic codes 7/39
RING of POLYNOMIALS
The set of polynomials in Fq[x] of degree less than deg(f (x)), with addition and
multiplication modulo f (x), forms a ring denoted Fq[x]/f (x).
Example Calculate (x + 1)2
in F2[x]/(x2
+ x + 1). It holds
(x + 1)2
= x2
+ 2x + 1 ≡ x2
+ 1 ≡ x(mod x2
+ x + 1).
How many elements has Fq[x]/f (x)?
Result |Fq[x]/f (x)| = qdeg(f (x))
.
Example Addition and multiplication in F2[x]/(x2
+ x + 1)
+ 0 1 x 1+x
0 0 1 x 1+x
1 1 0 1+x x
x x 1+x 0 1
1+x 1+x x 1 0
• 0 1 x 1+x
0 0 0 0 0
1 0 1 x 1+x
x 0 x 1+x 1
1+x 0 1+x 1 x
Definition A polynomial f (x) in Fq[x] is said to be reducible if f (x) = a(x)b(x), where
a(x), b(x) ∈ Fq[x] and
deg(a(x)) < deg(f (x)), deg(b(x)) < deg(f (x)).
If f (x) is not reducible, then it is said to be irreducible in Fq[x].
Theorem The ring Fq[x]/f (x) is a field if f (x) is irreducible in Fq[x].
prof. Jozef Gruska IV054 3. Cyclic codes 8/39
FIELD Rn, Rn = Fq[x]/(xn − 1)
Computation modulo xn
− 1
Since xn
≡ 1(mod (xn
− 1)) we can compute f (x) mod (xn
− 1) by replacing, in f (x),
xn
by1, xn+1
by x, xn+2
by x2
, xn+3
by x3
, . . .
Replacement of a word
a0a1 . . . an−1
by a polynomial
a0 + a1x + . . . + an−1xn−1
Is of large importance because
multiplication by x in Rn corresponds to a single cyclic shift
x(a0 + a1x + . . . an−1xn−1
) = an−1 + a0x + a1x2
+ . . . + an−2xn−1
prof. Jozef Gruska IV054 3. Cyclic codes 9/39
ALGEBRAIC CHARACTERIZATION of CYCLIC CODES
Theorem A code C is cyclic if and only if it satisfies two conditions
(i) a(x), b(x) ∈ C ⇒ a(x) + b(x) ∈ C
(ii) a(x) ∈ C, r(x) ∈ Rn ⇒ r(x)a(x) ∈ C
Proof
(1) Let C be a cyclic code. C is linear ⇒
(i) holds.
(ii)
Let a(x) ∈ C, r(x) = r0 + r1x + . . . + rn−1xn−1
r(x)a(x) = r0a(x) + r1xa(x) + . . . + rn−1xn−1
a(x)
is in C by (i) because summands are cyclic shifts of a(x).
(2) Let (i) and (ii) hold
Taking r(x) to be a scalar the conditions imply linearity of C.
Taking r(x) = x the conditions imply cyclicity of C.
prof. Jozef Gruska IV054 3. Cyclic codes 10/39
CONSTRUCTION of CYCLIC CODES
Notation If f (x) ∈ Rn, then we define
f (x) = {r(x)f (x)|r(x) ∈ Rn}
(multiplication is modulo xn
− 1).
Theorem For any f (x) ∈ Rn, the set f (x) is a cyclic code (generated by f ).
Proof We check conditions (i) and (ii) of the previous theorem.
(i) If a(x)f (x) ∈ f (x) and also b(x)f (x) ∈ f (x) , then
a(x)f (x) + b(x)f (x) = (a(x) + b(x))f (x) ∈ f (x)
(ii) If a(x)f (x) ∈ f (x) , r(x) ∈ Rn, then
r(x)(a(x)f (x)) = (r(x)a(x))f (x) ∈ f (x)
Example C = 1 + x2
, n = 3, q = 2.
We have to compute r(x)(1 + x2
) for all r(x) ∈ R3.
R3 = {0, 1, x, 1 + x, x2
, 1 + x2
, x + x2
, 1 + x + x2
}.
Result
C = {0, 1 + x, 1 + x2
, x + x2
}
C = {000, 011, 101, 110}
prof. Jozef Gruska IV054 3. Cyclic codes 11/39
CHARACTERIZATION THEOREM for CYCLIC CODES
We show that all cyclic codes C have the form C = f (x) for some f (x) ∈ Rn.
Theorem Let C be a non-zero cyclic code in Rn. Then
there exists unique monic polynomial g(x) of the smallest degree such that
C = g(x)
g(x) is a factor of xn
− 1.
Proof
(i) Suppose g(x) and h(x) are two monic polynomials in C of the smallest degree.
Then the polynomial g(x) − h(x) ∈ C and it has a smaller degree and a
multiplication by a scalar makes out of it a monic polynomial. If g(x) = h(x) we
get a contradiction.
(ii) Suppose a(x) ∈ C.
Then
a(x) = q(x)g(x) + r(x), (deg r(x) < deg g(x)).
and
r(x) = a(x) − q(x)g(x) ∈ C.
By minimality
r(x) = 0
and therefore a(x) ∈ g(x) .
prof. Jozef Gruska IV054 3. Cyclic codes 12/39
CHARACTERIZATION THEOREM for CYCLIC CODES - continuation
(iii) Clearly,
xn
− 1 = q(x)g(x) + r(x) with deg r(x) < deg g(x)
and therefore
r(x) ≡ −q(x)g(x)(mod xn
− 1) and
r(x) ∈ C ⇒ r(x) = 0 ⇒ g(x) is a factor of xn
− 1.
GENERATOR POLYNOMIALS
Definition If
C = g(x) ,
holds for a cyclic code C, then g is called the generator polynomial for the code C.
prof. Jozef Gruska IV054 3. Cyclic codes 13/39
HOW TO DESIGN CYCLIC CODES?
The last claim of the previous theorem gives a recipe to get all cyclic codes of the given
length n in GF(q).
Indeed, all we need to do is to find all factors (in GF(q)) of
xn
− 1.
Problem: Find all binary cyclic codes of length 3.
Solution: Since
x3
− 1 = (x − 1)(x2
+ x + 1)
| {z }
both factors are irreducible in GF(2)
we have the following generator polynomials and codes.
Generator polynomials
1
x + 1
x2
+ x + 1
x3
− 1 ( = 0)
Code in R3
R3
{0, 1 + x, x + x2
, 1 + x2
}
{0, 1 + x + x2
}
{0}
Code in V (3, 2)
V (3, 2)
{000, 110, 011, 101}
{000, 111}
{000}
prof. Jozef Gruska IV054 3. Cyclic codes 14/39
DESIGN of GENERATOR MATRICES for CYCLIC CODES
Theorem Suppose C is a cyclic code of codewords of length n with the generator
polynomial
g(x) = g0 + g1x + . . . + gr xr
.
Then dim (C) = n − r and a generator matrix G1 for C is
G1 =
0
B
B
B
@
g0 g1 g2 . . . gr 0 0 0 . . . 0
0 g0 g1 g2 . . . gr 0 0 . . . 0
0 0 g0 g1 g2 . . . gr 0 . . . 0
. . . . . . . . .
0 0 . . . 0 0 . . . 0 g0 . . . gr
1
C
C
C
A
Proof
(i) All rows of G1 are linearly independent.
(ii) The n − r rows of G represent codewords
g(x), xg(x), x2
g(x), . . . , xn−r−1
g(x) (*)
(iii) It remains to show that every codeword in C can be expressed as a linear
combination of vectors from (*).
Inded, if a(x) ∈ C, then
a(x) = q(x)g(x).
Since deg a(x) < n we have deg q(x) < n − r.
Hence
q(x)g(x) = (q0 + q1x + . . . + qn−r−1x
n−r−1
)g(x)
= q0g(x) + q1xg(x) + . . . + qn−r−1x
n−r−1
g(x).
prof. Jozef Gruska IV054 3. Cyclic codes 15/39
EXAMPLE
The task is to determine all ternary codes of length 4 and generators for them.
Factorization of x4
− 1 over GF(3) has the form
x4
− 1 = (x − 1)(x3
+ x2
+ x + 1) = (x − 1)(x + 1)(x2
+ 1)
Therefore there are 23
= 8 divisors of x4
− 1 and each generates a cyclic code.
Generator polynomial Generator matrix
1 I4
x − 1
2
4
−1 1 0 0
0 −1 1 0
0 0 −1 1
3
5
x + 1
2
4
1 1 0 0
0 1 1 0
0 0 1 1
3
5
x2
+ 1
»
1 0 1 0
0 1 0 1
–
(x − 1)(x + 1) = x2
− 1
»
−1 0 1 0
0 −1 0 1
–
(x − 1)(x2
+ 1) = x3
− x2
+ x − 1
ˆ
−1 1 −1 1
˜
(x + 1)(x2
+ 1)
ˆ
1 1 1 1
˜
x4
− 1 = 0
ˆ
0 0 0 0
˜
prof. Jozef Gruska IV054 3. Cyclic codes 16/39
Check polynomials and parity check matrices for cyclic codes
Let C be a cyclic [n, k]-code with the generator polynomial g(x) (of degree n − k). By
the last theorem g(x) is a factor of xn
− 1. Hence
xn
− 1 = g(x)h(x)
for some h(x) of degree k (where h(x) is called the check polynomial of C).
Theorem Let C be a cyclic code in Rn with a generator polynomial g(x) and a check
polynomial h(x). Then an c(x) ∈ Rn is a codeword of C if and only if c(x)h(x) ≡ 0
–(this and next congruences are all modulo xn
− 1).
Proof Note, that g(x)h(x) = xn
− 1 ≡ 0
(i) c(x) ∈ C ⇒ c(x) = a(x)g(x) for some a(x) ∈ Rn
⇒ c(x)h(x) = a(x) g(x)h(x)
| {z }
≡0
≡ 0.
(ii) c(x)h(x) ≡ 0
c(x) = q(x)g(x) + r(x), deg r(x) < n − k = deg g(x)
c(x)h(x) ≡ 0 ⇒ r(x)h(x) ≡ 0 (mod xn
− 1)
Since deg (r(x)h(x)) < n − k + k = n, we have r(x)h(x) = 0 in F[x] and therefore
r(x) = 0 ⇒ c(x) = q(x)g(x) ∈ C.
prof. Jozef Gruska IV054 3. Cyclic codes 17/39
POLYNOMIAL REPRESENTATION of DUAL CODES
Since dim ( h(x) ) = n − k = dim(C⊥
) we might easily be fooled to think that the
check polynomial h(x) of the code C generates the dual code C⊥
.
Reality is “slightly different”:
Theorem Suppose C is a cyclic [n, k]-code with the check polynomial
h(x) = h0 + h1x + . . . + hk xk
,
then
(i) a parity-check matrix for C is
H =
0
B
B
@
hk hk−1 . . . h0 0 . . . 0
0 hk . . . h1 h0 . . . 0
. . . . . .
0 0 . . . 0 hk . . . h0
1
C
C
A
(ii) C⊥
is the cyclic code generated by the polynomial
h(x) = hk + hk−1x + . . . + h0xk
i.e. the reciprocal polynomial of h(x).
prof. Jozef Gruska IV054 3. Cyclic codes 18/39
POLYNOMIAL REPRESENTATION of DUAL CODES
Proof A polynomial c(x) = c0 + c1x + . . . + cn−1xn−1
represents a code from C if
c(x)h(x) = 0. For c(x)h(x) to be 0 the coefficients at xk
, . . . , xn−1
must be zero, i.e.
c0hk + c1hk−1 + . . . + ck h0 = 0
c1hk + c2hk−1 + . . . + ck+1h0 = 0
. . .
cn−k−1hk + cn−k hk−1 + . . . + cn−1h0 = 0
Therefore, any codeword c0c1 . . . cn−1 ∈ C is orthogonal to the word hk hk−1 . . . h000 . . . 0
and to its cyclic shifts.
Rows of the matrix H are therefore in C⊥
. Moreover, since hk = 1, these rowvectors are
linearly independent. Their number is n − k = dim (C⊥
). Hence H is a generator matrix
for C⊥
, i.e. a parity-check matrix for C.
In order to show that C⊥
is a cyclic code generated by the polynomial
h(x) = hk + hk−1x + . . . + h0xk
it is sufficient to show that h(x) is a factor of xn
− 1.
Observe that h(x) = xk
h(x−1
)and since h(x−1
)g(x−1
) = (x−1
)n
− 1
we have that xk
h(x−1
)xn−k
g(x−1
) = xn
(x−n
− 1) = 1 − xn
and therefore h(x) is indeed a factor of xn
− 1.
prof. Jozef Gruska IV054 3. Cyclic codes 19/39
ENCODING with CYCLIC CODES I
Encoding using a cyclic code can be done by a multiplication of two polynomials - a
message polynomial and the generating polynomial for the cyclic code.
Let C be an [n, k]-code over an field F with the generator polynomial
g(x) = g0 + g1x + . . . + gr−1xr−1
of degree r = n − k.
If a message vector m is represented by a polynomial m(x) of degree k and m is encoded
by
m ⇒ c = mG,
then the following relation between m(x) and c(x) holds
c(x) = m(x)g(x).
Such an encoding can be realized by the shift register shown in Figure below, where input
is the k-bit message to be encoded followed by n − k 0’ and the output will be the
encoded message.
input
output
Shift-register encodings of cyclic codes. Small circles represent multiplication by
the corresponding constant,
L
nodes represent modular addition, squares are delay
elements
prof. Jozef Gruska IV054 3. Cyclic codes 20/39
Hamming codes as cyclic codes
Definition (Again!) Let r be a positive integer and let H be an r × (2r
− 1) matrix whose
columns are distinct non-zero vectors of V (r, 2). Then the code having H as its
parity-check matrix is called binary Hamming code denoted by Ham (r, 2).
It can be shown that:
Theorem The binary Hamming code Ham (r, 2) is equivalent to a cyclic code.
Definition If p(x) is an irreducible polynomial of degree r such that x is a primitive
element of the field F[x]/p(x), then p(x) is called a primitive polynomial.
Theorem If p(x) is a primitive polynomial over GF(2) of degree r, then the cyclic code
p(x) is the code Ham (r, 2).
prof. Jozef Gruska IV054 3. Cyclic codes 21/39
Hamming codes as cyclic codes
Example Polynomial x3
+ x + 1 is irreducible over GF(2) and x is primitive element of
the field F2[x]/(x3 + x + 1).
F2[x]/(x3
+ x + 1) =
{0, x, x2
, x3
= x + 1, x4
= x2
+ x, x5
= x2
+ x + 1, x6
= x2
+ 1}
The parity-check matrix for a cyclic version of Ham (3, 2)
H =
0
@
1 0 0 1 0 1 1
0 1 0 1 1 1 0
0 0 1 0 1 1 1
1
A
prof. Jozef Gruska IV054 3. Cyclic codes 22/39
PROOF of THEOREM
The binary Hamming code Ham (r, 2) is equivalent to a cyclic code.
It is known from algebra that if p(x) is an irreducible polynomial of degree r, then the ring
F2[x]/p(x) is a field of order 2r .
In addition, every finite field has a primitive element. Therefore, there exists an element α of
F2[x]/p(x) such that
F2[x]/p(x) = {0, 1, α, α2, . . . , α2r−2}.
Let us identify an element a0 + a1 + . . . ar−1xr−1 of F2[x]/p(x) with the column vector
(a0, a1, . . . , ar−1)
and consider the binary r × (2r − 1) matrix
H = [1 α α2 . . . α2r
−2].
Let now C be the binary linear code having H as a parity check matrix.
Since the columns of H are all distinct non-zero vectors of V (r, 2), C = Ham (r, 2).
Putting n = 2r − 1 we get
C = {f0f1 . . . fn−1 ∈ V (n, 2)|f0 + f1α + . . . + fn−1αn−1
= 0} (1)
= {f (x) ∈ Rn|f (α) = 0 in F2[x]/p(x)} (2)
If f (x) ∈ C and r(x) ∈ Rn, then r(x)f (x) ∈ C because
r(α)f (α) = r(α) • 0 = 0
and therefore, by one of the previous theorems, this version of Ham (r, 2) is cyclic.
prof. Jozef Gruska IV054 3. Cyclic codes 23/39
BCH codes and Reed-Solomon codes
To the most important cyclic codes for applications belong BCH codes and
Reed-Solomon codes.
Definition A polynomial p is said to be minimal for a complex number x in Zq if p(x) = 0
and p is irreducible over Zq.
Definition A cyclic code of codewords of length n over Zq, q = pr
, p is a prime, is called
BCH code1
of distance d if its generator g(x) is the least common multiple of the
minimal polynomials for
ωl
, ωl+1
, . . . , ωl+d−2
for some l, where
ω is the primitive n-th root of unity.
If n = qm
− 1 for some m, then the BCH code is called primitive.
Definition A Reed-Solomon code is a primitive BCH code with n = q − 1.
Properties:
Reed-Solomon codes are self-dual.
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes.
prof. Jozef Gruska IV054 3. Cyclic codes 24/39
CHANNEL (STREAMS) CODING I.
The task of channel coding is to encode streams of data in such a way that if they are
sent over a noisy channel errors can be detected and/or corrected by the receiver.
In case no receiver-to-sender communication is allowed we speak about forward error
correction.
An important parameter of a channel code is code rate
r =
k
n
in case k bits are encoded by n bits.
The code rate expressed the amount of redundancy in the code - the lower is the rate,
the more redundant is the code.
prof. Jozef Gruska IV054 3. Cyclic codes 25/39
CHANNEL (STREAM) CODING II
Design of a channel code is always a tradeoff between energy efficiency and bandwidth
efficiency.
Codes with lower code rate can usually correct more errors. Consequently, the
communication system can operate
with a lower transmit power;
transmit over longer distances;
tolerate more interference;
use smaller antennas;
transmit at a higher data rate.
These properties make codes with lower code rate energy efficient.
On the other hand such codes require larger bandwidth and decoding is usually of higher
complexity.
The selection of the code rate involves a tradeoff between energy efficiency and
bandwidth efficiency.
Central problem of channel encoding: encoding is usually easy, but decoding is usually
hard.
prof. Jozef Gruska IV054 3. Cyclic codes 26/39
CONVOLUTION CODES
Our first example of channel cdes are convolution codes.
Convolution codes, with simple encoding and decoding, are quite a simple generalization
of linear codes and have encodings as cyclic codes.
An (n, k) convolution code (CC) is defined by an k × n generator matrix, entries of which
are polynomials over F2.
For example,
G1 = [x2
+ 1, x2
+ x + 1]
is the generator matrix for a (2, 1) convolution code CC1 and
G2 =
„
1 + x 0 x + 1
0 1 x
«
is the generator matrix for a (3, 2) convolution code CC2
prof. Jozef Gruska IV054 3. Cyclic codes 27/39
ENCODING of FINITE POLYNOMIALS
An (n,k) convolution code with a k x n generator matrix G can be used to encode a
k-tuple of plain-polynomials (polynomial input information)
I = (I0(x), I1(x), . . . , Ik−1(x))
to get an n-tuple of crypto-polynomials
C = (C0(x), C1(x), . . . , Cn−1(x))
As follows
C = I · G
prof. Jozef Gruska IV054 3. Cyclic codes 28/39
EXAMPLES
EXAMPLE 1
(x3
+ x + 1) · G1 = (x3
+ x + 1) · (x2
+ 1, x2
+ x + 1)
= (x5
+ x2
+ x + 1, x5
+ x4
+ 1)
EXAMPLE 2
(x2
+ x, x3
+ 1) · G2 = (x2
+ x, x3
+ 1) ·
„
1 + x 0 x + 1
0 1 x
«
prof. Jozef Gruska IV054 3. Cyclic codes 29/39
ENCODING of INFINITE INPUT STREAMS
The way infinite streams are encoded using convolution codes will be Illustrated on the
code CC1.
An input stream I = (I0, I1, I2, . . .) is mapped into the output stream
C = (C00, C10, C01, C11 . . .) defined by
C0(x) = C00 + C01x + . . . = (x2
+ 1)I(x)
and
C1(x) = C10 + C11x + . . . = (x2
+ x + 1)I(x).
The first multiplication can be done by the first shift register from the next figure; second
multiplication can be performed by the second shift register on the next slide and it holds
C0i = Ii + Ii+2, C1i = Ii + Ii−1 + Ii−2.
That is the output streams C0 and C1 are obtained by convolving the input stream with
polynomials of G1.
prof. Jozef Gruska IV054 3. Cyclic codes 30/39
ENCODING
The first shift register
input
output
will multiply the input stream by x2
+ 1 and the second shift register
input
output
will multiply the input stream by x2
+ x + 1.
prof. Jozef Gruska IV054 3. Cyclic codes 31/39
ENCODING and DECODING
The following shift-register will therefore be an encoder for the code CC1
input
output streams
For decoding of the convolution codes so called
Viterbi algorithm
Is used.
prof. Jozef Gruska IV054 3. Cyclic codes 32/39
SHANNON CHANNEL CAPACITY
For every combination of bandwidth (W ), channel type , signal power (S) and received
noise power (N), there is a theoretical upper bound, called channel capacity or Shannon
capacity, on the data transmission rate R for which error-free data transmission is
possible.
For so-called white Gaussian noise channels this limit is
R < W log
„
1 +
S
N
«
{bits per second}
Shannon capacity sets a limit to the energy efficiency of the code.
Till 1993 channel code designers were unable to develop codes with performance close to
Shannon capacity limit, that is Shannon capacity approaching codes, and practical codes
required about twice as much energy as theoretical minimum predicted.
Therefore there was a big need for better codes with performance (arbitrarily) close to
Shannon capacity limits.
Concatenated codes and Turbo codes have such a Shannon capacity approaching
property.
prof. Jozef Gruska IV054 3. Cyclic codes 33/39
CONCATENATED CODES
Let Cin : Ak
→ An
be an [n, k, d] code over alphabet A.
Let Cout : BK
→ BN
be an [N, K, D] code over alphabet B with |B| = |A|k
symbols.
Concatenation of Cout (as outer code) with Cin (as inner code), denoted Cout ◦ Cin is the
[nN, kK, dD] code
Cout ◦ Cin : AkK
→ AnN
that maps an input message m = (m1, m2, . . . , mK ) to a codeword
(Cin(m1), Cin(m2), . . . , Cin(mN )), where
(m1, m2, . . . , mN ) = Cout (m1, m2, . . . , mK )
outer
encoder
inner
encoder
inner
decoder
outer
decoder
super decodersuper encoder
noisy
channel
super
channel
Of the key importance is the fact that if Cin is decoded using the maximum-likelihood
principle (thus showing an exponentially decreasing error probability with increasing
length) and Cout is a code with length N = 2n
r that can be decoded in polynomial time
in N, then the concatenated code can be decoded in polynomial time with respect to
n2nr
and has exponentially decreasing error probability even if Cin has exponential
decoding complexity.
prof. Jozef Gruska IV054 3. Cyclic codes 34/39
APPLICATIONS
Concatenated codes started to be used for deep
space communication starting with Voyager
program in 1977 and stayed so until the invention
of Turbo codes and LDPC codes.
Concatenated codes are used also on Compact
Disc.
The best concatenated codes for many
applications were based on outer Reed-Solomon
codes and inner Viterbi-decoded short constant
length convolution codes.
prof. Jozef Gruska IV054 3. Cyclic codes 35/39
TURBO CODES
Turbo codes were introduced by Berrou, Glavieux and Thitimajshima in 1993.
A Turbo code is formed from the parallel composition of two (convolution) codes
separated by an interleaver (that permutes blocks of data in a fixed (pseudo)-random
way).
A Turbo encoder is formed from the parallel composition of two (convolution) encoders
separated by an interleaver.
input x
interleaver
convolution
i
convolution
encoder
encoder
parity bit b1
parity bit b2
prof. Jozef Gruska IV054 3. Cyclic codes 36/39
EXAMPLE of TURBO and CONVOLUTION ENCODERS
A Turbo encoder
input x
interleaver
convolution
i
convolution
encoder
encoder
parity bit b1
parity bit b2
and a convolution encoder
prof. Jozef Gruska IV054 3. Cyclic codes 37/39
DECODING and PERFORMANCE of TURBO CODES
A soft-in-soft-out decoding is used - the decoder gets from the analog/digital
demodulator a soft value of each bit - probability that it is 1 and produces only a
soft-value for each bit.
The overall decoder uses decoders for outputs of two encoders that also provide only
soft values for bits and by exchanging information produced by two decoders and
from the original input bit, the main decoder tries to increase , by an iterative
process, likelihood for values of decoded bits and to produce finally hard outcome - a
bit 1 or 0.
Turbo codes performance can be very close to theoretical Shannon limit.
This was, for example the case for UMTS (the third Generation Universal Mobile
Telecommunication System) Turbo code having a less than 1.2-fold overhead. in
this case the interleaver worked with block of 40-5114 bits.
Turbo codes were incorporated into standards used by NASA for deep space
communications, digital video broadcasting and both third generation ce;;ular
standards.
Literature: M.C. Valenti and J.Sun: Turbo codes - tutorial, Handbook of RF and
Wireless Technologies, 2004 - reachable by Google.
prof. Jozef Gruska IV054 3. Cyclic codes 38/39
WHY ARE TURBO CODES SO GOOD?
Turbo codes are linear codes.
A ”good” linear code is one that has mostly
high-weight codewords.
High-weight codewords are desirable because
they are more distinct and the decoder can more
easily distinguish among them.
A big advantage of Turbo encoders is that they
reduce the number of low-weight codewords
because their output is the sum of the weights of
the input and two parity output bits.
prof. Jozef Gruska IV054 3. Cyclic codes 39/39