A series of short exact formulas for the Bhattacharya parameter of coordinate channels

Let $W$ be a symmetric channel with binary input alphabet and a finite output alphabet. In 2007, E. Arikan discovered the phenomenon of channel polarization, which makes it possible to single out those synthetic channels $W_N^{(i)}$, constructed by $W$, through which it is preferable to transmit information bits. One of the tools for splitting channels into “bad” and “good” is the Bhattacharya parameter $Z(W_N^{(i)})$. However, the calculation of $Z(W_N^{(i)})$ is difficult, since it requires about $2^{2N}$ addition operations, where $N$ is the code length. In 2013, I. Tal and A. Vardy proposed a method for estimating from above and below the error probabilities in the channels $W_N^{(i)}$, $1 \leqslant i \leqslant N$, which has a complexity $O(N\mu^2\log \mu)$, where $\mu > \mu_0$ and the number $\mu_0$ does not depend on $N$. However, the number $\mu$ can be quite great and depends, in particular, on the required precision. Previously, in the case where $W$ is a memoryless binary symmetric channel, the authors constructed two series of exact formulas for the Bhattacharya parameters, which still require an exponential but much less number of operations than in the formulas from Arikan's original paper. In the present paper, for every $N=2^n$, we construct a series of $n(n-1)/2$ exact formulas that do not contain summation over variables.