автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Повышение помехоустойчивости информационных коммуникаций с помощью кодов с малой плотностью проверок на четность и сетевого кодирования

Государственное образовательное учреждение высшего профессионального образования Московский физико-технический институт (государственный университет)

Владимиров Сергей Михайлович

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

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

г 4 053 2011

Долгопрудный - 2011

4856163

4856163

Работа выполнена в Московском физико-техническом институте (ГУ).

Научный руководитель: доктор технических наук,

профессор

Габидулин Эрнст Мухамедович Официальные оппоненты: доктор технических наук,

профессор

Зяблое Виктор Васильевич Институт проблем передачи информации имени А. А. Харкевича; кандидат физико-математических наук, Обернихин Виталий Александрович, ООО «Параллелз»

Ведущая организация: Санкт-Петербургский государственный

университет аэрокосмического

приборостроения

Защита состоится 1 марта 2011 г. в 15:00 на заседании диссертационного совета Д 212.156.04 при Московском физико-техническом институте (ГУ) по адресу: 141700, г. Долгопрудный, Московская обл., Институтский пер., д. 9, ауд. 204 Нового корпуса.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ). Автореферат разослан 27 января 2011 г.

Ученый секретарь диссертационного совета, кандидат технических наук

Куклев Л. П.

Общая характеристика работы

Актуальность работы. В настоящее время сетевое кодирования является новой и быстроразвивающейся областью исследований как в теории сетей, так и в теории информации. Телекоммуникационные сети - к началу XXI века это проводные, беспроводные, оптоволоконные - в том числе самые различные по своему назначению, вошли в повседневную жизнь. Исследованию таких сетей посвящено большое количество работ. Однако вплоть до 2000 года существенным было требование, чтобы в существующих телекомуникационных сетях передача сообщений происходила от источника к получателю через цепочку промежуточных узлов, работающих по принципу «принимай и передавай далее», то есть без взаимного влияния различных информационных потоков друг на друга. Хотя промежуточные узлы могли временно хранить у себя пакеты и группировать их для более оптимальной передачи (либо разбивать на более мелкие части), считалось, что другая обработка пакетов не нужна. Сравнительно недавно было показано [1], что методами сетевого кодирования можно показать лучшие результаты в использовании пропускной способности сети, в том числе без радикальных изменений в её инфраструктуре.

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

Ещё в 1960-х годах Галлагером были предложены коды с малой плотностью проверок на чётность. Кроме большой длины блока, что приближает их характеристики по исправлению ошибок на блок к так

называемой границе Шеннона, их достоинством является вычислительная простота итеративного декодирования. Тем не менее, до середины 1980-х годов этих коды практически не исследовались. МакКей отмечает, что причиной этому являлось слабое развитие вычислительной техники, которое только в последнее время смогло полностью использовать всю мощь кодов с большой длиной блока. В настоящий момент коды широко используются, в том числе в новых стандартах спутниковой передачи данных БУВ-82 и \ViMAX.

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

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

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

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

• анализ возможностей использования известных кодов с большим размером блока (в частности, кодов с низкой плотностью проверок на чётность) для сетевого кодирования;

• анализ влияния сетевого кодирования на особенности исправления ошибок итеративными алгоритмами декодирования;

• разработка нового метода использования низкоплотностных кодов для сетевого кодирования для повышения пропускной способности сети и защиты от помех;

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

получателей, произвольную структуру сети;

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

Для уменьшения времени численного моделирования использования низкоплотностных кодов для случайного сетевого кодирования решена задача ускорения работы процедуры поиска и исправления ошибок в кодовых векторах двоичных низкоплотностных кодов для итеративного алгоритма с распространением доверия при использовании виртуальной машины 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, 2010r. [5];

• 53-я научная конференция МФТИ - Всероссийская молодёжная научная конференция с международным участием «Современные проблемы фундаментальных и прикладных наук», Долгопрудный, 2010 г. [6]

Публикации. Материалы диссертации опубликованы в 9 печатных работах, из них 3 статьи в рецензируемых журналах [7-9], 1 статья в сборниках трудов конференций [5] и 3 тезиса докладов [3, 4, 6].

Личный вклад автора. Диссертация написана по материалам исследований, выполненных на кафедре радиотехники МФТИ (ГУ) в период с 2007 по 2011 годы. Личный вклад соискателя в опубликованные работы составляет в среднем не менее 70%. Результаты, выносимые на защиту, получены автором самостоятельно. Все представленные в диссертации результаты получены лично автором.

