Binary Cyclic Codes
A subtype of
linear block codes is binary cyclic codes. They have a lot of important
features. Errors caused by bursts of noise that influence multiple consecutive
bits can be corrected using cyclic codes. Cyclic codes include Hamming, BCH,
and Golay codes, all of which are excellent block codes.
If every
cyclic shift of the code vector creates another code vector, the linear block
code is said to be cyclic.
The
characteristics of a cyclic code are as follows.
(i) Linearity Property: If the modulo-2 sum of any two
codewords produces another acceptable codeword, the code is said to be linear.
(ii) Cyclic Property: If every cyclic shift of a
codeword yields another acceptable code word, the code is said to be cyclic.
Consider the n-bit codeword X = (xn-1, xn-2, ….. x1, x0) as an example.
When we
cyclically shift the above code word to the left side by one bit, the resultant
code word is
X’ = (xn-2, xn-3, ….. x1, x0,
xn-1)
X' is also a
suitable code word in this case. Another valid code vector X" is produced
by one additional cyclic left shift.
X’’ = (xn-3, xn-4, ….. x1, x0,
xn-1, xn-2)
Representation
of codewords by a polynomial
• The cyclic
property indicates that the elements of a codeword of length n can be treated
as the coefficients of a degree polynomial (n-1).
• Consider
the n-bit codeword,
X = (xn-1, xn-2, ….. x1, x0)
------------------- (1)
This code
word may be expressed as a code word polynomial, as shown below:
X (p) = xn-1pn-1 + xn-2pn-2
+ ….. + x1p + x0 ------------------ (2)
X (p) denotes
the degree polynomial (n-1).
The variable
p can be any real number. The coefficients are either 1s or 0s in binary codes.
The location
of the codeword bits is represented by the 'p' power. pn-1 stands
for MSB whereas p0 stands for LSB.
• In the
polynomial X(p), each power of p represents a one-bit cyclic shift in time. As
a result, multiplication of the polynomial X(p) by p can be regarded as a
cyclic shift or rotation to the right, as long as pn = 1.
• We employ
polynomial representation to express cyclic codes for the following reasons.
1. Algebraic
codes are what they are. As a result, algebraic operations like addition,
subtraction, multiplication, and division become exceedingly straightforward.
2. In a
polynomial, the positions of the bits are represented by powers of p.
Generation
of code vectors in the non-systematic form of cyclic codes
• Let M = (mk-1,
mk-2, …… m1, m0) be ‘k’ bits of message
vector. Then it can be represented by the polynomial as,
M(p) = mk-1pk-1 + mk-2pk-2
+ ……+ m1p + m0 ------------- (3)
• The
codeword polynomial X(P) is given as
X (P) = M(P)
. G(P) (3.16)
where G(P) is
called as the generating polynomial of degree ‘q’ (parity or check bits q = n –
k). The generating polynomial is given as
G (P) = pq + gq-1pq-1+ ……..
+ g1p + 1 ------------------ (4)
Here gq-1,
gq-2 ….. g1 are the parity bits.
• If M1,
M2, M3, …… etc. are the other message vectors, then the
corresponding code vectors can be calculated as,
X1
(P) = M1 (P) G (P) -------------- (5)
X2
(P) = M2 (P) G (P)
X3
(P) = M3 (P) G (P) and so on
• All the
above code vectors X1, X2, X3 ….. are in
non-systematic form and they satisfy the cyclic property.
Generation
of code vectors in the systematic form of cyclic codes
• The code
word for the systematic form of cyclic codes is given by
X = (k
message bits ⋮q check bits)
=> X = (mk-1 mk-2
…….. m1 m0⋮ cq-1 cq-2
….. c1 c0) --------------- (6)
• In
polynomial form, the check bits vector can be written as
C(p) = cq-1pq-1 + cq-2pq-2
+ …….. + c1p + c0 ------------- (7)
• In
systematic form, the check bits vector polynomial is obtained by
C(p) = rem[๐๐.๐(๐)/๐บ(๐)] -------------------
(8)
where M(p) is
message polynomial
G(p) is
generating polynomial
‘rem’ is the remainder
of the division
Advantages
of Cyclic Codes
• Cyclic
codes have an excellent mathematical structure and can repair burst mistakes
that span several subsequent bits. This enables the creation of
error-correcting codes that can repair numerous errors quite simply.
• Cyclic
codes' encoding and decoding circuits can be readily constructed using shift
registers; cyclic codes' error-correcting and decoding procedures are simpler
and easier to build. These solutions remove the requirement for huge amounts of
storage (memory) for lookup table decoding. As a result, the codes become more
strong and more effective.
Disadvantages
of cyclic codes
• Even though
error detection is easier, error rectification is significantly more difficult.
This is owing to the complexity of the error-correcting combinational logic
circuit.