Открытый доступ
Доступ предоставлен
Только для подписчиков
Том 59, № 1 (2023)
Статьи
Серии формул для параметров бхаттачарьи в теории полярных кодов
Аннотация
В теории полярных кодов для определения позиций замороженных и информационных бит используются параметры Бхаттачарьи. Они характеризуют скорость поляризации каналов WN(i), 1 ≤ i ≤ N, специальным образом построенных из исходного канала W, где N = 2n - длина кода, n = 1, 2, ... В случае, когда W - двоичный симметричный канал без памяти, приведены две серии формул для параметров Z(WN(i)): при i = N - 2k + 1, 0 ≤ k ≤ n, и при i = N/2 - 2k + 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). Также исследуются комбинаторные свойства поляризационной матрицы GN полярного кода с ядром Арикана. В частности, установлены простые рекуррентные соотношения между строками матриц GN и GN/2.
Проблемы передачи информации. 2023;59(1):3-16
3-16
Коды для точного нахождения носителя разреженного вектора по ошибочным линейным измерениям и их декодирование
Аннотация
Построены коды, позволяющие точно находить носитель неизвестного разреженного вектора, у которого модули всех ненулевых координат примерно равны, по результатам линейных измерений в присутствии шума с ограниченной сверху ℓp-нормой. Предложен алгоритм декодирования, имеющий асимптотически минимальную сложность.
Проблемы передачи информации. 2023;59(1):17-24
17-24
Построение и декодирование полярных кодов с большими ядрами: обзор
Аннотация
Представлены методы построения и декодирования полярных кодов с большими ядрами. Важнейшей проблемой при реализации алгоритма последовательного исключения декодирования полярных кодов и его обобщений является обработка ядра, т.е. быстрое вычисление логарифмических отношений правдоподобия для входных символов ядра. Представлены оконный и рекурсивный решетчатый методы обработки больших ядер. Рассмотрены методы оценки надежности битовых подканалов и получения кодов с улучшенными свойствами расстояния.
Проблемы передачи информации. 2023;59(1):25-45
25-45
Перепараметризованные тесты максимального правдоподобия для обнаружения разреженных векторов
Аннотация
Рассматривается задача обнаружения разреженного вектора большой размерности на фоне белого гауссовского шума. Предполагается, что неизвестный вектор может иметь только p ненулевых компонент, положение и величина которых неизвестны, а их число, с одной стороны, велико, но с другой - мало по сравнению с его размерностью. Тест максимального правдоподобия (МП) в этой задаче имеет простой вид и, естественно, зависит от p. В статье изучаются статистические свойства перепараметризованных тестов МП, т.е. тестов, построенных на основе предположения, что число ненулевых компонент вектора равно q (q > p), в ситуации, когда на самом деле вектор имеет всего лишь p ненулевых компонент. Показывается, что в некоторых случаях перепараметризованные тесты могут быть лучше стандартных тестов МП.
Проблемы передачи информации. 2023;59(1):46-63
46-63
О проверке выполнимости алгебраических формул над полем из двух элементов
Аннотация
Построен вероятностный полиномиальный алгоритм проверки выполнимости алгебраических формул глубины 3 над полем из двух элементов, верхней операцией в которых является сложение. Алгоритм с теми же характеристиками существует для проверки равенства нулю многочлена (задача PIT), задаваемого формулами указанного вида. Однако эти задачи и алгоритмы их решения существенно отличаются. Вероятностный алгоритм для задачи PIT основан на лемме Шварца - Зиппеля, а предложенный в этой статье алгоритм проверки выполнимости основан на лемме Вельянта - Вазирани.
Проблемы передачи информации. 2023;59(1):64-70
64-70
Неординарные пуассоновские модели трафика мультисервисных сетей
Аннотация
Появление сетей передачи данных с коммутацией пакетов показало, что пуассоновские модели потоков не являются адекватными, и потребовало разработки новых моделей, основанных на непуассоновских распределениях. Статья посвящена анализу частного случая группового марковского потока - группового неординарного пуассоновского потока событий. В таком потоке выполняются свойство стационарности и отсутствия последействия, но не выполняется свойство ординарности. Рассматривается класс систем массового обслуживания с постоянным временем обслуживания. Приведены результаты аналитических расчетов параметров потока и результаты имитационного моделирования. Показано, что дисперсия очереди зависит от третьего момента размера пачки заявок во входящем групповом пуассоновском потоке.
Проблемы передачи информации. 2023;59(1):71-79
71-79