Low density parity check (LDPC) code
View Patent ↗Low density parity check code (LDPC) base parity check matrices and the method for use thereof in communication systems. The method of expanding the base check parity matrix is described. Examples of expanded LDPC codes with different code lengths and expansion factors are also shown.
1. A method for constructing a low-density parity-check (LDPC) code having a structured parity check matrix, the method comprising the steps of:
constructing, in a computer processor, a base parity check matrix H=[H d |H p ] having a plurality of elements, H d being a data portion of the base parity check matrix, H p being the parity portion of the base parity check matrix; and
expanding the base parity check matrix into an expanded parity check matrix by replacing each non-zero element of the plurality of elements by a shifted identity matrix; and each zero element of the plurality of elements by a zero matrix;
wherein the base parity check matrix has a coding rate selected from the group consisting of R=½, ⅔, ¾, ⅚, and ⅞; and accordingly is of the size selected from the group consisting of 12×24, 8×24, 6×24, 4×24, and 3×24.
2. The method of claim 1 wherein the parity portion allows a recursive encoding algorithm.
3. The method of claim 1 wherein an inverse of the parity portion of the expanded parity check matrix is sparse, allowing simple encoding per equation
p=H p — exp −1 H d — exp d
and wherein
d is a vector of uncoded bits,
p is a vector of parity bits,
H p — exp −1 is the inverse of the parity portion H p of the expanded parity check matrix, and
H d — exp is the data portion H d the expanded parity check matrix.
4. The method of claim 1 , wherein the data portion of the base parity check matrix has a minimum column weight of 3.
5. The method of claim 1 , wherein the base parity check matrix has a coding rate of R=⅔, and is of the size 8×24.
6. The method of claim 5 , wherein the data portion of the base parity check matrix has a minimum column weight of 3.
7. The method of claim 6 , wherein the data portion of the base parity check matrix has a maximum column weight of 8.
8. The method of claim 7 , wherein the total weight of the base parity check matrix is equal or less then 88.
9. The method of claim 8 , wherein the base parity check matrix is:
1
1
1
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
1
1
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
0
1
1
0
0
0
0
0
1
1
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
1
1
1
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
.
10. The method of claim 9 wherein the base parity check matrix is expanded by an expansion factor L of 81, thereby supporting a code length of up to 1944, and is represented by the expanded parity check matrix:
61
75
4
63
56
-
1
-
1
-
1
-
1
-
1
-
1
8
-
1
2
17
25
1
0
-
1
-
1
-
1
-
1
-
1
-
1
56
74
77
20
-
1
-
1
-
1
64
24
4
67
-
1
7
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
28
21
68
10
7
14
65
-
1
-
1
-
1
23
-
1
-
1
-
1
75
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
48
38
43
78
76
-
1
-
1
-
1
-
1
5
36
-
1
15
72
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
40
2
53
25
-
1
52
62
-
1
20
-
1
-
1
44
-
1
-
1
-
1
-
1
0
-
1
-
1
-
1
0
0
-
1
-
1
69
23
64
10
22
-
1
21
-
1
-
1
-
1
-
1
-
1
68
23
29
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
12
0
68
20
55
61
-
1
40
-
1
-
1
-
1
52
-
1
-
1
-
1
44
-
1
-
1
-
1
-
1
-
1
-
1
0
0
58
8
34
64
78
-
1
-
1
11
78
24
-
1
-
1
-
1
-
1
-
1
58
1
-
1
-
1
-
1
-
1
-
1
-
1
0
wherein −1 represents L×L all-zero square matrix, and other integers represent L×L identity matrix, circularly right shifted a number of times corresponding to the integers.
11. The method of claim 10 wherein the base parity check matrix is expanded by an expansion factor L of 27, thereby supporting a code length of up to 648, and is represented by the expanded parity check matrix:
3
11
13
25
4
-
1
-
1
-
1
-
1
-
1
-
1
22
-
1
11
15
22
1
0
-
1
-
1
-
1
-
1
-
1
-
1
10
2
19
12
-
1
-
1
-
1
15
5
9
24
-
1
15
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
4
26
24
11
2
19
17
-
1
-
1
-
1
3
-
1
-
1
-
1
4
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
24
21
15
5
8
-
1
-
1
-
1
-
1
19
15
-
1
17
3
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
15
18
7
25
-
1
7
6
-
1
8
-
1
-
1
4
-
1
-
1
-
1
-
1
0
-
1
-
1
-
1
0
0
-
1
-
1
1
24
23
12
23
-
1
1
-
1
-
1
-
1
-
1
-
1
0
0
12
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
13
4
12
17
22
23
-
1
4
-
1
-
1
-
1
6
-
1
-
1
-
1
9
-
1
-
1
-
1
-
1
-
1
-
1
0
0
14
25
26
3
5
-
1
-
1
8
2
7
-
1
-
1
-
1
-
1
-
1
7
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
wherein −1 represents L×L all-zero square matrix, and other integers represent L×L identity matrix, circularly right shifted a number of times corresponding to the integers.
12. The method of claim 9 wherein the base parity check matrix is expanded by an expansion factor L of 54, thereby supporting a code length of up to 1296, and is represented by the expanded parity check matrix:
49
13
11
30
27
-
1
-
1
-
1
-
1
-
1
-
1
34
-
1
46
0
45
1
0
-
1
-
1
-
1
-
1
-
1
-
1
38
32
35
53
-
1
-
1
-
1
14
40
12
7
-
1
42
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
13
52
19
51
42
23
49
-
1
-
1
-
1
20
-
1
-
1
-
1
3
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
43
22
23
48
7
-
1
-
1
-
1
-
1
38
28
-
1
46
17
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
41
25
44
17
-
1
11
46
-
1
27
-
1
-
1
12
-
1
-
1
-
1
-
1
0
-
1
-
1
-
1
0
0
-
1
-
1
12
27
32
9
13
-
1
41
-
1
-
1
-
1
-
1
-
1
49
31
23
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
8
34
23
35
23
52
-
1
36
-
1
-
1
-
1
43
-
1
-
1
-
1
5
-
1
-
1
-
1
-
1
-
1
-
1
0
0
17
19
48
16
11
-
1
-
1
38
43
11
-
1
-
1
-
1
-
1
-
1
8
1
-
1
-
1
-
1
-
1
-
1
-
1
0
wherein −1 represents L×L all-zero square matrix, and other integers represent L×L identity matrix, circularly right shifted a number of times corresponding to the integers.
13. The method of claim 1 wherein weights of all columns in the data portion of the base parity check matrix are uniform.
14. The method of claim 13 wherein the weights of all rows in the data portion of a base parity check matrix is uniform.
15. The method of claim 14 wherein the base parity check matrix has a coding rate of R=¾, and is:
1
1
1
1
0
0
0
1
1
0
1
0
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
0
0
0
1
0
1
0
1
1
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
1
.
16. The method of claim 15 wherein the base parity check matrix is expanded by expansion factors L between 24 and L max =96, and is represented by the expanded parity check matrix:
6
38
3
93
-
1
-
1
-
1
30
70
-
1
86
-
1
37
38
4
11
-
1
46
48
0
-
1
-
1
-
1
-
1
62
94
19
84
-
1
92
78
-
1
15
-
1
-
1
92
-
1
45
24
32
30
-
1
-
1
0
0
-
1
-
1
-
1
71
-
1
55
-
1
12
66
45
79
-
1
78
-
1
-
1
10
-
1
22
55
70
82
-
1
-
1
0
0
-
1
-
1
38
61
-
1
66
9
73
47
64
-
1
39
61
43
-
1
-
1
-
1
-
1
95
32
0
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
32
52
55
80
95
22
6
51
24
90
44
20
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
63
31
88
20
-
1
-
1
-
1
6
40
56
16
71
53
-
1
-
1
27
26
48
-
1
-
1
-
1
-
1
0
wherein −1 represents L×L all-zero square matrix, the integer s ij represents circular shifted L×L identity matrix, the amount of the shift s ij ′ is determined as follows:
s
ij
′
=
{
floor
(
L
×
s
ij
L
max
)
,
s
ij
>
0
s
ij
,
otherwise
.
17. The LDPC code constructed using the method of claim 16 .
18. A device using the LDPC code of claim 16 .
19. The LDPC code constructed using the method of claim 15 .
20. A device using the LDPC code of claim 15 .
21. A storage medium readable by a computer encoding a computer program for execution by the computer to carry out a method for constructing a low-density parity-check (LDPC) code having a structured parity check matrix, the method comprising the steps of:
constructing, in a computer processor, a base parity check matrix H=[H d |H p ] having a plurality of elements, H d being a data portion of the base parity check matrix, H p being the parity portion of the base parity check matrix; and
expanding the base parity check matrix into an expanded parity check matrix by replacing each non-zero element of the plurality of elements by a shifted identity matrix, and each zero element of the plurality of elements by a zero matrix;
wherein the base parity check matrix has a coding rate selected from the group consisting of R=½, ⅔, ¾, ⅚, and ⅞; and accordingly is of the size selected from the group consisting of 12×24, 8×24, 6×24, 4×24, and 3×24.
22. The storage medium of claim 21 , wherein the data portion of the base parity check matrix has a minimum weight of 3, the base parity check matrix has a constraint of maximum base parity check matrix weight of 88, and the base parity check matrix is:
1
1
1
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
1
1
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
0
1
1
0
0
0
0
0
1
1
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
1
1
1
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
.
23. The storage medium of claim 21 wherein the base parity check matrix is expanded by an expansion factor L of 27, thereby supporting a code length of up to 648, and is represented by following matrix:
3
11
13
25
4
-
1
-
1
-
1
-
1
-
1
-
1
22
-
1
11
15
22
1
0
-
1
-
1
-
1
-
1
-
1
-
1
10
2
19
12
-
1
-
1
-
1
15
5
9
24
-
1
15
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
4
26
24
11
2
19
17
-
1
-
1
-
1
3
-
1
-
1
-
1
4
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
24
21
15
5
8
-
1
-
1
-
1
-
1
19
15
-
1
17
3
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
15
18
7
25
-
1
7
6
-
1
8
-
1
-
1
4
-
1
-
1
-
1
-
1
0
-
1
-
1
-
1
0
0
-
1
-
1
1
24
23
12
23
-
1
1
-
1
-
1
-
1
-
1
-
1
0
0
12
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
13
4
12
17
22
23
-
1
4
-
1
-
1
-
1
6
-
1
-
1
-
1
9
-
1
-
1
-
1
-
1
-
1
-
1
0
0
14
25
26
3
5
-
1
-
1
8
2
7
-
1
-
1
-
1
-
1
-
1
7
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
wherein −1 represents L×L all-zero square matrix, and other integers represent L×L identity matrix, circularly right shifted a number of times corresponding to the integers.
24. The storage medium of claim 21 wherein the base parity check matrix has a coding rate of R=¾, and is:
1
1
1
1
0
0
0
1
1
0
1
0
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
0
0
0
1
0
1
0
1
1
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
1
.
25. The storage medium of claim 24 wherein the base parity check matrix is expanded by expansion factors L between 24 and L max =96, and is represented by the expanded parity check matrix:
6
38
3
93
-
1
-
1
-
1
30
70
-
1
86
-
1
37
38
4
11
-
1
46
48
0
-
1
-
1
-
1
-
1
62
94
19
84
-
1
92
78
-
1
15
-
1
-
1
92
-
1
45
24
32
30
-
1
-
1
0
0
-
1
-
1
-
1
71
-
1
55
-
1
12
66
45
79
-
1
78
-
1
-
1
10
-
1
22
55
70
82
-
1
-
1
0
0
-
1
-
1
38
61
-
1
66
9
73
47
64
-
1
39
61
43
-
1
-
1
-
1
-
1
95
32
0
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
32
52
55
80
95
22
6
51
24
90
44
20
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
63
31
88
20
-
1
-
1
-
1
6
40
56
16
71
53
-
1
-
1
27
26
48
-
1
-
1
-
1
-
1
0
wherein −1 represents L×L all-zero square matrix, the integer s ij represents circular shifted L×L identity matrix, the amount of the shift s ij ′ is determined as follows:
s
ij
′
=
{
floor
(
L
×
s
ij
L
max
)
,
s
ij
>
0
s
ij
,
otherwise
.
26. A device using a low density parity check (LDPC) code expanded from an LDPC base parity check matrix comprising a data part having a minimum weight of 3, the base parity check matrix having a coding rate of R=⅔, a constraint of maximum base parity check matrix weight of 88, the LDPC base parity check matrix being:
1
1
1
1
1
0
0
0
0
0
0
1
0
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
1
1
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
0
1
1
0
0
0
0
0
1
1
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
1
1
1
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
,
by an expansion factor L of 27, thereby supporting a code length of 648, and is represented by following matrix:
3
11
13
25
4
-
1
-
1
-
1
-
1
-
1
-
1
22
-
1
11
15
22
1
0
-
1
-
1
-
1
-
1
-
1
-
1
10
2
19
12
-
1
-
1
-
1
15
5
9
24
-
1
15
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
4
26
24
11
2
19
17
-
1
-
1
-
1
3
-
1
-
1
-
1
4
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
24
21
15
5
8
-
1
-
1
-
1
-
1
19
15
-
1
17
3
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
15
18
7
25
-
1
7
6
-
1
8
-
1
-
1
4
-
1
-
1
-
1
-
1
0
-
1
-
1
-
1
0
0
-
1
-
1
1
24
23
12
23
-
1
1
-
1
-
1
-
1
-
1
-
1
0
0
12
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
13
4
12
17
22
23
-
1
4
-
1
-
1
-
1
6
-
1
-
1
-
1
9
-
1
-
1
-
1
-
1
-
1
-
1
0
0
14
25
26
3
5
-
1
-
1
8
2
7
-
1
-
1
-
1
-
1
-
1
7
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
wherein 1 represents L×L all-zero square matrix, and other integers represent L×L identity matrix, circularly right shifted a number of times corresponding to the integers.
27. A method for encoding data, the method comprising the steps of:
constructing, in a computer processor, a low density parity check (LDPC) base parity check matrix comprising a data part having a minimum weight of 3, the base parity check matrix having a coding rate of R=⅔, a constraint of maximum base parity check matrix weight of 88, the LDPC base parity check matrix being:
1
1
1
1
0
0
0
1
1
0
1
0
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
0
0
0
1
0
1
0
1
1
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
1
expanding from the LDPC base parity check matrix, by an expansion factor L of 27, thereby supporting a code length of up to 648, resulting in an expanded LDPC code represented by following matrix:
3
11
13
25
4
-
1
-
1
-
1
-
1
-
1
-
1
22
-
1
11
15
22
1
0
-
1
-
1
-
1
-
1
-
1
-
1
10
2
19
12
-
1
-
1
-
1
15
5
9
24
-
1
15
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
4
26
24
11
2
19
17
-
1
-
1
-
1
3
-
1
-
1
-
1
4
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
24
21
15
5
8
-
1
-
1
-
1
-
1
19
15
-
1
17
3
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
15
18
7
25
-
1
7
6
-
1
8
-
1
-
1
4
-
1
-
1
-
1
-
1
0
-
1
-
1
-
1
0
0
-
1
-
1
1
24
23
12
23
-
1
1
-
1
-
1
-
1
-
1
-
1
0
0
12
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
13
4
12
17
22
23
-
1
4
-
1
-
1
-
1
6
-
1
-
1
-
1
9
-
1
-
1
-
1
-
1
-
1
-
1
0
0
14
25
26
3
5
-
1
-
1
8
2
7
-
1
-
1
-
1
-
1
-
1
7
1
-
1
-
1
-
1
-
1
-
1
-
1
0
wherein 1 represents L×L all-zero square matrix, and other integers represent L×L identity matrix, circularly right shifted a number of times corresponding to the integers.