ГЛАВА 6

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

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

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

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

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

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

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

а--I а~

а 6 В

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

ПОЛЯ GF (q). Если нет других указаний, то этот входной символ принимается равным нулевому элементу поля. В дискретные моменты времени, называемые тактами, содержащиеся в устройствах памяти элементы поля замещаются элементами поля с входных линий. Современные электронные регистры сдвига допускают тактовую частоту, превосходящую 10 миллионов тактов в секунду.

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

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

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

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

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

То Г, Тг Гз

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

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