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

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

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

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

 

 

 

Рисунок 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 [бит].

 

Недостаток тривиальной реализации заключается в значительной избыточности матриц 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 термов в выражениях для новых входных переменных.

 

 

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

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

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

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

 

⇐ Предыдущая78910111213141516

Поделиться: