Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
быть синтезирована. Например, элементарные логические функции И-НЕ и ИЛИ-
HE обе являются полными.
Глава 4. Многозначная логика в оптических вычислениях
117
Если отказаться от требования, что можно получить постоянные логические
функции f=0 и /=1, используя ЭЛФ, тогда условие получения всех возможных
логических функций из множества ЭЛФ относят к критерию слабой полноты
системы логических функций. Слабую полноту можно было бы рассматривать
как более практичное соображение, потому что разработчик логики обычно
осуществляет контроль по постоянным значениям входного сигнала. Множество
ЭЛФ является слабо полным тогда и только тогда, когда оно содержит ЭЛФ,
обладающие двумя свойствами: одну ЭЛФ, не являющуюся монотонной, и одну -
не являющуюся линейной.
Очевидно, что любое множество, являющееся полным, одновременно является и
слабо полным. ИСКЛЮЧАЮЩЕЕ ИЛИ никогда не является ни полной, ни слабо
полной. ЭЛФ ИСКЛЮЧАЮЩЕЕ ИЛИ и И являются слабо полными. Обе функции
сохраняют 0. Однако И является нелинейной, а ИСКЛЮЧАЮЩЕЕ ИЛИ -
немонотонной. Отдельные ЭЛФ, такие как И-НЕ и ИЛИ-HE, удовлетворяющие
требованиям слабой полноты, называются универсальными ЭЛФ. На этом
завершается короткое обсуждение возможных канонических логических
элементов для систем двоичной логики. В следующем разделе будет
рассмотрена одна из возможных многозначных систем, обладающих слабой
полнотой - модульные вычисления в ССОК-Такая система может быть
реализована в оптике различными способами. Некоторые из этих способов
будут описаны в последующих разделах.
4.3. Многозначные логические схемы, основанные на системе счисления в
остаточных классах (ССОК)
Обсуждение многозначных логических элементов начнем с рассмотрения
обладающего слабой полнотой множества элементов для выполнения операций
сложения и умножения по модулю р, являющемуся простым целым числом.
Операции сложения и умножения по модулю р образуют поле тогда и только
тогда, когда р является простым числом: существует только р различных
элементов, {0, 1, 2, ..., р-1}. Эта часть обсуждения заимствована из
работы [5]. Рассмотрим произвольную функцию /, имеющую значение /(0)=со,
/(1)=си ..., f(p- l)=cp_i. Всегда может быть составлен полином вида
р-1
f (х) = 2 щх1 (mod р). (4.3)
"= о
Чтобы убедиться в этом, рассмотрим следующую систему уравнений:
118
Часть II. Многозначная и пороговая логика
Таблица 4.2. Обобщенная спецификация таблицы истинности для многозначной
переключающей функции двух переменных f(x, у)
У!х 0 1... р-1
0 соо С01 С0(р-1)
1 С10 сч с1(р-1)
Р- 1 с(р-1)о с(р-1)1 с(р-1)(р-1)
Сп Чп
С1 - а0 + а\ + а2 аР-1
Съ == й0 + 2й! + 22а2 2р 1йР_1
Cp-i = a0+(p~ 1)^1+ (р- 1)2й2+ • • • +(/°- 1)р_1йр-1- (4'4)
В матричной форме эта система выглядит как: с=Уа, где с и а вектор-
столбцы, с=(с0, сь ср-х)т и а= (а0, ai, ар_i)r, где Г обозначает
транспонирование, а V - матрица Вандер-монда [6].
10 0 ... 0
11 1 ... 1
1 2 22 ... 2Р-1
1 р-1
(4-5)
(4-6)
(р-1)2 ... (р- 1Г1
Матрица У является обратимой, потому что вычисления детерминанта (см.
[5]) дают величину
det V ~ 1!2!3! ... (р- 1)1 ^ 0 (mod/?),
являющуюся ненулевой, если р - простое число. Таким образом, видим, что
любая переключающая многозначная функция одной переменной в ССОК может
быть представлена как полином порядка (р-1) по модулю р.
Этот результат может быть распространен на многозначную переключающую
функцию двух переменных f(x, у). Для простого р каждая из рр* функций
двух переменных может быть
Глава 4. Многозначная логика в оптических вычислениях 119
определена в табл. 4.2, являющейся эквивалентом полинома вида
fix, у) =/о (х) + /i (х) у + /i (х) г/2 + ... + / р-! (х) yp~l (mod р),
где (4.7а)
fi (х) = a0; -f- axix -ря2гХ2 -f- . . . +й(р_!) ixp 1 (mod p).
(4.76)
Пример 4.2
Рассмотрим трехуровневую переключающую функцию двух переменных f{x, у) в
ССОК, определенную в табл. 4.3. Данная
Таблица 4.3. Троичная переключающая ССОК-функция двух переменных
У/х 0 1 2
0 1 1 0
1 2 0 2
2 2 0 2
функция может быть представлена как полином двух переменных, где под
операциями понимаются операции по mod 3
f{x, г/)= 1 +2х + х2 + у2 + х2у2 (mod 3).
Пример 4.3
Рассмотрим более сложную трехуровневую переключающую функцию f(x, у),
определенную в табл. 4.4. Ниже представлен
Таблица 4.4. Вариант переключающей ССОК-функции двух переменных
У/х 0 1 2
0 1 2 0
1 2 2 1
2 0 0 1
непосредственный способ получения переключающего полинома. В общем виде
полином будет иметь вид
/ (х, у) =а0 + а^х + а2у + адх2 + а^2 + аъху + авх2г/ + а7хг/2 + а8х2уг.
120
Часть II. Многозначная и пороговая логика
Вычислим коэффициенты а:
/(0, 0) = 1 а0 = 1
/ (0, 1) = 2 и 1 + а2 + а4 = 2 f (0, 2) = 0 1 -f- 2а2 -f- а4 = О
2 + 2 а4 = 2 а4 = О
а2 = 1
/ (1 > 0) = 2 1 -f- ах + о3 = 2
f( 2,0) = 0 1+2о1 + а3==0
2 + 2а3 = 2 а3 = О
а4 = 1
1 +х + у + аъху + аях2у + а.хуг + а6х2у2 /(2, 2) = 1 2 + а5 + 2а6 +
2а, + а8 = 1
/ (2, 1) = 1 1 + 2а5 + ав + 2а, + а8 = 1
+
/ (1" 2) = О 1 + 2о5 + 2а6 + а, + а8 = О
