Patent Description:
Mobile communications typically employ error correcting codes, such as polar codes.

While polar codes can provide good error correcting performance, they can be computationally complex.

In <NPL>et al. describe how the complexity of polar codes can be reduced by relaxing the polarization of both sufficiently good and sufficiently bad bit-channels.

In <NPL>et al. propose a class of polar codes where polarization units are irregularly pruned to reduce complexity and latency.

In <NPL>et al. propose a class of irregular polar codes using flexible polarization pruning.

Furthermore, like reference numerals in the figures indicate like elements, and wherein:.

Polar codes may have significant potential in achieving high throughput under practical constraints of energy efficiency, power density, and flexibility. An approach to enable higher throughputs is to reduce the complexity of encoding and decoding operations while preserving the error-correction performance. Such a reduction in complexity may allow encoding and decoding operations to operate within practical constraints including, for example, energy efficiency, power density, and/or flexibility.

Implementation(s) associated with reducing the encoding and decoding complexity and/or latency of polar codes, which may preserve or improve error-correction performance, are disclosed herein. Disclosed implementation(s) may facilitate higher throughputs within the practicality constraints of interest.

Polar codes may be used in wireless communication systems. Polar codes may be used as capacity achieving codes. Polar codes may show comparable performance to other codes (e.g., low-density parity-check (LDPC) code or turbo code) and may have a low error floor when aided by an embedded CRC, e.g. particularly for small to medium block lengths. Polar codes with successive cancellation decoding may require relatively low encoding and decoding complexities. The decoding complexity may increase in proportion to a list size, e.g. when CRC-aided list decoding is adopted. Decoding complexity may increase in proportion to the block-length of the codeword. The complexity increase may become an issue, e.g. for medium to large block-lengths, and may limit the adaptation of polar codes for a high throughput regime, e.g. including <NUM> NR eMBB data rates (~<NUM> Gbps) and above.

Polar codes may be used as a channel coding scheme for 3GPP NR, e.g., to be used in control channel FEC operations, and may have better performance for small block lengths.

Polar code encoding is as in Equation <NUM>: <MAT>.

