Помехоустойчивое кодирование в задачах достоверной и защищенной передачи данных тема диссертации и автореферата по ВАК РФ 00.00.00, доктор наук Иванов Федор Ильич

• Иванов Федор Ильич
• доктор наук
• 2023

Оглавление диссертации доктор наук Иванов Федор Ильич

Введение

Глава 1 Комбинаторно-вероятностные методы построения и анализа кодов

1.1 Введение к первой главе

1.2 Основные понятия теории кодирования

1.2.1 Каналы передачи данных и их пропускные способности

1.2.2 Линейные блоковые коды

1.2.3 Сверточные коды

1.3 Коды с малой плотностью проверок на четность

1.3.1 Различные комбинаторые и алгебраические конструкции МПП-кодов

1.3.2 Оценка экспоненты вероятности ошибки регулярных МПП-кодов

1.4 Сверточные коды

1.4.1 Распределение длин пакетов ошибок на выходе декодера Витерби

1.4.2 Оценка вероятности ошибки на блок

1.4.3 Локальные свойства сверточных кодов

1.5 Выводы к первой главе

Глава 2 Полярные коды

2.1 Введение ко второй главе

2.2 Конструкции полярных кодов

2.3 Декодирование полярных кодов

2.3.1 Декодирование последовательного исключения (Successive

Cancellation)

2.3.2 Списочное декодирование

2.3.3 Быстрое декодирование на основе подкодов

2.3.4 Декодирование на основе инвертирования битов

2.3.5 Критические подмножества информационных символов полярного кода

2.3.6 Быстрый списочный декодер на основе инвертирования битов

2.4 Численные результаты

2.5 Анализ сложности

2.6 Выводы к второй главе

Глава 3 Кодирование в многопользовательских системах

3.1 Введение к третьей главе

3.2 Векторный дизъюнктивный канал множественного доступа

3.2.1 Модель канала

3.2.2 Анализ свойств канала

3.2.3 Неасимптотическая форма пропускной способности канала множественного доступа

3.2.4 Асимптотическая форма пропускной способности канала множественного доступа при р =1/2

3.2.5 Обобщение асимптотической оценки для случая произвольного р

3.2.6 Представление векторного дизъюктивного канала как объединения параллельных подканалов

3.2.7 Об оптимальности биномиального распределения

3.2.8 Пропускная способность зашумленного канала множественного доступа

3.3 Конструкции для разрешения коллизий для векторного дизъюнктивного канала

3.3.1 Конструкции на базе перемеженных кодов Рида-Соломона

3.3.2 Конструкции на базе перемеженных двоичных кодов

3.3.3 Коды на границе Варшамова-Гилберта

3.4 Выводы к третьей главе

Глава 4 Методы защиты информации на базе помехоустойчивых кодов

4.1 Введение к четвертой главе

4.2 Система Мак-Элиса

4.3 Атаки на систему Мак-Элиса

4.3.1 Декодирование по информационным совокупностям

4.3.2 Сложность атак на основе декодирования для системы Мак-Элиса

4.4 Различные варианты системы Мак-Элиса

4.4.1 Класс систем с декодированием в смежном классе

4.4.2 Система защиты информации на основе информационной совокупности, свободной от ошибок

4.5 Новые задачи в системах защиты информации на базе помехоустойчивых кодов - построение множества исправимых ошибок

4.6 Система на базе двоичного образа кода Рида-Соломона

4.6.1 Обобщенные коды Рида-Соломона и их двоичные образы268

4.6.2 Описание системы на базе двоичного образа ОРС кода

4.6.3 Связь между размерами блоков в матрице Q и множе-

ством Е

4.6.4 Связь между структурой матрицы Q и допустимым числом вносимых пакетов ошибок

4.6.5 Анализ некоторых атак

4.6.6 Длина ключей

4.7 Выводы к четвертой главе

Заключение

Список литературы

Приложение А. Доказательства теорем

А.1 Доказательство теоремы

А.2 Доказательство теоремы

А.3 Доказательство теоремы

А.4 Доказательство теоремы

Введение

Введение диссертации (часть автореферата) на тему «Помехоустойчивое кодирование в задачах достоверной и защищенной передачи данных»

Актуальность работы

Активное развитие вычислительной техники и информационных технологий, наблюдаемое в настоящий момент, приводит к все более стремительному усилению требований, предъявляемых к системам передачи информации. Основными требованиями, предъявляемыми к современным телекоммуникационным системам, являются: скорость (объем передаваемых данных на единицу времени), достоверность (вероятность корректного приема и обработки данных) и поддерживаемое число активных абонентов системы. Кроме того, по мере все большей цифровизации современного общества, также крайне актуальными становятся вопросы безопасности, то есть защищенной передачи данных по (в первую очередь) открытым каналам связи. Удовлетворение требований на скорость и достоверность невозможно без использования методов помехоустойчивого кодирования.

В ранних телекоммуникационных системах в качестве помеустойчивых кодов выступали, в первую очередь, алгебраические коды (например, коды БЧХ, Рида-Соломона, Рида-Маллера и др.), которые использовались совместно с их декодерами до половины кодового расстояния (Bounded Distance Decoder). Однако теория кодирования, основанная на алгебраических кодах c их декодированием до половины расстояния, уже не способна удовлетворять покрывать все сценарии использования современных систем обработки, передачи и хранения информации.

Вместе с тем, активный качественный скачок развития вычислительной техники, наблюдаемый с начала 1990-x, открыл возможность реализации длинных кодов, имплементация которых до этого была затруднительна. Именно новые доступные вычислительные мощности явились причиной активных исследований в области построения длинных кодов, для которых

существуют эффективные полиномиальные алгоритмы декодирования, практически реализующие декодирование по максимальному правдоподобию.

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

Как уже было отмечено выше, одним из ключевых требований, предъявляемым к современным телекоммуникационным системам, является достоверность (качество) передаваемых данных. Например, существующие на сегодняшний день, а также перспективные системы, использующие связь по оптоволокну, допускают потерю одного пакета данных из 1015. Это означает, что для выбора кода-кандидата, предлагаемого к использованию в такого рода системах, требуется провести не менее 1016 — 1018 итераций его моделирования, для получения требуемой вероятности ошибки на блок 10-15. Очевидно, что такого рода моделирование ведет с существенным временным и накладным расходам, а в некоторых случаях в принципе не реализуемо. В связи с этим особенно актуальной становится задача построения достаточно точных аналитических оценок, позволяющих оценить эффективность заданного кода без проведения или с минимальным объемом имитационного моделирования.

Решению задачи построения эффективных классов МПП-кодов, а так-

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

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

Дополнительное требование, которое с увеличением плотности сетей передачи данных, становится все более значимым, заключается в обеспечении возможности большому числу устройств/абонентов системы вести передачу данных на базовую станцию с заданным уровнем достоверности и задержки. Примером системы, где требование на число активных абонентов является определяющим, может послужить Интернет Вещей (допускается до одного миллиона устройств на квадратный километр). Понятно, что традиционные системы "точка-точка предполагающие одну линию связи между отправителем информации и ее получателем, будут неэффективны в такого рода сценариях. В связи с этим появилась необходимость разрабатывать методы неортогонального некоординированного множественного доступа, допускающую только синхронизацию блоков. Для анализа эффективности того или иного метода множественного доступа необходимо оценивать его пропускную спо-

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

Наконец, в последнее время все более критическим становится требование обеспечения безопасности передачи данных. Это связано с тем, что цифровые технологии все больше проникают в нашу жизнь, делая многие сферы жизнедеятельности человека, нормальное функционирование организаций и целых отраслей экономики зависимым от нормального функционирования ряда информационных систем и приложений. Следует отметить, что в настоящий момент проблема безопасности не только окончательно не решена, но в целых отраслях, таких, как Интернет Вещей, нет единого понимания того, каким образом следует организовывать защиту. Кроме того, определенную тревогу вызывает также и то, что подавляющее большинство традиционных методов защиты информации, передаваемой по открытым каналам связи, уже не могут считаться надежными, ввиду возможности их взлома с использованием квантового компьютера. В связи с этим становится актуальной разработка таких перспективных методов защиты данных, которые было бы достаточно легко имплементировать, но которые также бы не были скомпрометированы при помощи квантовых алгоритмов. Разработка постквантовых методов защиты информации, основанных на системе Мак-Элиса, была проведена в четвертой главе работы.

Существенный вклад в решение проблем построения семейств высокоэффективных кодов, разработки эффективных методов их кодирования, декодирования и исследования их свойств, разработки методов множественного доступа, а также проблемы иссследования и построения кодовых систем защиты информации, внесли в нашей стране В. Б. Афанасьев, А. М. Барг, Л. А. Бассылыго, Э. Л. Блох, С. В. Беззатеев, И. Е. Бочарова, Э. М. Габидулин,

И. И. Думер, К. Ш. Зигангиров, В. А. Зиновьев, В. В. Зяблов, Г. А. Каба-тянский, В. Д. Колесник, Е. А. Крук, Б. Д. Кудряшов, Е. Т. Мирончиков, Д. С. Осипов, М. С. Пинскер, Ю. Полянский, П. С. Рыбин, Ю. Л. Сагалович, В. М. Сидельников, В. Р. Сидоренко, Ф. И. Соловьева, П. В. Трифонов, С. В. Федоренко, А. А. Фролов, С. О. Шестаков, Н. А. Шехунова, за рубежом Э. Арикан, М. Балди, Э. Берлекэмп, Р. Блейхут, А. Варди, С. Джонсон, Р. Галлагер, В. Гурусвами, Т. Касами, Р. Кеттер, С. Кудекар, С. Кумар, Р. Мак-Элис, Дж. Месси, Т. Ричардсон, М. Судан, И. Тал, Т. Танака, Р. Урбанке, М. Фоссорье и многие другие.

Цель диссертационной работы

Классическая теория кодирования развивалась в направлении создания новых классов кодов, обладающих хорошими по отношению к границам параметрами (скоростью, спектром, кодовым расстоянием). Создаваемые алгоритмы декодирования были ориентированы на реализацию корректирующих возможностей этих кодов с возможно меньшей сложностью. Между тем развитие теории и техники использования кодов (связь, системы хранения данных, системы защиты информации) привело к постановке новой задачи совместного выбора кодов и методов декодирования, ориентированных на на использование в конкретной прикладной задаче, где модель передачи данных чаще всего не может быть описана метрическими методами.

Целью настоящей диссертационной работы является построение и анализ сигнально-кодовых конструкций и алгоритмов их декодирования для неметрических моделей каналов и сценариев передачи данных.

При этом объектами исследований являются линейные коды, системы множественного доступа и системы защиты информации, основанные на помехоустойчивых линейных кодах, а предметом исследований — методы построения линейных кодов и способы их декодирования, методы построения систем множественного доступа и оценки их пропускных способностей, а так-

же методы построения и анализа систем защиты информации, основанных на помехоустойчивых кодах.

