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

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

ОГЛАВЛЕНИЕ

Следующая >>

с =(1011)

а8 а2 ! 1 =(0101)

а3
а9 - =(1010)


2
10
- а
а --(0111)
1-1
+а 2 +а
а3
а11 - -(1110)
+а 2 +а
а3
--
а12 -1 -(1111)
2
+а +1
3
13
= а
а -(1101)
а3
а14 +1
- = (1001)

=а°
1
15
а -




табл. 2.5 еще раз, определяем, что а1 соответствует элементу (0010).
Окончательно получаем (1011) • (1010) = (0010).
При программной реализации умножения в полях Галуа, как пра-
вило, используют так называемые таблицы логарифмов и антилога-
рифмов. Таблица антилогарифмов ноля. GF(2 4 ) совпадает с табл.
2.5. Используя эту таблицу, очень легко определить двоичный экви-
валент элемента а* по заданному г, 0 < г < 14. Таблица логарифмов
(табл." 2.6), наоборот, позволяет быстро найти степень примитивного
элемента а по его двоичному представлению.
Так как операция деления в полях Галуа эквивалентна умноже-
нию на обратный элемент, весьма полезной при вычислениях ока-
зывается таблица обратных элементов (табл. 2.7), которая для поля
GF(2 4 ) строится следующим образом. Пусть, например, нам нуж-
но найти обратный элемент к (1010). По таблице логарифмов нахо-
дим, что (1010) соответствует а 9 . Обратным элементом к а 9 являет-
ся а 1 5 " 9 = а 6 . По таблице антилогарифмов находим, что двоичным
160 Глава 2. Линейные блоковые коды

4
Таблица 2.6. Таблица логарифмов элементов GF(2 ).

шо 1111
0001 0010 ООН 0100 0101 ОНО 0111 1000 1001 1010 1 1 1100 1101
01
0 1 4 2 8 5 10 3 ы 9 7 6 13 11 12
а а а а а а а а а а а а а а а




эквивалентом а 6 является (1100). Таким образом, окончательно по-
лучаем (1010)-1 = (1100).
При небольших значениях т для ускорения умножения при про-
граммной реализации можно построить таблицу умножений элемен-
тов ноля GF(2m) размерности 2т х 2т. После того, как все необходи-
мые арифметические таблицы построены, можно заменить двоичные
обозначения на целочисленные.
Реализация операции сложения (и совпадающей с ней операции
вычитания) элементов в поле GF(2m) не представляет проблем. Сло-
жение элементов из GF(2 m ) сводится к покомпонентному сложению
их двоичных представлений по модулю 2. Так, например, в ноле
GF(2 4 ) (ООН) + (1101) = (1110).
Таблица 2.7. Таблица обратных элементов ноля GF(24).

0001 0010 0011 0100 0101 0110 0 Ш 1000 1001 1010 1011 1100 1101 1110 1111

оно 1111 0010
0001 1001 1110 1101 1011 0111 1100 0101 1010 0100 0011 1000



С подробным обоснованием построения полей GF(2 m ) и исследо-
ванием их алгебраической структуры читатель может ознакомиться
в [5].
В заключение отметим, что при всей кажущейся сложности, ис-
пользование полей Галуа в теории помехоустойчивого кодирования
имеет глубокий математический смысл. Свойства полей Галуа поз-
воляют при построении кодов использовать законы линейной алгеб-
ры, справедливые для полей действительных и комплексных чисел.
Отличие заключается лишь в том, что арифметические операции
необходимо производить но правилам, определенным для данного
конечного поля.
ГЛАВА 3
ЦИКЛИЧЕСКИЕ
КОДЫ


3.1. Введение
Прежде всего покажем, что применение на практике простейших ли-
нейных блоковых кодов с их последующим синдромным декодиро-
ванием связано с чрезмерными техническими затратами. Для этой
цели рассмотрим два примера.
Первым примером является протокол передачи данных по теле-
фонному каналу ISDN-D, в котором используется формат передачи
данных LAPD (Link Asset Procedure on D-channel). Все передаваемые
данные заносятся в отведенные им поля в потоке данных, согласно
стандарту (см. рис. 3.1). Длины полей заданы в байтах (один байт
содержит блок из 8 бит). Под проверочные символы отводится поле
FCS (Frame Check Sequens) длиной 2 байта. С помощью проверочных
сумм производится обнаружение ошибок в поле адреса A (Adress),
поле команд С (Control) и информационном поле I (Information). Та-
ким образом, общая длина блока составляет (2+2-f 260+2) =266 байт
или 2128 бит. При использовании для защиты данных от ошибок
простейшего линейного кода с 16-ю проверочными битами потребо-
валась бы порождающая матрица размерности 2112x2128 и порож-
дающая матрица размерности 16 х 2128.

Байт 1 2 1(2) шах 260 2 1




Р и с . 3.1. Формат передачи данных LAPD с флагом
F=(01111110), полем адреса А, полем команд С
и информационным полем I.


В качестве второго примера рассмотрим формат передаваемых
данных, используемый в стандарте 802.3-CSMA/CD (Carrier Sense
Multiple Access/ Collision Detection) для передачи данных в локаль-
ных сетях связи (Lokal Area Network, LAN) (рис 3.2).

6—795
Глава 3. Циклические коды



Байт
7
Преамбула
1
Разделитель
2(6)
Адрес получателя
Адрес источника 2(6)
64... 1518
Данные




Р и с . 3.2. Формат передачи данных 802.3-CSMA/CD
(Carrier Sense Multiple Access/ Collision Detection).

В этом случае защита информации от помех методами, рассмот-
ренными в предыдущей главе этой книги, также требует использова-
ния кодовых слов очень большой длины и, связанных с этим, чрез-
мерных технических затрат.
Оба примера показывают, что на практике кодируются и декоди-
руются информационные потоки относительно большой длины. При-
меняемые при этом методы контроля ошибок должны быть макси-
мально эффективными. В рассмотренных двух примерах этим тре-
бованиям отвечают двоичные циклические коды.
Циклические коды используются в беспроводной телефонии в
стандарте DECT (Digital Enhanced Cordless Telephony), и в мобиль-
ной связи. В мобильной связи циклические коды применяются как в
стандарте GSM (Global System For Mobile Communication), так и в
стандарте CDMA (Code Division Multiple Access).
Далее будет показано, что, при передаче в стандарте ATM
(Asynchronins Transfer Mode), циклические коды, используемые в
НЕС (Header Error Control), позволяют также обнаруживать ошибки
синхронизации.
Замечание. Последующее изложение материала базируется на /7].
Математические основы формулируются в виде тезисов и по ме-
ре необходимости доказываются. Доказательства иллюстрируют-
ся короткими примерами. Практические применения циклических
кодов поясняются с помощью регистров с обратными связями, ко-
торые выполняют роль кодеров и декодеров. Такое изложение тео-
рии на примерах схемной реализации вначале может показаться
немного непривычным. С другой стороны, детальное усвоение про-
цессов реализации кодирования и декодирования в дальнейшем мо-
жет принести Вам большую пользу. Изучив последующие разделы,
3.2. Определение и свойства двоичных циклических кодов 163;