A codeword vector of polar code, denoted as <MAT>, is generated by the product of an input vector, denoted as <MAT>, and a generator matrix, denoted as GN. <MAT> and <MAT> are binary vectors with length N = <NUM>n, where N denotes the codeword block length. The generator matrix GN is defined by the Kronecker power of <MAT>, <MAT> where ()⊗n stands for the n-th Kronecker power of (). In certain situations, GN may be equal to BNF⊗n. BN denotes a bit reversing matrix that changes the order of elements in <MAT> [u<NUM>, u<NUM>,. It is assumed that GN = F⊗n , e.g., unless stated otherwise.

Some input bits for polar encoding may have a fixed value (e.g., zero) and be referred to as "frozen bits. " The input indices for frozen bits are represented by the set Ac.

The remaining input bits for polar encoding may convey variable information bits and may referred to as "unfrozen bits. " The input indices for unfrozen bits are represented by the set A.

The number of information bits (e.g., unfrozen bits) is defined as K and the number of frozen bits is N - K.

The code rate R of polar code is defined as <MAT>.

Determination of input bit indices for frozen bits and unfrozen bits is referred to as "code construction" (e.g., for polar encoding).

There are several code construction implementations for polar encoding. In general, the implementations initially calculate the reliability of input bit indices (e.g., each input bit index), and therefore have an order of bit index reliabilities before starting the encoding operation. From the obtained reliability order, the least reliable input bits are assigned as frozen bits and the remaining bits as unfrozen/information bits. The proportion of frozen and unfrozen bits is determined according to a desired code rate. With the frozen and unfrozen bit locations available, the encoding operation continues as in Equation <NUM> shown in <FIG> shows an example polar encoder where a codeword block length is equal to <NUM>.

Decoding of polar code is categorized into one or more (e.g., two) implementations, for example Successive Cancellation (SC) based decoding and Belief Propagation (BP) based decoding.

SC polar decoding uses sequential decoding to calculate a log-likelihood ratio (LLR) value of input bits in a serial manner. SC polar decoding is based on the assumption that the previously decoded bits are correct. The previously decoded bits are used for decoding the current bit. Successive Cancellation List (SCL) decoding adopts several lists of candidate paths to improve the performance of SC decoding. A list (e.g., the best list) is selected according to the outcome of the LLR calculation. CRC Aided Successive Cancellation List (CA-SCL) decoding adopts embedded CRC as a tool to select the list. By CA-SCL decoding, polar code may achieve error performance comparable or superior to other codes, e.g. LDPC code or turbo code.

In a representation denoted as a Tanner graph representation of polar code, polar code is decoded by message passing according to the sum product implementation or min sum implementation.

One approach that may be used in reducing the complexity of encoding and decoding operations of polar codes is relaxation. Relaxation of polar code means that parts of a polarization implementation in polar code are omitted. The polarization implementation corresponds to an XOR operation in polar encoding. Relaxation is done by omitting the XOR operation, e.g., in some parts of polar encoding. <FIG> shows an example relaxation operation.

A corresponding decoding XOR operation is be performed (e.g., in the decoding of relaxed polar code). This may provide decoding complexity reduction. It may be that one or more decoding implementations developed for polar decoding, e.g. including SC, SCL, CASCL and BP decoding, may be used equivalently with reduced decoding complexity.

The relaxation scheme (e.g., including irregular polar code as described herein) may provide reduction of complexity and latency in encoding and decoding in addition to performance improvement with proper selection of relaxed nodes.

A graph representation of polar code is described herein.

Polar codes may be well structured, e.g., in terms of encoding and decoding. The design of a polar code depends on the mapping of K information bits to N(= <NUM>n) input bits of a polar encoder <MAT>. The K information bits may be put on the K best bit channels. The remaining N - K input bits (e.g., those which are not mapped from the information bits) are called frozen bits, and are generally set as <NUM>. The set of the positions for frozen bits is called frozen set Ac.

Polar code encoding and decoding may be described by a graph representation, e.g. as shown in <FIG> shows a polar code graph where a codeword block length is equal to <NUM>. As shown in <FIG>, a polar code graph may consist of (n + <NUM>)N nodes. Nodes (e.g., each node) may be indexed by (i,j), where i = <NUM>, <NUM>,. , N, j = <NUM>,<NUM>,. i indicates a row index and j indicates a column index. The rows are numbered from top to bottom, and the columns from left to right. Numbering of the columns may start with zero (e.g., rather than one). The left most nodes (i, <NUM>) indicate input bits of polar code ui, where i = <NUM>, <NUM>,. The right most node (i, n) indicate the output coded bits ci, where i = <NUM>, <NUM>,. vi,j is defined as the value of node (i, j), with vi,<NUM> = ui and vi,n = ci. The column index j is also defined as the jth level.

In <FIG>, the relation of the connection between level j and level j + <NUM> is as shown and node (i,j) is connected with (i, j + <NUM>). For example, v<NUM>,<NUM> and v<NUM>,<NUM> may have a connection (e.g., a link) with v<NUM>,<NUM> and v<NUM>,<NUM>, respectively. v<NUM>,<NUM> and v<NUM>,<NUM> may have a connection (e.g., a link) with v<NUM>,<NUM> and v<NUM>,<NUM>. The connection (e.g., link) may be extended from level <NUM> to level n. A bit reversing interleaver may be applied and the connected nodes between subsequent two levels may have a different indices.

Two nodes involved in a polarization operation are defined as "paired. " In <FIG>, a and b may be paired, e.g. before relaxation. As shown in <FIG>, node (<NUM>,<NUM>) is paired with node (<NUM>,<NUM>) and node (<NUM>,<NUM>) is paired with node (<NUM>,<NUM>).

In polar encoding, the input bits are transferred to n level and experience polarization at some levels (e.g., each level). Polar decoding may be understood as the polarization process from the channel input values, e.g., by corresponding Log-Likelihood Ratio (LLR) or log-likelihood (LL) calculation.

Polar code may be represented by binary expansion (e.g., as shown in <FIG>). The graph or tree representation of polar code in <FIG> may be used for an SC-based decoding structure. It may be (e.g., continuously) divided into two nodes corresponding to two operations of polarization (e.g., initially starting with a single mother node). One branch corresponds to polarization into a bad channel and the other to polarization into a good channel. For example, nodes (e.g., all nodes) corresponding to a at some levels (e.g., each level) in <FIG> may be polarized to bad channels and nodes (e.g., all nodes) corresponding to b at some levels (e.g., each level) in <FIG> may be polarized to good channels.

For example, the first divergence from the initial mother node (e.g., as shown in <FIG>) has two nodes as child nodes. The first divergence that results in bad channel polarization (e.g., as shown in <FIG>) corresponds to an XOR operation between values of nodes (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) and values of nodes (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) (e.g., as shown in <FIG>). After this operation, output coded bits c<NUM>, c<NUM>, c<NUM>, c<NUM> are generated. The first divergence corresponding to good channel polarization (e.g., as shown in <FIG>) directly passes operation of nodes (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) to the final encoder level. After this operation, output coded bits c<NUM>, c<NUM>, c<NUM>, c<NUM> are generated (e.g., having the same values of (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>)). This divergence is performed continuously until the nodes corresponding to input bits are reached.

The number of levels in <FIG> may be the same as in <FIG>. The initial mother node corresponds to channel input codewords. A dotted connection in <FIG> corresponds to a good channel connection and a solid connection to a bad channel connection.

The leaf nodes in the left most side of <FIG> correspond to input bits (e.g., frozen or unfrozen bits). A node may be denoted as a Rate-<NUM> node (e.g., if the child nodes of the node are all frozen bits). A node may be denoted as a Rate-<NUM> node (e.g., if the child nodes of the node are all unfrozen bits). A node may be denoted as a Rate-R node (e.g., if the child nodes of the node are a combination of frozen and unfrozen bits).

In polar decoding, the parameters αl, αr, αv, βr, βl, βv may be exchanged for successive cancellation decoding.

Relaxation schemes for polar encodings may be based on the calculation of error probability in nodes (e.g., each node) in a polar encoding operation (e.g., as shown in <FIG>), e.g. corresponding to nN nodes in total and their error probability calculations. This approach may require significant computational load and memory, and may limit the code-rate flexibility of polar codes as code-rates (e.g., each code-rate) may require re-computation of these reliability values.

Error probability is used for some forms of relaxation. The error probability of some levels (e.g., each level) and corresponding nodes in some levels (e.g., each level) (i, n), where i = <NUM>,. , N (e.g. as shown in <FIG>, <FIG>, and <FIG>), is calculated. The nodes that are selected for an initial relaxation operation are determined. For example, a node is selected if its error probability is less than or larger than a predetermined threshold value. For example, in good channel relaxation, a node is selected for an initial relaxation operation when the error probability of the node is less than a first predetermined threshold value (e.g., denoted Eg). In bad channel relaxation, a node is selected when the error probability of the node is larger than a second predetermined threshold value (e.g., denoted Eb). Some (e.g., all) connected nodes in the subsequent levels may be included in the overall relaxation operation, e.g. starting from the relaxation nodes that are selected for initial relaxation.

A generalized, not claimed concept of relaxation includes "inactivation" instead of "relaxation," which may result in irregular polar code. The union bound of error rate based on the mutual information for each node is calculated for candidate groups (e.g., each candidate group) of inactivated nodes. The candidate group that shows the lowest error rate is selected for inactivation, e.g. where the frozen and unfrozen bit indices based on the new code construction are also derived.

A challenge in forward error correction (FEC) technologies is to develop channel codes that can achieve high throughputs (e.g., ><NUM> Gbps) within the practicality constraints of several use-cases (e.g., battery limited wireless terminals and/or sufficient error-correcting performance). One or more conventional implementations for polar encoding have several drawbacks, e.g., limiting their application in practical use cases. Relaxation operations associated with polar codes are disclosed herein. In examples disclosed herein, complexity and/or latency reduction are achieved by relaxation, e.g. without sacrificing performance.

For example, conventional relaxation schemes may incur prohibitively high computation complexity while determining the set of encoding nodes (and similar decoding operations) that may participate in a relaxation operation. Conventional relaxation implementations may be based on code construction and may require processing-heavy calculations, e.g. theoretical error probability or mutual information values for nodes (e.g., every node) in the encoding process. The implementation of these calculations, and hence the execution of conventional relaxation implementations, may be prohibitive due to their high complexities.

Certain relaxation schemes depend on the storage of relaxed node information, e.g. the IDs of encoding nodes that participate in the relaxation operation for possible code block lengths (e.g., every possible code block length) and code rate. This may require significant additional memory requirements in the unit.

After the calculations and selection of the relaxed nodes in an encoding operation, the information indicating relaxed nodes (e.g., node ID and/or relaxation attribute value) is saved in memory, e.g. in order to apply relaxation during the encoding or decoding process. The used memory may not be negligible and may be substantial, as the memory usage increases, e.g. in proportion to the code block length and also considering various possible code block lengths and code rates.

Conventional relaxation schemes may provide limited code block-length and code-rate flexibility. In certain applications, flexibility in code block length or code rate is be highly desired. Therefore, encoding and decoding schemes which support high flexibility may be preferred, e.g. particularly depending on the use cases of interest and adaptation to variations of channel environment. In conventional schemes, code lengths (e.g., each code length) and code rates (e.g., each code rate) may require re-calculation of node probability levels and re-determination of relaxed nodes. This property of conventional relaxation implementations may lead to a substantial flexibility limitation of the codes, e.g. due to prohibitive complexity and memory usage associated with these implementations.

Polar encoder and decoder implementations associated with relaxation are described herein. One or more polar encoder and decoder implementations is associated with complexity reduction.

In relaxation examples, the most reliable or most unreliable input bit indices, e.g. bit channels in a polar code encoding operation, are used in the selection of the nodes that will participate in the relaxation. The number of bit indices that participate in a relaxation operation is determined, for example based on performance-complexity trade-offs (e.g., the degree of desired complexity reduction vs achieved coding gain). The relaxation attributes of an initial level, relaxation group(s), and a final relaxation encoding level(s)/stage(s) for relaxation group(s) (e.g., each relaxation group) are identified, e.g. by using one or more of the following: the set of most and least reliable bit channels or the number of bit indices participating in relaxation operation. Relaxation attributes in encoding levels beyond the initial stage are determined from the relaxation attributes of preceding levels. XOR operations in the encoding process and message passing operations corresponding to them in the decoding process are omitted, e.g. depending on the value of the relaxation attributes. For example, an XOR operation is omitted between two or more consecutive encoding nodes that each have a relaxation attribute indicating that a bit index associated with the encoding node is in a set of most reliable bit indices or a set of least reliable bit indices.

<FIG> shows an example relaxation implementation. As shown in <FIG>, one or more of the following occur in an example relaxation implementation. An initial relaxation attribute is selected for an encoding node. For example, a respective initial relaxation attribute is selected for each encoding node. A relaxation group is determined. A final relaxation level is determined for each relaxation group. A current relaxation level is set to zero. An encoding operation (e.g., including relaxation) is performed on a relaxation group for the current relaxation level. The current relaxation level is incremented (e.g., by <NUM>). Whether the final relaxation level has been reached is determined. If the final relaxation level has been reached, no further relaxation occurs. If the final relaxation level has not been reached, a relaxation attribute is determined for the incremented relaxation level. The encoding operation is be repeated for each relaxation level up to the final relaxation level.

There is a set of encoding nodes (e.g., which may be referred to as nodes), with each encoding node being associated with a bit index and a relaxation level. An encoding node is denoted as (i, j), with i representing the bit index and j representing the relaxation level associated with the encoding node. For example, an encoding node associated with bit index <NUM> and relaxation level <NUM> is denoted as (<NUM>, <NUM>). Two encoding nodes associated with the same bit index and consecutive relaxation levels are connected (e.g., linked). For example, encoding node (<NUM>, <NUM>) and encoding node (<NUM>, <NUM>) are connected. An encoding node (e.g., each encoding node) is associated with a relaxation attribute.

An initial relaxation attribute is selected for an encoding node in the set of encoding nodes. For example, a respective initial relaxation attribute is selected for each encoding node in the set of encoding nodes. A graph-representation of a polar encoding operation (e.g., as described in <FIG> and <FIG>) is followed. The level <NUM> corresponds to input bits. Values of nodes in level <NUM> are calculated from level <NUM> input bits (e.g., by XOR operations). These operations proceed to the level n - <NUM>. Output coded bits of level n are produced.

The relaxation implementation may be combined with encoding and may start from level <NUM> and proceed to the next level of encoding. Initial relaxation requirements may need to be defined (e.g., in the beginning of the proposed relaxation implementation). For example, initial relaxation requirements refer to an extent of relaxation that are given initially. The initial relaxation requirements may be a percentage of encoding nodes that may be relaxed following relaxation. The initial relaxation requirements may be identified by a number of most reliable bits and a number of least reliable bits. The initial relaxation requirements may be based on a complexity reduction-error correction performance trade-off parameter. This parameter may depend on specific use-cases. For example, it may be assigned a value according to the operation (e.g., either in static or dynamic fashion).

A relaxation attribute of a node (i,j) is denoted as RLi,j. If paired nodes (e.g., both paired nodes) in j level have a value of RLi,j = <NUM>, the pair is relaxed and no XOR operation among these nodes may be performed. If at least one node of the paired nodes has a value of RLi,j = <NUM>, there is no relaxation and an XOR operation is performed. <FIG> shows an example of this relation. In a non-relaxed polar code implementation, RLi,j values may all be equal to <NUM>.

In polar code encoding, the indices of two encoding nodes that are paired and have XOR operation at level j are described as follows:
node (i,j) and (i + <NUM>j,j) are paired when mod(i, <NUM>j+<NUM>) = x, where mod(a, b) is the remainder when b divides a. x is a value equal to, for example, <NUM> (e.g., when the index i starts from <NUM>) or <NUM>.

There may be an XOR operation between node (i,j) and (i + <NUM>j,j) in an encoding implementation.

Nodes (i,j) and (i + <NUM>,j) are paired (e.g., always) when mod(i, <NUM>) = x, e.g. where the (non-claimed) bit reversing interleaver is applied in the encoding operation. x is a value equal to, for example, <NUM> (e.g., when the index i starts from <NUM>) or <NUM>. RLi,<NUM> stands for an initial relaxation attribute.

Initial relaxation attributes are determined as described herein.

Initial attributes, RLi,<NUM>, are defined, e.g. by reliability order of polar code construction. The most reliable bits and the most unreliable bits are selected, e.g. as an initial input bit index of relaxation involved nodes. The number of most reliable bits are denoted as Ng, and the number of least reliable bits as Nb. The participating reliable bits and unreliable bits correspond to good channel and bad channel relaxations, respectively. Selection of the most reliable and least reliable bits may be done from a sequence (e.g., a single sequence) indicating the reliability of input bit indices or a sequence (e.g., a single sequence) indicating the input indices in reliability order, e.g. without the necessity of full code construction. With this approach, complexity and/or latency involved in code constructions (e.g., in Bhattacharyya code construction or Gaussian approximation code construction) may be reduced.

Polar code construction is performed by a reliability sequence of input bit indices. The most reliable input bit indices or most unreliable input bit indices are acquired, e.g. based on the sequence showing the reliability order of input bit indices (e.g., each input bit index). Using a reliability sequence of input bit indices may not use a complex calculation of a reliability value of each node and it may increase efficiency.

Initial relaxation attribute determination is performed as described herein. One or more of the following may apply.

A reliability sequence of the polar code of length N is be obtained. A number of nodes to be relaxed in an encoding operation is identified, e.g., using a given code rate (K/N) and a desired complexity-error performance trade-off value. The total number of relaxation candidate nodes (e.g., a total number of "<NUM>'s" of initial attributes) in the <NUM>th level is denoted as Ng + Nb, where Ng relaxation candidate nodes (e.g., a number of "<NUM>'s" selected from most reliable bits) are used in good-channel relaxation, and Nb relaxation candidate nodes (e.g., a number of "<NUM>'s" selected from most unreliable bits) are used in bad-channel relaxation. A first relaxation attribute (e.g., <NUM>) is selected for an encoding node if the bit index associated with the encoding node is included in a set of most reliable bit indices or a set of least reliable bit indices (e.g., as shown in Equation <NUM>). A second relaxation attribute (e.g., <NUM>) is selected for an encoding node if the bit index associated with the encoding node is not included in a set of most reliable bit indices or a set of least reliable bit indices (e.g., as shown in Equation <NUM>). If i ∈ [<NUM>,. , N] is included in most reliable Ng indices or i ∈ [<NUM>,. , N] is included in most unreliable Nb indices, then <MAT> else <MAT>.

Ng is not more than K, whereas Nb is on the order of Ng. The selection of Nb and Ng may depend on the desired performance outcome.

In examples, one may select <MAT> <MAT> which may result in maximum complexity reduction by good and bad channel relaxation.

In examples (e.g., which may provide better performance of good channel relaxation) one may select <MAT> <MAT> Some of the initial RLi,<NUM> = <NUM> values may be changed to <NUM> (e.g., depending on which initial level nodes are selected for relaxation).

Ng > <NUM> corresponds to good channel relaxation and Nb > <NUM> to bad channel relaxation. Good channel relaxation corresponds to relaxing good channel polarization, e.g. sufficient polarization and reliability. Bad channel relaxation corresponds to relaxing bad channel polarization, e.g. inadequate polarization and no further improvement in the future polarization may be expected. When Ng is set to a high value, the complexity reduction ratio may also be high. The performance of relaxed polar code may become worse due to limited polarization created in the encoding. When Ng is set to a low value, the complexity reduction ratio may also be low. Relaxed polar code error correction performance may become better (e.g., comparable to non-relaxed polar code). Non-relaxed polar codes may not show better performance than relaxed polar code. Relaxed polar code may show better performance than non-relaxed polar code, e.g. if a proper value of Ng is selected, which may be in addition to the benefit of complexity reduction. Enhancement in performance may be because there may be increased minimum or average reliability by relaxation.

The complexity reduction ratio (CR) is defined as the ratio of the number of reduced XOR operations (e.g., by relaxation) to the number of XOR operations without relaxation in a polar code encoder.

The number of input bits for bad channel relaxation may be the same as the number of frozen bits, which may maximize the CR value. This may be referred to as full frozen bit relaxation.

Relaxation groups are determined, for example based on the selected relaxation attributes for the encoding nodes. One or more of the following may apply.

A relaxation group includes two or more encoding nodes from the set of encoding nodes. For example, a relaxation group may include a first encoding node and a second encoding node. The first encoding node is associated with a first bit index and a first relaxation level (e.g., an initial relaxation level), and the second encoding node is associated with a second bit index and the first relaxation level. The first relaxation level is relaxation level <NUM>. The first bit index and the second bit index may be consecutive. For example, the first encoding node may be (<NUM>, <NUM>) and the second encoding node may be (<NUM>, <NUM>). The first encoding node and the second encoding node may each be associated with a first relaxation attribute, which indicates that the first bit index and the second bit index are included in a set of most reliable bit indices or a set of least reliable bit indices.

Relaxation indices are grouped based on their local continuity in an input bit domain, e.g. after initialization of the relaxation index and initial attributes (e.g., RLi,<NUM>). A relaxation group determination includes the following:
<IMG>
where c is a parameter that determines the minimum block size of the relaxation group, and where the bit indices of the selected relaxation group correspond to a component polar code. The component polar code includes one or more bit indices. For example, as shown in the pseudocode, a relaxation group determination includes determining whether one or more (e.g., all) attributes of each block with a size of <NUM>b has a value of <NUM>. If all attributes of a block with a size of <NUM>b have a value of <NUM>, the block is selected for relaxation. A current block (e.g., a block with attributes currently being determined) does not include a previously selected block. For example, a relaxation group determination includes searching through N bits. The search is performed block by block (e.g., with a block size of <NUM>b). If the block that is currently being search is not previously relaxed, the block is selected for relaxation.

The minimum block size of a relaxation group may be determined by a value denoted by c such that the minimum block size may be <NUM>c(e.g., where c ≥ <NUM>). The value c may be <NUM> for good and/or bad channel relaxation, or may be a larger value (e.g., to support generalization of the polarization operation to include more than <NUM> bit indices). In the case of c = <NUM>, at least two bit indices are involved in polarization, and at least two nodes are relaxed in the minimum level. In this case, the relaxation attribute of isolated input bits (e.g., single isolated input bits) which have a value of <NUM> in the initial relaxation attribute may be changed to a value of <NUM>. The relaxation attribute values of the consecutive blocks that are not larger than <NUM>c and include consecutive bit indices with attributes equal to <NUM> may be (e.g., all) set to <NUM>. Thus, the number of <NUM> in RLi,<NUM> may be the same as Ng + Nb, e.g. for c = <NUM>, and may be smaller than Ng + Nb, e.g. for c > <NUM>. Changing RLi,<NUM> from <NUM> to <NUM> includes the following:
<IMG>.

Changing RLi,<NUM> from <NUM> to <NUM> (e.g., as described herein) may be performed (e.g., simultaneously) during encoding. In examples, for a bit index i (e.g., for each bit index i) from <NUM> to N, a value for bit index i - <NUM> is expressed as a binary digit, and the number of zeros before the first one may be counted from the least significant bit. The number of zeroes before the first one is denoted as d. Counting the number of zeroes before the first one in the binary expression is equivalent to checking the ones of RLi,<NUM> from a to a + <NUM>d - <NUM> for b = d to c. For example, N = <NUM>, i - <NUM> = <NUM> = <NUM>x<NUM> and number of zeros from the least significant is <NUM>. By checking the ones of {RL<NUM>,<NUM>} , {RL<NUM>,<NUM>, RL<NUM>,<NUM> } , {RL<NUM>,<NUM>, RL<NUM>,<NUM>, RL<NUM>,<NUM>, RL<NUM>,<NUM> }, e.g. in case of c = <NUM>, a group of relaxation is determined. A smaller group may be included in a larger group. The smaller group included is be considered, e.g. if the large group is already determined as a relaxation group.

In a non-claimed variant, the relaxation in the first level (e.g., the <NUM>th level) is applied when at least one node of paired nodes has RLi,<NUM> = <NUM> (e.g., differently from <FIG>, where both paired nodes have RLi,<NUM> = <NUM>), e.g. when c = <NUM>. This relaxation, e.g. by "OR" condition instead of "AND" condition, may be extended or may not be extended to the remaining levels.

Consecutive ones are checked to identify a relaxation group (e.g., if all RLi,<NUM> is <NUM> and RLi,<NUM> is not selected as the group of relaxation for all i from i = a to a + <NUM>b - <NUM>). In a non-claimed variant, this is generalized to another condition, e.g. if <MAT> is true and RLi,<NUM> is not selected as the group of relaxation for all i from i = a to a + <NUM>b - <NUM>. e is the number of ones from i = a to a + <NUM>b - <NUM> and f is a positive real number not more than <NUM> (e.g., f ≈ <NUM> and/or f ≤ <NUM>). An implementation disclosed herein is a special case of f = <NUM>. f may be the code rate of the component (e.g., embedded) polar code as shown in <FIG>, for example in the case of good channel relaxation. The component polar code includes a set of bit indices. A bit index (e.g., each bit index) in the component polar code corresponds to a bit index of an encoding node. The code rate f of the component polar code may be calculated by dividing the number of bit indices in the component polar code that correspond to unfrozen bit indices of encoding nodes with a relaxation attribute of <NUM> divided by the number of bit indices in the component polar code.

In a non-claimed relaxation approach, group selection may correspond to the selection of the encoding node where the relaxation operation may be initiated. For instance, for levels (e.g., each level) of divergence in <FIG>, a node may be selected (e.g., if that node is reliable enough for good channel relaxation or has sufficiently low reliability for bad channel relaxation). This approach is shown in <FIG>. The selection of the node where relaxation is started may be done automatically, e.g. using the values of Ng or Nb.

Polar code may be configured in several ways. In some non-claimed configurations, the input bit index may be bit-reversed, e.g. in comparison to <FIG>. "Bit-reversed" means that the order of binary digit expression is reversed. For example, "0x11100" is bit-reversed to "0x00111. " If BR(x, n) is defined as the bit-reversed value of x (BR(<NUM>x<NUM>,<NUM>) = <NUM>x<NUM> = <NUM>), the above may be modified as follows:
<IMG>
"BR(i - <NUM>, n) + <NUM>" may be "BR(i, n)" (e.g., instead) if indexing starts from <NUM> instead of <NUM>.

A final relaxation level (e.g., a second relaxation level) for a group (e.g., each group) is determined. For a bit index group (e.g., each bit index group) that will participate in relaxation, there is a maximum number of encoding levels b to which relaxation is applied. Relaxation starts from level <NUM> and end at level b - <NUM> for a group (e.g., each group) as described herein. Relaxation is stopped, e.g. after the level b - <NUM>, and is not applied for corresponding relaxation groups in the levels b, b + <NUM>,. The final relaxation level is determined by the length (e.g., or size) of a relaxation group. The final relaxation level may be set to another value, e.g., which may be less than b. For example, the final relaxation level may be the same as the initial relaxation level (e.g., level <NUM>). No relaxation is applied for the final level b because the final level corresponds to the output nodes of embedded polar code, e.g. as shown in <FIG>.

A next level relaxation attribute is determined. The relaxation attribute for a level (e.g., each level) is determined from the previous level (e.g., as shown in <FIG>). In examples, one may set: <MAT> where "cn(i)" stands for a connected node with node (i, j-<NUM>) at level j and cn(i) = i when the configuration shown in <FIG> is used. This implies that the relaxation attribute of the node in the current level is set to <NUM> if the relaxation attribute of connected node in the previous level is <NUM>.

For example, relaxation is continued up to a final relaxation level when they are connected. The final relaxation level is determined to be level b - <NUM>. A relaxation group (e.g., a block of consecutive encoding nodes with a relaxation attribute of <NUM>) may have a size of <NUM>b (e.g., a number of consecutive relaxation attributes of <NUM>).

In certain non-claimed situations (e.g. when a bit reversing interleaver is applied at encoding), the following equations apply: <MAT> <MAT> In certain non-claimed situations (e.g. if the index i starts from <NUM>), the following equations apply: <MAT> <MAT> where <MAT> is the maximum integer not more than x.

Determination of a relaxation attribute (e.g., in the next level) is performed in an incremental manner, e.g. as encoding is processed from left level to right level as shown in <FIG>. In examples, the total relaxation attributes from the initial level to the final level is determined before the encoding operation (e.g., combined with the initial three boxes as shown in <FIG>). For example, relaxation attributes for one or more levels after the initial level may be performed concurrently with one or more of selecting initial relaxation attributes, determining relaxation groups, and/or determining a final relaxation level for each group. For example, relaxation attributes for levels between the initial level and final level (e.g., inclusive) may be determined and/or selected concurrently.

The proposed relaxation implementations correspond to the selection of smaller (e.g. component) polar codes within the overall polar code and its encoding operations, and then relaxing (e.g., completely) these component codes (e.g. no XOR operations within the component codes). For example, a component polar code is a subset of a relaxation group. For instance, the final (or last) relaxation level, b - <NUM>, corresponds to a component polar code of size B = <NUM>b within the parent polar code. <FIG> demonstrates multiple component codes that may participate in a relaxation operation.

Encoding operations of level j (e.g., including relaxation) are performed as described herein. An encoding operation is described as shown in <FIG>. Polar encoding (e.g., conventional polar encoding) starts from level <NUM> and the node values of j are calculated from the previous level j - <NUM> for pairs (e.g., each pair). The values of nodes at level n are final coded bits, e.g. when j = n - <NUM>.

For XOR operations (e.g., each operation) of a pair (i,j) and (i',j), both RLi,j and RLi',j may be <NUM>. i and i' may be consecutive bit indices (e.g., i and i' may differ by <NUM>). The pair may be relaxed and there is no XOR operation performed for the pair. For example, (i, j) and (i', j) may be included in a relaxation group. Encoding may be performed on (i,j) and (i', j), including relaxation (e.g., with an XOR operation between (i, j) and (i', j) omitted). j is incremented by <NUM> and encoding may be performed on (i, j') and (i', j'), including relaxation (e.g., with an XOR operation between (i, j') and (i', j') omitted). j continues incrementing and encoding is performed on encoding nodes in the jth level until the final relaxation level is reached.

A non-claimed compact relaxation attribute determination is described herein.

A non-claimed compact implementation that demonstrates the described relaxation node selection may be described, e.g. which may assume relaxation limited to good channel relaxation and b =<NUM>. Bad channel relaxation or combination with two schemes may be performed in a similar manner. <IMG>
<IMG>
For good channel relaxation, the most reliable Ng bit indices may be selected as attributes of initialization for RLi,<NUM>, e.g. in line <NUM>.

A single relaxation attribute with a value of <NUM> between two consecutive input indices may be excluded, e.g. because the minimal unit of relaxation may be done for a polarization between them. The lines from <NUM> to <NUM> may be performed for this exclusion.

<NUM> to <NUM> in the compact relaxation description may describe the extension of the relaxation technique from the initialization stage j = <NUM> to remaining stages. When RLk,<NUM> (e.g., all) from k = i to k = i + <NUM>j - <NUM> has a value of <NUM>, RLk,l (e.g., all RLk,l) from k = i to k = i + <NUM>j - <NUM> and from l = <NUM> to l = j - <NUM> may be equal to <NUM>. This may correspond to the relaxation of the component polar code, e.g. starting from input bit index i with a size of <NUM>j. The value of j = n may correspond to full polar code length and there may be no need to implement the case in real implementation e.g., because initial nodes (e.g., all initial nodes) participate in relaxation. The finding a group of consecutive ones may proceed until the minimum block size of <NUM>, e.g. because c=<NUM>. Checking of a smaller group may not be performed when a larger group is determined, e.g. in the loop of i, and looping may stop.

Relaxation for rate matching (non-claimed) may be performed as described herein. A rate matching may be applied, e.g. to adapt a code rate or coded block length for polar encoding. There may be one or more implementations which may be considered for rate matching of polar codes. For example, puncturing, shortening, and/or repetition may be considered.

Puncturing (non-claimed) may be performed as described herein. Parts of polar coded bits may be excluded (e.g., punctured), for example depending on the specific puncturing pattern (e.g., may start from the coded bit index <NUM>). There may be corresponding input bits to punctured output coded bits. The value of corresponding input bits may be set to zero. The corresponding input bit index to the punctured bit may be the same as the punctured output bit index, e.g. in the encoder structure as shown in <FIG>. Corresponding input bits may be considered as less reliable bits than the other input bits and may be handled as frozen bits, e.g. in polar code construction. In decoding, the LLR of a punctured output bit may be set as <NUM>, e.g. because there is no allowable information for the punctured bit. The same probability may be assumed for <NUM> and <NUM>.

The proposed relaxation may not be changed when puncturing is applied, e.g. because corresponding input bits may be included in least reliable bits. For example, the proposed relaxation implementations may be applicable even if puncturing is applied during polar encoding. Puncturing may convert one or more input bits into frozen bits. The converted frozen bits may be considered as very unreliable bits, and may be included as part of bad channel relaxation. The same implementation as for bad channel relaxation (e.g., frozen bit relaxation) may be applied.

Shortening (non-claimed) may be performed as described herein. Parts of polar coded bits may be excluded (e.g., shortened), e.g. depending on the specific shortening pattern (e.g., may start from the coded bit index N). There may be corresponding input bits to shortened output coded bits. The value of corresponding input bits may be set to zero. The corresponding input bit index to the shortened bit may be same as the shortened output bit index, e.g. in the encoder structure as shown in <FIG>. Corresponding input bits may be considered as less reliable bits than the other input bits and may be handled as frozen bits, e.g. in polar code construction. In decoding, the LLR of shortened output bit may be set as infinite, e.g. because the value of shortened and coded output bit is <NUM>.

The proposed relaxation may not be changed when shortening is applied, e.g. because corresponding input bits may be included in least reliable bits. For example, the proposed relaxation implementations may be applicable even if shortening is applied during polar encoding. Shortening may convert one or more input bits into frozen bits. The converted frozen bits may be considered as very unreliable bits, and may be included as part of bad channel relaxation. The same implementation as for bad channel relaxation (e.g., frozen bit relaxation) may be applied.

A number of puncturing or shortening may be denoted as P. P may be included in N - K(P < N - K). A code rate for polar encoding may be R = K/M, e.g., when M = N - P.

Repetition (non-claimed) may be performed as described herein. Repetition of polar code may be performed, e.g. when there is no puncturing or shortening. The proposed relaxation implementation may be applied, e.g. without any consideration. For example, relaxation may be performed in a similar manner regardless of whether repetition is performed.

Polar code decoding implementations (e.g., with relaxation) are performed as disclosed herein.

Decoding employed for polar codes is modified based on the defined relaxation. The defined relaxation is used to identify the operations to be omitted in decoding (e.g., as shown in <FIG>).

Decoding polar code may be categorized into one or more implementations, for example Successive Cancellation (SC) based and Belief Propagation (BP) based. In the decoding implementations, the basic unit for decoding may be shown as in <FIG>.

Message passing to left or right is changed for a relaxed pair. <MAT> <MAT> <MAT> <MAT> where G(x,y) is equal to sgn(x)sgn(y)min (|x|, |y|) and sgn(x) is a sign value of x. When x ≥ <NUM>, sgn(x) = <NUM> and when x < <NUM>, sgn(x) = -<NUM>. |x| represents the absolute value of x.

To employ the relaxation in the decoding operation, RLi,j is generated (e.g., initially) for nodes and levels (e.g., all nodes and levels) for decoding of proposed polar code with relaxation, as described herein. RLi,j may be generated in a parallel manner with decoding.

Equations <NUM>-<NUM> may be modified as follows: <MAT> <MAT> <MAT><MAT> when, for example, at least one of RLi,j and RLi',j is <NUM> for a relaxed pair, i and i', and where i' = i + <NUM>j, e.g., as shown in the configuration described in <FIG>.

For an SC-based implementation, decoding and determination of relaxation operations in the decoder levels may be performed in a parallel manner, e.g. since the decoding may start from level n - <NUM> and the maximum value of the final level in the relaxed group may be less than n.

For a BP-based implementation, the message passing from level k to level k + <NUM> may be analogous to polar encoding, and the decoding as well as the relaxation operation determination may be performed (e.g., simultaneously) as described herein.

Numerical results may be presented herein.

Simulation conditions for evaluations described herein are summarized in Table <NUM>.

The details of evaluated implementations are summarized in Table <NUM>. Relaxation implementations (e.g., all) are based on good channel selection (e.g., selection of unfrozen bits).

An evident coding gain by relaxation as proposed herein in a case of code rate <NUM>/<NUM> is observed (e.g., at a high SNR region). The same performance is observed in the other code rates of ¼ and ¾.

The performance improvement (e.g., by relaxation) may be due to the averaging effect on reliability. The error performance in bit channels (e.g., each bit channel) of polar code may be non-uniform and different bit by bit. Overall BLER performance may be more dependent on the error rates of less reliable bits (e.g., rather than those of more reliable bits). Some more reliable bits may have higher reliability than bits without relaxation. Reliability in some nodes may be improved at the expense of sacrificing high reliability in some nodes, e.g. by applying relaxation. BLER or BER performance may be improved, e.g. by minimizing or averaging reliability of overall bit channels.

Non-claimed Bhattacharyya code construction-based relaxation may be performed as described herein.

Bhattacharyya code construction for polar encoding is described herein. Bhattacharyya code construction is independent from other implementations described herein. For example, Bhattacharyya code construction and relaxation are different and independent from other implementations described herein.

Conventional Bhattacharyya code construction is performed as follows:
<IMG>.

Sorting zi,<NUM> for all i = <NUM>, <NUM>,. , N in descending order and select indices from N - K + <NUM> to N. As shown in the pseudocode, one or more indices of frozen and unfrozen bits are determined. To determine the indices, the reliability of an input bit (e.g., each input bit) is calculated. The reliability is calculated from the right-most nodes corresponding to channel symbols.

A proposed non-claimed Bhattacharyya code construction for relaxation is performed as follows
<IMG>
Sorting zi,<NUM> for all i = <NUM>, <NUM>,. , N in descending order and select indices from N - K + <NUM> to N.

As shown in the pseudocode, a reliability value for zi,j is determined. zi,n is the initial reliability (e.g., probability of error) determined by SNR. From right to left, zi,j is calculated based on Bhattacharyya parameter calculation.

tg and tb are thresholds used to determine whether the nodes are candidates for relaxation. tg or tb are decided heuristically based on evaluation for a specific required BLER level.

RLi,j (e.g., all RLi,j) are acquired from the proposed Bhattacharyya code construction. RLi,j are used for encoding and decoding in the same manner described herein. There is no process of determining RLi,j for a next level, and the final level value does not need to be determined in encoding. The conditions of relaxation based on values of RLi,j may be different from other implementations as described herein. For example, if at least one node of two paired nodes in j level has a value of RLi,j = <NUM>, the pair may be relaxed and no XOR operation between these nodes may be performed. If both paired nodes in j level have a value of RLi,j = <NUM>, there is no relaxation and a standard XOR operation may be performed.

An attribute value of RLi,j = <NUM> or RLi,j = <NUM> may correspond to the starting point of good channel and bad channel relaxation, respectively. Nodes with these relaxation attributes are not relaxed, and encoding and decoding operations (e.g., without relaxation) are performed for them. From the next level to the level where these attributes occur, the connected nodes are relaxed and their RLi,j is equal to <NUM>.

The proposed non-claimed Bhattacharyya code construction for relaxation may be used for an application that does not require flexibility of encoder or decoder application. For example, the proposed Bhattacharyya code construction may be used for a fixed code rate application.

An adaptive polar encoder and decoder complexity reduction (e.g., which may be denoted as relaxation) implementation is performed as described herein.

The disclosed polar encoder and decoder complexity reduction (e.g., which may be denoted as relaxation) implementations may be employed and configured adaptively, e.g. by utilizing various system, network, and device parameters (e.g., which may include channel quality, the received signal power at the decoding entity, the battery status of the transmitting and receiving entities, desired BER/QoS performance, etc.). An adaptive configuration may provide performance gains, e.g. reduced power consumption at the transmitting and receiving entities and improved BER/QoS at the receiving entity.

A transmitter may obtain the parameters from the network and the receiver, identify the level of complexity reduction necessary at the transmitter, receiver, or both, and inform the receiver for the corresponding information to be employed in complexity reduction (e.g., as described herein). The receiver may inform the transmitter regarding the complexity reduction it desires. Both entities may employ complexity reduction based on this information.

Implementations (non-claimed) for a transmitter obtaining necessary parameters from a receiver and network are provided herein. The transmitter may inform the receiver regarding the complexity reduction level. Other cases (e.g., the receiver providing the complexity reduction level to the transmitter) may be performed as described herein.

<FIG> shows an example of a non-claimed adaptive system (e.g., an exemplary adaptive channel encoder/decoder complexity reduction (relaxation)). A transmitter transmits polar coded symbols, and a receiver decodes corrupted symbols from a channel. The transmitter identifies (e.g., initially) the desired complexity reduction (e.g., denoted as a relaxation level) to be achieved at the encoder (e.g. at the transmitter), and the decoder (e.g. at the receiver). Based on complexity reduction information obtained from the control channel, the receiver configures the decoder. The decoder has the same structure of relaxation as the transmitter and performs polar decoding. The control channel may be an independent channel from the data channel, or may be jointly configured with the data channel.

The control information related to the complexity reduction may be Ng and/or Nb as described herein. A long field in the control channel format may be required, e.g., when the block length is long (e.g. the potential range of Ng and/or Nb is large). The range may be divided into a number of intervals. The maximum or minimum or average value of Ng and/or Nb may be indexed, e.g. to reduce the redundancy caused by long control field. This index value (e.g., instead of the full Ng and/or Nb information) may be delivered by the control channel.

The complexity reduction detailed herein or conventional relaxation schemes may employ a plurality of offline calculations of relaxation attributes, e.g. at the polar encoding nodes. The relaxation attribute calculations may take different values for possible complexity reduction levels (e.g., degree of relaxation). The exact or index values corresponding to a relaxation attribute (e.g., each relaxation attribute) may be calculated. These indices may be delivered from the transmitter to the receiver, e.g. by a control channel.

The information to be utilized in determining the complexity reduction/relaxation level may be composed of various system, network, and device parameters. The complexity reduction level at the receiver may be determined by the allocated receive power to that particular receiver by the transmitter. In an example, when the scheduled power level to a specific receiver is sufficiently high (e.g., a received SNR can achieve better than desired BER/QoS), further complexity reduction at the receiver (e.g., its decoder) may be employed. Similarly, in the cases of relatively low received SNR, the complexity reduction assigned at the receiving entity may be lowered to yield sufficient BER performance.

A degree of complexity reduction may be determined by a transmitter depending on a receiver's information of battery status. The information may be delivered by the other control channel (e.g., as shown by the dotted line in <FIG>). Delivery of battery status information may be similar to Channel State Information (CSI) reporting. The transmitter may deliver the control information corresponding to high degree of relaxation, e.g. when the receiver has low battery power level. The transmitter may deliver the control information corresponding to low degree of relaxation, e.g. when the receiver has high battery power level, or when the receiver has low battery power level but it is charging.

<FIG> shows a trade-off relation between complexity reduction and BLER performance. The simulation conditions are the same as in <FIG>.

The complexity reduction-BLER performance trade-off is seen as shown in <FIG>. For the case of a receiving entity requiring a minimum of <NUM>^-<NUM> BLER, based on the implementations disclosed herein, the transmitter (e.g., or the receiver itself) may identify the complexity reduction parameter, e.g. Ng=~<NUM>. This information may be exchanged between the transmitter and receiver, which may then be used in the disclosed polar encoder and decoder operations.

<FIG> shows an example associated with relaxation. As shown in <FIG>, there are one or more encoding nodes (e.g., encoding nodes <NUM>, <NUM>, <NUM>, <NUM> shown in <FIG>). Each encoding node is associated with a bit index and a level (e.g., a relaxation level). For example, as shown in <FIG>, there are three levels, level <NUM>, level <NUM>, and level <NUM>. For example, encoding node <NUM> is associated with bit index <NUM> and level <NUM>, encoding node <NUM> with bit index <NUM> and level <NUM>, encoding node <NUM> with bit index <NUM> and level <NUM>, and encoding node <NUM> with bit index <NUM> and level <NUM>. Encoding nodes associated with the same bit index and consecutive levels (e.g., encoding nodes <NUM> and <NUM>, or encoding nodes <NUM> and <NUM>) may be connected or linked.

An initial relaxation attribute (e.g., RLi,<NUM>) is selected for each encoding node in an initial level (e.g., level <NUM>), where i denotes the bit index for the encoding node. A first relaxation attribute (e.g., <NUM>) is selected for encoding nodes associated with most reliable (e.g., Ng) and/or most unreliable (e.g., Nb) bit indices. Whether a bit index is one of the most reliable or most unreliable bit indices may be determined by comparing a reliability value associated with the bit index to a first threshold and/or a second threshold. For example, if the reliability value associated with the bit index is higher than the first threshold, the bit index is a most reliable bit index, or if the bit index is lower than the second threshold, the bit index is a most unreliable bit index. A second relaxation attribute (e.g., <NUM>) is selected for bit indices that are not one of the most reliable or most unreliable bit indices. As shown in <FIG>, the first relaxation attribute is selected for encoding nodes <NUM> and <NUM>.

A relaxation group in the initial level is determined based on the selected relaxation attributes. A relaxation group includes two or more encoding nodes. For example, as shown in <FIG>, relaxation group <NUM> includes encoding nodes <NUM> and <NUM>. Encoding nodes in the relaxation group are associated with consecutive bit indices. Each encoding node in the relaxation group is associated with the first relaxation attribute.

A final relaxation level for a relaxation group (e.g., each group) is determined. For example, the final relaxation level indicates a final level where relaxation is performed on the relaxation group. For example, as shown in <FIG>, there are two relaxation levels, level <NUM> and level <NUM>. The final relaxation level is determined based on the size of the relaxation group. For example, the final relaxation level is equal to log<NUM>(m) - <NUM>, where m is the size of the relaxation group. A final relaxation level for relaxation group <NUM> is determined to be level <NUM> (e.g., because log<NUM>(<NUM>) - <NUM> = <NUM>).

Encoding is performed on the relaxation group depending on the selected relaxation attributes for the encoding nodes in the relaxation group. Encoding is performed on the encoding nodes in the relaxation group based on the relaxation levels. For example, as shown in <FIG>, encoding is firstly performed on the level <NUM> encoding nodes (e.g., encoding nodes <NUM> and <NUM>) in the relaxation group and secondly on the level <NUM> nodes (e.g., encoding nodes <NUM> and <NUM>). The encoding includes relaxation. For example, an XOR operation may be omitted between encoding nodes in the relaxation group in the same level. For example, a first XOR operation between encoding nodes <NUM> and <NUM> is omitted, and a second XOR operation between encoding nodes <NUM> and <NUM> is omitted. After relaxation is performed on encoding nodes in a given level, relaxation attributes for encoding nodes in the next level are determined. For example, after relaxation is performed on encoding nodes <NUM> and <NUM>, relaxation attributes are determined for encoding nodes <NUM> and <NUM>. The same attribute as the connected node of a previous level is assigned, e.g. before reaching b. Encoding (e.g., including relaxation) proceeds before the final relaxation level is reached. For example, encoding is performed on levels (e.g., each level) up to level b - <NUM>, inclusive.

Although the features and elements of the present invention are described in the preferred embodiments in particular combinations, each feature or element may be used alone without the other features and elements of the preferred embodiments or in various combinations with or without other features and elements of the preferred embodiments as long as said variations fall under the scope of the present invention as set out in the appended claims.

Claim 1:
A wireless transmit/receive unit, WTRU, (<NUM>) for performing polar code encoding and/or decoding based on a polar code graph consisting of (n+<NUM>)N nodes, where N denotes the code length of the polar code with N=<NUM>n, each node being indexed by (i,j) with bit index i = <NUM>, <NUM>, ... , N and level j=<NUM>, <NUM>, ..., n, nodes (i, <NUM>) indicate input bits for polar code encoding and nodes (i, n) indicate output coded bits and each node (i,j) is associated with a relaxation attribute RLi,j, the WTRU comprising:
a processor (<NUM>) configured to:
select an initial relaxation attribute RLi,<NUM> using a reliability order of input bit indices, wherein the initial relaxation attribute RLi,<NUM> = <NUM> indicates that the associated nodes are included in a set of most reliable bit indices or in a set of least reliable bit indices;
determine one or more relaxation groups and a corresponding final relaxation level for each of the one or more relaxation groups based on the initial relaxation attributes RLi,<NUM> according to
<IMG>
where c is the minimum block size of each of said one or more relaxation groups; and
for each determined relaxation group, iteratively select relaxation attributes RLi,j for the level j=<NUM> up to the final relaxation level of said relaxation group as RLi,j = <NUM> if RLi,j-<NUM> = <NUM> for bit indices i within said relaxation group; and
perform polar code encoding using the polar code graph by relaxing paired nodes where both paired nodes have a relaxation attribute RLi,j =<NUM> so that no XOR operation among said relaxed paired nodes is performed and/or perform polar code decoding by relaxing paired nodes where both paired nodes have a relaxation attribute RLi,j =<NUM> so that no decoding XOR operation among said relaxed paired nodes is performed.