Для достижения указанной цели в работе решаются следующие задачи:

1. Разработка новых конструкций кодов с малой плотностью проверок (МПП-кодов), основанных на комбинаторных конструкциях и матрицах перестановок, которые позволяют кодировать и декодировать данные коды с умеренной сложностью, а также оценка экспоненты вероятности ошибки некоторых регулярных конструкций МПП-кодов, при их фиксированной длине.

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

3. Постоение высокоэффективных и низкоресурсных схем декодирования полярных кодов, которые основаны на списочных алгоритмах с инвертированием информационных символов и быстром декодировании под-кодов полярных кодов.

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

5. Разработка методов обеспечения безопасной передачи данных в системах множественного доступа.

Научная новизна

В работе предложены новые конструкции МПП-кодов. Данные кодовые конструкции основаны на подходе, предполагающем одновременное использование двух конструкций: матрицы малого размера, построенной алгебраическими и/или комбинаторными методами и матриц перестановок, которые используются для получения требуемой длины кода. В частности, в качестве алгебраических конструкций в данной работе рассматриваются системы троек Штейнера, а также коды с повторением. С помощью данного подхода удалось построить новые семейства высокоскоростных (при использовании систем троек Штейнера) и низкоскоростных (при использовании кода с повторением) кодов, которые допускают эффективное хранением а также показывают высокую эффективность ( с точки зрения вероятности ошибки на блок в зависимости от отношения сигнал-шум) при их декодировании алгоритмом "распространения доверия". Кроме того, для регулярных МПП-кодов предложен новый подход оценки их экспоненты вероятности ошибки при декодировании по максимуму правдоподобия. Данный подход основан на использовании теоремы Хаймана, используемой для поиска корней полинома численными методами.

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

Предложен новый алгоритм декодирования полярных кодов, основанный на списочном декодировании с инвертированием символов и быстром списочном декодировании некоторых подкодов полярного кода. Данный ал-

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

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

Разработаны новые конструкции кодовых систем защиты информации с открытым ключом. Данные конструкции базируются на известной системе Мак-Элиса, основанной на трудной задаче декодирования линейного кода с произвольной структурой. Новым является подход к построению такого рода систем — в отличие от существующих подходов, основная идея которых состоит в замене кода Гоппы на другую кодовую конструкцию, позволяющую компактно описать публичный ключ, предложенный в диссертационной работе подход предполагает изменение самой структуры открытого ключа. Основной целью данного изменения является усложнение атаки по информационным совокупностям, которая для кодовых систем считается одной из наиболее эффективных. В диссертационной работе предложен ряд систем защиты информации, основанных на описанном выше подходе. Кроме того,

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

Все полученные результаты на момент их публикации являлись новыми.

Практическая значимость

Предложенные в работе конструкции МПП-кодов, алгоритмы декодирования и построения критического множества для полярных кодов могут быть использованы в существующих и перспективных системах передачи информации, в которых применяются помехоустойчивые коды. В частности, сценариями использования могут являться: передача данных со сверхмалой задержкой и высокой надежностью (ИКЬЬО) или усовершенстованная мобильная широкополосная связь (eMBB). Оба сценария передачи предусмотрены стандартом мобильной связи 50. Кроме того, предложенный алгоритм декодирования полярных кодов, обладая низкой задержкой, может претендовать на его внедрение в перспективные стандарты связи для сценариев, где требования на достоверность и задержку являются определяющими при выборе кодовой конструкции и алгоритма ее декодирования.

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

Предложенные в работе методы неортогонального множественного до-

ступа а также методы защиты информации на базе системы Мак-Элиса могут быть использованы для организации защищенной и надежной связи в системах передачи информации, где большое количество устройств не позволяет эффективно организовать ортогональный множественный доступ. Примером концепции, предусматривающей большое количество устройств и их неортогональный доступ к общему каналу связи является Интернет Вещей, а соответ-свтвующий сценарий передачи данных - массовое межмашинное взаимодействие (50 тМТС), предполагающее наличие до одного миллиона устройств на один квадратный километр. Кроме того, исследователи отмечают, что проблема безопасности — это один из ключевых факторов риска повсеместного внедрения Интернета Вещей [4], [5].

На защиту выносятся следующие основные результаты и положения:

1. Разработанный подход к построению МПП-кодов, который базируется на совместном использовании некоторой заданной алгебраической структуры (систем троек Штейнера, кодов с повторением) с детерминированными свойствами и матрицами перестановок позволяют получать ансамбли МПП-кодов с гарантированным минимальным расстоянием, что улучшает корректирующие характеристики кодов при малой вероятности ошибки.

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

3. Разработанный математический аппарат исследования свойств сверточ-

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

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

5. Быстрый алгоритм декодирования полярных кодов, основанный на построении критического множества инверсий информационных символов и быстром списочном декодировании некоторых специальных под-кодов полярных кодов, имеет эффективность посимвольного списочного декодера, но имеет при этом существенно меньшие пространственную и вычислительную сложности.

6. Предложенный метод организации некоординированного неортогонального множественного доступа в векторном дизъюнктивном канале позволяет некоординированно передавать короткие пакеты бит на базовую станцию с существенно большей пропускной способностью, чем слоти-рованная ALOHA.

7. Методы защиты информации, основанные на базе системы Мак-Эли-са, использующие модифицированные публичные ключи, затрудняющие их анализ с использованием декодирования по информационным совокупностям, обладают существенно меньшими длинами публичных ключей, чем в исходной системе Мак-Элиса.

Апробация работы

Основные результаты диссертации докладывались на следующих конференциях:

1. Международная конференция IEEE International Conference on Communications (2018, Канзас-сити, США). Тема доклада - "Signal-code construction based on interleaved reed-solomon codes for multiple access system over vector-disjunctive channel";

2. Международная конференция IEEE International Symposium on Information Theory and its Applications (2018, Сингапур). Тема доклада - "Novel signal-code construction for multiple access system over vector-disjunctive channel";

3. Международная конференция IEEE International Symposium on Information Theory and its Applications (2020, онлайн). Тема доклада -"Theoretical Estimates of Burst Error Probability for Convolutional Codes";

4. Международная конференция IEEE International Symposium on Information Theory and its Applications (2020, онлайн). Тема доклада -"Upper and Lower Estimates of Frame Error Rate for Convolutional Codes";

5. Международная конференция 16th Canadian Workshop on Information Theory (2019, Гамильтон, Канада). Тема доклада - "On the performance of slotted vector-disjunctive channel";

6. Международная конференция IEEE International Conference on Computer, Information and Telecommunication Systems (2019, Пекин, КНР). Тема доклада - "On the Asymptotic Capacity of Slotted Multiple Access Channel";

7. Международная конференция 1st International Workshop on Code-Based Cryptography (2020, онлайн). Тема доклада - "A new code-based cryptosystem";

8. Международная конференция IEEE International Black Sea Conference on Communications and Networking (2018, Батуми. Грузия). Тема доклада - "On the Maximal Achievable Rate for Signal-Code Construction Based on Interleaved Reed-Solomon Codes for Multiple Access System Over Vector-Disjunctive Channel";

9. Международная конференция IEEE International Black Sea Conference on Communications and Networking (2019, Сочи, Россия). Тема доклада - "Signal-Code Construction Based on Codes on Gilbert-Varshamov Bound for Multiple Access System over Vector-Disjunctive Channel";

10. Международная конференция 11th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (2019, Дублин, Ирландия). Тема доклада - "On the capacity estimation of a slotted multiuser communication channel";

11. Международная конференция XVI International Symposium"Problems of Redundancy in Information and Control Systems (2019, Москва, Россия). Тема доклада - "On the capacity estimation of a slotted multiuser communication channel with noise".

Кроме того, основные результаты диссертации были представлены на следующих семинарах:

1. Семинар по теории кодирования Института проблем передачи информации РАН (Москва, руковолитель - Л.А. Бассалыго);

2. Семинар по теории кодирования и кодовой криптографии Сколковского института науки и технологий (Сколтех) (Москва, руководитель - Г.А. Кабатянский);

3. Семинар "Коды, исправляющие ошибки, и постквантовая криптография" Института Электроники и Математики им. А. Н. Тихонова, Национального Исследовательского Университета Высшая Школа Экономики (Москва, руководитель - Е.А. Крук).

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

Материалы диссертации опубликованы в 18 печатных работах, из них 7 статей в рецензируемых журналах [6], [7], [8], [9], [10], [11], [12], 11 статей в сборниках трудов конференций [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23].

Личный вклад автора

Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Некоторые результаты получены совместно с соавторами (В. В. Зябловым, Е. А. Кру-ком, Г. А. Кабатянским, В. Р. Сидоренко, В. А. Мирошником, П. С. Рыби-ным, А. А. Смешко, А. А. Крещуком, В. Б. Афанасьевым, Н. Ю. Руменко, Н. М. Шевелем, В. С. Дыренковым), которым автор выражает свою искреннюю благодарность. В работе [6] все результаты были получены автором самостоятельно. В работе [8] автором была предложена идея использования теоремы Хаймана для оценки спектра регулярных МПП-кодов, а также получены численные результаты. В работе [9] автору принадлежит описание модели канала, а также все теоретические выкладки, численные результаты были получены соавторами. В работе [13] вклад автора состоял в формулировке и доказательстве теорем 17, 18, 19 а также в получении алгоритма восстановления стираний. В работах [14], [14], [11] автору принадлежит идея

использования спектра активных расстояний для исследования свойств свер-точных кодов, а также идеи доказательств основных теорем о распределении длин пакетов ошибок и оценки вероятности ошибки на блок. В работах [16] и [17] автором была поставлена задача исправления стираний, предложено использовать для этих целей перемеженные двоичные и коды Рида-Соломона, а также получены численные результаты. В работе [18] автором была поставлена задача оценки достижимой суммарной скорости передачи при использовании кодов, лежащих на границе Варшамова-Гилберта, а также предложена методика получения численных результатов. В работах [19], [20], [21], [22] автором были предложены методики оценки пропускной способности и получены все аналитические и численные результаты. В работе [23] автором был проведен анализ предложенных в работе систем, указаны их недостатки и предложены методы компенсации данных недостатков. В работе [10] автору принадлежит идея быстрого алгоритма декодирования полярных кодов с дополнительным инвертированием бит из критического множества. В работе [12] автору принадлежит общая постановка задачи полиномиального по сложности построения множества исправимых кодом ошибок, а также исследование системы защиты информации на базе двоичного образа обобщенных кодов Рида-Соломона.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, библиографии и приложения. Общий объем диссертации 330 страниц, включая 72 рисунка и 9 таблиц. Библиография включает 211 наименований на 24 страницах.

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

Список литературы диссертационного исследования доктор наук Иванов Федор Ильич, 2023 год

Список литературы

1. Zhilin IV, Kreshchuk AA, Zyablov VV. Generalized error-locating codes and minimization of redundancy for specified input and output error probabilities // Journal of Communications Technology and Electronics. — 2015. —Vol. 60, no. 6. —P. 695-706.

2. Yang Xueshi, Burd Gregory, Tang Heng et al. Encoding and decoding methods using generalized concatenated codes (GCC). — 2010. — Aug. 24. —US Patent 7,782,232.

3. Maevskii Aleksei Eduardovich, Gritsenko Vladimir, Shiyao XIAO, Chen Hong. Gel codeword structure encoding and decoding method, apparatus, and related device. — 2020. — Dec. 29. — US Patent 10,879,937.

4. Evaluating critical security issues of the IoT world: Present and future challenges / Mario Frustaci, Pasquale Pace, Gianluca Aloi, Gi-ancarlo Fortino // IEEE Internet of things journal. — 2017. — Vol. 5, no. 4. —P. 2483-2495.

5. Bekara Chakib. Security issues and challenges for the IoT-based smart grid // Procedia Computer Science. — 2014. — Vol. 34. — P. 532-537.

6. Иванов Ф. И., Зяблов В. В. Коды с малой плотностью проверок, основанные на системах троек Штейнера и матрицах перестановок. // Проблемы передачи информации. — 2013. — Т. 49, № 4. — С. 333-347.

7. Иванов Ф. И. Специальный класс квазициклических кодов с малой плотностью проверок, основанный на кодах с повторением и матрицах перестановок // Проблемы передачи информации. — 2017. — Т. 53, № 3. — С. 229-241.

8. Rybin PS, Ivanov FI. On estimation of the error exponent for finite length regular graph-based ldpc codes // Journal of Communications Technology and Electronics. —2018. —Vol. 63, no. 12. —P. 1518-1523.

9. Оценка пропускной способности многопользовательского векторного дизъюнктивного канала для произвольных входных распределений / В. С. Дыренков, Н. М. Шевель, Ф. И. Иванов, А. А. Крещук // Информационные процессы. — 2020. — Т. 20, № 2.— С. 133-141.

10. Ivanov F., Miroshnik V., Krouk E. Improved Generalized Successive Cancellation List Flip Decoder of Polar Codes with Fast Decoding of Special Nodes // Journal of Communications and Networks. — 2021. — Vol. 23. — P. 417-432.

11. Смешко А. А., Иванов Ф. И., Зяблов В. В. Теоретические и экспериментальные оценки сверху и снизу для эффективности сверточных кодов в двоичном симметричном канале. // Проблемы передачи информации. — 2022. —Т. 58, № 2. —С. 24-40.

12. О новых задачах в асимметричной криптографии, основанной на помехоустойчивом кодировании. / Ф. И. Иванов, В. В. Зяблов, Е. А. Крук, В. Р. Сидоренко // Проблемы передачи информации. — 2022. — Т. 58, № 2. —С. 92-111.

13. Ivanov Fedor, Kreshchuk Alexey, Zyablov Victor. On the local erasure correction capacity of convolutional codes // 2018 International Symposium on Information Theory and Its Applications (ISITA) / IEEE. — 2018. — P. 296-300.

14. Smeshko Anastasiia, Ivanov Fedor, Zyablov Victor. Upper and Lower Estimates of Frame Error Rate for Convolutional Codes // 2020 International Symposium on Information Theory and Its Applications (ISITA) / IEEE. —2020. —P. 160-164.

15. Smeshko Anastasiia, Ivanov Fedor, Zyablov Victor. Theoretical Estimates of Burst Error Probability for Convolutional Codes // 2020 International Symposium on Information Theory and Its Applications (ISITA) / IEEE. —2020. —P. 136-140.

16. Ivanov Fedor, Rybin Pavel. Signal-Code Construction Based on Interleaved Reed-Solomon Codes for Multiple Access System over Vector-Disjunctive Channel // 2018 IEEE International Conference on Communications Workshops (ICC Workshops) / IEEE.— 2018.— P. 1-5.

17. Ivanov Fedor, Rybin Pavel. Novel Signal-Code Construction for Multiple Access System over Vector-Disjunctive Channel // 2018 International Symposium on Information Theory and Its Applications (ISITA) / IEEE. —2018. —P. 560-564.

18. Smeshko Anastasiia, Ivanov Fedor. Signal-Code Construction Based on Codes on Gilbert-Varshamov Bound for Multiple Access System over Vector-Disjunctive Channel // 2019 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom) / IEEE. — 2019. —P. 1-3.

19. Ivanov Fedor, Rybin Pavel, Afanassiev Valentin. On the Performance of Slotted Vector-Disjunctive Channel // 2019 16th Canadian Workshop on Information Theory (CWIT) / IEEE.— 2019.— P. 1-5.

20. Ivanov Fedor, Rybin Pavel. On the Asymptotic Capacity of Slotted Multiple Access Channel // 2019 International Conference on Computer, Information and Telecommunication Systems (CITS) / IEEE. — 2019. — P. 1-5.

21. On the Capacity Estimation of a Slotted Multiuser Communication Channel with Noise / Fedor Ivanov, Pavel Rybin, Valentin Afanassiev, Alexey Kreschuk // 2019 XVI International Symposium" Problems of Redundancy in Information and Control Systems"(REDUNDANCY) / IEEE. —2019. —P. 27-31.

22. On the Capacity Estimation of a Slotted Multiuser Communication Channel / Fedor Ivanov, Alexey Kreshchuk, Pavel Rybin, Valentin Afanassiev // 2019 11th International Congress on Ultra Mod-

ern Telecommunications and Control Systems and Workshops (ICUMT) / IEEE. —2019. —P. 1-5.

23. A new code-based cryptosystem / Fedor Ivanov, Grigory Kabatiansky, Eugeny Krouk, Nikita Rumenko // Code-Based Cryptography Workshop / Springer. — 2020. — P. 41-49.

24. 5G: A tutorial overview of standards, trials, challenges, deployment, and practice / Mansoor Shafi, Andreas F Molisch, Peter J Smith et al. // IEEE journal on selected areas in communications. — 2017. — Vol. 35, no. 6.— P. 1201-1221.

25. Li Shancang, Da Xu Li, Zhao Shanshan. 5G Internet of Things: A survey // Journal of Industrial Information Integration. — 2018. — Vol. 10. — P. 1-9.

26. Da Xu Li, He Wu, Li Shancang. Internet of things in industries: A survey // IEEE Transactions on industrial informatics. — 2014. — Vol. 10, no. 4. —P. 2233-2243.

27. Wang Xuyu, Mao Shiwen, Gong Michelle X. An overview of 3GPP cellular vehicle-to-everything standards // GetMobile: Mobile Computing and Communications. —2017. —Vol. 21, no. 3. —P. 19-25.

28. Ahamed Md Maruf, Faruque Saleh. 5G backhaul: requirements, challenges, and emerging technologies // Broadband Communications Networks: Recent Advances and Lessons from Practice. — 2018. — Vol. 43.

29. Use cases and scenarios of 5G integrated satellite-terrestrial networks for enhanced mobile broadband: The SaT5G approach / Konstantinos Liolis, Alexander Geurtz, Ray Sperber et al. // International Journal of Satellite Communications and Networking. — 2019. — Vol. 37, no. 2. — P. 91-112.

30. Yuan Yifei, Zhao Xiaowu. 5G: Vision, scenarios and enabling technologies // ZTE communications. — 2015. — Vol. 13, no. 1. — P. 3-10.

31. A survey on non-orthogonal multiple access for 5G networks: Research

challenges and future trends / Zhiguo Ding, Xianfu Lei, George K Kara-giannidis et al. // IEEE Journal on Selected Areas in Communications. — 2017. —Vol. 35, no. 10. —P. 2181-2195.

32. Myung Hyung G, Lim Junsung, Goodman David J. Single carrier FDMA for uplink wireless transmission // IEEE Vehicular Technology Magazine. — 2006.—Vol. 1, no. 3. —P. 30-38.

33. Nelson Randolph, Kleinrock Leonard. Spatial TDMA: A collision-free multihop channel access protocol // IEEE Transactions on communications. —1985. —Vol. 33, no. 9. —P. 934-944.

34. Buranapanichkit Dujdow, Andreopoulos Yiannis. Distributed time-frequency division multiple access protocol for wireless sensor networks // IEEE wireless communications letters. — 2012. — Vol. 1, no. 5. — P. 440443.

35. Hara Shinsuke, Prasad Ramjee. Overview of multicarrier CDMA // IEEE communications Magazine. — 1997. — Vol. 35, no. 12. — P. 126-133.

36. A survey on mobile WiMAX [wireless broadband access] / Bo Li, Yang Qin, Chor Ping Low, Choon Lim Gwee // IEEE Communications magazine. — 2007. — Vol. 45, no. 12. — P. 70-75.

37. A tutorial on IEEE 802.11 ax high efficiency WLANs / Evgeny Khorov, Anton Kiryanov, Andrey Lyakhov, Giuseppe Bianchi // IEEE Communications Surveys & Tutorials. —2018. —Vol. 21, no. 1. —P. 197-216.

38. Bolton Walker, Xiao Yang, Guizani Mohsen. IEEE 802.20: mobile broadband wireless access // IEEE Wireless Communications. — 2007. — Vol. 14, no. 1. —P. 84-95.

39. Dahlman Erik, Parkvall Stefan, Skold Johan. 4G: LTE/LTE-advanced for mobile broadband. — Academic press, 2013.

40. Cover T. An achievable rate region for the broadcast channel // IEEE Transactions on Information Theory. — 1975. — Vol. 21, no. 4. — P. 399-

41. Abramson Norman. The ALOHA system: Another alternative for computer communications // Proceedings of the November 17-19, 1970, fall joint computer conference. — 1970. — P. 281-285.

42. Akyildiz Ian F, Wang Xudong. A survey on wireless mesh networks // IEEE Communications magazine.— 2005.— Vol. 43, no. 9. —P. S23-S30.

43. Power-domain non-orthogonal multiple access (NOMA) in 5G systems: Potentials and challenges / SM Riazul Islam, Nurilla Avazov, Octavia A Dobre, Kyung-Sup Kwak // IEEE Communications Surveys & Tutorials. —2016. —Vol. 19, no. 2. —P. 721-742.

44. An overview of the ATSC 3.0 physical layer specification / Luke Fay, Lachlan Michael, David Gómez-Barquero et al. // IEEE Transactions on Broadcasting. — 2016. — Vol. 62, no. 1. —P. 159-171.

45. Application of non-orthogonal multiple access in LTE and 5G networks / Zhiguo Ding, Yuanwei Liu, Jinho Choi et al. // IEEE Communications Magazine. —2017. —Vol. 55, no. 2. —P. 185-191.

46. Gallager Robert. Low-density parity-check codes // IRE Transactions on information theory. — 1962. — Vol. 8, no. 1. — P. 21-28.

