1.6. Полиномиальные кодеры и фильтры (декодеры) циклических кодов.

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

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

Термин «полиномиальные» для обозначения узлов, построенных на базе сдвигающих регистров и сумматоров по модулю 2, отражает способность этих узлов аппаратно реализовать ряд операций над полиномами (многочленами), имеющими двоичные (бинарные) коэффициенты при степенях переменной x. Эти операции позволяют построить целый класс циклических кодов, которые широко используются для обнаружения или исправления ошибок при передаче и хранении данных.

Некоторый полином с бинарными коэффициентами (т.е. с коэффициентами, которые могут принимать значения только лишь 0 и 1), например,, можно записать в более развернутой форме:

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

Кодовый эквивалент равен 01001, т.е. коду исходного полинома A, равного 10010, но сдвинутого вправо.

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

Например:

.

Или более детально, выделив для каждой степени x отдельный столбец:

	x0	x1	x2	x2	x3	x4	x5	x6
A	1		+	x3	Множимое множитель
∙G	1+	x	+	x3
A∙1 =	1		+	x3
A∙x =		x	+
A∙x3 =				x3	x4	+		x6
A∙G =	1+	x		0∙x3	x4	+		x6

Если полиномы представить их кодовыми эквивалентами, то эту же операцию можно записать следующим образом:

A 1001 ∙G 1101

1001 1001 0000

1001

K=A∙G 1100101

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

Второй полином - задан структурной схемой: в первой схеме расположением мест ввода в регистр входного кода, а во второй схеме – расположением выводов на общий сумматор по модулю 2. Именно такая конфигурация обеспечивает сложение трех копий входного кода А, взаимно сдвинутых в соответствии с кодом множителя из примера.

Процесс продвижения кода А из сдвигающего регистра источника через вторую схему в сдвигающий регистр приемника выглядит следующим образом:

№ такта	А	Q 1 Q2Q3	K
0	1001
1	100	1	1
2	10	0 1	01
3	1	0 0 1	101
4		1 0 0	0101
5		1 0	00101
6		1	100101
7			1 100101

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

№ такта		Q1 Q2Q3
0	1100101
1	110010	1
2	11001	0 1
3	1100	0 0 1
4	11	1 0 0	1
5	1	0 0 1	01
6		0 0 0	1001
7			1 001

Остаток A

Узлы умножения и деления на полиномы широко используются в схемах контроля.

1 способ. Перед подачей исходный код А кодера умножается на некоторый порождающий полином G, и в линию связи (или в память) передается кодовое слово K=A∙G. На приемной стороне кодовое слово в фильтре (декодере) делится на тот же полином G.

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

2 способ. Вместо передачи по линии связи кодового слова K=A∙G передается сам код A и следом за ним – остаток от деления его на порождающий полином G . На приемном конце еще раз выполняется деление A:G и оба остатка сравниваются, если они не равны, следовательно произошла ошибка.

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

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

Разработаны коды этого класса способные исправлять следующие ошибки при передаче данных:

- одиночные ошибки в слове (коды Хэмминга – HAMMING CODES);

- компактные группы (пакеты) ошибок длинной не более l (коды Файра – FIRE CODES);

- группы, числом не более t произвольно разбросанных по слову ошибок (код Боуза – Чоудхри – Хокенгхема) - BCH CODE – BOSE – CHAUDHURL – HOCQUENGHEM CODE.

Параметры l и t также определяются видом порождающего полинома .

На основе этого кода разработана микросхема циклического регистра диагностики ошибок КР 1818 ВЖ1.

Узлы деления полиномов используют также при контроле правильности работы логических схем методом сигнатурного анализа (SIGNATURE ANALISIS).

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

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

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

Распространен 16-ти разрядный сигнатурный анализатор с обратными связями, обеспечивающими формирование последовательности максимальной длины (2¹⁶-1 тактов).

Сигнатурный анализатор используют как при стендовом контроле схем, так и при создании встроенной схемы самоконтроля цифровых блоков.

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

Т

1

Т

2

Т

3

М2

Т

1

Т

2

Т

3

М2

Т

1

Т

2

Т

3

М2

Т

1

Т

3

М2

x

x