METHOD FOR PERFORMING BELIEFS PROPAGATION, COMPUTER PROGRAM PRODUCT, NON-TRANSITORY INFORMATION STORAGE MEDIUM, AND POLAR CODE DECODER

Abstract

A decoder performs: computing (S501) a value (i,j) of a performance-improvement metric for each kernel K.sub.i,j; and sorting (S502) the kernels in a list in decreasing order of the values (i,j). The decoder then performs a beliefs propagation iterative process as follows: updating (S503) output beliefs for the W top kernels of the list , and propagating said output beliefs as input beliefs of the neighbour kernels of said W top kernels; updating (S504) output beliefs for each neighbour kernel of said W top kernels following update of their input beliefs, and re-computing (S505) the performance-improvement metric value (i,j) for each said neighbour kernel; setting (S505) the performance-improvement metric for said W top kernels to a null value; and re-ordering (S506) the kernels in the list . Then, the decoder repeats the beliefs propagation iterative process until a stop condition is met.

Claims

1. A method for performing beliefs propagation in a scope of polar code decoding by a decoder, the polar code having a size of N bits and being based on a structure of L sub-polarization stages of N/2 parallel kernels K.sub.i,j, wherein N and L being positive integers such that N=2.sup.L, wherein i is an index that identifies the sub-polarization stage of the kernel K.sub.i,j and j is an index that represents the position of said kernel K.sub.i,j among the N/2 parallel kernels at the sub-polarization stage identified by the index i, the N/2 parallel kernels at each sub-polarization stage are separated from their neighbour N/2 parallel kernels at each adjacent sub-polarization stage by a shuffler (Φ.sub.i), characterized in that the decoder performs: computing a value (i,j) of a performance-improvement metric for each kernel K.sub.i,j of the structure, wherein the performance-improvement metric is representative of a magnitude in which the input beliefs of the considered kernel K.sub.i,j are not in agreement and/or the performance-improvement metric is representative of a magnitude in which the output beliefs of the considered kernel K.sub.i,j bring instantaneous information rate to the neighbour kernels of said considered kernel K.sub.i,j; and sorting the kernels in a list in decreasing order of the values (i,j) of the performance-improvement metric ; further in that the decoder performs a beliefs propagation iterative process as follows: updating output beliefs for the W top kernels of the list , wherein W is a positive integer, and propagating said output beliefs as input beliefs of neighbour kernel of said W top kernels; updating output beliefs for each neighbour kernel of said W top kernels following update of their input beliefs, and re-computing the performance-improvement metric value (i,j) for each said neighbour kernel; setting the performance-improvement metric for said W top kernels to a null value; and re-ordering the kernels in the list in decreasing order of the values (i,j) of the performance-improvement metric ; and in that the decoder repeats the beliefs propagation iterative process until a stop condition is met.

2. The method according to claim 1, wherein the value (i,j) of the performance-improvement metric for each kernel K.sub.i,j depends on a difference between the sum of the information rate associated to the input beliefs of said kernel K.sub.i,j, and the sum of the information rate associated to each input belief of said kernel K.sub.i,j before the previous update of said kernel K.sub.i,j.

3. The method according to claim 2, wherein the value (i,j)=.sup.(1)(i, j) of the performance-improvement metric for each kernel K.sub.i,j is defined as follows ${\left(1\right)}^{}\left(i,j\right)=.Math.m_{i,j}^{\left(1\right)}-m_{i,j}^{\left(1\right)\mathrm{old}}.Math.$ $\mathrm{wherein}$ $m_{i,j}^{\left(1\right)}=1-\frac{1}{4}\left({\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{out}\right)}}\right)\right)$ wherein L.sub.i,2j−1:2j.sup.(in) are the input beliefs coming from the sub-polarization stage i−1 and L.sub.i,2j−1:2j.sup.(out) are the in the input beliefs coming from sub-polarization stage i+1, and wherein m.sub.i,j.sup.(1) becomes m.sub.i,j.sup.(1)old after each effective update of the kernel K.sub.i,j, during which the output beliefs {circumflex over (L)}.sub.i,2j−1:2j.sup.(in) and {circumflex over (L)}.sub.i,2j−1:2j.sup.(out) are computed from the input beliefs L.sub.i,2j−1:2j.sup.(in) and L.sub.i,2j−1:2j.sup.(out), so as to be used in a later update of the performance-improvement metric value (i, j)=.sup.(1)(i,j), and wherein m.sub.i,j.sup.(1)old=0 at the very first computation of the performance-improvement metric value .sup.(1) (i, j) for the kernel K.sub.i,j.

4. The method according to claim 1, wherein the value (i,j) of the performance-improvement metric for each kernel K.sub.i,j depends on a sum rate difference between the sum of the information rate associated to input ex post beliefs of said kernel K.sub.i,j, and the sum of the information rate associated to input ex post beliefs of said kernel K.sub.i,j before the previous update of said kernel K.sub.i,j, wherein ex-post belief is a sum of a-priori beliefs and extrinsic beliefs.

