Теория автоматов

Y0 = Æ;	Y1 = {y2, y5, y10};	Y2 = {y3, y4};	Y3 = {y1, y3 , y4};
Y4 = {  y10, y11};	Y5  = {y6, y8};	Y6 = {y1};	Y7 = {y9, y14};
Y8 = {y7};	Y9 = {y6, y13};	Y10 = {y12}.

Закодируем каждую микрокоманду таким  образом, чтобы выражения для  микроопераций сводились к одному терму. Тогда выходные сигналы МПА будут сформированы слоем конъюнкторов, следующих за  кодами микрокоманд.

 

Матричная реализация комбинационных схем и автоматов

Развитие  микроэлектроники привело  в начале 60-х годов к появлению  ИС, которые представляют собой функциональные узлы электронной аппаратуры, все компоненты  и соединительные проводники которых изготавливаются  в объеме или на поверхности полупроводникового кристалла.  Сложность ИС принято оценивать числом логических элементов, необходимых для выполнения ее функций. С этой точки зрения все ИС разделяются на следующие классы: МИС (1-10 ЛЭ): СИС (10-100 ЛЭ): БИС ( более 100 ЛЭ): СБИС (Свыше 1000 ЛЭ).

В зависимости от функционального назначения различают следующие БИС:

• БИС памяти - ЗУ;
• логические БИС, реализующие логические функции:
• линейные БИС, предназначенные для построения различных преобразователей информации, усилителей.

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

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

Выпускаемые промышленностью матричные  кристаллы имеют размерность  не менее 128 ´128. Поэтому целесообразно использовать их для реализации достаточно больших схем УА, либо отдельных их частей, если имеющихся входов/выходов недостаточно для реализации всех булевых функций, полученных при проектировании.

Матричная реализация комбинационных схем

Любая ДНФ системы булевых функций  y₁, y₂, ... , y_n  от переменных x₁, x₂, ... , x_L может быть реализована двухуровневой схемой, на первом уровне которой формируются все различные термы X_1,  X₂, ... , X_H , а на втором дизъюнкции этих термов y₁, y₂, ... , y_n. В логических БИС комбинационные схемы часто выполняются в матричной форме, Рис. 1.

Рисунок 8 Структура матричной реализации комбинационных схем

 На рисунке  М₁ и М₂ представляют собою систему ортогональных шин, в местах пересечения которых при изготовлении схемы могут быть установлены полупроводниковые элементы - транзисторы или диоды. Каждая горизонтальная шина матрицы М₁ - это терм Х_h, а каждая вертикальная шина матрицы М₂ - это дизъюнкция y_n термов, полученных в матрице М₁. Иначе, матрица М₁  формирует H различных конъюнкций, от которых в матрице М₂ реализуется N различных дизъюнкций. При построении матриц М₁ и М₂  используются полупроводниковые биполярные и МОП -элементы.¹

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 9 Матричная реализация системы логических функций на биполярных элементах

Рассмотрим матричную реализацию комбинационных схем на примере системы булевых функций, представленных в ДНФ:

y₁ = `x<sub>1</sub>x<sub>2</sub> Ú x<sub>1</sub>`x₂`x₄ Ú x₁x₃x₄;

y₂ = `x<sub>1</sub>x<sub>2</sub> Ú `x₁`x<sub>3</sub>x<sub>4</sub> Ú `x₁`x<sub>2</sub>x<sub>3</sub> Ú x<sub>2</sub>`x₄;

y₃ = x₁`x<sub>2</sub>`x₄ Úx₁`x<sub>3</sub>   Ú `x₁`x₂x₃.

Реализация этой системы функций  на ПЛМ показана на Рис.2.  Точками  на схеме обозначены места межсоединений вертикальных и горизонтальных шин, необходимые для реализации термов, входящих в систему функций.  Эти межсоединения образуются в матричной структуре при программировании матрицы.

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

