Polar-code based encoder and method for configuring divide and conquer structure of polar-code based encoder

Abstract

A polar-code based encoder is used to perform a transfer of useful data to a polar-code based decoder via a Binary Discrete-input Memory-less Channel. The Divide and Conquer structure consists of a multiplexer having useful data bits and a set of frozen bits as inputs followed by a polarization block of size N=2.sup.L, wherein the polarization block of size N comprises a set of front kernels followed by a shuffler and two complementary polarization sub-blocks of size N/2 with a similar structure as the polarization block of size N but with half its size. A dynamically configurable interleaver is present between the shuffler and one and/or the other of the complementary polarization sub-blocks at each recursion of the Divide and Conquer structure. The configuration of the dynamically configurable interleavers is dynamically modified according to changes detected in the Binary Discrete-input Memory-less Channel.

Claims

1. A method for configuring a Divide and Conquer structure of a polar-code based encoder performing a transfer of useful data to a polar-code based decoder via a Binary Discrete-input Memory-less Channel, the method being performed by the polar-code based encoder, the Divide and Conquer structure consisting of a multiplexer followed by a polarization block of size N=2.sup.L, the multiplexer having useful data bits and a set of frozen bits as inputs so as to form input data x.sub.1:N.sup.(in), wherein the polarization block of size N comprises a set of front kernels followed by a shuffler and two complementary polarization sub-blocks of size N/2 with a similar structure as the polarization block of size N but with half its size, wherein the shuffler distributes its odd entries to one of the complementary polarization sub-blocks and its even entries to the other one of the complementary polarization sub-blocks, such that the Divide and Conquer structure is recursive with a depth equal to L, wherein a dynamically configurable interleaver is present between the shuffler and one and/or the other of the complementary polarization sub-blocks at each recursion of the Divide and Conquer structure, and in that the method comprises: detecting change in the Binary Discrete-input Memory-less Channel; obtaining probability functions p.sub.1:N.sup.(out), which characterize channel transitions probabilities of the Binary Discrete-input Memory-less Channel at output of the polarization block of size N, according to the detected change in the Binary Discrete-input Memory-less Channel; computing probability functions p.sub.1:N.sup.(in), which characterize channel transitions probabilities of an equivalent Binary Discrete-input Memory-less Channel at input of the polarization block of size N, from the obtained probability functions p.sub.1:N.sup.(out) for a set of interleaving configurations of the dynamically configurable interleavers, determining corresponding positions of the frozen bits and determining a corresponding figure of merit value, wherein the figure of merit is an estimation representative of performance of the transfer to the polar-code based decoder via the Binary Discrete-input Memory-less Channel; and selecting and applying the interleaving configuration of the dynamically configurable interleavers which shows the best performance of the transfer to the polar-code based decoder via the Binary Discrete-input Memory-less Channel in view of the determined corresponding figure of merit values.

2. The method according to claim 1, wherein the figure of merit is mutual information-based and is defined as follows: $\underset{0<jN.Math.F\left(j\right)=0}{.Math.}I\left(x_j^{\left(\mathrm{in}\right)};y.Math.x_{1:j-1}^{\left(\mathrm{in}\right)}\right)$ wherein I(x.sub.j.sup.(in); y|x.sub.1:j1.sup.(in)) is the mutual information between the j-th input x.sub.j.sup.(in) of the polarization block of size N and an observation vector y, assuming that the values of the inputs x.sub.1:j1.sup.(in) are known or correctly decoded, and wherein F is an N-long vector indicating the positions of the frozen bits at corresponding entries set to 1.

3. The method according to claim 1, wherein the figure of merit is information word decoding success-related and is defined as follows: $\underset{0<jN.Math.F\left(j\right)=0}{.Math.}\left(1-P_e\left(x_j^{\left(\mathrm{in}\right)}.Math.x_{1:j-1}^{\left(\mathrm{in}\right)};y\right)\right)$ wherein P.sub.e(x.sub.j.sup.(in)|.sub.1:j1.sup.(in);y) represents decoding success probability of the j-th input x.sub.j.sup.(in) of the polarization block of size N and thus 1P.sub.e(x.sub.j.sup.(in)|.sub.1:j1.sup.(in);y) represents the bit error probability for said j-th input x.sub.j.sup.(in) of the polarization block of size N, and wherein F is an N-long vector indicating the positions of the frozen bits at corresponding entries set to 1.

4. The method according to claim 1, wherein the set of interleaving configurations of the dynamically configurable interleavers is defined using a genetic approach, by considering all possible interleaving configuration input-output association switches.

5. The method according to claim 1, wherein the set of interleaving configurations of the dynamically configurable interleavers gathers all interleaving configurations made possible by the dynamically configurable interleavers.

6. The method according to claim 1, wherein the set of interleaving configurations of the dynamically configurable interleavers consists of a predefined codebook of interleaving configurations.

7. The method according to claim 1, wherein the set of interleaving configurations of the dynamically configurable interleavers consists of a predefined quantity of random configurations of the dynamically configurable interleavers.

8. The method according to claim 1, wherein the Binary Discrete-input Memory-less Channel is a Binary Erasure Channel modelled by relying on erasure rate as parameter monitored to obtain the probability functions p.sub.1:N.sup.(out).

9. The method according to claim 1, wherein the Binary Discrete-input Memory-less Channel is an Additive White Gaussian Noise channel over which a Binary Phase Shift Keying modulation is used and modelled by relying on Signal-to-Noise Ratio as parameter monitored to obtain the probability functions p.sub.1:N.sup.(out).

