Iterative concatenated convolutional Reed-Solomon decoding method

[0001] The present disclosure relates generally to polynomial-generated error-correcting encoding and decoding and, more specifically, to Reed-Solomon (RS) error detection and correction techniques for example concatenated convolutional RS decoding.

[0002] Reed-Solomon coding and decoding schemes are used in many communication systems, such as satellites, modems, audio compact discs and wireless telephones. Each communication system has a different set of values for the parameters which define the Reed-Solomon code. Reed-Solomon encoders/decoders use Galois Field (GF) arithmetic to map blocks of communication into larger blocks.

[0003] As implemented in hardware, the Reed-Solomon encoder/decoder requires a substantial number of logic gates and other hardware. Many efforts have been directed to reducing the amount of hardware by, for example, parallel processing and reducing the arithmetic representation of the processes. Reed-Solomon decoders, specific to various communication systems, have been implemented in dedicated hardware blocks because of the computational complexity and low power requirements. See, for example, R. E. Blahut's “Theory and practice of error control codes,” Addison-Wesley, 1984; and S. B. Wicker's “Error control systems for digital communication and storage,” Prentice Hall, Inc., 1995.

[0004] One example of an error correction device for a communications system using the Reed-Solomon code is U.S. Pat. No. 6,065,149. The error correction device is provided with an internal code decoder which outputs a series of decoded data and reliability information of the decoded data, a CRC (Cyclic Redundancy Check) decoder, a de-interleaver, an erasure position detector, and an external code decoder for decoding an external code by soft judgment. When the external code is decoded by the soft judgment, not only the series of decoded data of the internal code and their reliability information, but also the frame error information based on CRC are used as input signals. In example described in the patent, one symbol in the Reed-Solomon code is constituted by 8-bits and therefore the Galois field is 256. After CRC decoding, the erasure position detector determines if 8-bits have been erased in 40 symbols. If so, it controls the external code decoder so as to correct the erasure of the 8 symbols. If no frame error is detected by the CRC decoder, the erasure position detector controls the external decoder to perform 4 symbol error correction. Thus, the system either performs corrections of the erasures for 8 symbols or performs 4 symbol error correction based on the results of the CRC decoder.

[0005] A similar system for coding and decoding symbols using CRC check bit of a Reed-Solomon code is described in U.S. Pat. No. 6,081,919. The decoding apparatus includes error detection using the CRC check bits performed after decoding of the inner decode. After symbol deinterleaving is performed, decoding of the outer code by erasure decoding or error detection is performed depending upon the number of symbols included in a frame in which an error has been detected. If the number of symbols in a frame after deinterleaving in which errors have been detected is not larger than the number of symbols which can be corrected by the erasure decoding, the decoding of the outer code is done by erasure decoding. If the number of symbols in the frame after deinterleaving which have detected errors is larger than the number of symbols which can be corrected by the erasure decoding, than the outer code is decoded by error correction. As in the previous patent, this is a system that performs either erasure decoding or error correction decoding.

[0006] The present system is a method and apparatus for decoding an encoded data stream of bits using an inner decoder, deinterleaver and an outer decoder. The outer decoder first decodes by error correction decoding for r errors per word. The decoding is terminated and a decoded word is outputted if the syndromes of the corrected word of the first decoding are all zeros. If the syndromes of the corrected word of the first decoding are not all zeros, a second decoding is performed by error correcting and erasure decoding for the number of errors r reduced by one and the number of erasures increased by two. The decoding is terminated and a decoded word is outputted if the syndromes of the corrected word of the second decoding are all zeros. If the syndromes of the corrected word of the second decoding are not all zeros, the second decoding by error correcting and erasure decoding is repeated for the number of errors reduced by one and the number of erasures increased by two for each iteration of the second decoding.

[0007] Also, a method and apparatus of decoding includes an inner coder, a deinterleaver and an outer decoder wherein the outer decoder first decodes by error correction for r error per word. The decoding is terminated and a decoded word is outputted if the syndromes of the corrected word of the first decoding are all zeros. If the syndromes of the corrected word of the first decoding are not all zeros, the error r is reduced by one and the number of erasures is increased by two. An error locator polynomial is derived and the degree of the error located polynomial is compared to the decreased number of errors if the syndromes of the corrected word of the first decoding are not all zeros. If the degree of the error locator is greater than the decreased number of errors, the number of errors are decreased by one and the number of erasures are increased by two and the deriving and comparing steps are repeated. If the degree of the error locator is equal to or less than the decreased number of errors, the second decoding by error correcting and erasure decoding is performed.