Структура и объём диссертации. Диссертация состоит из введения, обзора литературы, 3 глав, заключения, библиографии и одного приложения. Общий объем диссертации 114 страниц, из них 104 страницы текста, включая 31 рисунок. Библиография включает 31 наименование на 5 страницах.

Содержание работы

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

В первой главе рассмотрено поведение алгоритма декодирования кодов с низкой плотностью проверок на чётность в сетевом кодировании для канала со стиранием и предложено его улучшение.

Рис. 1. Модель сети «бабочка».

В модели сети «бабочка», изображённой на рис. 1, в каналах Т —» Y, W —» X и U —» Z могут возникать ошибки (стирания). Для исправления ошибок используется двоичный код с малой плотностью проверок (двоичный МПП-код, двоичный низкоплотностный код), также называемый кодом с малой плотностью проверок на чётность или МППЧ-кодом (англ. low dencity parity check code, LDPC-code). Рассматривается случай передачи одного кодового вектора ш двумя частями а и b от узла-источника S узлам-получателям Y и Z.

В случае, если сетевое кодирование не используется, то для передачи пакета целиком (обоих частей а и Ь исходного кодового вектора ш) обоим конечным узлам У и2 необходимо затратить пять итераций:

1. а: 5 ->7\ Ь:5 -> 1!;

2. а : Т -> У, а : Т -> V/, а : V -> 2, а : £/ -» УУ;

3. а : V/ -> X;

4. а : X -» г, Ь : IV X;

5. Ь : X -> У.

Если бы канал № —> X имел повышенную пропускную способность (два пакета за итерацию), это уменьшило бы число итераций, необходимое для передачи кодового вектора от Я обоим получателям. Аналогичный результат может быть достигнут без изменения структуры сети (без изменения физических характеристик канала) с использованием сетевого кодирования. В этом случае по каналу -* X передаётся не отдельные пакеты, а некоторая линейная рекомбинация пакетов (в рассматриваемом нами случае - побитовое сложение пакетов по модулю 2). Тогда для передачи кодового вектора обоим получателям достаточно 4-х итераций:

1. а : 5 —> Г, Ь : 5 {/;

2. а : Т -> У, а : Т -» Ь : и -> 2, Ь : и -» \¥;

3. (а © Ь): УУ -> X;

4. (а ©Ь): X —> У,Х-*7~

а

а <ь Ь

Ь

©

(I)

Рис. 2. Модель сети «бабочка» с сетевым кодированием.

Схема передачи пакетов приведена на рисунке 2.

Рассмотрен стандартный подход к восстановлению исходного кодового вектора и исправлению ошибок в нём и показано, что при использовании данного метода возникают дополнительные стирания, что можно выразить как увеличение вероятности возникновения стирания с р (без использования сетевого кодирования) до р' (с использованием):

Данная оценка вместе с данными численного моделирования изображена на рис. 3.

Таким образом, хотя использование сетевого кодирования позволяет улучшить пропускную способность сети в целом, в двоично-симметричном канале со стираниями при наличии ошибок в каналах передачи (в рассматриваемом нами случае это каналы Т —> У, X и I! —> Т) эффект от использования сетевого кодирования при увеличении вероятности стирания бита уменьшается. Например, как показано на графике 4 для двоичного

(1)

1,000

0,100

о

\

• V

41 ••

К

о о. о ш

V

•' ^ 0,001 0,5 0,45 0,4 0,35 0,3 0,25 0,2 0,15 0,1

Вероятность стирания бита в канале

■ Без сетевого «Теоретическое V С сетевым кодирования ожццание кодированием

Рис. 3. Вероятность ошибки декодирования блока на конечном узле без использования сетевого кодирования и с использованием сетевого кодирования.

МПП-кода длиной 96 бит и скоростью около 1/2 эффект пропадает при р > 0.26. График построен при следующих условиях:

1. передача без сетевого кодирования без ошибок требует 5 итераций;

2. передача с сетевым кодированием без ошибок требует 4 итерации;

3. ошибка при передаче требует перепосылки, на которую тратится 4 итерации в обоих случаях.

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

■

♦ ♦ ■

♦ ♦ ■ ■

♦ ■

...............♦.......................

У

______

0,2 0,25 0,3 0,35 С Вероятность стирания бита

' Без сетевого ко- ♦ С сетевым коди-дировэния рованием. Стан-

дартный алгоритм декодирования.

Рис. 4. Время передачи кодового вектора с учетом необходимости псрепосылки встора при ошибке декодирования.

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

Я =

10 110 1 0 10 111 1110 10

(2)

Рис. 5. Граф Таннера для двоичного МПП-кода с проверочной матрицей (2).

Исходный граф Таннера кода выглядит как показано на рис. 5. В новом алгоритме граф Таннера дополняется узлами как показано на рис. 6. Оба

ф ф ф ф ® ©

□ □□□□□

Рис. 6. Граф Таннсра для двоичного МПП-кода с проверочной матрицей (2), дополненный символьными и проверочными узлами Ш1 и т2.

графа заполнены значениями символьных узлов в предположении, что на конечный узел У пришло два сообщения Ш) итг:

