Polar-coded multiple-input multiple-output systems are investigated. An advanced receiver implementing joint list decoding of polar codes and QR- and MMSE-based detectors is proposed. The approximate and exact path metrics are derived for joint list decoder of polar codes. A construction of polar subcodes for MIMO systems with cross-antenna dynamic freezing constraints is proposed. The obtained polar subcodes provide significant performance gain compared to LDPC-coded MIMO systems with the same rate allocation.

novel construction of randomized polar subcodes and subcodes of extended BCH codes is presented. The proposed approach stems from a new heuristic for building polar code frozen set which minimizes the error probability of successive cancellation algorithm applied to permuted noisy codewords. The frame error rate (FER) of the proposed codes under permutationbased decoding is comparable to FER of existing polar subcodes under successive cancellation list or sequential algorithm.

A generalization of the fast successive cancellation decoding algorithm to the case of binary polar codes with arbitrary large kernels is presented. Its asymptotic latency is shown to be$O(N^{1-1/\mu })$, where$\mu $is the scaling exponent of the underlying polarization kernel.

A novel class of polarization kernels is proposed, which is based on the construction of generalized concatenated codes. The complexity of the kernel processing operation, which is the computational core of the (list) successive cancellation decoder, for the obtained kernels of size 64 is several orders of magnitude less compared to BCH and Yao-Fazeli-Vardy kernels. Polar subcodes based on the obtained kernels under list successive cancellation decoder provide both performance and complexity improvement with respect to those based on the Arikan kernel.

Novel reduced complexity soft-input soft-output decoding algorithms for first-order Reed-Muller codes are proposed. They are based on modified fast Hadamard transform and have lower decoding complexity compared to the recursive approaches.

A reduced complexity symbolwise maximum a posteriori probability (MAP) decoding algorithm for linear block codes is presented. This algorithm is based on the recursive trellises and performs two passes over the recursion tree. Probability-domain and Log-Max implementations are considered. Numeric results show that the proposed method has lower complexity compared to other known recursive algorithms and the classical BCJR algorithm. The complexity analysis for random codes is provided.

A reduced complexity algorithm for computing polarization behavior of binary kernels is presented. It is based on the Yao-Fazeli-Vardy algorithm. The idea is to recompute linear manifolds, which represent trellis vertices, via those obtained at a previous trellis layer. It provides several times complexity reduction for many published kernels.

A reduced complexity algorithm is presented for computing the log-likelihood ratios (LLRs) arising in the successive cancellation (SC) decoder for polar codes with large kernels of arbitrary dimension. The proposed algorithm exploits a recursive trellis representation of the codes generated by submatrices of the polarization kernel and enables polar codes based on large kernels to be decoded with lower complexity compared to the codes based on the Arıkan kernel with the same performance. Extensions to the case of non-binary kernels are presented.

A reduced complexity SISO decoder of linear block codes is presented. This method is based on recursive trellises and uses Hartmann-Rudolph transform. Probability- and log-domain sign-magnitude implementations are derived. Numeric results demonstrate substantial complexity reduction compared to the recursive SISO and BCJR algorithms.

A method for computing the reliability of bit sub-channels arising in multilevel polar codes with shaping is presented. The proposed approach is based on explicit expressions for cumulative density functions of LLRs arising in the SC decoder in multilevel Honda-Yamamoto polar coding scheme.

We consider a set of security and privacy problems under reliability and storage constraints that can be tackled by using codes and particularly focus on the secret-key agreement problem. Polar subcodes (PSCs) are polar codes (PCs) with dynamically-frozen symbols and have a larger code minimum distance than PCs with only statically-frozen symbols. A randomized nested PSC construction, where the low-rate code is a PSC and the high-rate code is a PC, is proposed for successive cancellation list (SCL) and sequential decoders. This code construction aims to perform lossy compression with side information, i.e., Wyner-Ziv (WZ) coding. Nested PSCs are used in the key agreement problem with physical identifiers and two terminals since WZ-coding constructions significantly improve on Slepian-Wolf coding constructions such as fuzzy extractors. Significant gains in terms of the secret-key vs. storage rate ratio as compared to nested PCs with the same list sizes are illustrated to show that nested PSCs significantly improve on all existing code constructions. The performance of the nested PSCs is shown to improve with larger list sizes, unlike the nested PCs considered. A design procedure to efficiently construct nested PSCs and possible improvements to the nested PSC designs are also provided.

A reduced complexity algorithm is presented for computing the log-likelihood ratios arising in the successive cancellation decoder for polar codes with large kernels of arbitrary dimension. The proposed algorithm exploits recursive trellis representation of the codes generated by submatrices of the polarization kernel, and enables polar codes based on large kernels to provide better performance compared to the codes based on Arikan kernel with the same decoding complexity.

