Вернер М. Основы кодирования (2004) (1151849), страница 38
Текст из файла (страница 38)
Детектор Витерби с субоптимальной аддитивной метрикой.Таким образом, при аддитивной метрике информационная последовательность также детектируется без ошибок.ГЛАВА 5ДИСКРЕТНЫЕПРЕОБРАЗОВАНИЯ ФУРЬЕИ КОДЫ РИДА - СОЛОМОНА5.1. ВведениеВ предыдущих главах мы рассматривали только двоичные коды, тоесть коды с символами из GF(2). Между тем, коды над алфавитомGF(q), где q > 2, так называемые g-ичные коды, помимо чисто теоретического интереса, имеют в настоящее время огромное прикладноезначение.
Мы ограничимся только рассмотрением кодов Рида - Соломона, как наиболее ярких представителей д-ичных кодов, без которых немыслима современная теория и практика помехоустойчивогокодирования.Остановимся, прежде всего, на прикладном значении кодов Рида - Соломона. Как было показано в предыдущих главах, простейшие алгебраические двоичные коды могут успешно применяться дляпередачи данных в компьютерных сетях связи, обеспечивая необходимую надежность передаваемой информации.
Это объясняется достаточно высоким качеством проводных и оптоволоконных каналовсвязи и возможностью переспроса передаваемых блоков данных. Задача кодирования для таких каналов, в основном, сводится только кобнаружению независимых ошибок и пакетов ошибок.Все многообразие современных коммуникационных линий связине исчерпывается только компьютерными сетями. В качестве примеров достаточно привести спутниковые каналы и мобильную цифровую связь. Здесь уже переспросы не допустимы и корректирующая способность кода определяется максимальным числом исправляемых ошибок.
Предельная мощность передаваемого сигнала в таких каналах жестко ограничивается, что приводит к высокой вероятности появления как независимых ошибок, так и пакетов ошибок.В таких каналах использование рассмотренных нами простейшихдвоичных кодов не имеет смысла. Так, например, коды Хэммингасdm'm = 3 и dm;n = 4 при наличии в блоке более, чем одной ошибки, вместо исправления ошибок будут вносить новые. Проблему, в5.1. Введениекакой-то степени, могут решить низкоскоростные двоичные коды Боуза Чоудхури - Хоквингема, однако, их реализация и декодирование аналогично кодам Рида Соломона осуществляется с помощьюопераций над GF(2m) при т > 1.С другой стороны, турбо-коды, построенные на базе двоичныхсверточных кодов, хотя и позволяют обеспечить требуемую надежность при кодовых скоростях, близких к пропускной способности каналов с независимыми ошибками, не расчитаны на борьбу с длинными пакетами ошибок.
Кроме этого, для их эффективной реализациитребуются блоки очень большой длины (десятки и даже сотни кбит),что не всегда технически приемлемо.Решению подобных задач в немалой степени способствовало появление в 1968 г. кодов Рида - Соломона с символами из GF(q), гдеq > 2 [20]. Коды Рида - Соломона с параметрами (п, к) имеют минимальное расстояние dm,n = п — к+1 и способны исправлять ](п—к)/2[ошибок. После открытия Берлекэмпом в 1968 г. простого и эффективного алгоритма декодирования кодов Рида - Соломона, эти кодыпрочно вошли в практику помехоустойчивого кодирования.В первую очередь в 60 ы х годах коды Рида - Соломона стали применяться в качестве внешних кодов в каскадных конструкциях, используемых в спутниковых линиях связи.
В таких конструкциях [21]q-ичные символы кодов Рида - Соломона (один или несколько) кодируются внутренними двоичными сверточными кодами. При декодировании сверточных кодов используется мягкое решение, особенноэффективное в каналах с АБГШ. Так как шум в реальных каналахвсегда отличается от гауссовского, в спутниковых каналах возможнопоявление пакетов ошибок. Такие пакеты могут привести к ошибочному декодированию внутренними сверточными кодами одного илинескольких довольно длинных блоков. Для внешних кодов Рида Соломона это, в основном, эквивалентно появлению ошибочных qичных символов небольшой кратности, лежащих в пределах корректирующей способности внешнего кода.
Таким образом, весь каскадный код, даже при наличии пакетов ошибок, в подавляющем большинстве случаев декодируется правильно, что обеспечивает необходимую надежность передаваемой информации. Самое удивительноезаключается в том, что четкой альтернативы каскадным кодам свнешними кодами Рида Соломона для спутниковых линий связи досих пор найти не удалось и коды Рида Соломона являются неотъемлемой частью большинства стандартов (например Intelsat IESS-308).Кроме этого коды Рида - Соломона имеют самостоятельное нрак-. 270Глава 5. Дискретные преобразования Фурье и коды PCтическое применение. Они, например, являются практически оптимальными при записи информации на носители аудио-CD, что обусловлено техническими характеристиками и характером ошибэк призаписи.Структура кодов Рида - Соломона и алгоритм декодированиянаиболее просто описывается с помощью спектральных методов [5).Арифметика нолей Галуа GF(q) описана в приложении 2.5.5.2.
Дискретные преобразования Фурье в полеГалуаОпределение. Пусть задан вектор v = (vo, «i,..., v n -i) над GF(q),где q = 2 m , a n = q — 1 и пусть а - примитивный элемент поля ГалуаGF(q) характеристики 2. Преобразование Фурье в ноле Галуа вектора v определяется как вектор V = (Vo, Vi,..., Vn_i), задаваемыйравенствамиn-ly;- = 5 > y « i ,i=0j = o,...,n-i.(5.i)По аналогии с преобразованиями Фурье непрерывных сиглалов,дискретный индекс г принято называть временем и говорить э том,что вектор v принадлежит временной ^области. Естественно, что вэтом случае индекс j называется частотой и говорят, что вектор Vопределен в частотной области.Теорема 5.2.1. Над полем GF(q) характеристики 2 вектор v вовременной области и вектор V в частотной области связаны соотношениямип-1у;-= £ < * « « »(5-2)г=0г* = Х > - ^ ,(5.3)По аналогии с непрерывными сигналами будем называть преобразование (5.2) прямым преобразованием Фурье, а (5.3) - обратнымпреобразованием.Вектор v иногда задается многочленом v(X).
С помощью преобразования Фурье в поле Галуа многочленv(X)= vo + vlX+ --- + vn_lXn-1(5.4)5.2. Дискретные преобразования Фурье в поле Галуаможет быть преобразован в многочленкоторый называется спектральным многочленом или многочленомв частотной области вектора v.Теорема 5.2.2.1. j-ая частотная компонента Vj равна нулю тогда и только тогда,когда элемент а? является корнем многочлена v{X);2.
г-ая временная компонента Vi равна нулю тогда и только тогдакогда элемент а"1 является корнем многочлена V(X).Доказательство. Доказательство утверждений 1. и 2. очевидны,так какп-1туX "* ij(г\3 \(Z\ f!\г=0Ип-13V/*V/j=0шПреобразование Фурье обладает многими важными свойствами,которые переносятся на случай конечных полей.
Помимо линейностипреобразований Фурье для нас важным является свойство свертки.Прежде чем сформулировать теорему о свертке, введем некоторыеопределения.Пусть в поле GF{q) заданы векторы g = (<?o,Si> • • • ,<?n-i)d = (do,d\,..., dn-i), многочлены которых имеют вид д(Х) =до + 31 № + • • • + Э п - i ^ " " 1 и d(X) = do + di{X) + ••• +иdn^iXn~l.Тогда компоненты вектора линейной свертки с = (со,сь . .
. ,Cn-i)векторов g и d определяются какп-1к=ои многочлен линейной свертки с(Х) может быть записан в виде произведенияс(Х) = g(X)d(X).272Глава 5. Дискретные преобразования Фурье и коды PCОперацию линейной свертки двух векторов мы уже рассматривалив разделе 4.2.Циклическая свертка может быть записана в видек=огде двойные скобки означают вычисление индексов по модулю п =q — 1 (заметим, что в арифметике но mod n имеет место равенство—k = п — к).Многочлен циклической свертки имеет видс(Х) = g{X)d(X)( modJs: n -l).Для того, чтобы избежать путаницы, будем обозначать операциюциклической свертки символом «*», а операцию линейной свертки- символом «©».
Наконец, операцию покомпонентного умножениядвух векторов с = gd определим каксг = gidt.Заметим, что все введеные выше операции обладают свойством линейности.Теорема 5.2.3. Теорема о свертке.Пусть во временной области заданы векторы f = (/о, / i , . . . , / n -i)и g = (<йь5ь • • • > <?n-i), прямые преобразования Фурье которых в частотной области имеют вид F = (FQ,FI,. .. ,F n _i) и G = (Go,<?i,---.,Gn-i), тогда покомпонентному произведению векторов в частотнойобласти Е = FG взаимно однозначно соответствует их циклическаясвертка во временной области е = f * g, т.е.
если Е = FG, топ-1кЧ = ^2 ?((* ~ ))9к,fc=oг = 0,..., п - 1.Справедлива так же обратная теорема. Для ее формулировкинужно только поменять местами временную и частотные области.Изложенных выше сведений из теории дискретных преобразований Фурье вполне достаточно для изучения структуры кодов Рида- Соломона и алгоритма их декодирования.5.3. Коды Рида - Соломона 2 7 3 ,5.3. Коды Рида - СоломонаПрежде, чем приступить к изложению теории кодов Рида - Соломона, введем понятие кода с максимальным расстоянием.Теорема 5.3.1. Граница Синглтона.Минимальное расстояние dm;n любого (п, &)-кода (необязательнолинейного) удовлетворяет неравенствуd m j n < п — к + 1.Доказательство. Пусть символы кода принадлежат полю GF(q).В множестве qk кодовых слов выделим и зафиксируем к — 1 разрядов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
