NOMINAL COMPLEXITY AND WEIGHTED COMBINATIONS FOR POLAR CODE CONSTRUCTION

Methods, systems, and devices for wireless communication are described. A wireless device may decode a polar coded codeword using a successive cancelation (SC) or successive cancelation list (SCL) decoder. The construction of the codeword may be based on multiple factors, such as a decoding complexity, reliability, codeword size, number of information bits, type of communication, etc. In some cases, multiple codeword constructions may be compared (e.g., with various weights applied to the relevant factors) and an optimal construction selected. Techniques described herein are applicable both to the selection of an optimal codeword as well as decoding operations. Specifically, the described techniques may allow for a reduced decoding complexity through the use of subtree pruning, in which characteristics of the polar scheme (e.g., the scheme selected by the encoder) may be exploited to reduce the complexity of the decoding operation.

BACKGROUND

The following relates generally to wireless communication, and more specifically to nominal complexity and weighted combinations for polar code construction.

Information transmitted between devices in wireless multiple-access communications systems may be encoded into a codeword in order to improve the reliability of successfully decoding the transmitted information. In some cases, codewords may provide redundancy, which may be used to correct errors that result from the transmission environment (e.g., path loss, obstacles, etc.). Some examples of encoding algorithms with error correcting codes include convolutional codes (CCs), low-density parity-check (LDPC) codes, and polar codes. A polar code is an example of a linear block error correcting code and has been shown to asymptotically approach the theoretical channel capacity as the code length increases. Polar codes are based on polarization of sub-channels used for information bits or frozen bits (e.g., predetermined bits set to a ‘0’ or a ‘1’), with information bits generally assigned to the higher reliability sub-channels. However, practical implementations of a polar decoder are complex due to the ordered nature of decoding and list decoding techniques used for improving the error-correcting performance. Techniques for high-performance polar codes that reduce complexity of decoding are desired.

SUMMARY

The described techniques relate to improved methods, systems, devices, or apparatuses that support nominal complexity and weighted combinations for polar code construction. Generally, the described techniques provide for receiving and transmitting a codeword encoded using a polar code. The codeword contains a plurality of information bits as well as one or more frozen bits. The information bits may be allocated to a given set of polar channel indices. The set of polar channel indices may be determined based at least in part on a reliability metric of each index of the set and a decoding complexity associated with the codeword as a whole. Accordingly, receiving and transmitting devices may be configured to identify (e.g., may dynamically determine, may identify based on some pre-configured information, etc.) the set of polar channel indices for a given situation (e.g., a given codeword size, a number of information bits, a type of communication, etc.).

A method of wireless communication is described. The method may include receiving a codeword encoded using a polar code, the codeword generated based on a set of information bits, identifying a set of polar bit channel indices corresponding to the set of information bits, where the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices, and decoding the codeword to obtain the set of information bits based on the set of polar bit channel indices.

An apparatus for wireless communication is described. The apparatus may include a processor, memory in electronic communication with the processor, and instructions stored in the memory. The instructions may be executable by the processor to cause the apparatus to receive a codeword encoded using a polar code, the codeword generated based on a set of information bits, identify a set of polar bit channel indices corresponding to the set of information bits, where the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices, and decode the codeword to obtain the set of information bits based on the set of polar bit channel indices.

Another apparatus for wireless communication is described. The apparatus may include means for receiving a codeword encoded using a polar code, the codeword generated based on a set of information bits, identifying a set of polar bit channel indices corresponding to the set of information bits, where the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices, and decoding the codeword to obtain the set of information bits based on the set of polar bit channel indices.

A non-transitory computer-readable medium storing code for wireless communication is described. The code may include instructions executable by a processor to receive a codeword encoded using a polar code, the codeword generated based on a set of information bits, identify a set of polar bit channel indices corresponding to the set of information bits, where the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices, and decode the codeword to obtain the set of information bits based on the set of polar bit channel indices.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the decoding complexity metric may be based on a number of logarithmic likelihood ratio (LLR) derivations for at least one polar bit channel index of the set of polar bit channel indices, a number of bit feedback operations for the at least one polar bit channel index of the set of polar bit channel indices, or a combination thereof.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, for the at least one polar bit channel index of the set of polar bit channel indices, one or both of the number of bit feedback operations or the number of LLR derivations may be based on a tree traversal depth between the at least one polar bit channel index and a prior polar bit channel index of the set of polar bit channel indices.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the decoding complexity metric may be determined based on merging single parity check decoding operations and repetition decoding operations for a subtree of the polar code.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the subtree includes less than two of the set of polar bit channel indices and at least one frozen bit index.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the decoding complexity metric may be generated based on a tree traversal depth between adjacent polar bit channel indices of the set of polar bit channel indices, the subtree including one of the adjacent polar bit channel indices.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the identifying the set of polar bit channel indices may include operations, features, means, or instructions for determining a provisional set of polar bit channel indices for the set of information bits based on a reliability metric for the provisional set of polar bit channel indices, determining an aggregate performance metric for the provisional set of polar bit channel indices, the aggregate performance metric based on a provisional decoding complexity metric, iteratively modifying at least one index of the provisional set of polar bit channel indices and determining a modified aggregate performance metric for each of a set of search branches and adopting the modified provisional set of polar bit channel indices having a highest modified aggregate performance metric as the set of polar bit channel indices.

Some examples of the method, apparatuses, and non-transitory computer-readable medium described herein may further include operations, features, means, or instructions for determining a weighted combination of the reliability metric and the decoding complexity metric by applying a first weighting factor to the reliability metric and applying a second weighting factor to the decoding complexity metric, where the set of polar bit channel indices may be selected from the set of polar bit channel indices of the polar code based on the weighted combination.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, one or both of the first weighting factor or the second weighting factor may be based on a type of wireless communication protocol associated with the codeword.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the type of wireless communication protocol includes one of enhanced mobile broadband (eMBB), ultra-reliable low latency communication (URLLC), Internet of Things (IoT) communication, or machine-type communication (MTC).

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, an aggregate reliability weight for eMBB may be greater than an aggregate reliability weight for URLLC and MTC, where the aggregate reliability weights may be determined based on the first weighting factor applied to the reliability metric.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, an aggregate complexity weight for eMBB may be less than an aggregate complexity weight for URLLC and MTC, where the aggregate complexity weights may be determined based on the second weighting factor applied to the decoding complexity metric.

A method of wireless communication is described. The method may include identifying a set of polar bit channel indices corresponding to a set of information bits of an information bit vector for encoding using a polar code, where the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices, encoding the set of information bits according to the polar code based on the set of polar bit channel indices to obtain a codeword, and transmitting the codeword.

An apparatus for wireless communication is described. The apparatus may include a processor, memory in electronic communication with the processor, and instructions stored in the memory. The instructions may be executable by the processor to cause the apparatus to identify a set of polar bit channel indices corresponding to a set of information bits of an information bit vector for encoding using a polar code, where the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices, encode the set of information bits according to the polar code based on the set of polar bit channel indices to obtain a codeword, and transmit the codeword.

Another apparatus for wireless communication is described. The apparatus may include means for identifying a set of polar bit channel indices corresponding to a set of information bits of an information bit vector for encoding using a polar code, where the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices, encoding the set of information bits according to the polar code based on the set of polar bit channel indices to obtain a codeword, and transmitting the codeword.

A non-transitory computer-readable medium storing code for wireless communication is described. The code may include instructions executable by a processor to identify a set of polar bit channel indices corresponding to a set of information bits of an information bit vector for encoding using a polar code, where the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices, encode the set of information bits according to the polar code based on the set of polar bit channel indices to obtain a codeword, and transmit the codeword.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the decoding complexity metric may be based on a number of LLR derivations for at least one polar bit channel index of the set of polar bit channel indices, a number of bit feedback operations for the at least one polar bit channel index of the set of polar bit channel indices, or a combination thereof.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, for the at least one polar bit channel index of the set of polar bit channel indices, one or both of the number of bit feedback operations or the number of LLR derivations may be based on a tree traversal depth between the at least one polar bit channel index and a prior polar bit channel index of the set of polar bit channel indices.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the decoding complexity metric may be determined based on merging single parity check decoding operations and repetition decoding operations for a subtree of the polar code.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the subtree includes less than two of the set of polar bit channel indices and at least one frozen bit index.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the decoding complexity metric may be generated based on a tree traversal depth between adjacent polar bit channel indices of the set of polar bit channel indices, the subtree including one of the adjacent polar bit channel indices.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the identifying the set of polar bit channel indices may include operations, features, means, or instructions for determining a provisional set of polar bit channel indices for the set of information bits based on a reliability metric for the provisional set of polar bit channel indices, determining an aggregate performance metric for the provisional set of polar bit channel indices, the aggregate performance metric based on a provisional decoding complexity metric, iteratively modifying at least one index of the provisional set of polar bit channel indices and determining a modified aggregate performance metric for each of a set of search branches and adopting the modified provisional set of polar bit channel indices having a highest modified aggregate performance metric as the set of polar bit channel indices.

