Настраиваемые логические устройства и их применение

Шалыто А. А.

1. Настраиваемые логические устройства

В конце 60-х – начале 70-х годов прошлого века в связи с развитием микроэлектроники в мире, и в СССР, в частности, пришли к пониманию того, что программирование функций должно выполняться не только на уровне вычислительных машин, но и на уровне элементной базы.

Элементы, которые путём настройки могли реализовать определённый набор булевых функций, были назваными настраиваемыми логическими устройствами (модулями, элементами). Такие устройства можно разделить на четыре класса: многофункциональные; универсальные в классах булевых функций; универсальные в классе всех булевых функций; однородные структуры.

2. Многофункциональные логические модули из функциональных элементов (элементов с односторонней проводимостью) 

2.1. Первый в мире многофункциональный логический модуль 

Первым в мире специально созданным многофункциональным логическим модулем был разработанный в СССР в 1969 г. элемент на базе МДП-транзисторов, который входил в состав серии микросхем К108 под шифром К1ЖЛ081 [1, 2] (шифр «ЖЛ» – элемент многофункциональный).

Он появился следующим образом. В результате анализа функциональных схем, применяемых в системах управления корабельными техническими средствами, в ЦНИИ «Аврора» (Ленинград) было установлено, что в этих системах наиболее часто применяются 22 схемы с восемью входами. После общения со специалистами электронной промышленности стало ясно, что изготовить столь широкую номенклатуру логических элементов малой серийности неэффективно, и было предложено заменить все эти схемы одной.

Так как указанные работы проводились совместно с сотрудниками Института проблем управления (ИПУ) АН СССР, то ими (Ивери Варламовичем Прангишвили и Марленом Александровичем Ускачем) было предложено реализовать эту схему на новом для того времени принципе – принципе многофункциональности, при использовании которого строится избыточная (по элементам и входам) схема, из которой заданные схемы получаются за счёт настройки – присвоения входам значений констант 0 и 1, отождествления входов, а также выбором выхода.

Используя эвристические методы, авторам работы [3] удалось построить порождающую функцию модуля (функцию, описывающую его структуру), которая была реализована схемой, содержащей 79 МДП-транзисторов [4].

Создание этого элемента поставило ряд принципиально новых научных задач, решение которых позволило сформировать новое научное направление в области логического проектирования. К ним относятся:

• оценка логической эффективности модулей;
• разработка методов построения многофункциональных логических модулей;
• разработка методов синтеза схем из многофункциональных логических модулей.

2.2. Оценка логической эффективности многофункциональных модулей

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

Этот недостаток был устранён в работе [7]. Введённый показатель (коэффициент логической эффективности – Км) определяется как сумма от 1 до m (m – число входов модуля) отношений, каждое из которых представляет дробь. В ней числитель – число функций от i переменных в некотором классе функций, которые реализуются модулем путём настройки, а знаменатель – теоретическое число функций от того же числа переменных в этом классе.

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

При этом авторами работы [7] было впервые предложено использовать в исследованиях по логическому синтезу не булевы функции и их классы, а булевы формулы (в определённом базисе и из определённого числа букв) и их важнейший подкласс – бесповторные формулы. Это связано с тем, что из заданной бесповторной формулы путём отождествления переменных всегда может быть получена повторная формула той же структуры. Более того, было предложено использовать не все бесповторные формулы, а только представителей их типов относительно операций перестановки переменных, замены переменных и/или формул с их инверсиями. Интересно, что бесповторных формул мало, но из них можно получать повторные формулы, в то время как повторные формулы, которых много, менее удобны для порождения других формул.

В последней работе было отмечено, что базис формул должен быть таким, чтобы каждая двуместная операция в нём подчинялась сочетательному закону. Это обеспечивает простоту декомпозиции таких формул.

В ходе исследования функциональных возможностей микросхемы К1ЖЛ081 работе [8] было установлено в, что она реализует не 22, как считали её авторы, а 26 из возможных 522 типов бесповторных формул в базисе И, ИЛИ, НЕ из восьми букв (26/522). Для семи букв этот показатель – 50/180, для шести букв – 58/66, для пяти букв – 24/24, поэтому для четырёх букв – 10/10, для трёх букв – 4/4, для двух букв – 2/2 и для одной буквы – 1/1. При этом      Км = 6,21.

Анализ этих соотношений позволил установить принципиально новое свойство этого модуля, которое не было известно его авторам, которое состоит в том, что модуль является не просто многофункциональным, а и универсальным в классе произвольных формул в указанном базисе из пяти и менее букв (Ку = 5). Это позволило предложить принципиально новый метод синтеза схем на таких модулях, резко уменьшающий объём перебора.

Применительно к классу бесскобочных формул (дизъюнктивных нормальных форм) в работе [8] было установлено, что рассматриваемый модуль универсален при шести и менее буквах.

В ходе этих работ сложилось понимание [9, 10] того, что кроме повторителя и инвертора, не существует однофункциональных логических элементов, а все элементы, начиная с двухвходового элемента И-НЕ (реализует две функции – порождающую и инверсию), являются многофункциональными и отличаются только коэффициентом логической эффективности.

