Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf

Скачать файл (15,00Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 123

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Поскольку каждый /-й набор может входить в выражение (3.48) по нескольку раз (в этом мы убедились на примере модели

рования функции 1 — е~х ), то логическая схема Л П может иметь различные конструкции в зависимости от выбранной ДСНФ логической функции. В частности, совсем не обязательно (как это принято настр. 120), чтобы логическая схема Л П в структуре линейного преобразователя вероятность — вероятность выпол няла функцию сравнения кодов А и X. Для реализации заданной зависимости важно лишь, чтобы любая ДСНФ логической функ ции содержала одинаковое число /с;- членов для каждого из /-х

наборов.					функции Л П не
Для нахождения ДСНФ переключательной
обходимо	перейти от		вычисленных значений		коэффициентов г0,
r lt г2, . .	., rt к	значениям		коэффициентов	выражения	(3.51),
т. е. определить		к 0,	к 2, .	. ., &2/ . Обращаясь к		зависи

мостям (3.51) и (3.52), заметим, что индексы при коэффициентах к ,

объединяемых равенством с г 15	определяются рядом
2-, 24_3,	24' 2, 24"1.	(3.62)
Индексы при коэффициентах, объединяемых равенством с г2,
определяются как все возможные и неповторяющиеся		парные

суммы из членов ряда (3.62), при коэффициентах, объединяемых

равенством с г 3,	— как	все тройные суммы из членов		ряда (3.62)
и т. д.	к 0 =	г 0, а к 15 = г4.
Кроме того,	к 0 =	г 0, а к 15 = г4.	По индукции	для любого
ненулевого I получим трансформацию ряда (3.62) в последователь
ность
		2°, 2\ 22, . . .,	21"1,	(3.63)

а к 0 = г 0 и к21_г - Г[.

На практике процесс поиска нужных индексов при коэффи циентах к можно существенно упростить, если искомые индексы отождествить с одинаковым количеством единиц в двоичном

представлении каждого индекса. Так,	например, к 3 = къ = г 2,
так как Зс10) = 11(3)Т а 5(10) = 101(2)	и сумма единиц в обоих
разложениях равна двум.

Так для рассмотренного выше примера воспроизведения зави

симости
имеем	1,5 ( I - е -* )
имеем
1,5 (1 —e“z ) =	(24р — 12р2 + 4р3 —р4),	(3.64)

где р представляет машинную переменную X.

Пользуясь указанным алгоритмом нахождения индексов для коэффициентов к, получаем: к 0 = г 0 = 0, к г = к 2 = k t = ка =

130

г i 6, к 3	к3	к3	к3—■кхз— к 12 — г2 — 16? ^7 — —'
— к is — А:44 =	гз =	13,	кхз — г4 = 15.

Теперь несложно записать любую ДСНФ переключательной функции устройства, реализующего зависимость (3.64). Возвра щаясь к выражениям (3.47) и (3.48), определим все множество

возможных ДСНФ		в виде
2 = xmaxa2a3ax V		(a1a2a3ai V а ха2а3ах V		аха2а3ах V аха2а3ах) \]
	\]xm (аха2а3ах V	аха2а3ах V % а 2а 3а 4 V о,ха2а3ах V аха2а3аАV
V аха2а3ах) V ■Д3’ (а1а2а3а4 V аха 2а3ах V аха2а 3ах \/ аха2а3ах) V
		\J xw axa2a3ax,				(3.65)
где	.	Т1
			i = 0, 1,	2, 3,	4,	(3.66)
	хм — Ух^'х^х^х^,
и дизъюнкция берется по всем наборам				<р4,	\|32, р3, р4 >	, где
2 =	1.
Таким образом, количество слагаемых в выражении для						ФАЛ
х Н)	определяется значением г,-,		а всего	может	быть построено
Cj+s	различных функций х (1) (для каждого i),				так как по усло

вию в уравнения (3.66) элементарные произведения могут под ставляться в любом порядке.

Так, например, для рассматриваемого случая воспроизведения

