Линейные счетчики.

Синхронный автомат, изображенный на рис. 4.1, называется линейным, если КС описывается линейными функциями, свойства которых рассмотрены в § 1.15. Линейный автомат с циклическим изменением внутренних состояний называется линейным счетчиком. Наиболее широкое практическое применение в настоящее время нашли линейные автоматы над полем

Проектирование линейных автоматов производится алгебраическими методами, изложенными в [13,16]. Многие из линейных автоматов описываются многочленами

над полем GF(2), алгебраические свойства которых и используются для их проектирования или 1). Так, неприводимые примитивные многочлены над полем GF(2) [13] могут быть использованы для построения на сдвигающих регистрах генераторов последовательностей максимальной длины (ПМД), которые называются также генераторами псевдослучайных последовательностей. Период генерируемой последовательности содержит символов 0 и 1, если генератор построен на -разрядном сдвигающем регистре, т. е. генератор имеет внутренних состояний из возможных.

Таблица 4.15. (см. скан) Неприводимые примитивные многочлены с минимальным числом ненулевых коэффициентов

В табл. 4.15 в восьмеричной системе счисления указаны коэффициенты некоторых неприводимых примитивных многочленов (4.59), взятых из [13]. Двойственным к многочлену (4.59) называется многочлен

свойства которого аналогичны свойствам многочлена Двойственные многочлены также помещены в табл. 4.15.

Пример 1. Пусть Тогда из табл. 4.15 следует, что коэффициенты многочлена задаются восьмеричным числом

Пример 2. Пусть Тогда из табл. 4.15 следует, что

коэффициенты многочлена задаются восьмеричным числом

Для двойственных многочленов восьмеричные числа получаются на основании записи в обратном порядке двоичного числа, характеризующего многочлен Так, из предыдущего примера следует, что коэффициенты двойственного многочлена задаются 8-ричным числом 160400001.

Рис. 4.53

На рис. 4.53,а показана схема генератора ПМД, реализованная в соответствии с многочленом (4.61). Ненулевые коэффициенты многочлена однозначно определяют функцию возбуждения первого триггера сдвигающего регистра. По функциям возбуждения генератора

можно составить таблицу истинности (табл. 4.16) для функции переходов из которой видно, что автомат имеет 15 внутренних состояний. Из этого следует, что его можно использовать в качестве счетчика по Вообще, любой генератор ПМД является счетчиком по

Таблица 4.16. (см. скан) Функция переходов генератора

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

и автомат не может самостоятельно из него выйти.

На основании (4.60) многочлен является двойственным к многочлену (4.61). На рис. показана схема генератора, соответствующая данному многочлену (добавлена нелинейная функция Для принудительного вывода генератора из нулевого состояния на основании того, что Табл. 4.17 для функции переходов автомата составляется по функции возбуждения так как минтерм только в нулевом состоянии регистра.

Таблица 4.17. (см. скан) Функция переходов генератора

Временные диаграммы работы генератора, выполненного по схеме на рис. 4.53,а, показаны на рис. 4.53,е. Из этих диаграмм видно, что генерируемая последовательность символов 0 и 1 имеет случайный

характер, но поскольку последовательность выдается детерминированным автоматом, то она называется псевдослучайной. Легко заметить, что генератор на рис. 4.53, б, соответствующий двойственному многочлену, выдает символы 0 и 1 в обратном порядке следования (рис. 4.53,г).

Для из табл. 4.15 следует, что коэффициенты многочлена определяются восьмеричным числом т.е.

Данному многочлену соответствует схема генератора, изображенная на рис. 4.54 и выдающая периодическую последовательность из символов 0 и 1. Реализовать функцию можно на одном четырехвходовом с прямым выходом вместо трех ЛЭ сумма по модулю два.

Рис. 4.54

Рис. 4.55

Из выражения (4.63) следует, что

При получается функция возбуждения первого триггера сдвигающего регистра Показатель степени к у члена указывает, через сколько тактов его значение (0 или 1) появится на выходе сдвигающего регистра. Основываясь на этом правиле отыскания функции легко построить схему любого генератора из табл. 4.15. Так, неприводимому примитивному многочлену (4.62) соответствует функция возбуждения

первого триггера 24-разрядного сдвигающего регистра. Данный генератор выдает псевдослучайную последовательность, один период которой содержит символов 0 и 1.