Patent Description:
Polar code has attracted much attention since its birth in <NUM>. It can achieve Shannon capacity with very simple encoding and decoding. In recently released 3GPP technical specification, polar coding has been adopted as channel coding for a control channel in case of enhanced mobile broadband (eMBB) service. There are two major domains of decoding schemes for polar code: Successive Cancellation (SC) based decoding and Belief Propagation (BP) based decoding.

For the SC based decoding, Successive Cancellation List (SCL) decoding was introduced which can achieve maximum likelihood (ML) bound with sufficiently large list size. For the BP based decoding, Belief Propagation List (BPL) decoding was proposed which can improve performance of the BP based decoding.

<NPL>, discloses a SCAN List decoder. The SCAN decoder is a belief propagation, BP, decoder modified to follow the scheduling a Successive Cancellation, SC, decoder. The SCAN decoder maintains a table of rightwards and leftwards messages initialized with channel values at the right-hand side and with zeroes and infinite values at the left-hand side. The messages are updated at each basic 2x2 factor graph during the BP iterations according to the simplified min-sum rule.

The present disclosure proposes an improved BP based decoding solution, which may be referred to as Belief Propagation Conflict Search List (BPCSL) decoding.

The invention concerns a method according to claim <NUM> and receivers according to claims <NUM> and <NUM>. Optional features of the invention are defined in the dependent claims <NUM> to <NUM>.

The disclosure itself, the preferable mode of use and further objectives are best understood by reference to the following detailed description of the embodiments when read in conjunction with the accompanying drawings, in which:.

As used herein, the term "communication network" refers to a network following any suitable communication standards, such as new radio (NR), long term evolution (LTE), LTE-Advanced, wideband code division multiple access (WCDMA), high-speed packet access (HSPA), and so on. Furthermore, the communications between a terminal device and a network node in the communication network may be performed according to any suitable generation communication protocols, including, but not limited to, the first generation (<NUM>), the second generation (<NUM>), <NUM>, <NUM>, the third generation (<NUM>), <NUM>, <NUM>, <NUM> communication protocols, and/or any other protocols either currently known or to be developed in the future.

The term "network node" refers to a network device in a communication network via which a terminal device accesses to the network and receives services therefrom. The network node or network device may refer to a base station (BS), an access point (AP), a multi-cell/multicast coordination entity (MCE), a controller or any other suitable device in a wireless communication network. The BS may be, for example, a node B (NodeB or NB), an evolved NodeB (eNodeB or eNB), a next generation NodeB (gNodeB or gNB), an IAB node, a remote radio unit (RRU), a radio header (RH), a remote radio head (RRH), a relay, a low power node such as a femto, a pico, and so forth.

Yet further examples of the network node comprise multi-standard radio (MSR) radio equipment such as MSR BSs, network controllers such as radio network controllers (RNCs) or base station controllers (BSCs), base transceiver stations (BTSs), transmission points, transmission nodes, positioning nodes and/or the like. More generally, however, the network node may represent any suitable device (or group of devices) capable, configured, arranged, and/or operable to enable and/or provide a terminal device access to a wireless communication network or to provide some service to a terminal device that has accessed to the wireless communication network.

The term "terminal device" refers to any end device that can access a communication network and receive services therefrom. By way of example and not limitation, the terminal device may refer to a user equipment (UE), or other suitable devices. The UE may be, for example, a subscriber station, a portable subscriber station, a mobile station (MS) or an access terminal (AT). The terminal device may include, but not limited to, portable computers, image capture terminal devices such as digital cameras, gaming terminal devices, music storage and playback appliances, a mobile phone, a cellular phone, a smart phone, a tablet, a wearable device, a personal digital assistant (PDA), a vehicle, and the like.

As yet another specific example, in an Internet of things (IoT) scenario, a terminal device may also be called an IoT device and represent a machine or other device that performs monitoring, sensing and/or measurements etc., and transmits the results of such monitoring, sensing and/or measurements etc. to another terminal device and/or a network equipment. The terminal device may in this case be a machine-to-machine (M2M) device, which may in a 3rd generation partnership project (3GPP) context be referred to as a machine-type communication (MTC) device.

As one particular example, the terminal device may be a UE implementing the 3GPP narrow band Internet of things (NB-IoT) standard. Particular examples of such machines or devices are sensors, metering devices such as power meters, industrial machinery, or home or personal appliances, e.g. refrigerators, televisions, personal wearables such as watches etc. In other scenarios, a terminal device may represent a vehicle or other equipment, for example, a medical instrument that is capable of monitoring, sensing and/or reporting etc. on its operational status or other functions associated with its operation.

As described above, the SC based decoding and the BP based decoding are main decoding schemes for polar code. The SCL decoding with Cyclic Redundancy Check (CRC) can performs better than the BP based decoding. However, the SCL decoding is to decode with serial characteristic and high complexity, which would lead to high decoding latency and reduced decoding throughput. On the other hand, the BP based decoding can be easily parallelized. Moreover, with enabled characteristic of soft-in/soft-out decoding, the BP based decoding could joint iterative detection and decoding. Therefore, the BP based decoding can satisfy requirements of low latency and high data rate. But the performance of the BP based decoding is not as good as that of the SCL decoding with CRC.

In addition, the performance of the BP based decoding may be improved with the increasing of predetermined maximum iteration times. However, for some sequences that are not able to be decoded by the BP based decoding, there are some updated iterations unnecessary that may cause higher computing consumption.

Therefore, it is desirable to provide an improved BP based decoding scheme to achieve better performance, low latency and easy parallel computing in a single decoder.