Some examples of the method, apparatuses, and non-transitory computer-readable medium described herein may further include operations, features, means, or instructions for determining a weighted combination of the reliability metric and the decoding complexity metric by applying a first weighting factor to the reliability metric and applying a second weighting factor to the decoding complexity metric, where the set of polar bit channel indices may be selected from the set of polar bit channel indices of the polar code based on the weighted combination.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, one or both of the first weighting factor or the second weighting factor may be based on a type of wireless communication protocol associated with the codeword.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, the type of wireless communication protocol includes one of eMBB, URLLC, IoT communication, or MTC.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, an aggregate reliability weight for eMBB may be greater than an aggregate reliability weight for URLLC and MTC, where the aggregate reliability weights may be determined based on the first weighting factor applied to the reliability metric.

In some examples of the method, apparatuses, and non-transitory computer-readable medium described herein, an aggregate complexity weight for eMBB may be less than an aggregate complexity weight for URLLC and MTC, where the aggregate complexity weights may be determined based on the second weighting factor applied to the decoding complexity metric.

DETAILED DESCRIPTION

Some wireless communications systems may support the use of polar codes, which are a type of linear block error correcting code that has been shown to approach the theoretical channel capacity as the code length increases. The number of sub-channels for polar codes follows a power function (e.g., 2X), where a number of information bits are mapped to different polarized sub-channels (e.g., polar channel indices). The capacity of a given polar channel index may be a function of a reliability metric of the polar channel index. Information bits may be loaded on a set of polar channel indices, and the remaining bits (e.g., frozen bits) may be loaded on the remaining polarized bit channels. The number of permutations for the set of polar channel indices for a given polar code length may be large. As an example, a codeword may be encoded using a polar code of length256, of which 16 polar channel indices are allocated as information bits. In such a scenario, the number of potential information bit polar index sets (i.e., the number of groups of 16 indices in which at least one index differs between each set) is on the order of 1038.

Error correction performance of the polar code may be optimized with selection of the information bit polar index set based on reliability of the polar indices. However, polar codes that are constructed purely based on the reliability of successfully receiving and decoding a codeword may not provide sufficient performance in all scenarios. For example, devices with constrained battery power and/or devices for whom low latency is a key performance indicator may in some cases prefer selection of the information bit polar index set to reduce decoding complexity (e.g., at the cost of lower reliability). However, when considering that devices may support multiple schemes in which the codeword length and/or the number of information bits vary between schemes, and further considering that different decoders may implement decoding functions using different schemes (e.g., a software decoder, a hardware decoder) with different complexity constraints, comparison of decoding performance and decoding complexity between different sets of indices becomes computationally rigorous.

The described techniques are directed to optimizing the decoding performance and decoding complexity for polar codes. In some cases, determination of the information bit polar index set may be based on one or more factors (e.g., reliability, decoding complexity, number of feedback operations, etc.) that are appropriately weighted in order to produce an aggregate metric for the information bit polar index set (e.g., which can be compared to aggregate metrics for other information bit polar index sets). In some cases, determination of a decoding complexity for a given information bit polar index set may be based at least in part on simplifications of the decoding operation in accordance with various techniques described herein. Additionally or alternatively, the described simplifications may be used in practice at a decoder in order to reduce the decoding complexity. The simplifications are generally based on sub-tree pruning of a polar code tree (e.g., in which given sub-trees within the polar code tree are treated as a block). Strategically grouping calculations into blocks may reduce the number of operations that need to be performed, which may in turn benefit the decoding device (e.g., in terms of latency, power consumption, etc.).

Aspects of the disclosure are initially described in the context of a wireless communications system. Aspects of the disclosure are then illustrated by and described with reference to various polar code structures, subtrees, and decoding schemes. Aspects of the disclosure are further illustrated by and described with reference to apparatus diagrams, system diagrams, and flowcharts that relate to nominal complexity and weighted combinations for polar code construction.

FIG. 1illustrates an example of a wireless communications system100in accordance with various aspects of the present disclosure. The wireless communications system100includes base stations105, UEs115, and a core network130. In some examples, the wireless communications system100may be a Long Term Evolution (LTE), LTE-Advanced (LTE-A) network, or a New Radio (NR) network. In some cases, wireless communications system100may support enhanced broadband communications, ultra-reliable (i.e., mission critical) communications, low latency communications, and communications with low-cost and low-complexity devices. Base stations105and UEs115may use a polar code design to encode information bits of an input vector to obtain a codeword for transmission. In some cases, the base stations105and UEs115may reduce decoding complexity (e.g., at the expense of decoding reliability) for these transmissions by shifting a position of at least one information bit. Additionally or alternatively, a decoder may achieve reductions in decoding complexity and/or latency using one or more simplification techniques described below.

Base stations105may wirelessly communicate with UEs115via one or more base station antennas. In some cases, the transmissions may be encoded using a polar code design. Each base station105may provide communication coverage for a respective geographic coverage area110. Communication links125shown in wireless communications system100may include uplink transmissions from a UE115to a base station105, or downlink transmissions from a base station105to a UE115. Control information and data may be multiplexed on an uplink channel or downlink according to various techniques. Control information and data may be multiplexed on a downlink channel, for example, using time division multiplexing (TDM) techniques, frequency division multiplexing (FDM) techniques, or hybrid TDM-FDM techniques. In some examples, the control information transmitted during a transmission time interval (TTI) of a downlink channel may be distributed between different control regions in a cascaded manner (e.g., between a common control region and one or more UE-specific control regions).

In some cases, a UE115may also be able to communicate directly with other UEs (e.g., using a peer-to-peer (P2P) or device-to-device (D2D) protocol). One or more of a group of UEs115utilizing D2D communications may be within the coverage area110of a cell. Other UEs115in such a group may be outside the coverage area110of a cell, or otherwise unable to receive transmissions from a base station105. In some cases, groups of UEs115communicating via D2D communications may utilize a one-to-many (1:M) system in which each UE115transmits to every other UE115in the group. In some cases, a base station105facilitates the scheduling of resources for D2D communications. In other cases, D2D communications are carried out independent of a base station105.

In some cases, an MTC device may operate using half-duplex (one-way) communications at a reduced peak rate. MTC devices may also be configured to enter a power saving “deep sleep” mode when not engaging in active communications. In some cases, MTC or IoT devices may be designed to support mission critical functions and wireless communications system may be configured to provide ultra-reliable communications for these functions.

The core network130may provide user authentication, access authorization, tracking, Internet Protocol (IP) connectivity, and other access, routing, or mobility functions. At least some of the network devices, such as base station105may include subcomponents such as an access network entity, which may be an example of an access node controller (ANC). Each access network entity may communicate with a number of UEs115through a number of other access network transmission entities, each of which may be an example of a smart radio head, or a transmission/reception point (TRP). In some configurations, various functions of each access network entity or base station105may be distributed across various network devices (e.g., radio heads and access network controllers) or consolidated into a single network device (e.g., a base station105).

Wireless communications system100may operate in an ultra-high frequency (UHF) frequency region using frequency bands from 700 MHz to 2600 MHz (2.6 GHz), although some networks (e.g., a wireless local area network (WLAN)) may use frequencies as high as 4 GHz. This region may also be known as the decimeter band, since the wavelengths range from approximately one decimeter to one meter in length. UHF waves may propagate mainly by line of sight, and may be blocked by buildings and environmental features. However, the waves may penetrate walls sufficiently to provide service to UEs115located indoors. Transmission of UHF waves is characterized by smaller antennas and shorter range (e.g., less than 100 km) compared to transmission using the smaller frequencies (and longer waves) of the high frequency (HF) or very high frequency (VHF) portion of the spectrum. In some cases, wireless communications system100may also utilize extremely high frequency (EHF) portions of the spectrum (e.g., from 30 GHz to 300 GHz). This region may also be known as the millimeter band, since the wavelengths range from approximately one millimeter to one centimeter in length. Thus, EHF antennas may be even smaller and more closely spaced than UHF antennas. In some cases, this may facilitate use of antenna arrays within a UE115(e.g., for directional beamforming). However, EHF transmissions may be subject to even greater atmospheric attenuation and shorter range than UHF transmissions.

Thus, wireless communications system100may support millimeter wave (mmW) communications between UEs115and base stations105. Devices operating in mmW or EHF bands may have multiple antennas to allow beamforming. That is, a base station105may use multiple antennas or antenna arrays to conduct beamforming operations for directional communications with a UE115. Beamforming (which may also be referred to as spatial filtering or directional transmission) is a signal processing technique that may be used at a transmitter (e.g., a base station105) to shape and/or steer an overall antenna beam in the direction of a target receiver (e.g., a UE115). This may be achieved by combining elements in an antenna array in such a way that transmitted signals at particular angles experience constructive interference while others experience destructive interference.

