Способы представления переключательных функций

Учебный комплекс «Вычислительная техника»

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

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

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

Совершенная дизъюнктивная нормальная форма (СДНФ) представления переключательной функции – запись функции в виде дизъюнкции конъюнкций, для которых значение функций равно 1 (дизъюнкции минтермов).

Порядок перехода следующий:

1. Составить минтермы для строк таблицы истинности, где функция равна единице. Если значение переменной равно 0, то в минтерме записывается отрицание этой переменной.
2. Записать дизъюнкцию составленных минтермов, которая и будет представлять переключательную функцию в СДНФ.

Совершенная конъюнктивная нормальная форма (СКНФ) представления переключательной функции – запись функции в виде конъюнкции дизъюнкций, для которых значение функций равно 0 (конъюнкции макстермов).

Порядок перехода к СКНФ:

1. Составить макстермы для строк таблицы истинности, где функция равна нулю. Если значение переменной равно 1, то в минтерме записывается отрицание этой переменной.
2. Записать конъюнкцию составленных макстермов, которая и будет представлять переключательную функцию в СКНФ.

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

Источник

Способы задания переключательных функций

Задать переключательную функцию (ПФ) – значит указать ее значение при всех возможных наборах ее аргументов. Логические функции в общем случае могут иметь различные формы представления: словесное, табличное, алгебраическое, графическое (например, карта Карно).

а) табличный способ задания ПФ

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

Эта таблица называется таблицей истинности или таблицей соответствия.

Кроме наглядности табличный способ обладает тем достоинством, что каждой функции соответствует одна и только одна таблица истинности. Недостаток табл. способа – громоздкость таблицы истинности, растет с возрастанием числа переменных: n=6, 2 6 строк.

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

б) аналитический способ (алгебраический)

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

ДСНФ (дизъюнктивная совершенная нормальная форма)

КСНФ (конъюнктивная совершенная нормальная форма)

Аналитическая запись ПФ в ДСНФ и КСНФ строится по средствам суперпозиции (наложения) специальных вспомогательных функций (минтермов m_i и макстермов М_i)

Минтерм – (констентуента единицы) – булево произведение (конъюнкция) от n переменных, в котором каждая переменная входит только один раз, либо в ПК (если ее значение в данном наборе равно 1), либо в инверсном (если значение переменной в наборе равно 0)

Макстерм М_i – (констентуэнта нуля) – булева сумма (дизъюнкция) от n переменных, в который каждая переменная входит только 1 раз в прямом или инверсном виде.

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

Таким образом алгебраическое выражение для любой переключательной функции можно представить в форме:

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

Где больше 1 – ДСНФ

Где больше 0 – КСНФ.

Однако при минимизации ПФ более удобной является ДСНФ.

в) при относительно небольшом числе элементов (не более 6) в ряде случаев удобным и наглядным является графическое представление ПФ в виде т.н. карт минтермов.

Наиболее распространенная форма – карта Карно.

Карта Карно содержит 2 n клеток, каждая из клеток соответствует одному из минтермов. (q=2 n )

Если требуется представить на карте Карно (кК) функцию, заданную в виде ДСНФ, то в клетках карты для минтермов, входящих в ДСНФ ставится 1, иначе – 0 или оставляются незаполненными.

Существует целый класс, значение которых определено для части наборов аргументов (они называется частично определенные ПФ)

Наборы, для которых ПФ определена – рабочие.

Наборы, для которых ПФ неопределенна – безразличные (в табл. обозначены крестиком). На практике безразличные режимы не реализуются.

Упрощение (минимизация) ПФ

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

Под минимизацией ПФ подразумевают нахождение для нее такой ДНФ, которая имеет минимальную цену или сложность.

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

Методы минимизации ПФ.

В настоящее время известен целый ряд методов м. в ПФ. Все они основаны на преобразовании логических выражений и подразделяются на систематические и несистематические.

а) систематические методы

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

Нахождение минимальной формы производится в 3 этапа:

анализируется вид задания ПФ

Если она задана произвольной формой в булевой алгебре, то с помощью законов алгебры логики она приводится в ДСНФ.

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

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

Обычно в процессе м. склеивают смежные минтермы, затем – имбликаты. Процесс длится до получения имбликат, которые не склеиваются между собой. Такие имбликаты называются простыми, состоящими из дизъюнкции простых импликат, называемых сокращенной ДНФ.

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

Искомая минимальная ДНФ совпадает с той из тупиковой, которая содержит наименьшее число вхождений аргументов.

