Полиномиальные счетчики

Полиномиальные счётчики строятся на основе n-разрядного регистра сдвига с линейными обратными связями (с сумматорами по модулю два в цепи обратной связи).

В качестве примера рассмотрим схему счётчика при n = 4:

Последовательность состояний регистра сдвига представлена на рисунке (состояние 0 0 0 0 запрещено).

 

Работа схемы описывается с помощью квадратной матрицы С, связывающей данное и последующее состояния. Для нее состояния триггеров q₁, q₂, q₃и q₄ в момент времени (t+1) определятся следующим образом:

или в матричной форме

или ,

где

.

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

Периодические свойства последовательностей на выходах счетчика определяются характеристическим многочленом , который является определителем матрицы (Е –единичная матрица).

Если многочлен неприводим и примитивен, то счетчик будет формировать последовательность максимальной длины или М- последовательность. Для данного примера характеристический многочлен j (х) неприводим, примитивен и имеет следующий вид: = x⁴ x 1.

Вероятности появления символа 1 и символа 0 для М-последовательности определяются следующим образом:

, .

Известен оригинальный метод построения счетчика на регистре с многошаговым (s-шаговым) сдвигом за один рабочий такт (). Запишем следующие соотношения:

, и т.д.

Пусть s = 2. Тогда матрицабудет имеет вид:

.

По матрице построим схему счетчика:

Последовательность состояний регистра сдвига при s = 2 (пунктирные линии) и при s = 1 (сплошные линии) показаны на рисунке.

Как видно из рисунка, счетчик также формирует М-последовательность. Возьмем s = 3. Матрица функционирования счетчика в этом случае имеет вид:

.

Рассмотрим схему счетчика при s = 3:

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

Здесь необходимо отметить, что для того, чтобы каждый выходной разряд счетчика также формировал последовательности максимальной длины, необходимо, чтобы число шагов s и период последовательности M были взаимно простыми числами, т.е. (M, s) = 1. Поскольку в данном примере это условие не выполняется, диаграмма последовательности состояний регистра разбивается на несколько периодов меньшей длины:

 

Пусть s = 4. Матрица в этом случае имеет вид:

 

.

 

Схема счетчика приведена на рисунке.

 

Эта схема может быть построена только на Т-триггерах и одном сумматоре по модулю два:

 

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

Если коэффициент C_i = 1, то выход i-го триггера подается на вход сумматора по модулю 2, если же C_i =0, то – не подается. В соответствии с коэффициентами многочлена однозначно определяется структура обратной связи регистра сдвига. Есть таблица всех неприводимых многочленов, из которой находят многочлены, представленые в 8-ричной форме.

Например, характеристический многочлен = x⁴ x 1 в этой таблице будет иметь следующий вид:

= 1.

В двоичном виде этом многочлен запишется как: 10 011, или в 8-ричном виде – 23. По такой записи многочлена однозначно строится схема полиномиального счетчика.