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

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

ОГЛАВЛЕНИЕ

Следующая >>

равны нулю.
Утверждение, что минимальное кодовое расстояние d m i n кодов
Хэмминга с проверкой на четность равно 4, следует непосредственно
из определения веса кодовых слов. В самом деле, так как минималь-
ный вес всех векторов кода Хэмминга, за исключением нулевого,
равен 3, то дополнительный разряд проверки на четность увеличи-
вает этот минимальный вес до 4. Расширенный код Хэмминга также
является линейным и его минимальное расстояние dm\a = 4.
Прежде чем говорить о декодировании кодов Хэмминга с провер-
кой на четность, напомним два возможных режима декодирования
обычных кодов Хэмминга.

1. Режим обнаружения ошибок.
Глава 2. Линейные блоковые коды

Если синдром s ф 0, то декодер выдает сигнал ошибки. Так как
rfmin кода Хэмминга равно 3, то ошибки кратности < 2 всегда
обнаруживаются.

2. Режим коррекции ошибок.
Если синдром s ф О, то декодер всегда исправляет один из раз-
рядов кодового слова (так как код Хэмминга является плотно-
упакованным сферами радиуса t = 1). Таким образом, декодер
исправляет все однократные ошибки.

Из всего вышесказанного видно, что код Хэмминга или только
обнаруживает вес ошибки кратности не выше 2, или только исправ-
ляет все однократные ошибки.
Теперь перейдем к кодам Хэмминга с проверкой на четность. Так
как dmm таких кодов равно 4, то в режиме обнаружения фиксиру-
ются все ошибки кратности 3 и ниже. Режим же коррекции ошибок
можно существенно улучшить, благодаря наличию в кодовых словах
дополнительного разряда проверки на четность.
Прежде всего заметим, что процесс исправления одиночных оши-
бок во всех разрядах, исключая проверочный, ничем не отличается
от обычного кода Хэмминга. Таким образом, одиночная ошибка все-
гда может быть исправлена. (В этом случае, признаком одиночной
ошибки в проверочном разряде, является равенство нулю всех ком-
понент синдрома s за исключением so, которая равна единице). С
другой стороны, заметим, что при одиночной ошибке всегда выпол-
няется равенство so = 1- При двукратной же ошибке, компонента ?о
всегда равна «О». Таким образом, получаем следующий улучшенный
алгоритм коррекции ошибок в расширенном коде Хэмминга.

1. Если So = 1JT 0 производится исправление одиночной ошибки.

2. Если so = 0 и I ф 0, то считаем, что в канале произошла неис-
правляемая ошибка и принятое слово или должно быть стерто,
или в обратный канал должен быть подан сигнал переспроса.

Таким образом, код Хэмминга с проверкой на четность способен
или только обнаруживать ошибки, кратности не выше трех, или ис-
правлять все одиночные ошибки и, одновременно, обнаруживать все
двукратные.
2.5. Приложение: Поля Галуа

2.5. Приложение: Поля Галуа
Множество А образует поле, если для любых элементов а,, а,, ак ? А
определены операции сложения «+» и умножения «х» и выполня-
ются следующие аксиомы:
Сложение «+»

(А1) Замкнутость ai + a,j ? A

(А2) Ассоциативность {щ + aj) + ак = сц + {aj + ак)
(A3) Существование единственного нулевого элемента 0 € Л, тако-
го, что 0 + at = ui
(А4) Обратный элемент {—ai) ? А такой, что (—а) + а^ = О

(А5) Коммутативность ец + о,- = a,j + сц,

Умножение «х»

(Ml) Замкнутость о, х aj ? А
(М2) Ассоциативность (а* х aj) х ак = щх (а^ х ак)
(МЗ) Существование единственного единичного элемента 1 ? А та-
кого, что 1 х Oi = ai
(М4) Обратный элемент aj1 x а, = 1
(М5) Коммутативность а^ х aj = aj x <ц

Сложение и умножение

