Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    A Modified Implementation of Chien Search For Reed-Solomon Decoder

    Uploaded by

    John Brown
    This document summarizes three approaches to implementing Chien search for Reed-Solomon decoding. The first approach uses Horner's rule and requires p multipliers and p adders with latency of pm cycles. The second approach uses properties of Galois fields to simplify calculations and requires pm cycles with less hardware. The third approach checks values from α2m-2 to α0 and requires only p constant multipliers and p adders with latency of m cycles regardless of error locator polynomial degree.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    A Modified Implementation of Chien Search For Reed-Solomon Decoder

    Uploaded by

    John Brown
    25 views3 pages
    This document summarizes three approaches to implementing Chien search for Reed-Solomon decoding. The first approach uses Horner's rule and requires p multipliers and p adders with latency of pm cycles. The second approach uses properties of Galois fields to simplify calculations and requires pm cycles with less hardware. The third approach checks values from α2m-2 to α0 and requires only p constant multipliers and p adders with latency of m cycles regardless of error locator polynomial degree.

    Original Title

    15-46-1-PB

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document summarizes three approaches to implementing Chien search for Reed-Solomon decoding. The first approach uses Horner's rule and requires p multipliers and p adders with latency of pm cycles. The second approach uses properties of Galois fields to simplify calculations and requires pm cycles with less hardware. The third approach checks values from α2m-2 to α0 and requires only p constant multipliers and p adders with latency of m cycles regardless of error locator polynomial degree.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    25 views3 pages

    A Modified Implementation of Chien Search For Reed-Solomon Decoder

    Uploaded by

    John Brown
    This document summarizes three approaches to implementing Chien search for Reed-Solomon decoding. The first approach uses Horner's rule and requires p multipliers and p adders with latency of pm cycles. The second approach uses properties of Galois fields to simplify calculations and requires pm cycles with less hardware. The third approach checks values from α2m-2 to α0 and requires only p constant multipliers and p adders with latency of m cycles regardless of error locator polynomial degree.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    Journal Basic Science And Technology, 1(2),9-12,2012 ISSN : 2089-8185

    A Modified Implementation of Chien Search for Reed-Solomon Decoder


    Ali Mahmudi
    Department of Computing, National Institute of Technology Malang, Indonesia [email protected]
    Abstract New implementations of Chien-search are presented. It is shown that by modifying a Chien search for solving the error-locator polynomial, efficient hardware architectures can be derived. Furthermore, these architectures are particularly suited to implementing RS decoders. Keyword : chien, search, architectur, RS decoder

    II.

    THEORY AND IMPLEMENTATION

    2.1 Implementation 1 The common approach to find the error locations is using Chien-search. It is equivalent to finding out l (l GF(2m)) such that (l)=0. The way to find this root is by implementing Horners rule on Chien search as follows
    ( x ) = (...( x +
    p p 1 ) x + ...) + (1) 0

    I.

    INTRODUCTION

    Reed-Solomon (RS) codes are a class of cyclic codes widely utilised and is a standard in a number of applications such as DVB, CDs and satellite communication systems. Since the decoding process for RS codes involves very high computational complexity, most research work has been focused on this area. Most widely used decoding strategies of RS codes involve the following main steps: 1) Evaluating the syndrome polynomial S(x), 2) Solving the key equation: S(x) (x)(x) mod x2t where (x) represents the error locator polynomial and (x) represents error evaluator polynomial, 3) Solving (x) using Chien-search[2] and 4) determining the error values. This 4-step decoding procedures is illustrated in Figure 1.

    The following figure shows the circuit diagram of this Horners implementation
    p -l p-1 p-2 0

    (-l)
    m size buffer m size buffer

    Figure 2 Horners rule implementation of Chien search

    Figure 1. Reed Solomon Decoder

    As m clock cycles are required to complete every multiplication (using for example a Berlekamp[1] serial bit multiplier), the total latency is therefore pm cycles. The above circuitry requires p multipliers and p adders (mod 2 addition). The total hardware requirements are 3pm-p registers, pm+p XOR2 gates and pm AND2 gates. The above algorithm can be simplified if there is a circuit to calculate xk (where 2 k p) effectively. 2.2 Implementation 2 Theorem 1. Let x, y GF(2m) such that y = xk and let {0, 1, , m-1} be a basis for GF(2m). Further let be a root of the primitive polynomial p(x), GF(2m) and let f be a linear function f:GF(2m) GF(2). If x is represented over this basis by x =

    In the second step, the techniques frequently used to solve the key equation include the Berlekamp-Massey[5] algorithm, the Euclidean[6] algorithm and the Welch-Berlekamp[7] algorithm. In this paper, three algorithms of Chien search implementation are presented. The first algorithm will be the implementation based on Horners rule. The second and third algorithm are derived from properties of Galois Fields (GF). The complexity and the efficiency of each algorithm will be discussed in detail.

    im=01xi i then the following relation holds[4]

    10

    f (y) f ( y ) L = m 1 ) f ( y

    Journal Basic Science And Technology, 1(2),9-12,2012 ISSN : 2089-8185 hardware requirements is 2pm-p registers, pm+p XOR2 gates, pm AND2 gates and some extra gates to implement xk (p k > 1) circuitry. The advantage of this implementation over implementation 1 is that it requires pm less registers and it only needs m cycles latency to complete the calculation. However, some extra XOR2 gates are required to implement xk and every value of k has different combinational gates. 2.3 Implementation 3 The third implementation can be explained as follows. Let k(x)= k xk for 0 k p . Let the symbol location be j (j GF(2m)) where 0 j < 2m-1 and its check position is at 0 j < 2t-1.
    ( x) = ( x) +
    p p 1 ( x ) + ... + (3) 0

    f (k) 0 f (k) 0 L k m1 f ( ) 0

    k k f ( ) L f ( ) x 1 m1 0 k k f ( ) L f ( ) x1 (2) 1 m1 L L L L x k k f ( m1) f ( m1) m1 1 m1

    The proof of this equation can be seen on[4]. If the basis {0, 1, , m-1} is the dual basis to the polynomial basis with respect to f and , then yi in eq(3) gives the dual basis representation of y. As an example, consider GF(26) with p(x)=x6+x+1 and take to be a root of p(x). The dual basis to the polynomial basis {1, , 2, 3, 4, 5} is {1, 5, 4, 3, 2, }. Let y = x6 and putting these values in eq(3) yields:

    If we check the Chien search value up to b provided b-1 0; then


    ( ) =
    k k
    bp

    bk

    and
    b ( p 1)

    y0 1 y1 0 y 0 2 = y3 0 y 4 0 y5 0
    Hence

    x 1 1 1 1 1 0 x 1 0 0 0 0 1 1 1 0 0 0 x2 0 0 1 0 0 x 3 0 0 1 1 0 x 1 0 1 0 1 4 x 5

    ( ) =
    p

    p 1

    + ... +

    The next attempt is b-1 and its value is


    (
    k b 1 )= k (b 1) k = ( k bk ) k

    and so

    b 1 bp

    )= p + ( p 1

    y =x +x +x +x +x +x , y =x , y =x +x 0 0 1 2 3 4 5 1 1 2 1 2

    ( p

    b ( p 1)

    1 p

    (4)
    + ... + 0

    y =x , y =x +x , y =x +x +x 3 3 4 3 4 5 1 3 5

    From the above description, it is clear that the value of p(b-1) is directly proportional to p(b) and it is linear. Of course, it needs to be initialized. If we try all possible input from
    (
    k
    2m 2

    This implementation is much simpler than getting the result by multiplying x by x for 5 times. So, the Chien search implementation can be shown as follows
    p p-1 p-2 0

    to 0 then
    ( 2 m 2) k k

    2m 2

    )= k = k

    ( 2 m 1) k k

    = k

    So, this new approach of implementing Chien search can be generalized as follows
    xp xp-1 xp-2
    (x)

    Initialisation
    (
    2m 2 ) = p p +

    -l

    p 1

    1 p

    + ... + (5) 0

    Figure 3. Second approach to implement Chien search

    For 0 b<2m-2

    It requires p multipliers and p adders (mod 2 addition). Consider using a Berlekamp[1] serial bit multiplier, the total

    11

    ( ) = (
    p

    b +1

    p 1

    Journal Basic Science And Technology, 1(2),9-12,2012 ISSN : 2089-8185 III. b +1 1 p ( ) + ... + (6)
    0

    CONCLUSION

    The hardware implementation is shown in Figure . It should be noted that this new approach requires p constant multipliers and p adders (mod 2 addition). Again, consider using a Berlekamp[1] serial bit multiplier, the total hardware requirements is It only takes m cycles latency, whatever the degree of the error locator polynomial; at the expense of p-1 XOR delays the output.
    -p Init p
    reg

    A novel Chien search implementations have been presented and compared. The third approach is shown to achieve better efficiency and less latency than the two others. REFERENCES
    [1] Berlekamp E.R., Bit-serial Reed-Solomon encoders, IEEE Trans Inform. Theory, pp 869-874, 1982. [2] Chien R.T., Cyclic Decoding Procedures for Bose-ChaudhuriHocquenghem Codes, IEEE Trans Inform. Theory, pp 357-363, Oct 1964. [3] Fenn S.T.J., Benaissa M. and Taylor D., Bit-serial Berlekamplike Multipliers for GF(2m), Electronics Letters, pp 1893-94, Oct 1995. [4] Fenn S.T.J., Benaissa M. and Taylor D., Finite Field Inversion Over the Dual Basis, IEEE Trans on VLSI Systems, vol. 4 no 1, March 96, pp 134-137. [5] Liu K.Y. Architecture for VLSI Design of Reed-Solomon Decoders. IEEE Transactions on Computers, pages 178-189, Febr 1984. [6] Shao H.M., Truong T.K., Deutsch L.J., Yuen J.H. and Reed I.S. A VLSI Design of a Pipeline Reed-Solomon Decoder. IEEE Transactions on Computers, pages 393-403, May 1985. [7] Welch L.R. and Berlekamp E.R. Error Correction for Algebraic Block Codes. US Patent Number 4,633,470, Dec 1986.

    (x) Init p-1


    reg

    1-p Init 0

    reg

    Figure 4. Third approach to implement Chien search

    12

    You might also like