In accordance with some exemplary embodiments, the present disclosure provides improved solutions for the BP based decoding, i.e. BPCSL decoding. These solutions may be applied to a receiver in a communication network. The receiver may be implemented in a terminal device or a network node in the communication network. With the improved solutions, the receiver can implement easy parallel computing for decoding to reduce the decoding latency and improve the decoding performance, thereby reducing decoding complexity and computational power and increasing system capacity.

It is noted that some embodiments of the present disclosure are mainly described in relation to <NUM> specifications being used as non-limiting examples for certain exemplary network configurations and system deployments. As such, the description of exemplary embodiments given herein specifically refers to terminology which is directly related thereto. Such terminology is only used in the context of the presented non-limiting examples and embodiments, and does not limit the present disclosure naturally in any way. Rather, any other system configuration or radio technologies may equally be utilized as long as exemplary embodiments described herein are applicable.

<FIG> shows a communication system in which polar code is utilized. As shown in <FIG>, a source may obtain K information bits from a higher layer and transfer them to a polar encoder. The polar encoder may add frozen bits into the information bits to generate an (N, K) polar code (which is an N-bit sequence) and send the polar code to a modulator. The modulator may select a digital or analog waveform with respect to the polar code and send the waveform to a transmitter. The transmitter may convert the waveform to a signal with a specific radio frequency and power and transmit the signal. After transmitted through a wireless channel, such as an additive white Gaussian noise (AWGN) channel, the signal is captured in a receiver. The receiver may convert the signal to the waveform with proper digitalization. Then a demodulator may extract the polar code from the waveform, and generate a hard or soft value. A polar decoder may retrieve the value from the demodulator and correct errors occurring in the transmission by a decoding scheme, then transfer the estimated information bits to a destination. In most cases, the destination may use cyclic redundancy check (CRC) to check the correctness of the information bits.

<FIG> shows an example graph of <NUM>-bit polar code construction which may be implemented in the polar encoder in <FIG>. Generally the N-bit polar code construction can be constituted by several F<NUM> kemels. The F<NUM> kernel is a mapping F<NUM>: U→X such that (u<NUM>, u<NUM>)→(u<NUM> ⊕ u<NUM>, u<NUM>), where ⊕ represents an addition modulo-<NUM> or XOR operation. With this construction, for an (N, K) polar code, K bits transfer more reliably and are used to transfer information bits, and (N-K) bits transfer less reliably and are used to transfer frozen bits. Bit positions of the information bits and frozen bits in a bit sequence can be expressed by a vector I as follows: <MAT> where <NUM>≤k≤N. In <FIG>, N = <NUM> and K = <NUM>, and the vector I = [<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>] which indicates that the first to third bits and the fifth bit are frozen bits, and the remaining bits (i.e. the fourth bit and the sixth to eighth bits) are information bits. The generated (<NUM>, <NUM>) polar code may be transmitted after modulation in a signal to a receiver. In the receiver, the demodulator may demodulate the received signal and provide the demodulated information to the polar decoder for decoding. As noise exists in the transmission, the received signal may also contain the noise.

To facilitate the understanding of the embodiments of the present disclosure, the conventional BP decoding will be first described in detail. The BP decoding may involve a plurality of processing elements (PEs). The PE is shown in <FIG>. The BP decoding for an (N, K) polar code (where N = <NUM>m) is based on an m-stage factor graph, which comprise N*(m+<NUM>) nodes. As shown in <FIG>, the PE generally comprises four nodes, i.e. left-upper node (i, j<NUM>), left-lower node (i, j<NUM>), right-upper node (i+<NUM>, j<NUM>), and right-lower node (i+<NUM>, j<NUM>), where i represents a column in which the node is located in the factor graph. In <FIG>, the PE is shown in a dashed block. Each node is associated with a left-to-right message denoted as R and a right-to-left message denoted as L. The left-to-right message and the right-to-left message may be in the form of logarithmic likelihood ratio (LLR). At t-th iteration, the left-to-right message R and the right-to-left message L can be calculated as follows: <MAT> <MAT> <MAT> <MAT> where Ri+<NUM>,j<NUM> and Li+<NUM>,j<NUM> represent the left-to-right message and the right-to-left message associated with the right-upper node (i+<NUM>, j<NUM>) respectively, Ri+<NUM>,j<NUM> and Li+<NUM>,j<NUM> represent the left-to-right message and the right-to-left message associated with the right-lower node (i+<NUM>, j<NUM>) respectively, Ri,j<NUM> and Li,j<NUM> represent the left-to-right message and the right-to-left message associated with the left-upper node (i, j<NUM>) respectively, Ri,j<NUM> and Li,j<NUM> represent the left-to-right message and the right-to-left message associated with the left-lower node (i, j<NUM>) respectively, sign(·) represents a sign function to get the sign of a parameter therein, and min(·) represents a minimum function. All the right-to-left messages L associated with the nodes in the factor graph form a right-to-left table (which is also referred to as L table) with size N*(m+<NUM>), and the left-to-right messages R associated with the nodes form a left-to-right table (which is also referred to as R table) with size N*(m+<NUM>).

In the BP decoding process, firstly an initialization of the R table and L table may be performed to obtain R<NUM> table and L<NUM> table. In R<NUM> table, the left-to-right messages associated with the most-left nodes may be set based on the bit positions of the information bits and frozen bits as indicated by the vector I. For the most-left node indicating the information bit, the associated left-to-right message may be set to a first value. For the most-left node indicating the frozen bit, the associated left-to-right message may be set to a second value. In an embodiment, the first value and the second value are the LLR values calculated based on the information bit and frozen bit. Other left-to-right messages in R<NUM> table will be set to all zero. With respect to the (<NUM>, <NUM>) polar code in <FIG>, R<NUM> table may be expressed as:.

