Part I
Linear, Cyclic, stream and channel codes. Speccial decodings
LINEAR CODES - continuation
LINEAR CODES II. - continuation, decoding
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 2/84
Appendix I.
APPENDIX I.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 3/84
WISDOM
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 4/84
WISDOM
When you have eliminated impossible,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 4/84
WISDOM
When you have eliminated impossible,
whatever remains,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 4/84
WISDOM
When you have eliminated impossible,
whatever remains,
however impossible
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 4/84
WISDOM
When you have eliminated impossible,
whatever remains,
however impossible
must be
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 4/84
WISDOM
When you have eliminated impossible,
whatever remains,
however impossible
must be the TRUTH
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 4/84
WHY LINEAR CODES?
WHY LINEAR CODES?
Most of the important codes are special types of so-called linear codes.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 5/84
WHY LINEAR CODES?
WHY LINEAR CODES?
Most of the important codes are special types of so-called linear codes.
Linear codes are of very large importance because they have
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 5/84
WHY LINEAR CODES?
WHY LINEAR CODES?
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,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 5/84
WHY LINEAR CODES?
WHY LINEAR CODES?
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,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 5/84
WHY LINEAR CODES?
WHY LINEAR CODES?
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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 5/84
WHY LINEAR CODES?
WHY LINEAR CODES?
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 general,
an easy to describe decoding.II.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 5/84
WHY LINEAR CODES?
WHY LINEAR CODES?
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 general,
an easy to describe decoding.II.
Many practically important linear codes have also an efficient decoding.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 5/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 =
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 =
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
Example — GF(7)
5 +7 5 =
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
Example — GF(7)
5 +7 5 = 3
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
Example — GF(7)
5 +7 5 = 3 5 ×7 5
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
Example — GF(7)
5 +7 5 = 3 5 ×7 5 = 4
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
Example — GF(7)
5 +7 5 = 3 5 ×7 5 = 4
Example — GF(11)
7 +11 8 =
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
Example — GF(7)
5 +7 5 = 3 5 ×7 5 = 4
Example — GF(11)
7 +11 8 = 4
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
Example — GF(7)
5 +7 5 = 3 5 ×7 5 = 4
Example — GF(11)
7 +11 8 = 4 7 ×11 8 =
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
MATHEMATICS BEHIND - GALOIS FIELDS GF(q) – with q a
prime.
It is the set {0, 1, . . . , q − 1} with two operations
addition modulo q — + mod q or +q or very simply +
multiplication modulo q — × mod q or ×q or very simply × or ·
Example — GF(3)
2 +3 2 = 1 2 ×3 2 = 1
Example — GF(7)
5 +7 5 = 3 5 ×7 5 = 4
Example — GF(11)
7 +11 8 = 4 7 ×11 8 = 1
Comment. To design linear codes we will use Galois fields GF(q) with q being a prime.
One can also use Galois fields GF(qk
), k > 1, but their structure and operations are
defined in a more complex way, see the Appendix.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 6/84
REPETITIONS - I.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 7/84
REPETITIONS - I.
Given an alphabet Σ, any set C ⊂ Σ∗
is called a code and
its elements are called codewords.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 7/84
REPETITIONS - I.
Given an alphabet Σ, any set C ⊂ Σ∗
is called a code and
its elements are called codewords.
By a coding/encoding of elements (messages) from a set
M by codewords from a code C we understand any
one-to-one mapping (encoder) e such that
e : M → C
.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 7/84
REPETITIONS - I.
Given an alphabet Σ, any set C ⊂ Σ∗
is called a code and
its elements are called codewords.
By a coding/encoding of elements (messages) from a set
M by codewords from a code C we understand any
one-to-one mapping (encoder) e such that
e : M → C
.
Encoding (code) is called systematic if for any
m ∈ M ⊂ Σ∗
e(m) = mcm for some cm ∈ Σ∗
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 7/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
Small n.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
Small n.
Large M;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
Small n.
Large M;
Large d;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
Small n.
Large M;
Large d;
Encoding should be fast;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
Small n.
Large M;
Large d;
Encoding should be fast; decoding reasonably efficient
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
Small n.
Large M;
Large d;
Encoding should be fast; decoding reasonably efficient
Encodings of similar messages should be very different.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
Small n.
Large M;
Large d;
Encoding should be fast; decoding reasonably efficient
Encodings of similar messages should be very different.
Error corrections potential should be large.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
REPETITIONS - II.
1. A code C is said to be an (n, M, d) code, if
n is the length of codewords in C
M is the number of codewords in C
d is the minimal distance of C
2. A good code for encoding a set of messages should have:
Small n.
Large M;
Large d;
Encoding should be fast; decoding reasonably efficient
Encodings of similar messages should be very different.
Error corrections potential should be large.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 8/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
2 au ∈ C for all u ∈ C, and all a ∈ GF(q)
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
2 au ∈ C for all u ∈ C, and all a ∈ GF(q)
if u = (u1, u2, . . . , un),, then au = (au1, au2, . . . , aun))
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
2 au ∈ C for all u ∈ C, and all a ∈ GF(q)
if u = (u1, u2, . . . , un),, then au = (au1, au2, . . . , aun))
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
2 au ∈ C for all u ∈ C, and all a ∈ GF(q)
if u = (u1, u2, . . . , un),, then au = (au1, au2, . . . , aun))
Lemma A subset C ⊆ Fn
q is a linear code iff one of the following conditions is satisfied
1 C is a subspace of Fn
q .
2 Sum of any two codewords from C is in C (for the case q = 2)
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
2 au ∈ C for all u ∈ C, and all a ∈ GF(q)
if u = (u1, u2, . . . , un),, then au = (au1, au2, . . . , aun))
Lemma A subset C ⊆ Fn
q is a linear code iff one of the following conditions is satisfied
1 C is a subspace of Fn
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 Fn
q , then C is called [n, k]-code.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
2 au ∈ C for all u ∈ C, and all a ∈ GF(q)
if u = (u1, u2, . . . , un),, then au = (au1, au2, . . . , aun))
Lemma A subset C ⊆ Fn
q is a linear code iff one of the following conditions is satisfied
1 C is a subspace of Fn
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 Fn
q , then C is called [n, k]-code. It has qk
codewords.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
2 au ∈ C for all u ∈ C, and all a ∈ GF(q)
if u = (u1, u2, . . . , un),, then au = (au1, au2, . . . , aun))
Lemma A subset C ⊆ Fn
q is a linear code iff one of the following conditions is satisfied
1 C is a subspace of Fn
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 Fn
q , then C is called [n, k]-code. It has qk
codewords.
If the minimal distance of C is d, then it is said to be the [n, k, d] code.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation.
Linear codes are special sets of words of a fixed length n over an alphabet
Σq = {0, .., q − 1}, where q is a (power of) prime.
Definition A subset C ⊆ Fn
q is a linear code if
1 u + v ∈ C for all u, v ∈ C
(if u = (u1, u2, . . . , un), v = (v1, v2. . . . , vn) then
u + v = (u1 +q v1, u2 +q v2 . . . , un +q vn))
2 au ∈ C for all u ∈ C, and all a ∈ GF(q)
if u = (u1, u2, . . . , un),, then au = (au1, au2, . . . , aun))
Lemma A subset C ⊆ Fn
q is a linear code iff one of the following conditions is satisfied
1 C is a subspace of Fn
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 Fn
q , then C is called [n, k]-code. It has qk
codewords.
If the minimal distance of C is d, then it is said to be the [n, k, d] code.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 9/84
LINEAR CODES - continuation II.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 10/84
LINEAR CODES - continuation II.
If C is a linear [n, k] code, then it has several bases.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 10/84
LINEAR CODES - continuation II.
If C is a linear [n, k] code, then it has several bases.
A base B of C is such a sets of k codewods of C that
each codeword of C is a linear combination of the
codewords from the base B.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 10/84
LINEAR CODES - continuation II.
If C is a linear [n, k] code, then it has several bases.
A base B of C is such a sets of k codewods of C that
each codeword of C is a linear combination of the
codewords from the base B.
Each base B of C is usually reperesented by a (k, n)
matrix, GB, so called a generator matrix of C, the i-th
row of which is the i-th codeword of B.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 10/84
EXERCISE
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11}
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110}
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011}
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011}
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011}
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110}
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
How to create a linear code?
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
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:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
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,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
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,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
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}.
EXERCISE
Which of the following binary codes are linear?
C1 = {00, 01, 10, 11} – YES
C2 = {000, 011, 101, 110} – YES
C3 = {00000, 01101, 10110, 11011} – YES
C5 = {101, 111, 011} – NO
C6 = {000, 001, 010, 011} – YES
C7 = {0000, 1001, 0110, 1110} – NO
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}.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 11/84
BASIC PROPERTIES of LINEAR CODES I
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
Lemma If x, y ∈ Fn
q , then h(x, y) = w(x − y).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
Lemma If x, y ∈ Fn
q , then h(x, y) = w(x − y).
Proof x − y has non-zero entries in exactly those positions where x and y differ.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
Lemma If x, y ∈ Fn
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).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
Lemma If x, y ∈ Fn
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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
Lemma If x, y ∈ Fn
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).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
Lemma If x, y ∈ Fn
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 non-linear code with m codewords, then in order to determine h(C) one has
to make in general m
2
= Θ(m2
) comparisons in the worst case.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
Lemma If x, y ∈ Fn
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 non-linear code with m codewords, then in order to determine h(C) one has
to make in general m
2
= Θ(m2
) comparisons in the worst case.
If C is a linear code with m codewords, then in order to determine h(C), m − 1
comparisons are enough.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
BASIC PROPERTIES of LINEAR CODES I
Notation: Let w(x) (weight of x) denote the number of non-zero entries of x.
Lemma If x, y ∈ Fn
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 non-linear code with m codewords, then in order to determine h(C) one has
to make in general m
2
= Θ(m2
) comparisons in the worst case.
If C is a linear code with m codewords, then in order to determine h(C), m − 1
comparisons are enough.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 12/84
EQUIVALENCE of LINEAR CODES I
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or positions of the code;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or positions of the code;
(b) multiplication of symbols appearing in a fixed position by a non-zero scalar.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or 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 Fn
q if one
matrix can be obtained from the other by a sequence of the following operations:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or 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 Fn
q if one
matrix can be obtained from the other by a sequence of the following operations:
(a) permutation of the rows
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or 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 Fn
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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or 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 Fn
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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or 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 Fn
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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or 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 Fn
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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES I
Definition Two linear codes on GF(q) are called equivalent if one can be obtained from
another by the following operations:
(a) permutation of the words or 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 Fn
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 13/84
EQUIVALENCE of LINEAR CODES II
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 14/84
EQUIVALENCE of LINEAR CODES II
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




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 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 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 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



 →
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 14/84
ENCODING with LINEAR CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n matrix G.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n matrix G.
Theorem C has qk
codewords.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
Corollary The code C can be used to encode uniquely qk
messages.
(Let us identify messages with elements of Fk
q .)
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
Corollary The code C can be used to encode uniquely qk
messages.
(Let us identify messages with elements of Fk
q .)
Encoding of a message u = (u1, . . . , uk ) using the generator matrix G:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
Corollary The code C can be used to encode uniquely qk
messages.
(Let us identify messages with elements of Fk
q .)
Encoding of a message u = (u1, . . . , uk ) using the generator matrix G:
u · G = k
i=1 ui ri where r1, . . . , rk are rows of G.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
Corollary The code C can be used to encode uniquely qk
messages.
(Let us identify messages with elements of Fk
q .)
Encoding of a message u = (u1, . . . , uk ) using the generator matrix G:
u · G = k
i=1 ui ri where r1, . . . , rk are rows of G.
Example Let C be a [7, 4]-code with the generator matrix
G=




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




A message (u1, u2, u3, u4) is encoded as:???
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
Corollary The code C can be used to encode uniquely qk
messages.
(Let us identify messages with elements of Fk
q .)
Encoding of a message u = (u1, . . . , uk ) using the generator matrix G:
u · G = k
i=1 ui ri where r1, . . . , rk are rows of G.
Example Let C be a [7, 4]-code with the generator matrix
G=




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




A message (u1, u2, u3, u4) is encoded as:???
For example:
0 0 0 0 is encoded as? .....
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
Corollary The code C can be used to encode uniquely qk
messages.
(Let us identify messages with elements of Fk
q .)
Encoding of a message u = (u1, . . . , uk ) using the generator matrix G:
u · G = k
i=1 ui ri where r1, . . . , rk are rows of G.
Example Let C be a [7, 4]-code with the generator matrix
G=




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




A message (u1, u2, u3, u4) is encoded as:???
For example:
0 0 0 0 is encoded as? ..... 0000000
1 0 0 0 is encoded as? .....
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
Corollary The code C can be used to encode uniquely qk
messages.
(Let us identify messages with elements of Fk
q .)
Encoding of a message u = (u1, . . . , uk ) using the generator matrix G:
u · G = k
i=1 ui ri where r1, . . . , rk are rows of G.
Example Let C be a [7, 4]-code with the generator matrix
G=




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




A message (u1, u2, u3, u4) is encoded as:???
For example:
0 0 0 0 is encoded as? ..... 0000000
1 0 0 0 is encoded as? ..... 1000101
1 1 1 0 is encoded as? .....
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ENCODING with LINEAR CODES
is a vector × matrix multiplication
Let C be a linear [n, k]-code over Fn
q with a generator k × n 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 codewords/vectors.
Corollary The code C can be used to encode uniquely qk
messages.
(Let us identify messages with elements of Fk
q .)
Encoding of a message u = (u1, . . . , uk ) using the generator matrix G:
u · G = k
i=1 ui ri where r1, . . . , rk are rows of G.
Example Let C be a [7, 4]-code with the generator matrix
G=




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




A message (u1, u2, u3, u4) is encoded as:???
For example:
0 0 0 0 is encoded as? ..... 0000000
1 0 0 0 is encoded as? ..... 1000101
1 1 1 0 is encoded as? ..... 1110100
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 15/84
ALTERNATIVE APPROACH to DECODING
SYNDROMES APPROACH to DECODING
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 16/84
DUAL CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 =
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 =
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 =
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal words.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal words.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal words.
Given a linear [n, k]-code C, then the dual code of C, denoted by C⊥
, is defined by
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal words.
Given a linear [n, k]-code C, then the dual code of C, denoted by C⊥
, is defined by
C⊥
= {v ∈ Fn
q | v · u = 0 for all u ∈ C}.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal words.
Given a linear [n, k]-code C, then the dual code of C, denoted by C⊥
, is defined by
C⊥
= {v ∈ Fn
q | v · u = 0 for all u ∈ C}.
Lemma Suppose C is an [n, k]-code having a generator matrix G. Then for v ∈ Fn
q
v ∈ C⊥
⇔ vG = 0,
where G denotes the transpose of the matrix G.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal words.
Given a linear [n, k]-code C, then the dual code of C, denoted by C⊥
, is defined by
C⊥
= {v ∈ Fn
q | v · u = 0 for all u ∈ C}.
Lemma Suppose C is an [n, k]-code having a generator matrix G. Then for v ∈ Fn
q
v ∈ C⊥
⇔ vG = 0,
where G denotes the transpose of the matrix G.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal words.
Given a linear [n, k]-code C, then the dual code of C, denoted by C⊥
, is defined by
C⊥
= {v ∈ Fn
q | v · u = 0 for all u ∈ C}.
Lemma Suppose C is an [n, k]-code having a generator matrix G. Then for v ∈ Fn
q
v ∈ C⊥
⇔ vG = 0,
where G denotes the transpose of the matrix G.
In general, the problem of finding the nearest neighbour in a linear code is NP-complete.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
DUAL CODES
Inner product of two vectors (words)
u = u1 . . . un, v = v1 . . . vn
in Fn
q is an element of GF(q) defined (using modulo q operations) by
u · v = u1v1 + . . . + unvn.
Example In F4
2 : 1001 · 1001 = 0
In F4
3 : 2001 · 1210 = 2
1212 · 2121 = 2
If u · v = 0 then words (vectors) u and v are called orthogonal words.
Given a linear [n, k]-code C, then the dual code of C, denoted by C⊥
, is defined by
C⊥
= {v ∈ Fn
q | v · u = 0 for all u ∈ C}.
Lemma Suppose C is an [n, k]-code having a generator matrix G. Then for v ∈ Fn
q
v ∈ C⊥
⇔ vG = 0,
where G denotes the transpose of the matrix G.
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 17/84
HAMMING CODES
An important family of simple linear codes that are easy to encode and decode, are
so-called Hamming codes.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 18/84
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 all
non-zero distinct words from Fr
2 . The code having H as its parity-check matrix is called
binary Hamming code and denoted by Ham(r, 2).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 18/84
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 all
non-zero distinct words from Fr
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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 18/84
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 all
non-zero distinct words from Fr
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 =


0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 1 0 1 0 0 1

 ⇒ G =




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




IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 18/84
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 all
non-zero distinct words from Fr
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 =


0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 1 0 1 0 0 1

 ⇒ G =




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




Theorem Hamming code Ham(r, 2)
is [2r
− 1, 2r
–1 − r]-code,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 18/84
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 all
non-zero distinct words from Fr
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 =


0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 1 0 1 0 0 1

 ⇒ G =




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




Theorem Hamming code Ham(r, 2)
is [2r
− 1, 2r
–1 − r]-code,
has minimum distance 3,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 18/84
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 all
non-zero distinct words from Fr
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 =


0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 1 0 1 0 0 1

 ⇒ G =




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




Theorem Hamming code Ham(r, 2)
is [2r
− 1, 2r
–1 − r]-code,
has minimum distance 3,
and is a perfect code.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 18/84
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 all
non-zero distinct words from Fr
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 =


0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 1 0 1 0 0 1

 ⇒ G =




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




Theorem Hamming code Ham(r, 2)
is [2r
− 1, 2r
–1 − r]-code,
has minimum distance 3,
and 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 18/84
HAMMING CODES - DECODING
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 19/84
HAMMING CODES - DECODING
Decoding algorithm for the case the columns of H are
arranged in the order of increasing binary numbers the
columns represent.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 19/84
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 .
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 19/84
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 19/84
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 19/84
EXAMPLE
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 20/84
EXAMPLE
For the Hamming code given by the parity-check matrix
H =


0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1


IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 20/84
EXAMPLE
For the Hamming code given by the parity-check matrix
H =


0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1


and the received word
y = 1101011,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 20/84
EXAMPLE
For the Hamming code given by the parity-check matrix
H =


0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1


and the received word
y = 1101011,
we get syndrome
S(y) = 110
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 20/84
EXAMPLE
For the Hamming code given by the parity-check matrix
H =


0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1


and the received word
y = 1101011,
we get syndrome
S(y) = 110
and therefore the error is in the sixth position.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 20/84
EXAMPLE
For the Hamming code given by the parity-check matrix
H =


0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1


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).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 20/84
EXAMPLE
For the Hamming code given by the parity-check matrix
H =


0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1


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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 20/84
EXAMPLE
For the Hamming code given by the parity-check matrix
H =


0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1


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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 20/84
SOME BASIC IMPORTANT CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 21/84
SOME BASIC 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 21/84
SOME BASIC 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 21/84
SOME BASIC 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 21/84
SOME BASIC 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 21/84
SOME BASIC 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. They are also
special cases of quadratic residue codes.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 21/84
GOLAY CODES - DESCRIPTION
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 22/84
GOLAY CODES - DESCRIPTION
Golay codes G24 and G23 were used by Voyager I and Voyager II to transmit color pictures
of Jupiter and Saturn.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 22/84
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 following very simple form:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 22/84
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 following very simple form:
G =


















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


















IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 22/84
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 following very simple form:
G =


















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


















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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 22/84
GOLAY CODES - CONSTRUCTION
Matrix G for Golay code G24 has actually a simple and
regular construction.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 23/84
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 23/84
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 23/84
REED-MULLER CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 24/84
REED-MULLER CODES
This is an infinite, recursively defined, family of so called RMr,m binary linear
[2m
, k, 2m−r
]-codes with
k = 1 +
m
1
+ . . . +
m
r
.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 24/84
REED-MULLER CODES
This is an infinite, recursively defined, family of so called RMr,m binary linear
[2m
, k, 2m−r
]-codes with
k = 1 +
m
1
+ . . . +
m
r
.
The generator matrix Gr,m for RMr,m code has the form
Gr,m = Gr−1,mQr
where Qr is a matrix with dimension m
r
× 2m
where ??????? are representations of the
column numbers.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 24/84
REED-MULLER CODES
This is an infinite, recursively defined, family of so called RMr,m binary linear
[2m
, k, 2m−r
]-codes with
k = 1 +
m
1
+ . . . +
m
r
.
The generator matrix Gr,m for RMr,m code has the form
Gr,m = Gr−1,mQr
where Qr is a matrix with dimension m
r
× 2m
where ??????? are representations of the
column numbers.
Matrix Qr is obtained by considering all combinations of r rows of G1,m and by
obtaining products of these rows/vectors, component by component. The result of
each of such a multiplication constitues a row of Qr .
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 24/84
SINGLETON and PLOTKIN BOUNDS
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
SINGLETON and PLOTKIN BOUNDS
To determine distance of a linear code can be computationally hard task. For that reason
various bounds on distance can be much useful.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
SINGLETON and PLOTKIN BOUNDS
To determine distance of a linear code can be computationally hard task. For that reason
various bounds on distance can be much useful.
Singleton bound: If C is a q-ary (n, M, d)-code, then
M ≤ qn−d+1
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
SINGLETON and PLOTKIN BOUNDS
To determine distance of a linear code can be computationally hard task. For that reason
various bounds on distance can be much useful.
Singleton bound: If C is a q-ary (n, M, d)-code, then
M ≤ qn−d+1
Proof Take some d − 1 coordinates and project all codewords to the remaining
coordinates.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
SINGLETON and PLOTKIN BOUNDS
To determine distance of a linear code can be computationally hard task. For that reason
various bounds on distance can be much useful.
Singleton bound: If C is a q-ary (n, M, d)-code, then
M ≤ qn−d+1
Proof Take some d − 1 coordinates and project all codewords to the remaining
coordinates.
The resulting codewords have to be all different and therefore M cannot be larger than
the number of q-ary words of the length n − d − 1.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
SINGLETON and PLOTKIN BOUNDS
To determine distance of a linear code can be computationally hard task. For that reason
various bounds on distance can be much useful.
Singleton bound: If C is a q-ary (n, M, d)-code, then
M ≤ qn−d+1
Proof Take some d − 1 coordinates and project all codewords to the remaining
coordinates.
The resulting codewords have to be all different and therefore M cannot be larger than
the number of q-ary words of the length n − d − 1.
Codes for which M = qn−d+1
are called MDS-codes (Maximum Distance Separable).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
SINGLETON and PLOTKIN BOUNDS
To determine distance of a linear code can be computationally hard task. For that reason
various bounds on distance can be much useful.
Singleton bound: If C is a q-ary (n, M, d)-code, then
M ≤ qn−d+1
Proof Take some d − 1 coordinates and project all codewords to the remaining
coordinates.
The resulting codewords have to be all different and therefore M cannot be larger than
the number of q-ary words of the length n − d − 1.
Codes for which M = qn−d+1
are called MDS-codes (Maximum Distance Separable).
Corollary: If C is a binary linear [n, k, d]-code, then
d ≤ n − k + 1.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
SINGLETON and PLOTKIN BOUNDS
To determine distance of a linear code can be computationally hard task. For that reason
various bounds on distance can be much useful.
Singleton bound: If C is a q-ary (n, M, d)-code, then
M ≤ qn−d+1
Proof Take some d − 1 coordinates and project all codewords to the remaining
coordinates.
The resulting codewords have to be all different and therefore M cannot be larger than
the number of q-ary words of the length n − d − 1.
Codes for which M = qn−d+1
are called MDS-codes (Maximum Distance Separable).
Corollary: If C is a binary linear [n, k, d]-code, then
d ≤ n − k + 1.
So called Plotkin bound says
d ≤
n2k−1
2k − 1
.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
SINGLETON and PLOTKIN BOUNDS
To determine distance of a linear code can be computationally hard task. For that reason
various bounds on distance can be much useful.
Singleton bound: If C is a q-ary (n, M, d)-code, then
M ≤ qn−d+1
Proof Take some d − 1 coordinates and project all codewords to the remaining
coordinates.
The resulting codewords have to be all different and therefore M cannot be larger than
the number of q-ary words of the length n − d − 1.
Codes for which M = qn−d+1
are called MDS-codes (Maximum Distance Separable).
Corollary: If C is a binary linear [n, k, d]-code, then
d ≤ n − k + 1.
So called Plotkin bound says
d ≤
n2k−1
2k − 1
.
Plotkin bound implies that q-nary error-correcting codes with d ≥ n(1 − 1/q) have only
polynomially many codewords and hence are not very interesting.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 25/84
REED-SOLOMON CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 26/84
REED-SOLOMON CODES
An important example of MDS-codes are q-ary Reed-Solomon codes RSC(k, q), for
k ≤ q.
They are codes a generator matrix of which has rows labelled by polynomials Xi
,
0 ≤ i ≤ k − 1, columns labeled by elements 0, 1, . . . , q − 1 and the element in the row
labelled by a polynomial p and in the column labelled by an element u is p(u).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 26/84
REED-SOLOMON CODES
An important example of MDS-codes are q-ary Reed-Solomon codes RSC(k, q), for
k ≤ q.
They are codes a generator matrix of which has rows labelled by polynomials Xi
,
0 ≤ i ≤ k − 1, columns labeled by elements 0, 1, . . . , q − 1 and the element in the row
labelled by a polynomial p and in the column labelled by an element u is p(u).
RSC(k, q) code is [q, k, q − k + 1] code.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 26/84
REED-SOLOMON CODES
An important example of MDS-codes are q-ary Reed-Solomon codes RSC(k, q), for
k ≤ q.
They are codes a generator matrix of which has rows labelled by polynomials Xi
,
0 ≤ i ≤ k − 1, columns labeled by elements 0, 1, . . . , q − 1 and the element in the row
labelled by a polynomial p and in the 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


1 1 1 1 1
0 1 2 3 4
0 1 4 4 1


IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 26/84
REED-SOLOMON CODES
An important example of MDS-codes are q-ary Reed-Solomon codes RSC(k, q), for
k ≤ q.
They are codes a generator matrix of which has rows labelled by polynomials Xi
,
0 ≤ i ≤ k − 1, columns labeled by elements 0, 1, . . . , q − 1 and the element in the row
labelled by a polynomial p and in the 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


1 1 1 1 1
0 1 2 3 4
0 1 4 4 1


Interesting property of Reed-Solomon codes:
RSC(k, q)⊥
= RSC(q − k, q).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 26/84
REED-SOLOMON CODES
An important example of MDS-codes are q-ary Reed-Solomon codes RSC(k, q), for
k ≤ q.
They are codes a generator matrix of which has rows labelled by polynomials Xi
,
0 ≤ i ≤ k − 1, columns labeled by elements 0, 1, . . . , q − 1 and the element in the row
labelled by a polynomial p and in the 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


1 1 1 1 1
0 1 2 3 4
0 1 4 4 1


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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 26/84
APPENDIX - I
APPENDIX - I.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 27/84
LDPC (Low-Density Parity Check) - CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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 said to be 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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 said to be 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 recent years LDPC codes are replacing in many important applications other types
of codes for the following reasons:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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 said to be 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 recent 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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 said to be 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 recent 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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 said to be 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 recent 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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 said to be 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 recent 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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 said to be 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 recent 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.
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,....
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
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 said to be 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 recent 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.
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,....
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.IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 28/84
DISCOVERY and APPLICATION of LDPC CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 29/84
DISCOVERY and APPLICATION of LDPC CODES
LDPC codes were discovered in 1960 by R.C. Gallager in
his PhD thesis,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 29/84
DISCOVERY and APPLICATION of LDPC CODES
LDPC codes were discovered in 1960 by R.C. Gallager in
his PhD thesis, but were ignored till 1996 when linear time
decoding methods were discovered for some of them.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 29/84
DISCOVERY and APPLICATION of LDPC CODES
LDPC codes were discovered in 1960 by R.C. Gallager in
his PhD thesis, but were 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,....
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 29/84
DISCOVERY and APPLICATION of LDPC CODES
LDPC codes were discovered in 1960 by R.C. Gallager in
his PhD thesis, but were 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,....
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 29/84
BI-PARTITE (TANNER) GRAPHS 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) ”parity check nodes (pc-nodes)”.
Variable nodes:
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
Parity check nodes:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 30/84
BI-PARTITE (TANNER) GRAPHS 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) ”parity check nodes (pc-nodes)”.
Variable nodes:
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
Parity check nodes:
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 =


1 1 1 1 0 0
0 0 1 1 0 1
1 0 0 1 1 0


IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 30/84
TANNER GRAPHS - CONTINUATION
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 31/84
TANNER GRAPHS - CONTINUATION
The LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 31/84
TANNER GRAPHS - CONTINUATION
The LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
has the parity check matrix
H =


1 1 1 1 0 0
0 0 1 1 0 1
1 0 0 1 1 0


IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 31/84
TANNER GRAPHS - CONTINUATION
The LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
has the parity check matrix
H =


1 1 1 1 0 0
0 0 1 1 0 1
1 0 0 1 1 0


and therefore the following constrains have to be satisfied:
a1 + a2 + a3 + a4 = 0
a3 + a4 + a6 = 0
a1 + a4 + a5 = 0
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 31/84
DECODING
Since for the LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 32/84
DECODING
Since for the LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
the following constrains have to be satisfied:
a1 + a2 + a3 + a4 = 0
a3 + a4 + a6 = 0
a1 + a4 + a5 = 0
Let the word ?01?11 be received.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 32/84
DECODING
Since for the LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
the following constrains have to be satisfied:
a1 + a2 + a3 + a4 = 0
a3 + a4 + a6 = 0
a1 + a4 + a5 = 0
Let the word ?01?11 be received.From the second equation it follows that the second
unknown symbol is
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 32/84
DECODING
Since for the LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
the following constrains have to be satisfied:
a1 + a2 + a3 + a4 = 0
a3 + a4 + a6 = 0
a1 + a4 + a5 = 0
Let the word ?01?11 be received.From the second equation it follows that the second
unknown symbol is 0. From the last equation it then follows that the first unknown
symbol is
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 32/84
DECODING
Since for the LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
the following constrains have to be satisfied:
a1 + a2 + a3 + a4 = 0
a3 + a4 + a6 = 0
a1 + a4 + a5 = 0
Let the word ?01?11 be received.From the second equation it follows that the second
unknown symbol is 0. From the last equation it then follows that the first unknown
symbol is 1.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 32/84
DECODING
Since for the LDPC-code with the Tanner bipartite graph for (6, 3) LDPC-code.
= = = = = =
+ + +
a a a a a a1 2 3 4 5 6
the following constrains have to be satisfied:
a1 + a2 + a3 + a4 = 0
a3 + a4 + a6 = 0
a1 + a4 + a5 = 0
Let the word ?01?11 be received.From the second equation it follows that the second
unknown symbol is 0. From the last equation it then follows that the first unknown
symbol is 1.
Using so called iterative belief propagation techniques, LDPC codes can be decoded in
time linear to their block length.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 32/84
DESIGN of LDPC codes
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 33/84
DESIGN of LDPC codes
Some good LDPC codes were designed through
randomly chosen parity check matrices.
Some LDPC codes are based on Reed-Solomon codes,
such as the RS-LDPC code used in the 10-gigabit
Ethernet standard.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 33/84
LDPC CODES APPLICATIONS
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 34/84
LDPC CODES APPLICATIONS
In the recent years have been several interesting competition between LDPC codes
and Turbo codes introduced in Chapter 1 for various applications.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 34/84
LDPC CODES APPLICATIONS
In the recent years have been several interesting competition between LDPC codes
and Turbo codes introduced in Chapter 1 for various applications.
In 2003, an LDPC code was able to beat six turbo codes to become the error
correcting code in the new DVB-S2 standard for satellite transmission for digital
television.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 34/84
LDPC CODES APPLICATIONS
In the recent years have been several interesting competition between LDPC codes
and Turbo codes introduced in Chapter 1 for various applications.
In 2003, an LDPC code was able to beat six turbo codes to become the error
correcting code in the new DVB-S2 standard for satellite transmission for digital
television.
LDPC is also used for 10Gbase-T Ethernet, which sends data at 10 gigabits per
second over twisted-pair cables.
Since 2009 LDPC codes are also part of of the Wi-Fi 802.11 standard as an optional
part of 802.11n, in the High Throughput PHY specification.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 34/84
POLYNOMIAL CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 35/84
POLYNOMIAL CODES
A Polynomial code, with codewords of length n, generated by a (generator)
polynomial g(x) of degree m < n over a GF(q) is the code whose codewords are
represented exactly by those polynomials of degree less than n that are divisible by g(x).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 35/84
POLYNOMIAL CODES
A Polynomial code, with codewords of length n, generated by a (generator)
polynomial g(x) of degree m < n over a GF(q) is the code whose codewords are
represented exactly by those polynomials of degree less than n that are divisible by g(x).
Example: For the binary polynomial code with n = 5 and m = 2 generated by the
polynomial g(x) = x2
+ x + 1 all codewords are of the form:
a(x)g(x)
where
a(x) ∈ {0, 1, x, x + 1, x2
, x2
+ 1, x2
+ x, x2
+ x + 1}
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 35/84
POLYNOMIAL CODES
A Polynomial code, with codewords of length n, generated by a (generator)
polynomial g(x) of degree m < n over a GF(q) is the code whose codewords are
represented exactly by those polynomials of degree less than n that are divisible by g(x).
Example: For the binary polynomial code with n = 5 and m = 2 generated by the
polynomial g(x) = x2
+ x + 1 all codewords are of the form:
a(x)g(x)
where
a(x) ∈ {0, 1, x, x + 1, x2
, x2
+ 1, x2
+ x, x2
+ x + 1}
what results in the code with codewords
00000, 00111, 01110, 01001,
11100, 11011, 10010, 10101.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 35/84
REED-MULLER CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 36/84
REED-MULLER CODES
Reed-Muuller codes with parameters 0 ≤ r ≤ m, notation RM(r, m), are linear block
codes, usually binary - mapping binary messages to binary codewords, used currently
especially in wireless and deep-space communications.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 36/84
REED-MULLER CODES
Reed-Muuller codes with parameters 0 ≤ r ≤ m, notation RM(r, m), are linear block
codes, usually binary - mapping binary messages to binary codewords, used currently
especially in wireless and deep-space communications.
Each Reed-Muller code RM(r, m) is the code of k codewords of length n = 2m
, to
encode k messages, and distance 2m−r
, where
k =
r
s=0
d
s
.
There are several elegant, mathematically sophisticated ways, to describe Reed-Muller
codes and they have nice and useful properties. As a congruence they are locally testable,
locally decodable, list decodable and useful in probabilistically checkable proofs -see rest
of this chapter.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 36/84
REED-MULLER CODES
Reed-Muuller codes with parameters 0 ≤ r ≤ m, notation RM(r, m), are linear block
codes, usually binary - mapping binary messages to binary codewords, used currently
especially in wireless and deep-space communications.
Each Reed-Muller code RM(r, m) is the code of k codewords of length n = 2m
, to
encode k messages, and distance 2m−r
, where
k =
r
s=0
d
s
.
There are several elegant, mathematically sophisticated ways, to describe Reed-Muller
codes and they have nice and useful properties. As a congruence they are locally testable,
locally decodable, list decodable and useful in probabilistically checkable proofs -see rest
of this chapter.
RM(r, m) code is generated by the set of all up to r inner products of the codewords vi ,
0 ≤ i ≤ d, where v0 = 12d
and vi are prefixes of the word {1i
0i
}∗
.
Example 1: RM(1, 3) code is generated by the codewords
v0 = 11111111
v1 = 10101010
v2 = 11001100
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 36/84
REED-MULLER CODES
Reed-Muuller codes with parameters 0 ≤ r ≤ m, notation RM(r, m), are linear block
codes, usually binary - mapping binary messages to binary codewords, used currently
especially in wireless and deep-space communications.
Each Reed-Muller code RM(r, m) is the code of k codewords of length n = 2m
, to
encode k messages, and distance 2m−r
, where
k =
r
s=0
d
s
.
There are several elegant, mathematically sophisticated ways, to describe Reed-Muller
codes and they have nice and useful properties. As a congruence they are locally testable,
locally decodable, list decodable and useful in probabilistically checkable proofs -see rest
of this chapter.
RM(r, m) code is generated by the set of all up to r inner products of the codewords vi ,
0 ≤ i ≤ d, where v0 = 12d
and vi are prefixes of the word {1i
0i
}∗
.
Example 1: RM(1, 3) code is generated by the codewords
v0 = 11111111
v1 = 10101010
v2 = 11001100
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 36/84
REED-MULLER CODES
Reed-Muuller codes with parameters 0 ≤ r ≤ m, notation RM(r, m), are linear block
codes, usually binary - mapping binary messages to binary codewords, used currently
especially in wireless and deep-space communications.
Each Reed-Muller code RM(r, m) is the code of k codewords of length n = 2m
, to
encode k messages, and distance 2m−r
, where
k =
r
s=0
d
s
.
There are several elegant, mathematically sophisticated ways, to describe Reed-Muller
codes and they have nice and useful properties. As a congruence they are locally testable,
locally decodable, list decodable and useful in probabilistically checkable proofs -see rest
of this chapter.
RM(r, m) code is generated by the set of all up to r inner products of the codewords vi ,
0 ≤ i ≤ d, where v0 = 12d
and vi are prefixes of the word {1i
0i
}∗
.
Example 1: RM(1, 3) code is generated by the codewords
v0 = 11111111
v1 = 10101010
v2 = 11001100
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 36/84
REED-MULLER CODES
Reed-Muuller codes with parameters 0 ≤ r ≤ m, notation RM(r, m), are linear block
codes, usually binary - mapping binary messages to binary codewords, used currently
especially in wireless and deep-space communications.
Each Reed-Muller code RM(r, m) is the code of k codewords of length n = 2m
, to
encode k messages, and distance 2m−r
, where
k =
r
s=0
d
s
.
There are several elegant, mathematically sophisticated ways, to describe Reed-Muller
codes and they have nice and useful properties. As a congruence they are locally testable,
locally decodable, list decodable and useful in probabilistically checkable proofs -see rest
of this chapter.
RM(r, m) code is generated by the set of all up to r inner products of the codewords vi ,
0 ≤ i ≤ d, where v0 = 12d
and vi are prefixes of the word {1i
0i
}∗
.
Example 1: RM(1, 3) code is generated by the codewords
v0 = 11111111
v1 = 10101010
v2 = 11001100
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 36/84
BCH CODES and REED-SOLOMON CODES
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 37/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 37/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 37/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code1
of the 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.
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 37/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code1
of the 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.
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 37/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code1
of the 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.
Applications of BCH codes: satellite communications, compact disc players,disk drives,
two-dimensional bar codes,...
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 37/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code1
of the 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.
Applications of BCH codes: satellite communications, compact disc players,disk drives,
two-dimensional bar codes,...
Comments: For BCH codes there exist efficient variations of syndrome decoding.
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 37/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code1
of the 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.
Applications of BCH codes: satellite communications, compact disc players,disk drives,
two-dimensional bar codes,...
Comments: For BCH codes there exist efficient variations of syndrome decoding. A
Reed-Solomon code is a special primitive BCH code.
1
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 37/84
REED-SOLOMON CODES - basic idea behind - I
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 38/84
REED-SOLOMON CODES - basic idea behind - I
A message of k symbols can be encoded by viewing these symbols as coefficients of a
polynomial of degree k − 1 over a finite field of order N, evaluating this polynomial at
more than k distinct points and sending the outcomes to the receiver.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 38/84
REED-SOLOMON CODES - basic idea behind - I
A message of k symbols can be encoded by viewing these symbols as coefficients of a
polynomial of degree k − 1 over a finite field of order N, evaluating this polynomial at
more than k distinct points and sending the outcomes to the receiver.
Having more than k points of the polynomial allows to determine exactly, through the
Lagrangian interpolation, the original polynomial (message).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 38/84
REED-SOLOMON CODES - basic idea behind - I
A message of k symbols can be encoded by viewing these symbols as coefficients of a
polynomial of degree k − 1 over a finite field of order N, evaluating this polynomial at
more than k distinct points and sending the outcomes to the receiver.
Having more than k points of the polynomial allows to determine exactly, through the
Lagrangian interpolation, the original polynomial (message).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 38/84
REED-SOLOMON CODES - basic idea behind - I
A message of k symbols can be encoded by viewing these symbols as coefficients of a
polynomial of degree k − 1 over a finite field of order N, evaluating this polynomial at
more than k distinct points and sending the outcomes to the receiver.
Having more than k points of the polynomial allows to determine exactly, through the
Lagrangian interpolation, the original polynomial (message).
Variations of Reed-Solomon codes are obtained by specifying ways distinct points are
generated and error-correction is performed.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 38/84
REED-SOLOMON CODES - basic idea behind - I
A message of k symbols can be encoded by viewing these symbols as coefficients of a
polynomial of degree k − 1 over a finite field of order N, evaluating this polynomial at
more than k distinct points and sending the outcomes to the receiver.
Having more than k points of the polynomial allows to determine exactly, through the
Lagrangian interpolation, the original polynomial (message).
Variations of Reed-Solomon codes are obtained by specifying ways distinct points are
generated and error-correction is performed.
Reed-Solomon codes found many important applications from deep-space travel to
consumer electronics.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 38/84
REED-SOLOMON CODES - basic idea behind - I
A message of k symbols can be encoded by viewing these symbols as coefficients of a
polynomial of degree k − 1 over a finite field of order N, evaluating this polynomial at
more than k distinct points and sending the outcomes to the receiver.
Having more than k points of the polynomial allows to determine exactly, through the
Lagrangian interpolation, the original polynomial (message).
Variations of Reed-Solomon codes are obtained by specifying ways distinct points are
generated and error-correction is performed.
Reed-Solomon codes found many important applications from deep-space travel to
consumer electronics.
They are very useful especially in those applications where one can expect that errors
occur in bursts - such as ones caused by solar energy.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 38/84
UNIQUE DECODING versus LIST DECODING
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 39/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 39/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
This list decoding error-correction task/model is not sufficiently good in case when the
number of error can be large.
n the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 39/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
This list decoding error-correction task/model is not sufficiently good in case when the
number of error can be large.
n the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
List decoding is considered to be successful in case the outputted list contains the
codeword that was sent.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 39/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
This list decoding error-correction task/model is not sufficiently good in case when the
number of error can be large.
n the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
List decoding is considered to be successful in case the outputted list contains the
codeword that was sent.
It has turned out that for a variety of important codes, say for Reed-Solomon codes, there
are efficient algorithms for list decoding that allow to correct a large variety of errors.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 39/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
This list decoding error-correction task/model is not sufficiently good in case when the
number of error can be large.
n the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
List decoding is considered to be successful in case the outputted list contains the
codeword that was sent.
It has turned out that for a variety of important codes, say for Reed-Solomon codes, there
are efficient algorithms for list decoding that allow to correct a large variety of errors.
The notion of list-decoding, as a relaxed error-correcting mode, was proposed by Elias in
1950s.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 39/84
EFFICIENCY of LIST DECODING
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 40/84
EFFICIENCY of LIST DECODING
With list decoding the error-correction performance
doubles.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 40/84
EFFICIENCY of LIST DECODING
With list decoding the error-correction performance
doubles.
It has been shown, non-constructively, that codes of the
rate R exist that can be list decoded up to a fraction of
errors approaching 1 − R.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 40/84
EFFICIENCY of LIST DECODING
With list decoding the error-correction performance
doubles.
It has been shown, non-constructively, that codes of the
rate R exist that can be list decoded up to a fraction of
errors approaching 1 − R.
The quantity 1 − R is referred to as the list decoding
capacity.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 40/84
EFFICIENCY of LIST DECODING
With list decoding the error-correction performance
doubles.
It has been shown, non-constructively, that codes of the
rate R exist that can be list decoded up to a fraction of
errors approaching 1 − R.
The quantity 1 − R is referred to as the list decoding
capacity.
For Reed-Solomon codes there is list decoding up to
1 −
√
2R errors.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 40/84
CHANNEL (STREAMS) CODING
CHANNELS (STREAMS) CODING
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 41/84
CHANNEL CODING - BASICS
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 42/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 42/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 42/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology. How well can channel coding be
done?
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 42/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology. How well can channel coding be
done? So called Shannon’s channel coding theorem says that over many common
channels there exist data coding schemes that are able to transmit data reliably at all
code rates smaller than a certain threshold, called nowadays the Shannon channel
capacity, of the given channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 42/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology. How well can channel coding be
done? So called Shannon’s channel coding theorem says that over many common
channels there exist data coding schemes that are able to transmit data reliably at all
code rates smaller than a certain threshold, called nowadays the Shannon channel
capacity, of the given channel.
Moreover, the theorem says that probability of a decoding error can be made to decrease
exponentially as the block length N of the coding scheme goes to infinity. However, the
complexity of a ”naive”, or straightforward, optimum decoding schemes increased
exponentially with N - therefore such an optimum decoder rapidly become unfeasible.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 42/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology. How well can channel coding be
done? So called Shannon’s channel coding theorem says that over many common
channels there exist data coding schemes that are able to transmit data reliably at all
code rates smaller than a certain threshold, called nowadays the Shannon channel
capacity, of the given channel.
Moreover, the theorem says that probability of a decoding error can be made to decrease
exponentially as the block length N of the coding scheme goes to infinity. However, the
complexity of a ”naive”, or straightforward, optimum decoding schemes increased
exponentially with N - therefore such an optimum decoder rapidly become unfeasible.
A breakthrough came when D. Forney, in his PhD thesis in 1972, showed that so called
concatenated codes could be used to achieve exponentially decreasing error probabilities
at all data rates less than the Shannon channel capacity, with decoding complexity
increasing only polynomially with the code length.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 42/84
CHANNEL (STREAMS) CODING I.
Therefore, 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 43/84
CHANNEL (STREAMS) CODING I.
Therefore, 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 43/84
CHANNEL (STREAMS) CODING I.
Therefore, 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.
An important parameter of a channel code is code rate
r =
k
n
in case k bits are encoded by n bits.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 43/84
CHANNEL (STREAMS) CODING I.
Therefore, 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.
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 express the amount of redundancy in the code - the lower is the
code rate, the more redundancy is in the codewords.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 43/84
CHANNEL (STREAM) CODING II
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 44/84
CHANNEL (STREAM) CODING II
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 44/84
CHANNEL (STREAM) CODING II
Codes with lower code rate can usually correct more errors. Consequently, the
communication system can:
operate with a lower transmit power;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 44/84
CHANNEL (STREAM) CODING II
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;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 44/84
CHANNEL (STREAM) CODING II
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 from the environment;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 44/84
CHANNEL (STREAM) CODING II
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 from the environment;
use smaller antennas;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 44/84
CHANNEL (STREAM) CODING II
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 from the environment;
use smaller antennas;
use smaller antennas;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 44/84
CHANNEL (STREAM) CODING II
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 from the environment;
use smaller antennas;
use smaller antennas;
transmit at a higher data rate.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 44/84
CHANNEL CAPACITY
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 45/84
CHANNEL CAPACITY
Channel capacity of a communication channel, is the
tightest upper bound on the (code) rate of information
that can be reliably transmitted over that channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 45/84
CHANNEL CAPACITY
Channel capacity of a communication channel, is the
tightest upper bound on the (code) rate of information
that can be reliably transmitted over that channel.
By the noisy-channel Shannon coding theorem, the
channel capacity of a given channel is the limiting code
rate (in units of information per unit time) that can be
achieved with arbitrary small error probability.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 45/84
CHANNEL CAPACITY - FORMAL DEFINITION
Let X and Y be random variables representing the input and output of a channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 46/84
CHANNEL CAPACITY - FORMAL DEFINITION
Let X and Y be random variables representing the input and output of a channel.
Let PY |X (y|x) be the conditional probability distribution function of Y given X, which
can be seen as an inherent fixed probability of the communication channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 46/84
CHANNEL CAPACITY - FORMAL DEFINITION
Let X and Y be random variables representing the input and output of a channel.
Let PY |X (y|x) be the conditional probability distribution function of Y given X, which
can be seen as an inherent fixed probability of the communication channel.
The joint distribution PX,Y (x, y) is then defined by
PX,Y (x, y) = PY |X (y|x)PX (x),
where PX (x) is the marginal distribution.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 46/84
CHANNEL CAPACITY - FORMAL DEFINITION
Let X and Y be random variables representing the input and output of a channel.
Let PY |X (y|x) be the conditional probability distribution function of Y given X, which
can be seen as an inherent fixed probability of the communication channel.
The joint distribution PX,Y (x, y) is then defined by
PX,Y (x, y) = PY |X (y|x)PX (x),
where PX (x) is the marginal distribution.
The channel capacity is then defined by
C = sup
PX (x)
I(X, Y )
where
I(X, Y ) =
y∈Y x∈X
PX,Y (x, y) log
PX,Y (x, y)
PX (x)PY (y)
is the mutual distribution - a measure of variables mutual distribution.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 46/84
SHANNON NOISY CHANEL THEOREM
For every discrete memoryless channel, the channel capacity
C = sup
PX
I(X, Y )
has the following properties:
1. For every ε > 0 and R < C, for large enough N there exists a code of length N and
code rate R and a decoding algorithm, such that the maximal probability of the block
error is ≤ ε.
2. If a probability of the block error pb is acceptable, code rates up to R(pb) are
achievable, where and H2(pb) is the binary entropy function. and H2(pb) is the binary
entropy function.
3. For any pb code rates greater than R(pb) are not achievable.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 47/84
ENCODING of FINITE POLYNOMIALS
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 48/84
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 message-polynomials (polynomial input information)
I = (I0(x), I1(x), . . . , Ik−1(x))
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 48/84
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 message-polynomials (polynomial input information)
I = (I0(x), I1(x), . . . , Ik−1(x))
to get an n-tuple of encoded-polynomials
C = (C0(x), C1(x), . . . , Cn−1(x))
where
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 48/84
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 message-polynomials (polynomial input information)
I = (I0(x), I1(x), . . . , Ik−1(x))
to get an n-tuple of encoded-polynomials
C = (C0(x), C1(x), . . . , Cn−1(x))
where
Cj (x) = Ij (x) · G
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 48/84
EXAMPLES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 49/84
EXAMPLES
EXAMPLE 1 – when the code CC1 is used:
(x3
+ x + 1) · G1 = (x3
+ x + 1) · (x2
+ 1, x2
+ x + 1)
= (x5
+ x2
+ x + 1, x5
+ x4
+ 1)
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 49/84
EXAMPLES
EXAMPLE 1 – when the code CC1 is used:
(x3
+ x + 1) · G1 = (x3
+ x + 1) · (x2
+ 1, x2
+ x + 1)
= (x5
+ x2
+ x + 1, x5
+ x4
+ 1)
EXAMPLE 2 – when the code CC2 is used:
(x2
+ x, x3
+ 1) · G2 = (x2
+ x, x3
+ 1) ·
1 + x 0 x + 1
0 1 x
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 49/84
ENCODING of INFINITE INPUT STREAMS
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 50/84
ENCODING of INFINITE INPUT STREAMS
One of the way infinite streams can be encoded using convolution codes will be
Illustrated on the code CC1.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 50/84
ENCODING of INFINITE INPUT STREAMS
One of the way infinite streams can be encoded using convolution codes will be
Illustrated on the code CC1.
An input stream I(x) = (I0(x), I1(x), I2(x), . . .) is mapped into the output stream
C = (C00, C10, C01, C11 . . .) defined by
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 50/84
ENCODING of INFINITE INPUT STREAMS
One of the way infinite streams can be encoded using convolution codes will be
Illustrated on the code CC1.
An input stream I(x) = (I0(x), I1(x), I2(x), . . .) 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).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 50/84
ENCODING of INFINITE INPUT STREAMS
One of the way infinite streams can be encoded using convolution codes will be
Illustrated on the code CC1.
An input stream I(x) = (I0(x), I1(x), I2(x), . . .) 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 (x) + Ii+2(x), C1i (x) = Ii + Ii−1 + Ii−2.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 50/84
ENCODING of INFINITE INPUT STREAMS
One of the way infinite streams can be encoded using convolution codes will be
Illustrated on the code CC1.
An input stream I(x) = (I0(x), I1(x), I2(x), . . .) 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 (x) + Ii+2(x), C1i (x) = Ii + Ii−1 + Ii−2.
That is the output streams C0 and C1 are obtained by convoluting the input stream with
polynomials of G1.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 50/84
ENCODING
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 51/84
ENCODING
The first shift register
input
output
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 51/84
ENCODING
The first shift register
input
output
will multiply the input stream by x2
+ 1 and the second shift register
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 51/84
ENCODING
The first shift register
input
output
will multiply the input stream by x2
+ 1 and the second shift register
input
output
input
output
will multiply the input stream by x2
+ x + 1.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 51/84
ENCODING and DECODING
The following shift-register will therefore be an encoder for the code CC1
input
output streams
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 52/84
ENCODING and DECODING
The following shift-register will therefore be an encoder for the code CC1
input
output streams
For decoding of convolution codes so called
Viterbi algorithm
is used.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 52/84
VITERBI ALGORITHM
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 53/84
VITERBI ALGORITHM
In 1967 Andrew Vieterbi constructed his nowadays
famous decoding algorithm for soft decoding.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 53/84
VITERBI ALGORITHM
In 1967 Andrew Vieterbi constructed his nowadays
famous decoding algorithm for soft decoding.
Vieterbi was very modest in evaluation of importance of
his algorithm - considered it as impractical.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 53/84
VITERBI ALGORITHM
In 1967 Andrew Vieterbi constructed his nowadays
famous decoding algorithm for soft decoding.
Vieterbi was very modest in evaluation of importance of
his algorithm - considered it as impractical.
Although this algorithm was rendered as impractical
due to the excessive storage requirements it started to
be well known,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 53/84
VITERBI ALGORITHM
In 1967 Andrew Vieterbi constructed his nowadays
famous decoding algorithm for soft decoding.
Vieterbi was very modest in evaluation of importance of
his algorithm - considered it as impractical.
Although this algorithm was rendered as impractical
due to the excessive storage requirements it started to
be well known, because it contributes to a general
understanding of convolution codes and sequential
decoding through its simplicity of mechanization and
analysis.
Nowadays
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 53/84
VITERBI ALGORITHM
In 1967 Andrew Vieterbi constructed his nowadays
famous decoding algorithm for soft decoding.
Vieterbi was very modest in evaluation of importance of
his algorithm - considered it as impractical.
Although this algorithm was rendered as impractical
due to the excessive storage requirements it started to
be well known, because it contributes to a general
understanding of convolution codes and sequential
decoding through its simplicity of mechanization and
analysis.
Nowadays (since 2006),
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 53/84
VITERBI ALGORITHM
In 1967 Andrew Vieterbi constructed his nowadays
famous decoding algorithm for soft decoding.
Vieterbi was very modest in evaluation of importance of
his algorithm - considered it as impractical.
Although this algorithm was rendered as impractical
due to the excessive storage requirements it started to
be well known, because it contributes to a general
understanding of convolution codes and sequential
decoding through its simplicity of mechanization and
analysis.
Nowadays (since 2006), a Viterbi decoder in a cellphone
takes up the area
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 53/84
VITERBI ALGORITHM
In 1967 Andrew Vieterbi constructed his nowadays
famous decoding algorithm for soft decoding.
Vieterbi was very modest in evaluation of importance of
his algorithm - considered it as impractical.
Although this algorithm was rendered as impractical
due to the excessive storage requirements it started to
be well known, because it contributes to a general
understanding of convolution codes and sequential
decoding through its simplicity of mechanization and
analysis.
Nowadays (since 2006), a Viterbi decoder in a cellphone
takes up the area of a tenth of a square millimeter.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 53/84
BIAGWN CHANNELS
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 54/84
BIAGWN CHANNELS
Binary Input Additive Gaussian White Noise (BIAGWN) channel, is a continuous channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 54/84
BIAGWN CHANNELS
Binary Input Additive Gaussian White Noise (BIAGWN) channel, is a continuous channel.
A BIAGWN channel, with a standard deviation σ ≥ 0, can
be seen as a mapping
Xσ = {−1, 1} → R,
where R is the set of reals.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 54/84
BIAGWN CHANNELS
Binary Input Additive Gaussian White Noise (BIAGWN) channel, is a continuous channel.
A BIAGWN channel, with a standard deviation σ ≥ 0, can
be seen as a mapping
Xσ = {−1, 1} → R,
where R is the set of reals.
The noise of BIAGWN is modeled by continuous Gaussian
probability distribution function:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 54/84
BIAGWN CHANNELS
Binary Input Additive Gaussian White Noise (BIAGWN) channel, is a continuous channel.
A BIAGWN channel, with a standard deviation σ ≥ 0, can
be seen as a mapping
Xσ = {−1, 1} → R,
where R is the set of reals.
The noise of BIAGWN is modeled by continuous Gaussian
probability distribution function:
Given (x, y) ∈ {−1, 1} × R, the noise y − x is distributed
according to the Gaussian distribution of zero mean and
standard derivation σ of the channel
Pr(y|x) =
1
σ
√
2π
e−(y−x)2
2σ2
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 54/84
SHANNON CHANNEL CAPACITY
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 55/84
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 55/84
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 BIAGWN channels, that well capture deep space channels, this limit is (by so-called
Shannon-Hartley theorem):
R < W log 1 +
S
N
{bits per second}
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 55/84
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 BIAGWN channels, that well capture deep space channels, this limit is (by so-called
Shannon-Hartley theorem):
R < W log 1 +
S
N
{bits per second}
Shannon capacity sets a limit to the energy efficiency of the code.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 55/84
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 BIAGWN channels, that well capture deep space channels, this limit is (by so-called
Shannon-Hartley theorem):
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 so called Shannon capacity approaching codes, and practical
codes required about twice as much energy as theoretical minimum predicted.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 55/84
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 BIAGWN channels, that well capture deep space channels, this limit is (by so-called
Shannon-Hartley theorem):
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 so called 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 55/84
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 BIAGWN channels, that well capture deep space channels, this limit is (by so-called
Shannon-Hartley theorem):
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 so called 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, discussed later, have such a Shannon capacity
approaching property.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 55/84
CONCATENATED CODES - I
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 56/84
CONCATENATED CODES - I
The basic idea of concatenated codes is extremely simple.
A given message is first encoded by the first (outer) code
C1 (Cout) and C1-output is then encoded by the second
code C2 (Cin). To decode, at first C2 decoding and then
C1 decoding are used.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 56/84
CONCATENATED CODES - I
The basic idea of concatenated codes is extremely simple.
A given message is first encoded by the first (outer) code
C1 (Cout) and C1-output is then encoded by the second
code C2 (Cin). To decode, at first C2 decoding and then
C1 decoding are used.
outer
encoder
inner
encoder
inner
decoder
outer
decoder
super decodersuper encoder
noisy
channel
super
channel
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 56/84
CONCATENATED CODES II.
In 1962 Formey showed that concatenated codes could be
used to achieve exponentially decreasing error probabilities
at all data rates less than channel capacity in such a way
that decoding complexity increases only polynomially with
the code block length.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 57/84
CONCATENATED CODES II.
In 1962 Formey showed that concatenated codes could be
used to achieve exponentially decreasing error probabilities
at all data rates less than channel capacity in such a way
that decoding complexity increases only polynomially with
the code block length.
In 1965 concatenated codes were considered as unfeasible.
However, already in 1970s technology has advanced
sufficiently and they became standardize by NASA for
space applications.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 57/84
CONCATENATED CODES BRIEFLY
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 58/84
CONCATENATED CODES BRIEFLY
A code concatenated codes Cout and Cin maps a message
m = (m1, m2, . . . , mK ),
as follows: At first Cout encoding is applied to get
Cout(m1, m2, . . . , mk) = (m1, m2, . . . , mN)
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 58/84
CONCATENATED CODES BRIEFLY
A code concatenated codes Cout and Cin maps a message
m = (m1, m2, . . . , mK ),
as follows: At first Cout encoding is applied to get
Cout(m1, m2, . . . , mk) = (m1, m2, . . . , mN)
and then Cin encoding is applied to get
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 58/84
CONCATENATED CODES BRIEFLY
A code concatenated codes Cout and Cin maps a message
m = (m1, m2, . . . , mK ),
as follows: At first Cout encoding is applied to get
Cout(m1, m2, . . . , mk) = (m1, m2, . . . , mN)
and then Cin encoding is applied to get
Cin(m1), Cin(m2), . . . , Cin(mN)
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 58/84
BCH CODES and REED-SOLOMON CODES
2
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 59/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
2
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 59/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
2
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 59/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code2
of the 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.
2
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 59/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code2
of the 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.
2
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 59/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code2
of the 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.
Applications of BCH codes: satellite communications, compact disc players,disk drives,
two-dimensional bar codes,...
2
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 59/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code2
of the 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.
Applications of BCH codes: satellite communications, compact disc players,disk drives,
two-dimensional bar codes,...
Comments: For BCH codes there exist efficient variations of syndrome decoding.
2
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 59/84
BCH CODES and REED-SOLOMON CODES
BCH codes and Reed-Solomon codes belong to the most important codes for
applications.
Definition A polynomial p is said to be a minimal polynomial for a complex number x
in GF(q) if p(x) = 0 and p is irreducible over GF(q).
Definition A cyclic code of codewords of length n over GF(q), where q is a power of a
prime p, is called BCH code2
of the 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.
Applications of BCH codes: satellite communications, compact disc players,disk drives,
two-dimensional bar codes,...
Comments: For BCH codes there exist efficient variations of syndrome decoding. A
Reed-Solomon code is a special primitive BCH code.
2
BHC stands for Bose and Ray-Chaudhuri and Hocquenghem who discovered these codes in 1959.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 59/84
UNIQUE DECODING versus LIST DECODING
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 60/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 60/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
This list decoding error-correction task/model is not sufficiently good in case when the
number of error can be large.
In the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 60/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
This list decoding error-correction task/model is not sufficiently good in case when the
number of error can be large.
In the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
List decoding is considered to be successful in case the outputted list contains the
codeword that was sent.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 60/84
UNIQUE DECODING versus LIST DECODING
In the unique decoding model of error-correction, considered so far, the task is to find,
for a received (corrupted) message wc , the closest (and therefore unique) codeword w to
the one which was sent when the message wc was received.
This list decoding error-correction task/model is not sufficiently good in case when the
number of error can be large.
In the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
List decoding is considered to be successful in case the outputted list contains the
codeword that was sent.
It has turned out that for a variety of important codes, say for Reed-Solomon codes, there
are efficient algorithms for list decoding that allow to correct a large variety of errors.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 60/84
LIST DECODING
The notion of list-decoding, as a relaxed error-correcting mode, was proposed by Elias in
1950s.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 61/84
LIST DECODING
The notion of list-decoding, as a relaxed error-correcting mode, was proposed by Elias in
1950s.
In the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 61/84
LIST DECODING
The notion of list-decoding, as a relaxed error-correcting mode, was proposed by Elias in
1950s.
In the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
With list decoding the error-correction performance doubles.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 61/84
LIST DECODING
The notion of list-decoding, as a relaxed error-correcting mode, was proposed by Elias in
1950s.
In the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
With list decoding the error-correction performance doubles.
It has been shown, non-constructively, that codes of the rate R exist that can be list
decoded up to a fraction of errors approaching 1 − R.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 61/84
LIST DECODING
The notion of list-decoding, as a relaxed error-correcting mode, was proposed by Elias in
1950s.
In the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
With list decoding the error-correction performance doubles.
It has been shown, non-constructively, that codes of the rate R exist that can be list
decoded up to a fraction of errors approaching 1 − R.
The quantity 1 − R is referred to as the list decoding capacity.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 61/84
LIST DECODING
The notion of list-decoding, as a relaxed error-correcting mode, was proposed by Elias in
1950s.
In the list decoding model the task is for a received (corrupted) message wc and a given
to output (list of) all codewords with the distance at most ε from the codeword that
was sentwc .
With list decoding the error-correction performance doubles.
It has been shown, non-constructively, that codes of the rate R exist that can be list
decoded up to a fraction of errors approaching 1 − R.
The quantity 1 − R is referred to as the list decoding capacity.
For Reed-Solomon codes there is list decoding up to 1 −
√
2R errors.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 61/84
LISToT DECODING III
List decoding is considered to be successful in case the outputted list contains the
codeword that was sent.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 62/84
LISToT DECODING III
List decoding is considered to be successful in case the outputted list contains the
codeword that was sent.
It has turned out that for a variety of important codes, say for Reed-Solomon codes, there
are efficient algorithms for list decoding that allow to correct a large variety of errors.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 62/84
LISToT DECODING III
List decoding is considered to be successful in case the outputted list contains the
codeword that was sent.
It has turned out that for a variety of important codes, say for Reed-Solomon codes, there
are efficient algorithms for list decoding that allow to correct a large variety of errors.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 62/84
CHANNEL (STREAMS) CODING
CHANNELS (STREAMS) CODING
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 63/84
CHANNEL CODING - BASICS
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 64/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 64/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 64/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology.
How well can channel coding be done?
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 64/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology.
How well can channel coding be done? So called Shannon’s channel coding theorem
says that over many common channels there exist data coding schemes that are able to
transmit data reliably at all code rates smaller than a certain threshold, called nowadays
the Shannon channel capacity, of the given channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 64/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology.
How well can channel coding be done? So called Shannon’s channel coding theorem
says that over many common channels there exist data coding schemes that are able to
transmit data reliably at all code rates smaller than a certain threshold, called nowadays
the Shannon channel capacity, of the given channel.
Moreover, the theorem says that probability of a decoding error can be made to decrease
exponentially as the block length N of the coding scheme goes to infinity.
However, the complexity of a ”naive”, or straightforward, optimum decoding schemes
increased exponentially with N - therefore such an optimum decoder rapidly become
unfeasible.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 64/84
CHANNEL CODING - BASICS
Channel coding is concerned with sending streams of data, at the highest possible
rate, over a given communication channel and then obtaining the original data
reliably, at the receiver side, by using encoding and decoding algorithms that are
feasible to implement in available technology.
How well can channel coding be done? So called Shannon’s channel coding theorem
says that over many common channels there exist data coding schemes that are able to
transmit data reliably at all code rates smaller than a certain threshold, called nowadays
the Shannon channel capacity, of the given channel.
Moreover, the theorem says that probability of a decoding error can be made to decrease
exponentially as the block length N of the coding scheme goes to infinity.
However, the complexity of a ”naive”, or straightforward, optimum decoding schemes
increased exponentially with N - therefore such an optimum decoder rapidly become
unfeasible.
A breakthrough came when D. Forney, in his PhD thesis in 1972, showed that so called
concatenated codes could be used to achieve exponentially decreasing error probabilities
at all data rates less than the Shannon channel capacity, with decoding complexity
increasing only polynomially with the code length.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 64/84
CHANNEL (STREAMS) CODING I.
Therefore, 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 65/84
CHANNEL (STREAMS) CODING I.
Therefore, 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 65/84
CHANNEL (STREAM) CODING II
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 66/84
CHANNEL (STREAM) CODING II
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 66/84
CHANNEL (STREAM) CODING II
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;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 66/84
CHANNEL (STREAM) CODING II
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 from the environment;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 66/84
CHANNEL (STREAM) CODING II
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 from the environment;
use smaller antennas;
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 66/84
CHANNEL (STREAM) CODING II
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 from the environment;
use smaller antennas;
transmit at a higher data rate.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 66/84
CHANNEL CAPACITY
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 67/84
CHANNEL CAPACITY
Channel capacity of a communication channel, is the
tightest upper bound on the (code) rate of information
that can be reliably transmitted over that channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 67/84
CHANNEL CAPACITY
Channel capacity of a communication channel, is the
tightest upper bound on the (code) rate of information
that can be reliably transmitted over that channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 67/84
CHANNEL CAPACITY
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 68/84
CHANNEL CAPACITY
Channel capacity of a communication channel, is the
tightest upper bound on the (code) rate of information
that can be reliably transmitted over that channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 68/84
CHANNEL CAPACITY
Channel capacity of a communication channel, is the
tightest upper bound on the (code) rate of information
that can be reliably transmitted over that channel.
By the noisy-channel Shannon coding theorem, the
channel capacity of a given channel is the limiting code
rate (in units of information per unit time) that can be
achieved with arbitrary small error probability.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 68/84
CHANNEL CAPACITY - FORMAL DEFINITION
Let X and Y be random variables representing the input and output of a channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 69/84
CHANNEL CAPACITY - FORMAL DEFINITION
Let X and Y be random variables representing the input and output of a channel.
Let PY |X (y|x) be the conditional probability distribution function of Y given X, which
can be seen as an inherent fixed probability of the communication channel.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 69/84
CHANNEL CAPACITY - FORMAL DEFINITION
Let X and Y be random variables representing the input and output of a channel.
Let PY |X (y|x) be the conditional probability distribution function of Y given X, which
can be seen as an inherent fixed probability of the communication channel.
The joint distribution PX,Y (x, y) is then defined by
PX,Y (x, y) = PY |X (y|x)PX (x),
where PX (x) is the marginal distribution.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 69/84
CANNEL ENCODING
CANNEL ENCODING On the other hand such codes require larger
bandwidth and decoding is usually of higher complexity.
CANNEL ENCODING 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.
CANNEL ENCODING 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 70/84
APPENDIX - II.
APPENDIX II.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 71/84
LOCALLY DECODABLE CODES -I
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 72/84
LOCALLY DECODABLE CODES -I
Classical error-correcting codes allow one to encode an n-bit message w into an N-bit
codeword C(w), in such a way that w can still be recovered even if C(w) gets corrupted
in a number of bits.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 72/84
LOCALLY DECODABLE CODES -I
Classical error-correcting codes allow one to encode an n-bit message w into an N-bit
codeword C(w), in such a way that w can still be recovered even if C(w) gets corrupted
in a number of bits.
The disadvantage of the classical error-correcting codes is that one needs to consider all,
or at least most of, the (corrupted) codeword to recover anything about w.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 72/84
LOCALLY DECODABLE CODES -I
Classical error-correcting codes allow one to encode an n-bit message w into an N-bit
codeword C(w), in such a way that w can still be recovered even if C(w) gets corrupted
in a number of bits.
The disadvantage of the classical error-correcting codes is that one needs to consider all,
or at least most of, the (corrupted) codeword to recover anything about w. On the other
hand so-called locally decodable codes allow reconstruction of any arbitrary bit wi , from
looking only at k randomly chosen bits of C(w), where k is as small as 3.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 72/84
LOCALLY DECODABLE CODES -I
Classical error-correcting codes allow one to encode an n-bit message w into an N-bit
codeword C(w), in such a way that w can still be recovered even if C(w) gets corrupted
in a number of bits.
The disadvantage of the classical error-correcting codes is that one needs to consider all,
or at least most of, the (corrupted) codeword to recover anything about w. On the other
hand so-called locally decodable codes allow reconstruction of any arbitrary bit wi , from
looking only at k randomly chosen bits of C(w), where k is as small as 3.
Locally decodable codes have a variety of applications in cryptography and theory of
fault-tolerant computation.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 72/84
LOCALLY DECODABLE CODES -II
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 73/84
LOCALLY DECODABLE CODES -II
Locally decodable codes have another remarkable property:
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 73/84
LOCALLY DECODABLE CODES -II
Locally decodable codes have another remarkable property:
A message can be encoded in such a way that should a
small enough fraction of its symbols die in the transit, we
could, with high probability, to recover the original bit
anywhere in the message we choose.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 73/84
LOCALLY DECODABLE CODES -II
Locally decodable codes have another remarkable property:
A message can be encoded in such a way that should a
small enough fraction of its symbols die in the transit, we
could, with high probability, to recover the original bit
anywhere in the message we choose.
Moreover, this can be done by picking at random only
three bits of the received message and combining them in
a right way.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 73/84
TURBO codes
TURBO CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 74/84
EXAMPLE from SPACE EXPLORATION
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 75/84
EXAMPLE from SPACE EXPLORATION
At the very beginning of the Galileo mission to explore
Jupiter and its moons in 1989 it was discovered that
primary antenna (deployed in the figure on the top) failed
to deploy,
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 75/84
GALILEO MISSION - SOLUTION
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 76/84
GALILEO MISSION - SOLUTION
The primary antenna was designed to send 100, 000 b/s. Spacecraft had also another
antenna, but that was capable to send only 10 b/s. The whole mission looked as being a
disaster.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 76/84
GALILEO MISSION - SOLUTION
The primary antenna was designed to send 100, 000 b/s. Spacecraft had also another
antenna, but that was capable to send only 10 b/s. The whole mission looked as being a
disaster.
A heroic engineering effort was immediately undertaken in the mission center to design
the most powerful concatenated code conceived up to that time, and to program it into
the spacecraft computer.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 76/84
GALILEO MISSION - SOLUTION
The primary antenna was designed to send 100, 000 b/s. Spacecraft had also another
antenna, but that was capable to send only 10 b/s. The whole mission looked as being a
disaster.
A heroic engineering effort was immediately undertaken in the mission center to design
the most powerful concatenated code conceived up to that time, and to program it into
the spacecraft computer.
The inner code was a 214
convolution code, decoded by the Viterbi algorithm.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 76/84
GALILEO MISSION - SOLUTION
The primary antenna was designed to send 100, 000 b/s. Spacecraft had also another
antenna, but that was capable to send only 10 b/s. The whole mission looked as being a
disaster.
A heroic engineering effort was immediately undertaken in the mission center to design
the most powerful concatenated code conceived up to that time, and to program it into
the spacecraft computer.
The inner code was a 214
convolution code, decoded by the Viterbi algorithm.
The outer code consisted of multiple Reed-Solomon codes of varying length.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 76/84
GALILEO MISSION - SOLUTION
The primary antenna was designed to send 100, 000 b/s. Spacecraft had also another
antenna, but that was capable to send only 10 b/s. The whole mission looked as being a
disaster.
A heroic engineering effort was immediately undertaken in the mission center to design
the most powerful concatenated code conceived up to that time, and to program it into
the spacecraft computer.
The inner code was a 214
convolution code, decoded by the Viterbi algorithm.
The outer code consisted of multiple Reed-Solomon codes of varying length. After all
reparations and new encodings it was possible to send up to 1000 b/s.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 76/84
GALILEO MISSION - SOLUTION
The primary antenna was designed to send 100, 000 b/s. Spacecraft had also another
antenna, but that was capable to send only 10 b/s. The whole mission looked as being a
disaster.
A heroic engineering effort was immediately undertaken in the mission center to design
the most powerful concatenated code conceived up to that time, and to program it into
the spacecraft computer.
The inner code was a 214
convolution code, decoded by the Viterbi algorithm.
The outer code consisted of multiple Reed-Solomon codes of varying length. After all
reparations and new encodings it was possible to send up to 1000 b/s. Mission was
rescued.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 76/84
GALILEO MISSION - SOLUTION
The primary antenna was designed to send 100, 000 b/s. Spacecraft had also another
antenna, but that was capable to send only 10 b/s. The whole mission looked as being a
disaster.
A heroic engineering effort was immediately undertaken in the mission center to design
the most powerful concatenated code conceived up to that time, and to program it into
the spacecraft computer.
The inner code was a 214
convolution code, decoded by the Viterbi algorithm.
The outer code consisted of multiple Reed-Solomon codes of varying length. After all
reparations and new encodings it was possible to send up to 1000 b/s. Mission was
rescued.
Nowadays when so called iterative decoding is used concatenation of even very simple
codes can yield superb performance.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 76/84
TURBO CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 77/84
TURBO CODES
Channel coding was revolutionized by the invention of Turbo codes.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 77/84
TURBO CODES
Channel coding was revolutionized by the invention of Turbo codes. Turbo codes were
introduced by Berrou, Glavieux and Thitimajshima in 1993. Turbo codes are specified by
special encodings.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 77/84
TURBO CODES
Channel coding was revolutionized by the invention of Turbo codes. Turbo codes were
introduced by Berrou, Glavieux and Thitimajshima in 1993. Turbo codes are specified by
special encodings.
A Turbo code can be seen as formed from a parallel composition of two (convolution)
codes separated by an interleaver (that permutes blocks of data in a fixed
(pseudo)-random way).
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 77/84
TURBO CODES
Channel coding was revolutionized by the invention of Turbo codes. Turbo codes were
introduced by Berrou, Glavieux and Thitimajshima in 1993. Turbo codes are specified by
special encodings.
A Turbo code can be seen as formed from a 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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 77/84
EXAMPLES of TURBO and CONVOLUTION ENCODERS
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 78/84
EXAMPLES of TURBO and CONVOLUTION ENCODERS
A Turbo encoder
input x
interleaver
convolution
i
convolution
encoder
encoder
parity bit b1
parity bit b2
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 78/84
EXAMPLES 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
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 78/84
ADVANTAGES of INTERLEAVING
let us assume that a word
cenaje200kc
is transmitted
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 79/84
ADVANTAGES of INTERLEAVING
let us assume that a word
cenaje200kc
is transmitted and during the transmission symbols 7-10 are lost to get:
cenaje....c
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 79/84
ADVANTAGES of INTERLEAVING
let us assume that a word
cenaje200kc
is transmitted and during the transmission symbols 7-10 are lost to get:
cenaje....c
In such a case very important information was definitely lost.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 79/84
ADVANTAGES of INTERLEAVING
let us assume that a word
cenaje200kc
is transmitted and during the transmission symbols 7-10 are lost to get:
cenaje....c
In such a case very important information was definitely lost.
However, if the input word is first permuted according to the permutation
3, 8, 7, 9, 10, 1, 2, 6, 4, 11, 5
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 79/84
ADVANTAGES of INTERLEAVING
let us assume that a word
cenaje200kc
is transmitted and during the transmission symbols 7-10 are lost to get:
cenaje....c
In such a case very important information was definitely lost.
However, if the input word is first permuted according to the permutation
3, 8, 7, 9, 10, 1, 2, 6, 4, 11, 5
then the input will be actually the word
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 79/84
ADVANTAGES of INTERLEAVING
let us assume that a word
cenaje200kc
is transmitted and during the transmission symbols 7-10 are lost to get:
cenaje....c
In such a case very important information was definitely lost.
However, if the input word is first permuted according to the permutation
3, 8, 7, 9, 10, 1, 2, 6, 4, 11, 5
then the input will be actually the word
n020kceeacj
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 79/84
ADVANTAGES of INTERLEAVING
let us assume that a word
cenaje200kc
is transmitted and during the transmission symbols 7-10 are lost to get:
cenaje....c
In such a case very important information was definitely lost.
However, if the input word is first permuted according to the permutation
3, 8, 7, 9, 10, 1, 2, 6, 4, 11, 5
then the input will be actually the word
n020kceeacj
and if the same four positions are lost the output will be
n020kc....j
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 79/84
ADVANTAGES of INTERLEAVING
let us assume that a word
cenaje200kc
is transmitted and during the transmission symbols 7-10 are lost to get:
cenaje....c
In such a case very important information was definitely lost.
However, if the input word is first permuted according to the permutation
3, 8, 7, 9, 10, 1, 2, 6, 4, 11, 5
then the input will be actually the word
n020kceeacj
and if the same four positions are lost the output will be
n020kc....j
However, after the inverse permutation the output actually will be
c.n.j.200k.
which is quite easy to decode correctly!!!!
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 79/84
DECODING and PERFORMANCE of TURBO CODES
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 80/84
DECODING and PERFORMANCE of TURBO CODES
A soft-in-soft-out decoding is usually 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 80/84
DECODING and PERFORMANCE of TURBO CODES
A soft-in-soft-out decoding is usually 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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 80/84
DECODING and PERFORMANCE of TURBO CODES
A soft-in-soft-out decoding is usually 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. pause
Turbo codes performance can be very close to theoretical Shannon limit.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 80/84
DECODING and PERFORMANCE of TURBO CODES
A soft-in-soft-out decoding is usually 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. pause
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 blocks of 40 bits.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 80/84
DECODING and PERFORMANCE of TURBO CODES
A soft-in-soft-out decoding is usually 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. pause
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 blocks of 40 bits.
Turbo codes were incorporated into standards used by NASA for deep space
communications, digital video broadcasting and both third generation cellular
standards.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 80/84
DECODING and PERFORMANCE of TURBO CODES
A soft-in-soft-out decoding is usually 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. pause
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 blocks of 40 bits.
Turbo codes were incorporated into standards used by NASA for deep space
communications, digital video broadcasting and both third generation cellular
standards.
Literature: M.C. Valenti and J.Sun: Turbo codes - tutorial, Handbook of RF and
Wireless Technologies, 2004 - reachable by Google.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 80/84
REACHING SHANNON LIMIT
Though Shannon developed his capacity bound already in 1940, till recently code
designers were unable to come with codes with performance close to theoretical limit.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 81/84
REACHING SHANNON LIMIT
Though Shannon developed his capacity bound already in 1940, till recently code
designers were unable to come with codes with performance close to theoretical limit.
In 1990 the gap between theoretical bound and practical implementations was still
at best about 3dB
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 81/84
REACHING SHANNON LIMIT
Though Shannon developed his capacity bound already in 1940, till recently code
designers were unable to come with codes with performance close to theoretical limit.
In 1990 the gap between theoretical bound and practical implementations was still
at best about 3dB
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 81/84
Decibel
The decibel dB is a number that represents a logarithm of the ration of two values of a
quantity (such as value dB = 20 log(V1/V 2)
A decibel is a relative measure. If E is the actual energy and Eref is the theoretical lower
bound, then the relative energy increase in decibels is
10 log10
E
Eref
Since log10 2 = 0.3 a two-fold relative energy increase equals 3dB.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 82/84
Turbo codes performance can be very close to theoretical Shannon limit.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 83/84
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 blocks of 40 bits.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 83/84
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 blocks of 40 bits.
Turbo codes were incorporated into standards used by NASA for deep space
communications, digital video broadcasting and both third generation cellular
standards.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 83/84
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 blocks of 40 bits.
Turbo codes were incorporated into standards used by NASA for deep space
communications, digital video broadcasting and both third generation cellular
standards.
Literature: M.C. Valenti and J.Sun: Turbo codes - tutorial, Handbook of RF and
Wireless Technologies, 2004 - reachable by Google.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 83/84
TURBO CODES - SUMMARY
Turbo codes encoding devices are usually built from two (usually identical) recursive
systematic convolution encoders, linked together by nonuniform interleaver
(permutation) devices.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 84/84
TURBO CODES - SUMMARY
Turbo codes encoding devices are usually built from two (usually identical) recursive
systematic convolution encoders, linked together by nonuniform interleaver
(permutation) devices.
For decoding of Turbo codes so called soft decoding is used. Soft decoding is an
iterative process in which each component decoder takes advantage of the work of
other at the previous step, with the aid of the original concept of intrinsic
information.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 84/84
TURBO CODES - SUMMARY
Turbo codes encoding devices are usually built from two (usually identical) recursive
systematic convolution encoders, linked together by nonuniform interleaver
(permutation) devices.
For decoding of Turbo codes so called soft decoding is used. Soft decoding is an
iterative process in which each component decoder takes advantage of the work of
other at the previous step, with the aid of the original concept of intrinsic
information.
For sufficiently large size of interleavers, the correcting performance of turbo codes,
as shown by simulations, appears to be close to the theoretical Shannon limit.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 84/84
TURBO CODES - SUMMARY
Turbo codes encoding devices are usually built from two (usually identical) recursive
systematic convolution encoders, linked together by nonuniform interleaver
(permutation) devices.
For decoding of Turbo codes so called soft decoding is used. Soft decoding is an
iterative process in which each component decoder takes advantage of the work of
other at the previous step, with the aid of the original concept of intrinsic
information.
For sufficiently large size of interleavers, the correcting performance of turbo codes,
as shown by simulations, appears to be close to the theoretical Shannon limit.
Permutations performed by interleaver can often by specified by simple polynomials
that make one-to-one mapping of some sets {0, 1, . . . , q − 1}.
Turbo codes are linear codes.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 84/84
TURBO CODES - SUMMARY
Turbo codes encoding devices are usually built from two (usually identical) recursive
systematic convolution encoders, linked together by nonuniform interleaver
(permutation) devices.
For decoding of Turbo codes so called soft decoding is used. Soft decoding is an
iterative process in which each component decoder takes advantage of the work of
other at the previous step, with the aid of the original concept of intrinsic
information.
For sufficiently large size of interleavers, the correcting performance of turbo codes,
as shown by simulations, appears to be close to the theoretical Shannon limit.
Permutations performed by interleaver can often by specified by simple polynomials
that make one-to-one mapping of some sets {0, 1, . . . , q − 1}.
Turbo codes are linear codes.
A ”good” linear code is one that has mostly high-weight codewords.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 84/84
TURBO CODES - SUMMARY
Turbo codes encoding devices are usually built from two (usually identical) recursive
systematic convolution encoders, linked together by nonuniform interleaver
(permutation) devices.
For decoding of Turbo codes so called soft decoding is used. Soft decoding is an
iterative process in which each component decoder takes advantage of the work of
other at the previous step, with the aid of the original concept of intrinsic
information.
For sufficiently large size of interleavers, the correcting performance of turbo codes,
as shown by simulations, appears to be close to the theoretical Shannon limit.
Permutations performed by interleaver can often by specified by simple polynomials
that make one-to-one mapping of some sets {0, 1, . . . , q − 1}.
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 84/84
TURBO CODES - SUMMARY
Turbo codes encoding devices are usually built from two (usually identical) recursive
systematic convolution encoders, linked together by nonuniform interleaver
(permutation) devices.
For decoding of Turbo codes so called soft decoding is used. Soft decoding is an
iterative process in which each component decoder takes advantage of the work of
other at the previous step, with the aid of the original concept of intrinsic
information.
For sufficiently large size of interleavers, the correcting performance of turbo codes,
as shown by simulations, appears to be close to the theoretical Shannon limit.
Permutations performed by interleaver can often by specified by simple polynomials
that make one-to-one mapping of some sets {0, 1, . . . , q − 1}.
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.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 84/84
TURBO CODES - SUMMARY
Turbo codes encoding devices are usually built from two (usually identical) recursive
systematic convolution encoders, linked together by nonuniform interleaver
(permutation) devices.
For decoding of Turbo codes so called soft decoding is used. Soft decoding is an
iterative process in which each component decoder takes advantage of the work of
other at the previous step, with the aid of the original concept of intrinsic
information.
For sufficiently large size of interleavers, the correcting performance of turbo codes,
as shown by simulations, appears to be close to the theoretical Shannon limit.
Permutations performed by interleaver can often by specified by simple polynomials
that make one-to-one mapping of some sets {0, 1, . . . , q − 1}.
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.
A turbo code can be seen as a refinement of concatenated codes plus an iterative
algorithm for decoding.
IV054 1. Linear, Cyclic, stream and channel codes. Speccial decodings 84/84