Это позволило в качестве многофункциональных логических элементов рассматривать произвольные логические элементы и серии таких элементов [11], а не только специально спроектированные элементы, как это считалось до появления работы [10]. 

2.3. Методы построения многофункциональных логических модулей

 В ходе решения второй задачи (разработка методов построения многофункциональных логических модулей) были предложены методы построения таких, которые содержат меньшее число внешних выводов по сравнению с модулями, построенными классическим методом, базирующемся на объединении заданных формул в порождающую функцию модуля на основе разложения Шеннона [12].

Первый из этих методов, основанный на объединении в порождающую функцию не заданных формул, а их разнотипных «половинок», описан в работе [10]. Ряд других весьма эффективных методов, разработанных автором совместно с В.Л. Артюховым, изложен в работе [13]. Некоторые из этих методов в работе [13] удалось обобщить с помощью мультиплексорного метода построения модулей [14]. На основе этих методов разработано большое число многофункциональных логических модулей, которые защищены 26 авторскими свидетельствами СССР. Среди этих модулей, описанных в работе [13], отметим модули, универсальные в классе формул в рассматриваемом базисе из трёх [15], четырёх [16], пяти [17] и шести [18] букв. При этом последний из них состоит из двух модулей [15, 16], и, видимо, является наиболее эффективной логической микросхемой с параллельным вводом информации, которая может быть размещена в корпусе с 14 внешними выводами.

 2.4. Методы синтеза схем из многофункциональных логических модулей

Решению третьей задачи (разработке методов синтеза схем из многофункциональных логических модулей) был посвящён ряд работ [19, 20]. Недостаток этих методов (отсутствие оценок сложности предстоящих реализаций) был устранён при разработке формульного метода синтеза комбинационных схем [21–23], при использовании которого число многофункциональных модулей в схеме линейно зависит от числа букв в реализуемой формуле.

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

Лишь почти через 30 лет после начала работ по этой тематике в работе [13] удалось разработать мультиплексорный метод синтеза [24], основанный на решении логических уравнений, при применении которого удается определять число решений, существующих каждом шаге. Применение этого метода позволяет более полно использовать функциональные возможности модулей по сравнению с формульным методом, что в ряде случаев приводит к уменьшению числа модулей в схемах, построенных на них.

Этот метод может рассматриваться как метод реализации произвольных булевых функций на произвольных логических элементах, который, несмотря на многолетние усилия многих учёных, не был до этого сознан. Сравнение предложенного метода с известными, выполненное в работе [13], показало, что этот универсальный метод в большинстве случаев позволяет получать решения, которые по числу элементов не уступают даже специализированным методам.

В это же время было предложен новый метод разложения булевых функций, отличающийся от известных тем, что разложение проводится не по крайним левым входным переменным таблиц истинности, как это делается обычно, а по крайним правым переменным [25]. Такое разложение позволяет без перестроения таблиц истинности получать второе решение. При этом было показано, что все разложения булевой функции по крайней правой входной переменной либо совпадает с разложениями Шеннона и Рида, либо PN-однотипны (P – permutation, N – negation) с ними, и других разложений на две остаточные функции не существует.

Работа автора настоящего обзора, посвящённая исследованиям по указанной тематике («Декомпозиция и логический синтез булевых функций в базисе произвольных логических элементов»), была признана одним из победителей конкурса исследовательских проектов в области автоматизации проектирования интегральных схем, который проводился в 2003 г. в странах СНГ корпорацией «Intel» [26].

Изложенные подходы не только применялись на практике в момент их создания, но использовались также и на новом витке развития элементной базы [27, 28].

3. Многофункциональные логические модули на других типах элементной базы

3.1. Применение элементов пневмоавтоматики 

В первой половине 1960-х годов во многих отраслях техники, в том числе и в судостроении, резко возрос интерес к пневматике как весьма надёжному и дешёвому средству автоматизации. Этому способствовали разработка и серийных выпуск мембранных пневмоэлементов универсальной системы элементов промышленной пневмоавтоматики (УСЭППА).

В.Е. Вольский (ЦНИИ «Аврора», Ленинград) в 1968 г. завершил исследование вопросов построения алгоритмов релейного управления судовыми энергетическими установками и их реализации на стандартной пневмоаппаратуре, которые в дальнейшем были обобщены в работе [29]. Им был и исследованы функциональные возможности отдельных элементов, входящих в систему УСЭППА, и показано, что некоторые из них являются многофункциональными логическими элементами, которые в зависимости от способов их включения могут выполнять различные логические функции.

При этом в работе [30] было показано, что универсальное трёхмембранное реле типа  Р-3Ф, содержащее фиксирующую пружину, является модулем, универсальным в классе формул в базисе И, ИЛИ, НЕ из трёх и менее букв, причём формула, описывающая его поведение, является наиболее простой из формул для аналогичных модулей, реализованных на другой элементной базе.

3.2. Модули из элементов с двусторонней проводимостью

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

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

