LDPC ENCODING AND DECODING OF PACKETS OF VARIABLE SIZES

• US 20080178065A1
• Filed: 01/24/2008
• Published: 07/24/2008
• Est. Priority Date: 01/24/2007
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Richardson, Thomas, Khandekar, Aamod
• Granted Patent: US 8,433,984 B2
• Time in Patent Office: Days
• US Class Current: 714/801
• CPC Class Codes: H03M 13/1137 Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel
• 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/1185 wherein the parity-check matrix comprises a part with a double-diagonal
• CPC Class Codes: H03M 13/1188 wherein in the part with the double-diagonal at least one column has an odd column weight equal or greater than three
• 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/6393 Rate compatible low-density parity check [LDPC] codes
• 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/0007 by modifying the frame length
• CPC Class Codes: H04L 1/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 1/1812 Hybrid protocols; Hybrid automatic repeat request [HARQ]

Abstract

Techniques to support low density parity check (LDPC) encoding and decoding are described. In an aspect, LDPC encoding and decoding of packets of varying sizes may be supported with a set of base parity check matrices of different dimensions and a set of lifting values of different powers of two. A base parity check matrix G of dimension m_B×n_B may be used to encode a packet of k_B=n_B−m_B information bits to obtain a codeword of n_B code bits. This base parity check matrix may be “lifted” by a lifting value of L to obtain a lifted parity check matrix H of dimension L·m_B×L·n_B. The lifted parity check matrix may be used to encode a packet of up to L·k_B information bits to obtain a codeword of L·n_B code bits. A wide range of packet sizes may be supported with the set of base parity check matrices and the set of lifting values.

Claims

1. An apparatus comprising:

at least one processor configured to encode or decode packets of variable sizes based on a set of base parity check matrices of different dimensions and a set of lifting values of different powers of two; and

a memory coupled to the at least one processor and configured to store parameters for the set of base parity check matrices.

2. The apparatus of claim 1, wherein the at least one processor is configured to determine a packet size of a packet to be encoded or decoded, to select a lifting value from the set of lifting values based on the packet size, to select a base parity check matrix from the set of base parity check matrices based on the packet size and the selected lifting value, to generate a lifted parity check matrix based on the selected base parity check matrix and the selected lifting value, and to encode or decode the packet based on the lifted parity check matrix.

3. The apparatus of claim 2, wherein the at least one processor is configured to select the lifting value by computing

L=2┌

log₂(k/k_B,max)┐

,

where k is the packet size, k_B,max is a maximum number of information bits for the set of base parity check matrices, L is the selected lifting value, and “

┌

┐

”

denotes a ceiling operator.

4. The apparatus of claim 2, wherein the at least one processor is configured to select the base parity check matrix by computing

k_B=┌

k/L ┐

,

where k is the packet size, L is the selected lifting value, k_B is a number of information bits for the selected base parity check matrix, and “

┌

┐

”

denotes a ceiling operator.

5. The apparatus of claim 2, wherein the at least one processor is configured to generate the lifted parity check matrix based further on cyclic shift values for non-zero elements of the selected base parity check matrix.

6. The apparatus of claim 5, wherein the at least one processor is configured to compute cyclic shift values for the lifted parity check matrix based on the cyclic shift values for the non-zero elements of the selected base parity check matrix and the selected lifting value, and to generate the lifted parity check matrix by replacing each non-zero element of the selected base parity check matrix with a cyclic permutation matrix of a cyclic shift value computed for the non-zero element.

7. The apparatus of claim 2, wherein the at least one processor is configured to generate the lifted parity check matrix based on L copies of a base graph for the selected base parity check matrix, where L is the selected lifting value, and to interconnect nodes of the L copies of the base graph based on permutation matrices for non-zero elements of the selected base parity check matrix.

8. The apparatus of claim 7, wherein the base graph comprises a plurality of edges for the non-zero elements of the selected base parity check matrix, and wherein the at least one processor is configured to perform decoding in parallel for L copies of same edge in the L copies of the base graph, and to perform decoding sequentially for different edges in the L copies of the base graph.

9. The apparatus of claim 7, wherein the at least one processor is configured to perform decoding in parallel for the nodes of each copy of the base graph, and to perform decoding sequentially for the L copies of the base graph.

10. The apparatus of claim 2, wherein the at least one processor is configured to encode information bits in the packet based on the lifted parity check matrix to obtain first parity bits, and to encode the information bits and the first parity bits based on the lifted parity check matrix to obtain second parity bits.

11. The apparatus of claim 10, wherein the at least one processor is further configured to encode the information bits, the first parity bits, and the second parity bits based on the lifted parity check matrix to obtain third parity bits.

12. The apparatus of claim 1, wherein the set of base parity check matrices comprises at least one base parity check matrix for at least one of 6, 7, 8, 9, 10 and 11 information bits.

13. The apparatus of claim 1, wherein the set of lifting values comprises at least one lifting value for at least one of 4, 8, 16, 32, 64, 128, 256, 512 and 1024.

