Methods and apparatus for compactly describing lifted low-density parity-check (LDPC) codes

• US 10,469,104 B2
• Filed: 06/13/2017
• Issued: 11/05/2019
• Est. Priority Date: 06/14/2016
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Kudekar, Shrinivas, Richardson, Thomas Joseph
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US15/622,019
• Publication Number:
  US 20170359086A1
• Time in Patent Office: 875 Days
• CPC Class Codes: H03M 13/036 Heuristic code construction methods, i.e. code construction or code search based on using trial-and-error
• CPC Class Codes: H03M 13/1148 Structural properties of the code parity-check or generator matrix
• CPC Class Codes: H03M 13/116 Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H03M 13/6306 Error control coding in combination with Automatic Repeat reQuest [ARQ] and diversity transmission, e.g. coding schemes for the multiple transmission of the same information or the transmission of incremental redundancy H03M13/3761, H03M13/3769 and H03M13/635 take precedence
• CPC Class Codes: H03M 13/6393 Rate compatible low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/6505 Memory efficient implementations
• CPC Class Codes: H03M 13/6516 Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0056 Systems characterized by the type of code used H04L1/08 takes precedence
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0058 Block-coded modulation
• CPC Class Codes: H04L 1/0067 Rate matching H04L1/0013 and H04L1/08 take precedence
• CPC Class Codes: H04L 1/0068 by puncturing
• CPC Class Codes: H04L 1/1812 Hybrid protocols; Hybrid automatic repeat request [HARQ]
• CPC Class Codes: H04L 1/1819 with retransmission of additional or different redundancy

Abstract

Certain aspects of the present disclosure generally relate to techniques for compactly describing lifted low-density parity-check (LDPC) codes. A method for wireless communications by a transmitting device is provided. The method generally includes selecting a first lifting size value Z and a first set of lifting values for generating a first lifted LDPC code; generating the first lifted LDPC code by applying the first set of lifting values to interconnect edges in Z copies of a base parity check matrix (PCM) having a first number of base variable nodes and a second number of base check nodes to obtain a first lifted PCM corresponding to the first lifted LDPC code; determining a second set of lifting values for generating second lifted PCM corresponding to a second lifted LDPC code for a second lifting size value based on the first lifted PCM and the first set of lifting values; encoding a set of information bits based on at least one of: the first lifted LDPC code or the second lifted LDPC code to produce a code word; and transmitting the code word.

Claims

1. A method for wirelessly transmitting data in accordance with a radio technology, comprising:

determining a tower of lifting size values including a set of a plurality of powers of an integer multiplied by a set of a plurality of lifting size values, the tower of lifting size values comprising a plurality of families of lifting size values;

determining a first lifting size value from a first family of the plurality of families of lifting size values and a first set of cyclic lifting values for generating a first lifted low density parity check (LDPC) code;

determining the first lifted LDPC code by applying the first set of cyclic lifting values to interconnect edges in a number of copies of a base parity check matrix (PCM) having a first number of columns corresponding to base variable nodes in a base graph and a second number of rows corresponding to base check nodes in the base graph to obtain a first lifted PCM corresponding to the first lifted LDPC code, the number of copies corresponding to the first lifting size value;

storing the first lifted LDPC code;

determining a second set of cyclic lifting values for generating a second lifted PCM corresponding to a second lifted LDPC code for a second lifting size value in the first family by computing a modulo of each of the first set of cyclic lifting values with respect to the second lifting size value;

encoding a set of information bits based on at least one of;

the first lifted LDPC code or the second lifted LDPC code to produce one or more code words; and

transmitting the one or more code words in accordance with the radio technology across a wireless channel.

2. The method of claim 1, wherein each family of lifting size values in the tower of lifting size values comprises the lifting size values corresponding to the set of powers of the integer multiplied by one lifting size value of the set of lifting size values.

3. The method of claim 1, wherein the first lifting size value Z comprises a largest lifting size value in the first family of lifting size values.

4. The method of claim 1, further comprising storing only lifted PCMs corresponding to the largest lifting size value in each of the plurality of families of lifting size values.

5. The method of claim 1, wherein computing the modulo of the second set of cyclic lifting values with respect to the second lifting size value comprises, for each cyclic lifting value in the second set of cyclic lifting values, performing a modulo operation, wherein the second lifting size value is a divisor in the modulo operation and a corresponding cyclic lifting value in the first set of cyclic lifting values is a dividend in the modulo operation.

6. The method of claim 1, wherein the second lifting size value is selected based on a target range of blocklengths of the code word.

7. The method of claim 1, wherein:

the first lifted PCM and the second lifted PCM are associated with a first code rate; and

the method further comprises generating different lifted PCMs based on second base PCM associated with a second code rate.

8. The method of claim 1, wherein the set of lifting size values comprises lifting size values within a defined range of each other.

9. The method of claim 8, wherein the defined range of lifting size values comprises a smallest lifting size value in the set of lifting size values that is within a factor of 2 or 3 of the largest lifting size value in the set of lifting size values.

10. The method of claim 8, wherein each family of lifting size values in the tower of lifting size values corresponds to a power of the set of powers of the integer multiplied by each of the set of lifting size values.

11. The method of claim 10, wherein the first lifting size value comprises a smallest lifting size value in the first family of lifting size values.

12. The method of claim 10, further comprising:

determining a second base PCM and a third fourth set of lifting size values for another family of lifting size values in the tower of lifting size values; and

using the second base PCM and the third fourth set of lifting values for other lifting size values in that family of lifting size values.

