К.т.н. Хмільник С.І.
Розглядаються електричні ланцюги 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, де, yv потенціали. У цій схемі
, (4)
. (5)
Схема AnOR зображена на фіг. 2.2. де, vv потенціали. У цій схемі
(6)
(7)
Схеми AnAND і AnOR очевидні. Новою є схема AnNOT. Вона зображена на фіг. 2.3, де
- Потенціали,
u - е.р.с. джерела постійного струму,
- Струми.
Для цієї схеми справедливі наступні співвідношення:
, (8)
. (9)
Розглянемо реалізацію елемента AnNOT. Але перед цим опишемо так звані трансформатори постійного струму [1], які ми далі будемо називати трансформаторами Денніса v ТД. На фіг. 2.4 ТД зображений умовно. Він містить дві гілки v первинну зі струмом і напругою і вторинну зі струмом і напругою. ТД описуються рівняннями
(10)
(11)
де hv коефіцієнт трансформації. З цих рівнянь випливає, що
(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, vv точки схеми та їх потенціали.
Точки 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 | |||||