Вернер М. Основы кодирования (2004) (1151849), страница 21
Текст из файла (страница 21)
В самом деле, так как минимальный вес всех векторов кода Хэмминга, за исключением нулевого,равен 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=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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
