Разработка конструкций сверточных кодов с малой плотностью проверок тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Кондрашов, Константин Александрович

• Кондрашов, Константин Александрович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Кондрашов, Константин Александрович

Содержание

Введение

Глава 1. Сверточные коды с единичной памятью и малой плотностью проверок

1.1. Введение

1.2. Базовые определения

1.3. Структура сверточных МПП кодов с единичной памятью

1.4. Асимптотическая оценка кодовых расстояний сверточных МПП кодов с единичной памятью

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

Глава 2. Исследование корректирующих свойств ЕП МПП кодов

2.1. Введение

2.2. Алгоритм декодирования ЕП МПП кодов

2.3. Декодирование ЕП МПП кодов с нулевым хвостом

2.4. Декодирование ЕП МПП кодов с циклическим замыканием хвоста

2.5. Декодирование ЕП МПП кодов, построенных на основе системы троек Штейнера

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

Глава 3. Плетеные МПП коды

3.1. Введение

3.2. Сверточные МПП коды

3.3. Выбор кодов-компонентов

3.4. Конструкция 2-плетоного сверточного МПП кода

3.5. Конструкция 4-нлетеного сверточного МПП кода

3.6. Кодирование плетеных сверточных кодов

3.7. Построение ансамбля плетеных сверточных кодов

3.8. Оценка активных расстояний плетеных МПП кодов

Глава 4. Исследование корректирующих свойств плетеных МПП кодов

4.1. Декодирование плетеных сверточных кодов

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

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

4.4. Исследование корректирующих свойств П-СМПП кодов

4.5. Описание параметров моделирования

4.6. Декодирование итеративным алгоритмом

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

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

Глава 5. Заключение

Литература

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

Введение

Актуальность работы. Объемы накапливаемой и обрабатываемой в современном мире информации непрерывно возрастают, повышаются и требования к скорости и достоверности передачи данных по каналам связи. Для достижения меньших вероятностей ошибок при передаче, согласно фундаментальным результатам теории кодирования, необходимо использовать все более длинные коды. Однако, при выборе длинных кодов недостаточно руководствоваться только их корректирующими свойствами. Определяющими факторами применимости таких кодов, наряду с хорошими асимптотическими корректирующими свойствами, становятся сложность кодирования и декодирования. Возникает задача построения и исследования эффективных кодов, имеющих реализуемые с помощью современных технических средств алгоритмы кодирования и декодирования. Реализуемыми принято считать алгоритмы кодирования и декодирования с неэкспоненциальной сложностью. Наиболее известными и широкоупотребимыми кодами этого класса являются коды с малой плотностью проверок (МПП). МПП коды были предложены Р. Г. Галлагером в 1962 г. В работах В. В. Зяблова и М. С. Пинксера 1974 г. и 1975 г. было показано, что минимальное расстояния МПП кодов растет линейно с длиной кода и были предложены просто реализуемые алгоритмы декодирования. Однако, несмотря на хорошие потенциальные корректирующие свойства, МПП коды долгое время игнорировались.

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

ности декодирования. В работе Хименеса и Зигангирова 1999 г концепция МПП кодов Галлагера была применена к сверточным кодам. Далее, в работе А. Е. Пусане, Д. К. Зигангирова и Д.Дж. Костелло были исследованы границы минимального и свободного расстояний и было доказано, что пороги МПП сверточных кодов приближаются к пропускным способностям каналов.

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

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

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

• Разработан класс сверточных кодов с единичной памятью и малой плотностью проверок (ЕП МПП). Получены теоретические оценки свободного и активных расстояний. Показано, что при скоростях Я < 0.5 граница свободного расстояния ЕП МПП кодов совпадает с границей Томмесена-Юстесена свободного расстояния случайных ЕП кодов.

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

• Разработан класс 4-нлетеных сверточных кодов (4-П-СМПП) с малой

плотностью проверок. Экспериментально установлены метрические свойства.

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

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

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

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

4

строенных на основе блоковых кодов с малой плотностью проверок (ЕП МПП), и рассмотрены потенциальные корректирующие свойства;

• предложен ансамбль ЕП МПП кодов, получены асимптотические характеристики лучших кодов в ансамбле;

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

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

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: IEEE International Symposium on Information Theory (2011), International Workshop on Algebraic and Combinatorial Coding Theory (2010, 2012), XII Symposium on Problems of redundancy in information and control systems (2009), конференциях молодых ученных и специалистов ИППИ РАН "Информационные технологии и системы" (2009, 2010, 2011). Результаты работы используются на практике, в частности, при выполнении НИР «Методы обеспечения качества обслуживания при доступе к широкополосным мультимедийным услугам в беспроводных самоорганизующихся сетях», проводимой ИППИ РАН по Соглашению №8330 (2012 г.) с Министерством образования и науки России.

Публикации. Материалы диссертации опубликованы в б печатных работах, из них 3 статьи в рецензируемых журналах [42, 45, 46], 3 статьи в сборниках конференций [19, 43, 44].