10. A method for performing a transfer of useful data from a polar-code based encoder to a polar-code based decoder via a Binary Discrete-input Memory-less Channel, the polar-code based encoder including a Divide and Conquer structure consisting of a multiplexer having useful data bits and a set of frozen bits as inputs followed by a polarization block of size N=2.sup.L, wherein the polar-code based encoder performs the method according to claim 1 and wherein the polar-code based decoder performs: detecting change in the Binary Discrete-input Memory-less Channel; obtaining an interleaving configuration dynamically defined by the polar-code based encoder according to the detected change in the Binary Discrete-input Memory-less Channel; configuring a beliefs propagation decoder according to the obtained interleaving configuration; wherein the beliefs propagation decoder thus configured is implemented in the polar-code based decoder, so as to decode observations made by said polar-code based decoder via the Binary Discrete-input Memory-less Channel during the transfer of useful data from a polar-code based encoder.

11. The method according to claim 10, wherein the polar-code based decoder obtains the interleaving configuration by simulating, in view of the probability functions p.sub.1:N.sup.(out), the behaviour of the polar-code based encoder 110 when dynamically determining the interleaving configuration to be applied.

12. A computer program wherein it comprises program code instructions which 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, wherein it stores a computer program comprising program code instructions which 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 based encoder intended to perform a transfer of useful data to a polar-code based decoder via a Binary Discrete-input Memory-less Channel, the polar-code based encoder including a Divide and Conquer structure consisting of a multiplexer having useful data bits and a set of frozen bits as inputs followed by a polarization block of size N=2.sup.L, wherein the polarization block of size N comprises a set of front kernels followed by a shuffler and two complementary polarization sub-blocks of size N/2 with a similar structure as the polarization block of size N but with half its size, wherein the shuffler distributes its odd entries to one of the complementary polarization sub-blocks and its even entries to the other one of the complementary polarization sub-blocks, such that the Divide and Conquer structure is recursive with a depth equal to L, wherein a dynamically configurable interleaver is present between the shuffler and one and/or the other of the complementary polarization sub-blocks at each recursion of the Divide and Conquer structure, and in that the polar-code based encoder further comprises: means for detecting change in the Binary Discrete-input Memory-less Channel; means for obtaining probability functions p.sub.1:N.sup.(out), which characterize channel transitions probabilities of the Binary Discrete-input Memory-less Channel at output of the polarization block of size N, according to the detected change in the Binary Discrete-input Memory-less Channel; means for computing probability functions p.sub.1:N.sup.(out), which characterize channel transitions probabilities of an equivalent Binary Discrete-input Memory-less Channel at input of the polarization block of size N, from the obtained probability functions p.sub.1:N.sup.(out) for a set of interleaving configurations of the dynamically configurable interleavers, determining corresponding positions of the frozen bits and determining a corresponding figure of merit value, wherein the figure of merit is an estimation representative of performance of the transfer to the polar-code based decoder via the Binary Discrete-input Memory-less Channel; and means for selecting and applying the interleaving configuration of the dynamically configurable interleavers which shows the best performance of the transfer to the polar-code based decoder via the Binary Discrete-input Memory-less Channel in view of the determined corresponding figure of merit values.

15. A system including a polar-code based encoder and a polar-code based decoder, the polar-code based encoder being intended to perform a transfer of useful data to the polar-code based decoder via a Binary Discrete-input Memory-less Channel, the polar-code based encoder including a Divide and Conquer structure consisting of a multiplexer having useful data bits and a set of frozen bits as inputs followed by a polarization block of size N=2.sup.L, wherein the polar-code based encoder is according to claim 14 and wherein the polar-code based decoder comprises: means for detecting change in the Binary Discrete-input Memory-less Channel; means for obtaining an interleaving configuration dynamically defined by the polar-code based encoder according to the detected change in the Binary Discrete-input Memory-less Channel; means for configuring a beliefs propagation decoder according to the obtained interleaving configuration; wherein the beliefs propagation decoder thus configured is implemented in the polar-code based decoder, so as to decode observations made by said polar-code based decoder via the Binary Discrete-input Memory-less Channel during the transfer of useful data from a polar-code based encoder.

Description

BRIEF DESCRIPTION OF DRAWING

(1) FIG. 1 schematically represents a system including a polar code encoder and a corresponding polar code decoder.

(2) FIG. 2A schematically represents an encoding part of the encoder according to the prior art.

(3) FIG. 2B schematically represents a modular architecture of the encoding part according to the prior art.

(4) FIG. 2C schematically represents a kernel structure as used in the encoding part according to the prior art.

(5) FIG. 2D schematically represents an algorithm for probability functions propagation as used for deciding frozen bits positions according to the prior art.

(6) FIG. 3 schematically represents a recursive algorithm for performing encoding according to the modular architecture shown in FIG. 2B.

(7) FIG. 4A schematically represents a modular architecture of the decoding part according to the prior art.

(8) FIG. 4B schematically represents a decoding algorithm according to the prior art.

(9) FIG. 4C schematically represents a factor graph applied to the kernel structure schematically shown in FIG. 2C.

(10) FIG. 4D schematically represents a beliefs propagation algorithm according to the prior art.

(11) FIG. 5A schematically represents a first embodiment of a modular architecture of the encoding part according to the present invention.

(12) FIG. 5B schematically represents a second embodiment of a modular architecture of the encoding part according to the present invention.

(13) FIG. 5C schematically represents a third embodiment of a modular architecture of the encoding part according to the present invention.

(14) FIG. 6 schematically represents a modular architecture of the decoding part according to the present invention.

(15) FIG. 7 schematically represents an algorithm for configuring the encoding part according to the present invention.

(16) FIG. 8 schematically represents an algorithm for determining, in a genetic approach, an appropriate configuration of the encoding part according to the present invention.