47. MacKay David JC. Good error-correcting codes based on very sparse matrices // IEEE transactions on Information Theory. — 1999. — Vol. 45, no. 2. —P. 399-431.

48. Elias Peter. Coding for noisy channels // IRE Conv. Rec. — 1955.— Vol. 3. —P. 37-46.

49. Berrou Claude, Glavieux Alain, Thitimajshima Punya. Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1 // Proceedings of ICC'93-IEEE International Conference on Communications / IEEE.— Vol. 2. — 1993. — P. 1064-1070.

50. Benedetto Sergio, Montorsi Guido. Design of parallel concatenated con-

volutional codes // IEEE Transactions on Communications. — 1996. — Vol. 44, no. 5. —P. 591-600.

51. MacKay David JC, Mac Kay David JC. Information theory, inference and learning algorithms. — Cambridge university press, 2003.

52. Goldsmith Andrea. Wireless communications. — Cambridge university press, 2005.

53. Samimi Mathew K, Rappaport Theodore S. 3-D millimeter-wave statistical channel model for 5G wireless system design // IEEE Transactions on Microwave Theory and Techniques. — 2016. — Vol. 64, no. 7. — P. 22072225.

54. Meredith J. Study on channel model for frequency spectrum above 6 ghz // 3GPP TR 38.900, Jun, Tech. Rep. —2016.

55. Forney G David. Concatenated codes. — MIT Press, 1965.

56. Barg Alexander, Zemor Gilles. Error exponents of expander codes under linear-complexity decoding // SIAM Journal on Discrete Mathematics. — 2004. —Vol. 17, no. 3. —P. 426-445.

57. Kudekar Shrinivas, Richardson Tom, Urbanke Riidiger L. Spatially coupled ensembles universally achieve capacity under belief propagation // IEEE Transactions on Information Theory. — 2013.—Vol. 59, no. 12.— P. 7761-7813.

58. Arikan Erdal. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels // IEEE Transactions on Information Theory. — 2009. — Vol. 55, no. 7. — P. 30513073.

59. Reed-Muller codes achieve capacity on erasure channels / Shrini-vas Kudekar, Santhosh Kumar, Marco Mondelli et al. // IEEE Transactions on information theory. — 2017. — Vol. 63, no. 7. — P. 4298-4316.

60. Eroz Mustafa, Sun Feng-Wen, Lee Lin-Nan. DVB-S2 low density parity

check codes with near Shannon limit performance // International Journal of Satellite Communications and Networking. — 2004. — Vol. 22, no. 3. — P. 269-279.

61. Viterbi Andrew. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm // IEEE transactions on Information Theory. — 1967. — Vol. 13, no. 2. — P. 260-269.

62. Optimal decoding of linear codes for minimizing symbol error rate (cor-resp.) / Lalit Bahl, John Cocke, Frederick Jelinek, Josef Raviv // IEEE Transactions on information theory. — 1974. — Vol. 20, no. 2. — P. 284287.

63. Berrou Claude, Glavieux Alain. Near optimum error correcting coding and decoding: Turbo-codes // IEEE Transactions on communications. — 1996. —Vol. 44, no. 10. —P. 1261-1271.

64. An overview of turbo codes and their applications / Claude Berrou, Ramesh Pyndiah, Patrick Adde et al. // The European Conference on Wireless Technology, 2005. / IEEE.— 2005.— P. 1-9.

65. Omura J. On the Viterbi decoding algorithm // IEEE transactions on information theory. — 1969. — Vol. 15, no. 1. — P. 177-179.

66. Active distances for convolutional codes / Stefan Host, Rolf Johannesson, K Sh Zigangirov, Victor V. Zyablov // IEEE Transactions on Information Theory. — 1999. — Vol. 45, no. 2. — P. 658-669.

67. Tanner R. A recursive approach to low complexity codes // IEEE Transactions on information theory. — 1981. — Vol. 27, no. 5. — P. 533-547.

68. Richardson Thomas J, Shokrollahi Mohammad Amin, Urbanke Rüdiger L. Design of capacity-approaching irregular low-density parity-check codes // IEEE transactions on information theory. — 2001. — Vol. 47, no. 2.— P. 619-637.

69. Milenkovic Olgica, Prakash Kiran, Vasic Bane. Regular and irregular

low density parity check codes for iterative decoding based on cycle-invariant difference sets // PROCEEDINGS OF THE ANNUAL ALLERTON CONFERENCE ON COMMUNICATION CONTROL AND COMPUTING / The University; 1998. —Vol. 41. —2003. —P. 1700-1701.

70. MacKay David JC, Neal Radford M. Near Shannon limit performance of low density parity check codes // Electronics letters. — 1996. — Vol. 32, no. 18. —P. 1645-1646.

71. MacKay David JC, Wilson Simon T, Davey Matthew C. Comparison of constructions of irregular Gallager codes // IEEE Transactions on Communications. — 1999. — Vol. 47, no. 10. — P. 1449-1454.

72. Fossorier Marc PC. Quasicyclic low-density parity-check codes from circulant permutation matrices // IEEE transactions on information theory. — 2004. —Vol. 50, no. 8. —P. 1788-1793.

73. Okamura Toshihiko. Designing LDPC codes using cyclic shifts // IEEE International Symposium on Information Theory, 2003. Proceedings. / IEEE. —2003. —P. 151.

74. Vasic Bane, Pedagani Karunakar, Ivkovic Milos. High-rate girth-eight low-density parity-check codes on rectangular integer lattices // IEEE Transactions on Communications. — 2004. — Vol. 52, no. 8. — P. 12481252.

75. Hagiwara Manabu. On the Minimal Length of Quasi Cycilc LDPC Codes with Girth greater than or equal to 6 // ISITA2006, Seoul, Korea, October 29-Novenber 1. —2006.

76. Wang Yige, Yedidia Jonathan S, Draper Stark C. Construction of high-girth QC-LDPC codes // 2008 5th International Symposium on Turbo Codes and Related Topics / IEEE.— 2008.— P. 180-185.

77. Milenkovic Olgica, Kashyap Navin, Leyba David. Shortened array codes of large girth // IEEE Transactions on Information Theory. — 2006. —

Vol. 52, no. 8. —P. 3707-3722.

78. Gabidulin Ernst, Moinian Abdi, Honary Bahram. Generalized construction of quasi-cyclic regular LDPC codes based on permutation matrices // 2006 IEEE International Symposium on Information Theory / IEEE. — 2006. —P. 679-683.

79. Zhang Haotian, Moura Jose MF. The design of structured regular LDPC codes with large girth // GL0BEC0M'03. IEEE Global Telecommunications Conference (IEEE Cat. No. 03CH37489) / IEEE.— Vol. 7.— 2003. — P. 4022-4027.

80. Quasi-Cyclic Low-Density Parity-Check Codes With Girth Larger Than 12 / Sunghwan Kim, Jong-Seon No, Habong Chung, Dong-Joon Shin // IEEE Transactions on Information Theory. — 2007. — Vol. 53, no. 8. — P. 2885-2891.

81. Esmaeili M, Gholami M. Structured quasi-cyclic LDPC codes with girth 18 and column-weight J=3 // AEU-International Journal of Electronics and Communications. —2010. —Vol. 64, no. 3. —P. 202-217.

82. Zhang Guohua, Sun Rong, Wang Xinmei. Construction of girth-eight QC-LDPC codes from greatest common divisor // IEEE Communications Letters. —2013. —Vol. 17, no. 2. —P. 369-372.

83. Myung Seho, Yang Kyeongcheol, Kim Jaeyoel. Quasi-cyclic LDPC codes for fast encoding // IEEE Transactions on Information Theory. — 2005. — Vol. 51, no. 8. —P. 2894-2901.

84. Richardson Thomas J, Urbanke Rüdiger L. Efficient encoding of low-density parity-check codes // IEEE transactions on information theory. — 2001. —Vol. 47, no. 2. —P. 638-656.

85. Groshev FV, Zyablov VV, Potapov VG. Low-complexity decoded LDPC Codes with Reed-Solomon constituent codes // Proc. 11th Int. Work shop on Algebraic and Combinatorial Coding Theory ACCT'08, Pomporovo,

Bulgaria, June 16-22. — 2008.

86. Savin Valentin. Self-corrected min-sum decoding of LDPC codes // 2008 IEEE International Symposium on Information Theory / IEEE. — 2008. —P. 146-150.

87. Kschischang Frank R, Frey Brendan J, Loeliger H-A. Factor graphs and the sum-product algorithm // IEEE Transactions on information theory. — 2001. —Vol. 47, no. 2. —P. 498-519.

88. Adaptive-normalized/offset min-sum algorithm / Xiaofu Wu, Yue Song, Ming Jiang, Chunming Zhao // IEEE communications letters. — 2010. — Vol. 14, no. 7. —P. 667-669.

89. Lentmaier Michael, Zigangirov K Sh. On generalized low-density parity-check codes based on Hamming component codes // IEEE communications letters. —1999. —Vol. 3, no. 8. —P. 248-250.

90. A class of low-density parity-check codes constructed based on ReedSolomon codes with two information symbols / Ivana Djurdjevic, Jun Xu, Khaled Abdel-Ghaffar, Shu Lin // International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes / Springer. — 2003. —P. 98-107.

91. Yi Yu, Shaobo Liu, Dawei Huang. Construction of LDPC codes based on narrow-sense-primitive BCH codes // 2005 IEEE 61st Vehicular Technology Conference / IEEE. —Vol. 3. —2005. —P. 1571-1574.

92. Baldi Marco, Cancellieri Giovanni, Chiaraluce Franco. Array convolu-tional low-density parity-check codes // IEEE Communications Letters. — 2014. —Vol. 18, no. 2. —P. 336-339.

93. Ling Alan CH. Difference triangle sets from affine planes // IEEE Transactions on Information Theory. — 2002.— Vol. 48, no. 8. —P. 2399-2401.

94. Short quasi-cyclic LDPC codes from convolutional codes / Irina E Bocharova, Boris D Kudryashov, Roman V Satyukov,

Stephan Stiglmayry // 2009 IEEE International Symposium on Information Theory / IEEE. —2009. —P. 551-555.

95. Huang Chun-Ming, Huang Jen-Fa, Yang Chao-Chin. Construction of quasi-cyclic LDPC codes from quadratic congruences // IEEE communications Letters. — 2008. — Vol. 12, no. 4. —P. 313-315.

96. Lu Jin, Moura Jose MF, Niesen Urs. Grouping-and-shifting designs for structured LDPC codes with large girth // International Symposium on-Information Theory, 2004. ISIT 2004. Proceedings. / IEEE. — 2004. — P. 236.

97. Ivanov FI, Zyablov VV, Potapov VG. Low-density parity-check codes based on Galois fields // Journal of Communications Technology and Electronics. — 2012.—Vol. 57, no. 8. —P. 857-867.