В ходе работ по этой тематике были созданы модули из элементов с двусторонней проводимостью [32, 33], которые в предположении о равной доступности прямых и инверсных выходах источников информации универсальны в классе булевых формул в базисе И, ИЛИ, НЕ из q букв. Эти модули до определенного значения числа букв не обладают элементной избыточностью. При значениях q, меньших или равных шести, многофункциональность таких модулей обеспечивается только за счёт дополнительных выходов без элементной избыточности. При больших значениях q, как и в модулях из элементов с односторонней проводимостью, имеются оба вида избыточности.

Предложенные модули существенно более просты по сравнению с модулями из элементов с односторонней проводимостью с теми же значениями q. Так, например, при           q=5 модуль, описанный в работе [3], имеет 14 внешних выводов (два предназначены для подачи питания) и состоит, как отмечалось в разд. 2.1, из 79 МДП-транзисторов, объединённых в функциональные элементы, в то время как предлагаемый модуль из элементов с двусторонней проводимостью при этом значении q имеет 12 внешних выводов и содержит лишь пять элементов.

При q = 7 модуль из семи элементов реализует путём настройки 179 из 180 параллельно-последовательных контактных схем. С ростом величины q доля параллельно-последовательных контактных схем, реализуемых предлагаемым модулем из q элементов, уменьшается. Так, например, при q = 8 модуль из восьми элементов путём настройки реализует 518 из возможных 522 схем.

Свойство двусторонней проводимости позволило предложить метод синтеза схем из рассматриваемых модулей, при котором имеет место существенно меньшая избыточность, чем при использовании модулей из элементов с односторонней проводимостью. Этот метод, базирующийся на свойстве эйлеровых графов, которые могут быть «пройдены» не отрывая руки от бумаги [34], был назван топологическим. Такие графы называются «уникурсальными».

Граф является эйлеровым, если он содержит ноль или две вершины нечётной степени [35]. Вершина называется нечётной, если она образована нечётным числом ребер. Из теории графов известно, что при отсутствии нечётных вершин граф «проходим» при его обходе, начиная из любой чётной вершины, а при двух нечётных вершинах его обход должен начинаться из одной из этих вершин. В произвольном графе число нечётных вершин чётно и при наличии более двух таких вершин он «непроходим». Для обеспечения возможности его прохода должна быть введена избыточность в виде «мостов».

Эти результаты теории графов были использованы при реализации произвольных (в том числе, многополюсных) схем, построенных из нормально разомкнутых контактов. Если реализуемая схема является эйлеровой, то в ней может быть найден эйлеров маршрут (эйлерова линия), который определяет настройку модуля – обозначения контактов в «цепочке» [32] и перемычки между её внешними выводами. Так как в «цепочке» обеспечен доступ к любой «точке», то произвольная эйлерова схема из q контактов может быть безызбыточно реализована такой «цепочкой» из q контактов.

В рассмотренных модулях должны быть доступны прямые и инверсные выходы источников информации. Если доступны только прямые выходы, то в качестве                      q-универсального модуля при q = 2 и 3 может быть использована схема из q переключательных контактов, предложенная в работе [36].

Подход на основе эйлеровых графов, предложенный для эффективного использования рассмотренных модулей, был применён также и для исследования функциональных возможностей цепочек из одинаковых резисторов [37]. При этом, например, было показано, что цепочка из пяти одинаковых резисторов, каждый из которых имеет сопротивление R, может реализовать путём наложения перемычек 35 различных номиналов сопротивлений, лежащих в диапазоне от R/5 до 5R.

4. Модули, универсальные в классах булевых функций 

Выше были рассмотрены модули, универсальные в классе формул.

Существуют также модули, универсальные в определённых классах булевых функций. Так, в частности, модуль из работы [15] универсален, не только в указанном классе формул из трёх букв, но и в классе пороговых функций трёх переменных, так как он за счёт настройки реализует не только представителей всех типов бесповторных формул в базисе И, ИЛИ, НЕ из трёх букв, но и функцию «голосование два и более из трёх».

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

4.1. Модули, универсальные в классе симметрических функций 

Стандартная схема для реализации симметрических функций в базисе релейно-контактных элементов, названная симметрическим многополюсником, была предложена в работе [38].

Стандартная схема из функциональных элементов, построенная на основе принципа локального кодирования [39], которая предназначена для реализации путём настройки произвольных симметрических функций n переменных, предложена в работе [40].

Методы эффективного использования модулей рассматриваемого класса предложены в работе [13].

4.2. Модули, универсальные в классе самодвойственных функций и в «близких» к ним классах

Для классификации пороговых функций была предложена SD-классификация (от английского словосочетания self-dual) [41]. Эта классификация была использована также и для произвольных булевых функций. При её применении определяются типы самодвойственных функций n + 1 переменных, которые порождают заданные функции n переменных.

В работе [42] был предложен модуль, реализующий путём настройки всех представителей самодвойственных функций четырёх переменных, которые, в свою очередь, порождают всех представителей PN-типов функций трёх переменных.

Более «крупной» для булевых функций n переменных является самодвойственная классификация [43], которая в отличие от SD-классификации, является групповой [44]. При применении этой классификации определяют типы функций n переменных, при подстановке в которые самодвойственных функций удаётся порождать произвольные функции того же числа переменных.

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