где ej, - некоторые векторы ошибок, означающие происходящие стирания.

Показано, что в новом алгоритме можно использовать стандартное декодирование с жёстким решением с итеративным алгоритмом с передачей сообщений (англ. iterative message-passing algorithm), если использовать новую проверочную матрицу Я' и новый вектор х в качестве входных данных. Построим новый вектор х как конкатенацию частично восстановленного вектора и принятых сообщений:

Количество бит в векторе - удвоенная длина кодового вектора т'. Пусть Н - проверочная матрица выбранного двоичного МПП-кода размером п х к. Построим новую, расширенную проверочную матрицу:

mi = а + ej = | ? 1 m2 = a©b + e2 = (l 0 ?

(3)

x = m'||m1||m2

(4)

%

0,001

0,5 0,45 0,4 0,35 0,3 0,25 0,2 0,15 0,1 Вероятность стирания

■ Без сетевого V Стандартный Улучшенный кодирования алгоритм алгоритм

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

н о „,*

Я'= Е, 0и Е, 0и , (5)

Я/ Е[ 0 ц Е,

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

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

выше, чем при отказе от использования сетевого кодирования при вероятности стирания бита в канале не выше р ~ 0.33, а также выше, чем со стандартным алгоритмом декодирования, как показано на рис. 8.

■ Без сетевого ко- ♦ С сетевым коди- 7 С сетевым коди-

дирования рованием. Стан- рованием. Улуч-дартный алгоритм шенный алгоритм

декодирования. декодирования.

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

Если производительность оригинального алгоритма оценивается как О (N log N), то нового алгоритма - О (2N log 2N), то есть замедляет работу декодера чуть более чем в два раза. Тем не менее, с учётом значительного выигрыша, который позволяет скомпенсировать использование сетевого кодирования, новый алгоритм стоит использовать.

Показано, что для простых случаев, как, например, для модели сети «бабочка», новый алгоритм может быть упрощён за счёт опускания шага предварительного восстановления ш' (левой части вектора х). Однако в более общем случае отсутствие данного шага может повлечь за собой отказ от декодирования. Доказана соответствующая лемма:

Лемма 1. Пусть восстанавливаемый кодовый вектор двоичного МПП-кода х может быть разбит на две группы битов Х| и хг таким образам, что:

1. первая группа битов стёрта;

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

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

Результаты первой главы опубликованы в работе [7].

Во второй главе рассмотрен новый алгоритм декодирования для использования в гауссовых каналах. Алгоритм основывается на итеративном декодировании с мягким решением с распространением доверия, также известном как алгоритме Перла или алгоритм «сумма-произведение» (англ. soft decoding iterative belief-propagation, sum-product algorithm). Используется аналогичная модификация входных параметров алгоритма (проверочной матрицы и восстанавливаемого кодового вектора).

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

m = (ai,a2,...,a„) 16

Узел-отправитель делит вектор на две части, записывая элементы вектора в матрицу из двух строк, после чего дополняет её единичной матрицей:

М =

щ а2 ... а„/2 ^ Дп/2+1 ...... а,,

ЕМ =

10 а, а2 ... а„/2

0 1 ап/2+1 ...... а„

Два передаваемых сообщения тогда имеют вид:

1 = ^1 0 а\ а2 ... ап/г ' = ( 0 1 ап/2+1 ...... ап |

(7)

(8)

(9)

(10)

Из-за линейной рекомбинации пакетов (в неизвестном для получателя порядке) конечный узел получает следующие пакеты:

т, = / 1 0 Й| а2 ... я„/2 )

Ш2 = I 1 1 я, ©а„/2+1 ...... а„/2©а„)

