Patent Description:
Polar codes are proposed as channel codes for use in future wireless communications, and have been selected for uplink and downlink enhanced Mobile Broadband (eMBB) control channel coding for the new <NUM>th Generation (<NUM>) air interface, also known as the <NUM> New Radio (NR). These codes are competitive with state-of-the-art error correction codes and have low encoding complexity. Successive Cancellation (SC) decoding and its extensions (e.g., SC List decoding) are effective and efficient options for decoding polar coded information.

Polar codes employ channel polarization to theoretically reach channel capacity. Polarization refers to a coding property that, as code length increases to infinity, bit-channels (also referred to as sub-channels) polarize and their capacities approach either zero (completely noisy channel) or one (completely perfect channel). In other words, bits encoded in high capacity sub-channels will experience a channel with high Signal-to-Noise Ratio (SNR), and will have a relatively high reliability or a high likelihood of being correctly decoded, and bits encoded in low capacity sub-channels will experience a channel with low SNR, and will have low reliability or a low possibility to be correctly decoded. The fraction of perfect bit-channels is equal to the capacity of this channel.

Improved channel codes or channel coding methods are generally desired. While improvements to conventional polar codes and to other channel codes have been proposed, even more improvements are possible to benefit encoding and decoding performance.

<CIT> relates to polar code decoding method and decoder. <CIT> relates to method and apparatus for parallel decoding of polar codes.

<NPL>, relates to Polarization-adjusted convolutional (PAC) codes.

<NPL>), relates to parallel decoders of polar codes.

Examples of implementations will now be described in greater detail with reference to the accompanying drawings.

<FIG> is a diagram showing, by way of an illustrative example, how a polar coding generator matrix can be produced from a kernel G2 <NUM>. Note that <FIG> is an example. Other forms of kernel are also possible.

A polar code can be formed from a Kronecker product matrix based on a seed matrix F = G<NUM> <NUM>. For a polar code having codewords of length N = <NUM>m, the generator matrix is G<NUM> ⊗m. The <NUM>-fold Kronecker product matrix G<NUM> ⊗<NUM> <NUM> and the <NUM>-fold Kronecker product matrix G<NUM> ⊗<NUM> <NUM> in <FIG> are examples of polar coding generator matrices. The generator matrix approach illustrated in <FIG> can be expanded to produce an m-fold Kronecker product matrix G<NUM> ⊗m.

<FIG> shows an example use of a polar coding generator matrix for producing codewords and <FIG> shows a schematic illustration of an example polar encoder. In <FIG>, the generator matrix G<NUM> ⊗<NUM> <NUM> is used to produce codewords of length <NUM><NUM> = <NUM>. A codeword x is formed by the product of an input vector u = [<NUM><NUM><NUM> u<NUM> <NUM> u<NUM> u<NUM> u<NUM>] and the generator matrix G<NUM> ⊗<NUM> <NUM> as indicated at <NUM>. The input vector u is composed of information bits and fixed or frozen bits. In the specific example shown in <FIG>, N=<NUM>, so the input vector u is an <NUM>-bit vector, and the codeword x is an <NUM>-bit vector. The input vector has frozen bits in positions <NUM>,<NUM>,<NUM> and <NUM>, and has information bits at positions <NUM>,<NUM>,<NUM>, and <NUM>. An example implementation of an encoder that generates codewords is indicated in <FIG>at <NUM>, where the frozen bits are all set to <NUM>, and the circled "+" symbols represent modulo <NUM> addition. For the example of <FIG>, an N = <NUM>-bit input vector is formed from K = <NUM> information bits and N-K = <NUM> frozen bits. Codes of this form are referred to as polar codes and the encoder is referred to as a polar encoder. Decoders for decoding polar codes are referred to as polar decoders. Frozen bits are set to zero in the example shown in <FIG>. However, frozen bits could be set to other bit values that are known to both an encoder and a decoder. For ease of description, all-zero frozen bits are considered herein, and may be generally preferred.

As is known, polar coding may be performed with or without bit reversal. The example polar encoder in <FIG> is without bit reversal.

Generally, the output of a polar encoder can be expressed as <MAT>, where, without bit reversal, GN = F⊗n is an N-by-N generator matrix, N = <NUM>n, n ≥ <NUM> (e.g. for n= <NUM>, G<NUM> = F (indicated as <NUM> in <FIG>)). For bit reversal, GN = BNF⊗n, where BN is an N-by-N bit-reversal permutation matrix.

Implementations disclosed herein could be implemented without or with bit reversal.

In polar code construction, ideally the more "reliable" positions of an input vector are used to carry the information bits, and the more "unreliable" positions of an input vector are used to carry the frozen bits (i.e., bits already known to both encoder and decoder). However, when information is transmitted over a physical channel, the reliability of a given bit position is also a function of the characteristics of the physical channel, such as the erasure rate or the Signal-to-Noise Ratio (SNR) of the physical channel. A reliability sequence (reliable and unreliable positions) could be calculated based on assumed or measured characteristics of the physical channel before the information is transmitted over the channel, for example. In theory, the frozen bits can be set to any value as long as the location of each frozen bit is known to both the encoder and the decoder. In conventional applications, the frozen bits are all set to zero.

With a sufficiently long code length, a code designed according to polarization theory can reach the channel capacity in a binary symmetric memoryless channel if a Successive Cancellation (SC) decoding algorithm is used. A very simple SC decoding algorithm was analyzed and simulated by Arikan.

In practice, a code length cannot be infinite and a channel cannot be a binary memoryless channel, and therefore channel capacity cannot be reached by such a simple SC decoder. According to Arikan, the channel capacity can be approached when using SC decoding if a code length is over <NUM><NUM> bits in an AWGN channel. Such a long code length is impractical in wireless communications, for example.

During encoding, an N-bit input vector could be formed from K information bits, including optional cyclic redundancy check (CRC) bits, and (N - K) frozen bits. In this example, starting with a number of input bits, a CRC is calculated and appended to the input bits to produce a set of K information bits including the input bits and the CRC bits. The remaining (N - K) frozen bits are inserted to produce an N-bit input vector, where N is a power of <NUM> in an Arikan polar code. The input vector is then multiplied by a generator matrix for a polar code to produce an N-bit codeword.

The codeword is transmitted over a channel, and a receiver, in turn, receives a word. Due to channel effects such as noise, the received word might not be identical to the transmitted codeword. A decoder attempts to decode the received word to determine information bits in the original input vector.

During decoding of a codeword encoded from an input vector, the locations and values of frozen bits in the input vector are treated as known. For descriptive simplicity, bits of the input vector that are not known to the decoder in advance will be referred to as "unknown" bits. For example, the information bits including any CRC bits are unknown bits. Some polar decoders use SC decoding as noted above, in which the unknown bits are decoded sequentially and successive cancellation is applied. Once a particular decision has been made regarding how an unknown bit is to be decoded, SC polar decoders do not allow that bit to be changed or corrected, and the decoder moves on to decoding the next unknown bit.

An extension of the SC polar decoding algorithm is known as List or SCL decoding. In a List decoder, successive levels of a binary decision tree are generated, each level corresponding to a decision on a respective unknown bit. Each (decoding) path in the decision tree from the root node to leaf nodes represents a possible partial decoded sequence of unknown bits and has a corresponding likelihood. Typically, during generation of the decision tree, at each level of the decision tree where the number of paths grows beyond a set threshold L, the L paths having the highest likelihoods are identified, and the remaining paths are discarded. Some List decoders may also make use of CRC bits included in the codeword to assist in decoding. For example, if the codeword includes encoded CRC bits for the previous information bits, then once the decision tree is generated, each of the surviving paths that corresponds to decoded information bits is checked against the CRC bits represented in each of those surviving paths. The decoder then outputs as a decoded vector the information bits in the surviving path that passes the CRC check.

<FIG> is a diagram showing a portion of an example decision list tree <NUM> used in an SCL polar decoder, whose width is limited by a maximum given list size L. In <FIG> the list size L is <NUM>. Five levels <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of the decision tree are illustrated. Although five levels are illustrated, it should be understood that a decision tree to decode K information bits (including CRC bits) would have K + <NUM> levels. At each level after the root level <NUM>, each one of up to <NUM> surviving decoding paths is extended by one bit. The leaf or child nodes of root node <NUM> represent possible choices for a first bit, and subsequent leaf nodes represent possible choices for subsequent bits. The decoding path from the root node <NUM> to leaf node 330a, for example, represents an estimated codeword bit sequence: <NUM>, <NUM>, <NUM>, <NUM>. At level <NUM>, the number of possible paths is greater than L, so L paths having the highest likelihood (e.g. best Path Metrics) are identified, and the remaining paths are discarded. The decoding paths that survive after the path sort at level <NUM> are shown in bold in <FIG>. Similarly, at level <NUM>, the number of possible paths is again greater than L, so the L paths having the highest likelihood (best PMs) are identified, and the remaining paths are again discarded. In the example shown, the paths terminating in leaf nodes 330a, 330b, 330c, and 330d represent the highest likelihood paths. The paths terminating in leaf nodes 340a, 340b, 340c, 340d are the lower likelihood paths which are discarded.

