Method and apparatus for providing reduced memory Low Density Parity Check (LDPC) codes
An approach is provided for generating Low Density Parity Check (LDPC) codes. An LDPC encoder generates a LDPC code with an outer Bose Chaudhuri Hocquenghem (BCH) code. For a rate 3/5 code, the approach provides a degree profile that yields reduced memory requirements for storage of the edge values without significantly affecting the performance with respect to an “unmodified” rate 3/5 code. The relevant parameters for the reduced memory LDPC codes are as follows: q=72, n ldpc =64800, k ldpc =n BCH =38880, k BCH =38688. The above approach has particular application in digital video broadcast services over satellite.
1. A method comprising:
generating, based on information bits, parity bits of a Low Density Parity Check (LDPC) code according to a code rate of 3/5 by accumulating bits at parity bit addresses according to {x+m mod 360×q} mod(n ldpc −k ldpc ), where n ldpc is the codeword size, k ldpc is the information block size, m is an integer corresponding to a particular information bit, q is the code rate, and x denotes the address of the parity bit accumulator as specified by respective tables using parity bit accumulators,
Address of Parity Bit Accumulators (Rate 3/5)
22407 10271 11614 19944 11218 2914 3149 73
15405 9692 9911 3315 343 22463 11100 12704
22561 17290 22501 6471 6935 8761 13279 8911
11053 22855 25752 14337 5499 19226 8772 2187
7750 7477 6155 7039 15401 20623 11950 16146
25376 5191 15926 21804 17531 11820 21622 12048
16555 14530 7636 10699 17439 11098 5675 14131
10381 22342 15382 7062 17440 13122 14500 24536
1041 15025 25372 14243 24448 21620 23701 7474
18504 22194 20916 8948 5461 15657 6146 21549
24143 2676 23993 24376 22472 10350 1079 12342
23825 9004 25634 16833 5736 18814 11600 5591
21494 24795 6352 17362 7102 13903 3993 16495
11561 15038 23349 503 3497 11202 15418 16076
22528 2432 19064 2934 21660 1911 7499 5616
7283 16543 13866 6723 8888 18245 16962 1743
2727 16421 728 10651 7012 9191 10149 9106
13005 10331 15275 3145 13413 12800 17139 4932
4504 15820 24833 17200 14077 4993 9788 6653
18224 11374 9038 4713 510 9369 7421 8337
23906 18930 7269 12514 4373 20020 6164 21016
4406 8242 22946 25140 10353 5300 14809 5808
15911 16437 15764 17765 17427 9495 8358 4961
2131 12908 5343 14758 14678 7988 20631 4357
24002 10014 11034 3773 24265 8059 19802 854
23920 10497 19268 17515 6333 7787 17171 17614
15810 7467 23718 3651 24578 16552 17557 22433
20507 4411 24872 11006 17541 15667 15278 4243
24148 10488 8501 23359 4030 1418 4442 23299
16584 8067 24762 3645 25884 8712 9585 20358
10710 6116 24519 7728 19963 24989 23944 13660
18708 145 3901 22948 16454 17670 15352 18189
3218 11549 18170 12733 18733 5705 14682 17199
14921 11190 25097 23569 86 4804 10478 22553
657 53 15215 15049 13307 2328 19535 21435
19767 2988 16855 4858 23970 15171 724 23353
0 19274 20228
1 13271 1515
2 10864 476
3 4787 21317
4 2609 15664
5 23875 22477
6 9537 18270
7 12039 16705
8 15180 18317
9 10133 6682
10 10203 5671
11 12482 13992
12 19116 1725
13 17558 16333
14 7932 18883
15 23346 6770
16 5049 15145
17 6960 8821
18 10686 16411
19 14276 4043
20 6988 1073
21 20504 4318
22 14806 18855
23 23408 2829
24 22876 24662
25 14159 10002
26 8898 25354
27 5936 1007
28 16162 7228
29 23710 23342
30 23745 16423
31 13336 18903
32 10697 8815
33 6198 6723
34 2880 20781
35 1185724611
36 8005 2292
37 24679 6248
38 21841 20646
39 11296 9870
40 21935 16106
41 10983 18735
42 12821 12188
43 13941 10895
44 5712 19077
45 6437 11275
46 10827 11446
47 14047 13073
48 1503 19612
49 17944 1338
50 11235 24946
51 19170 7268
52 2913 2560
53 17734 7765
54 9625 22307
55 17651 16905
56 300 3636
57 1526 23116
58 17733 2448
59 14977 13008
60 11946 12026
61 8819 8702
62 11906 4819
63 2629 12075
64 4854 5201
65 13627 18773
66 18658 12753
67 24872 8887
68 3455 8326
69 10772 3134
70 21514 18584
71 15689 18484.
2. A method according to claim 1 , wherein parity bits, p i , are determined according to p i =p i ⊕ p i−1 , i=1,2, . . . ,n ldpc −k ldpc −1.
3. A method according to claim 1 , wherein a Bose Chaudhuri Hocquenghem (BCH) outer code is used based on a generator polynomial of:
g ( x )=(1 +x+x 3 +x 5 +x 14 )×(1 +x 6 +x 8 +x 11 +x 14 )×(1 +x+x 2 +x 6 +x 9 +x 10 +x 14 )×(1 +x 4 +x 7 +x 8 +x 10 +x 12 +x 14 )×(1 +x 2 +x 4 +x 6 +x 8 +x 9 +x 11 +x 13 +x 14 )×(1 +x 3 +x 7 +x 8 +x 9 +x 13 +x 14 )×(1 +x 2 +x 5 +x 6 +x 7 +x 10 +x 11 +x 13 +x 14 )×(1 +x 5 +x 8 +x 9 +x 10 +x 11 +x 14 )×(1 +x+x 2 +x 3 +x 9 +x 10 +x 14 )×(1 +x 3 +x 6 +x 9 +x 11 +x 12 +x 14 )×(1 +x 4 +x 11 +x 12 +x 14 )×(1 +x+x 2 +x 3 +x 5 +x 6 +x 7 +x 8 +x 10 +x 13 +x 14 ).
4. A method according to claim 1 , wherein the LDPC code is transmitted over a satellite link in support of a broadband satellite application.
5. A method according to claim 4 , wherein the LDPC code represents digitized video signals.
6. A method according to claim 5 , wherein the video signals conform with MPEG (Motion Pictures Expert Group) packet transmission.
7. A computer-readable medium bearing instructions for encoding, said instructions, being arranged, upon execution, to cause one or more processors to perform the method of claim 1 .
8. An apparatus comprising:
logic configured to generate, based on information bits, parity bits of a Low Density Parity Check (LDPC) code according to a code rate of 3/5 by accumulating bits at parity bit addresses according to {x+m mod 360×q} mod(n ldpc −k ldpc ), where n ldpc is the codeword size, k ldpc is the information block size, m is an integer corresponding to a particular information bit, q is the code rate, and x denotes the address of the parity bit accumulator as specified by respective tables using parity bit accumulators,
Address of Parity Bit Accumulators (Rate 3/5)
22407 10271 11614 19944 11218 2914 3149 73
15405 9692 9911 3315 343 22463 11100 12704
22561 17290 22501 6471 6935 8761 13279 8911
11053 22855 25752 14337 5499 19226 8772 2187
7750 7477 6155 7039 15401 20623 11950 16146
25376 5191 15926 21804 17531 11820 21622 12048
16555 14530 7636 10699 17439 11098 5675 14131
10381 22342 15382 7062 17440 13122 14500 24536
1041 15025 25372 14243 24448 21620 23701 7474
18504 22194 20916 8948 5461 15657 6146 21549
24143 2676 23993 24376 22472 10350 1079 12342
23825 9004 25634 16833 5736 18814 11600 5591
21494 24795 6352 17362 7102 13903 3993 16495
11561 15038 23349 503 3497 11202 15418 16076
22528 2432 19064 2934 21660 1911 7499 5616
7283 16543 13866 6723 8888 18245 16962 1743
2727 16421 728 10651 7012 9191 10149 9106
13005 10331 15275 3145 13413 12800 17139 4932
4504 15820 24833 17200 14077 4993 9788 6653
18224 11374 9038 4713 510 9369 7421 8337
23906 18930 7269 12514 4373 20020 6164 21016
4406 8242 22946 25140 10353 5300 14809 5808
15911 16437 15764 17765 17427 9495 8358 4961
2131 12908 5343 14758 14678 7988 20631 4357
24002 10014 11034 3773 24265 8059 19802 854
23920 10497 19268 17515 6333 7787 17171 17614
15810 7467 23718 3651 24578 16552 17557 22433
20507 4411 24872 11006 17541 15667 15278 4243
24148 10488 8501 23359 4030 1418 4442 23299
16584 8067 24762 3645 25884 8712 9585 20358
10710 6116 24519 7728 19963 24989 23944 13660
18708 145 3901 22948 16454 17670 15352 18189
3218 11549 18170 12733 18733 5705 14682 17199
14921 11190 25097 23569 86 4804 10478 22553
657 53 15215 15049 13307 2328 19535 21435
19767 2988 16855 4858 23970 15171 724 23353
0 19274 20228
1 13271 1515
2 10864 476
3 4787 21317
4 2609 15664
5 23875 22477
6 9537 18270
7 12039 16705
8 15180 18317
9 10133 6682
10 10203 5671
11 12482 13992
12 19116 1725
13 17558 16333
14 7932 18883
15 23346 6770
16 5049 15145
17 6960 8821
18 10686 16411
19 14276 4043
20 6988 1073
21 20504 4318
22 14806 18855
23 23408 2829
24 22876 24662
25 14159 10002
26 8898 25354
27 5936 1007
28 16162 7228
29 23710 23342
30 23745 16423
31 13336 18903
32 10697 8815
33 6198 6723
34 2880 20781
35 11857 24611
36 8005 2292
37 24679 6248
38 21841 20646
39 11296 9870
40 21935 16106
41 10983 18735
42 12821 12188
43 13941 10895
44 5712 19077
45 6437 11275
46 10827 11446
47 14047 13073
48 1503 19612
49 17944 1338
50 11235 24946
51 19170 7268
52 2913 2560
53 17734 7765
54 9625 22307
55 17651 16905
56 300 3636
57 1526 23116
58 17733 2448
59 14977 13008
60 11946 12026
61 8819 8702
62 11906 4819
63 2629 12075
64 4854 5201
65 13627 18773
66 18658 12753
67 24872 8887
68 3455 8326
69 10772 3134
70 21514 18584
71 15689 18484.
9. An apparatus according to claim 8 , wherein parity bits, p i , are determined according to p i =p i ⊕ p i−1 , i=1,2, . . . ,n ldpc −k ldpc −1.
10. An apparatus according to claim 8 , wherein a Bose Chaudhuri Hocquenghem (BCH) outer code is used based on a generator polynomial of:
g ( x )=(1 +x+x 3 +x 5 +x 14 )×(1 +x 6 +x 8 +x 11 +x 14 )×(1 +x+x 2 +x 6 +x 9 +x 10 +x 14 )×(1 +x 4 +x 7 +x 8 +x 10 +x 12 +x 14 )×(1 +x 2 +x 4 +x 6 +x 8 +x 9 +x 11 +x 13 +x 14 )×(1 +x 3 +x 7 +x 8 +x 9 +x 13 +x 14 )×(1 +x 2 +x 5 +x 6 +x 7 +x 10 +x 11 +x 13 +x 14 )×(1 +x 5 +x 8 +x 9 +x 10 +x 11 +x 14 )×(1 +x+x 2 +x 3 +x 9 +x 10 +x 14 )×(1 +x 3 +x 6 +x 9 +x 11 +x 12 +x 14 )×(1 +x 4 +x 11 +x 12 +x 14 )×(1 +x+x 2 +x 3 +x 5 +x 6 +x 7 +x 8 +x 10 +x 13 +x 14 ).
11. An apparatus according to claim 8 , wherein the LDPC code is transmitted over a satellite link in support of a broadband satellite application.
12. An apparatus according to claim 11 , wherein the LDPC code represents digitized video signals.
13. An apparatus according to claim 12 , wherein the video signals conform with MPEG (Motion Pictures Expert Group) packet transmission.
14. A system comprising:
a Low Density Parity Check (LDPC) encoder configured to output, based on received information bits, an LDPC code; and
a Bose Chaudhuri Hocquenghem (BCH) encoder coupled to the LDPC encoder and configured to provide an outer code to the LDPC code, wherein the LDPC code is generated according to a code rate of 3/5 associated with a table specifying address of parity bit accumulators according to {x+m mod 360×q} mod(n ldpc −k ldpc ), where n ldpc is the codeword size, k ldpc is the information block size, m is an integer corresponding to a particular information bit, q is the code rate, and x denotes the address of the parity bit accumulator,
Address of Parity Bit Accumulators (Rate 3/5)
22407 10271 11614 19944 11218 2914 3149 73
15405 9692 9911 3315 343 22463 11100 12704
22561 17290 22501 6471 6935 8761 13279 8911
11053 22855 25752 14337 5499 19226 8772 2187
7750 7477 6155 7039 15401 20623 11950 16146
25376 5191 15926 21804 17531 11820 21622 12048
16555 14530 7636 10699 17439 11098 5675 14131
10381 22342 15382 7062 17440 13122 14500 24536
1041 15025 25372 14243 24448 21620 23701 7474
18504 22194 20916 8948 5461 15657 6146 21549
24143 2676 23993 24376 22472 10350 1079 12342
23825 9004 25634 16833 5736 18814 11600 5591
21494 24795 6352 17362 7102 13903 3993 16495
11561 15038 23349 503 3497 11202 15418 16076
22528 2432 19064 2934 21660 1911 7499 5616
7283 16543 13866 6723 8888 18245 16962 1743
2727 16421 728 10651 7012 9191 10149 9106
13005 10331 15275 3145 13413 12800 17139 4932
4504 15820 24833 17200 14077 4993 9788 6653
18224 11374 9038 4713 510 9369 7421 8337
23906 18930 7269 12514 4373 20020 6164 21016
4406 8242 22946 25140 10353 5300 14809 5808
15911 16437 15764 17765 17427 9495 8358 4961
2131 12908 5343 14758 14678 7988 20631 4357
24002 10014 11034 3773 24265 8059 19802 854
23920 10497 19268 17515 6333 7787 17171 17614
15810 7467 23718 3651 24578 16552 17557 22433
20507 4411 24872 11006 17541 15667 15278 4243
24148 10488 8501 23359 4030 1418 4442 23299
16584 8067 24762 3645 25884 8712 9585 20358
10710 6116 24519 7728 19963 24989 23944 13660
18708 145 3901 22948 16454 17670 15352 18189
3218 11549 18170 12733 18733 5705 14682 17199
14921 11190 25097 23569 86 4804 10478 22553
657 53 15215 15049 13307 2328 19535 21435
19767 2988 16855 4858 23970 15171 724 23353
0 19274 20228
1 13271 1515
2 10864 476
3 4787 21317
4 2609 15664
5 23875 22477
6 9537 18270
7 12039 16705
8 15180 18317
9 10133 6682
10 10203 5671
11 12482 13992
12 19116 1725
13 17558 16333
14 7932 18883
15 23346 6770
16 5049 15145
17 6960 8821
18 10686 16411
19 14276 4043
20 6988 1073
21 20504 4318
22 14806 18855
23 23408 2829
24 22876 24662
25 14159 10002
26 8898 25354
27 5936 1007
28 16162 7228
29 23710 23342
30 23745 16423
31 13336 18903
32 10697 8815
33 6198 6723
34 2880 20781
35 11857 24611
36 8005 2292
37 24679 6248
38 21841 20646
39 11296 9870
40 21935 16106
41 10983 18735
42 12821 12188
43 13941 10895
44 5712 19077
45 6437 11275
46 10827 11446
47 14047 13073
48 1503 19612
49 17944 1338
50 11235 24946
51 19170 7268
52 2913 2560
53 17734 7765
54 9625 22307
55 17651 16905
56 300 3636
57 1526 23116
58 17733 2448
59 14977 13008
60 11946 12026
61 8819 8702
62 11906 4819
63 2629 12075
64 4854 5201
65 13627 18773
66 18658 12753
67 24872 8887
68 3455 8326
69 10772 3134
70 21514 18584
71 15689 18484.
15. An apparatus according to claim 14 , wherein parity bits, p i , are determined according to p i =p i ⊕ p i−1 , i=1,2, . . . ,n ldpc −k ldpc −1.
16. An apparatus according to claim 14 , wherein a Bose Chaudhuri Hocquenghem (BCH) outer code is used based on a generator polynomial of:
g ( x )=(1 +x+x 3 +x 5 +x 14 )×(1 +x 6 +x 8 +x 11 +x 14 )×(1 +x+x 2 +x 6 +x 9 +x 10 +x 14 )×(1 +x 4 +x 7 +x 8 +x 10 +x 12 +x 14 )×(1 +x 2 +x 4 +x 6 +x 8 +x 9 +x 11 +x 13 +x 14 )×(1 +x 3 +x 7 +x 8 +x 9 +x 13 +x 14 )×(1 +x 2 +x 5 +x 6 +x 7 +x 10 +x 11 +x 13 +x 14 )×(1 +x 5 +x 8 +x 9 +x 10 +x 11 +x 14 )×(1 +x+x 2 +x 3 +x 9 +x 10 +x 14 )×(1 +x 3 +x 6 +x 9 +x 11 +x 12 +x 14 )×(1 +x 4 ×x 11 +x 12 +x 14 )×(1 +x+x 2 +x 3 +x 5 +x 6 +x 7 +x 8 +x 10 +x 13 +x 14 ).
17. A system according to claim 14 , wherein the LDPC code is transmitted over a satellite link in support of a broadband satellite application.
18. A system according to claim 3 , wherein the LDPC code represents digitized video signals.
19. A system according to claim 17 , wherein the video signals conform with MPEG (Motion Pictures Expert Group) packet transmission.