[Title of Invention]

METHOD AND DEVICE FOR MULTILEVEL POLAR-CODED MODULATION TRANSMITTING AND RECEIVING [Technical Field]

[0001]

This disclosure relates to digital telecommunication systems, and relates more specifically to a multilevel polar-coded modulation scheme.

[Background Art]

[0002]

Most modem telecommunication systems rely on the combination of quadrature amplitude modulation, QAM, modulations (or at least discrete constellations) and error correcting codes, leading to so-called coded modulations. Today, the most common architecture is called bit-interleaved coded modulation (BICM), which involves a bit interleaver between the output of the error correcting code and the input of the symbol modulator. During the quest for the best coded modulation scheme (from around 60 years ago), several other architectures were invented such as trellis-coded modulations (TCM) and multilevel coded (MLC) modulations which were finally outperformed by the BICM main advantage to naturally welcome the breakthrough capacity achieving codes (turbo-codes, low density parity check codes, LDPCs). The TCM stmcture involves a joint design of the error correcting code and symbol modulator, the complexity of which explodes for the random structure of turbo-codes or LDPCs. As for MLC, it inherently involves a successive cancellation structure between independent codes, which is sub-optimal with respect to an error correcting code spanning the whole coded bits, when using an iterative decoding approach.

[0003]

Shannon’s information theory teaches us that random codes, for which no decoder can be implemented in practice, asymptotically achieve the channel capacity. Thus, the main strategy has been to use off-the-shelf error correcting codes with a strong algebraic structure that allows practical decoder implementation, and to combine them by introducing an as-random-as possible structure (e.g. with random interleaving). The decoder complexity can be kept low by using belief propagation iterative decoding. One key difficulty is to predict the performance of such error correcting codes, especially in a coded modulation context where even the BICM channel capacity can only be known with approximations. This difficulty is today the main obstacle to extremely good performance, especially for small data packets. As a remark, error correcting codes are most of the time optimized for the binary input additive white Gaussian noise, AWGN, channel case. Such high performance optimizations are then used in the BICM context, which is not a standard binary input AWGN channel, which causes sub-optimality in the BICM context.

[0004]

Recently (from 2009), a new class of capacity achieving error correcting codes was invented that relies neither on algebraic structure nor on iterative belief propagation, that do not have a random structure, but still provably asymptotically achieve the channel capacity. The polar codes, invented by Arikan [ARI2009], rely on a construction from information theory. By combining, in a divide and conquer approach (like fast Fourier transform for example), parallel polarization channels and using successive cancellation decoding, it can be proved that the equivalent parallel polarization channels are asymptotically (infinite length) either perfect or null (polarization effect), in a proportion equal to the initial channel capacity. The encoding and decoding complexity is limited in number of operations, thanks to the divide-and-conquer structure of the error correcting code. The main challenge is to be able to predict the position of the polarization channels with null capacity, that will carry frozen bits (known to the transmitting device and to the receiving device), since these positions can vary in a seemingly random behavior according to the characteristics of the actual channel targeted for transmission. Only few simple channels allow having an optimal choice of said frozen bits. For the well-known binary input AWGN channel, efficient techniques are known for the determination of the frozen bits positions according to their number (code rate) and to the signal to noise ratio, SNR, of the AWGN channel. Thus, we have at our disposal, from the scientific literature, a polar code toolbox designed for binary input AWGN [BIO2019]. The toolbox is able to provide good performance for any coding rate and data packet length.

[0005]

Polar codes have been included e.g. in 5G standardization [3GPP38212]. Polar codes not only show high performance on typical AWGN channels but are also very promising for designing coded modulations and for being applied to less known channels. The most important facts on polar codes are: polar codes are capacity achieving for infinite data packet length; the decoder associated with polar codes involve a serial processing of the bits, which involve that the latency for decoding is linear with the data packet length; this makes polar codes impractical for large packet lengths in latency constrained applications; this is why they were only selected for short data packets in 5G standardization; the polar codes have no error floor, which allow to easily predict the performance and attain packet error rates down to 10 ¹⁰ , which is good for ultra reliable communications.

[0006]

From the former points, we can conclude that polar codes are only practical for short data packets, but good only for large data packets, which is contradictory. However, instead of using the initially (and optimal for large data packets) successive cancellation decoding, it has been proposed to generalize such decoder to a list based decoder (a kind of K- first tree search). This algorithm provides a list of candidate survivors instead of a direct estimation of the transmitted data bits of one polarization channel. Then, analysis of polar codes has shown that their minimal distance is weak, but that their second minimal distance is good. Thus, it has been proposed to include a cyclic redundancy check, CRC, in the data packet to allow sorting between the candidates provided by the list decoder. This provides very high increase of performance for short data packets, and makes polar codes providing a better performance / complexity tradeoff than other coding strategies. As of today, the combination of polar codes, CRC and list decoder has not been beaten by other designs of polar codes for short data packets (lower than 8000 data bits).

[0007]

The polar code structure is based on the chain rule on information theory, which suggests multilevel encoding and decoding with no information loss. MLC modulations also rely on this same concept. Thus, it seems a good strategy to rely on polar codes for MLC modulations, leading into multilevel polar-coded modulations [SEID2013] [ION2014]. Also, the list decoding approach can easily be extended to multilevel coded modulations by passing the lists from one polar code decoder to another. The increase of complexity is limited. There is no need to consider belief propagation algorithms.

[0008]

