Вернер М. Основы кодирования (2004) (1151882), страница 21
Текст из файла (страница 21)
Таккак dmm таких кодов равно 4, то в режиме обнаружения фиксируются все ошибки кратности 3 и ниже. Режим же коррекции ошибокможно существенно улучшить, благодаря наличию в кодовых словахдополнительного разряда проверки на четность.Прежде всего заметим, что процесс исправления одиночных ошибок во всех разрядах, исключая проверочный, ничем не отличаетсяот обычного кода Хэмминга. Таким образом, одиночная ошибка всегда может быть исправлена. (В этом случае, признаком одиночнойошибки в проверочном разряде, является равенство нулю всех компонент синдрома s за исключением so, которая равна единице). Сдругой стороны, заметим, что при одиночной ошибке всегда выполняется равенство so = 1- При двукратной же ошибке, компонента ?овсегда равна «О».
Таким образом, получаем следующий улучшенныйалгоритм коррекции ошибок в расширенном коде Хэмминга.1. Если So=1JT0производится исправление одиночной ошибки.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 = 02. а , Ь ^ 0=> а = 0Оахб^О3. а / 0 и а х Ь = 0=> 6 = 04. -(а х 6) = (-а) х 6 = а х (-6)Глава 2. Линейные блоковые коды5. а / О и а х Ь = а х с=> Ь = с.Отметим также, что операции сложения и умножения имеют обратные операции: вычитания и деления, причем, вычитание определяется как а — Ь = а + (—6), а деление - как а -г- Ь = а х b~l.Неподготовленного читателя может смутить и даже испугатьстоль громоздкое аксиоматическое построение алгебраической структуры, называемой полем.
Однако, эти страхи должны довольнобыстро исчезнуть после того, как мы убедимся, что множество рациональных чисел образует поле. Напомним, что множество рациональных чисел содержит все положительные и отрицательные целыечисла (включая ноль), а также все числа вида п/т, где п,т- целыеи т ф 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 и т.д.2.5. Приложение: Поля ГалуаI57JТаблица 2.4. Операции сложения и умножения в GF(5).+01234X01234001234000000112340101234202413223401334012303142440123404321Наиболее просто операции сложения и умножения выполняютсяв поле с числом элементов, равным простому числу (т = 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и а2 = 3, так как 2° = 1, 2 1 = 2, 22 = 4, 23( mod 5) = 3 и 3° = 1,З 1 = 3, 32( mod 5) = 4, 33( mod 5) = 2.Сложнее обстоит дело с построением полей Галуа GF(pm), гдет > 1 (простое число р называется характеристикой поля).Так как теория кодирования имеет дело, в основном, с нолямихарактеристики 2, рассмотрим основные методы построения полейGF(2m).Глава 2.
Линейные блоковые кодыПрежде всего заметим, что каждый элемент GF(2m) можно представить в виде слова длины т над GF(2) или многочлена с двоичными коэффициентами, степень которого меньше, чем т. Так, например, любой элемент о £ GF(23) можно записать как двоичное слово0,20,10,0 или как многочлен а^Х2 + а\Х + ао, где {a2,«i,oo} £ {0,1}. Вэтом случае, сложение элементов из GF(2m) выполняется по правилусложения представляющих их многочленов в поле GF(2).
Если приэтом умножение элементов мы определим как умножение представляющих эти элементы многочленов по модулю некоторого заданногонеприводимого многочлена над GF(2) степени т, то тем самым мыпостроим поле Галуа GF(2m).Неприводимым, называется многочлен, неразложимый на произведение многочленов с коэффициентами из GF{2).Проводя аналогию с полем GF(p), можно сказать, что роль элементов GF(p) в поле GF(2m) играют двоичные слова или многочлены степени, меньшей т, а роль простого числа р - неприводимыймногочлен степени т .Для реализации операций в поле GF{2m) в качестве неприводимого многочлена степени т удобнее выбирать примитивный многочлен.Примитивным многочленом р(Х) над GF(2) называется неприводимый многочлен степени т, такой, что в ноле GF(2m), построенного по модулю р{Х), элемент поля X является примитивным.В теории полей Галуа доказывается следуюгцая теорема.Теорема 2.5.2.
Для каждого поля Галуа существуют примитивныемногочлены всех степеней.Таблицы неприводимых и примитивных многочленов над GF(2)степени, не превосходящей 34, приведены в [11].В качестве примера приведем поле Галуа GF(24) (табл. 2.5). Дляего построения был выбран примитивный многочлен четвертой степени ХА + X + 1. Из таблицы видно, что степени примитивного элемента а = X образуют все множество ненулевых элементов GF(2 4 ).В таком представлении операция умножения в ноле GF{2i) реализуется очень просто. Пусть, например, нам требуется найти произведение элементов (1011) • (1010). Из таблицы 2.5 находим, что элемент(1011) можно представить в виде a 7 , a (1010) в виде а 9 . Из этогоследует, что (1011) • (1010) = а 7 • а 9 = а ( 7 + 9 ) m o d 1 5 = а 1 . Используя2.5.
Приложение: Поля Галуа159]4Таблица 2.5. Представление поля GF(2 ) (Таблица антилогарифмов).1=1а2:аа-а3-а4-а5=6а7са-аа=(1000)аа3=(1100)+а2+а2-а3+а 2+аа12--а3+а 2+а32=аа14-а315-аа+а=(1011)! 1 =(0101)а1113+1+аа3а=(0011)-(ОНО)+а 210аt1+аа2а-=(0100)а8а9233-(0001)-(0010)=(1010)1-1--(0111)-(1110)-1-(1111)+1-(1101)+1= (1001)1=а°табл. 2.5 еще раз, определяем, что а1 соответствует элементу (0010).Окончательно получаем (1011) • (1010) = (0010).При программной реализации умножения в полях Галуа, как правило, используют так называемые таблицы логарифмов и антилога4рифмов. Таблица антилогарифмов ноля. GF(2 ) совпадает с табл.2.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
