Generalized polar codes
AssigneeSocpra Sciences Et Genie S.E.C.
InventorsDavid Poulin, Andrew J. Ferris
Life of this patent
Estimating the term…
Abstract
A method for determining the n best positions of frozen bits in a channel decoder for a noisy communication channel. A decoding method and decoding processing unit for implementing the channel having frozen bits at the n worst positions. A method and system that iteratively, for each bit i from the n bits, determines a probability vector for the bit i by traversing a logical graph using contraction identities simplified to specific values, indexes the specific values from the contraction identities newly computed during the determination of the probability vector for subsequent reference during a following iteration based on corresponding contraction identities, fixes the bit i from the probability vector and moving to bit i+1 until all n bits are fixed.
Claims6
A method of decoding data received over a noisy channel having a channel bandwidth defining channel bits, the method comprising:
- receiving channel bits transmitted over the noisy channel and encoded using a polar code encoding scheme having input positions, the received channel bits encoding non-frozen message bits and frozen bits, the non-frozen message bits applied to encoder input positions having a highest probability of successful decoding after transmission;
- selecting a polar code decoding scheme corresponding to the polar code encoding scheme;
- decoding the received channel bits to output the non-frozen message bits by iteratively, for each bit position:
- if the bit at a bit position is a frozen bit, fixing the decoded bit at the bit position to a fixed frozen bit value;
- if the bit at the bit position is a non-frozen bit, fixing the decoded bit at the bit position to a respective non-frozen value determined using the selected polar code decoding scheme and the previously fixed decoded bits by:
- determining a probability vector for the decoded bit by traversing a logical graph using contraction identities simplified to specific values;
- and
- fixing the bit from the probability vector;
- indexing the specific values from the contraction identities newly computed during the determination of the probability vector for subsequent reference during a following iteration based on corresponding contraction identities;
- and
- increasing to a next bit position and processing the next bit until all channel bits are fixed;
- and
- outputting as the decoded message the non-frozen bits of the fixed decoded bits.
A non-transitory computer readable medium storing instructions, which when executed a processor of a computing device configure the device to perform a method of decoding data received over a noisy channel having a channel bandwidth defining channel bits, the method comprising:
- receiving the channel bits transmitted over the noisy channel and encoded using a polar code encoding scheme having input positions, the received channel bits encoding non-frozen message bits and frozen bits, the non-frozen message bits applied to encoder input positions having a highest probability of successful decoding after transmission;
- selecting a polar code decoding scheme corresponding to the polar code encoding scheme;
- decoding the received channel bits to output the non-frozen message bits by iteratively, for a bit:
- if the bit is a frozen bit, fixing the decoded bit to a fixed frozen bit value;
- and
- if the bit is a non-frozen bit, fixing the decoded bit to a respective non-frozen value determined using the selected polar code decoding scheme and the previously fixed decoded bits by:
- determining a probability vector for the decoded bit by traversing a logical graph using contraction identities simplified to specific values;
- and
- fixing the bit from the probability vector;
- indexing the specific values from the contraction identities newly computed during the determination of the probability vector for subsequent reference during a following iteration based on corresponding contraction identities;
- and
- outputting as the decoded message the non-frozen bits of the fixed decoded bits.
Dependencies are inferred from the claim text.