Интерес представляют также модули, универсальные в классе самоантидвойственных функций, а также модули, которые путём настройки реализуют одновременно две функции – произвольную булеву функцию и её антидвойственную, что может рассматриваться также и как вычисление произвольной булевой функции одновременно на двух противоположных наборах [39].

Эти модули, а также модули, которые путём настройки одновременно реализуют булеву функцию и её двойственную, предложены в работе [45].

5. Модули, универсальные в классе всех булевых функций 

Модули этого типа с минимальным числом входов строятся путём перебора без разделения информационных и управляющих входов в предположении о равной доступности прямых и инверсных выходов источников информации [46–49].

Наибольшее распространение на практике получили модули этого типа, в которых информационные и управляющие входы разделены. В работах [50, 51] описаны универсальные логические модули n переменных без парафазных входных переменных, настройка которых осуществляется за счет подачи на управляющие входы констант 0 и 1.

В этих работах описаны также универсальные логические модули n переменных с одной парафазной входной переменной, настройка которых осуществляется за счёт подачи на управляющие входы констант 0, 1 и парафазной переменной. Это позволило сократить число входов модулей.

Дальнейшее сокращение числа входов достигается при использовании универсальных логических модулей n переменных с n парафазными входными переменными, настройка которых осуществляется за счёт подачи на управляющие входы констант 0, 1 и парафазных входных переменных [51–53].

Из изложенного следует, что в теории построения универсальных логических модулей был пробел: не рассматривались универсальные логические модули n переменных с m парафазными входами (m не превосходит n). Этот пробел был устранён в работе [54]. При этом были построены модули указанного типа и продемонстрирована их эффективность.

6. Однородные структуры

Рассмотренные выше модули могут использоваться отдельно или объединяться в схемы на основе соответствующих методов синтеза. Эти схемы обычно не являются однородными.

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

Результаты исследований в области однородных структур достаточно подробно изложены в монографиях отечественных авторов [55, 56], а результаты, полученные под руководством В.И. Варшавского, изложены в работах [57, 58]. В этой области был получен и ряд других результатов, которые описываются ниже.

6.1. Реализация булевых формул в базисе И, ИЛИ, НЕ каскадами Макхопадхая и пороговыми элементами 

Одномерная однонаправленная структура из элементов И и ИЛИ называется каскадом Макхопадхая [59].

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

В этой работе, а также в работе [10], также были рассмотрены обобщённые каскады Макхопадхая, являющиеся древовидными схемами из каскадов Макхопадхая. При этом было показано, что такой обобщённый каскад с h входами содержит не более [h/2] каскадов Макхопадхая.

Так как произвольная булева формула в базисе И, ИЛИ, НЕ из h букв при равной доступности прямых и инверсных входных переменных реализуется обобщённым каскадом с h входами, то тем самым доказано, что формулы этого класса реализуются схемами из пороговых элементов, число которых не превосходит [h/2].

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

Простейшим настраиваемым однородным каскадом Макхопадхая является каскад из трёхвходовых мажоритарных элементов [10]. Эти каскады из n – 1 элементов при равной доступности прямых и инверсных входных переменных реализуют бесповторные пороговые функции n переменных [62, 63].

6.2. Реализация булевых функций каскадами Майтра

Одномерная однонаправленная структура из двухвходовых элементов И, ИЛИ, НЕРАВНОЗНАЧНОСТЬ называется каскадом Майтра [64].

Функциональные возможности таких каскадов исследованы в работе [60].

Известны также настраиваемые однородные каскады Майтра, каждая ячейка которых может быть настроена на реализацию функций, указанных выше элементов [10]. Существенно более простым каскадом этого типа является однородный каскад из мультиплексоров «2 в 1», в котором выход предыдущего элемента соединяется с управляющим входом последующего элемента.

Отметим, что каскады этого типа имеют принципиально другую структуру по сравнению со вторым типом однородных каскадов, которые также построены из мультиплексоров «2 в 1», но не являются каскадами Майтра [62].

Модификация структуры каскадов приводит к изменению их функциональных возможностей. При этом каскад второго типа из (h – 1)-го мультиплексора «2 в 1» позволяет реализовать произвольные булевы формулы в рассматриваемом базисе из h букв [62].

Этот метод основан на замене мультиплесором каждой условной вершины в линейном бинарном графе, читаемом в обратном порядке. Метод построения таких графов и их свойства описаны в работах [65–67]. При таком построении каскада на выходах мультиплексоров реализуются не подформулы, как это происходит традиционно, а её фрагменты, несмотря на наличие в реализуемой формуле скобок произвольной глубины.

В работе [13] предложен метод построения каскадов Майтра, число элементов в которых равно n – 1, для реализации определённого в этой работе класса булевых функций n переменных. При этом, в частности, используются преобразования Артюхова–Шалыто [62], которые модифицирует разложение Шеннона по одной переменной, позволяя инвертировать верхнюю или нижнюю половину столбца значений булевой функции.

6.3. Реализация булевых формул многоканальными однородными структурами 

Известны двухканальные однородные структуры из комбинационных элементов [68], называемые каскадами Шорта [57, 58].

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