In an Additive White Gaussian Noise (AWGN) channel, a polar code in effect divides a channel into N sub-channels, where N is referred to as mother code length and is always a power of <NUM> in an Arikan polar code, which is based on a polar kernel that is a <NUM>-by-<NUM> matrix. A key to code construction for a polar code is to determine which bit-channels, also referred to herein as sub-channels, are selected or allocated for information bits and which sub-channels are allocated for frozen bits. In some implementations, one or more sub-channels are also allocated to parity, CRC, and/or other types of bits that are used to assist in decoding. In terms of polarization theory, the sub-channels that are allocated for frozen bits are called frozen sub-channels, the sub-channels that are allocated for information bits are called information sub-channels, and additional assistant sub-channels may be allocated to assistant bits that are used to assist in decoding. In some implementations, assistant bits are considered to be a form of information bits, for which more reliable sub-channels are selected or allocated.

Polar encoders based on Kronecker products of a <NUM>-by-<NUM> Arikan kernel G<NUM> are described above. <FIG> is a block diagram illustrating an example of a polar encoder <NUM> based on a <NUM>-by-<NUM> kernel. Sub-channels and coded bits are labeled in <FIG>. A channel is divided into N sub-channels by a polar code as noted above. An information block and frozen bits are allocated onto the N sub-channels, and the resultant N-sized vector is multiplied with an N-by-N Kronecker matrix by the polar encoder <NUM> to generate a codeword that includes N coded bits. An information block includes at least information bits and could also include assistant bits such as CRC bits or parity check bits. A sub-channel selector (not shown) could be coupled to the polar encoder <NUM> to select sub-channels for information bits and any assistant bits, with any remaining sub-channels being frozen sub-channels. Sub-channel selection is based on reliabilities of the sub-channels, and typically the highest reliability sub-channels are selected as information sub-channels for carrying information bits.

For polar codes that are based on a <NUM>-by-<NUM> kernel and an N-by-N Kronecker matrix, N is a power of <NUM>. This type of kernel and polar codes based on such a kernel are discussed herein as illustrative examples. Other forms of polarization kernels with a different size (or number of inputs) could be generally characterized by code length N = Dn, where D is the dimension (i.e., size or number of inputs) of the applied kernel. In addition, polarization kernels such as other prime-number kernels (e.g. <NUM>-by-<NUM> or <NUM>-by-<NUM>) or combinations of (prime or non-prime number) kernels to produce higher-order kernels could yield polarization among code sub-channels. It should also be noted that coded bit processing such as puncturing, shortening, zero padding, and/or repetition could be used in conjunction with polar codes that are based on <NUM>-by-<NUM> kernels or other types of kernels, for rate matching and/or other purposes for example.

The low minimum distance of polar codes for small to moderate size codewords, combined with low complexity SC decoding, may negatively affect performance. Therefore, new ideas to further exploit channel polarization and improve performance of polar codes are of interest.

A new class of code, referred to as a Polarization-Adjusted Convolutional (PAC) code, was proposed in <NPL>. With a PAC code, Arikan introduced an outer convolutional code prior to a polar transform to exploit the channel capacity of frozen-bit channels and achieve better code performance for small to moderate size codewords.

The Arikan PAC code uses a convolutional outer code to encode K information bits and N-K frozen bits and generates an N-bit output vector, and then applies an N-by-N polar transform to the convolutionally encoded data. Finally, an N-bit message is transmitted on a communication channel. At the decoder, the Arikan PAC code can be processed using a Fano decoding algorithm, for example. Using the same path metric as an SCL decoder, the decoder explores multiple decoding paths on the SC tree according to the Fano algorithm.

Arikan concludes that a PAC code is more sensitive to the frozen and information sub-channel selection than to the convolution polynomial. For an Arikan PAC code, a random convolution polynomial is acceptable as long as length of the polynomial is sufficiently large.

Although a PAC code can still be decoded with SC decoding, including SCL, SC-Flip, SC-Fano and other variants of SC-based decoding algorithms, PAC coding adds a new constraint to a decoding algorithm. At the encoder, message bits are sequentially processed by a convolutional encoder, starting with message bit #<NUM> and ending with bit #N-<NUM>. The value of bit #x changes the state of the convolution encoder, and thus contributes to the encoding results of bits #x+<NUM> to #N-<NUM>. At the decoder, the same bit sequence must be executed because the state of the convolutional decoder must include the estimated value of bits #<NUM> to #x-<NUM> before estimating the post-convolution value of bit #x.

<FIG> is a block diagram illustrating a PAC coding scheme <NUM>. PAC encoding includes rate profiling at <NUM>, convolutional encoding at <NUM>, and a polar transform at <NUM> using the following parameters: N (power-of-<NUM> code length), K (information block length), A (score function to select K sub-channels to carry the message) and c (convolution polynomial).

The rate profiling operation at <NUM> involves selection of K sub-channels or indices of an N-bit codeword <NUM> and inserting the K-bit message <NUM> inside those K positions. The value of the remaining N-K positions are frozen sub-channels or positions and have a fixed known value, such as <NUM>. As shown at <NUM>, a one-to-one convolution operation, also referred to herein as convolutional encoding, follows the rate profiling at <NUM>. The state of a convolutional encoder that is configured to perform convolutional encoding is re-initialized to <NUM> at the start of every codeword. All message bits are convolutionally encoded from bit #<NUM> to #N-<NUM> to generate N convolutionally encoded bits at <NUM>. An N-by-N polar transform, based on the <NUM>-by-<NUM> polar code kernel in this example, is applied to the N-bit convoluted codeword <NUM> to generate a PAC-encoded message that is transmitted over a physical channel <NUM>.

At a receiver, PAC decoding of a received word is performed at <NUM> to recover an N-bit message <NUM>, from which K information bits <NUM> are extracted at <NUM>.

<FIG> is a block diagram illustrating a PAC coding system <NUM>, which includes a rate profiler <NUM>, a PAC code encoder <NUM>, a channel <NUM>, a PAC code decoder <NUM>, and a data extractor <NUM>. The PAC code encoder <NUM> includes a convolutional encoder <NUM> and a polar encoder <NUM>, and the PAC code decoder <NUM> includes a polar decoder <NUM> and a convolutional decoder <NUM>.

The system <NUM> implements an N=<NUM>, K=<NUM>, A={<NUM>,<NUM>,<NUM>,<NUM>} PAC code. The PAC code encoder <NUM> and the PAC code decoder <NUM> each combine a polar transform stage, illustrated as the polar encoder <NUM> and the polar decoder <NUM>, and a convolution stage, illustrated as the convolutional encoder <NUM> and the convolutional decoder <NUM>. The post-convolution value of each frozen sub-channel is known a-priori, and is used by the PAC decoder <NUM> to measure the correctness of the decoding path. For a frozen bit position, which includes sub-channels <NUM>,<NUM>,<NUM>,<NUM> in the example shown, the input value to the convolutional decoder <NUM> is predicted assuming the value of v̂x = <NUM>, where x=<NUM>, <NUM>,<NUM>,<NUM> for this example. If the actual value of ûx differs from the predicted value of ûx, then the value of ûx, is flipped to match the predicted value of ûx and the decoding path is penalized. The polar partial sum is then calculated by the polar decoder <NUM> with the predicted value of ûx, or another fixed frozen bit value, before the value of ûx+<NUM> can be estimated. For an information bit position, the estimated value of ûy, where y=<NUM>,<NUM>,<NUM>,<NUM> in the example shown, is fed from the polar decoder <NUM> to the convolution decoder <NUM> to generate the v̂y value. An incorrect information bit estimated value for ûy will impact the following pre-convolution frozen bit prediction values and consequently the overall correctness of the decoding path.

Codeword decoding latency, decoder hardware complexity, and performance of a code are keys for a successful channel coding solution. Polar code performance improves as the code length increases. However, longer codewords increase decoding latency and require larger and more complex decoders. Therefore, it is generally desirable to have a high performance code with a short decoding latency achieved by a low complexity decoder.

According to an aspect of the present disclosure, segmentation is applied to PAC coding. Segmenting a long codeword may reduce decoding latency and improve hardware efficiency. For example, consider a non-segmented polar code with N=<NUM> and K=<NUM>. An <NUM>-by-<NUM> polar transform is applied to an input vector that includes at least information bits and frozen bits to generate a codeword, and at a decoding side, an SC-based decoder sequentially recovers the input vector. As disclosed herein, an encoder may apply a segmentation transform, such as interleaving, a reverse polar transform, or potentially some other form of permutation, to an input vector to generate multiple segments that can be separately encoded according to a polar code. Constraints over the segmentation transform may be derived from the input vector to enable information bits to be estimated from bits that are decoded by separate segment decoding.

