О синтезе контактных схем

Вн ииВ1л Й и иклзалзли гиии кандидат физико-ипливмаиликгских наук С. В. ЯБЛОНСКИЙ Одной из задач кибернетики является задача построения сложных схем, реализующих заданные функции, из сравните.льно простых элементов. Это может быть, например, синтез электронных схем из стандартных блоков, синтез релейно-контактных схем из стандартных реле и т, д, При этом обычно стремязся строить в том илн ином смысле наилучшие схемы. Во многих случаях имеется тривиальный способ нахождения такой экстремальной схемы, однако он мало эффективен в том смысле, что связан с очень большим перебором и, кроме того, не дает никакого представления о сложности получаемой схемы. Поэтому встает вопрос об отыскании более эффективных методов построения достаточно хороших схем с оценками их сложности.

Первые значительные результаты в этом направлении были получены К. Э. 1Пеннопом Ц. Оказывается, что получающиеся здесь результаты мало зависят от природы средств, из которых построены схемы. Кроме того, трудности, которые возникают при решении подобных задач, также сходны. Это позволяет производить исследования некоторого (одного) модельного объекта и затем сравнительно просто распространять результаты на случай схем из других элементов. В качестве такого модельного объекта обычно берутся контактные схемы (точнее, математический объект, являющийся абстракцией «реальных» контактных схем; определение см., например, [а з)). Это обстоятельство объясняется тем, что контактные схемы раньше других были описаны математически дискретным образом (' з '). Для характеристики множества контактных схем для всех функций алгебры логики п аргументов К.

Э. Шепноном была введена ('] функция 1. (п) — минимальное число контактов, достаточное для реализации любой функции п аргументов. Им же было показано, что для любого в>0 и п>п(е) причем доля функций, требующих для своей реализации не бо2п лее (1 — е) — контактов, стремится к 0 с ростом и. Каждый конкретный метод синтеза естественно характеризовать аналогичной функцией — минимальным числом контактов, достаточным для получения любой функции и аргументов этим методом. Для получения верхней оценки К. Э.

Шеннон пользовался разработанным им методом универсальных многополюсников. Впоследствии Г. Н. Поваров предложил другой метод синтеза — метод каскадов [''), являющийся улучшением метода Шеннона. Правда, метод каскадов не позволяет понизить верхнюю оценку в формуле (1). В 1956 г, автором был получен еще один метод синтеза, позволивший в два раза понизить верхнюю оценку в (1) ['). В диссертации описывается метод синтеза контактных схем с верхней оценкой, в 4 раза меньшей, чем в (1).

Тем самым полностью решен вопрос об асимптотическом поведении упомянутой функции Шеннона, именно показано, что зл Е (и) — —— Этот метод основан на использовании двух обстоятельств. Первым из них является некоторое специальное представление произвольной функции алгебры;югики в виде композици ~ функций более простой природы (оно использовалось ранее автором для получения асимптозических оценок в случае вентильных и контактно-вентильных схем [")) . Вторым обстоятельством является применение контактного многополюсппка, реализующего ~все конъюнкции и переменных и их отрицаний и содержащего асимптотически в два раза меньше контактов, чем контактное дерево [~ '1.

Здесь существенную роль играют некоторые факты из теории самокорректирующихся кодов ["). Следствием последнего результата и замечания по поводу нижней оценки в (1) является следующее утверждение; почти все функции и аргументов почти так же плохи, как самая плохая функция (в смысле контактной реализации). В диссертации получены также асимптотические формулы для минимальной нагрузки реле, достаточной для того, чтобы реализовать контактной схемой: а) произвольную функцию алгебры логики и аргументов; б) все конъюнкции и аргументов и их отрицаний.

Более подробное изложение результатов диссертации содержится в ["1. ЛИТЕРАТУРА 1. С. Е. 5 Ь а п п о п. ТЬе зупрйез!з о1 1тчо-1егпт(па) ючйсЬ!лй с!гспВз. Вей Буз1. Тесйп. Я., 28, йй 1 (1949), 59 — 98. 2. М. А. Г а ар илов. Теория релейно-контактных схем, изд. АН СССР, ! 950. 3, С. В. Я бл о н с к и й.

Функциональные построения в к.значной логике. Труды Матем. ин-та им. В. А. Стеклова, П (1957), 5 — 142. 4. В. И, Ш е с та ко в. Алгебра двухполюсных схем, построенных нсклю. чнтельно из двухполюсников. ЖТФ, 11, 73 6 (!941), 532. 5 С. Е. 5 Ь а и и о и. А зуптЬо11с апа1уяз о1 ге!ау апс1 зчг!(сЫпй с!гсгй1.

Тгапз. а1 Агпег. 1пз1. Е1ес1г. Епк. 57 (1938), 713 — 722. 6 А. Ж а 1г а з)ш а. Цикл статей в журнале ЬВрроп Е!ес!г. Сопнпцп(с. Епй., 1936 — 1937. 7. Г. Н. П о в а р о в. Математическая теория синтсза контактных (1, к) — полюсннков. ДАН 100, )чз 5 (1955), 909 — 912. 8 Г. Н. П о в а р о в. Метод синтеза вычислительных и управляющих схем. Автоматика и телемеханика, 18, Ьгг 2 (1957), 145 — 162. 9. О.

Б. Л у и а н о в. Об одном методе синтеза схем. Известия высших учебных заведений. Радиофизика, 1958, )че 1, !20 — 140. !О. О. Б. Л у п а н о в О вентнльных н контактно-вентнльных схемах ДАН, 111, йй 6, (1956), !171 †11. 11, Р В. Х з м м и н г. В сб. Коды с обнаружением и исправлением ошибок. ИЛ. !956, 7 — 22. !2. О. Б. Л у п а н о в. О синтезе контактных схем, ДАН, 1!9, 73 1 (1958) 23 — 26.

.