5. The method according to claim 4, wherein the value (i,j)=.sup.(2)(i, j) of the performance-improvement metric for each kernel K.sub.i,j is defined as follows ${\left(2\right)}^{}\left(i,j\right)=.Math.m_{i,j}^{\left(2\right)}-m_{i,j}^{\left(2\right)\mathrm{old}}.Math.$ $\mathrm{wherein}$ $m_{i,j}^{\left(2\right)}=1-\frac{1}{4}\left({\log }_2\left(1+e^{-\left(L_{i,2j-1}^{\left(\mathrm{in}\right)}+{\hat{L}}_{i,2j-1}^{\left(\mathrm{in}\right)\mathrm{old}}\right)}\right)+{\log }_2\left(1+e^{-\left(L_{i,2j}^{\left(\mathrm{in}\right)}+{\hat{L}}_{i,2j}^{\left(\mathrm{in}\right)\mathrm{old}}\right)}\right)+{\log }_2\left(1+e^{-\left(L_{i,2j-1}^{\left(\mathrm{out}\right)}+{\hat{L}}_{i,2j-1}^{\left(\mathrm{out}\right)\mathrm{old}}\right)}\right)+{\log }_2\left(1+e^{-\left(L_{i,2j}^{\left(\mathrm{out}\right)}+{\hat{L}}_{i,2j}^{\left(\mathrm{out}\right)\mathrm{old}}\right)}\right)\right)$ wherein L.sub.i,2j−1:2j.sup.(in) are the input beliefs coming from the sub-polarization stage i−1 and L.sub.i,2j−1:2j.sup.(out) are the input beliefs coming from the sub-polarization stage i+1, and wherein {circumflex over (L)}.sub.i,2j−1:2j.sup.(in)old represents the immediately preceding respective values of {circumflex over (L)}.sub.i,2j−1:2j.sup.(in) which are the output beliefs toward the sub-polarization stage i−1, and {circumflex over (L)}.sub.i,2j−1:2j.sup.(out)old represents the immediately preceding respective values of {circumflex over (L)}.sub.i,2j−1:2j.sup.(out) which are the output beliefs toward the sub-polarization stage i+1.

6. The method according to claim 1, wherein the value (i,j) of the performance-improvement metric for each kernel K.sub.i,j depends on an increase of information output by the kernel K.sub.i,j during the last update of said kernel K.sub.i,j.

7. The method according to claim 6, wherein the value (i, j)=.sup.(3) (i, j) of the performance-improvement metric for each kernel K.sub.i,j is defined as follows ${\left(3\right)}^{}\left(i,j\right)=.Math.{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{in}\right)}}\right)-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{out}\right)}}\right).Math.$ and wherein {circumflex over (L)}.sub.i,2j−1:2j.sup.(in) are the output beliefs toward the sub-polarization stage i−1, and {circumflex over (L)}.sub.i,2j−1:2j.sup.(out) are the output beliefs toward the sub-polarization stage i+1.

8. The method according to claim 2, wherein the value (i,j) of the performance-improvement metric for each kernel K.sub.i,j further depends on an increase of information output by the kernel K.sub.i,j during the last update of said kernel K.sub.i,j.

9. The method according to claim 8, wherein the value (i, j)=.sup.(1)(i,j)+.sup.(3)(i,j) of the performance-improvement metric for each kernel K.sub.i,j is defined as follows ${\left(1\right)}^{}\left(i,j\right)=.Math.m_{i,j}^{\left(1\right)}-m_{i,j}^{\left(1\right)\mathrm{old}}.Math.$ $\mathrm{wherein}$ $m_{i,j}^{\left(1\right)}=1-\frac{1}{4}\left({\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{out}\right)}}\right)\right)$ $\mathrm{and}$ ${\left(3\right)}^{}\left(i,j\right)=.Math.{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{in}\right)}}\right)-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{out}\right)}}\right).Math.$ wherein L.sub.i,2j−1:2j.sup.(in) are the input beliefs coming from the sub-polarization stage i−1 and L.sub.i,2j−1:2j.sup.(out) are the input beliefs coming from the sub-polarization stage i+1, wherein {circumflex over (L)}.sub.i,2j−1:2j.sup.(in) are the output beliefs toward the sub-polarization stage i−1, and {circumflex over (L)}.sub.i,2j−1:2j.sup.(out) are the output beliefs toward the sub-polarization stage i+1, and wherein m.sub.i,j.sup.(1) becomes m.sub.i,j.sup.(1)old each effective update of the kernel K.sub.i,j, during which the output beliefs {circumflex over (L)}.sub.i,2j−1:2j.sup.(in) and {circumflex over (L)}.sub.i,2j−1:2j.sup.(out) are computed from the input beliefs L.sub.i,2j−1:2j.sup.(in) and L.sub.i,2j−1:2j.sup.(out) so as to be used in a later update of the performance-improvement metric value (i, j)=.sup.(1)(i,j), and wherein m.sub.i,j.sup.(1)old=0 at the very first computation of the performance-improvement metric value .sup.(1) (i, j) for the kernel K.sub.i,j.