A novel SISO decoding algorithm for linear block codes is presented. This algorithm is based on the recursive trellises and performs two passes over the recursion tree. Probabilitydomain implementation and its LogMax approximation are considered. Numeric results show that proposed method has lower complexity compared to the other known recursive algorithms and the classical BCJR algorithm.

A decoding algorithm for polar (sub)codes with binary 2t×2tpolarization kernels is presented. It is based on the window processing (WP) method, which exploits the linear relationship of the polarization kernels and the Arikan matrix. This relationship enables one to compute the kernel input symbols probabilities by computing the probabilities of several paths in Arikan successive cancellation (SC) decoder. In this paper we propose an improved version of WP, which has significantly lower arithmetic complexity and operates in log-likelihood ratios (LLRs) domain. The algorithm identifies and reuses common subexpressions arising in computation of Arikan SC path scores. The proposed algorithm is applied to kernels of size 16 and 32 with improved polarization properties. It enables polar (sub)codes with the considered kernels to simultaneously provide better performance and lower decoding complexity compared with polar (sub)codes with Arikan kernel.

Recursive trellis decoding of polar codes is considered. Polar codes are shown to have much lower recursive trellis decoding complexity compared to similar Reed-Muller codes. Furthermore, a low-latency decoding algorithm, which combines recursive trellis and successive cancellation decoding methods, is presented.

A method for construction of polar subcodes with reduced error coefficient is presented. The proposed approach relies on explicit enumeration of low-weight non-zero codewords in a polar code, and construction of dynamic freezing constraints which define a subcode not containing most of these codewords. The obtained codes provide a large performance gain in the high-SNR region compared to non-optimized polar subcodes and polar codes with CRC.

A lower bound on minimum distance of convolutional polar codes is provided. The bound is obtained from the minimum weight of generalized cosets of the codes generated by bottom rows of the polarizing matrix. Minimum weight of cosets is also used for construction of convolutional polar subcodes, which provide lower FER under list SC decoding compared to polar subcodes and convolutional polar codes.

Polar subcodes with large kernels were shown to require lower complexity to achieve the same performance as Arikan polar codes under SCL decoding. In this paper we present design techniques for polar (sub)codes with large kernels. Namely, methods are presented to estimate the capacities of bit subchannels, as well as to eliminate low-weight non-zero codewords from the obtained codes.

We propose a reduced complexity algorithm for computing log-likelihood ratios (LLRs) needed for successive cancellation (SC) decoding of polar codes with 2t× 2tpolarization kernels. This algorithm is applied to some polarization kernels of length 16 and 32 with high polarization rate. The complexity reduction is achieved by exploiting linear relationship of the considered kernels and Arikan matrix. Further complexity reduction is achieved by identification of common subexpressions. The proposed approach enables SC list decoding of polar codes with some large kernels with lower complexity compared to the codes based on the Arikan kernel with the same performance.

A recursive trellis-based algorithm is proposed for computing the probabilities arising in the successive cancellation (SC) decoding algorithm for polar codes with arbitrary linear kernels. This approach enables one to re-use intermediate values obtained at different phases. Arikan SC algorithm is shown to be a special case of this method.

An algorithm for construction of binary polarization kernels of size 16 and 32 with polarization rate greater than 0.5, which admit low complexity processing is proposed. Kernels are obtained by employing such linear transformations of the Arikan matrix, which minimize the complexity of the window processing algorithm, while preserving required rate of polarization. Simulation results show that polar subcodes with obtained kernels can outperform polar codes with Arikan kernel, while having lower decoding complexity.

A lower bound on the minimum distance of convolutional polar codes is provided. The bound is obtained from the minimum weight of the generalized cosets of the codes generated by the bottom rows of the polarizing matrix. Moreover, a construction of convolutional polar subcodes is proposed, which provides improved performance under successive cancellation list decoding. For sufficiently large list size, the decoding complexity of convolutional polar subcodes appears to be lower compared with Arikan polar subcodes with the same performance. The error probability of successive cancellation list decoding of convolutional polar subcodes is lower than that of Arikan polar subcodes with the same list size.

A novel score function is proposed for sequential decoding of polar codes. Significant reduction of the average decoding complexity is achieved by biasing the path metrics in the min-sum version of the stack successive cancellation decoding algorithm with its expected value. The proposed approach can be also used for near-ML decoding of short extended BCH codes.