98. Kou Yu, Lin Shu, Fossorier Marc PC. Low-density parity-check codes based on finite geometries: a rediscovery and new results // IEEE Transactions on Information theory. — 2001. — Vol. 47, no. 7. — P. 2711-2736.

99. Johnson Sarah. Low-density parity-check codes from combinatorial designs. — Citeseer, 2003.

100. Johnson Sarah J, Weller Steven R. Regular low-density parity-check codes from combinatorial designs // Proceedings 2001 IEEE Information Theory Workshop (Cat. No. 01EX494) / IEEE. — 2001. — P. 90-92.

101. Liva Gianluigi, Ryan William E, Chiani Marco. Quasi-cyclic generalized LDPC codes with low error floors // IEEE Transactions on Communications. — 2008.—Vol. 56, no. 1. —P. 49-57.

102. Djidjev Hristo N. A faster algorithm for computing the girth of planar and bounded genus graphs // ACM Transactions on Algorithms (TALG).— 2010. —Vol. 7, no. 1. —P. 1-16.

103. Girth analysis of Tanner's (3, 5) QC LDPC codes / Sunghwan Kim, Jong-Seon No, Habong Chung, Dong-Joon Shin // Proceedings. International

Symposium on Information Theory, 2005. ISIT 2005. / IEEE. —2005.— P. 1632-1636.

104. Wu Xiaofu, You Xiaohu, Zhao Chunming. An efficient girth-locating algorithm for quasi-cyclic LDPC codes // 2006 IEEE International Symposium on Information Theory / IEEE. — 2006. — P. 817-820.

105. Protograph-based raptor-like LDPC codes / Tsung-Yi Chen, Kasra Vak-ilinia, Dariush Divsalar, Richard D Wesel // IEEE Transactions on Communications. — 2015.—Vol. 63, no. 5. —P. 1522-1532.

106. Low-rate PBRL-LDPC codes for URLLC in 5G / Xiaoning Wu, Ming Jiang, Chunming Zhao et al. // IEEE Wireless Communications Letters. —2018. —Vol. 7, no. 5. —P. 800-803.

107. Low-complexity LDPC decoder for 5G URLLC / Jian-Cheng Liu, Huan-Chun Wang, Chung-An Shen, Jih-Wei Lee // 2018 IEEE Asia Pacific Conference on Postgraduate Research in Microelectronics and Electronics (PrimeAsia) / IEEE. — 2018. — P. 43-46.

108. Gamage Heshani, Rajatheva Nandana, Latva-Aho Matti. Channel coding for enhanced mobile broadband communication in 5G systems // 2017 European conference on networks and communications (EuCNC) / IEEE. — 2017. —P. 1-6.

109. On the performance of polar codes for 5G eMBB control channel / Seyyed Ali Hashemi, Carlo Condo, Furkan Ercan, Warren J Gross // 2017 51st Asilomar Conference on Signals, Systems, and Computers / IEEE. — 2017. —P. 1764-1768.

110. Tsatsaragkos Ioannis, Paliouras Vassilis. A reconfigurable LDPC decoder optimized for 802.11 n/ac applications // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. — 2017. — Vol. 26, no. 1. — P. 182-195.

111. Dielissen John, Hekstra Andries, Berg Vincent. Low cost LDPC decoder

for DVB-S2 // Proceedings of the Design Automation & Test in Europe Conference / IEEE. — Vol. 2. — 2006. — P. 1-6.

112. Wiberg Niclas. Codes and decoding on general graphs. — 1996.

113. Zhao Jianguang, Zarkeshvari Farhad, Banihashemi Amir H. On implementation of min-sum algorithm and its modifications for decoding low-density parity-check (LDPC) codes // IEEE transactions on communications. — 2005. —Vol. 53, no. 4. —P. 549-554.

114. Ivanov FI, Zyablov VV, Potapov VG. The score of the minimum length of cycles in generalized quasi-cyclic regular LDPC codes // Proc. 13th Int. Workshop on Algebraic and Combinatorial Coding Theory (ACCT-13), Pomorie, Bulgaria. — 2012. — P. 162-167.

115. Xiao Hua, Banihashemi Amir H. Improved progressive-edge-growth (PEG) construction of irregular LDPC codes // IEEE Communications Letters. —2004. —Vol. 8, no. 12. —P. 715-717.

116. Hu Xiao-Yu, Eleftheriou Evangelos, Arnold Dieter-Michael. Regular and irregular progressive edge-growth tanner graphs // IEEE Transactions on Information Theory. — 2005.— Vol. 51, no. 1. —P. 386-398.

117. Construction of irregular LDPC codes with low error floors / Tao Tian, Chris Jones, John D Villasenor, Richard D Wesel // IEEE International Conference on Communications, 2003. ICC'03. / IEEE. — Vol. 5. — 2003. —P. 3125-3129.

118. Vukobratovic Dejan, Djurendic Aleksandar, Senk Vojin. ACE spectrum of LDPC codes and generalized ACE design // 2007 IEEE International Conference on Communications / IEEE. — 2007. — P. 665-670.

119. Riordan John. Introduction to combinatorial analysis. — Courier Corporation, 2012.

120. Noor-A-Rahim Md, Nguyen Khoa D, Lechner Gottfried. Finite length analysis of LDPC codes // 2014 IEEE Wireless Communications and Net-

working Conference (WCNC) / IEEE.— 2014.— P. 206-211.

121. Finite-length analysis of low-density parity-check codes on the binary erasure channel / Changyan Di, David Proietti, I Emre Telatar et al. // IEEE Transactions on Information theory. — 2002. — Vol. 48, no. 6.— P. 1570-1579.

122. Richardson T, Urbanke R. Finite-length density evolution and the distribution of the number of iterations for the binary erasure channel // unpublished.[Online]. Available: http://lthcwww. epfl. ch/RiU02. ps.—

2003.

123. Zhang Junan, Orlitsky Alon. Finite-length analysis of LDPC codes with large left degrees // Proceedings IEEE International Symposium on Information Theory, / IEEE. — 2002. — P. 3.

124. Johnson Sarah J. A finite-length algorithm for LDPC codes without repeated edges on the binary erasure channel // IEEE transactions on information theory. —2008. —Vol. 55, no. 1. —P. 27-32.

125. Burshtein David, Miller Gadi. Asymptotic enumeration methods for analyzing LDPC codes // IEEE Transactions on Information Theory. —

2004. —Vol. 50, no. 6. —P. 1115-1131.

126. Rybin Pavel. On the error-correcting capabilities of low-complexity decoded irregular LDPC codes // 2014 IEEE International Symposium on Information Theory / IEEE. — 2014. — P. 3165-3169.

127. Wilf Herbert S. generatingfunctionology. — CRC press, 2005.

128. Блох Э. Л., Зяблов В. В. Линейные каскадные коды // Москва, СССР: Наука. —1982.

129. Polyanskiy Yury, Poor H Vincent, Verdu Sergio. Channel coding rate in the finite blocklength regime // IEEE Transactions on Information Theory. —2010. —Vol. 56, no. 5. —P. 2307-2359.

130. Miller RL, Deutsch LJ, Butman SA. On the error statistics of Viterbi de-

coding and the performance of concatenated codes // JPL Publication. — 1981. —Vol. 8. —P. 1-9.

131. Justesen J0rn, Andersen Jakob Dahl. Critical lengths of error events in convolutional codes // IEEE Transactions on Information Theory. — 1998. —Vol. 44, no. 4. —P. 1608-1611.

132. Зяблов В. В., Йоханненсон Р., Павлюшков В. В. Обнаруживающие и корректирующие способности сверточных кодов // Проблемы передачи информации.— 2004.— Т. 40, №3. —С. 187-194.

133. Thommesen Christian, Justesen J0rn. Bounds on distances and error exponents of unit memory codes // IEEE Transactions on Information Theory. — 1983.—Vol. 29, no. 5. —P. 637-649.

134. Johannesson Rolf, Zigangirov Kamil Sh. Fundamentals of convolutional coding. — John Wiley & Sons, 2015.

135. Cyclic linear binary locally repairable codes / Pengfei Huang, Ei-tan Yaakobi, Hironori Uchikawa, Paul H. Siegel // 2015 IEEE Information Theory Workshop (ITW). —IEEE, 2015. —Apr.

136. Linear locally repairable codes with availability / Pengfei Huang, Ei-tan Yaakobi, Hironori Uchikawa, Paul H. Siegel // 2015 IEEE International Symposium on Information Theory (ISIT). — IEEE, 2015. — Jun.

137. Epstein Marvin A. Algebraic decoding for a binary erasure channel. — 1958.

138. Analysis of using convolutional codes to recover packet losses over burst erasure channels / M. Arai, A. Yamamoto, A. Yamaguchi et al. // Proceedings 2001 Pacific Rim International Symposium on Dependable Computing.— IEEE Comput. Soc.

139. Tomas Virtudes, Rosenthal Joachim, Smarandache Roxana. Decoding of Convolutional Codes Over the Erasure Channel. — 2012. —jan. — Vol. 58, no. 1. —P. 90-108.

140. Active distances for convolutional codes / S. Host, R. Johannesson, K.Sh. Zigangirov, V.V. Zyablov. — 1999. — mar. — Vol. 45, no. 2. — P. 658-669.

141. Huth G., Weber C. Minimum weight convolutional codewords of finite length (Corresp.). —1976. —mar. —Vol. 22, no. 2. —P. 243-246.

142. Jordan R., Pavlushkov V., Zyablov V.V. Maximum Slope Convolutional Codes. —2004. —oct. —Vol. 50, no. 10. —P. 2511-2522.

143. MCC Support. Final Minutes Report RAN1#87. — 2017. — feb.

144. Tal Ido, Vardy Alexander. List decoding of polar codes // Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on / IEEE. —2011. —P. 1-5.

145. Niu Kai, Chen Kai. CRC-aided decoding of polar codes // IEEE Communications Letters. —2012. —Vol. 16, no. 10. —P. 1668-1671.

146. Alamdar-Yazdi Amin, Kschischang Frank R. A simplified successive-cancellation decoder for polar codes // IEEE communications letters. — 2011. —Vol. 15, no. 12. —P. 1378-1380.

147. Fast polar decoders: Algorithm and implementation / Gabi Sarkis, Pascal Giard, Alexander Vardy et al. // IEEE Journal on Selected Areas in Communications. —2014. —Vol. 32, no. 5. —P. 946-957.

148. Hanif Muhammad, Ardakani Masoud. Fast successive-cancellation decoding of polar codes: Identification and decoding of new nodes // IEEE Communications Letters.— 2017.— Vol. 21, no. 11. —P. 2360-2363.

149. Hashemi Seyyed Ali, Condo Carlo, Gross Warren J. Simplified successive-cancellation list decoding of polar codes // 2016 IEEE International Symposium on Information Theory (ISIT) / IEEE. — 2016. — P. 815-819.

