У. Питерсон - Коды, исправляющие ошибки (1267328), страница 54
Текст из файла (страница 54)
ступившни из буферного устройства, исправлен, то синдром также должен быть изменен путем подачи выхода логической схемы на линию обратной связи генератора синдрома. (См. фиг. 8.5.) В результате синдром будет соответствовать измененному полученному вектору — обстоятельство, которое в дальнейшем обсуждается более подробно. 5. Второй и третий шаги повторяются до тех пор, пока полученный вектор не будет целиком считан из буферного устройства.
Для каждого символа, считываемого из буферного устройства, производится сдвиг на один разряд вправо содержимого как буферного устройства, так и генератора синдрома. В соответствии с теоремой 8.7 содержимое генератора синдрома после сдвига соответствует синдрому сдвинутой комбинации ошибок. Таким образом, выход логической схемы в каждый момент времени указывает значение ошибочного символа, которое должно быть прибавлено к следующему полученному символу. 6.
После того как полученное слово считано из буферного устройства, будут исправлены все ошибки, если они соответствуют комбинации ошибок, на которую рассчитана логическая схема; при этом содержимое генератора синдрома должно состоять из одних нулей. Если содержимое генератора синдрома в конце процесса отлично от нуля, то это значит, что обнаружена ошибка, которая не может быть исправлена посредством данной логической схемы. Таким образом, декодер Меггита способен декодировать сразу лишь одно из полученных слов, причем в декодирующей схеме сдвиги проводятся в моменты поступления символов, т. е. декодирование производится с линейной скоростью.
Существует несколько способов преодоления этого ограничения: 1. Можно предусмотреть дублирующие декодеры; при этом все схемы могут действовать с линейной скоростью. 2. Можно предусмотреть второе буферное устройство, состоящее из а ячеек. Когда будут исправляться ошибки в слове В, слово А будет считываться, а слово С поступит в это дополнительное буферное устройство. По окончании декодирования роли двух запоминающих устройств меняются. В этом случае декодер должен действовать не менее чем с удвоенной линейной скоростью. 3. Если целое слово может быть декодировано за то время„которое проходит между поступлением отдельных символов, то нужно лишь немного дополнительного оборудования.
В этом случае декодер проводит все п сдвигов в промежутке времени между поступлениями последнего символа слова А и первого символа слова В. Тот факт, что прибавление с помощью обратной связи исправляющего символа, например — а„к содержимому генератора синдрома исправляет синдром, может быть объяснен следующим образом. Первоначально генератор синдрома содержит многочлен з(Х), соответствующий г(Х). Поправка — а прибавляется (после сдвига) к Хг(Х). 11осле этого новое содержимое регистра должно быть равно Х -"(Хг(Х) — а) по модулю а(Х), так как синдром для и равен также — а. Это значит, что содержимое генератора синдрома должно быть изменено путем прибавления к нему — аХ -х по модулю й" (Х). Прибавление — а посредством обратной связи реализует эту операцию с минимальным количеством дополнительного оборудования.
Предположим, что полученное сообщение принадлежит смежному классу некоторой исправимой комбинации ошибок. Для всех элементов этого смежного класса синдром одинаков. Когда считывается разряд, соответствующий первому ненулевому символу в образующем смежного класса, то на выходе комбинационной схемы появляется тот же самый символ, но с противоположным знаком, который прибавляется к символу, поступающему на выход и к содержимому генератора синдрома посредством схемы обратной связи. В результате н полученное сообщение, и синдром «исправляются» таким образом, что после исправления эти много- члены соответствуют тому смежному классу, который содержит первоначальный образующий смежного класса с измененным на нуль первым ненулевым символом.
Последний вектор, будучи потомком первоначального образующего смежного класса, по предположению (1) является также образующим смежного класса. Таким образом, когда символ разряда, соответствующий первому ненулевому символу, появится на выходе буферного устройства, он также будет «исправлен» комбинационной схемой. В конце концов в регистре синдрома останутся одни нули, и полученное сообщение будет превращено в кодовое слово, соответствующее сумме полученного сообщения и образующего смежного класса, как и должно быть.
Декодер Меггита в целом легко поддается практическому осуществлению, быть может, за исключением комбинационной логической схемы. Возможность практической реализации этого метода при декодировании некоторого определенного кода целиком зависит от сложности этой логической схемы. Для всех кодов, исправляющих пакеты ошибок, которые рассматриваются в гл. 11, эта схема является очень простой.
Мажоритарно-декодируемые коды, описываемые в гл. 19, вызывают интерес, поскольку для них логическая схема может быть реализована при помощи умеренного количества оборудования. С другой стороны, оказывается, что для БЧХ-кодов, рассматриваемых в гл. 9, эта комбинационная схема достаточно сложна.
Была предпринята попытка найти для некоторых относительно коротких БЧХ-кодов минимальную двухступенчатую логическую схему, используя метод минимизации Квина — Мак-Класки (215]. Исследовались, в частности, (15,7)- и (31,21)-коды БЧХ, исправляющие двойные ошибки, (15, 5)- и (31, 16)-коды БЧХ и (23, 12)- код Голея, исправляющие тройные ошибки. Полученные схемы не оказались существенно проще уже известных.
Например, для (23,12)-кода минимальная двухступенчатая логическая схема содержит примерно на одну треть слагаемых меньше, чем первоначальная схема. Дальнейшая факторизация сводит эту величину к одной второй или немного меныпе. Этому коду соответствуют 1 одиночная ошибка, 22 двойные ошибки и 22 >с',21 = 462 тройные ошибки, последними компонентами которых является !.
В результате получается, что в первоначальном выражении должно быть всего 485 слагаемых. Даже половина этого числа требует все еще слишком дорогой логической схемы. К счастью, существует существенно более простой метод реализации декодирования БЧХ-кодов, который рассматривается в следующей главе.
Кроме того, код Голея можно более эффективно декодировать методом вылавливания ошибок, который описывается ниже в этом разделе. Коды Хэмминга при помощи декодера Меггита можно декодировать очень легко. Первый столбец проверочной матрицы И двоичного кода Хэмминга равен а"-', где а — примитивный элемент поля 6Р(2") >и и = 2 — !. Если единственная ошибка появилась в разряде наивысшего порядка, то состоящий из и символов синдром совпадает с двоичным представлением элемента сс"-1! если единственная ошибка появилась где-то еще, то синдром не совпадает с этим представлением. Поскольку в генераторе синдрома декодера Меггита истинный синдром умножается на Х -" = Х", то в регистре содержится а'" ', синдром для Х -'.
В двоичной форме этот синдром равен просто набору (000 ... 001) длины т. Таким образом, логическая схема для этого декодера Меггита представляет собой просто элемент «И» с т входами, на выходе которого появляется 1 для этого и только для этого синдрома. Пример. Многочлен д(Х) = Х4+Х+1 порождает (15, !1)-код Хэмминга. Если появилась комбинация ошибок, равная Х'«, то содержимое генератора синдрома равно Х«.Хм по модулю д(Х), т. е. Хв; двоичное представление этого синдрома просто равно 000 1. Декодер Меггита для этого кода показан на фиг. 8.6. Недвоичные коды Хэмминга также можно просто декодировать прн помощи декодера Меггита.
Комбинационная схема любого типа должна обнаруживать имеющиеся в разрядах синдрома низших порядков лт — 1 нулей. Когда это произойдет, значение ошибки появится в первом разряде. Синдром '), вычисленный по полученному многочлену г(Х) с использованием регистра сдвига, содержащего и — гг ячеек ') Заметим, что »тот синдром отличвется от введенного ранее синдроме тем> что ои предварительно умиажен ив Х"-". Фиг. 8.6. Декодер Меггита для (15, 11)-кода Ханнинг . (фиг.
8.2), будет иметь вид з(Х) = Х" аг (Х) — г1(Х) д(Х), где д(Х) — частное от деления (с остатком) Х"-"г(Х) на д(Х). Вычитая этот синдром из разрядов высшего порядка полученного многочлена, получаем г (Х) — Хаа (Х) = г (Х) — Х"г (Х) + и' (Х) д (Х) = и' (Х) д (Х), так как Х" — 1 = О. Таким образом, в результате вычитания синдрома из разрядов наивысших порядков полученного ьшогочлена всегда получается кодовый многочлен.
Предположим теперь, что все оп|ибки действительно появились в а — А наивысших разрядах многочлена г(Х). Результатом вычитания синдрома из разрядов высших порядков «(Х) будет кодовое слово, А низших разрядов которого совпадают с соответствующими разрядами г(Х) и, следовательно, переданного многочлена 1(Х).
Итак, в многочлене г(Х) — Х"з(Х) — 1(Х) коэффициенты при А низших степенях равны нулю, и поэтому этот многочлен имеет вид Ха)(Х), где степень 1(Х) меньше чем и — А. Но поскольку это разность между двумя кодовыми многочленами, то она должна делиться на д(Х). Это возможно, если только Х"1(Х) = О. Следовательно, ,(Х) =1(Х)+Х' (Х), и поскольку многочлен г(Х) является суммой многочлсна 1(Х) и комбинации ошибок, то многочлен Х"з(Х) должен совпадать с этой комбинацией ошибок, Таким образом, справедлива следующая теорема; Теорема 8.8. Если в качестве синдрома для г(Х) выбирается остаток от деления Х"-кт(Х) на д(Х) и все ошибки имеют место в и — А высших степенях т(Х), то ненулевые символы комбинации ошибок появляются в соответствующих разрядах синдрома.
Известен вариант метода декодирования Меггита, называемый методом вылавливания ошибок (262), в основе которого лежит только что доказанная теорема. Предположим, что любой образующий смежного класса содержит в некоторых разрядах А последовательных нулей. (В силу циклической природы кода эти А пулей могут располагаться частично в начале и частично в конце кодового слова.) Тогда в результате одновременных сдвигов полученного вектора и синдрома на некотором этапе эти нули выстроятся в ряд в разрядах низшего порядка регистра буферного устройства, а в разрядах высшего порядка появится целиком комбинация ошибок. Тогда по теореме 8.8 эта же комбинация ошибок появится в регистре синдрома.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