14. The apparatus of claim 1, wherein each base parity check matrix comprises a plurality of non-zero elements at a plurality of locations, each non-zero element being associated with a cyclic shift value within a range of 0 to L_max−

1, where L_max is a maximum lifting value.

15. The apparatus of claim 14, wherein the memory is configured to store a plurality of cyclic shift values for the plurality of non-zero elements of each base parity check matrix.

16. The apparatus of claim 15, wherein the at least one processor is configured to determine cyclic shift values for all lifting values for each base parity check matrix based on the plurality of cyclic shift values stored for the base parity check matrix.

17. A method of processing data, comprising:

encoding or decoding packets of variable sizes based on a set of base parity check matrices of different dimensions and a set of lifting values of different powers of two.

18. The method of claim 17, wherein the encoding or decoding packets of variable sizes comprises

determining a packet size of a packet to be encoded or decoded,

selecting a lifting value from the set of lifting values based on the packet size,

selecting a base parity check matrix from the set of base parity check matrices based on the packet size and the selected lifting value,

generating a lifted parity check matrix based on the selected base parity check matrix and the selected lifting value, and

encoding or decoding the packet based on the lifted parity check matrix.

19. The method of claim 18, wherein the selecting the lifting value comprises computing

L=2┌

log₂(k/k_B,max)┐

,

where k is the packet size, k_B,max is a maximum number of information bits for the set of base parity check matrices, L is the selected lifting value, and “

┌

┐

”

denotes a ceiling operator.

20. The method of claim 18, wherein the selecting the base parity check matrix comprises computing

k_B=┌

k/L┐

,

where k is the packet size, L is the selected lifting value, k_B is a number of information bits for the selected base parity check matrix, and “

┌

┐

”

denotes a ceiling operator.

21. The method of claim 17, wherein the generating the lifted parity check matrix comprises

generating the lifted parity check matrix based further on a plurality of cyclic shift values for a plurality of non-zero elements of the selected base parity check matrix.

22. The method of claim 17, further comprising:

storing a plurality of cyclic shift values for a plurality of non-zero elements of each base parity check matrix in the set of base parity check matrices.

23. An apparatus for processing data, comprising:

means for encoding or decoding packets of variable sizes based on a set of base parity check matrices of different dimensions and a set of lifting values of different powers of two.

24. The apparatus of claim 23, wherein the means for encoding or decoding packets of variable sizes comprises

means for determining a packet size of a packet to be encoded or decoded,

means for selecting a lifting value from the set of lifting values based on the packet size,

means for selecting a base parity check matrix from the set of base parity check matrices based on the packet size and the selected lifting value,

means for generating a lifted parity check matrix based on the selected base parity check matrix and the selected lifting value, and

means for encoding or decoding the packet based on the lifted parity check matrix.

25. The apparatus of claim 24, wherein the means for selecting the lifting value comprises means for computing

L=2┌

log₂(k/k_B,max)┐

,

where k is the packet size, k_B,max is a maximum number of information bits for the set of base parity check matrices, L is the selected lifting value, and “

┌

┐

”

denotes a ceiling operator.

26. The apparatus of claim 24, wherein the means for selecting the base parity check matrix comprises means for computing

k_B=┌

k/L┐

,

where k is the packet size, L is the selected lifting value, k_B is a number of information bits for the selected base parity check matrix, and “

┌

┐

”

denotes a ceiling operator.

27. The apparatus of claim 23, wherein the means for generating the lifted parity check matrix comprises

means for generating the lifted parity check matrix based further on a plurality of cyclic shift values for a plurality of non-zero elements of the selected base parity check matrix.

28. The apparatus of claim 23, further comprising:

means for storing a plurality of cyclic shift values for a plurality of non-zero elements of each base parity check matrix in the set of base parity check matrices.

29. A computer program product, comprising:

a computer-readable medium comprising;

code for causing at least one computer to encode or decode packets of variable sizes based on a set of base parity check matrices of different dimensions and a set of lifting values of different powers of two.

30. The computer program product of claim 29, wherein the computer-readable medium further comprises:

code for causing the at least one computer to determine a packet size of a packet to be encoded or decoded;

code for causing the at least one computer to select a lifting value from the set of lifting values based on the packet size;

code for causing the at least one computer to select a base parity check matrix from the set of base parity check matrices based on the packet size and the selected lifting value;

code for causing the at least one computer to generate a lifted parity check matrix based on the selected base parity check matrix and the selected lifting value; and

code for causing the at least one computer to encode or decode the packet based on the lifted parity check matrix.

31. The computer program product of claim 30, wherein the computer-readable medium further comprises:

code for causing the at least one computer to select the lifting value by computing

L=2┌

log₂(k/k_B,max)┐

,

where k is the packet size, k_B,max is a maximum number of information bits for the set of base parity check matrices, L is the selected lifting value, and “

┌

┐

”

denotes a ceiling operator.

32. The computer program product of claim 30, wherein the computer-readable medium further comprises:

