Methods and systems for decoding polar codes
A polar code decoder includes: processing elements each receiving a pair of input values and applying a first or a second predetermined mathematical function depending on a provided function control signal; a first memory that stores at least one of the outputs from processing elements and a plurality of channel values relating to a received polar code to be decoded; a second memory that stores indices of a plurality of frozen bits each representing a bit within an information-bit vector of the polar code being decoded; and a computation block that receives a plurality of inputs from a portion of the processing elements and generates an output that is can be set to a predetermined frozen value or to a calculated value, depending on whether a current index of the bit being decoded is indicated as frozen or not frozen.
1. A method of decoding comprising the steps of:
providing an integer P processing elements, each processing element receiving a pair of input values and applying one of a first predetermined mathematical function and a second predetermined mathematical function in dependence upon a function control signal provided to the processing element;
providing a first memory for storing at least one of the outputs from the integer P processing elements and a plurality of channel values relating to a received polar code to be decoded, the one of the outputs for storing being determined in dependence upon a clock cycle of a decoding process for the polar code currently being performed;
providing a second memory for storing indices of a plurality of frozen bits, each frozen bit representing a bit within an information-bit vector of the polar code being decoded for which a predetermined error probability has a predetermined magnitude;
providing a computation block coupled to the second memory receiving a plurality of inputs from the outputs of a predetermined portion of the processing elements and generating an output, the output being set to a predetermined frozen value if the current index of the bit being decoded is indicated as frozen within the second memory and set to a calculated value established in dependence upon a predetermined decision process applied to the plurality of inputs when the current index of the bit being decoded is indicated as not frozen.
2. The method of decoding according to claim 1 wherein,
each processing element is configurable between two configurations wherein,
in the first configuration the processing element applies the first predetermined mathematical function using only the two input values for generating the output; and
in the second configuration the processing element applies the second predetermined mathematical function using the two input values and a third input value generated in dependence of a partial sum generated in dependence upon at least a predetermined subset of the plurality of previously estimated bits from the computation block.
3. The method according to claim 1 wherein,
the predetermined frozen value is the frozen bit value for the current index of the bit being decoded; and
the calculated value established by the predetermined decision process is a threshold-detection-based hard decision.
4. The method according to claim 1 wherein,
the integer P equals an integer N defining the length of the polar code being decoded divided by 2 to the power of a positive integer n, where n>1.
5. The method according to claim 1 wherein,
the indices of the plurality of frozen bits are established in dependence upon at least the length of the polar code being employed.
6. The method according to claim 1 further comprising;
receiving an indication of the polar code being employed for decoding; and
providing a third memory for storing indices of a plurality of frozen bit sequences, each frozen bit sequence representing the sequence of bits within the information-bit vector of a predetermined polar code for which a predetermined error probability has a predetermined magnitude; wherein
the second memory is provided a predetermined frozen bit sequence of the plurality of frozen bit sequences, the predetermined frozen bit sequence determined in dependence upon at least the indication of the polar code being employed.
7. The method according to claim 1 wherein,
at least one of the channel values and the outputs from the processing elements are at least one of likelihood ratios and logarithmic likelihood ratios.
8. The method according to claim 1 wherein,
the outputs of the processing elements are stored within the first memory according to a predetermined memory mapping sequence such that in a subsequent clock cycle that a predetermined portion of the stored outputs are read as a contiguous word from the first memory to provide the input values of the processing elements.
9. The method according to claim 2 , wherein
each processing element of the plurality P processing elements is established in a predetermined one of the configurations for each clock cycle of decoding a polar code keyword.
10. A device for decoding comprising:
an integer P processing elements, each processing element receiving a pair of input values and applying one of a first predetermined mathematical function and a second predetermined mathematical function in dependence upon a function control signal provided to the processing element to the pair of input values;
a first memory for storing at least one of the outputs from the integer P processing elements and a plurality of channel values relating to a received polar code to be decoded, the one of the outputs for storing being determined in dependence upon a clock cycle of a decoding process for the polar code currently being performed;
a second memory for storing indices of a plurality of frozen bits, each frozen bit representing a bit within an information-bit vector of the polar code being decoded for which a predetermined error probability has a predetermined magnitude;
a computation block coupled to the second memory receiving a plurality of inputs from the outputs of a predetermined portion of the processing elements and generating an output, the output being set to a predetermined frozen value if the current index of the bit being decoded is indicated as frozen within the second memory and set to a calculated value established in dependence upon a predetermined decision process applied to the plurality of inputs when the current index of the bit being decoded is indicated as not frozen.
11. The device of decoding according to claim 10 wherein, each processing element is configurable between two configurations wherein,
in the first configuration the processing element applies the first predetermined mathematical function using only the two input values for generating the output; and
in the second configuration the processing elements applies the predetermined mathematical function using the two input values and a third input value generated in dependence of a partial sum generated in dependence upon at least a predetermined subset of the plurality of previously estimated bits from the computation block.
12. The device according to claim 10 wherein,
the predetermined frozen value is the frozen bit value for the current index of the bit being decoded; and
the calculated value established by the predetermined decision process is a threshold-detection-based hard decision.
13. The device according to claim 10 wherein,
the integer P equals an integer N defining the length of the polar code being decoded divided by 2 to the power of a positive integer n, where n>1.
14. The device according to claim 10 wherein,
the indices of the plurality of frozen bits are established in dependence upon at least the length of the polar code being employed.
15. The device according to claim 10 further comprising;
an input port for receiving an indication of the polar code being employed for decoding; and
a third memory for storing indices of a plurality of frozen bit sequences, each frozen bit sequence representing the sequence of bits within the information-bit vector of a predetermined polar code for which a predetermined error probability has a predetermined magnitude; wherein
the second memory is provided a predetermined frozen bit sequence of the plurality of frozen bit sequences, the predetermined frozen bit sequence determined in dependence upon at least the indication of the polar code being employed.
16. The device according to claim 10 wherein,
at least one of the channel values and the outputs from the processing elements are at least one of likelihood ratios and logarithmic likelihood ratios.
17. The device according to claim 10 wherein,
the outputs of the processing elements are stored within the first memory according to a predetermined memory mapping sequence such that in a subsequent clock cycle that a predetermined portion of the stored outputs are read as a contiguous word from the first memory to provide the input values of the processing elements.
18. The method according to claim 1 , wherein
the plurality of P processing elements are configured in a binary-tree configuration which decreases from a first stage to a final stage.
19. The method according to claim 1 , wherein
the plurality of P processing elements are configured in a binary-tree configuration which decreases from X processing elements in a first stage to a single processing element in the final stage;
the output from the final stage of processing is an estimated bit which is coupled back to the first stage of processing elements; and
P=N−1 where N is an integer defining the length of a polar code being decoded by the method.
20. The device according to claim 10 , wherein
the plurality of P processing elements are configured in a binary-tree configuration which decreases from a first stage to a final stage.
21. The device according to claim 10 , wherein
the plurality of P processing elements are configured in a binary-tree configuration which decreases from X processing elements in a first stage to a single processing element in the final stage;
the output from the final stage of processing is an estimated bit which is coupled back to the first stage of processing elements; and
P=N−1 where N is an integer defining the length of a polar code being decoded by the method.
22. The device according to claim 11 , wherein
each processing element of the plurality P processing elements is established in a predetermined one of the configurations for each clock cycle of decoding a polar code keyword.