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

Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. А. А. Харкевича Российской академии

наук

На правах

Иванов Федор Ильич

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

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

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

СЕН 2014

005552682

Москва - 2014

005552682

Работа выполнена в Лаборатории Л- 3 Федерального государственного бюджетного учреждения науки Института проблем передачи информации им. А. А. Харкевича Российскоий академии наук

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

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

Автореферат разослан 14 сентября 2014 года.

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

(ИППИ РАН).

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

доктор технических наук, Зяблое Виктор Васильевич доктор технических наук, профессор, НИУИТМО, Кудряшов Борис Давидович кандидат физико-математических наук,

инженер-програмлшст в ООО "Одноклассники", Владимиров Сергей Михайлович Санкт-Петербургский государственный университет аэрокосмического приборостроения

Официальные оппоненты:

Ведущая организация:

кандидат физико-математических наук,

Стрыгин Л. В.

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

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

Для исправления ошибок при передаче данных по каналу связи используют помехоустойчивые коды. На практике одним из важнейших критериев при выборе той или иной кодовой конструкции является наличие быстрых и эффективных алгоритмов алгоритмов кодирования и декодирования, а также возможности эффективного (экономного) использования памяти, необходимой для хранения кодовой конструкции. Двоичные коды с малой плотностью проверок (МПП-коды), впервые предложенные Р. Галлагером в 1960 году, удовлетворяют приведенным выше требованиям. Однако "слу-чайность"рассматриваемого Галлагером кода затрудняет использовать его в большинстве практических приложений ввиду достаточно большой сложности реализации. В связи с этим рядом исследователей, таких как Т. Ричардсон, Д. Маккей, М. Фоссориер, Э. Габидулин, М. Эсмаэли было предложено использовать матрицы перестановок для генерации проверочных матриц МПП-кодов. Данпый подход позволяет оптимизировать как процедуры храпения матриц, так и алгоритмы кодирования и декодирования. Кроме того К. Ш. Зигангировым было доказано, что для почти всех кодов, проверочная матрица которых состоит из случайных матриц перестановок, мипимальное расстояние растет линейно с длиной кода. Как результат - в настоящее время МПП-коды, основанные на матрицах перестановок, вошли в ряд стандартов: стандарт подвижной беспроводной связи LTE, стандарт спутникового телевидения DVB-S2, стандарт беспроводных локальных сетей WiFi 802.Нас.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Конструкции МПП-кодов, основанных на матрицах перестановок специального вида.

• Конструкции МПП-кодов, основанные на системах троек и четверок Штейнера и матрицах перестановок.

• Векторный алгоритм декодирования МПП-кодов, основанных на матрицах перестановок.

Апробация работы Основные результаты диссертации докладывались на следующих конференциях: XIII International Symposium on Problems of Redundancy in Information and Control Systems (2012); XIII International Workshop on Algebraic and Combinatorial Coding Theory (2012); конференциях молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (2012-2013). Кроме того, основные результаты докладывались на семинарах по теории кодирования в ИППИ РАН.

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

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

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

Структура и объем диссертации Диссертация состоит из введения, обзора литературы, 3 глав, заключения и библиографии. Общий объем диссертации 149 страниц, из них 111 страниц текста, включая 73 рисунка и 7 таблиц. Библиография включает 66 наименований на 9 страницах.

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

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

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

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

Пусть т, I, п0 S N, причем п0 > I, т\ > 1по. Рассмотрим группу Vm матриц перестановок размера тп х т.

Выберем 1щ случайных матриц {Ру} С Vm, г — 1,1, j = 1, по- Потребуем так же, что если Ру = Pjts, то г = j, к = s. Ясно, что такие условия выбора матриц Ру соответствуют урновой модели без возвращений.

Построим проверочную матрицу Н размера I х щ:

