Generalized polar codes
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.
1. 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.
2. The method of claim 1 , wherein the noisy communication channel is modelled as an erasure channel with an erasure probability.
3. The method of claim 1 , wherein the noisy channel is modelled as an erasure channel that presents correlated noise characteristics and is further defined by:
a bad-state probability of erasure;
a good-state probability of erasure, where the bad-state probability of erasure is greater than or equal to the good-state probability of erasure;
a probability of transition between the good state and the bad state; and
a probability of transition between the bad state and the good state.
4. 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.
5. The computer readable medium of claim 4 , wherein the noisy communication channel is modelled as an erasure channel with an erasure probability.
6. The computer readable medium of claim 4 , wherein the noisy channel is modelled as an erasure channel that presents correlated noise characteristics and is further defined by:
a bad-state probability of erasure;
a good-state probability of erasure, where the bad-state probability of erasure is greater than or equal to the good-state probability of erasure;
a probability of transition between the good state and the bad state; and
a probability of transition between the bad state and the good state.