10665

Разработка комбинационных схем

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа №1 Разработка комбинационных схем Цель работы – приобретение навыков по составлению таблиц истинности записи логических функций минимизации логических функций и составлению комбинационных схем из простейших логических элементов. Кратки

Русский

2013-03-30

145 KB

28 чел.

Лабораторная работа №1

Разработка комбинационных схем

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

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

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

- составления таблицы истинности для входов и выходов комбинационной схемы по условию задачи;

- записи логической функции или логических функций для всех разрядов выхода;

- минимизации логических функций;

- записи логических функций в заданном базисе;

- составления функциональной схемы по логическим функциям.

1. Составление таблицы истинности

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

Пример 1.

Составить таблицу истинности устройства сравнения двух двухразрядных двоичных чисел, формирующего выход у=1, если А>B и y=0, если .  

y

A1

A0

B1

B0

Сравнение А и В в десятичных кодах*

0

0

0

0

1

0

0

0

1

1

0

0

1

1

1

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0 = 0

0 < 1

0 < 2

0 < 3

1 > 0

1 = 1

1 < 2

1 < 3

2 > 0

2 > 1

2 = 2

2 < 3

3 > 0

3 > 1

3 > 2

3 = 3

.

Пример 2. Составить таблицу истинности устройства для суммирования двух  двухразрядных двоичных чисел.

у2

у1

у0

A1

A0

B1

B0

Суммирование А и В в десятичных кодах*

0

0

0

0

0

0

0

0=0+0

0

0

1

0

0

0

1

1=0+1

0

1

0

0

0

1

0

2=0+2

0

1

1

0

0

1

1

3=0+3

0

0

1

0

1

0

0

1=1+0

0

1

0

0

1

0

1

2=1+1

0

1

1

0

1

1

0

3=1+2

1

0

0

0

1

1

1

4=1+3

0

1

0

1

0

0

0

2=2+0

0

1

1

1

0

0

1

3=2+1

1

0

0

1

0

1

0

4=2+2

1

0

1

1

0

1

1

5=2+3

0

1

1

1

1

0

0

3=3+0

1

0

0

1

1

0

1

4=3+1

1

0

1

1

1

1

0

5=3+2

1

1

0

1

1

1

1

6=3+3

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

2. Запись логических функций

Логическую функцию, заданную таблично в виде таблицы истинности, можно записать либо в виде совершенной дизъюнктивной нормальной формы (СДНФ), либо совершенной конъюнктивной нормальной формы (СКНФ). Например.

у

х3

х2

х1

0

0

0

1

1

1

1

1

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

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

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

Для записи СКНФ выбирают строки с нулевыми значениями у

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

В соответствии с этим  выражением у=0 если хотя бы одна элементарная дизъюнкция будет равна 0.

Чаще используется запись в виде СДНФ.

Составим дизъюнктивную нормальную форму по единицам у для примера 1:

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

       Для разрядов у1 и у2 примера 2:

3. Минимизация логических функций

Важнейшие законы, применяемые при преобразовании и минимизации логических функций:

- идемпотентные:

- коммутативные или переместительные:

- ассоциативные или сочетательные:

- дистрибутивные или распределительные:

- отрицания:  

                      

                      

- двойственности (теоремы де Моргана):

- двойного отрицания: ;

- поглощения:

- склеивания:

- обобщенного склеивания:

.

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

Для примера 1.

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

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

.

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

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

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

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

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

Для трех переменных матрица Карно имеет вид:

При такой адресации соседними являются клетки находящиеся на границах матрицы, в частности, на правой и левой границах, т. к. они отличаются только состоянием х3. Фактически матрица сворачивается в цилиндр с вертикальной осью.

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

Составим матрицу Карно для примера1 и запишем минимальную дизъюнктивную нормальную форму:

Как видно, она совпала с предыдущей.

Для второго разряда у из примера 2 проведем последовательное склеивание всех конъюнкций, отличающихся состоянием только одного разряда:

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

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

Составим матрицу Карно

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

4. Запись логических функций в заданном базисе

Любую функцию булевой логики можно реализовать в естественном базисе, то есть с помощью комбинаций трёх базовых функций: И, ИЛИ, НЕ. Также можно доказать, что любую логическую функцию можно реализовать комбинацией функций И, НЕ, либо функций ИЛИ,НЕ

Чтобы записать функцию в базисе И-НЕ, следует исключить операцию логического сложения ИЛИ. Для этого пользуются теоремой двойственности или де Моргана:

 

Запишем выражение у2 в базисе И-НЕ. Чтобы исключить операцию ИЛИ применим двойное отрицание к правой части логической функции для у2, что не изменит левой части, и заменим отрицание дизъюнкций элементов конъюнкцией их отрицаний:  

 