зависимости (3.64) имеем: г 0 =		0, а потому х10) = 0, но уже гх = 6
и ФАЛ х(1) может иметь Схв =		8008 модификаций. Вот некоторые
из них:
я !1’ = ххх2х3х4 V	ххх2х3х4 V		ххх2х3х4 V	ХХХ2Х3ХХ V
V	ххх2х3хх V		ххх2х3хх,	(3.67)
х [ и = X 1x 2x 3x i V X1X 2X3Xi	V Xl X2X3Xi		V X1X2X3Xi V	Х 2Х 2Х3Х4 V ххх2х3хх,

^8008 = X l X2X3Xn V XXX2X3XA V ХХХ2Х3Х 4 V X VX2X3X4 V XxX2X3X4 \ Jxxx2x3xx.

(3.68)

Подобные же семейства функций алгебры логики хН) можно построить и для остальных i (2, 3, 4).

Выбор той или иной ФАЛ из этих семейств функций в конеч ном счете будет определять сложность технической реализации ФГ1ВВ. Поэтому для уменьшения затрат оборудования можно рекомендовать такие способы расстановки единиц в столбце 2

таблицы истинности,	при которых для каждого j -то набора из
9:	131

< a l5 a 2, . . .,a ; > наборы < р г, § 2, .. .,|Зг > следуют подряд, начиная с любого нечетного номера, так как в этих случаях возможно наибольшее число склеиваний. При этом безразлично, начинаем

ли мы нумерацию (1,	2, 3, ...) с	набора 000 ...	0	или с набора
111.... 1.
Будем, например,	записывать	все наборы < р		р 2, . . .,(3, )

подряд, начиная с набора 111...1. Тогда для ускорения процесса нахождения минимальной формы для функций х (г) воспользуемся алгоритмом, блок-схема которого приведена на

рис. 60.


		Алгоритм				основан на
		следующих положениях:
		1. Если в элементар
		ном	произведении					дизъ
		юнктивной				нормальной
		формы функции xli> коли
		чество букв Ж;1’ увеличи
		вается на единицу, то ко
		личество наборов, харак
		теризующих эту конъюнк
		цию,	уменьшается					вдвое.
		Например, для I =					5 ха> =
		= х 1х 2,			к 1 =	8,		х <2> =
конец.		— x xx 2x s,			к 2 = 4.			Таким
конец.		образом,			к х/к 2	=	2.
Рис. 60. Блок-схема	алгоритма нахож	2.	Если к сумме,					содер
дения МДНФ	функций x(i)	жащей		п	дизъюнктивных
		членов,		добавить еще один

п + 1 член, то количество наборов, характеризующих новую ДНФ, увеличится на 21~п~1.

Папример,

для

I = 5 хш

= х х V х 2,

к х =

24,

xi2) — х х V

\J x 2 \J ж3,

к 2 — 28,

к 2 — к х =

25-2-1 = 4.

Для

того

чтобы

воспользоваться

алгоритмом

на рис. 60,

данное

необходимо представить в двоичном коде

1+S

Л/- 2

2'+s-% ,

где bt — разрядные

коэффициенты.

Пример. Пусть

Z+

s = 6

к, =

49,... =

110001,,., т. е.

Ьг = 1,

Ъ2 =

1, bs =

b4 =

Ъь =

ь\ =

Тогда,

проходя

алгоритм,

получаем:

1. хН) — 0,

7 =

СчЬ =

2. Так

как

Ъх *= 1,

то xli) =

0 \J lx ,

= х ,.

3. C 4b = 4 + l - 2= fZ +

s + l = 7.

4. Так

как

Ъ2 =

то х н>

х х V

1 ,ж2=

X/ х 2.

5. Сч Ъ = 2 + 1 = 3 Ф 7.

132

6.	Так как	bs — 0,		то у =	1 х 3 = х 3.
7.	Сч Ъ = 3 + 1 =			4 =h 7.
8.	Так как	&4 = О, то у =			х3х4.
9. Сч Ъ = 4 + 1			= 5 4 . 7.		х 3х4хъ.
10.	Так как	65 = 0, то у =			х 3х4хъ.
И . Сч Ъ = 5 + 1 = 6 ф 7.
12.	Так как	Ь6 =	1,	то х(г> =	х г \/ х г \/ х 3х4хъх&.
13.	Сч Ъ = 6	+ 1	=	7. Конец. В результате получаем

хш = xt V х2V х3а:4х5а:в.

Пользуясь такими же приемами, определим функции алгебры логики (3.66) в виде

я‘0) = 0,

ха >= xi {х2 V хз)’

х(2) = *1 V Х2Х3,

£<3) = *1 V Х2 V Х3Х4,

Х(4) = хг < $ < & < н

Подставляя полученные зависимости в уравнение (3.65), окон чательно запишем

