Polar-code based encoder and method for configuring divide and conquer structure of polar-code based encoder
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 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.
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 L , the multiplexer having useful data bits and a set of frozen bits as inputs so as to form input data x 1:N (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 1:N (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 1:N (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 1:N (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:
∑
0
<
j
≤
N
❘
F
(
j
)
=
0
I
(
x
j
(
in
)
;
y
❘
x
1
:
j
-
1
(
in
)
)
wherein I(x j (in) ; y|x 1:j−1 (in) ) is the mutual information between the j-th input x j (in) of the polarization block of size N and an observation vector y, assuming that the values of the inputs x 1:j−1 (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:
∏
0
<
j
≤
N
❘
F
(
j
)
=
0
(
1
-
P
e
(
x
j
(
in
)
❘
x
1
:
j
-
1
(
in
)
;
y
)
)
wherein P e (x j (in) | 1:j−1 (in) ;y) represents decoding success probability of the j-th input x j (in) of the polarization block of size N and thus 1−P e (x j (in) | 1:j−1 (in) ;y) represents the bit error probability for said j-th input x j (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 1:N (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 1:N (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 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 1:N (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 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 1:N (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 1:N (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 1:N (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 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.