006-012

IPASJ International Journal of Electronics & Communication (IIJEC)
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
A Publisher for Research Motivation........
Volume 2, Issue 10, October 2014
A Mathematical Derivation for Error
Correction and Detection in Communication
using BCH Codes
P.Mozhiarasi1, Ms.C.Gayathri2
1
(ME Student VLSI Design, Sri Eshwar College of Engineering, Coimbatore, Tamil Nadu, India)
2
(Asst. Prof Department of ECE, Eshwar College of Engineering, Coimbatore, Tamil Nadu, India)
3
Third Author Affiliation with address
ABSTRACT
In this paper, (15,5,3)BCH encoder and decoder are designed using mathematical derivation. The codeword length(n), message
length(k) and maximum number of correctable errors(t) are 15, 5 and 3 respectively. The encoding and decoding is done over
the Galois Field GF(24) with an irreducible polynomial of x4 +x+1. The redundant bits(R(X)) are appended with the message
bit, to form a codeword in encoder part and it is transmitted through the channel. In the meanwhile, the Flash memory is used
to store codeword, later for correction part in decoder side. Decoder includes 3 major steps: 1) The Syndrome calculation(SC) is
carried out with the received polynomial(r(x)) and minimum polynomial for detecting errors.2) Berlekamp Massey Algorithm
(BMA) helps in finding the location of the error if error is identified in the received codeword. 3)The Chein Search(CS)
method finds the error. The error is then corrected effectively.
Keywords: BCH (Bose Chaudhuri Hocquenghem), Syndrome calculation(SC), Berlekamp Massey Algorithm (BMA),
Chein Search(CS)
1. INTRODUCTION
In digital communication, the data is transmitted through the channel [Figure 1] to the receiver side [11]. If noise is
included in the channel, data that is received at the receiver side will not be the actual data. This may create a
corruption of data which is unacceptable. There are lots of Error Correcting Codes (ECC) available, one among them is
BCH codes[10]. BCH codes have many advantages compared to other codes. They include cost effective, reliable and
powerful tool for correcting errors. They reduce the complexity, increase the throughput and there is a flexibility in
selection of codeword lengths(n) and code rate(r = k / n). These codes can detect upto ‘t’ random errors which is
generalization of Hamming codes for multiple error correction. BCH codes are mostly preferred for their simplicity. In
encoder stage, the message bit is padded with zeroes which is then divided with the generator polynomial to obtain the
remainder which is known as redundant bit(R(X)). If remainder is zero then no error in codeword otherwise
error(Syndrome) is present. The decoder has three pipelined stages namely Syndrome calculation, Berlekamp Massey
Algorithm and Chien Search. This syndrome calculation operates over Galois Field(GF) which is also known as Finite
Field[12]. Galois Field(GF) is a set of finite number of elements that may add, subtract, multiply, divide the field
elements and one more field element within that set is obtained. GF(2) is called Base Field, then GF(2m) is an extension
field. The properties of field element are applied for syndrome calculation in decoding stage. The Berlekamp Massey
Algorithm(BMA)[14] is used for finding error locator polynomial[3]. It uses a “Key Equation”[5] by providing known
number of coefficients of generating function to determine remaining coefficients of the polynomial. After finding the
coefficients of the polynomial[1] the perfects roots are identified and these roots are given to the Chien Search
Algorithm. The Chien Search (CS) Algorithm finds the error location in the received polynomial by inversing the
obtained roots. By performing modulo-2 addition for received polynomial and error pattern polynomial, the actual data
is retrieved. This technique may be applicable for banking account, digital television, satellite, wireless or mobile
communication etc., In this paper (15,5)BCH encoder and decoder are designed[Figure 2] and they can detect and
correct upto triple errors in any position of 15 bit codeword. In early stage, each character is a text message which is
converted to a 5 bit binary data and is encoded to form 15 bit codeword. The BCH decoder is implemented with
Berlekamp Massey Algorithm(BMA) and Chien Search (CS) Algorithm.
Volume 2, Issue 10, October 2014
Page 6
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivation........
Volume 2, Issue 10, October 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
Figure 1 Data transmission (a) Transmitter side (b) Receiver side
2. BCH CODES
BCH(Bose Chaudhuri Hocquenghem) code[14] is defined by
Codeword length, n = 2m-1
Number of parity check bits, n-k ≤ mt
Minimum distance, dmin ≥ 2t+1
where, m – primitive polynomial
k – message length
t – maximum number of correctable errors
Figure 2 Encoding and decoding process
They are superior error correcting code among the other codes. The generator polynomial g(x) of the code is
represented as roots over Galois Field GF(2m). In this work let us consider m=4, n=2m -1= 24-1=15, k=5, t =3, dmin
=2t+1=2(3)+1=7. The generator polynomial g(x) is obtained by finding roots of polynomial P(x) of degree m which is
primitive if and only if smallest integer n for which p(x) divides xn+1[6]. Here addition is performed by modulo 2addition.
P(x) = (x15 +1) = (x+1) (x4+x+1)(x10+x9+x8+x6+x5+x2+1)
q(x)
p(x)
10
8
5
By inversing the root q(x), generator polynomial g(x) will become x +x +x +x4+x2+x+1. Let fi (x), i= 1,2,3,…,2t be
Volume 2, Issue 10, October 2014
Page 7
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivation........
Volume 2, Issue 10, October 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
the minimal polynomial[3], then g(x) = LCM{f1(x),f2(x),f3(x),…,f2t(x)}. But, g(x)[3] is simplified to g(x) =
LCM{f1(x),f3(x),f5(x),…,f2t-1(x)}[12] because every even power of primitive element will have same minimal polynomial
as some odd power of the elements having the number of factors in the polynomial[13]. Therefore,
g(x) = LCM{f1(x),f3(x),f5(x)}
(see Table 2 & 3)
where
f1(x) = (x+α) (x+α2) (x+α8) (x+α4) = x4+x+1
f3(x) = (x+α3) (x+α6) (x+α12) (x+α9) = x4+x3+x2 +x+1
f5(x) = (x+α5) (x+α10) = x2+x+1
These factors are obtained by primitive polynomial x4+x+1 and conjugates of 16 field elements using Galois Field
theory. (see Table 2)
Table 1: (a) modulo-2 addition
(b) modulo-2 multiplication
Note:
1) Multiplication of two elements of Galois field is done by adding their exponents and applying α15 = 1.
Example: α12. α7 = α19 = α15. α4 = α4
2) Division of two elements of Galois Field is carried out by multiplying numerator with α15, then dividing it by
the denominator. Example α3/ α6 = α18/ α6 = α12
3) Addition of two elements of Galois Field is implemented by using Table 2.Example: α7+ α9 = (α3+α+1) +
(α3+α) = 1 (see Table 1 & 2)
Table 2: GF(16) generated with Primitive polynomial x4+x+1[15]
The polynomial form is obtained by considering first 6 rows of power form. [12]
When α5 is considered, α5= α(α4) = α (α+1) = α2+α,
when α6 is considered, α6 = α(α5) = α (α2+α) = α3+ α2,
finally for α14, α14 = α(α13) = α (α3+α2+1) = α4+ α3+ α = (α+1)+ α3+ α = α3+1.
The 4-Tuple form is obtained from polynomial form by representing them in α3, α2, α, 1 and converted to Decimal
form.
Example: α4 = 0α3+0α2+α+1 = 0011 = 3
Volume 2, Issue 10, October 2014
Page 8
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivation........
Volume 2, Issue 10, October 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
Table 3 Minimal Polynomials of the element in GF(16)
φ1(x)
φ2(x)
φ3(x)
φ4(x)
Conjugate roots
0
1
α,α2,α4,α8
α3,α6,α9,α12
α5,α10
7 11 13 14
α ,α ,α ,α
Minimal polynomial
x
x+1
x4+x+1
x4+x3+x2+x+1
x2+x+1
x4+x3+1
The minimal polynomial can be obtained by using conjugate roots as mentioned below.
Those conjugate roots[1] can be found by considering
,
,
,
where i = 1,2,3,…[14] For example when ‘i’
value is substituted in
, we obtain α,
,
,
and the same procedure is followed for
other roots. Therefore α, α2, α4, α8 are used for finding the minimal polynomial φ1(x)
φ1(x) = (x+α) (x+α2) (x+α4) (x+α8)
= (x2 + (α2+α)x + α3) ( x2+(α4+α8)x+α12)
= (x2+α5x+α3) ( x2+((α+1)+(α2+1))x+α12)
(see Table 2)
= (x2+α5x+α3) ( x2+(α2+α)x+α12)
(see Table 1)
= (x2+α5x+α3) ( x2+ α5x+α12)
= x4+α5x3+α12x2+α5x3+α10x2+ α17x+α3x2+ α8x+α15
= x4+(α5+α5) x3+(α12+α10 +α3) x2+ (α2+ α8 ) x+1
(see Table 2)
0
= x4 +((α3+α2+α+1)+( α2+α+1)+ α3 )x2+ (α2+(α2+1)) x+1 (see Table 1)
= x4+x+1
0
similarly, we can calculate minimal polynomial for φ2(x), φ3(x), φ4(x).
2.1 BCH Encoder
In initial stage, the message polynomial(M(x)) is padded with (n-k) zero bits to form Xn-k M(x) i.e., Xn-k M(x) = X15-5
M(x) = X10 M(x) = M + 0000000000 By Xn-k M(x) mod g(x), the remainder polynomial(R(x)) is obtained which should
be appended with the message polynomial(M(x)) to produce the codeword(c(x)) i.e., c(x) = Xn-k M(x) + R(x). This
codeword is then stored in flash memory, later for correction purpose in decoder stage[10]. These encoder procedure is
illustrated by considering M(x) = 10001.
Therefore, Xn-k M(x) = X10 M(x) = 100010000000000. Dividing Xn-k M(x) by g(x)[4] we obtain remainder polynomial
R(x) = 1110101100 which is then appended with X10 M(x) to get codeword, c(x) = 100011110101100.
2.1 BCH Decoder
R(x)
M(x)
2.2.1 Syndrome Calculation
Let us consider c(x) with 3 errors (t = 3) and represent them as r(x) i.e., when noise is added in the channel while
transmitting the data to the receiver[10]. At the receiver side, let us assume r(x) = 110010110100100. The number of
syndrome elements is 2*t = 6, to find t=3 errors. Those syndrome elements[3] are represented as S1, S2, S3, S4, S5, S6 and
they can be calculated by
S1(x) = r(x) mod f1(x)
S2(x) = r(x) mod f2(x) = r(x) mod f1(x)
S3(x) = r(x) mod f3(x)
S4(x) = r(x) mod f4(x) = r(x) mod f1(x)
S5(x) = r(x) mod f5(x)
S6(x) = r(x) mod f6(x) = r(x) mod f3(x)
By the property of Field element[4] several powers of generating element will have the same minimal polynomial (see
Table 2) When f(x) is polynomial over GF(2), α is an element of GF(2m)[15]. Thus, syndrome polynomial can be
represented as S(x) = S1x + S2x2 + S3x3+…+ S2tx2t.
S1(α) = r(α) mod f1(α) = α3+ α2+ α+1= α12
S2(α2) = r(α2) mod f2(α2) = r(α2) mod f1(α2) = α3+ α= α9
S3(α3) = r(α3) mod f3(α3) = α3+ α2+ α+1= α12
S4(α4) = r(α4) mod f4(α4) = r(α4) mod f1(α4) = α3
S5(α5) = r(α5) mod f5(α5) = α2+ α = α5
Volume 2, Issue 10, October 2014
Page 9
IPASJ International Journal of Electronics & Communication (IIJEC)
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
A Publisher for Research Motivation........
Volume 2, Issue 10, October 2014
S6(α6) = r(α6) mod f6(α) = r(α6) mod f3(α6) = α3+ α = α9
The Syndrome can be calculated by
For S1(α) = r(α) mod f1(α)
r(α) = α14+ α13+ α10+ α8+ α7+ α5+ α2
= (α3+1)+(α3+ α2+1)+(α2+ α+1)+( α2+1)+(α3+α+1)+( α2+ α)+α2
= α3+ α2+ α+1 = α12
f1(α) = α4+ α+1 = (α+1)+α+1 = 0
12
Therefore, S1(α) = α , likewise S2(α2), S3(α3), S4(α4), S5(α5), S6(α6) syndromes can be calculated. If the remainder
equals zero, then it is declared that no error in the codeword or else error(S) is present. So this error will be a seed for
decoding the codeword and to find error location.
2.2.2 Berlekamp Massey Algorithm:
This method has been reduced by a Berlekamp algorithm and error locator polynomial[Table 4] is obtained by iterative
method[1].
Table 4 Finding error locator polynomial
(µ)
-1/2
0
1
2
t=3
(x)
1
1
12
α x+1
α7x2+α12x+1
α25x3+α5x2+α12x+1
dµ
1
S1
α4
α2
-
lµ
0
0
1
2
-
2µ-lµ
-1
0
1
2
-
Note: 1) Lin and Costello notations were used
2) dµ represents discrepancy value
The “Key Equation” is given by
Steps:
= 1 + α12 (1)-1x(1)
= α12x + 1
Volume 2, Issue 10, October 2014
Page 10
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivation........
Volume 2, Issue 10, October 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
2.2.3 Chien Search Algorithm
The roots of
in GF (24) should be found out by following order[2]. If
α11,α12, α13, α14 then they are considered as roots.
Example:
= α25(0)3+ α5 (0)2+ α12(0)+1 = 1 ≠ 0
= α25(1)3+ α5 (1)2+ α12(1)+1
= α10+ α5+ α12+1
= (α2+ α+1)+(α2+ α) +(α3+α2+ α+1)+1
= α3+ α2+ α+1 ≠ 0
= α25(α)3+ α5 (α)2+ α12(α)+1
= α28+ α7+ α13+1
= α13+ α7+ α13+1
= (α3+ α2+1)+(α3+ α+1) +(α3+α2+1)+1
= α3+α ≠ 0
= α25(α2)3+ α5 (α2)2+ α12(α2)+1
= α31+ α9+ α14+1
= α+ α7+ α13+1
= α+(α3+α) +(α3+1)+1 = 0
= α25(α6)3+ α5 (α6)2+ α12(α6)+1
= α25(α18)+ α5(α12)+ α12(α6)+1
= α43+ α17+ α18+1
= α13+ α2+ α3+1
= (α3+α2+α) +α2+α3+1 = 0
= α25(α12)3+ α5 (α12)2+ α12(α12)+1
= α25(α36)+ α5(α24)+ α24+1
= α+α14+ α9+1
= α+ α14+ α9+1
= α+(α3+1) +(α3+ α)+1 = 0
= α25(α14)3+ α5 (α14)2+ α12(α14)+1
= α25(α42)+ α5(α28)+ α26+1
= α7+α3+ α11+1
= (α3+α+1)+ α3 +(α3+ α2+ α) = α3+ α2+1 ≠ 0
2
6
Therefore, α , α , α12 are the roots for
= α25x3+ α5 x2+ α12x+1. The bit position of error location will be the
2
6
12
inverse of their roots (α , α , α ) i.e., 010001000001000
Volume 2, Issue 10, October 2014
Page 11
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivation........
Volume 2, Issue 10, October 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
Thus, the error pattern polynomial can be written as e(x) = x13 + x9+ x3. As a result, the actual data is recovered by
performing modulo-2 addition for r(x) and e(x)[7].
c(x) = r(x) + e(x)
= 110010110100100 + 010001000001000
= 100011110101100
M(x)
R(x)
3. CONCLUSION
The error correcting technique plays an important role in modern communication system. At first, each character in a
text message is transformed to a binary data. (15, 5)BCH encoder and decoder are designed with mathematical
derivations and upto 3 errors can be detected and corrected by using Berlekamp Massey Algorithm (BMA) and Chien
Search (CS). The derived BCH encoder and decoder can be designed in future using hardware description language
(HDL) known as Verilog, VHDL and synthesized by Xilinx ISE 13.2 simulator.
References
[1] Arul K. Subbiah, Somnath Viswanath,”Evolving throughput driven architecture for error correction in NAND
memory”, Arasan Chip Systems Inc. White Paper, February 2010.
[2] Berlekamp.E.R, “Algebraic Coding Theory”, McGrawHill, New York, 1968.
[3] Hank Wallace, “Error Detection and Correction using BCH Codes”, Copyright © 2001 Hank Wallace.
[4] http://en.wikipedia.org/wiki/Polynomial_long_division, an article on polynomial long division in Wikipedia.
[5] Lin. S and Costello Jr. D.J, “Error Control Coding”, Prentice-Hall, New Jersey, 1983.
[6] Paul Garrett “Factoring xn-1: cyclotomic and Aurifeuillian polynomials”, March 16, 2004.
[7] Prashanthi. M, Samundiswary. P,”An Enhanced (15, 5) BCH Decoder Using Verilog HDL”, Pg. No. 4356 - 4361,
International Journal of Advanced Research in Computer and Communication Engineering, Vol. 2, Issue 11,
November 2013.
[8] Rohith S, Pavithra S, “FPGA Implementation of (15, 7) BCH encoder and decoder for text message”, Pg. No. 209214, International Journal of Research and Technology, Vol. 2, Issue 09, September 2013.
[9] Ryoh Fuji-Hara, “Galois Field Manual”, University of Tsukuba, Second edition, June 2008.
[10] Shu Lin, Daniel J. Castello, “Error control coding: Fundamentals and applications”, Prentice-Hall, New Jersey,
1983.
[11] Simon Haykin, “Communication Systems”, 4th Edition, John Wiley & Sons, Inc.
[12] Ass. Prof. Dr Thamer, “Information Theory”.
[13] Wireless Information Transmission Systems Lab, “BCH Codes, Chapter 6”, Institute of Communication
Engineering, National Sun Yat Sen University.
[14] W.W.Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri Codes”, IRE Trans. Inf.
Theory, September 1960.
[15] Yunghsiang S. Han, “BCH Codes”, Graduate Institute of Communication Engineering, National Taipei University
Taiwan.
Volume 2, Issue 10, October 2014
Page 12