10. The method according to claim 8, wherein the value (i,j)=.sup.(1) (i, j).Math..sup.(3) (i, j) of the performance-improvement metric for each kernel K.sub.i,j is defined as follows ${\left(1\right)}^{}\left(i,j\right)=.Math.m_{i,j}^{\left(1\right)}-m_{i,j}^{\left(1\right)\mathrm{old}}.Math.$ $\mathrm{wherein}$ $m_{i,j}^{\left(1\right)}=1-\frac{1}{4}\left({\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{out}\right)}}\right)\right)$ $\mathrm{and}$ ${\left(3\right)}^{}\left(i,j\right)=.Math.{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{in}\right)}}\right)-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{out}\right)}}\right).Math.$ wherein L.sub.i,2j−1:2j.sup.(in) are the input beliefs coming from the sub-polarization stage i−1 and L.sub.i,2j−1:2j.sup.(out) beliefs coming from the sub-polarization stage i+1 i, wherein {circumflex over (L)}.sub.i,2j-1:2j.sup.(in) are the output beliefs toward the sub-polarization stage i−1, and {circumflex over (L)}.sub.i,2j−1:2j.sup.(out) are the output beliefs toward the sub-polarization stage i+1, and wherein m.sub.i,j.sup.(1) becomes m.sub.i,j.sup.(1)old after each effective update of the kernel K.sub.i,j, during which the output beliefs {circumflex over (L)}.sub.i,2j−1:2j.sup.(in) and {circumflex over (L)}.sub.i,2j−1:2j.sup.(out) are computed from the input beliefs L.sub.i,2j−1:2j.sup.(in) and L.sub.i,2j−1:2j.sup.(out) so as to be used in a later update of the performance-improvement metric value (i,j)=.sup.(1)(i,j), and wherein m.sub.i,j.sup.(1)old=0 at the very first computation of the performance-improvement metric value .sup.(1)(i,j) for the kernel K.sub.i,j.

11. The method according to claim 1, wherein the stop condition is met when one of the following conditions is fulfilled: when a time period of predefined duration has ended since the beliefs propagation iterative process has started; when a predefined quantity of iterations has been performed in the beliefs propagation iterative process; and when the value (i,j) of the performance-improvement metric of the kernel at the top position in the list is below a predefined threshold.

12. A computer program product comprising program code instructions that can be loaded in a programmable device for implementing the method according to claim 1, when the program code instructions are run by the programmable device.

13. Non-transitory information storage medium storing a computer program comprising program code instructions that can be loaded in a programmable device for implementing the method according to claim 1, when the program code instructions are run by the programmable device.

14. A polar code decoder configured for performing beliefs propagation in a scope of polar code decoding, the polar code having a size of N bits and being based on a structure of L sub-polarization stages of N/2 parallel kernels K.sub.i,j, wherein N and L being positive integers such that N=2.sup.L, wherein i is an index that identifies the sub-polarization stage of the kernel K.sub.i,j and j is an index that represents the position of said kernel K.sub.i,j among the N/2 parallel kernels at the sub-polarization stage identified by the index i, the N/2 parallel kernels at each sub-polarization stage are separated from their neighbour N/2 parallel kernels at each adjacent sub-polarization stage by a shuffler (Φ.sub.i), characterized in that the decoder comprises: a calculator to compute a value (i,j) of a performance-improvement metric for each kernel K.sub.i,j of the structure, wherein the performance-improvement metric is representative of a magnitude in which the input beliefs of the considered kernel K.sub.i,j are not in agreement and/or the performance-improvement metric is representative of a magnitude in which the output beliefs of the considered kernel K.sub.i,j bring instantaneous information rate to the neighbour kernels of said considered kernel K.sub.i,j; and a sorter to sort the kernels in a list in decreasing order of the values (i,j) of the performance-improvement metric ; further in that the decoder comprises a processor to perform a beliefs propagation iterative process including: a first updater to update output beliefs for the W top kernels of the list , wherein W is a positive integer, and propagating said output beliefs as input beliefs of neighbour kernel of said W top kernels; a second updater to update output beliefs for each neighbour kernel of said W top kernels following update of their input beliefs, and re-computing the performance-improvement metric value (i,j) for each said neighbour kernel; a setter to set the performance-improvement metric for said W top kernels to a null value; and a sequencer to re-order the kernels in the list in decreasing order of the values (i,j) of the performance-improvement metric ; and in that the decoder is further configured for repeating the beliefs propagation iterative process until a stop condition is met.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0058] FIG. 1 schematically represents a system including a polar code encoder and a corresponding polar code decoder.