(17) FIG. 9 schematically represents an algorithm for probability functions propagation as used for deciding frozen bits positions according to the present invention.

(18) FIG. 10 schematically represents a hardware architecture that may be used to implement the polar code encoder and/or the polar code decoder.

(19) FIG. 11 schematically represents a decoding algorithm according to the present invention.

(20) FIG. 12 schematically represents a hardware architecture that may be used to implement the polar code decoder.

(21) FIG. 13 schematically represents a beliefs propagation algorithm according to the present invention.

DESCRIPTION OF EMBODIMENTS

(22) The following description applies to a wireless communication between a transmitter including a polar code-based encoder and a receiver including a corresponding polar-code based decoder. The principles detailed hereafter may also be applied to communications of other kind, such as optical communications or wired communications. Moreover, the principles detailed herein may also be applied to a context of encoding original data, of storing encoded data in memory and then of reading the stored data later on for further decoding and retrieval of the original data.

(23) The system described herein relies on the same context as shown in FIG. 1. However, the encoder 110 and the decoder 120 are arranged as detailed hereafter.

(24) FIG. 5A schematically represents a first embodiment of a modular architecture of the polarizer POL-N 220 according to the present invention.

(25) As in FIG. 2B, the polarizer POL-N 220 comprises the front kernels 250, the shuffler 260, the upper polarizer UPOL-N/2 271 of size N/2 and the lower polarizer LPOL-N/2 272 of size N/2 and the merger 280. Contrary to the arrangement in FIG. 2B, the first embodiment shown in FIG. 5A further includes an interleaver 500 inserted between the shuffler 260 and the lower polarizer LPOL-N/2 272 of size N/2. The upper polarizer UPOL-N/2 271 and the lower polarizer LPOL-N/2 272 have the same structure and are built like the polarizer POL-N 220 but with half its size. It means that each polarizer of size N/2 is built from two other polarizers of size N/4, and so on, as far as reaching a couple of polarizers of size equal to 2 as shown in FIG. 2C. Therefore, in the first embodiment, such an interleaver 500 is placed between each shuffler and each lower polarizer. Each interleaver 500 can be dynamically configured, so as to be able to dynamically define which output among the n/2, with n being a power of 2 such that 2<nN/2, concerned outputs of the shuffler in question is connected to which input of the lower polarizer in question. As detailed hereafter, each interleaver 500 can be configured independently from any other interleaver 500 of the polarizer POL-N 220.

(26) The polarizer POL-N 220 further comprises a configurator 512 to which each interleaver 500 is connected. The configurator 512 is in charge of configuring each interleaver 500. Thus the configurator 512 dynamically defines which output among the n/2, with n being a power of 2 such that 2<nN/2, concerned outputs of the shuffler in question is connected to which input of the lower polarizer in question. This aspect is detailed hereafter with regard to FIGS. 7 and 8.

(27) The polarizer POL-N 220 further comprises a detector 511 that is connected to the configurator 512 so as to activate the configurator 512 for defining a new configuration to be applied by the interleavers 500 of the polarizer POL-N 220. This aspect is detailed hereafter with regard to FIG. 7.

(28) FIG. 5B schematically represents a second embodiment of the modular architecture of the polarizer POL-N 220 according to the present invention.

(29) As in FIG. 2B, the polarizer POL-N 220 comprises the front kernels 250, the shuffler 260, the upper polarizer UPOL-N/2 271 of size N/2 and the lower polarizer LPOL-N/2 272 of size N/2 and the merger 280. Contrary to the arrangement in FIG. 2B, the second embodiment shown in FIG. 5B further includes the interleaver 500. In FIG. 5B, the interleaver 500 is inserted between the shuffler 260 and the upper polarizer UPOL-N/2 271 of size N/2. The upper polarizer UPOL-N/2 271 and the lower polarizer LPOL-N/2 272 have the same structure and are built like the polarizer POL-N 220 but with half its size. It means that each polarizer of size N/2 is built from two other polarizers of size N/4, and so on, as far as reaching a couple of polarizers of size equal to 2 as shown in FIG. 2C. Therefore, in the second embodiment, such an interleaver is placed between each shuffler and each upper polarizer. Each interleaver can be dynamically configured, so as to be able to dynamically define which output among the n/2, with n being a power of 2 such that 2<nN/2, concerned outputs of the shuffler in question is connected to which input of the upper polarizer in question. As detailed hereafter, each interleaver can be configured independently from any other interleaver of the polarizer POL-N 220.

(30) The polarizer POL-N 220 further comprises the configurator 512 to which each interleaver 500 is connected. The configurator 512 is in charge of configuring each interleaver 500. Thus the configurator 512 dynamically defines which output among the n/2, with n being a power of 2 such that 2<nN/2, concerned outputs of the shuffler in question is connected to which input of the upper polarizer in question. This aspect is detailed hereafter with regard to FIGS. 7 and 8.

(31) The polarizer POL-N 220 further comprises the detector 511 that is connected to the configurator 512 so as to activate the configurator 512 for defining a new configuration to be applied by the interleavers 500 of the polarizer POL-N 220. This aspect is detailed hereafter with regard to FIG. 7.

(32) FIG. 5C schematically represents a third embodiment of the modular architecture of the polarizer POL-N 220 according to the present invention.

