Abstract:
Methods and apparatus are provided for integrated-interleaved Low Density Parity Check (LDPC) coding and decoding. Integrated-interleaved LDPC encoding is performed by obtaining at least a first data element and a second data element; systematically encoding the at least first data element using a submatrix H 0  of a sparse parity check matrix H 1  to obtain at least a first codeword; truncating the at least first data element to obtain at least a first truncated data element; systematically encoding the at least second data element and the at least first truncated data element using the sparse parity check matrix H 1  to obtain a nested codeword; and generating a second codeword based at least in part on a combination of the first codeword and the nested codeword. Integrated-interleaved LDPC decoding is also provided.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a divisional of U.S. patent application Ser. No. 13/755,757, filed Jan. 31, 2013 (now U.S. Pat. No. 9,077,378), and incorporated by reference herein. 
    
    
     FIELD 
     The present invention relates generally to error correcting codes, and more particularly, to integrated-interleaved encoding and decoding techniques. 
     BACKGROUND 
     Error correcting codes allow data errors to be detected and corrected, provided the number of errors or the characteristics of the errors fall within the correction capabilities of the code that is used. Integrated-interleaved codes, for example, are systematic codes (i.e., the input data is included or otherwise embedded in the encoded data) that generate multiple codewords, each of which is associated with a particular level. The integrated-interleaved coding scheme can be used to compensate for format inefficiencies due to small block lengths and be deployed in distributed storage systems. 
     SUMMARY 
     Generally, methods and apparatus are provided for integrated-interleaved Low Density Parity Check (LDPC) coding and decoding. According to one aspect of the invention, integrated-interleaved LDPC encoding is performed by obtaining at least a first data element and a second data element; systematically encoding the at least first data element using a submatrix H 0  of a sparse parity check matrix H 1  to obtain at least a first codeword; truncating the at least first data element to obtain at least a first truncated data element; systematically encoding the at least second data element and the at least first truncated data element using the sparse parity check matrix H 1  to obtain a nested codeword; and generating a second codeword based at least in part on a combination of the first codeword and the nested codeword. 
     According to another aspect of the invention, integrated-interleaved LDPC decoding is performed by; obtaining a channel word, y, comprised of a plurality m of component words, y 0  through y m-1 ; applying a min-sum decoding technique to each of the plurality of component words, y 0  through y m-1 , to obtain a corresponding plurality of decoded codewords, c 0  through c m-1 ; detecting a failed component word, y j  incurring a decoding failure; adding all passing decoded codewords (c i , for i equal to 0 through m−1, where i does not equal j) from the plurality of decoded codewords, c 0  through c m-1  to the failed component word, y j , to obtain a resulting channel word, y; decoding the resulting channel word, y, with respect to a sparse parity check matrix H 1  to generate a corresponding decoded codeword, c; and declaring a decoded codeword, c j , corresponding to the failed component word, y j , to be equal to the decoded codeword, c, less a sum of the all passing decoded codewords (c i , for i equal to 0 through m−1, where i does not equal j) from the plurality of decoded codewords, c 0  through c m-1 , if the corresponding decoded codeword, c, decoded to a valid codeword. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         FIG. 1  illustrates an exemplary communication system in which aspects of the present invention can be employed; 
         FIG. 2  is a block diagram of an exemplary two-level integrated-interleaved Low Density Parity Check (LDPC) encoder incorporating aspects of the present invention; 
         FIG. 3  is a flowchart illustrating an embodiment of an exemplary encoding process for two-level integrated-interleaved LDPC encoding; and 
         FIG. 4  is a flowchart illustrating an embodiment of an exemplary decoding process for two-level integrated-interleaved LDPC decoding. 
     
    
    
     DETAILED DESCRIPTION 
     Various aspects of the invention are directed to integrated-interleaved LDPC encoding and decoding techniques. A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured. 
     Integrated-Interleaved Coding Scheme 
     The integrated-interleaved coding scheme nests a set of m component codewords with v (v&lt;m) more powerful (e.g., second or higher level) codewords in the nested layer which is a subcode of the component layer. Thus, v can be considered a number of second level codewords. The nested layer enables the correction of up to v component words that fail by self-decoding. For a more detailed discussion of the integrated-interleaved coding scheme, see, for example, U.S. Pat. No. 5,946,328, entitled “Method and Means for Efficient Error Detection and Correction in Long Byte Strings Using Integrated Codewords;” M. A. Hassner et al., “Integrated Interleaving—a Novel ECC Architecture,” IEEE Trans. Magnetics, vol. 37, 773-775 (March 2001); and/or U.S. Pat. No. 8,161,360, entitled “Integrated Interleaved Codes,” each incorporated by reference herein. 
     Under an exemplary two-level integrated-interleaved coding scheme, let (C i ) i=0   1  be (n,k i ,d i ) over the Galois field GF(q) such that C 1 ⊂C 0  and d 1 &gt;d 0 , where C i , i=0,1, explicitly assume cyclic components codes, such as Reed-Solomon codes (possibly shortened). Denote by α a primitive element of GF(q). An integrated-interleaved code is defined as follows: 
                     C   ⁢   ⁢     {       c   =         [       c   0     ,     c   1     ,     c   2     ,   …   ⁢           ,     c     m   -   1         ]     ⁢     :     ⁢     c   i       ∈     C   0         ,         ∑     i   =   0       m   -   1       ⁢           ⁢       α   bi     ⁢     c   i         ∈     C   1       ,     b   =   0     ,   1   ,   2   ,   …   ⁢           ,     v   -   1       }       ,           (   1   )               
