Файл: Вычислительная техника и прикладная математика.pdf

Рисунок 1
Если на входе y значение возникает на
 позже, чем значение на входе
x , то на выходе схемы


y
x
S
,
значение также запаздывает на величину
 . Таким образом, фиктивные пере- менные могут принимать участие в управлении задержками.
Пусть




0
,
,...,
1
n
x
x
f
– ФАЛ с нулевыми задержками. Тогда будем считать, что функция








0
,
,...,
1 1
n
n
t
x
t
x
f




имеет внешнюю за- держку (или задержку на входе), равную




n
n





,...,
min
,...,
max
1 1
. Таким образом, в подсхеме некоторой схемы имеется задержка, которую можно рассматривать как сумму внутренней и внешней задержек (при этом внешняя задержка для подсхемы является составляющей для внутренней задержки всей схемы). Задержка для цепи в схеме в общем случае не является суммой внутренних задержек элементов цепи.
Приведем пример подсчета задержки цепи
(см. рисунок 2), где
1
 ,
2
 ,
3
 – внутренние задержки элементов цепи, а t ,
1
t ,
2
t ,
3
t – мо- менты времени подачи сигнала. Тогда задержка цепи равна:
















2 1
1 1
1 1
,
min
,
max
t
t
t
t




















3 2
1 1
1 1
2 1
,
,
,
min
,
max max
t
t
t
t
t
t








3 3
2 1
1 1
1 2
1
,
,
,
min
,
max min












t
t
t
t
t
t

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
57
Задержка схемы есть максимум задержек по всем цепям. ▲
)
(
1
t
y
)
(
2
t
y
1

1
t
2

3

2
t
3
t
Рисунок 2
Основная часть. В базисе


z
,
,
&, 
под- счет задержек схемы может быть определен индуктивно по числу элементов в схеме.
1. Базис индукции. Задержки элементов & ,
 , равны нулю. Тождественная функция с за- держками
 


x
x
z


,
имеет
 
 
1 0
2 1







2. Шаг индукции. Пусть определены две
ФАЛ с задержками

 



n
n
x
x
x
x
f
,...,
,
,...,
1 1
1

и

 



n
n
x
x
x
x
f
,...,
,
,...,
1 1
2
 
. Тогда для схем на рисунке 3 задержки соответственно равны: а)
 
 
1

f
x



; б)
 
x


; в)-г)
   


x
x

,

max
 

x

1
f
z
1
f
x

а
б
2
f
&
x
1
f
2
f
x

1
f
в
г
Рисунок 3
Функция задержек схемы
2
S (см. рису- нок 4), реализующей конъюнкцию двух переменных, определяется столбцом задержек


T
2 1
2 2
1 1
2
,
,
,
2








– соответственно входным набором


0
,
0
,


1
,
0
,


0
,
1
и
 
1
,
1
Функция задержек схемы
3
S (см. рисунок 5) равна:
1 3 на наборе


0
,
0
,
0
;
2 1
2



на наборах


1
,
0
,
0
,


0
,
1
,
0
,


0
,
0
,
1
;
2 1
2


на наборах


1
,
1
,
0
,


1
,
0
,
1
,


0
,
1
,
1
;
2 3 на наборе


1
,
1
,
1
. Эта схема реализует конъюнкцию от трех переменных, причем на наборах с различным числом единиц схема на выходе выдает значения с разными задержками. Такое свойство сохранится при реализации конъюнк- ции от четырех переменных (см. рисунок 6):
1 4 на наборе


0
,
0
,
0
,
0
;
2 1
3



на наборах с одной единицей;
2 1
2 2



на наборах с двумя единицами;
2 1
3


на наборах с тремя едини- цами;
2 4 на наборе


1
,
1
,
1
,
1
x
y
z
&
z
z
x
y
z
&
2
S
2
S
2
S
z
Рисунок 4
Рисунок 5
Схема
2
S
Схема
3
S
1
x
2
x
3
x
4
x
&
z
3
S
3
S
3
S
3
S
Рисунок 6
Схема
4
S
Легко заметить, что функция задержек схемы
n
S равна:



































