In successive cancellation (SC) polar decoding, an incorrect estimate of any prior unfrozen bit may bring about severe error propagation in the following decoding, thus it is desirable to find out and correct an error as early as possible. In this paper, we first construct a critical set S of unfrozen bits, which with high probability (typically >99%) includes the bit where the first error happens. Then we develop a progressive multi- level bit-flipping decoding algorithm to correct multiple errors over the multiple-layer critical sets each of which is constructed using the remaining undecoded subtree associated with the previous layer. The level in fact indicates the number of independent errors that could be corrected. We show that as the level increases, the block error rate (BLER) performance of the proposed progressive bit flipping decoder competes with the corresponding cyclic redundancy check (CRC) aided successive cancellation list (CA-SCL) decoder, e.g., a level 4 progressive bit-flipping decoder is comparable to the CA-SCL decoder with a list size of L=32. Furthermore, the average complexity of the proposed algorithm is much lower than that of a SCL decoder (and is similar to that of SC decoding) at medium to high signal to noise ratio (SNR).

This paper focuses on low complexity successive cancellation list (SCL) decoding of polar codes. In particular, using the fact that splitting may be unnecessary when the reliability of decoding the unfrozen bit is sufficiently high, a novel splitting rule is proposed. Based on this rule, it is conjectured that, if the correct path survives at some stage, it tends to survive till termination without splitting with high probability. On the other hand, the incorrect paths are more likely to split at the following stages. Motivated by these observations, a simple counter that counts the successive number of stages without splitting is introduced for each decoding path to facilitate the identification of correct and incorrect paths. Specifically, any path with counter value larger than a predefined threshold ω is deemed to be the correct path, which will survive at the decoding stage, while other paths with counter value smaller than the threshold will be pruned, thereby reducing the decoding complexity. Furthermore, it is proved that there exists a unique unfrozen bit uN-K1+1, after which the successive cancellation decoder achieves the same error performance as the maximum likelihood decoder if all the prior unfrozen bits are correctly decoded, which enables further complexity reduction. Simulation results demonstrate that the proposed low complexity SCL decoder attains performance similar to that of the conventional SCL decoder, while achieving substantial complexity reduction.

In the future Internet of Things (IoT), a multitude of objects are to be provided with always-on-line connections and dynamic access to the network services, which brings new challenges to multiple access protocol design. In this paper, a novel multiple access protocol, termed as "multi-carrier rateless multiple access (MC-RMA)'', is proposed to overcome such challenges. Instead of assigning the available resource elements (REs) to the users in a fixed and centralized manner, the base station (BS) simply assigns a specific distribution profile to each user, with which each user randomly chooses a certain number of coded symbols, linearly combines them, and then transmits the resultant signal to BS until receiving an acknowledgement (ACK) from BS. The transmission process of each user, as well as those of all the users as a whole, resembles a special form of linear superposition rateless coding and the user information can be decoded using the low-complexity belief propagation (BP) algorithm. Due to the inherent rate adaptation property of rateless codes, the proposed RMA protocol is quite suitable for dynamic massive access in future IoT.

The distribution of information bits and frozen bits on the decoder graph can be exploited to simplify the successive‐cancellation (SC) decoding of polar codes. In this study, the authors establish a general simplified SC decoding framework for polar codes with arbitrary block‐length, which is independent of any specific or explicit generator matrices and considerably reduces decoding complexity while retaining the same error performance. Then, based on the fact that the complexity reduction depends on the distribution of information bits, a so‐called m ‐radius reselection scheme is proposed to construct multiple feasible information sets which are different from the original one defined by Arıkan. In this way, flexible tradeoffs between performance and complexity could be achieved.

Some multilevel codes which are constructed based on polar codes have been introduced recently, and show good performance with elaborately designed rates at each level and special multistage decoder. However, the multistage decoding is usually implemented in a sequential manner, which might yield poor performance at lower levels since the corresponding component codes are decoded without any information from higher levels, and the decoding errors occurred at previous stages could hardly be corrected. Thus, an iterative multistage decoding algorithm for polar code based multilevel codes is introduced in this paper, which could further improve the performance by feeding the reliable information obtained at higher levels back to the first level, and correct the decoding errors occurred at lower levels. Our proposed algorithm has only moderate complexity, and it is found that, the first iteration contributes the most performance improvement.

Puncturing is widely used to generate rate-compatible codes. However, for punctured polar codes, some puncturing patterns may greatly affect the split bit channels and cause considerable performance loss. In this paper, we aim to investigate how the split bit channels are affected by various puncturing patterns, and then evaluate the performances of these patterns. We propose a search algorithm to design good punctured polar codes, and prove that designing the optimal puncturing pattern for output bits is equivalent to finding the optimal puncturing pattern for frozen bits. We also propose a heuristic approach based on the idea of polarization to select the position of each punctured output bit, and simulations show that the puncturing pattern designed this way almost achieves the same performance as the optimal one selected by exhaustive search.

Polar codes can achieve symmetric capacity of a channel with a simple encoder and a successive cancellation (SC) decoder, both with complexity of the order of O(N log N). Polar codes of length N = lnmay have a faster polarization rate compared to polar codes of length N = 2n. In this paper, we introduce a simple and explicit method to obtain the recursive formulas of SC decoder for any polar code of length ln, which helps us better understand the essence of SC decoding. Based on this, we give a complete proof that the simplified SC decoding introduced in previous works can also be applicable for polar codes of all kinds of kernels.

A novel belief propagation algorithm with gradual edge removal (ERBP) is proposed for Raptor codes over additional white gaussian noise (AWGN) channel. Specifically, the variable nodes with sufficiently high confidence and the corresponding edges are removed gradually from the Tanner graph during the BP iterations so as to reduce the decoding complexity. Then considering the intrinsic nature of incremental redundancy of Raptor codes, we extend the ERBP algorithm into a progressive manner, i.e., the so-called PERBP algorithm, which not only conducts edge removal operation but also makes use of the decoding states from the previous decoding attempts. Simulation results show that compared with the conventional BP algorithm, both ERBP and PERBP algorithms provide drastically reduced decoding complexity without much loss of coding performance.