Из этих пакетов узел выделяет битовые поля:

00

3 =

(12)

Ь\\ Ь 12

, ¿21 Ь22 _

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

н 0,,* 0а

ЬЦЕ, ЬпЕ1 Е\ 0и ¿21Е/ ¿22 Ех 0 и £■/ Данный подход с битовыми полями напоминает подход Кёттера и Кшишанга к использованию ранговых кодов для случайного сетевого

Н' =

(13)

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

м

8 и и « „

» Е И и X "< ы

т и

I И

6-1

х и

ЕС к И В И

и й

I I 8 *

о

1.0Е-01 Н-1-1-1-Г-

3 4 5 6 7

К 0

* Я

И

ЕЬ / N (дБ)

и Б«.: а; Ь ^ 31?.: а+Ь; Ь > .: а; а+Ь 1№ук:а;Ь -«№м:а+Ь;Ь ► Меуу:а;а+Ь

Рис. 9. Вероятность ошибки в блоке в зависимости от величины энергии на информационный бит для стандартного и нового алгоритма для случайного сетевого кодирования.

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

Лемма 2. Пусть принятый кодовый вектор двоичного МПП-кода х может быть разбит на две группы битов и Хг таким образом, что:

1.0ЕЮ0

1,06-01

Н1

5 о

1.0Б02

1.0Е-03

1.0Е-04

Яа 2 я «н

а ; и " н и и „

* и

....................................Х'Щ"

4 5 6 7 8

Е Ь / N (дБ)

и БК.: а; Ь вн.: а+Ь; Ь > БИ.: а; а+Ь I : а; Ь Ыеуу: а+Ь; Ь ► New: а; а+Ь

10

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

1. первая группа битов стёрта, то есть вероятность каждого бита быть равным 1 или 0 равна 50%;

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

Тогда первая часть Х| принятого кодового вектора х не может быть восстановлена итеративным алгоритмом декодирования с мягким решением с распространением доверия «сумма-произведение».

Результаты второй главы опубликованы в работе [8].

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

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

500

450

400

2 350

1 300 В-

g 250 |

8 200 8

| 150

100 50 0

3 3,5 4 4,5 5 5,5 6 6,5 7 Eb/N (дБ)

* Без предгене- т С генерацией * С генерацией рации байт-кода байт-кода байт-кода и заменой массивов

Рис. 11. Время моделирования без использования и с использованием предварительной генерации байт-кода декодера.

-М-

На рис. 11 показано время численного моделирования без предварительной

генерации оптимизированного кода декодера, с генерацией, а также с генерацией и с заменой массивов гО и г1 на переменные дополнительного класса. Моделирование выполнялось с использованием проверочной матрицы двоичного МПП-кода «408.3.834 (N=408, К=204, М=204, 11=0.5)» из энциклопедии низкоплотностных кодов МакКея.

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

Результаты третьей главы опубликованы в работе [9].

Список публикаций

1. Габидулин Э.М., Пилипчук Н.И., Владимиров С.М. и др. Сетевое кодирование // Труды Московского физико-технического института (государственного университета). 2010. Т. 1, № 2. С. 3-28.

2. Владимиров С.М. Использование сетевого кодирования и двоичных кодов с малой плотность проверок на чётность для широковещательной передачи данных // Информационные технологии моделирования и управления. 2010. Т. 4(63). С. 475-483.

3. Владимиров С.М. Использование кодов с малой плотностью проверок на чётность // Труды 51-й научной конференции МФТИ Современные проблемы фундаментальных и прикладных наук. Т. 1. Часть 1. Радиотехника и кибернетика. 2008. С. 4 -7.

4. Владимиров С.М. Использование итеративного декодирования в сетевом кодировании // Труды 52-й научной конференции МФТИ Современные

проблемы фундаментальных и прикладных наук. Т. 1. Часть 1. Радиотехника и кибернетика. 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. Владимиров C.M. Новый итеративный алгоритм декодирования кодов с малой плотностью проверок на чётность в сетевом кодировании для двоичных каналов со стиранием на основе message-passing алгоритма // Труды 52-й научной конференции МФТИ Современные проблемы фундаментальных и прикладных наук. Т. 1. Часть 1. Радиотехника и кибернетика. 2010. С. 155-157.

