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

• Айдаркин Евгений Евгеньевич
• кандидат наук
• 2025

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

Введение

1. Современные методы защиты от стираний в каналах передачи данных

1.1. Модели каналов передачи данных

1.2. Стирающий канал передачи данных

1.3. Алгебраические коды исправления ошибок

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

1.4.1. Исправление стираний с помощью замены на ошибку

1.4.2. Исправление стираний алгоритмом по минимуму расстояния Хемминга

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

1.5. Алгебраические коды исправления стираний

1.5.1. Фонтанные коды (коды Лаби)

1.5.2. Раптор коды

1.5.3. Коды для облачных хранилищ

1.5.4. Коды, основанные на структурированных матрицах

1.5.5. Коды, основанные на сбалансированных структурах

1.6. Выводы по главе

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

2.1. Вектор вероятностей успешного декодирования как инструмент априорной оценки результата декодирования

2.2. Способ построения кодирующих матриц, основанный на латинских квадратах

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

2.3.1. Алгоритм генерации кодирующих матриц, основанный на равновесных столбцах

2.3.2. Модификация алгоритма генерации кодирующих матриц, основанного на равновесных столбцах

2.3.3. Экспериментальное определение наилучшего веса столбца

2.3.4. Итоги построения кодов РСт и МРСт

2.4. Построение алгоритмов кодирования и декодирования для кодов РСт и МРСт

2.4.1. Алгоритм кодирования

2.4.2 Декодирование по информационным совокупностям в случае ошибок

2.4.3. Декодирование по информационным совокупностям в случае стираний

2.4.4. Модификация алгоритма декодирования по информационным совокупностям в случае стираний в условиях отсутствия заранее подготовленного множества ИС

2.4.5. Модификация алгоритма декодирования по информационным совокупностям в случае стираний в гибридном режиме

2.4.6. Алгоритм декодирования по принципу распространения доверия для кода МРСт

2.5. Выводы по главе

3. Имитационная модель цифрового канала передачи данных с защитой

от стираний

3

3.1. Схема имитационной модели

3.2. Программная реализация имитационной модели

3.3. Модели потоков стираний

3.4. Экспериментальное исследование методов, основанных на структурированных матрицах

3.5. Исследование ВВУД для метода РСт

3.6. Экспериментальное исследование зависимости корректирующей способности метода РСт от типа стираний

3.7. Сравнение метода В. Пана с методом РСт в случае коротких кодовых слов

3.7.1. Сравнение метода В. Пана и метода РСт в случае фиксированного числа битовых стираний

3.7.2. Сравнение метода В. Пана и метода РСт в случае стираний символов расширенного алфавита

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

3.8. Сравнение скоростей работы алгоритмов декодирования по ИС в различных режимах

3.9. Сравнение работы алгоритма декодирования по ИС в гибридном режиме и алгоритма декодирования по принципу распространения доверия

3.10. Выводы по главе

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

4.1. Сетевое кодирование

4.2. Стандартная модель сетевого кодирования

4.3. Об одном классе сетевых кодов, исправляющих пакетные стирания

4.4. Новый метод каскадного канально-сетевого кодирования

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

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

4.7.1. Каскадный канально-сетевой код и символьные стирания

4.7.2. Сетевой код и пакетные стирания

4.7.3. Каскадный канально-сетевой код в случае пакетных и символьных стираний

4.7.4. Сравнение корректирующей способности построенного каскадного канального-сетевого кода с сетевым кодом

4.8. Выводы по главе

Заключение

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

Приложение А

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

Введение

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

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

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

Помехоустойчивое кодирование появилось с момента публикации К.

Шенноном работы «Математическая теория связи» в 1948 г. Значительный

6

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

Учеными разработано большое количество моделей каналов [1]. Среди них можно выделить двоичный симметричный канал (ДСК) передачи данных [1], [2], [3]. Он является самой простой моделью передачи данных по каналу с ошибками типа замены. А также двоичный симметричный канал со стираниями (ДСКС), который предполагает наличие как ошибок типа стирание, так и ошибок типа замены. Важным подклассом ДСКС является стирающий канал, в котором происходят только ошибки типа стирания [2], поскольку в таком случае можно добиться большей пропускной способности канала [4]. Большое внимание уделяется и физическим свойствам каналов, которые учитываются для построения мягких декодеров [5], [6], [7], [8].

Современные компьютеры быстрее всего работают с полями Р2 и F24 [9], [10]. Это связано как с особенностями архитектуры компьютеров, так и с частотой попадания в кэш-линейки процессоров. Поэтому важную роль в построении системы защиты от стираний играет возможность алгоритмов кодирования и декодирования работать в этих полях.

Учеными разработано большое количество методов защиты от ошибок. Среди них можно выделить блочные коды [11], линейные коды [12], циклические коды [2], [12], [13], каскадные коды [2], [14], [15]. Наиболее известными семействами кодов выступают коды Хемминга [16], [17], коды БЧХ [18], коды Рида-Соломона [19], мажоритарно декодируемые коды [20], сверточные коды [21], [22], [23], [24], турбо коды [15].

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

следующие группы кодов: фонтанные коды или коды Лаби [25], [26], [27],

7

раптор коды [26], [28], [29], коды для облачных хранилищ [30], [31], [32], [33], [34], [35], регенерирующие коды [36], а также коды, основанные на структурированных матрицах [37], [38], [39], [40], [41], [42], и коды, основанные на сбалансированных структурах [10], [43].

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

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

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

Задачи диссертационной работы. Основные задачи диссертационной работы:

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

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

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

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

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

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

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

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

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

1. Комплекс алгоритмов исправления стираний в данных, закодированных кодом исправления ошибок, основанный на применении декодеров кодов исправления ошибок. Отличительной особенностью комплекса является отсутствие изменений в используемых алгоритмах коррекции ошибок, а также учет числа стираний в кодовом слове до его декодирования, что позволяет уменьшать сложность алгоритма декодирования в процессе исправления стираний. Показана корректность комплекса алгоритмов (пункт 17 паспорта специальности, стр. 27-39).

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

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

4. Оценка вероятности ошибки декодирования данных,

закодированных кодами РСт или МРСт, в каналах с независимыми

равномерно распределенными стираниями. Оценка хорошо согласуется с

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

10

вероятности р* группирующихся стираний в канале и желаемой вероятности ошибки декодирования р#ес теоретически подобрать подходящие параметры кода РСт или МРСт (пункт 3 паспорта специальности, стр. 102-112).

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