(D) Дистрибутивность а* х (а^ + ак) = aj.x а^ + a; x в^

Из перечисленных выше аксиом следуют важнейшие правила ариф-
метики, справедливые в любом поле:
Для 0,1, а, Ъ, с ? А имеет место

1. а + 0 = 0 => а = 0

2. а , Ь ^ 0 О ахб^О

3. а / 0 и а х Ь = 0 => 6 = 0
4. -(а х 6) = (-а) х 6 = а х (-6)
Глава 2. Линейные блоковые коды

5. а / О и а х Ь = а х с => Ь = с.

Отметим также, что операции сложения и умножения имеют об-
ратные операции: вычитания и деления, причем, вычитание опреде-
l
ляется как а — Ь = а + (—6), а деление - как а -г- Ь = а х b˜ .
Неподготовленного читателя может смутить и даже испугать
столь громоздкое аксиоматическое построение алгебраической струк-
туры, называемой полем. Однако, эти страхи должны довольно
быстро исчезнуть после того, как мы убедимся, что множество ра-
циональных чисел образует поле. Напомним, что множество рацио-
нальных чисел содержит все положительные и отрицательные целые
числа (включая ноль), а также все числа вида п/т, где п,т- целые
и т ф 0. Операциями сложения, вычитания, умножения и деле-
ния в ноле рациональных чисел являются обычные арифметические
операции, которые мы изучали еще в начальной школе. Нетрудно за-
метить, что эти операции удовлетворяют всем перечисленным выше
аксиомам.
Расширениями ноля рациональных чисел являются ноля веще-
ственных и комплексных чисел, они также содержат бесконечное
множество элементов.
Так как в каналах связи множество передаваемых сигналов все-
гда конечно, основой теории кодирования являются поля, содержа-
щие конечное число элементов (поля Галуа). Простейшим полем Га-
луа является двоичное ноле GF(2), операции в котором (сложение
и умножение) выполняются по правилам арифметики «по модулю
2». Нетрудно заметить, что правила арифметики по mod 2 удовле-
творяют всем вышеперечисленным аксиомам (с учетом того, что об-
ратным элементом к «1» по сложению и умножению является сама
,1»).
В высшей алгебре доказывается, что число элементов q конечного
поля всегда удовлетворяет условию

Я = Рт, (2-55)

где р - простое, а т = 1,2
Другими словами, если число элементов q некоторого множества
не удовлетворяет условию (2.55), то для этого множества невозмож-
но определить операции сложения и умножения, удовлетворяющие
аксиомам поля. Так, например, невозможно образовать ноле с чис-
лом элементов, равным 6, 10, 12, 14 и т.д., но можно построить иоле,
с числом элементов, равным 2, 3, 4, 5, 7, 8, 9, 11 и т.д.
I57J
2.5. Приложение: Поля Галуа

Таблица 2.4. Операции сложения и умножения в GF(5).

+ 1 1
0 2 4 2
3 0 3 4
X

1
0 0 2 3 4 0 0 0 0 0 0
1 1 2 1 1
4 2 4
3 0 0 3
2
2 3 4 1 2 4 1
0 2 0 3
1
3 3 4 0 2 3 0 3 1 4 2
4 4 0 1 1
2 3 4 0 4 3 2




Наиболее просто операции сложения и умножения выполняются
в поле с числом элементов, равным простому числу (т = 1 ) . Здесь
они определены как операции сложения и умножения по mod p, a
сами элементы образуют последовательность-чисел

{0,1,2,...,р-1}. (2.56)

Для примера, в таблице 2.4. приведены результаты сложения и
умножения всех нар элементов^, bj 6 {0,1,2,3,4}, т.е сумма а* +
bj( mod 5) и произведение а*-ft,( mod 5). Непосредственной провер-
кой можно убедиться в выполнении аксиом (А1) (А5), (Ml) - (М5)
и (D) для операций сложения и умножения. Таким образом, множе-
ство элементов a € {0,1,2,3,4} с операциями сложения и умноже-
ния, заданными табл. 2.4, образуют ноле GF(5).
В теории полей Галуа доказывается следующая, очень важная
теорема.