[0059] FIG. 2A schematically represents an encoding part of the encoder according to the prior art.

[0060] FIG. 2B schematically represents a sub-polarization stage of the encoding part according to the prior art.

[0061] FIG. 3 schematically represents a binary kernel structure as used in the encoding part according to the prior art.

[0062] FIG. 4A schematically represents a modular architecture of the decoding part according to the prior art.

[0063] FIG. 4B schematically represents a decoding algorithm according to the prior art.

[0064] FIG. 4C schematically represents a factor graph applied to the kernel structure schematically shown in FIG. 3.

[0065] FIG. 4D schematically represents a beliefs propagation algorithm according to the prior art.

[0066] FIG. 5 schematically represents a beliefs propagation algorithm according to the present invention.

[0067] FIG. 6 schematically represents an exemplary embodiment of hardware architecture for implementing the beliefs propagation algorithm according to the present invention.

[0068] FIG. 7 schematically represents a particular embodiment of the beliefs propagation algorithm according to the present invention.

DESCRIPTION OF EMBODIMENTS

[0069] In the scope of the present invention, polar code encoding and transmission over BDMC are performed in accordance with the description provided hereinbefore with respect to FIGS. 1, 2A, 2B, 2C and 3. Polar code decoding is performed in accordance with the description provided hereinbefore with respect to FIGS. 4A, 4B and 4C. Beliefs propagation is however performed as detailed hereinafter with respect to FIGS. 5, 6 and 7.

[0070] In general, the mutual information I(x′; y′) of a BDMC with input x′, output y′ (i.e. observations), and probability function P(y′ Ix′) characterizing channel transitions probabilities, is defined as follows:

I(x′;y′)=1−E.sub.L′[log.sub.2(1+e.sup.−L′)]

where E.sub.L′[ ] represents the mathematical expectation over the random variable L′ called Log Likelihood Ratio (LLR) and defined as follows:

L′=log(P(y′|x′)/P(y′|1−x′))

wherein P(y′|x′) and P(y′|1−x′) both depend on the input bits and output channel observations.

[0071] Let us define instantaneous information rate as 1−log.sub.2(1+e.sup.−L′), i.e. the mathematical expectation of the instantaneous information rate provides the mutual information I (x′; y′).

[0072] Let us consider the kernel K.sub.i,j. Each output on the right size of the kernel (as represented in FIG. 3) is associated with a BDMC encompassing all the effects of the combinations of inputs and outputs of other kernels located at the depth positions from i+1 to L toward the transmission channel. Indeed, the operations performed by each kernel are binary operations, which does not change the BDMC nature of the channel.

[0073] Let I (x.sub.i,2j−1.sup.(out); y.sub.i,2j−1:2j) be mutual information between the bit x.sub.i,2j−1.sup.(out) and a channel observation vector y.sub.i,2j−1:2j. Let also I(x.sub.i,2j.sup.(out); y.sub.i,2j−1:2j) be mutual information between the bit x.sub.i,2j.sup.(out) and the channel observation vector y.sub.i,2j−1:2j. Let also I(x.sub.i,2j−1.sup.(in); y.sub.i,2j−1:2j) be mutual information between the bit x.sub.i,2j−1.sup.(in) and the channel observation vector y.sub.i,2j−1:2j. Let also I(x.sub.i,2j.sup.(in); y.sub.i,2j−1:2j|x.sub.i,2j−1.sup.(in)) be the mutual information between the bit x.sub.i,2j.sup.(in) and the channel observation vector y.sub.i,2j−1:2j knowing without error the bit x.sub.i,2j−1.sup.(in). As a result of the polarization operation and due to the BDMC nature of the channel, the following relationship exists:

[00012]$I\left(x_{i,2j-1}^{\left(\mathrm{in}\right)};y_{i,2j-1\text{:}2j}\right)+I\left(x_{i,2j}^{\left(\mathrm{in}\right)};y_{i,2j-1\text{:}2j}.Math.x_{i,2j-1}^{\left(\mathrm{in}\right)}\right)=I\left(x_{i,2j-1}^{\left(\mathrm{out}\right)};y_{i,2j-1\text{:}2j}\right)+I\left(x_{i,2j}^{\left(\mathrm{out}\right)};y_{i,2j-1\text{:}2j}\right)$

which is the capacity conservation property of the considered kernel, under the assumption that x.sub.i,2j−1.sup.(in) is correctly decoded before trying to decode x.sub.i,2j.sup.(in).