Multiple-input multiple-output (MIMO) wireless systems use a transmission scheme between a transmitter (e.g., a base station105) and a receiver (e.g., a UE115), where both transmitter and receiver are equipped with multiple antennas. Some portions of wireless communications system100may use beamforming. For example, base station105may have an antenna array with a number of rows and columns of antenna ports that the base station105may use for beamforming in its communication with UE115. Signals may be transmitted multiple times in different directions (e.g., each transmission may be beamformed differently). A mmW receiver (e.g., a UE115) may try multiple beams (e.g., antenna subarrays) while receiving the synchronization signals.

In some cases, the antennas of a base station105or UE115may be located within one or more antenna arrays, which may support beamforming or MIMO operation. One or more base station antennas or antenna arrays may be collocated at an antenna assembly, such as an antenna tower. In some cases, antennas or antenna arrays associated with a base station105may be located in diverse geographic locations. A base station105may multiple use antennas or antenna arrays to conduct beamforming operations for directional communications with a UE115.

A shared radio frequency spectrum band may be utilized in an NR shared spectrum system. For example, an NR shared spectrum may utilize any combination of licensed, shared, and unlicensed spectrums, among others. The flexibility of eCC symbol duration and subcarrier spacing may allow for the use of eCC across multiple spectrums. In some examples, NR shared spectrum may increase spectrum utilization and spectral efficiency, specifically through dynamic vertical (e.g., across frequency) and horizontal (e.g., across time) sharing of resources.

FIG. 2illustrates an example of a device200that supports nominal complexity and weighted combinations for polar code construction in accordance with various aspects of the present disclosure. The device200may be any device within a wireless communications system100that performs an encoding or decoding process. For example, the device200may be a UE115or base station105, as described inFIG. 1.

As shown, device200includes a memory205, an encoder/decoder210, and a transmitter/receiver215. Bus220may connect memory205to encoder/decoder210and bus225may connect encoder/decoder210to transmitter/receiver215. In some instances, device200may have data stored in memory205to be transmitted to another device, such as a UE115or base station105. To initiate the transmission process, the device200may retrieve from memory205data (e.g., in the form of an input vector) for transmission. The data may include a number of information bits provided from memory205to encoder/decoder210via bus220. The number of information bits may be represented as a value ‘k,’ as shown. The encoder/decoder210may encode the number of information bits and output a codeword having a length ‘N.’ The bits that are not allocated as information bits (i.e., N−k bits) may be assigned as frozen bits. Frozen bits may be bits of a value (e.g., 0) known to both the encoder and decoder (i.e., the encoder encoding information bits at a transmitter and the decoder decoding the codeword received at a receiver). Further, from the receiving device perspective, device200may receive encoded data via receiver215, and decode the encoded data using decoder210to obtain the transmitted data.

In some wireless systems, the decoder210may be an example of a successive cancellation list (SCL) decoder. A UE115or base station105may receive a transmission including a codeword at the receiver215, and may decode the codeword (e.g., using the decoder210). The SCL decoder may determine input logarithmic-likelihood ratios (LLRs) for the bit channels of the received codeword. During decoding, the SCL decoder may determine decoded LLRs based on these input LLRs, where the decoded LLRs correspond to each bit channel of the polar code. These decoded LLRs may be referred to as bit metrics. In some cases, if the LLR is zero or a positive value, the SCL decoder may determine the corresponding bit is a 0 bit. Alternatively, a negative LLR may correspond to a 1 bit. The SCL decoder may use the bit metrics to determine the decoded bit values.

The SCL decoder may employ multiple concurrent successive cancellation (SC) decoding processes. Each SC decoding process may decode the codeword sequentially (e.g., in order of the bit channel indices). Due to the combination of multiple SC decoding processes, the SCL decoder may calculate multiple decoding path candidates. For example, an SCL decoder of list size ‘L’ (i.e., the SCL decoder has L SC decoding processes) may calculate L decoding path candidates, and a corresponding reliability metric (e.g., a path metric) for each decoding path candidate. The path metric may represent a reliability of a decoding path candidate or a probability that the corresponding decoding path candidate is the correct set of decoded bits. The path metric may be based on the determined bit metrics and the bit values selected at each bit channel. The SCL decoder may have a number of levels equal to the number of bit channels in the received codeword. At each level, each decoding path candidate may select either a 0 bit or a 1 bit based on a path metric of the 0 bit and the 1 bit. The SCL decoder may select a decoding path candidate based on the path metrics, and may output the bits corresponding to the selected decoding path as the decoded sets of bits. For example, the SCL decoder may select the decoding paths with the highest path metrics.

The decoder210may improve decoding latency due to LLR derivation and bit feedback if it does not need to perform operations to determine every bit in the decoding path. For example, if a number of sub-channels correspond to known bit values, the decoder210may skip performing computations in order to determine hard bit values for the sub-channels. If the decoder210determines that the first number of bits are all frozen bits, the decoder210may determine that the correct decoding path for the first number of bits are the default values associated with frozen bits (e.g., if the default frozen bit value is 0, the correct decoding path for the first number of bits is determined to be all zeros). Once the decoder210reaches the first information bit, the decoder210may begin performing operations to decode the rest of the bits of the codeword, as the decoder210may not be able to determine the correct decoding path from the first information bit onwards (e.g., because the first information bit may be a 0 or a 1 and represents the first branch in the decoding tree).

In accordance with various aspects of the present disclosure, bit selection schemes that factor reliability of the bit channels as well as decoding complexity may be employed to determine how to allocate the k information bits among the N bits of the codeword. For example, a first scheme may be used for scenarios in which decoding latency and power consumption are key performance indicators (e.g., ultra-reliable low latency communications (URLLC), massive MTC (mMTC), Internet-of Things (IoT), etc.). Because decoding complexity may in some cases be tied to decoding latency and/or power consumption, the first bit selection scheme may weigh reductions in decoding latency more heavily than improvements in reliability. Alternatively, a second bit selection scheme may be used for scenarios in which transmission reliability is a more important performance indicator than decoding latency or power consumption (e.g., enhanced mobile broadband (eMBB) communications). The second bit selection scheme may therefore weight improvements in reliability more heavily than reductions in decoding latency.

Polar codes are characterized by the fact that the decoding complexity has a strong dependency on the location of the information bits (e.g., as opposed to other codes such as tail-biting convolutional codes (TBCCs) in which the decoding complexity is more uniformly distributed across the bit positions). Accordingly, the decoding complexity for any two bit positions (e.g., which may or may not be separated by one or more frozen bits) may vary.

Generally, the techniques described herein support development of a suitable bit selection scheme for a given scenario that sufficiently reflects the relevant factors in the target scenario. If multiple factors (e.g., power consumption, reliability, decoding complexity, etc.) play a role in a target scenario, the polar code for the target scenario may be constructed based on a relevant bit selection scheme. The described techniques include an effective method to capture (and in some cases reduce) the complexity of decoding operations. The described techniques may account for various simplifications in decoding to determine a nominal complexity for various types of decoders. Further considerations for comparing and combining various bit selection schemes are detailed below.

In some cases, aspects of the encoding and decoding techniques described herein may be performed at an entity other than encoder/decoder210. For example, the entity may be part of wireless communications system100or may be independent of wireless communications system100. The polar codeword structures may, for example, be empirically determined by a special purpose processor (e.g., one designed or configured to implement the various described techniques) or some other suitable entity. This entity may determine a codeword structure for a variety of scenarios (e.g., different N, k, L, transmission type, etc.) based on an optimized combination of decoding complexity/latency and reliability metrics. Communicating devices may then be configured to encode and decode transmissions using the specified codeword structure. For example, communicating devices may be preconfigured (e.g., with a look-up table), semi-statically configured (e.g., through various control signaling such as RRC control signaling), or dynamically configured (e.g., through downlink control information (DCI)) to use a first table for a first communication type (e.g., eMBB) and a second table for a second communication type (e.g., URLLC), where each table specifies a respective bit order, and the tables differ for at least one bit position.

FIG. 3illustrates an example polar code structure300as a convenient way to conceptualize construction of a polar codeword in accordance with various aspects of the present disclosure. Polar code structure300includes N (e.g.,256, as illustrated) bit positions305. Each bit position305may be indexed (e.g., such that the top bit position305-ais indexed 0 and the bottom bit position305-eis indexed 255). In a given polar code structure of length N, K bit positions305may be allocated for information bits. The set of indices associated with these K bit positions305may be referred to as a set of information bit channel indices.

As illustrated, polar code structure300contains multiple (e.g.,9in the present example) layers310arranged in a hierarchical fashion. For example, each block in layer310-icontains two blocks in layer310-h, four blocks in layer320-g, etc. In some cases, the layers310may be illustrated in a tree structure (e.g., as illustrated below with respect toFIGS. 6 through 8). Accordingly, blocks in intermediate layers310-h,310-g,310-f,310-e,310-d,310-c,310-bmay be referred to as subtrees in various examples. For example, the third block from the top in layer310-fmay be a subtree which spans a set315of bit positions305(e.g., 32 bit positions305). Some, all, or none of the bit positions305in set315may be frozen bits. Layer310-amay, in some cases, be referred to as the leaf layer.

