К.т.н. Хмельник С.И.

Рассматриваются электрические цепи c линейными элементами и диодами, не содержащие транзисторов. Все потенциалы в этих цепях принимают только два значения. Анализируются требования, которым должны удовлетворять такие цепи. Устанавливается соответствие между такими цепями и схемами, построенными из дискретных элементов. В качестве дискретных схем такие цепи являются обратимыми в том смысле, что их выводы могут использоваться либо как входы, либо как выходы. При передаче сигналов через такую дискретную схему в одном (прямом) направлении вычисляется некоторая (прямая) функция алгебры логики. При передаче сигналов в другом (обратном) направлении вычисляется функция алгебры логики, которая является обратной относительно прямой функции. Указываются возможные области применения.

1. Введение

Логические элементы, используемые в вычислительной технике, являются нелинейными и активными. В статье рассматриваются схемы, которые не содержат транзисторов, а содержат только линейные элементы и диоды. Эти схемы подобны в определенном смысле логическим элементам AND, OR, NOT. Подобие заключается в том, что существуют такие потенциалы на входах и выходах этих схем, которые удовлетворяют функциям AND, OR, NOT алгебры логики. Кроме того, потенциалы и токи в указанных схемах удовлетворяют законам Кирхгофа. Поэтому они в общем случае могут и не удовлетворять функциям алгебры логики. В этом заключается различие между логическими элементами и указанными схемами, которые далее называются аналоговыми логическими элементами AND, OR, NOT или, сокращенно, элементами AnAND, AnOR, AnNOT.

Рассматривается определенная электрическая цепь, составленная из элементов AnAND, AnOR, AnNOT. Эта цепь далее называется аналого-дискретной схемой АД. Схема АД при определенных условиях ведет себя подобно обычным цифровым схемам. Принципиальное отличие заключается в следующем.

Схема АД имеет две группы выводов, х и у. Они могут использоваться либо как входы, либо как выходы схемы АД. Показывается, что при одном способе включения схема АД выполняет преобразование (назовем его прямым) входа х в выход у в соответствии с некоторой системой уравнений алгебры логики v вычисляет ДНФ. При другом способе включения схема АД выполняет преобразование входа у в выход х, обратное прямому, т.е. решает задачу, обратную вычислению ДНФ.

Отмечается аналогия между схемой АД и обычным преобразователем, реализующим некоторую ДНФ. При замене в схеме АД элементов AnAND, AnOR, AnNOT элементами AND, OR, NOT и исключении некоторых дополнительных элементов она превращается в указанный преобразователь. Отличие заключается в том, что преобразователь вычисляет ДНФ, а схема АД вычисляет как ДНФ, так и обратную ДНФ.

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

2. Аналоговые логические элементы

Описываемые ниже электрические цепи содержат источники напряжения, резисторы, диоды и трансформаторы постоянного тока. Все эти элементы рассмотрены Деннисом [1] в аналогичном контексте и мы будем пользоваться его формулировками при описании характеристик этих элементов.

Перечисленные элементы используются далее в определенных комбинациях, которые мы будем называть аналоговыми логическими элементами AND, OR, NOT или, сокращенно, элементами AnAND, AnOR, AnNOT. Используемые в них диоды удовлетворяют условиям

         ,       (1)

    ,       (2)

         ,       (3)

где

 - токи, протекающие через диоды,

 - напряжения на диодах.

Схема AnAND изображена на фиг. 2.1, где, y v потенциалы. В этой схеме

    ,      (4)

    .      (5)

Схема AnOR изображена на фиг. 2.2. где , v v потенциалы. В этой схеме

          (6)

           (7)

Схемы AnAND и AnOR очевидны. Новой является схема AnNOT. Она изображена на фиг. 2.3, где

  - потенциалы,

  u - э.д.с. источника постоянного тока,

  - токи.

Для этой схемы справедливы следующие соотношения:

    ,       (8)

    .       (9)

Рассмотрим реализацию элемента AnNOT. Но перед этим опишем так называемые трансформаторы постоянного тока [1], которые мы далее будем называть трансформаторами Денниса v ТД. На фиг. 2.4 ТД изображен условно. Он содержит две ветви v первичную с током  и напряжением  и вторичную с током  и напряжением. ТД описываются уравнениями

         (10)

         (11)

где h v коэффициент трансформации. Из этих уравнений следует, что

          (12)

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

Схема AnNOT на ТД с единичным коэффициентом трансформации представлена на фиг. 2.5. Можно предложить и другие схемы AnNOT на интеграторах [4, 5].

3. Электрическая цепь с ТД

Рассмотрим электрическую цепь, которая содержит ТД с единичным коэффициентом трансформации, диоды, резисторы и источники напряжения. Деннис [1] показал, что в такой электрической цепи минимизируется функция

 .      (1)

при ограничениях

 ,          (2)

         (3)

          (4)

где

I - вектор токов в ветвях цепи;

 - вектор токов в первичных ветвях ТД (часть вектора I);

- вектор токов во вторичных ветвях ТД (часть вектора I);

- вектор токов в диодах (часть вектора I);

E - вектор напряжений в ветвях цепи;

N - матрица инциденций с элементами 1,0,-1;

R - диагональная матрица сопротивлений в ветвях цепи.

В этой системе уравнение (2) описывает первый закон Кирхгофа, уравнение (3) идентично уравнению (2.10), а уравнение (4) идентично уравнению (2.4). Функция (1) имеет глобальный минимум. Необходимые условия минимума этой функции имеют вид уравнений

 ,       (5)

         (6)

          (7)

.         (8)

где

- вектор узловых потенциалов;

- вектор напряжений на первичных ветвях ТД;

- вектор напряжений на вторичных ветвях ТД;

- вектор напряжений на диодах.

В этой системе уравнение (5) описывает второй закон Кирхгофа, уравнение (6) идентично уравнению (2.11), а уравнения (7) и (8) идентичны уравнениям (2.1) и (2.3) соответственно. Новые переменные являются неопределенными множителями Лагранжа для условий (2), (3), (4). Итак, расчет рассматриваемой электрической цепи эквивалентен поиску минимума функции (1) при ограничении (2-4). Другими словами эта электрическая цепь моделирует задачу квадратичного программирования. У этой задачи имеются единственное решение.

4. Электрическая цепь с аналоговыми логическими элементами - схема АД

Рассмотрим теперь электрическую цепь, построенную из элементов ТД с единичным коэффициентом трансформации, AnAND, AnOR, AnNOT, резисторов и источников напряжения. Имея в виду, что элементы AnAND, AnOR, AnNOT, в свою очередь, содержат ТД с единичным коэффициентом трансформации, диоды, резисторы и источники напряжения, замечаем, что эта электрическая цепь содержит только ТД с единичным коэффициентом. Таким образом, эта цепь является частным случаем рассмотренной выше. В дальнейшем дальнейшем будет именовать схемой АД. Она изображена на фиг 3.1, где

 R - сопротивления,

 x, , y, z, v v точки схемы и их потенциалы.

Точки x и y составляют два множества выводов схемы АД. Между точками z и v в схеме АД включена матрица трансформаторов ТД, изображенная на фиг 3.2. Из и этой схемы следует, что

   ,       (1)

   ,       (2)

где  - векторы токов.

В схеме АД каждый элемент AnAND-m соединен своими входами с одним из выходов некоторого подмножества элементов AnNOT-k, а каждый элемент AnOR-j соединен своими входами с выходами некоторого подмножества элементов AnAND-m. Обозначим:

 - матрица связей элементов AnAND-m и AnNOT-k,

 - матрица связей элементов AnAND-m и AnOR-j,

причем

Таким образом, матрица B имеет M строк и K столбцов и в ней каждая m-строка соответствует элементу AnAND-m, а каждый k-столбец соответствует элементу AnNOT-k. Матрица G имеет M строк и J столбцов и в ней каждая m-строка соответствует элементу AnAND-m, а каждый j-столбец соответствует элементу AnOR-j. В матрице трансформаторов ТД на фиг. 3.2 TD-mj присутствует, если, и отсутствует, если.

Выводы х и у могут использоваться либо как входы, либо как выходы схемы АД. Другими словами, либо к этим выводам может быть подключен источник напряжения и тогда через них проходит ток, либо выводы Lвисят в воздухе¦ и тогда ток через них не проходит.

Из вышеизложенного следует, что в схеме АД минимизируется функция

   (3)

при ограничениях (3.2), (3.4), (2).

