Abstract:
A method and apparatus for encoding data and for decoding data using LDPC (low density parity check) codes includes providing a mother LDPC matrix of a particular size. A data payload of a smaller size is encoded by shortening the mother matrix to a smaller daughter matrix corresponding in size to the data payload and using the smaller daughter matrix for the encoding. The portions of the mother matrix to be removed in the shortening are derived from a control signal. The encoded data is transmitted with the control signal so that the receiver can derive the portions of the mother matrix to be removed to obtain the daughter matrix. At the receiver, a mother matrix is shortened to a daughter matrix and is then used to decode the data. The data at the encoder may be further reduced by puncturing to remove selected information bits and selected parity bits. The decoder inserts the selected information bits and parity bits when decoding the data.

Description:
BACKGROUND 
     Field 
     The present method and system relates generally to a digital communication system and more particularly to the use of error correcting codes in digital communications systems, and particularly relates to the use of LDPC (low density parity check) codes in digital communications systems. Examples of such systems include digital television broadcast systems, cellular telephone systems and the like. 
     Description of the Related Art 
     Like all linear block codes, an LDPC (low density parity check) code can be described in terms of a matrix. In the case of an LDPC code the matrix contains a first portion consisting of information bits and a second portion containing parity bits, the matrix commonly being referred to as an H-matrix, or a parity check matrix. The LDPC code gets its name from the H-matrix which contains relatively few 1&#39;s in comparison to the number of 0&#39;s. 
     Many modern communications systems require the use of error correction codes that can accommodate different code rates and different lengths of information bits. It is well known that longer code lengths improve error correcting performance, while shorter code lengths are characterized by reduced processing delays. Likewise it is known that increasing code rates improves the data rate and bandwidth efficiency, while reducing code rates increases information robustness in noisy channels. However, designing separate error correction codes for each different code length and code rate that may be used in a particular communications system is a very complicated process and often not practical. 
     It would therefore be highly desirable to provide a novel error correction system using error correction codes capable of adapting to different information lengths and different code rates. Such a system would be designed with the goal of providing performance that is equal or close to the performance of systems using separately designed codes and would inherently be of low complexity since it would obviate the need to design a separate code for each condition and would employ encoder and decoder hardware that can be reused in different situations without extra cost. 
     SUMMARY 
     The present invention achieves these and other objects by specially modifying a first LDPC code H matrix, referred to a “mother code,” to become a smaller size LDPC code H matrix, referred to as a daughter code, and using the daughter code to encode and decode the information bits of transmitted and received digital signals. Another aspect of the invention employs code puncturing to improve code error correcting performance. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram showing an embodiment of an encoder according to the present invention; 
         FIG. 2  is a block diagram showing an embodiment of a decoder according to the present invention; and; 
         FIGS. 3 a , 3 b , 4 a , 4 b , 5 a , and 5 b    are matrix diagrams that illustrate an LDPC H matrix as used by the encoder and decoder of  FIGS. 1 and 2 . 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a block diagram showing an embodiment of an encoder  10  according to a certain embodiment of the present invention. The encoder  10  may be provided in a transmitter of a digital communication system, for example. The encoder  10  comprises a shortening and puncturing sets allocator  12  which largely controls the operation of the encoder  10 . The allocator  12  includes four outputs; a first output  14  connected to the input of a mother LDPC (low density parity check) code shortening unit  16 , a second output  18  connected to an information bits puncturing unit  20 , a third output  22  connected to a parity bits puncturing unit  24 , and a fourth output  26  connected to a combiner  28 . The allocator  12  also includes an input  30  for receiving a control signal reflecting a target SNR (signal to noise ratio) for the transmitted signal and the payload length of the transmitted information bits. The control signal on the control signal input  30  may be generated by another piece of equipment or may be manually inserted by the user on the encoder  10 . The allocator  12 , in response to the control signal supplied on the control signal input  30 , derives and provides a first message on the first output  14  defining an information shortening set, a second message on the second output  18  defining an information puncturing set and a third message on the third output  22  defining a parity puncturing set. The allocator  12  also provides the control signal at the fourth output  26  for application to the combiner  28 . 
     The purpose of the information shortening set provided on the output  14  of the allocator  12  is to shorten as necessary the mother LDPC H matrix stored in the code shortening unit  16  to match the length of the data payload supplied over an input  32  to a daughter LDPC code encoder  34 . The information shortening set in certain embodiments identifies portions of the mother matrix to be removed to obtain the daughter matrix. Taking for example the simple case where the payload data is 800 bits and the mother LDPC code H matrix is 1000 bits, the information shortening set would instruct the shortening unit  16  to shorten the mother LDPC code H matrix by 200 bits and supply the resulting shortened daughter LDPC code H matrix for storage in the encoder  34 . The daughter LDPC code matrix thus corresponds to the size of the data payload to be encoded and the daughter matrix may be used to encode the payload data for transmission in a digital communication system, for example. 
     More realistic parameters for the operation just described above are shown in  FIGS. 3 a  and 3 b   .  FIGS. 3 a  and 3 b    illustrate a practical mother LDPC code H matrix  80  comprising an information bits portion  82  and a parity bits portion  84 . Each value in the information bits portion  82  of the chart  80  defines a unique smaller matrix of 1&#39;s and 0&#39;s characterized by a quasi-cyclic variation from one small matrix to the next. Each “0” value in the parity bits portion  84  of the chart  80  defines a smaller matrix of 1&#39;s and 0&#39;s characterized in that it consists of a single diagonal through the matrix. Although the H matrix  80  illustrated in  FIG. 3 a  and 3 b    is relatively complex, it is treated similar to the simple example given above. Thus, the mother LDPC code H matrix  80  illustrated in  FIG. 3 a  and 3 b    is shortened by reducing the number of bits comprising the matrix to match the number of bits in the data payload. Shortening is achieved in this example by dropping the bits in each column of the mother H matrix  80  identified by an “S” in the third row  86  of the matrix  80  (which corresponds to columns 2, 3, 7, 15, 21 and 27 in the illustrated example). The information shortening set on the output  14  as derived by the allocator  12 , the first message, therefore comprises the set {2, 3, 7, 15, 21, 27}, which identifies the columns to be removed. The allocator  12  also supplies the control signal reflecting the information on the input  30  to the output  26  for application to the combiner  28  for transmission to the decoder, which will be described in more detail hereinafter. 
     The illustrated example shows removal of columns to achieve shortening of the mother matrix. It is possible that other portions of the matrix may be removed for shortening, such as rows, a combination of columns and rows, or other arrangements or patterns for shortening to form the daughter matrix. 
     The shortened daughter LDPC H matrix is supplied from the code shortening unit  16  to the encoder  34  where the shortened matrix is used to process the input data payload, for example to provide encoded data. Referring back to the simple example where both the data payload and shortened LDPC code H matrix are 800 bits, the encoder  34  will output  800  information bits on an output  36  and, for example, 1000 parity bits on an output  38 . The parity bits on the output  38  are supplied to the input of the parity bits puncturing unit  24  and the information bits on the output  36  are supplied to the information bits puncturing unit  20 . 
     Referring to  FIGS. 4 a  and 4 b   , which illustrates the same mother LDPC code H matrix  80  as  FIG. 3 a  and 3 b   , in response to the second message comprising the information puncturing set {1, 4, 5}, identified by the letter “P” in row 88 at the top of the respective columns in the chart  80 , on the output  18  of the allocator  12 , the puncturing unit  20  will puncture the information bits supplied on the output  36  of the encoder  34  by dropping columns 1, 4, and 5 from the H matrix. In the case of the simple example, if 100 information bits are thus punctured from the 800 information bits provided, 700 punctured information bits are supplied from the information bits puncturing unit  20  to the combiner  28 . 
     With reference now to  FIGS. 5 a  and 5 b   , which also illustrates the same mother LDPC code H matrix  80  as shown in  FIGS. 3 a  and 3 b   , in response to the third message comprising the parity puncturing set {1, 4, 5, 13, 18}, identified by the letter “P” in row 90 at the top of the respective columns in the parity portion of the chart  80 , on the output  22  of the allocator  12 , the puncturing unit  24  will puncture the parity bits supplied on the output  38  of the encoder  34  by dropping (or removing) columns 1, 4, 5, 13 and 18 from the H matrix. The person of skill in this art understands how to select portions of the matrix for puncturing. In the case of the simple example, if 1000 parity bits are supplied on the output  38  and 300 bits are punctured by the puncturing unit  24 , 700 parity bits are supplied by the parity bits puncturing unit  24  to the combiner  28 . 
     The illustrated example shows removal of columns to achieve puncturing of the matrix. It is possible that other portions of the matrix may be removed for puncturing, such as rows, combinations of rows and columns, or other arrangements or patterns for forming the punctured matrix. 
     Referring back to  FIG. 1 , the allocator  12  also supplies the control signal on the output  26 , from which the first, second and third messages are derived, for application to the combiner  28 . The combiner  28 , which may comprise a conventional multiplexer, combines the (700) punctured information bits from the information bits puncturing unit  20 , the (700) punctured parity bits from the parity bits puncturing unit  24  and the control signal from of the allocator  12 . The combined signal is applied to a modulator  40  and other appropriate transmission equipment for transmission to the decoder, such as a decoder at a receiver, for example. 
     It should be noted that in operation the encoder has adapted itself to encode a shorter payload than the mother LDPC code H matrix is configured to handle and has punctured (performed a data puncturing process on) both the shortened information bits as well as the parity bits, thereby improving bandwidth efficiency and improving robustness of the transmitted signal. 
       FIG. 2  is a block diagram showing an embodiment of a decoder  50  according to the present invention. The decoder  50  may be provided in a receiver of a digital communication system, for example. The decoder  50 , which may be implemented, for example, in the form of a field programmable gate array (FPGA), comprises a receiving unit  52  for receiving the signal transmitted from encoder  10 . Other implementations are of course possible within the scope of the invention. The receiving unit  52  comprises a tuner, a demodulator and other receiving circuits for providing a digital signal on an output  54  representing the bits provided in the signal transmitted from the encoder  10 . Continuing with the previously used example, 1400 bits are therefore supplied from the receiving unit  52  to a splitter  56  over the output  54 . 
     It will be recalled that the transmitted signal included a control signal (representing a target SNR for the transmitted signal and the payload length of the transmitted information bits) from which the information shortening set (the first message), the information puncturing set (the second message) and the parity puncturing set (the third message) are obtained by an allocator. The splitter  56  extracts the control signal from the signal supplied on the output  54  and supplies it to a shortening and puncturing allocator  58 . The splitter  56  also supplies a first portion of the bits on the output  54  containing the punctured information bits (700 bits in the example) to a first depuncturing unit  60  and supplies a second portion of the bits on the output  54  containing the parity bits (also 700 bits in the example) to a second depuncturing unit  62 . The allocator  58  derives the information shortening set (the first message), the information puncturing set (the second message) and the parity puncturing set (the third message) from the received control signal and supplies them on outputs  68 ,  64  and  66 , respectively. The allocator  58  is operationally identical to the allocator  12  at the encoder, so that the same information shortening set, information puncturing set and parity puncturing set are derived from the same control signal (that includes the SNR and payload length, in the illustrated example). The depuncturing units  60  and  62  are controlled by the second and third messages representing the information and parity puncturing sets supplied by the allocator  58  to the depuncturing units  60  and  62  on the respective outputs  64  and  66 . The third message representing the information shortening set is supplied by the allocator  58  over the output  68  to a shortening LDPC mother code H matrix unit  70 . The output of the shortening LDPC mother code H matrix unit  70  comprises a shortened H matrix supplied over a line  72  for storage in a memory of a daughter LDPC code decoder  74  which provides the recovered payload data on a decoder output  76 . The mother code matrix is shortened to provide the smaller daughter code matrix, the daughter code matrix corresponding in size to the received data payload so that the data can be decoded using the daughter matrix. 
     It will be understood that much of the operation of the decoder  50  is reverse that of the operation of the encoder  10 . Thus, with reference again to the simplified example, 700 punctured bits of the received 1400 bits are depunctured by the first depuncturing unit  60  so that 800 expanded bits are provided thereby to the decoder  74 . The depuncturing operation performed by the depuncturing unit  60  adds a number of 0&#39;s (100 in the case of the simplified example) in the correct locations as defined by the second message corresponding to the information puncturing set supplied on the output  64  of the allocator  58 . A similar operation is performed by the depuncturing unit  62  which expands the 700 punctured parity bits supplied by the splitter  56  to 1000 expanded parity bits with 0&#39;s inserted in the correct locations as defined by the third message corresponding to the parity puncturing set supplied on the output  66  of the allocator  58 . 
     The 800 expanded information bits and 1000 expanded parity bits are supplied by the depuncturing units  60  and  62  to the daughter LDPC code decoder  74 . The decoder  74  comprises an H matrix corresponding in size to the supplied 800 expanded information bits (i.e. 800 bits) which is responsive to the expanded information bits together with the 1000 expanded parity bits to recover 800 error corrected payload data bits on the output  76 . Advantageously, the H matrix used in the decoder  74  is derived from the H matrix stored in the shortening LDPC mother code H matrix unit  70 . In particular, the H matrix stored in the matrix unit  70  is shortened by the matrix unit  70  in response to the first message corresponding to the information shortening set supplied on the output  68  of the allocator  58  from 1000 bits to 800 bits (matching the 800 expanded information bits in size) and supplied over the output  72  for storage in and use by the decoder  74 . 
     Of course, both the encoder portion and the decoder portion may be shortened to accommodate data payloads of different sizes by shortening the mother code matrix as needed to provide daughter code matrices of corresponding sizes. In this way the operation of the decoder  50  is compatible with different length LDPC codes by appropriately varying the first message corresponding to the information shortening set supplied to the shortening LDPC mother code H matrix unit  70 . 
     As in the case of the encoder  10 , more realistic parameters for the operation of the decoder  50  are shown in  FIGS. 3 a -5 b    which were previously described in connection with the operation of the encoder and will therefore not be described in detail again. Thus, it will be recalled that  FIGS. 3 a  and 3 b    illustrate a practical mother LDPC code H matrix  80  used by the matrix unit  70  to create the daughter LDPC code H matrix contained in the decoder  74 ,  FIGS. 4 a  and 4 b    illustrate the use of the information puncturing set by the first depuncturing unit  60  to form the expanded information bits and  FIGS. 5 a  and 5 b    illustrate the use of the parity puncturing set by the second depuncturing unit  62  to form the expanded parity bits. 
     Thus, there is shown and described a certain embodiment of a method and system for modifying the size of an encoding and decoding matrix to correspond to different sizes of data payloads. Other embodiments for modifying an encoding and/or decoding means and method to accommodate different sizes or characteristics of data payloads are within the scope of the present invention. 
     There is also shown and described a certain embodiment of a method and system for reducing data by puncturing both the information bits and the parity bits and for recovering the data by depuncturing the information bits and the parity bits. Other embodiments of a data reducing and data recovering means and method are within the scope of the present invention. 
     Although other modifications and changes may be suggested by those skilled in the art, it is the intention of the inventors to embody within the patent warranted hereon all changes and modifications as reasonably and properly come within the scope of their contribution to the art.