Временные булевы функции и последовательностные автоматы

Ранее были рассмотрены способы анализа и синтеза схем первого рода (комбинационных), которые невозможно использовать при описании схем второго рода (схем с памятью). Основная особенность схем с памятью (последовательностных автоматов) состоит в том, что алгоритм их работы зависит от времени. Следовательно, в число переменных, от которых зависит выходная функция схемы с памятью, должно входить время t. Но время не является двоичной переменной. Поэтому вводится понятие автоматного времени, принимающего дискретные целочисленные значения 0, 1, 2 и т.д. это означает, что работа схемы с памятью распадается на ряд интервалов, в течение которых автоматное время условно принимает постоянное значение. эти интервалы времени формируются некоторыми тактирующими сигналами - тактами.

Временная булева функция (ВБФ) - это логическая функция

y = (x 1, x 2,..., x n, t), принимающая значение {0,1} при 0 t s -1, где s - количество интервалов автоматного времени.

Можно утверждать, что число различных ВБФ равно . В самом деле, если функция времени принимает ы значений, т.е. t = 0, 1, 2,..., s -1, и каждому интервалу времени соответствует 2nразличных двоичных наборов, то всегда будет s2n различных наборов. Следовательно, общее количество ВБФ равно .

 

Любая временная булева функция может быть представлена в виде

 

y = (x 1, x 2,..., x n, t) = 00 11 s-1s-1, (9.1)

 

где i - конъюнктивный или дизъюнктивный терм от переменных (x 1, x 2,..., x n); i - вспомогательная функция, принимающая значение i = {0, 1} в момент времени t i.

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

 

Пример. Преобразовать функцию, заданную нижеследующей таблицей в вид (9.1).

 

x1 x2 t (x1, x2, t) x1 x2 t (x1, x2, t)

0 0 0 0 1 0 1 1

0 1 0 0 1 1 1 0

1 0 0 1 0 0 2 0

1 1 0 0 0 1 2 0

0 0 1 0 1 0 2 1

0 1 1 1 1 1 2 1

 

Решение. Функцию y = (x 1, x 2, t) представляем совокупностью трех логических функций 0(x 1, x 2); 1(x 1, x 2); 2(x 1, x 2), которые для таблицы имеют вид

 

0(x1, x2) = x1x2; 1(x1, x2) =x1x2 x1x2; 2(x1, x2) = x1x2 x1x2 = x1.

 

На основании (9.1) записываем окончательный вид временной логической функции:

 

y = x1x20 (x1x2 x1x2)1 x12.

 

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

Предположим, что на выходах некоторой схемы (дешифратора) в моменты времени е появляются сигналы:

если t1 = 0, то на выходе 1 сигнал 0 = 1, при 1 = 0, 2 = 0;

если t2 = 1, то на выходе 2 сигнал 1 = 1, при 0 = 0, 2 = 0;

если t3 = 2, то на выходе 3 сигнал 2 = 1, при 0 = 0, 1 = 0.

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

Рекуррентная булева функия (РБФ) - логическая функция, зависящая как от текущих значений входных переменных, так и от предшествующих значений самой функции y(t-1). Полная аналитическая запись такой функции

 

yt = {0, 1} при t > 0,

 

где - текущие значения входных переменных; yj - значения выходных функций в момент времени j = t-1; t-2 и т.д.

Введем понятие элемента задержки (D), для которого справедливо равенство yt+1 = xi= т.е. значение выходного сигнала в момент времени t+1 равно значению входного сигнала в момент времени t. D(t) - является его логичес-ком оператором.

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

 

 

x(t) f(xi, yi)

 

 

y(t)

 

Предположим, что в качестве схемы с функцией f(x,y) взята логическая схема ИЛИ. Тогда в совокупности эта схема работает так, что

 

f(x,y) = xt+1 yt.

 

В этой схеме выходной сигнал зависит как от входного сигнала в данный момент времени, так и от выходного сигнала в предшествующий момент времени.

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

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

Поэтому справедливо следующее утверждение:

Любую схему с памятью можно представить в виде совокупности схем одного из рассмотренных ранее базисов и триггеров.

 

 

Глава 10.