150. Giard Pascal, Burg Andreas. Fast-SSC-flip decoding of polar codes // 2018 IEEE Wireless Communications and Networking Conference Workshops (WCNCW) / IEEE. —2018. —P. 73-77.

151. Hashemi Seyyed Ali, Condo Carlo, Gross Warren J. Fast and flexible successive-cancellation list decoders for polar codes // IEEE Transactions on Signal Processing. — 2017. — Vol. 65, no. 21. — P. 5756-5769.

152. Afisiadis Orion, Balatsoukas-Stimming Alexios, Burg Andreas. A low-complexity improved successive cancellation decoder for polar codes // 2014 48th Asilomar Conference on Signals, Systems and Computers / IEEE. —2014. —P. 2116-2120.

153. Ercan Furkan, Gross Warren J. Fast thresholded SC-flip decoding of polar codes // ICC 2020-2020 IEEE International Conference on Communications (ICC) / IEEE. — 2020. — P. 1-7.

154. Bit-flip algorithm for successive cancellation list decoder of polar codes / Fengyi Cheng, Aijun Liu, Yingxian Zhang, Jing Ren // IEEE Access. — 2019. —Vol. 7. —P. 58346-58352.

155. Mori Ryuhei, Tanaka Toshiyuki. Performance of polar codes with the construction using density evolution // IEEE Communications Letters. — 2009. —Vol. 13, no. 7.

156. Tal Ido, Vardy Alexander. How to construct polar codes // IEEE Transactions on Information Theory. — 2013. — Vol. 59, no. 10. — P. 6562-6582.

157. Balatsoukas-Stimming Alexios, Parizi Mani Bastani, Burg Andreas. LLR-based successive cancellation list decoding of polar codes // IEEE transactions on signal processing. — 2015. — Vol. 63, no. 19. — P. 5165-5179.

158. Hardware architecture for list successive cancellation decoding of polar codes / Alexios Balatsoukas-Stimming, Alexandre J Raymond, Warren J Gross, Andreas Burg // IEEE Transactions on Circuits and Systems II: Express Briefs. — 2014.— Vol. 61, no. 8. —P. 609-613.

159. Low complexity list decoding for polar codes with multiple CRC codes / Jong-Hwan Kim, Sang-Hyo Kim, Ji-Woong Jang, Young-Sik Kim // entropy. — 2017.—Vol. 19, no. 4. —P. 183.

160. Condo Carlo, Bioglio Valerio, Land Ingmar. Generalized fast decoding of polar codes // 2018 IEEE Global Communications Conference (GLOBE-COM) / IEEE. —2018. —P. 1-6.

161. Fast list decoders for polar codes / Gabi Sarkis, Pascal Giard, Alexander Vardy et al. // IEEE Journal on Selected Areas in Communications. — 2015. —Vol. 34, no. 2. —P. 318-328.

162. Chandesris Ludovic, Savin Valentin, Declercq David. Dynamic-SCFlip decoding of polar codes // IEEE Transactions on Communications. — 2018. —Vol. 66, no. 6. —P. 2333-2345.

163. Progressive bit-flipping decoding of polar codes over layered critical sets / Zhaoyang Zhang, Kangjian Qin, Liang Zhang et al. // GLOBECOM 20172017 IEEE Global Communications Conference / IEEE. — 2017. — P. 1-6.

164. Rowshan Mohammad, Viterbo Emanuele. Shifted Pruning for List Decoding of Polar Codes // arXiv preprint arXiv:2001.10732. — 2020.

165. Deep-Learning-Aided Successive-Cancellation Decoding of Polar Codes / Seyyed Ali Hashemi, Nghia Doan, Thibaud Tonnellier, Warren J Gross // 2019 53rd Asilomar Conference on Signals, Systems, and Computers / IEEE. —2019. —P. 532-536.

166. Chen Chun-Hsiang, Teng Chieh-Fang, Wu An-Yeu Andy. Low-complexity LSTM-assisted bit-flipping algorithm for successive cancellation list polar decoder // ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) / IEEE.— 2020.— P. 17081712.

167. Pan Yi-Han, Wang Chuang-Hsuan, Ueng Yeong-Luh. Generalized SCL-Flip Decoding of Polar Codes // Global Communications Conference (GLOBECOM), 2020 IEEE / IEEE.— 2020.— P. 1-6.

168. Bioglio Valerio, Condo Carlo, Land Ingmar. Design of polar codes in 5G new radio // IEEE Communications Surveys & Tutorials. — 2020.

169. Aurora Harsh, Condo Carlo, Gross Warren J. Low-complexity software stack decoding of polar codes // 2018 IEEE International Symposium on Circuits and Systems (ISCAS) / IEEE.— 2018.— P. 1-5.

170. Rimoldi Bixio, Urbanke Rudiger. A rate-splitting approach to the Gaussian multiple -access channel // IEEE Transactions on Information Theory. — 1996.—Vol. 42, no. 2. —P. 364-375.

171. Interleave division multiple -access / Li Ping, Lihai Liu, Keying Wu, Wai Kong Leung // IEEE transactions on wireless communications. — 2006. —Vol. 5, no. 4. —P. 938-947.

172. Cohen A, Heller J, Viterbi A. A new coding technique for asynchronous multiple access communication // IEEE Transactions on Communication Technology. — 1971. — Vol. 19, no. 5. — P. 849-855.

173. Осипов Д. С., Фролов А. А., Зяблов В. В. Система множественного доступа для векторного дизъюнктивного канала. // Проблемы передачи информации.— 2012.— Т. 48, № 3. —С. 243-249.

174. On a multiple-access in a vector disjunctive channel / Alexey Frolov, Victor Zyablov, Vladimir Sidorenko, Robert Fischer // 2013 IEEE International Symposium on Information Theory / IEEE. — 2013. — P. 211-215.

175. Chang Shih-Chun, Wolf J. On the T-user M-frequency noiseless multiple-access channel with and without intensity information // IEEE Transactions on Information Theory. — 1981. — Vol. 27, no. 1. — P. 41-48.

176. Wilhelmsson L, Zigangirov Kamil'Shamil'evich. On the asymptotic capacity of a multiple -access channel // Problemy Peredachi Informatsii. — 1997. —Vol. 33, no. 1. —P. 12-20.

177. Bassalygo Leonid Alexandrovich, Pinsker Mark Semenovich. Evaluation of the asymptotics of the summarized capacity of an m-frequency t-user noiseless multiple -access channel // Problemy Peredachi Informatsii. — 2000. —Vol. 36, no. 2. —P. 3-9.

178. Vinck AJ Han, Keuning K Jeroen. On the capacity of the asynchronous T-user M-frequency noiseless multiple -access channel without intensity information // IEEE Transactions on Information Theory. — 1996.—Vol. 42, no. 6. —P. 2235-2238.

179. Schmidt Georg, Sidorenko Vladimir R, Bossert Martin. Collaborative decoding of interleaved Reed-Solomon codes and concatenated code designs // IEEE Transactions on Information Theory. — 2009. — Vol. 55, no. 7. —P. 2991-3012.

180. Puchinger Sven, ne Nielsen Johan Rosenkilde. Decoding of interleaved Reed-Solomon codes using improved power decoding // 2017 IEEE International Symposium on Information Theory (ISIT) / IEEE. — 2017. — P. 356-360.

181. Wachter-Zeh Antonia, Zeh Alexander, Bossert Martin. Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability // Designs, Codes and Cryptography. — 2014. — Vol. 71, no. 2.— P. 261-281.

182. Massey James. Shift-register synthesis and BCH decoding // IEEE transactions on Information Theory. — 1969. — Vol. 15, no. 1. — P. 122-127.

183. McEliece Robert J. The guruswami-sudan decoding algorithm for reedsolomon codes // IPN progress report. — 2003. — Vol. 42, no. 153.

184. Horn Gavin B, Karp RM. A maximum likelihood polynomial time syndrome decoder to correct linearly independent errors // Proceedings. 2001 IEEE International Symposium on Information Theory (IEEE Cat. No. 01CH37252) / IEEE. —2001. —P. 87.

185. McEliece Robert J. A public-key cryptosystem based on algebraic // Coding Thv. — 1978.—Vol. 4244. —P. 114-116.

186. Kabatianskii Gregory, Krouk Evgenii, Smeets Ben. A digital signature scheme based on random error-correcting codes // IMA International Con-

ference on Cryptography and Coding / Springer. — 1997. — P. 161-167.

187. Rivest Ronald L, Shamir Adi, Adleman Leonard. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. —1978. —Vol. 21, no. 2. —P. 120-126.

188. ElGamal Taher. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE transactions on information theory. — 1985. —Vol. 31, no. 4. —P. 469-472.

189. Veron Pascal. Code based cryptography and steganography // International Conference on Algebraic Informatics / Springer. — 2013. — P. 9-46.

190. Reducing key length of the McEliece cryptosystem / Thierry P Berger, Pierre-Louis Cayrel, Philippe Gaborit, Ayoub Otmani // International Conference on Cryptology in Africa / Springer. — 2009. — P. 77-97.

191. Algebraic cryptanalysis of McEliece variants with compact keys / JeanCharles Faugere, Ayoub Otmani, Ludovic Perret, Jean-Pierre Tillich // Annual International Conference on the Theory and Applications of Cryptographic Techniques / Springer. — 2010. — P. 279-298.

192. Kocher Paul C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems // Annual International Cryptology Conference / Springer. — 1996. — P. 104-113.

193. Barker Elaine, Dang Quynh. Nist special publication 800-57 part 1, revision 4 // NIST, Tech. Rep. — 2016.— Vol. 16.

194. Report on post-quantum cryptography / Lily Chen, Lily Chen, Stephen Jordan et al. — US Department of Commerce, National Institute of Standards and Technology, 2016. — Vol. 12.

195. Shor Peter W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM review. —1999. — Vol. 41, no. 2. —P. 303-332.

196. Berlekamp Elwyn, McEliece Robert, Van Tilborg Henk. On the inherent

intractability of certain coding problems (corresp.) // IEEE Transactions on Information Theory. — 1978.— Vol. 24, no. 3. —P. 384-386.

197. A survey of lightweight-cryptography implementations / Thomas Eisenbarth, Sandeep Kumar, Christof Paar et al. // IEEE Design & Test of Computers. —2007. —Vol. 24, no. 6. —P. 522-533.

198. Ivanov Fedor, Krouk Evgenii, Kreshchuk Alexey. On the Lightweight McEliece Cryptosystem for Low-Power Devices // 2019 XVI International Symposium" Problems of Redundancy in Information and Control Sys-tems"(REDUNDANCY) / IEEE. — 2019.— P. 133-138.

199. MDPC-McEliece: New McEliece variants from moderate density parity-check codes / Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, Paulo SLM Barreto // 2013 IEEE international symposium on information theory / IEEE. —2013. —P. 2069-2073.

200. Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem / Marco Baldi, Franco Chiaraluce, Roberto Garello, Francesco Mininni // 2007 IEEE International Conference on Communications / IEEE. — 2007. — P. 951-956.