6. Имитационная модель случайной коммуникационной сети передачи данных, в которой для защиты данных применяется каскадный канально-сетевой метод борьбы со стираниями. Имитационная модель, реализованная в виде программного комплекса, позволяет исследователям проводить эксперименты по оценке корректирующей способности разработанного метода кодирования по отношению к пакетным и символьным стираниям (пункт 3 паспорта специальности, стр. 145 - 149).

Положения, выносимые на защиту.

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

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

3. Имитационная модель цифрового стирающего канала передачи данных с возможностью выбора кодеров и декодеров, в том числе основанных на кодах РСт и МРСт, а также позволяющая моделировать равномерные и

группирующиеся стирания различной интенсивности.

11

4. Теоретическая оценка ошибки декодирования для кодов РСт и МРСт при передаче данных по каналу с равномерно распределенными независимыми стираниями.

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

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

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

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

Область исследования. Содержание диссертации соответствует паспорту специальности 2.3.8 - «Информатика и информационные процессы».

Пункт 17. Разработка методов обеспечения надежной обработки и

обеспечения помехоустойчивости информационных коммуникаций для целей

12

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

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

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

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

1. 18-ая Национальная молодежная научно-практическая конференция «Фундаментальные исследования с применением компьютерных технологий в науке, производстве, социальных и экономических процессах» (г. Новочеркасск, 2019 год);

2. Научная конференция «Современные информационные технологии: тенденции и перспективы развития» (г. Ростов-на-Дону, 2021 год, 2024 год);

3. Всероссийская научно-техническая конференция «Фундаментальные и прикладные проблемы математики и информатики в современной науке: теория и практика актуальных исследований» (г. Махачкала, 2022 год).

4. Международная мультиконференция «Математические методы в технике и технологиях», ММТТ-36 (г. Минск, 2023 год).

Публикации. Основные результаты по теме диссертации опубликованы

в 11 научных печатных изданиях [37], [44], [45], [46], [47], [48], [49], [50], [51],

[52], [53], из которых: 1 - в международных научных изданиях,

индексируемых Scopus [46], 4 - в рецензируемых журналах из списка ВАК

[37], [45], [49], [52], 4 - в материалах конференций и других научных печатных

13

изданиях [44], [50], [51], [53], 2 - свидетельства о государственной регистрации программы для ЭВМ [47], [48].

Личный вклад автора. Все результаты по теме диссертационного исследования получены лично автором. В работах, опубликованных в соавторстве [37], [44], [45], [46], [48], [49], [50], [52], [53] научными руководителями Деундяк В.М. и Могилевской Н.С. были поставлены задачи, предложены идеи по возможным подходам решения задач, обсуждены формы и содержание экспериментов.

Структура и объем работы. Диссертационная работа изложена на 187 страницах, включает 4 главы, 41 рисунок, 18 таблиц и список литературы из 144 наименований.

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

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

В третьей главе проводится экспериментальное исследование нового

метода равновесных столбцов с помощью созданной имитационной модели

14

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

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

1. Современные методы защиты от стираний в каналах передачи данных

Эта глава посвящена небольшому обзору основных методов защиты от стираний в каналах передачи данных. В разделе 1.1 приводятся необходимые сведения о моделях каналов передачи данных. Операторная постановка стирающего канала передачи данных представлена в разделе 1.2. Обзор алгебраических кодов исправления ошибок содержится в разделе 1.3. Раздел 1.4 посвящен возможному применению алгебраических кодов исправления ошибок для исправления стираний. Построено 4 алгоритма исправления стираний в данных, закодированных кодеками коррекции ошибок. Проведен анализ их преимуществ и недостатков. В разделе 1.5 приведен краткий обзор некоторых специализированных кодов борьбы со стираниями. Основные выводы главы содержатся в разделе 1.6.

1.1. Модели каналов передачи данных

Под ошибкой в теории информации понимается прием получателем неверного символа [2], [13], [54] в цифровом канале передачи данных. В качестве примера неформально предположим, что источник сообщения отправил слово «лайка», а получатель на выходе из канала получил слово «майка». В процессе передачи произошла замена одного символа на другой. Это является ошибкой при передаче данных по каналу. Стирание отличается от ошибки тем, что получатель знает место, где произошло стирание, но не знает значение символа [2], [13], [54]. Обращаясь к предыдущему примеру, получатель увидит сообщение «*айка», где символ «*» указывает на стирание. В рассмотренных примерах видна основная проблема передачи незакодированных специальным образом данных по каналам с ошибками: оригинальный текст сообщения может быть изменен. Все существующие каналы передачи данных вносят в передаваемые данные непреднамеренные искажения. Обычно для защиты передаваемых данных применяют методы помехоустойчивого кодирования. Цель помехоустойчивого кодирования -обеспечить такую передачу данных, в которой получатель сможет

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

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

Двоичный симметричный канал (ДСК) является самой простой моделью цифрового канала с ошибками [1], [2], [3] (см. рис. 1.1). Входом и выходом такого канала является множество {0,1}. ДСК определяется значениями переходных вероятностей, которые задаются выражениями

Р(0|0) = Р(1|1) = 1-р&; Р(0|1) = Р(1|0) = р0,

где р0 - вероятность битовой ошибки в канале. Переходные вероятности в ДСК не зависят от символов, которые передавались или принимались ранее, т.е. ДСК является каналом без памяти [1]. Канал называется симметричным, если переходные вероятности разных символов равны, например, Р(0|1) = Р(1|0), в противном случае - несимметричным.

передано

1 - Рп

принято

О

1

1 -ро

О

1

Рисунок 1.1. Граф переходов двоичного симметричного канала

Двоичный симметричный канал со стираниями (ДСКС) является важным частным случаем ДСК. По сравнению с ДСК в ДСКС в выходной алфавит добавляется символ стирания (см. рис. 1.2). Вероятность появления стирания обозначим q. С физической точки зрения стирание происходит в случае, когда физический сигнал попадает в зону неопределенности, в которой демодулятор не может достоверно опознать переданный символ [1], [2], [3]. Пример такой зоны показан на рисунке 1.3, по оси Ь отложено время, по оси А - амплитуда. Эту зону для двоичных сигналов {0,1} можно определить как 0.5 ± £, где 2е - величина коридора нечеткого принятия символа.

передано

1 — Ро — и принято

о

1

1 -ро-д

Рисунок 1.2. Граф модели симметричного канала со стираниями

О * 1

Рисунок 1.3. Условные функции плотности распределения вероятностей продетектированного сигнала и области принятия решений.

