Различные классификации математических моделей

Моделирование, тестирование и диагностика цифровых устройств

Лекция 12: Уровни и области моделирования: версия для печати и PDA  В лекции вводятся области проектирования - физическая, структурная и поведенческая. Для каждой области возможны различные уровни моделирования – схемный, логический, языков регистровых передач, системный. Показана связь между областями и уровнями моделирования. Рассмотрены основные аспекты тестирования .

При автоматизации проектирования и диагностирования цифровых устройств (ЦУ) широкое применение находят системы моделирования. Для представления устройств они требуют соответствующих математических моделей. При проектировании ЦУ следует различать модели устройств и их спецификации [1]. Спецификации описывают устройство в терминах получаемых результатов проектирования, таких как схемы, временные диаграммы и т.п. Модели используются в процедурах проектирования устройств при моделировании в данной области (domain), на данном уровне представления для проверки соответствия заданным спецификациям. Они также применяются для установления соответствия между различными уровнями и областями проектирования.

Области и уровни проектирования

В зависимости от взглядов на природу ЦУ и его организацию, принято рассматривать три области представления: физическая, структурная и поведенческая, которые показаны на рис. 1.1 [1], [3]. Для каждой из этих областей различают различные уровни: схемный, логический, языков регистровых передач (ЯРП) и системный. При этом в поведенческой области дается функциональное представление ЦУ, в структурной области описываются блоки архитектуры ДУ, физическая область отражает реальный кристалл (chip). Например, для логического уровня эти три области показаны на рис. 1.2.

С другой стороны на рис. 1.3 показаны различные уровни для структурной области. В табл.1.1 представлены различные уровни проектирования ДУ для каждой области. Следует отметить, что ЦУ на одном и том же уровне в данной области может быть описано различными способами. Например, ЦУ на логическом уровне в поведенческой области может быть описано с помощью булевых выражений, таблиц, языка программирования, языка описания аппаратуры.

Рис. 1.1.  Диаграмма уровней абстракции (Гайского-Кана)

Рис. 1.2.  Области представления схемы на логическом уровне

Рис. 1.3.  Уровни абстракции структурной области

Синтез ЦУ сводится к процессу трансформации проекта от верхнего уровня абстракции к нижнему уровню. Процесс проектирования ЦУ на приведенной диаграмме рис. 1.4а) можно отразить в виде последовательного спуска по уровням абстракции по каждой из областей представления. Но спуск по уровням в любой области связан и чередуется с движением по оси иерархии остальных областей. При этом по уровневый характер внутри любой области сочетается с согласованным движением по осям остальных областей. Этот путь состоит из нескольких переходов от одного уровня к другому в одной и той же области; переходе от одной области к другой на том же уровне и оптимизации на любом участке пути. Преобразования носят характер "от нескольких ко многим", что, например, означает существование нескольких структурных реализаций для каждого поведенческого представления и еще больше физических конфигураций для каждой структурной модели.

увеличить изображение Рис. 1.4.  Процесс синтеза

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

На рис. 1.5 показаны различные процессы, имеющие место при высокоуровневом синтезе [1]. Дуга 1а переводит различные операции в конкретные подсистемы, процессоры и т.п. Дуга 1b дает описание на уровне ЯРП. ЯРП синтез представлен дугами 2a, 2b, 2c . При этом на шаге 2c выполняется на вентильном уровне оптимизация схемы по некоторым критериям, таким число вентилей, пересечений и т.п. Дуга 3с представляет технологическое отображение. Соответственно 4a и 4b соответствуют логическому синтезу и оптимизации. Остальные дуги 5a, 5b, 5c относятся к физическому синтезу, где генерируются маски. При проектировании на стандартных ячейках достаточно выполнить5a. Однако, системы на кристалле содержат ядра (cores), что требует привлечения 5с в зависимости от типа ядра.

Рис. 1.5.  Высокоуровневый синтез

В зависимости от доступности инструментальных средств систем автоматизации проектирования (САПР) и других факторов, разработчики ЦУ могут использовать любой тип синтеза. Чем выше уровень автоматизации, тем быстрее и качественнее выполняется процесс синтеза. Исторически первым автоматизирован был синтез в физической области. Затем была решена проблема автоматизации логического синтеза. И относительно недавно автоматизирована задача автоматизации отображения с ЯРП уровня на логический уровень.

Приведенная многомерная иерархия отражает объективные взаимосвязи разных аспектов проектирования ЦУ и учитывается в методиках по организации процессов проектирования, а также реализуется в системах, поддерживающих автоматизированное проектирование. Сама организация процесса проектирования ЦУ также носит иерархический характер

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

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

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

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

Тестирование

В большинстве случаев тестирование можно рассматривать как эксперимент, в процессе которого на тестируемое устройство подается входное воздействие и снимается выходная реакция [4], как показано на рис.1.6 .

Рис. 1.6.  Тестируемое устройство

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

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

Тестирование проводится на различных этапах производства, что представлено в табл.1.2. Здесь приведены основные этапы производства интегральных схем - от изготовления кристаллов и подложки до их проектирования "Модели логических элементов".

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

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

Часто интегральные схемы тестируются на максимально возможной рабочей частоте. Это объясняется тем, что стоимость некоторых ИС, например, микропроцессоров, зависит от их рабочей частоты. ИС, имеющие характеристики лучше на 10%, могут стоить дороже на 20-50%.

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

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

Отметим, что при тестировании устройства, прежде всего, необходимо решить три основных проблемы:

1. Найти тестовые воздействия.

2. Определить корректность выходных реакций.

3. Оценить эффективность входных воздействий.

При тестирований цифровых систем они реализуются на следующих этапах:

1. генерация проверяющих тестов ;

2. логическое моделирование исправных схем;