Теорема 2.5.1. В поле Галуа GF(p), содержащем q элементов, су-
ществует но крайней мере один примитивный элемент а такой, что
каждый ненулевой элемент из GF(p) может быть представлен как
некоторая степень а.
Так, в поле GF(5) существует'два примитивных элемента а\ = 2
1 2 3
и а2 = 3, так как 2° = 1, 2 = 2, 2 = 4, 2 ( mod 5) = 3 и 3° = 1,
1 2 3
З = 3, 3 ( mod 5) = 4, 3 ( mod 5) = 2.
Сложнее обстоит дело с построением полей Галуа GF(pm), где
т > 1 (простое число р называется характеристикой поля).
Так как теория кодирования имеет дело, в основном, с нолями
характеристики 2, рассмотрим основные методы построения полей
GF(2m).
Глава 2. Линейные блоковые коды

Прежде всего заметим, что каждый элемент GF(2m) можно пред-
ставить в виде слова длины т над GF(2) или многочлена с двоичны-
ми коэффициентами, степень которого меньше, чем т. Так, напри-
мер, любой элемент о ? GF(23) можно записать как двоичное слово
2
0,20,10,0 или как многочлен а^Х + а\Х + ао, где {a2,«i,oo} ? {0,1}. В
m
этом случае, сложение элементов из GF(2 ) выполняется по правилу
сложения представляющих их многочленов в поле GF(2). Если при
этом умножение элементов мы определим как умножение представ-
ляющих эти элементы многочленов по модулю некоторого заданного
неприводимого многочлена над GF(2) степени т, то тем самым мы
m
построим поле Галуа GF(2 ).

Неприводимым, называется многочлен, неразложимый на произ-
ведение многочленов с коэффициентами из GF{2).
Проводя аналогию с полем GF(p), можно сказать, что роль эле-
ментов GF(p) в поле GF(2m) играют двоичные слова или многочле-
ны степени, меньшей т, а роль простого числа р - неприводимый
многочлен степени т .
Для реализации операций в поле GF{2m) в качестве неприводи-
мого многочлена степени т удобнее выбирать примитивный много-
член.
Примитивным многочленом р(Х) над GF(2) называется непри-
водимый многочлен степени т, такой, что в ноле GF(2m), построен-
ного по модулю р{Х), элемент поля X является примитивным.

В теории полей Галуа доказывается следуюгцая теорема.

Теорема 2.5.2. Для каждого поля Галуа существуют примитивные
многочлены всех степеней.
Таблицы неприводимых и примитивных многочленов над GF(2)
степени, не превосходящей 34, приведены в [11].
4
В качестве примера приведем поле Галуа GF(2 ) (табл. 2.5). Для
его построения был выбран примитивный многочлен четвертой сте-
пени ХА + X + 1. Из таблицы видно, что степени примитивного эле-
4
мента а = X образуют все множество ненулевых элементов GF(2 ).
В таком представлении операция умножения в ноле GF{2i) реализу-
ется очень просто. Пусть, например, нам требуется найти произведе-
ние элементов (1011) • (1010). Из таблицы 2.5 находим, что элемент
(1011) можно представить в виде a 7 , a (1010) в виде а 9 . Из этого
следует, что (1011) • (1010) = а 7 • а 9 = а ( 7 + 9 ) m o d 1 5 = а 1 . Используя
159]
2.5. Приложение: Поля Галуа

Таблица 2.5. Представление поля GF(2 4 ) (Таблица антило-
гарифмов).

1 -(0001)
=
а1 а -(0010)
а2
-
2
:а =(0100)
а3
а3 - =(1000)
а4 - а t1 =(0011)


а2
а5 -(ОНО)
=
+а 2
3
а6 - а =(1100)
+а +1
3
7
- а

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

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

ОГЛАВЛЕНИЕ

Следующая >>