Електричні
ланцюга з бінарними потенціалами
К.т.н. Хмільник
С.І.
Розглядаються
електричні ланцюги 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,
причому
1, якщо
вихід з'єднаний з AnAND-m,
0, якщо
вихід з'єднаний з AnAND-m,
-1,
якщо AnNOT-k вихід не з'єднаний з AnAND-m,
1, якщо
AnAND-m з'єднаний з AnOR-j,
0, якщо
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.
X1
X2
X3
Y1
Y2
Y3
0
0
1
1
1
1
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
1
0
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, Москва.
(Дешифратор на схемах синусоїдальної струму)