3. моделирование неисправностей;

4. Подготовка диагностической информации.

В соответствии с этим последующие лекции разбиты на четыре части:

1. Логическое моделирование исправных цифровых устройств;

2. Логическое моделирование неисправных цифровых устройств;

3. Построение проверяющих тестов ;

4. Сокращение диагностической информации.

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

Область представления в проектировании ЦУ – поведенчекая, структурная, физическая.

Уровень модели в проектировании - схемный, логический, языков регистровых передач, системный.

Тесты – специально организуемые входные воздействия для проверки ЦУ.

Тестирование – процесс проверки ЦУ.

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

Данная лекция является вводной в область проектирования ЦУ и показывает место моделирования и тестирования в САПР.

В разделе "Области и уровни проектирования" описаны области представления: поведенческая, структурная и физическая. Для каждой области описаны различные уровни моделирования, используемые в САПР: схемный, логический, языков регистровых передач и системный.

В разделе "Тестирование" рассмотрены основные виды и аспекты тестирования .

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

1. Чем отличаются области проектирования от уровней моделирования?

2. Приведите основные области проектирования.

3. Приведите основные уровни моделирования цифровых устройств.

4. Чем различаются модели устройств и их спецификации?

5. Приведите свой пример трех областей проектирования для логического уровня.

6. Приведите свой пример различных уровней моделирования для структурной области проектирования.

7. В чем суть тестирования устройства?

8. На каких этапах производства интегральных схем используется тестирование ?

9. Назовите основные компоненты тестирования интегральных схем.

13. Лекция: Модели цифровых устройств: версия для печати и PDA  В лекции вводятся функциональные и структурные модели для комбинационных и последовательностных устройств. Рассматриваются табличные модели в виде таблиц истинности и примитивных кубов, альтернативные графыбинарные диаграммы решений) длякомбинационных схем, синхронные и асинхронные автоматы - для последовательностных схем. В качестве структурных моделей используются логические схемы. Вводятся модели уровня языков регистровых передач (ЯРП).

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

Объектом наших исследований являются ДУ, которые делятся на два класса [5], [8]: комбинационные и последовательностные устройства. ЦУ называется комбинационным, или ЦУ без памяти, если значения его выходных сигналов однозначно определяются только значениями входных сигналов. Последовательностным, или ЦУ с памятью, называется устройство, у которого значения выходных сигналов в данный момент времени зависят от значений входных сигналов в текущий момент и от внутреннего состояния объекта в предыдущий момент времени, определяемого значениями сигналов на линиях обратных связей. При построении моделей ЦУ мы рассмотрим три подхода: функциональный, структурный и представление ДУ языками описания аппаратуры (hardware design languages - HDL).

Функциональные модели

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

Модели комбинационных схем

В качестве функциональной модели комбинационных устройств, чаще всего, используют систему булевых функций:

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

Рис. 2.1.  Комбинационное ДУ

Здесь каждая булева функция - отображение . Простейшим способом представления булевой функции является таблица истинности. Например, в табл.2.1 приведена таблица истинности для булевой функции трех переменных.

Кроме этих таблиц часто используются также табличные модели в виде так называемых "примитивных" (простых) кубов. Эти кубы в сжатом виде фактически представляют ту же самую информацию. Один "примитивный" куб объединяет несколько "соседних" строк таблицы истинности, на которых булева функция принимает одно и тоже значение. Под "соседними" здесь понимаются строки, отличающиеся значением одного (или более) бита. В отличие от таблиц истинности такие кубы используют не двоичный алфавит , а троичный алфавит , где символ представляет неопределенное значение ( или ) переменной. В табл.2.2 представлена табличная модель в виде "примитивных" кубов той же булевой функции (таблица 2.1).

В табл. 2.2 первая строка ("примитивный" куб – ) объединяет третью () и седьмую () строки исходной таблицы истинности. Отметим, что третья стока (куб ) объединяет четыре строки таблицы истинности, имеющих всевозможные значения переменных и и одно и тоже значение булевой функции . Фактически, "примитивный" куб соответствует простой импликанте [9].

Модели последовательностных схем

В качестве функциональной модели последовательностных устройств используется абстрактный конечный автомат [10], являющийся совокупностью пяти объектов , где – конечные множества состояний, входных и выходных сигналов соответственно; - функция переходов, определяющая следующее состояние автомата; - функция выхода, определяющая выходной сигнал.

Различают два типа автомата:

автомат Мили

и автомат Мура

Например, таблица 2.3представляет конечный автомат Мили с одним входом – , одним выходом – и четырьмя состояниями. Здесь на пересечении строки (текущего состояния) и столбца (входного сигнала) приводятся следующее состояние и выходной сигнал автомата.

Кроме приведенной табличной формы автомат также часто представляется графом переходов и выходов. Для примера на рис.2.2 показан граф переходов–выходов автомата, представленного табл.2.3 .

Рис. 2.2.  Граф переходов – выходов автомата табл.2.3

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

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

Здесь каждое состояние в таблице автомата соответствует комбинации переменных состояния - . Синхронизация неявно реализуется в виде дополнительного входа – . Таким образом события (изменение состояния и выходного сигнала ) инициируются импульсами на входе синхронизации. Состояние схемы запоминается в синхронизируемых триггерах (flip-flop - FF) и изменяется при поступлении импульсов на соответствующий вход. На рис.2.4представлены три используемые на практике типа синхронизируемых триггеров: JK-триггер, Т-триггер и D-триггер (задержка). В общем случае синхронные ДУ могут иметь несколько входов синхронизации.

Рис. 2.3.  Модель схемы с памятью

Асинхронные последовательностные схемы не имеют входов синхронизации. Их поведение может быть также представлено таблицей переходов и выходов.

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

