Полярные коды с памятью высшего порядка

Предложено построение множества последовательностей кодов $\{\mathscr{C}_n^{(m)}:\: n\ge 1, m\ge 1\}$ с памятью порядка $m$ и кодовой длиной $N(n)$. Семейство $\{\mathscr{C}_n^{(m)}\}$ — обобщение полярных кодов, предложенных Ариканом в [Arikan], в котором кодирующее отображение для длины $N(n)$ получается рекуррентным образом из кодирующих отображений для длин $N(n-1)$ и $N(n-m)$, где коды $\{\mathscr{C}_n^{(m)}\}$ при $m=1$ — это обычные полярные коды. Показано, что коды $\{\mathscr{C}_n^{(m)}\}$ достигают симметричной пропускной способности $I(W)$ произвольного канала $W$ без памяти с двоичными входами и дискретными выходами для любого фиксированного $m$. Получена верхняя граница для вероятности $P_e$ ошибки декодирования на блок для $\{\mathscr{C}_n^{(m)}\}$ и показано, что вероятность $P_e=O (2^{-N^\beta})$ достигается при $\beta<1/[1+m(\phi-1)]$, где $\phi\in (1;2]$ — наибольший вещественный корень многочлена $F(m,\rho)=\rho^m-\rho^{m-1}-1$. Сложность кодирования и декодирования для $\{\mathscr{C}_n^{(m)}\}$ убывает с ростом $m$, что доказывает существование новых схем полярного кодирования, имеющих меньшую сложность, чем конструкция Арикана.