В частности, если выводы х являются входами, а выводы у v выходами, то минимизируется функция

      (4)

Если же выводы у являются входами, а выводы х v выходами, то минимизируется функция

     (5)

Решение будем называть булевским, если все потенциалы  принимают одно из двух значений - 0 или u. Эти значения будем называть бинарными. Очевидно, без потери общности можно принять u = 1. Потенциалы с бинарными значениями при u = 1 будем также называть булевскими потенциалами.

5. Прямое включение.

Обозначим входы элементов AnAND-m как . При этом:

     (1)

Пусть все элементы AnAND-m соединены со всеми элементами AnNOT-k, т.е.

 .        (2)

При этом

        (3)

Тогда из (2.5) следует, что

 .         (4)

Из (2.7) следует, что

 .         (5)

При прямом включении схемы АД выводы х являются входами, а выводы у являются выходами схемы АД. Это означает, что выводы у нагружены на очень большое сопротивление и, практически,

.         (6)

Все входные потенциалы х принимают булевские значения. Пусть, кроме того, выполняется условие (2) и существует такая S-строка в матрице В, что

 .         (7)

Это означает, что булевский вектор х совпадает с S-строкой матрицы В v см. (3).

Покажем, что в этом случае все потенциалы у также принимают булевские значения.

Из (4) следует, что

         (8)

Из (5) и (7) следует, что

T, если точка  (с потенциалом) присоединена к одному из входов элемента AnOR-j,

T , если точка  (с потенциалом) не присоединена ни к одному из входов элемента AnOR-j.

Таким образом, все потенциалы v принимают булевские значения. Из (6) следует, что и все потенциалы у также принимают булевские значения, что и требовалось показать.

6. Обратное включение.

При обратном включении схемы АД выводы у являются входами, а выводы х являются выходами схемы АД. Все входные потенциалы у принимают булевские значения. Пусть, кроме того, существует такая S-строка в матрице G, что

 .          (1)

Это означает, что булевский вектор у совпадает с S-строкой матрицы G. Пусть еще

          (2)

и, следовательно,

          (3)

Существование и количество решений уравнения (4.1) относительно z определяется рангом расширенной матрицы. Но, по условию, булевский вектор у совпадает с S-строкой матрицы G, т.е. совпадает с одним из столбцов матрицы. Следовательно, ранг матрицы  равен рангу матрицы. Таким образом, существование и количество решений уравнения (4.1) определяется рангом матрицы G. Точнее,

T если ранг матрицы G равен M (числу неизвестных), то (4.1) имеет единственное решение;

T если ранг матрицы G меньше M, то (4.1) имеет несколько решений;

T ранг матрицы G не может быть больше M, т.к. матрица  имеет ровно столбцов.

Таким образом, решение уравнения (4.1) будет единственным, если ранг матрицы  равен M или ранг G матрицы равен M. Это верно, если выполняется следующее условие, которое в дальнейшем для краткости будем называть как

Первое ранговое условие:

T в матрице  все M столбцов линейно независимы,

T в матрице  есть не менее M линейно независимых строк.

Если выполняется первое ранговое условие, решение уравнения (4.1) единственно, выполняется условие (1) и для строки S не существует линейно зависимых строк, то это решение имеет вид

         (4)

Отсюда и из (5.4) следует, что

 ,

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

Второе ранговое условие:

T в матрице  все M столбцов линейно независимы,

T в матрице  все строки линейно независимы.

7. Таблица истинности для схемы АД

Из вышесказанного следует, что достаточное условие существования булевского решения для обратного включения заключается в следующем:

1. матрица G удовлетворяет ранговому условию;

2. вектор у совпадает с одной из строк матрицы G;

3. все элементы AnAND соединены со всеми элементами AnNOT (математически это означает, что матрица B является бинарной);

4. любое  в матрице В должно принимать оба значения v 0 и 1 (в любом столбце матрицы В должен присутствовать и 0, и 1).

Схему АД будем описываеть таблицей, которая имеет вид, где матрицы B и G удовлетворяют вышеперечисленным условиям.

Будем называть схему АД булевской, если она удовлетворяет условиям 1) и 3), а вектор у, совпадающий с одной из строк матрицы G, будем называть правильным вектором. Булевская схема АД, на которую подан правильный вектор y, имеет булевское решение.