where v&lt;m&lt;q.
 
Integrated-Interleaved LDPC Coding Scheme
 
     According to one aspect of the present invention, the above integrated-interleaved code description is extended to LDPC codes with respect to v=1. Let H 1  be a sparse parity check matrix of C 1 (n,k 1 ) LDPC code and H 0  be a submatrix of H 1  corresponding to C 0 (n,k 0 ) LDPC code. An exemplary integrated-interleaved LDPC code can be defined as follows: 
     
       
         
           
             
               
                 
                   C 
                   ⁢ 
                   ⁢ 
                   
                     { 
                     
                       
                         c 
                         = 
                         
                           
                             
                               [ 
                               
                                 
                                   c 
                                   0 
                                 
                                 , 
                                 
                                   c 
                                   1 
                                 
                                 , 
                                 
                                   c 
                                   2 
                                 
                                 , 
                                 … 
                                 ⁢ 
                                 
                                     
                                 
                                 , 
                                 
                                   c 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                 
                               
                               ] 
                             
                             ⁢ 
                             
                               : 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               H 
                               0 
                             
                             ⁢ 
                             
                               c 
                               i 
                               T 
                             
                           
                           = 
                           0 
                         
                       
                       , 
                       
                         
                           
                             
                               H 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     0 
                                   
                                   
                                     m 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   c 
                                   i 
                                 
                               
                               ) 
                             
                           
                           T 
                         
                         = 
                         0 
                       
                     
                     } 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
       FIG. 1  illustrates an exemplary communication system  100  in which aspects of the present invention can be employed. As shown in  FIG. 1 , a transmitter  110  includes an integrated-interleaved LDPC encoder  200 , as discussed further below in conjunction with  FIGS. 2 and 3 . Data is encoded using an integrated-interleaved LDPC code and any additional processing is applied as needed or appropriate. The processed data is then transmitted over a communication network  130 . The communication network  130  may be embodied, for example, as any combination of wired and/or wireless communication devices. A receiver  150  receives a signal from the network  130  and processes the signal, including decoding the signal using an integrated-interleaved LDPC decoder  400 , as discussed further below in conjunction with  FIG. 4 . Typically, a communication network  130  is noisy and the signal received by the receiver  150  is typically corrupted by noise. 
     In one or more exemplary embodiments, an integrated-interleaved LDPC code is used to compensate for format inefficiencies (e.g., due to a short block length and/or to reduce hardware costs in designing codes of a relatively long block length). In further embodiments, an integrated-interleaved LDPC code is used in another application besides the exemplary example shown in  FIG. 1 . 
     Aspects of the present invention provide a particular mapping or coding associated with integrated-interleaved LDPC coding. In one or more exemplary embodiments, a second level has a single component codeword and in other embodiments the second level has two or more codewords. 
       FIG. 2  is a block diagram of an exemplary two-level integrated-interleaved LDPC encoder  200  incorporating aspects of the present invention, for the case where m=4 and v=1. Generally, the exemplary integrated-interleaved LDPC encoder  200  of  FIG. 2  aligns input messages a 0 , a 1 , a 2 , a 3 , and then linearly combines the input messages a 0 , a 1 , a 2 , a 3 , for the nested-layer encoding. As discussed hereinafter, the first step systematically encodes the messages a 1 , a 2 , . . . , a m-1 , with respect to H 0 , and consequently yields component codewords c 1 , c 2 , . . . , c m-1 , respectively. 
     Thus, as shown in  FIG. 2 , the exemplary integrated-interleaved LDPC encoder  200  comprises systematic encoders  240 - 1  through  240 - 3  that are configured to receive and encode input data a 1 , a 2 , a 3 , respectively, using submatrix H 0 , as defined by Eq. (2). First-level codewords c 1 , c 2 , c 3 , are generated by systematic encoders  240 - 1  through  240 - 3 , respectively. 
     To obtain the exemplary second-level codeword c 0 *, truncated input data a 1 , a 2 , a 3 , is added to a delayed version of input data a 0  generated using delay element  210 . Denote by a′ i , the truncated message of a i , a′ 1 =[a i,0 , a i,1 , . . . , a i,k     l     −1 ]. The original input messages a 0 , a 1 , a 2 , a 3  have a length k 0  and the truncated messages a′ 1 , a′ 2 , a′ 3  have a length k 1  (k 0 &gt;k 1 ). 
     As shown in  FIG. 2 , the left-aligned summation a 0 +Σ i=1   m-1 a′ i  (using delay element  210  for alignment and adder  220  for summation) is selected by multiplexer  225  and systematically encoded at stage  230  with respect to H 1  to yield a nested codeword  c . 
     As shown in  FIG. 2 , adder  250  is configured to receive the first-level codewords c 1 , c 2 , c 3 , as well as the nested codeword e to perform the following operation to generate the exemplary second-level codeword c 0 *: 
     
       
         
           
             
               
                 
                   
                     
                       c 
                       0 
                       * 
                     
                     ⁢ 
                     ⁢ 
                     
                       c 
                       _ 
                     
                   
                   - 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       
                         m 
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       c 
                       i 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     In the exemplary embodiment of  FIG. 2 , where v is equal to 1, the second level has a single component codeword. In cases where v is greater than 1, the second level has a plurality of component codewords. 
     It can be verified that c 0 *εC 0 , and furthermore, c 0 *+Σ i=1   m-1 c i =cεC 1 . 
       FIG. 3  is a flowchart illustrating an embodiment of an exemplary encoding process  300  for two level integrated-interleaved LDPC encoding, where m=4 and v=1. As shown in  FIG. 3 , the exemplary encoding process  300  initially obtains input messages a 0 , a 1 , a 2 , a 3  during step  310 . Thereafter, first level codewords c 1 , c 2 , c 3  are generated during step  320  by performing systematic encoding with respect to H 0 . 
     The truncated version of input message a 0  is then delayed during step  330  using delay element  210  to align the truncated input message a 0  with input messages a 1 , a 2 , a 3 . Adder  220  then performs a left-aligned summation a 0 +Σ i=1   m-1 a′ i  during step  340 . The sum generated by adder  220  is then systematically encoded with respect to H 1  during step  350  to generate a nested codeword  c . 
     Finally, adder  250  receives the first-level codewords c 1 , c 2 , c 3 , as well as the nested codeword  c  during step  360  to generate the exemplary second-level codeword c 0 *, as follows: 
                 c   0   *     ⁢   ⁢     c   _       -       ∑     i   =   1       m   -   1       ⁢           ⁢       c   i     .             