We propose to reduce the decoding complexity of polar codes with non-Arikan kernels by employing a (near) ML decoding algorithm for the codes generated by kernel rows. A generalization of the order statistics algorithm is presented for soft decoding of Reed-Solomon codes. Algebraic properties of the Reed-Solomon code are exploited to increase the reprocessing order. The obtained algorithm is used as a building block to obtain a decoder for polar codes with Reed-Solomon kernel.

An efficient numerically stable successive cancellation decoding algorithm for convolutional polar codes is proposed. The proposed algorithm makes use of only summation and comparison operations, and admits immediate extension to the case of list SC decoding, which provides near-ML performance.

A decoding algorithm for polar codes with binary 16×16 kernels with polarization rate 0.51828 and scaling exponents 3.346 and 3.450 is presented. The proposed approach exploits the relationship of the considered kernels and the Arikan matrix to significantly reduce the decoding complexity without any performance loss. Simulation results show that polar (sub)codes with 16×16 kernels can outperform polar codes with Arikan kernel, while having lower decoding complexity.

A method for construction of polar subcodes is presented, which aims on minimization of the number of low-weight codewords in the obtained codes, as well as on improved performance under list or sequential decoding. Simulation results are provided, which show that the obtained codes outperform LDPC and turbo codes.

An extension of polar codes is proposed, which allows some of the frozen symbols, called dynamic frozen symbols, to be data-dependent. A construction of polar codes with dynamic frozen symbols, being subcodes of extended BCH codes, is proposed. The proposed codes have higher minimum distance than classical polar codes, but still can be efficiently decoded using the successive cancellation algorithm and its extensions. The codes with Arikan, extended BCH and Reed-Solomon kernel are considered. The proposed codes are shown to outperform LDPC and turbo codes, as well as polar codes with CRC.

A low-complexity systematic encoding algorithm for polar codes with Reed-Solomon (RS) kernel is presented. The proposed method relies on fast Fourier transform-based RS encoding techniques. An application of polar codes in storage systems is considered.

The problem of efficient decoding of polar codes is considered. A multilevel bucket structure is proposed for implementation of the stack in the sequential decoding algorithm. This data structure reduces the complexity of stack operations with respect to the implementation based on a red-black tree.

Fast algorithms are proposed for encoding and reconstructing data in RAID based on Reed-Solomon codes. The proposed approach is based on the cyclotomic fast Fourier transform algorithm and enables one to significantly reduce the number of expensive Galois field multiplications required. The complexity of the obtained algorithms is much lower than those for existing MDS array codes. Software implementation of the proposed algorithms is discussed. The performance results show that the new algorithms provide substantially better performance compared with the standard algorithm.

Reduced complexity implementation of the successive cancellation decoding algorithm for polar codes with Reed-Solomon kernel is presented. The proposed approach is based on the representation of Reed-Solomon codes as Arikan polar codes over F2mwith dynamic frozen symbols, and application of list successive cancellation decoding algorithm.

The problem of efficient soft-decision decoding of polar codes with any binary kernel is considered. The proposed approach represents a generalization of the sequential decoding algorithm introduced recently for the case of polar codes with Arikan kernel. Numeric results show that the proposed algorithm enables near-ML decoding of polar codes with BCH kernel.

A novel soft-decision decoding algorithm for Reed-Solomon codes over F2mis considered. The proposed approach is based on their representation as Arikan polar codes with dynamic frozen symbols and application of the sequential successive cancellation decoding algorithm. Furthermore, permutation techniques are utilized in order to reduce the decoding complexity.

A novel construction of polar codes with dynamic frozen symbols is proposed. The proposed codes are subcodes of extended BCH codes, which ensure sufficiently high minimum distance. Furthermore, a decoding algorithm is proposed, which employs estimates of the not-yet-processed bit channel error probabilities to perform directed search in code tree, reducing thus the total number of iterations.

The problem of construction of binary polar codes with high-dimensional kernels is considered. A novel method for computing the erasure probability in the bit subchannels induced by the polarization kernel is proposed. The codes obtained using the proposed method outperform those based on the Arikan kernel.

The problem of efficient evaluation of the discrete Fourier transform over finite fields is considered. The techniques for additive complexity reduction of the cyclotomic FFT algorithm are proposed. The first one is based on the classical simultaneous reduction algorithm. The second one is based on a factorization of the presummation matrix into a sparse and block-diagonal ones. The proposed methods provide smaller asymptotic complexity, although for small-sized problems the required number of operations appears to be higher than the complexity of computer-optimized algorithms.