Личный вклад автора. Все основные научные положения и выводы, составляющие содержание диссертации, разработаны автором самостоятельно. Теоретические и практические исследования, а также вытекающие из них выводы и рекомендации проведены и получены автором лично. Подготовка к публикации полученных результатов проводилась совместно с соавторами. Все теоретические результаты работ [43-46], [19] получены автором самостоятельно. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавторами.

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

Глава 1

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

1.1. Введение

Вынесенные Ли в 1976 году в отдельный класс [23] коды с единичной памятью (ЕП) и параметрами (./V,1'<), где N - длина кодового блока, а К - размерность, являются сверточными (./V, К, т, 1/)-кодами с памятью т = 1 и длиной кодового ограничения V = К. Каждый последующий кодовый блок такого сверточного кода зависит от текущего информационного блока и одного предыдущего. Длина кодового ограничения V определяет количество символов сохраненного блока, участвующих в этой зависимости. Идея кодов с единичной памятью получила дальнейшее развитие в работах Лаэра. В работе [22] он представил (ЛГ, К, и) - коды с частично единичной памятью (ЧЕГ1). Как и коды с полной единичной памятью, они являются сверточными кодами с памятью т = 1, однако длина их кодового ограничения меньше максимальной: и < К.

Простые верхние границы свободного расстояния (Ч)ЕП кодов были получены Ли [23] и Лаэром [22] на основе общей границы сверточных кодов. Позже было установлено различие в корректирующих свойствах ЕП кодов и сверточных кодов с большей памятью. В своей работе [33], К. Томмесен и И. Юстесен показали, что ЕП коды могут обладать свойствами, превосходящими свойства сверточных кодов с произвольной памятью при сравнимых параметрах.

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

ему информационных блоков, (Ч)ЕП коды предлагают богатые возможности для их исследования. Аналитические методы, разработанные для изучения блоковых кодов, могут быть применены и к (Ч)ЕП кодам, которые имеют в своей основе те же блоковые коды [41], [5, 6].

В данной главе предлагается конструкция (Ч)ЕП кодов, построенных на основе блоковых кодов с малой плотность проверок (МПП). Свойства МПП кодов чаще всего исследуются через их разреженные проверочные матрицы. Аналогично, свойства предложенных (Ч)ЕП МПП кодов исследуются на основе их проверочных матриц. Ансамбль (Ч)ЕП МПП кодов состоит из полубесконечных проверочных матриц, обладающих, (частично) единичной памятью. Для заданного ансамбля кодов выводятся нижние оценки активных строчных расстояний, свободного расстояния и уклона.

1.2. Базовые определения

Всякий линейный код может быть задан как порождающей, так и проверочной матрицей. Для построения ансамбля (Ч)ЕП МПП кодов используем проверочные матрицы блочных МПП кодов Галлагера.

Коды с малой плотностью проверок, описываемые разреженными проверочными матрицами, были впервые предложены Галлагером [13]. Проверочная матрица Ньорс к0Да Галлагера состоит из так называемых "слоев" следующего вида:

/

Н0 0 ... О О Н0 ... О

\

н*

\

где Hq - проверка на четность длины щ:

Н0 = (1 1 ... 1).

—v"

п0

Пусть 7Г (Н*) обозначает матрицу, полученную из матрицы Н* случайной перестановкой столбцов. Тогда проверочная матрица МПП кода Галлагера с £ слоями имеет вид:

VLldpc =

( 7Г1 (H*) Х 7Г2 (Н*)

(1.1)

\ Ц j/ £bxbn0

Все возможные независимые равновероятные перестановки столбцов в разных слоях 7Ti, ... ne порождают ансамбль £ (щ,£, Ъ) МПП кодов Галлагера со скоростью R > 1 — t/щ и длиной N = Ьпо.

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

НР(0) Нс(О)

Н/(1) н,(1) Нс(1)

Н/(2) Нр(2)

Нс(2) ••• Н/(3) •••

(1.2)

где подматрицы Нр(£), Н/(£) имеют размер V х п и выбираются независимо из ансамбля £ (по,1;/Ь,Ь) блочных МПП кодов Галлагера, а иодматрицы

И

Hc(í) имеют размер (N — К — v) х п и выбираются независимо из ансамбля £ (щ, {N — К — v)/b, b) блочных МПП кодов Галлагера. Значение и ограничено следующими условиями: u<K,v + K<n.

По построению МПП кодов Галлагера, их проверочные матрицы могут иметь неполный ранг. Будем считать, что rk Нр(£) = rk H/(í) = z/ < и, а rk Hc(í) — N —К' —v'<N —К —v. Отметим, что при Ъ —> оо с вероятностью р 1 ранги rk Hp(í), rk H/(í) -> и и rk Н c(t) N - К -и.

Определение 1.1. Ансамбль <5рмт(Лг, К, и) (Ч)ЕП МПП кодов, v<K,u + K<N, состоит из проверочных матриц вида (1.2), полученных независимым случайным равновероятным выбором подматриц Hp(í), Hc(¿), H/(í) из соответствующих ансамблей блочных МПП кодов Галлагера.

Можно показать, что проверочной матрице вида (1.2) соответствует порождающая матрица вида

Gc(0)

G/(0) Gp(l) Gc(l)

G/(l) Gp(2) Gc( 2)

G/(2) Gp(3)

где подматрицы Gc(¿) и G/(¿), Gp(¿) — матрицы полного ранга размеров (if' — i/') х N и и' х N, соответственно.

Связь между информационной и кодовой последовательностями u, v , где информационная последовательность и состоит из блоков u¿ Е F^', а кодовая последовательность v из блоков v¿ G F2, г £ N:

u = . . . u-г—1 ui uf+i ...

v = . . . vi_i vi vi+1 . . .

(1.3)

можно выразить как

1 п m

v )

Корректирующие свойства сверточного кода во многом опеределяются такими характеристиками, как свободное расстояние, активные строчные расстояния и уклон (средний линейный рост) активных строчных расстояний. Приведем их определения.

Определение 1.2 (Свободное расстояние). Свободное расстояние d/гее линейного сверточного кода С - это минимальное Хэммингово расстояние между любыми двумя различными кодовыми последовательностями:

dfree= min dist(v, v')-Для линейного кода С выполняется min dist (v, v') = min wt (v"),

v,v'€C, v^v' 7 v"€C, v'VO

где функция wt(-) - Хэммингов вес.

В каждый момент времени содержимое памяти определяет состояние кодера сверточного кода. Для кодов с (частично) единичной памятью кодер может быть переведен в нулевое состояние из любого состояния подачей одного нулевого информационного блока. При этом вес кодовой последовательности не увеличится. При частичной памяти ЧЕП МПП кода возможны переходы в нулевое состояние и по ненулевому информационному блоку. Далее будет показано, что в таком случае вес кодовой последовательности увеличивается. Обозначим с помощью Itj множество всех информационных последовательностей и вида

. . О 0 Ui ut+i ... ui+j_i 0 0...,

где Ui Ф 0 при t < i < t + j.

О п p e д e л e н и e 1.3 (Активное строчное расстояние). Активным строчным расстоянием drj (Ч)ЕП МПП кода называется минимальный вес

13

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

(Га = min min {шн (uG)} .

J t u eit,j

Из определений 1.2, 1.3 следует,

dfree = min Щ}.

Определенней (Уклон). Средний линейный рост активного строчного расстояния (уклон) определяется как предел

dri

a = lim -f.

j-УОО J

1.3. Структура сверточных МПП кодов с единичной памятью

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

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

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

и е

Разобьем информационные блоки на две части из К' — и' и и' двоичных символов, где К' — и' - размерность матриц Сс(£), а и' - размерность матриц Ср(£), соответственно: и* = (и^о и*д). В соответствии с кодирующим

правилом,

( ^

v

л Т

и

¿,0

ии

т

иш,о т

ие+1Д

сс (г) о с, (г) Ср(г + 1)

Ос (* + 1) о С/(г + 1) Ср(£ + 2) Сс (г + 2) С7 (* + 2)

\

/

(1.4)

Из (1.4) видно, что каждый кодовый блок в кодовой последовательности принадлежит одному из множеств (здесь и далее, где это не играет роли, опустим временные индексы):

С0 - {хС0}х6]Р1с', Сс - {хСс}х£1,я'-,', С/ = {хС/}хбР^ , Ср = {хСр}хе1Г^ ,

Срс —

в,

» Ср/ -

хеЕ*'

хе¥2»'

Срс/ — <

X

Сс С/

>

(1.5)

\

По построению (Ч)ЕП МПП кодов, множества слов Со, Сс, С/, Ср, Срс являются кодами. Множества Ср/ и Срс/ будут являться кодами только в том случае, если матрицы

Сжр

и Сс Vе//

имеют полный ранг, а для Срс/ дополнительно требуется выполнение условия и' + К' < п. Для выбранных блочных МПП кодов при построении проверочной матрицы (1.2) при Ь —> оо с вероятностью р —> 1 порождающие матрицы кодов Ср/ и Срс/ будут иметь полный ранг, а при условии V + К < п так же выполняется и г/7 + К' < п. Таким образом, большинство кодов из ансамбля удовлетворяют этим требованиям и для них множества (1.5) являются кодами. Дальнейший анализ и все полученные результаты верны только для таких, типичных, кодов из ансамбля.

Лемма 1.1, 5 ансамбле £рит К, г^) (Ч)ЕП МПП кодов, К + ь> < N, кодовые слова, пороэюденные информационными последовательностями и £ и,п без нулевых блоков внутри имеют п или п + 1 ненулевых кодовых блоков.

Лемма 1.2. Кодовая последовательность (Ч)ЕПП МПП кода из ансамбля Ерит {И, К, и), полученная при кодировании информационной последовательности

... О 0 и£+1 ... 0 0... из где и, = (иг;о 141), может иметь

вес, равный активному расстоянию сГ^, только в том случае, если

иг,о ф о, ф О при £ < г < ] - 1, и^_1>0 ф О.

