Error correction with fast syndrome calculation

Abstract

Error correction is proposed in which a syndrome calculation is carried out in a code domain of a second code and an efficient error correction algorithm is carried out in a code domain of a first code.

What is claimed is: 
     
       1. A method for error correction in a data processing circuit configured to carry out a syndrome calculation, comprising:
 carrying out a syndrome calculation in a code domain of a second code, using the data processing circuit, and 
 carrying out an efficient error correction algorithm in a code domain of a first code, using the data processing circuit; 
 
       wherein the method comprises, between the syndrome calculation and carrying out the efficient error correction algorithm, transitioning between the code domains by means of at least one linear mapping. 
     
     
       2. The method of  claim 1 , further comprising:
 receiving a data word in the code domain of the first code and converting into the code domain of the second code by means of a first linear mapping, 
 wherein the syndrome calculation is carried out in the code domain of the second code on the basis of the result of the first linear mapping and, in response to determining that the result of the syndrome calculation reveals that the data word is erroneous:
 converting the result of the syndrome calculation into the code domain of the first code by means of a second linear mapping, 
 determining an error vector on the basis of the result of the second linear mapping in the code domain of the first code by means of the efficient error correction algorithm, and 
 correcting the erroneous data word on the basis of the error vector. 
 
 
     
     
       3. The method of  claim 2 ,
 wherein the first code is determined by a matrix H, 
 wherein the second code is determined by a matrix K, 
 wherein the first linear mapping P and the second linear mapping L are determined such that the following holds true:
     H=L·K·P.    
 
 
     
     
       4. The method of  claim 3 , wherein the matrix K is a check matrix comprising a unit matrix. 
     
     
       5. The method of  claim 2 , wherein the first linear mapping comprises a permutation. 
     
     
       6. The method of  claim 1 , further comprising carrying out the syndrome calculation in the code domain of the second code on the basis of a received data word and, in response to determining that the result of the syndrome calculation reveals that the data word is erroneous:
 converting the result of the syndrome calculation is converted into the code domain of the first code by means of a second linear mapping, 
 determining an error vector of the code domain of the first code on the basis of the result of the second linear mapping in the code domain of the first code by means of the efficient error correction algorithm, 
 converting the error vector of the code domain of the first code into an error vector of the code domain of the second code by means of a first linear mapping, and 
 correcting the erroneous data word on the basis of the error vector of the code domain of the second code. 
 
     
     
       7. The method of of  claim 6 ,
 wherein the first code is determined by a matrix H, 
 wherein the second code is determined by a matrix K, 
 wherein the first linear mapping P and the second linear mapping L are determined such that the following holds true:
     H=L·K·P.    
 
 
     
     
       8. The method of  claim 7 , wherein the matrix K is a check matrix comprising a unit matrix. 
     
     
       9. The method of  claim 6 , wherein the first linear mapping comprises a permutation. 
     
     
       10. A device for error correction comprising a processing circuit, wherein the processing circuit is configured to:
 carry out a syndrome calculation in a code domain of a second code, and 
 carry out an efficient error correction algorithm in a code domain of a first code; 
 
       wherein the processing circuit is configured to carry out, between the syndrome calculation and carrying out the efficient error correction algorithm, a transition between the code domains by means of at least one linear mapping. 
     
     
       11. The device of  claim 10 , wherein the processing circuit is further configured to:
 receive a data word in the code domain of the first code and convert it into the code domain of the second code by means of a first linear mapping, 
 carry out the syndrome calculation in the code domain of the second code on the basis of the result of the first linear mapping and, if the result of the syndrome calculation reveals that the data word is erroneous:
 convert the result of the syndrome calculation into the code domain of the first code by means of a second linear mapping, 
 determine, on the basis of the result of the second linear mapping in the code domain of the first code, an error vector by means of the efficient error correction algorithm, 
 correct the erroneous data word on the basis of the error vector. 
 
 
     
     
       12. The device of  claim 11 ,
 wherein the first code is determined by a matrix H, 
 wherein the second code is determined by a matrix K, 
 wherein the first linear mapping P and the second linear mapping L are determined such that the following holds true;
     H=L·K·P.    
 
 
     
     
       13. The device of  claim 12 , wherein the matrix K is a check matrix comprising a unit matrix. 
     
     
       14. The device of  claim 11 , wherein the first linear mapping comprises a permutation. 
     
     
       15. The device of  claim 10 , wherein the processing circuit is configured to carry out the syndrome calculation in the code domain of the second code on the basis of a received data word and, if the result of the syndrome calculation reveals that the data word is erroneous:
 convert the result of the syndrome calculation into the code domain of the first code by means of a second linear mapping, 
 determine an error vector of the code domain of the first code on the basis of the result of the second linear mapping in the code domain of the first code by means of the efficient error correction algorithm, 
 convert the error vector of the code domain of the first code into an error vector of the code domain of the second code by means of a first linear mapping, and 
 correct the erroneous data word on the basis of the error vector of the code domain of the second code. 
 
     
     
       16. The device of  claim 15 ,
 wherein the first code is determined by a matrix H, 
 wherein the second code is determined by a matrix K, 
 wherein the first linear mapping P and the second linear mapping L are determined such that the following holds true:
     H=L·K·P.    
 
 
     
     
       17. The device of  claim 16 , wherein the matrix K is a check matrix comprising a unit matrix. 
     
     
       18. The device of  claim 10 , wherein the processing circuitry is configured to effect no correction if no error was determined on the basis of the result of the syndrome calculation. 
     
     
       19. A non-transitory computer-readable medium comprising, stored thereupon, a computer program product that is directly loadable into a memory of a digital computer configured to carry out a syndrome calculation and that comprises program code parts configured to cause said digital computer to carry out a method for error correction, said method comprising:
 carrying out a syndrome calculation in a code domain of a second code, and 
 carrying out an efficient error correction algorithm in a code domain of a first code; 
 
       wherein said method further comprises, between the syndrome calculation and carrying out the efficient error correction algorithm, transitioning between the code domains by means of at least one linear mapping.