[0008] These and other aspects of the present disclosure will become apparent from the following detailed description of the disclosure, when considered in conjunction with accompanying drawings.

[0012] The present method is an iterative decoding algorithm for the Concatenated Convolutional Reed-Solomon encoders. The entire decoding algorithm is executed in software in an iterative fashion. The decoding process-starts assuming the received word has at most t errors, where 2t+1 is the code minimum distance. If, after the decoding process, all the syndromes are zero, the decoding is successful, otherwise most probable more than t errors are encountered. At this point the decoder will assume s erasure positions based on the erasure information coming from the convolutional decoder. If the error locator polynomial has the degree equal to or less than (2t−s)/2 or r (the number of errors) then most likely the error positions are in the current Galois-Field and the error correction and erasure algorithm is further performed. If not, set s=s+2 erasures and r=r−1 errors are assumed and again the degree of the error locator polynomial is checked and, so on until the maximum number of erasures is reached. In the case of errors only decoding, any of the known decoding algorithms can be used. In case of errors and erasures decoding, an algorithm is described herein. By not doing the entire decoding algorithm for each iteration, the increased computational complexity is easily manageable in software.

[0013] The present method can be used with an existing communication systems such as DSL, DVB-T/H, 802.11, 802.16 etc. Communication devices, for example from Sandbridge Technologies, allows an efficient software implementation of the Reed-Solomon function that provides both flexibility and low power consumption. In addition it allows correcting more than t errors. The total error and erasure correction capability is 2t.

[0014] FIG. 1 shows the block diagram for a concatenated decoding system with error/erasure decoding. The inner decoder 10 is shown as a SOVA (Soft Output Viterbi Algorithm) convolutional decoder. The SOVA decoder 10 processes the input signal stream x and its corresponding signal to noise ratio SNR estimates. The output of the SOVA 10 is the decoded information bit (hard decision) stream u and its associated log likelihood ratio reliability (soft decision, or L value) sequence L(u). u and L(u) are ran through a bit to byte packaging block 12 to generate the packed byte streams v and L(v) for outer processing. The outer deinterleaver 14 will output RS code words w and its associated erasure information E(w) for error/erasure RS decoding by outer decoder 16. The output of the outer decoder 16 is the decoded word.

[0015] Assume a convolutional code having a code rate: 1/N , there are only two branches ending in each trellis node; a constraint length: K; a memory of the code: m=K−1; and a number of trellis states: 2^m. In classical Viterbi algorithm for the inner decoder 10, for each trellis state S_k, S=0, . . . 2^m−1, at time instant k, compute the accumulated ML path metric:

[0016] $\Gamma \left(S_{k-1},S_k\right)=\Gamma \left(S_{k-1}\right)+\sum _{n=0}^{N-1}\frac{E_s}{N_o}{\left(y_{\mathrm{kn}}-x_{\mathrm{kn}}^{\left(i\right)}\right)}^2,i=1,2$

[0017] Where y_kn are the n^th output bits from the encoder if the state transitions from k−1 to k. x_knⁱ is the n^th soft input bit on the i^th path at time k. E_s/N_o is the corresponding SNR estimate for input bit x_knⁱ.

[0018] Γ(S_k)=min[Γ(S_k−1, S_k)] is determined, and stored with its associated survivor pre-state. In the above classical Viterbi algorithm, for two paths ending at the same node, only the information regarding the survivor path is saved. The information regarding the other path (the competing path) is discarded. SOVA looks at the path matrix difference:
Δ=max[Γ(S_k−1, S_k)]−min[Γ(S_k−1, S_k)]
to make a statement about the reliability for the survivor path decision.

[0019] At time instant k for state S_k, S=0 . . . 2^m−1, the reliability of selecting the right survivor path at time k for state S_k can be approximated as the path metric difference Δ_Sk^k. Each time when a survivor path is selected, the reliability values along the survivor path for the associated node needs to be updated if the survivor and competing paths yield different bit decisions on those nodes. FIG. 2 shows such an example. The survivor and competing paths will yield different bit decisions for nodes k−2 and k−3. The reliability values along the survivor path on these two nodes will need to be updated:
L_Sk^p=min[L_Sk^p, Δ_Sk^k], p=(k−2), and (k−3)

