Построение и исследование кодов со свойством локальности тема диссертации и автореферата по ВАК РФ 05.13.17, доктор наук Фролов Алексей Андреевич

• Фролов Алексей Андреевич
• доктор наук
• 2021

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

Введение

Глава 1. Потенциальные корректирующие свойства МПП-кодов

1.1. Введение

1.2. Обозначения

1.3. МПП-коды над полем вР(д)

1.4. Нижняя оценка минимального кодового расстояния для МПП-кодов над полем вР(д)

1.5. Верхняя граница минимального кодового расстояния для МПП-кодов над полем вР(д) методом укорочения

1.6. Верхняя граница минимального кодового расстояния для МПП-кодов над полем вР(д) на основе подсчета числа синдромов

1.7. Верхняя граница для ансамбля квазициклических МПП-кодов над полем вР(д)

1.8. Анализ результатов

1.9. Выводы к главе

Глава 2. Реализуемые корректирующие свойства МПП-кодов

2.1. Введение

2.2. Теоретическая оценка радиуса декодирования, реализуемого мажоритарными алгоритмом декодирования

2.2.1. Оценки веса обобщенного синдрома

2.2.2. Однопороговый мажоритарный алгоритм

2.2.3. Многопороговый мажоритарный алгоритм

2.2.4. Анализ результатов

2.3. Экспериментальное исследование алгоритма распространения доверия

2.3.1. Алгоритм распространения доверия (Лвр)

2.3.2. Построение проверочных матриц МПП-кодов

2.3.3. Результаты имитационного моделирования

2.4. Выводы к главе

Глава 3. Применение методов машинного обучения для декодирования МПП-кодов

3.1. Введение

3.2. Предварительные сведения

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

3.2.2. Алгоритм распространения доверия

3.3. Архитектура нейронной сети

3.3.1. Построение нейронной сети с использованием графа Тан-нера

3.3.2. Функция потерь

3.3.3. Общие веса и остаточные соединения

3.4. Результаты имитационного моделирования

3.5. Выводы к главе

Глава 4. Множественный доступ на базе МПП-кодов

4.1. Введение

4.2. Бесшумные каналы без/с информацией об интенсивности

4.2.1. Координированная передача

4.2.2. Некоординированная передача

4.2.3. Схема передачи для А-канала

4.3. Суммирующий канал с АБГШ

4.3.1. Граница существования

4.3.2. Схема совместного итеративного декодирования на основе МПП-кодов

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

4.4. Канал Рэлея

4.4.1. Граница несуществования

4.4.2. Границы существования

4.4.3. Схемы передачи на основе МПП-кодов

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

4.4.5. Применение схем на базе МПП-кодов для массового случайного доступа

4.5. Выводы к главе

Глава 5. Коды с локальным восстановлением для систем распределенного хранения данных

5.1. Предварительные сведения

5.1.1. ЛВ-коды

5.1.2. ЛВ-коды с несколькими непересекающимися восстанавливающими множествами

5.1.3. ЛВ-коды с несколькими непересекающимися восстанавливающими множествами

5.1.4. Ранговые коды

5.1.5. Графы-расширители

5.2. Верхняя граница для скорости для (г, ЛВ-кодов

5.3. Верхние границы для минимального расстояния (г, ¿) ЛВ-кодов

5.4. Нижние границы для минимального расстояния (г, ¿) ЛВ-кодов

5.4.1. Конструкция на основе графов-расширителей

5.4.2. Каскадная конструкция

5.5. Верхняя граница для скорости (г, £, х) ЛВ-кодов

5.6. Нижние границы для скорости (г, х) ЛВ-кодов

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

5.8. Выводы к главе

Заключение....................................1б7

Литература

Введение

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

Актуальность темы исследования.

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

Идея помехоустойчивого кодирования [1] была предложена К. Шенноном -основателем теории информации. Он доказал теоретическую возможность создания достаточно длинных помехоустойчивых кодов, обеспечивающих надежную связь, но не объяснил, как именно такие коды могут быть построены. С тех пор было создано уже несколько поколений кодов (например, коды Рида-Соломона, коды Рида-Маллера, турбо-коды, сверточные коды).

Важнейшим обстоятельством при выборе той или иной кодовой конструкции на практике является наличие быстрых алгоритмов кодирования и декодирования. При этом необходимо, чтобы код обладал хорошими корректирующими свойствами, что верно для большинства линейных кодов. Тем не менее задача декодирования линейного кода по максимуму правдоподобия в общем случае является МР-трудной, что означает, что сложность декодирования, вероятно, растет экспоненциально с длиной кода. Поэтому нужно использовать классы кодов, имеющих минимальный рост сложности в зависимости от длины кода и возможность распараллеливания данных процедур. Одним из свойств, позволяющих строить хорошие коды с простым алгоритмом декодирования, является свойство локальности. В литературе можно найти несколько разных определений свойства локальности. Наиболее известным вариантом является свойство локального декодирования, когда любой бит кодового слова можно восстановить, просмотрев лишь небольшое число принятых бит [2], [3]. Есть также свойство локального тестирования, когда нужно определить с некоторой заранее заданной вероятностью ошибки, является ли слово кодовым, просмотрев небольшое число принятых бит [4]. Далее нас будет интересовать другое свойство локальности, а именно локальность задания. Это свойство заключается в том, что любой символ кодового слова является функцией небольшого числа других символов кодового слова. В случае линейных кодов, являющихся основным предметом исследований в данной работе, это означает наличие слов малого веса в дуальном коде. Вспомнив, что слова дуального кода являются проверочными соотношениями, мы приходим к необходимости наличия разреженных проверочных соотношений. Отметим, что мы не требуем,

чтобы все проверочные соотношения были малого веса, а требуем лишь, чтобы объединение проверочных соотношений малого веса покрывало все координаты кодового слова. Важнейшими классами кодов со свойством локальности являются коды с малой плотностью проверок (МПП-коды, low-density parity-check codes, LDPC codes) [5] и коды с локальным восстановлением (ЛВ-коды, locally recoverable codes, LRC) [6],[7]. Данная диссертация посвящена теоретическому исследованию данных классов кодов, а также рассмотрению возможности применения этих кодов в современных системах передачи и хранения данных.

МПП-коды - это линейные коды с разреженной проверочной матрицей. Иными словами, проверочная матрица состоит преимущественно из нулей и содержит лишь малое число элементов, отличных от нуля. Ясно, что данные коды обладают свойством локальности, которое позволяет использовать простые алгоритмы передачи сообщений (англ. message passing) для декодирования таких кодов. МПП-коды были предложены Р. Дж. Галлагером [5] в 1960 году. В этой работе были получены нижняя оценка минимального кодового расстояния и предложены алгоритмы декодирования, подходящие для практического применения: алгоритм распространения доверия (англ. belief propagation) и алгоритм инвертирования бита (англ. bit flipping). В 1974 г. В. В. Зяблов и М. С. Пинскер [8] доказали существование МПП-кодов, способных исправить линейную долю стираний при декодировании с помощью алгоритма, имеющего сложность 0(N log N), где N - это длина кода. В 1975 г. ими был получен аналогичный результат для ошибок [9]. В 1981 г. Р. Таннер [10] предложил метод построения длинных кодов из коротких кодов компонентов. Конструкция МПП-кодов Галлагера является частным случаем конструкции Таннера и получается из нее, если использовать код с двоичной проверкой на четность в качестве компонентного кода. Таким образом, коды построенные Таннером можно назвать обобщенными МПП-кодами. После этого ввиду слабого развития вычислительной техники МПП-коды были на долгое время забыты. Активное исследование МПП-кодов началось в середине 90-х годов в связи с появлением работ М. Сипсера, Д. Спилмана [11] и Д. Маккея

[12]. Исследованию двоичных МПП-кодов посвящено множество работ, среди которых следует особо отметить работы таких русских и зарубежных ученых, как Р. Дж. Галлагер, М. С. Пинскер, В. В. Зяблов, К. Ш. Зигангиров, А. М. Барг, Р. Тан-нер, Д. Спилман, Д. Маккей, Т. Ричардсон, Р. Урбанке, Д. Бурштейн, С. Л. Лицын, Ж. Земор, М. Фоссорье, Д. Деклерк, С.И. Ковалев. Как результат, в настоящее время эти коды приняты для использования в канале данных систем мобильной связи пятого поколения (5G). Несмотря на это, двоичные МПП-коды не подходят для передачи коротких сообщений, а также режима высоких кодовых скоростей, так как имеют при малых вероятностях ошибки, так называемую, "полку" (англ. error floor).

МПП-коды над полем GF(g) впервые рассмотрены в работе М. Дэви и Д. Мак-кея [13], где был предложен алгоритм декодирования, являющийся обобщением алгоритма распространения доверия для двоичного случая, и проведено исследование методом имитационного моделирования. Было показано, что недвоичные МПП-коды значительно превосходят двоичные. Кроме того, недвоичные МПП-коды значительно лучше для каналов с пачками ошибок и каналов с модуляциями высокой кратности [14]. Число работ, посвященных исследованию недвоичных МПП-кодов, сравнительно невелико. В существующих работах по этой теме [15-28] приводятся упрощенные варианты алгоритма декодирования и результаты исследований этих модифицированных алгоритмов методом имитационного моделирования. Однако результатов исследований методом имитационного моделирования недостаточно.

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

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

ЛВ-коды также обладают свойством локальности, которое позволяет оптимизировать процедуру восстановления одного вышедшего из строя диска/сервера. Такие коды крайне важны для систем распределенного хранения данных. Данный класс кодов хорошо исследован в литературе. Предложены оптимальные конструкции ЛВ-кодов как на основе кодов в ранговой метрике [29] (для алфавита, мощность которого растет экспоненциально с длиной кода), так и на основе кодов Рида-Соломона [30] (для алфавита, размер которого растет линейно с длиной кода).

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

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

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

о разработать методы оценки минимального кодового расстояния для МПП-кодов над полем вР(д).

о разработать методы декодирования и исследования реализуемых корректи-

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

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

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

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

Научная новизна. В настоящей работе впервые:

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

о Предложен мажоритарный алгоритм декодирования МПП-кодов над полем вР(д) и его многопороговая модификация.

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

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

о Установлены неасимптотические верхние и нижние границы на вероятность ошибки для многопользовательского канала Рэлея.

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

о Установлены границы для параметров ЛВ-кодов с несколькими восстанавливающими множествами.

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

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

Практическая значимость полученных результатов определяется тем, что в диссертации рассмотрены перспективные направления развития технологий беспроводной связи, обсуждаемые в настоящее время в комитетах по стандартизации (3GPP, IEEE 802) в рамках работ по созданию сетей пятого поколения. В частности, это задачи межмашинного взаимодействия и использование методов машинного обучения при декодировании. Разработанные технологии легко переносимы на коммерческие приложения и стартапы. Результаты могут быть применены для разработки национального стандарта LP-WAN, чтобы конкурировать с существующими решениями LoRa, SigFox и т.д. Новые конструкции ЛВ-кодов могут быть

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

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

1. Верхние и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF(g).

2. Асимптотическая оценка на радиус декодирования МПП-кодов над полем GF(g), реализуемый с помощью мажоритарного алгоритма декодирования, имеющего сложность 0(N log N).

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

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

5. Границы для параметров ЛВ-кодов с несколькими восстанавливающими множествами.

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

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

• IEEE International Symposium on Information Theory (2011, 2013, 2015, 2017, 2018, 2019, 2020);

• IEEE Information Theory Workshop (2015, 2017);

• International Symposium on Information Theory and its Applications (2018);

• IEEE Wireless Communications and Networking Conference (2019);

• IEEE Vehicular Technology Conference (2019);

• International Symposium "Problems of Redundancy in Information and Control Systems" (2009, 2014, 2016, 2019);

• International Workshop on Algebraic and Combinatorial Coding Theory (2010, 2014, 2018);

• Asilomar Conference on Signals, Systems, and Computers (2019). Кроме того, они были представлены на следующих семинарах:

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

• лаборатории информационных систем и систем принятия решений Масса-чусетского технологического института (MIT), г. Кембридж, Массачусетс, руководитель - Ю.Г. Полянский;

• по управлению и обработке сигналов университета Мэриленда, г. Колледж Парк, Мэриленд, руководитель - А.М. Барг;

• по теории кодирования Израильского технологического института (Техни-он), г. Хайфа, Израиль, руководитель - Р. Рот;

• по криптографии университета г. Рен, Франция, руководитель - П. Лодрё;

• по алгебраической теории кодирования университета г. Ульм, Германия, руководитель - М. Боссерт;

• по теории кодирования Технического университета г. Мюнхен (TUM), Германия, руководитель - Г. Крамер;

• по телекоммуникациям немецкого аэрокосмического цента (DLR), Германия, руководитель - Дж. Лива;

• по алгебраической теории кодирования для сетей и систем хранения данных исследовательского центра Дагштуль, Германия, руководитель - Р. Зедел;

Кроме того были сделаны доклады на профессорских днях московского исследовательского центра компании «Хуавэй» в 2015-2020 гг.

Публикации. Материалы диссертации опубликованы в 33 печатных работах, из них 14 статей [31-44] в рецензируемых журналах и 19 статей [45-63] в сборниках трудов конференций.

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

Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, пяти глав, заключения и библиографии. Общий объем диссертации 186 страниц, включая 35 рисунков и 5 таблиц. Библиография включает 153 наименования на 17 страницах.

Глава 1

Потенциальные корректирующие свойства

МПП-кодов

1.1. Введение

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

1.2. Обозначения

Через GF(g) обозначим поле из q элементов.

Пусть A матрица размера М х N, I С {1, 2,..., М} - подмножество строк, J С {1, 2,..., N} - подмножество столбцов. Обозначим через Aj,j подматрицу матрицы A, содержащую строки и столбцы только из I и J соответственно. В случае если I = {1,2,..., М} обозначим Aj,j через Aj.

Под весом вектора мы понимаем вес Хэмминга или число ненулевых элементов в векторе. Обозначим вес (вес Хэмминга) вектора x через wt (x).

Введем следующее обозначение. Пусть X - это дискретная случайная величина, обозначим через Hq (X) энтропию X, т.е.,

Hq(X) = " Е Рг(Х = ж) logQ Рг(Х = ХУ

X

Введем еще одно обозначение. Пусть х - это действительное число, причем 0 < х < 1, тогда hq(x) - это функция Q-ичной энтропии, т.е.

hQ(x) = -х logQ х - (1 - х) logQ(1 - х) + х logQ(Q - 1).

В случае д = 2 мы будем опускать нижний индекс и использовать обозначение Ъ(х) для функции двоичной энтропии.

1.3. МПП-коды над полем GF(g)

МПП-код С длины N над полем вР(д) - это линейный код с разреженной проверочной матрицей Н = [Ъ^], 1 < ] < М, 1 < г < N размера М х N над полем вР(д). Таким образом, проверочная матрица состоит преимущественно из нулей и содержит малое число элементов, отличных от нуля. Далее мы будем рассматривать как регулярные, так и нерегулярные МПП-коды. Начнем с более общего случая - нерегулярных МПП-кодов. Пусть строки матрицы Н имеют веса п0\ ] = 1,..., М, а столбцы - веса 1(г), г = 1,..., N. Легко убедиться, что для скорости кода С выполнено соотношение

Н(Г)>1 £Г=1 ^/к щс) -1 - ЕМ^?

где в числителе и знаменателе дроби стоят средние веса столбцов и строк матрицы соответственно. Равенство достигается в случае полного ранга матрицы Н.

В случае регулярного МПП-кода все строки матрицы Н имеют вес п0, а все столбцы -I. Скорость регулярного МПП-кода можно оценить следующим образом

I

Щс) - 1 - —

По

Код С можно представить в виде двудольного графа, называемого графом Таннера [10] (см. рис. 1.1). Граф состоит из N символьных вершин у1 ,у2, ... ,ум и М проверочных вершин с1,с2,... ,см. Символьная вершина У{ и проверочная вершина с^ соединены ребром тогда и только тогда, когда Ъ^ = 0. Данное ребро имеет метку Ъ^ е вР(д) (см. рис. 1.1).

Введем обозначения Г(г) = {] : Ъ^ = 0,1 < ] < М} и Ф(^) = {г : Ъ^ = 0,1 < г <_ Чтобы проверить, является ли слово г = (г1 ,г2,... ,гм) е вР(д)я кодовым, поставим символы слова в соответствие символьным вершинам (у^ ^ = 1,..., N).

С1 С2 ... cj . cm

h ■ ■

¡41

ЖЖ Ж ,> Ж

Рис. 1.1. Tanner graph

Каждая проверочная вершина с^, 1 < ] < М, накладывает следующее линейное ограничение

Ч : ЬьП = о

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

Легко увидеть, что коды с проверкой на четность можно заменить на любые линейные коды, имеющие те же длины. Так мы приходим к обобщенным МПП-кодам. Далее (для простоты изложения) мы рассматриваем только только случай, когда все коды-компоненты одинаковы (обозначим этот код через Со). Код С0 является линейным [п0, Я0, й0] кодом над полем вР(д). Обозначим проверочную матрицу компонентного кода через Н0. Эта матрица имеет размер т0 х п0, где то = (1 - ^0)п0.

Пусть д0(в, п0, й0) - это нумератор весов кода С0, т.е.

по

go(s,no,do] = 1+ Е )

,w

W=d0

где ) - это число слов веса W в коде С0.

Обозначим через дх (з,щ, нумератор весов всех остальных слов, т.е.

дх (в, по, = (1 + (д - 1)й)п° - до(з, щ, ¿о).

В случае кода с проверкой на четность над полем вР(д) будем использовать обозначения до(в, п0) и дх(в, п0). Напомним, что

до(в, по) = 1 (1 + (д - 1)з)п° + 1(1 - 5)п°. д д

Чтобы убедиться в этом, достаточно применить теорему МакВильямс, ведь дуальный код - это код с повторением над полем вР(д).

Обозначим через 8 синдром принятого вектора г, т.е.

8 = гНт.

Данный синдром состоит из синдромов компонентных кодов и может быть представлен в виде

8 = ( 81 82 ... 8 м

где 8^, г = 1,..., М - синдром ¿-го компонентного кода. Полученное представления называют обобщенным синдромом.

Для доказательств мы будем использовать метод случайного кодирования. Введем ансамбль 8(Ь, п0,1) МПП-кодов над полем вР(д) по аналогии с ансамблем двоичных МПП-кодов Галлагера [5]. Рассмотрим блочную диагональную матрицу

Н

ъ =

/

V

Но 0 0 Но

00

0 0

\

Но

/

Ьтх Ьп

°

на главной диагонали которой находятся Ь проверочных матриц Но кода Со. Пусть

^(Л) = А • П • diag(7l,... ), где П - это матрица перестановки, а ^^ е 0¥(д )\{0}, ] = 1,... , ] = 1,...

19

Тогда матрица

( ЫН) х

Н

^(Н )

( ) } (ЪтхЬпо

размера £Ьт х Ьщ, составленная из I таких матриц, как слоев, является разреженной проверочной матрицей МПП-кода из ансамбля £(Ь, щ,£). Дадим формальное определение

Определение 1.1. Элементы ансамбля £(Ь,щ,£) получаются путем независимого выбора преобразований = 1, 2,... ,£.

Замечание 1.1. Отметим, что в отличие от определения ансамбля для двоичных кодов здесь добавляется умножение на константы, не равные нулю.

Замечание 1.2. Из определения ансамбля £(Ь,щ,£) ясно, что длина кода N = Ьщ.

Верна следующая нижняя оценка скорости кода С е £(Ь,щ, I)

К > 1 - № (7 - Ь) = 1 - 1(1 - Во), (1.1)

Ьщ

равенство достигается в случае полного ранга матрицы Н.

Далее нам также понадобится ансамбль квазициклических МПП-кодов. Квазициклические МПП-коды (КЦ МПП-коды) были предложены в [64; 65]. Эти коды являются важным классом МПП-кодов [5; 10]. Также КЦ МПП-коды являются подклассом МПП-кодов на протографах [66]. Такие коды просты в описании, для них есть эффективные алгоритмы кодирования [67] и декодирования, основанные на алгоритме распространения доверия [68]. Все это делает эти коды популярными для применения в практических приложениях.

Рассмотрим следующую двоичную матрицу размера т х п

НЬше = [М е {0,1}тхте. 20

Эту матрицу мы будем называть базовой матрицей. Данная матрица является матрицей смежности протографа.

Построим проверочную матрицу Н КЦ МПП-кода С. Для этого расширим матрицу Н^а8е циклическими матрицами (циркулянтами), умноженными на ненулевые элементы поля вР(д), т.е.

Н

аМР1Д «1,2^1,2 «2,1Р2,1 «2,2Р2,2

«1,пР1,п «2,пР2,п

^т,1Рт,1 ^т,2Рт,2 ' ' ' ОтпР

т.п*- т,п

е ОР(д)

т п

где Р{^ - двоичный циркулянт размера й х й веса1 ^, ] = 1,... ,т; % = 1,... ,п. е 0Р(<?)\{0}, ] = 1,...,т; г = 1,...,п.

Обозначим длину кода С через N = пв, для скорости полученного кода справедливо следующее неравенство

Я(С) ^ 1 -

п

Пусть вР(д) некоторое поле, а вР(д)[х] кольцо полиномов с коэффициентами из вР(д). Т.к. кольцо циркулянтов размера й х й над вР(д) изоморфно факто-кольцу СР(д)(в )[ж] = СР(д)[х]/(хв — 1), то сопоставим проверочной матрице Н полиномиальную проверочную матрицу Н(ж) размера т х п:

Н(х) =

а1,1Р1д(ж) ®1,2Р1,2(х) &2,№,1(х) ®2,2Р2,2(Х)

&1,пР1,п(х)

®2,пР2,п(х)

^т,1Рт,1(Х) ^т,2Рт,2(Х^) ' ' ' &т,п'Рт,п(%)

где (х) = Р«,з (1,1)^ 1, а Р^ 1) - элемент на пересечении ¿-го строки и первого столбца матрицы Р , .