В этой структуре и её модификациях [57, 58] булевы формулы могут быть реализованы в дизъюнктивной нормальной форме, в виде полиномов Жегалкина, а также на основе разложений Рида.

В этих работах была предложена также трёхканальная однородная структура из комбинационных элементов, каждая ячейка которой содержит только один внешний вход, который может использоваться в одних случаях как информационный, а в других – как управляющий вход. Реализация булевых формул в этой структуре выполняется при их представлении в виде полиномов Жегалкина.

Для реализации скобочных формул ограниченной глубины в работе [57] были предложены двух- и трёхканальные однородные структуры.

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

Для устранения этого недостатка в работе [69] были предложены однородные структуры, число ячеек в которых равно h – 1, где h – число букв в реализуемой формуле, записанной в базисе, для двухместных операций которого выполняется сочетательный закон. При этом число каналов в структуре равно числу уровней каскадов в древовидной схеме максимальной глубины, построенной из двухвходовых элементов этого базиса. При использовании этих структур, в отличие от известных подходов, в однородную структуру вкладываются не «составляющие» реализуемой формулы, а элементы эквивалентной ей древовидной схемы указанного выше типа, реализующей заданную формулу.

В случае, когда доступны только прямые входные переменные, то булева формула представляется в виде полинома Жегалкина или скобочной формы, построенной из этого полинома.

При этом, в частности, в двухканальной структуре [70] удается реализовать двухуровневые каскадные схемы, которым соответствуют дизъюнктивные нормальные формы и полиномы Жегалкина, что обеспечивает универсальность этой структуры.

6.4. Реализация булевых формул плоскостными однородными структурами

Известны [55, 56] различные плоскостные однородные структуры. Однако такие структуры для реализации произвольных скобочных формул в выбранном базисе в литературе не рассматривались.

В работе [71] предложена ячейка однородной структуры, которая путём настройки может быть настроена на реализацию одной из четырёх функциональных и коммутационных конфигураций. На основе этой ячейки может быть построена однородная плоскостная структура, которая при равной доступности прямых и инверсных входных переменных может быть настроена на реализацию произвольной булевой формулы в базисе И, ИЛИ, НЕ.

За счёт незначительного усложнения ячеек, рассмотренной плоскостной структуры, может быть обеспечена совместная реализация систем булевых формул [72].

В работах [73, 74] изложены результаты, полученные на основе развития подходов, изложенных в разд. 6.

7. Клеточные автоматы

В последние годы основное внимание исследователей направлено не на аппаратные реализации однородных структур, а их программную реализацию. Реализуемые программно однородные структуры называются клеточными автоматами [75].

Исследования клеточных автоматов (в частности, «выращивание кошки» в работе [76]) проводились В.И. Варшавским в рамках исследований однородных структур [57, 58] и децентрализованного управления [77, 78].

Для исследования клеточных автоматов создаются различные инструментальные средства [79]. Одно из таких средств было создано в «Университете ИТМО» и показало свою эффективность [80].

Обзор широкого класса клеточных автоматов выполнен в работе [81], а результаты теоретических исследований функциональных возможностей простейших клеточных автоматов приведён в [82]. 

8. Переходные процессы в логических схемах

При построении асинхронных логических схем необходимо учитывать переходные процессы. Исследования по этой тематике породило новый класс схем – апериодические схемы или схемы с самосинхронизацией [83–85].

Результаты исследования переходных процессов в одноконтурных логических схемах, содержащих чётное число инверторов, приведены в работах [86, 87]. При этом был предложен метод построения устройств задержки, длительность запаздывания которых может превышать сумму запаздываний составляющих их элементов.

Этот метод относится к группе методов, которые позволяют обеспечить композиции элементов более высокие показатели качества по сравнению с ее составляющими. К таким методам, в частности, относится метод построения надёжных схем из ненадёжных элементов [38, 88].

Послесловие 

В заключение отмечу огромное влияние, которое оказал член-корреспондент АН СССР Михаил Александрович Гаврилов [89, 90], на исследования в рассматриваемой области и на автора лично. При этом, в частности, под его руководством в течение нескольких десятилетий (!) проходили школы по теории релейных устройств и конечных автоматов, которые, в свою очередь, породили другие школы, например, по однородным структурам и диагностике.

В одной обзорной статье невозможно упомянуть все работы по рассматриваемой тематике, которые были выполнены в этой области. Однако, имена многих исследователей, которые обеспечили в нашем стране Великую эпоху в теории автоматов и близких к ней областях, приведены в работах [91, 92], опубликованных на русском и английском языках. В книге [93] опубликованы статьи о роли Виктора Ильича Варшавского и Анатолия Васильевича Каляева в становлении отечественных информационных технологий. Там же приведена статья об Ивери Варламовиче Прангишвили, с которым автор был соавтором [32].

Со многими публикациями, указанными ниже, которые выполнены автором или при его участии, можно ознакомиться на сайте http://is.ifmo.ru в разделах «Статьи» и «Articles». Эти публикации легли также в основу монографии [13].

