A novel algorithm is proposed for soft decoding of Reed-Solomon codes. This algorithm is based on list decoding algorithm allowed to correct errors beyond half the minimum distance. The coding gain of the proposed algorithm is shown for some high rate codes. A block diagram of new ReedSolomon soft decoder is given.
A Reed-Solomon (RS) code [
It is known that RS codes can correct any pattern of t errors or less iff 2t+1≤d (or
t≤ tC). Several efficient RS decoding algorithms are developed for correcting up to tC
errors. Two frequently used are the Berlekamp-Massey (BM) algorithm and the
algorithm by Sugiyama et al. [
A procedure providing tC+1 error correction for RS codes was developed by Blahut
[
In [
Guruswami and Sudan proposed an algorithm providing tC+ τ (τ ≥1) error
correction for RS codes (GS-algorithm) [
In this paper a novel algorithm for soft decoding of Reed-Solomon codes is
proposed. This algorithm is based on list decoding algorithm allowed to correct errors
beyond half the minimum distance [
The proposed soft decoding algorithm is based on the list decoding algorithm. In this
section this list decoding algorithm is described following [
Basic list decoding algorithm belongs to the class of decoding algorithms known as
“syndrome decoding algorithms” and is based on the Berlekamp-Massey algorithm
[
The main idea of this algorithm is to continue analytically the Berlekamp-Massey algorithm through 2τ more iterations and to search for values of error position, such that the corresponding error locator polynomial of degree tC+τ has exactly tC+τ legitimate roots.
The basic list decoding algorithm consists of the following steps: 1) Calculate the syndrome polynomial S(x).
2) Calculate the locator polynomial (2tC ) (x) , auxiliary polynomial B (2tC ) ( x) and formal degree of the locator polynomial L2tC using 2tC iterations of the Berlekamp
3) Calculate the Fourier transforms of the polynomials (2tC ) (x) and B(2tC ) (x) . 4) Search for unknown discrepancies 2tC 1, 2tC 2 ,..., 2tC 2 , such as that (2tC2 )( i ) 0 for exactly tC+τ values of i. The values of i locate error positions. 5) Compute error magnitudes and correct errors.
The algorithm described above fulfils a list decoding procedure, it finds all the codewords that lie within the decoding sphere of radius t=tC+τ drawn about the received codeword.
Computational complexity of the step 4 of the algorithm is bounded by polynomial in n for constant τ. In particular, for τ = 1 the complexity is described as O(n2), for τ = 2 as O(n4). Total complexity of the algorithm is less than one of Guruswami-Sudan algorithm for small τ.
In detail this list algorithm was presented in [
The proposed soft decoding algorithm is based on list decoding algorithm described above. The main step 4 of the list decoding algorithm is altered as following:
Calculate the sequences S L[i1],L[i2 ],..., L[i2 1 ] of possible values of the discrepancy L[i1 ], L[i2 ],..., L[i2 ] for all permitted sets of indices i1, i2,…,i2τ-1 (i2τ = i2τ -1+1,…, nC-1), and search for discrepancy values which are happened exactly w times in any sequences S L[i1 ], L[i2 ],..., L[i2 1 ] :
SL[i1],L[i2],...,L[i2 1] {L[i1],L[i2],...,L[i2 ] where: { j1, j2,...,jo}J {k1,k2} j1 j2... jo k1k2 j1, j2,...,jo{1,2,...,2 } k1,k2J F o ( L[i1 ], L[i2 ],..., L[i2 ], RL[i1 ] , RL[i2 ] ,..., RL[i2 ] ) ( L[ik1] L[ik2] ) {k1,k2} k1k2 k1,k2{1,2,...,l}\J
o ( L[ik1] L[ik2] )RL[i j ] k1 k , (2 s1)i B (2tC ) ( i ) / (2tC ) ( i ) if s 0, Ri (2s1)i (2tC ) ( i ) / B (2tC ) ( i ) in other case s = tC - ܮ ଶ௧ , o1 = τ - |s+1|, o2 = τ - |s|.
If there exists a discrepancy value which is happened exactly w times in some sequence S L[i1 ], L[i2 ],..., L[i2 1 ] then error positions are given by index set L[i1], L[i2],…, L[i2τ-1] of this sequence and by set of L[i2τ] values corresponding the discrepancy value in this sequence.
The error position search is fulfilled in order of ascending total symbol reliability measure. A symbol reliability measure may be estimated on the base of soft decisions about symbol bits. The sequence of symbol position ordered by symbol reliability measures is stored in the table L[ ]. The search range is bounded by nC ≤ n and contains the least reliable symbol position of the received codeword.
The soft decoding algorithm is many orders lower in complexity compared to the basic list decoding algorithm.
The proposed soft decoding algorithm consists of the following steps: 1) Calculate the syndrome polynomial S(x). If terms of S(x) are all zero, then go to step 14 (there are no errors in the received codeword).
2) Calculate the locator polynomial (2tC ) (x) , auxiliary polynomial B (2tC ) ( x) and formal degree of the locator polynomial L2tC using 2tC iterations of the Berlekamp
3) If L2tC ≤ tC, then roots of the polynomial (2tC ) (x) are searched. If the number
of legitimate roots is equal to L2tC , then their inverses are considered as error locators.
Error magnitudes are computed using Forney’s formula [
4) Set s (shift): s = tC - L2tC . If s ≥ τ or s< - τ, go to step 13.
5) Calculate the Fourier transforms of the polynomials (2tC ) (x) and B(2tC ) (x) .
6) Calculate the set of fractions Ri (2s1)i B(2tC ) ( i ) / (2tC ) ( i ) when s ≥ 0 or Ri (2s1)i(2tC ) ( i ) / B(2tC ) ( i ) otherwise, i=0,…,n-1.
7) Set v = 1 (v is number of extra errors for correction). 8) Calculate the auxiliary variables: l = 2v, o1 = v - |s+1|, o2 = v - |s|, w = tC +1-v. 9) Set sc = 1 (sc is counter of equation set).
10) Calculate the sequences S L[i1 ],L[i2 ],..., L[il 1 ] of possible values of the discrepancy L[i1 ],L[i2 ],..., L[il ] for most probable sets of indices i1, i2,…,il-1 (il = il-1 +1,…,n1), and search for discrepancy values which are happened exactly w times in any sequences S L[i1],L[i2 ],..., L[il 1 ] (1).
S L[i1],L[i2 ],..., L[il1]
If there exists a discrepancy value which is happened exactly w times in some sequence then error positions are given by index set L[i1], L[i2 ],...,L[il1] of this sequence and by set of L[il] values corresponding the discrepancy value in this sequence.
Compute error magnitudes using Forney’s formula. A false error pattern is rejected, true one is introduced in the list.
If error pattern is introduced in the list and (exit = 1 or exit = 2), then search is finished. If exit = 1 then go to step 13. If exit = 2 then go to step 11.
11) If v = -s, then go to step 12, else sc = sc +1, l = l – 1, o1 = o1 – 1, o2 = o2 – 1, w = w + 1.
If sc ≤ (v-|s|), then go to step 10. 12) v=v+1. If v≤ τ, then go to step 8.
13) If the error list is empty, then decoding failure. If error list contains one error pattern, then this error pattern is corrected. If error list contains more error patterns, then error pattern is corrected such as closest to the received codeword. 14) End.
The following notations are used for the algorithm description: - L is lookup table contained symbol position ordered by reliability. - exit is exit mode of the algorithm, exit {0,1,2} , 0 – usual exit, 1 - urgent exit after detecting first error pattern, 2 – exit after detecting first error patterns for all system sets.
The soft decoding algorithm was simulated for some practical high rate RS codes with d=17. The modulation used was BPSK and the channel model was AWGN. The minimum of symbol bit LLRs is taken as the reliability measure of the symbol.
Fig. 1, 2 show the performance of the new algorithm for these codes. Fig. 3 shows
the average complexity of discrepancy computation for RS code (120,104). On the all
figures: 1 denotes the conventional decoding algorithm correcting up to tC errors
(t=8), 2 – the proposed soft decoding algorithm with τ =1 (t=9), 3 – this algorithm
with τ =2 (t=10), 4 – this algorithm with τ =3 (t=11), 5 – Koetter-Vardy algorithm
(multiplicity 2) [
A (255,239) RS code is used for long hall optical transmission. A coding gain of 0.42 dB (FER of 10-2) over the conventional algorithm is achieved with τ =3 (t=11) (see fig. 1). This coding gain is more than one of Koetter-Vardy algorithms with small multiplicities.
The simulation results for the (120,104) RS code used in WORM optical disks are shown in the figure 2. We see that a coding gain of 0.48 dB (FER of 10-3) over the conventional decoding algorithm is achieved by the new algorithm with τ =3 (t=11).
In the fig. 3 ξ denotes an average number of GF arithmetical operations needed for calculation of discrepancies for one received codeword. It is assumed that one multiplication is equaled to m additions, and one division is equaled to m2 additions, (m – number of bits in the RS-code symbol). The adding of soft decisions into the basic list decoding algorithm decreases in computational complexity by decimal order and more. 4
The proposed algorithm can be implemented with simple hardware. A block diagram of a decoder is shown in fig. 4. The decoder consists of a data buffer, a syndrome calculator, a sorting circuit, a Galois processor, a discrete Fourier transform (DFT) circuit, an error position searcher and an error value calculator.
DIn ri
800 DOut Ci ( x ) Error '( x) Value {PE} Calculator 200 600 SoftIn reli {PE} Sorting AddrR1 Circuit Syndrome S(x) Calculator
(Berlekamp-Massey) t)(2 xt)(2 xB 400 Discrete
Fourier Ri Transform Msk1
Circuit Ai AddrW {PE’} ''
The decoder operates as a pipeline. Its units handle simultaneously the varied sequenced received codeword.
The data buffer, the syndrome calculator, the Galois processor and the error value calculator function as usual. Additionally, the Galois processor calculates (2tC2 ) (x) , when there are tC+τ error positions found.
The sorting circuit generates a sequence of codeword symbol position ordered by symbol reliability measures and stores it in the table L[ ].
The DFT circuit calculates Fourier transforms of the polynomials (2tC) (x) and B(2tC) (x) and calculates coefficients Ri. Additionally, the DFT circuit calculates the inverse of the roots of the polynomial (2tC ) (x) and checks that the number of roots is not equal to L2tC
when L2tC tC.
The error position searcher fulfils steps 7-10 of the proposed algorithm. The tC+ τ error positions {PE’} and the corresponding values are found by the searcher. The error position searcher performs most operations in the present decoder. 5
The proposed soft decoding algorithm increases the coding gain of RS codes in telecommunication and storage systems without any modification of the existing standards.
Using symbol reliability measures reduces greatly the computational complexity of the algorithm comparing to basic list decoding algorithm.