Том 59, № 1 (2023)

В теории полярных кодов для определения позиций замороженных и информационных бит используются параметры Бхаттачарьи. Они характеризуют скорость поляризации каналов W_N⁽ⁱ⁾, 1 ≤ i ≤ N, специальным образом построенных из исходного канала W, где N = 2ⁿ - длина кода, n = 1, 2, ... В случае, когда W - двоичный симметричный канал без памяти, приведены две серии формул для параметров Z(W_N⁽ⁱ⁾): при i = N - 2^k + 1, 0 ≤ k ≤ n, и при i = N/2 - 2^k + 1, 1 ≤ k ≤ n - 2. Формулы требуют порядка $\binom{2^{n-k}+2^k-1}{2^k} 2^{2^k}$ операций сложения для первой серии и порядка $\binom{2^{n-k-1}+2^k-1}{2^k} 2^{2^k}$ для второй. Для случаев i = 1, N/4 + 1, N/2 + 1, N найденные выражения для параметров удалось упростить, вычислив входящие в них суммы. Указаны возможные обобщения для значений i из интервала (N/4, N). Также исследуются комбинаторные свойства поляризационной матрицы G_N полярного кода с ядром Арикана. В частности, установлены простые рекуррентные соотношения между строками матриц G_N и G_N/2.

Представлены методы построения и декодирования полярных кодов с большими ядрами. Важнейшей проблемой при реализации алгоритма последовательного исключения декодирования полярных кодов и его обобщений является обработка ядра, т.е. быстрое вычисление логарифмических отношений правдоподобия для входных символов ядра. Представлены оконный и рекурсивный решетчатый методы обработки больших ядер. Рассмотрены методы оценки надежности битовых подканалов и получения кодов с улучшенными свойствами расстояния.

Построен вероятностный полиномиальный алгоритм проверки выполнимости алгебраических формул глубины 3 над полем из двух элементов, верхней операцией в которых является сложение. Алгоритм с теми же характеристиками существует для проверки равенства нулю многочлена (задача PIT), задаваемого формулами указанного вида. Однако эти задачи и алгоритмы их решения существенно отличаются. Вероятностный алгоритм для задачи PIT основан на лемме Шварца - Зиппеля, а предложенный в этой статье алгоритм проверки выполнимости основан на лемме Вельянта - Вазирани.