[0074] It is worth noting that, if L.sub.i,2j.sup.(in)=0, L.sub.i,2j−1.sup.(in)=(−1).sup.x.sup.i,2j−1.sup.(in).sup.+1×+∞, then from the computation rules of each kernel described with respect to the step S471, the following relationship can be expressed:

[00013]$1-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+1-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{in}\right)}}\right)=1-{\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)+1-{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{out}\right)}}\right)$

which involves that the conservation property is also achieved instantaneously (i.e. without the mathematical expectation being present in the information rates). This property teaches that if a kernel reaches this property after updating {circumflex over (L)}.sub.i,2j−1.sup.(in) and {circumflex over (L)}.sub.i,2j.sup.(in) from L.sub.i,2j−1.sup.(out) and L.sub.i,2j.sup.(out), then the beliefs L.sub.i,2j−1.sup.(out) and L.sub.i,2j.sup.(out) are in perfect agreement, which involves that the kernel is stable from iterative processing point of view. Since the kernel operations are symmetric (left to right or right to left), the same observation applies with the comparison of {circumflex over (L)}.sub.i,2j−1.sup.(out) and {circumflex over (L)}.sub.i,2j.sup.(out) with L.sub.i,2j−1.sup.(in) and L.sub.i,2j.sup.(in).

[0075] As a result, in a particular embodiment, metrics of stability of the kernel can consequently be derived and priority can be given to kernels for which the input beliefs are not in agreement, and which will provide a higher update to their neighbour kernels than other kernels that already are stable.

[0076] Moreover, in a particular embodiment, priority can be given to kernels manipulating beliefs with high instantaneous information rate, that will feed their neighbour kernels with more relevant and robust information.

[0077] By defining corresponding metrics as described hereafter, priority is given to processing the kernels providing the most beneficial increase to the decoding performance, and thus reduces complexity of the decoding process for a given performance target.

[0078] FIG. 5 schematically represents a beliefs propagation algorithm according to the present invention.

[0079] In a step S501, the decoder 120 computes a value (i,j) of a performance-improvement metric for each kernel K.sub.i,j (identified by the couple (i,j), ∀i, j), wherein i is an index such that 0<i≤L and j is an index such that 0<j≤N/2. In other words, the index i represents the depth position (sub-polarization stage) of the considered kernel K.sub.i,j identified by the couple (i,j) in the structure of the polar code and j represents the position of said considered kernel among the N/2 parallel kernels at the structure depth position (sub-polarization stage) identified by the index i.

[0080] As expressed by the embodiments detailed hereafter, the performance-improvement metric is representative of a magnitude in which the input beliefs of the considered kernel K.sub.i,j are not in agreement (i.e. the higher value (i,j) of the performance-improvement metric , the higher difference between the input beliefs) and/or the performance-improvement metric is representative of a magnitude in which the output beliefs of the considered kernel K.sub.i,j bring instantaneous information rate to the neighbour kernels of said considered kernel K.sub.i,j (i.e. the higher value (i,j) of the performance-improvement metric , the higher instantaneous information rate).

[0081] According to a first embodiment, the performance-improvement metric value (i, j) for each kernel K.sub.i,j (thus identified by the couple (i,j)) depends on a difference between the sum of the information rate associated to the input beliefs of said kernel K.sub.i,j, and the sum of the information rate associated to each input belief of said kernel K.sub.i,j before the previous update of said kernel K.sub.i,j.

[0082] In a particular example of the first embodiment, the performance-improvement metric value (i, j)=.sup.(1)(i,j) is defined as follows in the first embodiment:

[00014]${\left(1\right)}^{}\left(i,j\right)=.Math.m_{i,j}^{\left(1\right)}-m_{i,j}^{\left(1\right)\mathrm{old}}.Math.$$\mathrm{wherein}$$m_{i,j}^{\left(1\right)}=1-\frac{1}{4}\left({\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)+{\log }_2\left(1+e^{-L_{i,2j}^{\left(\mathrm{out}\right)}}\right)\right)$

and wherein m.sub.i,j.sup.(1) becomes m.sub.i,j.sup.(1)old after each effective update of the kernel K.sub.i,j, during which the output beliefs {circumflex over (L)}.sub.i,2j−1:2j.sup.(in) and {circumflex over (L)}.sub.i,2j−1:2j.sup.(out) are computed) from the input beliefs L.sub.i,2j−1:2j.sup.(in) and L.sub.i,2j−1:2j.sup.(out), so as to be used in a later update of the performance-improvement metric value (i,j)=.sup.(1)(i,j), and wherein m.sub.i,j.sup.(1)old=0 at the very first computation of the performance-improvement metric value .sup.(1)(i,j) for the kernel K.sub.i,j.