(Метод Квайна Мак Класки – при большом числе переменных, >6. При n≤6 наиболее простым является метод Вейч-Карно, основанный на табличном представлении ПФ.

Карты Карно (диаграмма Вейча) – это прямоугольные таблицы, состоящие из 2 n клеток.

Для задания ПФ надо в каждую клетку занести значение функции, которое она принимает на соответствующем наборе аргументов.

Клетки, содержащие 1 (единица-клетка) –соответствует определенному минтерму. Если в соседних клетках содержится 1, то надо объединить соответствующие минтермы в имбликаты. Такое объединение клеток эквивалентно операции склеивания минтермов, получается более простое выражение для ПФ.

Объединенные клетки будут соответствовать имбликатам, дизъюнкции которых содержат сокращенную ДСНФ:

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

создание и развитие средств связи, особенно беспроводной.

Возникновение и развитие авиации и космической техники. Современные летательные аппараты по своим техническим и конструктивным характеристикам не сопоставимы с первыми летательными аппаратами.

Но наиболее разительный прогресс произошел в области вычислительной техники. (ок 50 лет назад первые ЭВМ имели вез ок. 30 тонн, площадь ок. 200м 2 )

время выполнения вычислений измерялось часами или сутками.

Теперь ЭВМ можно разместить на кремниевом кристалле S=5мм 2 , время выполнения расчетов – микросекунды, стоят мало.

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

Появление первой машины для выполнения четырех арифметических действий дотируется началом 17 в. (1623 г В. Шикард изобрел мех. машину сложения, вычитания, частично умножения и деления), но более известным оказался настольный арифмометр (1642г.) франц. ученым Паскалем. 1671г. Лейбниц изобрел т.н. зубчатое колесо Лейбница, позволяющее выполнять 4 арифметические операции.

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

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

Источник

Способы представления переключательных функций

ЛАБОРАТОРНАЯ РАБОТА № 1

Краткие теоретические сведения

Маршрут проектирования цифровых устройств на базе ПЛИС фирмы Xilinx

Для создания цифрового устройства на базе ПЛИС Xilinx необходимо выполнить следующую последовательность операций:

1) создать новый проект, указав серию, тип ПЛИС и средств синтеза;

2) разработать описание проектируемого устройства в схемотехнической (с использованием схемотехнического редактора), алгоритмической (с использованием графа состояний конечного автомата) или текстовой (с использованием языков описания аппаратуры – hardware description languages, HDL) формах;

3) выполнить синтез устройства;

4) провести проверку проекта методом функционального моделирования;

5) выполнить размещение и трассировку проекта в кристалл;

6) провести окончательную верификацию проекта методом временного моделирования;

7) загрузить конфигурационные данные проекта в кристалл (выполнить программирование ПЛИС).

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

Программирование ПЛИС с помощью языка VHDL

К современным HDL‑языкам относятся VHDL (Very High Speed HDL) и Verilog.

Проект на VHDL состоит из макросов, на основе которых строится описание схемы в целом. Структура макроса имеет вид, показанный на рис. 1.1.

Рис. 1.1. Структура макроса, написанного на языке VHDL

Способы представления переключательных функций (ПФ)

Функция называется переключательной (булевой), если она принимает значения также как и ее аргументы, и зависит от аргументов .

Существуют следующие способы представления (ПФ):

3) указанием номеров наборов, на которых ПФ равна единице;

4) указанием номеров наборов, на которых ПФ равна нулю;

5) представление ФП в Совершенной дизъюнктивной нормальной форме (СовДНФ);

6) Представление ФП в Совершенной конъюнктивной нормальной форме (СовКНФ);

Для записи ПФ в СовДНФ используется вспомогательная функция, которая называется конституентой единицы (КЕ). Обозначение: .

КЕ – это ПФ ‑аргументов, равная единице только на одном ‑м наборе. КЕ представляет собой элементарное произведение (конъюнкцию) ‑аргументов, взятых с инверсиями или без.

СовДНФ ПФ записывается следующим образом:

1. Выписывается ряд произведений всех аргументов и соединяется знаками дизъюнкции. Число произведений равно числу единиц ПФ.

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

Для записи ПФ в СовКНФ используется вспомогательная функция, которая называется конституентой нуля (КН). Обозначение: .

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

СовКНФ ПФ образуется следующим образом:

1. Записываются конъюнкции элементарных дизъюнкций всех аргументов. Число дизъюнкций равно числу нулей ПФ.

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

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

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

Порядок минимизации ПФ с помощью карт Карно при поиске МДНФ:

1. ПФ представляется с помощью карт Карно. При поиске МДНФ нули можно не указывать.

2. Охватываются контурами «соседние» единицы карты. Число единиц в правильном контуре равно (где ). При этом требуется, чтобы контуры были максимальны по числу охватываемых единиц, а число всех контуров – минимальным. При формировании контуров некоторые контуры могут охватывать единицы из других контуров.