201. May Alexander, Meurer Alexander, Thomae Enrico. Decoding Random Linear Codes in (9(20 054n) // International Conference on the Theory and Application of Cryptology and Information Security / Springer. — 2011. — P. 107-124.

202. Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding / Anja Becker, Antoine Joux, Alexander May, Alexander Meurer // Annual international conference on the theory and applications of cryptographic techniques / Springer. — 2012. — P. 520536.

203. Barg Alexander, Krouk Evgueni, van Tilborg Henk CA. On the complexity of minimum distance decoding of long linear codes // IEEE Transactions

on Information Theory. — 1999.— Vol. 45, no. 5. —P. 1392-1405.

204. Крук Е. А. Граница для сложности декодирования линейных блоковых кодов // Проблемы передачи информации. — 1989. — Т. 25, № 3. — С. 103-107.

205. Сидельников В. М., Шестаков С. О. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона // Дискретная математика. — 1992. — Т. 4, № 3. — С. 57-63.

206. Bernstein Daniel J, Lange Tanja, Peters Christiane. Attacking and defending the McEliece cryptosystem // International Workshop on PostQuantum Cryptography / Springer. — 2008. — P. 31-46.

207. Lee Pil Joong, Brickell Ernest F. An observation on the security of McEliece's public-key cryptosystem // Workshop on the Theory and Application of of Cryptographic Techniques / Springer. — 1988. — P. 275280.

208. Leon Jeffrey S. A probabilistic algorithm for computing minimum weights of large error-correcting codes // IEEE Transactions on Information Theory. —1988. —Vol. 34, no. 5. —P. 1354-1359.

209. Stern Jacques. A method for finding codewords of small weight // International colloquium on coding theory and applications / Springer. — 1988. —P. 106-113.

210. Wagner David. A generalized birthday problem // Annual International Cryptology Conference / Springer. — 2002. — P. 288-304.

211. Grover Lov K. Quantum computers can search arbitrarily large databases by a single query // Physical review letters. — 1997. — Vol. 79, no. 23. — P. 4709.

Приложение А Доказательства теорем

А.1 Доказательство теоремы 1.3.4

Доказательство. В доказательстве будем полагать, что все сравнения выполняются по модулю т.

Пусть u Е С и w(u) = 4. Ясно, что если u состоит только из двух ненулевых векторов u 1j1, u,;2j2 Е F™, то w(u 1j1) = w(u,;2j2) = 2, кроме того, эти векторы должны входить в один синдром Sj. Без ограничения общности можно считать, что i = 1 и u i 1j1 = un, u 1j1 = u12. Тогда для того, чтобы Si = 0, необходимо и достаточно, чтобы

u11 = \ 12-р и u12 u11 = Ip14-p13 u12 или

112-Р 11 u12 = 114-P13 u12,

откуда

u12 = Ipu12,

где

P = (P14 - Р13) - (P12 - Pn).

Отсутствие циклов длины 4 гарантирует, что р ф 0 mod т. C другой стороны, так как т — простое, то u12 = Ii,u12 только тогда, когда w(u12) = т.

Доказательства для случая, когда u состоит из трех ненулевых векторов: двух векторов веса 1 и одного вектора веса 2 и случая, когда u состоит из четырех векторов веса 1, очевидны и будут опущены. Таким образом, согласно теореме 1.3.4, dmn(C) > 6.

Теперь покажем, что С не содержит слов веса 6. Очевидно, что если и (»(и) = 6) состоит из £ ненулевых векторов, причем среди них найдется такой вектор, что его вес больше суммы весов всех остальных £ — 1 векторов, то такое слово и не будет являться кодовым.

Ситуация, когда и состоит только из двух ненулевых векторов

и- и- • Р Fm

и Ш , и г 2 ] 2 Е 2

была рассмотрена выше.

Рассуждения для случаев, когда £ = 3,4,6 очевидны и опущены в доказательстве.

Пусть Ь = 5. Тогда и состоит из четырех векторов и^, и2j2, и {3^3, иЕ F т веса 1 и одного вектора и iвеса 2. Тогда либо в формировании хотя бы одного синдрома будут участвовать только вектора веса 1, а, значит, по доказанному ранее, хотя бы один синдром не будет нулевым, либо вектором веса 2 является иц или и12. Для определенности можно считать, что »(иц) = 2. Если при этом и12 = 0, то для того, чтобы и Е С, необходимо, чтобы »(и^) = 1, % = 2..4, 2 = 1, 2, но тогда »(и) = 8. Если же »(и12) = 1, то для того, чтобы и Е С необходимо, чтобы только один вектор в каждой паре (и21, и22), (и31, и32), (и41, и42) имел вес, равный 1. Без ограничения общности рассмотрим пару (и21, и22) и будем считать, что »(и21) = 1. Рассмотрим систему уравнений:

{и11 = 1р12- рп и12 + 1р41-р11 и21 и11 = 14—Р13 и12 + 1Р43-_Р13 и21

Пусть вирр(и11) = {иЦ, и^}, вирр(и12) = {и^}, вирр(и21) = {и2^}, тогда из

~1Р12-Р11 и12 + 1^41 —Р11 и21 = !р14-.р13 и12 + 1Р43-_Р13 и21

и, свойства

с = у1р ^ й ирр(с) = р + <§ирр(у).

следует, что

и^ + (Р12 -Р11) + 41 + (Р41 -Р11) = и^ + (р 14 -Р1э) + 41 + (р43 -Р13)то(1т. Из последнего выражения легко получить, что

(р 13 - Рп) - (р 14 - Р12) = (Р43 - Р41) - (р 13 - Р11) то( т. Последнее сравнение означает, что определители матриц

'1Р12 \ | ^11 '1Р21 113 114 у У^Р 13 123

сравнимы по модулю т. Таким образом, подматрица д4) не является 2-равномерной. Аналогично можно показать, что никакая из матриц ^^3+i), г = 1..3 не является 2 равномерной. Противоречие.

Пусть £ = 6, тогда и состоит из 6 векторов и^,...,иЕ F т веса 1. Если ни один из этих векторов не входит в главную часть синдрома, то, ввиду отсутствия циклов длины 4 в проверочной матрице, w(Si) = 2, г = 1, 2, 3. Аналогичное доказательство можно провести, если в любой 8^ попадет нечетное количество единиц. Если главную часть синдрома формирует только один вектор веса 1, то в формировании каждой дополнительной части участвует только один вектор единичного веса, а потому, ввиду отсутствия циклов длины 4, такой вектор и не может быть кодовым. Наконец, если w(u11) = w(u12) = 1, то для того, чтобы и Е С, необходимо, чтобы w(uij) = 1, % = 2,3,4, ] = 1, 2, а, значит, w(u) = 8. Противоречие.

Мы показали, что никакое слово u веса 4 или 6 не может являться кодовым, поскольку код не содержит слов веса 5 и 7, то (тп(С) > 8. □

А.2 Доказательство теоремы 1.3.5

Доказательство. Для доказательства необходимо и достаточно показать, что если и — кодовое слово, то »(и) > 10. Согласно теореме 1.3.4, нам осталось показать, что С не содержит слов веса 8. Предположим противное: пусть и Е С, но »(и) = 8. Единицы вектора и могут распределиться по 2 <Ь< 8 векторам длины т. Будем проводить доказательство для различных t.

Рассуждения для случаев, когда £ = 2, 3,4, 6, 7 очевидны и опущены в доказательстве.

Пусть £ = 5. Существуют три допустимые конфигурации, которые включают в себя пять ненулевых векторов и^, и2^2, и3^3, и4^4, и i5^5:

{Ци 1л), »(ипп), Чиедз), »(ич?4), »(и^5)} =

{{1,1,1,1,4}, {1,1, 2, 2, 2}, {1,1,1, 2,3}}.

Легко показать (путем размещения векторов разных весов в информационную часть вектора и), что первые две конфигурации не могут сформировать кодовое слово, а потому сразу перейдем к конфигурации {1, 1, 1, 2, 3}.

Так как число векторов ненулевого веса нечетно, то информационная часть и содержит хотя бы один ненулевой вектор. Пусть ненулевой вектор только один. Если он имеет вес 3, то для того, чтобы произвольный синдром 8^ был равен 0 необходимо, чтобы суммарный вес векторов, входящих в его дополнительную часть, был, по крайней мере 3, однако, при этом »(и) > 12. Если единственный ненулевой вектор имеет вес 1, то найдется синдром 8^ (можно считать, что = 1), в который войдут вектора веса 3 и 2, тогда вес дополнительных частей 82, 83 равен 2, а потому, ввиду отсутствия циклов длины 4 в Н, 82, 83 = 0. Аналогичные рассуждения легко провести для случая, когда единственный ненулевой вектор информационной части и имеет вес 2. Таким образом, информационная часть вектора и должна состоять из

двух ненулевых векторов.

Пусть »(и11) = »(и12) = 1, тогда

ЦРг (иц , и12)Т) = 2, I = 1..3.

Пусть вектор веса 3 находится в дополнительной части синдрома 81. Тогда для того, чтобы 81 = 0, необходимо, чтобы в дополнительную часть синдрома 81 также входил оставшийся вектор веса 1. Без ограничения общности можно считать, что вектор веса 2 принадлежит дополнительной части синдрома 82. Тогда 82 = 0 и 83 = 0 (так как Н не содержит циклов длины 4). Пусть »(и11) = 3, »(и12) = 1, тогда

»(Цг(иц, и!2)т) > 2, г = 1..3.

Так как вес оставшихся ненулевых векторов равен 4, то найдется хотя бы один 8 :

»8) > 0, ] Е {1, 2,3}.

Пусть »(и11) = 2, »(и12) = 1, тогда ровно 2 синдрома 8^, 8^2 будут сформированы векторами веса 1, 1, 2, а значит согласно теореме 1.3.4:

»(8л), ™(832) > а

Осталось рассмотреть случай, когда »(и11) = 3, »(и12) = 2. Тогда 81, 82, 83 будут сформированы векторами 1, 2, 3. Рассмотрим 81 и будем считать, что »(и11) = 3, »(и12) = 2, »(и21) = 1, »(и22) = 0. Так как

/ГЛ ГЛ \ I 111 112 121 122

(Ч1 Ч4) = I

13 14 1^23 ^24

то

81 = № Р4)(иц и12 и21 и22)Т = 0

равносильно системе векторных уравнений с матричными коэффициентами:

+ 1р12 u12 + 1р21 u21 = 0 !р 13 + !р 14 U12 + 1р23 u21 = 0 Здесь и далее мы будем опускать знак транспонирования у векторов Uy■ для упрощения выкладок.

Пусть вирр^п) = {иЦ,и^,иЦ}, вирр^^) = {и112),и122)}, вирр^^) = "21 }.

Выразим u11 из обоих уравнений системы

