О Н Дячекно - Аппаратная реализация и корректирующие возможности - страница 1

Страницы:
1  2 

АППАРАТНАЯ РЕАЛИЗАЦИЯ И КОРРЕКТИРУЮЩИЕ ВОЗМОЖНОСТИ

КОДОВ РИДА-СОЛОМОНА

Дяченко О.Н. Донецкий национальный технический университет do@cs.dgtu.donetsk.ua

Abstract

Dyachenko O.N. Hardware implementation and correcting possibilities of Reed-Solomon codes. Integrated assessment of modes of hardware implementation for encoders and decoders for Reed-Solomon codes is discussed. Analysis of choice of generator polynomial is concerned using single-error-correcting Reed-Solomon code as example; characteristic properties of construction of code and circuits of encoder and decoders are illustrated. Method of increase of correcting possibilities of codes is proposed.

Введение

Коды Рида-Соломона нашли широкое применение в цифровых системах связи и хранения информации. Можно привести несколько наиболее известных примеров: (255, 223, 33) код Рида-Соломона для космической связи NASA, укороченные коды Рида-Соломона над полем Галуа GF(2 ) для CD-ROM, DVD и цифрового телевидения высокого разрешения (формат HDTV), расширенный (128, 122, 7) код Рида-Соломона над полем Галуа GF(2 ) для кабельных модемов [1]. Коды Рида-Соломона широко описаны в литературе [1, 2, 3], но вместе с тем аппаратная реализация кодирования и декодирования освещена либо вкратце, либо вовсе отсутствует. Данная работа посвящена особенностям построения кодирующих и декодирующих устройств кодов Рида-Соломона и их корректирующих возможностей.

Порождающий полином кодов Рида-Соломона

Коды Рида - Соломона являются частным случаем кодов БЧХ. Главное отличие кодов Рида - Соломона заключается в том, что в качестве символа выступает не двоичный символ (один бит), а элемент поля Галуа (несколько битов).

Порождающий полином кода Рида - Соломона, исправляющего s ошибок, должен содержать 2 s корней:

(aJo, aJo , aJo       aJo }, где j0 - конструктивный параметр.

Как правило, j0 выбирают равным 1. Тогда множество корней полинома принимает вид {а, а2, а3... a2s}.

Для   кода   Рида   -   Соломона,   исправляющего   s ошибок, порождающий полином имеет следующий вид:

RS^) = - а)(х - а2)(х - а3).. .(х - a2s),

При таком представлении очевидно, что порождающий полином имеет множество корней {a, а2, а3... a2s}.

Коды Рида-Соломона, исправляющие одиночную ошибку

Для кода Рида-Соломона, исправляющего одиночную ошибку (s=1), порождающий полином имеет вид RS^) = - а)(х - а ).

Возможно несколько форм записи порождающего полинома для кодов Рида-Соломона. Как правило, для построения кодов Рида-Соломона используют расширения поля GF(2) над примитивным полиномом p(z). В этом случае, в соответствии с определением примитивного полинома, элемент поля z является примитивным. Поэтому вместо обозначения примитивного элемента а можно использовать z:

RS(x) = x2 + (a + a2)*x + a3 = x2 + (z + z2)*x + z3.

Другая форма будет зависеть от того, какое именно поле используется для построения кода Рида-Соломона. Поэтому эту форму рассмотрим на примере.

Пример. Построим поле Галуа GF(8) как расширение поля GF(2) над примитивным полиномом р^) = z + z + 1. Элементы поля могут быть представлены в различном обозначении.

В виде степени

В виде полинома

В двоичном виде

0

0

000

а0

1

001

а1

z

010

а2

2

z

100

а3

z + 1

011

а4

2 ,

z +z

110

а5

z2 + z + 1

111

а6

z + 1

101

2 2 3 2

Поскольку RS(x) = x   +(z + z )*x + z , а (z + z) для

4 3 3

рассматриваемого поля GF(8) в степенном обозначении a , z - a , то порождающий полином можно представить в следующей форме: RS(x) =

2 4 3 x + a x + a .

При изменении j0 также изменяется порождающий полином.

2 3 2 3       2 5

Например, при j0=2 RS(x) = (x - a )(x - a ) = x + (z + z )x + z . Для GF(8) над рф = z3 + z + 1 RS(x) = x2 + (z2 + z + 1)x + z2 + z + 1 = x2 + a5 x + a5. Кроме того, отметим, что элементы поля в общем виде для поля GF(8) можно обозначить: a2z   + a1z + a0, где а2, а1, а0 - коэффициенты, принимающие разные значения. Эти элементы поля -   в данном случае триады - являются символами кода Рида - Соломона.

Кодирующие и декодирующие устройства

Итак, для кода Рида-Соломона, исправляющего одиночные ошибки, получены разные формы порождающих полиномов:

1) RS^) = (x - a)(x - a ) при j0 = 1;

23

2) RS(x) = (x - a )(x - a ) при j0 = 2;

3) RS(x) = x2 + (z + z2)*x + z3 при j0 = 1;

4) RS(x) = x2 + (z3 + z2)x + z5 при j0 = 2;

5) RS(x) = x2 + (z + z2)*x + z + 1 при j0 = 1;

6) RS(x) = x2 + (z2 + z + 1)x + z2 + z + 1 при j0 = 2;

