Abstract:
An apparatus includes a circuit configured to at least one of (i) encode first data to produce encoded data or (ii) decode second data to produce decoded data. The circuit is configured to operate according to a predetermined matrix. Each element of the predetermined matrix labeled with a hyphen corresponds to a zero matrix. Each element of the predetermined matrix labeled with a number corresponds to a respective cyclic-permutation matrix.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This is a continuation of U.S. patent application Ser. No. 13/614,065 (now U.S. Pat. No. 8,489,960), filed on Sep. 13, 2012, which is a continuation U.S. patent application Ser. No. 12/852,817 (now U.S. Pat. No. 8,281,213), filed Aug. 9, 2010, which is a continuation of U.S. patent application Ser. No. 11/481,141 (now U.S. Pat. No. 7,774,675), filed Jul. 5, 2006, which claims the benefit of U.S. Provisional Application No. 60/742,432, filed Dec. 5, 2005. The entire disclosures of the above applications are incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to error control coding, and more specifically to low density parity check codes. 
     BACKGROUND OF THE INVENTION 
     The draft standard of IEEE 802.11n (Enhanced Wireless Consortium, PHY specification, Revision V1.28, Jan. 2, 2006), which is incorporated herein by reference in its entirety, specifies a MIMO (multiple-input multiple-output) OFDM (orthogonal frequency-division multiplexing) system. Referring now to  FIG. 1 , a functional block diagram of an exemplary implementation of an 802.11n transmitter is depicted. The transmitter includes a scrambler  104 , which receives user data to be transmitted. The scrambler  104  scrambles the data to prevent long sequences of zeros or ones, and communicates with an encoder parser  106 . The encoder parser  106  demultiplexes the scrambled bits among a number, N ES , of FEC (forward error correction) encoders  108 . N ES , the number of encoding streams, is two in the example of  FIG. 1 . 
     The FEC encoders  108  encode the data to enable error correction, and may include a binary convolutional encoder followed by a puncturing device, or an LDPC (low density parity check) encoder. Implementing convolutional codes is mandatory, while LDPC codes are optional as a high-performance ECC (error correcting code) technique. When the LDPC codes are used, the number of FEC encoders is one (N ES =1). The FEC encoders  108  communicate with a stream parser  110 , which divides the output of the FEC encoders  108  into blocks that will be sent to different interleaver  112  and mapping  114  devices. The blocks going to a particular interleaver  112  are referred to as a spatial stream. 
     The stream parser  110  communicates with a number, N SS , of interleavers  112 . N SS , the number of spatial streams, is four in the example of  FIG. 1 . The interleavers  112  interleave the bits of each spatial stream by changing order of the bits to prevent long sequences of adjacent noisy bits entering the FEC decoder. Each interleaver communicates with one of N SS  number of QAM (quadrature amplitude modulation) mapping modules  114 . The QAM mapping modules  114  map the sequence of bits in each spatial stream to constellation points (in the complex number plane). The QAM mapping modules  114  optionally communicate with a STBC (space time block coding) module  116 . The STBC module  116  spreads constellation points from N SS  spatial streams into N STS  (where N STS &gt;N SS ) space time streams using a space time block code. 
     The STBC module  116  communicates with a number, N STS −1, of cyclic shift modules  118 , and with a spatial mapping module  120 . N STS , the number of space time streams, is four in the example of  FIG. 1 . The cyclic shift modules  118  insert cyclic shift into blocks in the frequency domain as part of spatial expansion when optional spatial mapping is implemented. The cyclic shift modules  118  communicate with the spatial mapping module  120 . The spatial mapping module  120  maps spatial streams to different transmit chains. This may include: direct mapping each sequence of constellation points to a different transmit chain; spatial expansion, where each vector of constellation points from all sequences is multiplied by a matrix to produce input to the transmit chains; and/or beam forming, where each vector of constellation points from all sequences is multiplied by a matrix of steering vectors to produce input to the transmit chains. 
     The spatial mapping module  120  communicates with a number, N TX , of IFFT (inverse fast Fourier transform) modules  122 . N TX , the number of transmit chains, is four in the example of  FIG. 1 . Each IFFT module  122  converts a block of constellation points into a time domain block. All but one of the IFFT modules  122  communicates with a corresponding cyclic shift insertion module  124 . The one IFFT module  122  that does not communicate with one of the cyclic shift insertion modules  124  communicates with a GI/window module  126 . The cyclic shift insertion modules  124  insert cyclic shift into the time domain blocks, and communicate with GI/window modules  126 . The GI/window modules  126  insert guard intervals and optionally smooth the edges of each symbol to increase spectral decay. The GI/window modules  126  communicate with analog/RF modules  128 , which up convert the complex baseband waveform to an RF signal and transmit. 
     SUMMARY OF THE INVENTION 
     A MIMO transmitter comprises a scrambler; an encoder parser responsive to the scrambler; a forward error correction encoder responsive to the encoder parser, wherein the encoder applies a parity check matrix derived from a base matrix; an interleaver responsive to the forward error correction encoder; a QAM mapping module responsive to the interleaver; an inverse fast Fourier transform module responsive to the QAM mapping module; and an output module responsive to the inverse fast Fourier transform module. 
     A MIMO transmitter comprises a scrambler and a forward error correction encoder responsive to the scrambler, wherein the encoder applies a parity check matrix derived from a base matrix. In other features, the MIMO transmitter further comprises an encoder parser responsive to the scrambler, wherein the forward error correction encoder is responsive to the encoder parser; an interleaver responsive to the forward error correction encoder; a QAM mapping module responsive to the interleaver; an inverse fast Fourier transform module responsive to the QAM mapping module; and an output module responsive to the inverse fast Fourier transform module. 
     A method of encoding data comprises receiving data blocks; deriving a parity check matrix from a base matrix; and encoding each of said data blocks based upon said parity check matrix. A computer program executed by a processor comprises receiving data blocks; deriving a parity check matrix from a base matrix; and encoding each of said data blocks based upon said parity check matrix. 
     A computer program stored for use by a processor for encoding data comprises receiving data blocks; deriving a parity check matrix from a base matrix; and encoding each of said data blocks based upon said parity check matrix. A computer program executed by a processor comprises receiving data blocks; deriving a parity check matrix from a base matrix; and encoding each of said data blocks based upon said parity check matrix. 
     A MIMO transmitter comprises scrambling means for preventing consecutive sequences; encoder parsing means responsive to the scrambling means for demultiplexing scrambled information; forward error correction (FEC) encoding means responsive to the encoder parsing means for applying a parity check matrix derived from a base matrix; interleaving means responsive to the FEC encoding means for preventing sequences of adjacent noisy bits; QAM mapping means responsive to the interleaving means for mapping bits to constellation points; inverse fast Fourier transformation means responsive to the QAM mapping means for converting constellation information to time domain; and output means responsive to the inverse fast Fourier transformation means for outputting time domain information. 
     A low density parity check coding (LDPC) system comprises data generating means for providing data in blocks; LDPC encoding means for encoding each of said blocks based upon a parity check matrix derived from a base matrix. A MIMO transmitter comprises scrambling means for preventing consecutive sequences; and forward error correction (FEC) encoding means responsive to the scrambling means for applying a parity check matrix derived from a base matrix. 
     In other features, the MIMO transmitter further comprises encoder parsing means responsive to the scrambling means for demultiplexing scrambled information; interleaving means responsive to the FEC encoding means for preventing sequences of adjacent noisy bits; QAM mapping means responsive to the interleaving means for mapping bits to constellation points; inverse fast Fourier transformation means responsive to the QAM mapping means for converting constellation information to time domain; and output means responsive to the inverse fast Fourier transformation means for outputting time domain information. 
     In other features, the base matrix referred to above is one of the following: 
     
       
         
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 35 
                 71 
                 56 
                 55  
                 — 
                 — 
                 23 
                 34 
                 — 
                 — 
                 — 
                 71 
                 — 
                  3 
                 — 
                 72 
                 1 
                 0 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
               
               
                  6 
                 48 
                 70 
                 42 
                 30 
                 — 
                 20 
                 — 
                 — 
                 — 
                 58 
                 — 
                 14 
                 — 
                 — 
                 12 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
                 — 
                 — 
               
               
                 13 
                  1 
                 68 
                 59 
                 45 
                 26 
                 — 
                 — 
                 55 
                 — 
                 — 
                 — 
                 20 
                 — 
                 — 
                 20 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
                 — 
               
               
                 74 
                  2 
                 61 
                 30 
                 — 
                 34 
                 — 
                 — 
                 36 
                 — 
                  9 
                 — 
                 50 
                 — 
                 46 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
               
               
                 35 
                 15 
                  4 
                 20 
                 57 
                 — 
                 34 
                 — 
                 — 
                 79 
                 — 
                 — 
                 — 
                 — 
                 30 
                 — 
                 0 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
               
               
                 40 
                 50 
                 49 
                 14 
                 79 
                 — 
                  1 
                 — 
                 — 
                 12 
                 65 
                 — 
                 — 
                 — 
                 20 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
               
               
                 46 
                 78 
                 78 
                 46 
                 — 
                 40 
                 — 
                 80 
                 17 
                 — 
                 — 
                  8 
                 — 
                  6 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
               
               
                 10 
                 22 
                 40 
                 17 
                 — 
                 48 
                 — 
                 38 
                 — 
                 18 
                 — 
                 72 
                 — 
                 54 
                 — 
                 — 
                 1 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
               
               
                   
               
             
          
         
       
     
     
       
         
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 14 
                 10 
                 49 
                 47 
                 23 
                 — 
                 33 
                 — 
                 — 
                 — 
                 — 
                 40 
                 — 
                 1 
                 — 
                 38 
                 1 
                 0 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
               
               
                 47 
                 35 
                 33 
                 53 
                 — 
                 25 
                 — 
                 — 
                 44 
                 — 
                 34 
                 — 
                 16 
                 — 
                 31 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
                 — 
                 — 
               
               
                 25 
                 9 
                 51 
                 12 
                 44 
                 — 
                 7 
                 51 
                 — 
                 51 
                 — 
                 8 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
                 — 
               
               
                 28 
                 38 
                 8 
                 45 
                 — 
                 7 
                 — 
                 — 
                 15 
                 — 
                 10 
                 — 
                 — 
                 2 
                 — 
                 32 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
               
               
                 19 
                 12 
                 43 
                 38 
                 13 
                 — 
                 49 
                 — 
                 — 
                 — 
                 — 
                 — 
                 13 
                 — 
                 45 
                 — 
                 0 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
               
               
                 7 
                 9 
                 46 
                 33 
                 — 
                 48 
                 — 
                 1 
                 — 
                 24 
                 — 
                 13 
                 — 
                 15 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
               
               
                 16 
                 53 
                 32 
                 1 
                 48 
                 — 
                 45 
                 — 
                 19 
                 — 
                 6 
                 — 
                 — 
                 — 
                 — 
                 48 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
               
               
                 15 
                 47 
                 13 
                 51 
                 — 
                 27 
                 — 
                 38 
                 — 
                 47 
                 — 
                 — 
                 6 
                 — 
                 7 
                 — 
                 1 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
               
               
                   
               
             
          
         
       
     
     
       
         
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 25 
                 26 
                 14 
                 — 
                 20 
                 — 
                 2 
                 — 
                 4 
                 — 
                 — 
                 8 
                 — 
                 16 
                 — 
                 18 
                 1 
                 0 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
               
               
                 10 
                 9 
                 15 
                 11 
                 — 
                 0 
                 — 
                 1 
                 — 
                 — 
                 18 
                 — 
                 8 
                 — 
                 10 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
                 — 
                 — 
               
               
                 16 
                 2 
                 20 
                 26 
                 21 
                 — 
                 6 
                 — 
                 1 
                 26 
                 — 
                 7 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
                 — 
               
               
                 10 
                 13 
                 5 
                 0 
                 — 
                 3 
                 — 
                 7 
                 — 
                 — 
                 26 
                 — 
                 — 
                 13 
                 — 
                 16 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
                 — 
               
               
                 23 
                 14 
                 24 
                 — 
                 12 
                 — 
                 19 
                 — 
                 17 
                 — 
                 — 
                 — 
                 20 
                 — 
                 21 
                 — 
                 0 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
                 — 
               
               
                 6 
                 22 
                 9 
                 20 
                 — 
                 25 
                 — 
                 17 
                 — 
                 8 
                 — 
                 14 
                 — 
                 18 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
                 — 
               
               
                 14 
                 23 
                 21 
                 11 
                 20 
                 — 
                 24 
                 — 
                 18 
                 — 
                 19 
                 — 
                 — 
                 — 
                 — 
                 22 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
                 0 
               
               
                 17 
                 11 
                 11 
                 20 
                 — 
                 21 
                 — 
                 26 
                 — 
                 3 
                 — 
                 — 
                 18 
                 — 
                 26 
                 — 
                 1 
                 — 
                 — 
                 — 
                 — 
                 — 
                 — 
                 0 
               
               
                   
               
             
          
         
       
     
     In still other features, the methods described above are implemented by a computer program executed by one or more processors. The computer program can reside on a computer readable medium such as but not limited to memory, non-volatile data storage and/or other suitable tangible storage mediums. 
     Further areas of applicability of the present invention will become apparent from the detailed description provided hereinafter. It should be understood that the detailed description and specific examples, while indicating the preferred embodiment of the invention, are intended for purposes of illustration only and are not intended to limit the scope of the invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention will become more fully understood from the detailed description and the accompanying drawings, wherein: 
         FIG. 1  is a functional block diagram of an exemplary implementation of an 802.11n transmitter; 
         FIG. 2A  is a rate-⅔ base matrix for an LDPC code with block size (n) of 1944; 
         FIG. 2B  is another rate-⅔ base matrix for an LDPC code with n=1944; 
         FIG. 2C  is another rate-⅔ base matrix for an LDPC code with n=1944; 
         FIG. 2D  is another rate-⅔ base matrix for an LDPC code with n=1944; 
         FIG. 2E  is another rate-⅔ base matrix for an LDPC code with n=1944; 
         FIG. 2F  is a rate-⅔ base matrix for an LDPC code with n=1296; 
         FIG. 2G  is another rate-⅔ base matrix for an LDPC code with n=1296; 
         FIG. 2H  is another rate-⅔ base matrix for an LDPC code with n=1296; 
         FIG. 2I  is another rate-⅔ base matrix for an LDPC code with n=1296; 
         FIG. 2J  is another rate-⅔ base matrix for an LDPC code with n=1296; 
         FIG. 2K  is another rate-⅔ base matrix for an LDPC code with n=1296; 
         FIG. 2L  is a rate-⅔ base matrix for an LDPC code with n=648; 
         FIG. 2M  is another rate-⅔ base matrix for an LDPC code with n=648; 
         FIG. 2N  is another rate-⅔ base matrix for an LDPC code with n=648; 
         FIG. 2O  is another rate-⅔ base matrix for an LDPC code with n=648; 
         FIG. 3  is a graphical representation of the division of a matrix into sub-matrices according to the Richardson-Urbanke method; 
         FIG. 4  is a graphical representation of how the codeword c is formed using computed values according to the Richardson-Urbanke method; 
         FIG. 5  is a functional block diagram of an exemplary communications channel; 
         FIG. 6A  is a functional block diagram of a media player; 
         FIG. 6B  is a functional block diagram of a high definition television; 
         FIG. 6C  is a functional block diagram of a vehicle control system; 
         FIG. 6D  is a functional block diagram of a cellular phone; and 
         FIG. 6E  is a functional block diagram of a set top box. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The following description of the preferred embodiments is merely exemplary in nature and is in no way intended to limit the invention, its application, or uses. For purposes of clarity, the same reference numbers will be used in the drawings to identify similar elements. As used herein, the term module refers to an application specific integrated circuit (ASIC), an electronic circuit, a processor (shared, dedicated, or group) and memory that execute one or more software or firmware programs, a combinational logic circuit, and/or other suitable components that provide the described functionality. As used herein, the phrase at least one of A, B, and C should be construed to mean a logical (A or B or C), using a non-exclusive logical or. It should be understood that steps within a method may be executed in different order without altering the principles of the present invention. 
     Low-density parity check (LDPC) codes form a class of error correcting code that approaches the Shannon limit. LDPC codes are linear block codes specified by a sparse parity-check matrix H of size (n−k)×n, where n is the codeword length and k is the number of user bits within the codeword. Codeword block lengths include 648, 1296, and 1944. For each codeword block length, supported code rates include ½, ⅔, ¾, and ⅚. Code rate is determined by the number of user bits contained within every block of transmitted bits, and is equal to k/n. 
     Much of the analysis of LDPC codes is based on their graph representations. For LDPC codes to perform well, cycles of length 4 are usually avoided in their graph representations. A cycle of length 4 in graph representations translates to the following in parity matrix representations: 
                 1       ⋯       1           ⋮                   ⋮           1       …       1             
Eliminating the cycle of length 4 in graph representations is equivalent to forcing the following constraint to parity matrix representations: no two columns/rows can have more than one “1” in common. Codes proposed below ( FIGS. 2A-2O ) meet the above constraint.
 
     Parity check matrices H are generated by expanding a base matrix H b  z times. Expansion operation is defined by the element values of the base matrix H b . Each non-empty base matrix element having value i is replaced by a z×z cyclic-permutation matrix P i . P i  is obtained from the z×z identity matrix by cyclically shifting the columns to the right by i elements. Each vacant entry (denoted by a “−”) in the base matrix is replaced by a z×z zero matrix. 
     Proposed LDPC codes belong to the more general class of quasi-cyclic LDPC codes. Proposed LDPC codes are rate-⅔ codes, with codeword block lengths of 648, 1296, and 1944 bits. The base matrices are of size 8×24 (8 rows, 24 columns). The expansion factors are z=27 for n=648 (24*27); z=54 for 1296 (24*54); and z=81 for n=1944 (24*81). The total weight (number of non-zero entries in the matrix) of each base matrix is 88. The row weight (number of non-zero entries in a row) is 11 for all rows. 
     Referring now to  FIG. 2A , a rate-⅔ base matrix for an LDPC code with block size (n) of 1944 is presented. Matrix elements denoted by “−” are empty, and therefore expanded using a zero matrix.  FIG. 2B  presents another rate-⅔ base matrix for an LDPC code with n=1944.  FIG. 2C  presents another rate-⅔ base matrix for an LDPC code with n=1944.  FIG. 2D  presents another rate-⅔ base matrix for an LDPC code with n=1944.  FIG. 2E  presents another rate-⅔ base matrix for an LDPC code with n=1944. 
       FIG. 2F  presents a rate-⅔ base matrix for an LDPC code with n=1296.  FIG. 2G  presents another rate-⅔ base matrix for an LDPC code with n=1296.  FIG. 2H  presents another rate-⅔ base matrix for an LDPC code with n=1296.  FIG. 2I  presents another rate-⅔ base matrix for an LDPC code with n=1296.  FIG. 2J  presents another rate-⅔ base matrix for an LDPC code with n=1296.  FIG. 2K  presents another rate-⅔ base matrix for an LDPC code with n=1296. 
       FIG. 2L  presents a rate-⅔ base matrix for an LDPC code with n=648.  FIG. 2M  presents another rate-⅔ base matrix for an LDPC code with n=648.  FIG. 2N  presents another rate-⅔base matrix for an LDPC code with n=648.  FIG. 2O  presents another rate-⅔ base matrix for an LDPC code with n=648. 
     An encoder for LDPC codes is systematic, which means that it encodes an information block of size k, u=[u 0 , u 1 , . . . , u k-1 ], into a codeword c of size n, c=[u 0 , u 1 , . . . , u k-1 , p 0 , p 1 , . . . , p n-k-1 ], by adding n−k parity bits. Parity bits are obtained such that H·c T =0. In general, encoding a linear block code is done via the generator matrix G, i.e., c=u·G, where G satisfies GH T =0. 
     The generator matrix G is obtained using the following derivation: 
     
       
         
           
             
               H 
               · 
               
                 c 
                 T 
               
             
             = 
             
               
                 
                   [ 
                   
                     
                       H 
                       1 
                     
                     | 
                     
                       H 
                       2 
                     
                   
                   ] 
                 
                 · 
                 
                   [ 
                   
                     
                       
                         
                           u 
                           T 
                         
                       
                     
                     
                       
                         
                           p 
                           T 
                         
                       
                     
                   
                   ] 
                 
               
               = 
               
                 
                   
                     0 
                     ⁢ 
                     
                       
 
                     
                     ⇓ 
                     
                       
 
                     
                     ⁢ 
                     
                       H 
                       1 
                     
                   
                   · 
                   
                     u 
                     T 
                   
                 
                 = 
                 
                   
                     
                       H 
                       2 
                     
                     · 
                     
                       
                         p 
                         T 
                       
                       ⁢ 
                       
                         
 
                       
                       ⇓ 
                       
                         
 
                       
                       ⁢ 
                       c 
                     
                   
                   = 
                   
                     
                       [ 
                       up 
                       ] 
                     
                     = 
                     
                       u 
                       · 
                       
                         
                           [ 
                           
                             
                               I 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     H 
                                     2 
                                     
                                       - 
                                       1 
                                     
                                   
                                   · 
                                   
                                     H 
                                     1 
                                   
                                 
                                 ) 
                               
                             
                             T 
                           
                           ] 
                         
                         
                           ︸ 
                           G 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     Encoding methods having reduced complexity are available for LDPC codes having the structure of the matrices proposed in  FIGS. 2A-2O . One such example is block based backward-substitution. Another is Richardson-Urbanke encoding. See T. Richardson and R. Urbanke, “Efficient encoding of low-density parity-check codes,” IEEE Trans. on Inform. Theory, Vol. 47, February 2001, which is incorporated herein by reference in its entirety. 
     In Richardson-Urbanke encoding, the parity check matrix is divided into 6 sub-matrices.  FIG. 3  is a graphical representation of the division of a matrix into sub-matrices according to the Richardson-Urbanke method. The shift value at the middle of B is 0 and the top value of B and D have the same values. The rightmost shift value of E is 0 and the other sub-matrices are zero matrices. For example, B T =[P 0 0 . . . 0 1 0 . . . 0 0 0], D=[P], and E=[0 0 . . . 0 0 1]. Therefore, ET −1 =[1 1 . . . 1 1 1].  FIG. 4  is a graphical representation of how the codeword c is formed using computed values of p 1  and p 2 . Computation proceeds as follows: 
     Step 1: Compute Au T  and Cu T    
     Step 2: Compute ET −1 (Au T ) 
     Step 3: Compute p 1   T  by p 1   T =ET −1 (Au T )+Cu T    
     Step 4: Compute p 2   T  by Tp 2   T =Au T +Bp 1   T    
     For decoding, the most common decoding algorithm is the standard belief propagation algorithm (BPA), or sum-product algorithm (SPA), which passes messages on the bipartite (Tanner) graph associated with the parity check matrix. See D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, Vol. 45, March 1999, which is incorporated herein by reference in its entirety. For the class of quasi-cyclic codes, the “turbo decoding message-passing” algorithm is available. See M. Mansour and N. Shanbhag, “High-Throughput LDPC Decoders,” IEEE Trans. On VLSI Systems, Vol. 11, No. 6, December 2003, which is incorporated herein by reference in its entirety. Also available is the “layered belief propagation” algorithm. See D. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC Codes,” IEEE Workshop on Signal Proc. Systems (SIPS), October 2004, which is incorporated herein by reference in its entirety. 
     LDPC codes can also be viewed as equivalent General-Repeat-Accumulate (GRA) codes, which support turbo-like decoding. See K. M. Chugg, P. Thiennviboon, G. D. Dimou, P. Gray, and J. Melzer, “A New Class of Turbo-like Codes with Universally Good Performance and High-Speed Decoding,” Proc. IEEE Military Comm. Conf. 2005, which is incorporated herein by reference in its entirety. 
     In standard belief propagation, messages are exchanged between variable nodes (associated with information bits) and check nodes (associated with parity check bits) in an iterative fashion. Each iteration consists of 2 phases of computations: in phase 1, updates of all variable nodes are done by sending messages to neighboring check nodes; in phase 2, updates of all check nodes are done by sending messages to neighboring bit nodes. This process continues until a codeword is found or the maximum number of iterations is reached. 
     Referring now to  FIG. 5 , a first device  200 - 1  communicates with a second device  200 - 2  over a communications channel  202 . The communications channel  202  may be, for example, an Ethernet network, a wireless local area network, a bus for a hard drive, etc. The communications channel  202  may represent a storage media (such as a hard drive), in which case there would be no second device  200 - 2 . Instead, the communications channel would store data from the first device  200 - 1  (e.g., the read/write head and channel of a hard drive) and later provide the data to the first device  200 - 1 . 
     The first device  200 - 1  includes components  204 - 1  that output signals to an LDPC (low density parity check) encoder  206 - 1  and that receive signals from an LDPC decoder  208 - 1 . Likewise, the second device  200 - 2  includes components  204 - 2  that output signals to an LDPC encoder  206 - 2  and that receive signals from an LDPC decoder  208 - 2 . The components  204 - 1  of the first device  200 - 1  may be similar to or different than the components  204 - 2  of the second device  200 - 2 . The LDPC encoders  216  encode data before the encoded data is output onto the communications channel  202 . The encoding process adds redundant information to the data stream that may allow the LDPC decoders  218  to possibly detect and correct errors in the received data. In the case where the communications channel  202  is a compact disc, the first device  200 - 1  (such as a CD recording device) would not need an LDPC decoder  208 - 1  and the second device  200 - 2  (such as a CD player) would not need an LDPC encoder  206 - 2 . The LDPC matrices proposed in  FIGS. 2A-2O  may be used in the LDPC encoders  206  and decoders  208 . 
     Referring now to  FIGS. 6A-6E , various exemplary implementations of the device are shown. Referring now to  FIG. 6A , the device can be implemented in a communications channel of a media player  500 . In some implementations, the media player  500  includes a display  507  and/or a user input  508  such as a keypad, touchpad and the like. In some implementations, the media player  500  may employ a graphical user interface (GUI) that typically employs menus, drop down menus, icons and/or a point-and-click interface via the display  507  and/or user input  508 . The media player  500  further includes an audio output  509  such as a speaker and/or audio output jack. The signal processing and/or control circuits  504  and/or other circuits (not shown) of the media player  500  may process data, perform coding and/or encryption, perform calculations, format data and/or perform any other media player function. 
     The media player  500  may communicate with mass data storage  510  that stores data such as compressed audio and/or video content in a nonvolatile manner. In some implementations, the compressed audio files include files that are compliant with MP3 format or other suitable compressed audio and/or video formats. The mass data storage may include optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The media player  500  may be connected to memory  514  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The media player  500  also may support connections with a WLAN via a WLAN network interface  516 . Still other implementations in addition to those described above are contemplated. 
     Referring now to  FIG. 6B , the device can be implemented in a communications channel of a high definition television (HDTV)  420 . The HDTV  420  receives HDTV input signals in either a wired or wireless format and generates HDTV output signals for a display  426 . In some implementations, signal processing circuit and/or control circuit  422  and/or other circuits (not shown) of the HDTV  420  may process data, perform coding and/or encryption, perform calculations, format data and/or perform any other type of HDTV processing that may be required. 
     The HDTV  420  may communicate with mass data storage  427  that stores data in a nonvolatile manner such as optical and/or magnetic storage devices. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The HDTV  420  may be connected to memory  428  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The HDTV  420  also may support connections with a WLAN via a WLAN network interface  429 . 
     Referring now to  FIG. 6C , the device may implement and/or be implemented in a communications channel of a control system of a vehicle  430 . In some implementations, the device implement a powertrain control system  432  that receives inputs from one or more sensors such as temperature sensors, pressure sensors, rotational sensors, airflow sensors and/or any other suitable sensors and/or that generates one or more output control signals such as engine operating parameters, transmission operating parameters, and/or other control signals. 
     The device may also be implemented in other control systems  440  of the vehicle  430 . The control system  440  may likewise receive signals from input sensors  442  and/or output control signals to one or more output devices  444 . In some implementations, the control system  440  may be part of an anti-lock braking system (ABS), a navigation system, a telematics system, a vehicle telematics system, a lane departure system, an adaptive cruise control system, a vehicle entertainment system such as a stereo, DVD, compact disc and the like. Still other implementations are contemplated. 
     The powertrain control system  432  may communicate with mass data storage  446  that stores data in a nonvolatile manner. The mass data storage  446  may include optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The powertrain control system  432  may be connected to memory  447  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The powertrain control system  432  also may support connections with a WLAN via a WLAN network interface  448 . The control system  440  may also include mass data storage, memory and/or a WLAN interface (all not shown). 
     Referring now to  FIG. 6D , the device can be implemented in a communications channel of a cellular phone  450  that may include a cellular antenna  451 . In some implementations, the cellular phone  450  includes a microphone  456 , an audio output  458  such as a speaker and/or audio output jack, a display  460  and/or an input device  462  such as a keypad, pointing device, voice actuation and/or other input device. The signal processing and/or control circuits  452  and/or other circuits (not shown) in the cellular phone  450  may process data, perform coding and/or encryption, perform calculations, format data and/or perform other cellular phone functions. 
     The cellular phone  450  may communicate with mass data storage  464  that stores data in a nonvolatile manner such as optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The cellular phone  450  may be connected to memory  466  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The cellular phone  450  also may support connections with a WLAN via a WLAN network interface  468 . 
     Referring now to  FIG. 6E , the device can be implemented in a communications channel of a set top box  480 . The set top box  480  receives signals from a source such as a broadband source and outputs standard and/or high definition audio/video signals suitable for a display  488  such as a television and/or monitor and/or other video and/or audio output devices. The signal processing and/or control circuits  484  and/or other circuits (not shown) of the set top box  480  may process data, perform coding and/or encryption, perform calculations, format data and/or perform any other set top box function. 
     The set top box  480  may communicate with mass data storage  490  that stores data in a nonvolatile manner. The mass data storage  490  may include optical and/or magnetic storage devices for example hard disk drives HDD and/or DVDs. The HDD may be a mini HDD that includes one or more platters having a diameter that is smaller than approximately 1.8″. The set top box  480  may be connected to memory  494  such as RAM, ROM, low latency nonvolatile memory such as flash memory and/or other suitable electronic data storage. The set top box  480  also may support connections with a WLAN via a WLAN network interface  496 . 
     Those skilled in the art can now appreciate from the foregoing description that the broad teachings of the present invention can be implemented in a variety of forms. Therefore, while this invention has been described in connection with particular examples thereof, the true scope of the invention should not be so limited since other modifications will become apparent to the skilled practitioner upon a study of the drawings, the specification and the following claims.