Рис. 2.4.  Основные типы триггеров

Следует отметить, что далеко не все состояния схемы являются стабильными. Например, таблица 2.4представляет асинхронный автомат, в котором стабильные состояния здесь выделены жирным шрифтом.

Для асинхронных последовательных ДУ также часто используется каноническая форма, представленная на рис.c5 (модель Хафмена).

Рис. 2.5.  Модель Хафмена

Альтернативные графы (бинарные диаграммы решений)

Бинарные диаграммы решений являются ациклическими ориентированными графами, представляющими булевы функции. Этот тип модели был предложен в [10]и в настоящее время широко используется при моделировании и генерации тестов ЦУ. Множество его вершин можно разбить на три подмножества: внутренние узлы (степень входа равна , степень исхода равна ), листья (степень входа равна , степень исхода равна ) и корень (степень входа равна , степень исхода равна ). Логические значения или , принимаемые булевой функцией, соответствуют листьям диаграммы. Внутренние вершины соответствуют переменным булевой функции. Путь на графе из корневой вершины до одного листа, в зависимости от значений переменных булевой функции, определяет ее значение. Например, на рис.2.6 представлена бинарная диаграмма решений для булевой функции .

Рис. 2.6.  Бинарная диаграмма решений

Для определения значения булевой функции начинаем двигаться из корневой вершины вниз к листьям дерева. При прохождении каждой внутренней вершины, необходимо решить – по какой ветви (левой или правой), в зависимости от значения переменной, соответствующей текущей вершине, мы должны идти дальше. Значение булевой функции () определяется последней вершиной такого пути - висячей вершиной (листом дерева). Допустим, что нам необходимо вычислить значение данной булевой функции c помощью бинарной диаграммы (рис. 2.6) при следующих значения переменных: . Начиная с корневой вершины, при прохождении вершины выбираем левую ветвь (так как ), далее в вершине также выбираем левую ветвь и попадаем в лист дерева, соответствующий (в данном случае функция не зависит от значения переменной ). Следует отметить, что иногда листья дерева могут соответствовать не только константам , но и переменным. Так для нашего примера листом является вершина , поскольку при значение функции определяется этой переменной (). Точка соответствует инверсии конечного результата. Например, при для нашего примера получаем . Если при прохождении по графу встречается несколько инверсий (точек), то конечный результат инвертируется в случае их нечетного числа.

Рассмотрим построение бинарной диаграммы из таблицы истинности на примере булевой функции, заданной табл.2.5 [10]. Сначала строится полное двоичное дерево, представленное на рис. 2.7 а), где каждый путь от корня до листа соответствует одной строке таблицы истинности. Далее эта диаграмма упрощается следующим образом. Так как обе ветви из левого узла с помечены , то этот узел можно удалить и заменить его листом, помеченным . Дальнейший анализ показывает, что остальные узлы имеют ветви, помеченные или ( или ), и их также можно также удалить и заменить на листья, помеченные или . Дальнейшие упрощения показаны на рис.2.7 б)-в).

Рис. 2.7.  Бинарные диаграммы

Структурные модели

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

1. элементы, функционирование которых описывается булевыми функциями;

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

Внешнее описание схемы

Структурная модель ДУ может быть представлена, например, с помощью простого специализированного языка описания схемы международного каталога ISCAS-89 [6], который позволяет описывать ее входы и выходы, компоненты и связи между ними.

На рис.2.8 представлена логическая схем s27 из каталога ISCAS-89 , описание которой на этом языке приведено на рис.2.9 (сравнив эти рисунки легко освоить данный язык для текстового ввода). Из рис. 2.8 видно, что описание схемы начинается с комментариев (в первой позиции стоит символ ), содержащих сведения о схеме: число внешних входов, число внешних выходов и D-триггеров, число вентилей по типам. Далее следуют строки описания для каждого элемента схемы, включая внешние входы и выходы. Каждая строка описания содержит:

1. имя элемента (для внешних входов , а для внешних выходов );

2. знак равенства для логических вентилей;

3. тип вентиля для логических вентилей;

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

Рис. 2.8.  Графическое описание схемы S27.

Допускаются следующие типы вентилей:

1.  – D-триггер, описание триггеров должно идти непосредственно за описанием внешних входов и выходов схемы;

2.  - вентиль И;

3.  - вентиль НЕ-И;

4.  - вентиль ИЛИ;

5.  - вентиль НЕ-ИЛИ;

6.  - вентиль сумма по mod2;

7.  - вентиль равнозначность;

8.  - буфер (повторитель).

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

Кроме связей элементов, в некоторых языках описания может быть представлена информация о временных задержках элементов. Например, это может быть сделано следующим образом:

Это утверждение показывает величину задержки распространения сигнала от входов к выходу данного логического вентиля в некоторых единицах. Текстовое описание схемы S27

Свойства структурных моделей

Как было показано выше, структурная модель представляется ориентированным графом, в котором элементы и связи схемы отображаются соответственно в вершины и дуги графа. Внешние входы и выходы схемы при этом отображаются в специальные вершины. Поэтому для исследования свойств структурной модели схемы можно использовать методы теории графов. Например, на рис.2.9 а), б) приведена схема и ее представление ориентированным графом. Отметим, что в данной схеме каждая дуга соединяет только две вершины (сигнал с выхода любого элемента поступает на вход только одного элемента - преемника). Эти схемы не содержат разветвлений (fan out freecircuits). Граф такой схемы является деревом.

Рис. 2.9.  Представление древовидной схемы графом

Схема с разветвлениями представляется двудольным ориентированным графом, который является более общей моделью по сравнению с древовидной структурой. Здесь элементы и связи отображаются в вершины графа таким образом, что каждая дуга соединяет вершину, отображающую элемент схемы, с вершиной, соответствующей связи этого элемента. На рис.2.10 для примера показан такой граф [10]. Здесь вершины, соответствующие связям, отмечены знаком . Такая модель позволяет представлять схемы с элементами, имеющими несколько выходов, и является более общей.

Рис. 2.10.  Двудольный граф схемы

Следует отметить, что наличие сходящихся разветвлений (reconvergent), как мы увидим дальше в "Машинные модели логических схем и управление процессом моделирования ", существенно осложняет построение тестов. На нашем примере рис. 2.10имеется сходящееся разветвление, содержащее два пути, которое соединяет вершины и . В схемах, состоящих из простейших вентилей , часто используется понятие четности инверсий пути, которое определяется четностью (суммой по ) числа инвертирующих вентилей вдоль данного пути.

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

В последовательностной схеме , для вычисления уровней элементов сначала производится условный обрыв линий обратных связей и получившимся псевдовходам присваивается уровень, равный . Уровни остальных элементов вычисляются по той же формуле. Для примера на рис.2.11 представлена последовательностная схема , в которой уровень имеют элементы уровень – ; уровень – ; уровень – .

Рис. 2.11.  Ранжированная последовательностная схема

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

Монтажная логика

Логическое моделирование выполняется при предположении, что информация обрабатывается логическими элементами и передается в схеме другим элементам в одном направлении (от входов к выходам в самом элементе, от выходов элемента к входам других элементов в схеме). Но эти предположения не всегда выполняются. Например, достаточно часто при некоторых технологиях используется "монтажная логика". При этом выходы логических элементов соединяются непосредственно и в месте соединения реализуется логическая функция (или в зависимости от используемой технологии и мощности соединяемых элементов). Такой элемент называется "проводным (монтажным) ". Для того чтобы подобные ситуации могли обрабатываться в процессе логического моделирования в схему вводится дополнительный фиктивный логический элемент , как это показано на рис.2.12 . Здесь на рис.2.12 а) представлена исходная схема, а рис.2.12 б) – преобразованная схема с фиктивным элементом. Следует отметить, что логическое значение на выходе фиктивного элемента при этом всегда правильное, но значения на его входах при такой модели не всегда соответствует реальной схеме. В этой модели входы фиктивного элемента могут иметь различные значения (например, для схемы рис. 2.12б), хотя очевидно, что в реальной схеме они принимают одинаковое значение. При корректном моделировании после вычисления значения выхода фиктивного элемента С его надо присвоить также и обоим входам . На рис. 2.12б) это показано пунктирными стрелками. Следует отметить, что введение подобных фиктивных элементов нарушает соответствие между моделью и реальной схемой, что может, например, привести к ошибочной интерпретации результатов моделирования неисправной схемы или построения тестов. Более корректно такие ситуации (и многие другие) моделируются на уровне электрических схем.

Рис. 2.12.  Моделирование монтажной логики фиктивным элементом

Модели уровня ЯРП

В настоящее время для описания функционирования дискретных устройств широко используются специализированные языки описания цифровой аппаратуры – HDL, которые стали стандартным инструментом при проектировании ДУ[10]. Сейчас вопрос стоит не в том - использовать или не использовать эти языки, а какой именно язык следует использовать при проектировании данного ДУ. Современные языки позволяют описывать ДУ на структурном (вентильном) и функциональном (поведенческом) уровне. В настоящее время они больше используются для описания ДУ на функциональном или уровне регистровых передач. Использование таких языков позволяет существенно сократить срок проектирования и повысить размерность проектируемых ДУ. Следует отметить, что в настоящее время часто срок жизни (эксплуатации) цифровых систем меньше срока его проектирования. В настоящее время наиболее популярными являются языки проектирования SpecC, VHDL (Very high speed integrated circuits HDL) и Verilog HDL.

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

Два регистра могут быть описаны следующим образом:

где в квадратных скобках указана их разрядность. Аналогичные описания существуют и для других типов устройств (переменных). Так память из 32-разрядных 256 элементов описывается с помощью объявления

Обработка и пересылка может быть описана следующим образом:

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

Для описания функционирования ДУ обычно используется следующие группы операторов ЯРП.

1. Логические операторы: . Эти операторы обычно выполняются над регистрами или некоторыми их разрядами.

2. Операторы сравнения: больше (>), меньше (<), больше или равно (), меньше или равно(), равно (), не равно (). Эти операторы выполняются над векторами или скалярными переменными. Результатом является логическое значение или .

3. Арифметические операторы: сложение (), вычитание (), умножение (), деление (), инкремент, декремент (используются, в основном, для моделирования функционирования счетчиков ).

4. Битовые операции: правый сдвиг (), левый сдвиг (), циклический правый сдвиг (), циклический левый сдвиг () и конкатенация (сцепление). Эти операторы выполняются над векторными переменными.

5. Операция пересылки содержимого регистра в регистр . Эта операция может быть унарной (выполняется над одним операндом, например, ), или бинарной (выполняется над двумя операндами, например, ). Единичная задержка неявно ассоциируется с операцией пересылки. Произвольная задержка должна быть указана явно (например, ).

6. Условные операторы:

• бинарный: ;

где является условием, а и – блоки, состоящие из операторов.

• оператор ветвления типа :

где являются выражениями и – блоки. Таким образом, может быть описан, например, дешифратор.

Конечные автоматы могут быть описаны двумя способами. При первом (функциональном) подходе языковыми средствами с помощью условных операторов описывается непосредственно таблица переходов и выходов автомата [10]. При втором (структурном) подходе фактически автомат представляется и описывается структурной моделью рис. 2.5.

