Модели логических элементов

Модели логических элементов в двоичном алфавите

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

Таблицы истинности

Сначала рассмотрим модели логических элементов в двоичном алфавите. Простейшей моделью логического элемента комбинационного базиса в двоичном алфавите является табличная модель, реализующая его таблицу истинности, рассмотренная в лекции 2. Пусть значения булевой функции хранятся в одномерном битовом массиве $$V[i]$$. При вычислении значения выхода с помощью таблицы истинности необходимо выполнить следующие действия:

сформировать из двоичных значений входов одно двоичное слово;

перевести это двоичное слово в целое число – $$i$$;

определить значение выхода $$z=y[i]$$.

Рассмотрим для примера таблицу истинности вентиля $$И$$ с тремя входами, представленную в табл.4.1.

При этом в памяти компьютера хранятся только значения функции (столбец $$Y$$ для нашего примера). Вычисление значения выхода элемента по данным значениям входов сводится к получению индекса и выборке с его помощью нужного значения. Пусть для определенности в нашем примере входные значения $$x_1=1,x_2=0,x_3=1$$ дают индекс $$i=101_2=5_{10}$$ массива $$Y$$; таким образом, получаем $$Y[5]=0$$. Несмотря на свою простоту, это очень эффективный и быстрый метод вычисления. Но, очевидно, при увеличении числа входов он требует больших затрат памяти.

a	b	c	Y
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

Таблицы zoom

При использовании таблиц истинности в моделировании необходимо сначала определить тип соответствующего логического элемента. Поэтому определение типа элемента и собственно вычисление выходного значения выполняются в два этапа. Эти два шага можно объединить в один следующим образом. Пусть $$t$$ является номером типа элемента и $$S$$ - максимальный размер таблицы истинности (для всех типов). Тогда можно построить таблицу zoom размера $$t \times S$$, в которой хранятся $$t$$ таблиц истинности, которые начинаются с позиции $$0, S,…, (t-1)S$$. Для вычисления значения выхода элемента с использованием такой таблицы необходимо упаковать тип элемента и значения его входов в одно слово, которое определяет индекс в таблице zoom, как это показано на рис.4.1.

Применение zoom таблиц позволяет значительно ускорить процесс вычислений, поскольку заменяет последовательность вычислений одним шагом выборки необходимого значения.

Программные функциональные модели

Очень распространенным методом построения моделей является составление программы с помощью логических операторов языка высокого уровня (например, C) или ассемблера непосредственно по логическому выражению булевой функции или логической схеме, построенному с помощью операций конъюнкции, дизъюнкции и отрицания (иногда и $$\oplus$$).

(рис 4.1) Zoom таблица

В отличие от предыдущих табличных методов, в которых модель элемента представлена фактически структурой данных, а сама программа вычисления значения выхода является универсальной, здесь модель элемента представляется непосредственно программой (и она уникальна для каждого типа элемента). Часто программная модель компилируется на основе структурной модели автоматически. Рассмотрим этот метод на примере схемы, представленной на рис.4.2.

С использованием языка программирования С эта схема моделируется следующим образом:

$$ E=A\B;\\ F=!(C\D);\\ Y=E\mid\mid F; $$ (рис 4.2) Пример схемы

Эта программа компилируется в машинный код и далее используется при моделировании путем вызова соответствующей функции.

С применением ассемблера модель этой схемы (представляющей логический элемент) имеет следующий вид.

