 Open Access
 Total Downloads : 497
 Authors : Sangeeta Singh, S. Sujana
 Paper ID : IJERTV2IS4965
 Volume & Issue : Volume 02, Issue 04 (April 2013)
 Published (First Online): 24042013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
ASIC Implementation Of Reed Solomon Codec For Burst Error Detection And Correction
Sangeeta Singh S. Sujana
Associate Professor Associate Professor Dept. of ECE Dept. of ECE
Vardhaman College of Engineering Vardhaman College of Engineering Hyderabad (A.P) Hyderabad (A.P)
Abstract
Accuracy of information in any communication system is very critical. Use of Forward Error Correction (FEC) to lower the probability of error and increase transmission distance has become widespread. ReedSolomon code is one of the block FEC, capable of correcting multiple errors, focusing specifically on burst errors, making it popular for mass storage devices, wireless and mobile communication units, digital television (DTV), satellite communications, digital video broadcasting (DVB) and broadband modems. When RS(n, k) codes are used for high reliable systems, the occurrence of faults in the encoder and decoder subsystems should be considered. Reed Solomon codec consists of both encoder and decoder on a single chip. In this paper new architecture is proposed for RS codec which consists of an encoder, decoder and a noise block that generates random noise. The RS encoder architecture is designed using LFSRs which exploits some properties of the arithmetic operations in G(2m). The ReedSolomon decoder processes each block and attempts to correct up to t = (nk)/2 symbols and recovers the original data. In the RS decoder, the implicit redundancy of the received codeword, under certain assumptions explained in this paper, allows implementation of concurrent error detection schemes useful for a wide range of applications. In this paper new decoding method for Reed Solomon codec is proposed which uses Berlekamps algorithm instead of Euclidean method. The codec is designed using verilog hardware description language and simulated using Xilinx tools. To improve the performance of the RS codec, the same design is synthesized and implemented with 180nm TSMC library using cadence tools.

Introduction
Wireless technology is fast becoming a trend in present communication systems. The demand for greater bandwidth allocation is being addressed by fixed wireless broadband access. However, the use of free space, as a transmission medium, introduces many sources of error in the data being transmitted across the channel. As the accuracy of information is very critical, the use of Forward Error Correction (FEC) methods has gained tremendous importance. FEC improves the reliability of data reception for a system. The basic principle behind any error correcting codes is the application of a mathematical transform onto the message signal such that redundant message information is used to correct any errors that may have been introduced during transmission.
In the design of high reliable electronics systems both the ReedSolomon (RS) encoder and decoder should be self checking in order to avoid faults in these blocks which compromise the reliability of the whole system. In fact, a fault in the encoder can produce a non correct codeword, while a fault in the decoder can give a wrong data word even if no errors occur in the codeword transmission. Therefore, great attention must be paid to detect and recover faults in the encoding and decoding circuitry. Nowadays, the most used error correcting codes are the RS codes, based on the properties of the finite field arithmetic. In particular, finite fields with 2m elements are suit able for digital implementations due to the isomorphism between the addition, performed modulo 2, and the XOR operation between the bits representing the elements of the field.
The use of the XOR operation in addition and multiplication allows to use parity checkbased strategies to check the presence of faults in the RS
encoder, while the implicit redundancy in the code word is used either for correct erroneous data and for detect faults inside the decoder block.