As discussed above, each bit position305may have an associated reliability, and the set of all bit positions305may be ranked accordingly. By way of example, the 18 most reliable bit positions305may have indices in the set [222 127 237 243 238 245 191 246 249 250 223 252 239 247 251 253 254 255]. In this example and the following description, the indices are included for the sake of explanation only; the concepts may be generalized to other example sets of indices. In polar code structure300, bit position305-bhas index127, bit position305-chas index191, and bit position305-dhas index222. Construction of a polar codeword of length256that contains 17 information bits in which the only relevant metric is reliability may simply select the indices of the 17 most reliable bit positions305(i.e., beginning with bit position305-bwith index127and continuing through the end of the set to give [127 237 243 238 245 191 246 249 250 223 252 239 247 251 253 254 255]).

However, as mentioned above, the decoding complexity of a polar codeword is not uniformly distributed across all the bit positions. Accordingly, sets of bit indices that differ only in the inclusion of one or two bit positions305may have different (e.g., sometimes significantly different) decoding complexities. By way of example, the set of indices beginning with bit position305-b(index127) and continuing through the end of the set may have a significantly higher decoding complexity than the set of indices beginning with bit position305-d(index222), excluding bit position305-bwith index127, and continuing through the end of the set (e.g., [222 237 243 238 245 191 246 249 250 223 252 239 247 251 253 254 255]). For ease of reference, these sets are referred to as a first set and second set, respectively (i.e., the first set contains index127, while the second set contains index222instead).

The first set may have a higher decoding complexity because there are fewer leading frozen bits. That is, for the first set, the bit positions indexed 0 through 126 may be referred to as leading frozen bits. Because these frozen bits do not result in any bit decisions, they may not result in any branches in a decoding tree. Any path metric associated with these frozen bits may be determined based purely on input LLRs with known feedback.

Accordingly, various polar decoding operations such as bit feedback operations, sorting, and list management may be avoided for these frozen bits. This reduction in necessary operations may be associated with a corresponding decrease in complexity and/or latency of decoding. Thus, the second set may allow the decoder to treat the first 191 bit positions305(indexed 0 through 190) as leading frozen bits. The increased number of leading frozen bits (e.g., and corresponding decrease in bits after the first information bit for which path metric calculations must be performed) may result in a decreased decoding complexity.

Although introduced in the context of leading information bit position305(e.g.,305-bor305-cin the first and second set, respectively), it is to be understood that the described techniques extend to other bit positions305in the set. For example, in some cases, the first set may be modified to include bit position305-d(index222) and exclude bit position305-c(index191). The modified first set may then have a different (higher or lower) decoding complexity than the original first set. The differences in decoding complexity may be based at least in part on a distribution of intermediate frozen bits (i.e., frozen bits after the first information bit) between the information bit positions305of the codeword. Accordingly, in this example and those that follow, frozen bits may be generally categorized as leading frozen bits or intermediate frozen bits (i.e., frozen bits having an index higher than at least one information bit).

In accordance with aspects of the present disclosure, multiple bit selection schemes may be developed and compared in order to determine an optimal information bit set for a given scenario. For example, an optimal information bit set (for a given N:K codeword) may be determined separately for mMTC, URLLC, IoT, and eMBB communication scenarios (e.g., among other communication scenarios). The example first and second set introduced above are used for the sake of explanation.

For example, a reliability weight may be applied to the aggregate reliabilities of the information bit positions of each set. Similarly, a complexity weight may be applied to the decoding complexity of the first set and the decoding complexity of the second set. The first reliability metric (e.g., determined based on applying the reliability weight to the aggregate reliabilities of the information bit positions of the first set) may be combined with the first decoding complexity metric (e.g., determined based on applying the complexity weight to the decoding complexity of the first set as a whole) to generate a first aggregate performance metric. Analogous techniques may be employed to generate a second aggregate performance metric (i.e., for the second set). The aggregate performance metrics may then be compared to determine an optimal set of the two sets for a given communication scenario. Iterative simulations may be used to perform a gradient search and determine the optimal set of information bit indices for a given scenario. That is, because of the large number of possible sets, a gradient search (or some other suitable optimization technique) may be employed to select an optimal or satisfactory set (i.e., rather than a brute force comparison of each possible set), as discussed below with reference toFIG. 9.

As an example, the scenario may be URLLC using a given N:K codeword. As mentioned above, URLLC may prioritize decoding complexity (e.g., because of the associated decrease in latency) as a performance indicator. Accordingly, for URLLC, the reliability weight and/or complexity weight may be appropriately scaled to bias the search towards sets with smaller decoding complexity metrics. Alternatively, the scenario may be eMBB communications using the same N:K codeword. As mentioned above, eMBB communications may prioritize reliability as a performance indicator. Accordingly, for eMBB communications, the reliability weight and/or complexity weight may be appropriately scaled to bias the search towards sets with larger reliability metrics.

Because comparison of weighting schemes is based at least in part on an estimate of the decoding complexity, techniques for efficient estimation of decoding complexity are described herein. These techniques may be extended to provide similar reductions in decoding complexity in practice (e.g., which may benefit a decoder with power or computational constraints), as described further below.

In some cases, the various weights themselves may be determined through iterative simulations. That is, through simulation, complexity weighting for each of the information bits given a set of parameters (e.g., N, K, L, puncturing, weighting from other schemes, etc.) can be derived. The weights may be used to form polar codeword structures that account for factors beyond a simple reliability ranking (e.g., also consider decoding complexity). Accordingly, different weights may represent different tradeoffs which may be used by encoder-decoder pairs to communicate more efficiently in different use cases.

FIG. 4illustrates an example of a polar code subtree400in accordance with various aspects of the present disclosure. Polar code subtree400may illustrate aspects of polar code structure300. For example, polar code subtree400contains a single subtree node405from a first layer (e.g., layer310-cofFIG. 3), two intermediate nodes410from a second layer (e.g., layer310-bofFIG. 3), and four leaf nodes415from a third layer (e.g., leaf layer310-aofFIG. 3). As illustrated, each leaf node415may be an information node or a frozen node.

Decoding schemes may vary across decoders (e.g., SC decoders, SCL decoders, software decoder, hardware decoders, etc.). However, the different decoding schemes may share a common set of operations. These common operations may comprise a majority of the complexity involved in the decoding operations, such that comparing the operations across different decoding schemes may provide an adequate estimate of the comparative decoding complexities.

For example, decoding operations at a SC decoder and/or SCL decoder may generally be organized into three categories: non-leaf-layer LLR derivations, leaf node operations (e.g., LLR derivations, list management, sorting, etc.), and bit feedback operations. Operations in these categories may comprise a majority of the complexity involved in successive cancellation decoding schemes. SCL decoders may in some cases include additional decoding operations. For example, in an SCL decoder, intermediate frozen bits (i.e., frozen bits that have indices larger than an information bit) may incur unequal LLRs across list members and may therefore be included in run-time computations for path metric updates. Additionally or alternatively, in an SCL decoder, since processing for each new information bit involves doubling the number of path candidates, certain list sorting by the path metrics and selection for the top L path candidates may be needed. Further, in some SCL decoders, since sorting and selection are involved in processing for each new information bit, the ordering of the list members may be properly reflected in the list as well as in the feedback bits kept in each active branch of a layer.

While these SCL-specific operations represent potential differences in decoder implementation from one decoder variation to another, the fundamental polar decoder properties organized into the three categories above may be common to SC and SCL implementations. Accordingly, in determining decoding complexity for polar code construction (e.g., to compare performance of different polar codes), capturing the nominal complexity of these primary decoding operations may be sufficient. As illustrated, for a given branch420of the polar code subtree400, LLR derivations may flow in a direction425(e.g. to determine a bit hypothesis) while bit feedback operations may flow in a direction430(e.g., to return the decoded bit hypothesis such that a subsequent LLR derivation may use the decoded bit hypothesis).

For the non-leaf layer LLR derivations, the major factor in determining decoding latency and complexity is the number of nodes over which to operate. For example, given any two consecutive indices ‘i’ and ‘i+1’ in the range of [0,K−1] for any two information bits and their locations in the range of [0, N−1], the nominal complexity for LLR derivations can be derived (e.g., assuming that all bits between the two information bits are frozen bits). The nominal complexity of this category can cover the number of F and G operations for the decoding scheme.

Bit feedback operations primarily comprise exclusive-or (XOR) operations. The number of XOR operations depends primarily on the layer of the subtree node405that covers the adjacent information nodes (e.g., leaf nodes415-band415-d). The nominal complexity of this category can cover the amount of XOR operations needed for feedback messaging.