$$ \text{LDA A /* загрузка сумматора А */}\\ \text{AND B /* вычисление A\B*/}\\ \text{STA E /* запоминание E*/}\\ \text{LDA C /* загрузка сумматора C */}\\ \text{AND D /* вычисление C\D*/}\\ \text{INV /* инвертирование C\D */}\\ \text{OR E /* вычисление }E\vee \overline{C\D}*/\\ \text{STA Y /* запоминание выхода Y */} $$

Алгоритмические функциональные модели

При этом подходе функционирование элемента задается с помощью некоторого алгоритма. Например, для вентиля $$И$$ $$y=x_1 \ x_2 \ x_3$$ это можно сделать следующим образом:

$$ \text{если x1= 0, то y = 0;}\\ \text{если x2= 0, то y = 0;}\\ \text{если x3= 0, то y = 0;}\\ \text{иначе y = 1.} $$

Этот метод широко используется на функциональном уровне ЯРП поскольку позволяет, например, описать систему команд микропроцессора.

При построении моделей логических элементов применяются также альтернативные графы (двоичные диаграммы) и т.п.

Модели логических элементов в многозначных алфавитах

При построении многозначных моделей элементов используются те же подходы, что и в случае двоичного алфавита. Рассмотрим сначала моделирование логических элементов в троичном алфавите $$E_3$$. Для примера возьмем 2-входовой вентиль $$И$$ $$y=x_1\x_2$$. Входы и выход этого элемента принимают значения из троичного алфавита $$E_3=\lbrace0,1,u \rbrace$$. Пусть входы имеют значения $$x_1=0,x_2=u$$. Чему равно значение выхода $$y$$ в алфавите $$E_3$$? Поскольку символ $$u$$ представляет два значения $$u=\lbrace 0 \cup 1 \rbrace$$ (это $$0$$ или $$1$$, но неизвестно, что именно), то моделирование на одном троичном наборе можно выполнить путем моделирования на двух двоичных наборах, покрываемых троичным, и затем сравнить результаты. Для нашего примера имеем:

значения первого двоичного набора $$x_1=0,x_2=0$$ (покрываемом троичным) дают $$y=0$$;

значения второго двоичного набора $$x_1=0,x_2=1$$ также дают $$y=0$$.

Поскольку значения выхода y для двух двоичных наборов совпадают, то полагаем $$y=0$$ (где $$0$$ – символ троичного алфавита). Для другого входного троичного набора $$x_1=1,x_2=u$$ аналогично получаем:

значения первого двоичного набора $$x_1=1,x_2=0$$ дают $$y=0$$;

значения второго двоичного набора $$x_1=1,x_2=1$$ дают $$y=1$$.

Поскольку значения y различны для двоичных наборов, покрываемых данным троичным, полагаем значение выхода $$y=u$$. Исходя из подобных соображений и физического смысла, можно построить табличные модели логических элементов в 3- и 5-значном алфавитах.

Табличные многозначные модели

В таблица 4.2, таблица 4.3, таблица 4.4 представлены 5-значные модели стандартных 2-входовых вентилей соответственно $$И, ИЛИ\ и\ НЕ$$.

И	0	1	u	E	H
0	0	0	0	0	0
1	0	1	u	E	H
u	0	u	u	u	u
E	0	E	u	E	u
H	0	H	u	u	H

ИЛИ	0	1	u	E	H
0	0	1	u	E	H
1	1	1	1	1	1
u	u	1	u	u	u
E	E	1	u	E	u
H	H	1	u	u	H

НЕ
0	1
1	0
u	u
E	Н
H	Е

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

И	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	2	2	2
3	0	3	2	3	2
4	0	4	2	2	4

$$f^*$$	$$f^0$$	$$f^1$$
$$A^*B^*$$	$$A^0 \lor B^0$$	$$A^1B^1$$
$$A^* \lor B^*$$	$$A^0B^0$$	$$A^1 \lor B^1$$
$$\overline{A^*}$$	$$A^1$$	$$A^0$$

$$x^*$$	$$x^*$$	$$x^*$$
0	1	0
1	0	1
u	1	1

При этом вычисление значение выхода в многозначном алфавите по заданным значениям входов сводится к выборке нужного элемента в двумерном массиве, так как значения входов определяют индексы этого массива. Пусть, например, для вентиля $$И$$ модель описана в виде двумерного массива $$TAND[0:4, 0:4]$$. При входных значениях $$x_1=1$$ (соответствует символу $$1E_3$$) и $$x_2=2$$ (соответствует символу $$u$$) получаем $$y=TAND[1,2]=2$$, что соответствует неопределенному значению $$u$$. Ясно, что с ростом числа переменных резко возрастает объем требуемой памяти и метод становится практически непригодным. Следует отметить, что эвристический подход к построению моделей логических элементов в многозначных алфавитах и табличная форма задания модели, сдерживают дальнейшую разработку многозначных моделей для сложных ДУ, реализованных на СБИС. В третьем разделе рассмотрены более подробно вопросы построения многозначных моделей, как на вентильном, так и на функциональном уровне.

Компонентные многозначные модели

Данный способ построения многозначных моделей элементов основан на кодировании многозначных алфавитов и является обобщением метода построения моделей, изложенных для двоичного алфавита. Рассмотрим сначала троичные компонентные модели. Так как каждая троичная переменная $$x^*$$ принимает три значения $${0,1,u}$$,то она может быть представлена двумя булевыми переменными, принимающими двоичные значения. Для этого используются различные способы кодирования троичного алфавита . Мы, в основном, будем использовать дизъюнктивный метод кодирования троичного алфавита, представленный табл.4.7.

Здесь переменные $$x^0,x^1$$ могут принимать только двоичные значения. В современных системах моделирования, как правило, компоненты хранятся в разных машинных словах. Очевидно, что при таком подходе для моделирования логического элемента с троичной функцией $$f^*$$ необходимо две булевых функции $$f^0$$ и $$f^1$$. В табл.4.6 представлены троичные компонентные модели основных вентилей для дизъюнктивного метода кодирования.

Известен простой способ построения функций $$f^0$$ и $$f^1$$ для произвольной булевой функции. Если $$f$$ задана дизъюнктивной нормальной формой (ДНФ), то компонента $$f^1$$ получается из ДНФ функции $$f$$ заменой вхождений переменных $$x_i$$ на $$x_i^1$$ и $$\bar{x_i}$$ на $$x_i^0$$. Аналогично компонента $$f^0$$ получается из ДНФ отрицания функции $$\bar f$$. Например, для функции $$f=a\overline b \lor bc \lor \overline c \overline b$$ и $$\overline f=с\overline b \lor a\overline b\overline c$$ имеем $$f^1=a^1b^0\lor b^{1c1} \lor b^0c^0$$ и $$f^0=c^1b^0\lor a^1b^0c^0$$.

Метод сканирования входов

C	x	x	$$c\oplus i$$
X	c	x	$$c\oplus i$$
X	x	c	$$c\oplus i$$
$$\overline c$$	$$\overline c$$	$$\overline c$$	$$\overline c\oplus i$$

	C	I
И	0	0
ИЛИ	1	0
НЕ-И	0	1
НЕ-ИЛИ	1	1

В большинстве программ моделирования в качестве базовых (элементарных) логических элементов используются простейшие вентили $$И, ИЛИ, НЕ, НЕ-И, НЕ-ИЛИ$$. Они характеризуются, прежде всего, двумя параметрами: контролирующее значение $$c$$ и инверсия $$i$$. Значение входа называется контролирующим, если оно определяет выход вентиля, равный $$y=c\oplus i$$, независимо от значений остальных входов. таблица 4.9 и таблица 4.8представляют соответственно простые кубы и значения параметров для любых стандартных 3-входовых вентилей. В табл.4.9 в каждой строке представлен простой куб вентиля в порядке, указанном в табл.4.8.

Ниже представлен псевдокод типичной программы вычисления значения выхода, реализующей данный метод .

$$ \text{Вычисление (G,c,i)}\\ \{\\ \text{\quad u\_values=FALSE;}\\ \text{\quad for каждого входа v вентиля G}\\ \text{\quad \{}\\ \text{\qquad if v=c then return } c\oplus i;\\ \text{\qquad if v=u then u\_values=TRUE;}\\ \text{\quad \}}\\ \text{\quad if u\_values then return u;}\\ \text{\quad return }\overline c\oplus i;\\ \} $$

Метод счетчиков

Анализ программы показывает, что для вычисления значения выхода стандартного вентиля в троичном алфавите достаточно знать: имеет ли какой либо вход контролирующее значение $$c$$ и при его отсутствии наличие неопределенного значения $$u$$ на входах. Поэтому был предложен метод , в котором вместо хранения значений входов для каждого вентиля сохраняются значения двух счетчиков – $$c\_count$$ и $$u\_count$$, где содержится число входов с контролирующим и неопределенным значением соответственно. При очередном вызове функции модели вентиля значение этих счетчиков может изменяться. Например, при изменении $$1 \to 0$$ входа вентиля $$И$$ счетчик $$0_\count$$ увеличивается на $$1$$, в то время как при изменении $$0 \to u$$ увеличивается на $$1$$ счетчик $$u\_count$$. Тогда вычисление значения выхода вентиля сводится к проверке счетчиков. Ниже представлен метод вычисления значения выхода.

$$ \text{Вычисление (G,c,i)}\\ \{\\ \text{\quad If c\_count > 0 then return }c\oplus i;\\ \text{\quad If u\_count > 0 then return u;}\\ \text{\quad return }\overline c\oplus i;\\ \} $$

Более подробно вопросы построения многозначных моделей логических элементов будут изложены в лекции 7 , где рассматривается единая система многозначных алфавитов и функций.

Модели задержек логических элементов

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

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

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

(рис 4.3) Модель транспортной задержки

Модель, в которой времена задержек всех логических элементов считаются одинаковыми, носит название модели с единой (или единичной) задержкой. Благодаря тому, что элементам присвоены задержки, появляется возможность обрабатывать асинхронные схемы с обратными связями и проводить хотя бы приближенный анализ временных соотношений в схеме. В общем случае, однако, следует учитывать то, что различные типы логических элементов обладают разными задержками. Поэтому более адекватной является модель с номинальными задержками, при которой каждому логическому элементу присваивается свое целочисленное значение задержки, измеряемое в единицах модельного времени. Для того чтобы осуществить соответствующее этому случаю моделирование, в качестве базовой единицы модельного времени обычно используют наибольший общий делитель времен задержек $$\Delta_T$$ элементов и присваивают значения задержек в соответствии с их кратностью.

(рис 4.4) Пример схемы

Пример. Пусть для схемы, показанной на рис. 4.4 , выполняется моделирование с использованием модели с единичной задержкой. На рис.4.5а) представлены результаты логического моделирования с использованием модели единичных задержек в виде временных диаграмм сигналов на линиях схемы. На рис.4.5б) показаны временные диаграммы для той же схемы, но с использованием модели номинальных задержек, где время задержки элементов $$В, D\ и\ Е$$ составляет $$2$$ единицы, а для остальных элементов – $$1$$ (здесь одно деление соответствует единице модельного времени).