5. Составление функциональных  схем по логическим или переключательным

функциям

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

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

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

Для формирователя выхода у,  полученного согласно примера 1, комбинационная схема имеет вид:

У2 для примера 2

  

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

  1.  Ознакомиться с теоретическими сведениями.
  2.  Для выданного преподавателем условия синтезировать комбинационную схему.
  3.  Условие, таблицу истинности, СДНФ и МДНФ, полученную аналитически и по матрице Карно, функциональную схему занести в отчет.
  4.  Ответить на контрольные вопросы.

Контрольные вопросы

1.Что такое логическая функция?

2. Как записывается таблица истинности?

3. Что такое СДНФ, СКНФ ?

4. Как составить СДНФ по таблице истинности?

5. Как составить СКНФ по таблице истинности?

6. Какие логические операции вы знаете?

7. Как выполнить минимизацию СДНФ с помощью логических операций?

8. На какой логической операции базируется табличный метод минимизации?

9. Как кодируются клетки в матрице Карно?

10.Какие клетки в матрице называются соседними?

11.Какие логические элементы используются при построении комбинационных схем?

PAGE  2


 

А также другие работы, которые могут Вас заинтересовать

77731. Технологии флэш-памяти 130.5 KB
  Итак флэш-память. Вообще изобретателем считается Intel представившая в 1988 году флэш-память с архитектурой NOR. Годом позже Toshib разработала архитектуру NND которая и сегодня используется наряду с той же NOR в микросхемах флэш.
77733. Внешние запоминающие устройства (ВЗУ) и их интерфейсы 3.5 MB
  В этих устройствах могут быть реализованы различные физические принципы хранения информации магнитный оптический магнитооптический электронный в любых их сочетаниях. Устройства внешней памяти оперируют блоками информации но никак не байтами или словами как например оперативная память. Процедуры обмена с устройствами внешней памяти привязаны к типу устройства его контроллеру и способу подключения устройства к системе интерфейсу.
77735. Интерфейс НГМД 2.29 MB
  Интерфейс НГМД Интерфейс накопителей на гибких магнитных дисках НГМД является сугубо специфическим по нему передаются не байты команд и данных а сигналы управления приводом и не декодированные сырые битовые потоки данных чтения-записи. Основные функции по управлению НГМД а также по кодированию-декодированию данных выполняет контроллер расположенный на системной плате1. Все функции необходимые для использования НГМД в качестве устройств хранения данных реализованы сервисами BIOS INT 13h и ОС. Контроллер 2 FDC АТ поддерживает два...
77736. Интерфейс ATA 205 KB
  После введения в 2003 году стандарта Seril T Последовательный T традиционный T стали именовать Prllel T имея в виду способ передачи данных по 40 жильному кабелю. Это вдвое увеличивает скорость передачи данных по интерфейсу. Также введена проверка на четность CRC что повышает надёжность передачи информации. 1й регистр с адресом 0 является 16 разрядный и используется для передачи данных между диском и контроллером.
77737. Подключение жестких дисков ATA к компьютеру 112 KB
  Неправильное подключение разъемов кабеля к жесткому диску или системной плате не ведет с необходимостью к повреждению электроники диска или платы жесткий диск просто не распознается и не инициализируется BIOS. Включить компьютер и войти в SetupBIOS программу настройки BIOS бапзовой системы вводавывода нажав комбинацию клавиш высвечиваемую на экране компьютера во время его загрузки обычно клавиша Del. Сконфигурировать или убкдится в правильной конфигурации установленный жесткий диск задав параметры Type Cylinder Heds Sectors и...
77738. Интерфейс Serial ATA 278.5 KB
  Часто среди обоснований перехода на новый стандарт в статьях называют ограниченную скорость передачи параллельного интерфейса в 133 мбайт с но это ограничение конкретной его версии а не его вида вообще а у Seril T не намного и больше 150 Мбайт с. Основные причины ввода Seril T. Их решением стал новый последовательный интерфейс АТА Seril T1 пришедший на смену параллельному интерфейсу физических накопителей.
77739. Диски и контроллеры SAS 1.93 MB
  SS может использовать и большой набор разновидностей RID. Такие гиганты как dptec или LSI Logic в своих продуктах предлагают расширенный набор функций для расширения миграции создания гнёзд и других возможностей в том числе касающихся распределённых массивов RID по нескольким контроллерам и приводам. Но SS это больше нежели интерфейс следующего поколения для профессиональных жёстких дисков хотя он идеально подходит для построения простых и сложных RIDмассивов на базе одного или нескольких RIDконтроллеров. Вместе с мощными...