While constructing polar codes for successive-cancellation decoding can be implemented efficiently by sorting the bit channels, finding optimal polar codes for cyclic-redundancy-check-aided successive-cancellation list (CA-SCL) decoding in an efficient and scalable manner still awaits investigation. This paper first maps a polar code to a unique heterogeneous graph called the polar-code-construction message-passing (PCCMP) graph. Next, a heterogeneous graph-neural-network-based iterative message-passing (IMP) algorithm is proposed which aims to find a PCCMP graph that corresponds to the polar code with minimum frame error rate under CA-SCL decoding. This new IMP algorithm’s major advantage lies in its scalability power. That is, the model complexity is independent of the blocklength and code rate, and a trained IMP model over a short polar code can be readily applied to a long polar code’s construction. Numerical experiments show that IMP-based polar-code constructions outperform classical constructions under CA-SCL decoding. In addition, when an IMP model trained on a length-128 polar code directly applies to the construction of polar codes with different code rates and blocklengths, simulations show that these polar-code constructions deliver comparable performance to the 5G polar codes.

A novel recursive list decoding (RLD) algorithm for Reed-Muller (RM) codes based on successive permutations (SP) of the codeword is presented. A low-complexity SP scheme applied to a subset of the symmetry group of RM codes is first proposed to carefully select a good codeword permutation on the fly. Then, the proposed SP technique is integrated into an improved RLD algorithm that initializes different decoding paths with random codeword permutations, which are sampled from the full symmetry group of RM codes. Finally, efficient latency and complexity reduction schemes are introduced that virtually preserve the error-correction performance of the proposed decoder. Simulation results demonstrate that at the target frame error rate of 10−3 for the RM code of length 256 with 163 information bits, the proposed decoder reduces 6% of the computational complexity and 22% of the decoding latency of the state-of-the-art semi-parallel simplified successive-cancellation decoder with fast Hadamard transform (SSC-FHT) that uses 96 permutations from the full symmetry group of RM codes, while relatively maintaining the error-correction performance and memory consumption of the semi-parallel permuted SSC-FHT decoder.

This paper formulates the polar-code construction problem for the successive-cancellation list (SCL) decoder as a maze-traversing game, which can be solved by reinforcement-learning techniques. The proposed method provides a novel technique for polar-code construction that no longer depends on sorting and selecting bit-channels by reliability, as in most current algorithms. Instead, this technique decides whether the input bits should be frozen in a purely sequential manner. The equivalence of optimizing the polar-code construction for the SCL decoder under this technique and maximizing the expected reward of traversing a maze is drawn. Simulation results show that the standard polar-code constructions that are designed for the successive-cancellation decoder are no longer optimal for the SCL decoder with respect to the frame error rate (FER). In contrast, the proposed game-based construction method finds code constructions that have similar or lower FER for various code lengths and various list sizes of the SCL decoder, compared to the state-of-the-art construction methods. The advantage of the game-based constructions over the standard constructions increases with the channel signal-to-noise ratio and the list size of SCL decoding. Moreover, the learning is highly efficient in terms of the number of required training samples and computational operations.

In this paper, we introduce a novel bit-flipping algorithm for fast successive cancellation (FSC) decoding of polar codes. In particular, we first propose a new bit-flipping strategy tailored to single parity-check (SPC) constituent codes of polar codes. A parameterized bit-flipping model is then developed and reinforcement learning (RL) is used to optimize the parameters. Our experimental results show that for a polar code of length 512 with 256 information bits, the proposed decoder has a better or similar error-correction performance compared to the state-of-the-art fast DSCF (FDSCF) decoding algorithm when the same number of maximum decoding attempts is considered.

Reed-Muller (RM) codes are one of the oldest families of codes. Recently, a recursive projection aggregation (RPA) decoder has been proposed, which achieves a performance that is close to the maximum likelihood decoder for short-length RM codes. One of its main drawbacks, however, is the large amount of computations needed. In this paper, we devise a new algorithm to lower the computational budget while keeping a performance close to that of the RPA decoder. The proposed approach consists of multiple sparse RPAs that are generated by performing only a selection of projections in each sparsified decoder. In the end, a cyclic redundancy check (CRC) is used to decide between output codewords. Simulation results show that our proposed approach reduces the RPA decoder's computations by up to 80% with negligible performance loss.

