<< Предыдущая

стр. 48
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

с
dm'm = 3 и dm;n = 4 при наличии в блоке более, чем одной ошиб-
ки, вместо исправления ошибок будут вносить новые. Проблему, в
5.1. Введение

какой-то степени, могут решить низкоскоростные двоичные коды Бо-
уза Чоудхури - Хоквингема, однако, их реализация и декодирова-
ние аналогично кодам Рида Соломона осуществляется с помощью
m
операций над GF(2 ) при т > 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-l
y;- = 5 > y « i , j = o,...,n-i. (5.i)
i=0
По аналогии с преобразованиями Фурье непрерывных сиглалов,
дискретный индекс г принято называть временем и говорить э том,
что вектор v принадлежит временной ^области. Естественно, что в
этом случае индекс j называется частотой и говорят, что вектор V
определен в частотной области.

Теорема 5.2.1. Над полем GF(q) характеристики 2 вектор v во
временной области и вектор V в частотной области связаны соотно-
шениями
п-1
у;-= ? < * « « » (5-2)
г=0


г* = Х > - ^ , (5.3)

По аналогии с непрерывными сигналами будем называть преоб-
разование (5.2) прямым преобразованием Фурье, а (5.3) - обратным
преобразованием.
Вектор v иногда задается многочленом v(X). С помощью преоб-
разования Фурье в поле Галуа многочлен
+ --- + vn_lXn-1 (5.4)
v(X) = vo + vlX
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
И
п-1
V /* V /
3
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к, г = 0,..., п - 1.
fc=o

Справедлива так же обратная теорема. Для ее формулировки
нужно только поменять местами временную и частотные области.
Изложенных выше сведений из теории дискретных преобразова-
ний Фурье вполне достаточно для изучения структуры кодов Рида
- Соломона и алгоритма их декодирования.
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

<< Предыдущая

стр. 48
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>