 Open Access
 Total Downloads : 629
 Authors : K. Rajani, C. Raju
 Paper ID : IJERTV2IS90689
 Volume & Issue : Volume 02, Issue 09 (September 2013)
 Published (First Online): 25092013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Design and Implementation of Encoder for (15, k) Binary BCH Code Using VHDL
K. Rajani *, C. Raju **
*M.Tech, Department of ECE, G. Pullaiah College of Engineering and Technology, Kurnool
**Assistant Professor, Department of ECE, G. Pullaiah College of Engineering and Technology, Kurnool
Abstract
In this project we have designed and implemented a (15,k)BCH code using VHDL for reliable data transfer in channel with multiple error correction control. The digital logic implementation of binary encoding of multiple error correcting BCH code (15, k) of length n=15 over GF (24) with irreducible primitive polynomial x4+x+1 is organised into shift register circuits. Using the cyclic codes, the reminder b(x) can be obtained in a linear (15k) stage shift register with feedback connections corresponding to the coefficients of the generated polynomial. Three encoder are designed using VHDL to encode the single, double and triple error correcting BCH code (15, k) corresponding to the coefficient of generated polynomial. Information bit is
transmitted in unchanged form upto k clock cycles and during this period parity bits are calculated in the LFSR then the parity bits are transmitted from k+1 to 15 clock cycles. Total 15k numbers of parity bits with k information bits are transmitted in 15 codeword. Here we have implemented (15, 5, 3), (15, 7, 2) and (15, 11, 1) BCH code encoder on Xilinx Spartan 3 FPGA using VHDL and the simulation & synthesis are done using Xilinx ISE 10.1. Also a comparative performance based on synthesis & simulation on FPGA is presented.

Introduction
In a noisy channel when the data is transmitted, at the receiver side it is very difficult to retrieve actual data. It is frequently the case that a digital system must be fully reliable, as a single error may shutdown the whole system, or cause unacceptable corruption of data, e.g. in a bank account [5], [6]. There are so many error correcting methods, one of them is liner block code and the simplest block codes are Hamming codes [1][4]. They are capable of correcting only one random error and therefore are not practically useful, unless a simple error control circuit is required. More sophisticated error correcting codes are the Bose, Chaudhuri and Hocquenghem (BCH) codes that are a generalization of the Hamming codes for multipleerror correction. The (BoseChaudhuriHocquenghem) BCH codes form a large class of powerful random error correcting cyclic codes [7][9] having capable of multiple error correction [8]. BCH codes operate over finite or Galois fields [7]. The mathematical background concerning finite fields is well specified and in recent years the hardware implementation of finite fields has been extensively studied. In recent years there has been an increasing demand for digital transmission and storage system and it has been accelerated by the rapid
development and availability of VLSI technology and digital processing. Programmable Logic Device (PLD) and Field Programmable Gate Arrays (FPGAs) [14],
[15] has revolutionized hardware design and its implementation advantages provides various solution like FPGA is fully reprogrammable and reconfigurable. A design can be automatically converted from the gate level into the layout structure by the place and route software. Xilinx Inc. offers a wide range of components [12] which offers millions gate complexity and flip flops, so even a relatively complex design can be implemented.Here implementation of encoder for (15, k) BCH code organized by LFSR for single, double and triple error correction control using VHDL [16], [17] on FPGA presented and also performance compared based on synthesis and simulation result to understand the device utilization and timing simulation by targeting on Xilinx Spartan 3S 1000 FPGA and XSA 3S1000 Board of Xess Corporation [13]. For simulation and synthesis Xilinx ISE 10.1 is used.
The structure of this paper is as follows. Section II contains a brief description of the BCH code and generated polynomial. Section III contains Encoder Design for multiple error correction. Section IV contains simulation shows FPGA implementation results.

