Method and apparatus for encoding and decoding data
View Patent ↗A structured parity-check matrix H is proposed, wherein H is an expansion of a base matrix H b and wherein H b comprises a section H b1 and a section H b2 , and wherein H b2 comprises a first part comprising a column h b having an odd weight greater than 2, and a second part comprising matrix elements for row i, column j equal to 1 for i=j, 1 for i=j+1, and 0 elsewhere. The expansion of the base matrix H b uses identical submatrices for 1s in each column of the second part H′ b2 , and the expansion uses paired submatrices for an even number of 1s in h b .
1. A method for operating a transmitter that generates parity-check bits p=(p 0 , . . . , p m−1 ) based on a current symbol set s=(s 0 , . . . , s k−1 ), the method comprising the steps of:
receiving the current symbol set s=(s 0 , . . . , S k−1 );
using a matrix H to determine the parity-check bits wherein H is represented by H bm or a column or row permutation of the matrix H bm , where H bm =
40
-
-
-
22
-
49
23
43
-
-
-
50
1
-
-
48
35
-
-
13
-
30
-
39
50
-
-
4
-
2
-
-
-
-
49
33
-
-
38
37
-
-
4
1
-
-
-
45
-
-
-
0
22
-
-
20
42
-
-
51
-
-
48
35
-
-
-
44
-
18
-
47
11
-
-
-
17
-
-
51
-
-
-
5
-
25
-
6
-
45
-
13
40
-
-
33
-
-
34
24
-
-
-
23
-
-
46
1
-
27
-
1
-
-
-
38
-
44
-
-
18
-
-
23
-
-
8
0
35
-
-
49
-
17
-
30
-
-
-
34
-
-
19
1
0
-
-
-
-
-
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
-
-
-
-
0
0
-
-
-
-
-
0
-
-
-
-
-
0
0
-
-
-
-
-
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
-
-
-
-
0
0
1
-
-
-
-
-
-
-
-
-
-
0
;
and transmitting the parity-check bits along with the current symbol set.
2. The method of claim 1 wherein:
H is an expansion of a base matrix H b with H b comprising a section H b1 and a section H b2 , with H b2 comprising a first part having a column h b having an odd weight greater than 2, and a second part H′ b2 comprising matrix elements for row i, column j equal to
1 for i=j,
1 for i=j+1,
0 elsewhere;
wherein the expansion of the base matrix H b uses identical submatrices for 1s in each column of the second part H′ b2 , and wherein the expansion uses paired submatrices for an even number of 1s in h b .
3. The method of claim 1 wherein the parity-check matrix H can be partitioned into square subblocks (submatrices) of size z×z, where subblock size is z=54 bits.
4. The method of claim 3 wherein the submatrices are either cyclic-permutations of the identity matrix or null submatrices.
5. The method of claim 3 wherein the cyclic-permutation matrix P i is obtained from the z×z identity matrix by cyclically shifting the columns to the right by i elements.
6. The method of claim 1 wherein the step of using matrix H to determine the parity-check bits p=(p 0 , . . . , p m−1 ) comprises the step of determining
v
(
0
)
=
P
z
-
p
(
x
,
k
b
)
∑
j
=
0
k
b
-
1
∑
i
=
0
m
b
-
1
P
p
(
i
,
j
)
u
(
j
)
,
where u=[u(0) u(1) . . . u(k b −1)] is the current symbol set s grouped into k b groups of z bits, v=[v(0) v(1) . . . v(m b −1)] is the parity-check bits p grouped into m b groups of z bits, p(i,j) is a shift size, and multiplication by P x circularly shifts a vector by x positions.
7. The method of claim 1 wherein the step of using matrix H to determine the parity-check bits (p 0 , . . . , p m−1 ) comprises the step of determining
v
(
0
)
=
P
z
-
p
(
x
,
k
b
)
∑
j
=
0
k
b
-
1
∑
i
=
0
m
b
-
1
P
p
(
i
,
j
)
u
(
j
)
and determining v(1), v(2), . . . , v(m b −1) recursively via
v
(
1
)
=
∑
j
=
0
k
b
-
1
P
p
(
i
,
j
)
u
(
j
)
+
P
p
(
i
,
k
b
)
v
(
0
)
,
i
=
0
,
v
(
i
+
1
)
=
v
(
i
)
+
∑
j
=
0
k
b
-
1
P
p
(
i
,
j
)
u
(
j
)
+
P
p
(
i
,
k
b
)
v
(
0
)
,
i
=
1
,
…
,
m
b
-
2
,
where u=[u(0) u(1) . . . u(k b −1)] is the current symbol set s grouped into k b groups of z bits, v=[v(0) v(1) . . . v(m b −1)] is the parity-check bits p grouped into m b groups of z bits, p(i,j) is a shift size, and multiplication by P x circularly shifts a vector by x positions.
8. The method of claim 1 wherein the step of using matrix H to determine the parity-check bits (p 0 , . . . , p m−1 ) comprises the step of determining
v
(
0
)
=
P
z
-
p
(
x
,
k
b
)
∑
j
=
0
k
b
-
1
∑
i
=
0
m
b
-
1
P
p
(
i
,
j
)
u
(
j
)
and determining v(1), v(2), . . . , v(m b −1) recursively, where u=[u(0) u(1) . . . u(k b −1)] is the current symbol set s grouped into k b groups of z bits, v=[v(0) v(1) . . . v(m b −1)] is the parity-check bits p grouped into m b groups of z bits, p(i,j) is a shift size, and multiplication by P x circularly shifts a vector by x positions.
9. The method of claim 1 further comprising the steps of:
determining additional parity-check bits need to be transmitted; and
transmitting the additional parity-check bits (p m , . . . , p m+m 2 −1 ) based on the current symbol set s=(s 0 , . . . , s k−1 ) and p=(p 0 , . . . , p m−1 ), where m 2 =m b (2) z.
10. The method of claim 9 further comprising the step of using a matrix Prototype H bm (2) to determine the additional parity-check bits wherein H bm (2) is based on H bm .
11. A method for operating a receiver that estimates a current symbol set s=(s 0 , . . . , s k−1 ), the method comprising the steps of:
receiving a received signal vector y=(y 0 . . . y n−1 ); and
using a matrix H to estimate the current symbol set s=(s 0 , . . . , s k−1 ), wherein matrix H is represented by H bm or a column or row permutation of the matrix H bm , where H bm =
40
-
-
-
22
-
49
23
43
-
-
-
1
0
-
-
-
-
-
-
-
-
-
-
50
1
-
-
48
35
-
-
13
-
30
-
-
0
0
-
-
-
-
-
-
-
-
-
39
50
-
-
4
-
2
-
-
-
-
49
-
-
0
0
-
-
-
-
-
-
-
-
33
-
-
38
37
-
-
4
1
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
45
-
-
-
0
22
-
-
20
42
-
-
-
-
-
-
0
0
-
-
-
-
-
-
51
-
-
48
35
-
-
-
44
-
18
-
-
-
-
-
-
0
0
-
-
-
-
-
47
11
-
-
-
17
-
-
51
-
-
-
0
-
-
-
-
-
0
0
-
-
-
-
5
-
25
-
6
-
45
-
13
40
-
-
-
-
-
-
-
-
-
0
0
-
-
-
33
-
-
34
24
-
-
-
23
-
-
46
-
-
-
-
-
-
-
-
0
0
-
-
1
-
27
-
1
-
-
-
38
-
44
-
-
-
-
-
-
-
-
-
-
0
0
-
-
18
-
-
23
-
-
8
0
35
-
-
-
-
-
-
-
-
-
-
-
-
0
0
49
-
17
-
30
-
-
-
34
-
-
19
1
-
-
-
-
-
-
-
-
-
-
0.
12. The method of claim 11 wherein the parity-check matrix H can be partitioned into square subblocks (submatrices) of size z×z, where subblock size is z=54 bits.
13. The method of claim 12 wherein the submatrices are either cyclic-permutations of the identity matrix or null submatrices.
14. The method of claim 13 wherein the cyclic-permutation matrix P i is obtained from the z×z identity matrix by cyclically shifting the columns to the right by i elements.
15. An apparatus comprising:
storage means for storing a matrix H;
a microprocessor using a matrix H to determine parity-check bits; and
a transmitter for transmitting the parity-check bits;
wherein matrix H is represented by H bm or a column or row permutation of the matrix H bm , where H bm =
40
-
-
-
22
-
49
23
43
-
-
-
1
0
-
-
-
-
-
-
-
-
-
-
50
1
-
-
48
35
-
-
13
-
30
-
-
0
0
-
-
-
-
-
-
-
-
-
39
50
-
-
4
-
2
-
-
-
-
49
-
-
0
0
-
-
-
-
-
-
-
-
33
-
-
38
37
-
-
4
1
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
45
-
-
-
0
22
-
-
20
42
-
-
-
-
-
-
0
0
-
-
-
-
-
-
51
-
-
48
35
-
-
-
44
-
18
-
-
-
-
-
-
0
0
-
-
-
-
-
47
11
-
-
-
17
-
-
51
-
-
-
0
-
-
-
-
-
0
0
-
-
-
-
5
-
25
-
6
-
45
-
13
40
-
-
-
-
-
-
-
-
-
0
0
-
-
-
33
-
-
34
24
-
-
-
23
-
-
46
-
-
-
-
-
-
-
-
0
0
-
-
1
-
27
-
1
-
-
-
38
-
44
-
-
-
-
-
-
-
-
-
-
0
0
-
-
18
-
-
23
-
-
8
0
35
-
-
-
-
-
-
-
-
-
-
-
-
0
0
49
-
17
-
30
-
-
-
34
-
-
19
1
-
-
-
-
-
-
-
-
-
-
0.
16. An apparatus comprising:
storage means for storing a matrix H;
a receiver for receiving a signal vector y=(y 0 . . . y n−1 ); and
a microprocessor using a matrix H to determine a current symbol set (s 0 , . . . , s k−1 ), wherein matrix H is represented by H bm or a column or row permutation of the matrix H bm , where H bm =
40
-
-
-
22
-
49
23
43
-
-
-
1
0
-
-
-
-
-
-
-
-
-
-
50
1
-
-
48
35
-
-
13
-
30
-
-
0
0
-
-
-
-
-
-
-
-
-
39
50
-
-
4
-
2
-
-
-
-
49
-
-
0
0
-
-
-
-
-
-
-
-
33
-
-
38
37
-
-
4
1
-
-
-
-
-
-
0
0
-
-
-
-
-
-
-
45
-
-
-
0
22
-
-
20
42
-
-
-
-
-
-
0
0
-
-
-
-
-
-
51
-
-
48
35
-
-
-
44
-
18
-
-
-
-
-
-
0
0
-
-
-
-
-
47
11
-
-
-
17
-
-
51
-
-
-
0
-
-
-
-
-
0
0
-
-
-
-
5
-
25
-
6
-
45
-
13
40
-
-
-
-
-
-
-
-
-
0
0
-
-
-
33
-
-
34
24
-
-
-
23
-
-
46
-
-
-
-
-
-
-
-
0
0
-
-
1
-
27
-
1
-
-
-
38
-
44
-
-
-
-
-
-
-
-
-
-
0
0
-
-
18
-
-
23
-
-
8
0
35
-
-
-
-
-
-
-
-
-
-
-
-
0
0
49
-
17
-
30
-
-
-
34
-
-
19
1
-
-
-
-
-
-
-
-
-
-
0.