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

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

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

005534837

Кондратов Константин Александрович

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

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

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

1 О С!<Т 2013

Москва - 2013

005534837

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

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

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

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

доктор технических наук, старший научный сотрудник. ИППИ РАН. главный научный сотрудник лаборатории №1 Владимиров Сергей Михайлович, кандидат физико-математических наук. инженер программист в ООО "Одноклассники"

Санкт-Петербургский государственный университет аэрокосмического приборостроения

,30 % 9ШЯГ ,/5-'

_оо

Защита состоится и'-гпаоро 2013 г. в '2._часов на заседании

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

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

Автореферат разослан 2013 г.

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

диссертационного совета Д 212.156.04 кандидат физико-математических наук

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

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

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

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

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

струкций, теоретическом и практическом исследовании их корректирующих свойств.

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

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

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

• Разработан класс 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 статьи в рецензируемых журналах [2, 5, 6], 3 статьи в сборниках конференций [1,3,4].

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

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

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

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

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

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

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

Н* =

/Н0 О

О

Но

\

\ О о

Но/

ЬхЬпо

Каждый подобный блок определяет "слой" проверочной матрицы МПП кода и состоит из Ь непересекающихся проверок на четность длины щ'

Но=(1 1 ... 1).

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

Н

ЬВРС ;

( (Н*) \ ТГ2 (Н*)

\ щ (н*) )

(1)

еьхЬчо

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

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

Си

Со Сх

однако в случае блоковых МПП кодов Галлагера сверточные коды приходится также описывать с помощью проверочной, а не порождающей матрицы. В общем случае, проверочная матрица ЕП кода в зависимости от скорости может иметь память больше единицы. В целях упрощения анализа, память проверочной матрицы предлагаемых ЕП-МПП кодов зафиксирована на всех скоростях и равна единице. Это накладывает ограничение на полную/частичную память: и < К, и + К < А", где N - длина базового МПП кода Галлагера, а К - его размерность. Параметр и определяет длину кодового ограничения. При соблюдении требований на единичную или частично единичную (в зависимости от скорости) память, проверочная матрица ЕП-МПП кода имеет вид:

(3)

где подматрицы Нр, Ну имеют размер V х Л" и выбираются независимо из ансамбля £ (по, и/Ь, Ь) блочных МПП кодов Галлагера, а подматрицы Нс имеют размер (И — К — и) х N н выбираются из ансамбля £ (по, (Ы — К — 1>)!Ъ, Ь) блочных МПП кодов Галлагера.

Определение 1. Ансамбль £;„,т(Лг, К, и) (Ч)ЕП-МПП-кодов, и < К, V + К < ЛГ, состоит из проверочных матриц вида (3), полученных независимым случайным равновероятным выбором подматриц Нр, Нс, Н/ из соответствующих ансамблей блочных МГШ-кодов Галлагера.

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

... О 0 иь иш ... и^-х 0 0...,

где и£ ф О при Ь < г < 1+]. Обозначим множество таких последовательностей как В общем случае можно считать память ЕП МПП кода неполной и

НР Нс

Н; Нр Нс

н, Нр

нс ••• Н/ ■

переписать порождающую матрицу G виде:

Gc Gf

Gc G}

Gp Gc Gf

где

G0l а

U)-

Gi. Обозначим блоковые коды, описываемые

сг )

порождающими матрицами Сс, С/, как Ср, Сс и С/. Обозначим блоковые коды, описываемые комбинированными порождающими матрицами

Gc

G„

как Со, Ccf, Cpf и Cpcf, соответственно. В соответствии с порождающей ма-рицей, каждый информационный блок иг может быть разбит на две части, Ui = (u,-,o Uj i), которые не могут быть одновременно нулевыми. Каждый кодовый блок внутри кодовой последовательности принадлежит одному из определенных выше блоковых кодов. Рассмотрение получаемых кодовых последовательностей в зависимости от всех возможных информационных последовательностей и, и Е It.j, позволяет сформулировать следующие леммы:

JI е м м а 1. В ансамбле Spum (N, К, v) (Ч)ЕП МПП-кодов, К + и < N, кодовые слова, порожденные информационными последовательностями и 6 1(>п без нулевых блоков внутри имеют п или п + 1 ненулевых кодовых блоков.

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

... О 0 ut ut+i ... u(+j_i 0 0 ... из Itj, где Uj = (u^o u^i), может иметь вес, равный активному расстоянию dp только в том случае, если

иг,0 ф 0, им ф О при t < i < j - 1,

u,

i,o + 0.

Л e

м м а 3. Активные расстояния кодов из ансамбля Spum (N,K,v)

(Ч)ЕП МПП-кодов. K+v < N,v < К удовлетворяют следующим условиям:

d\ > min (d (Сс), d (Со) + d (Ср)), Ü > d (Co) + min (d (Cpc), d (Cpcf) + d (Cp)), d)>d\ + {3-2)d(CpcJ),

где d(Ci) - минимальный вес кода С*.

Кодовые расстояния d, (С;) МПП кодов, выраженных через порождающие матрицы, неизвестны. Дальнейший анализ выполняется через проверочные матрицы.

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

нр

Нс

Н/ Нр

Не

Н/

как проверочную матрицу блокового кода МПП. Перепишем проверочную матрицу блокового кода в общем виде:

Н,

Н2 Нз

н.

Обозначим коды с проверочной матрицей такого вида, где подблоки выбираются из ансамблей £ (щ, £{, b), г = 1,... 4, (Л = Рц, ¿2 — ¿з, МПП кодов Галлагера, ансамблем £гд. Асимптотическую оценку кодового расстояния по ансамблю £с/, можно получить методом Галлагера.

Пусть Nch(\V) среднее число кодовых слов веса W в ансамбле £rh- В ансамбле найдется хотя бы один код с минимальным расстоянием dch > Wq, Wo

если Nch(W) < 1. Сформулируем следующую теорему:

Теорема 1. Если существует положительный корень 5q уравнения

£ log _ se log Ш + ш, log {доШ) _ 2Я(|)(, _ !)

относительно переменной 5, то в ансамбле Ь) существуют ко-

ды с относительным расстоянием больше <5ц.

Доказательство. Выразим среднее число кодовых слов заданного веса в ансамбле £с;1 через вероятность Р (И") случайного слова г = (г12 Г34) веса IV оказаться кодовым в ансамбле:

л^ио =

Пусть среднее число кодовых слов веса IV в ансамбле МПП-кодов

£ (по, ¿и Ь), а вероятность получить для слова веса х синдром в

ансамбле кодов £ (щ, Ъ). Среднее число кодовых пар с заданными весами ]¥п и в ансамблях £{п0^ъЬ) и £ (щ, Ь) оценивается произведением Вероятность в зависимости от веса получить совпадающие синдромы для ансамблей £ (щ, ¿2, Ь) и £ (п0, £3, Ь) можно описать суммой по всем возможным синдромам:

в.

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

Е ( ЩуШЖ - у) Е Р2(8Лу)Р3(Я№ - у))

Р (ИО = ^-^-^ (5)

Наибольшая вероятность случайного слова г = (Г12 Г34) веса IV и длины 2п оказаться кодовым в ансамбле £¿¡1 в зависимости от распределения веса между частями гп и Г34 достигается при '^(ухг) = = \¥/2.

Оценив сумму в 5 наибольшим членом и взяв значение в точке у = получим

(и__^2по + и + -«я-УЛ*6 и

\2bno-W) Ц1 2Ъпа-К) + } [»» ^Йло-^]