This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements$P$that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is$O\left(N^{1-1/\mu}+ \frac{N}{P}\log_{2}\log_{2}\frac{N}{P}\right)$, where$N$is the block length of the code and$\mu$is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where$P=\frac{N}{2}$, the latency of SSC decoding is$O\left(N^{1-1/\mu}\right)$, which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where$P=1$, the latency of SSC decoding scales as$O(N\, \log_{2}\log_{2}N)$. The multiplicative constant is also calculated: we show that the latency of SSC decoding when$P=1$is given by$(2+o(1))N\, \log_{2}\log_{2}N$. Third, in a semi-parallel implementation, the smallest$P$that gives the same latency as that of the fully-parallel implementation is$P=N^{1/\mu}$. The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.

Fast SC decoding overcomes the latency caused by the serial nature of the SC decoding by identifying new nodes in the upper levels of the SC decoding tree and implementing their fast parallel decoders. In this work, we first present a novel sequence repetition node corresponding to a particular class of bit sequences. Most existing special node types are special cases of the proposed sequence repetition node. Then, a fast parallel decoder is proposed for this class of node. To further speed up the decoding process of general nodes outside this class, a threshold-based hard-decision-aided scheme is introduced. The threshold value that guarantees a given error-correction performance in the proposed scheme is derived theoretically. Analysis and hardware implementation results on a polar code of length 1024 with code rates 1/4, 1/2, and 3/4 show that our proposed algorithm reduces the required clock cycles by up to 8%, and leads to a 10% improvement in the maximum operating frequency compared to state-of-the-art decoders without tangibly altering the error-correction performance. In addition, using the proposed threshold-based hard-decision-aided scheme, the decoding latency can be further reduced by 57% at Eb/N0= 5.0 dB.

This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1-1/μ), where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 or 1.

In this paper we address the problem of selecting factor-graph permutations of polar codes under belief propagation (BP) decoding to significantly improve the error-correction performance of the code. In particular, we formalize the factor-graph permutation selection as the multi-armed bandit problem in reinforcement learning and propose a decoder that acts like an online-learning agent that learns to select the good factor-graph permutations during the course of decoding. We use state-of-the-art algorithms for the multi-armed bandit problem and show that for a 5G polar codes of length 128 with 64 information bits, the proposed decoder has an error-correction performance gain of around 0.125 dB at the target frame error rate of 10-4, when compared to the approach that randomly selects the factor-graph permutations.

This paper formulates the polar-code construction problem for the successive-cancellation list (SCL) decoder as a maze-traversing game, which can be solved by reinforcement learning techniques. The proposed method provides a novel technique for polar-code construction that no longer depends on sorting and selecting bit-channels by reliability. Instead, this technique decides whether the input bits should be frozen in a purely sequential manner. The equivalence of optimizing the polar-code construction for the SCL decoder under this technique and maximizing the expected reward of traversing a maze is drawn. Simulation results show that the standard polar-code constructions that are designed for the successive-cancellation decoder are no longer optimal for the SCL decoder with respect to the frame error rate. In contrast, the simulations show that, with a reasonable amount of training, the game-based construction method finds code constructions that have lower frame-error rate for various code lengths and decoders compared to standard constructions.

An adaptive bandwidth allocation mechanism for the calendar associated with the Flexible Ethernet (FlexE) standard is proposed. The proposed method bases the FlexE calendar design on the clients' real transmit data rates. In particular, the proposed method treats clients with very low bandwidth utilization as minor clients and allows them to transmit in an opportunistic manner. Experiments on real Ethernet packet traces indicate that by using the proposed calendar scheme to allocate bandwidth to clients, the total required FlexE bandwidth can be reduced by up to 60% while meeting packet drop requirements.

This paper focuses on fast successive-cancellation (SC) decoding of polar codes. A threshold-based hard-decision-aided scheme is proposed to speed up the decoding process, especially when the communications channel has low noise. In addition, to eliminate the error-correction performance degradation caused by hard decisions, a backtracking strategy is introduced. Simulation results on a polar code of code length 1024 and rate 1/2 show that, with the help of the proposed scheme, the average decoding latency of existing fast SC decoding algorithms can be reduced by 53% at an Eb/N0 = 5.0 dB with negligible error-correction performance degradation.

