Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
логика.
Пример стандартной, или построенной на линейных неравенствах пороговой
логики наглядно показан на рис. 5.1. Здесь логическая функция y =
xlx2xixi-\-xiX3 (для которой дана таблица истинности) реализуется с
помощью пороговых логических элементов, у которых Х\, х3, х3 и х4-
входные двоичные сигналы, у- двоичный выходной сигнал, знак "+"
обозначает операцию ИЛИ, подразумеваемое умножение является операцией И,
а .черта - операцией НЕ. Элемент умножает каждый двоичный входной сигнал
на действительное число, являющееся весовым коэффициентом ((r)ь ш2, w3 или
до4),
144
Часть II. Многозначная и пороговая логика
сумм'ирует результаты и сравнивает их с пороговым действительным
значением Т. Если сумма меньше порогового значения, то выходной сигнал
равняется 0, в противном случае-1. В приведенном примере следует обратить
внимание на то, что единственный пороговый элемент реализует логическую
функцию, которая потребовала бы нескольких обычных булевых вентилей и
двух уровней логики,(трех уровней в том случае, если присутствует
операция НЕ). Следует также заметить, что, во-первых, пороговый элемент
будет правильно срабатывать в случае, если порог является любым числом,
удовлетворяющим условию 4<Г^5, и, во-вторых, если допустимое отклонение
значения порога ограничено, тогда могут быть определены ненулевые
допустимые отклонения весовых коэффициентов.
В общем пороговые логические элементы с линейными неравенствами имеют
несколько двоичных входов, один двоичный выход и встроенное аналоговое
устройство, пригодное для работы с оптикой (некоторые конструкции
элементов допускают применение дискретных встроенных устройств [13] и
несколько двоичных выходов .[14]). Как показано на рис. 5.1, можно
добиться, чтобы пороговый элемент работал корректно даже в случае
отклонения значения порога и веса от номинальных величин, что возникает
вследствие внешних условий, погрешностей при /изготовлении прибора и т.
д. Из таблицы истинности на ,рис. 5.1 видно, что соответствующие величины
веса и порога могут быть получены путем решения системы линейных
неравенств. Например, Л2-я строка таблицы истинности требует, чтобы
wxxt + w^ca + ю4х4 5= Т. (5.1)
-^ W? = 2
> II
w3 = 3 4 <Т <3
> W4 = 1
W,X, + W2X2 + W3X3 + W4X4 f<T, Y = 0 1 >T, Y = 1
^2 *3 Х4 У
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 О
1 1 1 1
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
Ряс. 5.1. Пример порогового логического элемента, выполняющего функцию .
у=х\Х2*3*4+XiX3: а--пороговый элемент; б - таблица истинности,
Г лава 5. Пороговое кодирование и взвешивание в вычислениях
145
Обычно число неравенств превышает число неизвестных (в приведенном
примере 16 неравенств, или строк таблицы истинности цриходится на ,5
неизвестных wu w2, Шз, Wt и T)> однако .решения будут существовать не
всегда. Тем не менее существующие решения, определяющие максимальные
допустимые отклонения различных порогов и весов, могут быть определены с
помощью методов линейного программирования. Большинство ранних работ ,по
пороговой логике было посвящено нахождению таких решений или их
характеристик без явного применения методов линейного программирования,
часто требующих проведения обширных вычислений. Совершенствование
вычислительной техники и алгоритмов, однако, сделало использование
линейного программирования для разработки пороговых логических элементов
и схем более привлекательным [15].
Как показано выше, не все логические функции могут .быть реализованы с
помощью пороговых логических элементов с одним линейным неравенством; те
из них, которые могут быть реализованы, называются пороговыми, или
линейно-разделяемыми функциями. В целом существует 22" логических функций
п двоичных переменных (каждая из 2п входных строк таблицы истинности
может иметь любой двоичный выход), но число пороговых функций обычно
намного меньше - верхний предел их числа составляет (2п +1)/п1. Например,
если п = 3, полное число функций равняется 256, верхнее предельное
значение составляет 170, а фактическое число функций оказывается равным
404 [10]. Для п = 2 (простейший случай) можно легко показать, что 14 из
16 возможных булевых логических вентилей с двумя входами, включая И и
ИЛИ, могут быть реализованы с помощью единственного порогового элемента;
таким образом, линейные неравенства пороговой логики можно рассматривать
как более общий случай булевой логики. Поскольку любые комбинационные
логические функции ;(с таблицей истинности из постоянных значений) .можно
реализовать на основе системы вентилей или элементов с не более чем двумя
уровнями булевой логики (т. е. сигнал в системе не должен проходить более
двух последовательно соединенных логических вентилей, исключая вентиль
НЕ), то оказывается, что то же самое справедливо для пороговой логики.
Однако (булевы логические схемы для сложных функций (например, 16-
разрядный умножитель) обычно требуют более двух логических уровней, чтобы
