The polarization process of polar codes over a prime q-ary alphabet is studied. Recently, it has been shown that the blocklength of polar codes with prime alphabet size scales polynomially with respect to the inverse of the gap between code rate and channel capacity. However, except for the binary case, the degree of the polynomial in the bound is extremely large. In this paper, a different approach to computing the degree of this polynomial for any prime alphabet size is shown. This approach yields a lower degree polynomial for various values of the alphabet size that were examined. It is also shown that even lower degree polynomial can be computed with an additional numerical effort.

A concatenated coding scheme over binary memoryless symmetric (BMS) channels using a polarization transformation followed by outer sub-codes is analyzed. Achievable error exponents and upper bounds on the error rate are derived. The first bound is obtained using outer codes which are typical random linear codes. As a byproduct of this bound, it determines the rates of the outer codes. A lower bound on the error exponent that holds for all BMS channels with a given capacity is then derived. Improved bounds and approximations for finite blocklength codes using channel dispersions (normal approximation), as well as converse and approximate converse results, are also obtained. The bounds are compared with actual simulation results from the literature. For the cases considered, when transmitting over the binary input additive white Gaussian noise channel, there was only a small gap between the channel dispersion-based approximation and the actual error rate of concatenated BCH-polar codes.

The polarization process of polar codes over a ternary alphabet is studied. Recently it has been shown that the scaling of the blocklength of polar codes with prime alphabet size scales polynomially with respect to the inverse of the gap between code rate and channel capacity. However, except for the binary case, the degree of the polynomial in the bound is extremely large. In this work, it is shown that a much lower degree polynomial can be computed numerically for the ternary case. Similar results are conjectured for the general case of prime alphabet size.

Polar code-based source coding is considered for some given code rate and some desired distortion level. The distortion level of a typical quantized source vector is required to be below the desired distortion level. A sufficient polynomial scaling law of the blocklength with respect to the gap between the desired distortion and the distortion-rate function is derived. The results are then used to obtain a polynomial scaling of the blocklength with respect to the gap to capacity for the polar code-based solution of the binary dirty paper problem and for polar write-once memory codes.

A concatenated coding scheme, recently proposed by Mahdavifar et al., is considered. The scheme uses polar codes as inner codes and maximum distance separable codes, such as Reed-Solomon codes, as outer codes. It was shown by Mahdavifar et al. that the concatenated coding scheme has a significantly better asymptotic error decay rate compared to Arikan's polar codes. However, the scaling of the required blocklength with respect to the gap between the code rate and the channel symmetric capacity was not considered. Following the analysis of the scaling problem for Arikan's polar codes by Guruswami and Xia, it is shown that the scaling of blocklength in the concatenated scheme is still inverse polynomial with the gap to the symmetric capacity. It is also shown that improved bounds can be derived for the concatenated scheme, compared to plain polar codes, both for the asymptotic error decay and for the scaling of the blocklength with respect to the gap to the symmetric capacity. An improved result for the error burst length that can be corrected is also derived for the concatenated coding scheme.

Improved upper bounds on the blocklength required to communicate over binary-input channels using polar codes, below some given error probability, are derived. For that purpose, an improved bound on the number of non-polarizing channels is obtained. The main result is that the blocklength required to communicate reliably scales at most as O((I(W ) - R)-5.702), where R is the code rate and I(W ) is the symmetric capacity of the channel W. The results are then extended to polar lossy source coding at rate R of a source with symmetric distortion-rate function D(·). The blocklength required scales at most as O((D0)-5.702), where D0is the maximal allowed gap between the actual average (or typical) distortion and D(R).

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.