Вернер М. Основы кодирования (2004) (1151882), страница 38
Текст из файла (страница 38)
Так, например, коды Хэммингас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 разрядов. Эти разряды могут содержать самое большее qk~i различныхg-ичных чисел. Следовательно, во всем множестве кодовых слов ввыделенных к—1 разрядах имеет место по крайней мере qk—qk~1 совпадений.
Рассмотрим любые два кодовых слова, совпадающие между собой в к — 1 разрядах. Так как эти слова могут иметь различиетолько в п - Н 1 компонентах, расстояние между ними не можетпревышать величины п — к + 1. •Определение. Любой код с минимальным расстоянием, удовлетворяющим равенствуdmin = П — к + 1называется кодом с максимальным расстоянием.Определение. Код, который может быть приведен к систематическому виду путем операций, не изменяющих дистанционный профиль кодовых слов, называется разделимым.Так как линейный код может быть приведен к систематическому виду элементарными преобразованиями порождающей матрицы, любой линейный код является разделимым.Определение.
Разделимый код с максимальным расстоянием называется МДР кодом (разделимым кодом с максимальным расстоянием).Теперь вернемся к кодам Рида - Соломона.Определение. Кодом Рида Соломона называется линейный циклический (п,п- d+ 1)-код над GF(q), где q = рт, длины п = q - 1,порождающий многочлен которого д(Х) имеет своими корнями d — 1последовательных степеней примитивного элемента а из поля GF(q).Глава 5. Дискретные преобразования Фурье и коды PCВ качестве порождающего многочлена кода Ридавыбрать, напримерд(Х) = (Х- а){Х -а2)---(Х-Соломона можноа"-1).Замечание. Так как мы ограничиваемся только полями характеристики 2, то будем в дальнейшем вместо операций вычитанияиспользовать операцию сложения.В теории помехоустойчивого кодирования доказывается, что свойства (п, &)-кода Рида Соломона с символами из GF(q) и параметрами п — q — I, k = п — d + 1 не зависят от метода его построенияи определяются только выбранными значениями q и d.
Наиболеепросто код Рида - Соломона, а так же алгоритм его декодирования реализуется на основе дискретных преобразований Фурье, рассмотренных нами в предыдущем разделе. Процедуры кодированияи декодирования такого кода могут быть значительно ускорены спомощью техники быстрых преобразований Фурье (БПФ).Выберем и зафиксируем некоторое поле Галуа GF(q) с q = 2 m ,примитивный элемент а £ GF(q) и параметр d. Рассмотрим информационный вектор и = (мо, ui,..., Wfc-i) длины к = п — d+ I = q — d скомпонентами из GF(q). Поставим в соответствие вектору и вектордлины п = q - 1, у которого первые к компонент совпадают с компонентами вектора и, а остальные компоненты - нулевые. Рассмотримпрямое преобразование Фурье вектора v в вектор V, определяемое(5.1) и удовлетворяющее теореме 5.2.1.
Тогда справедлива следующая теорема:Теорема 5.3.2. Множество q векторов V в частотной области образует (п, к)-код Рида Соломона.Доказательство. Представим векторы v и V в виде многочленовv(X) =vo + v1X--- + vk-iXk-1+ 0 • Xk + 0 • Xk+1+ • • • + 0 • Хп~1Так как г-ые временные компоненты вектора v равны нулю прик < г < п — 1, то, согласно теореме 5.2, многочлен V(X) имеет корниa~k = ad~l, a~(fc+1> = ad~2,... ,а~(п~1'> = а. Таким образом, много-5.4- Декодирование кодов Рида - Соломона 275Jчлены V(X) образуют (п, к)-код Рида - Соломона с порождающиммногочленомд(Х) = {Х + а){Х + а2) • • • (XСпектральный подход позволяет легко доказать следующую теорему.Теорема 5.3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