(33) As in FIG. 2B, the polarizer POL-N 220 comprises the front kernels 250, the shuffler 260, the upper polarizer UPOL-N/2 271 of size N/2 and the lower polarizer LPOL-N/2 272 of size N/2 and the merger 280. Contrary to the arrangement in FIG. 2B, the third embodiment shown in FIG. 5C further includes two interleavers 501 and 502. In FIG. 5C, the interleaver 501 is inserted between the shuffler 260 and the upper polarizer UPOL-N/2 271 of size N/2 and the interleaver 502 is inserted between the shuffler 260 and the lower polarizer LPOL-N/2 272 of size N/2. The upper polarizer UPOL-N/2 271 and the lower polarizer LPOL-N/2 272 have the same structure and are built like the polarizer POL-N 220 but with half its size. It means that each polarizer of size N/2 is built from two other polarizers of size N/4, and so on, as far as reaching a couple of polarizers of size equal to 2 as shown in FIG. 2C. Therefore, in the third embodiment, such one interleaver 501 is placed between each shuffler and each upper polarizer and another one such interleaver 502 is placed between each shuffler and each lower polarizer. Each interleaver 501 and 502 can be dynamically configured, so as to be able to dynamically define which output among the n/2, with n being a power of 2 such that 2<nN/2, concerned outputs of the shuffler in question is connected to which input of the upper polarizer in question, and to be able to dynamically define which output among the n/2, with n being a power of 2 such that 2<nN/2, concerned outputs of the shuffler in question is connected to which input of the lower polarizer in question. As detailed hereafter, each interleaver 501 and 502 can be configured independently from any other interleaver 501 and 502 of the polarizer POL-N 220.

(34) It has to be noticed that the introduction of the interleavers 501 and 502 in the internal structure of the polarizer POL-N 220 maintains independency between random variables input to the upper polarizer UPOL-N/2 271 and random variables input to the lower polarizer LPOL-N/2 272.

(35) The polarizer POL-N 220 further comprises the configurator 512 to which each interleaver 501 and 502 is connected. The configurator 512 is in charge of configuring each interleaver 501 and 502. Thus the configurator 512 dynamically defines which output among the n/2, with n being a power of 2 such that 2<nN/2, concerned outputs of the shuffler in question is connected to which input of the lower polarizer in question, and the configurator 512 dynamically defines which output among the n/2, with n being a power of 2 such that 2<nN/2, concerned outputs of the shuffler in question is connected to which input of the upper polarizer in question. This aspect is detailed hereafter with regard to FIGS. 7 and 8.

(36) The polarizer POL-N 220 further comprises the detector 511 that is connected to the configurator 512 so as to activate the configurator 512 for defining a new configuration to be applied by the interleavers 501 and 502 of the polarizer POL-N 220. This aspect is detailed hereafter with regard to FIG. 7.

(37) As already mentioned, the size of the polarizer POL-N 220 is N=2.sup.L and comprises two sub-polarization blocks having respectively a size equal to N/2, and each one of said sub-polarization blocks comprises two sub-polarization blocks having respectively a size equal N/4, and so on. Finally, the polarizer POL-N 220 comprises L1 sub-polarization stages, which means 2(2.sup.L1-1) sub-polarization blocks within which 2.sup.i sub-polarization blocks have a size equal to 2.sup.Li.

(38) Let illustratively consider that .sub.u represents the configuration of the interleaver identified by an index u such that 0<u<2.sup.L1 and further considering that there is one interleaver for each lower sub-polarization block. Indeed, it can be demonstrated that it is equivalent in terms of polar code result to insert an interleaver for each sub-polarization block of each sub-polarization stage as to insert only one interleaver per sub-polarization stage, but it only leads to a higher complexity in terms of polar code design. Each interleaver may be configured so as to be transparent, which is equivalent as deactivating said interleaver. The index u is such that it is representative of the position of the considered interleaver within the polarizer POL-N 220. Thus, the polarizer POL-N 220 comprises L1 sub-polarization stages, which means 2(2.sup.L1-1) sub-polarization blocks and (2.sup.L1-1) interleavers. Furthermore, the index u, which is an integer that can be decomposed into a binary word representation u.sub.b(1), . . . , u.sub.b(L1), represents the path through the D&C structure to reach the interleaver in question. The path representation, obtained thanks to the index u, indicates for each bit of the index u whether the upper branch (where is located the upper sub-polarization block) or the lower branch (where is located the upper sub-polarization block) is selected, as follows: u.sub.b(i)=1 indicates that the interleaver in question is located on the lower branch of the i-th recursion of the D&C structure; and u.sub.b(i)=0 indicates that the interleaver in question is located on the upper branch of the i-th recursion of the D&C structure.

(39) When the interleaver identified by the index u is present at the i-th sub-polarization stage (mandatorily between the shuffler of said i-th sub-polarization stage and the lower sub-polarization block), it means that the input u.sub.b(i)=1 and then the inputs u.sub.b(j>i)=0.

(40) In other words, for a given interleaving configuration .sub.u, one can get the binary representation u.sub.b(1), . . . , u.sub.b(L1) of the index u, and thus, by finding the last non-null input i such that u.sub.b(j>i)=0, it can be determined that the interleaver to which it is referred is placed in the i-th recursion depth in the recursive construction of the polarizer POL-N 220. This value is given by i=log.sub.2(u)+1. Thus, since the size of the polarizer POL-N 220 at the i-th recursion depth is 2.sup.Li+1, and since the interleaver is of half this size, the size of .sub.u is 2.sup.Li. Thus, the size of .sub.u is equal to 2.sup.Llog.sup.2.sup.(u)1.

(41) FIG. 6 schematically represents a modular architecture of the decoding part according to the present invention.

(42) As in FIG. 4A, the decoder 120 comprises the LLR computing module 421, the beliefs propagation decoder 422 and the decision maker 423, which together form the decoding part 420 of the decoder 120. The decoder 120 further includes the demultiplexer 410 that converts the estimation b* of the vector b into the estimation b* of the vector b, from a knowledge of the positions of the frozen bits used by the encoder 110. The LLR computing module 421 outputs the observations L.sub.x (thus in LLR form), which are then used by the beliefs propagation decoder 422 in conjunction with the a priori probabilities L.sub.b (in LLR form too) so as to output the estimates {circumflex over (L)}.sub.b. The estimates {circumflex over (L)}.sub.b are then used by the decision maker 423 so as to determine the estimation b* of the vector b.