[0020] When making decoding decisions along the final ML survivor path, the corresponding reliability values for the decoded bit will be output as the “soft” decision for further processing.

[0021] The SOVA output bit stream u and its associated reliability information stream L(u) from the inner decoder 10 will run through a bit to byte packaging process at 12 to prepare for outer RS decoding at 16. Due to the byte processing nature of RS decoding, the associated output reliability information for the packaged byte v=[u_k, u_k−1, . . . u_k−7] is
L(v)=min[L(u_k−i)], i=0, 1, . . . k−7.

[0022] The decoded byte stream v and its associated reliability information stream L(v) will run through the outer deinterleaving block 14 to generate the RS decoder input code word w, and its corresponding reliability information block L(w).

[0023] The Reed Solomon outer decoder 16 can correct any code word that meets the following conditions: 2r+s≦2t, where r is the number of byte errors, and s is the number of erasures in a code word. Using the RS(204, 188, t=8) shortened code in DVB-T/DVB-H system as an example, if the inner decoder 10 outputs only hard decisions and the RS decoder 16 is an error-only decoder, then s=0, and r≦8, it will only be able to correct up to eight error bytes. On the other hand, if the inner decoder 10 can provide soft decision about the reliability for the decoded bits, then it will be possible to declare erasures on error locations. Consider the most ideal situation, where all the erasures are correctly declared on the error locations:

• [0024] When s=2, r≦7, the total correctable errors will be: s+r=9.
• [0025] When s=4, r≦6, the total correctable errors will be: s+r=10.
• [0026] When s=6, r≦5, the total correctable errors will be: s+r=11.
• [0027] When s=8, r≦4, the total correctable errors will be: s+r=12.
  So, it can be seen that the more erasures s are declared, the more total errors s+r will be corrected. In reality, it will be extremely difficult to declare a lot of erasures all accurately on error locations. In the present method, only s≦8 is considered.

[0028] For an RS(k,n) code, find the least reliable or smallest eight L(w_i), i=0,1, . . . n−1 locations as possible candidates for erasures in the RS packet. Since error/erasure RS decoder requires more MIPs than the error-only RS decoder, an iterative decoding process is used where the first normal pass of RS decoding will be an error-only RS decoder. In most cases, when error number r is up to eight as in the example of RS(204, 188, t=8), the decoding will be successful. When the error number r is over eight, the first pass error-only decoding will fail and the RS decoder will enter an iterative decoding process where it will run RS error/erasure decoder with the errors decreasing by one and the erasures increasing by 2. The relationship between errors r and erasures s is described in the next table for the GF[256] or the equation: 2r−+s=2t.

[0029]

	Errors r	Erasures s
	8	0
	7	2
	6	4
	5	6
	4	8
	3	10
	2	12
	1	14
	0	16

The iterative decoding process will stop either when the RS decoding is successful or when the next RS package is ready for processing.

[0030] FIG. 3 illustrates a flow diagram of an example of implementation of the present outer decoding process. The process begins at block 22 to start decoding with errors only. This means that the number of errors r would equal eight in the present example and the number of erasures would equal zero. This decoding would use one of the known decoding algorithms such as Peterson-Gorenstein-Zieler or Euclid or the Forney-Messey-Berlekamp. Next at 22, the syndromes of the corrected word are determined. If the syndromes of the corrected word are all zero, the error decoding only is declared successful and decoding is stopped and the corrected word is outputted at 24. If the syndromes of the corrected word are not all zero, the number of errors r is decreased by one and the number of erasure s is increased by two at 26.

[0031] The error locator polynomial is derived at 28. Next, it is determined whether the degree of the error locator polynomial is equal to or less than the decreased r at 30. If it is equal to or less than r, decode using an algorithm for example Forney-Messey-Berlekamp method for error correction and erasure decoding at 32. After the error-erasure decoding, it is determined at 34 whether the syndromes of the corrected word are all zero. If yes, the decoding is declared successful and stopped and the corrected word is outputted at 36. If the syndromes of the corrected word are not all zeros, decoding is declared a failure and stopped at 38.