RS Codes
RS codes are an example of a block coding
and the overall data word is treated as a polynomial d(x) of degree k1 with coefficient in GF(2m). The RS codeword is then generated by using the generator polynomial g(x). All valid code words are exactly divisible by g(x). The general form of g(x) is
gx x i x i1 ……..x i2t
technique, where the data stream to be transmitted is
gx g
g x g x2 ……g
x2t1 x2t
broken up into blocks and redundant data is then
0 1 2
2t1
added to each block. The size of these blocks and the amount of check data added to each block is either specified for a particular application or can be user defined for a closed system. RS codes are specified using (n, k) notation where n represents the total length of the codeword and k refers to the number of original message symbols of mbit each.
n
k 2t
DATA PARITY
Figure 1: RS Codeword
The advantage of using Reed Solomon codes is that it can correct multiple errors. In general there are (nk) parity symbols of m bits each. A Reed Solomon decoder can correct up to t symbols that contain errors in a codeword, where 2t = nk. It is mainly used to correct burst errors in mass storage devices, communication systems, digital video broad casting (DVB) and broadband modems. The amount of processing "power" required to encode and decode ReedSolomon codes is related to the number of parity symbols per codeword. A large value of t means that a large number of errors can be corrected but requires more computational power than a small value of t.
The finite fields used in digital implementations are in the form GF(2m), where m represents the number of bits of a symbol to be coded. More information about finite fields and RS codes are
where 2t = nk, = primitive element.
The codewords of a separable RS(n,k) code correspond to the polynomial C(X) with degree n1 that can be generated by
Px dx.xnk modgx
cx px xnkmx
Where p(x) is a polynomial representing the parity symbols. In general encoder takes k data symbols and adds 2t parity symbols obtaining n symbol codeword. The 2t parity symbols allows correction of up to t symbols containing errors in a code word. From a device utilization standpoint, the size of the encoder is most heavily affected by the number of check symbols required for the target RS code. The total message length, as well as the field polynomial and first root value, do not have any appreciable effect on the device utilization or performance for a given target RS code.
In digital hardware, the encoder block is implemented using an LFSR with internal feedback connections corresponding to g(x).The computation of the remainder is implemented on digital hardware using a linear feedback shift register configuration as shown in Figure 2. Note that this setup resembles the iterative method of polynomial division. The final contents of the shift registers will contain the remainder.
provided in [1]. An element a(x) GF(2m) is a polynomial with coefficients ai{0,1} and can be seen as a symbol of m bits a=am1 …a1a0. The addition of two elements a(x) and b(x) GF(2m) is
the sum modulo 2 of the coefficients ai and bi, i.e., is the bitwise XOR of the two symbols a and b. The multiplication of two elements a(x) and b(x)
g0 g1 g2 g3 g4 g5
F/F + F/F + F/F + F/F + F/F + F/F +
i(x)
GF(2m) requires the multiplication of the two polynomials followed by the reduction modulo i(x), where i(x) is an irreducible polynomial ofdegree m. Multiplication can be implemented as an ANDXOR network, as explained in [5].

RS Encoder and Decoder
The RS(n, k) code is defined by representing the data word symbols as elements of the field GF(2m)
Figure2: Encoder Architecture
When a received block is given as input to the decoder for processing, the decoder first verifies whether the received block appears in the dictionary of valid code words. If it does not, then errors must have occurred during transmission. This part of the decoder processing is called error detection. The parameters required to reconstruct the original encoded block are available to the decoder. The decoder attempts to perform reconstruction if errors
are detected. This is called error correction. Conventionally, decoding is performed by the PetersenGorensteinZierler (PGZ) algorithm, which consists of following parts:

Syndromes calculation.

Derivation of the errorlocation polynomial.

Error Locations

Error Magnitudes

