Содержание к диссертации
Введение
Глава 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-плетоного сверточного МПП кода
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
Литература
- Асимптотическая оценка кодовых расстояний сверточных МПП кодов с единичной памятью
- Декодирование ЕП МПП кодов с нулевым хвостом
- Конструкция 2-плетоного сверточного МПП кода
- Исследование корректирующих свойств П-СМПП кодов
Введение к работе
Актуальность работы. Объемы накапливаемой и обрабатываемой в современном мире информации непрерывно возрастают, повышаются и требования к скорости и достоверности передачи данных по каналам связи. Для достижения меньших вероятностей ошибок при передаче, согласно фундаментальным результатам теории кодирования, необходимо использовать все более длинные коды. Однако, при выборе длинных кодов недостаточно руководствоваться только их корректирующими свойствами. Определяющими факторами применимости таких кодов, наряду с хорошими асимптотическими корректирующими свойствами, становятся сложность кодирования и декодирования. Возникает задача построения и исследования эффективных кодов, имеющих реализуемые с помощью современных технических средств алгоритмы кодирования и декодирования. Реализуемыми принято считать алгоритмы кодирования и декодирования с неэкспоненциальной сложностью. Наиболее известными и широкоупотребимыми кодами этого класса являются коды с малой плотностью проверок (МПП). МПП коды были предложены Р. Г. Галлагером в 1962 г. В работах В. В. Зяблова и М.С. Пинксера 1974 г. и 1975 г. было показано, что минимальное расстояния МПП кодов растет линейно с длиной кода и были предложены просто реализуемые алгоритмы декодирования. Однако, несмотря на хорошие потенциальные корректирующие свойства, МПП коды долгое время игнорировались.
В настоящее время МПП кодам посвящается множество работ. Реализуемые корректирующие свойства МПП кодов при неэкспоненциальной сложности декодирования исследовались в работах К. Ш. Зигангирова и Д. К. Зи-гангирова 2006 г., а также в работе К. Ш. Зигангирова, А. Е. Пусане, Д. К. Зигангирова и Д. Дж. Костелло 2008 г. При итеративном декодировании МПП коды обеспечивают лучший обмен в отношении помехоустойчивость к сложности декодирования. В работе Хименеса и Зигангирова 1999 г концепция МПП кодов Галлагера была применена к сверточным кодам. Далее, в работе А. Е. Пусане, Д. К. Зигангирова и Д. Дж. Костелло были исследованы границы минимального и свободного расстояний и было доказано, что пороги МПП сверточных кодов приближаются к пропускным способностям каналов.
Таким образом, исследование свойств различных конструкций сверточных МПП кодов представляет особый теоретический интерес. При этом как теоретическое, так и практическое значение имеет исследование как потенциальных, так и реализуемых при декодировании с неэкспоненциальной сложностью корректирующих свойств.
Цель диссертационной работы состоит в разработке конструкций сверточных кодов с малой плотностью проверок, алгоритмов декодирования с неэкспоненциальной сложностью, применимых к кодам предложенных кон-
струкции, теоретическом и практическом исследовании их корректирующих свойств.
Научная новизна состоит в следующем:
Разработан класс сверточных кодов с единичной памятью и малой плотностью проверок (ЕП МПП). Получены теоретические оценки свободного и активных расстояний. Показано, что при скоростях R < 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 г.) с Министерством образования и науки России.
Публикации. Материалы диссертации опубликованы в 6 печатных работах, из них 3 статьи в рецензируемых журналах [1, 2, 6], 3 статьи в сборниках конференций [3-5].
Личный вклад автора. Все основные научные положения и выводы, составляющие содержание диссертации, разработаны автором самостоятельно. Теоретические и практические исследования, а также вытекающие из них выводы и рекомендации проведены и получены автором лично. Подготовка к публикации полученных результатов проводилась совместно с соавторами. Все теоретические результаты работ [1-4], [5] получены автором самостоятельно. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавторами.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и библиографии. Общий объем диссертации 95 страниц, включая 31 рисунок. Библиография включает 45 наименований на 6 страницах.
Асимптотическая оценка кодовых расстояний сверточных МПП кодов с единичной памятью
Корректирующие свойства сверточного кода во многом опеределяются такими характеристиками, как свободное расстояние, активные строчные расстояния и уклон (средний линейный рост) активных строчных расстояний. Приведем их определения. Определение 1.2 (Свободное расстояние). Свободное расстояние dfree линейного сверточного кода С - это минимальное Хэммингово расстояние между любыми двумя различными кодовыми последовательностями: dfree = min dist (v, v ) Для линейного кода С выполняется min dist (v, v ) = min wt (v"), v.v eC, v v у"ЄС, м"фй где функция wt(-) - Хэммингов вес. В каждый момент времени содержимое памяти определяет состояние кодера сверточного кода. Для кодов с (частично) единичной памятью кодер может быть переведен в нулевое состояние из любого состояния подачей одного нулевого информационного блока. При этом вес кодовой последовательности не увеличится. При частичной памяти ЧЕП МПП кода возможны переходы в нулевое состояние и по ненулевому информационному блоку. Далее будет показано, что в таком случае вес кодовой последовательности увеличивается. Обозначим с помощью Itj множество всех информационных последовательностей и вида . . О 0 щ um ... uJ+j_! 0 0..., где и; ф 0 при t i t + j.
ОпределениеІ.З (Активное строчное расстояние). Активным строчным расстоянием dj (Ч)ЕП МПП кода называется минимальный вес кодовой последовательности, выходящей из нулевого состояния, не проходящей через нулевое состояние по нулевому входу и возвращающейся в нулевое состояние после j информационных блоков.
В данном параграфе будет показано, что кодовые последовательности с весом, равным активному расстоянию на некоторой длине j, могут быть получены только при кодировании информационных последовательностей определенного вида. Будет установлено, что если внутри информационной последовательности отсутствуют нулевые блоки, то внутри соответствующей кодовой последовательности (Ч)ЕП кода все блоки ненулевые. Это потребуется в дальнейшем для получения асимптотических границ. Будут получены аналитические оценки на активные строчные расстояния, свободное расстояние и уклон. Проведем анализ кодовых последовательностей в общем случае для свер-точных МПП кодов с частичной единичной памятью. Полученные результаты будут также верны и для сверточных МПП кодов с полной единичной памятью. Результаты анализа представлены на конференции [20] и опубликованы в рецензируемом журнале [45].
Рассмотрим все кодовые последовательности, порожденные информационными последовательностями различной длины j, начинающимися и заканчивающимися нулевой серией и не содержащими нулевых блоков внутри: и Є Itj.
Разобьем информационные блоки на две части из К — и и і/ двоичных символов, где К — и - размерность матриц Gc(), а и - размерность матриц Gp(t), Gj(t) соответственно: щ = (и4;0 Щ,\)
По построению (Ч)ЕП МПП кодов, множества слов С0, Сс, Cf, Ср, Срс являются кодами. Множества Cpf и Срс/ будут являться кодами только в том случае, если матрицы Gp Gf uP\ Gc \GfJ имеют полный ранг, а для Срс/ дополнительно требуется выполнение условия v + К п. Для выбранных блочных МПП кодов при построении проверочной матрицы (1.2) при b — со с вероятностью р — 1 порождающие матрицы кодов Cpf и СрС/ будут иметь полный ранг, а при условии и + К п так же выполняется и і/ + К п. Таким образом, большинство кодов из ансамбля удовлетворяют этим требованиям и для них множества (1.5) являются кодами. Дальнейший анализ и все полученные результаты верны только для таких, типичных, кодов из ансамбля.
Лемма 1.1. В ансамбле рит (N, К, и) (Ч)ЕП МПП кодов, К + v N, кодовые слова, порожденные информационными последовательностями и Є It,n без нулевых блоков внутри имеют п или п + 1 ненулевых кодовых блоков.
Л е м м а 1.2. Кодовая последовательность (Ч)ЕПП МПП кода из ансамбля Ерит (N, К, и), полученная при кодировании информационной последовательности ... О 0 Uj u(+i ... щ+j-i 0 0... из Itj, где щ = (и о и,д); может иметь вес, равный активному расстоянию Щ, только в том случае, если Uj,0 ф 0, Uj,i ф О при t i j-l, Uj-ifl ф О. Лемма 1.3. Активные расстояния кодов из ансамбля рит (N, К, и) (Ч)ЕП МПП кодов, K+v N, и К удовлетворяют следующим условиям: d\ min(d{Cc),d(Со) + d(Cp)), d\ d (Co) + min (d (Cpc), d (Cpcf) + d (Cp)), drj dr2 + (j 2)d(Cpcf), где d(C{) - минимальный вес кода СІ. Докажем утверждение лемм рассмотрением всех возможных случаев. Исследуем результаты произведения (1.4) при j = 1, 2,.... I 3 = 1 Пусть и = [..., 0, и(, О, ...], где u( = (utfi util), ut ф 0. Распишем результаты произведения (1.4): v = [..., О, \и vt+1, О, ...], vf = U(;0GC + ufilG/, vj+i = UfjGp. Для случайного ненулевого информационного блока щ = (и ;о Щ,і) возможны 3 случая. 1. На входе: "г,о ф 0, uu = О. На выходе: vt = uf,oGc, Vf+i = 0. Блок vt Є Сс и хэммингов вес кодовой последовательности wt(v, vi+1) d(Cc). 2. На входе: т,о Ф 0, Ui,i т4 0. На выходе: vt = utfiGc + ut,iGf, Vj+i = u iGp. Блоки v( Є Co, V(+i Є Cp и вес кодовой последовательности wt(vt vt+1) d (Со) + d(Cp). 3. На входе: uii0 = 0, и;д ф 0. На выходе: vt = uaG/, Vf+i = ut Gp. Блоки v( Є С/, Vt+i Є Ср, результирующий вес wt(vt vM) d (С/) + d(Cp).
Активное расстояние d\ соответствует минимальному весу рассмотренных выше кодовых последовательностей. Пусть при равной длине кодов, коды с меньшей скоростью имеют большее кодовое расстояние. В асимптотическом случае, лучшие блоковые МПП коды могут лежать сколь угодно близко к границе Варшамова-Гилберта и для них данное предположение выполняется. Тогда d (Со) d (С/) и минимальный возможный вес в случае 2 меньше, чем в случае 3. Сравним случаи 1 и 2. Кодовое расстояние d(Cc) больше d(Co). Однако d (Сс) может быть меньше суммы d (Со) + d (Ср). Последняя определяется отношением между К и v . Так, если К — и г/, то d (Сс) d (Ср) и d\ = d (Сс)- Таким образом,
Декодирование ЕП МПП кодов с нулевым хвостом
В главе 1 был предложен ансамбль сверточных кодов с единичной памятью и малой плотностью проверок (ЕП МПП), построенных из блоковых МПП кодов. Для кодов данного ансамбля были получены асимптотические оценки на свободное и активные расстояния. В данной главе корректирующие свойства представленных кодов исследуются методом имитационного моделирования. В качестве алгоритма декодирования был выбран итеративный алгоритм декодирования распространения доверия [29]. Алгоритм распространения доверия, известный также как алгоритм прохождения сообщений, широко используется при декодировании блоковых и сверточных МПП кодов благодаря малой сложности, хорошему распараллеливанию и надежности декодирования. В качестве модели канала был выбран канал с аддитивным белым Гауссовским шумом (АБГШ). Декодирование осуществляется методом компьютерного моделирования.
Задачей исследования ставится изучение корректирующих свойств ЕП МПП кодов в зависимости от параметров алгоритма и свойств блоковых МПП кодов, использованных при построении.
Прежде всего, опишем алгоритм декодирования „распространения доверия" (РД) применительно к блоковым МПП кодам, затем приведем его модификацию для работы со сверточными ЕП МПП кодам.
Для удобства описания представим блоковый (N,,no) МПП код в виде графа Таинера [30] - двудольного графа, вершины одной доли которого соответствуют кодовым символам vn, п = 1,..., N МПП кода и называются символьными, а вершины другой доли соответствуют проверкам кода СІ, г = 1, ...,Ъ, Ь = N/щ и называются проверочными. В графе Таннера (N,,m) МПП кода каждый символьный узел связан с I проверочными узлами и каждый проверочный узел связан с щ символьными узлами. Общий вид графа Таннера (N,,n0) МПП кода представлен на рис. 2.1.
Обозначим с помощью М{г) множество символьных узлов, связанных с проверочным узлом СІ, а с помощью С{п) множество проверочных узлов, связанных с символьным узлом vn. Пусть кодовое слово блокового (N, (., щ) МПП кода v = {v\V2 v ) передается но АБГШ каналу и пусть г — {г\г і... г ) означает принятую последовательность. Алгоритм распространения доверия основан на вычислении по принятой последовательности апостериорных вероятностей P(vn = 0\r) (2.1) для кодовых символов v„, п = 1, 2,..., N.
Операции, производимые декодером распространения доверия на J -OM шаге, j = 1, 2,...,/, могут быть разделены на две фазы. В первой фазе проверочные узлы получают сообщения от смежных с ними символьных узлов и, используя полученную информацию, формируют новое сообщение. Во второй фазе проверочные узлы посылают вновь сформированные сообщения смежным с ними символьным узлам, а те, в свою очередь, формируют новые сообщения, которые будут посланы ими на первой фазе следующего шага итеративного процесса декодирования. Процесс обмена сообщениями между узлами представлен на рис. 2.2.
Введем логарифмическое отношение правдоподобия z„ кодового символа vn, определяемое принятым символом г„. Пусть irn(0) = P(Vn = 0),n = l,2,...,N (2.3) означает априорную вероятность, что vn равно 0. Ниже мы будем полагать, что P(vn = 0) = 1/2. При передаче в АБГШ с соотношением сигнал/шум jf-плотность условной вероятности г„ задается функцией
Статистика Zn называется внутренней информацией о кодовом символе vn. В начале процесса итеративного декодирования каждый символьный VU\ 712 VTl3 VTli vna vn6
Иллюстрация обмена сообщениями при декодировании алгоритмом распространения доверия блокового (N,3,6) МПП кода: (а) обновление проверочного узла q, (б) обновление символьного узла vn. узел запоминает соответствующую внутреннюю информацию и хранит ее в памяти до окончания декодирования.
Каждый символьный узел связан с проверочными узлами. В первой фазе первого шага итеративного процесса, n-ый символьный узел, п = 1, 2, ..., N, посылает логарифмическое отношение правдоподобия zn = z„ связанным с ним проверочным узлам і Є (п). Затем г-ый проверочный узел, получивший по сообщений z\J, п Є М(і), формирует по логарифмических отношений правдоподобия y\J, та Є ЛГ(г), это условные вероятности что vn = 0, vn = 1, соответственно, при условии, что известно множество принятых символов {гп ,п Є Л/"(г) \ {п}}, входящих в проверку с,. Проверка Q выполняется, если в нее входит четное число еди ничных символов. Таким образом, Вычисление статистик yln , г = 1,2,...,Ь,пЄ N{i), завершает первую фазу первого шага процесса итеративного декодирования.
Во время выполнения второй фазы первого шага итеративного процесса декодирования г -ые, г = 1, 2,..., Ь, проверочные узлы шлют логарифмические отношения правдоподобия у\п , п Є А/"(і), соответствующим смежным символьным узлам. Затем n-ый символьный узел, получивший сообщения от смежных проверочных узлов, вычисляет J логарифмических отношений правдоподобия z(J, і Є С(п),
Здесь 2/,n, г Є L(n)\W означают сообщения, называемые внешней информацией, которую п-ый символьный узел получил от смежного проверочного узла. Вычисление статистик zni , г С{п), завершает вторую фазу первого шага процесса итеративного декодирования.
Опишем г-ый, г — 1,2,...,/— 1 шаг итеративного процесса декодирования. Во время первой фазы г-ой итерации п-ый символьный узел посылает сообщение z%[ , которое было вычислено им на предыдущем шаге, смежному проверочному узлу і Є (п). Затем г-ый проверочный узел, і = 1,2,... ,Ь, получивший по сообщений 2„Г , п Л/"(г), от смежных символьных узлов, вычисляет статистики уг , п Є Л/"(г) (ср. (2.9)),
Конструкция 2-плетоного сверточного МПП кода
В качестве кодов-компонентов для плетеных сверточных МПП кодов выбраны оптимальные коды с малой избыточностью и сложностью декодирова-ния.Для двоичных 2-П-СМПП кодов выбраны коды Хэмминга, для q-ннпых - коды Рида-Соломона и g-ичные коды с одной проверкой. Расстояние кодов Хэмминга d = Зп они способны исправлять одну ошибку. Коды Хэмминга являются совершенными и их декодирование оптимально. Коды Рида-Соломона являются МДР-кодами, а значит, их расстояние максимально среди кодов с данными длиной и размерностью, а избыточность минимальна. В работе используется код Рида-Соломона с d = 3 и проверочной матрицей (3.3) (і а а2 ... аЧ-2 " \\ (а)2 (а2)2 ... (а -2)2 где а - примитивный элемент поля q. В качестве g-ного кода с d = 2 и одной проверкой используется код с длиной q и проверочной матрицей Я = ( 1 а а2 ... а"-2 1 ) , (3.4) составленной из всех ненулевых элементов поля и дополнительного единичного элемента поля. И хотя сами по себе коды с d — 2 не могут исправить ни одной ошибки, все меняется при их комбинированном использовании. Простая реализация, малая сложность кодирования и декодирования и минималь ная избыточность делает оправданным при исследовании новых скоростных каскадных конструкций применение в первую очередь именно таких кодов в качестве кодов-компонентов.
До недавних пор МПП коды, обладающие хорошими корректирующими свойствами и позволяющие строить эффективные схемы декодирования при малой их сложности, были представлены практически исключительно блоковыми кодами. В классе сверточных МПП кодов можно было обнаружить лишь турбо-коды [2] и сверточные МПП коды, полученные специальным преобразованием проверочной матрицы их блоковых аналогов. Изменить сложившуюся ситуацию в некоторой мере удалось новым плетеным сверточным МПП кодам, представленным в работе К. Ш. Зигангирова, А. Хименеса и др. [10]. Востребованность сверточных кодов и появление новой конструкции поспособствовали притоку внимания к этой области и, как следствие, увеличению числа исследований и публикаций. Следует отметить, что в оригинальной статье [10] предложенные коды называются блоковыми плетеными кодами по природе кодов-компонентов, из которых они строятся, и методу построения. Тем не менее, независимо от природы кодов-компонентов, результирующие коды являются сверточными. Здесь и далее, во избежание путаницы, будем называть предложенные коды 2-плетеными сверточными МПП кодами (2-П-СМПП).
2-П-СМПП код строится «плетением» двух кодов-компонентов с кодовым расстоянием di 3 и скоростью Ri lk- Структура 2-П-СМПП кода позволяет естественным образом, без изменения конструкции использовать как двоичные коды-компоненты, так и коды-компоненты над произвольным полем д. В качестве кодов-компонентов рассмотрены двоичные (15, 11)-коды Хэмминга и восьмеричные коды Рида-Соломона. Для двоичных 2-П-СМПП кодов с кодами компонентами Хэмминга доказано [10], что их кодовое расстояние растет линейно с длиной кодового ограничения vs = (ms + 1)-с. Полученный в [10] результат может быть обобщен также и на случай произвольных подходящих недвоичных кодов-компонентов.
В 2-П-СМПП коде каждый символ кодовой последовательности v — [і»о Щ ... vt ...] входит ровно в два кода разных кодов-компонентов, при этом любой неинформационный символ 2-П-СМПП кода является информационным для одного и проверочным для другого кода-компонента. В зависимости от контекста, будем отличать принадлежность символа кодовой последовательности к первому или второму коду-компоненту с помощью надстрочного индекса (е), где е = 1, 2. Используя обозначение vfj, будем ссылаться на символ vfj как на проверочный символ кода . Чтобы показать, что информационный символ v\fj кода является проверочным символом второго кода , будем использовать запись Ц .
Опишем конструкцию 2-П-СМПП кода на примере 2-П-СМПП кода с кодами-компонентами (7, 5)-кодами Рида-Соломона. Пусть символы кодовой последовательности помещаются в ячейки бесконечного двумерного массива. Массив разделен на три области - полосы. В каждую из полос помещаются символы одной из трех групп: информационные символы, проверочны е символы первого кода-компонента, проверочные символы второго кода-компонента (рис. 3.1). В соответствии с геометрическим положением символов, образующих кодовое слово того или иного кода-компонента, коды-компоненты называются вертикальным кодом и горизонтальным кодом. Кодовое слово горизонтального кода-компонента v\ образуется символами [v}b v]2, и}, г)1; и2], гдегі? = [ut-1,2, щ,о, Щ,\].
Исследование корректирующих свойств П-СМПП кодов
Для исследования реализуемых корректирующих свойств П-СМПП кодов выполняется моделирование декодирования со случайным введением ошибок в кодовое слово при заданной вероятности ошибки в канале. Ошибки удовлетворяют требованиям ДСК и его восьмеричного аналога. Длины кодов выбираются порядка 2400. Максимально число итераций исправления ошибок 50. Выполняется 105 испытаний для каждого кода и алгоритма декодирования. Результатами моделирования являются вероятности опіибки на бит и на символ, вероятности отказа декодирования. При моделировании под-считывается число испытаний, завершившихся успехом, ошибкой и отказом. Количество оставшихся после декодирования ошибок суммируется по всем испытаниям, независимо от исходов декодирования. Вероятность символьной ошибки рассчитывается как отношение суммарного числа неисправленных ошибочных символов во всех испытаниях к числу испытаний и длине кода в символах. Вероятность отказа декодирования определяется как отношение суммарного числа отказов во всех испытаниях к числу испытаний.
В случае двоичных кодов проводилось моделирование 2-П-СМГШ кода с кодами-компонентами (15, 11)-кодами Хэмминга и длиной кодовой последовательности 2400 бит и 4-П-СМПП кода с кодами-компонентами (8, 7)-кодами проверки на четность и длиной кодовой последовательности 2400. Выходные вероятности ошибки на бит и вероятности отказа декодирования представлены на рис. 4.1 и 4.2, соответственно.
Несмотря на меньшие значения активных расстояний, результаты кода с четырьмя более простыми кодами-компонентами оказываются лучше, чем кода с двумя более сильными кодами-компонентами. понентами (7, 5)-кодами Рида-Соломона и длиной кодовой последовательности 2100 восьмеричных символов и 4-П-СМПП кода с кодами-компонентами (8, 7)-кодами с проверочной матрицей (3.4) и длиной кодовой последовательности 2400 символов. Выходные вероятности ошибки на символ и вероятности отказа декодирования представлены на рис. 4.3.
Здесь, 4-П-СМПП код имеет уже значительно большие расстояния, чем 2-П-СМПП код. При декодировании алгоритмом Л\ его результаты лучше.
Результаты декодирования двоичных П-СМПП кодов с помощью алгоритма Аг представлены на рис. 4.4 и 4.5.
Введение дополнительной информации в виде стираний повлияло на П-СМПП коды по-разному. По результатам декодирования, по сравнению с результатами декодирования алгоритмом Ль 2- и 4-П-СМПП коды поменялись местами. Такое поведение может быть обусловлено тем, что для исправления стираний в 2-П-СМПП коде с кодами-компонентами Хэмминга используется линейная система уравнений большей размерности.
Восьмеричный 4-П-СМПП код, с большими активными расстояниями и показавший лучшие результаты при декодировании алгоритмом А\, при введении стираний дает результаты хуже, чем 2-П-СМПП код. Однако здесь, в отличие от двоичных кодов, мы можем воспользоваться преимуществом поля GF (q) - наличием различных ненулевых элементов. Как видно из рисунка 24, в 4-П-СМПП коде с кодами-компонентами с проверочными матрицами (3.4), символы которых идут в порядке сверху вниз и слева направо по кодовому слову (рис. б), встречаются ситуации, когда несколько кодов-компонентов пересекаются но двум символам. При этом коэффициенты, с которыми эти символы входят в проверки кодов-компонентов, совпадают. Это увеличивает вероятность того, что при ошибках два из четырех кодов-компонентов будут давать одинаковые решения по таким символам. В случае ошибок, которые не могут быть исправлены кодами-компонентами за одну итерацию, мы хотим, чтобы все коды-компоненты давали для них разные решения. Для этого в проверочных матрицах кодов-компонентов 4-П-СМПП кода выбираются различные ненулевые элементы поля таким образом, чтобы в результирующей проверочной матрице 4-П-СМПП кода никакие символы не входили в два кода-компонента с одним и тем же коэффициентом. Результаты декодирования нового 4-П-СМПП кода представлены на рис. 4.7.
В результате такого преобразования проверочной матрицы 4-П-СМПП кода новый 4-П-СМПП код показал улучшения при обоих алгоритмах декодирования.
Видно, что с увеличением памяти улучшаются и корректирующие способности. Однако, при меньших вероятностях ошибки скорость роста исирав Вероятность ошибки в канале Рис. 4.6. Результаты декодирования алгоритмом А і восьмеричных П-СМПП кодов. ления ошибок уменьшается, что может быть обусловлено недостаточным свободным расстоянием. Прямое влияние на эту характеристику оказывает выбор матриц перестановки.
Использование большего числа более простых кодов-компонентов в двоичном случае приводит к уменьшению активных расстояний кода. Несмотря на это, при декодировании алгоритмом использовании более сложного алгоритма декодирования _42 наблюдается противоположное поведение: 4-П-СМПП код оказывается хуже. При этом, при декодировании алгоритмом Л2, 15 оба кода показывают результаты лучше, чем при декодировании по алгоритму Л\. В случае недвоичного поля GF (q) использование большего числа кодов-компонентов приводит к существенному А\ 4-П-СМПП код показывает лучшие результаты, чем 2-П-СМПП код. При улучшению активных расстояний. Больший порядок поля также позволяет применить методику для получения кодов с лучшими характеристиками. Поведение кодов при декодировании алгоритмами А\ и А% сохраняется.