code for causing the at least one computer to select the base parity check matrix by computing

k_B=┌

k/L┐

,

where k is the packet size, L is the selected lifting value, k_B is a number of information bits for the selected base parity check matrix, and “

┌

┐

”

denotes a ceiling operator.

33. The computer program product of claim 29, wherein the computer-readable medium further comprises:

code for causing the at least one computer to generate the lifted parity check matrix based further on the plurality of cyclic shift values for the plurality of non-zero elements of the selected base parity check matrix.

34. An apparatus comprising:

at least one processor configured to determine a first set of cyclic shift values for a first parity check matrix of a first lift size based on a second set of cyclic shift values for a second parity check matrix of a second lift size, the first and second lift sizes being different powers of two, to generate the first parity check matrix based on the first set of cyclic shift values, and to encode or decode a packet based on the first parity check matrix; and

a memory coupled to the at least one processor.

35. The apparatus of claim 34, wherein the at least one processor is configured to determine a factor K based on a ratio of the second lift size to the first lift size, and to remove K least significant bits (LSBs) of each cyclic shift value in the second set to obtain a corresponding cyclic shift value in the first set.

36. The apparatus of claim 34, wherein the at least one processor is configured to determine a ratio of the second lift size to the first lift size, and to obtain each cyclic shift value in the first set by dividing a corresponding cyclic shift value in the second set by the ratio and rounding down to an integer value.

37. The apparatus of claim 34, wherein the at least one processor is configured to determine a factor K based on a ratio of the second lift size to the first lift size, and to remove K most significant bits (MSBs) of each cyclic shift value in the second set to obtain a corresponding cyclic shift value in the first set.

38. The apparatus of claim 34, wherein the first and second lift sizes are different powers of two.

39. The apparatus of claim 34, wherein the at least one processor is configured to generate the first parity check matrix by replacing each non-zero element of a base parity check matrix with a cyclic permutation matrix of a cyclic shift value in the first set corresponding to the non-zero element.

40. A method of processing data, comprising:

determining a first set of cyclic shift values for a first parity check matrix of a first lift size based on a second set of cyclic shift values for a second parity check matrix of a second lift size, the first and second lift sizes being different powers of two;

generating the first parity check matrix based on the first set of cyclic shift values; and

encoding or decoding a packet based on the first parity check matrix.

41. The method of claim 40, wherein the determining the first set of cyclic shift values comprises

determining a factor K based on a ratio of the second lift size to the first lift size, and

removing K least significant bits (LSBs) of each cyclic shift value in the second set to obtain a corresponding cyclic shift value in the first set.

42. The method of claim 40, wherein the generating the first parity check matrix comprises

generating the first parity check matrix by replacing each non-zero element of a base parity check matrix with a cyclic permutation matrix of a cyclic shift value in the first set corresponding to the non-zero element.

43. An apparatus comprising:

at least one processor configured to obtain a lifted parity check matrix by replacing each non-zero element of a base parity check matrix with an L×

L permutation matrix of a particular cyclic shift value, where L is a power of two, to use cyclic shift values of s and s+L/m for two non-zero elements in a column of the base parity check matrix having at least three non-zero elements, where s is an arbitrary value and m is a power of two, and to encode or decode a packet based on the lifted parity check matrix; and

a memory coupled to the at least one processor.

44. The apparatus of claim 43, wherein the base parity check matrix comprises

$\left[\begin{array}{cc}B& T\\ D& E\end{array}\right],$

where T is a lower triangular matrix, matrices B and D each has a width of 1, matrices D and E each has a height of 1, and the at least three non-zero elements are in a column corresponding to matrices B and D.

45. The apparatus of claim 43, wherein the at least one processor is configured to select a cyclic shift value of s for a third non-zero element in the column having at least three non-zero elements.

46. The apparatus of claim 43, wherein m is equal to two and the cyclic shift values for the two non-zero elements are s and s+L/2.

47. The apparatus of claim 43, wherein m is equal to four and the cyclic shift values for the two non-zero elements are s and s+L/4.

48. The apparatus of claim 43, wherein m is equal to eight and the cyclic shift values for the two non-zero elements are s and s+L/8.

49. A method of processing data, comprising:

obtaining a lifted parity check matrix by replacing each non-zero element of a base parity check matrix with an L×

L permutation matrix of a particular cyclic shift value, where L is a power of two;

using cyclic shift values of s and s+L/m for two non-zero elements in a column of the base parity check matrix having at least three non-zero elements, where s is an arbitrary value and m is a power of two; and

encoding or decoding a packet based on the lifted parity check matrix.

50. The method of claim 49, wherein the base parity check matrix comprises

$\left[\begin{array}{cc}B& T\\ D& E\end{array}\right],$

where T is a lower triangular matrix, matrices B and D each has a width of 1, matrices D and E each has a height of 1, and the at least three non-zero elements are in a column corresponding to matrices B and D.

51. The method of claim 49, wherein m is equal to four and the cyclic shift values for the two non-zero elements are s and s+L/4.