Device, system and method of implementing product error correction codes for fast encoding and decoding

Abstract

A device, system and method for decoding a product code generated by encoding input data by a plurality of first and second dimension error correction codes. For each of a plurality of first dimension codewords, the first dimension input data codeword may be decoded using a first dimension error correction code and the first dimension codeword may be erased if errors are detected in the decoded first dimension codeword. For each of a plurality of second dimension codewords, the second dimension codeword may be decoded using a second dimension erasure correction code to recover an erasure in the second dimension codeword that was erased in the first dimension decoding.

1 - 26 . (canceled) 
     
     
         27 . A method for generating a product code, the method comprising:
 storing input data divided into a plurality of input data segments;   encoding the plurality of input data segments by a parity error correction code in a first dimension to generate a plurality of first dimension parity redundancy;   encoding the plurality of input data segments by an erasure error correction code in a second dimension to generate a plurality of second dimension erasure redundancy for correcting erasures,   wherein the first dimension parity error correction code and the second dimension erasure error correction code implement different types of error correction codes in the different first and second dimensions; and   generating a product code comprising a plurality of first dimension codewords comprising the input data and the plurality of first dimension parity redundancy in the first dimension and a plurality of second dimension codewords comprising the input data and the plurality of second dimension erasure redundancy in the second dimension.   
     
     
         28 . The method of  claim 27  comprising decoding the product code by:
 for each of the plurality of first dimension codewords:
 decoding the first dimension codeword using a first dimension parity error correction code decoder; 
 erasing the first dimension codeword if errors are detected in the decoded first dimension codeword; and 
 for each of the plurality of second dimension codewords: 
 
 decoding the second dimension codeword using a second dimension erasure correction code decoder, wherein the second dimension codeword redundancy contains erasure correction redundancy to correct an erasure in the second dimension codeword that was erased in the first dimension decoding. 
 
     
     
         29 . The method of  claim 27  comprising encoding one or more first data blocks of the input data by both the first dimension parity error correction code and the second dimension erasure error correction code and encode one or more second data blocks of the input data by the first dimension parity error correction code but not the second dimension erasure error correction code. 
     
     
         30 . The method of  claim 29  comprising, after a second dimension decoding corrects erasures in the first data block, repeating a first dimension decoding to propagate any corrected erasures to increase the probability of successfully decoding a first dimension codeword that had previously failed to decode. 
     
     
         31 . The method of  claim 27  comprising generating the product code to have a stair-step arrangement of input data blocks and erasure error correction redundancy blocks, comprising encoding each sequential data block in the product code by an erasure error correction redundancy block of incrementally increasing or decreasing length. 
     
     
         32 . The method of  claim 31  comprising, after a second dimension decoding corrects erasures in a current data block, repeating a first dimension decoding to propagate any corrected erasures to increase the probability of successfully decoding a first dimension codeword that had previously failed to decode. 
     
     
         33 . The method of  claim 32  comprising repeating the first and second dimension decoding for each sequential data block. 
     
     
         34 . The method of  claim 27 , wherein the product code further comprises error detection code to detect if errors exist in first or second dimension codewords. 
     
     
         35 . The method of  claim 27  comprising decoding the product code in two passes comprising decoding the first dimension codewords in a first pass and decoding the second dimension codewords in a second pass. 
     
     
         36 . The method of  claim 35 , wherein the first pass decoding is an erasure insertion channel that inserts erasures into the second dimension codewords of the product code and the second pass decoding is an erasure recovery decoder that corrects the inserted erasures with the erasure correction codes. 
     
     
         37 . The method of  claim 35  comprising repeating one or more additional iterations of the first and second passes if one or more first dimension codewords contain errors after the first iteration of the first and second passes. 
     
     
         38 . The method of  claim 27 , wherein the plurality of first dimension codewords are decoded by a maximum likelihood decoding, which determines, from multiple possible symbol values, a codeword that is most likely each first dimension codeword. 
     
     
         39 . The method of  claim 27 , wherein the plurality of second dimension codewords are decoded by solving a system of p or fewer equations with a set of p or fewer unknows corresponding to erasures, wherein p represents a length of the erasure correction redundancy in the second dimension codeword. 
     
     
         40 . A system for generating a product code, the system comprising:
 one or more processors configured to:
 store input data divided into a plurality of input data segments; 
 encode the plurality of input data segments by a parity error correction code in a first dimension to generate a plurality of first dimension parity redundancy; 
 encode the plurality of input data segments by an erasure error correction code in a second dimension to generate a plurality of second dimension erasure redundancy for correcting erasures, 
 wherein the first dimension parity error correction code and the second dimension erasure error correction code implement different types of error correction codes in the different first and second dimensions; and 
 generate a product code comprising a plurality of first dimension codewords comprising the input data and the plurality of first dimension parity redundancy in the first dimension and a plurality of second dimension codewords comprising the input data and the plurality of second dimension erasure redundancy in the second dimension. 
   
     
     
         41 . The system of  claim 40 , wherein the one or more processors are further configured to:
 for each of the plurality of first dimension codewords:
 decode the first dimension codeword using a first dimension parity error correction code decoder; 
 erase the first dimension codeword if errors are detected in the decoded first dimension codeword; and 
   for each of the plurality of second dimension codewords:
 decode the second dimension codeword using a second dimension erasure correction code decoder, wherein the second dimension codeword redundancy contains erasure correction redundancy to correct an erasure in the second dimension codeword that was erased in the first dimension decoding. 
   
     
     
         42 . The system of  claim 40 , wherein the one or more processors are further configured to encode one or more first data blocks of the input data by both the first dimension parity error correction code and the second dimension erasure error correction code and encode one or more second data blocks of the input data by the first dimension parity error correction code but not the second dimension erasure error correction code. 
     
     
         43 . The system of  claim 40 , wherein the one or more processors are further configured to generate the product code to have a stair-step arrangement of input data blocks and erasure error correction redundancy blocks, wherein each sequential data block in the product code is encoded by an erasure error correction redundancy block of incrementally increasing or decreasing length 
     
     
         44 . The system of  claim 40 , wherein the one or more processors are further configured to the generate the product code to have error detection code to detect if errors exist in first or second dimension codewords. 
     
     
         45 . The system of  claim 40  comprising a telecommunications device comprising one or more receivers to receive a distorted version of the product code transmitted by a transmitting telecommunications device over a communication channel. 
     
     
         46 . The system of  claim 40  comprising one or more memory devices to store the product code.