However, the main drawback of polar codes is that their design (choice of the frozen bits for a given rate) is very sensitive to the nature of the channel. Thus a polar code designed for a binary input AWGN channel does not exhibit good performance when used with e.g. a binary erasure channel, BEC.

[0009]

When the channel transition probability is non-trivial, the only possibility to have a good selection of frozen bits is to compute a so-called density evolution, i.e. propagating the transition probabilities within the structure of the error correcting code in order to determine the equivalent channel transition probability at each data bit level. This is already extremely complex in the binary case, and is even more complex in the multilevel modulation case. [0010]

[References]

[3GPP38212] 3rd Generation Partnership Project (3 GPP), “Multiplexing and channel coding”, 3GPP 38.212 V15.3.0, 2018.

[ARI2009] Arikan, E. (July 2009). “Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels”, IEEE Transactions on Information Theory.

[BIO2019] V. Bioglio, C.Condo, I. Land, “Design of Polar Codes in 5G New Radio”, arXiv:l 804.04389v2.

[ION2014] C. I. Ionita, M. Mansour, J. C. Roh, and S. Hosur, "On the design of binary polar codes for high-order modulation", Proceedings of IEEE Global Communications Conference, Austin, TX, USA, December 2014.

[SEID2013] M. Seidl, A. Schenk, C. Stierstorfer, and J. B. Huber, “Multilevel polar-coded modulation”, Proceedings of IEEE International Symposium on Information Theory, Munich, Germany, January 2013.

[Summary of Invention]

[0011]

The present disclosure aims at proposing a multilevel polar-coded modulation scheme in a way to keep the implementation simple with high performance, in some embodiments at least. In particular, the present disclosure aims at proposing a multilevel polar-coded modulation scheme that can provide good performance even when the channel is not an AWGN channel, and even with short data packets, which are of particular interest in the context of "Internet of Things" (IoT) applications.

[0012]

For this purpose, and according to a first aspect, the present disclosure relates to a method for transmitting a data stream from a transmitting device to a receiving device, the data stream comprising m data sub-streams, said method comprising: encoding the data sub-streams with respective polar codes, such as to produce m polar-encoded data sub-streams, modulating the m polar-encoded data sub-streams onto symbols of a multilevel modulation comprising m levels defining 2 ^m different symbols in a complex plane, according to a predetermined labeling function Z which bijectively associates a symbol to a set c ... , c _m of m bits from respective polar- encoded data sub-streams, such that successive sets of m bits from respective polar-encoded data sub-streams are converted into successive symbols forming a symbol stream, transmitting the symbol stream to the receiving device.

[0013]

The 2 ^m symbols of the multilevel modulation are distributed in the complex plane such that they are regularly spaced along the real axis and the complex axis by a spacing factor K, and the predetermined labeling function Z is such that:

F (Z) < 1.7 ^m x (0.0425 x m - 0.06) expression in which:

[0014]

In specific embodiments, the transmitting method can further comprise one or more of the following features, considered either alone or in any technically possible combination.

[0015]

In a specific embodiment, each of the m polar codes used is a polar code designed for a binary input additive white Gaussian noise, AWGN, channel. [0016]

In a specific embodiment, the respective code rates of the m polar codes are adapted to propagation conditions.

[0017]

In a specific embodiment, the transmitting method comprises: determining signal to noise ratios, SNRs, experienced by each data substream during the propagation from the transmitting device to the receiving device, selecting the code rates of each of the m polar codes used based on the SNRs experienced by each data sub-stream.

[0018]

In a specific embodiment, the data sub-stream and/or each of the data sub streams include an error detection code.

[0019]

In a specific embodiment, the multilevel modulation is a 16QAM modulation, and the labeling function is given by table 1 below, or by table 1 modified by rotating the constellation of symbols in the complex plane by an angle multiple of 90°, and/or by applying an axial reflection to the constellation of symbols with respect to the real axis, and/or by applying an axial reflection to the constellation of symbols with respect to the complex axis, and/or by inverting all the bit values.

[0020]

In a specific embodiment, the multilevel modulation is a 64QAM modulation, and the labeling function is given by table 2 below, or by table 2 modified by rotating the constellation of symbols in the complex plane by an angle multiple of 90°, and or by applying an axial reflection to the constellation of symbols with respect to the real axis, and/or by applying an axial reflection to the constellation of symbols with respect to the complex axis, and/or by inverting all the bit values.

[0021]

In a specific embodiment, the multilevel modulation is a 256QAM modulation, and the labeling function is given by table 3 below, or by table 3 modified by rotating the constellation of symbols in the complex plane by an angle multiple of 90°, and/or by applying an axial reflection to the constellation of symbols with respect to the real axis, and/or by applying an axial reflection to the constellation of symbols with respect to the complex axis, and/or by inverting all the bit values.

[0022]

According to a second aspect, the present disclosure relates to a computer program product comprising instructions which, when executed by a processor, configure said processor to carry out a transmitting method according to any one of the embodiments of the invention.

[0023]

According to a third aspect, the present disclosure relates to a computer- readable storage medium comprising instructions which, when executed by a processor, configure said processor to carry out a transmitting method according to any one of the embodiments of the invention.

[0024]

According to a fourth aspect, the present disclosure relates to a device for transmitting a data stream to a receiving device, comprising a processing circuit configured to carry out a transmitting method according to any one of the embodiments of the invention.

[0025]