( п \2<-2 '

иУ/2/

Таким образом,

Р(Щ <

*** щ-" ((' - +11+^г)" I- шг**

/2п\ ( п \2f-2 иу/ \WI2I

и среднее число кодовых слов Л^/ДИ7) = (^,Г;)Р(И') веса 1К в ансамбле £,./, ограничено сверху:

(IV) <

^Щ"" ((' - + ('+ ^ГГ

( п \2<-2 \WI2l

(6)

1Г=2 га

До тех пор, пока ^ -^(И') < 1, в ансамбле найдется хотя бы один код

И"=2

с минимальным расстоянием йсь > Пусть 5 - относительное расстояние, <5 = тогда асимптотическая оценка относительного кодового расстояния может быть получена из условия

/2-«Чп,И)» (¿Г*»" ((1 - + (1 + [до

22т0нф(е-1) ~ "

log

т =

ь ье ^Г^Г^ _ 1ой (_£.) + ^ 1об _ 2Нф{е _ 1). ▲

Асимптотическая граница свободного расстояния ЕП МПП кодов с полной памятью на скоростях до Я = 0.5 и максимально допустимой частичной памятью при скоростях выше, следует из лемм 1 -3 и теоремы 1. Граница ЕП МПП кодов представлена на рис. 1 вместе с границами Костелло и Томме-сена-Юстесена для сверточных кодов и границей Ва.ршамова-Гилберта для блоковых кодов. В случае полной памяти асимптотическая граница свободного расстояния ЕП МПП кодов совпадает с границей Томмесена-Юстесена для случайных ЕП кодов.

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

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

Рис. 1. Асимптотические границы относительного свободного расстояния. СУ граница Варшамова-Гилберта, Соз1е11о - граница Костелло, ИМ - граница Томмесела-Юстесена для кодов с полной единичной памятью, (Р)11М 1Л5РС - граница свободного расстояния для кодов с (частично)единичной памятью, полученных из блочных МПП-кодов.

узлом ь'п. Пусть кодовое слово блокового (И, £, щ) МПП кода V = (г^из... у^) передается по АБГШ каналу и пусть г = (Г1Г2 ... гдт) означает принятую последовательность.

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

Р (и„ = 0|г) (7)

для кодовых символов уп, п— 1.2...., N.

Операции, производимые декодером распространения доверия на ]-ош шаге, j — 1, 2,...,/, могут быть разделены на две фазы. В первой фазе проверочные узлы получают сообщения от смежных с ними символьных узлов и, используя полученную информацию, формируют новое сообщение. Во второй фазе проверочные узлы посылают вновь сформированные сообщения смежным с ними символьным узлам, а те, в свою очередь, формируют новые сообщения, которые будут посланы ими на первой фазе следующего шага итеративного процесса декодирования.

Опишем г-ый, г = 1,2,...,/— 1 шаг итеративного процесса декодирования. Во время первой фазы г-ой итерации п-ый символьный узел посылает сообщение г^1', которое было вычислено им на предыдущем шаге, смежному проверочному узлу г 6 С(п). Затем г-ый проверочный узел, г = 1,2,..., £Ь,

получивший по сообщений г^ п € Л/*(г), от смежных символьных узлов, вычисляет статистики у^, п € А/*(г),

Во время второй фазы г-ого итеративного процесса декодирования, г = 1,2,...,/ — 1, г-ый проверочный узел, г, г = 1,2,..., £Ь, посылает сообщение Уы гс-ому символьному узлу, п £ Л/*(г). Затем п-ый символьный узел вычисляет статистики

/<) = 2(0)+ „(О

711 ^п ' / у У<'п

¿'б£(п)\{«}

>'б£(п)\{;} 1 ~~ ПП'елг(|')\{П} /2)

которые данный символьный узел будет рассылать как сообщения на следующем шаге итеративного процесса. Этим завершается вторая фаза г-го шага процесса итеративного декодирования, г = 1, 2,...,/— 1.

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

В § 2.3 рассмотрено декодирование терминированных методом циклического замыкания хвоста последовательностей ЕП-МПП кодов. Проведено имитационное моделирование для различных выборов параметров кодов.

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

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

В § 3.1 Описана конструкция 4-плетеных сверточных МПП кодов и несколько способов их кодирования. 4-ПСМПП код получается 'плетением' четырех кодов-компонентов - горизонтального, вертикального, и двух - диагональ-пых. 4-ПСМПП код имеет следующую структуру:

О)

Л I

1

>Н 2

1

«М -1

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

В произвольный момент времени для получения на выходе закодированного блока VI на первом шаге кодируются вертикальный и диагональные коды-компоненты. Затем информационный блок щи полученные проверочные символы кодируются горизонтальным кодом-компонентом. Конструкцию 4-плетеных сверточных кодов можно рассматривать, как развитие идеи 2-плетеных сверточных кодов К.Ш. Зигангирова.

Кодирование П-СМПП-кодов может выполняться несколькими способами. Один из алгоритмов кодирования сверточного МПП-кода следует напрямую из рекуррентного уравнения кодовой последовательности сверточных кодов. Пусть, без потери общности, символы информационного блока гн стоят на первых Ь позициях кодового блока и*. Пусть г\ = \у[\иП^\ , = щ и Н/а состоит из первых Ъ строк матрицы Щ (¿), а из оставшихся с — Ь.

Напомним, что подматрица Щ (£), Ь 6 N имеет полный ранг с — Ь. Тогда проверочные символы кодового блока г>( являются единственным решением системы линейных уравнений

-ущн»? (г) = И|Я/Т(«) + + • • • + т*-т.Я£.(«) •

В аппаратной реализации такого кодирования можно использовать сдвиговые регистры. Объем памяти, необходимый для хранения символов из поля, составляет с ■ т$ + Ь ячеек. Сложность кодирования линейна относительно длины N П-С-МПП-кода.

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

= [0[о,4-1]|в4], (ю)

где = ^, ... - вектор частичных синдромов. На. самом деле,

вектор частичных синдромов - это не что иное как состояние кодера сг( в момент времени £. Вектор частичных синдромов вычисляется рекуррентно в соответствии со следующим правилом:

_ Г + + » = 1,...,т,-1 ( ,

гн-1Й*,(1 + т,-1), г = гп3. ^ 1

Кодовый блок Уг = , у[ = щ находится из решения

Необходимый объем памяти в этом случае составляет (с — Ь) ■ тп8 q-ных ячеек, что меньше, чем при первом алгоритме. При этом вычислительная сложность остается такой же. При аппаратной реализации для вычисления частичных синдромов можно использовать сдвиговый регистр.

Для построения ансамбля сверточных плетеных МПП кодов, коды представляются в виде графа Таннера, к которому затем применяется "расширение". Для построения ансамбля П-СМПП-кодов <Е(Ь), используются, выбираемые равновероятно, случайные матрицы перестановок Р размера Ь х Ь. Применяя к графу Таннера В операцию "копирование с перестановками": Кз = Кз^ч' каждому ребру графа В ставится в соответствие матрица перестановки, все узлы графа копируются Ь раз, а конечные точки ребер переставляются

В § 3.2 комбинаторно исследованы дистанционные свойства кода базовой конструкции. Для нахождения активных расстояний для различных длин ] решается система линейных уравнений = 0, из которой

исключены первые несколько строк, отвечающих нулевым проверочным символам вертикального и диагональных кодов-компонентов в первом кодовом блоке. Система уравнений имеет единственное нулевое решение или множество решений. В последнем случае найденные линейно независимые решения системы образуют фундаментальную систему решений (ФСР), линейная оболочка которой дает все решения. Найдем среди векторов линейной оболочки ФСР ненулевой вектор с минимальным весом. Его вес дает точное значение активного расстояния с^. Результаты вычисления активных расстояний П-СМПП-кодов представлены на рис. 2.

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

1

Рпс. 2. Активные расстояния ПСМПП кодов

В четвертой главе предложены итеративные алгоритмы декодирования. Опишем итеративный алгоритм с жестким принятием решений Л\. Пусть г - принятое из канала слово, содержащее ошибки. На произвольной итерации г, г 6 N на вход декодера подается слово г , где г(0)—г, выходом декодера является слово г(1 | 1). Для декодирования слов, относящихся к определенным кодам-компонентам, используются соответствующие компонентные декодеры

Каждая итерация декодирования состоит из следующих шагов:

Алгоритм Л1 :

1. для каждого кода-компонента с помощью декодера компонента декодируются все соответствующие ему слова из г-М. Результаты запоминаются в г)^;

2. создается слово следующей итерации г('+1), символы которого определяются мажоритарной функцией выбора по большинству из г^'' (в дальнейшем будем называть эту функцию голосованием). Если выбор неоднозначен, то в качестве значения символа г'1+1' выбирается зна-

М

чение соответствующего символа г^ ' из входного слова итерации;

3. вычисляется синдром слова г(1+1'.

В конце каждой итерации в зависимости от значения синдрома и номера итерации возможны четыре исхода:

1. переход к следующей итерации;

2. успех декодирования;

3. ошибка декодирования;

4. отказ от декодирования.

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

Успех декодирования. Успех декодирования происходит в том случае, если синдром выходного слова нулевой и декодированное кодовое слово совпадает с переданным: ¿>(г(,+1)) = 0, = V .

Ошибка декодирования. Происходит при нулевом синдроме, когда принятое слово декодировано в другое кодовое слово, не совпадающее с переданным: г'(г(;+1') = 0, г({+1> ф V.

Отказ от декодирования. Отказ происходит при ненулевом синдроме, если исчерпаны итерации или результирующее слово итерации не отличается от входного слова итерации : ф 0, = г^ V г = /тах.

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

Алгоритм Аг'-

1. для каждого символа т^ входного слова итерации г декодеры кодов-компонентов 2?® вычисляют соответствующие значения, удовлетворяющие проверкам кодов-компонентов. Результаты запоминаются в

2. создается слово следующей итерации символы которого

определяются голосованием по большинству из Если выбор неод-

(¿+1)

нозначен, то на месте символа г^ вводится стирание;

3. стирания в слове исправляются алгоритмом А\ с декодерами кодов-компонентов, исправляющими стирания, до полного устранения;

4. вычисляется синдром слова .

В § 4.2 проведено исследование корректирующих свойств методом имитационного моделирования. Результаты представлены на рис. 3. Результаты декодирования 4-плетеных МПП кодов с д-ичными кодами-компонентами -кодами Рида,-Соломона сравниваются с результатами декодирования 2-плетеных кодов, с кодами-компонентами - кодами Хэмминга, (отмечены на рис. Н-ВВС) с аналогичной памятью. При более простом декодировании 4-ПСМПП коды

оказываются предпочтительнее.

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

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

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

• предложен ансамбль ЕП МПП кодов, получены асимптотические характеристики лучших кодов в ансамбле. Полученная граница свободного расстояния, при скоростях И < 0.5, совпадает с границей Томмесена — Юстесена, полученной существенно большем классе кодов - случайных сверточных кодов с единичной памятью;

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

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

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

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

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

2. 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.

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

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

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

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

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

23.09.2013

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

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

—

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

04201363160

Кондратов Константин Александрович

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

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

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

Москва - 2013

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

Актуальность работы. Объемы накапливаемой и обрабатываемой в современном мире информации непрерывно возрастают, повышаются и требования к скорости и достоверности передачи данных по каналам связи. Для достижения меньших вероятностей ошибок при передаче, согласно фундаментальным результатам теории кодирования, необходимо использовать все более длинные коды. Однако, при выборе длинных кодов недостаточно руководствоваться только их корректирующими свойствами. Определяющими факторами применимости таких кодов, наряду с хорошими асимптотическими корректирующими свойствами, становятся сложность кодирования и декодирования. Возникает задача построения и исследования эффективных кодов, имеющих реализуемые с помощью современных технических средств алгоритмы кодирования и декодирования. Реализуемыми принято считать алгоритмы кодирования и декодирования с неэкспоненциальной сложностью. Наиболее известными и широкоупотребимыми кодами этого класса являются коды с малой плотностью проверок (МПП). МПП коды были предложены Р. Г. Галлагером в 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].

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

и е

Разобьем информационные блоки на две �