(43) The decoder 120 further comprises a configurator 602, as well as a detector 601. The detector 601 is in charge of detecting that a change in BDMC should have implied a change in the D&C structure of the encoder 110. Either the detector 601 detects such a change by monitoring relevant parameters of the BDMC or the detector 601 is informed by the encoder 110 that such a change occurred. The configurator 602 is in charge of configuring the beliefs propagation decoder 422 so that the beliefs propagation decoder 422 takes into account the up-to-date D&C structure of the encoder 110.

(44) FIG. 7 schematically represents an algorithm for configuring the polarizer POL-N 220 according to the present invention.

(45) In a step S701, the detector 511 detects that a new configuration of the polarizer POL-N 220 has to be determined and applied. The need for the new configuration of the polarizer POL-N 220 is detected following a change, above a predefined threshold, of the considered parameter of the BDMC, e.g. erasure rate or SNR, wherein said considered parameter of the BDMC is monitored.

(46) In a following step S702, the configurator 512 obtains updated probability functions p.sub.1:N.sup.(out), or parameters representative thereof or of numerical approximations thereof, of the effective BDMC in use. When the probability functions p.sub.1:N.sup.(out) are obtained from a closed form expression depending on the monitored channel parameters, such as the erasure rate for the BEC or the SNR for the AWGN channel with BPSK input, said parameter can be estimated and tracked through time, for example according to the reception of pilot sequences. As a remark, in this case, only the parameter can be stored and used in the next steps since it fully characterizes p.sub.1:N.sup.(out). Thus, it is equivalent to have the parametrized expression of p.sub.1:N.sup.(out) and the channel parameter knowledge, or the direct expression of p.sub.1:N.sup.(out), while it is simpler to store and use said channel parameter.

(47) When the probability functions p.sub.1:N.sup.(out) are estimated numerically, a histogram of the likelihoods can be built through time thanks to pilot sequences sent by the transmitter and known beforehand at the receiver.

(48) In a following step S703, the configurator 512 determines an interleaving configuration, i.e. a set of respective configurations of the interleavers 500 or of the interleavers 501 and 502, to be checked. The configurator 512 is expected to check various configurations of the interleavers 500 or of the interleavers 501 and 502.

(49) According to a particular embodiment, the configurator 512 checks in the scope of the algorithm of FIG. 7 all possible configurations of the interleavers 500 or of the interleavers 501 and 502.

(50) According to another particular embodiment, the configurator 512 checks in the scope of the algorithm of FIG. 7 all configurations of the interleavers 500 or of the interleavers 501 and 502 which are defined in a predefined codebook of interleaving configurations.

(51) According to yet another particular embodiment, the configurator 512 checks in the scope of the algorithm of FIG. 7 a predefined quantity of random configurations of the interleavers 500 or of the interleavers 501 and 502 including the configuration in which all the interleavers are configured to be transparent.

(52) According to yet another particular embodiment, the configurator 512 checks in the scope of the algorithm of FIG. 7 configurations of the interleavers 500 or of the interleavers 501 and 502 using a genetic approach, by considering all possible interleaving configuration input-output association switches. This aspect is detailed hereafter by way of an example with regard to FIG. 8.

(53) In a following step S704, the configurator 512 obtains updated probability functions p.sub.1:N.sup.(in), or parameters representative thereof or of numerical approximations thereof, of the equivalent BDMC corresponding to the updated probability functions p.sub.1:N.sup.(out), or parameters representative thereof or of numerical approximations thereof, obtained in the step S702, by taking into account the D&C structure of the polarizer POL-N 220 as arranged according to the interleaving configuration determined in the step S703. Compared with the algorithm described with regard to FIG. 2D, the step S296 is modified so as to not only take into consideration the shuffling operation performed by the shuffler in question (i.e. the shuffling operation performed by the shuffler of the i-th sub-polarization stage to which corresponds the considered recursion of the algorithm in FIG. 2D) but also of the configuration of each interleaver present in said i-th sub-polarization stage). This aspect is schematically shown in the algorithm in FIG. 9, wherein a step S296 accordingly replaces the step S296 of the algorithm of FIG. 2D.

(54) In a following step S705, the configurator 512 obtains corresponding positions of the frozen bits, by attributing to said frozen bits the virtual BDMCs that are the less reliable with respect to the updated probability functions p.sub.1:N.sup.(in), or parameters representative thereof or of numerical approximations thereof, obtained in the step S704.

(55) In a following step S706, the configurator 512 computes a value of a predefined figure of merit that is an estimation representative of performance of data transfer from the encoder 110 to the decoder 120.

(56) According to a first embodiment of the step S706, the figure of merit is mutual information-based and is defined as follows:

(57) $\underset{0<jN.Math.F\left(j\right)=0}{.Math.}I\left(x_j^{\left(\mathrm{in}\right)};y.Math.x_{1:j-1}^{\left(\mathrm{in}\right)}\right)$

(58) wherein I(x.sub.j.sup.(in); y|x.sub.1:j1.sup.(in)) is the mutual information between the j-th input of the polarization block of size N and the observation vector y, assuming that the values of the inputs x.sub.1:j1.sup.(in) are known or correctly decoded. The goal of the optimization performed by the algorithm of FIG. 7 is thus to maximize mutual information. As a remark, the frozen bits are preferably selected according to an ascendant sorting of the mutual information I(x.sub.j.sup.(in); y|x.sub.1:j1.sup.(in)).

(59) According to a second embodiment of the step S706, the figure of merit is information word decoding success-related and is defined as follows:

(60) $\underset{0<jN.Math.F\left(j\right)=0}{.Math.}\left(1-P_e\left(x_j^{\left(\mathrm{in}\right)}.Math.x_{1:j-1}^{\left(\mathrm{in}\right)};y\right)\right)$

(61) wherein P.sub.e(x.sub.j.sup.(in)|x.sub.1:j1.sup.(in); y) represents the decoding success probabilities of the j-th input of the polarizer POL-N 220 and thus 1P.sub.e(x.sub.j.sup.(in)|x.sub.1:j1.sup.(in); y) represents the bit error probability of said j-th input of the polarizer POL-N 220. The goal of the optimization performed by the algorithm of FIG. 7 is thus to maximize mutual information. As a remark, the frozen bits are preferably selected according to an ascendant sorting of the bit decoding success probabilities 1P.sub.e(x.sub.j.sup.(in)|x.sub.1:j1.sup.(in); y).

(62) In a following step S707, the configurator 512 determines whether there is at least one other interleaving configuration to be checked. If there is at least one other interleaving configuration to be checked, the step S703 is repeated; otherwise, a step S708 is performed.

(63) In the step S708, the configurator 512 retains the interleaving configuration and positions of the frozen bits which jointly provide the best figure of merit value, i.e. the value that shows the best performance of data transfer from the encoder 110 to the decoder 120. The configurator 512 applies the retained interleaving configuration, i.e. configures the interleavers 500 or the interleavers 501 and 502, in accordance with the retained interleaving configuration.

(64) In a particular embodiment, the encoder 110 informs the decoder 120 of the retained interleaving configuration and corresponding positions of the frozen bits. In a variant embodiment, the configurator 602 of the decoder 120 determines the retained interleaving configuration and corresponding positions of the frozen bits by simulation using the same approach than the configurator 512 of the encoder 110. The detector 601 of the decoder 120 may monitor the considered parameter of the BDMC and detect changes in said BDMC on its own. Another approach is that the encoder 110 informs the decoder 120 of the change in the BDMC and supplies to the decoder 120 information representative of the updated probability functions p.sub.1:N.sup.(out).

(65) FIG. 8 schematically represents an algorithm for determining, in a genetic approach, an appropriate configuration of the polarizer POL-N 220. For simplicity considerations, FIG. 8 describes how to optimize the interleaving configuration .sub.1 by using a genetic approach. The main principle is to test various interleaving configurations, and thus various configurations of the polarizer POL-N 220, by modifying input-output associations in the interleaver identified by the index u=1 (with u defined as explained hereinbefore). Performance evaluation is performed for each tested interleaving configuration by re-computing the probability functions p.sub.1:N.sup.(in) of the equivalent BDMC, optimizing the frozen bits and re-computing the corresponding value of the figure of merit. All the possible input-output association switches in the interleaving configuration .sub.1 are tested, and the configuration of the polarizer POL-N 220 showing the best estimated performance according to the figure of merit is retained and applied. This operation is repeated several times and converges to a sub-optimal solution. However, it allows to obtain a good version of the interleaving configuration in a limited number of tests, which is a key advantage.

(66) In a step S802, the polarizer POL-N 220 initializes the interleaving configuration .sub.1, as follows:
0<iN/2,.sub.1(i)=i

(67) which means that the interleaving configuration .sub.1 is transparent after initialization.

(68) In a step S803, the polarizer POL-N 220 initializes a local variable Psbestsav to 0.

(69) In a step S804, the polarizer POL-N 220 initializes a local variable .sub.best with the content of .sub.1, and a local variable Psbest with the content of the local variable Psbestsay. Moreover, the polarizer POL-N 220 sets a first index i1 to 1.

(70) In a step S805, the polarizer POL-N 220 initializes a second index i2 with the value of the first index i1.

(71) In a step S806, the polarizer POL-N 220 initializes a local variable .sub.test with the content of .sub.1.

(72) In a step S807, the polarizer POL-N 220 exchanges the inputs of .sub.test (i1) and .sub.test (i2), which means that the input of the interleaving configuration .sub.test connected to the output .sub.test (i1) is inverted with the input of the interleaving configuration .sub.test connected to the output .sub.test (i2). A new interleaving configuration is thus obtained, except for the iterations wherein i1=i2. This approach of considering the case where i1=i2 allows testing the configuration in which all and any interleavers are set as transparent (which leads to the D&C structure of the prior art).

(73) In a step S808, the polarizer POL-N 220 computes decoding success probabilities P.sub.e(x.sub.j.sup.(in)|x.sub.1:j1.sup.(in); y), 0<jN, according to the interleaving configuration .sub.test obtained in the step S807. In other words, the polarizer POL-N 220 computes the decoding success probabilities P.sub.e(x.sub.j.sup.(in)|x.sub.1:j1.sup.(in); y) according to the probability functions p.sub.1:N.sup.(out), according to the functions .sub.1 and .sub.2 and according to the interleaving configuration .sub.test obtained in the step S807. It means that at least the decoding success probabilities P.sub.e(x.sub.j.sup.(in)|x.sub.1:j1.sup.(in); y) for the inputs that have been inverted by the change brought by the interleaving configuration .sub.test obtained in the step S807 have to be recomputed, compared with the interleaving configuration .sub.est used during the last execution of the step S808.

