Принятое слово

Обратная связь цепи Веления на д(х)

т~~т

(7г-/(>)-разряВный регистр сЭвига

Проверка на совпаВение со всеми табличными синВромами

-Уё;г-х-

Мойисрикация синйромс;.

/г-разряВный IA. Буфер -Чу"

Рис. 6.20. Другой декодер Меггитта.

ления закончен. Следовательно, полный процесс работы декодера занимает 30 тактов.

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

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

Пусть ё (х) = е„ 1Х"-Ч Тогда вклад в синдром от этой единственной компоненты вектора ошибок равен

После исправления e„ i этот вклад надо вычесть из истинного синдрома, заменив содержимое s (х) синдромного регистра на S (х) - s (х). Но многочлен s (х) может иметь много ненулевых коэффициентов, так что такое вычитание затрагивает многие ячейки синдромного регистра и создает дополнительные неудоб-

Проверка равенства

15-рюрябный буфер

Рис. 6.21. Другой декодер Меггитта для (15, 11)-кода Хэмминга.

ства. Чтобы избежать этих неудобств, изменим определение синдрома, задав его равенством

s (х) = Rg (X) [x"-v (х) ].

Это определение отличается от первоначального, но не хуже его, и с ним можно работать точно так же, как и с первоначальным. Его преимущество состоит в том, что

S (х) = R [x«-fte„ ,x«-i] = R [Rn , К ,х2"--Ч] =

так как степень многочлена g (х) равна п - k. Но теперь отличен от нуля толь один коэффициент многочлена s (х), а именно старший. Соответственно после исправления е„ 1"для замены s (х) на S (х) - s (х) достаточно только вычесть e„ i из старшего коэффициента синдрома. При этом полностью ликвидируется вклад, вносимый в синдром исправляемым символом.

Предварительное умножение е (х) на х"- выполняется сдвигом V (х) в новую позицию синдромного регистра.

На рис. 6.21 изображен модифицированный декодер Меггитта для (15, 11)-кода Хэмминга, декодер которого уже рассматривался выше (рис. 6.19). Принятый многочлен v (х) умножается на x* и делится на g (х), так что синдром равен

W=g(.)[*()] = Rgxdxn ,lxeix)]l

Преимущество такой модификации ссстоит в том, что соответствующий ошибке е (х) = х* синдром равен

s (x) = Rx*+x+i Ix] = Rx+x+i [х] = х\

а это дает возможность исправления с помощью сигнала обратной связи.

Следующим примером является декодер для (15, 7)-кода ЁЧХ, исправляющего две ошибки (этот код будет определен в гл. 7). Сейчас мы только укажем без доказательства, что этот код цикличен, порождается многочленом.g (х) = + + + + X* + 1 и позволяет исправлять две ошибки. Среди них содержатся 16 конфигураций ошибок, содержащих ненулевой старший разряд: одна одиночная ошибка и 14 двойных.

Принятое слово умножается на х и делится на g (х). Следовательно, если е (х) = х*, то

s{x)== Rgixylx-xn-x

Аналогично если е (х) = х" + х, то

s{x) = Rg м [х • (х + х)] == х + x

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

Можно упростить этот декодер и далее и получить схему, изображенную на рис. 6.23. Заметим, что при циклическом сдвиге принятого слова многие из 15 исправляемых конфигураций ошибок появляются дважды. Например, вектор (000000100000001) после восьми циклических сдвигов переходит в вектор (000000010000001), где черта под единицей использвана в качестве маркера сдвигаемой единицы. Каждой из этих ошибок соответствует свой табличный синдром. Если удалить один из этих синдромов, то при соответствующем циклическом сдвиге ошибка все-таки будет найдена. Следовательно, для каждой такой пары достаточно запоминать только один синдром. В данном случае имеется только восемь синдромов, которые нужно запомнить. На рис. 6.22 они выписаны в первом столбце таблицы синдромов. Однако в тот момент, когда первая ошибка достигнет конца буфера, она может быть не исправлена, хотя в течение 15 сдвигов будет исправлена по меньшей мере одна ошибка. Для исправления обеих позиций необходимо произвести два полных цикла сдвигов, так что декодирование займет 45 тактов. Теперь необходимость модернизации синдрома очевидна, так как в противном случае ошибка не будет