Generated Polynomial of Binary BCH Code Over GF (24)
As the BCH code operate in Galois Field [7], it can be defined by two parameters that are length of codewords (n) and the number of error to be corrected t.
A terrorcorrecting binary BCH code is capable of correcting any combination of t or fewer errors in a block of n = 2m 1 digits. For any positive integer m 3 and t < 2m1, there exists a binary BCH code with the following parameters:
Block length: n = 2m – 1
Number of information bits: k nm*t Minimum distance: dmin 2t + 1.
The generator polynomial of the code is specified in terms of its roots over the Galois field GF (2m) which is explained in [7]. Let _ be a primitive element in GF (2m). The generator polynomial g(x) of
the code is the lowest degree polynomial over GF(2), which has , 2 , 3, 2t as its roots. [g(i)= 0 for 1 i 2t].
Let (x) be the minimum polynomials of then

Design of BCH Encoder on FPGA
BCH encoder is usually implemented with a serial linear feedback shift register (LFSR) architecture [10],
g(x) must be
i
the,
i [11].
g(x)= LCM{1(x),2(x),….,2t(x)} (1)
As the minimal polynomial for conjugate roots are same i.e. as i = (i )2l, i(x) = i (x), where i = i * 2l
BCH codeword are encoded as
C(x) = x nk * i(x)+b(x) (6)
for l 1, thus generated polynomial g(x) of binary terror correcting
Where C(x) = c0 + c1
x + + c
nl
xnl
BCH code of length given by eqn.(1) can be reduced to
g(x) = LCM{1(x),2(x),….,2t1(x)} (2)
BCH code generated by primitive elements is given in [8]. An irreducible polynomial g(x) of degree m is said to be primitive if only if it divides polynomial form of degree n, xn + 1 for n = 2m1. In fact, every binary primitive polynomial g(x) of degree m is a factor of x 2 m 1
+ 1. A list of primitive polynomial for degree m and for finding irreducible polynomial is given in [7].
For (15, k) BCH code, let _ be a primitive element of the GF (24) given in [7] such that 1 + + 4 is a primitive polynomial. From [7], [8] we find that minimal polynomials of , 3, 5 are
1(x) = 1+ x + x4
3(x) = 1+ x + x 2+ x 3+ x4
5(x) = 1+ x + x2
For single error correcting, BCH code of length n = 24 1
= 15 is generated by
g(x)= 1 (x)= 1+ x + x4 (3)
Here highest degree is 4 i.e (nk = 4), thus the code is a (15, 11) cyclic code with dmin _ 3 Since the generator polynomial is code polynomial of weighted 5, the minimum distance of this code is exactly 3.
For double error correcting, BCH code of length n = 15 is generated by
g(x) = LCM{1(x),3(x)}
= 1+ x4 + x6 + x7 + x8 (3)
Here highest degree is 8 i.e (nk = 8), thus the code is a (15, 7) cyclic code with dmin 5.
For triple error correcting, BCH code of length n = 15 is generated by
g(x) = LCM{1(x),3(x),(x) }
= 1+ x+ x2+ x4+ x5+ x 88+ x10 (4)
Here highest degree is 10 i.e (nk = 10), thus the code is a (15, 5) cyclic code with dmin 7.
i(x) = i0 + i1 x + .+ikl x kl
b(x) = b0 + b1 x + . + bm l xml and cj , ij , bj GF(2) .
Then if b(x) is taken to be the polynomial such that xnk i (x) = q(x) * q(x) b(x) (7)
The k data bits will be present in the codeword. Using the properties of cyclic codes [7], th remainder b(x) can be obtained in a linear (nk)stage shift register with feedback connections corresponding to the coefficients of the generator polynomial
g(x) = 1+ g1 x+.+ gnkl xnkl + xnk (8) Such a circuit is shown on Fig. 2.
On the encoder side, systematic encoding has been used, which makes easier implementation of encoder which is shown in Fig. 1.
Code Block
Information
Error Control
I1I2I3..Ik1Ik
P1..pnk1pnk
k Data bits
nk parity check bits
Figure 1:Systematic Encoding Diagram for (n, k) BCH Code
It is not useful to split the generator polynomial at the encoding side because it will demand more hardware and control circuitry. Therefore, the polynomial (1) is used as it is for encoding procedure. The digital logic implementing the encoding algorithms is organized into linear feedback shiftregister circuits (LFSR) that mimic the cyclic shifts and polynomial arithmetic required in the description of cyclic codes.
The LFSR block diagram for (n, k) BCH encoder is shown in Fig. 2.
Figure 2: LFSR Encoding circuit for a (n, k) BCH codes
The encoder which is shown in Fig. 2 operates as follows