7. Владимиров С.М. Улучшение алгоритма декодирования МППЧ-кодов в сетевом кодировании для канала со стиранием // Труды Московского физико-технического института (государственного университета). 2010. Т. 2, № 3. С. 100-107.

8. Владимиров С.М. Обобщение нового алгоритма декодирования МППЧ-кодов для сетевого кодирования на произвольное число частей сообщения // Системы управления и информационные технологии. 2010. Т. 3(41). С. 73-75.

9. Владимиров С.М. Способ оптимизации времени моделирования итеративного декодирования при использовании двоичных низкоплотностных кодов методом частичной генерации байт-кода на основе информации из проверочной матрицы кода // Труды Московского физико-технического института (государственного университета). 2011. Т. 3, № 1.

Подписано в печать: 25.01.11

Объем: 1,5усл.п.л. Тираж: 100 экз. Заказ № 775 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского,39 (495) 363-78-90; www.reglet.ru

Введение.

Обзор литературы.

1. Новый алгоритм поиска и исправления ошибок в кодовых векторах двоичных МПП-кодов в сетевом кодировании для канала со стиранием.

1.1. Введение.

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

1.3. Использование двоичных низкоплотностных кодов в сетевом кодировании.

1.4. Новый алгоритм на основе алгоритма передачи сообщений

1.5. Необходимость предварительного восстановления вектора ш'

1.6. Возможность использования информации из дополнительных сообщений.

1.7. Выводы

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

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

2.2. Новый алгоритм декодирования для двух частей кодового вектора с фиксированной структурой сети.

2.3. Результаты численного моделирования.

2.4. Обобщение подхода на случай случайного сетевого кодирования.

2.5. Использование дополнительной информации для исправления большего числа ошибок.

2.6. Обобщение на большее число частей сообщения.

2.7. Дополнительная инициализация вектора х.

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

3. Сокращение времени численного моделирования поиска и исправления ошибок для двоичных низкоплотностных кодов

3.1. Улучшение производительности численного моделирования

3.2. Результаты численного моделирования.

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

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

Хотя промежуточные узлы могли временно хранить у себя пакеты и группировать их для более оптимальной передачи (либо разбивать I на более мелкие части), считалось, что другая обработка .пакетов не нужна. Сравнительно недавно было показано [1-3], что методами сетевого кодирования можно показать лучшие результаты в использовании пропускной способности сети, в том числе без радикальных изменений в её инфраструктуре [4].

В 2007 и 2008 годах были представлены первые работы по случайному сетевому кодированию, среди которых стоит отметить работы Кёттера,

Кшишанга и Сильвы [5-7]. В этих работах был представлен вариант использования сетевого кодирования для сетей, неимеющих чёткой структуры или алгоритма маршрутизации. В работах существенным образом использовалась теория рангового кодирования, разрабатываемая Габидулиным с 1980-х годов [8].

Ещё в 1960-х годах Галлагером были предложены коды с малой плотностью проверок на чётность [9, 10]. Кроме большой длины блока, что приближает их характеристики по исправлению ошибок на блок к так называемой границе Шеннона, их достоинством является вычислительная простота итеративного декодирования [11]. Тем не менее, до середины 1980-х годов этих коды практически не исследовались. МакКей отмечает [12], что причиной этому являлось слабое развитие вычислительной техники, которое только в последнее время смогло полностью использовать всю мощь кодов с большой длиной блока. В настоящий момент коды широко используются, в том числе в новых стандартах спутниковой передачи данных БУВ-82 и Ч\/1МАХ [13].

Возможность использования низкоплотностных кодов в сетевом I кодировании активно исследуется в настоящее время [14-18]. I

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

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

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

• анализ возможностей использования известных кодов с большим размером блока (в частностй, кодов с низкой плотностью проверок на чётность) для сетевого кодирования;

• анализ влияния сетевого кодирования на особенности исправления ошибок итеративными алгоритмами декодирования;

• разработка нового метода использования низкоплотностных кодов для сетевого кодирования для повышения пропускной способности сети и защиты от помех;

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

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

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

Научная новизна состоит в улучшении пропускной способности сети с использованием сетевого кодирования с использованием кодов с низкой плотностью проверок на чётность: I

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

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

3. предложенный алгоритм расширен на случай случайного сетевого кодирования;

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

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

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

• алгоритм поиска и исправления ошибок в кодовых векторах двоичных низкоплотностных кодов в | сетевом кодировании для канала со стиранием;