This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1-1/μ), where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 and 1.

Visible light communication (VLC) provides a short- range optical wireless communication through light- emitting diode (LED) lighting. Light beam flickering and dimming are among the challenges to be addressed in VLC. Conventional methods for generating flicker-free codes in VLC are based on run-length limited codes that have poor error correction performance, use lookup tables which are memory consuming, and have low transmission rates. In this paper, we propose an efficient construction of flicker-free forward error correction codes to tackle the issue of flickering in VLC. Our simulation results show that by using polar codes and at a dimming ratio of 50%, the proposed system generates flicker-free codes without using lookup tables, while having lower complexity and higher transmission rates than the standard VLC methods. For an information block length of 256, the error correction performance of the proposed scheme is 1.8 dB and 0.9 dB better than that of the regular schemes at the bit error rate of 10^{-6} for a rate of 0.44 and 0.23, respectively.

Polar codes are the first class of error correcting codes that provably achieve the channel capacity at infinite code length. They were selected for use in the fifth generation of cellular mobile communications (5G). In practical scenarios such as 5G, a cyclic redundancy check (CRC) is concatenated with polar codes to improve their finite length performance. This is mostly beneficial for sequential successive-cancellation list decoders. However, for parallel iterative belief propagation (BP) decoders, CRC is only used as an early stopping criterion with incremental error-correction performance improvement. In this paper, we first propose a CRC-polar BP (CPBP) decoder by exchanging the extrinsic information between the factor graph of the polar code and that of the CRC. We then propose a neural CPBP (NCPBP) algorithm which improves the CPBP decoder by introducing trainable normalizing weights on the concatenated factor graph. Our results on a 5G polar code of length 128 show that at the frame error rate of 10-5and with a maximum of 30 iterations, the error-correction performance of CPBP and NCPBP are approximately 0.25 dB and 0.5 dB better than that of the conventional CRC-aided BP decoder, respectively, while introducing almost no latency overhead.

Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported.

Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10-4.

Polar codes are a class of channel capacity achieving codes that has been selected for the next generation of wireless communication standards. Successive-cancellation (SC) is the first proposed decoding algorithm, suffering from mediocre errorcorrection performance at moderate code lengths. In order to improve the error-correction performance of SC, two approaches are available: (i) SC-List decoding which keeps a list of candidates by running a number of SC decoders in parallel, thus increasing the implementation complexity, and (ii) SC-Flip decoding that relies on a single SC module, and keeps the computational complexity close to SC. In this work, we propose the partitioned SC-Flip (PSCF) decoding algorithm, which outperforms SCFlip in terms of error-correction performance and average computational complexity, leading to higher throughput and reduced energy consumption per codeword. We also introduce a partitioning scheme that best suits our PSCF decoder. Simulation results show that at equivalent frame error rate, PSCF has up to 4.1× less computational complexity than the SC-Flip decoder. At equivalent average number of iterations, the error-correction performance of PSCF outperforms SC-Flip by up to 0.26 dB at frame error rate of 10-3.

Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption. In this paper, we consider the paradigm of PSCL decoding from a practical standpoint, and we provide several improvements. First, by changing the target signal-to-noise ratio and consequently modifying the construction of the code, we are able to improve the performance at no additional computational, latency, or memory cost. Second, we bridge the performance gap between SCL and PSCL decoding by introducing a generalized PSCL decoder and a layered PSCL decoder. In this way, we obtain almost the same performance of the SCL decoder with a significantly lower memory requirement, as testified by hardware implementation results. Third, we present an optimal scheme to allocate cyclic redundancy checks. Finally, we provide a lower bound on the list size that guarantees optimal maximum a posteriori performance for the binary erasure channel.

Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption [1]. In this paper, we examine the paradigm of PSCL decoding from both theoretical and practical standpoints: (i) by changing the construction of the code, we are able to improve the performance at no additional computational, latency or memory cost, (ii) we present an optimal scheme to allocate cyclic redundancy checks (CRCs), and (iii) we provide an upper bound on the list size that allows MAP performance.

Successive-cancellation list (SCL) decoding is an algorithm that provides very good error-correction performance for polar codes. However, its hardware implementation requires a large amount of memory, mainly to store intermediate results. In this paper, a partitioned SCL algorithm is proposed to reduce the large memory requirements of the conventional SCL algorithm. The decoder tree is broken into partitions that are decoded separately. We show that with careful selection of list sizes and number of partitions, the proposed algorithm can outperform conventional SCL while requiring less memory.