The difference in decoding complexity for a given leaf node415across decoding variations is relatively small. For example, list management and sorting may occur at any information leaf node, regardless of the location of that information node relative to other information nodes. Accordingly, for a codeword of a given length with a given number of information bits, the variation in decoding complexity across various polar code constructions may be relatively small. It may thus be possible to ignore (e.g., or discount) the effects of leaf node operations on the estimated decoding complexity.

Each of these sets of operations may be associated with a given relative complexity. For example, bit feedback operations may be less computationally complex than non-leaf layer LLR derivations, such that an increase in the number of bit feedback operations that accompanies a corresponding decrease in the number of non-leaf layer LLR derivations may still decrease the overall complexity of the decoding operation. In some cases, a complexity weighting factor may be applied to the aggregate number of bit feedback operations and non-leaf layer LLR derivations (e.g., such that the two types of operations are treated equally). Alternatively, individual weights may be applied to each type of operation before an aggregate complexity metric is determined.

Through iterative simulations, complexity weighting for each of the information bits (e.g., given the known parameter set N, K, L) can be derived. Iterations may be used to update the resultant complexity. If higher order accuracy is needed in nominal complexity derivation, more details of operations may be considered (e.g., the SCL-specific operations discussed above). The nominal complexity derivation may adopt certain suitable decoding operation simplification schemes, as detailed below.

In order to support nominal complexity comparison of weightings from multiple schemes, various metrics may be derived and compared across multiple weighting schemes. For example, given a set of parameters (e.g., including N, K, L, and the weighting from other polar characteristics such as bit reliability), a set of metrics may be developed. Example metrics include a nominal complexity of decoding for each information bit and an effective scaling factor among multiple weighting schemes. Based on comparisons of these metrics, an update (e.g., modification) in information bit locations may be determined to find improvements in the overall weighted performance. In some cases, iterations may be used in the process of combination and modification before a stable weighting is derived on a given parameter set. In the case that a certain metric needs to be completely eliminated (i.e., ignored) from the final weighting scheme, the scaling factor for that metric may be set to zero. For example, assuming that both reliability weighting and complexity weighting are available (e.g., and only the reliability weighting needs to be considered in a target scenario), the scaling factor for complexity weighting metric may be set to zero. An iterative scheme as described herein can be seen as a generalized method to factor multiple metrics into different weighting schemes.

FIG. 5Aillustrates an example of a coder/decoder (codec) segment500-athat supports various aspects of the present disclosure. The codec segment500-amay be implemented in a receiver, such as a receiver included in a UE115or base station105described with reference toFIG. 1. For example, the codec segment500-amay be performed by the encoder/decoder210described with reference toFIG. 2. Codec segment500-aillustrates an example 2-bit decoder. Codec segment500-aillustrates operations performed to propagate LLRs through a polar codec. Because of the construction of the codec segment500-a(e.g., a SC/SCL construction), the relative capacities of the input bit-channels (with arrows drawn in the encoding direction) may be different than the output bit-channels.

The plurality of input LLRs505for codec segment500-amay be received corresponding to a plurality of interconnected bit-channels510. By way of example, codec segment500-ais shown to perform one F operation and one G operation. Each F operation may receive an operand LLR_a505-a(associated with a less significant (e.g., reliable) bit position or XOR'd bit position) and an operand LLR_b505-b(associated with a more significant bit position or non-XOR'd bit position) and obtain the output LLR515-aby performing a polar code single parity check (SPC) decoding operation (e.g., F operation):

The output LLR515-amay represent a decoded bit value (e.g., 0 or 1). Based on the sign of the LLR515-aand an expected value for the decoded bit, the codec segment500-amay assign one or more decoded bit values for the output bit-channel. For example, if the output LLR515-ais negative, the output bit-channel may be assigned a decoded bit value of 1. If the output LLR515-ais greater than or equal to 0, the output bit-channel may be assigned a decoded bit value of 0. In some cases, if the expected bit value for the output bit-channel is different from the decoded bit value corresponding to the LLR515-a, the output bit-channel may be assigned to the expected bit value and the path metric corresponding to the output bit-channel is updated based on the LLR515-a.

The assigned value for the output bit-channel may then be used as a feedback bit for a G operation. In some cases, the assigned value for the output bit-channel may be fed back to be used (e.g., in an XOR operation) to determine an output bit value for an F operation that corresponds to the G operation. Each G operation may receive operand LLR_a505-aand operand LLR_b505-band obtain the output LLR515-bby performing a polar code repetition decoding operation (e.g., G operation):

where b is equal to the determined output bit value for the corresponding F operation.

FIG. 5Billustrates an example of a codec segment500-bthat supports various aspects of the present disclosure. As with codec segment500-a, codec segment500-bmay be implemented in a receiver, such as a receiver included in a UE115or base station105as described with reference toFIG. 1. For example, the codec segment500-bmay be performed by the encoder/decoder210described with reference toFIG. 2.

Codec segment500-bcontains two LLRs520-aand520-b. Based on the LLR derivations (e.g., F operations and G operations) described with reference toFIG. 5A, bit decisions525may be determined. For example, bit decision525-amay represent the output of the F operation of the LLRs520, while bit decision525-bmay represent the output of the G operation, which takes bit decision525-aas an input.

Iteratively performing codec segment500-bover the course of a polar codeword represents one viable solution for polar decoding. However, the complexity of the decoding operation may in some cases be reduced using simplifications described herein. For example, in some cases, bit decisions525-aand525-bmay correspond to frozen bit locations (e.g., which have a value of zero). A number of LLR derivations and bit feedback operations for such a codec segment500-bmay be reduced.

Table 1 illustrates a pattern which may be exploited to simplify decoding operations. Table 1 considers a scenario in which a given subtree has rate zero (i.e., the subtree has no information bits). The example is described in terms of a 2-bit decoder, though the concept may be extended to larger subtrees. In some cases, larger subtrees may be used as long as they only contain a single information bit (e.g., as described with reference to Table 2). In the following examples, a negative LLR is assumed to generally correspond to a bit decision of 1 while a positive LLR is assumed to correspond to a bit decision of 0; the decoder may correlate larger LLR magnitudes (e.g., positive or negative) with a stronger bit hypothesis.

As illustrated in Table 1, when LLR520-a(e.g., represented in the table as ‘a’) and LLR520-b(e.g., represented in the table as ‘b’) are both non-negative, the path metric for the codec segment500-bmay be zero. That is, because both LLRs520are non-negative, they may be decoded (e.g., using F and G operations) as corresponding to zero bits. Because bit decisions525-aand525-brepresent intermediate frozen bits (e.g., which are known to have a value of zero), the LLRs520may not conflict with the frozen bits. Accordingly, the path metric (which represents the sum of the branch metrics BM0and BM1) may be zero. Because the path metric represents a penalty for a given decode path, non-negative LLRs520for a rate zero subtree may be associated with an optimal path (e.g., with no penalty).

However, as illustrated in the second condition set, a scenario may arise in which LLR520-ais non-negative while LLR520-bis negative. Accordingly, a non-zero path metric may apply. As illustrated, two sub-conditions may apply: a first in which the magnitude of LLR520-ais greater than or equal to that of LLR520-b, and a second in which the magnitude of LLR520-ais less than that of LLR520-b. As illustrated above with respect toFIG. 5A(e.g., the F-operation), BM0may be computed as the smaller of the two LLRs520. BM1may then be zero or the difference between the two LLRs520(e.g., in the case that the sign-conflicting LLR520-bis not the smaller of the two LLRs520as in the case of the second sub-condition). In either case, it is shown that the path metric (e.g., which represents the sum of the two branch metrics) has the magnitude of LLR520-b(i.e., the sign-conflicting LLR520). LLR520-bis referred to as a sign-conflicting LLR520because its negative value conflicts with the expected positive LLR value for a frozen bit.

Analogous computations may be carried out for the third and fourth conditions. In each case, the resulting path metric represents the sum of the LLR magnitudes of any sign-conflicting LLRs520. Accordingly, rather than performing LLR derivations and bit feedback operations in order to determine a path metric for a given subtree, the path metric may be more easily computed based on the input LLRs520.

The simplifications for a rate zero subtree may be extended to a subtree that contains a single information bit, as illustrated with respect to Table 2. Because of the nature of a polar code, the last bit location of a given subtree will contain the information bit (e.g., because the last bit location will be the most polarized, and therefore the most reliable bit location of the subtree). The BM1computations for Table 2 are complicated by the fact that bit decision525-bmay be a 0 or a 1. Accordingly, multiple path metrics must be calculated in order to make a decision. However, the same principles described with reference to Table 1 apply. For example, for any given condition, the path metric for a given bit decision525-brepresents the sum of any sign-conflicting LLRs525. As an example, looking at the first sub-condition of the third condition, BM0is shown to be |b| (i.e., because there is a sign-conflicting LLR value, and LLR520-bis smaller than LLR520-a). In the case that bit decision525-bis a 0, BM1is shown to be |a|−|b|. In the case that bit decision525-ais a 1, BM1is shown to be 0. In each case, a path metric is computed as the sum of BM0and BM1. The path metrics may be used in list management and sorting operations at the leaf node.

