Low density parity check (LDPC) decoder using broadcast messaging
View Patent ↗In a decoder implementing a belief propagation algorithm for iteratively decoding a Low Density Parity Check (LDPC) encoded data block, a method of computing messages to be sent by a first node of the decoder to at least one neighbor node of the decoder. The method comprises: processing messages received by the first node to remove an echo of a previous message sent by the first node to the at least one neighbor node in a previous iteration, to yield corresponding modified messages; computing a message for a current iteration using the modified messages; and broadcasting the computed message for the current iteration to each of the at least one neighbor nodes.
1. In a Low Density Parity Check (LDPC) code process implementing an iterative belief propagation algorithm, a method of computing messages to be sent by a first node to at least one neighbour node, the method comprising, in a current iteration of the algorithm:
processing one or more messages received by the first node, from at least one of the neighbour nodes, to at least partially remove an echo of a prior message sent to at least one of the neighbour nodes in a previous iteration;
computing, a message using the processed messages;
broadcasting the computed message from the first node to each of the neighbour nodes; and
wherein the previous iteration is more than one iteration prior to the current iteration.
2. The method of claim 1 , wherein the prior message sent to at least one of the neighbour nodes is a message broadcast from the first node to each of the neighbour nodes during the previous iteration.
3. The method of claim 1 , wherein the prior message sent to at least one of the neighbour nodes is a message broadcast from a second node to at least one of the neighbour nodes during the previous iteration.
4. The method of claim 1 , wherein first node is a Variable Node (VN) of the decoder, and the messages received by the first node arc represented by
Cn
i
=
∏
h
=
1
k
Sign
(
Vn
-
1
i
,
h
)
∑
h
=
1
k
θ
(
Vn
-
1
i
,
h
)
,
i
=
1
…
j
,
and wherein processing the messages received by the first node comprises computing:
Cm
i
=
Sign
(
Vn_old
)
∏
h
=
1
k
Sign
(
Vn
-
1
i
,
h
)
θ
[
∑
h
=
1
k
θ
(
Vn
-
1
i
,
h
)
-
θ
(
Vn_old
)
]
,
i
=
1
…
j
where Cm i is the modified message corresponding the Cn i ; and Vn_old is the previous message sent by the VN to each of its j neighbour nodes during the previous iteration.
5. The method of claim 4 , wherein computing the message for a current iteration comprises computing
Vn
=
∑
i
=
1
j
Cm
i
+
LLR
(
x
)
where Vn is the message for the current iteration; and LLR(x) is a Log-Likelihood Ratio (LLR) information sample for a bit position of the VN within the encoded data block.
6. The method of claim 1 , wherein first node is a Check Node (CN) of the decoder, and the messages received by the first node are represented by Vn h , h=1 . . . k, and wherein processing the messages received by the first node comprises computing:
Vm h =Vn h −Cn _old
where Vm h is the modified value from the h th neighbour node, and Cn_old is the message value sent to each of the neighbour nodes during the previous iteration.
7. The method of claim 6 , wherein computing the message for a current iteration comprises computing
Cn
=
∏
h
=
1
k
Sign
(
Vm
h
)
∑
h
=
1
k
θ
(
Vm
h
)
.
8. A forward error correction (FEC) decoder for decoding a Low Density Parity Check (LDPC) encoded data block using an iterative belief propagation algorithm, the FEC decoder comprising: a first node configured to communicate with at least one neighbour node, the first node being operative, in a current iteration of the iterative belief propagation algorithm to: process messages received from the neighbour nodes to at least partially remove an echo of a prior message received by at least one of the neighbour nodes in a previous iteration wherein the previous iteration is more than one iteration prior to the current iteration, to yield corresponding modified messages; and compute a message using the modified messages; and means for conveying the computed message from the first node to each of the neighbour nodes.
9. The FEC decoder as claimed in claim 8 , wherein the means for conveying the computed message from the first node to each of the neighbour nodes comprises a bus connection between an output of the first node and a respective input of each neighbour node.