Отмечу также, что при участии автора настоящего обзора был представлен доклад [94] на «Reed-Muller 2017 Workshop», где он был членом оргкомитета (http://www.mvl.jpn.org/RM2017/committee.html). В нём рассматривался вклад советских учёных в логическое проектирование, которое во многом развивалось благодаря беспрецедентному в науке явлению – многодесятилетнему существованию указанных выше школ, проводимых под руководством Михаила Александровича.

Мою связь с Гавриловым отметил в своем отзыве на автореферат моей докторской диссертации (http://is.ifmo.ru/aboutus/shalyto_dissert_otzivi/001.pdf) академик РАН Николай Александрович Семихатов (https://ru.wikipedia.org/wiki/Семихатов,_Николай_Александрович).

Литература

1. Справочник по интегральным микросхемам /Тарабрин Б.В., Якубовский С.В., Барканов Н. А.  и др. –М.: Энергия, 1977.
2. Справочник по полупроводниковым диодам, транзисторам и интегральным схемам   /  Горюнов Н.Н., Клейман А.Ю., Комков Н.Н. и др. –М.: Энергия, 1979.
3. Прангишвили И.В., Демченко О.П., Копейкин Г.А., Ускач М.А. и др. Многофункциональный логический модуль. Авторское свидетельство (А.с.) СССР. № 269599 // Бюл. изобретений. 1970. № 15.
4. Прангишвили И.В., Ускач М.А., Копейкин Г.А. Комплекс логических МДП-интегральных схем для систем автоматики и телемеханики // Приборы и системы управления. 1970. № 4.
5. Данем Б., Норт Д. Проблемы выбора логически эффективных основных ячеек //Синтез релейных структур. –М.: Наука, 1965.
6. Бабичева Е.И., Прангишвили И.В., Ускач М.А., Шаипов Н. Некоторые критерии оценки эффективности логических модулей // Автоматика и телемеханика. 1968. № 3.
7. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Оценка логической эффективности интегральных микросхем // Автоматика и вычислительная техника. 1981. № 1.
8. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Применение многофункциональных модулей среднего уровня интеграции для построения комбинационных схем               // Теория конечных автоматов и ее приложения. Рига: Зинатне, 1975. Вып.5.
9. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. О многофункциональном использовании цифровых интегральных схем / Тез. докл. 5-й Всесоюз. научн.-техн. конференции «Проблемы создания систем управления судовыми техническими средствами». –Л.: Судостроение, 1973.
10. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Настраиваемые модули для управляющих логических устройств. –Л.: Энергоиздат, 1981.
11. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Судовые управляющие логические системы. –Л.: Ин-т повышения квалификации руководящих работников и специалистов судостроительной промышленности, 1974.
12. Якубайтис Э.А. Теория автоматов. Многофункциональные логические модули // Итоги науки и техники: Теория вероятностей. Математическая статистика. Теоретическая кибернетика. –М.: ВИНИТИ, 1976. № 13.
13. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. –СПб.: Наука, 2000. http://is.ifmo.ru/books/log_upr/1.
14. Шалыто А.А. Методы построения многофункциональных логических модулей          // Известия РАН. Теория и системы управления. 2004. № 6.
15. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. и др. Многофункциональный логический модуль. А.с. СССР № 813787 // Бюл. изобр. 1981. № 10.
16. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Многофункциональный логический модуль А.с. СССР № 758141 // Бюл. изобр. 1980. № 31.
17. Артюхов В.Л., Копейкин Г.А., Шалыто А.А., Фишман Л.М. Многофункциональный логический модуль // А.с. СССР № 746500. Бюл. изобр. 1980. № 25.
18. Артюхов В.Л., Шалыто А.А. Многофункциональный логический модуль. А.с. СССР № 1096637 // Бюл. изобр. 1984. № 21.
19. Степановская И.А., Ускач М.А. Представление булевых функций многофункциональными логическими элементами // Автоматика и вычислительная техника. 1973. № 4.
20. Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирование автоматов. –М.: Наука, 1977.
21. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Вопросы выбора и применения многофункциональных логических модулей / Дискретные системы. Т.1. Симпозиум IFAC. –Рига: Зинатне, 1974.
22. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Синтез комбинационных схем из многофункциональных логических модулей /Построение управляющих устройств и систем. –М.: Наука, 1974.
23. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Об оценках сложности реализации булевых формул древовидными схемами из настраиваемых модулей // Автоматика и телемеханика. 1981. № 11.
24. Шалыто А.А. Мультиплексорный метод реализации булевых функций схемами из произвольных логических элементов // Известия РАН. Теория и системы управления. 2003. № 1.
25. Шалыто А.А. Разложение булевых функций по крайним правым входным переменным таблиц истинности // Известия РАН. Теория и системы управления. 2003. № 4.
26. Стимулы для САПР //Поиск. 2003. № 27. http://is.ifmo.ru/science/4/.
27. Артюхов В.Л., Кузнецова О.С., Шалыто А.А. Оценка функциональных возможностей программируемых логических матриц // Автоматика и вычислительная техника. 1985. № 2.
28. Мелехин В.Ф., Душутина Е.В., Пышкин Е.В. Автоматизация синтеза при логическом проектировании цифровых устройств на основе базовых матричных кристаллов // Труды СПбГТУ. 1994. № 449.
29. Вольский В.Е., Пушин Ю.Н., Юнг В.Н. Проектирование пневматических систем управления судовыми энергетическими установками. –Л.: Судостроение, 1975.
30. Артюхов В.Л., Вольский В.Е., Шалыто А.А. Логический модуль. А.с. СССР № 798806 // Бюл. изобр. 1981. № 3.
31. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Многофункциональные логические модули из элементов с двусторонней проводимостью // Известия вузов. Приборостроение. 1981. № 4.
32. Прангишвили И.В., Ускач М.А., Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Многофункциональный логический модуль. А. с. СССР № 427336 // Бюл. изобр. 1974. № 17.
33. Шалыто А.А. Многофункциональные логические модули из элементов с двусторонней проводимостью //Известия РАН. Теория и системы управления. 2006. № 1.
34. Оре О. Графы и их применение. –М.: Мир, 1965.
35. Зыков А.А. Теория конечных графов. Новосибирск: Наука, 1969.
36. Артюхов В.Л., Фишман Л.М., Боброва И.Л., Шалыто А.А. Многофункциональный логический модуль. А. с. СССР № 841518 // Бюл. изобр. 1981. № 23.
37. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Функциональные возможности микроэлектронных резистивных наборов //Автометрия. 1979. № 3.
38. Шеннон К. Работы по теории информации и кибернетике. –М.: Изд-во иностр. литер., 1963.
39. Лупанов О.Б. Об одном подходе к синтезу управляющих систем – принципе локального кодирования // Проблемы кибернетики. 1965. № 14.
40. Дулепов Е.Г. Многофункциональные симметрические схемы // Автоматика и телемеханика. 1970. № 5.
41. Goto  E., Takahasi H. Some Theorems Useful in Threshold Logic for Enumerating Boolean Functions /Information Proceedings. IFIP Congress 62. Amsterdam, 1963.
42. Попов В.А., Скибенко И.Т., Василенко А.С. и др. Логическая ячейка. А. с. СССР № 520585 // Бюл. изобр. 1976. № 25.
43. Розенблюм Л.Я. Самодвойственная классификация и некоторые классы булевых функций // Автоматика и вычислительная техника. 1971. № 2.
44. Страздинь И.Э. Группа самодвойственных преобразований булевых функций // Теория дискретных автоматов. Рига: Зинатне, 1967.
45. Шалыто А.А. Модули, универсальные в классе самодвойственных функций и в «близких» к ним классах // Известия РАН. Теория и системы управления. 2001. № 5.
46. Stone H.E. Universal Logic Modules /Recent Developments in Switching Theory. (Ed. by A. Mukhopadhyay). NY: Academic Press. 1971.
47. Варшавский В.И., Песчанский В.А., Мараховский В.Б. Многофункциональные модули, реализующие все функции трех и четырех переменных / II Всесоюз. совещ. по теории релейных устройств и конечных автоматов. Тез. докл. Рига : Зинатне, 1971.
48. Артюхов В.Л., Шалыто А.А., Фишман Л.М. Многофункциональный логический модуль. А. с. СССР. № 760451 // Бюл. изобр. 1980. № 32.
49. Стародубцев Н.А. Соотношения для числа настроек многофункциональных логических модулей // Известия АН СССР. Техническая кибернетика. 1972. № 4.
50. Yau S.S., Tang C.K. Universal Logic Modules and Their Applications // IEEE Trans. on Computers. 1970. № 2.
51. Friedman A.D., Menon P.R. Theory and Design of Switching Circuits. NY: Computer Science Press, 1975.
52. Preparata F. P., Muller D. E. Generation of Near-Optimal Universal Boolean Functions // J. Comp. and Sistem Sciences. 1970. № 2.
53. Майоров С.А., Скорубский В.И., Кравцов Л.Я. Универсальные логические модули и их применение //Управляющие системы и машины. 1977. № 1.
54. Шалыто А.А. Модули, универсальные в классе всех булевых функций с парафазными входными переменными // Известия РАН. Теория и системы управления. 1997. № 5.
55. Евреинов Э. В., Косарев Ю. Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука, 1966.
56. Прангишвили И.В., Абрамова Н.А., Бабичева Е.В., Игнатущенко В.В. Микроэлектроника и однородные структуры для построения логических и вычислительных устройств. –М.: Наука, 1967.
57. Варшавский В.И., Мараховский В.Б., Розенблюм Л.Я. и др. Синтез схем в однородных структурах // Обзоры по корабельной автоматике. –Л.: Судостроение. 1973. Вып. 6.
58. Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. Однородные структуры. Анализ. Синтез. Поведение. –М.: Энергия, 1973.
59. Makhapadhyay A. Unate Cellur Logic // IEEE Trans. on Computers. 1969. № 2.
60. Артюхов В.Л., Розенблюм Л.Я., Шалыто А.А. Логические возможности некоторых типов каскадных структур / Сети связи и дискретные устройства управления. –М.: Наука, 1976.
61. Бутаков Е.А. Методы синтеза релейных устройств из пороговых элементов. –М.: Энергия, 1970.
62. Артюхов В.Л., Шалыто А.А. Реализация булевых формул однородными мультиплексорными и мажоритарными каскадами // Известия РАН. Теория и системы управления. 1996. № 5.
63. Артюхов В.Л., Шалыто А.А. Однородная структура. А.с. СССР № 900279 // Бюл. изобр. 1982. № 3.
64. Maitra K. K. Cascaded Switching Networks of Two – Input Flexible Cells // IRE Trans. Elect. Comp. 1964. № 2.
65. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. I. Синтез и анализ // Известия РАН. Техническая кибернетика. 1994. № 5.
66. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. II. Оценка числа и суммарной длины путей. // Известия РАН. Теория и системы управления. 1995. № 3.
67. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. III. Оптимизация числа и суммарной длины путей // Известия РАН.Теория и системы управления. 1995. № 5.
68. Шорт Р. Каскады с матричной структурой из двухканальных элементов                        / Микроэлектроника и большие системы. –М.: Мир, 1967.
69. Шалыто А.А. Реализация булевых формул и булевых функций однородными структурами // Известия РАН. Теория и системы управления. 2002. № 2.
70. Артюхов В.Л., Шалыто А.А. Ячейка однородной среды. А.с. СССР № 798804 // Бюл. изобр. 1981. № 3.
71. Артюхов В.Л., Шалыто А.А. Ячейка однородной структуры. А.с. СССР № 1092492 // Бюл. изобр. 1984. № 18.
72. Шалыто А.А. Ячейка однородной структуры. А.с. СССР № 1264162 // Бюл. изобр. 1986. № 38.
73. Шидловский С.В. Автоматическое управление. Перестраиваемые структуры. Томск: ТГУ, 2006.
74.  Шидловский С.В. Автоматическое управление. Перестраиваемые структуры с распределенными параметрми. Томск: ТГУ, 2007.
75. Фон Нейман Дж. Теория самовоспроизводящихся автоматов. –М.: Мир, 1971.
76. Варшавский В.И., Мараховский В.Б., Песчанский В.А.  Исследование проблемы остановки в клеточных моделях // Биофизика. 1973. № 3.
77. Варшавский В.И. Коллективное поведение автоматов. –М.: Наука, 1973.
78. Варшавский В.И., Поспелов Д.А. Оркестр играет без дирижера. –М.: Наука, 1984.
79. Тоффоли Т., Марголус Н. Машины клеточных автоматов. –М.: Мир, 1991.
80. Наумов Л.А. Решение задач с помощью клеточных автоматов посредством программного обеспечения CAMEL // Информационно-управляющие системы. 2005. № 5, 6.
81. Wolfram S. A New Kind of Science. IL: Wolfram Media, 2002.
82. Наумов Л.А., Шалыто А.А. Классификация структур, порождаемых одномерными двоичными клеточными автоматами из точечного зародыша // Известия РАН. Теория и системы управления. 2005. № 5.
83. Астановский А.Г., Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я., Стародубцев Н.А., Финкельштейн Р.Л., Цирлин Б.Я. Апериодические автоматы. –М.: Наука, 1975.
84. Варшавский В.И., Кишиневский М.А., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я., Таубин А.Р., Цирлин Б.Я. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. –М.: Наука, 1986.
85. Стародубцев Н.А. Синтез схем управления параллельных вычислительных систем. –Л.: Наука, 1984.
86. Киселев В.В., Шалыто А.А. Исследование переходных процессов в одноконтурных логических схемах // Известия РАН. Теория и системы управления. 1999. № 5.
87. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. http://is.ifmo.ru/books/switch/1.
88. Фон Нейман Дж. Вероятностная логика и синтез надежных организмов из ненадежных компонент / В кн. «Автоматы». –М.: Изд-во иностр. литер., 1956.
89. Гаврилов М.А. Избранные труды. Теория релейных устройств и конечных автоматов. –М.: Наука, 1983.
90. Закревский А.Д., Прангишвили И.В. Гаврилов Михаил Александрович /В книге «Теория дискретных управляющих устройств». –М.: Наука, 1982. http://www.computer-museum.ru/galglory/gavrilov.htm.
91. Шалыто А.А. У нас была Великая эпоха! //Информационно-управляющие системы. 2003. № 1. http://www.computer-museum.ru/histsoft/epoch.htm.
92. Stankovic R., Astola J., Shalyto A., Strukov A. Reprints from the Early Days of Information Sciences. Early Work in Switching Theory and Logic Design in USSR. Tampere Int. Center for Signal Processing. Tampere. 2016. http://is.ifmo.ru/books/2016/ticsp-report-66.pdf.
93. Шалыто А.А. Виктор Ильич Варшавский / В книге «Страницы истории отечественных ИТ». –М.: Альпина Паблишер. 2016. http://is.ifmo.ru/belletristic/2016/it_history_2.pdf.
94. Stanković R., Astola J., Shalyto A., Strukov A. Early Work in Switching Theory and Logic Design of Gavrilov School in Former Soviet Union. http://www.computer-museum.ru/english/galglory_en/Gavrilov_school_new.pdf.

Об авторе: доктор технических наук, профессор, Университет ИТМО
Помещена в музей с разрешения автора 1 ноября 2018