Integrated-Interleaved LDPC Decoding Scheme
 
       FIG. 4  is a flowchart illustrating an embodiment of an exemplary decoding process  400  for two level integrated-interleaved LDPC decoding, where m=4 and v=1. As shown in  FIG. 4 , the exemplary decoding process  400  initially receives a channel word y=[y 0 , y 1 , . . . , y m-1 ] during step  410 . The exemplary decoding process  400  applies a min-sum decoding to each component word y i , i=0,1, . . . , m−1 during step  420 . If it is determined during step  430  that each component word is decoded successfully, then the corrected codeword is returned during step  440 . If it is determined during step  430  that two or more component words incur decoding failure, then a decoding failure is declared during step  450 . If it is determined during step  430  that one component word incurs a decoding failure, say, y j , then all other passing decoded codewords are added to the failed codeword during step  460 , such that y=y j +Σ i≠j c i  and then  y  is decoded with respect to H 1  during step  470 . If successfully decoding to a codeword c, then declare c j =c−Σ i≠j c i  during step  480 . 
     While aspects of the present invention have been illustrated using integrated-interleaved LDPC encoding and decoding for v equal to 1, the present invention can be extended to additional values of v, as would be apparent to a person of ordinary skill in the art. In addition, while aspects of the present invention have been illustrated using two-level integrated-interleaved LDPC encoding and decoding, the present invention can be extended to higher-level integrated-interleaved LDPC encoding and decoding, as would be apparent to a person of ordinary skill in the art. 
     Process, System and Article of Manufacture Details 
     While a number of flow charts herein describe an exemplary sequence of steps, it is also an embodiment of the present invention that the sequence may be varied. Various permutations of the algorithm are contemplated as alternate embodiments of the invention. While exemplary embodiments of the present invention have been described with respect to processing steps in a software program, as would be apparent to one skilled in the art, various functions may be implemented in the digital domain as processing steps in a software program, in hardware by circuit elements or state machines, or in combination of both software and hardware. Such software may be employed in, for example, a digital signal processor, application specific integrated circuit, micro-controller, or general-purpose computer. Such hardware and software may be embodied within circuits implemented within an integrated circuit. 
     Thus, the functions of the present invention can be embodied in the form of methods and apparatuses for practicing those methods. One or more aspects of the present invention can be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a device that operates analogously to specific logic circuits. The invention can also be implemented in one or more of an integrated circuit, a digital signal processor, a microprocessor, and a micro-controller. 
     As is known in the art, the methods and apparatus discussed herein may be distributed as an article of manufacture that itself comprises a computer readable medium having computer readable code means embodied thereon. The computer readable program code means is operable, in conjunction with a computer system, to carry out all or some of the steps to perform the methods or create the apparatuses discussed herein. The computer readable medium may be a tangible recordable medium (e.g., floppy disks, hard drives, compact disks, memory cards, semiconductor devices, chips, application specific integrated circuits (ASICs)) or may be a transmission medium (e.g., a network comprising fiber-optics, the world-wide web, cables, or a wireless channel using time-division multiple access, code-division multiple access, or other radio-frequency channel). Any medium known or developed that can store information suitable for use with a computer system may be used. The computer-readable code means is any mechanism for allowing a computer to read instructions and data, such as magnetic variations on a magnetic media or height variations on the surface of a compact disk. 
     The computer systems and servers described herein may each contain a memory that will configure associated processors to implement the methods, steps, and functions disclosed herein. The memories could be distributed or local and the processors could be distributed or singular. The memories could be implemented as an electrical, magnetic or optical memory, or any combination of these or other types of storage devices. Moreover, the term “memory” should be construed broadly enough to encompass any information able to be read from or written to an address in the addressable space accessed by an associated processor. With this definition, information on a network is still within a memory because the associated processor can retrieve the information from the network. 
     It is to be understood that the embodiments and variations shown and described herein are merely illustrative of the principles of this invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention.