Method and apparatus for decoding data
View Patent ↗A method and apparatus for decoding data is provided herein to show how to turbo decode LDPC codes that contain a partial dual diagonal parity-check portion, and how to avoid memory access contentions in such a turbo decoder. During operation, a decoder will receive a signal vector corresponding to information bits and parity bits and separate the received signal vector into two groups, a first group comprising signals corresponding to the information bits and one or more parity bits, a second group comprising a remainder of the parity bits. The first group of received signals is passed to a first decoder and the second group of received signals is passed to a second decoder. The decoders are separated by an interleaver and a deinterleaver. Iterative decoding takes place by passing messages between the decoders, through the interleaver and the deinterleaver, and producing an estimate of the information bits from the output of the first decoder.
1. A method for estimating an information vector containing information bits at a receiver, the method comprising the steps of:
receiving a signal vector corresponding to information bits and parity bits;
separating the received signal vector into two groups, a first group comprising signals corresponding to the information bits and one or more parity bits, a second group corresponding to a remainder of the parity bits;
passing the first group to a first decoder;
passing the second group to a second decoder;
iteratively decoding by passing messages between the decoders, where the decoders are separated by an interleaver and a de-interleaver; and
producing an estimate of the information vector from the output of the first decoder.
2. The method of claim 1 wherein the first decoder is a repetition decoder.
3. The method of claim 1 wherein the second decoder is a SPC-Accumulator decoder.
4. The method of claim 1 wherein the interleaver and the de-interleaver are contention-free.
5. The method of claim 1 wherein the step of receiving a signal vector corresponding to information bits and parity bits comprises the step of receiving a signal vector corresponding to a codeword of a structured LDPC code using a structured parity-check matrix H with an expansion factor z, a base matrix H b , and a model matrix H bm .
6. The method of claim 5 wherein the received signal vector is passed to a decoder comprising one or more copies of repetition decoders, an interleaver, a de-interleaver corresponding to the interleaver, and one or more copies of SPC-Accumulator decoders, where
each repetition decoder has a same repetition factor Q b obtained from the base matrix H b , and the output messages of the repetition decoders are sent to the interleaver;
each SPC-Accumulator decoder has a same SPC parameter J b obtained from the base matrix H b , and the output messages of the SPC-Accumulator decoders are sent to the de-interleaver;
7. The method of claim 5 wherein the interleaver comprises
a set R bm that stores a set of shift sizes from the model matrix H bm for performing cyclic rotation within each message vector, and
a Permuter (ρ) that is obtained from the base matrix H b to permute the message vectors.
8. The method of claim 7 wherein
the cyclic shift of each individual message vector is an inter-window shuffling with a shuffle pattern
φ
⌊
i
/
W
⌋
(
i
mod
W
)
=
(
R
bm
(
i
mod
W
)
+
⌊
i
W
⌋
)
mod
z
,
where the window size W is equal to the length of ρ, and
the interleaver generates an output address π(i)=ρ(i mod W)+Wφ └i/W┘ (i mod W) for an input i.
9. The method of claim 5 wherein each SPC-Accumulator decoder corresponds to an SPC-Accumulator that accumulates to zero.
10. The method of claim 5 wherein z=96 and H bm =
-
1
94
73
-
1
-
1
-
1
-
1
-
1
55
83
-
1
-
1
7
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
27
-
1
-
1
-
1
22
79
9
-
1
-
1
-
1
12
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
24
22
81
-
1
33
-
1
-
1
-
1
0
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
61
-
1
47
-
1
-
1
-
1
-
1
-
1
65
25
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
39
-
1
-
1
-
1
84
-
1
-
1
41
72
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
46
40
-
1
82
-
1
-
1
-
1
79
0
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
95
53
-
1
-
1
-
1
-
1
-
1
14
18
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
11
73
-
1
-
1
-
1
2
-
1
-
1
47
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
12
-
1
-
1
-
1
83
24
-
1
43
-
1
-
1
-
1
51
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
94
-
1
59
-
1
-
1
70
72
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
7
65
-
1
-
1
-
1
-
1
39
49
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
43
-
1
-
1
-
1
-
1
66
-
1
41
-
1
-
1
-
1
26
7
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
and parameters
Q b =[3 3 6 3 3 6 3 6 3 6 3 6 3];
J b =[5 5 5 4 4 5 4 4 5 4 4 5];
ρ=[15 36 49 0 5 32 1 16 19 28 33 45 10 29 46 11 23 37 6 12 24 38 41 50 7 20 34 8 13 25 39 42 51 2 17 47 3 18 21 30 35 48 22 31 43 9 14 26 40 44 52 4 27 53];
R bm =[61 12 43 94 27 11 73 47 39 95 73 7 24 53 65 22 46 83 22 81 40 24 94 66 79 842 9 33 82 43 59 41 55 65 39 83 25 41 14 47 49 72 18 70 12 0 79 51 72 26 7 0 7];
The inter-window shuffle interleaver is given by the permutation π(i)=ρ(i mod 54)+54φ └i/54┘ (i mod 54), where 0≦i<5184(=54×96), and the inter-window shuffle pattern φ is
φ
⌊
i
/
54
⌋
(
i
mod
54
)
=
(
R
bm
(
i
mod
54
)
+
⌊
i
54
⌋
)
mod
96.
11. An apparatus for estimating an information vector containing information bits at a receiver, the apparatus comprising:
a receiver receiving a signal vector corresponding to information bits and parity bits;
a channel LLR distributor separating the received signal vector into two groups, a first group comprising signals corresponding to the information bits and one or more parity bits, and a second group corresponding to a remainder of the parity bits;
a first decoder receiving the first group of signals;
a second decoder receiving the second group of signals; and
wherein the first and the second decoders iteratively decode the received signal vector by passing messages between the decoders, where the decoders are separated by an interleaver and a de-interleaver, and wherein the first decoder outputs an estimate of the information vector.
12. The apparatus of claim 11 wherein the first decoder is a repetition decoder.
13. The apparatus of claim 11 wherein the second decoder comprises a SPC-Accumulator decoder.
14. The apparatus of claim 11 wherein the interleaver and the de-interleaver are contention-free.
15. The apparatus of claim 11 wherein the signal vector corresponds to a codeword of a structured LDPC code using a structured parity-check matrix H with an expansion factor z, a base matrix H b , and a model matrix H bm .
16. The apparatus of claim 15 further comprising:
a plurality of repetition decoders receiving copies of the first group of received signals; and
a plurality of SPC-Accumulator decoders receiving copies of the second group of received signals, and wherein
each repetition decoder has a same repetition factor Q b obtained from the base matrix H b , and the output messages of the repetition decoders are sent to the interleaver;
each SPC-Accumulator decoder has a same SPC parameter J b obtained from the base matrix H b , and the output messages of the SPC-Accumulator decoders are sent to the de-interleaver.
17. The apparatus of claim 15 wherein the interleaver comprises
a set R bm of shift sizes from the model matrix H bm for performing cyclic rotation within each message vector, and
a Permuter (ρ) that is obtained from the base matrix H b to permute the message vectors.
18. The apparatus of claim 17 wherein
the cyclic shift of each individual message vector is an inter-window shuffling with a shuffle pattern
φ
⌊
i
/
W
⌋
(
i
mod
W
)
=
(
R
bm
(
i
mod
W
)
+
⌊
i
W
⌋
)
mod
z
,
where the window size W is equal to the length of ρ, and
the interleaver generates an output address π(i)=ρ(i mod W)+Wφ └i/W┘ (i mod W) for an input i.
19. The apparatus of claim 15 wherein each SPC-Accumulator decoder corresponds to an SPC-Accumulator that accumulates to zero.
20. The apparatus of claim 15 wherein z=96 and H bm =
-
1
94
73
-
1
-
1
-
1
-
1
-
1
55
83
-
1
-
1
7
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
27
-
1
-
1
-
1
22
79
9
-
1
-
1
-
1
12
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
24
22
81
-
1
33
-
1
-
1
-
1
0
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
61
-
1
47
-
1
-
1
-
1
-
1
-
1
65
25
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
39
-
1
-
1
-
1
84
-
1
-
1
41
72
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
46
40
-
1
82
-
1
-
1
-
1
79
0
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
95
53
-
1
-
1
-
1
-
1
-
1
14
18
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
11
73
-
1
-
1
-
1
2
-
1
-
1
47
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
12
-
1
-
1
-
1
83
24
-
1
43
-
1
-
1
-
1
51
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
-
1
-
1
-
1
-
1
94
-
1
59
-
1
-
1
70
72
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
-
1
-
1
-
1
7
65
-
1
-
1
-
1
-
1
39
49
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
0
43
-
1
-
1
-
1
-
1
66
-
1
41
-
1
-
1
-
1
26
7
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
-
1
0
and parameters
Q b =[3 3 6 3 3 6 3 6 3 6 3 6 3];
J b =[5 5 5 4 4 5 4 4 5 4 4 5];
ρ=[15 36 49 0 5 32 1 16 19 28 33 45 10 29 46 11 23 37 6 12 24 38 41 50 7 20 34 8 13 25 39 42 51 2 17 47 3 18 21 30 35 48 22 31 43 9 14 26 40 44 52 4 27 53];
R bm =[61 12 43 94 27 11 73 47 39 95 73 7 24 53 65 22 46 83 22 81 40 24 94 66 79 84 2 9 33 82 43 59 41 55 65 39 83 25 41 14 47 49 72 18 70 12 0 79 51 72 26 7 0 7];
the inter-window shuffle interleaver is given by the permutation
π( i )=ρ( i mod 54)+54φ └i/54┘ ( i mod 54), where 0≦i<5184(=54×96), [1], (17)
and the inter-window shuffle pattern φ is
φ
⌊
i
/
54
⌋
(
i
mod
54
)
=
(
R
bm
(
i
mod
54
)
+
⌊
i
54
⌋
)
mod
96.