1
...,
,
1 2
2 1
,
,
0
...,
,
0 2
2 1
2 1
2 1
1
наборе на единицами,
с наборах на единицами,
2
с наборах на единицей,
1
с наборах на наборе на
n
k
k
k
n
n
n
n
(1)
В (1) все задержки различны. Действи- тельно, пусть
m
k 
. Тогда предположим, что




2 1
2 1









k
m
n
k
k
n
. Отсюда получим




2 1
2 1







m
k
. Так как
2 1



, то
m
k 
, что противоречит предположению.
Рассмотрим теперь схему  с
m
n

1 2
входами, реализующую конъюнкцию
m -го

58
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
ранга, задержка в которой определяется числом единиц на входном наборе


m
y
y ,...,
1
и равна


2 1




r
r
m
, где
r – число единиц в этом наборе. Множество входов схемы  разобьем на группы следующим образом: в первую группу попадают
1 2

n
первых входов, во вторую группу – следующие
2 2

n
входов и так далее, в последнюю группу попадает один вход. Итого имеем:
1 2
1 2
2 2
1







n
n
n
. В полученных группах произведем операцию отождествления входов.
Полученная схема

реализует конъюнкцию
n -го ранга с задержками. Если на эту схему подать набор


n
x
x ,...,
1
с
k единицами, то на входах схемы

соответственно будет набор длины
m
n

1 2
и с числом единиц, равным
n
n
n
x
x
x
0 2
2 1
1 2
2 2





, (2) то есть десятичному числу, двоичная запись которого и есть набор


n
x
x ,...,
1
. Задержку схемы  можно получить из формул (1) и (2):


















n
r
r
r
n
n
r
r
r
n
n
x
x
1 2
1 1
2 2
1 2









n
r
r
r
n
n
x
1 1
2 1
2 2


. (3)
Пусть имеются различные наборы
y
x


, имеющие равные задержки:





















n
r
r
r
n
n
n
r
r
r
n
n
y
x
1 1
2 1
1 1
2 1
2 2
2 2
Отсюда имеем:







n
r
r
r
n
n
r
r
r
n
y
x
1 1
2 2
, что в двоичной записи означает, что
y
x

 . Полу- ченное противоречие доказывает, что при различных входных наборах схема реализует конъюнкцию
n -го ранга с разными задержками.
В частности, при
0 1


и
1 2


из формулы
(3) получим, что задержка на наборе x равна (2), то есть десятичному числу, двоичная запись которого есть набор x .
Теперь построим селекторное устройство с
задержками (СУЗ). Это будет тождественный булевый


n
n,
-оператор, выдающий входной на- бор x с задержкой, определяемой формулой (3).
Для этого используем схему  и


y
x
S
,
(рису- нок 1), где на y -входы схем


y
x
S
,
подается выход схемы  (см. рисунок 7).
Пусть
 
 


x
x
n

,...,

1


есть булев


n
n,
- оператор, реализуемый в базисе


,
&, 
с ну- левыми задержками. Тогда схема на рисунке 8 реализует этот оператор с дифференцирован- ными задержками. По величине задержек однозначно может быть определена комбинация на входе.
1
x
 
n
x
)
,
(
y
x
S
n
)
,
(
1
y
x
S
1
x
n
x
Рисунок 7


n

 ,...,
1 1
x
n
x
Рисунок 8
Результат, полученный в виде формулы (3), может быть получен при более общих начальных положениях. Пусть
   


x
x
f

,

– произвольная булева функция с задержками, причем существуют два набора 
и  такие, что
)

(
)