Error Correct
The RS decoder consists of five major blocks as shown below:
k factors. The hardware implementation is shown Figure 4.
D S0
8
/
/
1
1
r0,r1,–rn1 D S
ERROR MAGNITUDES
FORNEY ALGORITHM
ERROR MAGNITUDES
FORNEY ALGORITHM
Si
Si
r(x)
SYNDROME
CALCULATOR
ERROR POLYNOMIAL
BERLEKAMP'S
ERROR LOCATIONS
L(x)
Xi
CHIEN
Yi
ERROR CORRECTOR
c(x)
D S19
ALGORITHM
SEARCH
Figure 4: Syndrome Calculation
The method used for deriving error locator
Figure 3: Decoder Architecture
In this implementation the errorlocation polynomial is found using the BerlekampMassey algorithm, and the error values are obtained by the Forney algorithm.
Let the received codeword R(X) : R(X) = C(X) + E(X)
Where C(X) = original (transmitted) codeword, E(X) = error polynomial
A codewords syndrome s(x) is the remainder of the division of the received word r(x) by the genera tor polynomial, as implied by the following equation:
r(x) q(x) s(x)
polynomial in this implementation is the Berlekamp Massey Algorithm[6]. The BerlekampMassey algorithm is a shiftregister synthesis algorithm which takes the nk partial syndromes as input and outputs the error locator polynomial (X). The Berlekamp Massey algorithm is an algorithm for finding the shortest linear feedback shift register (LFSR) for a given output sequence.
The roots of error locator polynomial provides the error locations and is obtained by performing the Chien Search, which evaluates the Error Locator Polynomial at all elements of the GF(2m) field. The algorithm checks if ( P )equals zero, p = 0, 1, 2 .,
g(x)
g(x)
n, then P is a root of the polynomial, and P is an
c(x) e(x) q(x) s(x)
error location, XP. This is implemented using LFSRs
g(x)
g(x)
similar to those used in computing the partial
Since all code words are divisible by the generator polynomial, only the error component will yield a remainder.
e(x) q (x) s(x)
syndromes. The equation that determines the error evaluator or error magnitude polynomial (X) is given by
SXX XmodXnk
g(x) e g(x)
The above equation shows that the syndrome is independent of the message information and depends only on the error component. For no errors, the syndrome polynomial S(x) will be zero. In most systems, partial syndromes are computed instead of the syndrome, for reasons of simpler hardware implementation. In the computation of a partial syndrome, the divisor is no longer the entire generator polynomial, but only one of its factors, as shown in below equation:
An efficient way of computing (X) is to perform parallel computation of (X). The Forney Algorithm is used to compute for the error magnitudes, Yi, corresponding to the respective error locations using the following equation:
i
i
i
i
X1 Yi 'X1
where Xi1 indicates the root as computed from the Chien Search, and 1(X)the derivative of the error
locator polynomial.
r(x) q(x)
(x ak )
sk
(x ak )
The error corrector block takes the received code and performs XORoperation with the corresponding
There will be nk partial syndromes for every
received word, since the generator polynomial has n
error magnitudes computed at the respective error locations to attain the original message stream.
CXi RXi Yi


Results
In this paper the top module of the design integrates datarom block for input, an encoder, noise block and decoder. The design receives message symbols using datarom that generates sequence of symbols for input. These are processed by encoder operating on Galois Field to form a complete code word by adding parity symbols. A noise block generates random noise that gets added to the encoded message and converts it into an incorrect information. The function of decoder is to detect all possible errors and correct them.
The design is implemented in verilog hardware description language and simulated using Xilinx on Spartan3E. RS Codec is further synthesized using 180 nm TSMC technology. Table1 shows the results obtained for the order RS(208, 200) using Xilinx.
Timing Delay Report: This gives the delays that will be present in the realization of the design once it is implemented on a FPGA kit. It is the sum of the logic delays and the wiring delays. The wiring delays must be kept as low as possible and at times are comparable to the logic delays. The total delay is thus the sum of all the logic delays involved and the wiring delays. This is depicted in Table2 which shows the delays involved in the FPGA implementation of our design.
Table 1: Device Utilization Summary
Device Utilization Summary Selected Device:3x500efg3204
Number of Slices:
1446 out of 4656
31%
Flip Flops:
671 out of 9312
7%
Number of 4 input LUTs:
2635 out of 9312
28%
Number of bonded IOBs:
22 out of 232
9%
Number of GCLKs:
1 out of 24
4%
RTL compiler generates schematic for each sub modules including the top module after completing synthesis. Figure 5 to 7 show RTL schematic of top module, encoder and input message module respectively.
Figure 5: Top Module of RS(208,200) Codec
Figure 6: Encoder Module
Figure 7: Input Message Module
The same design is implemented using SOC encounter tool. Reports on gate count, power, timing etc are generated at the output. The leakage power obtained is 750.127 nW .
Type
Instances
Area
Area
%
Sequential
649
46842.365
35.3
Inverter
236
1609.978
1.2
Buffer
7
93.139
0.1
Logic
4326
84207.816
63.4
Total
5218
132753.29
8
100
Type
Instances
Area
Area
%
Sequential
649
46842.365
35.3
Inverter
236
1609.978
1.2
Buffer
7
93.139
0.1
Logic
4326
84207.816
63.4
Total
5218
132753.29
8
100
Timing Summary Speed Grade: 4
Minimum period:
24.379ns (Maximum Frequency: 41.019MHz)
Minimum input arrival time before clock:
13.201ns
Maximum output required time after clock:
28.420ns
Timing Summary Speed Grade: 4
Minimum period:
24.379ns (Maximum Frequency: 41.019MHz)
Minimum input arrival time before clock:
13.201ns
Maximum output required time after clock:
28.420ns
Table 2: Timing Summary.
Table 3: Gates Report