3. Для карт Карно трех переменных контур, содержащий одну единицу, заменяют произведением (простой импликантой), содержащей три буквы; две соседние единицы – двумя буквами; четыре соседние единицы – одной буквой; восемь единиц – ПФ константа «1».

4. Полученные произведения заменяют знаком дизъюнкции.

Порядок минимизации ПФ с помощью карт Карно при поиске МКНФ:

1. ПФ представляется в карте Карно ее нулями, единицы можно не указывать.

2. Образуются контуры, охватывающие нули.

3. Контуры, содержащие один ноль заменяются элементарной дизъюнкцией, cодержащей 4 буквы; 2 нуля – 3 буквы;4 нуля – 2 буквы;8 нулей – 1 буква.

4. Полученные элементарные дизъюнкции соединяются знаками конъюнкции.

Цель работы: изучение способов представления переключательных функций (ПФ), построение их логических схем и реализация на языке VHDL.

Исходные данные: ПФ, заданная номером (табл. 1.1).

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

Таблица 1.1. Варианты заданий

№ варианта
ПФ
№ варианта
ПФ

1) перейти от задания ПФ номером к табличному способу задания ПФ;

2) найти СовДНФ и СовКНФ ПФ по ее таблице истинности;

3) с помощью карт Карно найти МДНФ и МКНФ ПФ;

4) построить в универсальном (булевом) базисе логические схемы (ЛС) ПФ, представленных в виде МДНФ и МКНФ;

5) построить временные диаграммы работы ЛС;

6) написать программу на VHDL, реализующую МДНФ и МКНФ заданной ПФ в редакторе Xilinx ISE;

7) провести моделирование написанной программы в редакторе HDL Bencher;

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

1) название, цель работы, задание;

2) проектирование схемы в соответствии с планом задания (п.п. 1 – 6 задания);

3) результаты моделирования схемы в схемотехническом редакторе;

4) вид конфигурационной последовательности из редактора связей.

Пример выполнения работы.

Исходные данные: .

1‑й этап. Переход от задания номером к табличному способу задания ПФ.

Номер функции необходимо представить в виде степеней двойки. Так: . Каждой степени числа «2» соответствует определенный номер набора (табл. 1.2). Поэтому ПФ на 0‑м, 1‑м, 3‑м, 4‑м и 7‑м наборах принимает единичные значения, на остальных – нулевые.

Таблица 1.2. Табличное задание ПФ

№ набора				Вес набора

2‑й этап. СовДНФ и СовКНФ для ПФ, заданной в табл. 1.2, примут вид:

СовДНФ = ; (1.1)

СовКНФ = . (1.2)

3‑й этап. Нахождение МДНФ и МКНФ с помощью карт Карно.

Карты Карно для ПФ (1.1) и (1.2) показаны на рис. 1.2.

Рис. 1.2. Карты Карно для нахождения МДНФ и МКНФ функций (1.1) и (1.2)

Из карт Карно (см. рис. 1.1) найдены:

МДНФ = ; (1.3)

МКНФ = . (1.4)

4‑й этап. Построение ЛС для ПФ, представленных в виде МДНФ (1.3) и МКНФ (1.4) (рис. 1.3).

5‑й этап. Построение временных диаграмм для полученных ЛС (рис. 1.4).

6‑й этап. Написание программы на VHDL, реализующей МДНФ и МКНФ ПФ в редакторе Xilinx ISE.

Рис. 1.3. Логические схемы, соответствующие МДНФ (а) и МКНФ (б) ПФ

Рис. 1.4. Временная диаграмма для ПФ

Для запуска пакета Xilinx ISE в меню Программы следует выбрать группу Xilinx ISE, в которой нужно выделить строку Project Navigator и щелкнуть на ней левой кнопкой мыши. При этом на экране монитора появится основное окно Навигатора проекта (рис. 1.5), которое содержит кроме стандартных элементов 4 встроенных окна:

– окно исходных модулей проекта (Sources in Project);

– окно необходимых процессов для выбранного исходного модуля (Processes for Source);

– окно консольных сообщений программных модулей (Console);

– окно редактора текстовых HDL‑описаний проекта.

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

Окно процессов (Processes for Source) (рис. 1.5) показывает маршрут обработки выделенного исходного модуля в процессе проектирования устройства. В данном окне подробно отображаются все этапы процесса разработки и программирования ПЛИС. Последовательность и содержание этапов определяются типом исходного модуля и серией ПЛИС.

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

Окно интегрированного текстового редактора (рис. 1.5) становится активным, если для проектируемого устройства или используемых библиотек выбран способ описания на языке HDL.