(
2 1









. Составим матрицу:














n
n
n
r
k
j
i
x
x
x
x
x
x
1 0
1 0
1 1
0 0
1 1
1
Разобьем все переменные на группы: к группе
1
N отнесем переменные, под которыми в матрице стоит столбец
 
T
0 0
, аналогично к группе
2
N – столбец
 
T
1 0
, к группе
3
N – столбец
 
T
0 1
, к группе
4
N – столбец
 
T
1 1
, при этом некоторые переменные могут быть фик- тивными. Осуществим подстановку в функцию
 
x
f : на места переменных группы
1
N под- ставим константу 0, на места переменных группы
2
N подставим
x , на места переменных группы
3
N подставим x , на места переменных группы
4
N подставим 1. При склеивании всех входов получим функцию
 
x

, зависящую существенно от не более одного переменного функционально, но по задержке она сущест- венно зависит от этого переменного, так как
 
1 0




,
 
2 1




. Рассмотрим четыре случая.

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
59 1.
 
0

 x
. Тогда
 
x
x 

дает тождест- венную функцию
x с задержками
 
1 0



x
,
 
2 1



x
. (4)
2.
 
1

 x
. Тогда
 
x
x &

дает тождест- венную функцию с задержками (4).
3.
 
x
x 

. Тогда
 
x

дает тождественную функцию с задержками (4).
4. Наконец
 
x
x 

с задержками (4).
Таким образом, получаем следующий ре- зультат: для получения формул (3) достаточно иметь базис в
2
P с нулевыми задержками и произвольную функцию
 
x
f с задержками
 
 











2 1
f
f
Замечание. Очевидно, что СУЗ можно использовать для контроля информации не только на входе схемы, но и в любом сечении схемы.
Дополнение. Приведем еще один пример применения задержки. Пусть имеется некоторая схема в базисе


,
&, 
с дифференцированными задержками, но
 
0 0 

,
 
1 1 

. В этой схеме требуется проконтролировать работу некоторой подсхемы

S
, реализующей функцию


k
y
y ,...,
1

. Для этого определим вспомога- тельную функцию:


















,...,
,
0
,
,...,
,
1
,
,...,
1 1
1 1
1 1
k
k
k
k
k
k
y
y
y
y
y
y
y
y
y
если если
Ей отвечает схема

S
в базисе


,
&, 
(без задержек).
Рассмотрим схему на рисунке 9.
k
y
1
y

S

S
&
y
z
z
x
)
,
( y
x
S














Рисунок 9
Если подсхема

S
выдает на выходе ошибку


k
y
y
y
,...,
1


, то подсхема

S
выдает на вы- ходе 1, которое задерживается на l единиц.
Концевая подсхема


y
x
S
,
выдает на выходе y с задержкой l . Если подсхема

S
работает вер- но, то есть на ее выходе реализуется верное зна- чение


k
y
y
y
,...,
1


, то подсхема

S
на выходе реализует значение 0, которое без задержек достигает входа
x концевой подсхемы


y
x
S
,
Выводы
1. Дан пример базиса с элементами диффе- ренцированной задержки, в котором в виде макета построено селекторное устройство с такими дифференцированными задержками, что каждая входовая комбинация имеет свою, присущую только ей задержку. Селекторное устройство может быть подсоединено на вход любого булева оператора  (без задержек) так, что новый булев оператор  имеет такие же дифференцированные задержки, как и селек- торное устройство.
2. Описаны все базисы, состоящие из полных систем функций с нулевыми задерж- ками и с добавлением функций с ненулевыми задержками, позволяющие построить селек- торное устройство с дифференцированными задержками.
3. Приведен пример применения задержки для контроля работы выделенных подсхем данной схемы.
Библиографический список
1. Бирюкова Л.А., Кудрявцев В.Б. О полноте функций с задержками // Теория управляющих систем// Проблемы кибернетики, вып. 23. – М.:
Наука. 1970. – С. 5-26.
2. Лупанов О.Б. О схемах из функциональных элементов с задержками// Проблемы кибернетики, вып. 23. – М.: Наука. 1970. – С. 43-82.
3. Бирюкова Л.А. Вопросы

-полноты для функций с задержками // Проблемы кибернетики, вып. 31. – М.: Наука. 1976. – С. 53-76.
4. Храпченко В.М. Различие и сходство между глубиной и задержкой //Проблемы кибернетики, вып.
35. – М.: Наука. 1979. – С. 141-168.
5. Ложкин С.А. Поведение функции Шеннона для задержки схем из функциональных элементов в некоторых моделях //Тезисы докладов XII между- народной конференции «Проблемы теоретической кибернетики» (17-22 мая 1999 г.).

60
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
УДК 510
Г.С. Орлов
СЛУЧАЙНЫЕ ПРОЦЕССЫ НА БАЗЕ ОБОБЩЁННЫХ
ДИНАМИЧЕСКИХ ВЕРОЯТНОСТНЫХ НАГРУЖЕННЫХ ГРАФОВ
Описывается процедура построения случайного процесса на базе
обобщённых динамических вероятностных нагруженных графов. Анализиру-
ются её основные характеристики и свойства, даются определения
сопутствующих понятий.
Ключевые слова: динамическийвероятностный нагруженный граф,
случайный процесс, случайный граф, математическое моделирование.
Введение. Цель работы – описать процедуру построения случайного процесса, в основе которого лежит новый математический объект – обобщённый динамический вероятностный наг- руженный граф (ОДВНГ), рассмотреть её характерные особенности и ввести определения сопутствующих понятий.
Рассмотрим ОДВНГ [1]


G
G
P
X
G
,

, у которого


n
j
G
x
x
x
X
...,
,
...,
,
1

- множество вершин, а
 
 
 


n
j
G
S
S
S
P
...,
,
...,
,
1

- множество дуг и петель.
Причём
 


jn
jk
j
j
j
U
U
U
U
S
...,
,
...,
,
,
2 1

есть множество дуг (петель при
j
k  ), исходящих из вершины
G
j
X
x 
, а
 
 




jk
l
jk
jk
jk
def
jk
U
U
U
U
...,
,
,
2 1

- множество дуг из вершины
G
j
X
x 
в вершину
G
k
X
x 
. В соответствии с определением
ОДВНГ [1] будем считать, что в каждый момент времени
T
t 
определены вероятности сущест- вования вершин графа
 


n
j
x
P
j
t
,
1

и веро- ятности существования дуг
 
 
t
p
i
l
jk
. Обозна- чим через






G
G
X
x
x
x
X
B
...,
,
,
...,
,
,
2 1
1


булеан множества вершин
G
X
, все элементы которого упорядочены каким-либо способом (то
есть имеют порядковые номера), соответствен- но через
 
 
 
 




jk
jk
jk
jk
jk
U
U
U
U
U
B
...,
,
,
...,
,
,
2 1
1


- все возможные булеаны множеств
jk
U
, также с упорядоченными элементами. Элементы конк- ретного булеана могут быть упорядочены любым способом, однако при этом они должны быть ранжированы по числу содержащихся в них элементов, то есть элемент булеана с меньшим числом элементов обязан иметь меньший порядковый номер, чем элемент булеана с большим числом элементов. Будем считать, что в каждом конкретном временном сечении может существовать один и только один элемент каждого такого булеана. Иначе говоря, если


 
 
 


)
...,
,
,
(
...,
,
...,
,
2 1
1
j
s
j
j
j
m
j
b
b
b
B
B
B
B
B


- упорядоченная каким-либо способом совокуп- ность всех определённых ранее булеанов, то для элементов
 
j
i
b
каждого из них в любой момент
T
t 
определен закон распределения вероят- ностей
 
 
 
 
 
 
 
 
 
 
 
 















1
,
1 1
1
s
i
j
i
t
j
s
t
j
i
t
j
t
j
s
j
i
j
j
b
p
b
p
b
p
b
p
b
b
b
t
p
B
, ставящий в соответствие каждому элементу булеана вероятность его существования в дан- ном временном сечении.
Пусть
 


r
ij
ij
ij
j
i
b
b
b
b

...,
,

,

2 1

- произвольный элемент булеана
j
B
. Если все события вида: «в данный
момент
T
t 
существует элемент
1

k
ij
b
мно-
жества
 
j
i
b
булеана
j
B
» и «в данный момент
T
t 
существует элемент
2

k
ij
b
этого же мно-
жества
 
j
i
b
булеана
j
B
» считать независи- мыми (независимость в совокупности), то веро- ятность существования соответствующего элемента булеана
(множества
 


r
ij
ij
ij
j
i
b
b
b
b

...,
,

,

2 1

) будет равна
 


 



r
k
k
ij
t
j
i
t
b
p
b
p
1

, где через
 
k
ij
t
b
p

в данном случае обозначена вероятность сущест- вования элемента
k
ij
b

(то есть – определённой

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
61 вершины или дуги ОДВНГ


G
G
P
X
G
,

) в момент времени
T
t 
. Таким образом, если в любом временном сечении
T
t 

события, состоящие в существовании тех или иных вершин и дуг (в рамках одного булеана) графа


G
G
P
X
G
,

, считать независимыми в совокупности, то, зная величины
 


n
j
x
P
j
t
,
1

и
 
 
t
p
i
l
jk
, мы можем найти вероятность существования любого элемента любого булеана в момент
t

. Для выполнения условия нормировки
 
 
1 1



s
i
j
i
t
b
p
перейдём к нормированным вероятностям существования элементов булеана
 
 
 
 
 
 



s
i
j
i
t
j
i
t
def
j
i
t
b
p
b
p
b
p
1

Таким образом, будем считать, что в каждом временном сечении
T
t 
определена многомерная случайная величина
[2]
 
m
B
t


:

, отображающая последова- тельность всех булеанов
B
в

m
мерное прост- ранство векторов
 
 
 


t
t
t
m



...,
,
,
2 1
, где
 


t
j

- порядковый номер элемента
 
 
j
t
j
b

j
-го булеана
j
B
, который (один из всех
элементов
j
B
) существует в момент времени
T
t 
Очевидно, что упорядоченная последова- тельность номеров элементов булеана
 
 
 


t
t
t
m



...,
,
,
2 1
однозначно опре- деляет для любого сечения
T
t 
ОДВНГ
 
 
 


t
G
t
G
P
X
t
G
,

, существующий в этом сечении. То есть в каждом временном сечении определена случайная функция
[2]
 
 
t
G
B
t


:

, отображающая множество булеанов во множество ОДВНГ. Таким образом, получаем случайный процесс
[2]


G
T
B
t




:
,

, где через
G

обозначено множество всех подграфов
ОДВНГ


G
G
P
X
G
,

Найдём основные числовые характеристики
 
m
B
t


:

. Если ограничиться моментами порядка не выше второго, то совокупность случайных величин
 
 
 


t
t
t
m



...,
,
,
2 1
можно характеризовать вектором средних и ковариационной матрицей [2]. Очевидно, что
 
 
 


 


 


 




...,
,
...,
,
,
2 1
t
M
t
M
t
M
t
M
t
M
m
j






Для каждого булеана определён закон распределения его элементов
 
 
 
 
 


 


 








j
s
t
j
i
t
j
t
j
s
j
i
j
j
b
p
b
p
b
p
b
b
b
t
p
B
1 1
, поэтому определён и закон распределения номеров данных элементов, то есть соответствие
 
 


 


 








j
s
t
j
i
t
j
t
b
p
b
p
b
p
s
t
p
N
2 1
1
Следовательно,
 


 










j
w
t
s
w
j
b
p
w
t
M
1

, где символом
 

обозначена целая часть числа

. Ковариационная матрица для
 
t

по определению
[2] равна
 
 
t
k
K
ij
t




m
j
i
,
1
,

, где
 
 
 




t
t
COV
t
k
j
i
ij


,
 
 




 
 






t
M
t
t
M
t
M
j
j
i
i








Соответствующая корреляционная матрица [2] будет
 
 
t
r
R
ij
t


, где
 
 
 


 


 


t
D
t
D
t
t
COV
t
r
j
i
j
i
ij






,
, а
 


 




 







s
w
j
w
t
j
j
b
p
t
M
w
t
D
1 2


Отметим характерные особенности случай- ного процесса


G
T
B
t




:
,

. Ясно, что в соответствии с вышеизложенным существование какой-либо дуги
 
l
jk
U
в момент
T
t 

не зависит от существования в этом же сечении
t

инци- дентных ей вершин
r
j
x
x ,
. Введём следую- щие определения.

1   2   3   4   5   6