(

Pll Pl2 Рц • •• Pino Р21 Р22 Р23 • • - Р2по

\

Н =

(1)

\Рп Р¡2 Ргз ... Pino/

Указанный выше способ построения матрицы Н гарантирует, что все матрицы в каждой строке и в каждом столбце будут различны. Так какРу -квадратная матрица размера т хт, то размер Н - mi х тпо. Н определяет ансамбль (I, по)-регулярных (с постояннным весом столбца и с постоянным весом строки щ) МПП-кодов длины п = щт, который мы обозначим £л(1, по, тп). Элементы ансамбля £r{1, п0, тп) получаются путем выбора без возвращений матриц перестановокP¿j € Vm, i = 1,2,...,/, j = 1,2,...,no-

Определение 1. Произвольный код С е £r{1, Щ, тп) мы назовем МПП-кодом, основанным на матрицах перестановок.

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

Теорема 1. de < 2m VC € £r{1, щ,т), где de - кодовое расстояние кода С.

С другой стороны, имеет место следующая нижняя оценка па скорость кодов из апсамбля С 6 £r{1, щ, тп)

R> 1 - —. (2)

По

Из этих двух фактов можно сделать вывод, что далеко не при всех параметрах I, по коды из ансамбля £r(1, щ, тп) могут достигать границы Варша-мова-Гилберта.

Все представленные в первой главе диссертационной работы ансамбли кодов являются подансамблями ансамбля £ц(1,По,т). Матрицы перестановок, образующие их проверочные матрицы были выбраны специальным образом. В частности, были построены ансамбли МПП-кодов, основанных па смежных классах С 6 £м{1,Щ,т), на матрице Вандермонда £\у(1,Щ,тп), на случайных сдвигах С 6 £s(Z, no,m).

В первой главе диссертации также описан классический алгоритм декодирования, предложенный Галлагером. Sum-Product, известный так же под названиями Belief Propagation, алгоритм с распространением доверия - алгоритм декодирования, являющийся алгоритмом обмена сообщениями на фактор-графе. Алгоритм получает на вход вероятности приёма символов, которые в практической реализации для двоичного случая передаются как отношения правдоподобия. Далее алгоритм итеративно выполняет вычисления на вершинах-символах и вершинах-проверках, передавая между ними сообщения, представляющие из себя по сути отношения правдоподобия данного символа (проверки), вычисленные для соответствующей проверки (символа) на основе всех остальных, кроме того, для кого производится вычисление.

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

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

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

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

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

Определение 2. Под матрицей I/, размера тхт мы будем понимать матрицу Л -кратного циклического сдвига единичной тхт матрицы I.

Пусть - тхт матрица ру-кратного циклического сдвига, 1 < г < 1 < j < по- Построим I х по матрицу Н следующего вида:

Так как размер 1р„ - тхт, то размер Н - т1 х тщ. Н определяет ансамбль регулярных квазициклических МПП-кодов длины п — тщ. Обозначим этот ансамбль £с}с{1,Щ,т). Элементы ансамбля получаются путем равновероятного выбора (возможно с возвращениями) матриц -кратных циклических сдвигов.

Определение 3. Произвольный код С € £рс{1,Щ,т) мы назовем квазициклическим МПП-кодом.

Следующая теорема говорит об условии отсутствия циклов длины 4 в матрице Н9.

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

(3)

имеет место соотношение

(Р'231 - Рг 1л) / (РЬп ~ Рпп) то<1 т

(5)

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

Используя теорему (2), в работе построено два подансамбля£дсм(', «о, "г) и о,т) ансамбля £()с{1,п0,т), минимальная длина циклов в прове-

рочных матрицах которых равна 6.

Полученные результаты были обобщены на более широкий класс МПП-кодов, основанных на полях Галуа(ЗР (<•/"). В первой главе диссертации предложен метод, отображающий элементы мультипликативной группы поля Га-луа па матрицы перестановок. Квазициклические МПП-коды могут быть получены как частный случай МПП-кодов, основанных на полях Галуа.

Способ построения отображения между ненулевыми элементами и элементами некоторой подгруппы И симметрической группы 6/, определяется следующей теоремой.

к

Теорема 3. Если СР*(с[ш): - 1 = П рТ> то существует изоморфизм

!=1

к

ф : СР^д™) •->■ Н С Зн, к = причем У-у 6 справедливо

¿=1

равенство:

где Рх € СТ*(<?т) является образующей циклической подгруппы < А > группы | < /3; > | = рТ, г - П < р-' являются решениями уравнения

к пт _ 1

1 = (7)

1=1

Разложение (6) является произведением независимых циклов тг^..

На основе 3 строится ансамбль МПП-кодов, основанных ira полях Галуа.

Пусть ctij — aSi> € GF*(qm), где а - примитивный элемент поля. Предста-

к

вим Qm — 1 в каноническом виде: qm — 1 = П ?Т- Отобразим каждый элемент

¿=1

к

ctij на матрицу перестановкиPUl., dimPaij = J2pT- Выберем I, щ G N, n0 > l.

i=i

Тогда проверочная матрица

/р p р N

ГОП ^OlJ -■• ÛTlng

Н9/ =

P P

«21 Х 022

^Poui Pqj2 • • • Paj„0 J

(8)

определяет ансамбль регулярных двоичных МПП-кодов длины п = ^^ рГ) nо> который мы обозначим £gf(1, по, <7m—1). Элементы ансамбля £gf(1, Щ, Ят—1) получаются путем равновероятного выбора (с возвращением) элементов мультипликативной группы GF*(qm).

Определение 4. Произвольный код С 6 £gf(1, "о. Чт ~ 1) будем называть МПП-кодом, основанным на поле Галуа или GF-кодом.

Основываясь на теореме 2, было доказано следующее утверждение:

Теорема 4. Матрица (8) не содержит циклов длины 4 тогда и только тогда, когда имеют место к соотношений

(siih ~ Siih) i (shh ~ shh) mod P?>1 = 1~k>

где 1 < < г2 < I, 1 < п < 32 < п0, Чт - 1 = П Р?-

¿=1

Для представленных в первой главе кодовых конструкций с фиксированной скоростью Я = 0.5, длиной п ~ 2000 и итеративного алгоритма декодирования "распространения доверия "приведены результаты моделирования при

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

Выводы к главе 1

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

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

• Предложен способ представления элементов мультипликативной группы поля Галуа С_Р*(дт) в виде матриц перестановок. Данный способ основан на разложении перестановки па произведение независимых циклов. На основе предложенного способа построен ансамбль МПП-кодов, основанных на поле Галуа.

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

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

Определение 5. Система Штейнера - это пара (Х,В), где X

- множество из V элементов, а В - семейство к подмножеств X (назы-

баемых блоками), так что каждое t-подмножество множества X содержится ровно в одном блоке семейства В. Система S(v,3,2) называется системой троек Штейнера (STS(v)), а система S(v, 4,2) - система четверок Штейнера (SQS(v)).

Обозначение 1. IJodT-L[vn) будем понимать двоичный [2т — 1,2"' — т —1,3] код Хэмминга.

Известно, что кодовые слова веса 3 кода Хэмминга образуют систему троек Штейнера. Каждое слово с(х) веса 3 будем представлять в виде с(х) = xil + х'2 + х'3, где 0 < ¿1 < г2 < ¿з < 2т — 2. Слово с(х) будем выбирать так, чтобы все 2т — 2 циклических сдвига его координат были различны: Также определим р как наименьшее натуральное число, для которого выполняется соотношение с2"(i) = с{х) mod (х2™-1 — 1).

Во второй главе показало, что если 2т — 1 - простое, то р = га. При этом все множество кодовых слов веса три разбиваются на —^— семейства, причем каждый элемент одного семейства не представим через сдвиги и степени 2' элементов других семейств.

По заданному слову с(х) = х'1 4- х'2 + х'1 можно построить следующую матрицу:

Н = [во,..., Sp_ij,

где

Sj = [г\х), хг\х),x2m~2<?{xj\, о < j <р-1.

Подматрица Sj есть квадратная матрица размера (2m — 1) х (2т — 1). Нетрудно убедиться, что вес любой строки и любого столбца Sj С Н равен 3.

Таким образом, матрица Н имеет размер (2,п — 1) х р(2т — 1), причем вес каждой ее строки щ = 3р, а вес каждого столбца 1 — 3.

Размер матрицы Н можно сделать кратным р(2т — 1), заменив каждую из Зр(2т — 1) единиц на произвольную матрицу перестановки размера Ь х а каждый из р(2т - I)2 - Зр(2т - 1) нулей на нулевую £ х 4 матрицу Ъ^. Если обозначить за Н результат такого преобразования матрицы Н, то Н есть разреженная £(2т — 1) х рЬ{2т — 1) матрица, причем вес каждой строки Щ = щ = Зр, а вес каждого столбца 1 = 1 = 3.

Выберем произвольное целое к, такое что 2 < к < р. Образуем матрицу Н путем выбора произвольного &-элементого (1 < к < р) упорядоченного подмножества < ..., >С |Бо, ..., вр-^, 0<1^<р —1, l<j< к. Полученная таким образом матрица Н будет иметь размер Ь{2т — 1) х кЬ{2т — 1), причем вес каждой строки равен вес каждого столбца равен 3.

Таким образом, выбирая произвольные целые гп > 3, 2 < к < р, а также 3/с(2т — 1) случайных Ь х ¿-матриц перестановок, £ > 1, мы определим ансамбль регулярных (3,3к) кодов с малой плотностью проверок на четность длины п = Ы(2™ — 1). Обозначим полученный ансамбль через ^^(т, к, ?).

Определение 6. Произвольный код С £ £згз{т,к^), мы назовем кодом с малой плотностью проверок на четность, основаннъш на матрицах перестановок и ЗТБ(2т — 1).

Основным результатом второй главы является теорема, в которой сформулировано условие, гарантирующее строгое увеличение кодового расстояния при замене каждой из Щ2т - 1) единиц в Н = |Эо,..., нару-кратные матрицы матрицы циклических сдвигов.

Теорема 5. Пусть кодовое расстояние <1 кода с проверочной матрицей Н равно 4. Рассмотрим все комбинации из 4 линейно зависимых столбцов проверочной матрицы Н. Если в каждой такой комбинации при замене единиц

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

Теорема 5 имеет ряд важных следствий.

Следствие 1. Пусть кодовое расстояние й кода с проверочной матрицей Н равно 4. Расширим матрицу Н матрицами ^¿^ -кратных циклических сдвигов до матрицы Н согласно описанной выше процедуре. Тогда если в каждой комбинации из 4 линейно зависимых столбцов матрицы Н хотя бы один цикл длины 6 перешел в цикл большей длины, а в каждой комбинации из 6 линейно зависимых столбцов матрицы Н хотя бы один цикл длины 8 перешел в цикл большей длины, то минимальное расстояние кода с проверочной матрицей Н будет не менее 8.

Следствие 2. Если Н - проверочная матрица кода, основанного наБТЗ(2т— 1), и минимальная длина циклов в Н

9> Ю,

то минимальное расстояние такого кода

д'тт ^ 8.

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

Для представленных кодовых конструкций с фиксированной скоростью Я = 0.5 и итеративного алгоритма декодирования "распространения доверия" приведены результаты моделирования при передаче кодового слова с помощью двоичной фазовой манипуляции по каналу с аддитивным белым гауссовским шумом. В результате показано, что при указанной длине и скорости, МПП-коды, основанные на тройках Штейнера и матрицах перестановок превосходят коды основанные на четверках Штейнера и матрицах перестановок по вероятности ошибки на бит и на блок при фиксированном отношении сигнал-шум на кодовый символ. Преимущество составляет 1.5 — 2 порядка. В то же время кривые для кодов, основанных на системах четверок Штейнера и матрицах перестановок, имеют больший угол наклона, пежели кривые для кодов основанных на тройках, что связано с меньшим весом столбца в проверочных матрицах последних.

Выводы к главе 2

• Построен ансамбль кодов с малой плотностью проверок на четность, основанных на системах троек Штейнера и матрицах перестановок. Исследованы его свойства.

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

• Проведено моделирование полученных кодовых конструкций для скорости Д = 0.5 и длины N » 2000. В результате показано, что при указанной длине и скорости, МПП-коды из ансамбля £.?тя(1П1 к, £) превосходят коды, основанные на четверках Штейнера по вероятности ошибки на бит и на блок при фиксированном отношении сигнал-шум на кодовый символ (Ец/^).

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

В третьей главе диссертационной работы рассматриваются проблемы реализации кодов с малой плотностью проверок. Для кодов, основанных на матрицах перестановок, предложена модификация алгоритма "распространения доверия которая использует векторные операции и которая может быть естественным образом распараллелена. Также предложена модификация более простого, нежели Sum-Product, мажоритарного алгоритма декодирования.

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

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

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

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

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

волны, а в случае перспективных систем связи речь идёт о скоростях порядка 1 Тбит/с. Но в то же время современные устройства обработки данных работают на частотах порядка 1 ГГц, и их высокая производительность обеспечивается именно за счет параллельности вычислений.

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

Третья глава диссертации содержит результаты моделирования большинства представленных в работе кодовых конструкций: МПП-кодов, основанных на произвольных матрицах перестановок, МПП-кодов Галлагера, МПП-кодов, основанных на случайных сдвигах, квазициклических кодов (КЦ-кодов), КЦ-кодов, основанных на смежных классах, на матрице Вандермонда, МПП-кодов, основанных на полях Галуа, а также МПП-кодов, основанных на тройках и четверках Штейпера, МПП-кодов, основанных на (Ч)ЕП-кодах.

В данном разделе мы сфокусировались на моделировании длинных кодов с малой избыточностью. Длина кодов п была выбрана порядка 30000, а скорость R = 0.8.

Проведенное моделирование позволило установить, что:

• При декодировании кодов длины N = 30000 и скорости R = 0.8 алгоритмом "распространения доверия"наилучшие результаты показывают (3,15)-регулярные коды.

• Среди всех приведенных кодовых конструкций невозможно выделить "явного лидера"по корректирующим способностям, в то же время можно выделить 2 конструкции, которые демонстрируют почти всегда худшее поведение, чем остальные: это коды из ансамблей SQCM(l,no,m), £QCiv(l,n0,т)-

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

Мажоритарное декодирование проигрывает алгоритму "распространения доверия"по крайней мере 2.4 дБ. по уровню вероятности ошибки на блок Рь« Ю-5.

Коды, основанные на четверках Штейнера и матрицах перестановок проигрывают (3,15)-регулярным МПП-кодам лишь 0.05 дБ. по уровню вероятности ошибки на блок Рь « Ю-5.

МПП-коды, основанные па (Ч)ЕП МПП-кодах не уступают по корректирующим свойствам кодам, основанным на матрицах перестановок, кодам, основанным на тройках или четверках Штейнера и матрицах перестановок.

Коды, которые показывают наилучшие результаты декодирования для алгоритма "распространения доверия непригодны для мажоритарного декодирования.

Выводы к главе 3

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

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

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

• Представлены результаты моделирования большинства предложенных в диссертационной работе кодовых конструкций для случая, когда их длина N кз 30000 и скорость R и 0.8. Выявлены оптимальные параметры кодов для мажоритарного декодирования, оценена вероятность выбора "плохого кода"в некоторых ансамблях.

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

В Заключении обобщены полученные в диссертационной работе результаты и сделаны выводы.

Основные результаты:

1. Представлен ряд конструкций МПП-кодов, основанных на матрицах перестановок. Для проверочных матриц некоторых из этих кодов доказано отсутствие циклов длины 4. Приведен пример кода с минимальной длиной цикла 8.

2. Построен ансамбль кодов с малой плотностью проверок на четность, основанных на системах троек Штейнера и матрицах перестановок. Исследованы его свойства. Построены МПП-коды, основанные на четверках Штейнера и матрицах перестановок.

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

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

5. Проведено имитационное моделирование предложенных в работе конструкций МПП-кодов. Были выбраны скорости R ~ 0.5, 0.8 и N w 2000,30000 соответственно. Результаты моделирования позволяют судить о пригодности тех или иных кодовых конструкций.

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

1. Ivanov F. I., Zyablov V. V., Potapov V. G. Low-Density Parity-Check Codes Based on Galous Field // Information Processes. 2012. Vol. 12, no. 1. P. 68-83.

2. Иванов Ф. И., Зяблов В. В., Потапов В. Г. Оценка длины циклов квазициклических регулярных кодов с малой плотностью проверок на четность // Информационно-управляющие системы. 2012. Т. 42, № 3. С. 42-45.

3. Иванов Ф. И., Зяблов В. В., Потапов В. Г. Сравнение различных конструкций двоичных МПП-кодов, построенных на основе матриц перестановок // Информационные процессы. 2012. Т. 12, № 1. С. 31-52.

4. Ivanov F. I., Zyablov V. V., Potapov V. G. Low-Density Parity-Check Codes Based on the Independent Subgroups // Proc. of XIII International Symposium "Problems of Redundancy in Information and Control Systems". Russia, Saint-Petersburg. 2012. P 31-34.

5. Ivanov F. I., Zyablov V. V., Potapov V. G. The Score of the Minimum Length of Cycles in Generalized Quasi-Cyclic LDPC Codes // Proc. of Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2012. Pomorie, Bulgaria. 2012. P. 162-167.

6. Иванов Ф. И., Жилин И. В., Зяблов В. В. Алгоритм декодирования кодов с малой плотностью проверок на четность с большим распараллеливанием // Информационно-управляющие системы. 2012. № 6. С. 49-55.

7. Ivanov F. I., Zyablov V. V. Low-Density Parity-Check Codes Based on Steiner Systems and Permutation Matrices // Problems of Information Transmission. 2013. Vol. 49, no. 4. P. 41-56.

8. Ivanov F. I., Zyablov V. V., Potapov V. G. The score of the Minimum Length

of Cycles in Quasi-Cyclic LDPC codes based on permutation matrices // Proc. of 35-th conference "Information technologies and systems (ITAS)". Petrozavodsk, Russia. 2012. P. 133-136.

9. Ivanov F. I., Zyablov V. V. Low-Density Parity-Check Codes Based on Steiner Triple Systems and Permutation Matrices // Proc. of 36-th conference "Information technologies and systems (ITAS)". Kaliningrad, Russia. 2013.

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

10.09.2014

Заказ № 10202 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 \vww.autorefcrat. ги