13. The method of claim 8, further comprising determining a third set of cyclic lifting values for another lifting size value in another family of lifting size values in the tower of lifting size values corresponding to the power used for the first cluster plus 1.

14. The method of claim 13, wherein determining the third set of cyclic lifting values for an edge in the lifted PCMs for the different set of lifting size values comprises:

multiplying the first set of cyclic lifting values by the integer to obtain a scaled set of cyclic lifting values; and

for each scaled cyclic lifting value;

copying a portion of bits of the scaled cyclic lifting value in the first set of lifting values associated with that edge; and

adding a number of unique bits to the portion of copied bits.

15. The method of claim 14, wherein the first portion of copied bits is equal to the number of the set of powers in the tower and the number of unique bits for each set is equal to the integer.

16. An apparatus for wirelessly transmitting data in accordance with a radio technology, comprising:

means for determining a tower of lifting size values including a set of a plurality of powers of an integer multiplied by a set of a plurality of lifting size values, the tower of lifting size values comprising a plurality of families of lifting size values;

means for determining a first lifting size value from a first family of the plurality of families of lifting size values and a first set of cyclic lifting values for generating a first lifted low density parity check (LDPC) code;

means for determining the first lifted LDPC code by applying the first set of cyclic lifting values to interconnect edges in a number of copies of a base parity check matrix (PCM) having a first number of columns corresponding to base variable nodes in a base graph and a second number of rows corresponding to base check nodes in the base graph to obtain a first lifted PCM corresponding to the first lifted LDPC code, the number of copies corresponding to the first lifting size value;

means for storing the first lifted LDPC code;

means for determining a second set of cyclic lifting values for generating a second lifted PCM corresponding to a second lifted LDPC code for a second lifting size value in the first family by computing a modulo of each of the first set of cyclic lifting values with respect to the second lifting size value;

means for encoding a set of information bits based on at least one of;

the first lifted LDPC code or the second lifted LDPC code to produce one or more code words; and

means for transmitting the one or more code words in accordance with the radio technology across a wireless channel.

17. The apparatus of claim 16, wherein the set of lifting size values comprises lifting size values within a defined range of each other.

18. The apparatus of claim 16, further comprising means for determining a third set of cyclic lifting values for another lifting size value in another family of lifting size values in the tower of lifting size values corresponding to the power used for the first cluster plus 1.

19. The apparatus of claim 16, wherein means for determining the third set of cyclic lifting values comprises:

means for multiplying the first set of cyclic lifting values by the integer to obtain a scaled set of cyclic lifting values; and

for each scaled cyclic lifting value;

means for copying a portion of bits of the scaled cyclic lifting value in the first set of lifting values associated with that edge; and

means for adding a number of unique bits to the portion of copied bits.

20. An apparatus for wirelessly transmitting data in accordance with a radio technology, comprising:

at least one processor coupled with a memory and configured to;

determine a tower of lifting size values including a set of a plurality of powers of an integer multiplied by a set of a plurality of lifting size values, the tower of lifting size values comprising a plurality of families of lifting size values;

determine a first lifting size value from a first family of the plurality of families of lifting size values and a first set of cyclic lifting values for generating a first lifted low density parity check (LDPC) code;

determine the first lifted LDPC code by applying the first set of cyclic lifting values to interconnect edges in a number copies of a base parity check matrix (PCM) having a first number of columns corresponding to base variable nodes in a base graph and a second number of rows corresponding to base check nodes in the base graph to obtain a first lifted PCM corresponding to the first lifted LDPC code, the number of copies corresponding to the first lifting size value;

store the first lifted LDPC code;

determine a second set of cyclic lifting values for generating a second lifted PCM corresponding to a second lifted LDPC code for a second lifting size value in the first family by computing a modulo of each of the first set of cyclic lifting values with respect to the second lifting size value; and

encode a set of information bits based on at least one of;

the first lifted LDPC code or the second lifted LDPC code to produce one or more code words; and

a transmitter configured to transmit the one or more code words in accordance with the radio technology across a wireless channel.

21. A non-transitory computer readable medium having computer executable code stored thereon for wirelessly transmitting data in accordance with a radio technology, comprising:

code for determining a tower of lifting size values including a set of a plurality of powers of an integer multiplied by a set of a plurality of lifting size values, the tower of lifting size values comprising a plurality of families of lifting size values;

code for determining a first lifting size value from a first family of the plurality of families of lifting size values and a first set of cyclic lifting values for generating a first lifted low density parity check (LDPC) code;

code for determining the first lifted LDPC code by applying the first set of cyclic lifting values to interconnect edges in a number of copies of a base parity check matrix (PCM) having a first number of columns corresponding to base variable nodes in a base graph and a second number of rows corresponding to base check nodes in the base graph to obtain a first lifted PCM corresponding to the first lifted LDPC code, the number of copies corresponding to the first lifting size value;

code for storing the first lifted LDPC code;

code for determining a second set of cyclic lifting values for generating a second lifted PCM corresponding to a second lifted LDPC code for a second lifting size value in the first family by computing a modulo of each of the first set of cyclic lifting values with respect to the second lifting size value;

code for encoding a set of information bits based on at least one of;

the first lifted LDPC code or the second lifted LDPC code to produce one or more code words; and

code for transmitting the one or more code words in accordance with the radio technology across a wireless channel.

22. The method of claim 21, wherein selecting the first set of cyclic lifting values for generating the first lifted LDPC code comprises:

selecting a third set of cyclic lifting values for a smallest lifting size value in the first family of lifting values to obtain a third lifted PCM;

lifting the third lifted PCM by lifting size values of 2 until the third lifted PCM is lifted by the first lifting size value.