2 4 3

7) RS(x) = x + a x + a при j0 = 1;

2 5 5

8) RS(x) = x2 + a5 x + a5 при j0 = 2.

Формы 1, 2 являются общими для разных полей Галуа, но для построения схем в таком виде не используются. Все остальные формы могут быть использованы для построения схем кодера и декодера, при этом формы 3, 4 не зависят от конкретного поля Галуа, формы 5-6 зависят от конкретного поля Галуа.

Нечетные и четные варианты полиномов определяют разные коды -у них будет разная схемная реализация, но основные параметры -корректирующие возможности, длина кода n, количество информационных k и проверочных n-k=p символов - одинаковы.

Как правило, для представления функциональных схем кодирующих и декодирующих устройств используют 7, 8 варианты порождающих полиномов, вид схем наиболее компактный, но построение таких полиномов предполагает применение поля Галуа.

Для разработки принципиальных схем лучше использовать 3-6 варианты полиномов, поскольку они не требуют построения поля Галуа, причем 5, 6 варианты более предпочтительны.

Рассмотрим примеры.

2 4 3

Для поля GF(8) и порождающего полинома RS(x) = x + a x + a код Рида-Соломона, исправляющего одну ошибку (одну триаду - три двоичных символа) имеет следующие параметры: длина кода n=7, количество     проверочных     символов     p=degRS(x)=2, количествоинформационных символов к=п-р=5. Таким образом, реализуем (7, 5)-код Рида-Соломона, причем числа 7 и 5 означают количество триад двоичных символов.

Кодер этого кода аналогичен кодеру циклического кода Хэмминга. Как и для кодов Хэмминга, кодер систематического кода Рида-Соломона представляет собой схему умножения на полином xP и деления на порождающий полином; кодер несистематического кода Рида-Соломона представляет собой схему умножения на порождающий полином. Отличие в этих кодах - разная интерпретация символа кодового слова и, соответственно, элементов памяти и умножителей на константу.

Схема декодера аналогична декодеру Меггитта для циклического кода Хэмминга, за исключением того, что каждый элемент задержки в данном случае не один элемент памяти, а три. Кроме того, у этой схемы специфические умножители на константу. Именно эти умножители и представляют затруднение при преобразовании функциональной в принципиальную схему. Особенности реализации для кодеров и декодеров одинаковы, поэтому рассматривать их будем на примере декодеров.

2 4 3

Для порождающего полинома RS(x) = x + a x + а  декодер имеет вид, представленный на рисунке 1. In

Т

> 1

з з

л з

/ 3 3     _ J=.

-^-щ 1

"о"

з 3

Проверка на все нули

"'3 I

Да

/ 3

—г

3

-> Out

Рисунок 1 - Первый вариант декодера (7, 5)-кода Рида-Соломона

2 2 3

Для порождающего полинома RS(x) = x + (z + z )*x + z декодер имеет такой же вид за исключением умножителей на константы (рис. 2)

Рассмотрим пример реализации умножителя на константу z3.. Чтобы поставить ему в соответствие схему на двоичных элементах,

23

определим (a2z + a1z + ao)*z mod p(z).

In

7?

Z4Z

у З

2

З з 7"

У 1

/ з

з з

Проверка на все нули

У З

Да

/ З

З

■> Out

Рисунок 2 - Второй вариант декодера (7, 5)-кода Рида-Соломона

a2z5 + aiz4 + a0z3     z3 + z +1

- a2z5 + a2z3 + a2z2-

a1z + (a2+ao)z +a2z    a2z + a1z + (a2+ ao)

- aj_z4 + aiz2 + aiz

(a2 +ao)z3 + (ai +a2)z2 + aiz -(a2 +ao)z3 + (a2 +ao)z + (a2 +ao) (ai +a2)z2 + (ao + ai +a2)z + (a2+ ao)

По полученному остатку от деления строится схема умножителя на константу.

2 i 0

а) б)

Рисунок 3 - а - умножитель на константу z , б - умножитель на

3

константу z на основе сумматоров по модулю два

2

0

Получить остаток R от деления для реализации схемы умножителя на константу (z  + z) можно с помощью нескольких операций

умножения и деления на примитивный полином p(z):

2 2 4 3 2

1. (a2z + aiz + a0)*z = a2z + aiz + a0z

a2z4 + a1z3 + a0z2     z3 + z +1

- a2z4 + a2z2 + a2z-

a1z + (a2+a0)z +a2z   a2z + a1

- aiz3 + aiz + ai

(a2 +a0)z + (a1 +a2)z + a1 остаток R1

2 3 2

2. (a2z + a1z + a0)*z = a2z + a1z + a0z

3 2 3

a2z + a1z + a0z       z + z +1

- a2z3 + a2z + a2 -

a1z + (a2+a0)z+a2 остаток R2

a2

3. R = R1 + R2

(a2 +a0)z2 + (a1 +a2)z + a1

+ ajz~ + (a2+ao)z+a2_

(a2 + a1 + ao)z2 + (a1 + ao)z+(a2 + a1)

X

1

а)

б)

3

Рисунок 4 - а - умножитель на константу z + z, б - умножитель на константу z3 + z на основе сумматоров по модулю два

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

Страницы:
1  2 


Похожие статьи

О Н Дячекно - Аппаратная реализация и корректирующие возможности