3. ПРОСТЫЕ НЕАЛГЕБРАИЧЕСКИЕ МЕТОДЫ ДЕКОДИРОВАНИЯ ГРУППОВЫХ КОДОВ

Методы декодирования групповых кодов можно разбить на две большие группы: алгебраические и неалгебраические. В основе алгебраических методов лежит решение систем уравнений, задающих расположение и значение ошибок. При неалгебраических методах так же цель достигается с помощью простых структурных понятий теории кодирования, позволяющих найти комбинации ошибок более прямым путем. В этой главе будут рассмотрены три неалгебраических метода декодирования: декодирование впервые предложенное Меггиттом в 1961 г. для исправления пакетов ошибок [12], пороговое декодирование, предложенное Месси в 1963 г. [13], и перестановочное декодирование, впервые предложенное Прейнджем в 1962 г. [14]. Рассмотрение будет ограничиваться двоичными кодами, за исключением случаев, когда будет специально указываться, что результаты применимы и к недвоичным кодам.

3.1. Декодеры Меггитта

Декодеры Меггитта могут использоваться для декодирования произвольного циклического или укороченного циклического кода. На практике сложность этих декодеров сравнительно быстро возрастает с ростом числа исправляемых ошибок. Поэтому они обычно оказываются бесполезными при исправлении более трех случайных ошибок или более одного пакета ошибок. Синдром используется для распознавания исправляемых комбинаций ошибок. Будем применять синдром введенный в подразд. 2.2.7, хотя можно использовать и другие формы синдрома. Идея, лежащая в

основе декодера Меггитта, очень проста и опирается на следующие свойства циклических кодов;

1) , существует взаимно однозначное соответствие между множеством всех исправляемых ошибок и множеством всех синдромов; 2) если синдром, соответствующий многочлену ошибок то синдром, соответствующий

Свойство 2 означает, что если комбинация ошибок циклически сдвинута на одну позицию вправо, то для получения нового синдрома следует сдвинуть содержимое регистра сдвига с обратными связями, содержащего на одну позицию вправо. Отсюда вытекает, что множество всех комбинаций ошибок можно разбить на классы эквивалентности таким образом, чтобы каждый класс состоял из всех циклических сдвигов одной комбинации ошибок. Если длина циклического кода равна то для определения того, принадлежит ли комбинация ошибок данному классу, нужно сдвигать регистр с обратными связями, содержащий не более раз и сравнивать содержимое регистра с фиксированной последовательностью после каждого шага. Это свойство можно использовать для построения двух слегка отличающихся друг от друга вариантов декодера Меггитта. Отличие состоит в том, что в одном из вариантов обратная связь используется, а в другом — нет.

Построение декодеров Меггитта иллюстрируется на следующем примере. Многочленом порождается -код БЧХ. Кодовое расстояние этого кода и код может исправлять все одиночные и двойные ошибки, а также примерно 30% всех тройных ошибок. Вместе с тем этот код может использоваться для исправления пакетов ошибок и с его помощью можно однозначно определить все пакеты ошибок длиной 4 или менее. Основной декодер без обратной связи (рис. 3.1) работает следующим образом. Принятая

Рис. 3.1. Основной декодер для -кода, порожденного многочленом

(см. скан)

последовательность из 15 символов поступает одновременно в регистр сдвига с обратными связями и -символьный регистр памяти. После поступления всей последовательности вычисляется синдром который запоминается в регистре сдвига с обратными связями. После этого содержимое регистра сдвигается еще 15 раз и полученная последовательность выдается пользователю. Устройство распознавания запрограммировано таким образом, чтобы выдавать символ 1 при сдвиге, происходящем после того, как содержимое регистра сдвига с обратными связями совпадает с корректируемой комбинацией ошибок, в которой ошибка находится в последней (справа) ячейке регистра принятой последовательности. Если декодер должен исправлять все одиночные и двойные ошибки, то он должен различать 15 различных комбинаций, одна из которых соответствует одиночной ошибке в последнем символе, а 14 остальных соответствуют двойным ошибкам — с одной ошибкой в символе и другой ошибкой в каком-нибудь из символов между Комбинации, которые следует распознавать, легко получить из проверочной матрицы путем вычисления синдрома для каждой из требуемых комбинаций ошибок. Матрица, транспонированная к проверочной, показана как цикл а в табл. 3.1. Заметим, что когда одиночная ошибка передвигается на 15-ю позицию, содержимое регистра синдрома становится равным последней строке Аналогично для двух следующих подряд ошибок регистр синдрома будет содержать сумму (по модулю 2) строк что отвечает двум ошибкам в позициях 14 и 15. Точно так же вычисляются и другие комбинации.

В декодере, схема которого приведена на рис. 3.1, не используется полностью циклическая структура кода, и поэтому он должен распознавать большее число комбинаций, чем в действительности необходимо. Цикличность кода никак нельзя использовать, если устройство распознавания реализуется на постоянном запоминающем устройстве (ПЗУ), однако она может стать существенной, если устройство распознавания реализуется на элементах, выполняющих стандартные логические функции. Декодер, схема которого показана на рис. 3.2, отличается от декодера на рис. 3.1 в двух отношениях. После того как принятая последовательность записывается в регистр памяти и вычисляется начальный синдром переключатель ставится в положение 1. Затем содержимое регистра памяти циклически сдвигается один или несколько раз с одновременным сдвигом регистра обратной связи и поиском исправляемых ошибок. Каждый раз, когда появляется исправляемая ошибка, она корректируется, а также удаляется из регистра сдвига с обратными связями добавлением символа 1 на его вход. После того как содержимое регистра памяти сдвигается достаточное число раз для гарантии того, что число оставшихся ошибок не превосходит 1, переключатель переводится в положение 2. Затем последовательность направляется пользователю с одновременным окончательным исправлением оставшейся ошибки. Если декодер спроектирован так, что выполняются все возможные исправления, то в конце этого цикла содержимое регистра синдрома будет нулевым. Если, однако, исправляется лишь часть возможных комбинаций ошибок, то синдром может быть ненулевым, и это можно

Рис. 3.2. Декодер с обратной связью для -кода, порожденного многочленом

использовать как сигнал, указывающий пользователю, что последнее полученное им кодовое слово содержит обнаруживаемую, но не исправляемую ошибку.

Если декодер спроектирован таким образом, то устройство распознавания должно распознавать по одному представителю из каждого класса эквивалентности относительно циклических сдвигов, причем символ на 15-й позиции этого представителя должен быть ошибочным. Поскольку декодер может распознавать только по одному представителю из каждого класса, данный ошибочный символ может пройти один или несколько циклов до исправления. Предположим, например, что декодер должен исправлять все одиночные и двойные ошибки, а также возможно большее число тройных ошибок. При появлении исправляемой тройной ошибки один из трех ошибочных символов будет обязательно исправлен при первом цикле. После того как эта ошибка и ее влияние на синдром будут устранены, декодер перейдет к исправлению двойной ошибки. Для исправления одной из входящих в нее ошибок может потребоваться 15 дополнительных сдвигов. После этого второго цикла третья ошибка будет исправлена в процессе доставки скорректированного слова пользователю.

В табл. 3.1 приведены все возможные циклы, которые в рассматриваемом примере могут быть порождены регистром сдвига с обратными связями. Читатель должен отметить, что имеется девятнадцать различных циклов, длина шестнадцати из которых равна 15, а трех 5. Как уже говорилось, цикл а соответствует одиночной ошибке и устройство распознавания должно распознавать

последнее слово этого цикла. Циклы соответствуют различным комбинациям двух ошибок. Комбинации, которые следует распознавать, можно получить, находя в соответствующем цикле элемент с ошибкой в 15-й позиции. Например, цикл соответствует классу ошибок Устройство распознавания может распознавать набор, соответствующий ошибкам либо в позициях либо в позициях Остальные циклы соответствуют тройным исправляемым ошибкам. Таким образом, полный декодер должен распознавать девятнадцать различных комбинаций, в то время как декодер, исправляющий двойные ошибки, — восемь, а декодер, исправляющий одиночные ошибки, — одну комбинацию.

Можно, в частности, заметить, что комбинация ошибок, содержащаяся в первых восьми символах кодового слова, совпадает со своим синдромом. Из табл. 3.1 следует также, что все пакеты ошибок длиной 4 или меньше находятся в разных циклах и поэтому могут быть исправлены. Таким образом, декодер, исправляющий пакеты ошибок, может быть построен точно так же, как декодер, исправляющий случайные ошибки. Вместе с тем, сдвигая регистр синдрома на восемь позиций относительно регистра памяти [например, умножая на прежде, чем делить на как на рис. 2.4, или подавая сигнал обратной связи на выход ячейки 8 вместо ячейки 15 регистра памяти], получаем, что содержимое четырех правых ячеек регистра синдрома будет совпадать с любым исправляемым пакетом ошибок, соответствующих позициям циклически сдвинутой принятой последовательности. Такую комбинацию всегда можно узнать по четырем последовательным нулям в четырех левых ячейках регистра синдрома. Читатель может проверить справедливость этого утверждения, обратившись к табл. 3.1. В этом случае декодер будет исправлять ошибки, прибавляя комбинацию ошибок из регистра синдрома к принятой последовательности перед ее поступлением к пользователю.