Frozen-Bit Selection for a Polar Code Decoder
The present disclosure is directed to a system and method for decoding a polar encoded codeword using a frozen bit pattern determined based on a frozen bit pattern derived for a trellis decoder with a different routing structure between each of a plurality of processing stages. The frozen bit pattern can be determined based on the frozen bit pattern derived for the trellis decoder with the different routing structure between each of the plurality of processing stages such that a belief propagation decoder that uses a plurality of time-multiplexed processing elements with a fixed routing interconnect can still achieve a high decoding performance.
1 . A polar decoder comprising:
a plurality of inputs configured to receive a vector y corresponding to a polar encoded codeword;
a plurality of processing elements configured to be time multiplexed over a plurality of steps of a decoding process to decode the vector y into a vector û; and
a plurality of outputs configured to output the vector û, wherein select bits of the vector û are frozen in accordance with a frozen bit pattern determined based on a frozen bit pattern derived for a decoder trellis with a different routing structure between each of a plurality of processing stages.
2 . The polar decoder of claim 1 , wherein each of the plurality of processing elements is configured to perform the following equation:
f
(
l
a
,
l
b
)
=
1
+
l
a
·
l
b
l
a
+
l
b
or equivalent function in the logarithmic domain.
3 . The polar decoder of claim 1 , wherein each of the plurality of processing elements is configured to receive and process four input values to provide four output values.
4 . The polar decoder of claim 1 , wherein the plurality of processing elements consist of N/2 processing elements, where N is the length of the vector y corresponding to the polar encoded codeword.
5 . The polar decoder of claim 1 , wherein the plurality of processing elements are configured to propagate likelihood information during each of the plurality of processing steps from the plurality of inputs to the plurality of outputs or from the plurality of outputs to the plurality of inputs
6 . The polar decoder of claim 1 , wherein the frozen bit pattern derived for the decoder trellis with the different routing structure between each of the plurality of processing stages is determined using a successive-cancellation decoding algorithm for polar codes.
7 . The polar decoder of claim 1 , wherein the frozen bit pattern derived for the decoder trellis with the different routing structure between each of the plurality of processing stages is determined for an explicit communication channel.
8 . A polar decoder comprising:
a plurality of inputs configured to receive a vector y corresponding to a polar encoded codeword;
a plurality of processing elements configured to be time multiplexed over a plurality of steps of a decoding process to decode the vector y into a vector û; and
a plurality of outputs configured to output the vector û,
wherein select bits of the vector û are frozen in accordance with a frozen bit pattern determined based on a frozen bit pattern derived for a decoder trellis with a different routing structure between each of a plurality of processing stages,
wherein output messages of the plurality of processing elements produced during each of the plurality of steps of the decoding process are feedback to inputs of the processing elements using a fixed routing interconnect.
9 . The polar decoder of claim 8 , wherein the decoding process is based on a successive cancellation decoding algorithm.
10 . The polar decoder of claim 8 , wherein each of the plurality of processing elements is configured to perform the following equation:
f
(
l
a
,
l
b
)
=
1
+
l
a
·
l
b
l
a
+
l
b
or equivalent function in the logarithmic domain.
11 . The polar decoder of claim 8 , wherein each of the plurality of processing elements is configured to receive and process four input values to provide four output values.
12 . The polar decoder of claim 8 , wherein the plurality of processing elements consist of N/2 processing elements, where N is the length of the vector y corresponding to the polar encoded codeword.
13 . The polar decoder of claim 8 , wherein the plurality of processing elements are configured to propagate likelihood information during each of the plurality of processing steps from the plurality of inputs to the plurality of outputs or from the plurality of outputs to the plurality of inputs.
14 . The polar decoder of claim 8 , wherein the frozen bit pattern is determined using a successive-cancellation decoding algorithm for polar codes.
15 . The polar decoder of claim 8 , wherein the frozen bit pattern is determined for an additive white Gaussian noise channel.
16 . A method for performing polar decoding comprising:
receiving a vector y corresponding to a polar encoded codeword;
time multiplexing a plurality of processing elements over a plurality of steps of a decoding process to decode the vector y into a vector û; and
outputting the vector û,
wherein select bits of the vector û are frozen in accordance with a frozen bit pattern determined based on a frozen bit pattern derived for a decoder trellis with a different routing structure between each of a plurality of processing stages.
17 . The method of claim 16 , wherein each of the plurality of processing elements is configured to perform the following equation:
f
(
l
a
,
l
b
)
=
1
+
l
a
·
l
b
l
a
+
l
b
or equivalent function in the logarithmic domain.
18 . The method of claim 16 , wherein each of the plurality of processing elements is configured to receive and process four input values to provide four output values.
19 . The method of claim 16 , wherein the plurality of processing elements consist of N/2 processing elements, where N is the length of the vector y corresponding to the polar encoded codeword.
20 . The method of claim 16 , wherein the plurality of processing elements are configured to propagate likelihood information, during each of the plurality of processing steps, from the plurality of inputs to the plurality of outputs or from the plurality of outputs to the plurality of inputs.