The Successive-Cancellation List (SCL) algorithm is one of the best polar code decoding algorithms in terms of trade-offs between complexity and error correction performance. The List-Sphere Decoding (List-SD) algorithm has been recently proposed: it yields a better complexity/performance trade-off than SCL in the decoding of short polar codes, that can be used as component codes for larger polar codes. We exploit the structure of the generator matrix of polar codes to propose a matrix reordering technique which allows to significantly reduce the List-SD complexity without degrading its error correction performance, further improving the aforementioned trade-off. The proposed technique is implemented on hardware and it is shown that at the same Frame Error Rate (FER) and Bit Error Rate (BER), the matrix reordering can reduce the resource requirements of List-SD of up to 73%. Furthermore, FER and BER curves are plotted for case studies, showing that at the same complexity cost, matrix reordering improves the performance of List-SD of up to 0.75 dB at FER=10-2.

The Successive-Cancellation List (SCL) decoding algorithm is one of the most promising approaches towards practical polar code decoding. It is able to provide a good trade-off between error-correction performance and complexity, tunable through the size of the list. In this paper, we show that in the conventional formulation of SCL, there are redundant calculations which do not need to be performed in the course of the algorithm. We simplify SCL by removing these redundant calculations and prove that the proposed simplified SCL and the conventional SCL algorithms are equivalent. The simplified SCL algorithm is valid for any code and can reduce the time-complexity of SCL without affecting the space complexity.

This paper presents a novel discrete particle swarm optimization (PSO) technique for the high-level synthesis of digital filter data-paths. In this technique, the cost associated with the final digital filter data-path is minimized for obtaining combined area-cum-time optimal digital filter data-paths subject to user-specified constraints on the number of the required arithmetic functional units. In the proposed technique, the digital filter data-path encoding is achieved by combining the information regarding the operation scheduling together with the information regarding the allocation and binding of operations to arithmetic functional units into a single particle. The scheduling, and allocation and binding information form the coordinate values of the particles in PSO. The salient feature of the resulting PSO technique is its fast convergence speed, achieved by ensuring that the (random) movement of the particles in the search space in the course of optimization are automatically guaranteed to preserve the data-dependency relationships in the original digital filter signal flow-graph without any recourse to backtracking. The usefulness of the proposed PSO technique is demonstrated through the application of it to the high-level synthesis of a benchmark elliptic wave digital filter. It is observed that the application of the PSO leads to substantially faster convergence speeds as compared to the corresponding genetic algorithms.

A novel technique is presented for finite-wordlength (FW) particle swarm optimization (PSO) of BIBO stable FRM digital filters incorporating bilinear-LDI IIR interpolation subfilters. A novel LUT scheme is developed to ensure that the FWPSO automatically searches over permissible FW multiplier coefficient values only in the course of optimization. The salient feature of the proposed LUT scheme is that unlike the conventional PSO, there is no need to limit the search space in the course of optimization to prevent going over the boundaries of the search space. This is achieved by introducing barren layers in the LUTs. The usefulness of the proposed FWPSO is illustrated through its application to the design and simultaneous magnitude and group-delay optimization of a lowpass IIR-based FRM digital filter.

This paper presents a novel diversity-controlled (DC) genetic algorithm (GA) for the design and rapid optimization of frequency-response masking (FRM) digital filters over the CSD multiplier coefficient space. The resulting FRM digital filters incorporate bilinear-LDI IIR interpolation subfilters realized as a parallel combination of a pair of allpass digital networks. A novel LUT scheme is developed to ensure that the FRM digital filters under consideration are automatically BIBO stable throughout the course of DCGA optimization. The salient feature of the proposed LUT scheme is that it makes no recourse to slack variables for referencing the values of the CSD multiplier coefficients. The DCGA optimization fitness function includes not only the magnitude but also the group-delay frequency-response of FRM digital filters so as to minimize phase distortion caused by the IIR interpolation subfilters. An example is given to illustrate the application of the proposed DCGA optimization to the design of a lowpass FRM digital filter incorporating a seventh-order bilinear-LDI interpolation subfilter.