Серия коротких точных формул для параметра Бхаттачарьи координатных каналов

Пусть $W$ — симметричный канал с двоичным входом и конечным выходным алфавитом. В 2007 г. Э. Ариканом обнаружено явление поляризации каналов, которое позволяет выделить из множества координатных каналов $W_N^{(i)}$, построенных по $W$, те, по которым предпочтительнее передавать информационные биты. Один из инструментов, позволяющих произвести разделение каналов на «плохие» и «хорошие», — это параметр Бхаттачарьи $Z\big(W_N^{(i)}\big)$. Однако его вычисление затруднено из-за большого числа требуемых операций сложения — порядка $2^{2N}$, где $N$ — длина кода. В работе И. Тала и А. Варди 2013 г. предложен метод оценки сверху и снизу вероятностей ошибок в каналах $W_N^{(i)}$, $1 \leqslant i \leqslant N$, имеющий сложность порядка $O(N\mu^2\log\mu)$, где $\mu > \mu_0$, а число $\mu_0$ не зависит от длины $N$. Однако число $\mu$ может быть достаточно большим и зависит, в частности, от требуемой точности. Ранее авторами в случае, когда $W$ — двоичный симметричный канал без памяти, построены две серии точных формул для параметров Бхаттачарьи, требующих всё ещё экспоненциального, но много меньшего числа операций, чем в формулах из оригинальной статьи Э. Арикана. В настоящей работе для всякого $N=2^n$ удалось построить серию из $n(n-1)/2$ точных формул, которые не содержат суммирования по переменным.