Важным частным случаем ДСКС является канал, содержащий ошибки только типа стирания. Для такого канала р0 = 0, т.е. ошибок в канале не происходит, либо ими можно пренебречь (р0 ^ 0). Этот вид канала примечателен тем, что в нем можно достичь большей пропускной способности канала по сравнению с ДСК [4]. Модель такого канала представлена на рисунке 1.4. Далее такие каналы будем называть стирающими [51].

Рисунок 1.4. Граф модели стирающего канала.

Заметим, что ДСК является частным случаем ^-чного дискретного канала без памяти (ДКБП). На входе ДКБП имеет конечный набор символов

, ■■■, — 1

}, на выходе - (Уо,У',-,Уд—1}. Также такой канал

характеризуется набором из q2 переходных вероятностей. Они постоянны во

19

времени, переходные вероятности различных символов независимы. Такой канал можно рассмотреть и в случае наличия стираний, тогда множество выходных символов будет иметь вид {у&,у—,У(-1,*}.

Заметим, что рассмотренные модели каналов никак не учитывают физических свойств сигналов и рассматривают только операции над символами. Существуют работы [5], [6], [7], [8], направленные на изучение свойств физических сигналов и их применение для построения мягких декодеров.

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

Замечание. Достоинством стирающих каналов является возможность достижения большей пропускной способности по сравнению с каналами с ошибками [4], [7].

1.2. Стирающий канал передачи данных

Рассмотрим схему передачи данных по стирающему каналу (см. рис. 1.5) [45], [54], где для обеспечения помехоустойчивости данных используется алгебраический [п, к,й]( - код С, где п - длина кода, к - размерность кода, й - минимальное расстояние кода, q - мощность поля Галуа ^, над которым задается код [4], [11], [13], [16], [17], [54], [55], [56]. Минимальное кодовое расстояние определяет корректирующую способность кода [4], [11], [13], [16], [17], [54], [55], т.е. число ошибок в одном кодовом слове, которое способен исправлять код:

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

Источник

э

Рисунок 4.1. Сеть «бабочка»

Опишем протокол передачи двоичных данных с помощью данной сети, не используя принцип сетевого кодирования. Первый такт: пакет X' передается от источника 5 к промежуточному звену А, пакет Х2, в свою очередь, передается от источника 5 к звену В. Второй такт: звено А перенаправляет пакет X' по всем своим выходным ребрам: к звену С и к получателю Я'; звено В, соответственно, к звену С и к получателю Я2. Третий такт: звено С сохраняет пакет Х2 у себя, и передает пакет X' звену И.

Четвертый такт: звено Ю передает пакет Хг получателю И2; звено С отправляет пакет Х2 звену И. Пятый такт: звено И передает пакет Х2 получателю Я'.

Таким образом, передача двух пакетов обоим получателям завершена за 5 тактов работы сети. Заметим, что если провести второй канал между звеньями С и Б, то количество тактов можно сократить до четырех (на третьем такте передавать звену Ю сразу два пакета, каждый по своему каналу. Тогда на 4 такте оба получателя получат все пакеты). Но проводить новый канал не всегда удобно, а иногда и невозможно.

Рассмотрим протокол передачи данных по этой сети, используя принцип сетевого кодирования. Первые два такта совпадают с протоколом, описанным выше, т.е. первый такт: пакет Хг передается от источника 5 к промежуточному звену А, пакет Х2, в свою очередь, передается от источника 5 к звену В. Второй такт: звено А перенаправляет пакет Хг по всем своим выходным ребрам: к звену С и к получателю звено В, соответственно, передает пакет Х2 к звену С и к получателю Я2. Третий такт: звено С складывает пакеты Хг и Х2, т.е. формирует новый пакет 2 — X' ф Х2 и передает его звену И. Четвертый такт: звено И отправляет пакет 2 получателям И' и . Передача по сети окончена. Действительно, получатель И' получил пакеты X' и 2 и может вычислить пакет Х2 с помощью следующего соотношения:

X' ф 2 — X' ф(Х' ф X2) — (X' ф X') ф Х2 — Х2. Аналогичным способом получатель вычислит пакет X':

Х2 ф 2 — Х2 ф (X' ф Х2) — X' ф (Х2 ф Х2) — X'. Таким образом, используя принцип сетевого кодирования, можно передать два пакета обоим получателям за 4 такта. Напомним, что в обычном случае это заняло 5 тактов. Итак, мы получили выигрыш в тактах даже для сравнительно малой сети. Исходя из этого, можно сделать вывод, что сетевое кодирование позволяет за меньшее время передавать информацию по сети передачи данных, что повышает эффективность передачи.

В сетевом кодировании по сравнению с коммуникационной сетью, работающей без преобразования данных в узлах, помимо классических ошибок и пакетных потерь рассматриваются также пакетные приобретения, символьные ошибки и символьные стирания [65]. В диссертации рассмотрены проблемы борьбы с символьными и пакетными стираниями. Заметим, что обычно пакет с символьным стиранием внутри исключают из дальнейших преобразований, т.е. заменяют пакетным стиранием [65], что уменьшает вероятность успешного декодирования. Отслеживание символьных стираний в процессе передачи весьма затруднительно, обычно требует оснащения всех внутренних узлов кодеками, что достаточно проблематично для сети и замедляет процесс передачи данных. Однако существует и другой подход в решении этой задачи.

В качестве инструментов борьбы с помехами в сетях обычно рассматривают адаптированные для случая сетевого кодирования [9] ранговые коды Габидулина [69], нелинейные подкоды ранговых кодов [9], [66], [136], каскады кодов, где внутренними являются канальные коды, а внешними -сетевые (см, например, [54]).

Цель этого раздела - применить коды РСт (см. главу 2) для задачи передачи данных по коммуникационной сети с использованием принципа сетевого кодирования. Для этого разрабатывается каскад двоичных кодов, где канальным кодом выступает код РСт [44], [45], [51], описанный в главе 2, а нелинейный подкод рангового кода из [143] выполняет роль сетевого кода.

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

Случайные сети можно также интерпретировать как детерминированные сети, которые неизвестны конкретному пользователю. Например, злоумышленник пытается передать данные через сеть, к которой у него нет легального доступа, он не знает ни архитектуру сети, ни пути следования пакетов данных. В данной работе будет рассматриваться именно такая сеть. В литературе такие сети называются случайными [65].

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

Легальным пользователям известны следующие параметры сети: алфавит сети, который отождествляется с полем ^, Ь - длина отправляемых пакетов, п - максимальное количество одновременно отправляемых пакетов в сеть. Аналогично детерминированным сетям используется матрица сети А, которая задает линейные комбинации между пакетами, проходящими через сеть. Для случайной сети она является неизвестной в момент передачи. Заметим, что с течением времени матрица сети А может изменяться, то есть пакеты могут преодолевать разные пути следования от источника к приемнику.

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

матрицу) [9]. Тогда набор таких «расширенных» векторов является п-префиксно независимым. Впоследствии получатель, используя эти векторы, сможет составить матрицу сети, или часть матрицы сети, необходимую для извлечения информации. Осложняют восстановление информации ошибки и стирания, происходящие во время передачи, так как в этом случае с ошибками будет получена и матрица сети А'. Для такого случая были построены кодеки, описанные в статье [9]. Они могут справляться с некоторым числом ошибок типа замены и некоторым количеством потерь пакетов - стираний.

Для сетей, где происходят только стирания, введена характеристика качества сети [143]. Под качеством сети понимается минимальное количество п-префиксно независимых пакетов, которые имеет на выходе получатель. Назовем этот параметр г& (г& < п). Далее будем предполагать, что при каждой передаче приходит г > г0 п-префиксно независимых пакетов. Параметр г может изменяться с течением времени для конкретной сети (например, из-за изменения качества связи в каналах коммуникационной сети, которое, может происходить по причине изменения погодных условий).

4.2. Стандартная модель сетевого кодирования

Алфавит сети состоит из всех элементов поля Галуа Рц. Предположим,

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

п пакетов Х',...,Хп длины т (X, е Р.), X, — (х,', ...,х,,т). Организуем из

пакетов X', ...,Хп матрицу X е Р(х т. У любого узла связи, входящего в сеть,

имеется собственный набор коэффициентов из поля Галуа Р(, которые

умножаются на соответствующие пакеты. Таким образом составляются

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

п х т

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

Рассмотрим следующую модель линейной сети с одним отправителем и несколькими получателями, которая впервые описана в работе Кёттера, Кшишанга [66]. Предполагается, что матрицы X и У связаны следующим соотношением:

У = АХ + Ъ1, (4.1)

где X Е х т ,У Е Р(+г х т. Матрица А Е Р+г х п задает линейные преобразования над исходными пакетами за все время передачи данных по сети. Матрица 2 Е х т представляет ошибочные пакеты, появившиеся на

каком-либо из участков сети передачи данных. Матрица Э Е х 3 задает линейные преобразования с ошибочными пакетами на пути к приемнику.

Предполагается, что матрицы Э,! неизвестны, а матрица А может быть как известной, так и случайной. Данная модель является стандартной для сетевого кодирования с ошибками. Для борьбы с ошибками в теории линейных сетей разрабатываются специальные сетевые кодеки [65], [67].

Стандартную модель сетевого кодирования можно применять и в случае, когда в сети имеются буквенные стирания. В этом случае сетевой алфавит расширяется либо звездочкой " *", либо более обширным вспомогательным алфавитом, и в матрице 2 появляются символы из расширения алфавита [144].

4.3. Об одном классе сетевых кодов, исправляющих пакетные стирания

Рассмотрим двоичные сетевые коды из [143], которые являются нелинейными подкодами ранговых кодов из [9]. Сетевым кодом называется код, который используется для передачи данных по коммуникационной сети с использованием принципов сетевого кодирования, способный бороться с ошибками и/или стираниями.

Введем основные параметры кода. Пусть Ь - длина кодового пакета, п -максимальное количество пакетов, отправляемых за 1 такт, Р2 - сетевой

алфавит. Пусть к - длина информационного вектора, п = тк, где т -коэффициент избыточности кода. Предположим, что т + п < Ь.

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

Рассмотрим кодирование информационного вектора х(б Е*). Пусть

В, = (О ... О Е О ... О) е Е*хп, I = 1, ...,т, (4.2)

где Е - единичная (к х ^)-матрица, расположенная на ¿-том месте, О - нулевая (к х ^)-матрица. Вычислим векторы г, = хВ, е Е+ . Затем зафиксируем стандартный базис {еу} пространства ЕЦп. Сгенерируем вектор-столбцы Х] = (еу\21,у,г2,],..-,гт]) длины п + т для у = 1,...,п. Составим из полученных вектор-столбцов матрицу X:

X =

(1 0 ■ 0\

0 0 1

г1,1 21,2 г1,п =[г?

г2,1 22,2 г2,п

; ;

\гт, 1 2т,2 • г / т,+

(4.3)

где г, = (г,',..., г,1п). Процесс кодирования переводит элемент

информационного пространства Е* в элемент пространства матриц X размера

(п + т) х п. Множество 2 является сетевым кодом. В операторном

представлении процесс кодирования выглядит следующим образом:

п т-, г(п+т)хп

С:Е2 ) .

Заметим, что в алгоритме кодирования происходит «приклеивание» единичной матрицы к матрице, составленной из множества векторов г,, г =

1,т. Соответствующая конструкция в литературе называется конструкцией

поднятия, либо лифтинговой конструкцией [143]. Использование конструкции

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

пакетами в сети А. Если матрица А получена не полностью, то это, безусловно,

осложняет процесс декодирования информации. Назовем такую матрицу А' е

139

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

У = ХА' (Е р2(п+т)хг),

или

Также можно переписать данное уравнение в терминах информационного сообщения х, обозначив А, = В,А':

По имеющимся параметрам можно ввести относительную избыточность построенного сетевого кода:

а = = т2(к + 1). (4.4)

В работе [143] описана связь данного кода с ранговыми кодами Кеттера-Кшишанга-Силвы [67].

Декодирование основано на решении следующего уравнения:

хА = (Уп+11 Уп+2 1 ■■■ \^п+т X где z - неизвестный вектор, А = (Аг\ А2 \ ■.. \Ат), А, = В,А', У, - строка матрицы У с порядковым номером £.

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

4.4. Новый метод каскадного канально-сетевого кодирования

Сетевой код из раздела 4.3 способен бороться только с пакетными стираниями [9]. Пакетное стирание - это разновидность ошибки, при которой теряется целый набор бит. В коммуникационной сети, использующей такой код, если в пакете произошло даже одно символьное стирание, то этот пакет необходимо исключить из дальнейшего использования. Это создает дополнительные трудности при декодировании, т.к. количество «нестертых» пакетов может быть очень мало. Представляется разумным дополнить защиту данных, передаваемых по сети, канальным кодом борьбы с символьными стираниями, т.е. организовать двуступенчатую систему защиты данных для борьбы как с пакетными, так и символьными стираниями, используя сетевой код из раздела 4.3 и канальный код из раздела 2.4.

Целью данного раздела является создание каскадного метода кодирования для коммуникационных сетей со стираниями, который будет способен бороться не только с пакетными стираниями, но и с символьными (идея предложена в [144]). Под методом будем понимать схему передачи данных по коммуникационной сети, алгоритмы кодирования и декодирования.

Построим модель каскадной канально-сетевой защиты данных, передаваемых по коммуникационной сети (см. рис. 4.2) [49]. Рассмотрим сетевой код из раздела 4.3, обозначим к длину информационного сообщения, т - избыточность кода. Оператор кодирования сетевого кода (см. раздел 1.2) действует следующим образом:

Г ■ С* т?п+т,п

В качестве канального кода рассмотрим код РСт из раздела 2.4 с кодирующей матрицей С размера (п + т) х (п + т + р), где р - избыточность канального кода, п = кт - параметр сетевого кода. Оператор кодирования канального кода действует по следующему правилу:

г . рп+т,п , рп+т+р,п

г2 "2 .

В кодере сетевого кода (КСК) информационное сообщение х Е Р2 с помощью алгоритма кодирования сетевого кода превращается в матрицу X Е Ь2 . Столбцы матрицы X поочередно подаются на вход кодера канального кода (ККК), результаты этого преобразования записываются как столбцы в матрицу V (е рп+т+р,п). Матрица V является закодированным сообщением и отправляется в коммуникационную сеть. В сети происходят как символьные, так и пакетные стирания. Действия сети описываются следующим оператором:

^: рп+т+р,п — рп+т+р,г

К полученным пакетам с символьными стираниями в декодере канального кода (ДКК) применяется канальное декодирование. Оператор декодирования канального кода действует по правилу:

Всь:Ргт+Р'Г ^РГт,Г и{Е#},

где Р2* = Р2 и {*}, Е# = (*, *,... , *). Если канальный код не в состоянии исправить некоторое количество символьных стираний, то данный пакет удаляется. Далее из оставшихся пакетов как из столбцов формируется матрица, к которой применяется декодер сетевого кода (ДСК). Отметим, что в этой матрице может остаться г' < г столбцов. Заметим, что если ДКК не смог исправить символьные стирания в пакете, то он генерирует пакетное стирание. Оператор декодирования сетевого кода действует по правилу:

Оъет: РГт,Г' - ^ и {Е#}. На выходе получается декодированное информационное сообщение или сообщение об ошибке декодирования. Таким образом совокупность описанных операторов определяет коммуникационную сеть с защитой от пакетных и символьных стираний:

Опет •Ось •Н^ Ссъ • СПет: Р( - Р* и {Е#}.

Алгоритмы кодирования и декодирования каскадного канально-сетевого кода приведены в разделе 4.6.

Рисунок 4.2. Схема передачи данных по сети с помощью каскадного канально-сетевого метода.

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

сетевого кода, за счет дополнительной избыточности канального кода. Для выбранного сетевого кода заявленная избыточность довольно велика (см. формулу 4.4). Добавление каскада повышает относительную избыточность следующим образом:

п(п + т + р)

ак =---= т2 (к + 1 + р),

к

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

Алгоритмы кодирования и декодирования в канально-сетевом каскаде построены на основе модификации разработанных ранее алгоритмов для сетевого и канального кодов [44], [45], [143] (см. разделы 2.5 и 4.4).

Алгоритм 4.1. Кодирование каскадного канально-сетевого кода.

Вход: набор матриц В,(е Р*хкт)Л = 1, ...,т, вида (4.2); кодирующая

матрица С (Е р2п+т>х<(п+т+/) канального кода метода РС; информационное сообщение х = (х±,х2, ...,хк), х, Е Р2.

Выход: закодированное сообщение V (Е р2^а+т+р^)Хт).

1) Вычислить г, = хВ, = (г^гц, ...^пЕ?2,1 = 1,

2) Зафиксировать базис е±, е2, ...,еп пространства ¥2++.

3) Сгенерировать векторы = (еу 1г1уу,22у,...,гту) длины п + т для У = 1,... ,п, где {еу} стандартный базис пространства Р2 .

3) Вычислить Vу = 1у в = (Уу-^Ул, ...,Уу)п+т+р), } = 1, -,П.

4) Сформировать и вернуть закодированное сообщение V, расположив векторы У] по столбцам:

^1,п+т+р ^п,п+т+р/

144

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

V г,- т-(п+т+р)хг\ ^

алгоритма декодирования поступает матрица Y (Е t2 ), г < п, г -

параметр качества сети.

Алгоритм 4.2. Декодирование каскадного канально-сетевого кода. Вход: набор матриц В,(Е F2xkm), i = 1,...,т, вида (4.2); пришедшая из

V г г- j-.(n+m+p)xrп,_ коммуникационной сети матрица Y (Е t2 ); кодирующая матрица и (Е

г(п+т)х(п+т+р)л t2 ).

Выход: информационный вектор х = (х±,х2,...,х*) или сообщение об ошибке декодирования.

1. Выделить множество Y = (Yl$,Yl%,...,Yl>) столбцов матрицы Y, в которых произошли символьные стирания.

2. Для каждого вектора Y1у из Y выполнить:

2.1. Составить множество J = (j1,j2,.- ,jX) номеров координат вектора Y1у, полученных без стираний. Если р < к, то переходим к следующему вектору (возврат на шаг 2).

2.2. Составить упорядоченное множество L = [1±,12,...,ls}, s = С. всех сочетаний по к элементов множества J, р •— 1.

2.3. Если р > s, то перейти на шаг 4. Построить (к X &)-матрицу Нр из столбцов матрицы G с номерами из 1р.

