Vol 59, No 1 (2023)

Bhattacharyya parameters are used in the theory of polar codes to determine positions of frozen and information bits. These parameters characterize rate of polarization of channels W_N⁽ⁱ⁾, 1 ≤ i ≤ N, which are constructed in a special way from the original channel W, where N = 2ⁿ is the channel length, n = 1, 2, .... In the case where W is a binary symmetric memoryless channel, we present two series of formulas for the parameters Z(W_N⁽ⁱ⁾): for i = N - 2^k + 1, 0 ≤ k ≤ n, and for i = N/2 - 2^k + 1, 1 ≤ k ≤ n - 2. The formulas require of the order of $\binom{2^{n-k}+2^k-1}{2^k} 2^{2^k}$ addition operations for the first series and of the order of $\binom{2^{n-k-1}+2^k-1}{2^k} 2^{2^k}$ for the second. In the cases i = 1, N/4 + 1, N/2 + 1, N, the obtained expressions for the parameters have been simplified by computing the sums in them. We show potential generalizations for the values of i in the interval (N/4, N). We also study combinatorial properties of the polarizing matrix G_N of a polar code with Arıkan’s kernel. In particular, we establish simple recurrence relations between rows of the matrices G_N and G_N/2.

We present techniques for the construction of polar codes with large kernels and their decoding. A crucial problem in the implementation of the successive cancellation decoding algorithm and its derivatives is kernel processing, i.e., fast evaluation of the log-likelihood ratios for kernel input symbols. We discuss window and recursive trellis processing methods. We consider techniques for evaluation of the reliability of bit subchannels and for obtaining codes with improved distance properties.

We construct a probabilistic polynomial algorithm for testing the satisfiability of algebraic formulas of depth 3 over the two-element field, with addition as the top operation in the formulas. An algorithm with the same characteristics exists for the problem of testing whether a polynomial given by formulas of this type is identically zero (PIT problem). However, these problems and algorithms for their solution are essentially different. The probabilistic algorithm for the PIT problem is based on the Schwartz-Zippel lemma, whereas the satisfiability testing algorithm proposed in this paper is based on the Valiant-Vazirani lemma.