[0032] If the degree of error of the locator polynomial for the reduced r is not equal to or less than the reduced r at 30, then the error r is reduced by one and the erasures S are increased by 2 at 40. It is determined at 42 whether the number of erasures S is greater than 2t. If it is not, the iterative process is restarted by determining the error locator polynomial at 28 and testing the degree at 30. If the number of erasures have maxed out at 42 than the decoding is declared a failure and is stopped at 44. The iterative process may also be stopped if the reiteration process is not completed before the arrival of the next packet. It should also be noted that the interlative decoding may be stopped before the erasures s equal 2t at 42. The optimal number of erasures s may depend upon the erasure position probability accuracy.

[0033] The particular communication code was used as an example to show the implementation of the present method. The present method is applicable to other codes and decoding.

[0034] The following description is an example of the error and erasure decoding algorithms to be implemented in the SB DVB-T/H or any other communication protocols utilizing RS GF(2^m) fields. It applies for any GF(2^m) field for either full length or shortened codes.

Given:

• • [0035] 1. Valid code word x=(x₀, x₁, . . . , x_n−1)
  • [0036] 2. Received word r=(r₀, r₁, . . . , r_n−1)
  • [0037] 3. Generator polynomial in polynomial form:

[0038] $g\left(D\right)=\prod _{i=0}^{2t-1}\left(D-{\alpha }^{i+j}\right),$
where D stands for the variable, α^j is the j^th unity root and, 2t+l is the code minimum distance.

• • [0039] 4. m=(m₁, m₂, . . . , m_t) is the error position vector.
  • [0040] 5. e=(e_m1, e_m2, . . . , e_mt) error magnitude
    In polynomial form, assuming that the decoder can decode t errors

[0041] $e\left(D\right)=\sum _{i=0}^t{e}_{m_i}{D}^{m_i}$
The syndromes S_i, 0≦i≦δ−2

[0042] $S_i=r\left(D\right){|}_{D={\varepsilon }^{i+j}}=e\left(D\right){|}_{D={\alpha }^{i+j}}=\sum _{p=1}^t{e_{m_p}\left({\alpha }^{i+j}\right)}^{m_p}$
The previous equation is based on
r(D)=x(D)+e(D)=a(D)g(D)+S(D)
The GF Fourier transform

[0043] $X_i\sum _{k=0}^{N-1}{x}_k{\alpha }^{\mathrm{ik}},\mathrm{where}{\propto }^N=1\mathrm{and}i=0\dots N-1$ $\mathrm{or}$ $X_i=\sum _{k=0}^{N-1}{x}_k{D}^k{|}_{D={\alpha }^i}$
The spectral coefficients are the evaluation of the polynomial at the roots ∝ⁱ, i=0 . . . N−1. The inverse GF Fourier transform is defined as:

[0044] $x_k=\frac{1}{N^{\prime }}X\left(D\right){|}_{D={\alpha }^{-k}}\mathrm{In}\mathrm{GF}\left(2^m\right),N^{\prime }=1.$

[0045] For errors only decoding, error locators L_p=α^mp, where p=1, . . . , t. The syndromes are:

[0046] $S_i=\sum _{p=1}^t{e_{m_i}\left(L_p\right)}^{i+j}\mathrm{where}i=0,\dots ,\delta -2$
Define connection polynomial:

[0047] $B\left(D\right)=\prod _{i=0}^{2t-1}\left(1-L_{p}D\right)=1+B_{1}D+\dots +B_t{D}^t$ $B\left(D\right)=0\mathrm{for}D=L_p,p=0,\dots ,\delta -2$
Therefore the inverse Fourier transform of the B coefficients will yield the b coefficients with nonzero values at the error locations. Hence b_m. e_m=0 for m=0, . . . , n−1, and the convolution:

[0048] $\begin{array}{cc}\sum _{p=0}^t{B}_p{E}_{i-p}=0\mathrm{or}{E}_i=\sum _{p=1}^t{B}_p{E}_{i-p}\mathrm{where}i=0,\dots ,n-1& \\ \mathrm{Since}{E}_i\equiv S_i,S_i=\sum _{p=1}^t{B}_p{S}_{i-p}& \left(1\right)\end{array}$