2.4. Вычислить rank(Hp). Если rank(Hp) < к, то р — р + 1 и переходим к следующему вектору (переход на шаг 2).

2.5. Вычислить Y1d = Y# H;1, где Yj = (Y.j, y£.....Y?l), zt Elp.

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

4. Если тг > к, то вернуть ошибку декодирования и выйти из алгоритма.

5. Из первых п строк матрицы У образовать матрицу А' (Е Р2+Хг).

6. Вычислить А, = В,А', Ь = 1, ...,т, сформировать А = (А'1 А2 1-1Ат).

7. Вычислить г = гапк(А). Если г < к, то вернуть ошибку декодирования и выйти из алгоритма.

8. Решить следующее матричное уравнение относительно г:

хА = (Уп+11 ^п+2 1 \^п+т X где У у - у-я строка матрицы У.

9. Вернуть г = (г±,г2, ...,г*).

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

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

В работе построена имитационная модель коммуникационной сети с защитой данных от пакетных и символьных стираний с помощью каскадного канально-сетевого кода в виде программного комплекса (основано на [48]).

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

результирующим. Далее рассмотрим схему взаимодействия основных модулей и функций программного средства, реализующего имитационной модель (см. рисунок 4.3). Источник сообщений может генерировать как случайные, так и заданные пользователем сообщения над полем Галуа Р2. Кодер сетевого кода переводит сообщение х Е Р2 в кодовое пространство, т.е. в матрицу X Е р2п+т>хп (подробнее см. (4.3)). Матрица X далее поступает на

вход канального кодера, который преобразует ее в матрицу V Е Р2 .

Для имитации передачи сообщения по сети генерируется случайная матрица сети А полного ранга, закодированное сообщение умножается на эту матрицу, тем самым имитируя реальную передачу данных по коммуникационной сети. При передачи в сети имитируются искажения данных. Для этого модулем генерации случайных искажений генерируется матрица стираний DZ (см (4.1)), имитирующая пакетные и символьные стирания (см. рисунок 4.4). Матрица искажений суммируется с данными, прошедшими через сеть по правилу: Ух Е Р2:х +*=*, где * - означает наличие символьного стирания V' = АУ + Э!. Если подразумевается пакетное стирание, то все элементы пакета помечаются *. На вход алгоритма декодирования канального поступает результат прохождения через сеть информационного сообщения с учетом внешних воздействий V'. Канальный декодер взаимодействует только с теми пакетами (столбцами матрицы V), в которых произошли символьные стирания. На выходе канального декодера формируется матрица X', которая затем поступает в декодер сетевого кода. На выходе декодера сетевого кода образуется результирующее сообщение х' или сообщение об ошибке декодирования. Далее происходит сравнение оригинального информационного сообщения х и прошедшего через коммуникационную сеть сообщения х'.

Рисунок 4.3. Схематичное представление имитационной модели

передачи данных по коммуникационной сети с защитой от стираний.

Приведем описание основных модулей имитационной модели коммуникационной сети с защитой от стираний.

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

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

2. Настраивает вид сообщений для источника. Отвечает за длину передаваемых пакетов, тип сообщений - случайные или заданные пользователем.

3. Настраивает параметры генерации стираний. Передает тип стираний и их параметры в модуль генерации случайных сообщений.

4. Настраивает параметры передачи данных по сети, которые необходимо зафиксировать для проведения экспериментов.

5. Указывает, какой кодек использовать в текущий момент.

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

1. Фиксирует параметры сети, используемые для проведения эксперимента или единичной передачи данных.

2. Фиксирует результат текущего эксперимента.

3. Аккумулирует статистику текущего эксперимента.

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

Программная реализация имитационной модели передачи данных по коммуникационной сети с защитой от символьных и пакетных стираний для проведения экспериментов была создана на языке С++ с использованием фреймворка QT и библиотеки для работы с полями Галуа NTL [136]. Имитационная модель построена как дополнение имитационной модели, описанной в главе 3 диссертационного исследования.

Программный комплекс имитационной модели реализован с использованием графического интерфейса таким образом, что пользователь при желании может наблюдать основные этапы процесса кодирования и декодирования. Также реализован выбор типа кодирования: канал (описан в разделе 3), сеть (простое применение сетевого кода, рисунок 4.4), каскад (каскадный канально-сетевой код, рисунок 4.5).

Л Имитационная модель

Эксперименты Параметры

Тип кодирования:

Закодировать

Избыточность:

Сеть V/ |з

Введите сообщение: Закодированное сообщение:

100000000000000 0 10000000000000 001000000000000 000100000000000 000010000000000 000001000000000 000000100000000 0000000 10000000 000000001000000 000000000 100000 0000000000 10000 00000000000 1000 000000000000100 0000000000000 10 00000000000000 1 101010000000000 00000 10 10 100000 0000000000 10 10 1

Полученное из сети сообщение:

Результат декодирования:

Отправить->

10 100 10 1*10 1110 |ю 10 1

110 100 11100000 1

110110000011*0 1 Декодировать

010100000000110

10 1*10 11*10 110 1

0 10 10*10 100 00 10

1 10 *1 10 10 1 1000 1

00 100 10*0 1 100 10

•0 11100 00 100 110

•11111110 1000 10

0 1 10*0 10 1 10000 1

0011100110 10101

011101010110010

•000 10 100 1000 11

1**011110 001010

11010*1000*1010

10001101*010010

1**10000 10 11001

Рисунок 4.4. Графический интерфейс программного средства имитационной модели сетевого и канального кодирования в режиме сеть.

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

Эксперименты Параметры

Тип кодирования: Избыточность:

Каскад й

Введите сообщение: Закодированное сообщение:

10 10 1 011001111111000

10 10 11110011010

Закодировать 000 11000 10 1000 1

00 110 110 11000 10

001100110000001

110011100111100

011100001101100

00000000 1 1 100 11

10 110 10000 11111

110010111101010

001111111010100

110011111000101

101110001010111

0 110 10 100 1000 11

11110 10 10 110 100

00 1100 110 10 10 10

011101100110101

110011011001011

111001101010101

001111011101100

110010011000110

Полученное из сети сообщение:

Результат декодирования:

10 1 100 1*0 100 1 10 А 10 10 1

040 10 1 1 140 10 1

01110100111111" Декодировать

•О'О110'0 111100

0 1110 1100 11 100 1

000 100 110 11*111

10*110001100*10

0 10 101011*11*0 1

011110*10*11000

101011101001111

001*0 00111110*1

110100111*0 11 10

0 10 100111111001

0 10 1001111*10 10

0000 10 1000 10 110

0000*01110*0010

0 10 111010101001

00*110100011100

011100110001100

111000101100001

0011100110110 10 V

Рисунок 4.5. Графический интерфейс программного средства имитационной модели сетевого и канального кодирования в режиме каскад.

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

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

4.7.1. Каскадный канально-сетевой код и символьные стирания

Для каждого набора параметров канального кода, сетевого кода, параметров коммуникационной сети, параметров генерации стираний проведено 1000 итераций имитации передачи сообщений по сети. В таблице 4.1 представлен процент успешности декодирования в зависимости от двух характеристик символьных стираний: общего количества пакетов, на которые попали символьные стирания, и максимального количества символьных стираний, пришедшихся на один пакет.

Основным показателем качества передаваемых сообщений через коммуникационную сеть является процент успешности декодирования каскадного канально-сетевого кода. В таблице 4.1 приведены результаты некоторых экспериментов, которые проводились при следующих параметрах каскадного кода: длина передаваемого сообщения к = 5 символов, коэффициент избыточности сетевого кода т = 3 и канального кода р = 4, при этом количество пакетных стираний всегда равнялось 5. Напомним, что пакет это вектор длины п + т + р, являющийся столбцом матрицы V (см. раздел 4.4). Анализ показывает, что каскадный код может успешно бороться с пакетными и символьными стираниями, причем декодирование возможно даже в случае максимального числа символьных стираний в пакете для рассмотренной избыточности канального кода.

Таблица 4.1. Процент успешности декодирования каскадного канально-

сетевого кода для разных типов символьных стираний

Символьные стирания Процент успешности

Кол-во Процент Кол-во

затронутых затронутых стираний в декодирования, %

пакетов пакетов, % пакете

0-5 0 - 33 1-4 100

6 40 1-3 100

6 40 4 99

7 47 1 98

7 47 2 99

7 47 3 97

7 47 4 98

8 53 1 98

8 53 2 90

8 53 3 69

8 53 4 60

9 60 1 83

9 60 2 63

9 60 3 33

9 60 4 0

Замечание. Результаты экспериментов во многом зависят от самой коммуникационной сети. Поэтому в результатах экспериментов приведены средние значения для экспериментов с 10 тыс. коммуникационных сетей, матрица А которых построена случайно.

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

152

4.7.2. Сетевой код и пакетные стирания

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

Для каждого типа параметров было проведено 1000 итераций, в качестве матрицы А сетевого кодирования использована случайная матрица полного ранга. Заметим, что количество пакетов, отправляемых в сеть, при длине сообщения к и коэффициенте избыточности сетевого кода т равно кт. Например, если к = 3 и т = 3, то количество отправляемых пакетов равно 9.

Таблица 4.2. Процент успешности декодирования сетевого кода с коэффициентом избыточности 2.

Длина сообщения (к) Избыточность (т) Количество пакетных стираний Процент пакетных стираний, % Процент успешности декодирования, %

5 2 0-4 0-40 100

5 2 5 50 97,3

5 2 6 60 89,3

5 2 7 70 58,2

5 2 8-10 80-100 0

Анализ таблицы 4.2 показывает, что сетевой код с коэффициентом избыточности 2 может исправлять до 4 пакетных стираний с вероятностью 1, но не может исправить более 7 пакетных стираний. Заметим, что при потере 5 пакетов (50 % передаваемых данных) процент успешного декодирования составляет 97,3%. Это позволяет сделать вывод, что сетевой код хорошо справляется с исправлением пакетных стираний.

Таблица 4.3. Процент успешности декодирования сетевого кода с

коэффициентом избыточности 3.

Длина сообщения (к) Избыточность (т) Количество пакетных стираний Процент пакетных стираний, % Процент успешности декодирования, %

5 3 0-9 0-60 100

5 3 10 67 99,9

5 3 11 73 98,9

5 3 12 80 93,8

5 3 13 87 58,7

5 3 14-15 93-100 0

При увеличении коэффициента избыточности сетевого кода исправляется большее количество пакетных стираний (таблица 4.3). При потере 87% пакетов процент успешного декодирования составляет 58,7%.

Таблица 4.4. Процент успешности декодирования сетевого кода с

коэффициентом избыточности 4.

Длина сообщения (к) Избыточность (т) Количество пакетных стираний Процент пакетных стираний, % Процент успешности декодирования, %

5 4 0-16 0-80 100

5 4 17 85 99,1

5 4 18 90 89,2

5 4 19-20 95-100 0

Анализ таблиц 4.2-4.4 показывает, что с увеличением избыточности кода наблюдается тенденция увеличения процента успешности для большого количества пакетных стираний. При потере 90% пакетов процент успешного декодирования составляет 89,2% при коэффициенте избыточности т = 4 (см. таблицу 4.4).

Таблица 4.5. Процент успешности декодирования сетевого кода с коэффициентом избыточности 5.

Длина сообщения (к) Избыточность (т) Количество пакетных стираний Процент пакетных стираний, % Процент успешности декодирования, %

5 5 0-22 0 - 88 100

5 5 23 92 99,7

5 5 24 96 27,5

5 5 25 100 0

Анализ таблицы 4.5 позволяет сделать вывод, что при коэффициенте избыточности, совпадающем с длиной сообщения, присутствует возможность успешно декодировать сообщение даже в случае одного непотерянного пакета (27,5% успешных случаев декодирования). А со 100% исходом можно восстановить вплоть до 88% потерянных пакетов.

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

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

4.7.3. Каскадный канально-сетевой код в случае пакетных и символьных стираний

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

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

р = 4.

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

Сетевой код (т.) Канальный код (Р) Кол-во затронутых пакетов, шт. (% от общего количества пакетов) Кол-во стираний в пакете

5 3 4 5 (30%) 0-5 (0-30%) 1-4 100

5 3 4 5 (30%) 6 (40%) 1-3 100

5 3 4 5 (30%) 6 (40%) 4 99

5 3 4 5 (30%) 7 (47%) 1 98

5 3 4 5 (30%) 7 (47%) 2 99

5 3 4 5 (30%) 7 (47%) 3 97

5 3 4 5 (30%) 7 (47%) 4 98

5 3 4 5 (30%) 8 (53%) 1 98

5 3 4 5 (30%) 8 (53%) 2 90

5 3 4 5 (30%) 8 (53%) 3 69

5 3 4 5 (30%) 8 (53%) 4 60

5 3 4 5 (30%) 9 (60%) 1 83

5 3 4 5 (30%) 9 (60%) 2 63

5 3 4 5 (30%) 9 (60%) 3 33

5 3 4 5 (30%) 9 (60%) 4 0

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

4.7.4. Сравнение корректирующей способности построенного каскадного канального-сетевого кода с сетевым кодом

Для сравнения качества исправления стираний сетевым кодом (см. раздел 4.3) и каскадным канально-сетевым кодом (см. раздел 4.4) с помощью имитационной модели из раздела 4.6 проведен ряд экспериментов. Опишем условия и результаты одного из них.

Для проведения сравнительного эксперимента каскадного канально-сетевого кода с сетевым кодов выбраны следующие параметры: длина передаваемого сообщения к = 5 символов, коэффициент избыточности сетевого кода т = 3 и канального кода р = 4 (только для каскадного кода), при этом количество пакетных стираний всегда равняется 5. Заметим, что избыточность каскадного кода таким образом, становится выше - длина каждого вектор-столбца, передаваемого по сети, больше на 4. При этом избыточность повышается с 54 до 66 (~22%). Однако, это нивелируется тем фактом, что сетевой код не способен справляться даже с единичным символьным стиранием. Это значит, что, если в процессе передачи стерся хотя бы один символ внутри пакета, весь пакет оказывается стертым. Эксперименты проводились для двух кодов при одинаковом шаблоне стираний, с учетом отличий в избыточности кодов. Проведено 1000 итераций для каждого набора параметров канального кода, сетевого кода, параметров коммуникационной сети и шаблона сгенерированных стираний.

Таблица 4.7. Процент успешности декодирования каскадного метода и классического сетевого кода

Символьные стирания Процент успешности декодирования, %

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

0-5 1-4 100 100

6 1-4 98 100

7 1 92 99

7 2 91 99

7 3 94 94

7 4 90 90

8 1 63 98

8 2 62 86

8 3 56 69

8 4 53 53

9 1 0 93

9 2 0 69

9 3 0 25

9 4 0 0

Количество пакетных стираний для проведения экспериментов полагалось равным 5 (см. таблицу 4.7). При количестве затронутых пакетов, не превосходящем 5 из 15 пакетов (33%), передаваемых по сети, символьными стираниями оба метода справляются в 100% случаев. При увеличении затронутых пакетов происходит падение корректирующей способности. При достижении 4 символьных стираний в каждом пакете каскадный метод перестает исправлять символьные стирания, что говорит о равенстве итоговой корректирующей способности между кодами. Но если стираний становится меньше, то каскадный код справляется с символьными стираниями и повышает итоговую корректирующую способность относительно базового сетевого кода.

В таблице 4.7 в последних двух столбцах представлены проценты

успешности декодирования сетевого и каскадного канально-сетевого методов

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

Анализ показывает, что процент успешного декодирования у каскадного кода

всегда больше или равен проценту успешного декодирования сетевого кода.

Это наблюдение позволяет сделать вывод о том, что каскадный канально-

158

сетевой метод лучше подходит для применения в сетях с пакетными и символьными стираниями.

4.8. Выводы по главе

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

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

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

4. Проведенное экспериментальное исследование выявило, что каскадный метод успешно справляется как с символьными, так и с пакетными стираниями. Число символьных стираний, успешно корректируемых методом, ограничено только теоретической границей (см. (1.2)). При повышении

избыточности каскадного кода по сравнению с сетевым примерно на 20% средний процент успешного декодирования повышается на ~20%.

Основные результаты этой главы опубликованы в работах: [49].

Заключение

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

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

2. Изучен класс методов защиты от стираний, основанный на

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

двоичных метода РСт и МРСт, включающих в себя алгоритмы построения

порождающей матрицы кода, алгоритмы кодирования и декодирования.

Качество порождающих матриц построенных кодов оценено с помощью

вектора вероятностей успешного декодирования. Основным преимуществом

предложенных кодов является высокая скорость построения порождающих

161

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

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

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

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

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

двоичных кодов РСт и одного известного метода сетевого кодирования.

162

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

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

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

1. Васильев, К. К. Теория электрической связи: учебное пособие / К.К. Васильев, В.А. Глушков, А.В. Дормидонтов, А.Г. Нестеренко; Под ред. К.К. Васильева. — Ульяновск : УлГТУ, 2008. — ISBN: 978-59795-0203-8.

2. Золотарёв, В.В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник / В.В. Золотарёв, Г.В. Овечкин ; Под ред. чл.-корр. РАН Ю.Б. Зубарева. — Москва : Горячая линия-Телеком, 2004. - 127 с.

3. Скляр, Б. Цифровая связь. Теоретические основы и практическое применение. / Б. Скляр - Москва : Издательский дом «Вильямс», 2003. - 1104 с.

4. Вернер, М. Основы кодирования. Учебник для ВУЗов / М. Вернер. Мир программирования. — Москва : Техносфера, 2006. — ISBN: 594836-019-9.

5. Гладких, А. А. Метод формирования мягких решений в системе широкополосного канала связи с неизвестными параметрами / А.А. Гладких, Е.С. Баскакова // Периодический научно-технический и информационно-аналитический журнал. Инфокоммуникационные технологии, Том 12, № 4, 2013. - С.12-17.

6. Гладких, А. А. Формирование мягких решений в системе широкополосного канала связи с QPSK-QAM / А. А. Гладких, Н. Ю. Чилихин // Автоматизация процессов управления № 3 (33), 2013. - С. 8-18.

7. Гладких, А. А. Методы лексикографического декодирования избыточных кодов на базе модификаций стирающего канала связи / А. А. Гладких // Диссертация на соискание ученой степени д.т.н. -Ульяновск : УлГТУ. - 2015. - 315 с.

8. Гладких, А. А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи / А. А. Гладких. - Ульяновск : УлГТУ, 2010. - 379 с.

9. Koetter, R. Coding for errors and erasures in random network coding / R. Koetter, F.R. Kschischang // IEEE Transactions on Information Theory. 2008. V. IT-54. № 8. P. 3579-3591.

10. Kralevska, K. Balanced XOR-ed coding / K. Kralevska, D. Gligoroski, H. 0verby // In Advances in Communication Networking - 19th EUNICE/IFIP, volume 8115 of LNCS, Springer, 2013, p. 161-172.

11. Могилевская, Н.С. Введение в теорию информации: учеб. пособие / Н.С. Могилевская // Ростов-на-Дону: Издательский центр ДГТУ, 2013.

12. Вернер, М. Основы кодирования / М. Вернер. — Москва : Техносфера, 2004. - 284 с.

13. Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / р. Морелос-Сарагоса; пер. с англ. В.Б. Афанасьева — Москва : Техносфера, 2006. - 320 с.

14. Форни, Д. Каскадные коды / Д. Форни; пер. с англ. под ред. С.И. Самойленко - Москва : Мир, 1970. - 208 с.

15. Красносельский, И.Н. Турбокоды: применение и перспективы / И.Н. Красносельский // Электросвязь. - 2001. - № 1. С. 17 - 20.

16. Кларк, Дж. Кодирование с исправлением ошибок в системах цифровой связи / Дж. Кларк, Дж. Кейн; пер. с англ. под ред. Б.С. Цыбакова - Москва : Радио и связь, 1987. - 392 с.

17. Питерсон, У. Коды, исправляющие ошибки / Питерсон У., Уэлдон Э; пер. с англ. под ред. Р. П. Добрушина и С. И. Самойленко. - Москва : Мир, 1976. - 594 с.

18. Боуз, Р. К. Об одном классе двоичных групповых кодов с

исправлением ошибок / Р. К. Боуз, Д. К. Рой-Чоудхури //