In R<NUM> table as above, the first value is calculated as <NUM> and the second value is calculated as infinite (denoted as inf.

In L<NUM> table, the right-to-left messages associated with the most-right nodes may be set to the received information. As the right-to-left messages and the left-to-right messages use the LLR values, the received information needs to be transformed to the LLR values. Generally, the transformation of the received information is based on an LLR formula as follows: <MAT> where y represents the received information, x represents a transferred bit, and L(x) represents the LLR value. Other right-to-left messages in L<NUM> table may be set to all zero. For example, with respect to the (<NUM>, <NUM>) polar code in <FIG>, L<NUM> table may be expressed as:.

Then R table and L table may be updated. In each iteration, R table may be calculated from the most-left nodes to the most-right nodes based on the above equations (<NUM>) and (<NUM>). Each time when calculating the R table, the left-to-right messages associated with the most-left nodes keep unchanged. Then L table may be calculated from the most-right nodes to the most-left nodes based on the above equations (<NUM>) and (<NUM>). Each time when calculating the L table, the right-to-left messages associated with the most-right nodes keep unchanged.

In the first iteration to calculate R<NUM> table, as all the right-to-left messages except the right-to-left messages associated with the most-right nodes are <NUM> in L<NUM> table, the above equations (<NUM>) and (<NUM>) could be simplified as: <MAT> <MAT> <FIG> shows a diagram illustrating R<NUM> table for the (<NUM>, <NUM>) polar code in <FIG>.

At the end of each iteration, the right-to-left messages associated with the most-left nodes in L table may decide the decoded information bits û. The decoded information bits û may be decided as: <MAT>.

If the decoded information bits û pass the CRC, the BP decoding will be considered as being successful, and the decoded information bits û are provided to the destination. If the decoded information bits û do not pass the CRC and the iteration times do not exceed the predetermined maximum iteration times, the BP decoding process continues the next iteration of calculating the R table and L table. If the decoded information bits û do not pass the CRC and the iteration times exceed the maximum iteration times, or if the current R and L tables are identical to the previous R and L tables respectively and no decoded information bits û pass the CRC, the BP decoding will be considered as being unsuccessful.

<FIG> is a flowchart illustrating a method <NUM> for BPCSL decoding according to some embodiments of the present disclosure. The method <NUM> illustrated in <FIG> may be performed by an apparatus implemented in or communicatively coupled to a receiver. In some embodiments, the receiver may be implemented in a terminal device or a network node. In accordance with an exemplary embodiment, the terminal device may be a UE, and the network node may be a gNB.

According to the exemplary method <NUM> illustrated in <FIG>, the receiver obtains an original right-to-left table based on received information and an original left-to-right table, as shown in block <NUM>. In some embodiments, the original left-to-right table corresponds to R<NUM> table, and the original right-to-left table corresponds to L<NUM> table. As described above, L<NUM> table may be obtained based on the above equations (<NUM>) and (<NUM>). In L<NUM> table, the right-to-left messages associated with the most-right nodes are set to the received information in the form of LLR. In some embodiments, the received information is the information obtained after demodulating a received signal for the decoding. As the received signal may contain the noise, the received information may contain a polar code and the noise. Moreover, the bit positions of the information bits and frozen bits in the polar code can be known.

In some embodiments, prior to obtaining the original right-to-left table (block <NUM>), the receiver may firstly perform the BP decoding as described above on the received information, as shown in block <NUM>. If the BP decoding is unsuccessful, the receiver performs the obtaining of the original right-to-left table.

Then, in block <NUM>, the receiver searches for a conflict verification processing element (VPE) in the plurality of PEs, based on the original left-to-right table R<NUM> and the original right-to-left table L<NUM>. In some embodiments, the conflict VPE is a kind of PE which satisfies certain conditions.

Firstly, the conflict VPE shall be a VPE. With reference to R<NUM> table as shown in <FIG>, there are three possible situations for the left-to-right messages <MAT> associated with the left-upper node (i, j<NUM>) and the left-lower node (i, j<NUM>) of the PE respectively, i.e. [inf. <NUM>], and [<NUM>, <NUM>]. Correspondingly, the left-to-right messages <MAT> and <MAT> associated with the right-upper node (i+<NUM>, j<NUM>) and the right-lower node (i+<NUM>, j<NUM>) respectively may be [inf. ], [<NUM><NUM>], and [<NUM><NUM>]. Table <NUM> shows the possible situations for the left-to-right messages <MAT> and <MAT>.

In Table <NUM>, in the situation that <MAT> is [inf. <NUM>], the sign of the right-to-left message <MAT> should be positive and the signs of the right-to-left messages <MAT> and <MAT> should be the same. Such information may be used to verify whether the PE is correct. Therefore, the PE with the left-to-right messages <MAT> as [inf. <NUM><NUM><NUM>] is defined as the VPE.

In some embodiments, the VPE may satisfy that, in R<NUM> table, the left-to-right messages associated with the most-left nodes affecting the left-to-right message <MAT> associated with the VPE's left-upper node (i, j<NUM>) indicate frozen bits and the left-to-right messages associated with the most-left nodes affecting the left-to-right message <MAT> associated with the VPE's left-lower node (i, j<NUM>) indicate frozen bits and information bits. That is, if the most-left nodes for which the left-to-right messages are used for the calculation of the left-to-right message associated with the left-upper node of the PE indicate the frozen bits only, and if the most-left nodes for which the left-to-right messages are used for the calculation of the left-to-right message associated with the left-lower node of the PE indicate both the frozen bits and the information bits, such the PE will be considered as the VPE.

Further, the conflict VPE may have a negative sign for the right-to-left message <MAT> associated with its left-upper node (i, j<NUM>) in L<NUM> table. In the VPE, the right-to-left messages <MAT> and <MAT> may be calculated as: <MAT> <MAT> Therefore, if the signs of the right-to-left messages <MAT> and <MAT> are opposite, the sign of the right-to-left messages <MAT> is to be negative. Therefore, the VPE with the negative <MAT> is defined as the conflict VPE.

In some embodiments, in the searching of the conflict VPE, the receiver may check the left-to-right messages <MAT> and <MAT> associated with the left-upper node (i, j<NUM>) and the left-lower node (i, j<NUM>) of each PE, based on R<NUM> table. If a PE satisfies that the left-to-right message <MAT> has a larger value than the left-to-right message <MAT>, this PE may be determined as the VPE. Then for the VPE, the receiver may check whether the right-to-left message <MAT> associated with the left-upper node (i, j<NUM>) has a negative sign based on L<NUM> table. If the right-to-left message <MAT> has the negative sign, the VPE may be determined as the conflict VPE. If the right-to-left message <MAT> has the positive sign, it indicates that the VPE is not the conflict VPE, and the receiver may continue to check the next VPE until find the conflict VPE. In some embodiments, the searching of the conflict VPE may be performed from the most-right PEs.

<FIG> and <FIG> illustrate an example of the obtained R<NUM> table and L<NUM> table of a (<NUM>, <NUM>) polar code, respectively. In the example, assume that the vector I of the (<NUM>, <NUM>) polar code is [<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>]. Based on the R<NUM> table with size of <NUM>*<NUM> in <FIG>, from the most-right PEs, it can be found that the left-to-right message associated with node (<NUM>, <NUM>) has a larger value than the left-to-right message associated with node (<NUM>, <NUM>), then the PE having nodes (<NUM>, <NUM>), (<NUM>, <NUM>), (<NUM>, <NUM>) and (<NUM>, <NUM>) is determined as a VPE. Then based on the L<NUM> table with size of <NUM>*<NUM> as shown in <FIG>, it can be found that the right-to-left message associated with the node (<NUM>, <NUM>) of the VPE has a negative sign, and thus this VPE is determined as a conflict VPE.

Returning to <FIG>, after the conflict VPE is found, in block <NUM>, the receiver updates the original right-to-left table L<NUM> based on the conflict VPE to obtain a plurality of potential right-to-left tables. As described above, in the conflict VPE, the signs of the right-to-left messages <MAT> and <MAT> are opposite to each other, which is not correct. Thus the right-to-left messages of the conflict VPE need to be updated to be correct. That is, the sign of the right-to-left message <MAT> should be modified to be positive, and the signs of the right-to-left messages <MAT> and <MAT> should be modified to be same, i.e. both positive or both negative. Therefore, there are two ways to update the conflict VPE. One way is to modify the sign of the right-to-left message <MAT> to be positive and modify the sign of the right-to-left message <MAT> to be same as the sign of the right-to-left message <MAT>. The other way is to modify the sign of the right-to-left message <MAT> to be positive and modify the sign of the right-to-left message <MAT> to be same as the sign of the right-to-left message <MAT>.

Therefore, in the updating of the L<NUM> table, the receiver may modify the sign of the right-to-left message <MAT> to be positive and modify the sign of the right-to-left message <MAT> to be same as the sign of the right-to-left message <MAT> in the L<NUM> table, thereby obtaining a first potential right-to-left table. Further, the receiver may also modify the sign of the right-to-left message <MAT> to be positive and modify the sign of the right-to-left message <MAT> to be same as the sign of the right-to-left message <MAT> in the L<NUM> table, thereby obtaining a second potential right-to-left table. Herein the potential right-to-left table can be regarded as L<NUM> table after updating.

With respect to the above example as shown in <FIG>, the receiver updates the conflict VPE having nodes (<NUM>, <NUM>), (<NUM>, <NUM>), (<NUM>, <NUM>) and (<NUM>, <NUM>) in two ways as described above, to obtain two potential right-to-left tables, as shown in <FIG> and <FIG> respectively. In <FIG>, the right-to-message associated with node (<NUM>,<NUM>) is modified from -<NUM> to <NUM>, and the right-to-left message associated with node (<NUM>, <NUM>) is modified from <NUM> to -<NUM>, and thus the signs of the right-to-left messages associated with node (<NUM>, <NUM>) and node (<NUM>, <NUM>) are both negative. In <FIG>, the right-to-message associated with node (<NUM>,<NUM>) is modified from -<NUM> to <NUM>, and the right-to-left message associated with node (<NUM>, <NUM>) is modified from -<NUM> to <NUM>, and thus the signs of the right-to-left messages associated with node (<NUM>, <NUM>) and node (<NUM>, <NUM>) are both positive.

Then in block <NUM>, the receiver performs the BP decoding based on the respective one of the plurality of potential right-to-left tables. When performing the BP decoding, the receiver may utilize each potential right-to-left table as L<NUM> table to calculate R<NUM> table, and then calculate L<NUM> table. Then the decoded information bits û may be decided from L<NUM> table. If the decoded information bits û pass the CRC, it indicates that the BP decoding is successful. If the decoded information bits û do not pass the CRC and iteration times do not exceed the maximum iteration time, the receiver may continue to perform the BP decoding. If the decoded information bits û do not pass the CRC and the iteration times exceed the maximum iteration time, or if the current L table is same as the previous L table and no decoded information bits û pass the CRC, the BP decoding will be considered as being unsuccessful.

<FIG> shows a flowchart of the method <NUM> for BPCSL decoding performed by the receiver according to some embodiments of the present disclosure. In the method <NUM>, the blocks <NUM>, <NUM>, <NUM>, <NUM> and <NUM> are same as the blocks <NUM>, <NUM>, <NUM>, <NUM> and <NUM>.

According to the exemplary method <NUM> illustrated in <FIG>, if no BP decoding based on the respective potential right-to-left tables is successful at block <NUM>, the receiver searches each of the potential right-to-left table for a conflict PE or a new conflict VPE, as shown in block <NUM>. As the sign of the right-to-left message <MAT> or <MAT> of the conflict VPE is modified, it would affect the right-to-left messages for the PE(s) which is connected at the right of the conflict VPE, that is, the sign of the right-to-left message <MAT> or <MAT> of such the PE is changed. Herein the conflict PE is defined as a PE which is connected leftwards to the conflict VPE and has the right-to-left message associated with the left-upper node or the left-lower node changed. In some embodiments, the new conflict VPE may be searched for only when no conflict PE is found.

Then in block <NUM>, the receiver updates each potential right-to-left table based on the respective conflict PE or the new conflict VPE. In some embodiments, in the updating of the potential right-to-left table based on the conflict PE, the receiver may check whether the right-to-left message associated with the conflict PE's left-upper node or the right-to-left message associated with the conflict PE's left-lower node is changed. If the right-to-left message associated with the conflict PE's left-upper node is changed, the receiver may modify the sign of the right-to-left message associated with the right-upper node in the potential right-to-left table, based on the sign of the right-to-left message associated with the left-upper node and the sign of the right-to-left message associated with the right-lower node, to obtain the updated potential right-to-left table. In some embodiments, if the sign of the right-to-left message associated with the left-upper node is negative, the sign of the right-to-left message associated with the right-upper node will be modified to be opposite to the sign of the right-to-left message associated with the right-lower node. If the sign of the right-to-left message associated with the left-upper node is positive, the sign of the right-to-left message associated with the right-upper node will be modified to be same as the sign of the right-to-left message associated with the right-lower node. On the other hand, the receiver may modify the sign of the right-to-left message associated with the right-lower node in the potential right-to-left table, based on the sign of the right-to-left message associated with the left-upper node and the sign of the right-to-left message associated with the right-upper node, to obtain another updated right-to-left table. If the right-to-left message associated with the conflict PE's left-lower node is changed, the receiver may modify the sign of the right-to-left message associated with the right-lower node to be same as the sign of the right-to-left message associated with the left-lower node in the potential right-to-left table. Therefore, for each potential right-to-left table, one or two updated potential right-to-left table can be obtained after the updating.

Referring to the potential right-to-left table as shown in <FIG>, the PE having nodes (<NUM>, <NUM>), (<NUM>, <NUM>), (<NUM>, <NUM>) and (<NUM>, <NUM>) is searched for as the conflict PE, and the sign of the right-to-left message associated with node (<NUM>, <NUM>) (which is the left-upper node of the conflict PE) is changed. Then the right-to-left message associated with node (<NUM>, <NUM>) can be modified to obtain one updated potential right-to-left table as shown in <FIG>. Also, the right-to-left message associated with node (<NUM>, <NUM>) can be modified to obtain another updated potential right-to-left table as shown in <FIG>. In <FIG>, since the sign of the right-to-left message associated with node (<NUM>, <NUM>) is negative and the sign of the right-to-left message associated with node (<NUM>, <NUM>) is negative, the right-to-left message associated with node (<NUM>, <NUM>) is modified from -<NUM> to <NUM>. In <FIG>, since the sign of the right-to-left message associated with node (<NUM>, <NUM>) is negative and the sign of the right-to-left message associated with node (<NUM>, <NUM>) is negative, the right-to-left message associated with node (<NUM>, <NUM>) is modified from -<NUM> to <NUM>.

Referring to the potential right-to-left table as shown in <FIG>, the PE having nodes (<NUM>, <NUM>), (<NUM>, <NUM>), (<NUM>, <NUM>) and (<NUM>, <NUM>) is searched for as the conflict PE, and the sign of the right-to-left message associated with node (<NUM>, <NUM>) (which is the left-upper node of the conflict PE) is changed. Then the right-to-left message associated with node (<NUM>, <NUM>) can be modified to obtain one updated potential right-to-left table as shown in <FIG>. Also, the right-to-left message associated with node (<NUM>, <NUM>) can be modified to obtain another updated potential right-to-left table as shown in <FIG>. In <FIG>, since the sign of the right-to-left message associated with node (<NUM>, <NUM>) is positive and the sign of the right-to-left message associated with node (<NUM>, <NUM>) is positive, the right-to-left message associated with node (<NUM>, <NUM>) is modified from -<NUM> to <NUM>. In <FIG>, since the sign of the right-to-left message associated with node (<NUM>, <NUM>) is positive and the sign of the right-to-left message associated with node (<NUM>, <NUM>) is negative, the right-to-left message associated with node (<NUM>, <NUM>) is modified from <NUM> to -<NUM>.

After updating each potential right-to-left table in block <NUM>, the method proceeds to block <NUM>, in which the receiver may perform the BP decoding based on the respective updated potential right-to-left tables. In the BP decoding, the receiver may utilize each updated potential right-to-left table as L<NUM> table to perform the BP decoding. If the BP decoding based on any updated potential right-to-left table is successful, the BPCSL decoding ends. If no BP decoding based on the respective updated potential right-to-left table is successful, the method proceeds to block <NUM> in which the receiver searches each of the updated potential right-to-left table for a further conflict PE or a new conflict VPE. In some embodiments, the further conflict PE may be connected left-towards to the previously found conflict PE and has the right-to-left message associated with the left-upper node or the left-lower node changed. After the further conflict PE or the new conflict VPE is found, the receiver may repeat the operations in block <NUM> and <NUM>.

For example, if the BP decoding based on each of the updated potential right-to-left tables as shown in <FIG>, <FIG>, <FIG> and <FIG> is not successful, the receiver may search for the new conflict PE or conflict VPE in these potential right-to-left tables. Take <FIG> as an example, as no more conflict PE is found, the receiver may search for another conflict VPE. According to R<NUM> table as shown in <FIG> and the potential right-to-left table as shown in <FIG>, another conflict VPE can be found, which has nodes (<NUM>, <NUM>), (<NUM>, <NUM>), (<NUM>, <NUM>) and (<NUM>, <NUM>). Then the right-to-left messages for the conflict VPE can be modified to obtain new potential right-to-left tables as shown in <FIG> and <FIG> respectively. In <FIG>, the right-to-left message associated with node (<NUM>, <NUM>) is modified from -<NUM> to <NUM>, and the right-to-left message associated with node (<NUM>, <NUM>) is modified from <NUM> to -<NUM>. In <FIG>, the right-to-left message associated with node (<NUM>, <NUM>) is modified from -<NUM> to <NUM>, and the right-to-left message associated with node (<NUM>, <NUM>) is modified from -<NUM> to <NUM>. Then the receiver may utilize each of the potential right-to-left tables as shown in <FIG> and <FIG> as L<NUM> table to perform the BP decoding.

According to the above described embodiments, with the updating of the right-to-left table, an amount of the potential right-to-left table will significantly increase, and it will take more and more time to perform the BP decoding based on each potential right-to-left table. In order to improve the decoding efficiency, a maximum number for the potential right-to-left tables is predetermined. In some embodiments, if no BP decoding based on the respective potential right-to-left table is successful, prior to searching for the conflict PE or new conflict VPE in these potential right-to-left tables, the receiver may determine an amount N of these potential right-to-left tables which were used for the BP decoding, and further determine whether the amount N is greater than the predetermined maximum number. If not, the receiver may perform the subsequent searching of the conflict PE or conflict VPE on all the potential right-to-left tables. If the amount is greater than the predetermined maximum amount, the receiver may calculate a power metric for each BP decoding which was performed based on the respective potential right-to-left table. The power metric may be used to evaluate the performance of the BP decoding. The smaller the power metric is, the better the performance of the BP decoding is. In some embodiments, the power metric may be calculated based on the last right-to-left table during the BP decoding. For example, the power metric may be calculated as: <MAT> where PM(l) represents the power metric for the lth BP decoding, l is in a range from <NUM> to <NUM>*N and comprising <NUM> and <NUM>*N, N_frozen represents a total number of the most-left nodes indicating the frozen bit, llrk_frozen(l) represents the right-to-left message associated with the k_frozenth most-left node which indicates the frozen bit in the form of logarithmic likelihood ratio, LLR, in the last right-to-left table during the BP decoding, and ln(·) represents a logarithmic function with base e. After calculating the power metric for each BP decoding, the predetermined maximum number of the potential right-to-left tables corresponding to the smaller power metrics may be retained for the subsequent searching.

In order to illustrate the updating of the right-to-left table or the potential right-to-left table(s) more intuitively, a searching tree may be used. <FIG> shows an example searching tree which reflects the updating of the potential right-to-left table from <FIG> and <FIG>, and from <FIG> and <FIG> to <FIG>, <FIG>, <FIG> and <FIG> respectively, in which the maximum number is preset to <NUM>. In <FIG>, the root node at the first level of the searching tree may represent a conflict VPE, such as the conflict VPE having nodes (<NUM>, <NUM>), (<NUM>, <NUM>), (<NUM>, <NUM>) and (<NUM>, <NUM>). As there are two ways to update the conflict VPE, there are two branches extended from the root node to leaf nodes at the second level. The leaf node may represent a conflict PE or another conflict VPE, such as the conflict PE having nodes (<NUM>, <NUM>), (<NUM>, <NUM>), (<NUM>, <NUM>) and (<NUM>, <NUM>) in <FIG> and the conflict PE having nodes (<NUM>, <NUM>), (<NUM>, <NUM>), (<NUM>, <NUM>) and (<NUM>, <NUM>) in <FIG>. RT represents the case where the right-to-left message associated with the right-upper node is updated, RB represents the case where the right-to-left message associated with the right-lower node is updated. As the right-to-left messages associated with the left-upper nodes of the two conflict PEs are changed, there are also two ways to update the conflict PEs. Therefore, there are two branches extended from each leaf node at the second level, which corresponds to <FIG>, <FIG>, <FIG> and <FIG>. If the right-to-left message associated with the left-lower node of the conflict PE is changed, there is only one way to update and such a case will be represented by NS in the search tree. NS also represents the case where no new conflict VPE is found. In the searching tree, a path from the root node to any leaf-node can reflect an updating process of the potential right-to-left table, and thus there is the power metric of the BP decoding for each path. If there are <NUM> paths terminated at a certain level, that is, the amount of the potential right-to-left tables for performing the BP decoding is <NUM> which exceeds the maximum number, the power metric can be calculated for each BP decoding based on the respective one of the <NUM> potential right-to-left tables. Only <NUM> paths with the smaller power metric can be retained for the subsequent updating, and other <NUM> paths with higher power metric would be removed.

In the above described embodiments, it is described that the potential right-to-left table is obtained by updating the conflict VPE only for the original right-to-left table. In some other embodiments, the potential right-to-left table may be obtained by updating the conflict VPE and the conflict PE which is connected leftwards to the conflict VPE for the original right-to-left table. In such the embodiments, after the conflict VPE is found, the receiver may modify the sign of the right-to-left message associated with the conflict VPE's left-upper node to be positive and the sign of the right-to-left message associated with its right-upper node to be the same as the sign of the right-to-left message associated with its right-lower node in the original right-to-left table, to obtain a first intermediate right-to-left table. On the other hand, the receiver may the sign of the right-to-left message associated with the conflict VPE's left-upper node to be positive and the sign of the right-to-left message associated with its right-lower node to be the same as the sign of the right-to-left message associated with its right-upper node in the original right-to-left table, to obtain a second intermediate right-to-left table. Then the receiver may search each of the first intermediate right-to-left table and the second intermediate right-to-left table for the conflict PE. After the conflict PE is found for each of the first and second intermediate right-to-left table, the receiver may check whether the right-to-left message associated with the left-upper node or the left-lower node of the conflict PE is changed. If the right-to-left message associated with the left-upper node is changed, the receiver may modify the sign of the right-to-left message associated with its right-upper node based on the sign of the right-to-left message associated with its left-upper node and the sign of the right-to-left message associated with its right-lower node in the respective intermediate right-to-left table, to obtain the respective potential right-to-left tables. Moreover, the receiver may modify the sign of the right-to-left message associated with its right-lower node based on the sign of the right-to-left message associated with its left-upper node and the sign of the right-to-left message associated with its right-upper node in each of the first and second intermediate right-to-left table, to obtain further respective potential right-to-left tables. If the right-to-left message associated with the left-lower node is changed, the receiver may modify the sign of the right-to-left message associated with its right-lower node to be same as the sign of the right-to-left message associated with its left-lower node in the respective intermediate right-to-left table, to obtain the potential right-to-left table.

It can be seen from the above embodiments of the present disclosure, with the BPCSL decoding, the decoding performance can be improved as all the possible updating ways for the right-to-left table are considered. Moreover, the BPCSL decoding can realize parallel hardware implementation easily to reduce the decoding latency.

Please note that the order for performing the steps as shown in <FIG> and <FIG> is illustrated only as an example. In some implementation, some steps may be performed in a reverse order or in parallel. In some other implementation, some steps may be omitted or combined.

The various blocks shown in <FIG> and <FIG> may be viewed as method steps, and/or as operations that result from operation of computer program code, and/or as a plurality of coupled logic circuit elements constructed to carry out the associated function(s). The schematic flow chart diagrams described above are generally set forth as logical flow chart diagrams. As such, the depicted order and labeled steps are indicative of specific embodiments of the presented methods. Other steps and methods may be conceived that are equivalent in function, logic, or effect to one or more steps, or portions thereof, of the illustrated methods. Additionally, the order in which a particular method occurs may or may not strictly adhere to the order of the corresponding steps shown.

<FIG> illustrate simulation results of block error rate (BLER) for decoding <NUM> bit sequence and <NUM> bit sequence, respectively, using the conventional BP decoding (denoted as "BP") and the BPCSL decoding (denoted as "BPCSL", with N = <NUM>, <NUM>) according to the embodiments of the present disclosure. It can be seen that, with respect to BLER, the BPCSL decoding performs much better than the conventional BP decoding. Moreover, with the larger N, the performance of the BPCSL decoding is better.

<FIG> is a block diagram illustrating an apparatus <NUM> according to various embodiments of the present disclosure. As shown in <FIG>, the apparatus <NUM> may comprise one or more processors such as processor <NUM> and one or more memories such as memory <NUM> storing computer program codes <NUM>. The memory <NUM> may be non-transitory machine/processor/computer readable storage medium. In accordance with some exemplary embodiments, the apparatus <NUM> may be implemented as an integrated circuit chip or module that can be plugged or installed into the receiver as described with respect to <FIG> and <FIG>.

In some implementations, the one or more memories <NUM> and the computer program codes <NUM> may be configured to, with the one or more processors <NUM>, cause the apparatus <NUM> at least to perform any operation of the method as described in connection with <FIG> and <FIG>. In such embodiments, the apparatus <NUM> may be implemented as at least part of or communicatively coupled to the receiver as described above. As a particular example, the apparatus <NUM> may be implemented as a receiver.

Alternatively or additionally, the one or more memories <NUM> and the computer program codes <NUM> may be configured to, with the one or more processors <NUM>, cause the apparatus <NUM> at least to perform more or less operations to implement the proposed methods according to the exemplary embodiments of the present disclosure.

<FIG> is a block diagram illustrating an apparatus <NUM> according to some embodiments of the present disclosure. As shown in <FIG>, the apparatus <NUM> may comprise a BP decoder <NUM> and a BP conflict search list circuitry <NUM>. In an exemplary embodiment, the apparatus <NUM> may be implemented in a receiver. The receiver may be implemented in a terminal device such as UE or a network node such as gNB. The BP decoder <NUM> may be configured to carry out the operations in blocks <NUM> and <NUM> or the operations in blocks <NUM> and <NUM>. The BP conflict search list circuitry <NUM> may be configured to carry out the operations in blocks <NUM>, <NUM> and <NUM> or the operations in blocks <NUM>, <NUM>, <NUM>, <NUM> and <NUM>. Optionally, the BP decoder <NUM> and/or the BP conflict search list circuitry <NUM> may be configured to carry out more or less operations to implement the proposed methods according to the exemplary embodiments of the present disclosure.

<FIG> is a block diagram illustrating a telecommunication network connected via an intermediate network to a host computer in accordance with some embodiments of the present disclosure.

With reference to <FIG>, in accordance with an embodiment, a communication system includes a telecommunication network <NUM>, such as a 3GPP-type cellular network, which comprises an access network <NUM>, such as a radio access network, and a core network <NUM>. The access network <NUM> comprises a plurality of base stations 812a, 812b, 812c, such as NBs, eNBs, gNBs or other types of wireless access points, each defining a corresponding coverage area 813a, 813b, 813c. Each base station 812a, 812b, 812c is connectable to the core network <NUM> over a wired or wireless connection <NUM>. A first UE <NUM> located in a coverage area 813c is configured to wirelessly connect to, or be paged by, the corresponding base station 812c. A second UE <NUM> in a coverage area 813a is wirelessly connectable to the corresponding base station 812a.

An intermediate network <NUM> may be one of, or a combination of more than one of, a public, private or hosted network; the intermediate network <NUM>, if any, may be a backbone network or the Internet; in particular, the intermediate network <NUM> may comprise two or more sub-networks (not shown).

<FIG> is a block diagram illustrating a host computer communicating via a base station with a UE over a partially wireless connection in accordance with some embodiments of the present disclosure.

The host computer <NUM> further comprises a processing circuitry <NUM>, which may have storage and/or processing capabilities. The host application <NUM> may be operable to provide a service to a remote user, such as UE <NUM> connecting via an OTT connection <NUM> terminating at the UE <NUM> and the host computer <NUM>.

In the embodiment shown, the hardware <NUM> of the base station <NUM> further includes a processing circuitry <NUM>, which may comprise one or more programmable processors, application-specific integrated circuits, field programmable gate arrays or combinations of these (not shown) adapted to execute instructions.

The hardware <NUM> of the UE <NUM> further includes a processing circuitry <NUM>, which may comprise one or more programmable processors, application-specific integrated circuits, field programmable gate arrays or combinations of these (not shown) adapted to execute instructions.

It is noted that the host computer <NUM>, the base station <NUM> and the UE <NUM> illustrated in <FIG> may be similar or identical to the host computer <NUM>, one of base stations 812a, 812b, 812c and one of UEs <NUM>, <NUM> of <FIG>, respectively.

In <FIG>, the OTT connection <NUM> has been drawn abstractly to illustrate the communication between the host computer <NUM> and the UE <NUM> via the base station <NUM>, without explicit reference to any intermediary devices and the precise routing of messages via these devices.

Wireless connection <NUM> between the UE <NUM> and the base station <NUM> is in accordance with the teachings of the embodiments described throughout this disclosure. One or more of the various embodiments improve the performance of OTT services provided to the UE <NUM> using the OTT connection <NUM>, in which the wireless connection <NUM> forms the last segment. More precisely, the teachings of these embodiments may improve the latency and the power consumption, and thereby provide benefits such as lower complexity, reduced time required to access a cell, better responsiveness, extended battery lifetime, etc..

The measurement procedure and/or the network functionality for reconfiguring the OTT connection <NUM> may be implemented in software <NUM> and hardware <NUM> of the host computer <NUM> or in software <NUM> and hardware <NUM> of the UE <NUM>, or both. In embodiments, sensors (not shown) may be deployed in or in association with communication devices through which the OTT connection <NUM> passes; the sensors may participate in the measurement procedure by supplying values of the monitored quantities exemplified above, or supplying values of other physical quantities from which the software <NUM>, <NUM> may compute or estimate the monitored quantities. In certain embodiments, measurements may involve proprietary UE signaling facilitating the host computer <NUM>'s measurements of throughput, propagation times, latency and the like. The measurements may be implemented in that the software <NUM> and <NUM> causes messages to be transmitted, in particular empty or 'dummy' messages, using the OTT connection <NUM> while it monitors propagation times, errors etc..

<FIG> is a flowchart illustrating a method implemented in a communication system, in accordance with an embodiment.

<FIG> is a flowchart illustrating a method implemented in a communication system, in accordance with an embodiment.

<FIG> is a flowchart illustrating a method implemented in a communication system, in accordance with an embodiment.

<FIG> is a flowchart illustrating a method implemented in a communication system, in accordance with an embodiment.

In general, the various exemplary embodiments may be implemented in hardware or special purpose chips, circuits, software, logic or any combination thereof.

It should be appreciated that at least some aspects of the exemplary embodiments of the disclosure may be embodied in computer-executable instructions, such as in one or more program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types when executed by a processor in a computer or other device. The computer executable instructions may be stored on a computer readable medium such as a hard disk, optical disk, removable storage media, solid state memory, random access memory (RAM), etc. As will be appreciated by one of skill in the art, the function of the program modules may be combined or distributed as desired in various embodiments. In addition, the function may be embodied in whole or partly in firmware or hardware equivalents such as integrated circuits, field programmable gate arrays (FPGA), and the like.

Claim 1:
A method (<NUM>, <NUM>) for polar decoding performed by a receiver, comprising:
obtaining (<NUM>, <NUM>), based on received information and an original left-to-right table comprising left-to-right messages associated with nodes of a plurality of processing elements, PEs, for BP decoding, an original right-to-left table comprising right-to-left messages associated with the nodes, wherein each of the plurality of PEs comprise four nodes which are a left-upper node, a left-lower node a right-upper node and a right-lower node located in two successive columns in the factor graph of the polar code;
wherein the method is characterized in further comprising:
searching (<NUM>, <NUM>) for, based on the original left-to-right table and the original right-to-left table, a conflict verification processing element, VPE, in the plurality of PEs, the conflict VPE being a VPE for which the left-to-right messages associated with the most-left nodes of the VPE affecting the left-to-right message associated with its left-upper node indicate a frozen bit and the left-to-right messages associated with the most-left nodes of the VPE affecting the left-to-right message associated with its left-lower node indicate a frozen bit or an information bit, and having a negative sign for the right-to-left message associated with its left-upper node;
updating (<NUM>, <NUM>) the original right-to-left table based on the conflict VPE to obtain a plurality of potential right-to-left tables; and
performing (<NUM>, <NUM>) the BP decoding based on the respective one of the plurality of potential right-to-left tables.