Precoded polar product codes are proposed, where selected component codes enable successive cancellation list decoding to generate bit-wise soft messages efficiently for iterative decoding while targeting optimized distance spectrum as opposed to eBCH or polar component codes. Rate compatibility is a byproduct of 1-bit granularity in the component code design.

A tree search algorithm called successive cancellation ordered search (SCOS) is proposed forGN-coset codes that implements maximum-likelihood (ML) decoding with adaptive complexity for transmission over binary-input AWGN channels. Unlike bit-flip decoders, no outer code is needed to terminate decoding; therefore, SCOS also applies toGN-coset codes modified with dynamic frozen bits. The average complexity is close to that of successive cancellation (SC) decoding at practical frame error rates (FERs) for codes with wide ranges of rate and lengths up to 512 bits, which perform within 0.25 dB or less from the random coding union bound and outperform Reed–Muller codes under ML decoding by up to 0.5 dB. Simulations illustrate simultaneous gains for SCOS over SC-Fano, SC stack (SCS) and SC list (SCL) decoding in FER and the average complexity at various SNR regimes. SCOS is further extended by forcing it to look for candidates satisfying a threshold, thereby outperforming basic SCOS under complexity constraints. The modified SCOS enables strong error-detection capability without the need for an outer code. In particular, the (128, 64) polarization-adjusted convolutional code under modified SCOS provides gains in overall and undetected FER compared to CRC-aided polar codes under SCL/dynamic SC flip decoding at high SNR.

A product code with single parity-check component codes can be described via the tools of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following this observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over binary memoryless symmetric channels under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established for the binary erasure channel. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, simulations over the binary input additive white Gaussian channel show that successive cancellation list decoding outperforms belief propagation decoding applied to the code graph. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis. Examples of concatenations performing within 0.7 dB from the random coding union bound are provided.

This work identifies information-theoretic quantities that are closely related to the required list size on average for successive cancellation list (SCL) decoding to implement maximum-likelihood decoding over general binary memoryless symmetric (BMS) channels. It also provides upper and lower bounds for these quantities that can be computed efficiently for very long codes. For the binary erasure channel (BEC), we provide a simple method to estimate the mean accurately via density evolution. The analysis shows how to modify, e.g., Reed-Muller codes, to improve the performance when practical list sizes, e.g.,$L\in {[{8, 1024}]}$, are adopted. Exemplary constructions with block lengths$N\in \{128,512\}$outperform polar codes of 5G over the binary-input additive white Gaussian noise channel. It is further shown that there is a concentration around the mean of the logarithm of the required list size for sufficiently large block lengths, over discrete-output BMS channels. We provide the probability mass functions (p.m.f.s) of this logarithm, over the BEC, for a sequence of the modified RM codes with an increasing block length via simulations, which illustrate that the p.m.f.s concentrate around the estimated mean.

A complexity-adaptive tree search algorithm is proposed for $G_{N}$-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation (SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to N = 128. By modifying the algorithm to limit the worstcase complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified $G_{N}$-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter.

A successive cancellation (SC) decoder with inactivations is proposed as an efficient implementation of SC list (SCL) decoding over the binary erasure channel. The proposed decoder assigns a dummy variable to an information bit whenever it is erased during SC decoding and continues with decoding. Inactivated bits are resolved using information gathered from decoding frozen bits. This decoder leverages the structure of the Hadamard matrix, but can be applied to any linear code by representing it as a polar code with dynamic frozen bits. SCL decoders are partially characterized using density evolution to compute the average number of inactivations required to achieve the maximum a-posteriori decoding performance. The proposed measure quantifies the performance vs. complexity trade-off and provides new insight into dynamics of the number of paths in SCL decoding. The technique is applied to analyze Reed-Muller (RM) codes with dynamic frozen bits. It is shown that these modified RM codes perform close to extended BCH codes.

We present nonasymptotic upper and lower bounds on the maximum coding rate achievable when transmitting short packets over a Rician memoryless block-fading channel for a given requirement on the packet error probability. We focus on the practically relevant scenario in which there is no a priori channel state information available at the transmitter or at the receiver. An upper bound built upon the min-max converse is compared with two lower bounds: the first one relies on a noncoherent transmission strategy in which the fading channel is not estimated explicitly at the receiver and the second one employs pilot-assisted transmission (PAT) followed by maximum-likelihood channel estimation and scaled mismatched nearest-neighbor decoding at the receiver. Our bounds are tight enough to unveil the optimum number of diversity branches that a packet should span so that the energy per bit required to achieve a target packet error probability is minimized, for a given constraint on the code rate and the packet size. Furthermore, the bounds reveal that noncoherent transmission is more energy efficient than PAT, even when the number of pilot symbols and their power is optimized. For example, in Rayleigh fading, for the case when a coded packet of 168 symbols is transmitted using a channel code of rate 0.48-bits/channel use, over a block-fading channel with block size equal to eight symbols, PAT requires an additional 1.2 dB of energy per information bit to achieve a packet error probability of 10-3compared with a suitably designed noncoherent transmission scheme. Finally, we devise a PAT scheme based on punctured tail-biting quasi-cyclic codes and ordered-statistics decoding, whose performance is close (1-dB gap at 10-3packet error probability) to the ones predicted by our PAT lower bound. This shows that the PAT lower bound provides useful guidelines on the design of actual PAT schemes.

We introduce successive cancellation (SC) decoding of product codes (PCs) with single parity-check (SPC) component codes. Recursive formulas are derived, which resemble the SC decoding algorithm of polar codes. We analyze the error probability of SPC-PCs over the binary erasure channel under SC decoding. A bridge with the analysis of PCs introduced by Elias in 1954 is also established. Furthermore, bounds on the block error probability under SC decoding are provided, and compared to the bounds under the original decoding algorithm proposed by Elias. It is shown that SC decoding of SPC-PCs achieves a lower block error probability than Elias' decoding.