В соответствии с трактовкой понятия времени ЯРП можно разделить на две категории: процедурные и непроцедурные языки. Процедурные ЯРП похожи на обычные языки программирования (такие как Паскаль, С и т.п.), где операторы и утверждения языка выполняются последовательно таким образом, что результат выполненного оператора становится доступным для следующих операторов. Например, при выполнении операторов содержимое переменной (регистра) станет равным содержимому переменной . Поэтому некоторые процедурные ЯРП являются расширением обычных языков программирования (например, С, HDL). С другой стороны операторы и утверждения непроцедурных языков выполняются параллельно. В непроцедурных языках выполнение операторов соответствует обмену содержимым регистров и . Современные языки описания аппаратуры часто являются смешанными, то есть имеют как процедурные так и не процедурные средства описания и интерпретации.

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

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

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

Функциональный модели – учитывают только логику функционирования ЦУ и не принимают во внимание внутреннюю организацию устройства.

Структурные модели – описывают внутреннюю организацию устройства в виде логических схем.

Бинарная диаграмма (альтернативный граф) – ациклический ориентированный граф, который представляет булевы функции.

Языки регистровых передач – специализированные языки описания цифровых устройств, примером которых являются:VHDL, VERILОG и т.п.

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

В данной лекции вводятся основные модели ЦУ, которые в дальнейшем используются в курсе лекций.

В разделе 2.1 рассматриваются функциональные модели , которые абстрагируются от внутренней организации устройства и учитывают только логику функционирования. Раздел 2.1.1 описывает функциональные моделикомбинационных схем в виде системы булевых функций. В разделе 2.1.2 представлены функциональные модели схем с памятью в виде конечных автоматов. Раздел 2.1.3 посвящен функциональным моделям в виде бинарных диаграмм .

В разделе 2.2 описаны структурные модели в виде логических схем. В разделе 2.2.1 приведен пример внешнего описания схемы на простом специализированном языке. Раздел 2.2.2 посвящен свойствам структурных моделей , включая ранжирование элементов схемы.

Раздел 2.3 посвящен моделям уровня языков регистровых передач , где приведены основные типы операторов ЯРП.

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

1. Чем отличаются комбинационные устройства от последовательностных?

2. Чем отличаются функциональные модели от структурных ?

3. Приведите функциональные модели для комбинационных схем .

4. Чем отличаются таблицы истинности от примитивных кубов?

5. Могут ли приведенные ниже кубы быть примитивными кубами функции ?

   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

6. Рассмотрите булеву функцию, определенную примитивными кубами:

7. . Найдите значение этой функции на следующих входных наборах: .

8. Приведите функциональные модели для схем с памятью.

9. Что такое автомат Мили и как его можно описать?

10. Приведите каноническую модель схемы с памятью.

11. Чем отличается асинхронный автомат от синхронного?

12. Что такое альтернативные графы (бинарные диаграммы) ?

13. Постройте альтернативный граф булевой функции из упражнения 5.

14. Постройте альтернативный граф для функций:

16. Постройте таблицу переходов-выходов синхронного автомата с одним входом и одним выходом, который распознает входную последовательность .

17. Постройте граф переходов-выходов этого автомата

18. Постройте также схему для распознавания таких перекрывающихся последовательностей и дает на входную последовательность выходную последовательность .

19. Напишите ЯРП модели для D-триггера с передним фронтом переключения.

14. Лекция: Логическое моделирование: версия для печати и PDA  В лекции рассмотрены состав, назначение и общие принципы систем логического моделирования. Приведена классификация методов логического моделирования. Введены модели сигналов, включая многозначные алфавиты.

Состав и назначение программ логического моделирования

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

Логическое моделирование включает в себя построение математической модели ДУ - системы соотношений, описывающей поведение исследуемого устройства с заданной точностью, и дальнейший анализ поведения этой модели на заданной последовательности входных воздействий. При решении задач анализа и диагностирования ДУ обычно используется структурная математическая модель объекта, отражающая совокупность компонентов объекта, связи между компонентами и связь объекта с внешней средой. Для выполнения логического моделирования необходимы следующие компоненты, представленные на рис.3.1 :

1. модель ДУ,

2. входные воздействия,

3. библиотека логических элементов,

4. результаты моделирования.

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

Рис. 3.1.  Структура системы логического моделировании

Логическое моделирование является важнейшей компонентой САПР цифровых систем. С помощью логического моделирования в системах автоматизированного проектирования и диагностирования ДУ исследуются следующие проблемы [5]:

• проверка правильности логического функционирования ДУ;

• проверка функционирования цепей установки ДУ;

• проверка временных характеристик ДУ;

• анализ состязаний сигналов;

• определение полноты теста и списка непроверенных неисправностей;

• определение диагностических свойств тестов;

• получение диагностической информации для локализации неисправностей ДУ.

При верификации ДУ с помощью логического моделирования необходимо решить следующие проблемы:

1. построение необходимых входных воздействий (генерация тестов);

2. определение корректности полученных результатов;

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

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

Общие принципы логического моделирования

Исходной информацией для программ логического моделирования является описание схемы ДУ в виде сети, вершинами которой являются логические элементы, входы и выходы. Практически каждая система моделирования имеет свои языковые средства для описания схемы ДУ и входных воздействий (тестов).

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

Рис. 3.2.  Пример логического моделирования схемы

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

Этот процесс может быть организован по-разному в зависимости от применяемых методов моделирования. Основными отличительными чертами методов логического моделирования являются: модель сигналов, модель схемы в компьютере, способ учета времени распространения сигналов в ДУ, управление очерёдностью моделирования логических элементов [5]. В зависимости от применяемых моделей сигналов, методы делятся: по алфавиту – на двоичные и многозначные; по используемой модели схемы в компьютере – на интерпретативные и компилятивные; по учёту распространения сигналов – на синхронные (без учета задержек логических элементов) и асинхронные (с учетом задержек); по очередности моделирования логических элементов – сквозные и событийные [2]. Классификация методов моделирования представлена на рис.3.3 .

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

Рис. 3.3.  Методы логического моделирования

Адекватность моделирования зависит, в основном, от используемой модели ДУ, моделей логических элементов и сигналов, способа учёта временных соотношений между сигналами. Обычно повышение степени адекватности связано со снижением быстродействия и увеличением необходимого объёма памяти. Самыми быстрыми являются алгоритмы двоичного моделирования в алфавите без учёта задержек, где реальный порядок срабатывания элементов не принимается во внимание. Учёт задержек элементов снижает быстродействие. Анализ переходных процессов требует увеличения значности алфавита.

Модели сигналов

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

Простейшим является двоичный алфавит , в котором, как правило, соответствует низкому уровню сигнала, а – высокому.

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

Рис. 3.4.  Троичный алфавит

Кроме троичного применяется пятизначный алфавит , представленный на рис.3.5 , где – низкий уровень сигнала; – высокий; – гладкий переход из в (передний фронт); – гладкий переход из в (задний фронт); – неопределённое значение сигнала.

Рис. 3.5.  Пятизначный алфавит Е5

Для некоторых технологий (например, КМОП) моделирование даже определенных сигналов в статике требует введения дополнительных символов. Так иногда используют алфавит , где символ соответствует состоянию высокого импеданса для схем с отключающимся выходом, а – конфликту на шине [2]. В настоящее время существует множество многозначных алфавитов, которые применяются в логическом моделировании и генерации тестов. Большая часть из них включается в универсальную систему многозначных алфавитов, которая представлена в лекции 7 .

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

Логическое моделирование – моделирование поведения логической схемы на заданных входных воздействиях.

Модель сигналов – представляется алфавитом моделирования, символы которого представляют физические сигналы.

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

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

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

В разделе 3.2 изложены общие принципы и классификация методов логического моделирования по:

1. модели сигналов;

2. модели схемы;

3. учету распространения сигналов;

4. очередности обработки элементов.

В разделе 3.3 представлены модели сигналов, которые включают:

1. двоичный алфавит;

2. троичный алфавит;

3. пятизначный алфавит.

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

1. Что такое логическое моделирование?

2. Что необходимо для выполнения логического моделирования?

3. Приведите структуру системы логического моделирования.

4. Какие задачи решаются с помощью логического моделирования?

5. Приведите классификацию методов логического моделирования.

6. Приведите основные характеристики логического моделирования.

7. Что такое модель сигнала?

8. Чем отличается троичный алфавит от двоичного?

9. Опишите пятизначный алфавит и физический смысл его символов.

15. Лекция: Модели логических элементов: версия для печати и PDA  В лекции рассмотрены модели логических элементов в различных в двоичном и многозначных алфавитах. Введены табличные и функциональные модели элементов в различных алфавитах. Определены различные модели задержки для элементов.

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

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

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

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

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

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

3. определить значение выхода .

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

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

Таблицы zoom

При использовании таблиц истинности в моделировании необходимо сначала определить тип соответствующего логического элемента. Поэтому определение типа элемента и собственно вычисление выходного значения выполняются в два этапа. Эти два шага можно объединить в один следующим образом[8]. Пусть является номером типа элемента и - максимальный размер таблицы истинности (для всех типов). Тогда можно построить таблицу zoom размера, в которой хранятся таблиц истинности, которые начинаются с позиции . Для вычисления значения выхода элемента с использованием такой таблицы необходимо упаковать тип элемента и значения его входов в одно слово, которое определяет индекс в таблице zoom, как это показано на рис.4.1.

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

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

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

Рис. 4.1.  Zoom таблица

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

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

Рис. 4.2.  Пример схемы

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

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

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

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

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

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

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

При построении многозначных моделей элементов используются те же подходы, что и в случае двоичного алфавита. Рассмотрим сначала моделирование логических элементов в троичном алфавите . Для примера возьмем 2-входовой вентиль . Входы и выход этого элемента принимают значения из троичного алфавита . Пусть входы имеют значения . Чему равно значение выхода в алфавите ? Поскольку символ представляет два значения (это или , но неизвестно, что именно), то моделирование на одном троичном наборе можно выполнить путем моделирования на двух двоичных наборах, покрываемых троичным, и затем сравнить результаты. Для нашего примера имеем:

1. значения первого двоичного набора (покрываемом троичным) дают ;

2. значения второго двоичного набора также дают .

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

1. значения первого двоичного набора дают ;

2. значения второго двоичного набора дают .

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

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

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

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

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

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

Данный способ построения многозначных моделей элементов основан на кодировании многозначных алфавитов и является обобщением метода построения моделей, изложенных для двоичного алфавита. Рассмотрим сначала троичные компонентные модели. Так как каждая троичная переменная принимает три значения ,то она может быть представлена двумя булевыми переменными, принимающими двоичные значения. Для этого используются различные способы кодирования троичного алфавита [7]. Мы, в основном, будем использовать дизъюнктивный метод кодирования троичного алфавита, представленный табл.4.7.

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

Известен простой способ построения функций и для произвольной булевой функции. Если задана дизъюнктивной нормальной формой (ДНФ), то компонента получается из ДНФ функции заменой вхождений переменных на и на . Аналогично компонента получается из ДНФ отрицания функции . Например, для функции и имеем и .

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

В большинстве программ моделирования в качестве базовых (элементарных) логических элементов используются простейшие вентили . Они характеризуются, прежде всего, двумя параметрами: контролирующее значение и инверсия . Значение входа называется контролирующим, если оно определяет выход вентиля, равный , независимо от значений остальных входов. таблица 4.9 и таблица 4.8представляют соответственно простые кубы и значения параметров для любых стандартных 3-входовых вентилей. В табл.4.9 в каждой строке представлен простой куб вентиля в порядке, указанном в табл.4.8.

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

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