Лемма 1.3. Активные расстояния кодов из ансамбля £рит (Ч)ЕП МПП кодов, К+и < N, и < К удовлетворяют следующим условиям:

> шш {(I (Сс), й (Со) + Л (Ср)), ^ > Л (С0) + тт (й (Срс), о? (Срс/) + & (Ср)), Л) > + и - 2)(1 (Срс/), где й (Сг-) - минимальный вес кода С{.

Докажем утверждение лемм рассмотрением всех возможных случаев.

Исследуем результаты произведения (1.4) при ] = 1, 2,____

1 3 = 1

Пусть и = [..., 0, и^ О, ...], где = (и^0 ии), и^ ф 0. Распишем результаты произведения (1.4):

V = [..., О, V*, О, ...],

= и^хвр.

Для случайного ненулевого информационного блока иг = (и^0 возможны 3 случая.

1. На входе:

щ,0 ф 0, и^д = О.

На выходе:

\ъ = и^0Сс,

V**1 = 0.

Блок и хэммингов вес кодовой последовательности

^ {уь уж)>й(Сс).

2. На входе:

± о, им ф О.

На выходе:

vt = и^о Сс + игдС/,

Блоки ^ Е Со, Vt+l Е Ср и вес кодовой последовательности (у4 у4+1) > (I (С0) + (Ср).

3. На входе:

и»,о = 0, ф 0.

На выходе:

ví = имС/?

Vf.fi = и^дСр.

Блоки 6 С/, Уг+1 € Ср, результирующий вес wt(ví ум)>(1 (С/) + й{Ср).

Активное расстояние <1\ соответствует минимальному весу рассмотренных выше кодовых последовательностей. Пусть при равной длине кодов, коды с меньшей скоростью имеют большее кодовое расстояние. В асимптотическом случае, лучшие блоковые МПП коды могут лежать сколь угодно близко к границе Варшамова-Гилберта и для них данное предположение выполняется. Тогда (I (Со) < ¿(С/) и минимальный возможный вес в случае 2 меньше, чем в случае 3. Сравним случаи 1 и 2. Кодовое расстояние (1{Сс) больше (¿(Со). Однако с£(Сс) может быть меньше суммы с£(Со) + б,(Ср). Последняя определяется отношением между К' и у'. Так, если К' — и' > и', то ё,(Сс) < й(Ср) и (Гг = с1 {Сс). Таким образом,

= гшп (<* (сс), ё (Со) + а (ср)).

и 3 = 2

Пусть информационная последовательность и состоит из 2 последовательных ненулевых блоков и = [..., 0, и^ щ+1, 0, ...], где и* = (и^о игд), г = ¿,¿4-1. Исследуем все возможные кодовые последовательности, порождаемые информационной последовательностью такого вида. Из уравнения (1.4):

V = [. .., О, V*, ^+1, у<+2, 0, ...],

ут = и^двр + щ+1$Ос + и^хдС/, У(+2 = и4+1дСр.

Рассмотрим возможные случаи.

1. На входе:

и^о ф 0, = 0, блок щ+1 произвольный ненулевой. На выходе:

V* = и(;0Сс, У(+х = и4+1)0Сс + и4+1дС/, У<+2 = и£+1ДСр.

Получаем, У£ 6 сс, а блоки Уг+1, у*+2 соответствуют кодовым блокам, рассмотренным в случае п = 1. Таким образом,

ум; (у( у<+1 у 1+2) > <1 (сс) + ¿\.

2. На входе:

и*)0 ф о, им ф 0, иг+1)0 ф 0, иг-ид = 0.

На выходе:

у* = и*>0Сс + имС/,

= игдСр 4- иг+^оСс, = 0.

Блок £ Срс и у;+1 ф 0, так как порождающий его информационный блок ненулевой: и*д ф 0, иг+х,о ф 0. Получаем, V* £ Со, Уг+х £ Срс и wt (у* уш 0) > (I (С0) + й (С^).

3. На входе:

и*,о ф 0, игд ф 0, и^о = 0, иШд ф О

На выходе:

V* = и4>0Сс + имС/, Ví+l = и^Ср+ Уг+2 = и4+1дСр. Блок ф 0. Получаем, у4 £ Со, £ Ср/, у<+2 £ Ср и ^ (у* уш ут) > <1 (С0) + с? (Ср/) + й (Ср).

4. На входе:

Щ,о Ф О, Щ,1 Ф 0, иг+1,0 ф 0, иШд ф 0.

На выходе:

у* = и^оСс + и^С/, Ví+l = и^дСр + и^1,оСс + и<+1дС/, Уг+2 = и^хдСр.

Получаем, у< £ Со, у*+х 6 Срс/, Уг+2 £ Срб Уг+1 ф 0. Вес кодовой последовательности wt (у* у^х у*+г) > ^ (Со) + ^ (СрС/) + ^ (Ср).

5. На входе:

и{)0 = 0, и4д ф О, ненулевой щ+1.

В зависимости от и$+х, этот случай будет покрываться случаями 2-4 с тем исключением, что ^ Со, V* £ С/. Так как ¿(С/) > ¿(Со), то вес получившейся последовательности будет всегда больше, чем в случаях 2-4.

Определим минимальный вес среди возможных случаев. Сравним случаи 3 и 4:

d (Со) + d (Cpf) + d (Ср) > d (Со) + d (CpCf) 4- d (Cp),

так как d (Cpf) > d (Cpcf): dim (Cpf) = 2i/, dim (Cpcf) = К'+i/, a 2v' < K'+i/. Сравним случаи 1 и 2:

d (Сс) + min (d (Cc), d (Co) + d (Cp)) > d (Co) + d (Cpc),

так как d (Cc) > d (Cpc), d (Cc) > d (Co), a min (if (Cc), d (Co) + d (Cp)) больше d (Co) в любом случае. Сравним случаи 4 и 2:

d (Со) + d (CpCf) + d (Ср) V d (Со) + d (Cpc).

Вес d (CpC) > d(Cpcf)\ dim (Cpc) = K', dim (Cpcf) = K'-hv'. Однако вес d(Cpc) может оказаться как меньше, так и больше суммарного веса d (Cpcf) + d (Ср). Таким образом,

dr2 = d (Со) + min (d (Cpc), d (CPcf) + d (Cp)).

III j = 3

Пусть информационная последовательность u состоит из 3 последовательных ненулевых блоков и = [..., 0, ut, иш, ui+2, 0, ...], где иг- = (иг;0 иг-д), г = t, ¿4-1, t+2. Исследуем все возможные кодовые последовательности, порождаемые информационной последовательностью такого вида. Из уравнения (1.4):

V = [..., О, V*, vi+b vt+2, vi+3, 0, ...], vt = ut)oGc + uifiG/, vi+i = u^iGp + ui+lioGc 4-Uf+ijG/, Vi+2 = Ui+ijGp + Ui+2,oGc + U(+2,lG/, Vf+3 = Ui+2,lGp. Рассмотрим основные случаи.

1. На входе:

и^о ф 0, = 0, произвольные

На выходе:

V* = щ)0Сс,

Ví+l = и^^овс + и4+1дС/,

У4+2 = иг+1дСр + +

Ví+3 = Щ+2,1&р-

Блок V; 6 Сс, В зависимости от распределения нулевых частей в и*+1

и щ+2 кодовые блоки vt+2, относятся к кодам и случаям,

УЧ

рассмотренным при изучении <1\. Вес кодовой последовательности (ví V1+2 > Л (Сс) + ¿г2.

2. На входе:

и4>0 ф о, и4>1 ф 0, щ+1$ ф о, щ+1,1 = 0, ненулевой щ+2. На выходе:

У( = и^Се + ^дС/, = ЩдСр + и^^оСс, У<+2 = и«+2,оСс + и^гдС/, У4+з = 11*+2дСр.

Блоки € Со, £ срс, а блоки у4+2, ^ь+з соответствуют случаям, рассмотренным при анализе Вес последовательности ыЬ (у< у<+1 у<+2 v¿+з) > с1 (Со) 4- в, (СРс) + Далее мы опустим случай отличающийся только тем, что и^о = 0. Результат будет аналогичным, за исключением V* £ Сс, а это увеличит вес.

3. На входе:

и^о ф 0, ф 0, щ+1,о Ф 0, и^хд ф 0, ненулевой и^о-

22

На выходе:

Уг = \itflGc + и^в/, Ví+l = и^дСр-Ь иг+1,0Сс + и<+1дС/,

У£+2 = и4+1дСр + и^2,оСс + 114+2,1 в/,

Ví+3 = и;+2дСр.

Блоки у^ е Со, у*+1 6 Срс/? а блоки у*+2, Уг+з соответствуют случаям

А

2-4 анализа Вес последовательности

(уг Уг+1 У*+2 ^+3) > й [Со)+<1 (Срс/) + шш (д. (Срс) , (1 (Срс/) + с2 (Ср)).

Из рассмотрения опущены случаи, когда и^о = 0, и^д Ф 0 или и^+^о = О, и<+1д ф 0. Они дают результаты, похожие на результаты в случаях 2 или 3, но с большим весом. Определим минимальный вес среди возможных случаев. Вычтем общие части и сравним случаи 1 и 3:

л (сс) > а (Срс/).

Вычтем общие части и сравним случаи 2 и 3:

(1 (Срс)+тт (й (Сс), <1 (Со) + б. (Ср)) > <Х (Срс/)+тт (б. (Срс/), <1 (Срс) + б (Ср)). Получаем,

= <г2 +б (срс/).

Продолжая анализ, можно показать, что начиная с = 2, активные строчные расстояния растут по закону

^>4 + 0'-2 щсрс/)

с уклоном

а = (I (Срс/). 23

Таким образом, утверждения лемм 1-3 справедливы. Отметим, что при полной памяти один ненулевой блок всегда порождает два ненулевых кодовых блока. Таким образом, при и = К, активное расстояние с1\ = (¿(Со) + с2(Ср), а <Г2 = & (Со) + й (С,*/) + (1 (Ср).

1.4. Асимптотическая оценка кодовых расстояний сверточных МПП кодов с единичной памятью'

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

В результате проведенного в параграфе 1.3 анализа показано, что кодовые последовательности кодов из ансамбля (Ч)ЕП МПП кодов с весами, равными активным расстояниям с^, состоят из з (возможно только для ЧЕП кодов) или 3 + 1 идущих подряд ненулевых блоков. В соответствии с проверочной матрицей (1.2) каждая пара соседних блоков должна удовлетворять системе рекуррентных линейных уравнений

' нс(г -1)^ = о < п^и + нр(*кт = о н = О

\

Дополнительно, первый ненулевой и последний ненулевой блоки должны удовлетворять условиям

Нр(0)у£ = О, Н/0>7 = 0.

Уравнение

Н/фу^+Нр^^О

описывает проверочную матрицу

[Н/(0 нр(0]

(1.6)

и отвечает за память сверточного кода. В соответствии с леммами 1.1 - 1.3, память между кодовыми блоками не обнуляется и при проверках кодовых блоков матрицами Н/(£) и Нр(£) возникают совпадающие синдромы:

где Э - некоторый синдром. Частный случай блочных МПП кодов с проверочной матрицей вида (1.6) был исследован Ф. Хугом, В. Зябловым и Р. Йоханнесеном в работе [39]. В данном случае, при расчете минимального веса двух последовательных кодовых блоков необходимо анализировать проверочную матрицу следующего вида:

В зависимости от расположения пары кодовых блоков внутри кодовой последовательности, матрицы Нг будут меняться. Например, при расчете веса с£ (Со) + с1 (Ср) для активного расстояния матрица

Н/ЙУ?_1 = в, нр(*кт = в,

Н2

Нз

Н4

матрицы Н2 = Н/(* + 1) , Н3 = Нр(£ + 1) и

^ НУ(4 + 2) )

В общем случае, пусть матрицы Н^, 1 < г < 4 принадлежат ансамблям £ (по,£{,Ь) МПП кодов, = ^з- Пусть представленная блочная матрица принадлежит ансамблю £сн. Оценим кодовое расстояние в ансамбле £с}г.

Воспользуемся методом Галлагера [13]. Пусть А^л(^) ~ среднее число

кодовых слов веса У/ в ансамбле Тогда, до тех пор пока ^^(У/) < 1,

iv—2

в ансамбле найдется хотя бы один код с минимальным расстоянием (1сн > 1Уо.

Выразим среднее число кодовых слов заданного веса в ансамбле £сь через вероятность Р (У/) случайного слова г = (Г12 Г34) веса У/ оказаться кодовым в ансамбле:

№) =

Для произвольного кода из ансамбля £с/г, слово г будет кодовым, если выполняется система

Н1Г12 = о

< Н2г£ + Н3Г£ = 0 • (1.7)

Н4Г34 = О

V

Совместность системы (1.7) зависит от распределения веса У/ по блокам г12 и Г34, при этом слова г 12 и Г34 должны принадлежать кодам с проверочными матрицами Нх и Н4 из ансамблей £ (щ, Ь) и £ (по, £4, &), соответственно, а синдромы Нгг^ = 812, Н3Г34 = 834 должны совпадать. Распределение веса У/ между словами может быть различно, поэтому необходимо найти случай с наибольшей вероятностью.

Пусть А^-(Ж) - среднее число кодовых слов веса УУ в ансамбле МПП кодов £ (по, 6), а Рг(8^|ж) - вероятность получить для слова веса х синдром в ансамбле кодов £ (по, Ь). Среднее число кодовых пар с заданными весами

и \¥з4 в ансамблях £ (по,^ь&) и £ (щ,£4,Ь) оценивается произведением -^1(1^12)N4(1^34)• Вероятность в зависимости от веса получить совпадающие синдромы для ансамблей £ (по,^г,Ь) и £ (по,^з,Ь) можно описать суммой по всем возможным синдромам:

Таким образом, слово веса IV окажется кодовым в ансамбле £сь с вероятностью

Утверждение!.. Наибольшая вероятность случайного слова r = (г12 1*34) ^eca W и длины 2п оказаться кодовым в ансамбле £ch в зависимости от распределения веса между частями Т\2 и Г34 достигается при wt(v12) = wt(v12) = W/2. Докажем утверждение 1.

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

Литература

1. Bahl L. R., Cocke J., Jelinek F., Raviv J. Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate // IEEE TVans. Inform. Theory. 1974. Vol. IT-20. P. 284-287.

2. Berrou C., Glavieux A. Near Optimum Error-Correcting Coding and Decoding: Turbo Codes // IEEE Transactions on Communications. 1996. — Oct. Vol. COM-44. P. 1261-1271.

3. Costello D. J., Jr. A Construction Technique for Random Error-Correcting Convolutional Codes // IEEE Transactions on Information Theory. 1969. — Sept. Vol. IT-19. P. 631-636.

4. Costello D. J., Jr. Free Distance Bounds for Convolutional Codes // IEEE Transactions on Information Theory. 1974. — July. Vol. IT-20. P. 356-365.

5. Dettmar U., Shavgulidze S. New Optimal Partial Unit Memory Codes // Electronic Letters. 1992.-August. Vol. 28. P. 1748-1749.

6. Dettmar U., Sorger U. New optimal partial unit memory codes based on extended BCH codes // Electronic Letters. 1993. Vol. 29, no. 23. P. 2024-2025.

7. Divsalar D., Jones C., Dolinar S., Thorpe J. Protograph based LDPC codes with minimum distance linearly growing with block size // IEEE Global Telecommunications Conference (GLOBECOM). Vol. 3. 2005. —nov.-2 dec. P. 5.

8. Engdahl K., Lentmaier M., Zigangirov K. Sh. On the Theory of Low-Density Convolutional Codes // Lecture Notes in Computer Science (AAECC-13). 1999. - Springer-Verlag, New York. Vol. 1719. P. 77-86.

9. Engdahl K., Zigangirov K. Sh. On the Theory of Low-Density Convolutional Codes I // Problemy Peredachi Informatsii. 1999. Vol. 35. P. 12-27.

10. Feltstrôm Alberto Jimenez, Truhachev Dmitri, Lentmaier Michael, Zigangirov Kamil Sh. Braided block codes // IEEE Trans. Inf. Theor. 2009.. Vol. 55, no. 6. P. 2640-2658. URL: http://dx.doi.org/10.1109/TIT. 2009.2018350.

11. Forney G. D., Jr. The Viterbi Algorithm // Proceedings of the IEEE. 1973. — Mar. Vol. 61. P. 268-278.

12. Fossorier Marc P. C. Quasi-Cyclic Low-Density Parity-Check Codes From Circulant Permutation Matrices // IEEE Transactions on Information Theory. 2004. Vol. 50, no. 8. P. 1788-1793.

13. Gallager Robert G. Low-Density Parity-Check Codes. The MIT Press, 1972. URL: http : //www. worldcat. org/isbn/0262160390.

14. Hall M., Jr. The Theory of Groups. New York: Chelsea, 2nd edition, 1996.

15. Jiménez Feltstrôm A. Soft Iterative Decoding of Low-Density Convolutional Codes. Licentiate Thesis. 1997. Lund University, Sweden.

16. Jiménez Feltstrôm A., Zigangirov K. Sh. Periodic Time-Varying Convolutional Codes with Low-Density Parity-Check Matrices // IEEE Transactions on Information Theory. 1999.-Sept. Vol. IT-45, no. 5. P. 2181-2190.

17. Johnson Sarah J., Weller Steven R. Regular low-density parity-check codes from combinatorial designs // 2001 IEEE Information Theory Workshop (ITW'2001), Cairns. 2001.-sep.

18. Jordan R., Pavlushkov V., Zyablov V.V. Maximum slope convolutional

codes // Information Theory, IEEE Transactions on. 2004. —oct. Vol. 50, no. 10. P. 2511 - 2526.

19. Kondrashov K., Zyablov V. On the lower bound of the free distance of partial unit memory codes based on LDPC Codes // ISIT. 2011. P. 1831-1835.

20. Kondrashov Konstantin, Zyablov Victor V. On the lower bound of the free distance of partial unit memory codes based on LDPC Codes // ISIT. 2011. P. 1831-1835.

21. Kou Yu, Lin Shu, Fossorier Marc P. C. Low density parity check codes based on finite geometries: A rediscovery and new results // IEEE Trans. Inform. Theory. 2001. Vol. 47. P. 2711-2736.

22. Lauer Gregory S. Some Optimal Partial-Unit Memory Codes // IEEE Transactions on Information Theory. 1979. — March. Vol. 23, no. 2. P. 240-243.

23. Lee Lin-Nan. Short Unit-Memory Byte-Oriented Binary Convolutional Codes Having Maximal Free Distance // IEEE Transactions on Information Theory. 1976. - May. P. 349-352.

24. Lentmaier M. Towards a Theory of Codes for Iterative Decoding: Ph. D. thesis / Lund University, Sweden. 2003.

25. Lentmaier M., Truhachev D. V., Zigangirov K. Sh. To the Theory of Low-Density Convolutional Codes. II // Probl. Inf. Transm. 2001. — . Vol. 37, no. 4. P. 288-306. URL: http://dx.doi.Org/10.1023/A:1013815115684.

26. Lentmaier M., Zigangirov K. Sh. Iterative Decoding of Generalized Low-Density Parity-Check Codes // Proc. IEEE International Symposium on Information Theory. Boston, USA: 1998.— Aug. P. 149.

27. Lentmaier M., Zigangirov K. Sh. On Generalized Low-Density Parity-Check Codes Based on Hamming Component Codes // IEEE Communications Letters. 1999.-Aug. Vol. 3, no. 8. P. 248-250.

28. Pusane Ali Emre, Feltstrom Alberto Jimr(c)nez, Sridharan Arvind et al. Implementation aspects of LDPC convolutional codes. // IEEE Transactions on Communications. 2008. Vol. 56, no. 7. P. 1060-1069.

29. Tanner Robert Michael. A recursive approach to low complexity codes // IEEE Transactions on Information Theory. 1981. Vol. 27, no. 5. P. 533-547.

30. Tanner R. M. A Recursive Approach to Low Complexity Codes // IEEE Transactions on Information Theory. 1981. —Sept. Vol. IT-27, no. 9. P. 533-547.

31. Tavares Marcos B. S., Dresden Technische UniversitFnt, Zigangirov Kamil Sh. et al. Tail-Biting LDPC Convolutional Codes.

32. Tavares Marcos B. S., Zigangirov Kamil Sh., Fettweis Gerhard. Tail-Biting LDPC Convolutional Codes Based on Protographs // VTC Fall. 2007. P. 1047-1051.

33. Thommesen Christian, Justesen J0rn. Bounds on distances and error exponents of unit memory codes // IEEE Transactions on Information Theory. 1983. Vol. 29, no. 5. P. 637-649.

34. Truhachev D. V., Lentmaier M., Zigangirov K. Sh. Mathematical Analysis of Iterative Decoding of LDPC Convolutional Codes // Proc. IEEE International Symposium on Information Theory. Washington, USA: 2001. —July. P. 191.

35. Truhachev D. V., Lentmaier M., Zigangirov K. Sh. On Braided Block Codes.

Submitted to IEEE International Symposium on Information Theory, Yokohama. 2003. —July.

36. Truhachev D. V., Lentmaier M., Zigangirov K. Sh. On Braided Block Codes // Proc. IEEE International Symposium on Information Theory. Yokohama, Japan: 2003. - June. P. 32.

37. Zhang Wei, Lentmaier Michael, Zigangirov Kamil, Daniel J. Jr. Costello. Braided Convolutional Codes: A New Class of Turbo-Like Codes // IEEE Transactions on Information Theory. 2010. Vol. 56, no. 1. P. 316-331. URL: http ://lup.lub.lu.se/record/1533672/file/3731661.pdf.

38. Zigangirov K. Sh., Lentmaier M. On the Asymptotic Iterative Decoding Performance of Low-Density Parity-Check Codes // International Symposium on Turbo Codes. Brest, France: 2000.-Sept. P. 39-42.

39. Zyablov Victor, Hug Florian, Johannesson Rolf.' Chained Gallager codes. 2009. URL: http : //lup. lub. lu. se/record/1369522/f ile/1593308. pdf.

40. Zyablov Victor, Hug Florian, Johannesson Rolf. Chained Gallager codes. 2009. URL: http : //lup. lub. lu. se/record/1369522/f ile/1593308. pdf.

41. Zyablov V., Sidorenko V. On Periodic (Partial) Unit Memory Codes with Maximum Free Distance // Error Control, Cryptoplogy, and Speech Compression. 1994. Vol. 829 of Lecture Notes in Computer Science. P. 74-79.

42. Zyablov V. V., Kondrashov K. A., Skopintsev O. D. On the Active Distances of Partial Unit Memory Codes Based on LDPC Codes // Journal of Communications Technology and Electronics,. 2013. P. 636-647.

43. Зяблов B.B, Кондратов К.А. Декодирование Q-ных плетеных

сверточных МПП-кодов // Информационные технологии и системы (ИТиС), Геленджик, Россия. 2010. Р. 85 -88.

44. Зяблов В.В, Кондратов К.А. Граница свободного расстояния случайных кодов с (частично) единичной памятью // Информационные технологии и системы (ИТиС), Геленджик, Россия. 2011. Р. 53 -60.

45. Зяблов В.В, Кондратов К.А., Скопинцев О.Д. Оценка активных расстояний сверточных кодов (частично) единичной памяти с малой плотностью проверок // Информационные процессы. 2012. Р. 372 -388.

46. Зяблов В. В, Кондратов К.А. Конструкция плетеных сверточных кодов на базе кодов проверки на четность с одним проверочным символом // Информационно-управляющие системы. 2011. Р. 156 -159.