(74) In a step S809, the polarizer POL-N 220 performs a sorting operation for sorting in descending order the bit decoding success probabilities represented by 1-P.sub.e(x.sub.j.sup.(in)|x.sub.1:j1.sup.(in); y), 0<jN. The polarizer POL-N 220 then stores in a vector P.sub.s the results of the sorting operation, which means that P.sub.s(1) stores the highest bit decoding success probability 1-P.sub.e(x.sub.i.sup.(in)|x.sub.1:i-1.sup.(in); y) computed in the step S808 and P.sub.s(N) stores the lowest bit decoding success probability 1-P.sub.e(x.sub.i.sup.(in)|x.sub.1:i-1.sup.(in); y) computed in the step S808.

(75) In a step S810, the polarizer POL-N 220 computes a product value P.sub.s defined as follows:

(76) $P_s=\underset{j=1}{\overset{N.Math.R}{.Math.}}{P}_s^{}\left(j\right)$

(77) which means that only the N.Math.R first entries of the vector P.sub.s are retained for computing the product value P.sub.s, which thus represents the global information word decoding success probability for the N.Math.R best virtual BDMCs obtained with the interleaving configuration .sub.test or, in other words, the figure of merit in use corresponds to word decoding success rate.

(78) In a step S811, the polarizer POL-N 220 checks whether the product value P.sub.s is greater than the local variable Psbest. If the product value P.sub.s is greater than the local variable Psbest, a step S812 is performed; otherwise a step S813 is performed.

(79) In the step S812, the polarizer POL-N 220 stores in the local variable .sub.test the contents of the local variable .sub.test. Furthermore, the polarizer POL-N 220 stores the product value P.sub.s in the local variable Psbest. Then the step S813 is performed.

(80) In the step S813, the polarizer POL-N 220 checks whether the second index i2 is equal to N/2. If the second index i2 is equal to N/2, a step S815 is performed; otherwise, a step S814 is performed.

(81) In the step S814, the polarizer POL-N 220 increments the second index i2 by one unit. Then the step S806 is repeated.

(82) In the step S815, the polarizer POL-N 220 checks whether the first index i1 is equal to N/2. If the first index i1 is equal to N/2, a step S817 is performed; otherwise, a step S816 is performed.

(83) In the step S816, the polarizer POL-N 220 increments the second index i1 by one unit. Then the step S805 is repeated.

(84) In the step S817, the polarizer POL-N 220 checks whether the value stored in the local variable Psbest is greater than the value stored in the local variable Psbestsav, i.e. the polarizer POL-N 220 checks whether the configuration that led to the value stored in the local variable Psbest shows data transfer improvement, with respect to the considered figure of merit, compared with any previously considered interleaving configuration .sub.1. If the value stored in the local variable Psbest is greater than the value stored in the local variable Psbestsav, a step S818 is performed; otherwise, a step S819 is performed, in which the algorithm in FIG. 8 ends, which means that the interleaving configuration .sub.1 to be applied has been found.

(85) In the step S818, the polarizer POL-N 220 stores the interleaver configuration .sub.test test as interleaving configuration .sub.1. Furthermore, the polarizer POL-N 220 stores in the local variable Psbestsav the value stored in the local variable Psbest. Then the step S804 is repeated.

(86) In the scope of the algorithm of FIG. 8, the figure of merit illustratively used is word decoding success rate, and the frozen bit optimization is done by selecting the bit positions showing the N.Math.R lowest bit decoding success probabilities with respect to the probability functions p.sub.1:N.sup.(in). It is possible to use another figure of merit in the scope of FIG. 8 and the principles described here above would remain identical, for example when trying to maximize mutual information.

(87) FIG. 10 schematically represents an embodiment of architecture of the encoder 110. According to the shown architecture, the encoder 110 comprises the following components interconnected by a communications bus 1006: a processor, microprocessor, microcontroller or CPU (Central Processing Unit) 1000; a RAM (Random-Access Memory) 1001; a ROM (Read-Only Memory) 1002; an SD (Secure Digital) card reader 1003, or any other device adapted to read information stored on storage means, such as an HDD (Hard Disk Drive); and, a communication interface 1004 toward the decoder 120 via BDMC onto which polar codes are used.

(88) CPU 1000 is capable of executing instructions loaded into RAM 1001 from ROM 1002 or from an external memory, such as an HDD or an SD card. After the encoder 110 has been powered on, CPU 1000 is capable of reading instructions from RAM 1001 and executing these instructions that form one computer program.

(89) Any and all steps performed by the encoder 110 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 microcontroller; or else implemented in hardware by a machine or a dedicated component, such as an FPGA (Field-Programmable Gate Array) or an ASIC (Application-Specific Integrated Circuit). Similarly, the modular architecture embodiments presented in FIGS. 5A, 5B and 5C may be implemented in software form or in hardware form. In general, the encoder 110 comprises processing electronics circuitry configured for implementing the relevant steps to be performed by the encoder 110 as described herein.

(90) The behaviour of the decoder 120 according to the invention is schematically shown by the algorithm in FIG. 11.

(91) In a step S1101, the decoder 120 detects that a change in BDMC has implied a change in the D&C structure of the encoder 110. Either the decoder 120 detects such a change on its own by monitoring relevant parameters of the BDMC (similarly as the encoder 110 does) or is informed by the encoder 110, by using a signalling channel, that such a change occurred.

(92) In a step S1102, the decoder 120 initializes the vector L.sub.b first as a null vector, and then the decoder 120 modifies the vector L.sub.b according to the knowledge of the positions of the frozen bits used by the encoder 110, as follows:
0<jN,F(j)=1.Math.L.sub.b(j)=+
wherein + is numerically represented by a value that is sufficiently high to be out of the scope of the LLR values that can exist at the input of any polarizer of size n, with n being a power of 2 such that 0<nN/2. It means that, for any index value that corresponds to a position of a frozen bit in the vector b, the value of the vector L.sub.b at said index value is set to infinity or a default value representative thereof, and set to 0 otherwise.

