IP Library › Granted Patent US 7,934,146

Granted Patent B2

US 7,934,146 · App. 11/583,222 · Granted Apr 26, 2011

Method, apparatus and computer program product providing for data block encoding and decoding

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 7,934,146
App. No.: 11/583,222
Granted: Apr 26, 2011
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

Methods, apparatus and computer program products are provided for encoding and/or decoding a data block. The method for encoding a data block includes the steps of: providing an information block of size k, I=(i 0 , i 1 , . . . i (k−l) ; and encoding the information block into a low-density parity-check (LDPC) codeword c of size n, c=(i 0 , i 1 , . . . i (k−l) , p 0 , p 1 , . . . , p (n−k−l) ), by adding n−k parity bits obtained so that H·c T =0, where H is an (n−k)×n parity-check matrix.

Claims (3559)

1. A method comprising:

Providing, by an apparatus, an information block (I) of size k, where I=(i 0 , i 1 , . . . i (k−l) ); and

encoding, by the apparatus, the information block into a low-density parity-check (LDPC) codeword c of size n, where c=(i 0 , i 1 , . . . i (k−l) , p 0 , p 1 , . . . , p (n−k−l) ), by adding n−k parity bits obtained so that H·c T =0, where H is an (n−k)×n parity-check matrix, wherein the parity-check matrix is partitioned into square sub-matrices of size Z×Z, wherein the sub-matrices comprise one of a cyclic-permutation of a given sub-matrix or a null sub-matrix, wherein a cyclic-permutation sub-matrix P i is obtained from the given sub-matrix by cyclically shifting the columns of the given sub-matrix to the right by a shift value of i elements, wherein a null sub-matrix comprises a sub-matrix having 0 for all of its values.

2. The method of claim 1 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 648 bits, wherein Z=27, wherein the parity-check matrix comprises:

wherein each number i of the parity-check matrix represents a cyclic-permutation sub-matrix having a shift value of i, wherein a sub-matrix of shift value 0 represents the Z×Z identity sub-matrix, wherein a sub-matrix of shift value—represents a null sub-matrix.

3. The method of claim 1 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1296 bits, wherein Z=54, wherein the parity-check matrix comprises:

4. The method of claim 1 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1944 bits, wherein Z=81, wherein the parity-check matrix comprises:

5. The method of claim 1 , further comprising: generating the parity-check matrix for the LDPC code.

6. The method of claim 1 , wherein the method is implemented by the apparatus within a wireless local area network.

7. A computer-readable medium tangibly storing program instructions execution of the program instructions resulting in operations comprising:

providing an information block (I) of size k, where I=(i 0 , i 1 , . . . i (k−l) ); and

encoding the information block into a low-density parity-check (LDPC) codeword c of size n, where c=(i o , i 1 , . . . i (k−l) ) p 0 , p 1 , . . . p (n−k−l) ), by adding n−k parity bits obtained so that H·c T =0, where H is an (n−k)×n parity-check matrix, wherein the parity-check matrix is partitioned into square sub-matrices of size Z×Z, wherein the sub-matrices comprise one of a cyclic-permutation of a given sub-matrix or a null sub-matrix, wherein a cyclic-permutation sub-matrix P i is obtained from the given sub-matrix by cyclically shifting the columns of the given sub-matrix to the right by a shift value of i elements, wherein a null sub-matrix comprises a sub-matrix having 0 for all of its values.

8. The computer-readable medium of claim 7 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 648 bits, wherein Z=27, wherein the parity-check matrix comprises:

9. The computer-readable medium of claim 7 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1296 bits, wherein Z=54, wherein the parity-check matrix comprises:

10. The computer-readable medium of claim 7 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1944 bits, wherein Z=81, wherein the parity-check matrix comprises:

11. The computer-readable medium of claim 7 , execution of the program instructions resulting in operations further comprising transmitting the LDPC codeword from a first electronic device to a second electronic device.

12. The computer-readable medium of claim 11 , wherein the first electronic device comprises the computer-readable medium storing the program instructions that perform the encoding of the information block into the LDPC codeword.

13. An apparatus comprising:

at least one processor; and

at least one memory including computer program instructions, the at least one memory and the computer program instructions being configured to, with the at least one processor, cause the apparatus at least to perform:

providing an information block (I) of size k,