According to a fifth aspect, the present disclosure relates to a method for receiving a data stream by a receiving device, said data stream comprising m data sub-streams, comprising: receiving a symbol stream including the data stream from a transmitting device, the symbol stream including symbols of a multilevel modulation comprising m levels defining 2 ^m different symbols in a complex plane, demodulating the symbols of the symbol stream in order to produce m polar-encoded data sub-streams, by applying an inverse function of a predetermined labeling function Z which bijectively associates a symbol to a set c _l ... , c _m of ?7i bits from respective polar-encoded data sub-streams, decoding successively the m polar-encoded data sub-streams such as to produce m data sub-streams, by applying respective polar-code decoders.

[0026]

The 2 ^m symbols of the multilevel modulation used are distributed in the complex plane such that they are regularly spaced along the real axis and the complex axis by a spacing factor K, and the predetermined labeling function Z is such that:

F (Z) < 1.7™ x (0.0425 x m - 0.06) expression in which:

[0027]

In specific embodiments, the receiving method can further comprise one or more of the following features, considered either alone or in any technically possible combination.

[0028]

In a specific embodiment, each of the m polar code decoders used is designed for decoding a polar code designed for a binary input additive white Gaussian noise, AWGN, channel.

[0029]

In a specific embodiment, each polar-code decoder used is a list decoder. [0030]

According to a sixth aspect, the present disclosure relates to a computer program product comprising instructions which, when executed by a processor, configure said processor to carry out a receiving method according to any one of the embodiments of the invention.

[0031]

According to a seventh aspect, the present disclosure relates to a computer- readable storage medium comprising instructions which, when executed by a processor, configure said processor to carry out a receiving method according to any one of the embodiments of the invention.

[0032]

According to an eighth aspect, the present disclosure relates to a device for receiving a data stream from a transmitting device, comprising a processing circuit configured to carry out a receiving method according to any one of the embodiments of the invention.

[0033]

The invention will be better understood upon reading the following description, given as an example that is in no way limiting, and made in reference to the figures which show.

[Brief Description of Drawings]

[0034]

[Fig. 1]

Figure 1 is a schematic representation of an exemplary multilevel polar- coded modulation scheme.

[Fig. 2]

Figure 2 is a plot representing the mutual information for a 16QAM modulation using a Gray labeling function, and the distribution of the mutual information between the 4 bit levels.

[Fig- 3]

Figure 3 is a plot representing the mutual information for a 16QAM modulation using a random labeling function, and the distribution of the mutual information between the 4 bit levels.

[Fig. 4] Figure 4 is a plot representing the log likelihood ratio distribution at the input of the different polar code decoders of a multilevel polar-coded modulation scheme, when using a Gray labeling function.

[Fig. 5]

Figure 5 is a plot representing a preferred embodiment of a 16QAM labeling function.

[Fig. 6]

Figure 6 is a plot representing a preferred embodiment of a 64QAM labeling function.

[Fig. 7]

Figure 7 is a plot representing a preferred embodiment of a 256QAM labeling function.

[Fig. 8]

Figure 8 is a plot representing the log likelihood ratio distribution at the input of the different polar code decoders of a multilevel polar-coded modulation scheme, when using the 16QAM labeling function of figure 5.

[Fig. 9]

Figure 9 is a plot comparing the expected throughput performance for the 16QAM Gray labeling function and for the 16QAM labeling function of figure 5. [Fig. 10]

Figure 10 is a diagram representing the main steps of a transmitting method according to a preferred embodiment.

[Fig- 11]

Figure 11 is a schematic representation of a transmitting device according to a preferred embodiment.

[Fig. 12]

Figure 12 is a diagram representing the main steps of a receiving method according to a preferred embodiment.

[Fig. 13] Figure 13 is a schematic representation of a receiving device according to a preferred embodiment.

[Description of Embodiments]

[0035]

In these figures, references identical from one figure to another designate identical or analogous elements. For reasons of clarity, the elements shown are not to scale, unless explicitly stated otherwise.

[0036]

As indicated above, the present disclosure relates to a multilevel polar- coded modulation scheme.

[0037]

Figure 1 represents schematically a multilevel polar-coded modulation scheme. It is assumed, in a non-limiting manner, that the multilevel modulation comprises m levels, implying that the corresponding constellation comprises 2 ^m symbols in the complex plane. Preferably, m is higher than or equal to 4 (m > 4). Preferably, m is a power of 2, and is for instance equal to 4, equal to 6, equal to 8, etc.

[0038]

As illustrated by figure 1 , each level comprises a polar code encoder 20, such that m polar code encoders are used in parallel on the m different levels of the multilevel modulation. The m polar code encoders can be either identical or different. In preferred optional embodiments, that will be discussed hereinafter, the respective code rates of the m polar code encoders can be dynamically adapted to the propagation conditions, potentially resulting in the polar code encoders using different code rates.

[0039]

As illustrated by figure 1 , b _t represents data bits to be encoded by the polar code encoder 20 of the i-th level, that produces polar-encoded data bits . Each level of polar-encoded data bits is then fed to a symbol modulator 21 that produces a stream of symbols. The constellation modulator takes one polar-encoded data bit per level, i.e. a total of m bits (c _1; and outputs one symbol X =

Z ··· , c _m ) according to a predetermined labeling function Z. A symbol A is defined by a set of coordinates in real and complex dimensions and, as discussed above, the constellation of symbols comprises 2 ^m different symbols in the complex plane. The labeling function Z(c _lt ··· , c _m ) allows to make a one-to-one mapping between a set of m encoded data bits (c _1; ··· , c _m ) and a symbol X = Z(c _1; ··· , c _m ) . Successive sets of m polar-encoded data bits thus produce successive symbols, forming a symbol stream, i.e. a vector of symbols transmitted on respective resources.