= 12-р 11 u12 + ~1р21-р11 u21 U11 = 1р14-р13 U12 + ^Р23-Р13

и введем следующие обозначения:

{и21)}.

Р2 = Р12 - Р11,Р3 = Р21 - Р11,Р5 = Р14 - Р13,Р6 = Р23 - Р13, тогда перейдем к равносильной системе:

U11 = 1^2 U12 + %

u11 = Iр5 ^2 + u21

От каждого векторного уравнения с матричными коэффициентами перейдем к уравнениям над целыми числами. Сразу обратим внимание на то, что каждый из таких переходов будет равносильным с точностью до произвольной перестановки правых частей каждого из уравнений над целыми числами.

Так как ^ирр^п) = 3,^ирр^^)! = 2, ^ирр^^)! = 1 и с = у1р ^ й ирр(с) = р + вирр(у), то уравнение

u11 = u12 + 1р3 u21

равносильно системе

(1) и11) и 1) — и12 + р2 то( т

и 2) и11 (2) — и12) + р2 то(т,

(3) ,ип и 1) — и21 + р3 то( т

а из уравнения

u11 = 1_р5 u12 + Iр6 u21

получим

( (1) ии = и(1) = и12 + р5 mod т

, (2) < иЦ (2) = и12 + р5 mod т

(3) = U(1) = и21 + рб mod m

Теперь сложим все уравнения в каждой системе

Мц + ^11 + ^11

= и 12 + + м211) + 2р2 + рз mod т

Мц + Мц + Мц

= и12) + и!! + и211) + 2р>5 + ре mod т и вычтем из первого уравнения второе:

2(р5 - р2) = рз - ре mod т (А.1)

Условие (А.1) требуется для того, чтобы правые части системы

Г (1) u1i = и(1) = и12 + р5 mod т

< и(2) и11 (2) = и12 + р5 mod т

(3) = U(1) = и21 + рб mod т

являлись векторами веса 3. Если условие (А.1) не выполняется, то 81 = 0. Пусть (А.1) выполняется, тогда исключим вектор и11 и перейдем к уравнению

u12 + % u21 — u12 + ^ u21,

(% + )u21 — (1Й + IP5 )u12.

Так как H не содержит циклов длины 4, то м((!р3 +1^6)u21) — 2, в то время

как

i 2

I 4

Нас интересует только случай, когда w((I^2 + )щ2) = 2, что достигается при

(Й - Рб)2 — и + 1)2 то( т, где ] < |_т\ — наименьшее количество нулей между единицами в векторе

с = (1й + 1Ръ )ul2.

Поясним последнее сравнение. Если вирр^и) = {иЦ,и^}, то

й ирр(1р2u12) = {и112) + р2 то( т, и^ + р2 то( т},

вирр(1ръu12) = {и112) + р5 то( т, и^ + р5 то( т}. Ясно, что w((Ip2 +)u12) = 2 только если

„12 + й — «12 + ъгШт

или

и0> + р2 — ^ + й5 той т.

Если обозначить за ^ - наименьшее количество нулей между единицами в

векторе (1р2 + )щ2, то ] + 1 = |и12) - и^. Тогда выразив в двух послед-

(1) (2)

них сравениях и12 и и12 через р2 и р5 и перемножив полученные сравнения, получим (р2 - р5)2 — + 1)2 той т.

В нашем случае ] = рб - р3 - 1 (всегда можно считать, что рб > р3). Тогда для того, чтобы w((I^2 +)u12) = 2, необходимо, чтобы

(^2 - Р5)2 — (Р3 - Рб)2 то( т,

((?2 -155) - (?3 - Рб))((Й - р5) + (Й - Рб)) — 0то(т. Так как т — простое, то последнее уравнение равносильно совокупности

Ы - Р5) - ^3 - Рб) — 0 то( т ~ _ _ _ (А.2)

(Р2 - Р5) + (Р3 - Рб) — 0 то( т

Пусть выполняется первое уравнение совокупности (А.2). Добавив к нему условие (А.1), получим систему

(р2 - р5) = рз - рб mod т

2(р5 - р) = рз - рб mod т откуда

3(р95 - р)2) = 0 mod т, Так как т — простое, то последнее сравнение означает, что

(р 14 + рп) - (р 13 + р12) = 0 mod т. Последнее сравнение равносильно наличию цикла длины 4 в подматрице

111 112 113 114 ,

проверочной матрицы H. Противоречие.

Пусть выполняется второе уравнение совокупности (А.2). Добавив к нему условие (А.1), получим систему

(р2 - р5) = -(рз - рб) mod т

2(р5 - р2) = рз - рб mod т откуда

р5 - р2 = 0 mod т.

Полученное сравнение было рассмотрено ранее. Таким образом, если H не содержит циклов длины 4, то S1 — 0, и доказательство для случая t — 5 закончено.

Пусть t — 6.

Существуют две допустимые конфигурации, которые включают в себя шесть ненулевых векторов u i 1j1, u2 j2,... , u i6j6:

, {1,1,1,1,1,3}

{w(u% U1 ),...,w(u4J6)} —

{1, 1, 1, 1, 2, 2}

Рассмотрим конфигурацию {1,1,1,1,1,3}. Без ограничения общности можно считать, что вектор веса 3 входит в 81, тогда для того, чтобы 81 = 0, необходимо, чтобы в него также входили три вектора веса 1. При этом

w(Qi(^1, ) > 2, г = 1..3.

Так как общий вес векторов, которые не входят в Э1, равен 2, то найдется хотя бы один 8^, ] Е {1, 2,3}, такой, что w(Sj) > 0.

Перейдем к конфигурации {1,1,1,1, 2, 2}. Рассмотрим такую компоненту синдрома 8^, в которую входит вектор веса 2. Если данная компонента включает в себя еще только один ненулевой вектор, то он имеет вес 2, а потому 8^ = 0. Если данная компонета включает в себя еще два ненулевых вектора, то их веса равны 1. Такая конфигурация уже была рассмотрена ранее, а потому 8^ = 0. Если 8^ включает в себя еще три ненулевых вектора, то их веса равны 1, 1, 2, а потому

w(Qг(^1, ) > 2, г = 1..3.

Осталось воспользоваться рассуждением, которое было проведено для конфигурации {1,1,1,1,1,3}.

Пусть t = 7.

Существует единственная допустимая конфигурация, которая включают в себя семь ненулевых векторов ^, ^2 j2,..., ^7,7:

М^ 1Л 7,7 )} = {1, 1, 1, 1, 1, 1, 2}

Рассмотрим синдром 8 , в который входит вектор веса 2. Тогда для того, чтобы 8 = 0, необходимо, чтобы в 8 входило еще два вектора веса 1. Такая конфигурация уже была рассмотрена ранее, а потому 8 = 0.

Для £ = 8 существует единственная допустимая конфигурация, которая включают в себя восемь ненулевых векторов ^^, u i2,2,..., ^:

{W(U11),...,W(U42)} = {1, 1, 1, 1, 1, 1, 1, 1}.

В каждый Sj входит 4 вектора веса 1. Предположим, что матрица (QjQ^j) не содержит цикла длины 8. Без ограничения общности можно считать, что — 1. Тогда из

S1 — (Q1 Q4)(u11 u12 u21 u22)T — 0

следует, что

Ipn u11 + Ip12 u12 + Ip21 u21 + Ip22 u22 — 0 1P13 u11 + Ip14 u12 + Ip23 u21 + Ip23 u22 — 0

Пусть sирр^п) — {иЦ}, S^(u12) — {u^}, S^(u21) — {u^}, Suрр(u22) — {м22)}. Тогда от системы векторных уравнений перейдем к системе над целыми числами:

(р 11 + и11)) + (р 12 + и!2) + (р21 + и21)) + (р22 + и22)) = 0 mod т (р 1з + иЦ) + (р 14 + и12) + (р2з + и21}) + (р24 + и22) = 0 mod т Вычтем из первого уравнения второе:

(р 11 - р1з) + (р 12 - р14) + (р21 - р2з) + (р22 - р24) = 0 mod т.

Последнее условие означает наличие цикла длины 8 в матрице (Q1 Q4). Противоречие.

Мы показали, что никакое слово u веса 8 не может являться кодовым, а поскольку код С не содержит слов веса 9, то dmj/n(C) > 10.

□

А.3 Доказательство теоремы 1.3.9

Доказательство. Рассмотрим проверочную матрицу Н. Так как (1 = 4, то любые ее три столбца являются линейно независимыми и найдется хотя бы одна комбинация из 4 линейно зависимых столбцов. Выберем произвольную такую комбинацию Ь 1, Ь2, Ь i3, Ь4. По свойствам системы троек Штейнера

в матрице Н, полученной конкатенацией таких столбцов, вес каждой строки будет равен 2 и вес каждого столбца - 3. Конфигурация таких столбцов приведена на рис. А.1.

Рис. А.1. Конфигурация 4 линейно зависимых столбцов Ь^, Ь2, Ь3, Ь4

Рассмотрим вектор, который является кодовым для кода с проверочной матрицей Н:

с = (0 ... 0 ^ 0 ... 0 ^ 0 ... 0 ^ 0 ... 0 ^ 0 ... 0).

ч ч ч ч

Заменим в матрице Н каждую единицу £ х £ матрицей р^-кратного циклического сдвига столбцов единичной £х£ матрицы I, а каждый ноль - нулевой £х£ матрицей. Аналогично каждый ноль в векторе с заменим нулевым вектором длины а каждую из 4 единиц - произвольным вектором с , ] = 1..4 длины £ и веса 1. Легко заменить, что в случае, если 4 единицы распределились таким образом, что две или более из них попали в один вектор длины , то полученное слово не будет являться кодовым. Это следует из линейной независимости любых трех столбцов проверочной матрицы Н. Таким образом, нас будет интересовать случай, когда каждая из 4 единиц попала в разные векторы длины .

Для указанного случая вычислим произведение Нст, где Н получена

(А.3)

описанным преобразованием матрицы Н, а с - преобразованием вектора с. Пусть Нст = 0, тогда это матричное уравнение равносильно следующей системе из 6 уравнений:

11С % 1 + 12 С % 2 = 0 21С г 1 + 123 С г 3 = 0

31с г 1 + 1^34 с г 4 = 0

1^42 с г 2 + ^43 с г 3 = 0 ~1Р52 с г 2 + ^54 с г 4 = 0 1Р63 с г 3 + 164 с г 4 = 0

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

Пусть векторы с i 1, с i2, с i3, с i4 длины содержат единицу на позициях Ч, ^2, 2 з и г4 соответственно. Ввиду того, что

^Рокс к = с( г к+Р]к)то(И, к = 1.4, ] = I..6,

то система (А.3) векторных уравнений с матричными коэффициентами равносильна следующей системе в целых числах по модулю :

1 - г 2 = Р12 - р11 (то(1 £)

1 - г з = Р23 - р21 (тос1 £)