Combined Koetter-Vardy and Chase decoding of cyclic codes

Abstract

An apparatus having a first circuit and a second circuit is disclosed. The first circuit may be configured to generate (i) a plurality of symbols and (ii) a plurality of decision values both in response to detecting an encoded codeword. The second circuit may be configured to (i) generate a plurality of probabilities to flip one or more of the symbols based on the decision values, (ii) generate a modified probability by merging two or more of the probabilities of an unreliable position in the symbols and (iii) generate a decoded codeword by decoding the symbols using an algebraic soft-decision technique in response to the modified probability.

The invention claimed is: 
     
       1. An apparatus comprising:
 a device configured to (i) generate a plurality of probabilities to flip one or more of a plurality of symbols of an encoded codeword based on a plurality of decision values corresponding to said encoded codeword, (ii) generate a modified probability by merging two or more of said probabilities of an unreliable position in said symbols and (iii) generate a decoded codeword by decoding said symbols using an algebraic soft-decision technique in response to said modified probability. 
 
     
     
       2. The apparatus according to  claim 1 , wherein (i) said probabilities are generated using a Chase technique and (ii) said algebraic soft-decision technique comprises a Koetter-Vardy technique. 
     
     
       3. The apparatus according to  claim 1 , wherein said encoded codeword comprises one of (i) a Reed-Solomon encoded codeword and (ii) a BCH encoded codeword. 
     
     
       4. The apparatus according to  claim 1 , further comprising a circuit configured to generate (i) said symbols and (ii) said decision values both in response to a soft detecting said encoded codeword. 
     
     
       5. The apparatus according to  claim 1 , wherein said decisions comprise a plurality of hard decisions and a plurality of soft decisions. 
     
     
       6. The apparatus according to  claim 5 , wherein (i) a first of said probabilities corresponds to one of said hard decisions, (ii) a second of said probabilities corresponds to one of said soft decisions and (iii) said merging comprises adding said first probability and said second probability. 
     
     
       7. The apparatus according to  claim 1 , wherein (i) said device is further configured to assign a plurality of multiplicities in a plurality of multiplicity matrices in response to said modified probability, and (ii) said algebraic soft-decision technique is based on said multiplicity matrices. 
     
     
       8. The apparatus according to  claim 7 , wherein (i) said device is further configured to interpolate a bivariate polynomial in response to said multiplicity matrices and (ii) said algebraic soft-decision technique is based on said bivariate polynomial. 
     
     
       9. The apparatus according to  claim 1 , wherein said device is further configured to flip one or more of said symbols in response to a constant term of a bivariate polynomial being non-zero. 
     
     
       10. The apparatus according to  claim 1 , wherein said apparatus is implemented as one or more integrated circuits. 
     
     
       11. A method of cyclic code decoding, comprising the steps of:
 (A) generating a plurality of probabilities to flip one or more of a plurality of symbols of an encoded codeword based on a plurality of decision values corresponding to said encoded codeword; 
 (B) generating a modified probability by merging two or more of said probabilities of an unreliable position in said symbols; and 
 (C) generating a decoded codeword by decoding said symbols using an algebraic soft-decision technique in response to said modified probability. 
 
     
     
       12. The method according to  claim 11 , wherein (i) said probabilities are generated using a Chase technique and (ii) said algebraic soft-decision technique comprises a Koetter-Vardy technique. 
     
     
       13. The method according to  claim 11 , wherein said encoded codeword comprises one of (i) a Reed-Solomon encoded codeword and (ii) a BCH encoded codeword. 
     
     
       14. The method according to  claim 11 , further comprising the step of:
 generating (i) said symbols and (ii) said decision values both in response to soft detecting said encoded codeword. 
 
     
     
       15. The method according to  claim 11 , wherein said decisions comprise a plurality of hard decisions and a plurality of soft decisions. 
     
     
       16. The method according to  claim 15 , wherein (i) a first of said probabilities corresponds to one of said hard decisions, (ii) a second of said probabilities corresponds to one of said soft decisions and (iii) said merging comprises adding said first probability and said second probability. 
     
     
       17. The method according to  claim 11 , further comprising the step of:
 assigning a plurality of multiplicities in a plurality of multiplicity matrices in response to said modified probability, wherein said algebraic soft-decision technique is based on said multiplicity matrices. 
 
     
     
       18. The method according to  claim 17 , further comprising the step of:
 interpolating a bivariate polynomial in response to said multiplicity matrices, wherein said algebraic soft-decision technique is based on said bivariate polynomial. 
 
     
     
       19. The method according to  claim 11 , further comprising the step of:
 flipping one or more of said symbols in response to a constant term of a bivariate polynomial being non-zero. 
 
     
     
       20. An apparatus comprising:
 means for generating a plurality of probabilities in a device to flip one or more of a plurality of symbols of an encoded codeword based on a plurality of decision values corresponding said encoded codeword; 
 means for generating a modified probability by merging two or more of said probabilities of an unreliable position in said symbols; and 
 means for generating a decoded codeword by decoding said symbols using an algebraic soft-decision technique in response to said modified probability.