Iterative bit flip decoding based on symbol reliabilities

Abstract

The present application concerns an iterative bit-flipping decoding method using symbol or bit reliabilities, which is a variation of GRAND decoding and is denoted by ordered reliability bits GRAND (ORBGRAND). It comprises receiving a plurality of demodulated symbols from a noisy transmission channel; and receiving for the plurality of demodulated symbols, information indicating a ranked order of reliability of at least the most unreliable information contained within the plurality of demodulated symbols. A sequence of putative noise patterns from a most likely pattern of noise affecting the plurality of symbols through one or more successively less likely noise patterns is provided. Responsive to the information contained within the plurality of symbols not corresponding with an element of a code-book comprising a set of valid codewords, a first in the sequence of putative noise patterns is used to invert the most unreliable information of the information contained within the plurality of symbols to obtain a potential codeword, and responsive to the potential codeword not corresponding with an element of the code-book, repeatedly: a next likely noise pattern from the sequence of putative noise patterns is applied to invert a noise effect on the received plurality of demodulated symbols to provide a potential codeword, each successive noise pattern indicating an inversion of information for one or more demodulated symbols for a next more reliable combination of information contained within the plurality of symbols, until the potential codeword corresponds with an element of the code-book.

Claims

1. A method, in a decoder, of decoding as a codeword a plurality of symbols received from a data sender using a noisy transmission channel, the method comprising: receiving hard decision demodulation information about a plurality of demodulated symbols from the noisy transmission channel, each symbol corresponding to z≥1 bits; receiving for the plurality of demodulated symbols, information indicating a ranked order of reliability of the most unreliable information contained within the plurality of demodulated symbols, wherein said most unreliable information comprises n>1 most unreliable symbols of the plurality of demodulated symbols, wherein when n is equal to a power of 2, said information indicating a ranked order of reliability comprises no more than log.sub.2 (n) bits per unreliable symbol, and when n is not equal to a power of 2, said information indicating a ranked order of reliability comprises no more than the smallest integer which is larger than log.sub.2 (n) bits per unreliable symbol; providing a sequence of putative noise patterns from a most likely pattern of noise affecting said plurality of symbols through one or more successively less likely noise patterns based on the information indicating a ranked order of reliability; responsive to the information contained within the plurality of symbols not corresponding with an element of a code-book comprising a set of valid codewords, using a first in said sequence of putative noise patterns to invert the most unreliable information of the information contained within the plurality of symbols to obtain a potential codeword; responsive to the potential codeword not corresponding with an element of the code-book, repeatedly: applying a next likely noise pattern from the sequence of putative noise patterns to invert a noise effect on the received plurality of demodulated symbols to provide a potential codeword, each successive noise pattern indicating an inversion of information for one or more demodulated symbols for a next more reliable combination of information contained within the plurality of symbols, until the potential codeword corresponds with an element of the code-book; and outputting the potential codeword as the decoded codeword.

2. The method of claim 1 wherein each demodulated symbol provides more than 1 bit of information and where an inversion of information for a demodulated symbol comprises successively inverting the values for each bit for the demodulated symbol to obtain successive potential codewords.

3. The method of claim 1 wherein a sequence of permutations of n pieces of most unreliable information contained within the plurality of demodulated symbols is known a priori and said information indicating a ranked order of reliability comprises no more than log.sub.2 (n!)/n bits per piece of information.

4. The method of claim 1 where in response to more than one combination of information contained within the plurality of symbols having an equal increase in likelihood, one of said combinations is chosen arbitrarily as the next likely noise pattern.

5. The method of claim 1 wherein said sequence of putative noise patterns include patterns of noise requiring fewer inversions as being more likely.

6. A decoder for decoding as a codeword a plurality of symbols received from a data sender using a noisy data channel, the decoder being configured to perform the method of claim 1.

7. A computer program product comprising executable code stored on a non-transitory computer readable medium which when executed in a decoder is configured to perform the method according to claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Embodiments of the invention will now be described, by way of example, with reference to the accompanying drawings, in which:

(2) FIG. 1 illustrates a transmitter communicating with a receiver across a noisy transmission channel and showing a demodulator within the receiver providing soft information to a decoder in accordance with variants of GRAND; and

(3) FIG. 2 illustrates an exemplary sequence for putative noise patterns which can be employed within embodiments of the present invention.

DESCRIPTION OF THE EMBODIMENT

(4) Referring now to FIG. 1, there is shown a transmitter 10 and a receiver 12 communicating with one another across a noisy transmission channel 14. The transmitter 10 which can be of a conventional type generates or obtains information 16 which needs to be transmitted. Generally, this is produced by some type of application (not shown) running on the transmitting device 10. Nonetheless, it will be appreciated that the information can be produced by any level of software or hardware executing on the transmitter or on a device coupled to the transmitter. The information is typically serialised and provided to an encoder 18 which can encapsulate the information in any conventional manner, for example, adding redundant information to enable checking or recovery of lost information or encrypting the information, before providing the information to a modulator 20 for transmission across the channel 14.

(5) The channel 14 can be any form of wired or wireless channel which is subject to noisy interference and in some cases, the channel 14 may be divided into a number of sub-channels which carry information in parallel. In any case, it should be appreciated that the channel 14 can comprise any optical, electrical, electro-magnetic or other medium or combination thereof.

(6) The transmitted information is picked up by the receiver 12 coupled to the channel 14, typically through an antenna for wireless electro-magnetic channels, and provided to a demodulator 22. The modulator 20 and demodulator 22 are paired and can be of any form as long as the demodulator 22 is able to produce a stream of symbols from the signal received across the channel 14.

(7) In the embodiment, the stream of symbols is provided to a decoder 24 and again the decoder is configured to reverse the processing performed by the encoder 18 to provide digital information 26 corresponding to the transmitted information 16.

(8) As described above, using GRAND, only the streams of demodulated symbols produced by the demodulator 22 are provided to the decoder 24, for SRGRAND only a binary indication of the reliability or not of any given symbol is provided in addition to the stream of demodulated symbols, whereas for SGRAND, real-valued soft information is provided for each symbol generated by the demodulator 22 in addition to the stream of demodulated symbols.

(9) Part of the decoding process comprises mapping the stream of demodulated symbols into a binary stream of valid information i.e. a string of bits. Each portion of the stream of valid information corresponds to a codeword and once a codeword has been determined from one or more demodulated symbols, this can be processed including decrypting or buffering the information as required before providing the processed information 26.

(10) As will be appreciated, if the transmission channel 14 has been affected by noise, a potential codeword i.e. the string of bits derived from the demodulated symbols provided by the demodulator 22, will not be recognised as a valid codeword in a code-book. (Again, the code-book can be any of a random codebook, a random linear codebook, a Hamming codebook, or a Low Density Parity Check codebook or any form of code-book) Using GRAND, SRGRAND and SGRAND putative noise patterns are removed by the decoder 24 from the string of bits derived from the demodulated symbols and comprising a potential codeword, in order from most likely noise pattern to least likely based on their noise model and any soft information available to them, querying if what remains is in the code-book.

(11) According to one embodiment of the present invention, the decoder 24 uses the hard decision demodulation information provided by the demodulator 22 divided into groups of n demodulated symbols, y.sup.n, along with soft information comprising a permutation r.sup.n that indicates the rank ordering of the reliability of an associated group of n demodulated symbols.

(12) The rank ordering indicated by r.sup.n is a code-book independent quantisation of the soft information indicating in order the reliability of each symbol in a group of symbols. As will be appreciated n symbols can have n! permutations for their order of reliability and so r.sup.n requires a word size large enough to encode the particular permutation for a group of symbols.

(13) Where the ordering of permutations is not known a priori by the decoder 24, then where n is a power of 2, log.sub.2(n) bits of soft information will be required for each symbol. For values of n which are not powers of two, a slightly higher number, the smallest integer that is larger than log.sub.2 (n) bits of soft information, are required for each symbol.

(14) On the other hand, where the ordering of permutations is known by the demodulator 22 and decoder 24 a priori, then r.sup.n need only comprise an index for an algorithm or look-up table which will return the permutation in response to receiving r.sup.n and this can reduce the size of soft information required to no more than log.sub.2(n!)/n bits of soft information for each symbol, which is smaller than log.sub.2 (n) bits. So, the permutation indicating the rank ordering for a group of 12 demodulated symbols can be encoded in 29 bits, requiring less than 3 bits of soft information per symbol.

(15) Even this assumes that the rank ordering for all symbols of a group of n symbols is employed by the decoder 24. If for example, a decoder was only going to attempt to apply a query threshold T of putative noise patterns based on flipping only the information contained in the most unreliable symbols, then a group of n symbols can be divided into n-a the most unreliable symbols and the remaining a most reliable symbols. Then as will be seen from the example below, only the ranked order of the n-a most unreliable symbols needs to be provided to the decoder as only this information will be required to determine the sequence of up to T noise patterns to apply to a group of demodulated symbols, so reducing the amount of soft information required for a given amount of hard information.

(16) In any case, on receipt of the soft information indicating the permutation r.sup.n, the decoder 24 is immediately able to determine the ranked order of the reliability of symbols within the associated group of symbols, y.sup.n. This order enables the decoder to map each symbol in order of its reliability from the most unreliable to the least unreliable (most reliable).

(17) Referring now to FIG. 2, which illustrates the first 100 putative noise patterns in an exemplary sequence of noise patterns for a transmission channel 14 affected by white noise, and which can be applied to a sequence of 13 symbols. Each row represents a putative noise pattern with white being “no flip” and black corresponding to flipping the information for a symbol.