S(M) = S(M₁) + S(M₂) = 2LH + HN [бит]

Для сокращения информационной емкости  при реализации системы функций  необходимо представить ее в ДНФ с минимальным числом различных термов.  

Матрицы М₁ и М₂ при реализации системы принято изображать в виде таблицы, столбцы которой отмечаются переменными x₁,  ... , x_l  и функциями y₁, ... ,  y_n. Каждому терму ПЛМ ставится в соответствие строка таблицы. На пересечении столбца x_l и строки, соответствующей какому-либо  терму, записывается 1 или 0, если данная переменная входит в соответствующий терм  без инверсии или с инверсией, или как *, если данная переменная не входит в данный терм. В правой части таблицы на каждой вертикали указываются все термы, которые входят в ДНФ, означающую выход y_g. Программирование матриц для системы функций, реализованной ПЛМ, изображенной на Рис.2, приведено в Табл.3.

Таблица 34 Пример программирования ПЛМ

x1	x2	x3	x4	y1	y2	y3
0	1	*	*	1	1	.
1	0	*	0	1	.	1
1	*	1	1	1	.	1
0	*	0	1	.	1	.
0	0	1	*	.	1	1
*	1	*	0	.	1	.
1	*	0	*	.	.	1

Матричная реализация МПА

Матричная реализация МПА

Проиллюстрируем матричную реализацию МПА на примере синтеза автомата, заданного Табл.1. МПА  может быть реализован тривиальным образом в виде структуры, изображенной на Рис. 3. Здесь матрица М_Е формирует термы E₁, ... , E_H,  соответствующие строкам структурной таблицы МПА, а матрица M_yD  реализует микрооперации и функции возбуждения элементов памяти как дизъюнкции от термов из набора E₁, ... , E_H.

Схема тривиальной матричной реализации МПА, заданного Табл.1, приведена  на Рис.3.  Здесь предполагается, что  для построения матриц использованы биполярные элементы. Поэтому реализация осуществляется в базисе {&, Ú, `   }.

Достоинства такой матричной реализации очевидны. Прежде всего - это простота проектирования автомата, которое по существу сводится к отображению структурной  таблицы на матрицы М_Е и M_yD.

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

S(M) = S(M_E = S(M_yD) = (2L + 2R)H + (N + R) H [бит].

Рисунок 10 Матричная реализации МПА Мили

 

Недостаток тривиальной реализации заключается в значительной избыточности матриц M_E  и M_yD. Замена входных переменных и соответствующее кодирование состояний способствуют оптимизации схемы.

Структурная схема МПА с заменой  переменных представлена на Рис.10. Здесь матрицы M_z и М_р реализуют новые переменные, матрица M_F - термы ДНФ, определяющих новые переменные, а матрица  M_yD -  та же, что и на Рис.9.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Из сравнения Рис. 3 и 4 видно, что  матрица M_E   заменена матрицами M_Z, M_P, M_F. Выигрыш от замены входных переменных будет в том случае, если информационная емкость матрицы М_Е превышает суммарную информационную емкость матриц M_Z, M_P и M_F.  В реальных МПА средней сложности с параметрами: L=S=50, H=200, R=6, G=5  сложность S(M_E)=14400 бит, что более чем в два раза превышает S(M_Z)+S(M_P)+S(M_F)=5810 бит. Поэтому важно так заменить переменные и закодировать состояния автомата, чтобы минимизировать площадь матриц М_z и M_p. Последнее будет выполнено в случае  минимального числа S термов  в выражениях для новых входных переменных.

 

¹ МОП - металл -окисел-полупроводник. Действие МОП - элементов в отличие от биполярных основано на переносе только основных носителей заряда.

¹ Савельев А.Я. Прикладная теория цифровых автоматов. М.: «Высшая школа», 1987

² Самофалов К.Г. и др. Прикладная теория цифровых автоматов. Киев: «Вища школа», 1987. – 375 с.

³  Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962..