For clock cycles 1 to k, the information bits are transmitted in unchanged form (switch S2 in position 2) and the parity bits are calculated in the Linear Feedback Shift Register (LFSR) (switch S1 is on).

For clock cycles k+1 to n, the parity bits in the LFSR are transmitted (switch S2 in position 1) and the feedback in the LFSR is switch off (S1 – off).
To observe the speed and resource utilization, RTL is generated verified and synthesized. The proposed BCH encoder has been implemented on Spartan3 XC3S1000 target device by using Xilinx ISE 10.1

Design of Encoder for (15, 11, 1) BCH Code
Encoder for (15, 11, 1) single error correcting BCH code is designed by organizing LFSR with generated polynomial 1+x+x4 and implemented on Spartan 3S1000 FPGA of Xilinx. The RTL view and Schematic is generated by synthesis with Xilinx ISE 10.1, shown in Fig 3 and Fig. 4.
Figure 3: RTL for (15, 11, 1) BCH Encoder
Figure 4: Schematic for (15, 11, 1) BCH Encoder

Design of Encoder for (15, 7, 2) BCH Code
Encoder for (15, 7, 2) double error correcting BCH code is designed by organizing LFSR with generated polynomial
1+x4+x6+x7+x8 and implemented on Spartan 3S1000 FPGA of Xilinx. The RTL view and Schematic is generated by synthesis with Xilinx ISE 10.1, shown in Fig. 5and Fig. 6.
Figure 5: RTL for (15, 7, 2) BCH Coder
Figure 6: Schematic for (15, 7, 2) BCH Encoder

Design of Encoder for (15, 5, 3) BCH Code
Encoder for (15, 5, 3) triple error correcting BCH code is designed by organizing LFSR with generated polynomial 1+x+x2+x4+x5+x8+x10 and implemented on Spartan 3S1000 FPGA of Xilinx. The RTL view and Schematic is generated by synthesis with Xilinx ISE 10.1, which are shown in Fig.7 and Fig. 8.
Figure 7: RTL for (15, 5, 3) BCH Encoder
Figure 8: Schematic for (15, 5, 3) BCH Encoder


Result and Discussion
Input the netlist file generated from synthesizing, placing and routing on the Xilinx ISE 10.1 software. The simulation waveform for (15, k) BCH encoder is shown in Fig. 9, Fig. 10 & Fig. 11 under the simulation clock is
217.533 MHz.
The waveform simulation takes place with 20 ns clock period.

Simulation Waveform Result of (15, 11, 1) BCH Encoder
The timing simulation of (15, 11, 1) BCH encoder is shown in Fig. 9. Two data sequence is shown from 380 ns – 680 ns and 680 ns 980 ns. Total of 15 clock cycle is taking to complete transmitting of 15 codeword, 11bits are information bit and 4 bits are parity bit. 11 Information bits 01011001001 are transmitting as it is where as other 4 bits 1010 are transmitting as parity bit 1100.
Figure 9: Simulated Waveform for (15, 11, 1) BCH Encoder

Simulation Waveform Result of (15, 7, 2) BCH Encoder
The timing simulation of (15, 7, 2) BCH encoder is shown in Fig. 10. Two data sequence is shown from 580 ns
– 880 ns and 880 ns – 1180 ns. Total of 15 clock cycle is taking to complete transmitting of 15 codeword, 7bits are information bit and 8 bits are parity bit. 7 Information bits
1011001 are transmitting as it is where Vaosl. o2tIhsseure 89, Sbeiptstember – 2013
00110100 are transmitting as parity bit 00011110.
Figure 10: Simulated Waveform for (15, 7, 2) BCH Encoder

Simulation Waveform Result of (15, 5, 3) BCH Encoder
The timing simulation of (15, 5, 3) BCH encoder is shown in Fig. 11. Two data sequence is shown from 640 ns 940 ns and 940 ns – 1240 ns. Total of 15 clock cycle is taking to complete transmitting of 15 codeword, 5bits are information bit and 10 bits are parity bit. 5 Information bits 00110 are transmitting as it is where as other 10 bits 0110010100 are transmitting as parity bit 010001110.
Figure 11: Simulated Waveform for (15, 5, 3) BCH Encoder