[0040]

In the sequel, q denotes one polar-encoded data bit of the i-th level. If necessary to distinguish different polar-encoded data bits of a same level, a second subscript is used such that c _{i t} denotes the polar-encoded data bit of the i-th level that is used to produce the t-th symbol transmitted on the t-th resource. Also, h _j denotes one data bit of the i-th level, and bi corresponds to a vector comprising several data bits of the i-th level. Similarly, X and Y denote respectively one symbol and one observation. If necessary to distinguish different symbols and different observations, a subscript is used such that X _t and Y _t denote respectively the t-th symbol and the t-th observation, transmitted and observed on the t-th resource. X and F denote respectively a vector comprising T different symbols X _t (X = (¾, ·· ,X _T ) ) and a vector comprising T different observations Y _t (Ϋ = (Y _l ··· , y _r )). It is noted that the T resources can correspond to different time slots, to different frequencies (e.g. different subcarriers of an orthogonal frequency division multiplex, OFDM, symbol), different spreading codes, etc., or any combination thereof. Each symbol X _t is obtained based on a set of m polar- encoded data bits (c _{l t} , ··· , c _{m t} ) . The vector (c _{i 1} , ··· , c _{i T} ) comprising the T polar-encoded data bits for the i-th level is denoted q. Each vector q of polar- encoded data bits is obtained by encoding the vector b _t of data bits with a polar code. Each vector bi comprises a number of data bits that depends on the code rate of polar code encoder of the i-th level, and that can vary from one level to another.

[0041]

The vector X of symbols is then transmitted by a transmitting device 30 through a channel and an observation F of the vector X of symbols is obtained at a receiving device 40. The channel modifies each symbol X = Z(c ₁ , ·· , c _m ) into the observation Y according to a statistical behavior characterized by the transition probability p Y\c _l ··· , c _m ) of the channel. For example, when considering an additive white Gaussian noise, AWGN, channel, the observation Y is the result of Z(c _1; ··· , c _m plus a noise following a Gaussian distribution. [0042]

In order to properly design a multilevel polar-coded modulation, it is of interest to first characterize the model from an information theory standpoint. In general, the channel capacity is by definition the maximization of the channel mutual information I(X) Y), i.e. without taking into account any structure for the transmitting device 30 or the receiving device 40. When adding elements in the encoding/decoding structure, the mutual information decreases. For example, in an AWGN channel, by constraining the symbols to belong to a finite constellation, the mutual information I(X) Y) is lower than with a continuous Gaussian input which maximizes the channel mutual information.

[0043]

Further to constraining each symbol X to belong to a finite constellation, we constrain the system to a multilevel modulation structure. The one-to-one mapping between X = Z(c _l ··· , c _m ) and ··· , c _m ) allows to now consider l ··· , c _m ,· Y) without any loss. By using the chain rule, we obtain: expression in which 7( corresponds to the conditional mutual information.

[0044]

We can observe that by associating a code rate 7(q; Y |c _1; ... , q^) to the i- th polar-coded level, no loss of information is observed if successive cancellation decoding is performed at the receiving device (which is suggested by the knowledge of c _lt , q_ ₁ when decoding q ). By definition of the mutual information, no error occurs if the code rate is adapted to the equivalent level channel. An equivalent level channel corresponds to a virtual channel experienced by a single polar-encoded data sub-stream, the m polar-encoded data sub-streams being transmitted on m parallel equivalent level channels. In practice, when using a finite length coding scheme, errors occur and propagate from one level to another when using a successive decoding scheme. This error propagation should be as limited as possible, by design.

[0045]

We assume that the bits q are equiprobable, i.e., that the probability p(q = o) = p(q = 1) = 0.5, such that the conditional mutual information can be expressed as: expression in which:

E _Cl ... _,Crn is ^an expectation over all possible polar-encoded data bits ( , ··· , c _m }, or equivalently on all possible constellation symbols {A};

E _Y \ _{c .} .. _cm is ^an expectation over all possible observations Y when the transmitted symbol Z(c _lt ··· , c _m ) is known; it is fully characterized by the transition probability ··· , c _m )); the sum is performed over all the 2 ^m~i sets of polar-encoded data bits {c' _i+1 , ··· , c' _m } ; this marginalization makes appear the transition