Рис. 1.5. Основное окно Навигатора проекта пакета Xilinx ISE

Для создания нового проекта следует выполнить команду File основного меню Навигатора проекта, а затем во всплывающем меню выбрать строку New Project. При этом появится диалоговое окно, показанное на рис. 1.6.

Рис. 1.6. Создание нового проекта в САПР Xilinx ISE 6

В открывшейся диалоговой панели (рис. 1.6) нужно определить исходные данные, необходимые для создания проекта:

– название проекта (Project Name);

– диск и каталог, в котором предполагается расположить проект (Project Location);

– тип модуля верхнего уровня (Top‑Level Module Type).

Для создания проекта на языке описания аппаратуры (в том числе на VHDL) необходимо в меню Top‑Level Module Type (см. рис. 1.6) выбрать строку HDL.

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

Рис. 1.7. Параметры создаваемого проекта

В окне (см. рис. 1.7) устанавливаются следующие параметры:

– серия ПЛИС, на базе которой разрабатывается устройство (Device Family);

– тип кристалла (Device), определяющий его логическую ёмкость;

– тип корпуса (Package);

– быстродействие (Speed Grade);

– средство синтеза (Synthesis Tool);

– средство моделирования (Simulator);

– язык программирования (Generated Simulation Language).

Установив соответствующие параметры проекта (см. рис. 1.7) необходимо нажать на кнопку Далее, после чего на экране появится окно (рис. 1.8) добавления новых модулей в проект при его создании. Нажав Далее появится окно (рис. 1.9) добавления существующих модулей в новый проект.

Рис. 1.8. Окно добавления новых модулей при создании проекта

Рис. 1.9. Окно добавления существующих модулей при создании проекта

В результате нажатия в окне (см. рис. 1.9) кнопку Далее, на экране появится окно (рис. 1.10) информации о новом проекте (New Project Information). Нажав в окне (рис. 1.10) кнопку Готово, можно перейти к написанию программы.

Рис. 1.10. Окно информации о новом проекте

Для создания нового модуля исходного описания проекта следует выбрать команду New Source из раздела Project основного меню. В открывшейся диалоговой панели, показанной на рис. 1.11, необходимо выбрать тип нового модуля, записать его имя и указать место расположения файла на диске.

Для разработки функциональной схемы проекта следует в предложенном списке диалоговой панели выбрать тип создаваемого исходного модуля VHDL Module, щелкнув на соответствующей строке левой кнопкой мыши. Затем нужно активизировать поле редактирования названия модуля (файла) File Name и ввести текст имени с помощью клавиатуры. Расширение имени файла устанавливается автоматически в соответствии с выбранным типом модуля. Место расположения создаваемого модуля на диске указывается в поле редактирования Location диалоговой панели (рис. 1.11). По умолчанию предлагается рабочий каталог текущего проекта. Если флаг индикатора Add to project находится в установленном состоянии, то создаваемый модуль автоматически включается в состав текущего проекта. Установка значений всех необходимых параметров создаваемого модуля завершается нажатием клавиши Next (Далее), которая находится в нижней части диалоговой панели (рис. 1.11). При этом открывается информационная панель Define VHDL Source, показанная на рис. 1.12.

Рис. 1.11. Диалоговая панель установки параметров нового модуля проекта

Рис. 1.12. Диалоговое окно задания сигналов ввода-вывода исходного модуля

В диалоговом окне Define VHDL Source (см. рис. 1.12) задаются название модуля (поле Entity name), имя архитектуры (Architecture Name), а также входные и выходные сигналы модуля. В поле Port Name указываются названия входов и выходов, в поле Direction – их направление (in или out). Поля MSB и LSB задают разрядность многобитных сигналов (шин). На рис. 1.12 показано задание входных и выходных сигналов для ПФ в МДНФ и МКНФ. Следует отметить, что сигналы ввода-вывода в диалогом окне (см. рис. 1.12) вводить не обязательно. Их можно добавить на этапе разработки HDL‑описания. По завершении установок параметров в окне Define VHDL Source (см. рис. 1.12) следует нажать клавишу Далее. В результате этого появится окно New Source Information (рис. 1.13).

Рис. 1.13. Окно информации о новом исходном файле

Для перехода к редактированию HDL‑описания в окне (см. рис. 1.13) необходимо нажать клавишу Готово.

Разработанная программа на языке VHDL приняла вид:

library IEEE; — Раздел описания библиотек

entity lab1_vhdl is — Раздел объявления входных и выходных сигналов

Port ( x1 : in std_logic;

x2 : in std_logic;

x3 : in std_logic;

y1 : out std_logic;

y2 : out std_logic);

architecture Behavioral of lab1_vhdl is — описание переключательных функций

Источник