7. Реализация и применение кодов, исправляющих ошибки

7.1. Реализация кодов, исправляющих ошибки

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

На фиг. 7.2 показано, например, каким образом происходило и происходит снижение стоимости полупроводниковой памяти. Если стоимость полупроводникового триггера вначале составляла около 10 долл., то в настоящее время стоимость памяти составляет несколько центов за 1 бит. Ожидается, что к концу семидесятых годов она достигнет 0,1 цента за 1 бит. Поэтому, если на начальном этапе развития теории кодирования реализация кодирования и декодирования с помощью аппаратурных средств из-за их сложности и высокой стоимости представлялась почти нереальной, то сейчас можно привести большое число примеров, когда аппаратура для кодирования и декодирования используется в реальных системах (главным образом в системах связи). Как правило, эта аппаратура строится из обычных широко используемых интегральных и так называемых больших интегральных схем и выполняет относительно простые стандартные операции.

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

Применение программных методов позволяет снизить вес кодеров и декодеров. Например, если строить специализированное устройство для декодирования БЧХ-кода с большим числом исправляемых ошибок то при использовании алгоритма Питерсона и алгоритма Берлекэмпа-Месси приходится

(кликните для просмотра скана)

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

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

7.1.1. Стандартные схемы

Сначала рассмотрим простой пример, а именно показанную на фиг. 7.3 схему умножения фиксированного многочлена

на входной многочлен

Все ячейки памяти показанного на фиг. 7.3 регистра сдвига вначале содержат нулевые символы. Будем считать, что на вход регистра сдвига первыми подаются старшие члены входного многочлена (т. е. члены с высшими степенями неизвестного). Член поступивший на вход регистра сдвига, без изменений передается на выход. Точно так же без изменений передается на выход схемы и После того как на вход регистра сдвига поступит с помощью крайнего левого сумматора, он складывается с поступившим ранее и их сумма

поступает на выход схемы. Точно так же вычисляются и последующие члены искомого произведения

В общем случае умножение входного многочлена

на фиксированный многочлен

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

входного многочлена на фиксированный многочлен

Схема умножения в данном случае имеет вид, показанный на фиг. 7.5. При поступлении на вход регистра сдвига это слагаемое без изменений передается на выход схемы как Одновременно вводится во 2, 4, 5 и 7-й разряды регистра сдвига. Точно так же со входа без изменений на выход схемы передается при этом вводится в регистр сдвига точно так же, как Далее после того, как на вход поступит член поступивший на два момента времени ранее во 2-ю справа ячейку регистра сдвига, складывается с помощью крайнего правого сумматора с и полученная сумма поступает на выход схемы как Точно так же схема работает при поступлении последующих членов входного многочлена. В общем случае схема, выполняющая умножение указанным выше образом, имеет вид, показанный на фиг. 7.6.

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

Рассмотрим далее схему, выполняющую деление многочленов. Сначала рассмотрим пример такой схемы, а именно показанную на фиг. 7.7 схему, предназначенную для деления входного многочлена на многочлен

Пусть

Деление на «углом» проводится следующим образом:

(кликните для просмотра скана)

При делении на с помощью схемы, показанной на фиг. 7.7, сначала в регистр сдвига последовательно вводятся коэффициенты входного многочлена при При поступлении на вход регистра коэффициента при коэффициент при на входе поступает на выход схемы как коэффициент при частного. Одновременно коэффициент при с выхода регистра подается на входы трех сумматоров по модулю 2, установленных на выходах 3, 4 и 5-й слева ячеек памяти регистра сдвига, и складывает их с выходными символами этих ячеек. При следующем сдвиге коэффициент 0 при входного многочлена выводится как 0 при частного. При следующем сдвиге символ 0, получающийся в результате сложения коэффициента 1 при входного многочлена с коэффициентом 1 при поступающим по цепи обратной связи, выводится как коэффициент 0 при частного.

Фиг. 7.8. Схема деления в общем случае.

После ввода всех символов входного многочлена в регистре остается остаток (табл. 7.1).

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