(18) For simplicity, the example is described for symbols providing 1 bit of demodulated information. Thus, flipping the information for a symbol simply comprises flipping the demodulated value for a bit between 1 and 0. In other implementations, a symbol can provide z>1 bit of demodulated information. In this case, flipping the information for any given symbol involves a sub-sequence of flipping the demodulated values for all of the bits through their 2.sup.z-1 remaining combinations (the first combination being assumed to have been tried).

(19) Returning to the example of FIG. 2, the order of the noise patterns is determined by evaluating a cost for flipping information—the cost for flipping information for the least reliable bits being less than the cost for flipping information for more reliable bits. One simple cost function is based on a sum of the rank ordered positions (from 1 to 13 in FIG. 2) of bits to be flipped and comparing those sums. Thus, the most likely putative error sequence is no bit flips, followed by the sequence with only the most likely i.e. unreliable bit being flipped, followed by the sequence with only the second most unreliable bit flipped, followed by a tie, broken arbitrarily, between the sequence with the third most unreliable bit alone flipped and the sequence with first and second most unreliable bits both being flipped, and so forth.

(20) Thus, flipping the bit in position 1 i.e. the least reliable bit in a group of bits, has a lower value than flipping the bit in position 2 i.e. the second least reliable bit in a group of bits, and so this bit is flipped first and the bit in position 2 flipped next.

(21) As explained, using the simple sum criterion, leads to a tie between flipping both the least and second least reliable bits; or flipping just the 3rd least reliable bit. This tie as well as others can be broken arbitrarily so that in the example of FIG. 2, the 3rd noise pattern employed involves flipping the first and second least reliable bits, before then flipping the 3rd least reliable bit, if flipping using the previous noise patterns have not resulted in a valid codeword.

(22) Other noise models may place an additional likelihood penalty or cost on sequences that have more bits flipped and such models could plausibly provide a better approximation for higher quality channels. In this case, the third least reliable bit would be flipped before the combination of first and second bits least reliable bits would be flipped, because this involved fewer flips.

(23) Still further variations of noise model of FIG. 2 are also possible and these can be based on a priori knowledge of the characteristics of a given transmission channel or on characteristics which are learnt, causing the order of the noise patterns within the sequence to change to promote patterns which are more likely to contain a noise pattern (and so cost less to flip) affecting a demodulated group of symbols.

(24) In any case, it will be seen that in contrast to the approach of GRAND and SRGRAND, knowing the ranked order of reliability of demodulated information means that information for more unreliable bits can be flipped before information for more reliable bits is flipped. So, whereas in the example of FIG. 2, information for the most reliable symbol in position 13 is only flipped after more than 80 noise patterns into the sequence, using GRAND or SRGRAND (where all bits were flagged as unreliable), this bit would tend to be flipped after only 13 patterns into a sequence. Similarly, knowing the ranked order of reliability of demodulated information means that information for the two most unreliable bits can be examined by flipping their information with the 3.sup.rd (or 4.sup.th) noise pattern in a sequence, whereas using GRAND or SRGRAND, this could not happen until only after 13 patterns in a sequence and perhaps the 26.sup.th pattern.

(25) This improved application of potential noise patterns to demodulated information is possible using embodiments of the invention which need not assume any further information about either the received signal or the channel noise model than the soft information provided by the demodulator 22.

(26) The above embodiment has been described in terms of rank ordering the reliability of symbols within a group of n symbols and flipping bit information for those symbols in accordance with a sequence of noise patterns and the ranked reliability of the symbols.

(27) In variations of the invention, rather than rank order the reliability of demodulated symbols which may correspond with one or more bits of decoded information, the soft information provided from the demodulator 22 can instead rank order demodulated bits directly. Thus, as before, the demodulator 22 needs to pass no more than log.sub.2(n) bits of code-book independent soft information per demodulated bit to the decoder 24. (Again, for values of n which are not powers of two, a slightly higher number, the smallest integer that is larger than log.sub.2 (n) bits of soft information, are required for each bit.)

(28) The demodulated bits can then be ranked from the most unreliable to the most reliable using the soft information and the sequence of noise patterns, such as shown in FIG. 2 for groups of 13 bits, can be applied to the demodulated bits until a valid codeword is detected.

(29) Again, to reduce the amount of soft information which needs to be passed to the decoder 24 for a group of n bits, techniques such as disclosed above including agreeing the order of possible permutations of the bits or using knowledge of the query threshold T to limit the soft information to the ranked order of only the most unreliable bits can be used.

(30) Again, it will be appreciated that the above described processes lend themselves to parallelization so that for example, a number of decoders can apply a plurality of noise patterns simultaneously to the demodulated symbols provided by the demodulator.