У. Питерсон - Коды, исправляющие ошибки (1267328), страница 71
Текст из файла (страница 71)
(В данной главе во всех случаях, кроме особо оговариваемых, этот остаток будет называться синдромом.) для первого символа, взятого с коэффициентом, равным единице, Д вЂ” 1 ортогональных проверочных сумм вычисляются в бг(д) иа схемах умножения и г! — 1 сумматорах. На выходе мажоритарного элемента появляется символ, такой же как на большинстве его входов, или О, если ни один (ненулевой) Фиг. 10.1. Одношаговый мажоритарный декодер для циклического (п, А)-кода элемент поля бр(д) не имеет абсолютного большинства. При сдвиге информационного регистра и генератора синдрома на один разряд вправо найденный символ вычитается из первого принятого информационного символа. Согласно теореме 8.4, генератор синдрома после сдвига содержит синдром принятого слова, сдвинутый на один разряд вправо. Поэтому новыми значениями на входах мажоритарного элемента являются проверочные суммы, ортогональные относительно второго принятого символа, ввиду чего этот символ может быть исправлен точно так же, как и первый.
Очевидно, что для исправления всех ошибок на информационных позициях принятого слова требуется А — 1 сдвигов. Таким же образом могут быть исправлены ошибки и на проверочных позициях. Этот способ декодирования называется декодированием в один пгаг, так как для него необходим лишь один уровень мажоритарной логики.
Понятно, что каждая из д" —" проверочных сумм, вычисляемых декодером, соответствует одному из наборов символов длины и нулевого пространства кода. В раэд. 10.2 и 10,3 рассматривается проблема построения циклических кодов с ббльшим множеством ортогоиальных векторов в нулевых пространствах. В следуюшей ореме приводится одно нз необходимых условий для декодирования (и, А)-кода в один шаг.
Теорема 10.2. Пусть через д обозначено минимальное расстояние кади, двойственного к (и, й)-коду. Тогда число ошибок, которые могут быть исправлены (и, й)-кодом с помощью мажоритарного декодирования в один шаг, ограничено неравенством (10.2) х (й — 1) доказательство. Так как минимальный вес векторов нулевого пространства равен д, то в каждой проверочной сумме должно быть по крайней мере д символов. Один из них появляется во всех проверочных суммах, а каждый из д — 1 остальных символов входит только в одну из проверочных сумм. Поскольку существует и — 1 ошибочных символов, кроме символа, относительно которого проверочные суммы ортогональны, можно построить самое большее (и — 1)/(д — 1) ортогональных проверочных сумм.
Но 1~ не может быть больше половины этого числа. Таким образом, теорема доказана. Ч. т. д. Для многих кодов этот результат весьма значительно ограничивает число ошибок, которые могут быть исправлены при декодировании в один шаг. Например, (23,12)-код Голея, исправляющий тройные ошибки, имеет 1~ = 1. Более существенным является то, что большинство кодов Рида — Соломона исправляет таким способом очень мало ошибок, поскольку код, двойственный к коду Рида — Соломона с расстоянием й, также представляет собой код Рида — Соломона с расстоянием п — й+ 2, которое является большим числом. Например, (63, 32) -код Рида — Соломона над 6Р(2ь) имеет д = 32, д = ЗЗ, но 11 = О. Тем не менее существует ряд представляющих интерес циклических кодов, у которых является большим по сравнению с [(й — 1)/2К такие коды будут кратко рассмотрены ниже. Коды„у которых 11 =..
((й — 1)!21, яазываются полностью ортогонализуемыми в один шаг. Пример. Двоичный циклический (7, 3) -код Хэмминга имеет й 4 и д = 3. Пусть й(Х) = Хг+ Хг+ 1; тогда д(Х) = (Х+ + 1) (Хг+Х+1) = Ха+ Х'+Х'+1. Проверочная матрица кода 1011000 н Трт| 1 1110100 4 1100010 0110001 Так как перед вычислением синдрома принятая искаженная комбинация умножается на Х4, то ошибка в старшем разряде добавляет ровленные вмлиионние волы инолрм г1 символы Фиг. 10лк Одношаговый мажоритарный декодер для двоичного циклического 17, 3)-кода Хаммннга. (1000) к синдрому. Проверочные суммы, соответствующие первой строке, сумме первой и второй строк и сумме первой, третьей и четвертой строк, ортогональны относительно первого информационного символа.
В этом примере 11 — — ((с/ — 1)/2) = 1, и поэтому код полностью ортогонализуем. Декодер для этого кода показан на фиг. 10.2. Код является примером проективно-геометрических кодов, рассматриваемых в равд. 10.3. Заметим, что первый символ синдрома входит в каждую ортогональную проверочную сумму. Прибавление фиксированного элемента из 6Р(г/) к символу на каждом входе мажоритарного элемента эквивалентно прибавлению этого элемента к выходному символу. Согласно теореме де Моргана для д=2, ша1 (Хь Хм Ха) = = та1(ХиХмХа), где черта означает дополнение.
Конечно, последняя операция проще, и поэтому в некоторых случаях декодер, изображенный на фиг. 10.1, может быть немного упрощен. Упрощенный вариант декодера для (7,3)-кода, рассмотренного в предыдущем примере, показан на фиг. 10.3. Если относительно линейной комбинации ошибочных символов е можно построить не менее с( — 1 ортогональных проверочных сумм, то из рассуждений, аналогичных доказательству теоремы 10.1, следует, что значение е равно значению, принимаемому большинством проверочных сумм (или О, если ни один ненулевой элемент 6г(д) не имеет абсолютного большинства), при условии, что произошло не более ((с( — 1)/2) ошибок.
Таким образом, может быть определено некоторое число линейных комбинаций символов вектора ошибок, которые вместе с уже известными д" —" проверочными суммами и их линейными комбинациями образуют более и 1 — — — если г) четное, й 2 и+1 1 — — — если Й нечетное. 3+1 2 (10.3) 1с ~( сре ггфор скмголы ггкгые мпиисеные голы Фвт. 10.3. уорок1екный вариант декодера, изображенного ка фкг. 10.2. ~ирокое множество проверочных сумм. Это новое множество будет ве т векторным пространством, содержащим нулевое пространство кода в качестве собственного надпространства. Если такую процедуру можно осуществить несколько раз, получая каждый раз ие менее д — 1 ортогональных проверочных сумм, до тех пор, пока не будет получено множество проверочных сумм„ортогональных относительно некоторого ошибочного символа, то значение этого символа может быть определено правильно.
Если это возможно выполнить для всех и ошибочных символов, то говорят, что код ортогонализуем в Т. шагов, где 1.— число необходимых уровней мажоритарной логики. Очевидно, что если код циклический и произошло не более !!а — 1)/2) ошибок, то декодирование будет правильным, когда может быть правильно декодирован хоти бы один символ. Эта процедура декодирования была сначала разработана для кодов Рида — Маллера, описываемых в равд. 5.5, и поэтому называется также алгоритмом Рида.
Не удивительно, что декодирова. нне в Т. шагов обладает большими возможностями, чем декодирование в один шаг. Теорема 10.3. Пусть д — минимальное расстояние кода, двоисгвенного к 1п,я)-коду, Тогда число ошибок !ь, которые могут быть исправлены посредством мажоритарного декодирования в й шагов 1т. е. алгоритма Рида), ограничено неравенствами (-Ю)- -1Л Отсюда непосредственно следует утверждение теоремы. Ч. т. д. На основании этой теоремы для каждого кода можно ожидать исправления алгоритмом декодирования в В шагов примерно в 2 раза большего числа ошибок по сравнению с алгоритмом декодирования в один шаг. Пример. Двоичный пиклический (7,4)-код Хэмминга декодируется в два шага. Если д(Х) = Хз+ Х'+ 1, то проверочная матрица кода , 1011100-1 Н =~11!0010~.
0111001 (10.4) Обозначим вектор ошибок через (см ем..., зз). Проверочные суммы, соответствующие первой строке, а также сумме первой и второй строк, ортогональны относительно суммы з6+ ем Обозначим эту сумму через зь Суммы, соответствующие сумме первой„второй и третьей строк и сумме первой и третьей строк, ортогональны относительно за+ е~ — — зь (Напомним о предварительном умножении на Хз.) Если произошло не более одной ошибки, можно правильно определить з и зм Однако з, =з6+ем зз=е6+е~ ортогональны относительно ем и поэтому ошибочный символ может быть определен на втором уровне мажоритарной логики. Декодер для этого кода показан иа фиг.
10.4. Этот код как пример евклидово-геометрического кода будет рассмотрен в равд. 10.2. Доказательство, Для того чтобы исправить 1ь ошибок, нужно иметь возможность строить ие менее 21ь проверочных сумм, ортогональиых относительно множества символов, общих для всех сумм. Обозначим число символов в этом множестве через В, Очевидно, В ( (д/2). В противном случае сумма векторов, соответствующих любым двум проверочным суммам, ортогональным относительно множества символов В, которая является также вектором нулевого пространства кода, будет иметь вес меньше д. Так как указанные 21ь проверок имеют не более (Ы/2] общих символов и содержат ие менее И символов, то должно выполняться неравенство яяяюе лри ияяюраюй яямяаяы силюаяи Фиг.
10,4. Двухшаговый мажоритарный декодер дли двоичного циклического (?, 4)-кода Хэмминга. Учитывая, что первый символ синдрома входит во все ортогональные проверочные суммы, мажоритарные схемы, как и при одношаговом декодировании, могут быть несколько упрощены. Теоремы 10.2 и 10.3 показывают, что возможности и область применения мажоритарного декодирования довольно ограничены. Для того чтобы обойти эти ограничения, было предложено несколько модификаций основного алгоритма, которые описываются в равд. 10.4. 10.2. Евклидова-геометрические коды Коды Рида — Маллера, рассмотренные в равд. 5.5, имеют инте. ресную геометрическую интерпретацию: каждому из 2 символов кодового вектора можно однозначно поставить в соответствие одну из 2~ точек некоторой лт-мерной евклидовой геометрии над бг'(2), обозначаемой как Е61гп,2)').
Код Рида — Маллера г-го порядка '1 Евклицовы геометрии подробно описаны в книгах 125, 41). 1)Х "э="м. Я, ХЯ',=ЯР,, Очевидно, что и поэтому циклический сдвиг любого слова кода второго порядка также будет кодовым словом. Нетрудно показать, что все коды Рида — Маллера эквивалентны циклическим кодам, удлиненным на один символ, который задает проверку на четность. Евклидово-геометрические коды (ЕО-коды) являются естественным обобщением циклических кодов Рида — Маллера.
Фактически речь идет о обобщениях по трем направлениям. Во-первых, можно рассматривать коды с символами из ОР(р), где р— простое число, имеющее длину р '. Во-вторых, что более важно, р" кодовым точкам можно поставить в соответствие различные геометрии. Например, если т' = злт, з Ф 1 и т Ф 1, то геометрии ЕО(т',р), ЕО(т,р') и ЕО(з.р'") могут быть использованы для построения удлиненных циклических кодов длины р"', допускающих мажоритарное декодирование.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
