У. Питерсон - Коды, исправляющие ошибки (1267328), страница 75
Текст из файла (страница 75)
Имеется возможность исправить ошибку первого символа. Легче всего это показать на примере одношагового декодирования. Заметим, что результат декодирования будет правильным, если одна из д — ! проверочных сумм, ортогональных относительно первого символа, содержит две дополнительные ошибки. Тогда влияние одной нз ошибок будет устранено; останется только 1 ошибок, и комбинация может быть исправлена. Ошибка е„1 старшей позиции вносит в синдром вклад (0,0„...,0,е,), поскольку принятое слово перед вычислением синдрома предварительно умножаетсн на Х"-». Теперь если через обратную связь ввести — е ~ в генератор синдрома, то будет устранено влияние этой ошибки на синдром.
Эта операция осуществляется на фиг. 10.1 по пунктирной линии в момент сдвига генератора при переходе к декодированию второго информационного символа. Конечно, этот метод применим и при декодировании в Е шагов. деходнрованне с переменным порогом таунсенда н Уелдона 13051 Рассмотрим двоичные коды. Мажоритарный элемент с и входами есть частный случай порогового элемента с т' входами. Символ па выходе этого элемента равен 1, когда Т илн больше входных символов равны 1, н 0 в противном случае, Это подсказывает следующую модификацию процедуры декодирования в один шаг.
Порог устанавливается на наибольшее значение д — 1, и декодер пытается декодировать каждый символ принятого слова. Значение проверяемого символа изменяется тогда и только тогда, когда на соответствующем такте с( — 1 входов мажоритарного элемента равны 1. Если попытка декодера декодировать каждый из символов слова оказывается безрезультатной, величина порога понижается на единицу.
Если и следующий цикл заканчивается безрезультатно, порог снова снижается на единицу. Когда происходит изменение значения какого-либо символа, синдром изменяется и порог сразу же увеличивается на единицу. Порог уменыпается на единицу при завершении каждого цикла и увеличивается на единицу после исправления символа (исключая первоначальное состояние, когда порог имеет значение д — 1). Таким образом, порог постепенно снижается, пока не достигнет своего минимального значения ((д+!)~21, при котором декодирование прекращается.
Хотя никаких аналитических результатов не получено, машинное моделнрование показало, что этот способ позволяет исправлять многие комбинации ошибок веса, большего ((г( — 1)/21 которые не исправляются при обычном декодировании в один шаг.
Конечно, в этом случае для декодирования требуется значительно больше времени. Использованне неортогональных проверочных сумм Эта процедура является альтернативной по отношению к декодированию за 1. шагов и применима к конечно-геометрическим кодам обоих типов. Сложность ее реализации примерно такая же, как и для декодирования за Е шагов, но число исправляемых ошибок при этом несколько меньше.
Этот метод будет рассмотрен на примере проективно-геометрических кодов; для евклндово-геометрических кодов получаются аналогичные результаты. Пусть через М обозначено число г-мерных плоскостей в РС,(л),р ). В соответствии с работой Манна (200) «««! «(«««-Н ! ! «! !) („«г««! «)г«-И ! ! «) ( «««! ! «г). (И— ( «г ! В)г-П ! ! 5+!) ( «)г И ! «г) Каждая г-мерная плоскость состоит из р'"+ р (г-))+ ... + р«+1 точек. Следовательно, число г-мерных плоскостей, проходящих через некоторую точку, равно «г) ( «г ! ргм 'и ! ! р«! !) )))'— ()«ш ! ) «)г«« — И ! ! «! !) (10.26) ( «г«! г««« — и+ + «) (р«г ! р«)г — П ! ! «) ( «г+ «)г — ц) «г ° Далее, каждая г-мерная плоскость содержит (р" + "+р'+!)(р'к-и+ ...
+р'+!) !р'+ !) прямых, или 1-мерных плоскостей. Следовательно, число г-мерных плоскостей, проходящих через некоторую прямую, равно г«(10.27) (р' + ". +р'+ !) (р' "+ " + р«+ !)/(р'+ !) где знаменатель в точности равен числу 1-мерных плоскостей в РС«(т,р ). Рассмотрим й! проверочных сумм относительно некоторого символа, соответствующих г-мерным плоскостям, имеющим одну обпгую точку. Так как две точки задают прямую, по которой пересекаются Х г-мерных плоскостей, то любой другой символ входит в Х сумм. Заметим, что ,т-и ! .! ~«+ ! р'~ — ! (10.28) «к )) ! «! ! р«г В ли произошло не более (йч2)) ошибок, то значение апентраль* ногоъ символа вектора ошибки будет всегда равно значению, определяемому большинством г-мерных плоскостей, а при отсутствии или меньше ошибок, значение информационного символа старшего порядка в соответствии с формулой (10.28) будет правильно определяться большинством неортогональных (» — 1)-мерных плоскостей, пересекаюгцихся в точке, соответствующей этому символу.
Легко доказать, что это число не меныпе чем 1(г(мь — 1)/2]. Следовательно, этим методом может быть исправлено ((г(мь — 1)~2] или менее ошибок. Аналогичные результаты могут быть получены для евклндовогеометрических кодов; используя неортогональные плоскости, частичного исправления можно всегда достигнуть в один шаг, но для полного исправления требуется два шага. Необходимо отметить, что, хотя при помощи этого модифицированного алгоритма любой конечно-геометрический код может быть декодирован в два шага, применение обычного алгоритма, даже требующего более двух шагов, может оказаться более экономичным. Это объясняется тем, что для модифицированного алгоритма требуется мажоритарный элемент на У входов, а У, согласно (10.26), может быть очень большим числом даже для приемлемых значений р, т и ж Пример.
Двоичный циклический (7,4)-код Хэмминга, использованный для иллюстрации декодирования за Т. шагов, может быть декодирован в один шаг. Из выражения (10.4) следует, что 1011100 Н= 11 10010 0 1 11001 Б такого большинства будет равно О, Следовательно, коды могут быть декодированы с помощью одного мажоритарного элемента, хотя и с очень большим числом входов.
Для большинства представляющих интерес значений т, р, » и з величина У/Х, определяемая выражением (10.28),меньше чем дмь — 1, задаваемая выражением (10.25). Прн использовании этого метода приходится жертвовать некоторой частью корректирующей способности кода, особенно для длинных кодов. Используя неортогональные проверочные суммы и декодируя в два шага вместо одного, можно исправить все комбинации из ((г(мь — !)12] или меньшего числа ошибок, На 1-и шаге определяются все (» — 1) -мерные плоскости, которые пересекаются в точке, соответствуюгдей старшему символу кода.
На 2-м шаге из этих (» — 1)-мерных плоскостей при помощи метода, изложенного выше, определяются 0-мерные плоскости. Теперь, если произошло пр умрлр йЛЛГЮ7М Фиг. 10.5. Одношаговый мажоритарный декодер длв двоичного циклического (7,4)-кода Хвммивга, испольвушщнй неортогональные проверочные суммы. Векторы Й„К, + 14в, Й, + 1тв и Й, + Йг+ Йв равны соответственно 10!1100, 1100101, 0101110, 00!0111. Все четыре суммы, соответствующие этим векторам, проверяют ем первый искаженный символ, и ни один другой символ не входит более чем в две суммы. Таким образом, истинное значение еа равно значению, принимаемому большинством сумм, и нулю в «ничейном» случае.
Декодер для этого кода показан на фиг. 1О.Б. Заметим, что этот декодер будет идентичен декодеру, изображенному на фиг. 10.4, если заменить на фиг. 10.5 лгажоритарный элемент с четырьмя входами на три элемента с двумя входами. При использовании неортогональных проверочных сумм не требуется жертвовать корректирующей способностью кода. усоаершеастаоаа«1ие ад«ори«ма Рида даа ЕП-кода« Алгоритм Рида применим к кодам Рида — Маллера и двум их обобщениям — проективно-геометрическим и евклидово-геометрическим кодам. Описываемый усовершенствованный алгоритм применим лишь к ЕМ- и ЕО-кодам. При простом р удлиненный циклический р-ичный евклидовогеометрический код порядка г обладает следующими свойствами: п=р Сопоставляемая геометрия = ЕО (т, р') и, кроме того, многочлен, соответствующий (г+ 1)-мерной плоскости этой геометрии, принадлежит нулевому пространству кода. Теперь, если известны все (г+1)-мерные плоскости, то алгоритм Рида позволяет определить г-мерные плоскости.
Так как любая (г+ 1)-мерная плоскость состоит из р'('+') точек, то ««г «г «(«« — г) Р Р Р р«(г«г И+р«(«г г П+ +р«+ «(«+ц «г « (г+1)-мерных плоскостей пересекаются только по данной г-мерной плоскости. Выше было показано, что эти коды допускают мажоритарное декодирование за г+ 1 шагов.
В том случае, когда т — составное число, можно значительно сократить число шагов. Так как стоимость декодера очень быстро растет с увеличением числа шагов декодирования Т., такое сокращение может привести к значительной зкономии. Усовершенствованный алгоритм действует следующим образом. Первый шаг идентичен первому шагу исходного алгоритма, т. е. г-мериые плоскости находятся решением по большинству пересекающихся (г+!)-мерных плоскостей. Если (г,т) = 1, то второй шаг также идентичен шагу исходного алгоритма, т. е. (г — !)-мерные плоскости находятся из г-мериых плоскостей.
Продолжим эту процедуру до тех пор, пока не определим с-мерные плоскости, где (с, и) = ! Ф.!. Пусть с/! = с' и т/( = т'. Тогда некоторая с'-мерная плоскость в ЕО(лт', р'т) будет также и !с'-мерной плоскостью в ЕС«()т',р'). (Обратное, однако, не всегда справедливо.) Теперь можно рассмотреть геометрию ЕО(т', р'Г), имеющую значительно меньшую размерность, чем первоначальная. Так как все 1с'-мерные плоскости в ЕО((т',р') известны, то тем самым известны и с'-мерные плоскости в ЕС«(т'«р«г). Число с'-мерных плоскостей, ортогональных относительно некоторой (с' — 1)-мерной плоскости, равно «)«««) («и !г Р Р «((га «)+Р«)(га с и+ +рм+ Р Р «(с «) («и как г+ 1 ) с, то нетрудно проверить, что 1' ~ У для любого бора р, г, е, з и т.
Г1одробности здесь опущены. Следующий шаг состоит в определении (с' — !)-мерных плоскостей, если е меоные плоскости уже известны. Если произошло не более 1 = — (у/2) ошибок, то это всегда можно сделать, поскольку Х') Х. Поэтому новый алгоритм не уменьшает корректирующую способность декодера. Если известны (е' — 1) -мерные плоскости, то можно найти (е' 2)-мерные плоскости и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
