4.3. Многозначные логические схемы, основанные на системе счисления в остаточных классах (ССОК)

Обсуждение многозначных логических элементов начнем с рассмотрения обладающего слабой полнотой множества элементов для выполнения операций сложения и умножения по модулю являющемуся простым целым числом. Операции сложения и умножения по модулю образуют поле тогда и только тогда, когда является простым числом: существует только различных элементов, Эта часть обсуждения заимствована из работы [5]. Рассмотрим произвольную функцию имеющую значение Всегда может быть составлен полином вида

Чтобы убедиться в этом, рассмотрим следующую систему уравнений:

Таблица 4.2. Обобщенная спецификация таблицы истинности для многозначной переключающей функции двух переменных

В матричной форме эта система выглядит как: где с и а вектор-столбцы, где Т обозначает транспонирование, матрица Вандер-монда [6].

Матрица V является обратимой, потому что вычисления детерминанта (см. [5]) дают величину

являющуюся ненулевой, если — простое число. Таким образом, видим, что любая переключающая многозначная функция одной переменной в ССОК может быть представлена как полином порядка по модулю

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

определена в табл. 4.2, являющейся эквивалентом полинома вида

где

Пример 4.2

Рассмотрим трехуровневую переключающую функцию двух переменных в ССОК, определенную в табл. 4.3.

Таблица 4.3. Троичная переключающая ССОК-функция двух переменных

Данная функция может быть представлена как полином двух переменных, где под операциями понимаются операции по

Пример 4.3

Рассмотрим более сложную трехуровневую переключающую функцию определенную в табл. 4.4.

Таблица 4.4. Вариант переключающей ССОК-функции двух переменных

Ниже представлен непосредственный способ получения переключающего полинома. В общем виде полином будет иметь вид

Вычислим коэффициенты а:

Следовательно, в результате получается полином

Один из способов убедиться в том, что эта процедура всегда работает, — это рассмотреть окончательный вид табл. 4.5. Рядом с входными сигналами функции приведены произведения четырех термов, составленных так, чтобы произведение равнялось нулю, если значения х и у не удовлетворяют соответствующему входному сигналу. Чтобы получить значение функции, каждый член вычисляется при соответствующем входном сигнале и умножается на соответствующую константу. Теперь для получения окончательного вида полинома можно было бы перемножить

Таблица 4.5. Второй способ представления троичных переключающих функций из табл. 4.4

между собой все члены в выражениях и сложить по модулю 3.

Отметим, что методы преобразования многозначной таблицы истинности в полиномы не приводят к минимальным выражениям для аппаратной реализации. Рассмотрим пример 4.2, в котором был получен полином

Если бы двумя типами устройств, которые необходимо использовать, являлись 2-входовые сумматоры и умножители, тогда достаточно простая реализация могла бы выглядеть так, как показано на рис. 4.1. Однако не сложно обнаружить, что может быть преобразована к виду

Если реализовать непосредственно это выражение, то получим схему из трех сумматоров и четырех умножителей. Чтобы при неизменном числе сумматоров уменьшить число умножителей до 3, необходимо отметить, что

Схема для последнего выражения показана на рис. 4.2. К сожалению, не существует общих алгоритмов работы с полиномиальными уравнениями, позволяющих достичь минимальной степени сложности схем; в данном случае следует полагаться на способности и интуицию разработчика.

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

С помощью теоремы Ферма [7] эта функция может быть выражена как и

где . Для переключающей функции переменных, где значение функции при составляет Окончательное выражение имеет вид

где

Пример 4.4

Элементарными функциями по модулю 3 являются

Если умножение производится по модулю являющемуся простым числом, то в ССОК модульное умножение может быть сведено к операции сложения. Процедура основывается на представлении в степенном виде. С помощью теоремы Ферма [7] можно показать, что существует такое именуемое генератором число что, будучи возведенным в степень дает 1 по т. е.

Для этих чисел составлены таблицы (см. [23]). Возводя генератор в соответствующие степени, все числа могут быть представлены в виде выражений по модулю При использовании в ССОК этих экспоненциальных представлений чисел умножение может быть заменено сложением показателей степеней. Можно показать, что это сложение имеет модуль

Пример 4.5

Умножим 3 на 4 по модулю 5, используя метод сложения показателей степеней. Генератором по модулю 5 является 2. Таким образом, используя этот генератор, получаем

Заметим, что, во-первых, следуя теореме Ферма, «наибольшее» значение показателя степени составляет , во-вторых, нуль не может быть получен, и, следовательно, эта процедура должна быть учтена отдельно. Таким образом, для того чтобы умножить 3 на 4, складывают соответствующие им значения показателей степени, а именно Данный показатель

затель степени, являющийся эквивалентом логарифма, соответствует значению 2.

Процедура генерирования значения показателя степени для заданного генератора и простых модулей называется прямым -преобразованием. В свою очередь генерирование символов из значений показателей степени называется обратным -преобразованием. И то и другое преобразование эквивалентно операции перестановки. Если операции перестановки допустимы, то необходимо только модульное сложение.

Закончим краткий экскурс в многозначную логическую алгебру ССОК и перейдем к рассмотрению оптической реализации операций ССОК.