весом циркулянта называется вес его первой строки.

Пример 1.1. Рассмотрим следующую базовую матрицу

H

base —

0 1 1 1 0 1

При расширении каждая единица заменяется на пару (г, /3), где х - это номер циркулянта (величина сдвига), а [5 - это ненулевой элемент поля GF(q). Например, мы можем получить такую матрицу

H

exp

-- (2,1) (1,2) (0,1) -- (2,3)

Отметим, что Нехр соответствует такой проверочной матрице

H

0 0 0 0 1 0 0 0 2

0 0 0 0 0 1 2 0 0

0 0 0 1 0 0 0 2 0

1 0 0 0 0 0 0 3 0

0 1 0 0 0 0 0 0 3

0 0 1 0 0 0 3 0 0

Замечание 1.3. Отметим, что элементы циркулянта умножаются на один и тот же элемент поля GF(q). Это очень важно для практической реализации этих кодов, так как проверочные матрицы занимают малый объем памяти и могут эффективно храниться. Также предложенная конструкция проверочных матриц допускает параллельную реализацию алгоритмов кодирования и декодирования.

Сопоставим вектор

c — (ci, С2, . . . , cn),

где

С — (chi,ch2,... ,см), г — 1, 2,... ,п,

с вектором полиномов

с(х) = (с\(х),с2(х), ..., Сп(х)),

где сг(х) = ^2¿=1 Сг1х± 1.

Ясно, что

Ист = 0 (в кольце СР(д))

эквивалентно

И(ж)ст(х) = 0 (в кольце С¥(д)(з)[ж]).

Под весом полинома /(х) мы понимаем число его ненулевых коэффициентов и обозначаем как ий (/(х)). Определим вес вектора полиномов с(х) = (с1(х),с2(х),... ,Сп(х)) как

Список литературы диссертационного исследования доктор наук Фролов Алексей Андреевич, 2021 год

Литература

1. Shannon C. E. A mathematical theory of communication // The Bell System Technical Journal. — 1948. — July. — Vol. 27, no. 3. — P. 379-423.

2. Yekhanin S. Locally Decodable Codes: A Brief Survey // Coding and Cryptol-ogy / ed. by Y. M. Chee [et al.]. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2011.—P. 273-282.

3. Yekhanin S. Locally Decodable Codes // Foundations and Trends® in Theoretical Computer Science. — 2012. — Vol. 6, no. 3. — P. 139-255.

4. Kaufman T., Viderman M. Locally Testable vs. Locally Decodable Codes // Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques / ed. by M. Serna [et al.]. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2010. — P. 670-682.

5. Gallager R. G. Low-Density Parity-Check Codes. — MIT Press, 1963.

6. On the Locality of Codeword Symbols / P. Goplan [et al.] // IEEE Trans. Inf. Theory. — 2011. — Nov. — Vol. 58, no. 11. — P. 6925-6934.

7. Papailiopoulos D. S., Dimakis A. G. Locally Repairable Codes // IEEE Trans. Inf. Theory. — 2014. — Oct. — Vol. 60, no. 10. — P. 5843-5855.

8. Зяблов В. В., Пинскер М. С. Сложность декодирования низкоплотностных кодов при передаче по каналу со стираниями // Пробл. передачи информ. — 1974. — т. 10, № 1. — с. 5—28.

9. Зяблов В. В., Пинскер М. С. Оценка сложности исправления ошибок низ-коплотностными кодами Галлагера // Пробл. передачи информ. — 1975. — т. 11, № 1. —с. 23—36.

10. Tanner R. A recursive approach to low complexity codes // IEEE Transactions on Information Theory. — 1981. — Sept. — Vol. 27, no. 5. — P. 533-547.

11. Sipser M., Spielman D. A. Expander codes // IEEE Transactions on Information Theory. — 1996. — Nov. — Vol. 42, no. 6. — P. 1710-1722.

12. MacKay D. J. C. Good error correcting codes based on very sparse matrices // IEEE Trans. Inform. Theory. — 1999. — Vol. 45, no. 2. — P. 399-431.

13. Davey M. C., MacKay D. Low-density parity check codes over GF(q) // IEEE Communications Letters. — 1998. — Vol. 2, no. 6. — P. 165-167.

14. Hongxin Song, Cruz J. R. Reduced-complexity decoding of Q-ary LDPC codes for magnetic recording // IEEE Transactions on Magnetics. — 2003. — Mar. — Vol. 39, no. 2. — P. 1081-1087.

15. Barnault L., Declercq D. Fast decoding algorithm for LDPC over GF(2/sup q/) // Proceedings 2003 IEEE Information Theory Workshop (Cat. No.03EX674). — 03/2003.—P. 70-73.

16. Wymeersch H., Steendam H., Moeneclaey M. Log-domain decoding of LDPC codes over GF(q) // 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577). Vol. 2. — 06/2004. — 772-776 Vol.2.

17. Declercq D., Fossorier M. Decoding Algorithms for Nonbinary LDPC Codes Over GF(g) // IEEE Transactions on Communications. — 2007. — Apr. — Vol. 55, no. 4.—P. 633-643.

18. Low-complexity decoding for non-binary LDPC codes in high order fields / A. Voicila [et al.] // IEEE Trans. Communications. — 2010. — Vol. 58, no. 5. — P. 1365-1375.

19. Rathi V., Urbanke R. Density evolution, thresholds and the stability condition for non-binary LDPC codes // IEE Proceedings Communications. — 2005. — Vol. 152, no. 6. — P. 1069-1074.

20. Rathi V, Andriyanova I. Some Results on MAP Decoding of Non-Binary LDPC Codes Over the BEC // IEEE Trans. Inform. Theory. — 2011. — Vol. 57, no. 4.—P. 2225-2242.

21. Xinmiao Z., Fang C. Reduced-complexity extended Min-sum check node processing for non-binary LDPC decoding // Proc. IEEE International Midwest Symposium on Circuits and Systems. — 2010. — P. 737-740.

22. Architecture of a low-complexity non-binary LDPC decoder / A. Voicila [et al.] // Proc. International Conference on Consumer Electronics. — 2008. — P. 1-2.

23. Performance study of non-binary LDPC Codes over GF(q) / V. S. Ganepola [et al.] // Proc. International Symposium on Communication Systems. — 2008. — P. 585-589.

24. Savin V. Min-Max decoding for non binary LDPC codes // Proc. IEEE International Symposium on Information Theory. — 2008. — P. 960-964.

25. Poulliat C., Fossorier M., Declercq D. Design of non binary LDPC codes using their binary image: algebraic properties // Proc. IEEE International Symposium on Information Theory. — 2006. — P. 93-97.

26. Divsalar D., Dolecek L. Ensemble analysis of pseudocodewords of protograph-based non-binary LDPC codes // Proc. Information Theory Workshop. — 2011. —

P. 340-344.

27. Nozaki T., Kasai K., Sakaniwa K. Error floors of non-binary LDPC codes // Proc. IEEE International Symposium on Information Theory. — 2010. — P. 729-733.

28. Kelley C. A., Sridhara D., Rosenthal J. Pseudocodeword weights for non-binary LDPC codes // Proc. IEEE International Symposium on Information Theory. — 2006.—P. 1379-1383.

29. Optimal Locally Repairable Codes via Rank Metric Codes / N. Silberstein [et al.] // Proceedings IEEE International Symposium on Information Theory (ISIT). — 07/2013. — P. 1819-1823.

30. Tamo I., Barg A. A Family of Optimal Locally Recoverable Codes // IEEE Trans. Inf. Theory. — 2014. — Aug. — Vol. 60, no. 8. — P. 4661-4676.

31. Фролов А. А., Зяблов В. В. Асимптотическая оценка доли ошибок, исправляемых q-ичными МПП-кодами // Пробл. передачи информ. — 2010. — т. 46, № 2. — с. 47—65.

32. Зяблов В. В., Рыбин П. С., Фролов А. А. Алгоритм декодирования с вводом стираний для МПП-кодов, построенных над полем GF(q) // Информационно-Управляющие Системы. — 2011. — т. 50, № 1. — с. 62—68.

33. Фролов А. А., Зяблов В. В. Границы минимального кодового расстояния для недвоичных кодов на двудольных графах // Пробл. передачи информ. —

2011. — т. 47, № 4. — с. 27—42.

34. Zyablov V., Frolov A. A signal-code construction for a multiple-access system using a vector channel with an additive white Gaussian noise // J. Commun. Technol. Electron. — 2012. — Vol. 57. — P. 953-957.

35. Осипов Д. С., Фролов А. А., Зяблов В. В. Система множественного доступа для векторного дизъюнктивного канала // Пробл. передачи информ. —

2012. — т. 48, № 3. — с. 52—59.

36. Осипов Д. С., Фролов А. А., Зяблов В. В. О пропускной способности для пользователя системы множественного доступа в векторном дизъюнктивном канале при наличии ошибок // Пробл. передачи информ. — 2013. — т. 49, №4. —с. 13—27.

37. Фролов А. А., Зяблов В. В. О пропускной способности многопользовательского векторного суммирующего канала // Пробл. передачи информ. — 2014. — т. 50, № 2. — с. 20—30.

38. Frolov A., Zyablov V. A coding technique for Q-frequency S-user gaussian channel // J. Commun. Technol. Electron. — 2014. — Vol. 59. — P. 1483-1488.

39. Фролов А. А. Верхняя граница минимального кодового расстояния для МПП-кодов над полем GF(q) на основе подсчета числа синдромов // Пробл. передачи информ. — 2016. — т. 52, № 1. — с. 8—15.

40. Tamo I., Barg A., Frolov A. Bounds on the Parameters of Locally Recoverable Codes // IEEE Transactions on Information Theory. — 2016. — Vol. 62, no. 6. — P. 3070-3083.

41. Frolov A., Zyablov V. On the multiple threshold decoding of LDPC codes over GF(q) // Advances in Mathematics of Communications. — 2017. — Vol. 11, no. 1. — P. 123-137.

42. Kruglik S., Nazirkhanova K., Frolov A. New Bounds and Generalizations of Locally Recoverable Codes With Availability // IEEE Transactions on Information Theory. — 2019. — Vol. 65, no. 7. — P. 4156-4166.

43. Energy Efficient Coded Random Access for the Wireless Uplink /S.S. Kowshik [et al.] // IEEE Transactions on Communications. — 2020. — Vol. 68, no. 8. — P. 4694-4708.

44. Kruglik S., Frolov A. An Information-Theoretic Approach for Reliable Distributed Storage//J. Commun. Technol. Electron. — 2020. — Vol. 65. — P. 1505-1516.

45. Frolov A., Zyablov V. Upper and lower bounds on the minimum distance of expander codes //2011 IEEE International Symposium on Information Theory Proceedings. — 2011. — P. 1397-1401.

46. On a multiple-access in a vector disjunctive channel / A. Frolov [et al.] // 2013 IEEE International Symposium on Information Theory. — 2013. — P. 211-215.

47. Frolov A., Zyablov V. A new coding method for a multiple-access system with a large number of active users //2015 IEEE Information Theory Workshop (ITW). — 2015.—P. 1-5.

48. Frolov A., Zyablov V. On the multiple threshold decoding of LDPC codes over GF(q) //2015 IEEE International Symposium on Information Theory (ISIT). — 2015.—P. 2673-2677.

49. Frolov A. An upper bound on the minimum distance of LDPC codes over GF(q) // 2015 IEEE International Symposium on Information Theory (ISIT). — 2015. — P. 2885-2888.

50. Kruglik S., Frolov A. Bounds and constructions of codes with all-symbol locality and availability //2017 IEEE International Symposium on Information Theory (ISIT). — 2017. — P. 1023-1027.

51. On LDPC Code Based Massive Random-Access Scheme for the Gaussian Multiple Access Channel / A. Glebov [et al.] // Internet of Things, Smart Spaces, and Next Generation Networks and Systems. — Springer International Publishing, 2018. — P. 162-171.

52. On one generalization of LRC codes with availability / S. Kruglik [et al.] // 2017 IEEE Information Theory Workshop (ITW). — 2017. — P. 26-30.

53. Kruglik S., Nazirkhanova K., Frolov A. On Distance Properties of (r, t, ^)-LRC Codes //2018 IEEE International Symposium on Information Theory (ISIT). —

2018.—P. 1336-1339.

54. Kruglik S., Potapova V., Frolov A. A Method for Constructing Parity-Check Matrices of Quasi-Cyclic LDPC Codes Over GF(q) // J. Commun. Technol. Electron. — 2018. — Vol. 63. — P. 1524-1529.

55. Rybin P., Frolov A. On the Decoding Radius Realized by Low-Complexity Decoded Non-Binary Irregular LDPC Codes //2018 International Symposium on Information Theory and Its Applications (ISITA). — 2018. — P. 384-388.

56. Achievability Bounds for T-Fold Irregular Repetition Slotted ALOHA Scheme in the Gaussian MAC / A. Glebov [et al.] //2019 IEEE Wireless Communications and Networking Conference (WCNC). — 2019. — P. 1-6.

57. Energy efficient random access for the quasi-static fading MAC / S. S. Kowshik [et al.] // 2019 IEEE International Symposium on Information Theory (ISIT). —

2019. — P. 2768-2772.

58. A Polar Code Based Unsourced Random Access for the Gaussian MAC / E. Mar-shakov [et al.] //2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall). -2019. — P. 1-5.

59. Low Complexity Energy Efficient Random Access Scheme for the Asynchronous Fading MAC / K. Andreev [et al.] //2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall). — 2019. — P. 1-5.

60. Efficient Concatenated Same Codebook Construction for the Random Access Gaussian MAC / D. Ustinova [et al.] //2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall). — 2019. — P. 1-5.

61. Ustinova D., Rybin P., Frolov A. On the Analysis of T-Fold Coded Slotted ALOHA for a Fixed Error Probability //2019 11th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT). — 2019. — P. 1-5.

62. Short-Packet Low-Power Coded Access for Massive MAC / S. S. Kowshik [et al.] // 2019 53rd Asilomar Conference on Signals, Systems, and Computers. — 2019. — P. 827-832.

63. Andreev K., Marshakov E., Frolov A. A Polar Code Based TIN-SIC Scheme for the Unsourced Random Access in the Quasi-Static Fading MAC // 2020 IEEE International Symposium on Information Theory (ISIT). — 2020. — P. 30193024.

64. Tanner R. M. On quasi-cyclic repeat-accumulate codes // Proc. 37th Allerton Conf. Commun., Contr., Comput. — 09/1999. — P. 249-259.

65. Fossorier M. P. C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices // IEEE Transactions on Information Theory. — 2004. — Aug. — Vol. 50, no. 8. — P. 1788-1793.

66. Thorpe J. Low-Density Parity-Check (LDPC) Codes Constructed from Protographs //. 2003.

67. Efficient encoding of quasi-cyclic low-density parity-check codes / Zongwang Li [et al.] // IEEE Transactions on Communications. — 2006. — Jan. — Vol. 54, no. 1.—P. 71-81.

68. Kschischang F. R., Frey B. J., Loeliger H. Factor graphs and the sum-product algorithm // IEEE Transactions on Information Theory. — 2001. — Feb. — Vol. 47, no. 2. — P. 498-519.

69. Barg A., Zemor G. Distance Properties of Expander Codes // IEEE Trans. Inf. Theory. — 2006. — Vol. 52, no. 1. — P. 78-90.

70. Skachek V. Minimum distance bounds for expander codes // Information Theory and Applications Workshop. — 02/2008. — P. 366-370.

71. Boutros J., Pothier O., Zemor G. Generalized low density (Tanner) codes // 1999 IEEE International Conference on Communications (Cat. No. 99CH36311). Vol. 1. — 06/1999. — 441-445 vol.1.

72. Lentmaier M., Zigangirov K. S. On generalized low-density parity-check codes based on Hamming component codes // IEEE Communications Letters. —1999. — Aug. — Vol. 3, no. 8. — P. 248-250.

73. Barg A., Mazumdar A., Zemor G. Weight distribution and decoding of codes on hypergraphs // Advances in Mathematics of Communications. — 2008. — Vol. 2, no. 4. — P. 433-450.

74. Ben-Haim Y., Litsyn S. Upper Bounds on the Rate of LDPC Codes as a Function of Minimum Distance // IEEE Trans. Inf. Theory. — 2006. — May. — Vol. 52, no. 5. — P. 2092-2100.

75. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — Москва : Мир, 1976.

76. Smarandache R., Vontobel P. O. Quasi-Cyclic LDPC Codes: Influence of Proto-and Tanner-Graph Structure on Minimum Hamming Distance Upper Bounds // IEEE Transactions on Information Theory. — 2012. — Feb. — Vol. 58, no. 2.—P. 585-607.

77. MacKay D. J. C., Davey M. C. Evaluation of Gallager Codes for Short Block Length and High Rate Applications // Codes, Systems, and Graphical Models / ed. by B. Marcus, J. Rosenthal. — New York, NY : Springer New York, 2001. — P. 113-130.

78. Richardson T., Urbanke R. Modern coding theory. — Cambridge university press, 2008.

79. Ben-Haim Y., Litsyn S. A New Upper Bound on the Rate of Non-Binary Codes // 2006 IEEE International Symposium on Information Theory. — 2006. — P. 297301.

80. Burshtein D. On the Error Correction of Regular LDPC Codes Using the Flipping Algorithm // IEEE Transactions on Information Theory. — 2008. — Feb. — Vol. 54, no. 2.—P. 517-530.

81. О корректирующей способности кодов с малой плотностью проверок на четность / К. Ш. Зигангиров [и др.] // Пробл. передачи информ. — 2008. — т. 44, № 3. — с. 50—62.

82. Barg A., Mazumdar A. On the Number of Errors Correctable with Codes on Graphs // IEEE Transactions on Information Theory. — 2011. — Feb. — Vol. 57, no. 2.—P. 910-919.

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

84. Зяблов В. В., Йоханнессон Р., Лончар М. Просто декодируемые коды с малой плотностью проверок на основе кодов Хэмминга // Пробл. передачи информ. — 2009. — т. 45, № 2. — с. 25—40.

85. Ковалев С. И. Декодирование низкоплотностных кодов // Пробл. передачи информ. — 1991. — т. 27, № 4. — с. 51—56.

86. MacWilliams F. J., Sloane N. J. A. The theory of error-correcting codes. — North-Holland, 1991.

87. Alon N. Eigenvalues and expanders // Combinatorica. — 1986. — June. — Vol. 6, no. 2. — P. 83-96.

88. Маргулис Г. А. Явные конструкции расширителей // Пробл. передачи информ. — 1973. — т. 9, № 4. — с. 71—80.

89. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs // Combinatorica. — 1988. — Vol. 8, no. 3. — P. 261-277.

90. Kahale N. On the second eigenvalue and linear expansion of regular graphs // Proceedings., 33rd Annual Symposium on Foundations of Computer Science. — 10/1992.—P. 296-303.

91. Liva G., Chiani M. Protograph LDPC Codes Design Based on EXIT Analysis // IEEE GLOBECOM 2007 - IEEE Global Telecommunications Conference. — 11/2007. — P. 3250-3254.

92. Protograph-Based Raptor-Like LDPC Codes / T. Chen [et al.] // IEEE Transactions on Communications. — 2015. — May. — Vol. 63, no. 5. — P. 15221532.

93. Bazarsky A., Presman N., Litsyn S. Design of non-binary quasi-cyclic LDPC codes by ACE optimization //2013 IEEE Information Theory Workshop (ITW). — 09/2013.—P. 1-5.

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

95. Xiao-Yu Hu, Eleftheriou E., Arnold D. M. Regular and irregular progressive edge-growth tanner graphs // IEEE Transactions on Information Theory. — 2005. — Jan. — Vol. 51, no. 1. — P. 386-398.

96. Tal I., Vardy A. List Decoding of Polar Codes // IEEE Transactions on Information Theory. — 2015. — May. — Vol. 61, no. 5. — P. 2213-2226.

97. Deep Learning Methods for Improved Decoding of Linear Codes / E. Nachmani [et al.] // IEEE Journal of Selected Topics in Signal Processing. — 2018. — Feb. —Vol. 12, no. 1.—P. 119-131.

98. Scaling Deep Learning-Based Decoding of Polar Codes via Partitioning / S. Cammerer [et al.] // GLOBECOM 2017 - 2017 IEEE Global Communications Conference. — 12/2017. — P. 1-6.

99. Bennatan A., Choukroun Y., Kisilev P. Deep Learning for Decoding of Linear Codes - A Syndrome-Based Approach // 2018 IEEE International Symposium on Information Theory (ISIT). — 06/2018. — P. 1595-1599.

100. Protograph-Based Raptor-Like LDPC Codes for Rate Compatibility with Short Blocklengths / T. Chen [et al.] //2011 IEEE Global Telecommunications Conference - GLOBECOM 2011. — 12/2011. — P. 1-6.

101. Richardson T. J., Urbanke R. Multi-edge type LDPC codes //. — 2002.

102. Deep Residual Learning for Image Recognition / K. He [et al.] // 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). — 06/2016. — P. 770-778.

103. Goodfellow I., Bengio Y., Courville A. Deep Learning. — MIT Press, 2016. — http://www.deeplearningbook.org.

104. Polyanskiy Y., Poor H. V., Verdu S. Channel Coding Rate in the Finite Blocklength Regime // IEEE Transactions on Information Theory. — 2010. — May. — Vol. 56, no. 5.—P. 2307-2359.

105. Non-orthogonal transmission technology in LTE evolution / Y. Yuan [et al.] // IEEE Communications Magazine. — 2016. — Vol. 54, no. 7. — P. 68-74.

106. Nikopour H., Baligh H. Sparse code multiple access // Personal Indoor and Mobile Radio Communications (PIMRC), 2013 IEEE 24th International Symposium on. — IEEE. 2013. — P. 332-336.

107. 3GPP R1-164688. RSMA / Qualcomm Inc. — 2016.

108. 3GPP R1-164689. RSMA / Qualcomm Inc. — 2016.

109. Roberts L. G. ALOHA packet system with and without slots and capture // ACM SIGCOMM Computer Communication Review. — 1975. — Vol. 5, no. 2. — P. 28-42.

110. S.Tsybakov B. Survey of USSR Contributions to Random Multiple-Access Communications // IEEE Transactions on Information Theory. — 1985. — Vol. 31, no. 2. — P. 143-165.

111. Casini E., De Gaudenzi R., Del Rio Herrero O. Contention Resolution Diversity Slotted ALOHA (CRDSA): An Enhanced Random Access Schemefor Satellite Access Packet Networks // IEEE Transactions on Wireless Communications. — 2007. — July. — Vol. 6, no. 4. — P. 1408-1419.

112. Liva G. Graph-based analysis and optimization of contention resolution diversity slotted ALOHA // IEEE Transactions on Communications. — 2011. — Vol. 59, no. 2. — P. 477-487.

113. Paolini E., Liva G., Chiani M. Coded Slotted ALOHA: A Graph-Based Method for Uncoordinated Multiple Access // IEEE Transactions on Information Theory. — 2015. — Dec. — Vol. 61, no. 12. — P. 6815-6832.

114. Shih-Chun Chang, 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.

115. Бассалыго Л. А., Рыков В. В. Гиперканал множественного доступа // Пробл. передачи информ. — 2013. — т. 49, № 4. — с. 3—12.

116. Бассалыго Л. А., Пинскер М. С. Вычисление асимптотики суммарной пропускной способности M-частотного бесшумного канала с множественным доступом для T пользователей // Пробл. передачи информ. — 2000. — т. 36, № 2. — с. 3—9.

117. Вильхельмссон Л., Зигангиров К. Об асимптотической пропускной способности одного многопользовательского канала // Пробл. передачи информ. — 1997. — т. 33, № 1. — с. 12—20.

118. Гобер П., Винк А. Х. Замечание к статье Л. Вильхельмссона и К.Ш. Зиган-гирова «Об асимптотической пропускной способности одного многопользовательского канала» // Пробл. передачи информ. — 2000. — т. 36, № 1. — с. 21—25.

119. Han Vinck A. J., Keuning K. J. On the capacity of the asynchronous T-user M-fre-quency noiseless multiple-access channel without intensity information // IEEE Transactions on Information Theory. — 1996. — Vol. 42, no. 6. — P. 22352238.

120. Vinck A. J. H., Keuning J., Sang Wu Kim. On the capacity for the T-user M-fre-quency noiseless multiple access channel without intensity information // Proceedings of 1995 IEEE International Symposium on Information Theory. — 1995. — P. 444-.

121. Gober P., Han Vinck A. J., Coetzee S. A new approach to uncoordinated frequency hopping multiple-access communication // Proceedings. 1998 IEEE In-

ternational Symposium on Information Theory (Cat. No.98CH36252). —1998. — P. 403-.

122. 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.

123. Viterbi A. J. Very low rate convolution codes for maximum theoretical performance of spread-spectrum multiple-access channels // IEEE Journal on Selected Areas in Communications. — 1990. — Vol. 8, no. 4. — P. 641-649.

124. Zigangirov K. S. Theory of Code Division Multiple Access Communication. — New Jersey : John Whiley, Sons, 2004.

125. Polyanskiy Y. A perspective on massive random-access // Information Theory (ISIT), 2017 IEEE International Symposium on. — IEEE. 2017. — P. 25232527.

126. Liva G., Chiani M. Protograph LDPC Codes Design Based on EXIT Analysis // IEEE GLOBECOM 2007 - IEEE Global Telecommunications Conference. — 11.2007. —c. 3250—3254.

127. Bennatan A., Burshtein D. Design and analysis of nonbinary LDPC codes for arbitrary discrete-memoryless channels // IEEE Transactions on Information Theory. — 2006. — $eBp. — t. 52, № 2. — c. 549—583.

128. A user-independent serial interference cancellation based coding scheme for the unsourced random access Gaussian channel / A. Vem [et al.] // Information Theory Workshop (ITW), 2017 IEEE. — IEEE. 2017. — P. 121-125.

129. Quasi-static SIMO fading channels at finite blocklength / W. Yang [et al.] // Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on. — IEEE. 2013. — P. 1531-1535.

130. Polyanskiy Y., Poor H. V., Verdu S. Channel Coding Rate in the Finite Blocklength Regime // IEEE Transactions on Information Theory. — 2010. — May. — Vol. 56, no. 5.—P. 2307-2359.

131. Tan V. Y., Moulin P. Fixed error asymptotics for erasure and list decoding // arXiv preprint arXiv:1402.4881. — 2014.

132. Wainwright M. J. Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting // IEEE Transactions on Information Theory. — 2009. — Vol. 55, no. 12. — P. 5728-5741.

133. Reeves G., Gastpar M. The sampling rate-distortion tradeoff for sparsity pattern recovery in compressed sensing // IEEE Transactions on Information Theory. — 2012. — Vol. 58, no. 5. — P. 3065-3092.

134. Reeves G., Gastpar M. A note on optimal support recovery in compressed sensing // Signals, Systems and Computers, 2009 Conference Record of the Forty-Third Asilomar Conference on. — IEEE. 2009. — P. 1576-1580.

135. Reeves G. Sparse Signal Sampling using Noisy Linear Projections : tech. rep. / Univ. Calif., Berkeley, Dept. of Electrical Engineering ; Computer Science. — 2008.

136. Quasi-static SIMO fading channels at finite blocklength / W. Yang [et al.] // 2013 IEEE International Symposium on Information Theory. —07/2013. —P. 15311535.

137. Cai T. T., Wang L. Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise // IEEE Transactions on Information Theory. — 2011. — July. — Vol. 57, no. 7.—P. 4680-4688.

138. Ordentlich O., Polyanskiy Y. Low complexity schemes for the random access Gaussian channel // Information Theory (ISIT), 2017 IEEE International Symposium on. — IEEE. 2017. — P. 2528-2532.

139. Ghez S., Verdu S., Schwartz S. C. Stability properties of slotted Aloha with mul-tipacket reception capability // IEEE Transactions on Automatic Control. — 1988. — Vol. 33, no. 7. — P. 640-649.

140. Explicit Maximally Recoverable Codes with Locality / P. Goplan [et al.] // IEEE Trans. Inf. Theory. — 2014. — Sept. — Vol. 60, no. 9. — P. 5245-5256.

141. Optimal Locally Repairable and Secure Codes for Distributed Storage Systems / A. S. Rawat [et al.] // IEEE Trans. Inf. Theory. — 2014. — Jan. — Vol. 60, no. 1. — P. 212-236.

142. Yekhanin S. Locally Decodable Codes // Found. Trends Theoretical Comput. Sci. — 2012. — Vol. 6, no. 3. — P. 139-255.

143. Cadambe V. R., MazumdarA. Bounds on the Size of Locally Recoverable Codes // IEEE Trans. Inf. Theory. — 2015. — Nov. — Vol. 61, no. 11. — P. 5787-5794.

144. Prakash N., Lalitha V., Kumar P. V. Codes with Locality for Two Erasures // Proceedings IEEE International Symposium on Information Theory (ISIT). — 06/2014. — P. 1962-1966.

145. Linear Locally Repairable Codes with Availability / P. Huang [et al.] // Proceedings IEEE International Symposium on Information Theory (ISIT). — 06/2015. — P. 1871-1875.

146. Wang A., Zhang Z. Repair Locality With Multiple Erasure Tolerance // IEEE Trans. Inf. Theory. — 2014. — Nov. — Vol. 60, no. 11. — P. 6979-6987.

147. Locality and Availability in Distributed Storage / A. S. Rawat [et al.] // Proceedings IEEE International Symposium on Information Theory (ISIT). — 06/2014. — P. 681-685.

148. Balaji S. B., Kumar P. V. Bounds on the rate and minimum distance of codes with availability //2017 IEEE International Symposium on Information Theory (ISIT). —06/2017. — P. 3155-3159.

149. Wang A., Zhang Z., Liu M. Achieving Arbitrary Locality and Availability in Binary Codes // Proceedings IEEE International Symposium on Information Theory (ISIT). — 06/2015. — P. 1866-1870.

150. Gabidulin E. M. Theory of Codes with Maximum Rank Distance // Probl. Inf. Transm. — 1985. — Vol. 21, no. 1. — P. 1-12.

151. Burshtein D., Miller G. Expander Graph Arguments for Message-Passing Algorithms // IEEE Trans. Inf. Theory. — 2001. — Vol. 47, no. 2. — P. 782-790.

152. Graham R., Knuth D., Patashnik O. Concrete Mathematics. — Addison-Wesley Pub., 1988.

153. McKay B. D., Wormald N. C., Wysocka B. Short cycles in random regular graphs // Electron. J. Combinat. — 2004. — Vol. 11, no. 1. — P. 66.