(93) The decoder 120 is either capable of determining the positions of the frozen bits by simulating what would be computed by the encoder 110 in view of the probability functions p.sub.1:n.sup.(out), or is informed by the encoder 110, by using the signalling channel, of the selected positions of the frozen bits.

(94) Similarly, the decoder 120 is either capable of determining the interleaving configuration used by the encoder 110 by simulating what would be computed by the encoder 110 in view of the probability functions p.sub.1:n.sup.(out), or is informed by the encoder 110, by using the signalling channel, of the selected interleaving configuration.

(95) In a following step S1103, the decoder 120 initializes internal variables L.sub.1:N.sup.(in) and L.sub.1:N.sup.(out) with null values. Said internal variables are intended to be propagated along the recursions of the beliefs propagation.

(96) In a following step S1104, the decoder 120 computes beliefs propagation using the internal variables L.sub.1:N.sup.(in) and L.sub.1:N.sup.(out), according to the known D&C structure of the polarizer POL-N 220, including the interleaving configuration, and to the observations L.sub.x in LLR form. In other words, the decoder 120 uses the algorithm schematically shown in FIG. 13 by inputting therein the vector L.sub.b as L.sub.1:N.sup.(in) and the vector L.sub.x as L.sub.1:N.sup.(out). Compared with the algorithm described with regard to FIG. 4D, the step S477 is modified so as to not only take into consideration the shuffling operation performed by the shuffler in question (i.e. the shuffling operation performed by the shuffler of the i-th sub-polarization stage to which corresponds the considered recursion of the algorithm in FIG. 13) but also of the configuration of each interleaver present in said i-th sub-polarization stage. This aspect is schematically shown in the algorithm in FIG. 13, wherein a step S477 accordingly replaces the step S477 of the algorithm of FIG. 4D. Moreover, compared with the algorithm described with regard to FIG. 4D, the step S478 is also modified so as to not only take into consideration the shuffling operation performed by the shuffler in question (i.e. the shuffling operation performed by the shuffler of the i-th sub-polarization stage to which corresponds the considered recursion of the algorithm in FIG. 13) but also of the configuration of each interleaver present in said i-th sub-polarization stage. This aspect is schematically shown in the algorithm in FIG. 13, wherein a step S478 accordingly replaces the step S478 of the algorithm of FIG. 4D.

(97) The output of the beliefs propagation are the vectors {circumflex over (L)}.sub.b and {circumflex over (L)}.sub.x, wherein the vector {circumflex over (L)}.sub.b is then used by the decision maker 423 to determine the estimation b* of the vector b.

(98) In a following step S1105, the decoder 120 waits for availability of observations made on the BDMC and that said observations be made available in LLR form, i.e. the vector L.sub.x, by the LLR computing module 421.

(99) In a following step S1106, the decoder 120 has obtained the vector L.sub.x corresponding to an information word, i.e. the vector b, transferred by the encoder 110 using polar coding, and the decoder 120 makes a decision on each bit of the estimation b* of the vector b according to the estimates L.sub.b output by the beliefs propagation decoder 422. The decision is made as follows:

(100) $0<jN,\{\begin{array}{c}{\hat{L}}_b\left(j\right)>0.Math.\hat{b}\left(j\right)=0\\ {\hat{L}}_b\left(j\right)<0.Math.\hat{b}\left(j\right)=1\end{array}$

(101) {circumflex over (L)}.sub.b(j), 0<jN, should not be equal to 0. In case such a situation occurs, the decoder 120 arbitrarily sets the corresponding bit {circumflex over (b)}(j) either to 0 or to1.

(102) Then, since the decoder 120 knows the positions of the frozen bits in the vector b, the decoder is able to extract therefrom the information bits so as to form the estimation b* of the vector b, which ends the transfer of said information bits from the encoder 110 to the decoder 120 using the polar code approach.

(103) In a following step S1107, the decoder 120 checks whether there is a change in the effective BDMC in use. As already mentioned, the detector 601 may monitor the relevant parameter of the BDMC so as to detect a change in the aforementioned probability functions p.sub.1:n.sup.(out). In a variant, the detector 601 may be informed by the encoder 110 that a change occurred in the aforementioned probability functions p.sub.1:n.sup.(out) and consequently in the D&C structure used by the encoder 110 due to reconfiguration of the interleavers included therein. If there is a change in the effective BDMC in use, the step S1101 is repeated; otherwise the step S1105 is repeated for decoding a new information word transferred by the encoder 110 using polar coding.

(104) FIG. 12 schematically represents an embodiment of architecture of the decoder 120. According to the shown architecture, the decoder 120 comprises the following components interconnected by a communications bus 1006: a processor, microprocessor, microcontroller or CPU 1200; a RAM 1201; a ROM 1202; an SD card reader 1203, or any other device adapted to read information stored on storage means, such as an HDD; and, a communication interface 1204 for receiving communications from the decoder 120 via the BDMC onto which polar codes are used.

(105) CPU 1200 is capable of executing instructions loaded into RAM 1201 from ROM 1202 or from an external memory, such as an HDD or an SD card. After the decoder 120 has been powered on, CPU 1200 is capable of reading instructions from RAM 1201 and executing these instructions that form one computer program.

(106) Any and all 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, a DSP or a microcontroller; or else implemented in hardware by a machine or a dedicated component, such as an FPGA or an ASIC. Similarly, the modular architecture embodiments presented in FIG. 6 may be implemented in software form or in hardware form. In general, the decoder 120 comprises processing electronics circuitry configured for implementing the relevant steps to be performed by the decoder 120 as described herein.