Государственное образовательное учреждение
высшего профессионального образования
Московский физико-технический институт
(государственный университет)
На правах рукописи
Владимиров Сергей Михайлович
Повышение помехоустойчивости
информационных коммуникаций с помощью
кодов с малой плотностью проверок на четность и
сетевого кодирования 05.13.17 – Теоретические основы информатики
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Долгопрудный – 2011
Работа выполнена в Московском физико-техническом институте (ГУ).
Научный руководитель: доктор технических наук, профессор Габидулин Эрнст Мухамедович
Официальные оппоненты: доктор технических наук, профессор Зяблов Виктор Васильевич Институт проблем передачи информации имени А. А. Харкевича;
кандидат физико-математических наук, Обернихин Виталий Александрович, ООО «Параллелз»
Ведущая организация: Санкт-Петербургский государственный университет аэрокосмического приборостроения
Защита состоится 1 марта 2011 г. в 15:00 на заседании диссертационного совета Д 212.156.04 при Московском физико-техническом институте (ГУ) по адресу: 141700, г. Долгопрудный, Московская обл., Институтский пер., д. 9, ауд. 204 Нового корпуса.
С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ).
Автореферат разослан 27 января 2011 г.
Ученый секретарь диссертационного совета, кандидат технических наук Куклев Л. П.
Общая характеристика работы
В настоящее время сетевое кодирования Актуальность работы.
является новой и быстроразвивающейся областью исследований как в теории сетей, так и в теории информации. Телекоммуникационные сети – к началу XXI века это проводные, беспроводные, оптоволоконные – в том числе самые различные по своему назначению, вошли в повседневную жизнь.
Исследованию таких сетей посвящено большое количество работ. Однако вплоть до 2000 года существенным было требование, чтобы в существующих телекомуникационных сетях передача сообщений происходила от источника к получателю через цепочку промежуточных узлов, работающих по принципу «принимай и передавай далее», то есть без взаимного влияния различных информационных потоков друг на друга. Хотя промежуточные узлы могли временно хранить у себя пакеты и группировать их для более оптимальной передачи (либо разбивать на более мелкие части), считалось, что другая обработка пакетов не нужна. Сравнительно недавно было показано [1], что методами сетевого кодирования можно показать лучшие результаты в использовании пропускной способности сети, в том числе без радикальных изменений в её инфраструктуре.
В 2007 и 2008 годах были представлены первые работы по случайному сетевому кодированию, среди которых стоит отметить работы Кёттера, Кшишанга и Сильвы. В этих работах был представлен вариант использования сетевого кодирования для сетей, неимеющих чёткой структуры или алгоритма маршрутизации. В работах существенным образом использовалась теория рангового кодирования, разрабатываемая Габидулиным с 1980-х годов.
Ещё в 1960-х годах Галлагером были предложены коды с малой плотностью проверок на чётность. Кроме большой длины блока, что приближает их характеристики по исправлению ошибок на блок к так называемой границе Шеннона, их достоинством является вычислительная простота итеративного декодирования. Тем не менее, до середины 1980-х годов этих коды практически не исследовались. МакКей отмечает, что причиной этому являлось слабое развитие вычислительной техники, которое только в последнее время смогло полностью использовать всю мощь кодов с большой длиной блока. В настоящий момент коды широко используются, в том числе в новых стандартах спутниковой передачи данных DVB-S2 и WiMAX.
Возможность использования низкоплотностных кодов в сетевом кодировании активно исследуется в настоящее время.
Цель диссертационной работы состоит в повышении защиты от помех и увеличении пропускной способности информационных коммуникаций с использованием сетевого кодирования и низкоплотностных кодов.
Для достижения поставленных целей были решены следующие задачи:
анализ существующих способов кодирования с целью защиты от помех для сетевого кодирования;
анализ возможностей использования известных кодов с большим размером блока (в частности, кодов с низкой плотностью проверок на чётность) для сетевого кодирования;
анализ влияния сетевого кодирования на особенности исправления ошибок итеративными алгоритмами декодирования;
разработка нового метода использования низкоплотностных кодов для сетевого кодирования для повышения пропускной способности сети и защиты от помех;
обобщение методов использования низкоплотностных кодов для сетевого кодирования на произвольное число частей сообщения, получателей, произвольную структуру сети;
разработка методов использования низкоплотностных кодов для случайного сетевого кодирования.
Для уменьшения времени численного моделирования использования низкоплотностных кодов для случайного сетевого кодирования решена задача ускорения работы процедуры поиска и исправления ошибок в кодовых векторах двоичных низкоплотностных кодов для итеративного алгоритма с распространением доверия при использовании виртуальной машины Java в качестве среды исполнения.
Научная новизна состоит в улучшении пропускной способности сети с использованием сетевого кодирования с использованием кодов с низкой плотностью проверок на чётность:
1. показано, что сетевое кодирование при использовании двоичных кодов с малой плотностью проверок улучшает пропускную способность сети в том числе и для каналов с шумами, но в ограниченном диапазоне шумовых параметров канала;
2. предложен новый алгоритм декодирования и исправления ошибок в кодовых векторах двоичного МПП-кода для сетевого кодирования, улучшающий производительность сети с сетевым кодированием на большем диапазоне шумовых параметров канала;
3. предложенный алгоритм расширен на случай случайного сетевого кодирования;
4. предложенный алгоритм расширен на случай произвольного числа передаваемых пакетов и получателей.
Практическая значимость. Результаты, изложенные в диссертации, могут быть использованы для создания сети распространения данных с эффективным использованием пропускной способности каналов связи и с защитой от помех или потери пакетов, как это предложено в авторской работе [2].
На защиту выносятся следующие основные результаты и положения:
алгоритм поиска и исправления ошибок в кодовых векторах двоичных низкоплотностных кодов в сетевом кодировании для канала со модификация алгоритма для канала со стиранием для работы с различным числом пакетов, на которые при передаче делится кодовый модификация алгоритма для канала со стиранием для использования в случайном сетевом кодировании;
алгоритм поиска и исправления ошибок в кодовых векторах двоичных низкоплотностных кодов для канала с аддитивным белым гауссовским модификация алгоритма для канала с аддитивным белым гауссовским шумом для работы с различным числом пакетов, на которые при передаче делится кодовый вектор;
модификация алгоритма для канала с аддитивным белым гауссовским шумом для использования в случайном сетевом кодировании.
Апробация работы. Основные результаты диссертации докладывались на следующих конференциях:
51-я научная конференция МФТИ – Всероссийская молодёжная научная конференция с международным участием «Современные проблемы фундаментальных и прикладных наук», Долгопрудный, 2008 г. [3];
52-я научная конференция МФТИ – Всероссийская молодёжная научная конференция с международным участием «Современные проблемы фундаментальных и прикладных наук», Долгопрудный, 2009 г. [4];
IEEE R8 International Conference on Computational Technologies in Electrical and Electronic Engineering SIBIRCON-2010, Irkutsk Listvyanka, 53-я научная конференция МФТИ – Всероссийская молодёжная научная конференция с международным участием «Современные проблемы фундаментальных и прикладных наук», Долгопрудный, 2010 г. [6] Публикации. Материалы диссертации опубликованы в 9 печатных работах, из них 3 статьи в рецензируемых журналах [7–9], 1 статья в сборниках трудов конференций [5] и 3 тезиса докладов [3, 4, 6].
исследований, выполненных на кафедре радиотехники МФТИ (ГУ) в период с 2007 по 2011 годы. Личный вклад соискателя в опубликованные работы составляет в среднем не менее 70%. Результаты, выносимые на защиту
, получены автором самостоятельно. Все представленные в диссертации результаты получены лично автором.
Структура и объём диссертации. Диссертация состоит из введения, обзора литературы, 3 глав, заключения, библиографии и одного приложения.
Общий объем диссертации 114 страниц, из них 104 страницы текста, включая 31 рисунок. Библиография включает 31 наименование на 5 страницах.
Содержание работы Во введении обоснована актуальность диссертационной работы, сформулирована цель и аргументирована научная новизна исследований, показана практическая значимость полученных результатов, представлены выносимые на защиту научные положения.
В первой главе рассмотрено поведение алгоритма декодирования кодов с низкой плотностью проверок на чётность в сетевом кодировании для канала со стиранием и предложено его улучшение.
В модели сети «бабочка», изображённой на рис. 1, в каналах T Y, W X и U Z могут возникать ошибки (стирания). Для исправления ошибок используется двоичный код с малой плотностью проверок (двоичный МПП-код, двоичный низкоплотностный код), также называемый кодом с малой плотностью проверок на чётность или МППЧ-кодом (англ. low dencity parity check code, LDPC-code).
одного кодового вектора m двумя частями a и b от узла-источника S узлам-получателям Y и Z.
В случае, если сетевое кодирование не используется, то для передачи пакета целиком (обоих частей a и b исходного кодового вектора m) обоим конечным узлам Y и Z необходимо затратить пять итераций:
Если бы канал W X имел повышенную пропускную способность (два пакета за итерацию), это уменьшило бы число итераций, необходимое для передачи кодового вектора от S обоим получателям. Аналогичный результат может быть достигнут без изменения структуры сети (без изменения физических характеристик канала) с использованием сетевого кодирования. В этом случае по каналу W X передаётся не отдельные пакеты, а некоторая линейная рекомбинация пакетов (в рассматриваемом нами случае – побитовое сложение пакетов по модулю 2). Тогда для передачи кодового вектора обоим получателям достаточно 4-х итераций:
Рис. 2. Модель сети «бабочка» с сетевым кодированием.
Схема передачи пакетов приведена на рисунке 2.
Рассмотрен стандартный подход к восстановлению исходного кодового вектора и исправлению ошибок в нём и показано, что при использовании данного метода возникают дополнительные стирания, что можно выразить как увеличение вероятности возникновения стирания с p (без использования сетевого кодирования) до p (с использованием):
Данная оценка вместе с данными численного моделирования изображена на рис. 3.
Таким образом, хотя использование сетевого кодирования позволяет улучшить пропускную способность сети в целом, в двоично-симметричном канале со стираниями при наличии ошибок в каналах передачи (в рассматриваемом нами случае это каналы T Y, W X и U Z) эффект от использования сетевого кодирования при увеличении вероятности стирания бита уменьшается. Например, как показано на графике 4 для двоичного Рис. 3. Вероятность ошибки декодирования блока на конечном узле без использования сетевого кодирования и с использованием сетевого кодирования.
МПП-кода длиной 96 бит и скоростью около 1/2 эффект пропадает при p > 0.26. График построен при следующих условиях:
1. передача без сетевого кодирования без ошибок требует 5 итераций;
2. передача с сетевым кодированием без ошибок требует 4 итерации;
3. ошибка при передаче требует перепосылки, на которую тратится итерации в обоих случаях.
С целью уменьшения влияния сетевого кодирования на характеристики декодирования предложен новый алгоритм исправления ошибок на основе стандартного алгоритма с жёстким декодированием с алгоритмом передачи сообщений. Новый алгоритм построен на идее дополнения графа Таннера низкоплотностного кода дополнительными вершинами: символьным узлами, соответствующими битам принимаемых получателем сообщений, а также Рис. 4. Время передачи кодового вектора с учётом необходимости перепосылки ветора при ошибке декодирования.
узлами проверок, соответствующим связям между восстановливаемым вектором и принимаемыми сообщениями. Например, пусть исходная проверочная матрица кода определена в виде:
Рис. 5. Граф Таннера для двоичного МПП-кода с проверочной матрицей (2).
Исходный граф Таннера кода выглядит как показано на рис. 5. В новом алгоритме граф Таннера дополняется узлами как показано на рис. 6. Оба Рис. 6. Граф Таннера для двоичного МПП-кода с проверочной матрицей (2), дополненный символьными и проверочными узлами m1 и m2.
графа заполнены значениями символьных узлов в предположении, что на конечный узел Y пришло два сообщения m1 и m2 :
где e1, e2 - некоторые векторы ошибок, означающие происходящие стирания.
Показано, что в новом алгоритме можно использовать стандартное декодирование с жёстким решением с итеративным алгоритмом с передачей сообщений (англ. iterative message-passing algorithm), если использовать новую проверочную матрицу H и новый вектор x в качестве входных данных.
Построим новый вектор x как конкатенацию частично восстановленного вектора и принятых сообщений:
Количество бит в векторе – удвоенная длина кодового вектора m. Пусть H – проверочная матрица выбранного двоичного МПП-кода размером n k.
Построим новую, расширенную проверочную матрицу:
Рис. 7. Вероятность ошибки декодирования блока на конечном узле без использования сетевого кодирования, с использованием сетевого кодирования со стандартным и улучшенным алгоритмом декодирования.
Расширенная проверочная матрица 5 используется как проверочная матрица двоичного низкоплотностного кода для исправления ошибок (стираний) в векторе x (4) уже известным итеративным алгоритмом с передачей сообщений. После исправления ошибок, если все стирания исправлены, первые n бит вектора x (по длине оригинального вектора m) используется как результат декодирования.
Данный способ восстановления кодового вектора, а также поиска и исправления ошибок в нём, позволяет исправить больше ошибок, чем стандартный подход, как показано на рис. 7. В результате общая производительность сети при использовании сетевого кодирования будет выше, чем при отказе от использования сетевого кодирования при вероятности стирания бита в канале не выше p 0.33, а также выше, чем со стандартным алгоритмом декодирования, как показано на рис. 8.
Рис. 8. Время передачи кодового вектора на оба конечных узла с учётом необходимости перепосылки ветора при ошибке декодирования без сетевого кодирования, с сетевым кодированием со стандартным и улучшенным алгоритмом декодирования.
Если производительность оригинального алгоритма оценивается как O N log N, то нового алгоритма – O 2N log 2N, то есть замедляет работу декодера чуть более чем в два раза. Тем не менее, с учётом значительного выигрыша, который позволяет скомпенсировать использование сетевого кодирования, новый алгоритм стоит использовать.
Показано, что для простых случаев, как, например, для модели сети «бабочка», новый алгоритм может быть упрощён за счёт опускания шага предварительного восстановления m (левой части вектора x). Однако в более общем случае отсутствие данного шага может повлечь за собой отказ от декодирования. Доказана соответствующая лемма:
Лемма 1. Пусть восстанавливаемый кодовый вектор двоичного МПП-кода x может быть разбит на две группы битов x1 и x2 таким образом, что:
1. первая группа битов стёрта;
2. каждая строка проверочной матрицы соответствующего двоичного МПП-кода с равными единице битами, соответствующими первой и второй части принятого вектора, имеет, как минимум, два бита, равных единице, которые соответствуют первой части принятого вектора.
Тогда стирания в первой части x1 принятого вектора x не могут быть восстановлены с помощью итеративного декодирования с жёстким решением алгоритмом с передачей сообщений.
Результаты первой главы опубликованы в работе [7].
Во второй главе рассмотрен новый алгоритм декодирования для использования в гауссовых каналах. Алгоритм основывается на итеративном декодировании с мягким решением с распространением доверия, также известном как алгоритме Перла или алгоритм «сумма-произведение» (англ.
soft decoding iterative belief-propagation, sum-product algorithm). Используется аналогичная модификация входных параметров алгоритма (проверочной матрицы и восстанавливаемого кодового вектора).
Приведён способ модификации алгоритма для использования при случайном сетевом кодировании. Для этого передаваемые сообщения дополняются битовым полем, содержащим одну единицу на месте, соответствующем номеру части исходного кодового вектора. Пусть исходный кодовый вектор имеет вид Узел-отправитель делит вектор на две части, записывая элементы вектора в матрицу из двух строк, после чего дополняет её единичной матрицей:
Два передаваемых сообщения тогда имеют вид:
Из-за линейной рекомбинации пакетов (в неизвестном для получателя порядке) конечный узел получает следующие пакеты:
Из этих пакетов узел выделяет битовые поля:
Эти значения используются как для восстановления (с ошибками) кодового вектора m, так и для вычисления новой расширенной проверочной матрицы:
Данный подход с битовыми полями напоминает подход Кёттера и Кшишанга к использованию ранговых кодов для случайного сетевого кодирования, однако переносит их с ранговых кодов на двоичные МПП-коды.
Разница между ранговыми кодами и двоичными МПП-кодами приводит к необходимости отдельной защиты битовых полей сообщений (с помощью более медленного кода). Результаты численного моделирования при защите битового поля тем же двоичным МПП-кодом, а также с предположением об отсутствии ошибок в битовом поле (например, при использовании медленного кода), приведены на рисунках 9 и 10.
Рис. 9. Вероятность ошибки в блоке в зависимости от величины энергии на информационный бит для стандартного и нового алгоритма для случайного сетевого кодирования.
Показано, что отказ от использования предварительного восстановления исходного вектора, как и для канала со стиранием, может привести к отказу от декодирования в некоторых случаях. Доказана соответствующая лемма:
Лемма 2. Пусть принятый кодовый вектор двоичного МПП-кода x может быть разбит на две группы битов x1 и x2 таким образом, что:
Рис. 10. Вероятность ошибки в блоке в зависимости от величины энергии на информационный бит для стандартного и нового алгоритма для случайного сетевого кодирования при отсутствии ошибок в битовом поле.
1. первая группа битов стёрта, то есть вероятность каждого бита быть равным 1 или 0 равна 50%;
2. каждая строка проверочной матрицы соответствующего двоичного МПП-кода с равными единице битами, соответствующими первой и второй части принятого вектора, имеет, как минимум, два бита, равных единице, которые соответствуют первой части принятого Тогда первая часть x1 принятого кодового вектора x не может быть восстановлена итеративным алгоритмом декодирования с мягким решением с распространением доверия «сумма-произведение».
Результаты второй главы опубликованы в работе [8].
В третьей главе приведён метод оптимизации времени численного моделирования исправления ошибок в кодовых словах двоичных МПП-кодов при использовании алгоритма итеративного декодирования с распространением доверия «сумма-произведение».
Показано, что итеративный алгоритм декодирования с распространением доверия содержит большое количество циклов, которые могут быть раскрыты в последовательности команд, что уменьшит количество проверок условий.
В условиях, когда проверочная матрица двоичного МПП-кода является входными данными программы, подобное раскрытие не может выполняться на этапе компиляции программы. Поэтому требуется использовать механизм генерации кода программы в процессе моделирования, что было сделано с использованием библиотеки Javassist.
Рис. 11. Время моделирования без использования и с использованием предварительной генерации байт-кода декодера.
На рис. 11 показано время численного моделирования без предварительной генерации оптимизированного кода декодера, с генерацией, а также с генерацией и с заменой массивов r0 и r1 на переменные дополнительного класса. Моделирование выполнялось с использованием проверочной матрицы двоичного МПП-кода «408.3.834 (N=408, K=204, M=204, R=0.5)» из энциклопедии низкоплотностных кодов МакКея.
В результате, предложенный способ оптимизации позволяет уменьшить время, требуемое на моделирование использования двоичных МПП-кодов, а, следовательно, сократить время на исследование и моделирование способов построения телекоммуникационных сетей с использованием данных кодов.
Результаты третьей главы опубликованы в работе [9].
Список публикаций 1. Габидулин Э.М., Пилипчук Н.И., Владимиров С.М. и др. Сетевое кодирование // Труды Московского физико-технического института (государственного университета). 2010. Т. 1, № 2. С. 3–28.
2. Владимиров С.М. Использование сетевого кодирования и двоичных кодов с малой плотность проверок на чётность для широковещательной передачи данных // Информационные технологии моделирования и управления.
2010. Т. 4(63). С. 475–483.
3. Владимиров С.М. Использование кодов с малой плотностью проверок на чётность // Труды 51-й научной конференции МФТИ Современные проблемы фундаментальных и прикладных наук. Т. 1. Часть 1.
Радиотехника и кибернетика. 2008. С. 4 –7.
4. Владимиров С.М. Использование итеративного декодирования в сетевом кодировании // Труды 52-й научной конференции МФТИ Современные Радиотехника и кибернетика. 2009. С. 4–7.
5. Vladimirov S. New algorithm for message restoring with errors detection and correction using binary LDPC-codes and network coding // Computational Technologies in Electrical and Electronics Engineering (SIBIRCON), 2010 IEEE Region 8 International Conference on. 2010. "— jul. Pp. 40 –43.
6. Владимиров С.М. Новый итеративный алгоритм декодирования кодов с малой плотностью проверок на чётность в сетевом кодировании для двоичных каналов со стиранием на основе message-passing алгоритма // Труды 52-й научной конференции МФТИ Современные проблемы фундаментальных и прикладных наук. Т. 1. Часть 1. Радиотехника и кибернетика. 2010. С. 155–157.
7. Владимиров С.М. Улучшение алгоритма декодирования МППЧ-кодов в сетевом кодировании для канала со стиранием // Труды Московского физико-технического института (государственного университета). 2010.
Т. 2, № 3. С. 100–107.
8. Владимиров С.М. Обобщение нового алгоритма декодирования МППЧ-кодов для сетевого кодирования на произвольное число частей сообщения // Системы управления и информационные технологии. 2010.
Т. 3(41). С. 73–75.
9. Владимиров С.М. Способ оптимизации времени моделирования низкоплотностных кодов методом частичной генерации байт-кода на основе информации из проверочной матрицы кода // Труды Московского физико-технического института (государственного университета). 2011.