[0049] Any solution of the system Equation (1) will lead to the error locators. As previously discussed, the decoding may be direct solving by Peterson-Gorenstein-Zierler decoding algorithm or LSFR by Massey algorithm.

[0050] For erasures and errors decoding, the error locators L_p=α^mp, where p=1, . . . , r and the erasure locators Z_p=α^mp, where p=1, . . . , s. The correct values of code words at the error positions are −x_lp.

Decoding procedure includes:

• • [0051] 1. Stuff zero symbols in the l_p positions.
  • [0052] 2. Compute the syndromes S_i, 0≦i≦δ−2. The syndromes will represent δ−1 successive entries in the GF FT of the received sequence.

[0053] $S_i=\sum _{p=1}^r{e}_{m_p}{L}_p^{i+j}+\sum _{p=1}^s-x_{l_p}{Z}_p^{i+j}i=0,\dots ,\delta -2$ $S_i=E_{i+j}i=0,\dots ,\delta -2$
The GF FT of the incoming word:

[0054] $E=\left\{\underset{\underset{S_i,\dots S_{i+j}}{︸}}{E_0,E_1,\dots ,E_{i+j},\dots ,E_{i+\delta -2,j},\dots ,E_{n-1}}\right\}$

• • [0055] 3. Define the erasure locator polynomial

[0056] $\Lambda \left(D\right)=\prod _{i=1}^s\left(D-Z_p\right)={\lambda }_0{D}^s+\dots +{\lambda }_{s-1}{D}^{s-1}+{\lambda }_s$

• • [0057] 4. Modify the original syndromes (Forney)

[0058] $T_i=\sum _{p=0}^s{\lambda }_p{S}_{i+s-p}\mathrm{where},i=0,\dots ,\delta -s-2$

• • [0059] T_i are the modified syndromes and contains the error and erasure information.
• [0060] 5. Find T_i coefficients. The error locator polynomial coefficients are obtained through the Massey shift register algorithm. First, determine the 2t−s T coefficients from

[0061] $T_i=\sum _{p=0}^s{\lambda }_p{S}_{i+s-p}$
For this step the syndrome and erasure locator polynomials have the following form
S(D)=S₀+S₁D+ . . . +S_2t−1D^2t−1
λ(D)=λ₀+λ₁D+ . . . +λ_sD^s

• • [0062] 6. Massey algorithm:
    • [0063] A. Initialize: k=0, B⁽⁰⁾(x)=1, L=0 and T(x)=x.
    • [0064] B. Loop k=1, . . . , 2t−s
    • [0065] C. Compute the discrepancy

[0066] ${\Delta }^{\left(k\right)}=T_k-\sum _{i=1}^L{B}_i^{\left(k-1\right)}{T}_{k-1}$

• • • [0067] D. If Δ^(k)=0 Then Go To H
    • [0068] E. Modify connection polynomial B_i^(k)(x)=B_i^(k−1)(x)−Δ^(k)T(x)
    • [0069] F. If 2L≧k Then Go To H
    • [0070] G. L=k−L, T(x)=B^(k−1)(x)Δ^(k)−1
    • [0071] H. T(x)=xT(x)
  • [0072] 7. Compute error locations by solving the B(x).
  • [0073] 8. Compute error magnitudes (Forney)

[0074] $\frac{L_k\Omega \left(L_k^{-1}\right)}{{\Psi }^{\prime }\left(L_k^{-1}\right)}$

• • [0075] Where Ω(x)=B(x)[S(x)+1]] and, Ψ′(D) is the formal derivative of Ψ(D)=Γ(D)[S(D)+1]]
  • [0076] 9. Compute the erasure magnitudes

[0077] $\frac{Z_k\Omega \left(Z_k^{-1}\right)}{{\Psi }^{\prime }\left(Z_k^{-1}\right)}$

• • [0078] 10. Correct for errors and erasures
    The relationship between the total number of correctable errors and erasures is (2t−N_L)/2=N_z

[0079] Although the present disclosure has been described and illustrated in detail, it is to be clearly understood that this is done by way of illustration and example only and is not to be taken by way of limitation. The scope of the present disclosure is to be limited only by the terms of the appended claims.