Polar codes are shown to be instances of both generalized concatenated codes and multilevel codes. It is shown that the performance of a polar code can be improved by representing it as a multilevel code and applying the multistage decoding algorithm with maximum likelihood decoding of outer codes. Additional performance improvement is obtained by replacing polar outer codes with other ones with better error correction performance. In some cases this also results in complexity reduction. It is shown that Gaussian approximation for density evolution enables one to accurately predict the performance of polar codes and concatenated codes based on them.

The interpolation step of the Wu list decoding algorithm for Reed–Solomon codes is considered. The problem is reformulated as construction of a partially homogenized interpolation polynomial. A generalization of the binary interpolation algorithm, which is based on the novel formulation of the interpolation step, is provided. It enables complexity reduction both with respect to the Wu method based on the iterative interpolation algorithm, as well as the Guruswami–Sudan method based on re-encoding and the binary interpolation algorithm.

A concatenated code construction based on folded Reed-Solomon codes and short inner linear block codes is proposed. A generalization of the Das-Vardy weight assignment scheme to the case of multivariate interpolation decoding is developed. The decoding algorithm for the proposed construction makes use of the weighted version of the Guruswami-Rudra list decoding algorithm and list decoding of inner codes.

A novel algorithm is proposed for the interpolation step of the Guruswami-Sudan list decoding algorithm. The proposed method is based on the binary exponentiation algorithm, and can be considered as an extension of the Lee-O'Sullivan method. The algorithm is shown to achieve both asymptotical and practical performance gain compared to the case of iterative interpolation algorithm. Further complexity reduction is achieved by employing the reencoding transformation. The key contribution of the paper, which enables the complexity reduction, is a novel randomized ideal multiplication algorithm.

An optimization algorithm for finding user allocation, bit and power loading in the downlink of MIMO-OFDM systems is proposed. The algorithm represents a generalization of the well-known concepts of LQ decomposition with row pivoting and water filling.

In order to reduce the signaling overhead in adaptive OFDM transmission systems being designed for B3G and 4G wireless communications, the basic resource unit, referred to as chunk, comprises a number of adjacent sub-carriers and OFDM symbol periods. A consequent open issue is the mapping of long codewords onto limited size chunks, especially when link adaptation per chunk is carried out. This paper proposes a new method for joint coding and modulation. A data packet, independently of its length, is encoded without any segmentation into a single codeword spanning different chunks employing different signal constellations. The parameters of the underlying error correction code are chosen independently of the signal constellation and no puncturing is required. Moreover, a joint adaptation of the code length and the modulation format is proposed to optimise the number of chunks allocated for transmission

The most computationally demanding step in algebraic soft-decision decoding, as well as Sudan-type list-decoding, of Reed-Solomon codes is bivariate polynomial interpolation. The interpolation problem consists of computing a polynomial Q(X,Y) that passes through a given set of points P with prescribed multiplicities M. We propose a new divide-and-conquer method that can potentially reduce the complexity of interpolation. Specifically, we split the interpolation problem {P,M} into two problems {P1,M1} and {P2,M2}, and then show that the intersection of the corresponding polynomial ideals I(P1,M1)capI(P2,M2) is equal to their product. Our divide-and-conquer approach differs from the one suggested by Feng-Giraud [G.L.Feng, (2002)] in that the interpolation subproblems {P2,M2} and {P2,M2} are solved independently and only afterwards their solutions are merged. This makes it possible to solve these problems in parallel

Multi carrier (MC) transmission is considered the leading candidate for a new air interface for fourth generation wireless systems. In order to enable a flexible exploitation of the envisaged large transmission bandwidths, a sub-division of the available bandwidth into sub-bands through FDMA (frequency division multiple access) is seen as a very promising solution. Within each sub-band, an MC-multiple access system can be accommodated. Recently, an efficient adaptive sub-band allocation (ASBA) approach has been shown to provide a significant performance gain in such systems. A system design method is proposed that yields, for each propagation scenario, the proper number of sub-bands, such that a given performance gain can be attained through ASBA.

In this paper, a coding scheme with M-ary Walsh-Hadamard (WH) orthogonal modulation is considered for multi-carrier (MC) transmission. A novel pilot-assisted channel estimation approach is proposed, that efficiently exploits the properties of WH codes. Firstly, simulation results on the single-user performance show the influence of the energy distribution between pilot and information symbols. Then, the impact of the channel estimation method is assessed for different system loads in a MC code division multiple access (MC-CDMA) uplink scenario.

We propose an improved algorithm for finding roots of polynomials over finite fields. This makes possible significant speedup of the decoding process of Bose-Chaudhuri-Hocquenghem, Reed-Solomon, and some other error-correcting codes.