N94-18348 3.4.1 3rd NASA Symposium on VLS[ Design 1991 An Extended Reed Solomon Decoder Design J. Chen NASA Space Engineering Research Center for VLSI System Design University of Idaho Moscow, Idaho 83843 P. Owsley Advanced Hardware Architectures Moscow, Idaho 83843 J. Purviance NASA Space Engineering Research Center for VLSI System Design University of Idaho Moscow, Idaho 83843 Abstract- It has previously been shown that the Reed Solomon (RS) codes can correct errors beyond the Singleton and Rieger Bounds with arbitrarily small probability of a mlscorrect [1]. That is an (n,k) RS code can correct more than (n-k)/2 errors. An implementation of such an RS decoder is presented in this paper. An existing RS decoder, the AHA4010, is utilized in this work. This decoder is specially useful for errors which are patterned with a long burst plus some random errors. 1 Introduction It is well known that an (n,k) RS code can correct up to (n-k)/2 random errors. When burst errors are involved, the error correcting ability of the RS code can be increased beyond (n-k)/2 with arbitrarily small probability of a miscorrect [1]. Errors considered in this paper, called composite errors, have a single burst plus random error pattern. RS codes are powerful error correcting codes. There is a rich history of work developing decoding algorithms for RS codes. Virtually all of the work focuses on the general case of t unknown error locations. It is possible to extend the error correction capability of a RS code if error location information is available from some external source. This is ca/led erasure decoding. The extended decoding technique presented in this paper assumes that the locations of the burst are known and treats them as erasures. All possible burst error positions are given to the decoder sequentially as "guesses" to the burst error location. That is, the burst part of the error becomes an erasure and an erasure-locator polynomial is generated from the erasure locations for each burst location guess. By sending this erasure-locator polynomial along with a received code word to a general purpose RS decoder, such as AHA4010, the RS decoder will decode the received codeword. The result outputted by the 3.4.2 RS decoder is either a corrected data or a signal which indicates no correction can been made. The erasure-locator polynomial is generated iteratively for all possible locations during the decoding procedure. It is possible that more than one error polynomial results from this iterative procedure. When more than one error is obtained, the error that has higher probability of occurrence should be chosen. It is assumed in this paper that an error with smaller weight has higher probabil.ity of occurrence. This is true for most channels. If the chosen error is not the true error, a miscorrect occurs. The probability of mis- correct is a function of the size of the error that is detected and the channel statistics. It is usually very low as shown in reference 1. The implementation presented-inUihis paper is based on the AHA4010 RS decoder. The purpose is to increase the error correction capability with very little increase on the hardware and software. 2 Standard Decoding Description The standard procedure for decoding the RS code is summarized below: STEP i: Compute syndr0_e_:= i Sj=V(a j+jO-1) for j= 1,2,...,2t. STEP 2::_ From t_esyn_romes,:form the error-io:cationpolynomi_ _A(z) !,Where A(z) = (1 - zX1)(1 - zX_) ... (1 - zXi) and X1,X_,... and Xi are the error locations. STEP 3: Find error location Xj (j = 1,...,i) by finding zeros of A(z). STEP 4: Find error magnitude Y_- (j = 1, ...,i) by calculating first i syndrome equations. STEP 5: Correct the error. Two polynomials are needed during the decoding and they are: =F. sY = and = (2) This second equation is commonly known as the Key Equation, because solving it is the key to decoding the RS code. After obtaining the error locations, the error magnitudes can be found as: 3rd NASA Symposium on VLSI Design 1991 3.4.3 x_°-m(xT') (3) Y_= h,(x71 For j0 = 1, n(x,--') Yt = - h,(XT_ ) (4) It is now clear that the decoding procedure becomes one of finding the A and f_ poly- nomials from S(x), and then finding the location and magnitude of the errors from those two polynomials. When erasures are involved, an erasnre-locator polynomial is created. r(_) =II(1- _x_) P where the Xv's are the erasure locations. The Key equation can be solved for A and f/in several ways. One of them is Euclid's recursive algorithm. The Euclid's recursive algorithm is briefly described below. First let f_(-1)(=) = =2t n(o)(=)= s(_)r(_) (modx 2') ' h(-_)(=) = 0 A(°)(=) = r(=) the recursive equations are n'(_) : nn(,-,)(,)[n(i-2)(=)], (5) or equivalently, _(i- 2)(=)= q(i)(=)n('-')(=)+ n(i)(=) (6) and i({)(=) : q(1)(_g)i(/-1)(= ) -_ 5({-2)(=) (7) The recursion is continued until the degree of f/ is less than t + p/2 , where p is the number of erasures. Erasures are the errors which have been located prior to decoding. Utilizing this infor- mation will improve the error correction capability of the decoder. Since the burst is a big part of a composite error, a burst erasure will make the error correction capability much greater. This idea leads to the following approach: STEP 1 Set stop conditions, the maximum iteration time N and n=0. STEP 2 Assume the burst begins at location a and n=n+l. 3.4.4 >[ buffer _Y_w input. data input[ er ror corrected ) choice corrected dat a AHA4010 unit erasure- l ocator correct polynomial gene r a tor found [ r=255 flag Figure 1: Block Diagram STEP 3 Decode the error with th=_gbgrst as erasyres, L STEP 4 If the result satisfies the stop conditions or n_.N, go to STEP 5. Else, increase the beginning location of the burst, go to STEP 2. STEP 5 Report the result. - = == in other words, the decoding method_, used by the extended decoder, is to guess where = the burst part of the error is and try to decode it. 3 Extended Decoder Design E m = The extended RS decoder has an AHA4010 decoder at its center. An erasure-locator pol 7- nomlal generator, an error choice unit _nd-a data:buffer are attached to the AHA4010 decoder: The top level block diagram of this extended decoder is shown in Figure 1. The erasure-iocator polynomial generator generates P(z). F(z) could be generated for every possible error location. However, this may not be necessary. For example, let error, e(z), be defined as: The error, e(z), can be interpreted as 1. e(z) = 0z -1 + a8 + c_%' + a°= 3 + a4z '3 A burst length of 5 (0z -x + ae + agz ' + a6z _+ a°z 3 ) and one random error (a_z_). 2. e(z) = Oz-2 + Oz-! + _s + _9zl + ctSz= + zS + a%ls. A burst length of 5 (0z -2 + 0z -1 + o_6 + c_gz1 + asz _ ) and two random errors - i_.t 3.4.5 3rd NASA Symposium on VLSI Design 1991 out put _>_ increase ,_cont roll r:O input Figure 2: Erasure-locator Polynomial Generator T f o und 4-1- co r rected corrected data dala CONTROLS: Tiff Po + Pt*CORRECT*(C*I)' T2= PI*CORRECT*(C=I) + P2*(CA>CB), T3= Po 4,- PI*CORRECT*(C=I) 4- P2*(CA>CB), T4-- Po + Pl*CORRECT*(C*I)" Figure 3: Error Choice Unit Ol_'_r_,L FA,.qE _S OF POOR QUALFW a. e(=i"-_ + 59_i + 5_ _+ 50_3+ 6_,+ 6_s+ 5,_-. Aburstie@thof5(56+_'51 +5°5' +505_+05') andOne_andome_or (0__,_,=-. burst length of 5 (Oz -_ + c_6 + 59z a + 56z 2 + 5°z a + Oz' ) and tlbo rafidom error A RS code with the abillty of correcting a burst of length 5 and 2 random errors Will Coi:r_c{ _ the errors alcove. Using this logic, P(z) can be generated every m error locatlon bits= The usgr must decide the v_ue qf m under the consideration ot'_ _iih4be÷ of _itera"ho,n• " hitn...e..s and - the-- si,ne of the correctable er_ro:r .... Meanwhile, the error choice unit stores tlie dgta coi:rected by the Ai-/a_iOiij decoagr _nd reverses it back to the error poiynomid. If _;he slz_ of the error is iess tlaan t; (i.e. This error has the highest probability of occurrence), the error choice unit interrupts the _teration and outputs the corrected data, Otherwise the iteration continues. H"more daan _he error is Eund, the error-choice UflK compares _liese_ errors and the Smallest error is chosen (it is assumed tha_ tile smaiJes_ error has the highest probability oi" occurrence). 4 rastire-Locator FoiynomJai Generator Assume the received code words have a composite er-_r p_rned with i random ettt_t_ _ be o,;_,,_;_,...,5;;_, wi_ere and one burs_ error o_ ieiigih v. T_e burs_ io_/i_ioil_ is from 0 fo 255. The erasure-i0eat0r polynomial, i_(Zi, has a form: r(,) II( = II(,_-' + ,5%,, d=l = a_'(Fiz" + l%z *-a + ... + r,z + 5 -') where ri, r_,andr_ are constant and r is form ! to 255. For each received code word, the corresponding decoding process is performed N/m _imes with N/m different P(z), where N is the length 9f t_he .RS code and m is the bits that F(z) skips. At each end Of the decoding process, a DONE Signal is sent to the erasure- locator polynomial generator. The DONE signal catiseS erasures to shift t9 the right m bits. Therefore, a new F(z) is generated. This operation repeats until a FOUND signal is received oi: r > 255. 3rd NASA Symposium on VLSI Design 1991 3.4.7 The erasure-locator polynomial generator is depicted in Figure 2. The coefficients of this polynomial, Pja p" (j from 0 to v), are not constant. Fja w multiply by a whenever INCREASE CONTROL (i.e. DONE signal) is assertive. The operations can be described in a register transfer language where each P{ is a control state that defines the data transfers that take place when P{ is active. A register transfer language description for the erasure-locator polynomial generator is shown below: • P0 : r=0, if GO=l, then go to P1. • P1 : if FOUND=I or r=255, then go to P0 , else P0 = at,F1 = I_lam,I'2 = F2a _',...,Fp = Fpa v" and r = r + I. • P2: P(z) = I-I(1 - za'), if DONE=l, go to P1 • 5 Error Choice Unit During the decoding iteration, it is possible that more than one error results. The error with the highest probability of occurrence should be chosen. It is assumed that will be the smallest error. The diagram of the error choice unit is shown in Figure 3. The first data corrected by the AHA4010 decoder is stored in register A, its correspond- ing error is also calculated and the size of the error is stored in CA. If the size of the error is less than t', the CMP asserts the FOUND signal and outputs the data in register A. The decoding process otherwise continues. The second corrected data is stored in register B, the size of the second error is stored in CB. The CMP compares the values of CA and CB. If CA > CB, A is replaced by B and CA is replaced by CB. If the value of CB is less than t', the CMP asserts the FOUND signal and outputs the data in register A. If CA < CB, nothing changes. This comparison is performed every time a corrected data is output from the AHA4010 decoder. It guarantees that the register A always has the data which is corrected from the smallest error. A signal from the erasure-locator polynomial generator tells the error choice unit that the iteration is finished. The data in register A is the output. A register transfer language description for the error choice unit is: • P0 : 0--_A,0---*B,I_C, FFH_CB, if GO=l, gotoP,. • P1 : if CA < t' or CB < t' or FLAG=I (i.e. r=255), output data, set FOUND=l, go to P0 • • if CORRECT=I & C=I, correctedData _ A, size (correctedData) --_ CA, c = c+l; • if CORRECT--1 & C :_1, correctedData _ B, size (correctedData) --+ CB; • P_:ifCA>CB,B--+A, CB_CA, gotoP1. CORRECT is a signal from the AHA4010 decoder which indicates a correction has or has not been made. C is a counter. It counts the number of correction times for one received code word. 3.4.8 6 An Example Consider a (255,235) RS code over GF(2 s) defined by the primitive polynomial p(x) - zs + z_ + z 2 + z i + 1 with the primitive element a = z. This code can normally correct ten random errors. Assume received errors have a burst of length 8 and 5 random errors. After considering the number of iteration times and the size of the correctable error, let's set the m=4 and t'=ll. SOLUTION: The received polynomial is: (9) When the extended RS decoder is turned on, the erasure-iocator polynomial is: s = 1-[(1+ al). (io) j=l This F(z) is sent to the AHA4010 decoder, the FOUND signal is zero. Multiply the coefficients of P(z) by a_2 (i.e. a "_ = ct4.s = ct3_). The erasure-iocator polynomial becomes: 8 = lI(1 + zcJa,) _=1 and thls_new r(z)=_s sen_ to'the A_X_i0, the FOUND s_gnal is :still zero.:T_s=_ecoding process performs repeatedly until the FOUND signal is one. That gives the corrected data: {o,o,o,...;0} The corresponding erasure-locator polynomial is: 8 T(z) = II(1 + zaJa 12) (11) j=l and the corresponding error polynomial is: r Summary An extended RS decoder has been "presented in this paper. With two extra circuits, the error correction capability of a general purpose RS decoder can be increased. This design shows a way to improve the error correction capability of existing RS decoders. 3rd NASA Symposium on VLSI Design 1991 3.4.9 References [1] P. Owsley, "Burst Error Correction Extensions for Reed Solomon Codes," PH.D Dis- sertation, E.E. Dept. University of Idaho, July 1988. [2] W. W. Peterson, "Encoding and Error-Correction Procedures for the Bose-Chaudhuri Codes," IEEE Trans. Inf. Theor. IT-6 (1960), pp. 459-470. [3] R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley Publishing Company, 1983. i ..... k ,i_iJ,=