• модификация алгоритма для канала со стиранием для работы с различным числом пакетов, на которые при передаче делится кодовый вектор; I

• модификация алгоритма для канала со стиранием для использования в случайном сетевом кодировании;

• алгоритм поиска и исправления ошибок в кодовых векторах двоичных низкоплотностных кодов для канала с аддитивным белым гауссовским шумом;

• модификация алгоритма для канала с аддитивным белым гауссовским шумом для работы с различным числом пакетов, на которые при передаче делится кодовый вектор;

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

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

• 51-я научная конференция МФТИ - Всероссийская молодёжная научная конференция с международным участием «Современные проблемы фундаментальных и прикладных наук», Долгопрудный,

2008 г. [20];

• 52-я научная конференция МФТИ - Всероссийская молодёжная научная конференция с международным участием «Современные проблемы фундаментальных и прикладных наук», Долгопрудный,

2009 г. [21];

• IEEE R8 International Conference on Computational Technologies in Electrical and Electronic' Engineering SIBIRCON-2010, Irkutsk Listvyanka, 2010 r. [22];

• 53-я научная конференция МФТИ - Всероссийская молодёжная 4 научная конференция с международным участием «Современные проблемы фундаментальных и прикладных наук», Долгопрудный,

2010 г. [23]

Публикации. Материалы диссертации опубликованы в 9 печатных работах, из них 3 статьи в рецензируемых журналах [24-26], 1 статья в сборниках трудов конференций [22] и 3 тезиса докладов [20, 21, 23].

Личный вклад автора. Диссертация написана по материалам исследований, выполненных на кафедре радиотехники МФТИ (ГУ) в период с 2007 по 2011 годы. Личный вклад соискателя в опубликованные работы составляет в среднем не менее 70%. Результаты, выносимые на защиту, получены автором самостоятельно. Все представленные в диссертации результаты получены лично автором.

Структура и объём диссертации. Диссертация состоит из введения, обзора литературы, 3 глав, заключения, библиографии и одного приложения. Общий объем диссертации 114 страниц, из них 104 страницы текста, включая 31 рисунок. Библиография включает 31 наименование на 5 страницах.

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

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

500

450 400 350 300 250 200 150 100 50 0 ос г в ф 0 1 о о ф

-4— ♦

• ► А . т т ▼ ►Л ♦ г Т ► ► ▼ ♦

1 ♦

1 ♦ г 4 1 ♦ Г

3,5

4,5 5 ЕЬ/ N (дБ)

5,5

6,5 Без предгене- ▼ С генерацией ► С генерацией рации байт-кода байт-кода байт-кода и заменой массивов

Рис. 3.3. Время численного моделирования без использования и с использованием предварительной генерации байт-кода декодера

3 3

I ф <\> 1 0 о £ I I I

100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0%

А А А А ► ► ► ▲ ►

-рг— X г—

3,5

-г-4

4,5

-т-5

ЕЬ/ N (6Д)

Без предгене- А С генерацией рации байт-кода - байт-кода

1 Т"

5,5

С генерацией байт-кода и заменой массивов

6,5

Рис. 3.4. Время моделирования с использованием предварительной генерации байт-кода декодера в процентах от времени без использования генерации

Заключение

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

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

I • , " > » и исправлению ошибок в принятых кодовых векторах на узлах-получателях и улучшает общую пропускную способность сети с использование сетевого I кодирования.

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

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

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

1. Yeung R.W., Zhang Z. Distributed source coding for satellite communications // Information Theory, IEEE Transactions on. 1999. "— may. Vol. 45, no. 4. Pp. 1111 -1120.

2. Ahlswede R., N. Cai, S.R. Li, R.W. Yeung. Network information flow // IEEE Transactions on Information Theory. 2000. Vol. 46. Pp. 1204-1216.

3. Габидулин Э.М., Пилипчук Н.И., Владимиров C.M. и др. Сетевое кодирование // Труды Московского физико-технического института (государственного университета). 2010. Т. 1, № 2. С. 3-28.

4. Барашб JI. Сетевое кодирование // Компьютерное обозрение. 2009. № 5.

5. Silva D., Kschischang F.R. Using Rank-Metric Codes for Error Correction in Random Network Coding // Information Theory, 2007. ISIT 2007. IEEE International Symposium on. 2007. "— jun. Pp. 796 -800.

