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


 

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

30024. Опытно - экспериментальная работа по формированию умений письма и письменной речи по средствам информационно – коммуникационных технологий 121.3 KB
  Информационнокоммуникационные технологии заняли прочное место в процессе обучения иностранному языку. Практика показывает что информационнокоммуникационные технологии имеют немало преимуществ перед традиционными методами обучения. Среди них можно выделить интенсификацию самостоятельной работы учащихся повышение познавательной активности и индивидуализацию обучения.
30025. Моделирование стрижек 61.22 KB
  Стрижка волос довольно сложная и серьезная операция которая требует предельного внимания и собранности. Укладка Волос это изменение структуры волоса на непродолжительное время чаще всего от мытья до мытья. В моде светлый цвет волос.
30026. Экспертиза эффективности и финансовой реализуемости инвестиционного проекта 635.15 KB
  Главным критерием оценки деятельности интерната для детейсирот является социальный эффект. В данном случае строительство интерната для детейсирот на территории Орловского района создаст рабочих мест. Для оценки эффективности предложенного в дипломе инвестиционного проекта проведем анализ положения детейсирот в Орловской области По информации Департамента образования молодежной политики и спорта в Орловской области по состоянию на 1 сентября 2012 года насчитывалось 2775 детейсирот и детей оставшихся без попечения родителей. В...
30027. Підприємство як суб’єкт господарювання в ринкових умовах 474.21 KB
  Базою для підприємства є діяльність як ініціативна самостійна так і систематична по виробництву продукції також надання послуг і зайнятість торгівлі що має за мету сприяти прибутку. Метод господарювання можна розкрити функціями що і визначають суть підприємства такі як: ресурсна організаційна та творча. Генеральну мету підприємства тобто чітко окреслену причину його існування у світовій економіці заведено називати місією. Здебільшого місією сучасного підприємства вважають виробництво продукції для задоволення потреб ринку та...
30028. Перспективы развития железнодорожного транспорта и путевого хозяйства 192.05 KB
  Владимир Иванович Якунин Президент ОАО РЖД Обеспечение перевозок безопасность пассажиров и сохранность перевозимых на железнодорожном транспорте грузов гарантируется единым производственнотехнологическим комплексом с вертикальной системой управления охватывающим 17 железных дорог 64 отделения дорог около 6000 железнодорожных станций 400 дистанций пути 220 локомотивных и 200 вагонных депо 200 дистанций...
30029. Аудит расчетов по заработной плате на примере Управления по образованию, культуре и молодежной политике 134.38 KB
  Виды формы и системы оплаты труда порядок ее начисления. Документы по учету личного состава труда и его оплаты. Методика аудиторской проверки расчетов по оплате труда. Программа проведения аудиторской проверки расчетов по оплате труда отчет аудитора.
30030. Программный комплекс «ГРАНД-Смета» 74.32 KB
  Когда были разработаны Урочные реестры по части гражданского строительства и по военным работам. был издан общий нормативный сборник Урочное положение на все общие работы производящиеся при крепостях государственных зданиях и гидротехнических сооружениях. В составе СНиП IV были представлены элементные сметные нормы ЭСН на строительные конструкции и работы.
30031. Багатоцільовий легкий броньований тягач 2.16 MB
  Вага машини 120 кН. ЗМІСТ Вступ 6 Призначення та загальний опис проектованої машини 7 Тактикотехнічна характеристика 10 Попередній тяговий розрахунок 25 Потужність двигуна і його зовнішня характеристика 26 Мінімальна швидкість руху машини.70 10 Економічна частина 76 12 Охорона праці 92 Висновки 102 Список джерел інформації 103 ВСТУП Метою даного випускного проекту бакалавра є частковий розрахунок машини із заданою масою і максимальною швидкістю легкого багатоцільового гусеничного тягача. З їх допомогою отримані...