ГЛАВА 6. СХЕМНАЯ РЕАЛИЗАЦИЯ ЦИКЛИЧЕСКОГО КОДИРОВАНИЯ

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

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

6.1. ЛОГИЧЕСКИЕ ЦЕПИ ДЛЯ АРИФМЕТИКИ КОНЕЧНОГО ПОЛЯ

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

Регистр сдвига, как показано на рис. 6.1, представляет собой последовательность элементов памяти, называемых разрядами. Каждый разряд содержит один элемент поля Содержащийся в каждом разряде символ, покидая этот разряд, появляется на выходящей из него линии Каждый разряд снабжен также входной линией, но которой в пего поступает элемент

поля Если нет других указаний, то этот входной символ принимается равным нулевому элементу поля. 13 дискретные моменты времени, называемые тактами, содержащиеся в устройствах памяти элементы поля замещаются элементами поля с входных линий. Современные электронные регистры сдвига допускают тактовую частоту, превосходящую миллионов тактов в секунду.

Помимо регистров сдвига мы будем использовать три других элемента, показанных на рис. 6.2, а именно умножитель на скаляр, сумматор и умножитель. Умножитель на скаляр является функцией одной входной переменной; он умножает входную переменную на фиксированный элемент поля Сумматор умножитель являются функциями двух входных переменных, принимающих значения из В двоичном случае сумматор также называется элементом «исключительною или», а умножитель — элементом

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

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

Рис. 6.1. -разрядный регистр сдвиги.

Рис. 6.2. Элементы устройств, а — умножитель на скаляр; б - сумматор, в — умножитель.

Рис. 6.3. Построенные из двоичных компонентов регистры сдвига для поля из 16 элементов, а — последовательное исполнение, б - параллельное исполнение.

Рис. 6.4. Сложение двух элементов поля а - последовательное исполнение; б - параллельное исполнение.

Рис. 6.5. Умножение на константу поля а — последовательное исполнение; б - параллельное исполнение.

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

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

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

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