Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
+
/(!" О = 2 0 + а5 -f- а8 + Я7-Ь°8==2
1 а8 = 1
а8 = 0
1 2а, = 2
2а, = 2
2 + а5 =1
а5 =2
2 + 2 + 2а6 +1 +0=1
2а6 + 2 =1
2а" =2
а6 = 1
Следовательно, в результате получается полином f(x, у) = \+х + у + 2ху +
х2у + 2ху2 (mod 3).
Один из способов убедиться в том, что эта процедура всегда работает,- это
рассмотреть окончательный вид табл. 4.5. Рядом с входными сигналами
функции приведены произведения четырех термов, составленных так, чтобы
произведение равнялось нулю, если значения х и у не удовлетворяют
соответствующему входному сигналу. Чтобы получить значение функции,
каждый член вычисляется при соответствующем входном сигнале и умножается
на соответствующую константу. Теперь для получения окончательного вида
полинома можно было бы перемножить
Глава 4. Многозначная логика в оптических вычислениях
121
Таблица 4.5. Второй способ представления троичных переключающих функций
из табл. 4.4
X У f
0 0 1 (х+1) (х+2) (.(/4-1) (.V+2) 1
0 1 2 (х-И)(х+2) (//)((/+1) 2
0 2 0
1 0 2 х(х+1)(д+1)(1/+2) 2
1 1 2 х(х+1 )((/)(</-И) 2
1 2 0 0
2 0 0 0
2 1 1 (х)(х+2)(у)(д+1) 1
2 2 1 (х)(х+2)(у)(д+2) 1
между собой все члены в выражениях и сложить по модулю 3.
Отметим, что методы преобразования многозначной таблицы истинности в
полиномы не приводят к минимальным выражениям для аппаратной реализации.
Рассмотрим пример 4.2, в котором был получен полином
f (х, у) = 1 + 2х + х2 + у2 + х2у2 (mod 3). (4.8а)
Если бы двумя типами устройств, которые необходимо использовать, являлись
2-входовые сумматоры и умножители, тогда достаточно простая реализация
могла бы выглядеть так, как показано на рис. 4.1. Однако не сложно
обнаружить, что f(x, у) может быть преобразована к виду f(x, у) = 1 + 2х
+ х2 + у2 + х2у2
= (x+l)2 + y2{x2+l) (mod 3). (4.86)
Если реализовать непосредственно это выражение, то получим схему из трех
сумматоров и четырех умножителей. Чтобы при неизменном числе сумматоров
уменьшить число умножителей до 3, необходимо отметить, что
х2-\-1 =(x-f l)2 = 2x = (x-f I)2 -f x (mod 3).
Схема для последнего выражения показана на рис. 4.2. К сожалению, не
существует общих алгоритмов работы с полиномиальными уравнениями,
позволяющих достичь минимальной степени сложности схем; в данном случае
следует полагаться на способности и интуицию разработчика.
Вторым способом построения необходимой многозначной переключающей функции
f(x, у) является использование интерполяционных полиномов Ji(x). Эти
полиномы определяются как
11, если x - i,
Jt (•*) (q в противном случае. (4,9а)
122
Часть 11. Многозначная и пороговая логика
С помощью теоремы Ферма [7] эта функция может быть выражена как J0(x) =
(р-1)*р_1 + 1' и
Ji (х) = (р- 1) [xp-i + ixp~2 + i2xp~3 + ... + ip~2x], (4.96)
где 1г?Д'г?Ср-1. Для переключающей функции п переменных, где значение
функции при х = а составляет f(a)=Ki. Окончательное выражение имеет вид
Кх) = ад(х) + ад(х)+...+Яр_1</р-1(х), (4.10а)
где
Ja(x) = Jai(x1)Ja2(x2) ¦ ¦ ¦ Jap^iXp-г). (4.106)
Пример 4.4
Элементарными функциями h{x) по модулю 3 являются
J0(x) = 2х2+ 1,
Л (х) = 2 (х2 + х) = 2х2 + 2х,
J2 (х) = 2 (х2 2х) = 2х2 Ах.
Если умножение производится по модулю р, являющемуся простым числом, то в
ССОК модульное умножение может быть сведено к операции сложения.
Процедура основывается на представлении в степенном виде. С помощью
теоремы Ферма [7] можно показать, что существует такое именуемое
генератором число Ь, что, будучи возведенным в степень р-1, дает 1 по
modp, т. е.
ЬР~г= 1 (mod р). (4-11)
Для этих чисел составлены таблицы (см. [23]). Возводя генератор в
соответствующие степени, все числа могут быть представлены в виде
выражений по модулю р. При использовании в ССОК этих экспоненциальных
представлений чисел умножение может быть заменено сложением показателей
степеней. Можно показать, что это сложение имеет модуль р- 1.
Пример 4.5
Умножим 3 на 4 по модулю 5, используя метод сложения показателей
степеней. Генератором по модулю 5 является 2. Таким образом, используя
этот генератор, получаем
2° = 1, 2J = 2, 22 = 4, 23 = 3, 24 = 1.
Заметим, что, во-первых, следуя теореме Ферма, "наибольшее" значение
показателя степени составляет р-1=4, а, во-вторых, нуль не может быть
получен, и, следовательно, эта процедура должна быть учтена отдельно.
Таким образом, для того чтобы умножить 3 на 4, складывают соответствующие
им значения показателей степени, а именно 3+2=1 (mod 4). Данный пока-
Глава 4. Многозначная логика в оптических вычислениях
123
затель степени, являющийся эквивалентом логарифма, соответствует значению
2.
Процедура генерирования значения показателя степени для заданного
генератора и простых модулей называется прямым /(-преобразованием. В свою
очередь генерирование символов из значений показателей степени называется
обратным /(-преобразованием. И то и другое преобразование эквивалентно
операции перестановки. Если операции перестановки допустимы, то
необходимо только модульное сложение.