These simplifications may be generalized to larger decoding blocks. With such simplifications, the need for recursive F and G operations down to the lowest level of a tree to derive bit LLRs may be eliminated. Rather, equivalent block LLRs may be directly derived at a higher level using the sum of the absolute value of all sign-conflicting LLRs in the block.

In aspects, the terms blocks (e.g., decoding blocks) and subtree (e.g., polar code subtree400as discussed with reference toFIG. 4) may be used interchangeably. As the subtree size grows, there will be larger sets of combinations at the top of the subtree; more combinations means more hypotheses to consider, which may increase implementation difficulties. Nominal complexity for LLR derivation with the block LLR method may therefore be applicable if the subtree has a number of information bits below a certain threshold (e.g., fewer than two information bits). One reason for such a constraint is that sorting and permutations for SCL will be involved for a subtree that has more than one information bit. Resultant LLRs over the list for SCL may then have to undergo operations that may not be typical or common in SCL decoding. However, the described techniques may in some cases be extended to cover the scenario in which multiple information bits are contained within a subtree if it is deemed suitable for nominal complexity for LLR derivation. In some examples, the complexity of different operation categories may be combined with weighted sums, before being further combined with other weighting factors (e.g., reliability). The weights may be derived through simulation and further based on the selection of modeling characteristics and the targeted scenarios. As used herein, a weighted combination refers to a combination in which the aggregate weighted metrics for each of the combined metrics are equal or a combination in which the aggregate weighted metrics for different metrics are unequal (e.g., differ slightly, substantially differ, vary by orders of magnitude, have different signs).

FIG. 6illustrates an example polar tree600. Polar tree600contains four layers of nodes connected in a hierarchical fashion and may be implemented at an encoder or decoder as described above. By way of example, polar tree600contains four information bit nodes605-a,605-b,605-c,605-dand one intermediate frozen node610. Each of these nodes may represent a leaf layer node, as described above with reference toFIG. 3. Decoding of the codeword associated with polar tree600may be based in part on processing (e.g., sorting) path metrics associated with the various information bit nodes (e.g., which may represent branch points for the decoding operation).

As illustrated, information bit nodes605-aand605-bare adjacent (e.g., have adjacent indices), as are information bit nodes605-cand605-d. However, the decoding complexity of the separate pairs of information bit nodes may be significantly different (e.g., even though both pairs contain adjacent indices). Such differences illustrate the effect that the tree traversal depth has on the decoding complexity. For example, information bit nodes605-aand605-bare contained under a single intermediate node615-aat an immediately preceding layer. Accordingly, decoding of information bit node605-bmay involve a single bit feedback operation620and a single LLR derivation625. For list size L, such a decoding operation involves L bits of update and feedback and L LLR derivations.

Alternatively, information bit nodes605-cand605-dare contained under a single intermediate node615-bthat is multiple layers higher. Intermediate node615-bis illustrated as being at the top of polar tree600; however it is to be understood that polar tree600may represent a subset of the decoding tree for the entire codeword. In order to decode information bit node605-d, three bit feedback operations620may be involved, along with three LLR derivations625. For list size L, such a decoding operation involves 7*L bits of update and feedback and 7*L F or G operations for LLR derivations. In these examples, the 7 comes from the aggregated number of bits at each level (e.g., 1 bit from the leaf layer, 2 from the second layer, 4 from the third layer, etc.). Accordingly, because the tree traversal depth of the second pair of information bit nodes is greater than the tree traversal depth of the first pair of information bit nodes, the second pair of information bit nodes may be associated with a greater decoding latency (e.g., or complexity).

FIG. 7illustrates an example polar tree700. Polar tree700contains four layers of nodes connected in a hierarchical fashion and may be implemented at an encoder or decoder as described above. By way of example, polar tree700contains two information bit nodes705-aand705-b, which are separated by three intermediate frozen bits710-a,710-b,710-c. After a bit hypothesis for information bit node705-ais determined, there may be multiple feedback operations and LLR derivations associated with determining a bit hypothesis for information bit node705-b. For example, there may be three bit feedback operations720from information bit node705-ato intermediate node715-a. Each bit feedback operation720may be comprised of multiple sub-operations and each of the multiple sub-operations may include a single feedback bit.

The number of sub-operations within a given bit feedback operation720may depend on the tree traversal depth at which the bit feedback operation is performed. Accordingly, the three feedback operations720-a,720-b,720-cmay contain 1, 2, and 4 bits of feedback, respectively, such that the feedback from information bit node705-ato intermediate node715-acontains a total of 7 bits of feedback. An LLR derivation725may be performed between intermediate node715-aand intermediate node715-b. As with the bit feedback operations720, each LLR derivation725may contain multiple sub-processes in parallel depending on the tree traversal depth at which the operation is performed (e.g., such that the LLR derivation725between intermediate node715-aand intermediate node715-bmay contain four such sub-processes. Under intermediate node715-b, there may be multiple LLR derivation and feedback operations730in order to determine path metrics for the intermediate frozen bits710-a,710-b, and710-c. Additional LLR derivations725may be performed in order to determine the bit hypothesis for information bit node705-b. Such a decoding scheme may use 12*L bits of update and feedback and 12*L F or G operations for LLR derivations.

In some cases, the location of indices of information bit nodes705-a,705-bmay be determined based on a given weighting scheme, as described above. However, in order to compare weighting schemes and improve the performance of the various decoding operations, simplifications (e.g., subtree pruning) may be employed.

FIG. 8illustrates an example polar tree800, which may be an example of polar tree700. Polar tree800contains four layers of nodes connected in a hierarchical fashion and may be implemented at an encoder or decoder as described above. By way of example, polar tree800contains two information bit nodes805-aand805-b, which are separated by three intermediate frozen bits810-a,810-b,810-c.

Decoding of polar tree800may employ subtree pruning, as described with reference toFIGS. 5A and 5B. Accordingly, the nodes under pruned node815may be treated as a single LLR_block. That is, path metrics for information bit node805-bmay computed as the sum of the absolute values (i.e., magnitudes) of all sign-conflicting LLRs. Such a simplification may allow the decoding operation to use 7*L bits of update and feedback (e.g., instead of the 12*L bits of update and feedback employed for polar tree700), 4*L F or G operations for LLR derivation (e.g., instead of the 12*L F or G operations for LLR derivation employed for polar tree700), and 8*L summations for the four nodes at the pruned node815over the two hypotheses. As described above, the reduced complexity of the decoding of polar tree800may be used in practice at a decoder as well as in developing the optimal polar code for a given target scenario (e.g., in comparing different polar code constructions).

FIG. 9illustrates an example process flow900that supports nominal complexity and weighted combinations for polar code construction in accordance with various aspects of the present disclosure. The operations of process flow900may be implemented by a UE115, base station105, or device200as described herein. Additionally or alternatively, the operations of process flow900may be implemented by one or more processors (e.g., configured to simulate performance of a wireless communications system).

The number of permutations for a set of polar channel indices within a codeword may be large. As an example, a codeword may contain 256 information bits, of which 16 are allocated as information bits. In such a scenario, the number of potential information bit polar index sets (i.e., the number of groups of 16 indices in which at least one index differs between each set) is on the order of 1038. In some cases, restrictions may be implemented to reduce the number of potential sets. Regardless, comparison of performance between each different potential set of indices may be computationally rigorous. In accordance with aspects of the present disclosure, various optimization techniques may be employed to determine a satisfactory set of information bit indices.

At905, weighting factors for the relevant metrics (e.g., reliability and complexity) may be identified. In some cases, these weighting factors may be based on empirical considerations. For example, given a set of parameters N, K, and L along with a type of communication (e.g., URLLC, eMBB, etc.), a set of relevant metrics as well as weighting factors for one or more of these metrics may be determined. The weighting factors may be chosen pseudo-randomly or based on some previously determined set of weighting factors (e.g., a suitable set of weighting factors for a set of parameters having the same N and L values but different K). In some cases, the weighting factors may be selected such that only metrics within a certain range are weighted (e.g., the weighting factor may resemble a step function such that a latency for a set of information bits that is too high to be feasible or too low to enable sufficient reliability may be ignored). In some cases, the weighting factors themselves may be optimized (e.g., by maintaining a constant set of information bit indices and comparing the results of the various weighting schemes to empirical or simulated performance). However, for the sake of explanation, the process flow900shows a process for determining an information bit polar index set based on known weighting factors.

At910, an information bit set for performance testing may be determined. In some cases, the initial information bit set may be associated with the set of maximum-reliability information bit locations. Optimization of this initial information bit set may be performed in an iterative fashion (e.g., by modifying one information bit index at a time). Example optimization techniques are discussed further below.

At915, a complexity metric for the determined set of information bits may be computed. As described above, the complexity metric may apply to the codeword as a whole or in some cases may be an aggregate of complexity metrics associated with each information bit position. For example, a given information bit position may be covered by a subtree (e.g., or block) of the decoding tree. The decoding complexity of this block may be estimated using any of the techniques described above (e.g., the block LLR simplification techniques). In some cases, various decoding operations may factor into the complexity metric separately. For example, the bit feedback operations of a given subtree may be weighted by a first factor while the non-leaf layer LLR derivations of the same subtree may be weighted by a second factor different from the first. The aggregate number of weighted decoding operations may then factor into the computation of the complexity metric. Because decoding complexity may depend not only on the indices included in the information bit set, but also on the relationship between these indices, any update in the information bit set at910may involve a separate complexity metric computation at915.

At920, an aggregate metric for the set of information bits may be computed. In some cases, the aggregate metric includes a weighting factor applied to the complexity metric at915and a second weighting factor applied to an aggregate reliability metric (e.g., which may be determined based on the sum of the reliabilities of the information bit positions included in the set).

At925, a decision may be made as to whether the optimization process is complete. The decision at925may be based in part on the type of optimization process that is employed. Various optimization techniques are considered within the scope of the present application. For example, a gradient search may be employed in which the marginal improvement over a previous result influences the subsequent modified information bit set selection. In another example, a Monte Carlo tree search may be employed (e.g., in which each branch on the tree represents changing one information bit to a different index). In some cases, the gradient search or Monte Carlo tree search may be performed pseudo-randomly or with back-propagation to expand different nodes of the tree search (e.g., nodes with promising aggregate metrics).

Additionally or alternatively, branch and bound techniques for pruning the search tree may be used (e.g., minimax pruning, naïve minimax pruning, alpha-beta pruning). Further, combinatorial optimization techniques may be used such as dynamic programming to compute the optimal or near-optimal (e.g., based on maximizing the aggregate metric) selection of an information bit polar index set. In some examples, approximate programming techniques may be used to reduce computational complexity. For instance, approximations (e.g., rounding, truncating precision) in reliability, complexity, etc. may be employed to bound the solution space. In some examples, constrained optimization may be employed (e.g., such that performance is optimized with respect to some variables in the presence of constraints on other variables). The constrained variable may be, for example, a decoding complexity and/or a reliability threshold. For example, for URLLC type communications, the decoding latency may be determined by a latency metric that reflects a latency constraint for processing control information within a given time (e.g., number of symbol periods, etc.) and the process flow900may be used to find an information bit polar index set that meets the decoding latency constraint with an optimized aggregate reliability metric.

If the optimization process is not determined to be complete, the process flow may return to910. In some cases, the information bit set determined at910may be based at least in part on some feedback information930(e.g., back-propagation) in accordance with various optimization techniques. If the optimization process is determined to be complete, the optimized information bit polar index set may be identified for the given parameters (e.g., N, K, L, and weighting factors) at935.

FIG. 10shows a block diagram1000of a wireless device1005that supports nominal complexity and weighted combinations for polar code construction in accordance with aspects of the present disclosure. Wireless device1005may be an example of aspects of a UE115, base station105, or device200as described herein. Wireless device1005may include receiver1010, communications manager1015, and transmitter1020. Wireless device1005may also include a processor. Each of these components may be in communication with one another (e.g., via one or more buses).

Receiver1010may receive information such as packets, user data, or control information associated with various information channels (e.g., control channels, data channels, and information related to nominal complexity and weighted combinations for polar code construction, etc.). The receiver1010may be an example of aspects of the transceiver1335described with reference toFIG. 13. The receiver1010may utilize a single antenna or a set of antennas. Information may be passed on to other components of the device.

Communications manager1015may be an example of aspects of the communications manager1215described with reference toFIG. 12. Communications manager1015and/or at least some of its various sub-components may be implemented in hardware, software executed by a processor, firmware, or any combination thereof. If implemented in software executed by a processor, the functions of the communications manager1015and/or at least some of its various sub-components may be executed by a general-purpose processor, a digital signal processor (DSP), an application-specific integrated circuit (ASIC), an field-programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described in the present disclosure.

The communications manager1015may support encoding and/or decoding operations as described herein. For example, communications manager1015may receive a codeword encoded using a polar code, the codeword generated based on a plurality of information bits. Communications manager1015may identify a set of polar bit channel indices corresponding to the plurality of information bits, where each polar bit channel index of the set of polar bit channel indices is selected from a plurality of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric associated with the set of polar bit channel indices. Communications manager1015may decode the codeword to obtain the plurality of information bits based on the set of polar bit channel indices. Additionally or alternatively, communications manager1015may encode the set of information bits according to the polar code based on the set of polar bit channel indices to obtain a codeword.

FIG. 11shows a block diagram1100of a wireless device1105that supports nominal complexity and weighted combinations for polar code construction in accordance with aspects of the present disclosure. Wireless device1105may be an example of aspects of a wireless device1005as described with reference toFIG. 10or a UE115, base station105, or device200. Wireless device1105may include receiver1110, communications manager1115, and transmitter1120. Wireless device1105may also include a processor. Each of these components may be in communication with one another (e.g., via one or more buses).

Communications manager1115may be an example of aspects of the communications manager1215described with reference toFIG. 12. Communications manager1115may also include codeword construction component1125, decoder1130, and encoder1135.

Codeword construction component1125may identify a set of polar bit channel indices corresponding to the plurality of information bits, where each polar bit channel index of the set of polar bit channel indices is selected from a plurality of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric. In some cases, codeword construction component1125may adopt a modified provisional set of polar bit channel indices having a highest modified aggregate performance metric as the set of polar bit channel indices. In some cases, the decoding complexity metric is based on a number of LLR derivations, a number of bit feedback operations, or a combination thereof. In some cases, one or both of the number of bit feedback operations or the number of LLR derivations is based on a tree traversal depth between the each polar bit channel index and a prior polar bit channel index of the set of polar bit channel indices. In some cases, the decoding complexity metric is determined based on merging single parity check decoding operations and repetition decoding operations for a subtree of the polar code. In some cases, the subtree includes less than two of the set of polar bit channel indices and at least one frozen bit index. In some cases, the decoding complexity metric for the at least one polar bit channel index is generated based on a tree traversal depth between a polar bit channel index of the set of polar bit channel indices prior to the at least one polar bit channel index and the subtree.

Decoder1130may decode the codeword to obtain the set of information bits based on the set of polar bit channel indices. Encoder1135may encode the set of information bits according to the polar code based on the set of polar bit channel indices to obtain a codeword. In some cases, decoder1130and encoder1135may be the same component (e.g., an encoder/decoder210as described with reference toFIG. 2) or may otherwise share circuitry.

FIG. 12shows a block diagram1200of a communications manager1215that supports nominal complexity and weighted combinations for polar code construction in accordance with aspects of the present disclosure. The communications manager1215may be an example of aspects of a communications manager1015, a communications manager1115, or a communications manager1215described with reference toFIGS. 10, 11, and 12. The communications manager1215may include codeword construction component1220, decoder1225, encoder1230, codeword test component1235, performance component1240, modification component1245, and weighting component1250. Each of these modules may communicate, directly or indirectly, with one another (e.g., via one or more buses).

Codeword construction component1220may identify a set of polar bit channel indices corresponding to the plurality of information bits, where each polar bit channel index of the set of polar bit channel indices is selected from a set of polar bit channel indices of the polar code based on a reliability metric and a decoding complexity metric. In some cases, codeword construction component1220may adopt a modified provisional set of polar bit channel indices having a highest modified aggregate performance metric as the set of polar bit channel indices. In some cases, the decoding complexity metric is based on a number of LLR derivations, a number of bit feedback operations, or a combination thereof. In some cases, one or both of the number of bit feedback operations or the number of LLR derivations is based on a tree traversal depth between the each polar bit channel index and a prior polar bit channel index of the set of polar bit channel indices. In some cases, the decoding complexity metric is determined based on merging single parity check decoding operations and repetition decoding operations for a subtree of the polar code. In some cases, the subtree includes less than two of the set of polar bit channel indices and at least one frozen bit index. In some cases, the decoding complexity metric for the at least one polar bit channel index is generated based on a tree traversal depth between a polar bit channel index of the set of polar bit channel indices prior to the at least one polar bit channel index and the subtree. Decoder1225may decode the codeword to obtain the set of information bits based on the set of polar bit channel indices. Encoder1230may encode the set of information bits according to the polar code based on the set of polar bit channel indices to obtain a codeword. In some cases, decoder1225and encoder1230may be the same component (e.g., an encoder/decoder210as described with reference toFIG. 2) or may otherwise share circuitry.

Codeword test component1235may communicate with codeword construction component1220to identify the set of polar bit channel indices. In some cases, codeword test component1235may determine a provisional set of polar bit channel indices for the set of information bits based on respective reliability metrics for the set of polar bit channel indices of the polar code. Performance component1240may determine an aggregate performance metric based on the combination of the respective reliability metrics and provisional decoding complexity metrics for the provisional set of polar bit channel indices.

Modification component1245may modify at least one index of the provisional set of polar bit channel indices. Modification component1245may determine a modified aggregate performance metric based on the combination of the respective reliability metrics and modified provisional decoding complexity metrics for the modified provisional set of polar bit channel indices. Modification component1245may iteratively perform the modifying and the determining of the modified aggregate performance metric for each of a set of search branches.

Weighting component1250may communicate with codeword test component1235to identify the set of polar bit channel indices. In some cases, a combination of the respective reliability metric and the decoding complexity metric is determined by applying a first weighting factor to the respective reliability metric and applying a second weighting factor to the decoding complexity metric. In some cases, one or both of the first weighting factor or the second weighting factor is based on a type of wireless communication protocol associated with the codeword. In some cases, the type of wireless communication protocol includes one of eMBB, URLLC, IoT, or MTC. In some cases, an aggregate reliability weight for eMBB is greater than an aggregate reliability weight for URLLC and MTC, where the aggregate reliability weights are determined based on the first weighting factor applied to the respective reliability metrics. In some cases, an aggregate complexity weight for eMBB is less than an aggregate complexity weight for URLLC and MTC, where the aggregate complexity weights are determined based on the second weighting factor applied to the decoding complexity metrics.

In some cases, the operations of one or more of codeword test component1235, performance component1240, modification component1245, or weighting component1250may be performed by another device (e.g., a testing entity, a network controller, or the like), and communications manager1215may be configured (e.g., statically, dynamically) to operate according to results of the testing operations. For example, the testing entity may identify an optimal codeword structure for a given type of communication using techniques described herein, and communications manager1215may operate using the codeword structure identified by the testing entity. As an example, the testing entity may perform aspects of the operations described with reference toFIG. 15.

FIG. 13shows a diagram of a system1300including a device1305that supports nominal complexity and weighted combinations for polar code construction in accordance with aspects of the present disclosure. Device1305may be an example of or include the components of wireless device1005, wireless device1105, or a UE115, base station105, or device200as described above, e.g., with reference toFIGS. 10 and 11. Device1305may include components for bi-directional voice and data communications including components for transmitting and receiving communications, including communications manager1315, processor1320, memory1325, software1330, transceiver1335, antenna1340, and I/O controller1345. These components may be in electronic communication via one or more buses (e.g., bus1310).

Memory1325may include random access memory (RAM) and read only memory (ROM). The memory1325may store computer-readable, computer-executable software1330including instructions that, when executed, cause the processor to perform various functions described herein. In some cases, the memory1325may contain, among other things, a basic input/output system (BIOS) which may control basic hardware or software operation such as the interaction with peripheral components or devices.

I/O controller1345may manage input and output signals for device1305. I/O controller1345may also manage peripherals not integrated into device1305. In some cases, I/O controller1345may represent a physical connection or port to an external peripheral. In some cases, I/O controller1345may utilize an operating system such as iOS®, ANDROID®, MS-DOS®, MS-WINDOWS®, OS/2®, UNIX®, LINUX®, or another known operating system. In other cases, I/O controller1345may represent or interact with a modem, a keyboard, a mouse, a touchscreen, or a similar device. In some cases, I/O controller1345may be implemented as part of a processor. In some cases, a user may interact with device1305via I/O controller1345or via hardware components controlled by I/O controller1345.

FIG. 14shows a flowchart illustrating a method1400for nominal complexity and weighted combinations for polar code construction in accordance with aspects of the present disclosure. The operations of method1400may be implemented by a UE115, base station105, or device200or its components as described herein. For example, the operations of method1400may be performed by a communications manager as described with reference toFIGS. 10 through 13. In some examples, a UE115, base station105, or device200may execute a set of codes to control the functional elements of the device to perform the functions described below. Additionally or alternatively, the UE115, base station105, or device200may perform aspects of the functions described below using special-purpose hardware.

At block1405the UE115, base station105, or device200may receive a codeword encoded using a polar code, the codeword generated based at least in part on a plurality of information bits. The operations of block1405may be performed according to the methods described herein. In certain examples, aspects of the operations of block1405may be performed by a receiver as described with reference toFIGS. 10 through 13.

At block1410the UE115, base station105, or device200may identify a set of polar bit channel indices corresponding to the plurality of information bits, wherein each polar bit channel index of the set of polar bit channel indices is selected from a plurality of polar bit channel indices of the polar code based at least in part on a reliability metric and a decoding complexity metric. The operations of block1410may be performed according to the methods described herein. In certain examples, aspects of the operations of block1410may be performed by a codeword construction component as described with reference toFIGS. 10 through 13.

At block1415the UE115, base station105, or device200may decode the codeword to obtain the plurality of information bits based at least in part on the set of polar bit channel indices. The operations of block1415may be performed according to the methods described herein. In certain examples, aspects of the operations of block1415may be performed by a decoder as described with reference toFIGS. 10 through 13.

FIG. 15shows a flowchart illustrating a method1500for nominal complexity and weighted combinations for polar code construction in accordance with aspects of the present disclosure. The operations of method1500may be implemented by a UE115, base station105, or device200or its components as described herein. For example, the operations of method1500may be performed by a communications manager as described with reference toFIGS. 10 through 13. In some examples, a UE115, base station105, or device200may execute a set of codes to control the functional elements of the device to perform the functions described below. Additionally or alternatively, the UE115, base station105, or device200may perform aspects of the functions described below using special-purpose hardware.

At block1505the UE115, base station105, or device200may determine a first aggregate performance metric based at least in part on a reliability metric for a first (e.g., provisional) set of polar bit channel indices, a first decoding complexity metric for the first set of polar bit channel indices, or both. The operations of block1515may be performed according to the methods described herein. In certain examples, aspects of the operations of block1515may be performed by a performance component as described with reference toFIGS. 10 through 13.

At block1510the UE115, base station105, or device200may modify at least one index of the first set of polar bit channel indices to obtain a second set of polar bit channel indices. The operations of block1520may be performed according to the methods described herein. In certain examples, aspects of the operations of block1520may be performed by a modification component as described with reference toFIGS. 10 through 13.

At block1515the UE115, base station105, or device200may determine a second aggregate performance metric based at least in part on the combination of a second aggregate reliability metric (e.g., determined from respective reliability metrics of the second set of polar bit channel indices) and a second decoding complexity metric for the second set of polar bit channel indices. The operations of block1525may be performed according to the methods described herein. In certain examples, aspects of the operations of block1525may be performed by a modification component as described with reference toFIGS. 10 through 13.

At block1520the UE115, base station105, or device200may perform (e.g., iteratively) the modifying and the determining of the aggregate performance metric for each of a plurality of search branches. The operations of block1530may be performed according to the methods described herein. In certain examples, aspects of the operations of block1530may be performed by a modification component as described with reference toFIGS. 10 through 13.

At block1525the UE115, base station105, or device200may adopt the set of polar bit channel indices having a highest aggregate performance metric as the final set of polar bit channel indices. The operations of block1535may be performed according to the methods described herein. In certain examples, aspects of the operations of block1535may be performed by a codeword construction component as described with reference toFIGS. 10 through 13.

FIG. 16shows a flowchart illustrating a method1600for nominal complexity and weighted combinations for polar code construction in accordance with aspects of the present disclosure. The operations of method1600may be implemented by a UE115, base station105, or device200or its components as described herein. For example, the operations of method1600may be performed by a communications manager as described with reference toFIGS. 10 through 13. In some examples, a UE115, base station105, or device200may execute a set of codes to control the functional elements of the device to perform the functions described below. Additionally or alternatively, the UE115, base station105, or device200may perform aspects of the functions described below using special-purpose hardware.

At block1605the UE115, base station105, or device200may identify a set of polar bit channel indices corresponding to a plurality of information bits of an information bit vector for encoding using a polar code, wherein each polar bit channel index of the set of polar bit channel indices is selected from a plurality of polar bit channel indices of the polar code based at least in part on a reliability metric and a decoding complexity metric. The operations of block1605may be performed according to the methods described herein. In certain examples, aspects of the operations of block1605may be performed by a codeword construction component as described with reference toFIGS. 10 through 13.

At block1610the UE115, base station105, or device200may encode the plurality of information bits according to the polar code based at least in part on the set of polar bit channel indices to obtain a codeword. The operations of block1610may be performed according to the methods described herein. In certain examples, aspects of the operations of block1610may be performed by a encoder as described with reference toFIGS. 10 through 13.

At block1615the UE115, base station105, or device200may transmit the codeword. The operations of block1615may be performed according to the methods described herein. In certain examples, aspects of the operations of block1615may be performed by a transmitter as described with reference toFIGS. 10 through 13.