Анализ программы показывает, что для вычисления значения выхода стандартного вентиля в троичном алфавите достаточно знать: имеет ли какой либо вход контролирующее значение и при его отсутствии наличие неопределенного значения на входах. Поэтому был предложен метод [6], в котором вместо хранения значений входов для каждого вентиля сохраняются значения двух счетчиков – и , где содержится число входов с контролирующим и неопределенным значением соответственно. При очередном вызове функции модели вентиля значение этих счетчиков может изменяться. Например, при изменении входа вентиля счетчик увеличивается на , в то время как при изменении увеличивается на счетчик . Тогда вычисление значения выхода вентиля сводится к проверке счетчиков. Ниже представлен метод вычисления значения выхода.

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

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

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

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

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

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

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

Рис. 4.4.  Пример схемы

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

В ряде случаев используют для одного и того же элемента различные значения задержек для переднего и заднего фронтов сигнала. Например, в схемах на МОП-структурах время задержки спада сигнала может в 3 раза превышать время задержки переднего фронта . Следовательно, в данном случае при моделировании длительность (положительного) импульса может увеличиваться (как это имеет место на рис.4.5а). ( для элементов и для элементов )

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

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

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

а) ; б) ; в) .

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

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

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

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

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

Рис. 4.8.  Инерционная задержка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Постройте zoom-таблицу для вентилей .

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

5. Постройте алгоритмическую функциональную модель для элемента .

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

7. Постройте табличную модель в 5-значном алфавите для элемента .

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

9. Опишите компонентную троичную модель для элемента.

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

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

12. Напишите программные модели вентиля на основе методов: а) сканирования входов, б) счетчика.

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

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

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

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

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

• Транспортная с ;

• Инерциальная с ;

• Инерциальная с ;

15. Лекция: Машинные модели логических схем и управление процессом моделирования В лекции вводится компилятивное и интерпретативное представление логической схемы. Рассматривается управление процессом моделирования, описываются основные алгоритмы событийного моделирования логических схем.

Внутренние (машинные) модели схем

После ввода внешнего описания ДУ в компьютер, оно транслируется во внутреннее представление устройства, которое непосредственно используется в процессе логического моделирования. Существуют две основные формы (модели) внутреннего представления ДУ – компилятивная и интерпретативная. При компилятивной модели внешнее описание ДУ в виде структурной модели (схемы) или функциональной с использованием ЯРП транслируется в программу на некотором языке программирования (обычно ассемблере или С), которая непосредственно выполняет процесс моделирования. При интерпретативной модели внешнее описание транслируется в систему связанных таблиц, которые далее используются универсальной программой моделирования.

Компилятивная модель

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

Алгоритм компилятивного моделирования [39] приведен в виде псевдокода в листинге "Компилятивное моделирование". Следует обратить внимание на то, что при этом необходимо предварительно ранжировать схему по уровням. Основным преимуществом компилятивного метода моделирования является его высокое быстродействие. К недостаткам следует отнести то, что модель при изменении схемы (в процессе проектирования) каждый раз должна компилироваться заново. Здесь, как правило, используется сквозное (а не событийное ) моделирование, при котором на каждой итерации значение каждого логического элемента пересчитывается заново.

Рис. 5.1.  Схема для компилятивной модели

Компилятивная модель

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

Интерпретативная модель

В интерпретативном методе моделирования внешнее описание схемы транслируется в систему связанных таблиц, которая далее непосредственно используется в процессе моделирования. При этом каждой схеме соответствует своя система таблиц, а сама программа моделирования является универсальной. Например, на рис.2.20 приведены таблицы, представляющие схему S27 рис.2.9. Модель состоит из трех связанных между собой таблиц: - таблица типов элементов, - таблица элементов, - таблица контактов. Каждая строка таблицы соответствует элементу схемы и содержит следующую информацию: имя элемента (столбец ); ссылка на таблицу типов (); ссылка на таблицу контактов (), указывающая начало зоны контактов данного элемента.

Компилятивное моделирование

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

Таблица содержит информацию о контактах схемы. Каждая строка этой таблицы соответствует контакту некоторого элемента. Более того, в ней каждому элементу отведена своя зона контактов, начинающаяся со строки, указанной в таблицы элементов. В начале зоны идут выходные контакты, а затем входные. Входы схемы представляются как элементы, имеющие только выходные контакты, а выходы схемы имеют только входные контакты. Столбец содержит ссылку на таблицу элементов. В столбце поразрядно записываются различные признаки, необходимые в процессе моделирования и генерации тестов. Столбец содержит кодированные значения сигналов в многозначном алфавите. Столбец определяет связи между контактами. Из таблицы 5.1 видно, что контакты, образующие один узел в схеме (обычно это один выходной и несколько входных контактов), связаны между собой в кольцевой список. Такая структура данных п озволяет эффективно продвигаться от входов к выходам схемы и в противоположном направлении. Информационная избыточность (значения сигналов хранятся для нескольких контактов, образующих один узел) позволяет уменьшить число пересылок при подготовке элемента к обработке и существенно ускоряет процесс моделирования. Следует отметить, что первые строки во всех таблицах соответствуют фиктивным элементам, представляющим константы , которые присутствуют во всех схемах независимо от того, используются они в данной схеме или нет. Эти элементы используются, например, для представления постоянных уровней напряжения или , подаваемых на некоторые элементы.

Управление процессом моделирования