[0083] When at least one input of the kernel K.sub.i,j has been updated after update of a neighbour kernel connect thereto, the kernel identified K.sub.i,j should also be updated. Sometimes, the update of the kernel K.sub.i,j has no significant change on the overall polar code performance, which involves that priority of update of the kernel K.sub.i,j is lower than priority of update of another kernel that experiences a drastic change in one of its inputs. The performance-improvement metric values (i,j)=.sup.(1)(i,j) thus quantitatively allow managing priorities between updates of kernels.

[0084] According to a second embodiment, the performance-improvement metric value (i,j) for each kernel K.sub.i,j (thus identified by the couple (i,j)) depends on a sum rate difference between the sum of the information rate associated to input ex post beliefs of said kernel K.sub.i,j, and the sum of the information rate associated to input ex post beliefs of said kernel K.sub.i,j before the previous update of said kernel K.sub.i,j. Ex post belief is a sum of a-priori beliefs and extrinsic beliefs, which are characterized for example for the input identified by 2j−1 (which is the first input of the kernel K.sub.i,j, the input identified by 2j being the second input of the kernel K.sub.i,j) by L.sub.i,2j−1.sup.(in)+{circumflex over (L)}.sub.i,2j−1.sup.(in)old, wherein L.sub.i,2j−1.sup.(in) represents here the corresponding extrinsic belief and wherein {circumflex over (L)}.sub.i,2j−1.sup.(in)old represents here the corresponding a-priori belief.

[0085] In a particular example of the second embodiment, the performance-improvement metric value (i,j)=.sup.(2)(i, j) is defined as follows in the second embodiment:

[00015]${\left(2\right)}^{}\left(i,j\right)=.Math.m_{i,j}^{\left(2\right)}-m_{i,j}^{\left(2\right)\mathrm{old}}.Math.$$\mathrm{wherein}$$m_{i,j}^{\left(2\right)}=1-\frac{1}{4}\left({\log }_2\left(1+e^{-\left(L_{i,2j-1}^{\left(\mathrm{in}\right)}+{\hat{L}}_{i,2j-1}^{\left(\mathrm{in}\right)\mathrm{old}}\right)}\right)+{\log }_2\left(1+e^{-\left(L_{i,2j}^{\left(\mathrm{in}\right)}+{\hat{L}}_{i,2j}^{\left(\mathrm{in}\right)\mathrm{old}}\right)}\right)+{\log }_2\left(1+e^{-\left(L_{i,2j-1}^{\left(\mathrm{out}\right)}+{\hat{L}}_{i,2j-1}^{\left(\mathrm{out}\right)\mathrm{old}}\right)}\right)+{\log }_2\left(1+e^{-\left(L_{i,2j}^{\left(\mathrm{out}\right)}+{\hat{L}}_{i,2j}^{\left(\mathrm{out}\right)\mathrm{old}}\right)}\right)\right)$

and wherein {circumflex over (L)}.sub.i,2j−1.sup.(in)old represents the immediately preceding value of {circumflex over (L)}.sub.i,2j−1.sup.(in), {circumflex over (L)}.sub.i,2j.sup.(in)old represents the immediately preceding value of {circumflex over (L)}.sub.i,2j.sup.(in), {circumflex over (L)}.sub.i,2j−1.sup.(out)old represents the immediately preceding value of {circumflex over (L)}.sub.i,2j−1.sup.(out), and {circumflex over (L)}.sub.i,2j.sup.(out)old represents the immediately preceding value of L.sub.i,2j.sup.(out).

[0086] This second embodiment is close to the first embodiment, but keeps memory of the last LLR values provided to or resulting from computation of each input/output of each kernel K.sub.i,j, ∀i, j. For example, by summing L.sub.i,2j−1.sup.(in) and {circumflex over (L)}.sub.i,2j−1.sup.(in)old, information related to the ex-post belief instead of the extrinsic belief provided by L.sub.i,2j−1.sup.(in) solely considered (as in the first embodiment) is obtained. In order to implement the second embodiment, the decoder 120 needs to store in memory {circumflex over (L)}.sub.i,2j−1.sup.(in), {circumflex over (L)}.sub.i,2j.sup.(in) on one hand and {circumflex over (L)}.sub.i,2j−1.sup.(out), {circumflex over (L)}.sub.i,2j.sup.(out) on the other hand, at each computation of each input/output of each kernel K.sub.i,j, ∀i, j. The stored beliefs respectively become {circumflex over (L)}.sub.i,2j−1.sup.(in)old, {circumflex over (L)}.sub.i,2j.sup.*in)old on one hand and {circumflex over (L)}.sub.i,2j−1.sup.(out)old, {circumflex over (L)}.sub.i,2j.sup.(out)old on the other hand, for a subsequent processing of said kernel K.sub.i,j.

[0087] According to a third embodiment, the performance-improvement metric (i,j) for each kernel K.sub.i,j (thus identified by the couple (i,j)) depends on an increase of information output by the kernel K.sub.i,j during the last update of said kernel K.sub.i,j.