Z(c _v ... , q_ _1; q, c' _i+1 , ··· , c' _m ) is the symbol with the i first polar-encoded data bits in their labeling fixed to ( , ··· , ), the same values as the i first polar- encoded data bits of the labeling of Z(c _l ··· , c _m ) selected in the expectation E _{Cl ...,cm >} and the last ( m — i ) polar-encoded data bits of the labeling of are set by the configuration (c' _i+1 , ···, c' _m ) selected in the sum å _{{c/i+1,-,c/m}} 5 thus, Z(q, ... , c^, Ci, c' _i+1 , ··· , c' _m ) is one of the multilevel modulation symbols, and p(Y\Z can be easily computed by the knowledge of the observation Y and of the channel transition probability; similarly, Z is the constellation symbol with labeling having the (i — 1) first polar-encoded data bits equal to (c _1; ··· , , the i-th polar-encoded data bit value is (1 — q) , and the last (m — i) polar-encoded data bits values are ··· , c' _m ).

[0046]

The chain rule decomposition of the Gray labeling for a 16QAM (16-level QAM) is shown in Figure 2. The sum of the 4 plots associated each to one of the 4 bit levels is indeed equal to the mutual information of the 16QAM constellation without constraint on the polar-coding scheme. We can observe that, since the Gray labeling is independent and the same on the real and imaginary parts, the mutual information of bits 1 and 3 (i.e. of the levels 1 and 3 of the multilevel modulation) and bits 2 and 4 (i.e. of the levels 2 and 4) are equal. The chain rule decomposition of a random labeling for a 16QAM is shown in Figure 3. We can observe that, for a given signal to noise ratio, SNR, the rate splitting is different from the one of Gray labeling. Yet, the sum of the rates is still equal to the mutual information of the 16QAM constellation.

[0047]

Hence, it is important to note that, from the mutual information perspective, only the vector X of symbols has an impact on the performance. The labeling function itself does not improve or degrade the overall theoretical performance. It just changes the repartition of the rate between the parallel levels of the multilevel polar-coded modulation. This remark is important as it highlights that any labeling function performs theoretically the same in view of information theory.

[0048]

However, we will see later that, when combined with a practical polar code, this remark is not true anymore. In other words, when considering practical polar codes in a multilevel polar-coded modulation context, the labeling can influence the overall actual performance, such that optimization of the labeling function can be made by taking into account the polar coding strategy of each parallel level of the multilevel polar-coded modulation.

[0049]

In the sequel, we assume that the channel is memory-less. Hence, the channel effect is independent from one transmission resource to another (e.g., additive white Gaussian noise is usually independent in time).

[0050]

Thus, the likelihood p(?|h _1; ..., f½) can be decomposed through the T resources used for transmitting the symbol vector X — (X ₁ , · · · , X _T ), as follows:

[0051]

Then, by using the fact that the encoder converts the vector of data bits b^ into a vector of polar-encoded data bits q = (q ₁ , ··· , q _r ), we can write:

[0052]

This involves that the relationship between Ϋ and b ₁ ... , b _m can be analyzed resource per resource by working on Y _t and (c _{l t} , ··· , c _{m t} ), and the associated symbol X _t = Z(c _{l t} , ··· , c _{m t} )· It is recalled that the role of the labeling function Z is to determine which symbol is uniquely associated with a polar- encoded data bit vector (c _{l t} , ··· , c _{m t} ). This allows reducing the complexity of the decoder by considering a symbol-to-bit demodulation (i.e. inverse function of the labeling function Z) performed independently on each resource.

[0053]

It is assumed that the decoder successively decodes the first level (i.e. the level with index 1), then the second level (i.e. the level with index 2), etc., until the last level (i.e. the level with index m). For instance, the decoder of the multilevel polar-coded modulation with list decoding can typically involve the following steps, performed successively for each level, from the level with index 1 to the level with index m, which include for the i-th level: obtain the data bit vectors b _lt ... , b _i-1 associated to each surviving path of the list decoding procedure; re-encode and obtain the polar-encoded data bits according to the polar code encoder of each level (this can also be done during the decoding process of bi, , hj-i), for each transmission resource with index t with observation Y _t , compute the likelihoods ^an d p(X _t \ ^c i _,t> f° ^r the obtained re-encoded data bits ..., c _{i® t} and for all the 2 ^m~l possible configurations {c' _j+1 , ··· , compute the following log-likelihood ratios, for all indexes t: expression in which _{cri+1; ··^^ corresponds to the sum over the 2 ^{m 1} possible configurations { c' _i+1 , ·· , c' _m }, and å _{ c _//£+1,-, c _//m} corresponds to the sum over the

2 ^m~l possible configurations {c" _i+1 , ··· , c" _m }; feed the input of the decoder of the i-th level with the last cumulated metric resulting from the decoding of the (i — l)-th level for each list decoding survivor, and perform the decoding to obtain the data bit vector b _t for each surviving path and the associated cumulated metric.

[0054]

It is noted that the above steps are only given for exemplary purposes, and that the decoding can be performed differently. In particular, it is possible, in other embodiments, to apply a simple successive decoding scheme without list decoding, i.e. by computing only a single survivor for each level. More generally speaking, the present disclosure is not limited to a specific decoding process, and the choice of a specific decoding process merely constitutes an exemplary embodiment of the present disclosure.

[0055]

However, the present disclosure relies on the assumption that the different levels are decoded successively at the decoder, with the level with index 1 being decoded first and the level with index m being decoded last.

[0056]

Also, the above exemplary embodiment of a successive decoding scheme has been given in order to highlight the structure of the log-likelihood ratios LLR _{i t} , which is not expected to vary significantly from a successive decoding scheme to another, and which help understanding why the labeling function can be optimized in order to increase the overall actual performance of the system, when considering practical implementations.

[0057] As previously said, practical implementations of polar code encoders and decoders correspond to polar codes designed for binary input AWGN channels. Such polar codes expect to be used on an AWGN channel with binary input, and consequently expect to have log likelihood ratios LLR^ _t at the input of the polar code decoder that follow a Gaussian distribution.

[0058]

However, when using a high order multilevel coded modulation (m > 4) with a Gray labeling, at least one of the m polar code decoders experiences an input log likelihood ratio distribution which is not Gaussian, such as illustrated in Figure 4. This leads to degraded performance.

[00593

The inventors have noticed that the labeling function influences the input log likelihood ratio distribution of the different levels, and that some labeling functions outperform the conventional Gray labeling when considering a multilevel polar-coded modulation using an off-the-shelf polar codes designed for binary input AWGN channels.

[0060]

In particular, the inventors have discovered that it is possible to find labeling functions which provide input log likelihood ratio distributions that are substantially Gaussian for all the levels of the multilevel polar-coded modulation. Hence, despite not influencing the mutual information, the labeling function does influence the overall actual performance if it enables providing the inputs of the different polar code decoders with log likelihood ratios that tend to follow the expected Gaussian distributions.

[0061]

For that purpose, the inventors have discovered that the following function could be used to identify suitable labeling functions: (1)

[0062]

In the expression (1) above: e ^x corresponds to the exponential function applied to the real number x; \z\ corresponds to the modulus (or magnitude) of the complex number z being real numbers and j being the imaginary unit);

K is a spacing factor of the symbols in the complex plane; is a sum over the 2 ^m possible values of the vector (c _x , c _m ), bijectively associated to the 2 ^m symbols of the constellation by the labeling function Z possible values of the vector (c·, ... , when excluding the specific value (q, ... , c _m ) as currently set by the sum the value of i being set by the sum for completeness, it is emphasized that, said sum and that, said sum, etc.

[0063]

More specifically, regarding the spacing factor K, defined in expression (1) above, it implies that the 2 ^m symbols of the constellation of the multilevel modulation are distributed in the complex plane such that they are regularly spaced along the real axis and the complex axis by said spacing factor K. For instance, if the sum of the 2 ^m symbols is equal to zero (i.e. the 2 ^m symbols are centered around (0,0) the center of the complex plane), then the 2 ^m symbols are in the following set: expression in which N corresponds to the set of natural integers, such that: for m = 4 (16QAM modulation): k, k! G {1,2}; for m = 6 (64QAM modulation): k, k ' G {1,2, 3, 4}; for m = 8 (256QAM modulation): k, k ' G {1,2, 3, 4, 5, 6, 7, 8}; etc.

[0064]

In general, the function F is a function that produces a value representative of fairness between the elementary distances \Z(c ₁ , ..., c _m ) — playing a role in each log likelihood ratio LLR _{i t} production for each level of the multilevel coded modulation. By optimizing the function F, i.e. by minimizing the function F, it is possible to obtain a labeling function Z for which the log likelihood ratios LLR _{i t} will tend to follow a Gaussian distribution for all the levels of the multilevel coded modulation.

[0065]

As a remark, this function F does not take into account the channel transition probabilities. It helps determining labeling functions mimicking the log likelihood ratio distribution of a binary input AWGN channel regardless the actual channel. This is a key feature of our approach, since the labeling can be used in a context where the channel is unknown at the transmitting device 30.

[0066]

As indicated above, this function F assumes that the different levels are decoded successively at the receiving device 40, with the level with index 1 being decoded first and the level with index m being decoded last.

[0067]

In order to optimize the function F, it is for instance possible to execute a genetic-like algorithm, for example by executing the following steps: initialize a labeling function Z; for example, it is possible to start from the Gray labeling or any random labeling; compute BestMetric = F(Z); repeat the following steps until a stopping criterion is verified: for all for all {c _l ··· , } copy Z into Z' find the symbols with the labeling {c _1> ,C _j = 0, , c _m ) and (c _1; ... , C _j = 1, ... , c _m ) and switch their labeling in Z' compute Metric = F(Z') if Metric < BestMetric save Z' into Zsav set BestMetric = Metric end end set Z = Zsav end

[0068]

For instance, the stopping criterion can be considered to be verified when no improvement of BestMetric is observed between two iterations. Of course other optimization algorithms can be considered and other stopping criteria can be used for optimizing the function F.

[0069]

Without necessarily optimizing the function F, i.e. without necessarily finding the specific labeling function that minimizes the function F, the inventors have observed that the labeling functions satisfying the following criterion are good in the sense that, for such labeling functions, the log likelihood ratios LLR _{i t} tend to follow a Gaussian distribution for all the levels of the multilevel coded modulation:

F(Z) < 1.7 ^m x (0.0425 x m - 0.06) (2) expression in which m, as defined previously, corresponds to the number of levels of the multilevel modulation. Of course, the conventional Gray labeling function, inter alia, does not satisfy the expression (2) since the log likelihood ratios it produces do not follow a Gaussian distribution for all levels.

[0070]

Hence: for m = 4 (16Q AM modulation): 4) « 0.9187; for m = 6 (64QAM modulation): 4.7068; for m = 8 (256QAM modulation) : g(8) ~ 19.5321; etc.

[0071]

Table 1 gives an example of labeling function Z that verifies the expression (2) above, in the case of m = 4 (16QAM modulation). In table 1, j corresponds to the imaginary unit (j ² = 1).

[0072]

Table 1 : Example of 16QAM labeling function

[0073]

Figure 5 represents the labeling function Z given by table 1 in the complex plane. In figure 5, K is assumed to be equal to 2. It should be noted that a rotation of the constellation represented in figure 5 by a multiple of 90°, or an axial reflection of said constellation with respect to the real axis, or an axial reflection of said constellation with respect to the complex axis, or an inversion of all the bit values, or any combination thereof, does not modify the value of F (Z) and therefore yields a labeling function that is equally good.

[0074]

Table 2 gives an example of labeling function Z that verifies the expression (2) above, in the case of m = 6 (64QAM modulation).

[0075]

Table 2: Example of 64QAM labeling function

[0076]

Figure 6 represents the labeling function Z given by table 2 in the complex plane. In figure 6, K is assumed to be equal to 2. It should be noted that a rotation of the constellation represented in figure 6 by a multiple of 90°, or an axial reflection of said constellation with respect to the real axis, or an axial reflection of said constellation with respect to the complex axis, or an inversion of all the bit values, or any combination thereof, does not modify the value of F (Z) and therefore yields a labeling function that is equally good.

[0077]

Table 3 gives an example of labeling function Z that verifies the expression (2) above, in the case of m = 8 (256QAM modulation).

[0078]

Table 3: Example of 256QAM labeling function

[0079]

Figure 7 represents the labeling function Z given by table 3 in the complex plane. In figure 7, K is assumed to be equal to 2. It should be noted that a rotation of the constellation represented in figure 7 by a multiple of 90°, or an axial reflection of said constellation with respect to the real axis, or an axial reflection of said constellation with respect to the complex axis, or an inversion of all the bit values, or any combination thereof, does not modify the value of F (Z) and therefore yields a labeling function that is equally good. [0080]

Figure 8 represents the input log likelihood ratio distribution for the m polar code decoders when using the 16QAM labeling function given in table 1 above, which to be compared with the input log likelihood ratio distribution for the m polar code decoders when using the Gray labeling function (figure 4). As can be seen in figure 8, thanks to the particular labeling function identified by the inventors, the input log likelihood ratio distribution is substantially Gaussian for all the m polar code decoders. This makes this specific labeling function suitable for being used with any polar-code expecting input log likelihood ratios following a Gaussian distribution at the decoder, such as those polar-codes designed for binary input AWGN channels.

[0081]

Another advantage of labeling functions verifying the expression (2) is that they enable performing simple code rate adaptation for all the polar codes used in the multilevel polar-coded modulation.

[0082]

Indeed, since these labeling functions make each level of the system behave as if it were a binary input AWGN channel, and since the performance for such a binary input AWGN channel can be easily predicted, it is possible to adapt dynamically the respective code rates of the m polar codes to the propagation conditions experienced on each level. This can be done by reusing, on each level, the existing tools for predicting the performance on the binary input AWGN channel. For instance, it is possible to compute a function Y which gives the binary input mutual information as a function of the SNR of an AWGN channel. This formula for computing the function Y is considered to be known to the skilled person for the binary input AWGN channel. Then, it is possible to compute the inverse function of Y, denoted Y ^-1 in the sequel. It should be noted that Y ^-1 needs to be computed only once, and can then be memorized in storage means of the transmitting device 30. In order to adapt the code rate of the polar code of the i -th level, it is possible to compute the conditional mutual information l(bi, Again, the formula for computing the conditional mutual information is considered to be known to the skilled person for the binary input AWGN channel. The SNR experienced on the i -th equivalent level channel, denoted q, can then be estimated as q = Once q is estimated, the code rate to be used for the polar code of the i-th level can be chosen to be Y( q). Of course, it also possible to consider a backoff BO, for instance (—1) dB in logarithmic scale, in which case the code rate to be used for the polar code of the i-th level can be chosen to be Y(BO x q).

[0083]

Figure 9 represents schematically the simulated expected throughput performance for both the 16QAM Gray labeling function and the 16QAM labeling function given in table 1 above, both in the context of a multilevel polar-coded modulation scheme as represented by figure 1, and both using polar-codes designed for binary input AWGN channels. Packets of 1024 16QAM symbols are sent. An automatic repeat request (ARQ) scheme is considered for evaluation, which involves that a packet is retransmitted when it is not correctly received. For a given SNR value, the rate splitting for each SNR is the one provided in figure 3 and defined according to the above-described procedure. The frozen bits of each of the 4 polar codes are chosen according to its rate. Figure 9 represents also the mutual information for the 16QAM multilevel polar-coded modulation, i.e. the maximum achievable throughput as defined by information theory. As can be seen in figure 9, the optimized 16QAM labeling function introduces a gain of around 1 dB over the conventional 16QAM Gray labeling function.

[0084]

Figure 10 represents schematically the main steps of a method 50 for transmitting a data stream from a transmitting device 30 to a receiving device 40. Said data stream corresponds to one or several data packets comprising binary information to be transmitted from the transmitting device 30 to the receiving device 40.

[0085]

In the present disclosure, the transmitting device 30 can be e.g. a user equipment (UE), a base station, a laptop, a tablet, a mobile phone, or any communicating object that can transmit a data stream to a receiving device 40. Similarly, the receiving device 40 can be e.g. a UE, a base station, a laptop, a tablet, a mobile phone, or any communicating object that can receive a data stream from a transmitting device 30.

[0086]

The data stream to be transmitted is assumed to comprise m data sub streams (e.g. data bit vectors b ₁ r ^, , b _m ). Said data sub-streams can be independent from one another, or can correspond to a same data stream that has been split into m data sub-streams, e.g. by using a serial to parallel converter. As indicated above, in some embodiments, the data stream and/or the data sub streams can comprise error correcting codes such as CRCs.

[0087]

As illustrated by figure 10, said transmitting method 50 comprises the following steps, executed by the transmitting device 30: a step S51 of encoding the data sub-streams with respective polar codes, such as to produce m polar-encoded data sub-streams (e.g. polar encoded data bit vectors c _lt ··· , c _m ) a step S52 of modulating the m polar-encoded data sub-streams onto symbols of a multilevel modulation comprising m levels defining 2 ^m different symbols in the complex plane, according to a predetermined labeling function Z which bijectively associates a symbol to a set (c _1; of m bits from respective polar-encoded data sub-streams, such that successive different sets of m bits from respective polar-encoded data sub-streams are converted into successive symbols forming a symbol stream (e.g. vector X); a step S53 of transmitting the symbol stream to the receiving device. [0088]

As discussed above, the 2 ^m symbols of the multilevel modulation are distributed in the complex plane such that they are regularly spaced along the real axis and the complex axis by a spacing factor K, and the labeling function Z is such that the expression (2) above is verified. By using such a labeling function, it is possible to use off-the-shelf polar codes designed for binary input AWGN channels. Accordingly, each of the m polar codes used can be, in preferred optional embodiments, a polar code designed for a binary input AWGN channel. [0089]

As indicated above, especially when using polar codes designed for a binary input AWGN channel, code rate adaptation is simple. In such a case, the transmitting method 50 can comprise, in preferred optional embodiments: determining SNRs experienced on each level by each data sub-stream during the propagation from the transmitting device 30 to the receiving device 40, on the equivalent level channel, selecting the code rates of each of the m polar codes used based on the SNRs experienced by each data sub-stream.

[0090]

For instance, the SNR determination and code rate selection can be performed as discussed above. However, other SNR determination algorithms and/or code rate selection algorithms can also be considered in other embodiments of the present disclosure.

[0091]

Figure 11 represents schematically an exemplary embodiment of a transmitting device 30 suitable for implementing the transmitting method 50. [0092]

In this exemplary embodiment, the transmitting device 30 comprises a processing circuit 31 comprising one or more processors and storage means (magnetic hard disk, solid-state disk, optical disk, electronic memory, etc.) in which a computer program product is stored, in the form of a set of program-code instructions to be executed in order to implement all or a part of the steps of the transmitting method 50. Alternatively, or in combination thereof, the processing circuit 31 can comprise one or more programmable logic circuits (FPGA, PLD, etc.), and/or one or more specialized integrated circuits (ASIC), and/or a set of discrete electronic components, etc., adapted for implementing all or part of said steps of the transmitting method 50.

[0093]

The transmitting device 30 comprises also a communication unit 32, coupled to the processing circuit 31, allowing said transmitting device 30 to transmit the symbol stream. The communication unit 32 is preferably a wireless communication unit, in which case it corresponds to a radiofrequency circuit comprising components (antenna(s), amplifier(s), local oscillator(s), mixer(s), analog and/or digital filter(s), etc.) considered known to the skilled person.

[0094]

In other words, the processing circuit 31 and the communication unit 32 of the transmitting device 30 form a set of means configured by software (specific computer program product) and/or by hardware (processor, FPGA, PLD, ASIC, discrete electronic components, radiofrequency circuit, etc.) to implement all or part of the steps of the transmitting method 50.

[0095]

Figure 12 represents schematically the main steps of a method 60 for receiving a data stream by a receiving device 40, the data stream comprising m data sub-streams transmitted by using the transmitting method 60.

[0096]

As illustrated by figure 12, said receiving method 60 comprises the following steps, executed by the receiving device 40: a step S61 of receiving the symbol stream (e.g. vector F) including the data stream, a step S62 of demodulating the symbols of the symbol stream in order to produce m polar-encoded data sub-streams, by applying an inverse function of the labeling function Z, a step S63 of decoding successively the m polar-encoded data sub-streams such as to produce m data sub-streams, by applying respective polar-code decoders.

[0097]

It should be noted that the demodulating S62 and decoding S63 steps can be performed simultaneously, by performing joint demodulation / decoding. [0098]

Of course, the polar code decoders used are adapted to the polar code encoders used by the transmitting device 30. Hence, in preferred embodiments, each of the m polar code decoders used is designed for decoding a polar code designed for a binary input AWGN channel. In preferred embodiments, each polar-code decoder used in the decoding step S63 is a list decoder. The list decoder is considered to be known to the skilled person.

[0099]

Figure 13 represents schematically an exemplary embodiment of a receiving device 40 suitable for implementing the receiving method 60.

[0100]

In this exemplary embodiment, the receiving device 40 comprises a processing circuit 41 comprising one or more processors and storage means (magnetic hard disk, solid-state disk, optical disk, electronic memory, etc.) in which a computer program product is stored, in the form of a set of program-code instructions to be executed in order to implement all or a part of the steps of the receiving method 60. Alternatively, or in combination thereof, the processing circuit 41 can comprise one or more programmable logic circuits (FPGA, PLD, etc.), and/or one or more specialized integrated circuits (ASIC), and/or a set of discrete electronic components, etc., adapted for implementing all or part of said steps of the receiving method 60.

[0101]

The receiving device 40 comprises also a communication unit 42, coupled to the processing circuit 41, allowing said receiving device 40 to receive the symbol stream. The communication unit 42 is preferably a wireless communication unit, in which case it corresponds to a radioffequency circuit comprising components (antenna(s), amplifier(s), local oscillator(s), mixer(s), analog and/or digital filter(s), etc.) considered known to the skilled person.

[0102]

In other words, the processing circuit 41 and the communication unit 42 of the receiving device 40 form a set of means configured by software (specific computer program product) and/or by hardware (processor, FPGA, PLD, ASIC, discrete electronic components, radiofrequency circuit, etc.) to implement all or part of the steps of the receiving method 60.

[0103]

The above description clearly illustrates that by its various features and their respective advantages, the present disclosure reaches the goals set for it. In particular, by optimizing the labeling function such as to produce log likelihood ratios which follow a Gaussian distribution for all the levels of the multilevel polar-coded modulation, it is possible to have a simple and efficient multilevel polar-coded modulation scheme that can use off-the-shelf polar codes designed for a binary input AWGN channel. Also, such a multilevel polar-coded modulation scheme can provide predictable performance on each of the levels, which is suitable for allowing simple code rate adaptation, if necessary.