Вы будете подготовлены к самостоятельной программной реализа-
ции изученных алгоритмов.


3.2. Определение и свойства двоичных
циклических кодов
Циклические коды являются подмножеством линейных кодов. Они
обладают новыми специфическими свойствами, позволяющими упро-
щать процессы кодирования и декодирования. При этом, корректи-
рующая способность циклических кодов в большинстве случаев до-
вольно высока.
Упростив изложение, мы ограничимся описанием только двоич-
ных циклических кодов. Заметим, что операции с компонентами дво-
ичных кодов производятся по правилам арифметики по модулю 2.

Замечание. Двоичные циклические коды образуют линейные век-
торные пространства над полем Галуа GF(2). На практике широ-
ко используются циклические коды с компонентами из расширен-
ных полей Галуа GF(2m). Такими кодами являются коды Боуза-
Чоудхури-Хоквингема (БЧХ) и коды Рида-Соломона (PC). Коды PC,
в частности, используются в проигрывателях компакт дисков.

Линейный (п, к)-код С является циклическим, если циклический
сдвиг любого кодового слова из С также принадлежит коду С.
Рассмотрим кодовое слово

v = (wo,«i,...,u n _i), (3.1)

с компонентами v* е {0,1}. Циклический сдвиг соответствует сдви-
гу всех компонент на один разряд вправо, причем, освободившееся
место слева занимает крайняя правая компонента

(3.2)
vW = (vn-i,vo,vu...,vn-2).

При г-кратном циклическом сдвиге получаем

vW (3-3)
= (t7n_i,...,un_i,i;o,Vi,...,Vn-i-i).

Циклический сдвиг реализуется с помощью регистра сдвига длины
п с обратной связью (рис. 3.3).
Циклические коды можно описать, представив кодовые векто-
ры в виде многочленов. Такое представление позволяет обнаружить
Глава 3. Циклические коды

некоторые дополнительные полезные математические свойства цик-
лических кодов. Использование этих свойств приводит к построению
простых и эффективных процедур кодирования и декодирования.

Регистр сдвига в начальном состоянии




Регистр сдвига на такте 3




Рис. 3.3. Регистр сдвига с обратной связью.

Существует взаимно-однозначное соответствие между кодовым
вектором v = («Oi vii • • • ivn-i) и степенью многочлена п — 1
+ v1X1 + --- + vn^1Xn-1. (3.4)
При необходамости можно переходить от векторного представления
кодового слова к представлению в виде многочлена и наоборот.
Замечание. С математической точки зрения, представление ко-
довых слов в виде многочлена изоморфно линейному векторному
пространству кодовых векторов. При этом, операции с коэффици-
ентами многочленов производятся по привычным правилам ариф-
метики по модулю 2. Можно так же заметить, что степени пе-
ременной X используются только для обозначения места соответ-
ствующей компоненты кодового вектора в регистре сдвига и ника-
кой иной смысловой нагрузки не несут.

Представим циклический сдвиг кодового слова в виде многочлена

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

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

ОГЛАВЛЕНИЕ

Следующая >>