В ряде случаев используют для одного и того же элемента различные значения задержек для переднего и заднего фронтов сигнала. Например, в схемах на МОП-структурах время задержки спада сигнала $$\Delta_F$$ может в 3 раза превышать время задержки переднего фронта $$\Delta_R$$. Следовательно, в данном случае при моделировании длительность (положительного) импульса может увеличиваться (как это имеет место на рис.4.5а). ($$\Delta_T=2$$ для элементов $$В, D\ и\ Е$$ и $$\Delta_T=1$$ для элементов $$А, С\ и\ D$$)

(рис 4.5) Примеры моделирования: а) единичные задержки; б)номинальные задержки

Соответственно большее значение задержки нарастания фронта по сравнению с задним фронтом может привести к уменьшению длительности импульса (рис.4.6б). Вместе с тем, при некоторых соотношениях времен задержек переднего фронта и спада возможны случаи, когда моделирование показывает невозможные с практической точки зрения события (рис.4.6в), когда задний фронт "обгоняет" передний. Для исключения подобных ситуаций в процессе моделирования следует предусматривать специальные меры.

(рис 4.6) Различные задержки нарастания фронта и спада

а) $$\Delta_R=1, \Delta_F=3$$; б) $$\Delta_R=2, \Delta_F=1$$; в) $$\Delta_R=3, \Delta_F=1$$.