Как уже отмечалось, во многих случаях алгоритм моделирования можно представить следующим образом. После подачи входного воздействия на модель ДУ поочерёдно вычисляются значения на выходах всех элементов по значениям на их входах. Такая процедура называется итерацией. В результате вычислений значения некоторых сигналов могут измениться. В этом случае необходимо выполнить вторую итерацию (т.е. вычислить значения на выходах всех элементов по новым значениям на их входах), затем третью итерацию и так далее до тех пор, пока все сигналы не примут установившиеся значения. В этом случае процесс моделирования (на одном входном наборе) сходится естественным образом. Возможен и другой результат моделирования – значения сигналов на некоторых линиях периодически изменяются. В этом случае говорят, что моделирование не сходится из-за генерации модели ДУ. Такая ситуация может быть, например, в ДУ, содержащем контур обратной связи с нечетным числом инверсий.

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

Событийное моделирование

Как отмечалось выше, в зависимости от очередности обработки логических элементов различают сквозные и событийные методы логического моделирования. При сквозном методе на каждой итерации каждый логический элемент моделируется заново вне зависимости от того, произошли изменения сигналов на его входах или нет. В событийном методе логический элемент моделируется только в том случае, если на его входах произошло событие – изменилось значение сигнала хотя бы на одном из его входов. Для элементов памяти событием является также изменение его состояния (изменение переменной внутреннего состояния). Обычно в процессе моделирования на каждой итерации активны (имеют изменения на входах) только несколько процентов элементов (3-5%), поэтому событийный метод гораздо быстрее сквозного.

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

При этом центральное место занимает понятие очереди будущих событий (ОБС) [6], [10]. Каждое событие в ОБС содержит номер элемента и соответствующее значение сигнала . Это событие при моделировании привязывается в соответствии с задержкой выхода элемента к моменту времени , где — текущее модельное время. Значения сигналов при этом для текущего момента времени хранятся в массиве . Вновь вычисленные значения элементов записываются в ОБС с учетом задержки .

Для упорядочения событий в ОБС используют различные способы моделирования временного механизма. Один из них использует при программной реализации структуру связанных списков, как это показано на рис.5.2 .

Рис. 5.2.  Список событий.

Здесь каждому моменту времени соответствует свой список ОБС. Времена упорядочены и связаны списком. Занесение нового события с использованием этого способа требуют поиска нужного путём просмотра соответствующих указателей. Если моменты времени, для которых ОБС не пусты, идут достаточно плотно, то эффективней другой способ моделирования временного механизма, который показан на рис.5.3 .

Рис. 5.3.  Колесо времени

При этом для хранения указателей ОБС используется массив,

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

В листинге "Алгоритм логического моделирования" представлен укрупненный алгоритм логического моделирования на основе временного механизма в виде очереди будущих событий. Этот алгоритм отражает движение по очереди будущих событий.

В каждый (не пустой) момент времени события обрабатываются по алгоритму, представленному в листинге "Алгоритм логического моделирования" [44] (который реализует соответствующий шаг алгоритма рис.2.24).

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

Алгоритм логического моделирования

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

Двухпроходной алгоритм обработки событий

Улучшенный двухпроходной алгоритм обработки событий

В следующем алгоритме [6], представленном выше, заносятся в ОБС только "истинные события", при которых происходит изменение сигнала. В [6] показано, что данный алгоритм является более эффективным. Преимущество двухпроходного алгоритма заключается в том, что он позволяет избежать повторных вычислений (моделирования одного и того же логического элемента) в случае наличия кратных событий, когда на входах имеет место изменение нескольких сигналов. Однако проведенный статистический анализ [6] показал, что кратные события в процессе моделирования случаются достаточно редко. Поэтому кроме двухпроходного были разработаны также однопроходные алгоритмы логического моделирования [6]. Один из таких алгоритмов [6] представлен в листинге "Однопроходной алгоритм обработки событий".

Несмотря на свою привлекательность (простоту и эффективность) этот алгоритм имеет недостаток. На рис.5.4 показана суть проблемы обработки кратного события. Здесь на входе элемента имеет место одновременное изменение двух сигналов и . Если эти события обрабатываются в последовательности , то выход элемента не изменяется и, следовательно, не ставится в очередь будущих событий для последующей обработки.

Однопроходной алгоритм обработки событий

Рис. 5.4.  Пример некорректного моделирования

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

Улучшенный однопроходной алгоритм обработки событий

Мы рассмотрели основные алгоритмы событийного логического моделирования с использованием модели номинальных задержек. Но они с небольшими изменениями могут быть использованы и для других более сложных моделей задержек, рассмотренных в лекции 4 (различные задержки для переднего и заднего фронтов, разброс задержек, инерционная задержка).

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

Компилятивная модель схемы – представляется компьютерной программой, моделирующей данную схему.

Интерпретативная модель схемы – представляется системой связанных таблиц.

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

Очередь будущих событий – упорядоченные в модельном времени события (изменения сигналов на линиях схемы).

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

В лекции рассмотрены машинные модели цифровых схем и управление процессом логического моделирования..

В разделе 5.1 описаны машинные модели схем, которые используются в логическом моделировании, к которым относятся:

1. компилятивная модель, изложенная в разделе 5.1.1;

2. интерпретативная модель в виде связанных таблиц, которая представлена в 5.12.

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

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

1. Какие используются машинные модели схемы?

2. Опишите компилятивную модель схемы.

3. Что составляет интерпретативную модель схемы.

4. Чем отличается сквозное моделирование от событийного?

5. Опишите основной алгоритм событийного логического моделирования.

6. Что такое очередь будущих событий?

7. Какие вы знаете способы моделирования временного механизма?

8. Опишите двухпроходной алгоритм логического моделирования на основе продвижения по очереди будущих событий.

9. Какие недостатки имеет этот алгоритм?

10. Опишите улучшенный двухпроходной алгоритм логического моделирования.

11. Опишите однопроходной алгоритм событийного логического моделирования.