Булевская схема АД описывается таблицей истинности, которая имеет вид. При булевском решении

или

   .

Последнее выражение есть дизъюнктивная нормальная форма - ДНФ. Таким образом, схема АД, удовлетворяющая указанным условиям, удовлетворяет, кроме того, системе уравнений

   ,      

где каждое уравнение является ДНФ. Если задается вектор х, то вычисляется вектор у, т.е. функция, соответствующая системе ДНФ. Если же вектор у задается, а вектор х вычисляется, то схема АД вычисляет функцию, обратную системе ДНФ v обратную ДНФ.

Отметим явную аналогию между схемой АД и преобразователем, реализующим ДНФ. При замене в схеме АД элементов AnAND, AnOR, AnNOT элементами AND, OR, NOT и исключении ТД онапревращается в указанный преобразователь. Отличие заключается в том, что преобразователь вычисляет ДНФ, а схема АД вычисляет как ДНФ, так и обратную ДНФ.

8. Пример.

Некоторая булевская схема АД приведена на фиг 8.1 и фиг.8.2. Она описывается таблицей истинности табл. 1. Эта таблица удовлетворяет условиям 1), 2), 3).

Таблица 1.

9. Заключение

Предлагаемые схемы могут использоваться как обратимые преобразователи кодов [6, 7]. Другое применение - аппаратная реализация функций, для которых отсутствуют регулярные схемы алгебры логики, но существуют достаточно простые схемы вычисления функций, обратных данным. Например, существует комбинационная схема умножения, но отсутствует комбинационная схема деления. Умножитель, реализованный предложенным способом, может выполнять и умножение, и деление [8].

Показано, что электрические схемы с ТД эквивалентны электрическим схемам с интеграторами [9]. Поэтому описанные схемы могут быть также реализованы на интеграторах [3, 4, 5, 10].

Очевидна аналогия между ТД и обычными трансформаторами в цепях синусоидального тока. Можно предложить также некоторый иммитатор диода в цепях синусоидального тока. При этом описанные схемы постоянного тока могут быть реализованы как схемы синусоидального тока [11].

Разработана демонстрационная программа, моделирующая обратимое устройство для возведения в квадрат и извлечения квадратного корня. Она высылается по запросу бесплатно. Обращайтесь по адресу [email protected]

Список литературы

1. Деннис Дж. Б. Математическое программирование и электрические цепи. М.: ИЛ, 1961, 430 с.

2. Хмельник С.И., Жилейкина В.Н. Система преобразования напряжения. Авт. св. 1457117, БИ-5, 1989, Москва. (Трансформатор Денниса на оптронах)

3. Хмельник С.И., Жилейкина В.Н. Устройство для имитации трансформатора. Авт. св. 1601616, БИ-39, 1990, Москва. (Трансформатор Денниса на сумматорах и интеграторах)

4. Хмельник С.И. Преобразователь напряжения. Авт. св. 1448350, БИ-48, 1988, Москва. (AnNOT на интеграторах)

5. Хмельник С.И., Жилейкина В.Н. Преобразователь напряжения. Авт. св. 1591046, БИ-33, 1990, Москва. (AnNOT на сумматорах и интеграторах)

6. Хмельник С.И. Преобразователь кодов. Авт. св. 1524182, БИ-43, 1989, Москва (Обратимый преобразователь на оптронах)

7. Хмельник С.И. Табличный преобразователь кодов. Авт. св. 1649669, БИ-18, 1991, Москва. (Обратимый преобразователь на оптронах)

8. Хмельник С.И. Вычислительное устройство. Авт. св. 1559339, БИ-15, 1990, Москва (Умножитель v делитель)

9. Хмельник С.И. Квадратичное программирование и дифференциальные уравнения, сборник научных трудов ?Вопросы разработки АСУ в энергетике¦, ?Энергосетьпроект¦, Mосква, 1985, c. 128-141. (Аналогия между трансформаторами Денниса и интеграторами)

10. Хмельник С.И. Дешифратор. Авт. св. 1229965, БИ-17, 1986, Москва. (Дешифратор на сумматорах и интеграторах)

11. Хмельник С.И. Дешифратор для исправления ошибок. Авт. св. 1305873, БИ-15, 1987, Москва. (Дешифратор на схемах синусоидального тока)