LINEAR BLOCK CODES
The (n, k)
notation describes a family of parity check codes known as block codes. Forward
error correction codes are implemented using block codes. Linear Block Codes
are defined as block codes that have the property of linearity. Modulo-2
addition of any two codewords produces another acceptable codeword in a linear
code. Linear Block codes can be used in several ways such as:
1. Hamming
Codes
2. Cyclic
Codes
3. BCH Codes
4. Golay
Codes
5.
Reed-Solomon codes
• Systematic
linear block codes are linear block codes in which the superfluous bits are
introduced in such a way that the message bits appear first, followed by the
redundant bits.
•
Non-systematic linear block codes are linear block codes in which superfluous
bits are inserted in such a way that it is impossible to distinguish between
message bits and redundant bits.
Principles
of linear block codes
The functional diagram of a channel encoder for producing systematic linear block codes is shown in Figure 1.
Figure 1: Functional diagram of block
coder
• A block of
'k' message bits is created from the incoming binary data sequence. As a
result, each message block may be thought of as a message vector 'M'.
M = (m1
m2 …… mk) ---------------------- (1)
• Each block
of message input is given (n-k) check bits (redundant bits) by the channel
encoder. Allow n–k = q. According to the encoding rule, the 'q' check bits are
calculated from the message bits. The check bits vector 'c' is then used.
C = (c1
c2 ….. cq) ---------- (2)
• In the
encoder, 'q' check bits are inserted for each block of 'k' message bits. As a
result, the codeword generated at the encoder's output has a total bit length
of k + q = n. As a result, such codes are known as (n, k) linear block codes.
• At the
encoder's output, the code vector 'X' is
X = (m1
m2 ……. mk c1 c2 ……. cq)
= (M ⋮ C) -------------- (3)
Here M is of
order 1 x k
C is of order
1 x q, where q = n – k
and X is of
order 1 x n
• Let G
denote the k x n generator matrix used by the encoder to produce check
bits. The output code vector is given as:
X = M . G
This may be
expressed as a matrix as
[𝑋]1 x 𝑛 =
[𝑀]1 x 𝑘.[𝐺]𝑘 x 𝑛 --------------- (4)
• The
generator matrix is determined by the linear block code type. It is generally
shown as
[𝐺]𝑘 x 𝑛 = [𝐼𝑘 x 𝑘 ⋮ 𝑃𝑘 x 𝑞]𝑘 x 𝑛 -------------------- (5)
Where 𝐼𝑘 x 𝑘 = k x k Identity matrix given by
and 𝑃𝑘 x 𝑞 = k x q submatrix or coefficient
matrix.
𝑃𝑘 x 𝑞 is given by
• The check
bits vector may be obtained from this submatrix.
The check
bits vector, [𝐶]1 x 𝑞 = [𝑀]1
x 𝑘 . [𝑃]𝑘 x 𝑞 -------------- (7)
• When we
substitute the matrix form, we get
• The check
bits vector may be obtained by solving the given matrix equation. The check
bits are:
c1
= m1p11 Ꚛ m2 p21 Ꚛ …… Ꚛmk pk1
c2 =
m1p12 Ꚛ m2 p22 Ꚛ ……
Ꚛ mk pk2 --------------- (9)
cq
= m1p1q Ꚛ m2 p2q Ꚛ …… Ꚛ mkpkq
Here all the
additions are mod-2 addition.