6. Silva D., Kschischang RR., Koetter R. A Rank-Metric Approach to Error Control in Random Network C.oding // Information Theory for Wireless Networks, 2007 IEEE Information Theory Workshop on. 2007. jul. Pp. 1-5.

7. Габидулин Э.М. Теория кодов с максимальным ранговым расстоянием // Проблемы передачи информации. 1985. Т. 21, № 1. С. 3-16.1.* I83

8. Gallager R. Low-density parity-check codes // Information Theory, IRE Transactions on. 1962. "—jan. Vol. 8, no. 1. Pp. 21 -28.

9. Gallager R. Low-density parity-check codes. Cambridge, Mass., 1963.

10. Зигангиров К.Ш. О корректирующей способности кодов с малой плотностью проверок на чётность // Проблемы передачи информации. 2008. Т. 44, № 3. С. 50-62.

11. MacKay D. J. С. Information theory, inference and learning algorithms. Cambridge: Cambridge University Press, 1978.

12. Bao X., J. Li. Matching Code-on-Graph with Network-on-Graph: Adaptive Network Coding for Wireless Relay Networks // Proc. Allerton Conf. on Commun., Control and Computing IL. 2005.

13. Hausl C., Schreckenbach F., Oikonomidis I., Bauch G. Iterative network and channel decoding on a Tanner graph // Proc. 43rd Allerton Conf. on Communication, Control, and Computing,. 2005. "— sept. Pp. 1 -5.

14. Chang C., Lee H. Space-Time Mesh Codes for the Multiple-Access Relay Network: Space vs. Time Diversity Benefits. 2007.

15. Kang J., Zhou В., Ding Z., Lin S. LDPC coding schemes for error control in a multicast network // Information Theory, 2008. ISIT 2008. IEEE International Symposium on. 2008. "— jul. Pp. 822 -826.

16. Guo Z., Huang J., Wang B. et al. A practical joint network-channel coding scheme for reliable communication in wireless networks // MobiHoc. 2009. Pp. 279-288. URL: http://doi.acm.org/10.1145/1530748.1530787.

17. Владимиров C.M. Использование сетевого кодирования и двоичных кодов с малой плотность проверок на чётность для широковещательной передачи данных // Информационные технологии моделирования и управления. 2010. Т. 4(63). С. '475-483.

18. Владимиров С.М. Использование кодов с малой плотностью проверокна чётность // Труды 51-й научной конференции МФТИ Современныепроблемы фундаментальных и прикладных наук. Т. 1. Часть 1. Радиотехника и кибернетика. 2008. С. 4 -7.

19. Владимиров С.М. Использование итеративного декодирования в сетевом кодировании // Труды 52-й научной конференции МФТИ Современные проблемы фундаментальных и прикладных наук. Т. 1. Часть 1. Радиотехника и кибернетика. 2009. С. 4-7.

20. Vladimirov S. New algorithm for message restoring with errors detection and correction using binary LDPC-codes and network coding // Computational

21. Technologies in Electrical and Electronics Engineering (SIBIRCON), 2010i

22. EE Region 8 International Conference on. 2010. "—jul. Pp. 40 -43.

23. Владимиров С.М. Улучшение алгоритма декодирования МППЧ-кодов в сетевом кодировании для канала со стиранием // Труды Московского физико-технического института (государственного университета). 2010. Т. 2, № 3. С. 100-107.• •

24. Владимиров С.М. Обобщение нового алгоритма декодирования МППЧ-кодов для сетевого кодирования на произвольное число частей сообщения // Системы управления и информационные технологии. 2010. Т. 3(41). С. 73-75.

25. Зигангиров К.Ш., Зигангиров Д.К. Декодирование низкоплотностных кодов с проверочными матрицами, составленными из перестановочных матриц при передаче по каналу со стираниями // Проблемы передачи информации. 2006. Т. 42, № 2, С. 44-52.

26. MacKay D.J.C. Encyclopedia of Sparse Graph Codes. 2010. URL: http:www.inference.phy.cam.ac.uk/mackay/codes/data.html.i. i. •,

27. Gosling James, Joy Bill, Steele Guy, Bracha Gilad. The Java Language Specification, Third Edition. 3 edition. Amsterdam: Addison-Wesley Longman, 2005. June. P. 688. ISBN: 0321246780.

28. Chiba S. Javassist: Java bytecode engineering made simple // Java Developer's Journal. 2004.