Данный раздел содержит различные формы представления моделей, которые используются при моделировании и тестировании ЦУ. Прежде всего, мы рассмотрим вопросы моделирования на уровне логических элементов или логическом моделировании ЦУ. При этом, как правило, элементы, составляющие ЦУ, описываются с помощью логических уравнений (булевых функций), которые отражают логику их функционирования. Кроме этого исследуются функциональные модели ЦУ на уровне регистровых передач.
Объектом наших исследований являются ДУ, которые делятся на два класса , : комбинационные и последовательностные устройства. ЦУ называется комбинационным, или ЦУ без памяти, если значения его выходных сигналов однозначно определяются только значениями входных сигналов. Последовательностным, или ЦУ с памятью, называется устройство, у которого значения выходных сигналов в данный момент времени зависят от значений входных сигналов в текущий момент и от внутреннего состояния объекта в предыдущий момент времени, определяемого значениями сигналов на линиях обратных связей. При построении моделей ЦУ мы рассмотрим три подхода: функциональный, структурный и представление ДУ языками описания аппаратуры (hardware design languages - HDL).
Функциональные модели
Суть функционального подхода заключается в абстрагировании от внутренней организации устройства и рассмотрении только его логики функционирования. Как правило, под ЦУ подразумеваются устройства, перерабатывающие двоичную информацию.
Модели комбинационных схем
В качестве функциональной модели комбинационных устройств, чаще всего, используют систему булевых функций:
$$z_1=f_1(x_1,…,x_n) \\…\\ z_m=f_1(x_1,…,x_n)$$
где $$X=(x_1,…,x_n)$$ - входные, $$ Z=f_1(z_1,…,z_m)$$ - выходные переменные, принимающие двоичные значения $$B_2=\{0,1\}$$. Данная система булевых функций описывает комбинационное ДУ, которое имеет $$n$$ входов, $$m$$ выходов и представлено на рис. 2.1 .
(рис 2.1) Комбинационное ДУ
Здесь каждая булева функция $$f_i(x_i,…,x_n)$$ - отображение $$B_2^n\to B_2$$. Простейшим способом представления булевой функции является таблица истинности. Например, в табл.2.1 приведена таблица истинности для булевой функции трех переменных.
Кроме этих таблиц часто используются также табличные модели в виде так называемых "примитивных" (простых) кубов. Эти кубы в сжатом виде фактически представляют ту же самую информацию. Один "примитивный" куб объединяет несколько "соседних" строк таблицы истинности, на которых булева функция принимает одно и тоже значение. Под "соседними" здесь понимаются строки, отличающиеся значением одного (или более) бита. В отличие от таблиц истинности такие кубы используют не двоичный алфавит $$B_2=\{0,1\}$$, а троичный алфавит $$E_3=\{0,1,x\}$$, где символ $$х$$ представляет неопределенное значение ($$0$$ или $$1$$) переменной. В таблица 2.2).
В .
| X1 | X2 | X3 | F |
|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
| X1 | X2 | X3 | F |
|---|
| X | 1 | 0 | 0 |
| 1 | 1 | X | 0 |
| X | 0 | X | 1 |
| 0 | X | 1 | 1 |
Модели последовательностных схем
В качестве функциональной модели последовательностных устройств используется абстрактный конечный автомат , являющийся совокупностью пяти объектов $$A=(Y,X,Z,\delta,\lambda)$$, где $$Y, X, Z$$ – конечные множества состояний, входных и выходных сигналов соответственно; $$\delta: Y \times X \to Y$$ - функция переходов, определяющая следующее состояние автомата; $$\lambda: Y \times X \to Z$$ - функция выхода, определяющая выходной сигнал.
Различают два типа автомата:
автомат Мили
$$Y(t+1)= \delta (Y(t),X(t))\\ Z(t+1)= \lambda (Y(t),X(t))$$
и автомат Мура
$$Y(t+1)= \delta (Y(t),X(t))\\ Z(t+1)= \lambda (Y(t))$$
Например, таблица 2.3представляет конечный автомат Мили с одним входом – $$х$$, одним выходом – $$z$$ и четырьмя состояниями. Здесь на пересечении строки (текущего состояния) и столбца (входного сигнала) приводятся следующее состояние и выходной сигнал автомата.
Кроме приведенной табличной формы автомат также часто представляется графом переходов и выходов. Для примера на рис.2.2 показан граф переходов–выходов автомата, представленного табл.2.3 .
(рис 2.2) Граф переходов – выходов автомата табл.2.3
| S | X |
|---|
| 0 | 1 |
| 1 | 2,1 | 3,0 |
| 2 | 2,1 | 4,0 |
| 3 | 1,0 | 4,0 |
| 4 | 3,1 | 2,0 |
Следует отметить, что в этой форме представления неявно предполагается, что функционирование автомата рассматривается в дискретном времени, принимающем целые неотрицательные значения $$t=0,1,2...$$ Такие автоматы называются синхронными.
Синхронное последовательностное ДУ имеет каноническую форму представления, приведенную на рис.2.3 . Эта автоматная модель позволяет представить последовательностное устройство в виде комбинационного блока и блока памяти, которые соединены линиями обратной связи $$ Y=(y_1,...,y_k)$$.
Здесь каждое состояние в таблице автомата соответствует комбинации переменных состояния - $$y$$. Синхронизация неявно реализуется в виде дополнительного входа – $$clock$$. Таким образом события (изменение состояния и выходного сигнала ) инициируются импульсами на входе синхронизации. Состояние схемы запоминается в синхронизируемых триггерах (flip-flop - FF) и изменяется при поступлении импульсов на соответствующий вход. На рис.2.4 представлены три используемые на практике типа синхронизируемых триггеров: JK-триггер, Т-триггер и D-триггер (задержка). В общем случае синхронные ДУ могут иметь несколько входов синхронизации.
(рис 2.3) Модель схемы с памятью
Асинхронные последовательностные схемы не имеют входов синхронизации. Их поведение может быть также представлено таблицей переходов и выходов.
Но, в отличие от предыдущего случая, здесь изменение входного сигнала может вызвать цепочку переходов состояний, пока не будет достигнуто стабильное состояние.
(рис 2.4) Основные типы триггеров
Следует отметить, что далеко не все состояния схемы являются стабильными. Например, таблица 2.4представляет асинхронный автомат, в котором стабильные состояния здесь выделены жирным шрифтом.
| x1x2 | | | |
|---|
| 00 | 01 | 11 | 10 |
| 1 | 1,0 | 5,1 | 2,0 | 1,0 |
| 2 | 1,0 | 2,0 | 2,0 | 5,1 |
| 3 | 3,1 | 2,0 | 4,0 | 3,0 |
| 4 | 3,1 | 5,1 | 4,0 | 4,0 |
| 5 | 3,1 | 5,1 | 4,0 | 5,1 |
Для асинхронных последовательных ДУ также часто используется каноническая форма, представленная на рис.c5 (модель Хафмена).
(рис 2.5) Модель Хафмена
Альтернативные графы (бинарные диаграммы решений)
Бинарные диаграммы решений являются ациклическими ориентированными графами, представляющими булевы функции. Этот тип модели был предложен в и в настоящее время широко используется при моделировании и генерации тестов ЦУ. Множество его вершин можно разбить на три подмножества: внутренние узлы (степень входа равна $$1$$, степень исхода равна $$2$$ ), листья (степень входа равна $$2$$, степень исхода равна $$0$$) и корень (степень входа равна $$0$$, степень исхода равна $$2$$). Логические значения $$0$$ или $$1$$, принимаемые булевой функцией, соответствуют листьям диаграммы. Внутренние вершины соответствуют переменным булевой функции. Путь на графе из корневой вершины до одного листа, в зависимости от значений переменных булевой функции, определяет ее значение. Например, на рис.2.6 представлена бинарная диаграмма решений для булевой функции $$f=\overline ab\overline c+ac$$.
(рис 2.6) Бинарная диаграмма решений
Для определения значения булевой функции начинаем двигаться из корневой вершины вниз к листьям дерева. При прохождении каждой внутренней вершины, необходимо решить – по какой ветви (левой или правой), в зависимости от значения переменной, соответствующей текущей вершине, мы должны идти дальше. Значение булевой функции ($$\text{0 или 1}$$) определяется последней вершиной такого пути - висячей вершиной (листом дерева). Допустим, что нам необходимо вычислить значение данной булевой функции c помощью бинарной диаграммы (рис 2.6) при следующих значения переменных: $$a=0, b=0, c=1$$. Начиная с корневой вершины, при прохождении вершины $$a$$ выбираем левую ветвь (так как $$a=0$$), далее в вершине $$b$$ также выбираем левую ветвь и попадаем в лист дерева, соответствующий $$0$$ (в данном случае функция не зависит от значения переменной $$с$$). Следует отметить, что иногда листья дерева могут соответствовать не только константам $$0,1$$, но и переменным. Так для нашего примера листом является вершина $$с$$, поскольку при $$a=1$$ значение функции определяется этой переменной ($$f=c$$). Точка соответствует инверсии конечного результата. Например, при $$a=0, b=1$$ для нашего примера получаем $$f= \overline c$$. Если при прохождении по графу встречается несколько инверсий (точек), то конечный результат инвертируется в случае их нечетного числа.
Рассмотрим построение бинарной диаграммы из таблицы истинности на примере булевой функции, заданной . Сначала строится полное двоичное дерево, представленное на рис. 2.7 а), где каждый путь от корня до листа соответствует одной строке таблицы истинности. Далее эта диаграмма упрощается следующим образом. Так как обе ветви из левого узла с помечены $$0$$, то этот узел можно удалить и заменить его листом, помеченным $$0$$. Дальнейший анализ показывает, что остальные узлы $$c$$ имеют ветви, помеченные $$1$$ или $$0$$ ($$0$$ или $$1$$), и их также можно также удалить и заменить на листья, помеченные $$c$$ или $$\overline c$$. Дальнейшие упрощения показаны на рис.2.7 б)-в).
| a | b | C | F |
|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
(рис 2.7) Бинарные диаграммы
Структурные модели
Информация о логике функционирования ДУ, которую дают описанные выше функциональные модели , является недостаточной для решения проблем генерации тестов и моделирования. При разработке алгоритмов генерации тестов и моделирования чаще используется структурная модель цифрового устройства, отражающая, кроме логики функционирования ДУ, связи между его компонентами и внешней средой. В качестве структурной модели ДУ, как правило, используется правильная логическая сеть. Логическая сеть или схема - это ориентированный граф, вершинами которого являются логические элементы, входы, выходы и узлы разветвления. Направленные дуги графа отображают соединения сети. Правильная логическая сеть - это сеть, у которой выходы никаких двух элементов не соединены вместе и каждая из функций, реализуемых на выходах ДУ, может быть представлена как функция выхода конечного автомата. Основу сети составляют логические элементы двух типов:
элементы, функционирование которых описывается булевыми функциями;
элементы памяти, функционирование которых описывается моделью конечного автомата.
Внешнее описание схемы
Структурная модель ДУ может быть представлена, например, с помощью простого специализированного языка описания схемы международного каталога ISCAS-89 [6], который позволяет описывать ее входы и выходы, компоненты и связи между ними.
На рис.2.8 представлена логическая схем s27 из каталога ISCAS-89 , описание которой на этом языке приведено на рис.2.9 (сравнив эти рисунки легко освоить данный язык для текстового ввода). Из рис. 2.8 видно, что описание схемы начинается с комментариев (в первой позиции стоит символ $$‘#‘$$), содержащих сведения о схеме: число внешних входов, число внешних выходов и D-триггеров, число вентилей по типам. Далее следуют строки описания для каждого элемента схемы, включая внешние входы и выходы. Каждая строка описания содержит:
имя элемента (для внешних входов $$INPUT$$, а для внешних выходов $$OUTPUT$$);
знак равенства $$"="$$ для логических вентилей;
тип вентиля для логических вентилей;
перечисленные в скобках имена вентилей-предшественников данного элемента, которые позволяют сразу определить количество входов данного вентиля.
(рис 2.8) Графическое описание схемы S27.
Допускаются следующие типы вентилей:
$$DFF$$ – D-триггер, описание триггеров должно идти непосредственно за описанием внешних входов и выходов схемы;
$$AND$$ - вентиль И;
$$NAND$$ - вентиль НЕ-И;
$$OR$$ - вентиль ИЛИ;
$$NOR$$ - вентиль НЕ-ИЛИ;
$$XOR$$ - вентиль сумма по mod2;
$$XNOR$$ - вентиль равнозначность;
$$BUFF$$ - буфер (повторитель).
Часто в структурных моделях применяются макроэлементы. При этом элемент описывается в теле макроса, которое используется далее на более высоком уровне. Как правило, допускается несколько уровней вложения, что позволяет использовать иерархический подход к описанию схем.
Кроме связей элементов, в некоторых языках описания может быть представлена информация о временных задержках элементов. Например, это может быть сделано следующим образом:
$$G12 = NOR(G1, G7) delay 20
$$
Это утверждение показывает величину задержки распространения сигнала от входов к выходу данного логического вентиля в некоторых единицах.
Текстовое описание схемы S27
| # 4 inputs | G6 = DFF(G11) |
| # 1 outputs | G7 = DFF(G13) |
| # 3 D-type flipflops | G14 = NOT(G0) |
| # 2 inverters | G17 = NOT(G11) |
| # 8 gates (1 ANDs + 1 NANDs + | G8 = AND(G14, G6) |
| 2 ORs + 4 NORs) | G15 = OR(G12, G8) |
| INPUT(G0) | G16 = OR(G3, G8) |
| INPUT(G1) | G9 = NAND(G16, G15) |
| INPUT(G2) | G10 = NOR(G14, G11) |
| INPUT(G3) | G11 = NOR(G5, G9) |
| OUTPUT(G17) | G12 = NOR(G1, G7) |
| G5 = DFF(G10) | G13 = NOR(G2, G12) |
Свойства структурных моделей
Как было показано выше, структурная модель представляется ориентированным графом, в котором элементы и связи схемы отображаются соответственно в вершины и дуги графа. Внешние входы и выходы схемы при этом отображаются в специальные вершины. Поэтому для исследования свойств структурной модели схемы можно использовать методы теории графов. Например, на рис.2.9 а), б) приведена схема и ее представление ориентированным графом. Отметим, что в данной схеме каждая дуга соединяет только две вершины (сигнал с выхода любого элемента поступает на вход только одного элемента - преемника). Эти схемы не содержат разветвлений (fan out free circuits). Граф такой схемы является деревом.
(рис 2.9) Представление древовидной схемы графом
Схема с разветвлениями представляется двудольным ориентированным графом, который является более общей моделью по сравнению с древовидной структурой. Здесь элементы и связи отображаются в вершины графа таким образом, что каждая дуга соединяет вершину, отображающую элемент схемы, с вершиной, соответствующей связи этого элемента. На . Здесь вершины, соответствующие связям, отмечены знаком $$\bigotimes$$. Такая модель позволяет представлять схемы с элементами, имеющими несколько выходов, и является более общей.
(рис 2.10) Двудольный граф схемы
Следует отметить, что наличие сходящихся разветвлений (reconvergent), как мы увидим дальше в , существенно осложняет построение тестов. На нашем примере рис 2.10имеется сходящееся разветвление, содержащее два пути, которое соединяет вершины $$ERD$$ и $$B1$$. В схемах, состоящих из простейших вентилей $$И, ИЛИ, НЕ-И, НЕ-ИЛИ, НЕ$$, часто используется понятие четности инверсий пути, которое определяется четностью (суммой по $$mod2$$) числа инвертирующих вентилей вдоль данного пути.
Уровень логического элемента в комбинационной схеме определяется как мера расстояния этого элемента от внешних входов. При этом внешним входам присваивается уровень, равный $$0$$. Далее уровень $$l(i)$$ элемента $$i$$, на входы которого поступают сигналы с выходов элементов $$k_1,k_2,…,k_p$$, определяется следующим образом $$l(i)=1+\underset j \max l(k_j)$$
В последовательностной схеме , для вычисления уровней элементов сначала производится условный обрыв линий обратных связей и получившимся псевдовходам присваивается уровень, равный $$0$$. Уровни остальных элементов вычисляются по той же формуле. Для примера на рис.2.11 представлена последовательностная схема , в которой уровень $$1$$ имеют элементы $$E, D, J;$$ уровень $$2$$ – $$F, K$$; уровень $$3$$ – $$G$$; уровень $$4$$ – $$W$$.
(рис 2.11) Ранжированная последовательностная схема
Иногда вместо явного вычисления уровней используется упорядочивание и нумерация элементов в соответствии с их расстоянием от внешних входов. При этом для любых элементов с номерами $$i_1<i_2$$ если $$l(i_1)\leqslant\l(i_2)$$.
Монтажная логика
Логическое моделирование выполняется при предположении, что информация обрабатывается логическими элементами и передается в схеме другим элементам в одном направлении (от входов к выходам в самом элементе, от выходов элемента к входам других элементов в схеме). Но эти предположения не всегда выполняются. Например, достаточно часто при некоторых технологиях используется "монтажная логика". При этом выходы логических элементов соединяются непосредственно и в месте соединения реализуется логическая функция $$И$$ (или $$ИЛИ$$ в зависимости от используемой технологии и мощности соединяемых элементов). Такой элемент называется "проводным (монтажным) $$И (ИЛИ)$$". Для того чтобы подобные ситуации могли обрабатываться в процессе логического моделирования в схему вводится дополнительный фиктивный логический элемент $$И (ИЛИ)$$, как это показано на рис 2.12б), хотя очевидно, что в реальной схеме они принимают одинаковое значение. При корректном моделировании после вычисления значения выхода фиктивного элемента С его надо присвоить также и обоим входам $$A, B$$. На рис 2.12б) это показано пунктирными стрелками. Следует отметить, что введение подобных фиктивных элементов нарушает соответствие между моделью и реальной схемой, что может, например, привести к ошибочной интерпретации результатов моделирования неисправной схемы или построения тестов. Более корректно такие ситуации (и многие другие) моделируются на уровне электрических схем.
(рис 2.12) Моделирование монтажной логики фиктивным элементом
Модели уровня ЯРП
В настоящее время для описания функционирования дискретных устройств широко используются специализированные языки описания цифровой аппаратуры – HDL, которые стали стандартным инструментом при проектировании ДУ . Сейчас вопрос стоит не в том - использовать или не использовать эти языки, а какой именно язык следует использовать при проектировании данного ДУ. Современные языки позволяют описывать ДУ на структурном (вентильном) и функциональном (поведенческом) уровне. В настоящее время они больше используются для описания ДУ на функциональном или уровне регистровых передач. Использование таких языков позволяет существенно сократить срок проектирования и повысить размерность проектируемых ДУ. Следует отметить, что в настоящее время часто срок жизни (эксплуатации) цифровых систем меньше срока его проектирования. В настоящее время наиболее популярными являются языки проектирования SpecC, VHDL (Very high speed integrated circuits HDL) и Verilog HDL.
Рассмотрим основные конструкции этих языков. В них входы, выходы, внутренние состояния и регистры ДУ представляются соответствующими переменными. Как правило, эти переменные должны быть объявлены в начале описания устройства. Например, порты описываются следующим образом:
$$Port(x1,x2:in BIT; -входные\\
y:out BIT); -выходные.
$$
Два регистра могут быть описаны следующим образом:
$$REGISTER R1[1->32], R2[16] ,
$$
где в квадратных скобках указана их разрядность. Аналогичные описания существуют и для других типов устройств (переменных). Так память из 32-разрядных 256 элементов описывается с помощью объявления
$$MEMORY[1->256:32]
$$
Обработка и пересылка может быть описана следующим образом:
$$C\Leftarrow A+B$$
где выполняется сложение содержимого двух регистров $$A$$ и $$B$$ и пересылка результата в регистр $$С$$.
Для описания функционирования ДУ обычно используется следующие группы операторов ЯРП.
Логические операторы: $$AND, OR, NOT, NAND, NOT, XOR, EQUIV$$. Эти операторы обычно выполняются над регистрами или некоторыми их разрядами.
Операторы сравнения: больше (>), меньше (<), больше или равно ($$\ge$$), меньше или равно($$\leqslant$$), равно ($$=$$), не равно ($$!=$$). Эти операторы выполняются над векторами или скалярными переменными. Результатом является логическое значение $$1$$ или $$0$$.
Арифметические операторы: сложение ($$+$$), вычитание ($$-$$), умножение ($$*$$), деление ($$/$$), инкремент, декремент (используются, в основном, для моделирования функционирования счетчиков ).
Битовые операции: правый сдвиг ($$SR$$), левый сдвиг ($$SL$$), циклический правый сдвиг ($$RR$$), циклический левый сдвиг ($$RL$$) и конкатенация (сцепление). Эти операторы выполняются над векторными переменными.
Операция пересылки $$A\Leftarrow B$$ содержимого регистра $$B$$ в регистр $$А$$. Эта операция может быть унарной (выполняется над одним операндом, например, $$A\Leftarrow !B $$), или бинарной (выполняется над двумя операндами, например, $$ A\Leftarrow B+C $$). Единичная задержка неявно ассоциируется с операцией пересылки. Произвольная задержка должна быть указана явно (например, $$ A\Leftarrow B-C\ Delay\ 10$$).
Условные операторы:
бинарный: $$IF\ C\ THEN\ B1\ ELSE\ B2\ IFEND$$;
где $$С$$ является условием, а $$B1$$ и $$B2$$ – блоки, состоящие из операторов.
оператор ветвления типа $$CASE$$:
$$TEST (E0);\\
CASE E0:B0;\\
CASE E1:B1;\\
CASE E2:B2;\\
. . .\\
CASE En:Bn;\\
TESTEND;\\
$$
где $$E$$ являются выражениями и $$B$$ – блоки. Таким образом, может быть описан, например, дешифратор.
Конечные автоматы могут быть описаны двумя способами. При первом (функциональном) подходе языковыми средствами с помощью условных операторов описывается непосредственно таблица переходов и выходов автомата . При втором (структурном) подходе фактически автомат представляется и описывается структурной моделью рис 2.5.
В соответствии с трактовкой понятия времени ЯРП можно разделить на две категории: процедурные и непроцедурные языки. Процедурные ЯРП похожи на обычные языки программирования (такие как Паскаль, С и т.п.), где операторы и утверждения языка выполняются последовательно таким образом, что результат выполненного оператора становится доступным для следующих операторов. Например, при выполнении операторов $$A=B; С=A$$ содержимое переменной (регистра) $$С$$ станет равным содержимому переменной $$B$$. Поэтому некоторые процедурные ЯРП являются расширением обычных языков программирования (например, С, HDL). С другой стороны операторы и утверждения непроцедурных языков выполняются параллельно. В непроцедурных языках выполнение операторов $$A=B; B=A$$ соответствует обмену содержимым регистров $$A$$ и $$B$$. Современные языки описания аппаратуры часто являются смешанными, то есть имеют как процедурные так и не процедурные средства описания и интерпретации.
Ключевые термины:
Комбинационные схемы – схемы из логичесчких элементов, которые реализуют систему булевых функций и, как правило, не имеют обратных связей.
Последовательтностные схемы – схемы из логичесчких элементов, которые реализуют конечный автомат и, как правило, имеют обратные связи.
Функциональный модели – учитывают только логику функционирования ЦУ и не принимают во внимание внутреннюю организацию устройства.
Структурные модели – описывают внутреннюю организацию устройства в виде логических схем.
Бинарная диаграмма (альтернативный граф) – ациклический ориентированный граф, который представляет булевы функции.
Языки регистровых передач – специализированные языки описания цифровых устройств, примером которых являются:VHDL, VERILОG и т.п.
Краткие итоги
В данной лекции вводятся основные модели ЦУ, которые в дальнейшем используются в курсе лекций.
В разделе 2.1 рассматриваются функциональные модели , которые абстрагируются от внутренней организации устройства и учитывают только логику функционирования. Раздел 2.1.1 описывает функциональные модели комбинационных схем в виде системы булевых функций. В разделе 2.1.2 представлены функциональные модели схем с памятью в виде конечных автоматов. Раздел 2.1.3 посвящен функциональным моделям в виде бинарных диаграмм .
В разделе 2.2 описаны структурные модели в виде логических схем. В разделе 2.2.1 приведен пример внешнего описания схемы на простом специализированном языке. Раздел 2.2.2 посвящен свойствам структурных моделей , включая ранжирование элементов схемы.
Раздел 2.3 посвящен моделям уровня языков регистровых передач , где приведены основные типы операторов ЯРП.
Вопросы и упражнения
Чем отличаются комбинационные устройства от последовательностных?
Чем отличаются функциональные модели от структурных ?
Приведите функциональные модели для комбинационных схем .
Чем отличаются таблицы истинности от примитивных кубов?
Могут ли приведенные ниже кубы быть примитивными кубами функции $$f(x_1,x_2,x_3,x_4)$$?
| 0 | x | 1 | x | 0 |
|---|
| x | 1 | 0 | 1 | 0 |
| 1 | x | 1 | 1 | 0 |
| 0 | 1 | 0 | x | 1 |
| x | 0 | 1 | 0 | 1 |
Рассмотрите булеву функцию, определенную примитивными кубами:
$$X 1 0 | 0 , 1 1 x | 0 , x 0 x |1 , 0 1 1 | 1$$. Найдите значение этой функции на следующих входных наборах: $$10u, 01u, u1u, u01$$.
Приведите функциональные модели для схем с памятью.
Что такое автомат Мили и как его можно описать?
Приведите каноническую модель схемы с памятью.
Чем отличается асинхронный автомат от синхронного?
Что такое альтернативные графы (бинарные диаграммы) ?
Постройте альтернативный граф булевой функции из упражнения 5.
Постройте альтернативный граф для функций:
$$f(a,b,c,d,e,g)=ab \lor cd \lor eg \\ f(a,b,c,d)=a \oplus b \oplus c \oplus d$$
Постройте таблицу переходов-выходов синхронного автомата с одним входом и одним выходом, который распознает входную последовательность $$x=1111$$.
Постройте граф переходов-выходов этого автомата
Постройте также схему для распознавания таких перекрывающихся последовательностей и дает на входную последовательность $$x=1100111111101$$ выходную последовательность $$y=0000000111100$$.
Напишите ЯРП модели для D-триггера с передним фронтом переключения.
Данный раздел содержит различные формы представления моделей, которые используются при моделировании и тестировании ЦУ. Прежде всего, мы рассмотрим вопросы моделирования на уровне логических элементов или логическом моделировании ЦУ. При этом, как правило, элементы, составляющие ЦУ, описываются с помощью логических уравнений (булевых функций), которые отражают логику их функционирования. Кроме этого исследуются функциональные модели ЦУ на уровне регистровых передач.
Объектом наших исследований являются ДУ, которые делятся на два класса , : комбинационные и последовательностные устройства. ЦУ называется комбинационным, или ЦУ без памяти, если значения его выходных сигналов однозначно определяются только значениями входных сигналов. Последовательностным, или ЦУ с памятью, называется устройство, у которого значения выходных сигналов в данный момент времени зависят от значений входных сигналов в текущий момент и от внутреннего состояния объекта в предыдущий момент времени, определяемого значениями сигналов на линиях обратных связей. При построении моделей ЦУ мы рассмотрим три подхода: функциональный, структурный и представление ДУ языками описания аппаратуры (hardware design languages - HDL).
Функциональные модели
Суть функционального подхода заключается в абстрагировании от внутренней организации устройства и рассмотрении только его логики функционирования. Как правило, под ЦУ подразумеваются устройства, перерабатывающие двоичную информацию.
Модели комбинационных схем
В качестве функциональной модели комбинационных устройств, чаще всего, используют систему булевых функций:
$$z_1=f_1(x_1,…,x_n) \\…\\ z_m=f_1(x_1,…,x_n)$$
где $$X=(x_1,…,x_n)$$ - входные, $$ Z=f_1(z_1,…,z_m)$$ - выходные переменные, принимающие двоичные значения $$B_2=\{0,1\}$$. Данная система булевых функций описывает комбинационное ДУ, которое имеет $$n$$ входов, $$m$$ выходов и представлено на рис. 2.1 .
(рис 2.1) Комбинационное ДУ
Здесь каждая булева функция $$f_i(x_i,…,x_n)$$ - отображение $$B_2^n\to B_2$$. Простейшим способом представления булевой функции является таблица истинности. Например, в табл.2.1 приведена таблица истинности для булевой функции трех переменных.
Кроме этих таблиц часто используются также табличные модели в виде так называемых "примитивных" (простых) кубов. Эти кубы в сжатом виде фактически представляют ту же самую информацию. Один "примитивный" куб объединяет несколько "соседних" строк таблицы истинности, на которых булева функция принимает одно и тоже значение. Под "соседними" здесь понимаются строки, отличающиеся значением одного (или более) бита. В отличие от таблиц истинности такие кубы используют не двоичный алфавит $$B_2=\{0,1\}$$, а троичный алфавит $$E_3=\{0,1,x\}$$, где символ $$х$$ представляет неопределенное значение ($$0$$ или $$1$$) переменной. В таблица 2.2).
В .
| X1 | X2 | X3 | F |
|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
| X1 | X2 | X3 | F |
|---|
| X | 1 | 0 | 0 |
| 1 | 1 | X | 0 |
| X | 0 | X | 1 |
| 0 | X | 1 | 1 |
Модели последовательностных схем
В качестве функциональной модели последовательностных устройств используется абстрактный конечный автомат , являющийся совокупностью пяти объектов $$A=(Y,X,Z,\delta,\lambda)$$, где $$Y, X, Z$$ – конечные множества состояний, входных и выходных сигналов соответственно; $$\delta: Y \times X \to Y$$ - функция переходов, определяющая следующее состояние автомата; $$\lambda: Y \times X \to Z$$ - функция выхода, определяющая выходной сигнал.
Различают два типа автомата:
автомат Мили
$$Y(t+1)= \delta (Y(t),X(t))\\ Z(t+1)= \lambda (Y(t),X(t))$$
и автомат Мура
$$Y(t+1)= \delta (Y(t),X(t))\\ Z(t+1)= \lambda (Y(t))$$
Например, таблица 2.3представляет конечный автомат Мили с одним входом – $$х$$, одним выходом – $$z$$ и четырьмя состояниями. Здесь на пересечении строки (текущего состояния) и столбца (входного сигнала) приводятся следующее состояние и выходной сигнал автомата.
Кроме приведенной табличной формы автомат также часто представляется графом переходов и выходов. Для примера на рис.2.2 показан граф переходов–выходов автомата, представленного табл.2.3 .
(рис 2.2) Граф переходов – выходов автомата табл.2.3
| S | X |
|---|
| 0 | 1 |
| 1 | 2,1 | 3,0 |
| 2 | 2,1 | 4,0 |
| 3 | 1,0 | 4,0 |
| 4 | 3,1 | 2,0 |
Следует отметить, что в этой форме представления неявно предполагается, что функционирование автомата рассматривается в дискретном времени, принимающем целые неотрицательные значения $$t=0,1,2...$$ Такие автоматы называются синхронными.
Синхронное последовательностное ДУ имеет каноническую форму представления, приведенную на рис.2.3 . Эта автоматная модель позволяет представить последовательностное устройство в виде комбинационного блока и блока памяти, которые соединены линиями обратной связи $$ Y=(y_1,...,y_k)$$.
Здесь каждое состояние в таблице автомата соответствует комбинации переменных состояния - $$y$$. Синхронизация неявно реализуется в виде дополнительного входа – $$clock$$. Таким образом события (изменение состояния и выходного сигнала ) инициируются импульсами на входе синхронизации. Состояние схемы запоминается в синхронизируемых триггерах (flip-flop - FF) и изменяется при поступлении импульсов на соответствующий вход. На рис.2.4 представлены три используемые на практике типа синхронизируемых триггеров: JK-триггер, Т-триггер и D-триггер (задержка). В общем случае синхронные ДУ могут иметь несколько входов синхронизации.
(рис 2.3) Модель схемы с памятью
Асинхронные последовательностные схемы не имеют входов синхронизации. Их поведение может быть также представлено таблицей переходов и выходов.
Но, в отличие от предыдущего случая, здесь изменение входного сигнала может вызвать цепочку переходов состояний, пока не будет достигнуто стабильное состояние.
(рис 2.4) Основные типы триггеров
Следует отметить, что далеко не все состояния схемы являются стабильными. Например, таблица 2.4представляет асинхронный автомат, в котором стабильные состояния здесь выделены жирным шрифтом.
| x1x2 | | | |
|---|
| 00 | 01 | 11 | 10 |
| 1 | 1,0 | 5,1 | 2,0 | 1,0 |
| 2 | 1,0 | 2,0 | 2,0 | 5,1 |
| 3 | 3,1 | 2,0 | 4,0 | 3,0 |
| 4 | 3,1 | 5,1 | 4,0 | 4,0 |
| 5 | 3,1 | 5,1 | 4,0 | 5,1 |
Для асинхронных последовательных ДУ также часто используется каноническая форма, представленная на рис.c5 (модель Хафмена).
(рис 2.5) Модель Хафмена
Альтернативные графы (бинарные диаграммы решений)
Бинарные диаграммы решений являются ациклическими ориентированными графами, представляющими булевы функции. Этот тип модели был предложен в и в настоящее время широко используется при моделировании и генерации тестов ЦУ. Множество его вершин можно разбить на три подмножества: внутренние узлы (степень входа равна $$1$$, степень исхода равна $$2$$ ), листья (степень входа равна $$2$$, степень исхода равна $$0$$) и корень (степень входа равна $$0$$, степень исхода равна $$2$$). Логические значения $$0$$ или $$1$$, принимаемые булевой функцией, соответствуют листьям диаграммы. Внутренние вершины соответствуют переменным булевой функции. Путь на графе из корневой вершины до одного листа, в зависимости от значений переменных булевой функции, определяет ее значение. Например, на рис.2.6 представлена бинарная диаграмма решений для булевой функции $$f=\overline ab\overline c+ac$$.
(рис 2.6) Бинарная диаграмма решений
Для определения значения булевой функции начинаем двигаться из корневой вершины вниз к листьям дерева. При прохождении каждой внутренней вершины, необходимо решить – по какой ветви (левой или правой), в зависимости от значения переменной, соответствующей текущей вершине, мы должны идти дальше. Значение булевой функции ($$\text{0 или 1}$$) определяется последней вершиной такого пути - висячей вершиной (листом дерева). Допустим, что нам необходимо вычислить значение данной булевой функции c помощью бинарной диаграммы (рис 2.6) при следующих значения переменных: $$a=0, b=0, c=1$$. Начиная с корневой вершины, при прохождении вершины $$a$$ выбираем левую ветвь (так как $$a=0$$), далее в вершине $$b$$ также выбираем левую ветвь и попадаем в лист дерева, соответствующий $$0$$ (в данном случае функция не зависит от значения переменной $$с$$). Следует отметить, что иногда листья дерева могут соответствовать не только константам $$0,1$$, но и переменным. Так для нашего примера листом является вершина $$с$$, поскольку при $$a=1$$ значение функции определяется этой переменной ($$f=c$$). Точка соответствует инверсии конечного результата. Например, при $$a=0, b=1$$ для нашего примера получаем $$f= \overline c$$. Если при прохождении по графу встречается несколько инверсий (точек), то конечный результат инвертируется в случае их нечетного числа.
Рассмотрим построение бинарной диаграммы из таблицы истинности на примере булевой функции, заданной . Сначала строится полное двоичное дерево, представленное на рис. 2.7 а), где каждый путь от корня до листа соответствует одной строке таблицы истинности. Далее эта диаграмма упрощается следующим образом. Так как обе ветви из левого узла с помечены $$0$$, то этот узел можно удалить и заменить его листом, помеченным $$0$$. Дальнейший анализ показывает, что остальные узлы $$c$$ имеют ветви, помеченные $$1$$ или $$0$$ ($$0$$ или $$1$$), и их также можно также удалить и заменить на листья, помеченные $$c$$ или $$\overline c$$. Дальнейшие упрощения показаны на рис.2.7 б)-в).
| a | b | C | F |
|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
(рис 2.7) Бинарные диаграммы
Структурные модели
Информация о логике функционирования ДУ, которую дают описанные выше функциональные модели , является недостаточной для решения проблем генерации тестов и моделирования. При разработке алгоритмов генерации тестов и моделирования чаще используется структурная модель цифрового устройства, отражающая, кроме логики функционирования ДУ, связи между его компонентами и внешней средой. В качестве структурной модели ДУ, как правило, используется правильная логическая сеть. Логическая сеть или схема - это ориентированный граф, вершинами которого являются логические элементы, входы, выходы и узлы разветвления. Направленные дуги графа отображают соединения сети. Правильная логическая сеть - это сеть, у которой выходы никаких двух элементов не соединены вместе и каждая из функций, реализуемых на выходах ДУ, может быть представлена как функция выхода конечного автомата. Основу сети составляют логические элементы двух типов:
элементы, функционирование которых описывается булевыми функциями;
элементы памяти, функционирование которых описывается моделью конечного автомата.
Внешнее описание схемы
Структурная модель ДУ может быть представлена, например, с помощью простого специализированного языка описания схемы международного каталога ISCAS-89 [6], который позволяет описывать ее входы и выходы, компоненты и связи между ними.
На рис.2.8 представлена логическая схем s27 из каталога ISCAS-89 , описание которой на этом языке приведено на рис.2.9 (сравнив эти рисунки легко освоить данный язык для текстового ввода). Из рис. 2.8 видно, что описание схемы начинается с комментариев (в первой позиции стоит символ $$‘#‘$$), содержащих сведения о схеме: число внешних входов, число внешних выходов и D-триггеров, число вентилей по типам. Далее следуют строки описания для каждого элемента схемы, включая внешние входы и выходы. Каждая строка описания содержит:
имя элемента (для внешних входов $$INPUT$$, а для внешних выходов $$OUTPUT$$);
знак равенства $$"="$$ для логических вентилей;
тип вентиля для логических вентилей;
перечисленные в скобках имена вентилей-предшественников данного элемента, которые позволяют сразу определить количество входов данного вентиля.
(рис 2.8) Графическое описание схемы S27.
Допускаются следующие типы вентилей:
$$DFF$$ – D-триггер, описание триггеров должно идти непосредственно за описанием внешних входов и выходов схемы;
$$AND$$ - вентиль И;
$$NAND$$ - вентиль НЕ-И;
$$OR$$ - вентиль ИЛИ;
$$NOR$$ - вентиль НЕ-ИЛИ;
$$XOR$$ - вентиль сумма по mod2;
$$XNOR$$ - вентиль равнозначность;
$$BUFF$$ - буфер (повторитель).
Часто в структурных моделях применяются макроэлементы. При этом элемент описывается в теле макроса, которое используется далее на более высоком уровне. Как правило, допускается несколько уровней вложения, что позволяет использовать иерархический подход к описанию схем.
Кроме связей элементов, в некоторых языках описания может быть представлена информация о временных задержках элементов. Например, это может быть сделано следующим образом:
$$G12 = NOR(G1, G7) delay 20
$$
Это утверждение показывает величину задержки распространения сигнала от входов к выходу данного логического вентиля в некоторых единицах.
Текстовое описание схемы S27
| # 4 inputs | G6 = DFF(G11) |
| # 1 outputs | G7 = DFF(G13) |
| # 3 D-type flipflops | G14 = NOT(G0) |
| # 2 inverters | G17 = NOT(G11) |
| # 8 gates (1 ANDs + 1 NANDs + | G8 = AND(G14, G6) |
| 2 ORs + 4 NORs) | G15 = OR(G12, G8) |
| INPUT(G0) | G16 = OR(G3, G8) |
| INPUT(G1) | G9 = NAND(G16, G15) |
| INPUT(G2) | G10 = NOR(G14, G11) |
| INPUT(G3) | G11 = NOR(G5, G9) |
| OUTPUT(G17) | G12 = NOR(G1, G7) |
| G5 = DFF(G10) | G13 = NOR(G2, G12) |
Свойства структурных моделей
Как было показано выше, структурная модель представляется ориентированным графом, в котором элементы и связи схемы отображаются соответственно в вершины и дуги графа. Внешние входы и выходы схемы при этом отображаются в специальные вершины. Поэтому для исследования свойств структурной модели схемы можно использовать методы теории графов. Например, на рис.2.9 а), б) приведена схема и ее представление ориентированным графом. Отметим, что в данной схеме каждая дуга соединяет только две вершины (сигнал с выхода любого элемента поступает на вход только одного элемента - преемника). Эти схемы не содержат разветвлений (fan out free circuits). Граф такой схемы является деревом.
(рис 2.9) Представление древовидной схемы графом
Схема с разветвлениями представляется двудольным ориентированным графом, который является более общей моделью по сравнению с древовидной структурой. Здесь элементы и связи отображаются в вершины графа таким образом, что каждая дуга соединяет вершину, отображающую элемент схемы, с вершиной, соответствующей связи этого элемента. На . Здесь вершины, соответствующие связям, отмечены знаком $$\bigotimes$$. Такая модель позволяет представлять схемы с элементами, имеющими несколько выходов, и является более общей.
(рис 2.10) Двудольный граф схемы
Следует отметить, что наличие сходящихся разветвлений (reconvergent), как мы увидим дальше в , существенно осложняет построение тестов. На нашем примере рис 2.10имеется сходящееся разветвление, содержащее два пути, которое соединяет вершины $$ERD$$ и $$B1$$. В схемах, состоящих из простейших вентилей $$И, ИЛИ, НЕ-И, НЕ-ИЛИ, НЕ$$, часто используется понятие четности инверсий пути, которое определяется четностью (суммой по $$mod2$$) числа инвертирующих вентилей вдоль данного пути.
Уровень логического элемента в комбинационной схеме определяется как мера расстояния этого элемента от внешних входов. При этом внешним входам присваивается уровень, равный $$0$$. Далее уровень $$l(i)$$ элемента $$i$$, на входы которого поступают сигналы с выходов элементов $$k_1,k_2,…,k_p$$, определяется следующим образом $$l(i)=1+\underset j \max l(k_j)$$
В последовательностной схеме , для вычисления уровней элементов сначала производится условный обрыв линий обратных связей и получившимся псевдовходам присваивается уровень, равный $$0$$. Уровни остальных элементов вычисляются по той же формуле. Для примера на рис.2.11 представлена последовательностная схема , в которой уровень $$1$$ имеют элементы $$E, D, J;$$ уровень $$2$$ – $$F, K$$; уровень $$3$$ – $$G$$; уровень $$4$$ – $$W$$.
(рис 2.11) Ранжированная последовательностная схема
Иногда вместо явного вычисления уровней используется упорядочивание и нумерация элементов в соответствии с их расстоянием от внешних входов. При этом для любых элементов с номерами $$i_1<i_2$$ если $$l(i_1)\leqslant\l(i_2)$$.
Монтажная логика
Логическое моделирование выполняется при предположении, что информация обрабатывается логическими элементами и передается в схеме другим элементам в одном направлении (от входов к выходам в самом элементе, от выходов элемента к входам других элементов в схеме). Но эти предположения не всегда выполняются. Например, достаточно часто при некоторых технологиях используется "монтажная логика". При этом выходы логических элементов соединяются непосредственно и в месте соединения реализуется логическая функция $$И$$ (или $$ИЛИ$$ в зависимости от используемой технологии и мощности соединяемых элементов). Такой элемент называется "проводным (монтажным) $$И (ИЛИ)$$". Для того чтобы подобные ситуации могли обрабатываться в процессе логического моделирования в схему вводится дополнительный фиктивный логический элемент $$И (ИЛИ)$$, как это показано на рис 2.12б), хотя очевидно, что в реальной схеме они принимают одинаковое значение. При корректном моделировании после вычисления значения выхода фиктивного элемента С его надо присвоить также и обоим входам $$A, B$$. На рис 2.12б) это показано пунктирными стрелками. Следует отметить, что введение подобных фиктивных элементов нарушает соответствие между моделью и реальной схемой, что может, например, привести к ошибочной интерпретации результатов моделирования неисправной схемы или построения тестов. Более корректно такие ситуации (и многие другие) моделируются на уровне электрических схем.
(рис 2.12) Моделирование монтажной логики фиктивным элементом
Модели уровня ЯРП
В настоящее время для описания функционирования дискретных устройств широко используются специализированные языки описания цифровой аппаратуры – HDL, которые стали стандартным инструментом при проектировании ДУ . Сейчас вопрос стоит не в том - использовать или не использовать эти языки, а какой именно язык следует использовать при проектировании данного ДУ. Современные языки позволяют описывать ДУ на структурном (вентильном) и функциональном (поведенческом) уровне. В настоящее время они больше используются для описания ДУ на функциональном или уровне регистровых передач. Использование таких языков позволяет существенно сократить срок проектирования и повысить размерность проектируемых ДУ. Следует отметить, что в настоящее время часто срок жизни (эксплуатации) цифровых систем меньше срока его проектирования. В настоящее время наиболее популярными являются языки проектирования SpecC, VHDL (Very high speed integrated circuits HDL) и Verilog HDL.
Рассмотрим основные конструкции этих языков. В них входы, выходы, внутренние состояния и регистры ДУ представляются соответствующими переменными. Как правило, эти переменные должны быть объявлены в начале описания устройства. Например, порты описываются следующим образом:
$$Port(x1,x2:in BIT; -входные\\
y:out BIT); -выходные.
$$
Два регистра могут быть описаны следующим образом:
$$REGISTER R1[1->32], R2[16] ,
$$
где в квадратных скобках указана их разрядность. Аналогичные описания существуют и для других типов устройств (переменных). Так память из 32-разрядных 256 элементов описывается с помощью объявления
$$MEMORY[1->256:32]
$$
Обработка и пересылка может быть описана следующим образом:
$$C\Leftarrow A+B$$
где выполняется сложение содержимого двух регистров $$A$$ и $$B$$ и пересылка результата в регистр $$С$$.
Для описания функционирования ДУ обычно используется следующие группы операторов ЯРП.
Логические операторы: $$AND, OR, NOT, NAND, NOT, XOR, EQUIV$$. Эти операторы обычно выполняются над регистрами или некоторыми их разрядами.
Операторы сравнения: больше (>), меньше (<), больше или равно ($$\ge$$), меньше или равно($$\leqslant$$), равно ($$=$$), не равно ($$!=$$). Эти операторы выполняются над векторами или скалярными переменными. Результатом является логическое значение $$1$$ или $$0$$.
Арифметические операторы: сложение ($$+$$), вычитание ($$-$$), умножение ($$*$$), деление ($$/$$), инкремент, декремент (используются, в основном, для моделирования функционирования счетчиков ).
Битовые операции: правый сдвиг ($$SR$$), левый сдвиг ($$SL$$), циклический правый сдвиг ($$RR$$), циклический левый сдвиг ($$RL$$) и конкатенация (сцепление). Эти операторы выполняются над векторными переменными.
Операция пересылки $$A\Leftarrow B$$ содержимого регистра $$B$$ в регистр $$А$$. Эта операция может быть унарной (выполняется над одним операндом, например, $$A\Leftarrow !B $$), или бинарной (выполняется над двумя операндами, например, $$ A\Leftarrow B+C $$). Единичная задержка неявно ассоциируется с операцией пересылки. Произвольная задержка должна быть указана явно (например, $$ A\Leftarrow B-C\ Delay\ 10$$).
Условные операторы:
бинарный: $$IF\ C\ THEN\ B1\ ELSE\ B2\ IFEND$$;
где $$С$$ является условием, а $$B1$$ и $$B2$$ – блоки, состоящие из операторов.
оператор ветвления типа $$CASE$$:
$$TEST (E0);\\
CASE E0:B0;\\
CASE E1:B1;\\
CASE E2:B2;\\
. . .\\
CASE En:Bn;\\
TESTEND;\\
$$
где $$E$$ являются выражениями и $$B$$ – блоки. Таким образом, может быть описан, например, дешифратор.
Конечные автоматы могут быть описаны двумя способами. При первом (функциональном) подходе языковыми средствами с помощью условных операторов описывается непосредственно таблица переходов и выходов автомата . При втором (структурном) подходе фактически автомат представляется и описывается структурной моделью рис 2.5.
В соответствии с трактовкой понятия времени ЯРП можно разделить на две категории: процедурные и непроцедурные языки. Процедурные ЯРП похожи на обычные языки программирования (такие как Паскаль, С и т.п.), где операторы и утверждения языка выполняются последовательно таким образом, что результат выполненного оператора становится доступным для следующих операторов. Например, при выполнении операторов $$A=B; С=A$$ содержимое переменной (регистра) $$С$$ станет равным содержимому переменной $$B$$. Поэтому некоторые процедурные ЯРП являются расширением обычных языков программирования (например, С, HDL). С другой стороны операторы и утверждения непроцедурных языков выполняются параллельно. В непроцедурных языках выполнение операторов $$A=B; B=A$$ соответствует обмену содержимым регистров $$A$$ и $$B$$. Современные языки описания аппаратуры часто являются смешанными, то есть имеют как процедурные так и не процедурные средства описания и интерпретации.
Ключевые термины:
Комбинационные схемы – схемы из логичесчких элементов, которые реализуют систему булевых функций и, как правило, не имеют обратных связей.
Последовательтностные схемы – схемы из логичесчких элементов, которые реализуют конечный автомат и, как правило, имеют обратные связи.
Функциональный модели – учитывают только логику функционирования ЦУ и не принимают во внимание внутреннюю организацию устройства.
Структурные модели – описывают внутреннюю организацию устройства в виде логических схем.
Бинарная диаграмма (альтернативный граф) – ациклический ориентированный граф, который представляет булевы функции.
Языки регистровых передач – специализированные языки описания цифровых устройств, примером которых являются:VHDL, VERILОG и т.п.
Краткие итоги
В данной лекции вводятся основные модели ЦУ, которые в дальнейшем используются в курсе лекций.
В разделе 2.1 рассматриваются функциональные модели , которые абстрагируются от внутренней организации устройства и учитывают только логику функционирования. Раздел 2.1.1 описывает функциональные модели комбинационных схем в виде системы булевых функций. В разделе 2.1.2 представлены функциональные модели схем с памятью в виде конечных автоматов. Раздел 2.1.3 посвящен функциональным моделям в виде бинарных диаграмм .
В разделе 2.2 описаны структурные модели в виде логических схем. В разделе 2.2.1 приведен пример внешнего описания схемы на простом специализированном языке. Раздел 2.2.2 посвящен свойствам структурных моделей , включая ранжирование элементов схемы.
Раздел 2.3 посвящен моделям уровня языков регистровых передач , где приведены основные типы операторов ЯРП.
Вопросы и упражнения
Чем отличаются комбинационные устройства от последовательностных?
Чем отличаются функциональные модели от структурных ?
Приведите функциональные модели для комбинационных схем .
Чем отличаются таблицы истинности от примитивных кубов?
Могут ли приведенные ниже кубы быть примитивными кубами функции $$f(x_1,x_2,x_3,x_4)$$?
| 0 | x | 1 | x | 0 |
|---|
| x | 1 | 0 | 1 | 0 |
| 1 | x | 1 | 1 | 0 |
| 0 | 1 | 0 | x | 1 |
| x | 0 | 1 | 0 | 1 |
Рассмотрите булеву функцию, определенную примитивными кубами:
$$X 1 0 | 0 , 1 1 x | 0 , x 0 x |1 , 0 1 1 | 1$$. Найдите значение этой функции на следующих входных наборах: $$10u, 01u, u1u, u01$$.
Приведите функциональные модели для схем с памятью.
Что такое автомат Мили и как его можно описать?
Приведите каноническую модель схемы с памятью.
Чем отличается асинхронный автомат от синхронного?
Что такое альтернативные графы (бинарные диаграммы) ?
Постройте альтернативный граф булевой функции из упражнения 5.
Постройте альтернативный граф для функций:
$$f(a,b,c,d,e,g)=ab \lor cd \lor eg \\ f(a,b,c,d)=a \oplus b \oplus c \oplus d$$
Постройте таблицу переходов-выходов синхронного автомата с одним входом и одним выходом, который распознает входную последовательность $$x=1111$$.
Постройте граф переходов-выходов этого автомата
Постройте также схему для распознавания таких перекрывающихся последовательностей и дает на входную последовательность $$x=1100111111101$$ выходную последовательность $$y=0000000111100$$.
Напишите ЯРП модели для D-триггера с передним фронтом переключения.