In the context of an N=<NUM> polar code and segmentation into two segments, for example, separate N/<NUM> polar encoding is performed on each segment to generate an <NUM>-bit output vector that includes two distinct N/<NUM>-bit sub-codewords or segment codewords. These N/<NUM>-bit sub-codewords have their own respective channel LLR inputs (ŷ), and because of segmentation, the two sub-codewords can share the same decoder and be processed sequentially, or each sub-codeword can have its own decoder for parallel decoding. After the separate length N/<NUM> decoding, the recovered segments are combined back together and the original information block is recovered.

Similarly to parity check (PC) polar codes, the outer convolutional code of a PAC code introduces a "self-checking" capability that can be used in a decoder to measure correctness of a decoding path. Also, with segmentation, the continuation of the state of a convolutional decoder across consecutive segments acts as a form of "cross-checking" capability between segments.

Segmentation of PAC codes as disclosed herein is compatible with existing SC-based decoding algorithms, such as SC, SCL, SC-Fano, Fast-SSC, and other variants of SC-based decoding algorithms.

In comparison to N-based decoding, decoding of two sub-codewords of length N/<NUM> involves a lower complexity decoder implementation. Depending on the decoding algorithm, complexity saving can reach <NUM>% in this example of two segments.

The decoding latency of N/<NUM>-bit sub-codewords may also be less than the decoding latency of an N-bit codeword with the same or a similar code rate.

Generally speaking, coding design and coding systems sized for N-bit codewords also work for shorter codewords have a length smaller than N.

Given a set of parameters (K, N, A, c), where K is the information block length, N is the power-of-two mother code length, A is the set of indices to carry the information block, and c is the convolution impulse response (polynomial), PAC code construction for an N-bit codeword can be segmented in two sub-codewords of length N/<NUM>. These sub-codewords are associated with two segments, and are referred to herein as segment #<NUM> and #<NUM> codewords for ease of reference. At the decoder, the N/<NUM>-bit segment #<NUM> and #<NUM> codewords are processed by one or more decoders either in sequence or in parallel.

Different examples of segmented codes and related apparatus, methods, and systems are presented herein. Implementations may involve different operations during an encoding / decoding sequence, but enable parallel or otherwise lower complexity and/or lower latency decoding at a receiver.

<FIG> is a block diagram illustrating an example PAC coding system <NUM> with code segmentation based on outer code segment interleaving. In <FIG> and some of the subsequent drawings, an N=<NUM>, K=<NUM> code with information bits at sub-channel indices #<NUM>, #<NUM>, #<NUM> and #<NUM> is used as an illustrative and non-limiting example, and data flows from left to right and from top to bottom.

The example PAC coding system <NUM> includes a rate profiler <NUM>, a PAC code encoder <NUM>, a channel <NUM>, a PAC code decoder <NUM>, and a data extractor <NUM>, coupled together to receive inputs and provide outputs as shown. The PAC code encoder <NUM> includes a convolutional encoder <NUM> and a polar encoder <NUM> coupled to the convolutional encoder, and the PAC code decoder <NUM> includes a polar decoder <NUM> and a convolutional decoder <NUM> coupled to the polar decoder. The polar encoder <NUM> includes two segment encoders <NUM>, <NUM>, and the polar decoder <NUM> includes two segment decoders <NUM>, <NUM>. In addition to these elements of a PAC code encoding and decoding chain, the example PAC coding system <NUM> in <FIG> also includes interleaver modules or stages, shown as a segment interleaver <NUM> and a segment de-interleaver <NUM>.

The elements shown in <FIG> may be implemented in any of various ways. For example, these elements may be implemented using hardware or circuitry, examples of which are provided elsewhere herein, including hardware or circuitry configured to execute software. In an implementation, the rate profiler <NUM> and the data extractor <NUM> are implemented in hardware or circuitry to map data to and extract data from sub-channels. The segment interleaver <NUM> and the segment de-interleaver <NUM> include or otherwise implement cross-connections between inputs and outputs in order to produce interleaved and de-interleaved sequences as shown. The convolutional encoder <NUM> and the convolutional decoder <NUM> may be implemented using shift registers and one or more adders, and examples are provided elsewhere herein. Example structures for the polar encoder <NUM> and the polar decoder <NUM> are shown in <FIG> as modulo-<NUM> adders. Examples of the channel <NUM> over which codewords may be transmitted and received are provided elsewhere herein.

These are illustrative example implementations of the elements shown in <FIG>. Other implementations are also possible.

At the input side of the PAC code encoder <NUM>, the outer code segment interleaver <NUM> is coupled to the rate profiler <NUM>, to interleave the sub-channels from the rate profiler <NUM>. In the example shown, the segment interleaver <NUM> is configured to interleave the sub-channels such that all odd index sub-channels are relocated, permuted, or reordered as the first inputs into the convolution encoder <NUM>, followed by all even index sub-channels. As shown, input order into the convolutional encoder <NUM> is <NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>. The polar transform is then applied by the polar encoder <NUM> in two steps or stages, to allow the separate encoding of segment #<NUM> (even sub-channels) and segment #<NUM> (odd sub-channels) by the segment encoders <NUM>, <NUM>.

At the decoder, segment #<NUM> is processed first and the values of <MAT> (where x=<NUM>,<NUM>,<NUM>,<NUM>) are estimated. Then segment #<NUM> is decoded, taking into consideration the ûx values to generate the values of ûy (where y=<NUM>,<NUM>,<NUM>,<NUM>) before the convolutional decoding stage implemented by the convolutional decoder <NUM>. Once all bits of vector v̂' are ready, the sub-channels are re-ordered by the outer code segment de-interleaver <NUM>, before data extraction by the data extractor <NUM>.

A PAC code segmentation approach based on segment interleaving as shown by way of example in <FIG> may be advantageous in that it enables a single decoder module to be used at the decoder side, and sized for codewords of length N/<NUM> instead of length N, to sequentially process the segments. Therefore, although the segment decoders <NUM>, <NUM> are shown separately in <FIG>, a single segment decoder could be shared between segments. An alternative implementation could have a dedicated decoder or decoder instance per segment, for parallel decoding. However, because of the convolutional outer code convolution, decoded segment #<NUM> is used in processing segment #<NUM>. To maximize or at least increase hardware utilization in implementations with a decoder or decoder instance for each segment, one segment decoder such as the segment #<NUM> decoder <NUM> in <FIG> can be active and processing a segment from a next codeword while the other decoder(s) such as the segment #<NUM> decoder <NUM> in <FIG> completes the decoding of a current codeword.

Also, depending on the particular type of decoding that is implemented, a smaller codeword length can result in short decoding latency. For example, an SC-Fano decoder tracking a decoding path metric may have its search space reduced considerably when finding the decoding path of a <NUM>-bit codeword compared to a <NUM>-bit codeword.

<FIG> is a plot of performance results from simulations, and includes a reference trace for non-segmented PAC coding and a trace for PAC coding with segmentation using outer code segment interleaving, for an N=<NUM>, K=<NUM> PAC code and Fano-based decoding. Similar or different results might be observed under different simulation conditions, and/or under similar or different operating conditions.

The simulation results show that PAC code segmentation does not degrade code performance. The two traces nearly entirely overlap over most of the range shown in <FIG>, with a Frame Error Rate (FER) gain at 4dB for segmented PAC coding relative to non-segmented PAC coding (<NUM>. 9E-<NUM> versus <NUM>. Substantially the same error performance for segmented and non-segmented PAC coding is expected in this example, because the polar transform that is applied in PAC coding with a power-of-<NUM> mother code length for the polar coding stage is based on expansion of a <NUM>-by-<NUM> kernel. For example, the polar transform applied by the polar encoder <NUM> in <FIG> strictly follows the <NUM>-by-<NUM> expansion of the polar <NUM>-by-<NUM> kernel, and therefore it is expected that error performance of the polar code in <FIG>, and at least some other implementations herein, will remain substantially the same as for a non-segmented polar code.

<FIG> is a block diagram illustrating an example PAC coding system <NUM> with code segmentation based on outer code bit interleaving. In <FIG>, as in <FIG>, an N=<NUM>, K=<NUM> code with information bits at sub-channel indices #<NUM>, #<NUM>, #<NUM> and #<NUM> is used as an illustrative and non-limiting example, and data flows from left to right and from top to bottom.

The example PAC coding system <NUM> includes a rate profiler <NUM>, a PAC code encoder <NUM>, a channel <NUM>, a PAC code decoder <NUM>, and a data extractor <NUM>, coupled together to receive inputs and provide outputs as shown. The PAC code encoder <NUM> includes a convolutional encoder <NUM> and a polar encoder <NUM> coupled to the convolutional encoder, and the PAC code decoder <NUM> includes a polar decoder <NUM> and a convolutional decoder <NUM> coupled to the polar decoder. The polar encoder <NUM> includes two segment encoders <NUM>, <NUM>, and the polar decoder <NUM> includes two segment decoders <NUM>, <NUM>.

The segments in <FIG> are not grouped together as in <FIG>, and therefore the segment encoders <NUM>, <NUM> and the segment decoders <NUM>, <NUM> are each illustrated with multiple blocks. With reference to the segment encoder <NUM>, only one block is labeled in order to avoid further congestion in the drawing. The dotted line blocks in the polar encoder <NUM> are part of a segment #<NUM> encoder <NUM>. Similarly, the blocks that are shown in a "- · · -" pattern in the polar encoder <NUM> are part of a segment #<NUM> encoder <NUM>. In the polar decoder <NUM>, the dotted line blocks are part of a segment #<NUM> decoder <NUM> and the blocks that are shown in a "- · · -" pattern are part of a segment #<NUM> decoder <NUM>.

These elements in <FIG> implement a PAC code encoding and decoding chain. <FIG> also includes interleaver modules or stages, shown as a bit interleaver <NUM> and a bit de-interleaver <NUM>.

The example implementations provided above for the elements of <FIG> also apply to <FIG>, and as noted above for <FIG>, other implementations of <FIG> are also possible.

Instead of segment interleaving as shown in <FIG>, PAC code segmentation in the example coding system <NUM> in <FIG> is based on outer code bit interleaving. The outer code bit interleaver <NUM> is coupled to the rate profiler <NUM>, to bit interleave sub-channels. In the example shown, the segment interleaver <NUM> is configured to bit interleave the sub-channels such that odd and even index sequence is reversed on a pair-wise basis. At the input of the convolutional encoder <NUM>, the bit sequence is <NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>. The polar transform applied by the polar encoder <NUM>, still compliant to the <NUM>-by-<NUM> polar kernel to preserve or at least substantially preserve the code error performance, is reorganized to enable segmentation. The segmented polar transform is illustrated with separated blocks as noted above, to show the bit sequence for encoding, and similarly for decoding at the polar decoder <NUM>. These blocks, even if separated in the block diagram of <FIG>, allow separate segment #<NUM> and #<NUM> encoding and decoding of even and odd sub-channels, respectively.

At the polar decoder <NUM>, separate sequential or parallel decoding can still be performed, with a dependency from segment #<NUM> into segment #<NUM> for each decoded bit. Although the implementation of segmentation is different between <FIG> and <FIG>, segment decoding in <FIG> may be similar to that in <FIG>, with segment #<NUM> decoding being performed before segment #<NUM> decoding, sub-channels being re-ordered by the outer code bit de-interleaver <NUM> when the bits of vector v̂' are ready, and then data being extracted by the data extractor <NUM>.

Bit-based segmentation as shown by way of example in <FIG> may offer benefits similar to those described herein for outer code segment interleaving in terms of decoder latency, decoder complexity, or both.

<FIG> is a plot of further performance results from simulations, and includes a reference trace for non-segmented PAC coding and a trace for PAC coding with segmentation using outer code bit interleaving, for an N=<NUM>, K=<NUM> PAC code and Fano-based decoding. Similar or different results might be observed under different simulation conditions, and/or under similar or different operating conditions.

These simulation results show that bit-based PAC code segmentation does not degrade code performance. The two traces nearly entirely overlap over most of the range shown in <FIG>, with an FER gain observed for segmented PAC coding relative to non-segmented PAC coding above about 3dB.

Interleaving may be applied as a segmentation transform in some implementations, but interleaving is not mandatory for PAC code segmentation. <FIG>, for example, is a block diagram illustrating an example PAC coding system with code segmentation based on a reverse polar transform.

Similar to the implementations in <FIG> and <FIG>, the example PAC coding system <NUM> in <FIG> is based on an N=<NUM>, K=<NUM> code with information bits at sub-channel indices #<NUM>, #<NUM>, #<NUM> and #<NUM> as an illustrative and non-limiting example, and includes a rate profiler <NUM>, a PAC code encoder <NUM>, a channel <NUM>, a PAC code decoder <NUM>, and a data extractor <NUM>, coupled together to receive inputs and provide outputs as shown. The PAC code encoder <NUM> includes a convolutional encoder <NUM> and a polar encoder <NUM> coupled to the convolutional encoder, and the PAC code decoder <NUM> includes a polar decoder <NUM> and a convolutional decoder <NUM> coupled to the polar decoder. The polar encoder <NUM> includes two segment encoders <NUM>, <NUM>, and the polar decoder <NUM> includes two segment decoders <NUM>, <NUM>. As in <FIG>, the segments in <FIG> are not grouped together, and therefore the segment encoders <NUM>, <NUM> and the segment decoders <NUM>, <NUM> are illustrated with multiple blocks and different line patterns. At the polar encoder <NUM>, <NUM> denotes a segment #<NUM> encoder and <NUM> denotes a segment #<NUM> encoder, and at the polar decoder <NUM>, <NUM> denotes a segment #<NUM> decoder and <NUM> denotes a segment #<NUM> decoder.

These elements in <FIG> implement a PAC code encoding and decoding chain, and the example implementations provided above for such PAC code encoding and decoding chain elements with reference to <FIG> also apply to <FIG>. In addition to these elements, the example PAC coding system <NUM> in <FIG> also includes reverse polar transform elements <NUM>, <NUM>. The reverse polar transform elements <NUM>, <NUM> implement modulo <NUM> addition, and may be implemented using modulo <NUM> adders or XOR gates, for example. Other options for implementing modulo <NUM> addition may also or instead be applied to the reverse polar transform elements <NUM>, <NUM>.

At the encoding side of the example PAC coding system <NUM>, the sub-channel sequence is maintained as <NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM> for input to the convolutional encoder <NUM>. The reverse polar transform applied at the reverse polar transform element <NUM> in effect flips or reverses the modulo-<NUM> addition before the segment encoders <NUM>, <NUM> such that the ux value contributes to the ux+<NUM> value for x=<NUM>,<NUM>,<NUM>,<NUM>, instead of strictly following the <NUM>-by-<NUM> polar kernel in which ux+<NUM> is added to ux. At the polar decoder <NUM>, the value of ûx for x=<NUM>,<NUM>,<NUM>,<NUM> does not depend on the ux+<NUM> value, but rather the ux+<NUM> value depends on the ux value, and as in other implementations segment #<NUM> decoding can be performed before segment #<NUM> decoding. When the bits of vector v̂' are ready after convolutional decoding by the convolutional decoder <NUM>, data can be extracted by the data extractor <NUM>.

<FIG>, <FIG>, and <FIG> represent three implementations of PAC code segmentation. Segment interleaving as shown by way of example in <FIG> may be preferred for its separation of segments and grouping of segments together, which may improve efficiency of design relative to bit-based segmentation by bit interleaving or a reverse polar transform as shown by way of example in <FIG> and <FIG>, respectively. Bit-based segmentation may be advantageous over segment interleaving, however, in respect of enabling the segment decoders <NUM>, <NUM> or <NUM>, <NUM> to be synchronized per-bit instead of only after decoding of an entire segment. For error performance, segment interleaving or bit interleaving may be preferred over a reverse polar transform, because the polar transform that is applied in interleaving implementations can be based on expansion of a <NUM>-by-<NUM> kernel, and therefore segmenting can be implemented without substantially affecting overall code performance. Reversing a stage during polar encoding and decoding as shown by way of example in <FIG>, however, modifies the reliabilities of the sub-channels, and segmented PAC code performance may vary according to the selection method for A.

The implementations in <FIG>, <FIG>, and <FIG> illustrate examples of segmentation transforms. Some implementations may involve other features of a PAC coding system. Consider convolutional coding as an example.

<FIG> is a block diagram illustrating a convolution structure <NUM> in Arikan PAC encoding. The convolution structure <NUM> includes shift registers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and a modulo-<NUM> adder <NUM>, which operate to transform a rate profiler output v into a polar encoder input u. The convolution in <FIG> has a depth of <NUM> and a polynomial of <NUM><NUM>, and in Arikan PAC coding the shift registers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> are initialized to <NUM> prior to encoding or decoding. The convolution output from the adder <NUM> in <FIG> depends only on the current bit and the previous <NUM> input bits.

<FIG> is a block diagram illustrating a convolution structure <NUM> in accordance with an implementation. The convolution structure <NUM>, like the convolution structure <NUM>, includes shift registers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and a modulo-<NUM> adder <NUM>, but also includes feedback paths <NUM>, <NUM> and an input adder <NUM>. The convolution structure <NUM> operates to transform a rate profiler output v into a polar encoder input u, but by applying feedback as shown by way of example in <FIG>, each output bit from the adder <NUM> is determined in part by additional preceding input bits of the convolution. In the example shown, feedback is applied to the input v from the shift registers <NUM>, <NUM> via the feedback paths <NUM>, <NUM> and the adder <NUM>, and the output from the adder <NUM> is therefore determined based on all of the preceding input bits. The feedback applied to a convolution input can be described via a feedback polynomial, such as <NUM><NUM> in the example shown in <FIG>. Such feedback can also be described as feeding back outputs from shift registers from which outputs are not already used as inputs to the adder <NUM> to determine the convolution output. Feeding back shift register outputs that are already used as inputs to the adder <NUM> would in effect cancel the effect of such shift register outputs on the convolution output from the adder <NUM>. A feedback polynomial or selection of shift registers or positions for feedback may therefore be closely related to a convolution polynomial or the shift registers or positions that are used in a convolution.

Convolution state is initialized to <NUM> prior to encoding or decoding in Arikan PAC coding, as noted above. The first bits of v are almost always frozen bits, and hence the output of the convolution for these bits with initialization to <NUM> is almost always <NUM>. A non-zero convolution output for these bits can be achieved by initializing one or more of the shift registers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> to values other than <NUM>. When non-zero initialization is combined with a feedback strategy shown by way of example in <FIG>, the output stream of a convolution is unique for a particular initial condition, given the same input stream.

According to the claimed invention, non-zero convolution state initialization is implemented in combination with convolution feedback, to avoid an initial state being flushed out of shift registers more quickly. Convolution feedback may be implemented with or without non-zero convolution state initialization.

A convolution feedback and non-zero convolution state initialization strategy as shown by way of example in <FIG> may be useful in enhancing FER performance of PAC coding. <FIG> is a plot of additional performance results from simulations, and includes a reference trace for Arikan PAC coding with convolution of the type shown in <FIG> and a trace for PAC coding with convolution of the type shown in <FIG>, for an N=<NUM>, K=<NUM> PAC code with polar code using Reed-Muller construction. For simulation, the Arikan PAC convolution had a depth of <NUM> and polynomial of <NUM><NUM>, and the convolution with feedback and non-zero convolution state initialization used the same convolution depth and convolution polynomial with a feedback polynomial of <NUM><NUM> and initial values of s<NUM>-<NUM> = <NUM><NUM>. Similar or different results might be observed under different simulation conditions, and/or under similar or different operating conditions.

<FIG> shows that the simulated PAC coding with convolution feedback and non-zero convolution state initialization has superior FER performance compared to the simulated reference Arikan PAC coding.

The outer convolutional code in PAC coding may improve code performance by using the frozen sub-channels with a fixed value of <NUM> or <NUM>. At a decoder, frozen bits are estimated and matched against the expected fixed value. A match between a frozen bit estimate and the expected fixed value validates a current decoding path, while a mismatch indicates a possible erroneous estimate for the previous bit or the current bit. In the case of a mismatch, the decoding path is penalized, and the decoder may be forced to explore alternative paths.

Because of the polarization of the sub-channels in a polar code, the last codeword bits are more reliable than the first codeword bits. However, in Arikan PAC coding as illustrated by way of example in <FIG>, a codeword may end with a long sequence of information bits, without frozen bits, and a PAC code decoder cannot leverage frozen bit estimates to validate decoding of the last information bits.

One possible approach to potentially improve code performance is to insert one or multiple frozen bits at or toward the end of a codeword. The decoder can then benefit from the inserted frozen bit(s) to check the correctness of its decoding path(s).

However, it is understood that a match between frozen bit estimates and outer convolutional code expected values does not guarantee successful decoding. Adding a check code at the encoding stage would enable the decoder to confirm the correctness of the decoding path. A check code can be calculated, for example, using a CRC, a parity check, a Hamming code, or any other mechanisms that can generate redundant data bits to be inserted into a codeword to enable a decoder to reproduce the same calculations over the same information bits.

A PAC code with an embedded check code may improve code performance, because the decoder can confirm the correctness of the decoding path. For example, the decoder may determine whether a checksum computed from estimated values of decoded bits matches a checksum that is also estimated from a received codeword. In the case of a mismatch, the decoder can explore alternative decoding paths until a successful check is observed.

As noted above, the first bits of a polar codeword are less reliable compared to the last bits. A decoder may therefore maintain or explore multiple paths early in the decoding process, until more reliable bits are estimated. If one or more intermediate checksums are inserted at different codeword indices, then a PAC code construction enables the decoder to check decoding paths earlier in the decoding process. In the case of a checksum failure, the decoder can immediately determine that a current decoding path is invalid. For example, in the case of an SCL decoder, a path for which a checksum failure is detected is dropped from the list. The list size of the decoder can then be reduced without sacrificing decoding performance. For the example of an SC-Fano decoder, a path with an intermediate checksum mismatch would not be explored, allowing the decoder to converge faster toward a better decoding path.

<FIG> is a block diagram illustrating examples of PAC coding to support different types of code checking. The examples show three forms of embedded check codes at <NUM>, <NUM>, <NUM>. Each example relates to encoding a message <NUM>, <NUM>, <NUM> using K information bits <NUM>, <NUM>, <NUM> at a time, and involves rate profiling at <NUM>, <NUM>, <NUM>, convolutional encoding of sub-channels <NUM>, <NUM>, <NUM> at <NUM>, <NUM>, <NUM>, and polar encoding of convolutionally encoded bits <NUM>, <NUM>, <NUM> using a polar transform at <NUM>, <NUM>, <NUM> to generate N-bit PAC codewords at <NUM>, <NUM>, <NUM>.

In the example <NUM>, frozen sub-channels <NUM> are inserted at the end of the sub-channels <NUM> to provide a self-check capability for what would otherwise be a long sequence of information bits only. An end-of-codeword check code example is shown at <NUM>, and involves check code generation at <NUM>, to generate a CRC <NUM> that is inserted at the end of the sub-channels <NUM> at <NUM> in the example shown. The example <NUM> similarly involves check code generation and insertion at <NUM>, <NUM>, but intermediate check codes <NUM> are additionally generated and inserted at different codeword indices <NUM>.

At a receiver, the embedded check code(s) are used to recover the messages <NUM>, <NUM>, <NUM>, K information bits at a time from received codewords.

<FIG> illustrates different PAC code construction approaches with check code generation in the examples <NUM>, <NUM> based on the original messages <NUM>, <NUM>. In other implementations, one or more check codes may be generated or added at different encoding stages. For example, a check code can be calculated after rate profiling at <NUM>, or after convolutional encoding at <NUM>. These variations are also applicable to generation and insertion of intermediate check codes.

It should also be appreciated that embedded check code approaches are not necessarily mutually exclusive. Frozen bit insertion can be used in combination with check code generation, for example.

In all of these example, and others consistent with embedded check codes as proposed herein, a decoder can use a check code to potentially improve decoding performance, reduce decoding latency, and/or minimize hardware complexity.

<FIG> is a block diagram of an example apparatus for encoding and transmitting codewords. The apparatus <NUM> includes an encoder module <NUM> coupled to a transmitter module <NUM>. The apparatus <NUM> also includes a code processing module <NUM> coupled to the encoder module <NUM> and a post-encoding processing module <NUM>. The post-encoding processing module <NUM> is also coupled to the encoder module <NUM> and to the transmitter module <NUM>. A memory <NUM>, also shown in <FIG>, is coupled to the encoder module <NUM>, to the code processing module <NUM>, to the post-encoding processing module <NUM>, and to the transmitter module <NUM>. Although not shown, the transmitter module <NUM> could include a modulator, an amplifier, antenna and/or other modules or components of a transmit chain or alternatively could be configured to interface with a separate (RadioFrequency, RF) transmission module. For example, some or all of the modules <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of the apparatus <NUM> may be implemented in hardware or circuitry (e.g. in one or more chipsets, microprocessors, Application-Specific Integrated Circuits (ASICs), Field-Programmable Gate Arrays (FPGAs), dedicated logic circuitry, or combinations thereof) so as to produce codewords as described herein for transmission by a separate (RF) unit.

In some implementations, the memory <NUM> is a non-transitory computer readable medium, that includes instructions for execution by a processor to implement and/or control operation of the code processing module <NUM>, the encoder module <NUM>, the post-encoding processing module <NUM>, and the transmitter module <NUM> in <FIG>, and/or to otherwise control the execution of functionality and/or implementations described herein. In some implementations, the processor may be a component of a general-purpose computer hardware platform. In other implementations, the processor may be a component of a special-purpose hardware platform. For example, the processor may be an embedded processor, and the instructions may be provided as firmware. Some implementations may be implemented by using hardware only. In some implementations, the instructions for execution by a processor may be embodied in the form of a software product. The software product may be stored in a non-volatile or non-transitory storage medium, which could be, for example, a compact disc read-only memory (CD-ROM), universal serial bus (USB) flash disk, or a removable hard disk, at <NUM>.

In some implementations, the encoder module <NUM> is implemented in circuitry, such as a processor, that is configured to encode input bits as disclosed herein. <FIG> is one example of an encoder module. In a processor-based implementation of the encoder module <NUM>, processor-executable instructions to configure a processor to perform encoding operations are stored in a non-transitory processor-readable medium. The non-transitory medium could include, in the memory <NUM> for example, one or more solid-state memory devices and/or memory devices with movable and possibly removable storage media.

The code processing module <NUM> could be implemented in circuitry that is configured to determine coding parameters such as mother code block length, and to determine an ordered sub-channel sequence as disclosed herein and also referred to herein as rate profiling. In some implementations, the code processing module <NUM> is implemented using a processor. The same processor or other circuitry, or separate processors or circuitry, could be used to implement both the encoder module <NUM> and the code processing module <NUM>. As noted above for the encoder module <NUM>, in a processor-based implementation of the code processing module <NUM>, processor-executable instructions to configure a processor to perform code processing operations are stored in a non-transitory processor-readable medium, in the memory <NUM> for example.

Like the encoder module <NUM> and the code processing module <NUM>, the post-encoding processing module <NUM> is implemented in circuitry, such as a processor, that is configured to perform various post-encoding operations. These post-encoding operations could include rate-matching operations such as puncturing, shortening and/or interleaving, for example. In a processor-based implementation of the post-encoding processing module <NUM>, processor-executable instructions to configure a processor to perform post-encoding operations are stored in a non-transitory processor-readable medium, examples of which are described elsewhere herein. In an implementation, the post-encoding processing module <NUM> derives a puncturing or shortening scheme from a puncturing or shortening scheme that is to be applied to a codeword prior to transmission. Information indicative of bit positions and/or sub-channels that are affected by post-encoding operations, or information from which such bit positions or sub-channels may be determined, may be fed back to the code processing module <NUM>, stored to the memory <NUM>, or otherwise made available to the code processing module <NUM> by the post-encoding processing module <NUM>.

In some implementations of the code processing module <NUM>, the coding parameters and/or the ordered sub-channel sequence may be determined based on information from the post-encoding processing module <NUM>. For instance, the ordered sub-channel sequence may be determined based on the rate-matching scheme determined by the post-encoding processing module <NUM>. Conversely, in some other implementations, the post-encoding processing module <NUM> may determine a rate-matching scheme based on the coding parameters and/or the ordered sub-channel sequence determined by the code processing module <NUM>. In yet some other implementations, the determinations made within the code processing module <NUM> and post-encoding processing module <NUM> are jointly performed and optimized.

In an implementation, the encoder module <NUM> is configured to receive input bits at <NUM>, and encode those input bits into a codeword. The transmitter module <NUM> is coupled to the encoder module <NUM>, through the post-encoding processing module <NUM> in the example shown, to transmit the codeword.

The encoder module <NUM> is an example of an encoder to generate a codeword based on a segmentation transform and a PAC code that involves an outer convolutional code and a polar code, and based on separate encoding of respective different segments of convolutionally encoded input bits according to the polar code. Such an encoder may include, for example, a segment interleaver <NUM> and a PAC code encoder <NUM> as shown in <FIG>, a bit interleaver <NUM> and a PAC code encoder <NUM> as shown in <FIG>, or a PAC code encoder <NUM> with a polar encoder <NUM> that has a reverse polar transform stage <NUM> as shown in <FIG>. Segment interleaving, bit interleaving, and a reverse polar transform are all examples of a segmentation transform that may be applied to a PAC code.

A segmentation transform allows an encoder to generate a codeword, according to the polar code, based on separate encoding of respective different segments of convolutionally encoded input bits. Each segment includes multiple convolutionally encoded input bits for which the separate encoding of the segment is independent of the separate encoding of other segments. There may be interdependencies between bits in different segments in other parts of an encoding process, but the separate segment encoding of each segment as shown by way of example in <FIG>, <FIG>, and <FIG> is independent of the separate segment encoding of other segments. For example, although input bits to the polar encoder <NUM> are combined before encoding by the segment #<NUM> encoder <NUM>, the separate encoding by the segment #<NUM> encoder <NUM> is independent of the separate encoding by the segment #<NUM> encoder <NUM>, and similarly the separate encoding by the segment #<NUM> encoder <NUM> is independent of the separate encoding by the segment #<NUM> encoder <NUM>. Encoding by each segment encoder <NUM>, <NUM> does not depend on the encoding that is performed by the other segment encoder.

The encoder module <NUM>, other components of the example apparatus <NUM>, and/or a processor in a processor-based implementation, could implement any of various other features that are disclosed herein. In a processor-based implementation, for example, a memory coupled to the processor may store instructions which, when executed by the processor, cause the processor to perform a method that involves: generating a codeword based on a segmentation transform and a PAC code, and based on separate encoding of respective different segments of convolutionally encoded input bits as disclosed herein.

Other features may also be provided. For example, any one or more of the following could be provided, alone or in any of various combinations, in implementations:.

The apparatus <NUM> could implement any of various other features that are disclosed herein. For example, the encoder module <NUM>, the transmitter module <NUM>, the code processing module <NUM>, the post-encoding processing module <NUM>, and/or a processor in a processor-based implementation, could be configured to implement any one or more of the features listed or otherwise described herein.

In some alternative implementations, the functionality of the encoder module <NUM>, the transmitter module <NUM>, the code processing module <NUM>, and/or the post-encoding processing module <NUM> described herein may be fully or partially implemented in hardware or alternatively in software, for example in modules stored in a memory such as <NUM> and executed by one or more processors of the apparatus <NUM>.

An apparatus could therefore include a processor, and a memory such as <NUM>, coupled to the processor, storing instructions which, when executed by the processor, cause the processor to perform the functionality and/or implementations described in relation to the encoder module <NUM>, the transmitter module <NUM>, the code processing module <NUM>, and/or the post-encoding module <NUM> described herein.

<FIG> is a block diagram of an example apparatus for receiving and decoding codewords. The apparatus <NUM> includes a receiver module <NUM> which is configured to receive signals transmitted wirelessly and which is coupled to a decoder module <NUM>. The apparatus <NUM> also includes a code processing module <NUM> coupled to the decoder module <NUM> and a pre-decoding processing module <NUM>. The pre-decoding processing module <NUM> is also coupled to the decoder module <NUM> and to the receiver module <NUM>. A memory <NUM> also shown in <FIG>, is coupled to the decoder module <NUM>, to the code processing module <NUM>, to the receiver module <NUM>, and to the pre-decoding processing module <NUM>.

Although not shown, the receiver module <NUM> could include an antenna, demodulator, amplifier, and/or other modules or components of a receive chain or alternatively could be configured to interface with a separate (RF) receiving module. For example, some or all of the modules <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of the apparatus <NUM> may be implemented in hardware or circuitry (e.g. in one or more chipsets, microprocessors, ASICs, FPGAs, dedicated logic circuitry, or combinations thereof) so as to receive a word based on a codeword. Decoded bits are output at <NUM> for further receiver processing.

In some implementations, the memory <NUM> is a non-transitory computer readable medium that includes instructions for execution by a processor to implement and/or control operation of the receiver module <NUM>, decoder module <NUM>, the code processing module <NUM>, and the pre-decoding processing module <NUM> in <FIG>, and/or to otherwise control the execution of functionality and/or implementations described herein. In some implementations, the processor may be a component of a general-purpose computer hardware platform. In other implementations, the processor may be a component of a special-purpose hardware platform. For example, the processor may be an embedded processor, and the instructions may be provided as firmware. Some implementations may be implemented by using hardware only. In some implementations, the instructions for execution by a processor may be embodied in the form of a software product. The software product may be stored in a non-volatile or non-transitory storage medium, which could be, for example, a CD-ROM, USB flash disk, or a removable hard disk, at <NUM>.

The decoder module <NUM> is implemented in circuitry, such as a processor, that is configured to decode received codewords as disclosed herein. In a processor-based implementation of the decoder module <NUM>, processor-executable instructions to configure a processor to perform decoding operations are stored in a non-transitory processor-readable medium. The non-transitory medium could include, in the memory <NUM> for example, one or more solid-state memory devices and/or memory devices with movable and possibly removable storage media.

The code processing module <NUM> could be implemented in circuitry that is configured to determine (and store to the memory <NUM>) ordered sub-channel sequences. In a processor-based implementation of the code-processing module <NUM>, processor-executable instructions to configure a processor to perform code-processing operations are stored in a non-transitory processor-readable medium, examples of which are described herein. Information representing ordered sub-channel sequences, and/or the selected sub-channels could be provided to the decoder module <NUM> by the code processing module <NUM> for use in decoding received words, and/or stored in the memory <NUM> by the code processing module <NUM> for subsequent use by the decoder module <NUM>.

Like the decoder module <NUM> and the code processing module <NUM>, the pre-decoding processing module <NUM> is implemented in circuitry, such as a processor, that is configured to perform pre-decoding operations. These operations could include receiver/decoder-side rate matching operations also known as de-rate-matching operations, such as de-puncturing and/or de-shortening to reverse puncturing/shortening that was applied at an encoder/transmitter side, for example. In a processor-based implementation of the pre-decoding processing module <NUM>, processor-executable instructions to configure a processor to perform pre-decoding processing operations are stored in a non-transitory processor-readable medium, examples of which are described above. In an implementation, the pre-decoding processing module <NUM> derives a puncturing or shortening scheme from a puncturing or shortening scheme that is to be applied to a received codeword. Information indicative of bit positions and/or sub-channels that are affected by pre-decoding processing, or information from which such bit positions or sub-channels may be determined, may be fed back to the code processing module <NUM>, stored to the memory <NUM>, or otherwise made available to the code processing module <NUM> by the pre-decoding processing module <NUM>.

In some implementations of the code processing module <NUM>, the ordered sub-channel sequence may be determined based on information from the pre-decoding processing module <NUM>. For instance, the ordered sub-channel sequence may be determined based on the rate-matching scheme determined by the pre-decoding processing module <NUM>. Conversely, in some other implementations, the pre-decoding processing module <NUM> may determine a rate-matching scheme based on the coding parameters and/or the ordered sub-channel sequence determined by the code processing module <NUM>. In yet some other implementations, the determinations made within the code processing module <NUM> and pre-decoding processing module <NUM> are jointly performed and optimized.

In some alternative implementations, the functionality of the receiver module <NUM>, the decoder module <NUM>, the code processing module <NUM>, and/or the pre-decoding processing module <NUM> described herein may be fully or partially implemented in software or modules, for example in receiving and decoding modules stored in a memory <NUM> and executed by one or more processors of the apparatus <NUM>.

An apparatus could therefore include a processor, and a memory such as <NUM>, coupled to the processor, storing instructions which, when executed by the processor, cause the processor to perform the functionality and/or implementations disclosed herein, or receiving / decoding operations corresponding to transmitting / encoding operations disclosed herein.

The apparatus <NUM> could implement any of various other features that are disclosed herein. For example, the decoder module <NUM>, the receiver module <NUM>, the code processing module <NUM>, and/or the pre-decoding processing module <NUM> could be configured to implement any one or more of receiving / decoding features corresponding to encoding / transmitting features disclosed herein.

As an example, an apparatus may include a receiver a receiver to receive a codeword based on a codeword that was generated based on a segmentation transform and a PAC code. The PAC code is based on an outer convolutional code and a polar code, and the codeword was generated by separately encoding respective different segments of convolutionally encoded input bits according to the polar code, as described herein. Each segment includes multiple bits for which the separate encoding of the segment is independent of the separate encoding of other segments. A decoder is coupled to the receiver, to separately decode segments of the received codeword to recover segments of convolutionally encoded input bits corresponding to the separately encoded segments of the convolutionally encoded input bits, and to decode the convolutionally encoded input bits recovered from the received codeword.

A decoder may implement or provide other features, such as decoding features corresponding to encoding features disclosed herein.

Communication equipment could include the apparatus <NUM>, the apparatus <NUM>, or both a transmitter and a receiver and both an encoder and a decoder and other components shown in <FIG>. Such communication equipment could be user equipment or communication network equipment.

<FIG> illustrates an example communication system <NUM> in which implementations of the present disclosure could be implemented. In general, the communication system <NUM> enables multiple wireless or wired elements to communicate data and other content. The purpose of the communication system <NUM> may be to provide content (voice, data, video, text) via broadcast, narrowcast, user device to user device, etc. The communication system <NUM> may operate by sharing resources such as bandwidth.

In this example, the communication system <NUM> includes electronic devices (ED) 1910a-1910c, radio access networks (RANs) 1920a-1920b, a core network <NUM>, a public switched telephone network (PSTN) <NUM>, the internet <NUM>, and other networks <NUM>. Although certain numbers of these components or elements are shown in <FIG>, any reasonable number of these components or elements may be included.

The EDs 1910a-1910c and base stations 1970a-1970b are examples of communication equipment that can be configured to implement some or all of the functionality and/or implementations described herein. For example, any one of the EDs 1910a-1910c and base stations 1970a-1970b could be configured to implement the encoding or decoding functionality (or both) described above. In another example, any one of the EDs 1910a-1910c and base stations 1970a-1970b could include an apparatus <NUM> (<FIG>), an apparatus <NUM> (<FIG>), or both.

The EDs 1910a-1910c are configured to operate, communicate, or both, in the communication system <NUM>. For example, the EDs 1910a-1910c are configured to transmit, receive, or both via wireless or wired communication channels. Each ED 1910a-1910c represents any suitable end user device for wireless operation and may include such devices (or may be referred to) as a user equipment/device (UE), wireless transmit/receive unit (WTRU), mobile station, fixed or mobile subscriber unit, cellular telephone, station (STA), machine type communication (MTC) device , personal digital assistant (PDA), smartphone, laptop, computer, tablet, wireless sensor, or consumer electronics device.

In <FIG>, the RANs 1920a-1920b include base stations 1970a-1970b, respectively. Each base station 1970a-1970b is configured to wirelessly interface with one or more of the EDs 1910a-1910c to enable access to any other base station 1970a-1970b, the core network <NUM>, the PSTN <NUM>, the Internet <NUM>, and/or the other networks <NUM>. For example, the base stations 1970a-1970b may include (or be) one or more of several well-known devices, such as a base transceiver station (BTS), a Node-B (NodeB), an evolved NodeB (eNodeB), a Home eNodeB, a gNodeB, a transmission point (TP), a site controller, an access point (AP), or a wireless router. Any ED 1910a-1910c may be alternatively or additionally configured to interface, access, or communicate with any other base station 1970a-1970b, the internet <NUM>, the core network <NUM>, the PSTN <NUM>, the other networks <NUM>, or any combination of the preceding. The communication system <NUM> may include RANs, such as RAN 1920b, wherein the corresponding base station 1970b accesses the core network <NUM> via the internet <NUM>, as shown.

The EDs 1910a-1910c and base stations 1970a-1970b are examples of communication equipment that can be configured to implement some or all of the functionality and/or implementations described herein. In the implementation shown in <FIG>, the base station 1970a forms part of the RAN 1920a, which may include other base stations, base station controller(s) (BSC), radio network controller(s) (RNC), relay nodes, elements, and/or devices. Any base station 1970a, 1970b may be a single element, as shown, or multiple elements, distributed in the corresponding RAN, or otherwise. Also, the base station 1970b forms part of the RAN 1920b, which may include other base stations, elements, and/or devices. Each base station 1970a-1970b transmits and/or receives wireless signals within a particular geographic region or area, sometimes referred to as a "cell" or "coverage area". A cell may be further divided into cell sectors, and a base station 1970a-1970b may, for example, employ multiple transceivers to provide service to multiple sectors. In some implementations, there may be established pico or femto cells where the radio access technology supports such. In some implementations, multiple transceivers could be used for each cell, for example using multiple-input multiple-output (MIMO) technology. The number of RAN 1920a-1920b shown is exemplary only. Any number of RAN may be contemplated when devising the communication system <NUM>.

The base stations 1970a-1970b communicate with one or more of the EDs 1910a-1910c over one or more air interfaces <NUM> using wireless communication links e.g. RF, microwave, infrared (IR), etc. The air interfaces <NUM> may utilize any suitable radio access technology. For example, the communication system <NUM> may implement one or more channel access methods, such as code division multiple access (CDMA), time division multiple access (TDMA), frequency division multiple access (FDMA), orthogonal FDMA (OFDMA), or single-carrier FDMA (SC-FDMA) in the air interfaces <NUM>.

A base station 1970a-1970b may implement Universal Mobile Telecommunication System (UMTS) Terrestrial Radio Access (UTRA) to establish an air interface <NUM> using wideband CDMA (WCDMA). In doing so, the base station 1970a-1970b may implement protocols such as HSPA, HSPA+ optionally including HSDPA, HSUPA or both. Alternatively, a base station 1970a-1970b may establish an air interface <NUM> with Evolved UTMS Terrestrial Radio Access (E-UTRA) using LTE, LTE-A, and/or LTE-B. It is contemplated that the communication system <NUM> may use multiple channel access functionality, including such schemes as described above. Other radio technologies for implementing air interfaces include IEEE <NUM>, <NUM>, <NUM>, CDMA2000, CDMA2000 1X, CDMA2000 EV-DO, IS-<NUM>, IS-<NUM>, IS-<NUM>, GSM, EDGE, and GERAN. Of course, other multiple access schemes and wireless protocols may be utilized.

The RANs 1920a-1920b are in communication with the core network <NUM> to provide the EDs 1910a-1910c with various services such as voice, data, and other services. The RANs 1920a-1920b and/or the core network <NUM> may be in direct or indirect communication with one or more other RANs (not shown), which may or may not be directly served by core network <NUM>, and may or may not employ the same radio access technology as RAN 1920a, RAN 1920b or both. The core network <NUM> may also serve as a gateway access between (i) the RANs 1920a-1920b or EDs 1910a-1910c or both, and (ii) other networks (such as the PSTN <NUM>, the internet <NUM>, and the other networks <NUM>). In addition, some or all of the EDs 1910a-1910c may include functionality for communicating with different wireless networks over different wireless links using different wireless technologies and/or protocols. Instead of wireless communication (or in addition thereto), the EDs 1910a-1910c may communicate via wired communication channels to a service provider or switch (not shown), and to the internet <NUM>. PSTN <NUM> may include circuit switched telephone networks for providing plain old telephone service (POTS). Internet <NUM> may include a network of computers and subnets (intranets) or both, and incorporate protocols, such as IP, TCP, UDP. EDs 1910a-1910c may be multimode devices capable of operation according to multiple radio access technologies, and incorporate multiple transceivers necessary to support such radio access technologies.

These components could be used in the communication system <NUM> or in any other suitable system.

For example, the processing unit <NUM> could perform signal coding, data processing, power control, input/output processing, or any other functionality enabling the ED <NUM> to operate in the communication system <NUM>. The processing unit <NUM> may also be configured to implement some or all of the functionality and/or implementations described in more detail above.

The ED <NUM> also includes at least one transceiver <NUM>. The transceiver <NUM> is configured to modulate data or other content for transmission by at least one antenna or Network Interface Controller (NIC) <NUM>. The transceiver <NUM> is also configured to demodulate data or other content received by the at least one antenna <NUM>. Each transceiver <NUM> includes any suitable structure for generating signals for wireless or wired transmission and/or processing signals received wirelessly or by wire. Each antenna <NUM> includes any suitable structure for transmitting and/or receiving wireless or wired signals. One or multiple transceivers <NUM> could be used in the ED <NUM>, and one or multiple antennas <NUM> could be used in the ED <NUM>. Although shown as a single functional unit, a transceiver <NUM> could also be implemented using at least one transmitter and at least one separate receiver.

The ED <NUM> further includes one or more input/output devices <NUM> or interfaces (such as a wired interface to the internet <NUM>). The input/output devices <NUM> permit interaction with a user or other devices in the network. Each input/output device <NUM> includes any suitable structure for providing information to or receiving information from a user, such as a speaker, microphone, keypad, keyboard, display, or touch screen, including network interface communications.

In addition, the ED <NUM> includes at least one memory <NUM>. The memory <NUM> stores instructions and data used, generated, or collected by the ED <NUM>. For example, the memory <NUM> could store software instructions or modules configured to implement some or all of the functionality and/or implementations described herein and that are executed by the processing unit(s) <NUM>. Each memory <NUM> includes any suitable volatile and/or non-volatile storage and retrieval device(s). Any suitable type of memory may be used, such as random access memory (RAM), read only memory (ROM), hard disk, optical disc, subscriber identity module (SIM) card, memory stick, secure digital (SD) memory card, and the like.

As shown in <FIG>, the base station <NUM> includes at least one processing unit <NUM>, at least one transmitter <NUM>, at least one receiver <NUM>, one or more antennas <NUM>, at least one memory <NUM>, and one or more input/output devices or interfaces <NUM>. A transceiver, not shown, may be used instead of the transmitter <NUM> and receiver <NUM>. A scheduler <NUM> may be coupled to the processing unit <NUM>. The scheduler <NUM> may be included within or operated separately from the base station <NUM>. The processing unit <NUM> can also be configured to implement some or all of the functionality and/or implementations described in more detail above.

Each transmitter <NUM> includes any suitable structure for generating signals for wireless or wired transmission to one or more EDs or other devices. Each receiver <NUM> includes any suitable structure for processing signals received wirelessly or by wire from one or more EDs or other devices. Although shown as separate components, at least one transmitter <NUM> and at least one receiver <NUM> could be combined into a transceiver. Each antenna <NUM> includes any suitable structure for transmitting and/or receiving wireless or wired signals. Although a common antenna <NUM> is shown here as being coupled to both the transmitter <NUM> and the receiver <NUM>, one or more antennas <NUM> could be coupled to the transmitter(s) <NUM>, and one or more separate antennas <NUM> could be coupled to the receiver(s) <NUM>. Each memory <NUM> includes any suitable volatile and/or non-volatile storage and retrieval device(s) such as those described above in connection to the ED <NUM>. The memory <NUM> stores instructions and data used, generated, or collected by the base station <NUM>. For example, the memory <NUM> could store software instructions or modules configured to implement some or all of the functionality and/or implementations described above and that are executed by the processing unit(s) <NUM>.

Each input/output device <NUM> permits interaction with a user or other devices in the network. Each input/output device <NUM> includes any suitable structure for providing information to or receiving/providing information from a user, including network interface communications.

<FIG> are illustrative of processor-based implementations, in which an apparatus includes a processor in the form of a processing unit <NUM> or <NUM>, and a memory <NUM> or <NUM> storing instructions which, when executed by the processor, cause the processor to perform a method as disclosed herein. The transceiver <NUM> or the transmitter <NUM> may enable a codeword to be transmitted, and the transceiver <NUM> or the receiver <NUM> may enable a codeword to be received, and accordingly an apparatus consistent with <FIG> may be operable to generate and transmit a codeword, receive and decode a codeword, or both generate and transmit a codeword and receive and decode a codeword.

<FIG> is a flow diagram of an example coding method according to an implementation.

The example method <NUM> includes operations that may be performed in some implementations, and involves a segmentation transform and a PAC code that is based on an outer convolutional code and a polar code. The rate profiling at <NUM> is part of polar coding and involves sub-channel selection as disclosed by way of example elsewhere herein. A PAC code also involves an outer convolutional code, and convolutional encoding is shown at <NUM>.

The example method <NUM> also involves generating a codeword at <NUM>, based on the segmentation transform and the PAC code, and based on separate encoding of respective different segments of convolutionally encoded input bits according to the polar code. Each segment of the respective segments includes multiple bits of the convolutionally encoded input bits for which the separate encoding of the segment is independent of the separate encoding of other segments. A generated codeword may be stored and/or otherwise processed, and in the example method <NUM> the codeword is transmitted at <NUM>.

Receive-side operations are also illustrated in <FIG>. These operations include, in the example shown, receiving a codeword at <NUM> and decoding the codeword at <NUM>. The codeword that is received at <NUM> is based on a codeword that was generated based on a segmentation transform and a PAC code that includes an outer convolutional code and a polar code, and based on separately encoding respective different segments of convolutionally encoded input bits according to the polar code, with each segment of the respective segments including multiple bits of the convolutionally encoded input bits for which the separate encoding of the segment is independent of the separate encoding of other segments. The decoding at <NUM> involves separately decoding segments of the received codeword to recover segments of convolutionally encoded input bits corresponding to the separately encoded segments of the convolutionally encoded input bits, and decoding the convolutionally encoded input bits recovered from the received codeword.

For example, any one or more of the following could be provided, alone or in any of various combinations, in implementations:.

Although <FIG> shows example operations that would be performed at an encoder (or transmitter), other implementations could be implemented at a decoder (or receiver). A word that is based on a codeword of a code could be received at a receiver and decoded, based on sub-channels that are selected by the decoder, a sub-channel selector coupled to the decoder, or a processor in a processor-based implementation, according to a method as shown in <FIG>, and/or as otherwise disclosed herein.

In another implementation, a non-transitory processor-readable medium stores instructions which, when executed by one or more processors, cause the one or more processors to perform a method as disclosed herein.

The previous description of some implementations is provided to enable any person skilled in the art to make or use an apparatus, method, or processor readable medium according to the present disclosure.

For example, although implementations are described primarily with reference to bits, other implementations may involve non-binary multi-bit symbols. If one sub-channel can transmit more than one bit, then several bits can be combined into a symbol in a defined alphabet, and a non-binary symbol is encoded for each sub-channel. Accordingly, polarization kernels are not limited to binary kernels. Symbol-level (Galois field) or non-binary kernels are also contemplated. A non-binary kernel could be preferred for its higher degree of polarization than a binary kernel. However, decoding computation complexity is higher for a non-binary kernel, because a decoder would handle symbols rather than bits.

Non-binary kernels possess characteristics of binary kernels. Furthermore, non-binary kernels could be combined or cascaded with binary kernels to form one polar code. Although the Arikan <NUM>-by-<NUM> binary kernel is used herein as an example, disclosed features may be extended to other types of polarization kernels.

The present disclosure refers primarily to a <NUM>-by-<NUM> kernel as example to demonstrate and explain illustrative implementations. However, it is understood that the techniques for selecting sub-channels as disclosed herein could be applied to other types of polarization kernels as well, such as non-two prime number dimension kernels, non-primary dimension kernels, and/or higher dimension kernels formed by a combination of different (primary or non-primary) dimensions of kernels.

As noted above, polar codes have been selected for uplink and downlink eMBB control channel coding for the new <NUM> air interface, also known as <NUM> new radio (NR). The techniques disclosed herein could be used not only for control data over a control channel but also or instead other types of data (e.g. user data) over any type of channel (e.g. a data channel).

Illustrative examples described herein refer to sub-channel sequences that are in increasing order of a reliability metric. In other implementations, ordered sequences that are in decreasing reliability order could be used. Similarly, sequences could be generated in increasing order of reliability rather than starting with more reliable channels and building a sequence by adding sub-channels with progressively decreasing reliabilities.

Claim 1:
A method comprising:
generating (<NUM>) a codeword based on a segmentation transform and a Polarization-Adjusted Convolutional, PAC, code that comprises an outer convolutional code and a polar code, and based on separate encoding of respective different segments of convolutionally encoded input bits according to the polar code, each segment of the respective segments comprising a plurality of the convolutionally encoded input bits for which the separate encoding of the segment is independent of the separate encoding of other segments,
wherein the segmentation transform comprises interleaving the input bits before convolutional encoding according to the outer convolutional code or combining convolutionally encoded input bits for the separate encoding of a segment;
transmitting (<NUM>) the codeword;
wherein the outer convolutional code comprises a non-zero initial state and state feedback.