УДК 519.714:681.32 Ачасова С. М. Алгоритмы синтеза автоматов на программируе- мых матрицах/Под ред. О. Л. Бандман.—М.: Радио и связь, 1987.— 136 с.: ил. Предлагается новый подход для решения задач логического син- теза. На основе этого подхода разработаны алгоритмы решения сле- дующих задач компактной реализации программируемых логических матриц: построения кратчайшей дизъюнктивной нормальной формы системы булевых функций и кодирования (экономичного и противо- гоночного) состояний конечного автомата. В основе подхода лежит алгебра разбиений. Задается множество разбиений булева простран- ства на интервалы. На множестве разбиений определяются отноше- ние порядка и соответствующие этому отношению операции. Мно- жество разбиений образует алгебраическую структуру (решетку), которая допускает компактное представление. Исходя из свойств этой структуры, составляются алгоритмы решения задач логического синтеза. Отношение порядка на множестве разбиений и компактное представление этого множества позволяют уменьшить перебор в алгоритмах логического синтеза и улучшить емкостную (по памяти ЭВМ) оценку их сложности. Теоретический материал книги имеет самостоятельное значение и может быть развит для создания мето- дов решения других задач логического синтеза. Практическую часть книги составляют алгоритмы для автоматизированного проектиро- вания матричных больших интегральных схем. Для научных работников и инженеров, специализирующихся в области вычислительной техники и цифровой автоматики. Ил. 8. Библ. 34 назв. Рецензенты: канд. техн. паук А. А. Амбарцумян, канд. техн. наук И. А. Мамзелев Редакция литературы по вычислительной технике А 2405000000-174 046(01)-87 -45-87 Издательство «Радио и связь», 1987 ПРЕДИСЛОВИЕ РЕДАКТОРА На каждом этапе развития элементной базы и средств проектирования требуются новые постановки и новые методы решения задач логического синтеза, с ко- торыми сталкиваются разработчики систем автоматики и вычислительной техники. Математическую основу логического синтеза состав- ляет прикладная теория функций алгебры логики (в ино- странной литературе ее называют теорией переключа- тельных схем). Эта теория послужила основой для .со- здания нескольких поколений методов логического син- теза, соответствующих поколениям синтезируемых объ- ектов: 1) релейно-контактных схем, 2) схем из функци- ональных элементов, 3) схем средней степени интегра- ции, 4) схем большой и сверхбольшой степени интегра- ции. Каждому поколению соответствуют свои постанов- ки, свои размерности задач, свои критерии качества ре- шений и свои вычислительные средства для решения. В развитии методов логического синтеза четко про- слеживаются две тенденции, которые условно назовем интеграцией и автоматизацией. В первом поколении каждой элементарной операции алгебры логики соот- ветствовал элемент схемы; задачи синтеза ставились так, чтобы выразить заданные функции в наиболее про- стом виде—наименьшим числом операций и вхождений переменных. При этом в большинстве -методов исполь- зовалась классическая постановка — поиск минимальной дизъюнктивной нормальной формы (ДНФ). Во втором и третьем поколениях заданная функция отображается композицией из стандартного набора более простых, со- ставляющих базис схем малой и средней степени инте- грации. Затем интеграция достигает такого уровня, ког- да физически неделимый элемент рассматривается как элемент структурного синтеза устройства, а объектом логического синтеза является структура большой инте- гральной схемы (БИС). Тенденции большой интеграции и автоматизации имеют теперь определяющее значение. Первая форми- рует новый взгляд на результат синтеза—схему, вто- рая—на способ ее реализации. Прежде всего, большая интеграция изменяет критерии качества синтезируемых схем. Лучшей считается схема, занимающая меньшую площадь кристалла БИС. Этот критерий в сочетании с технологическим требованием регулярности структуры естественно побудил отображать на плоскость кри- сталла ДНФ функции или системы функций в виде матричной схемы, в которой столбцам соответствуют переменные, а строкам—элементарные конъюнкции или наоборот. Такие схемы, названные программируемыми логическими матрицами (ПЛМ), получили широкое рас- пространение. Потребность в методах синтеза ПЛМ вызвала новую волну интереса к преобразованиям функций в базисе ДНФ. Новые постановки задач отличаются в основном ориентацией на автоматизацию вычислений. Термин «методы синтеза» вытесняется термином «алгоритмы синтеза». Однако быстро растущую трудоемкость реше- ния задач не удается-«победить» с помощью ЭВМ. При- ходится отказаться от поиска точных решений. Более того, часто невозможно или нецелесообразно затрачи- вать много усилий на поиск «хороших» приближений к точному решению. Отсюда возникает еще одно требова- ние к методам логического синтеза — алгоритмическая гибкость. Это требование означает, что методы должны допускать построение алгоритмов, как простых для по- лучения грубых решений, так и сложных для хороших приближений к точному решению. Все перечисленные требования к методам синтеза ПЛМ были осознаны и сформулированы к началу 80-х годов. Было создано несколько комплексов алгоритмов. Каждый комплекс имеет свое назначение, использует свой набор эвристических приемов и свои языки про- граммирования. Однако все они основаны на одном и том же математическом аппарате: преобразование ДНФ логических функций достигается путем применения опе- раций «склеивания» пар интервалов, на которых значе- ния функций отличны от нуля. Поиск склеиваемых ин- тервалов осуществляется путем перебора, который с по- мощью эвристических приемов стараются сделать бо- лее направленным. Выработалось мнение, что такой подход единственный, что он исчерпывает возможности 4 математического аппарата и поэтому усилия следует направлять на поиск полезных эвристик, создание под- ходящих языков программирования и удобного сервиса. Такое мнение вполне справедливо относительно необхо- димости разработки хорошего программного обеспече- ния, но не возможностей математического аппарата. Действительно, преобразования логических функций в известных алгоритмах производятся в булевом прост- ранстве. На самом же деле как функции, так и все пре- образования определены на множестве интервалов бу- лева пространства. Свойства этого множества слабо изу- чены и мало используются. Однако известно, что чем глужбе исследована область определения функции, чем больше на ней «порядка», тем больше шансов найти способы сокращения перебора. Поэтому и стремяться упорядочить множество интервалов, исследовать его свойства и использовать их в алгоритмах преобразова- ния функций. В этом существо рассматриваемого в кни- ге подхода к разработке алгоритмов синтеза ПЛМ. Упорядочение множества интервалов достигается с помощью теории разбиений, основы которой изложены в замечательной книге Хартманиса и Стирнза [33]. Понятие множества разбиений с определенными на нем отношениями порядка и соответствующими этим от- ношениям операциями используется для представления множества всех интервалов булева пространства. При этом каждый интервал соответствует блоку (подмно- жеству) разбиения множества двоичных наборов. Мно- жество таких разбиений образует алгебраическую струк- туру (решетку), обладающую свойствами булевой алге- бры и изоморфную исходному множеству двоичных на- боров. Так осуществляется переход от множества дво- ичных наборов к множеству его равноблочных разбие- ний. В этой новой области определения преобразуемых функций отношения между импликантами выражаются явно, что естественно облегчает выбор тех из них, кото- рые лучшим образом удовлетворяют критериям постав- ленной задачи. Отсюда простота и однотипность про- цедур, а также возможность сокращения перебора. Более того, богатство свойств структуры и строгая симметричность отношений в ней позволили найти спо- соб улучшения емкостной сложности алгоритмов—вве- дение так называемых компактных представлений струк- туры. Структура множества разбиений представляется упорядоченным перечислением элементов множества, на 5 котором строятся разбиения (множества двоичных на боров или состояний). При этом любой блок любого разбиения извлекается из этого представления с по- мощью простых операций. Компактные представления являются главным результатом в изложенной теории. Основные процедуры алгоритмов синтеза ПЛМ све- дены к построению и анализу компактных представле- ний структуры. При этом в алгоритмах приближенной минимизации при поиске максимальных импликант со- кращение перебора достигается при использовании от- ношения порядка между разбиениями усеченной струк- туры — структуры, в которой отсутствуют блоки разбие- ний, пересекающиеся с областью нулевых значений ис- ходных функций. В алгоритмах кодирования перебор во- обще практически отсутствует: они состоят из простых операций упорядочения и переупорядочения множества состояний. Правила упорядочения обеспечивают получе- ние структуры множества разбиений, удовлетворяющего заданному критерию—либо наименьшему числу импли- кант в реализуемых функциях (экономичное кодирова- ние), либо отсутствию гонок при переходах из состоя- ния в состояние (противогоночное кодирование). Чрезвычайно интересно проявляется дуальность ал- горитмов решения этих двух задач. Построение структу- ры осуществляется по алгоритму экономичного кодиро- вания снизу вверх—от мелких разбиений (на пары со- стояний) к крупным (разбиения на два блока), а по ал- горитму противогоночного кодирования сверху вниз. Такая стройность построений при решении разных по критериям задач, вообще говоря, не свойственная алго- ритмам комбинаторного типа, свидетельствует о соот- ветствии математического аппарата решаемым задачам. Приведенные в книге алгоритмы, безусловно, не ис- черпывают возможностей предлагаемого подхода, они только служат хорошей иллюстрацией его полезности. Хотелось бы надеяться, что он будет разрабатываться для решения других задач логического синтеза, которые возникают и будут возникать в связи с усовершенство- ванием элементной базы. Читателю, который намерен воспользоваться готовыми алгоритмами, не разбираясь в их обоснованиях, можно рекомендовать ознакомиться с гл. 1, где вводятся все используемые понятия, и затем сразу перейти к гл. 3 или 4. В этих главах достаточно подробно описаны алгоритмы, чтобы выполнить про- граммирование без изучения материала гл. 2. 6 ГЛАВА 1 ЗАДАЧИ СИНТЕЗА ЛОГИЧЕСКИХ ПРЕОБРАЗОВАТЕЛЕЙ НА ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ МАТРИЦАХ 1. ПРОГРАММИРУЕМЫЕ ЛОГИЧЕСКИЕ МАТРИЦЫ В ЦИФРОВЫХ УСТРОЙСТВАХ Тезис о том, что наиболее целесообразной организа- цией микроструктуры ЭВМ на базе больших интеграль- ных схем (СБИС) является сеть из одинаковых автома- тов, одинаковым образом соединенных со своими бли- жайшими соседями и имеющих программируемые функ- ции, был выдвинут в 1962 г. [I]. Такие сети были назва- ны однородными вычислительными средами и наделены конструктивной и технологической однородностью, уни- версальностью (в смысле выполнения любого алгорит- ма), а также возможностью наращивания и параллель- ного выполнения сразу нескольких алгоритмов. Развитие микроэлектроники и вычислительной техни- ки подтвердило тезис об однородных вычислительных средах. Действительно, основным принципом, позволя- ющим проектировать сложные устройства на основе БИС быстро и дешево, является принцип регу- лярности. Развитие этого принципа привело к унифи- кации изделий в производстве, за исключением одной- двух последних операций. В результате возникли схе- мы-полуфабрикаты, имеющие однородную структуру, чаще всего матричную. Функции таких схем программи- руются с помощью последних технологических опера- ций. Матричный подход к организации структуры БИС позволяет сочетать массовость производства с возмож- ностью реализации произвольных логических функций. На современном уровне развития микроэлектроники и вычислительной техники теоретическая концепция од- нородных вычислительных сред воплотилась в реаль- ных объектах: сетях из микропроцессоров, параллель- ных микропрограммных структурах, вентильных, систо- лических, программируемых логических матрицах, ма- трицах макроэлементов*. * См «Электроника», 1979, № 6, 11; 1980, № 21; 1982, № 11: 1983, № 3. Один из основных разделов теории однородных вы- числительных сред составляют работы по синтезу ав- томатов в средах [2—5]. Особенности вычислительных сред, а именно их матричная структура, изменили кри- терий сложности реализации автомата и постановки за- дач синтеза. Сложность реализации автомата опреде- ляется площадью участка среды, на котором размещен автомат, а не числом элементов логической сети. Воз- никли методы синтеза автоматов, позволяющие от лю- бых форм задания автомата перейти к матрице, являю- щейся программой настройки среды. Эти методы оказа- лись применимыми без каких-либо изменений к про- граммируемым логическим матрицам. Программируемая логическая матрица [9, 10] пред- ставляет собой однородную сетку шин М, разделенную на две части: M[ и Ма (рис. 1). Каждая вертикальная Рис. 1 шина в Mi соответствует входному сигналу. Горизон- тальная шина в М формирует логическое произведение от входов. Каждая вертикальная шина в Mz формирует логическую сумму от логических произведений, резуль- тат суммирования является выходом. Таким образом, ПЛМ предназначена для реализации системы булевых функций, выраженных в ДНФ. При этом число входов ПЛМ соответствует числу переменных, число строк — числу конъюнкций в ДНФ системы, число выходов — числу функций в системе. Как и среды, ПЛМ обладают конструктивной и технологической однородностью, воз- можностью наращивания, универсальностью (в смысле реализации любой логической функции). Основным об- щим критерием сложности реализации автоматов в сре- де и ПЛМ, с учетом которого разрабатываются методы синтеза, является минимум площади среды или кристал- ла БИС. В узлах сетки шин находятся полупроводниковые элементы—диоды и транзисторы, которые могут быть включены в электрическую схему или выключены из нее на этапе программирования ПЛМ. Выключение эле- ментов производится путем разрушения соответствую- щих связей. ПЛМ является универсальным видом БИС, на основе которого реализуются как управляющие, так и арифметическо-логические устройства. При этом ПЛМ. могут выполнять самые разнообразные функции: памя- ти микропрограмм, преобразования кодов, поиска, ре- шающих таблиц и т. и, ПЛМ может занимать кристалл или разделять его с регистрами, вентилями и другими схемами. Производимые в настоящее время ПЛМ име- ют до 35 входов, 35 выходов, 100 строк. Часть входов и выходов могут быть внутренними и замыкаться через триггеры цепью обратной связи. Вот несколько типов ПЛМ: КР587РП1 (12 бинарных входов, 12 бинарных выходов, 64 строки), К588К1А (16 бинарных входов 12 бинарных выходов, 100 строк, 7 элементов памяти) fl4], KP556PT1 (16 бинарных входов, 8 бинарных вы- ходов, 48 строк) [II]. Опишем несколько конкретных примеров применения ПЛМ и способов организации устройств на их основе. Например, в машине IBM 7441 [15], выполняющей функции управления терминалом и режимом передачи сообщений, имеющей двустороннюю связь с централь- ным процессором, 86% всех логических схем реализова- но на 7 ПЛМ с параметрами: 31 вход, 29 выходов, 70 строк, в том числе 13 выходов и 13 входов внутрен- ние. Семь таких ПЛМ заменили 1731 логическую схему малой и средней степени интеграции. Вместо 6,5 плат размером 10Х7,5 см2, необходимых для реализации машины на схемах малой и средней степени интеграции, потребовалось 3,5 платы, чтобы разместить машину, реализованную на ПЛМ. В однокристальном микро- компьютере АМСС-1259 [12], предназначенном для управления и синхронизации, ПЛМ хранят микропро- граммы, управляются арифметическо-логическим устрой- ством и всем режимом работы микрокомпьютера. На одной из ПЛМ реализовано арифметическо-логическое устройство. 9- Многоразрядный сумматор [13] реализован в виде каскада ПЛМ. Входные коды разбиваются на группы по п разрядов. Для каждой группы используется свой сумматор—одна ПЛМ, имеющая 17 входов, 9 выходов, 73 строки. Для младшей группы разрядов применяется обычный сумматор, для остальных—сумматоры, орга- низующие две суммы: одну для случая, когда перенос в данную группу разрядов равен единице, другую для случая, когда перенос равен нулю. Нужная сумма выби- рается с помощью сигнала переноса. Если число групп разрядов больше двух, то одна дополнительная ПЛМ используется для организации сквозного переноса. Та- ким образом, для -V-разрядного сумматора требуется N/n+l ПЛМ, если N/n>2. Оптимальное число разря- дов в группе—восемь. При п>8 описанная реализация сумматора становится неприемлемой из-за больших раз- меров платы и значительной задержки, обусловленных большим числом термов в ДНФ системы функций, для каждой группы разрядов. ПЛМ широко используются для наведения «мостов» между крупными функциональными блоками, реализуе- мыми в виде отдельных БИС. Такие «мосты» необходи- мы для получения законченных конструкций и представ- ляют собой нетривиальные блоки произвольной логи- ки [16, 17]. Для реализации таких блоков на основе ПЛМ организуется как комбинационная, так и последо- вательностная логика. Для организации комбинацион- ной логики кроме двухуровневой ПЛМ используется упрощенный вариант—программируемая матричная логическая схема, представляющая собой первый уро- вень ПЛМ, т. е. матрицу Mi. Часто используется кон- кретный вид последовательностной схемы на основе ПЛМ—логический контроллер последовательности, представляющий собой автономный автомат, предназна- ченный для реализации логической последовательности как ряда переходов из одного состояния в другое. Архитектура самой ПЛМ может быть более гибкой, чем ПЛМ, представленной на рис. 1. Гибкость дости- гается за счет разрезания шин (линий металлизации) [18]. Разрезы в вертикальных шинах матриц Mi и Мз позволяют подавать переменные и выводить информа- цию с двух сторон. Делают разрезы и в горизонтальных шинах ПЛМ, при этом матрицу Mi разделяют на две части и между ними помещают матрицу М2 (рис. 2). Разрезание позволяет разделить оборудование на моду- 10 ли, повысить плотность записи информации в ПЛМ, бо- лее экономно и целесообразно использовать площадь кристалла. Места разрезов шин программируются поль- зователем. Рис. 2 Для увеличения гибкости структуры и расширения функциональных возможностей ПЛМ в [19] предлагает- ся чередовать входные и выходные шины матрицы, меж- ду вертикальными шинами располагать ряды триггеров. Такая матрица путем разрезания шин может быть раз- бита на независимые подматрицы с отдельным досту- пом для выполнения независимых заданий. 2. ИСПОЛЬЗУЕМЫЕ ПОНЯТИЯ Алгоритмы синтеза ПЛМ, описанные в книге, по- строены на основе теории конечных автоматов. Конечный автомат—это набор из пяти элементов {2, Г, 5, б, ^}, где S={oi, .... о,.}— конечное множество входных состояний; r={vi, ..., Vw}~ конечное множест- во выходных состояний; 5={si, ..., s„}—конечное мно- жество внутренних состояний; 6:2XS-^S—функция перехода; ?,:Ех5-^Г—функция выхода. Входные и выходные состояния связывают автомат с внешней средой. Автомат работает в дискретном времени. Опишем кратко работу автомата. Пусть в момент времени t ав- томат имел внутреннее состояние s; и входное оу Функ- ция перехода б определяет состояние s^ автомата в мо- мент ^+1 в ответ на полное состояние oyS,. Функция 11 выхода К ставит выход 'у, в соответствие полному со- стоянию SjSi (в этом случае автомат называется автома- том Мили) или внутреннему состоянию S{ (в этом слу- чае автомат называется автоматом Мура). Внутренние состояния автомата позволяют определить состояние выхода в момент t в зависимости от состояния входа не только в момент /, но и в предшествующие моменты, т. е. в зависимости от предыстории работы автомата. Для описания работы автомата чаще всего использу- ют таблицы и графы переходов. Функции перехода и выхода задаются двумя таблицами (переходов и выхо- дов) для автомата Мили Ai 3! °2 '3 °1 °2 "3 Si pi $з Sgl sl\^l Тз 7з1 Sa Sa — S3 , Ss та — Ъ SaLsa S.s —J 5з[т2 7i —J и одной для автомата Мура As 3l Зз ^ Si ] Si S3 Sal Ti Sz S2 — Sa 72 . Ssis^ Si —JTB Графы переходов автоматов Ai и Ag представлены на рис. 3, а и б соответственно. <3г «ifl °2// S-, ,-———-^ ^^ 1^•^eъrг sэ\\--^JI"e?s (^ ^чУг б) \_У5/ Рис. 3 Частным случаем автомата является автомат без памяти, выходное состояние которого зависит только от входного. На этапе построения логической схемы ав- томат принято считать состоящим из двух частей: логи- ческого преобразователя и памяти. Очевидно, что логи- ческий преобразователь—это автомат без памяти. 12 функции логического преобразователя (функции пе- рехода и выхода автомата) представляются в виде бу- левых функций, f{xo, ..., Хп-\), при этом все состояния (входные, выходные, внутренние) кодируются двоичны- ми кодами. Булева функция задается на множестве /tn) двоичных наборов (хо, ..., Хп-\). Общее число всех дво- ичных наборов длины п равно 2". В общем случае на каждом двоичном наборе булева функция может принимать значения 0 и 1 или неопреде- ленное значение (^ )-—либо 0, либо 1. Если функция на некоторых наборах имеет неопределенное значение, то она называется не полностью определенной или ча- стичной. Для задания полностью определенной булевой функции достаточно перечислить все двоичные наборы, на которых она равна единице. Множество таких набо- ров обозначим /1. Множество наборов, на которых функ- ция равна нулю, 1° определяется как дополняющее /! до 1^, т. е. /^/^V./1. Если функция имеет неопре- деленные значения, то она задается двумя множествами /' и /°, а множество наборов, на которых функция име- ет неопределенное значение, /* определяется как /<")\ (P\JI0). Булева функция может быть задана таблицей своих значений на множестве наборов /(/1) Например, функ- ция fi{xo, x\, Хг) задана следующей таблицей: ! Хо -|<0, Х(,х\—набору 10 ^. Троичный на- бор 10 ^ соответствует двум двоичным 100 и 101, набор 1 >}< 0—100, 110. Это те самые двоичные наборы, на ко- торых fi=l. Отсюда следует, что обе приведенные выше ДНФ реализуют функцию fi. Среди всего множества ДНФ, реализующих функ- цию f, можно выбрать такую, которая содержит наи- меньшее общее число букв. Эту ДНФ называют мини- мальной. ДНФ функции f, содержащая наименьшее чис- ло конъюнкций по сравнению со всеми другими ДНФ, реализующими f, называется кратчайшей. Задача по- строения минимальной или кратчайшей ДНФ функции называется задачей минимизации / в классе дизъюнк- тивных нормальных форм. Перейдем на язык булевых интервалов, дающий геометрическую интерпретацию понятиям, связанным с ДНФ булевой функции. Каждый двоичный набор из множества /(л) соответствует точке /г-мерного булева пространства. Наглядным представлением /г-мерного бу- лева пространства является единичный /г-мерный куб, каждая вершина которого соответствует одному двоич- ному набору из /(л). Множество вершин куба, как и булево пространство, будем обозначать через /(п), мно- 14 жество вершин куба, на которых булева функция рав- на единице,—Л, нулю—/°, неопределенному зниче- цию—/*. Множество точек л-мерного булева простран- ства, соответствующее некоторой грани единичного /z-мерного куба, называется булевым интервалом. На- пример, множество {0001, 1001, 0101, 1101} есть булев интервал. Существует более короткая запись булева интерва- ла—троичный набор, f-й компонент которого имеет зна- чение 0, если f-e компоненты всех двоичных наборов равны нулю, значение 1, если f-e компоненты всех дво- ичных наборов равны единице, неопределенное ( >(< ), если f-e компоненты двоичных наборов различные. Так, интервал {0001,1001,0101,1101} представляется троич- ным набором ^^ 01. Условимся троичные наборы обо- значать через ay. Если же интервал просто точка буле- ва пространства (вершина п-мерного куба), то обозна- чим его йу. В тех случаях, когда интервал как множест- во участвует в теоретико-множественных отношениях или операциях, будем обозначать его /а. или /в.. Для интервала существует понятие ранга. Ранг булева ин- тервала равен суммарному числу единиц и нулей в тро- ичном наборе (или в частном случае—двоичном набо- ре). Так, ранг интервала >{<>Ь:01 равен двум, ранг ин- тервала а, равен п. Интервалы ранга п в отличие от других булевых интервалов будем называть п-интер- валами. Булев интервал а,, который принадлежит области /' функции _/:/„. С /', называется допустимым для этой функции. Очевидно, что допустимый интервал соответ- ствует элементарной конъюнкции в ДНФ. ДНФ fi= ==XoXiX2\/XoX^X2\/XoXiX2 соответствует множеству интер- валов {100, 110, 101}, ДНФ fi=xox^\/xox~i— множеству интервалов {!>(< О, 10^<}. Для каждой ДНФ функции f(xo, ..., Хп-\) выполняется соотношение Р = U /а. , где {a.j} — множество интервалов, каждый из которых соответствует одной элементарной конъюнкции. Таким образом, каждой ДНФ функции f соответствует покры- тие множества Л допустимыми интервалами. Покрытие, содержащее минимальное число интервалов, соответст- вует кратчайшей ДНФ и само называется кратчайшим. Обычно такое покрытие строится из максимальных ин- 15 тервалов. Допустимый интервал а; называется макси- мальным для функции f, если не существует допустимо- го интервала о/, такого, что /а. С /„., т. е. внутри /1 нет интервала ку, объемлющего а,. Обобщим введенные понятия для частичных булевых функций. Интервал а; называется допустимым для ча- стичной функции f, если /а. П /0 = 0 и /о. П /1 т^ 0, т. е. интервал а, принадлежит области /4J^* и содержит хотя бы один элемент из области /'. Допустимый интер- вал ее, называется максимальным для функции f, если не существует допустимого интервала «_,, такого, что Л. С/а.. ДНФ частичной функции / соответствует по- крытию множества /' допустимыми интервалами. Крат- чайшая ДНФ частичной функции / соответствует крат- чайшему покрытию множества /1 максимальными ин- тервалами. Система булевых функций F (X) = {fo, ..., fm-i}, X= = {ху, ..., Хп-\}, задается множеством {^, ..., /^_, } об- ластей единичных значений функций fi ^F, если все функции системы являются полностью определенными, и дополнительно множеством {/^, .... ^_i} областей ну- левых значений функций fi eF, если среди функций си- стемы есть частичные. Система булевых функций также может быть представлен-а в виде ДНФ. При этом запи- сываются все конъюнкции, соответствующие булевым интервалам, на каждом из которых хотя бы одна функ- ция системы равна единице. Возле каждой конъюнкции в скобках указываются те функции, которые равны еди- нице на соответствующем интервале. Например, для си- стемы функций F} = {fo, fi, fz}, заданной таблицей -УО •<•! ^2 /О /I /2 11 ^о •Xl -У2 /0 /1 /2 0 о о 1 0 1 1 0 0 0 0 * о о 1 I 1 0 1 0 1 0 * 0 о 1 о 1 1 0 1 1 0 0 0 1 о 1 1 * 1 0 1 1 1 0 0 1 одна из ДНФ имеет вид Fl=XoXlX2(fo,f2)\/XoXlX2(fo,fl)\/ V-WCl.^2 (fo, /l) \УХоХ1Х2 (fl) \/XQXiX2 (fs) VХцХ^ (fs) . ДНФ системы булевых функций соответствует по- крытию множества областей {/д, ..., 1^_\} допустимыми 16 для функций fo, ..., frr,—\ интервалами. Кратчайшее по- крытие соответствует кратчайшей ДНФ системы буле- вых функций. Так, для системы Fi кратчайшая ДНФ имеет вид Fi=XoXiX2(fo, Ы VWz^oJOV-Wi (foJi) V \/xoxi(f2)- Области ^={000,001,010}, /;={001,010, Oil}, I!, ={000, 110, 111} покрыты четырьмя допустимы- ми интервалами 000, 0^1, 01 -л-, 11>^. Видно, что не все интервалы покрытия являются максимальными для сво- их функций. Все понятия, определенные в настоящем параграфе, можно найти, например, в [6, 8, 321. 3. МАТРИЧНАЯ РЕАЛИЗАЦИЯ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ Для разных технологий изготовления ПЛМ требует- ся представление систем булевых функций в разных ба- зисах. Так, в ПЛМ, выполненной на МОП-транзисторах, система функций представляется в базисе ИЛИ-НЕ, в ПЛМ на биполярных элементах—в базисе И-ИЛИ-НЕ. Обозначим через F(X)={fo(X), ..., f„i-\ (X)} систему булевых функций, заданных на множестве переменных Х= {хц, .... Xn-i} и выраженных в ДНФ PJ fj-= V f„ J =°. ••; /га—1. <—i Здесь ср, — элементарная конъюнкция от переменных {х.у, ..., Xn-v}'. pj—число конъюнкций в ДНФ функ- ции fy. Обозначим Ф={(р1, .... срр} множество элементарных конъюнкций, каждая из которых входит в ДНФ хотя бы одной из функций системы F (X) ; Х={хо,^о,..., л-л-i, х'г,-\\ множество всех переменных х^Х и их отрицаний; •'^((0;) =^ {^,,, ..., л,} подмножество переменных Xi.^X, к J входящих в конъюнкцию со; (л,, равен либо х,. либо ^,). Введем в рассмотрение следующие матрицы: ^i^llliiy II—матрица размера рХ2п, элемент ко- торой fl, если Xj^X(fi), \0 в противном случае; 2-1112 17 М2=||ц(у|1—матрица размера рХт, элемент ко- торой __ П, если ср, входит в ДНФ функции fj, 11 \Q в противном случае, X = || л', || — столбец из элементов х^Х; F == ||/,!| — строка из элементов /у ? F- Если для предсгавления булевых функций исполь- зуется базис ИЛИ-НЕ, система F(X) может быть запи- сана в виде следующего матричного выражения: F^Mi.Xr-Ma. (1) Здесь умножение матриц выполняется по правилам ма- тричного умножения с заменой арифметических опера- ций одноименными логическими; знак «т» обозначает транспонирование матрицы; черта над матрицей обо- значает поэлементное отрицание. Выражение (1) является математической моделью двухуровневой матричной схемы, реализующей систе- му F(X). При этом Mi соответствует первому уровню, реализующему множество конъюнкций Ф, а Ма—вто- рому уровню, реализующему функции fj^F как дизъ- юнкции некоторых ф, &Ф. Пример 1. Представим систему булевых функций F (X) = {fo = ХуХ^ V ^n^i V ^o-^i. fi == ХцХ^ \/ ХпХ^х-г} в виде матричного выражения. Множество конъюнкций, входящих в ДНФ функций fo я fi: Ф _- {ср, = XyX^Xt, ср2 = ХцХ^ Уз гг- -УО^Г ?4 == ХоХ^Х^}. Матрицы Mi и Ма имеют вид Ху Ху -У] Х\ Х^ Л"2 fy /i 'О 1 1 0 1 0 Пу1 Г1 0' cpi м^ о i о i о о , i о „, 1 0 1 0 0 0 уз 1 1 ?з _о i о i о i J^ LO i_|y4 Матричное выражение системы функций ~ ^~ — т _ ______ _ XyVXiVXy ГО 1 1 0 1 01 _? Г1 0~} ___ П (г р^ 010100 -^i ^^ XyVx^ i о lOlOOO'^i 11 - ~^—- 1 I "' LO i о 1 о iJ - LO iJ ^ov.t.i о i x•2 __________ _A-oV-ViV A-2_ --Уа-______ ________ = [^o-^i-^s V -to-»"i V -Co-»"]' -^0-^1 V ХоХ^]. 18 Операция матричного умножения с последующей ин- версией соответствует представлению функций в базисе ИЛИ-НЕ. В выражении (1) умножение с инверсией ис- пользуется дважды. Это отвечает тому, что в ПЛМ на МОП-транзисторах (МОП-ПЛМ) и первый, и второй каскады являются наборами вентилей ИЛИ-НЕ. Транс- понирование в выражении (1) означает перемену роля- ми строк и столбцов во втором каскаде МОП-ПЛМ по сравнению с первым, инвертирование матриц Х и F соответствует тому, что на МОП-ПЛМ подаются инвер- тированные переменные и значения функций на выходе ПЛМ также инвертированы. Все сказанное о соответст- вии матричного выражения (1) и принципиальной схе- мы ПЛМ можно проследить, сравнив пример 1 со схе- мой МОП-ПЛМ на рис. 4, и. SQ Лу ^1 ^-f Лу Л7^ t tj t \\v fHT , _a-(: :=, =^ =^ '-=. =^ l-'7-^ —Tl ^_„_-__iiU, [ i M< \ ?3 \ M2 [ ^"'^""''"^""''"l ^1 1 Ха Хд х^ Xf Ху_ х^ \ Ш Lt. ОТ1 _|———1Г—————--———~~-1 Ч J--—— -\ ,^T_—.__^i, [ ,.-^1 ^ i^!,^' ^"i_i ^ i i \ f0 ^\ M ® Рис. 4 2* 19 На рис. 4,6 приведена схема ПЛМ на основе бипо. лярных элементов, реализующая систему функций из примера 1. Для системы функций, реализованной в этой ПЛМ, матричное выражение имеет вид р^М.ОХГ-М^. (2. Матричная операция Q похожа на умножение матриц с заменой арифметических операций одноименными ло- гическими, только вместо дизъюнкции (сложения) по- элементных произведений строки и столбца здесь конъюнкция произведений, не равных нулю: ~Хц х0 (v-iiV-12 ••• "•«•2пЮ : = /\ (V-ijA-^j)- Х,г-1 v.a/\Xj+-"i _Xn-l На первом уровне биполярной ПЛМ производятся конъюнкции от входных переменных (операция Q в (2)), на втором—дизъюнкция логических произведе- ний, чему соответствует операция матричного умно- жения. Матричное представление системы функций х —————— ^ М= Mi Мз : (За) __ ^ F может рассматриваться как отображение принципиаль- ной схемы и топологического рисунка ее на кристалле. Одной и той же булевой функции соответствует мно- жество реализующих ее ДНФ. Следовательно, любой системе F булевых функций соответствует класс ма триц М, каждая из которых реализует систему F. Зада- ча синтеза ПЛМ—найти в классе матриц, реализую- щих систему F, одну матрицу, такую, которая удовлет- воряет заданным условиям, например имеет минималь- ное число строк по сравнению со всеми другими матри- цами в этом классе. 4. МАТРИЧНАЯ РЕАЛИЗАЦИЯ ЛОГИЧЕСКОГО ПРЕОБРАЗОВАТЕЛЯ КОНЕЧНОГО АВТОМАТА Пусть конечный автомат Л задан множествами вход- ных 2={cTi, .... Or)' внутренних 5 = {si,..., s.;,} и выходных r={vi, ..., v„,} состояний • и функциями переходов 20 6:SXS-^S и выходов ?.:SXS^T. Кодирующие матри- цы вида g° • • • g11-1 q° ••• 9'-' ~g°, ••• ^-'Ъ р? ••• ^"hl С - gi ••• gt1 ^ с = ^ ••• ^-' ^. -"Е . J S . ) g°r ••• g^1]^ L^•••^-1JS. го ... ^-' г' i /—1 ~i z, ••• z[ l ^ Cr = ^ '" z^ I ь , , ztШ ' ' ' Z•SI .J ^V где g, q, г—булевы переменные, ставят в соответст- вие каждому состоянию •з,, Sj, •^ набор значений пе- ременных, а каждой переменной g"*?G, ^'"(EQ, г"ег-два подмножества {2„ ^}. {5,, S^}, {Г„, PJ соответствующего множества состояний. При этом ^ - {-^••ё^ =1}; ^ - {^••ё". -=- о}; ^ = {^7 =1}-' S^={s^=0}; ^={т,:г^1}; Y^={^:z^-0}. Будем использовать обозначения, подобные тем, ко- торые были введены для систем булевых функций. Пусть Ф={ф\, ..., ф р}—множество полных состояний, при которых происходят переходы автомата, т. е. •^sSxS. Полное состояние автомата ф-i = {^jS^} может быть выражено конъюнкцией (?i=go - ^-V - Ф~\ (go, если ^.=1, ~ {q"1, если <7,"=1, где ^й== _ ; q"1-- .. [g1', если gl'^=П•, [q"1, если ^=0. Условимся через Y=[y°, ..., у'*'"'1} обозначать мно- жество внутренних переменных, определяющих состоя- ние перехода s, == 8(оу5д) (/= 1, ..., v). Функции перехо- дов автомата и функции выходов: yi= V Уп У=0> -, h-\; ?,:5(9S,)?S) г'= V У.. 7=0. •••• t- 1. y,!X(^)sr) 21 или, аналогично (1),в матричной форме Y= М,- •М,; G Q М, М '2- G _Q Матрица Mi=||u,y || размера pX2(d+h), строки ее взаимно однозначно соответствуют множеству Ф, столб- цы с номерами 1, 2, .... 2d—множеству G, с номерами 2d+1, ..., 2(d+h)— множеству Q; 1, если giC^Gf^,) при j < Id V-'j = или g'" G Q (ф,) при / > 2rf, т =--: j — 2й?, О в противном случае. Матрица М^=(|[л,у|| размера pXh, строки ее соот- ветствуют элементам множества Ф, столбцы—элемен- там множества У; М. если о(^)(=^, ' и — \ [Q в противном случае. Матрица Mg^||^y)f размера pXt, строки ее соот- ветствуют элементам множества Ф, столбцы — элемен- там множества Z; ^fl, если /.fg5;)G: П, '"' [0 в противном случае. G, Q — столбцовые матрицы из элементов множеств G и Q соответственно. V, Z—строчные матрицы, содержащие функции пе- реходов и выходов автомата. Переход к матричному представлению автомата вы- полняется по следующим правилам. 1. Если автомат задан таблицей или графом перехо- дов, то построение матрицы Mi заключается в расста- новке единиц в строках в соответствии с кодами вход- ного и внутреннего состояний для каждой непустой клетки таблицы или дуги графа. Порядок расположения строк соответствует порядку возрастания номеров внут- ренних состояний, в которые автомат переходит при со- 22 ответствующих фг Внутри подмножеств, приводящих автомат в одно и то же состояние, порядок строк про- извольный. Порядок расположения столбцов такой же, как порядок нумерации элементов в множествах G и Q. 2. Матрица Mg получается из кодирующей матри- цы Cs путем повторения каждой /г-й строки v;, раз, где Vft—число полных состояний, приводящих автомат в состояние s/,- 3. Матрица Мд получается из матрицы С г, поря- док строк определяется состоянием выходов для данно- го полного (для автомата Мили) или внутреннего (для автомата Мура) состояния. Матрицы Mi,M^ и Щ могут рассматриваться какод- на матрица 3' Q М, (36) М^ м2 М; Построить эту матрицу можно, исходя из описания алго- ритма функционирования автомата. Каждой строке со- ответствует один переход. Если это переход из состо- яния s; в состояние s/ при состояниях входов о, и вы- ходов у^, то в строке проставляются единицы в соот- ветствии с кодами о;, s,, SJ -\k в столбцах G, Q, У, Z соответственно. Столбцы G и Z являются внешними (связанными с другими устройствами) входами и выхо- дами ПЛМ, столбцы Q и У—внутренними входами и выходами, которые замыкаются в цепи обратной связи через элементы памяти. 5. ПОСТАНОВКА ЗАДАЧ МАТРИЧНОГО СИНТЕЗА ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ МАТРИЦ Здесь рассматриваются те задачи логического синте- за, которые вытекают из требований компактной реали- зации логического преобразователя в ПЛМ. Под ком- пактной будем понимать реализацию логического пре- образователя в ПЛМ, имеющей минимальную площадь. Площадь ПЛМ определяется размером матрицы М, представляющей логический преобразователь. На прак- 23 тике чаще всего внешними связями определено заране число входов и выходов проектируемой ПЛМ, т. е. за дано число столбцов в матрице М (За). В этих условияi поиски компактного матричного представления логиче: ского преобразователя сводятся к построению матри цы М, реализующей данный логический преобразова тель и имеющей минимальное число строк по сравнении- с другими его матричными представлениями. Здесь воз можны два случая. 1. Заданы коды входных и выходных состояний ло гического преобразователя, т. е. исходное матричное представление М как система булевых функций. В этом случае задача минимизации числа строк в матрице М является задачей построения кратчайшей ДНФ систе- мы булевых функций. 2. Коды входных состояний не заданы заранее (хотя заранее определена разрядность кода, чаще всего мини- мальная). В этом случае имеется возможность таким образом закодировать входные состояния, чтобы систе- ма булевых функций, порожденных кодом, имела бы кратчайшую ДНФ, наиболее короткую по сравнению с ДНФ системы, порожденной любым другим кодом. За- дачу поиска такого кода будем называть экономичным кодированием. Для матричного представления (36) логического преобразователя конечного автомата решаются анало- гичные задачи. Если заданы коды входных, выходных и внутренних состояний автомата, то соответствующая матрица М в виде (36) представляет систему булевых функций в ДНФ (конъюнкции реализуются в Mi, дизъюнкции конъюнкций—в Мг) и решается задача приведения ДНФ системы булевых функции к кратчай- шему виду. Если не заданы коды внутренних состояний автомата (считаем, что коды входных и выходных со- стояний заданы), решается задача их экономичного ко- дирования. При проектировании асинхронного автомата задача кодирования усложняется, так как в этом случае коду необходимо обеспечить и экономичность, и проти- вогоночность. Таким образом, мы определили три задачи синтеза компактной ПЛМ: приведение ДНФ системы булевых функций к кратчайшему виду, экономичное кодирование состояний логического преобразователя, противогоноч- ное кодирование внутренних состояний автомата. Далее даны точные постановки этих задач. 24 Задача 1. Приведение ДНФ системы булевых фу- нкций к кратчайшему виду. Обозначим /?, Л, /^ под- множества элементов га-мерного булева пространства [(л) = {а.о, ..., а^1_,}, на которых булева функция fi(X)(:=.F, Х-=^{Хц, •-., Хп-\}, имеет соответственно нулевое, единичное и неопределенное значения. Си- стему булевых функций f(X)=={/o,...,/„,-i}, среди которых могут быть частичные, будем задавать в виде множества Уд = {(а,, Ру)} (/' = 1, ..., рп) пар в об- щем случае троичных векторов. Пару (ay, ру) будем называть обобщенным (на множество функций) инте- рвалом. Часть я, обобщенного интервала назовем входной, а часть ру — выходной. Входная часть д, = -=. а"~1... а° обобщенного интервала является интер- валом в пространстве булевых переменных Х =. ={Ху, .... л-,,-,}. Выходная часть ^. = Р""1 ... ^ ... ^ обобщенного интервала является троичным вектором значений функций fo, .... fi, ..., fm-i на интервале а,.. При этом ^.=1, если /^.с/;,^.=0, если /^.с/^, Ц= ^, если /^.с/^. 7— Обозначим через /^ объединение интервалов ау, — Р таких, для которых ^.=0:/°=: И /а.. ' ' ,=1 ] «^.н - Р Аналогично /1 = (J la... 1=1 J ^.:^-=i Множество Уо = {(яу, ру)} представляет систему F, если для каждой функции fi^F выполнены условия: 1) 1\ == 1\\ 2) /^ -= 1^. Другими словами, множество обобщенных интервалов Ч^ц представляет области еди- ничных и нулевых значений всех функций системы. За- метим, что входные и выходные части обобщенных ин- тервалов из множества Vo могут быть двоичными век- торами, если входные части являются элементами буле- ва пространства (га-интервалами) и либо среди функций системы нет частичных, либо области неопределенных значений всех функций совпадают. 25 Поясним, почему разряды векторов яу и ^ перену мерованы справа налево. В гл. 2 будет использовав десятичное представление двоичного вектора, при этои естественно разряды двоичного вектора нумерован справа налево. Поскольку входной частью обобщенного интервала может быть двоичный вектор, то принята нумерация ее разрядов справа налево, для единообра- зия и разряды выходной части обобщенного интервала нумеруются справа налево. Множество обобщенных интервалов W =- {(ау. [3/)} реализует ДНФ системы F (или просто систему /7), если для каждой функции /,. ^F выполнены условия: ])^ГУ°=0; 2)ЛС^; 3)/^.П/;^0 при Р;.=1. Эти условия означают, что входные части о/ всех обоб- щенных интервалов являются допустимыми для своих функций (т. е. для тех функций, которые помечены еди- ницами в ру) и область единичных значений /^ каждой функции /, e=F покрыта допустимыми для этой функции интервалами (см. § 2). Заметим, что если из множества обобщенных интер- валов То удалить все те интервалы, в выходных частях которых нет единиц, то полученное множество реализу- ет некоторую ДНФ системы F. Из множества V обобщенных интервалов можно вос- становить ДНФ системы F. Для этого каждый обобщен- ный интервал надо представить в виде конъюнкции пе- ременных X, соответствующей входной его части, и эту конъюнкцию пометить теми функциями, которым соот- ветствуют единицы в выходной части обобщенного ин- тервала. Пример 2. Пусть система Fy{xo, x\, xs)=={fi), fi, fy], функции которой имеют следующие области определенных значений: 71 ^- -{010, 101}, /,°={000, 001, Oil, 100), /i={000, 010}, /I" ={001, 100, 101}, ^={000, 001, 010, 011}, /а =-{100}, представлена множеством обобщенных интервалов (°,, Эг) i (000, НО) 1 (001, 100) 2 ,(010, 111) 3 ""•(Oil, ]>(<0) 4 (100, 000) 5 (101, ^01) 6 :2б На наборах 110, 111 все функции системы не определены, поэтому множестве Vo нет обобщенных интервалов, входные части кото- пых содержали бы эти наборы. Очевидно, что множество У о после удаления из него интервала _(«о, Ps) реализует следующую ДНФ данной системы: F^x^iX^i, ^V^i-'^MV-W-^d'o, fi, ^)V VWi^Oyv'Wi-'i^/o). Множество обобщенных интервалов (0^0,110), _ (0^1,100), 1 - (^10,001), (1^1,^01) реализует _другую ДНФ заданной системы: F^x^di, ^V VWa (/2) \/XoX\ {fo) УхоХг (fo} • Действительно, входные части всех ин- тервалов из Vi являются допустимыми для своих функций и ^С~4 (/о 4010, 101, 110, 111}), 71 = /;, "7^ = /i. Обобщенный интервал (ay, ру), в выходной части ко- торого есть хотя бы одна единица, будет соответство- вать строке матрицы M=[Mi IMz], если значения 0,1, ^ во входной части его закодировать как 01, 10, 00 соот- ветственно, а неопределенным значениям в выходной части присвоить нули. Тогда множество обобщенных ин- тервалов будет представляться матрицей М и становит- ся понятным смысл названий «входной», «выходной» ча- стей обобщенного интервала: входные части составят входную часть ПЛМ (подматрицу Mi), выходные—вы- ходную часть ПЛМ (подматрицу М^). Пример 3. Матрица М, представляющая множество обоб- щенных интервалов YI из примера 2, имеет вид | х.2 л-з Xi -У] Хц х^ \ /а /i /о | 010001 110 ,, 010010 100 '"—001001 001 100010 001 Обобщенный интервал (с'.у, р^, в выходной части ко- торого есть хотя бы одна единица, называется макси- мальным, если интервал к, нельзя расширить без того, чтобы расширенный интервал не пересекся с областью нулевых значений хотя бы одной из функций системы. помеченных в (Зу единицами. Множество максимальных обобщенных интервалов, реализующее систему F, назы- иается кратчайшим, если оно имеет наименьшую мощ- 27 ность по сравнению со всеми другими множествами Mai с.имальных обобщенных интервалов, реализующими ci стему F. Очевидно, что кратчайшее множество обобще! ных интервалов У соответствует кратчайшей ДНФ ci стемы F и вкладывается в ПЛМ с наименьшим число строк. Таким образом, первая задача состоит в преобразс вании исходного множества обобщенных интервалов Ч^ представляющего систему булевых функций F, к крат чайшему множеству обобщенных интервалов. Эта зада ча классическая. Существуют методы точного ее реше ния для систем от малого числа (5,6) переменных i приближенного решения этой задачи для систем с боль шими значениями параметров: несколько десятков пере менных и функций, несколько сотен конъюнкций в ДНс! системы (см., например, [21—23]). С появлением ПЛ.У возрос угасший было интерес к этой задаче, что приве ло к интенсивному развитию методов решения задача минимизации, использующих идею направленного по- иска, при этом направление поиска выбирается по тем или иным эвристическим критериям [24—26]. В этой книге предлагается несколько алгоритмов одного клас- са (по качеству решения) с алгоритмами из [20, 23—26], отличающихся сложностью по памяти и времени выпол- нения на ЭВМ и имеющих меньшую сложность при ра- боте с системами функций определенного класса. Задача 2. Экономичное кодирование. Пусть задано множество состояний S={s\. ..., Sp}. Каждому состо- янию s, поставлен в соответствие вектор (5; —выходная часть гипотетического обобщенного интервала (s,, р,). Задача экономичного кодирования состояний s, ^5 при минимальной длине кодирующего слова состоит в при- своении каждому состоянию s; двоичного набора а; длины n=]\og2 p^(]log2 р[— ближайшее к \о^чР целое число, большее или равное log2 p), таким образом, чтобы множество обобщенных интервалов \Vo=^!a^. p;)} могло быть приведено к кратчайшему виду, наиболее коротко- му по сравнению с кратчайшим множеством, получен- ным при любом другом кодировании состояний 5. Ины- ми словами, задается матрица Мг размера рХт, тре- буется построить матрицу M) размера рХ^п, такую, чтобы система булевых функций, записанная в матри- це M=[M| j'Mz], имела бы кратчайшую ДНФ, наиболее 28 короткую по сравнению с тем, что могла бы дать любая другая Mi. Множеству строк матрицы М2 поставим во взаимно однозначное соответствие множество состояний 5= ={si, ..., Sp}. В матрице Ms можно выделить множест- во W подматриц w,, не содержащих ни одного нуля. Наименьшее число подматриц Wi, таких, что каждая единица из Мз входит хотя бы в одну w^ составляет минимальное покрытие Wmm матрицы Mg. Задача по- строения Wm\n для булевой матрицы (минимального дизъюнктивного базиса) поставлена в [27], там же даны методы ее решения. Если матрица Мз имеет не единст- венное минимальное покрытие, то мы будем иметь в ви- ду любое из таких покрытий. Пример 4. Пусть 3210 "I 1 0 1 - S, 11 1 0 s, О ^ 1 0 S3 Мг= 11 00 Si 01 1 0 s, 1 0 1 0 Se _ 1 0 >(< 1 _ ST Минимальное покрытие составляют следующие ее подматрицы: 32 21 '1 Us, Г1 П^ ^1 = 1 1 S, . ^2 = ^ I S, , 1 1JS4 LI U^ 3 1 0 Г1 1 i Se I s, W, =\ \ 6, ^4 = ' . LI *j^7 1 S7 Каждой подматрице w^^Wmin поставим в соответст- вие подмножество Ki c:5, определяемое теми строками матрицы Мз, на которых образована vs-i. Подмножест- во K.i будем называть K.-множеством. Подматрицы u)\, ..., ы'4 из примера 4 порождают следующие ^-мно- жества: /Ci={Si, S2, S.4}; " /Сз={52, S3, Ss}; Кз=[3б, S;}; A4={si, s/}. Если длина п кодирующего слова может быть выбрана произвольно, то множество состояний 5 может быть закодировано таким образом, что множест- ^ двоичных наборов, соответствующее каждому под- 29 множеству K.i, войдет целиком в некоторый интервал ; /г-мерного булева пространства, не содержащий ни о; ного набора, присвоенного любому s^i^E К i. Тогда MH( жество обобщенных интервалов Т ^- {(a;, P,>i (г'=1, l^minl), где (3; определяется подматрицей w,^W^ (при этом р^=1, если на k-м столбце матрицы Ма опрс лена Wi, &^ ==0 в противном случае), будет являтьс: кратчайшим для системы F(X), порожденной приняты.' кодом С s- Эта система может быть представлена ма трицей М с числом строк, равным [tt^minl. Очевидно что ни один код для заданной Мз не может дать матрич ное представление соответствующей ему системы меньшим числом строк, чем ) Wmin \ • Пример 5. К матрице М; из примера 4 присоединим матрп цу Mi, соответствующую следующему коду состоянии Si, ..., 57: "О Г 0- J '-s^ 1 1 0 S2 1 1 1 Ss 000 Sf 1 0 1 SB 0 0 1 Ss -° l 1- s^ ""О Г O-l^i М, 1 '-' t * I ° 7 Такое кодирование дает следующее кратчайшее множество обоб щенных интервалов: (^^0, 1100), 0^, ОНО), ((Ь)< 1, 1010), (01^,0001). Следовательно, ПЛМ, реализующая полученную систему функций, имеет четыре строки, и ни один другой код не может дать ПЛМ с меньшим числом строк. При минимальной длине кодирующего слова д== =]log2p[ может не найтись такого кода Cs- который позволил бы реализовать каждое /(-множество одним интервалом. При определенном коде Cs каждое К, может быть реализовано некоторым подмножеством бу- левых интервалов, не содержащих кодов, присвоенных состояниям ^^ К г Множество интервалов, наименее мощное из всех реализующих совокупность /(-множеств, порождаемую покрытием tt^min, обозначим через R^ • Наилучшим в смысле экономичности кодом множест- ва S для Мз при длине п=}\о^р[ будем называть такой С ' ^с Cg, что | R^ | < I /?rnin I для любого другого кода Сд с тем же п. Точное решение задачи экономичного кодирования, требующее перебора кодов, неприемлемо громоздко. По- 30 этому будем с помощью эвристических приемов строить «хороший» код. Допустим следующее отступление от точной поста- новки задачи. В практических случаях в матрице Ма число столбцов существенно меньше, чем число строк (матрица сильно вытянута по вертикали). Минималь- ным покрытием такой матрицы (определяющим Л-мно- жества) или близким к нему является покрытие столб- цовыми подматрицами, не содержащими нулей. Поэто- му в качестве исходной информации при экономичном кодировании мы будем брать совокупность /(-множеств, соответствующих столбцовым подматрицам, а в алго- ритме кодирования учитывать пересечения таких /<-мно- жеств, имея в виду, что любое /(-множество, соответст- вующее Wi^Wmin, является пересечением «столбцовых» Я-множеств. При кодировании внутренних состояний автомата К-множества выделяются для каждой пары (о,, Sj) (входное состояние, внутреннее состояние). В одно /(-множество входят те внутренние состояния, из кото- рых при входе <т, автомат переходит в состояние SJ (для автоматов Мура) и имеет выходное состояние "Гд (для автомата Мили). Задача 3. Противогоночное кодирование. При функ- ционировании асинхронного автомата могут возникнуть так называемые состязания или гонки между элемента- ми памяти. Гонки возникают, если при переходе автома- та из одного состояния в другое должны переключить- ся два или более элементов памяти. Из-за небольшого разброса во времени срабатывания элементов памяти, неодинаковых длин логических цепей, случайных задер- жек один или несколько элементов могут переключить- ся раньше, чем остальные, т. е. выиграть гонки. Это мо- жет привести к переходу автомата в состояние, не пре- дусмотренное его функцией переходов, т. е. к непра- вильному срабатыванию. В таком случае гонки назы- ваются опасными или критическими. Если автомат под влиянием гонок не отклоняется от заданного поведения, гонки называются неопасными или некритическими. Пример 6. В автомате при одном и том же входном сигна- пе имеются два перехода Si-^s;, Ss-^-s^ — из состояния Si (sg) автомат лереходит в состояние 53(54). Состояниям присвоены коды: si=000, ^^ПО, 5з==010, S4=100. При переходе Si-^Sa возникает гонка меж- ДУ первым и вторым элементами памяти (разряды кода нумеруют- 31 ся справа налево, начиная с нуля, номера элементов памяти со; падают с номерами разрядов кода). Если гонку выиграет, например первый элемент, то автомат вместо состояния Sz попадает в состод ние S4> это значит, состязание опасно. Состязание было бы неолац ным, если состояния ^ и s< были бы закодированы соответстве! но 011 и 101. ) Опасные гонки в асинхронном автомате устраняютс с помощью специального кодирования внутренних состс, яний, которое называют противогоночным [30]. В рабе, тах [28, 29] сформулировано необходимое и достаточно' условие отсутствия опасных состязаний в асинхронно:, автомате. Суть его в следующем. Два перехода Si -> &' и Sy ->- s^, происходящие под действием одного и того ж'. входного сигнала и такие, что s/, ^= s,., называют состя' зающимися. Два перехода в автомате, состояния кото1 рого закодированы двоичным кодом, называют развя1 занными, если хотя бы один (пусть г-й) разряд код;' имеет одно значение для пары состояний (s,, s/;) и про тивоположное—для пары (Sy, s^). Например, пр;1 s, = 000, ^=^110, Sy -=: 011, s,. = 101 переходы (Sy -» ^)< (Si—s^) развязаны по нулевому разряду кода. Итак) в автомате, состояния которого закодированы двоичны», кодом, опасные состязания отсутствуют тогда и толь; ко тогда, когда развязаны любые два состязающихс?, перехода. ^ Кроме этого условия при противогоночном кодирова-, нин часто используют достаточное условие отсутствия, опасных состязаний в автомате [28]. Оно формулирует- ся для ^-множеств внутренних состояний — множеств, из элементов которых при фиксированном входе ав- томат переходит в одно и то же состояние. Покажем на примере, как из таблицы переходов автомата выде- лить ^-множества. Пример 7. Из таблицы переходов автомата ст, 33 Стз S^ О) о^ Sy "2 1 "3 2 S3 5, 5, 5з •S'4 5.t S^ .УЗ S^ S^ Sg Sc, ^6 _ ^4 SQ Sr, _ можно выделить следующие й-множества: по первому столбцу k\-^ ={S\, S2, Ss], ks={St, Ss, Se}; ПО BTOpOMy ka={Si, S,}, ^4={S2, S;|), ks={ss. Se]; no третьему ^={si, s:}, ki ={53, Sf], ks={ss, Ss}. 32 Заметим, что й-множества внутренних состояний ав- гомата, используемые при противогоночном кодирова- нии, совпадают с ТС-множествами, выделяемыми по зходным состояниям и состояниям перехода без учета зыхода и используемыми при экономичном кодировании. Пары состязающихся й-множеств рассматривают по- побно парам состязающихся переходов. Так, в приме- ре 7 состязаются k\ и &2, попарно состязаются из, ^4, ^5, гак же, как и ke, k-г, ks. Два ^-множества (ky, k^) счи- таются развязанными, если хотя бы один, пусть t-й, раз- ряд кода имеет одно значение для всех состояний мно- жества ky и противоположное—для всех состояний множества k^. Достаточное условие отсутствия опасных :остязаний в автомате—все пары состязающихся й-мно- жеств развязаны. При противогоночном кодировании требуется мини- мизировать длину кода и, следовательно, общее число столбцов матричного представления автомата. Точное решение задачи противогоночного кодирования с мини- мизацией длины кода удается найти для автоматов, имеющих таблицы переходов небольших размеров [32]. В нашей работе предлагается алгоритм противогоночно- го кодирования, который обеспечивает длину кода, близ- кую к минимальной. Этот алгоритм отличается от из- вестных алгоритмов такого типа [28—30] «техникой» и тем, что позволяет сочетать противогоночное кодирова- ние с экономичным. ГЛАВА 2 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АЛГОРИТМОВ МАТРИЧНОГО СИНТЕЗА 6. ТЕОРЕТИКО-СТРУКТУРНЫЕ СВОЙСТВА СОВОКУПНОСТИ РАЗБИЕНИЙ БУЛЕВА ПРОСТРАНСТВА Разбиения булева пространства. Разбиением множе- ства S называется множество подмножеств S^crS, та- ^х, что: \)SiC\'Sj=0 при 1ф] (подмножества S^ по- ларно не пересекаются), 2) и5д=5 (все вместе подмно- жества 5д образуют множество S). 3-1Ц2 33 Множество /(п) -= {ад, ..., адл_,} элементов (д-инте валов) /г-мерного булева пространства разобьем i подмножества мощности 2", vs{0, ..., /г}, таким обр зом, чтобы эти подмножества являлись булевыми инте| валами ранга п—v, определенными на одной совокупи сти координат {^,,, ..., х^}с^{хо, ..., Xn-i}. В COBOKVI ность включаются те координаты, по которым п-интерв, лы одного подмножества склеиваются в интервал ранг п—v, иначе говоря, те координаты, которым в троично векторе, представляющем интервал, соответствуют щ определенные значения ( ^). Например, интерва {0000, 0001, 0010, ООН}, представленный троичным aei тором 00 >^*, определен на совокупности {хо, xi}. По; множества разбиения будем называть блоками, элеме( ты каждого блока будем объединять чертой сверху. Пример 8. Разбиение множества /(3) ={000, 001, 010, 01 100, 101, 110, 111} для v=2 и определяющей совокупности коорд:1 пат {хц, Хг] имеет вид I {000, 001, 100, 101; 010, Oil, 110, 111}. Имеется С'1 (число сочетаний из п элементов по v'' различных разбиений множества /(п) на блоки мощпс сти У так же, как имеется С„ различных совокупив стей координат мощности v. Множество таких разбив ний будем обозначать в" = {6^} (i = 0, ..., С^ -— 1). раз биение в множестве — 6J = {5,}, | By \ = 2\ j == 0, • ....S""'—!, By—блок в разбиении. Пример 9. Запишем все разбиения множества /'' на блч!: мощности 22 (v=2). Рядом с каждым разбиением укажем опреде ляющую совокупность координат ( ^0= {000, 001, 010, Oil; 100, 101, 110, 111}, {xc, -У,}.( e^{ouo, 001, loo, loi; oio, on, 110, IH}, {хц, x,.],i ej={000, 010, 100, 110; 001, ОН, 101, 111}, [x„ л-;}. Заставив v «пробежать» все значения нз множеств-' {О, ..., п.}, мы получим совокупность в=ив'' множеств разбиений. Чтобы сделать запись разбиений менее гро моздкой, вместо двоичных наборов будем использовать их десятичные представления. ^ Пример 10. Совокупность 6 разбиений множества / ' С'^1 пример 8): 34 ' ; в°={0, 1, 2, 3, 4, 5, 6, 7}, {0}, Ql= {0^; 2Д 4^; 67}, {х,}, е1 - el -- {о^; Гз; 4~б; 5J}, {х,}, бг = {ОЛ; П5; 2^; 3,7}, {х,}; ^={0, 1,2,3; 4, 5, 6, 7}, {х„ х,}, 82 = 6? = {0, 1, 4, 5; 2, 3, 6, 7}, {х„ х,}, 9|={0,2,4,6; 1,3,5,7}, {х„х,}; 93 = {ОТТХ^ЛГЗТб^}, {.Co, Xt, x,}. Совокупность разбиений как структура. Будем рас- :матривать отношение эквивалентности [6, ] на множест- зе f^'-a-g^} a^ означает, что а^, Од находятся в одном \ том же блоке разбиения 0] [31]. Разбиения можно складывать и умножать по сле- дующим правилам [33]. 1. Сложение. 6^ = 6, + 9L ag, а/, попадут в один )лок разбиения 6^, если найдутся й^, ..., ag , такие, гго а^}а„, а^[В]}а^, а,Л^а^ .., ^[6;.]^. Иными •ловами, каждый блок разбиения 6^ является объеди- юнием всех блоков из 6^ и 61, таких, отношению пересечения которых соответствует связный граф. 2. Умножение. 6^=6';.6^, ag, а^ попадут в один )лок разбиения 6^, если fl^[6]]a/, и a^Ma/i. Иными 'левами, каждый блок разбиения 9^ равен пересече- 1ию блоков из 6' и 6т, если пересечение не пусто. Пример 11. Пусть имеются два разбиения из совокупности Q 1ри п=4: ^={ОП7273; 4, 5, 6, 7; 8, 9, 10, 11; 12, 13, 14, 15}, 12 == {ОПТ^; 2, 3, 6, 7; 8, 9, 12, 13; 10, 11, 14, 15}. ^ + 9? = {0, 1, 2,3,4,5, 6, 7; 8,9, 10, 11, 12, 13, 14, 15}, ^•б!={0~1; 2Д 4^5; 6,7; 8^9; Ю7П"; ПЦЗ; 14,15}. 1* 35 На множестве 9 =: [Q]} (ч=0, ..., п; i =: 0, ..., С'- будем рассматривать отношение частичного поряд 6^<6^ означает, что из а^[^]а^ следует йд.[6т] Другими словами, для каждого блока B[^Q, в р биении бт найдется блок By, целиком включаюц блок B[. Например, нетрудно убедиться, что bj> 6^>6;. a 6g и 61 не сравнимы (6д, б;, 6^, бд2 см. в п мере 10). В частично упорядоченном множестве Q нижь границей для двух разбиений 6J и 9т. является р биение 6^, такое, что бд<6, и 6^ < 6т. Разбиение является максимальной нижней границей для 6', если любая нижняя граница 6^ для QJ, От удовлетЕ ряет отношению 6^<:6д. Аналогично верхней гран цей для 6^., 9т является разбиение 6^, такое, ч1 ^ ^' ^ и ^от ^ ^т' Разбиение б^ является мини-мальт. верхней границей для 6^, 9т, если любая верхняя гр ница 6^ для 6J, 6т удовлетворяет соотношению б^<б Например, разбиение б3 (см. пример 10) является вер ней границей, а разбиение 0j— минимальной верхне границей для Q[ и б^. Любые два разбиения О'^, 6т имеют максимальну: нижнюю и минимальную верхнюю границы. В само деле, в разбиениях, входящих в в, содержатся все ш тервалы /г-мерного булева пространства, а сравнени разбиений осуществляется поблочно. Отсюда следуем что для любой пары пересекающихся блоков ^/6Е1 и By GE 6}. В[Г\Ву^0, найдется минимальный объем лющий блок Вр в некотором разбиении 6^, В; с.В^ ВуС.Вр, а это значит, что разбиение Выявляется мини мальной верхней границей для б^. и 6.. При это» 6^ == OJ 4- Ц- Аналогично для любой пары пересекаю щихся блоков Bi G ^ и ^ G бт. найдется блок Вр ^ -==В[Г]Ву в некотором разбиении 6^, которое и яв ляется максимальной нижней границей для 6J и 9т. Пр^ этом 9^=:9;.6J. 36 Известно, что частично упорядоченное множество Является структурой, если в нем каждые два элемента ^меют максимальную нижнюю и минимальную верхнюю границы [31, 34]. На этом основании считаем, что ча- стично упорядоченное множество разбиений ё=<6, ^> является структурой. В структуре Q имеются об- ццие для всех разбиений универсальные верхняя и ниж- няя границы-________ Q"={ao, а,, ..., а^_^}; 6° = {йо, а,, ..., a^_J. [Универсальные верхняя и нижняя границы называются ^единицей и нулем структуры соответственно. Без доказательства скажем, что структура в, обла- дающая нулем и единицей, является дистрибутивной, [замкнутой относительно дополнения или булевой струк- турой [31, 34] (в этом легко убедиться, рассмотрев все 'понятия на конкретной структуре из примера 10). Ди- стрибутивность структуры следует из того, что в ней справедливы аксиомы дистрибутивности: 9^.(бт-4-0^=:(6].ер+(9^); ^+(9).6,)=(9;.+6р.(9,'+6^). Пример 12. Проверим второй закон дистрибутивности. Рас- смотрим три разбиения множества /'*, входящие в структуру Q: 6^={0j; 2^3; 4^5; 6,7; 87»'; 10.11; ЩЗ; 14^5}; 9} = {б, 2, 4, 6; 1,3,5,7; 8, 1U, 12, 14; 9, 11, 13, 15}; 6't = {0, 1,2, 3, 8,9, 10, 11; 4, 5,6,7, 12, 13, 14, 15}. Произведем над разбиениями следующие действия: eJ.9^^2; 4Тб; ГЗ; 577; 8JO; T2J4; 97П; f3J5}; ^+(6}-6^)={0, 1,2,3; 4,5,6,7; 8,9,10,11; i27l37T4, 15}; ^ + 6} = {0, 1,2, 3,4,5,6,7; 8, 9, 10, 11. 12, 13, 14, 15}; ^ + ^ ---= {О, 1, 2,3,8,9, 10, 11; 4,5,6, 7, 12, 13, 14, 15}, (6<+6}).(6^+6ft)^{OJ^3; 4:5,6,77 8,9,10,11; 12,13,14,15}. ^ким образом, ^ + (6). 6^) = (6, + 9Т). (6^ + 6^). Дополнением разбиения 6^ называется разбиение 6). такое, что е^+Э}^^", eJ-6J=9°. В 6 для каждо- г0 "J существует единственное дополнение 6т. 37 Пример 13. Разбиения из примера 10 &5={бП; 2^3; 4J; 677} и бг2 = {ОГ2Л76; 1, 3, 5, 7} дополняют друг друга в в. Действительно, ^ + ^ = {0,1,2,3,4,5,6,7}; 0^. ej = {О, Т, 2, "3, "4, "5, 6.1 Графом булевой структуры является д-мерный к; [31, 34]. Вершинам куба соответствуют разбиения ( а дугам — пары разбиений 6J, От, таких, что 6J < 6т, не существует такого 6^ в в, что 6'<6.<^6т. По множество разбиений в" с: Q (ч == 0, ..., д), содержаще С^ разбиений на 2"-' блоков мощности 2' кажды, условимся называть v-м уровнем структуры Q. Нош уровня, которому принадлежит некоторое разбиени. определяется верхним индексом в обозначении разбж ния. Граф структуры 0 для п==3 изображен на рис. i ^^-й^те________^ B^'{aw,V^7} g}-{[iw;г^7}^9^-Щw;:/^7} w/IV^"^^^""^//^""""""1'" oo ^ .^^^\W^^^\. f00 ^=[1У;2^;^;^7} e/-[U,2;^wy} s^[a^;^;z,ff;3^} ooB^^_______-____V-.Q ^{o.W^M?} Рис. 5 Вершины графа, соответствующие разбиениям одного' уровня, расположены на одной горизонтали. Разбиения можно нумеровать произвольно, в произ- вольном порядке можно располагать и блоки в разбие- ниях. Условимся разбиениям первого уровня всегда присваивать номера, совпадающие с номерами коорди- нат, по которым я-интервалы в блоках этих разбиений являются соседями. В примере 10 так и сделано: раз- биению 6^ соответствует {л-г.}, ^—{•'ч}. Ц — {х^}- Далее удобно будет вместо определяющего каждое разбиение 38 подмножества координат рассматривать двоичный век- тор g=g"~1 ...g0 с весом v (вес равен числу единиц в g}. Если координата XJ входит в определяющую некоторое разбиение совокупность координат, то g1 =\. Так, каж- дому разбиению первого уровня соответствует ^-вектор .с весом 1, единственная единица стоит в разряде с тем же номером, который присвоен самому разбиение. [Каждому разбиению второго уровня соответствует свой ^-вектор с весом 2 и т. д. Пример 14. Запишем соответствие между разбиениями \\з примера 10 и ^-векторами: е°—ооо, 6;-ooi, е;-ою, Ьд-юо, б^—оп, 6^— 101, 6J—110, в3-!!!. Структура в изоморфна булевой структуре G^ ==