[0088] In a particular example of the third embodiment, the performance-improvement metric (i,j)=.sup.(3)(i,j) is defined as follows in the third embodiment:

[00016]${\left(3\right)}^{}\left(i,j\right)=.Math.{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{in}\right)}}\right)+{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{in}\right)}}\right)-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j-1}^{\left(\mathrm{out}\right)}}\right)-{\log }_2\left(1+e^{-{\hat{L}}_{i,2j}^{\left(\mathrm{out}\right)}}\right).Math.$

[0089] According to a fourth embodiment, the performance-improvement metric (i,j) for each kernel identified by the couple (i,j) is such that (i,j)=.sup.(1)(i,j)+.sup.(3)(i,j).

[0090] According to a fifth embodiment, the performance-improvement metric (i,j) for each kernel identified by the couple (i,j) is such that (i,j)=.sup.(1) (i, j).Math..sup.(3) (i, j).

[0091] In a step S502, the decoder 120 sorts the kernel in a list in decreasing order of the performance-improvement metric .

[0092] Then starts a beliefs propagation iterative process that is repeated until a stop condition is met, as detailed hereafter.

[0093] In a step S503, the decoder 120 updates the LLRs for the W top kernels in the list , wherein W is a positive integer such that 0<W<L.Math.N/2, i.e. the W kernels having the highest performance-improvement metric . In a preferred embodiment, W=1.

[0094] In a step S504, the decoder 120 updates the LLRs for each neighbour kernel of said W top kernels in the list .

[0095] In a step S505, the decoder 120 sets the performance-improvement metric for the W top kernels in the list to a null value, since said kernels have been processed, and re-computes the performance-improvement metric of their neighbour kernels.

[0096] In a step S506, the decoder 120 reorders the kernels in the list following the changes made on the performance-improvement metric in the step S505, still in decreasing order of the performance-improvement metric .

[0097] In a step S507, the decoder 120 checks whether the stop condition is met.

[0098] According to a first embodiment, the stop condition is met when a time period of predefined duration has ended since the algorithm of FIG. 5 has been launched.

[0099] According to a second embodiment, the stop condition is met when a predefined quantity of iterations has been performed since the algorithm of FIG. 5 has been launched (i.e. number of times that the step S503 has been executed since the algorithm of FIG. 5 has been launched).

[0100] According to a third embodiment, the stop condition is met when the performance-improvement metric of the kernel at the top position in the list is below a predefined threshold α. Defining the threshold α allows tuning a trade-off between decoding performance and decoding complexity (i.e. time and/or processing resources used).

[0101] When the stop condition is met, the beliefs propagation process ends and a step S508 is performed; otherwise, the step S503 is repeated (new iteration of the beliefs propagation iterative process) with the list that has been reordered in the step S506.

[0102] In the step S508, the decoder 120 makes a decoding decision in view of the beliefs propagation achieved by execution of the preceding steps of the algorithm of FIG. 5.

[0103] FIG. 6 schematically represents an exemplary embodiment of hardware architecture for implementing the beliefs propagation algorithm according to the present invention. According to the shown architecture, the decoder 120 comprises the following components interconnected by a communications bus 610: a processor, microprocessor, CPU 600, or a GPU; a RAM (Random-Access Memory) 601; a ROM (Read-Only Memory) 602; an SD (Secure Digital) card reader 603, or any other device adapted to read information stored on a non-transitory storage medium, such as an HDD (Hard Disk Drive); and, a communication interface 604 with BDMC onto which polar codes are used during transmissions performed by the encoder 100.

[0104] CPU 600 is capable of executing instructions loaded into RAM 601 from ROM 602 or from an external memory, such as an HDD or an SD card. After the decoder 120 has been powered on, CPU 600 is capable of reading instructions from RAM 601 and executing these instructions that form one computer program.

[0105] The steps performed by the decoder 120 may be implemented in software by execution of a set of instructions or program by a programmable computing machine, such as a PC (Personal Computer), a DSP (Digital Signal Processor) or a GPU (Graphics Processing Unit). Indeed, nowadays, GPUs are increasingly used for non-graphical calculations, since they are well-suited to other massive computing parallel problems than in traditional image-related processing. Advantageously, CPU 600 or GPU can perform polar code decoding, including notably the beliefs propagation, during inactivity time of processing resources which usually occur when inter-memory transfers are scheduled.

[0106] FIG. 7 schematically represents a particular embodiment of the beliefs propagation algorithm according to the present invention.

[0107] In a step S701, the decoder 120 by way of its belief propagation decoder 422, initiates a call for achieving beliefs propagation for the input beliefs L.sub.i,j.sup.(in) and so as to get the output beliefs {circumflex over (L)}.sub.i,j.sup.(in) and {circumflex over (L)}.sub.i,j.sup.(out), ∀i,j′ such that 0<i≤L and 0<j′≤N (the index j′ is used here because the index j can not be used here since its maximum value is N/2).