Comparison of performance between single, double and tripple error correcting (15, k) BCH code
We study and compare the behavior of multiple error correcting (15, k) BCH encoder by implementing on FPGA using VHDL. The device utilization and timing summary is given on table 1.
Table 1: Device Utilization and Timing Summary
Component Utilization/ Time
(15, 11, 1) BCH
Encoder
(15, 7, 2) BCH
Encoder
(15, 5, 3) BCH
Encoder
No. of Slices
6
8
9
No. of Slice FF
9
12
15
4 input LUTs
12
14
16
Number of IOs
5
5
5
Simulation Clock
20 ns
20 ns
20 ns
Max. Combinational path delay
9.159 ns
9.159 ns
9.159 ns
Max. output required
8.81 ns
8.73 ns
8.57 ns
Total CPU time to Xst completion
6.13 sec
5.9 sec
5.7 sec


Conclusion
The result presented from the synthesis and timing simulation, shows the (15, 5, 3) BCH Encoder is more advantageous over the other two, according to speed requirement It can correct 3 error at the receiver side when the original data corrupt by the noise. But when considering area then (15, 11, 1) is better which can correct only 1 bit error. Also redundancy is less and data rate is more in it.
BCH codes have been shown to be excellent error correcting codes among codes of short lengths. They are simple to encode and relatively simple to decode. Due to these qualities, there is much interest in the exact capabilities of these codes. The speed and device utilization can be improved by adopting parallel approach methods.

References

M.Y. Rhee – Error Correcting Coding Theory, McGrawHill, Singapore, 1989.

S. Lin, and D.J. Costello Jr. – Error Control Coding, PrenticeHall, New Jersey, 1983.

E. R. Berlekamp, Algebraic coding theory, McGraw Hill, New York, 1968.

R.E. Blahut, Theory and practice of errorcontrol codes, AddisonWesley, Reading, MA, 1983

S. B. Wicker, Error Control Systems for Digital Communication and Storage. Upper Saddle River, New Jersey 075458: Prentice Hall, Inc,1995.

Berlekamp, E.R., Peile, R.E. and ope, S.P. (1987), "The application of error control to communications", IEEE Communication Magazine, 25, no.4, pp 4057.

Shu Lin, Daniel J. Castello, Error control coding, Fundamentals and applications, PremticeHall, New Jersey, 1983, Pages 1550.

Shu Lin, Daniel J. Castello, Error control coding, Fundamentals and applications, PremticeHall, New Jersey, 1983, Page 141182.

W.W. Peterson, Encoding and errorcorrection procedures for the BoseChaudhuri Codes, IRE Trans.Inf. Theory, IT6, pp. 459470, September 1960.

Goresky, M. and Klapper, A.M. Fibonacci and Galois representations of feedbackwithcarry shift registers, IEEE Transactions on Information Theory, Nov 2002, Volume: 48, On page(s): 2826 2836.

Panda Amit K, Rajput P, Shukla B, Design of Multi Bit LFSR PNRG and Performance comparison on FPGA
using VHDL, International Journal oVf olA. 2dvIsasunece9,sSeipntember – 2013
Engineering & Technology (IJAET), Mar 2012, Vol. 3,
Issue 1, pp. 566571

Xilinx, Inc. Xilinx Libraries Guide, 2011.

Xess Corp.. XSA3S1000 Board V1.1 User Manual. Available:http://xess.com/manuals/xsa3Smanual v1_1.pdf. Sept 2007.

J J.Rose S.D. Brown, R.J. Francis Field Programmable Gate Arrays, Kluwer Academic Publishers, 1992

Brown S., Vranesic Z Fundamental of Digital Logic Design with VHDL McGraw Hill, 2nd Edition.

P. J. Ashenden, The VHDL Cookbook, 1st ed. Dept. Computer Science, University of Adelaide, South Australia: University ofAdelaide, 1990.

Bhasker J, A VHDL Primer, P T R Prentice Hall, Pages 12, 413, 2830