Определить точное значение задержки для данного типа логического элемента довольно трудно так как всегда существует разброс значений (в силу технологических причин, влияния внешней среды и т.п. ). Поэтому иногда для повышения точности моделирования указывают некоторый диапазон ожидаемых задержек. Такую модель называют моделью с неопределенной задержкой. Модель, в которой в качестве концов диапазона указывают максимальное время задержки $$\Delta_M$$ и минимальное время задержки $$\Delta_m$$, носит название модели с максимальной и минимальной задержками.

В качестве примера рассмотрим распространение сигнала через элемент $$И$$. Как показано на рис.4.7 , выходное значение изменяется от $$0$$ к $$1$$ при изменении входного сигнала от $$0$$ к $$1$$. Однако, поскольку в течение времени $$\Delta_m$$ изменения не происходит, а после $$\Delta_M$$ устанавливается $$1$$, то в диапазоне от $$\Delta_m$$ до $$\Delta_M$$ присваивается неопределенное значение $$u$$. Аналогично при моделировании заднего фронта также присваивается неопределенное значение $$u$$, как показано на рис.4.7.

(рис 4.7) Образование неопределенного значения сигнала

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

В заключение рассмотрим модель инерционной задержки $$\Delta_I$$. В понятие инерционной задержки элемента вкладывают следующий смысл. Если на вход элемента подается входной импульс продолжительностью меньше инерционной задержки $$\Delta_I$$, то элемент не пропускает его (выходной сигнал не изменяется). Введение такой задержки позволяет моделировать ситуации в реальных схемах, когда элементы не успевают срабатывать на коротких импульсах вследствие своей инерционности (например, вследствие наличия емкости). Если, например, $$\Delta_I=2$$, то, как показано на рис. 4.8 , при ширине импульса $$1$$ (и менее) нельзя получить изменение сигнала на выходе элемента.

