Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
7.2. Рекуррентные булевы функции
Пусть некоторая функция в момент времени t может принимать значение yt, равное 0 или 1.
Рассмотрим множество векторов
= {< x1t, x2t, ..., xnt, y t - 1, ..., y t - k >}, (7.5)
координаты которых принимают значения 0 или 1. Осуществим однозначное отображение множества на множество y = {0,1}.
Определение 7.3. Функция yt = (x1t, ..., xnt, yt-1, ..., yt-k), задающая однозначное отображение на множество Y, называется рекуррентной булевой функцией первого рода (РБФ-1).
РБФ-1 определяется следующим соотношением:
(7.6)
где а{0,1}.
Рис. 7.4
Физически функция (7.6) реализуется в виде схем с n входами и K линиями обратной связи (рис. 7.3, а).
Если РБФ-1 не зависит от аргументов xi t (i = 1, 2, ..., n), то она называется вырожденной РБФ-1 и определяется соотношением
(7.7)
Физически в схеме, соответствующей собственной функции (7.7), отсутствуют внешние входы (рис. 7.4, б).
Пример 7.3
РБФ-1 задана следующей системой:
Рассмотрим несколько первых значений этой функции:
y1 = x11 y0 = x11 0 = x11;
y2 = x12 y1 = x11 x12;
y3 = x13 y2 = x11 x12 x13.
Отсюда для любого t имеем y t = x1 m.
Запишем множество наборов
= {< x1t, x2t, ..., xnt, x1(t - 1), x2(t - 1), ..., xn(t - 1), ..., x1(t - r), ..., xn(t - r) >},
где xj(t - i){0,1} и соответствует значению j-го входного аргумента в момент времени (t - i).
Рассмотрим функцию
y t = (x1t, ..., xnt, x1(t - 1), x2(t - 1), ..., xn(t - 1), ..., x1(t - r), ..., xn(t - r)). (7.8)
Определение 7.4. Функция yt, дающая однозначное отображение множества на множество ={0,1}, называется рекуррентной булевой функцией 2-го рода (РБФ-2).
Пример 7.4
Задана функция yt = x1t x2t x2(t - 1). На вход устройства, реализующего данную РБФ-2, подаются последовательности:
y0 (0, 0, 0) = 0,
{x1t} = 0, 1, 0, 1, 0, 1, 0, . . . y1 (1, 0, 0) = 1,
Тогда y2 (0, 0, 0) = 0,
{x2t} = 0, 0, 0, 1, 1, 1, 0, . . . y3 (1, 1, 0) = 1,
y4 (0, 1, 1) = 1 и т.д.
Введем замену переменных функций (7.8):
x1t = 1; x1(t - 1) = n+1; ... ; x1(t - r) = r n+1;
x2t = 2; x2(t - 1) = n+2; ... ; x2(t - r) = r n+2; (7.9)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xnt = n; xn(t - 1) = 2n; ... ; xn(t - r) = r n+n.
Тогда РБФ-2 (7.8) можно записать в виде функции y = (1,2,..., n,n+1,..., r n+ n), которая является обычной функцией алгебры логики. Итак, уравнение
y t = x1(t - 1) описывает работу однотактной линии задержки
(т.е. устройства, “задерживающего” входную величину на некоторую величину времени), а уравнение
yt = x1(t - k) (7.10)
работу K-тактной линии задержки
В связи с этим, возвращаясь к уравнению (7.9), можно утверждать, что любая РБФ-2 реализуется с помощью линий задержки и подбора функциональных элементов, представляющих обычные ФАЛ.
Пример 7.5
Синтезировать функциональную схему, реализующую следующую РБФ-2:
y = x1(t - 1) 2t x1t x2(t - 2).
Решение.
Осуществляем замену переменных 1 = x1t, 2 = x2t, 3 = x1(t-1), 4 = x2(t-2) и получаем функцию y = 3 1 2 4.
Анализируем, что входные аргументы x1 и x2 подаются на вход схемы в виде двоичных временных последовательностей, а для получения аргументов 3 и 4 применяются линии задержки. Тогда общая функциональная схема имеет вид, показанный на рис. 7.5:
Рис. 7.5
Рассмотрим множество векторов = T {< x1t, ..., xnt, x1(t-1), ..., xn(t-1), ..., x1(t-r), ..., xn(t-r), yt-1, ..., yt-k >}, где в конкретных наборах величины r и k могут принимать значения r = 1, 2, ..., t, k = 0, 1, 2, ..., t.
Определение 7.5. Функция yt, дающая однозначное отображение множества T на множество Y = {0,1}, называется рекуррентной булевой функцией (РБФ).
Пример 7.6
Заданы РБФ
и последовательность входов
{x1t} = 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, . . .
Имеем:
y1 = x11 y0 x10 = 0 1 0 = 0;
y2 = x12 y1 x11 = 0 0 0 = 0;
yt =
y0 = a при t 0,
(x1t, ..., xnt, yt-1, ..., yt-k) при t > 0,
y t - 1
y t - 2
y t - k
y t
. . .
а
x1t
x2t
xnt
. . .
y t - 1
y t - 2
y t - k
y t
. . .
б
yt =
y0 = a при t 0,
(yt-1, yt-2, ..., yt-k) при t > 0,
y0 = 0;
yt = x1t y t-1.
З1
xt
yt
З1
З1
xt
yt
З1
. . .
З1
З1
x1
y
x2
y0 = 1,
y t = x1t y t - 1 x1(t - 1)