where I=(i 0 , i 1 , . . . i (k−l) , and

encoding the information block into a low-density parity-check (LDPC) codeword c of size n, where c=(i 0 , i 1 , . . . i (k−l) , p 0 , p 1 , . . . , p (n−k−l) ), by adding n−k parity bits obtained so that H·c T =0, where H is an (n−k)×n parity-check matrix, wherein the parity-check matrix is partitioned into square sub-matrices of size Z×Z, wherein the sub-matrices comprise one of a cyclic-permutation of a given sub-matrix or a null sub-matrix, wherein a cyclic-permutation sub-matrix P i is obtained from the given sub-matrix by cyclically shifting the columns of the given sub-matrix to the right by a shift value of i elements, wherein a null sub-matrix comprises a sub-matrix having 0 for all of its values.

14. The apparatus of claim 13 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 648 bits, wherein Z=27, wherein the parity-check matrix comprises:

15. The apparatus of claim 13 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1296 bits, wherein Z=54, wherein the parity-check matrix comprises:

16. The apparatus of claim 13 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1944 bits, wherein Z=81, wherein the parity-check matrix comprises:

17. The apparatus of claim 13 , the at least one memory and the computer program instructions being configured to, with the at least one processor, cause the apparatus at least further perform:

transmitting the LDPC codeword from the apparatus to a second electronic device; and

dedecoding, using at least the parity-check matrix, a received LDPC codeword to obtain a corresponding information block.

18. The electronic device apparatus of claim 13 , wherein the at least one data processor comprises an encoder.

19. The apparatus of claim 13 , wherein the apparatus comprises a mobile electronic device.

20. The apparatus of claim 13 , wherein the apparatus comprises a mobile telephone.

21. The apparatus of claim 13 , wherein the apparatus comprises an integrated circuit.

22. The apparatus of claim 13 , wherein the apparatus comprises a node of a wireless local area network.

23. The apparatus of claim 13 , wherein the apparatus comprises a node of a wireless local area network using an IEEE 802.11n standard.

24. An apparatus comprising:

at least one processor; and

receiving a low-density parity-check (LDPC) codeword c of size n, where c=(i 0 , i 1 , . . . , i (k−l) , p 0 , p 1 , . . . , p (n−k−l) ), and

decoding the LDPC codeword to obtain an information block (I) of size k, where I=(i 0 , i 1 , . . . , i (k−l) ), by utilizing a (n−k)×n parity-check matrix H, where H·c T =0, wherein the parity-check matrix is partitioned into square sub-matrices of size Z×Z, wherein the sub-matrices comprise one of a cyclic-permutation of a given sub-matrix or a null sub-matrix, wherein a cyclic-permutation sub-matrix P i is obtained from the given sub-matrix by cyclically shifting the columns of the given sub-matrix to the right by a shift value of i elements, wherein a null sub-matrix comprises a sub-matrix having 0 for all of its values.

25. The apparatus of claim 24 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 648 bits, wherein Z=27, wherein the parity-check matrix comprises:

26. The electronic device apparatus of claim 24 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1296 bits, wherein Z=54, wherein the parity-check matrix comprises:

27. The apparatus of claim 24 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1944 bits, wherein Z=81, wherein the parity-check matrix comprises:

28. The apparatus of claim 24 , wherein the LDPC codeword is received from a second electronic device.

29. The apparatus of claim 24 , wherein the apparatus comprises an integrated circuit.

30. The apparatus of claim 24 , wherein the apparatus comprises a mobile electronic device.

31. The apparatus of claim 24 , wherein the apparatus comprises a mobile telephone.

32. The apparatus of claim 24 , wherein the apparatus comprises a node of a wireless local area network.

33. The apparatus of claim 24 , wherein the apparatus comprises a node of a wireless local area network using an IEEE 802.11n standard.

34. A circuit comprising:

an input configured to provide an information block (I) of size k,

where I=(i 0 , i 1 , . . . i (k−l) ); and

encoder circuitry configured to encode the information block into a low-density parity-check (LDPC) codeword c of size n, where c=(i 0 , i 1 , . . . i (k−l) , p 0 , p 1 , . . . , p (n−k−l) ), by adding n−k parity bits obtained so that H·c T =0, where H is an (n−k)×n parity-check matrix, wherein the parity-check matrix is partitioned into square sub-matrices of size Z×Z, wherein the sub-matrices comprise one of a cyclic-permutation of a given sub-matrix or a null sub-matrix, wherein a cyclic-permutation sub-matrix P i is obtained from the given sub-matrix by cyclically shifting the columns of the given sub-matrix to the right by a shift value of i elements, wherein a null sub-matrix comprises a sub-matrix having 0 for all of its values.

35. The circuit of claim 34 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 648 bits, wherein Z=27, wherein the parity-check matrix comprises:

36. The circuit of claim 34 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1296 bits, wherein Z=54, wherein the parity-check matrix comprises:

37. The circuit of claim 34 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1944 bits, wherein Z=81, wherein the parity-check matrix comprises:

38. The circuit of claim 34 , further comprising a transceiver, wherein the transceiver comprises the input.

39. The circuit of claim 38 , further comprising: second circuitry adapted to transmit the LDPC codeword.

40. The circuit of claim 38 , wherein the transceiver is operable to receive a LDPC codeword.

41. The circuit of claim 40 , further comprising third circuitry adapted to decode, using at least the parity-check matrix, the received LDPC codeword to obtain a corresponding information block.

42. A circuit comprising:

an input configured to receive a low-density parity-check (LDPC) codeword c of size n, where c=(i 0 , i 1 , . . . i (k−l) , p 0 , p 1 , . . . , p (n−k−l) ); and

decoder circuitry configured to decode the LDPC codeword into an information block (I) of size k, where I=(i 0 , i 1 , . . . i (k−l) , by utilizing a (n−k)×n parity-check matrix H, where H·c T =0, wherein the parity-check matrix is partitioned into square sub-matrices of size Z×Z, wherein the sub-matrices comprise one of a cyclic-permutation of a given sub-matrix or a null sub-matrix, wherein a cyclic-permutation sub-matrix P i is obtained from the given sub-matrix by cyclically shifting the columns of the given sub-matrix to the right by a shift value of i elements, wherein a null sub-matrix comprises a sub-matrix having 0 for all of its values.

43. The circuit of claim 42 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 648 bits, wherein Z=27, wherein the parity-check matrix comprises:

44. The circuit of claim 42 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1296 bits, wherein Z=54, wherein the parity-check matrix comprises:

45. The circuit of claim 42 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1944 bits, wherein Z=81, wherein the parity-check matrix comprises:

46. The circuit of claim 42 , further comprising a transceiver, wherein the transceiver comprises the input.

47. A method comprising:

receiving, by an apparatus, a low-density parity-check (LDPC) codeword c of size n, where c=(i 0 , i 1 , . . . i (k−l) , p 0 , p 1 , . . . , p (n−k−l) ); and

decoding, by the apparatus, the LDPC codeword into an information block (I) of size k, where I=(i 0 , i 1 , . . . i (k−l) ), by utilizing a (n−k)×n parity-check matrix H, where H·c T =0, wherein the parity-check matrix is partitioned into square sub-matrices of size Z×Z, wherein the sub-matrices comprise one of a cyclic-permutation of a given sub-matrix or a null sub-matrix, wherein a cyclic-permutation sub-matrix P i is obtained from the given sub-matrix by cyclically shifting the columns of the given sub-matrix to the right by a shift value of i elements, wherein a null sub-matrix comprises a sub-matrix having 0 for all of its values.

48. The method of claim 47 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 648 bits, wherein Z=27, wherein the parity-check matrix comprises:

49. The method of claim 47 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1296 bits, wherein Z=54, wherein the parity-check matrix comprises:

50. The method of claim 47 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1944 bits, wherein Z=81, wherein the parity-check matrix comprises:

51. The method of claim 47 , wherein the method is implemented by the apparatus within a wireless local area network.

52. A computer-readable medium tangibly storing program instructions, execution of the program instructions resulting in operations comprising:

receiving a low-density parity-check (LDPC) codeword c of size n, where c=(i 0 , i 1 , . . . i (k−l) , p 0 , p 1 , . . . , P (n−k−l) ; and

decoding the LDPC codeword into an information block (I) of size k, where I=(i 0 , i 1 , . . . i (k−l) ), by utilizing a (n−k)×n parity-check matrix H, where H·c T =0, wherein the parity-check matrix is partitioned into square sub-matrices of size Z×Z, wherein the sub-matrices comprise one of a cyclic-permutation of a given sub-matrix or a null sub-matrix, wherein a cyclic-permutation sub-matrix P i is obtained from the given sub-matrix by cyclically shifting the columns of the given sub-matrix to the right by a shift value of i elements, wherein a null sub-matrix comprises a sub-matrix having 0 for all of its values.

53. The computer-readable medium of claim 52 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 648 bits, wherein Z=27, wherein the parity-check matrix comprises:

54. The computer-readable medium of claim 52 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1296 bits, wherein Z=54, wherein the parity-check matrix comprises:

55. The computer-readable medium of claim 52 , wherein the given sub-matrix comprises a Z×Z identity sub-matrix, wherein a code rate is ¾, wherein a block length of the LDPC codeword is 1944 bits, wherein Z=81, wherein the parity-check matrix comprises:

Assignments (2)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 1, 2015

From: NOKIA CORPORATION

To: NOKIA TECHNOLOGIES OY

Reel/Frame 035561/0438 →

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 18, 2006

From: STOLPMAN, VICTOR

To: NOKIA CORPORATION

Reel/Frame 018444/0412 →