Conclusion
Reliability of information is critical in any communication systems. Use of errorcontrol codes reduces interference effects, and FECs in general, eliminate the need for retransmission of data streams. RS (208,200) Codec is capable of correcting 4 errors at a time and is mainly used to correct burst errors in storage devices.
The design has been verified using Xilinx tools on Spartan3E FPGA where the operating frequency is
41.019 MHz and the same is also synthesized using 180nm TSMC library RTL compiler and SOC Encounter to improve the performance by increasing the clock frequency to 100 MHz.
The RS Codec designed here considers only pseudo random noise. The same design can be extended to model different types of noises like Poissons distribution, Gaussian distribution. The length of the codeword can be increased in order to correct more number of errors.

References

R. E. Blahut, Theory and Practice of Error Control Codes. Reading, MA: AddisonWesley Publishing Company, 1983.

S. B. Wicker, Error control Systems for Digital Communication and Storage, Prentice Hall, 1995 G.C

G.B. Agnew, T. Beth, R.C. Mullin, and S.A. Vanstone,Arithmetic Operations in GF(2m), J. Cryptology, vol.6, pp. 313,1993.

Candarilli, S.Pontarelli, Concurrent Error Detection in ReedSolomon Encoders and Decoders IEEE trans. VLSI Systems. , Volume 15, July 2007.

A. R. Masoleh and M. A. Hasan, Low complexity bit parallel architectures for polynomial basis multiplication over GF(2m), computers, IEEE Trans. Computer., vol. 53, no. 8, pp. 945959, Aug. 2004.

G. L. Feng and K. K. Tzeng, A generalization of the BerlekampMassey algorithm for multisequence shift register synthesis with application to decoding cyclic codes, IEEE Trans. Inform.Theory, volume. 37,pp. 12741287, 1991.

W.J. Ebel, W. H. Tranter, The Performance of Reed Solomon Codes on a BurstyNoise Channel, IEEE Transactions on Communications, Vol. 43, No. 2/3/4, February/March/April 1995.

S. P. Kang, C. G. Kim, S. W. Rhee, and Y. Jee, ASIC Implementation of ReedSolomon Error Correction Circuits for Low Area Overhead on Memory System, International Conference on Electronics, Information, and Communication (ICEIC 2008), pp. 339342, June. 2008.

M. Gossel, S. Fenn, and D. Taylor, Online error detection for finite field multipliers, in Proc. IEEE Int. Symp. Defect Fault Tolerance VLSI Syst., 1997, pp. 307311.

T.A. Gulliver, M. Serra, and V.K. Bhargava, The Generation of Primitive Polynomials in GF(q) with Independent Roots and Their Application for Power
Residue Codes, VLSI Testing and Finite Field Multipliers Using Normal Bases, Intl J. Electronics, vol. 71, no. 4, pp. 559576, 1991.

S. B. Sarmadi and M. A. Hasan, Concurrent error detection of polynomial basis multiplication over extension fields using a multiplebit parity scheme, in Proc. IEEE Int. Symp. Defect Fault Tolerance VLSI Syst., 2005, pp. 102110.

E.D. Mastrovito, VLSI Architectures for Computation in Galois Fields, PhD thesis, Linkoping Univ., Linkoping, Sweden, 1991.

M.A. Hasan, M.Z. Wang, and V.K. Bhargava, Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fields GF(2m), IEEE Trans. Computers, vol. 41, no. 8, pp. 962971, Aug. 1992.