[0108] In a step S702, the decoder 120 sets {circumflex over (L)}.sub.i,j′.sup.(in) and L.sub.i,j′.sup.(out) to a null value, ∀i,j′.

[0109] In a step S703, the decoder 120 computes the performance-improvement metric for each kernel K.sub.i,j (thus identified by the couple (i,j), ∀i,j′ such that 0<i≤L and 0<j≤N/2, as already described with respect to FIG. 5.

[0110] In a step S704, the decoder 120 sorts the kernel in the list in decreasing order of the performance-improvement metric .

[0111] In a step S705, the decoder 120 extracts the W top kernels in the list .

[0112] In a step S706, the decoder 120 computes the output beliefs as follows, for each kernel K.sub.i,j among the W extracted kernels:

{circumflex over (L)}.sub.i,2j−1.sup.(in)=.sub.1.sup.(in)(L.sub.i,2j−1:2j.sup.(in),L.sub.i,2j−1:2j.sup.(out))

{circumflex over (L)}.sub.i,2j.sup.(in)=.sub.2.sup.(in)(L.sub.i,2j−1:2j.sup.(in),L.sub.i,2j−1:2j.sup.(out))

{circumflex over (L)}.sub.i,2j−1.sup.(out)=.sub.1.sup.(out)(L.sub.i,2j−1:2j.sup.(in),L.sub.i,2j−1:2j.sup.(out))

{circumflex over (L)}.sub.i,2j.sup.(out)=.sub.2.sup.(out)(L.sub.i,2j−1:2j.sup.(in),L.sub.i,2j−1:2j.sup.(out))

[0113] In a step S707, the decoder 120 resets the performance-improvement metric for each kernel that has been extracted from the list in the step S705. The performance-improvement metric becomes then null for these kernels.

[0114] In a step S708, the decoder 120 updates the LLRs for the neighbour kernels of the W kernels that have been extracted from the list in the step S705, as follows: [0115] when i<L, {circumflex over (L)}.sub.i,2j−1.sup.(out) is propagated as L.sub.i+1, j″.sup.(in), wherein j″ represents in this statement the position of the neighbour kernel at the depth position i+1 (sub-polarization stage) which is connected to the output 2j−1 of the kernel K.sub.i,j via the shuffler Φ.sub.i (which, in this direction of propagation, refers to the shuffling operation φ.sub.i) at the depth position i (sub-polarization stage); [0116] when i<L, {circumflex over (L)}.sub.i,2j.sup.(out) is propagated as L.sub.i+1,j″.sup.(in)(in).sub.i, wherein j″ represents in this statement the position of the neighbour kernel at the depth position i+1 (sub-polarization stage) which is connected to the output 2j of the kernel K.sub.i,j via the shuffler Φ.sub.i (which, in this direction of propagation, refers to the shuffling operation φ.sub.i) at the depth position i (sub-polarization stage); [0117] when i>1, {circumflex over (L)}.sub.i,2j−1.sup.(in) is propagated as L.sub.i−1,j″.sup.(out), wherein j″ represents in this statement the position of the neighbour kernel at the depth position i−1 (sub-polarization stage) which is connected to the output 2j−1 of the kernel K.sub.i,j via the shuffler Φ.sub.i−1 (which, in this direction of propagation, refers to the inverse shuffling operation epi φ.sub.i−1.sup.−1) at the depth position i−1 (sub-polarization stage); and [0118] when i>1, {circumflex over (L)}.sub.i,2j.sup.(in) is propagated as L.sub.i−1,j″.sup.(out) wherein j″ represents in this statement the position of the neighbour kernel at the depth position i−1 (sub-polarization stage) which is connected to the output 2j of the kernel K.sub.i,j via the shuffler Φ.sub.i−1 (which, in this direction of propagation, refers to the inverse shuffling operation φ.sub.i−1.sup.−1) at the depth position i−1 (sub-polarization stage).

[0119] In a step S709, the decoder 120 updates the performance-improvement metric for each neighbour kernels of the W kernels that have been extracted from the list in the step S705, in accordance with the LLRs update performed in the step S708.

[0120] In a step S710, the decoder 120 reorders the kernels in the list following the changes made on the performance-improvement metric in the steps S707 and S709, still in decreasing order of the performance-improvement metric .

[0121] In a step S711, the decoder 120 checks whether the stop condition is met, as already described with respect to FIG. 5. When the stop condition is met, a step S712 is performed; otherwise, the step S705 is repeated with the list that has been reordered in the step S710.

[0122] In the step S712, the beliefs propagation ends up by returning the output beliefs {circumflex over (L)}.sub.i,j′.sup.(in) and {circumflex over (L)}.sub.i,j′.sup.(out) ∀i, j′, in order to enable making a decoding decision as is.