z — x1 (х2 V ^з) (a1aia3a4 V d1d2d3di \J ага2а3а 4 V а4а2а3а4) V

V (^1 V Ж2Ж3) (д4#2&з&4 V ^iP2^3^4 \/ d4d3d3d4 V d-yd3d3d4 \J d4dod3d4 \/

V d^d^d^d^) V	\! х%\! хЗхд	( а Ха 2 а За 4 V d4d^d3d4V d4dzd3d4V
V	«1«2а з«4) V Он V	^2 V a;3 V г 4) «1а2а з®4-	(3.69)

Проверим, действительно ли логическая схема, построенная на основе ФАЛ (3.69), реализует требуемую зависимость (3.64). Заметим, что при р (хх) = р (х2) = ... = р (xt) = 0,5 из уравне ния (3.66) вытекает

р [*«>] = г<2-‘^».

(3.70)

Если к тому же добавить, что все дизъюнктивные члены уравне ния (3.69) ортогональны, найдем

р (z) = 2-4 [6 •4р (1 —р)3 + 1 0 •6р 2(1 —р)2 + 1 3 •4р3 (1 —р) + 15р4].

Раскрывая скобки и приводя подобные члены, получим

р (z) = ^ (24р —12р2 + 4р3 —р4),

что и требовалось доказать.

Функциональные преобразователи, построенные на основе ФАЛ (3.65), характеризуются еще одной особенностью. Нетрудно

133

заметить, что выражение (3.65) не изменится, если мы попытаемся реализовать иную нелинейность, взяв то же самое количество I членов степенного ряда (3.55). Изменятся лишь значения коэф фициентов х(г) (£ = 0, 1, 2 ,. . ., I). Это позволяет построить так называемую полууниверсальную структуру ФПВВ на рис. 61, состоящую из двух частей, одна из которых (Б 1 ) одинакова для всех зависимостей, представленных первыми I членами степенного ряда, а вторая (Б2) является специальной и характеризует кон кретный тип воспроизводимой нелинейности. На том же рисунке

представлен также уже известный (см.			стр. 56) способ разветвле
	s i 1	ния	входящей					последователь-
I		ности	на	основе				регистра сдви-
		висимых входов по перемен
		ной А.
		Определим					время		интегри
		рования. Будем считать, что по
		следовательности Х 1 , Х 2> . .
		действующие				на		входах Л П 2
		(рис. 61), стационарны и неза
		висимы;		тогда в				силу	того, что
		Л П 2	не	имеет				запоминающих
Рис. 61. Блок-схема полуунивер-		элементов,			последовательности
		/у»*(Оо/	/^(i)у,\X/		^/у».(2)		_		ухи также
сального ФПВВ:		1А/ у	\|А/	у	(I/
		носят бернуллиевский характер.
Рг — регистр сдвига; ЛЛ ,,	ЛЛ,
ческие преобразователи		Таким образом,					значения х[1) не
		зависимы для				любых			моментов
		времени т			(0,		1,	2, 3, . . .).
С другой стороны,	использование регистра сдвига Рг для раз

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

гистра.				а, хм , z смысл временного
Присвоим индексам	переменных
параметра т, тогда, учитывая (3.47), запишем:
ь = <Pi l4 0)1		~(1)	••i	)	а Ъ а21 • •	., а,1
		~(1)	» •■
			»* . X2	, а 2, а3, . . •>a !+ll
zt+1= ф2 [4 0)>х2
Zt+2 ==Фз 14°\	~(1)		™С/)		«3, ^4* ♦••> ®/+21>
			•1 Л'З	1
zt+i-i --= ф/[4°\	х\и ,		. . м х\1\		O'lt &1+1? •••1
Zt+l =z Ф/+1 [4°А,					, . . ., a2l\
	4\ г, •■., 4+1 , Я;+1, &1+2

Отсюда видно, что в течение I последовательных тактов зна чения выходной переменной ФПВВ действительно оказываются коррелированными. Следовательно, для расчета времени интегри-

134

Смотрите также файлы

Алимарин, И. П. Качественный и количественный ультрамикрохимический анализ.pdf

Аполлов, Б. А. Курс гидрологических прогнозов учебник.pdf

Барон, Л. И. Износ и защита внутренних поверхностей угольных бункеров.pdf

Бастарева, Л. И. Петропавловская крепость [иллюстрированный путеводитель].pdf

Богданов, В. И. Вычисление гравитационных аномалий от трехмерных тел (графические способы).pdf

Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно