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

На правах рукописи

ЯлГ

Рыбин Павел Сергеевич

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

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

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

1 7 МАЙ 2012

Москва - 2012

005044374

005044374

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

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

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

доктор технических наук, Зяблов Виктор Васильевич Зиновьев Виктор Александрович,

доктор физико-математических наук, профессор, ИППИ РАН, ведущий научный сотрудник лаборатории №1 Федоренко Сергей Валентинович, доктор технических наук, доцент, ФГАОУ ВПО Санкт-Петербургский государственный университет, аэрокосмического приборостроения, профессор кафедры комплексной защиты информации

ФГБОУ ВПО <гМосковский физико-технический институт (государственный университет,)»

Защита состоится «¿о ■» _2012 г. в часов на заседании

диссертационного совета Д 002.077.01 на базе ИППИ РАН. расположенном по адресу: 127994, г. Москва, ГСП-4, Большой Каретный переулок, д. 19, стр. 1.

С диссертацией можно ознакомиться в библиотеке ИППИ РАН. Автореферат разослан « ^ » 2012 г.

Ученый секретарь

диссертационного совета Д 002.077.01 доктор физико-математических наук C^S__.___И. И. Цитович

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

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

Одним из подходов к решению данной задачи является использование кодов с малой плотностью проверок (Г-МПП кодов), предложенных Р. Г. Гал-лагером в 1960 г. Данные коды позволяют строить кодовые блоки большой длины. При этом они являются асимптотически "хорошими"1 и имеют наименьшую из известных сложность декодирования. Исследованию этих кодов посвящено большое количество работ. Достаточно детально были исследованы как потенциальные, так и реализуемые асимптотические корректирующие свойства Г-МПП-кодов. К потенциальным корректирующим относят такие свойства, которые на данный момент реализуются только при использовании алгоритмов декодирования с экспоненциальной сложностью. Кодовое расстояние Г-МПП-кодов было оценено Р. Г. Галлагером в его диссертационной работе 1960 г. В работах Д. Бурштейна и О. Барака 2006 г. и 2007 г. получены верхние и нижние оценки на экспоненту вероятности ошибочного декодирования Г-МПП-кода по максимуму правдоподобия, сложность которого является экспоненциальной. Реализуемые корректирующие свойства Г-МПП-кодов исследовались в работах В. В. Зяблова и М. С. Пинксера 1974 г. и 1975 г., К. Ш. Зигангирова и Д. К. Зигангирова 2006 г., а также в работе К. Ш. Зигангирова, А. Е. Пусане, Д. К. Зигангирова и Д. Дж. Костелло 2008 г. При этом рассматривались алгоритмы декодирования с неэксгюненциальной сложностью для различных каналов связи.

В 1981 г. Р. Таннер предложил обобщеную конструкцию кода с малой плотностью проверок (МПП-кода2). В настоящее время обобщенные конструкции МПП-кодов вызывают всё больший интрес. Из них детально были иссле-

1 Под асимптотически "хорошими" кодами будем понимать кода, у которых минимальное кодовое расстояние растет линеГжо с длиной кода.

2 Здесь и далее под МПП-кодом будем понимать код с малой плотностью проверок с некоторым заданным компонентным кодом, в том числе и кодом с проверкой на четность.

дованы МПП-коды с компонентым кодом Хэмминга (Х-МПП-коды). Потенциальные корректирующие свойства рассматривались в работе К. Ш. Зиган-гирова и М. Лентмайера 1999 г. и в работе В. В. Зяблова и С. Стиглмайера 2007 г. А реализуемые корректирующие свойства Х-МПП-кода. исследовались в работе В. В. Зяблова, Р. Йоханнессона и М. Лоичар 2009 г., а также в работе А. Барга и А. Мазумдара 2011 г. Однако, в предыдущих работах при исследовании алгоритмов декодирования обобщенных конструкций МПП-кодов особенности декодирования компонентных кодов учитывались не в полной мере.

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

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

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

• доля гарантированно исправимых стираний;

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

• экспонента вероятности ошибочного декодирования,

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

Научная новизна состоит в следующем:

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

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

• Предложена новая конструкция МПП-кода и алгоритм его декодирования;

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

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

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

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

• предложена конструкция МПП-кода и алгоритм его декодирования;

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

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

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: IEEE International Symposium on Information Theory (2011), 5th International Symposium on Turbo Codes and Related Topics (2008), International Workshop on Algebraic and Combinatorial Coding Theory (2008, 2010), XII Symposium on Problems of redundancy in information and control systems (2009), конференциях молодых ученных и специалистов ИП-ПИ РАН "Информационные технологии и системы" (2008, 2010, 2011), всероссийских научно-технических конференциях "Актуальные проблемы ракетно-космического приборостроения и информационных технологий" (2010, 2011). Кроме того, основные результаты докладывались на семинарах по теории кодирования в ИППИ РАН, а также в Математическом институте им. А. Реньи Венгерской академии наук.

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

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

Подготовка к публикации полученных результатов проводилась совместно с соавторами. Все теоретические результаты работ [2-5, 9, 11-14] получены автором самостоятельно. В работах [1, 6-8, 10, 15] автору принадлежит разработка алгоритмов декодирования двоичных МПП-кодов и проведение имитационного моделирования.

Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, трех глав, заключения и библиографии. Общий объем диссертации 131 страница, включая 51 рисуиок и 10 таблиц. Библиография включает 73 наименования на 10 страницах.

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

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

В первой главе исследуются корректирующие свойства двоичного МПП-кода при передаче по симметричному стирающему каналу (ССК). Результаты опубликованы в работе [3].

В § 1.1 приведено введение к главе 1.

В § 1.2 описана струкртура двоичного МПП-кода. Рассмотрим построение проверочной матрицы Н обобщенного МПП-кода, компонентный код которого имеет проверочную матрицу Но- Запишем диагональную блочную матрицу Нби с Ъо проверочными матрицами Но па главной диагонали:

/ V

Но 0 .. ,. 0

0 Н0 .. .. 0

0 0 . .. н,

V : К "/

где &о очень велико. Если размер матрицы Но равен то х щ, тогда размер матрицы Щ, - ЬотохЬцщ. Обозначим тг (Щ,,) случайную перестановку столб-

цов матрицы Hj0. Тогда матрица, составленная из £ > 2 таких перестановок в качестве слоев,

([п(Щ) \

н =

н2

\н е/

^(Hi,,)

V /

является разреженной проверочной матрицей Н размера £Ьцто х Ьощ, которая определяет ансамбль обобщенного МПП-кода длины п = Ьцщ, где п По, с заданным кодом-компонентом с проверочной матрицей Нц. Обозначим этот ансамбль £ (щ, £, Ьо).

О п р е д е л е н и е 1.1. Для заданного компонентного кода с проверочной матрицей Но независимо и равновероятно выбирая случайные перестановки 7Гг , I = 1,2,..., £, определим ансамбль обобщенных МПП-кодов £ (щ, £, Ьо).

Таким образом, ансамбль МПП-кодов с компонентным кодом с проверкой на четность, т.е. ансамбль Г-МПП-кодов, будем обозначать &с (no, bo), а ансамбль МПП-кодов с компонетным кодом Хэмминга, т.е. ансамбль Х-МПП-кодов, будем обозначать <£# (п0. £, Ьо)- А обозначение £ (па, £, &о) будем понимать как ансамбль МПП-кодов с заданным компонентным кодом (в том числе и с кодом с проверкой на четности и кодом Хэмминга). В случае необходимости компонентный код будет указываться явно, иначе ансамбль <5 (п-о, £. Ьо) стоит рассматривать как ансамбль МПП-кодов с некоторым заданным компонентным кодом.

В § 1.3 получена новая асимптотическая оценка доли гарантированно исправимых стираний при декодировании двоичного МПП-кода по алгоритму со сложностью О (n logo п). Впервые оценка доли гарантированно исправимых стираний для Г-МПП-кода была получена В. В. Зябловым и М. С. Пин-скером. Затем К.Ш. Зигангиров и Д.К. Зигангиров получили оценку доли гарантированно исправимых стираний для Г-МПП-кода с проверочной матрицей, составленной из перестановочных матриц. В отличие от предыдущих оценок, полученных комбинаторными методами, новая оценка использует метод производящих функций. Это позволяет получить более точные результаты и унифицировать метод расчета доли гарантированно исправимых стираний для МПП-кода с любым компонентным кодом и любым алгоритмом декодирования этого кода-компонента, для которых известны производящие функции исправимых и неисправимых комбинаций стираний.

Описание алгоритма декодирования л/Т приводится в § 1.3.1. Идея алгоритма декодирования заключается в поиске исправимых комбинаций стираний кратности не более г, вошедших в компонентные коды МПП-кода, и в последующем их исправлении.

В § 1.3.2 формулируется основной результат в виде следующей теоремы:

Теорема!.1. Пусть существует хотя бы один положительный

корень и ыт - минимальный из этих корней следующего уравнения:

h{u) — £F(a,u!,Ti о) = О. где Е(а,и,щ) опреде.яяется выражением:

Fía, w, n0) = h(uj) — —Л(ошп 0) + п о

+ max{wlog2 s - — Iog2(ffo(s, "o)) - au Iog2

«o \9o{s,nü)J

где a > O - доля кодов с исправимыми стираниями (свободный параметр, определяющий константу перед оценкой сложности декодирования), и максимизация производиться по всем s, удовлетворяющим неравенству:

ашпр gi(s,n0) 1 — аит0 ~ ffo(s,no)'

Тогда в ансамбле S (щ, t, 6ц) существует код, который может исправить любую комбинацию стираний кратности до [úJrn\ со сложностью декодирования порядка C(7ilogn).

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

• ffo(s,no) — ЦСц'б* - производящая функция количества неиспра-

¿

вимых комбинаций стираний кратности г для заданного кода с длиной

■щ;

• ffi(s,tia) = JJGi'h* - производящая функция количества G^ иепра-

¿

вимых комбинаций стираний кратности i для заданного кода с длиной "о;

• h (ш) = — wlog2w — (1 — <¿>)log2 (1 — ш) - функция двоичной энтропии.

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

В § 1.3.3 приводится доказательство теоремы 1.1.

В § 1.3.4, § 1.3.5 и § 1.3.5 анализируются численные значени оценок доли гарантированно исправимых стираний для Г-МПП-кодов и Х-МПП-кодов. При этом для Г-МПП-кодов рассматривается алгоритм декодирования

т.к. код с проверкой па четность гарантированно исправляет только одно стирание. А для Х-МПП-кодов рассматриваются два алгоритма декодирования $&т=2 и т.к. код Хэмминга гарантированно исправляет любую комби-

нацию из 2 и менее стираний, а также некоторые комбинации стираний кратности более 2 и менее то- На рис. 1 сравниваются максимальные значения повой оценки (ыт=г) и оценки (сио), полученной В. В. Зябловым и М. С. Пин-скером в 1974 г., в зависимости от скорости Я Г-МПП-кода при декодировании по алгоритму Видно, что новая оценка превосходит оценку 1974 г. На рис. 2 приведены максимальные значения новой оценки (и;т=2 и шт=1По) при декодировании по алгоритмам 'г=2 и в зависимости от скорости

Я Х-МПП-кода. Видно, что использование алгоритма дает значитель-

ный выигрыш по сравнению с алгоритмом

Рис. 1. Зависимость максимального значения доли ит=\ и от скорости Я Г-МПП-кода

Рис. 2. Зависимость максимального значения ДОЛИ Шг=2 и шт=то ДЛЯ ЭЛГОриТ-мов " от скорости Я Х-МПП-

кода

В § 1.4 приведены результаты имитационного моделирования для ССК алгоритмов декодирования ¿/т=1 для Г-МПП-кода и £/т=т0 Для Х-МПП-кода. Рассматривались коды со скоростями Л, примерно равными 0, 25, 0,5 и 0,75, длиной п ^ 2000, различным количеством слоев и соотвсствующей длиной кода-компонента. Из полученных результатов следует, что для всех рассмот-репных скоростей вероятность отказа на блок 10~° для Г-МПП-кода достигается при больших значениях входной вероятности стирания, чем для Х-МПП-кода. Таким образом, в этом смысле Г-МПП-код имеет лучшие корректирующие свойства, чем Х-МПП-код. При этом стоит отметить, что оценка доли гарантированно исправимых стираний для Г-МПП-кода также превосходит аналогичную оценку для Х-МПП-кода.

В § 1.5 перечислены основные результаты главы.

Во второй главе исследуются корректирующие свойства двоичного МПП-кода при передаче по двоично-симметричному каналу (ДСК). Резуль-

таты опубликованы в работах [8, 11].

В § 2.1 приведено введение к главе 2.

В § 2.2 полумена новая асимптотическая оценка доли гарантированно исправимых ошибок при декодировании двоичного МПП-кода по алгоритму со сложностью C(nlog2 n). Впервые оценка доли гарантированно исправимых ошибок для Г-МПП-кода была получена В. В. Зябловым и М. С. Пипскером. Данная оценка является наилучшей из известных для Г-МПП-кодов. Наилучшую из известных оценок для Х-МГ1П-кодов получили А. Варг и А. Ма-зумдар. В отличие от предыдущих работ в новой оценке учитываются особенности декодировани компонентных кодов, т. е. учитывается не только количество проверочных соотношений, которые станут выполнеными после замены символа, но также и количество проверочных соотношений, которые останутся невыполненными после замены сим,вола. Это позволяет смягчить условие на существование символа, замена которого уменьшит количество невыполненных проверочных соотношений, что приводит к значительному увеличению значений новой оценки.

Описание итеративного мажоритарного алгоритма декодирования ¿/м приводится в § 2.2.1. Идея алгоритма декодирования заключается в уменьшении количества невыполненных проверочных соотношений на каждой итерации декодирования. Для данного алгоритма получено условие существования хотя бы одного символа, замена которого уменьшит количеств невыполненных проверочных соотношений, при входной комбинации ошибок кратности W:

W W

j=i J=I

где е^ - количество проверок, которые станут выполненными после замены ¿¿-ого символа, а е^ ^ - количество проверок, которые останутся невыполне-ными после замены ¿¿-ого символа.

В § 2.2.2 формулируется основной результат в виде следующей теоремы:

Теорема 2.1. Пусть существует хотя бы один положительный корень и wo - минимальный из этих корней следующего уравнения:

h (ы) - lFt (w, n0) = О, где Fe (ш, щ) определяется выражением:

Fc (ш, п0) = h (w) + max {wlog2si> - — log2 (ge (s, v,n0) + So (s,«o)) i • s>o,o<i'<i no J

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

нения:

h (w0) - IFS (a, lj0, n0, t) = 0, где Fs(a,ui0,no,i) определяется выражением:

д / £ - —

Fs (a, u0, n0, t) = h (wo) + max {cj0 bg2s + —j^-logjU

s>0.0<r<l \ I

- — 1°K2 (.91 (s, "о) V + ffo {s, no))} ■

Щ

Тогда в ансамбле 3 (no, Z, bo) существует код, который может исправить любую комбинацию ошибок кратности до [wtnj. где wt = Qo^o,- со сложностью декодирования порядка О (nlogn).

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

• go (s, по) = ^ Gq 's* - производящая функция количества Gq ' кодовых слов веса i заданного кода с длиной «о;

• <?1 (s, no) = ~ производящая функция количества G^ комбина-

i

ций г ошибок, обнаруживаемых заданным кодом с длиной гг.0;

• де (s, v, щ) = £ Ge^s>vl - производящая функция количества таких

' з

Ge'^ комбинаций j ошибок, что Е^ (см. (1)) равна в точности г.

Таким образом, подставляя производящие функции go (s, щ), gi (s, по) и ga(s,v,rio), соотвествующие компонентному коду, получаем нижнюю оценку доли гарантированной исправимых ошибок для МПП-кода с заданными компонентым кодом. В дальнейшем рассматриваются только Г-МПП-коды и Х-МПП-коды.

В § 2.2.3 приводится доказательство теоремы 2.1.

В § 2.2.4, § 2.2.5 и § 2.2.6 анализируются численные значения оценок доли гарантированно исправимых ошибок для Г-МПП-кодов и Х-МПП-кодов. На рис. 3 сравниваются максимальные значения новой оценки (ы() и оценки (ша/2), полученной В. В. Зябловым и М. С. Пинскером в 1975 г., в зависимости от скорости R Г-МПП-кода. Видно, что новая оценка улучшает оценку 1975 г. для Г-МПП-кодов. На рис. 4 сравниваются значения новой оценки (u>t) и оценки (7о/2), полученной А. Баргом и А. Мазумдаром 2011 г., в зависимости от длины кода-компонента п0 Х-МПП-кода со скоростью R = 0,5. Видно, что предложенная оценка улучшает оценку 2011 г. для Х-МПП-кодов.

-тафв^, 5 £ I £ 80 г-тах(ш 12), 5 £ I 5 81

ч.

0.4 0.6 14

Рис. 3. Зависимость максимального значения доли зд и иа/2 от скорости Я Г-МПП-кода

т* Ю

Рис. 4. Зависимость значения доли и 7о/2 от длины кода-компонента по Х-МПП-кода со скоростью Я = 0,5

В § 2.3 приведены результаты имитационного моделирования для ДСК алгоритма декодирования для Г-МПП-кода и Х-МПП-кода. Рассматривались коды со скоростями Я, примерно равными 0,25, 0,5 и 0, 75, длиной п и 2000, различным количеством слоев и соотвествующей длиной кода-компонента. Из полученных результатов следует, что для всех рассмотренных скоростей вероятность отказа на блок 10~5 для Г-МПП-кода достигается при больших значения входной вероятности ошибки, чем для Х-МПП-кода. Таким образом, в таком смысле Г-МПП-код имеет лучшие корректирующие свойства, чем Х-МПП-код. При этом стоит отметить, что оценка доли гарантированно исправимых ошибок для Г-МПП-кода также превосходит аналогичную оценку для Х-МПП-кода.

Так же для Г-МПП-кода исследован новый алгоритм декодирования с введением стираний Основная идея данного алгоритма заключается в том, что на позиции подозрительных символов (т.е. символов, удовлетворяющих критерию замены) устанавливаются стирания, а затем исправляются только стирания. По завершении каждой итерации на места стираний, если они не были исправлены, устанавливаются изначальные (принятые) Значения. Из полученных результатов следует, что для всех рассматриваемых кодовых скоростей предложенный алгоритм „с/, имеет лучшие корректирующие свойства, чем т.е. при декодировании по алгоритму вероятность отказа на блок 10~5 достигается при больших значениях входной вероятности ошибки, чем при декодировании по алгоритму ¿¿м- При этом следует отметить, что предложенный алгоритм л/» является универсальным и может быть использован не только в канале с ошибками, но также и в канале со стираниями и канале с ошибками и стираниями.

В § 2.4 перечислены основные результаты главы.

В третьей главе исследуется МПП-код со специальной контрукцией и его корректирующие свойства при передаче по ДСК. Результаты опубликованы в работе [5].

В § 3.1 приведено введение к главе 3.

В § 3.2 описывается исследуемая конструкция МПП-кода. Пусть Нг -проверочная матрица Г-МПП-кода со скростыо из ансамбля £с, ("оД Ьо), т.е. длина Г-МПП-кода п = щЬо■ Пусть Н1 - проверочная матрица линейного блокового кода со скоростью Rl и длиной щ. Рассмотрим блочную диагональную матриц}' Н;,,, на главной диагонали которой стоят Ь1 проверочных матриц Нх:

/ \

Hi 0 . .. 0

0 H, . .. 0

0 0 . .. H

1-,,-'

V Ь. /

где 61 такая, что bitii = ЬоЩ. Тогда, проверочную матрицу рассматриваемой конструкции МПП-кода можно записать следующий образом:

h=(w(ho)'

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

Определение 3.1. Построенную конструкцию МПП-кода будем называть Г-МПП-кодом с добавленным одним слоем, составленным из линейных кодов (CJI-Г-МПП-кодом).

Длина получившегося кода равна п = bono = &ini, а скорость R можно найти следующим образом:

R > Ri + R2 - 1.

Определе н и е 3.2. Равновероятно выбирая проверочную матрицу Н2 из ансамбля S'a ("о, é, bo) и случайную перестановку тг, определим ансамбль SL {по, I, Ьо, щ, 1, bi) СЛ-Г-МПП-кодов.

В § 3.3 получена асимптотическая оценка экспоненты вероятности ошибочного декодирования МПП-кода со специальной конструкцией при передаче по ДСК без памяти. Впервые показано, что при передаче по ДСК без памяти в ансамбле CJl-Г-МПП-кодов существуют коды, при декодировании которых по алгоритму со слоокностъю О (п log2 п) вероятность ошибочного декодирования убывает, экспоненциально для всех скоростей меньше пропускной способности канала.

Алгоритм декодирования описан в § 3.3.1. Идея алгоритма декодирования заключается в том, что каждую принятую последовательность алгоритм sie декодирует только один раз. Сначала - по максимуму прадоподобия, используя независимо каждый линейный код с проверочной матрицей Hi из добавленного слоя, затем полученную последовательность декодирует по мажоритарному алгоритму ¿¿м, используя Г-МПП-код с проверочной матрицей Н2.

Оценку вероятности ошибочного декодирования по алгоритму я/с для ДСК без памяти с вероятностью искажения символа pt представим следующим образом:

Р < ехр {-пЕ {R\,nhwt,Pt)},

где Е (üEi, ni,ut,pt) ~ искомая экспонента вероятности ошибочного декодирования.

В § 3.3.2 формулируется основной результат в виде следующей теоремы: Теорем а 3.1. Пусть в ансамбле SG (по, t &о) существует Г-МПП-код со скростью R2, который исправляет любую комбинацию ошибок кратности до [wtnj при декодировании по мажоритарному алгоритму

Пусть также, существует линейный код с длиной щ, скоростью Ri и экспонентой вероятности ошибочного декодирвания по максимуму правдоподобия E0(R\,pt).

Тогда в ансамбле SL (n0, i, Ь0) Щ, 1, h) существует СЛ-Г-МПП-код с длиной п:

п — щЬо = Jiibi

и скоростью R:

R > Rx + R2 - 1

такой, что при передаче по ДСК без памяти с вероятностью ошибки pt экспонента ошибочного декодирования со с.гожностью ü(nlog7i) ограничена снизу Е:

E(R\.ni,uit,Pt) = min {ßEü{RuPt) + E2(ß,üJt,pt)-^-H{ß)\, (2) Ut<ß<0O "1 J

где ß0 = min l), H (ß) = -ßlnß - (1 - ß) In (1 - ß) - функция энтропии, a E2{ß,Ut,Pt) имеет следующий вид:

Е-2 (ß, Wt, Pt) = \ (с* In Jt + {2ß - UH) In - ß In (2/3),

при этом п\ удовлетворяет следующим условиям:

Е{> (Ru Pi) ~

- Mo

< ni < — log2log2 (ri).

1

В самом общем виде нижняя оценка на. Ea(Ri,pt) для линейных кодов была получена Р. Г. Галлагером, откуда следует, что существуют коды, для которых Eq (Ri ,pt) >0 для Ri < rtf, где W - пропускная способность ДСК без памяти с вероятное™ ошибки pt. Тогда из (2) видно, что если R —¡> так, что R\ < и Я2 < 1) то можно подобрать такое щ, удовлетворяющее условию (3), что E(Ri,nj,Ut,Pt) > 0, если ojt > 0 для \/R2 < 1.

В § 3.3.3 приводится доказательство теоремы 3.1.

В § 3.3.4 анализируются численные значения оценки экспоненты вероятности ошибочного декодирования СЛ-Г-МПП-кода. Значение экспоненты вероятности ошибки будем максимизировать по таким скоростям R\ линейного кода и i?2 Г-МПП-кода, что R = Ri + R? — 1. Обозначим полученное значение следующим образом:

Рассмотрим зависимость E(R,p) от скорости R CJI-Г-МПП-кода при фиксированной длине линейного кода щ = 2000 и входной вероятности ошибки р = 0,001. Из рис. 5 видно, что полученная оценка Е (R,p) уступает наилучшей известной экспоненте вероятности ошибочного декодирования Eg (R. р) примерно два порядка при р = 0,001. При этом сложность декодирования СЛ-Г-МПП-кода с эксполентой вероятности ошибки Е (R, р) составляет порядка О (nlogn), а сложность декодирования линейного кода по максимуму правдоподобия с экспонентой вероятности ошибки Eq (R, р) составляет поряд-

В § 3.4 приведены результаты имитационного моделирования алгоритма декодирования s/c Для различных параметров СЛ-Г-МПП-кода. В качетсве линейных кодов были выбраны коды БЧХ (31, 21) и (63, 39). Рассматривались коды длины n ~ 2000, с. количеством слоев в диапазоне I = 3,4,..., 7 и скоростям R, примерно равными 0,25 и 0,5. Из полученных результатов следует, что СЛ-Г-МПП-код с кодом БЧХ (63, 39) имеет лучшие корректирующие свойства, чем СЛ-Г-МПП-код с кодом БЧХ (31, 21), в том смысле, что вероятность отказа от декодирования 10~° достигается при больших значениях входной вероятности ошибки. Важно отметить, что при некоторых значениях р£ экспериментально полученная экспонента вероятности ошибочного декодирования значительно превосходит полученную оценку.

В § 3.5 перечислены основные результата главы.

E(R,p) -

max Л1,Д2:Л1+Д2-1=й

E(Runj,wt,pt).

ка О (2п).

р

Рис. 5. Зависимость Е(Я,р) при фиксированной ni = 2000 и Во (Я, р) от скорости R при вероятности ошибки р — 0,001

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

• получена новая оценка доли гарантированно исправимых стираний при декодировании МПП-кода со сложностью О (nlogn);

• численно показано, что полученная оценка превосходит лучшую известную оценку доли гарантированно исправимых стираний при декодировании Г-МПП-кода со сложностью О (п log п);

• впервые получена оценка доли гарантированно исправимых стираний при декодировании Х-МПП-кода по двум алгоритмам: по алгоритму, гарантированно исправляющему не более двух стираний в компонентном коде, и по алгоритму, гарантированно исправляющему не более двух стираний и некоторые комбинации стираний большей кратности до то в комоппентиом коде;

• получена новая оценка доли гаратированно исправимых ошибок при декодировании МПП-кода со сложностью О (nlogn);

• численно показано, что полученная оценка превосходит лучшие известные оценки доли гарантированно исправимых ошибок при декодировании Г-МПП-кода и Х-МПП-кода со сложностью О (п logn);

• предложен новый алгоритм декодирования с вводом стираний;

• предложена новая конструкция МПП-кодов (CJT-Г-МПП-коды) и алгоритм их декодирования;

• впервые получена оценка экспоненты вероятности ошибочного декодирования СЛ-Г-МПП-кода по предложенному алгоритму со сложностью О (п log л.);

• впервые показано, что при передаче по ДСК без памяти существует CJI-Г-МПП-код, при декодировании которого со сложностью О (nlogn) вероятность ошибки убывает экспоненциально для любой скорости меньше пропускной способности.

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

1. Жилин И. В., Рыбин П. С., Зяблов В. В. Сравнение алгоритмов декодирования двоичных МПП-кодои с жестким входом // Сборник трудов конференции информационные технологии и системы (ИТиС'11), Геленджик, Россия. М: ИППИ РАН, 2011. С. 221 - 227.

2. Зяблов В. В., Рыбин П. С. Исправление стираний низкоплотностными кодами Галлагера // Сборник трудов конференции информационные технологии и системы (ИТиС'08), Геленджик, Россия. М: ИППИ РАН, 2008. С. 167 - 172.

3. Зяблов В. В., Рыбин П. С. Исправление стираний кодами с малой плотностью проверок // Пробл. передачи информ. 2009. Т. 45, № 3. С. 15—32.

4. Зяблов В. В., Рыбин П. С. Оценивание в графе Таннера числа ребер с заданными свойствами // Сборник трудов конференции информационные технологии и системы (ИТиС'Ю), Геленджик, Россия. М: ИППИ РАН,

2010. С. 79 - 84.

5. Зяблов В. В., Рыбин П. С. Оценка экспоненты вероятности ошибки декодирования обобщенного МПП-кода специальной конструкции /7 Информационные процессы. 2012. Т. 12, № 1. С. 84—97.

6. Зяблов В. В., Рыбин П. С., Жилин И. В. и др. Применение помехоустойчивых кодов с малой плотностью проверок (МПП) в радиолиниях ДЗЗ // IV Всероссийская научно-техническая конференция "Актуальные проблемы ракетио-космического приборостроения и информационных технологий".

2011. С. 79.

7. Зяблов В. В., Рыбин П. С., Петров С. В., Пятошин Ю. П. Сравнительная оценка практической целесообразности использования современных сигнальио-кодовых конструкций в высокоскоростных радиолиниях // III

Всероссийская научно-техническая конференция "Актуальные проблемы ракетно-космического приборостроения и информационных технологий". 2010. С. 101.

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

9. Рыбин П. С. , Зяблов В. В. Оценка доли гарантированно исправимых ошибок двоичным Х-МПП-кодом // Сборник трудов конференции информационные технологии и системы (ИТиС'11), Геленджик, Россия. М: ИППИ РАН, 2011. С. 189 - 194.

10. Rybin P., Zyablov V. Decoding with Erasure Insertion of Binary LDPC Codes // XII International Symposium on Problems of redundancy in information and control systems, St. Petersburg, Russia. 2009. P. 150 - 154.

11. Rybin P., Zyablov V. Asymptotic estimation of error fraction corrected by binary LDPC code /,/ Proceedings of IEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia. 2011. P. 351 - 355.

12. Zyablov V., Loncar V., Johannesson R., Rybin P. On the Asymptotic Performance of Low-Complexity Decoded LDPC Codes with Constituent Hamming Codes // 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland. 2008. P. 174 -179.

13. Zyablov V.. Loncar V., Johannesson R., Rybin P. On the Erasure-Correcting capabilities of Low-Complexity Decoded LDPC Codes with Constituent Hamming Codes // Eleventh International Workshop on Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria. 2008. P. 338- 347.

14. Zyablov V., Loncar V., Johannesson R., Rybin P. On the Error-Correcting Ca-pabilitiers of Low-Complexity Decoded LDPC Codes with Constituent Hamming Codes // Eleventh International Workshop on Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria. 2008. P. 326 - 337.

15. Zyablov V., Rybin P. Majority decoding and decoding with erasure insertion of binary LDPC codes ,// Twelfth International Workshop on Algebraic and Combinatorial Coding Theory, Akademgorodok, Novosibirsk, Russia. 2010. P. 329 - 334.

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

26.04.2012

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

Федеральное государственное бюджетное учереждение науки ИНСТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ им А. А. Харкевича Российской академии наук

61 12-1/803

На правах рукописи

Рыбин Павел Сергеевич

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

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

ДИССЕРТАЦИЯ

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

Научный руководитель д. т. н. Зяб лов В. В.

Москва - 2012

Содержание

Введение ......................................................................4

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

Глава 1. Исправление стираний двоичным МПП-кодом .... 10

1.1. Введение...............................10

1.2. Структура двоичного МПП-кода................. . 10

1.3. Асимптотическая оценка доли гарантированно исправимых стираний .................................13

1.4. Имитационное моделирование алгоритма декодирования МПП-кода для исправления стираний..................35

1.5. Выводы к главе...........................43

Глава 2. Исправление ошибок двоичным МПП-кодом.....47

2.1. Введение...............................47

2.2. Асимптотическая оценка доли гарантированно исправимых ошибок ..................................47

2.3. Имитационное моделирование алгоритмов декодирования МПП-кода для исправления ошибок...................80

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

Глава 3. Построение МПП-кода со специальной контрукцией 97

3.1. Введение...............................97

3.2. Структура МПП-кода со специальной конструкцией ......97

3.3. Асимптотическая оценка экспоненты вероятности ошибочного декодирования ........................................................99

3.4. Имитационное моделирования алгоритма декодирования МПП-кода со специальной контрукцией.................110

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

Заключение..................................120

Литература..................................122

Введение

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

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

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

ной работе 1960 г. В работах Д. Бурштейна и О. Барака 2006 г. и 2007 г. получены верхние и нижние оценки на экспоненту вероятности ошибочного декодирования Г-МПП-кода по максимуму правдоподобия, сложность которого является экспоненциальной. Реализуемые корректирующие свойства Г-МПП-кодов исследовались в работах В. В. Зяблова и М. С. Пинксера 1974 г. и 1975 г., К.Ш. Зигангирова и Д. К. Зигангирова 2006 г., а также в работе К. Ш. Зигангирова. А. Е. Пусане, Д. К. Зигангирова и Д. Дж. Костелло 2008 г. При этом рассматривались алгоритмы декодирования с неэкспоненциальной сложностью для различных каналов связи.

В 1981 г. Р. Таннер предложил обобщеную конструкцию кода с малой плотностью проверок (МПП-кода2). В настоящее время обобщенные конструкции МПП-кодов вызывают всё больший интрес. Из них детально были исследованы МПП-коды с компонентым кодом Хэмминга (Х-МПП-коды). Потенциальные корректирующие свойства рассматривались в работе К. Ш. Зигангирова и М. Лентмайера 1999 г. и в работе В. В. Зяблова и С. Стиглмайера 2007 г. А реализуемые корректирующие свойства Х-МПП-кода исследовались в работе В. В. Зяблова, Р. Иоханнессона и М. Лончар 2009 г.. а также в работе А. Барга и А. Мазумдара 2011 г. Однако, в предыдущих работах при исследовании алгоритмов декодирования обобщенных конструкций МПП-кодов особенности декодирования компонентных кодов учитывались не в полной мере.

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

2 Здесь и далее под МПП-кодом будем понимать код с малой плотностью проверок с некоторым заданным компонентным кодом, в том числе и кодом с проверкой на четность.

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

• доля гарантированно исправимых стираний;

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

• экспонента вероятности ошибочного декодирования,

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

Научная новизна состоит в следующем:

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

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

• Предложена новая конструкция МПП-кода и алгоритм его декодирования.

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

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

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

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

• предложена конструкция МПП-кода и алгоритм его декодирования;

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

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

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

Theory (2011), 5th International Symposium on Turbo Codes and Related Topics (2008), International Workshop on Algebraic and Combinatorial Coding Theory (2008, 2010), XII Symposium on Problems of redundancy in information and control systems (2009), конференциях молодых ученных и специалистов ИП-ПИ РАН "Информационные технологии и системы" (2008, 2010, 2011), всероссийских научно-технических конференциях "Актуальные проблемы ракетно-космического приборостроения и информационных технологий" (2010, 2011). Кроме того, основные результаты докладывались на семинарах по теории кодирования в ИППИ РАН, а также в Математическом институте им. А. Реньи Венгерской академии наук.

Публикации. Материалы диссертации опубликованы в 15 печатных работах, из них 3 статьи в рецензируемых журналах [11, 13, 16], 10 статей в сборниках трудов конференций [3, 10, 12, 20, 61, 62, 70-73] и тезисах 2 докладов [14, 15].

Личный вклад автора. Все основные научные положения и выводы, составляющие содержание /диссертации, разработаны автором самостоятельно. Теоретические и практические исследования, а также вытекающие из них выводы и рекомендации проведены и получены автором лично. Подготовка к публикации полученных результатов проводилась совместно с соавторами. Все теоретические результаты работ [10-13, 20, 62, 70-72] получены автором самостоятельно. В работах [3, 14-16, 61, 73] а,втору принадлежит разработка алгоритмов декодирования двоичных МПП-кодов и проведение имитационного моделирования.

Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, трех глав, заключения и библиографии. Общий объем диссертации 131 страница, включая 51 рисунок и 10 таблиц. Библиография включает 73 наименования на 10 страницах.

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

В 1960 г. Р. Г. Галлагер предложил Г-МПП-коды, описанные в работе [42], в которой приведена оценка кодового расстояния и предложены практически реализуемые эффективные алгоритмы декодирования (мажоритарный алгоритм и алгоритм распространения доверия ). В 1974 г. и 1975 г. В. В. Зяблов и М.С. Пинскер в работах [8, 9] исследовали реализуемые корректирующие свойства предложенных кодов для симметричного стирающего канала (ССК) и двочино-симметричного канала (ДСК). В 1981 г. Р. Таннер предложил [67] обобщеную конструкцию МПП-кода. К сожалению, в силу слабого развития вычислительной техники, интерес к Г-МПП-кодам угас на некоторое время.

Но с появлением работ М. Сипсера, Д. Спилмана [63, 65], Д. Маккея [51] и Г. Земора [69] активное исследование Г-МПП-кодов возобновилось. В настоящий момент Г-МПП-кодам посвящено большое количество работ. Рассматривались корректирующие свойства различных алгоритмов декодирования как для исправления ошибок [5, 6, 18, 24, 27, 30, 33, 34, 36, 53, 56, 68], так и для исправления стираний [37, 43, 44, 55]. Исследовались кодовое расстояние и спектр Г-МПП-кодов [23, 28, 35, 38, 47, 57, 58, 64]. Предлагались эффективные алгоритмы кодирования Г-МПП-кодов[31, 41, 49, 60]. Исследовались различные конструкции Г-МПП-кодов [4, 19, 22, 26, 29, 39, 40, 48, 50, 59].

Начиная с работ К. Ш. Зигангирова, М. Лентмайера [45, 46] и Дж. Бутроса, О. Пофиера, Г. Земора [32] всё больший интерес вызывают обобщенные МПП-коды. Из класса обобщенных МПП-кодов детально были исследованы Х-МПП-коды. В работе [66] показано, что нижняя оценка кодового расстояния Х-МПП-кода достигает границу Варшамова-Гилберта. В дальнейшем исследовались реализуемые корректирующие свойства Х-МПП-кодов [7, 25]. В настоящее время актиано исследуются различные конструкции обобщенных МПП-кодов [52, 54].

Глава 1

Исправление стираний двоичным МПП-кодом 1.1. Введение

В первой главе для симметричного стирающего канала (ССК) исследуются реализуемые корректирующие свойства двоичного МПП-кода. Рассматривается алгоритм декодирования для исправления стираний. Получена нижняя оценка доли гарантированно исправимых стираний двоичным МПП-кодом при декодировании по алгоритму для исправления стираний со сложностью 0{п\о%п). Эффективность рассматриваемого алгоритма декодирования показана с помощью иммитационным моделированием.

1.2. Структура двоичного МПП-кода

Рассмотрим построение проверочной матрицы Н обобщенного МПП-кода, компонентный код которого имеет проверочную матрицу Но. Запишем диагональную блочную матрицу Щ0 с &о проверочными матрицами Но на главной диагонали:

Щ,

(

\

Н0 О О Н0

О О

О 0 ... Нг

V

Ьп

/

где 60 очень велико. Если размер матрицы Но равен то х щ, тогда размер матрицы Нг,0 - х Обозначим 7г (Нь0) случайную перестановку столбцов матрицы Щ0. Тогда матрица, составленная из £> 2 таких перестановок

в качестве слоев,

Н =

н.

у не у у тте(нь0) у является разреженной проверочной матрицей Н размера £Ьогпо х ЬоЩ, которая определяет ансамбль обобщенного МПП-кода длины п = Ьощ, где п по, с заданным кодом-компонентом с проверочной матрицей Но- Обозначим этот ансамбль <§ (щ, £, Ьо).

Определение 1.1. Для заданного компонентного кода с проверочной матрицей Но независимо и равновероятно выбирая случайные перестановки 7гI , I = 1. 2,.... £, определим ансамбль обобщенных МПП-кодов § (щ, £, Ьо).

Замечание 1.1. Необходимо отметить, что <§ (щ, £, Ьо) определяет не ансамбль всех обобщенных МПП-кодов, а ансамбль обобщенных МПП-кодов с заданным компонентным кодом. В данной работе мы будем рассматривать только код с проверкой на четность и код Хэмминга в качестве компонентных кодов. В случае необходимости компонентный код будет указываться явно, иначе ансамбль § (щ.£,Ьо) стоит рассматривать как ансамбль МПП-кодов с некоторым заданным компонентным кодом.

Таким образом, ансамбль МПП-кодов с компонентным кодом с проверкой на четность, т.е. ансамбль Г-МПП-кодов, будем обозначать (щ, А Ьо), а ансамбль МПП-кодов с компонетным кодом Хэмминга, т.е. ансамбль Х-МПП-кодов, будем обозначать (Щ, £-, Ьо)-

Нижняя оценка, полученная в [67], на скорость Я кода из ¿> (по,£,Ьо) определяется следующим неравенством:

К ^ 1 - £ (1 - Щ ,

где Ко - скорость кода-компонента. Равенство достигается только в случае,

когда Н имеет полный ранг.

Как следует из построения, обобщенный МПП-код из (о (щ,£,Ьо) имеет п = Ьопо кодовых символов, которые распределены между £Ьо компонентных кодов (Ъ0 в каждом слое) с проверочной матрицей Н0. Такие коды могут быть представлены с помощью двудольного графа ТаIшора [67] (•' (VI : У2,Е) с п — Ьощ вершинами-символами 14 и £Ьо вершинами-кодами как на рис. 1.1. Каждая вершина-код включает то проверочных уравнений, соот-

Слой 1 Слой 2 Слой е

Рис. 1.1. Двудольный граф Таннера соответствующий проверочной матрице Н обобщенного МПП-кода

ветствующих проверочной матрице Но- Если символ входит в проверку кода-компонента, то в графе Таннера существует ребро из Е, соединяющее соответствующую вершину-символ из У\ с соответствующей вершиной-кодом из У^. В соответствии с конструкцией проверочной матрицы обобщенного МПП-кода каждый кодовый символ входит в проверки точно одного кода-компонента в каждом слое. Таким образом, соответствующий граф Таннера регулярен со степенью вершины-символа равной £ и степенью вершины-кода равной щ.

1.3. Асимптотическая оценка доли гарантированно исправимых стираний

Впервые для симметричного стирающего канала (ССК) корректирующие свойства Г-МПП-кода исследовались в работе [8], где было доказано, что существует Г-МПП-код с длиной п, гарантированно исправляющий линейно растующее с длиной число стираний при декодировании со сложностью 0(п\о&п). Затем в работе [4| для определенного класса Г-МПП-кодов с проверочными матрицами, составленными из перестановочных матриц, был получен результат аналогичный [8]. При этом численно показано, что оценка [4] в некоторых случах превосходит результаты оценки [8]. Заметим, что в работе [4] рассматривался определенный подкласс Г-МПП-кодов, в то время, как в работе [8] рассматривался весь ансамбль Г-МПП-кодов.

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

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

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