(рис 4.8) Инерционная задержка

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

логическая верификация с использованием только модели с единичными задержками;

моделирование с учетом различных задержек для подъема и спада сигналов;

моделирование с использованием модели с неопределенной задержкой;

моделирование с использованием статистических методов вычисления задержки.

Ключевые термины:

Двоичный алфавит – минимально возможный алфавит моделирования логического моделирования, содержащий два символа $${0,1}$$, обычно соответствующие низкому и высокому уровню сигнала.

Многозначный алфавит – содержит большее число символов, отражающих различные физические сигналы, например, символы пятизначного алфавита $${0,1,E,H,u}$$ соответствуют низкому и высокому уровням, переднему и заднему фронтам, неопределенности.

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

Инерционная задержка – не пропускает короткие импулься с длиной менее заданного порога.

Краткие итоги

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

В разделе 4.1 описаны модели логических элементов в традиционном двоичном алфавите , которые включают: 1) таблицы истинности; 2) zoom-таблицы; 3) программные функциональные модели; 4) алгоритмические функциональные модели.

Раздел 4.2 посвящен методам моделирования элементов в многозначных алфавитах , которые включают:

табличные модели;

компонентные модели;

метод счетчиков;

метод сканирования входов.

В разделе 4.3 изложены типовые модели задержек логических элементов, к которым относятся:

единичная задержка;

номинальная задержка;

различные задержки дл переднего и заднего фронтов;

модель мини-максных задержек;

инерционная задержка.

Вопросы и упражнения

Как может быть использована таблица истинности при моделировании логического элемента.

Чем отличается zoom-таблица от таблицы истинности?

Постройте zoom-таблицу для вентилей $$И, ИЛИ, НЕИ, НЕИЛИ$$.

Как строится программная функциональная модель элемента?

Постройте алгоритмическую функциональную модель для элемента $$ИЛИ$$ $$y=x_1\lor x_2 \lor x_3$$.

Чем отличаются многозначные модели логических элементов от двоичных?

Постройте табличную модель в 5-значном алфавите для элемента $$y=\overline x_1 x_2$$.

Как многозначная модель двухвходового вентиля $$И$$ может быть использована для многозначной модели такого вентиля на 4 входа?

Опишите компонентную троичную модель для элемента$$y=\overline x_1\lor x_2$$.

Опишите метод сканирования входов.

Что такое метод счетчиков?

Напишите программные модели вентиля $$Исключающее\ ИЛИ$$ на основе методов: а) сканирования входов, б) счетчика.

Приведите модель транспортной задержки.

Что такое модель единичной задержки?

Выполните вручную логическое моделирование для представленной ниже схемы

на приведенных входных воздействиях.

со следующими задержками обоих элементов:

Транспортная с $$d=2$$;

Инерциальная с $$d_I=2$$;

Инерциальная с $$d_I=1$$;

С разными значениями для переднего и заднего фронтов с $$d_r=3; d_f=1$$;

С разными значениями для переднего и заднего фронтов с $$d_r=1; d_f=3$$;

Минимаксная $$d_m=1; d_M=2$$.

Опишите модель с неопределенной задержкой.

Что такое инерционная задержка.