5.4. Процедура Ченя

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

Один из методов исправления ошибок, предложенный Ченем [1964], позволяет избежать отыскания явного решения алгебраического уравнения Когда позиция с локатором выводится из буфера, декодер вычисляет значение многочлена чтобы выяснить, обращается ли оно в нуль. Если то позиция с локатором не изменяется, если же а то в позиции с локатором произошла ошибка, и она исправляется. Использование этого метода не ограничивается кодами, исправляющими одиночные или двойные ошибки. Если в декодере известен многочлен локаторов ошибок корни которого взаимны локаторам, то процедура Ченя может быть применена к каждому из локаторов для проверки, является ли ошибочным символ, выводимый в данный момент. Для БЧХ-кодов, исправляющих двойные ошибки, многочлен локаторов ошибок может быть вычислен в соответствии с уравнением (1.47); для БЧХ-кодов, исправляющих ошибки более высокой кратности, процедура вычисления многочлена локаторов ошибок описана в гл. 7.

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

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

Рис. 5.9. Схема умножения на а.

Рис. 5.10. Схема умножения на

Например, умножение в на элемент а, такой, что может быть выполнено с помощью схемы, изображенной на рис. 5.9. Умножение на элемент может быть выполнено с помощью схемы, изображенной на рис. 5.10. Процедура Ченя реализуется с помощью схемы, представленной на рис. 5.11.

Рис. 5.11. Схема Ченя для кода, исправляющего две ошибки.

Сначала в верхнем регистре схемы рис. 5.11 записан элемент а в нижнем В каждом временном цикле верхний регистр умножается на а нижний на а. После к временных циклов верхний регистр содержит , а нижний В сумматоре вычисляется величина . Если эта величина равна нулю, то является взаимным корнем многочлена локаторов ошибок; к ошибочному символу с локатором выводимому в данный

момент из буфера, добавляется единица. Если о то не является взаимным корнем многочлена локаторов ошибок и позиция с локатором выводится из буфера без изменений.

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

Рис. 5.12. Общий вид схемы Ченя для кода, исправляющего ошибок.

Для реализации такого способа требуется только регистр умножения на а, но для больших значений это приводит к большому числу сдвигов. В этих случаях обычно более экономным является использование временных циклов для каждого из умножений, которые могут быть выполнены одним из методов, описанных в разд. 2.4. Целесообразно выполнять все умножений одновременно. На рис. 5.12 приведена схема, реализующая такое умножение. В этой схеме используется один главный блок управления и идентичных вспомогательных умножителей, один из которых изображен на рис. 5.13. В начальный момент первый вспомогательный накопитель содержит первый вспомогательный регистр осуществляет умножение на ; второй вспомогательный накопитель содержит второй вспомогательный регистр

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

Рис. 5 13. Типичный вспомогательный умножитель.

В главном сумматоре вычисляется сумма содержимых всех вспомогательных накопителей, которая помещается затем в главный накопитель. Эта величина и есть Продолжая эту процедуру, последовательно подсчитаем . Позиция с локатором выводимая из буферного регистра, исправляется тогда и только тогда, когда а