Задания на лабораторную работу № 1
Nbsp; Лабораторная работа №1
СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ НА УНИВЕРСАДЫШХ ЛОГИЧЕСКИХ ЭЛЕМЕНТАХ
Цель работы. Изучение методов логического синтеза комбинационных схем на элементах И-НЕ и ИЛИ-НЕ.
Комбинационные схемы
В ЦВМ информация кодируется в двоичном коде и представляется в виде множества двоичных сигналов. Каждому из последних соответствует двоичная переменная, принимавшая лишь два значения 0 и I. Отсюда следует, что любую схему в ЦВМ можно представить как функциональный преобразователь, в котором появление на входах какой-либо комбинации из нулей и единиц вызывает появление на выходах определенной комбинации из нулей и единиц. При этом выделяются два основных класса схем - комбинационные схемы (КС) и конечные автоматы.
В КС значения выходных сигналов в момент времени t однозначно определяются значениями входных сигналов в тот же момент времени. Выходные сигналы в конечном автомате зависят также и от состояния автомата, которое, в свою очередь, зависит от входных сигналов, поступивших в предыдущие моменты времени.
Технические вопросы синтеза КС решаются с помощью аппарата алгебры логики, в котором основным понятием является понятие переключательной (или булевой) функции. Переключательной функцией (ПФ) называется функция, способная принимать лишь два значения, и такая, что все ее аргументы также могут принимать только два значения. Если значения ПФ отождествить с выходными сигналами схемы, а значения ее аргументов с входными сигналами, то функция будет описывать процесс преобразования электронной схемой входных сигналов в выходные. На этом основано приложение алгебры логики к синтезу КС.
|
|
Рис. 1
Общий вид КС представлен на рис.1. Можно сказать, что эта схема реализует т переключательных функций от п аргументов (yi=fi(x1, x2, …, xn), i=1-m).
Любая сколь угодно сложная КС строится из более простых схем с одним выходом, реализующих элементарные ПФ. Эти схемы, называемые логическими элементами, должны реализовывать базис, т.е. систему ПФ, из которых с помощью операций алгебры логики может быть получена ПФ любой сложности [l].В цифровой технике наиболее широко используется булевый базис, включающий переключательные функции или операции: отрицания (операция НЕ), дизъюнкции (операция ИЛИ), конъюнкции (операция И), и универсальный базис, включающий либо операцию отрицания дизъюнкции (операция ИЛИ-НЕ), либо операцию отрицания конъюнкции (операция И-НЕ).
Рис.2 |
Операция отрицания реализуется элементом НЕ (или инвертором), значение сигнала на выходе которого равно обратному значению входного сигнала ( ). Таблица истинности и условное обозначение элемента представлены на рис.2.
|
|
Операция дизъюнкции над значениями входных сигналов (y = x1 v x2 v …v xn, n³2) выполняется элементом ИЛИ. Сигнал на выходе элемента ИЛИ принимает значение 0 только в том случае, если ни один из входных сигналов не имеет в данный момент времени значения I. Таблица истинности и условное обозначение элемента ИЛИ ( п. = 2) приведены на рис.3
Операция конъюнкции (y = x1x2 … xn, n³2) выполняется элементом И, сигнал на выходе которого равен 1, если все входные сигналы одновременно равны I. На рис.4 приведены таблица истинности и условное обозначение элемента И (п = 2).
Рис.3 Рис.4
Операцию отрицания дизъюнкции ( ) реализует элемент ИЛИ-НЕ, представляющий собой элемент ИЛИ с инверсным выходом. Операцию отрицания конъюнкции ( ) реализует элемент И-НЕ, являющийся элементом И с инверсным выходом. Таблицы истинности и условные обозначения элементов ИЛИ-НЕ и И-НЕ приведены на рис.5 и 6 соответственно.
Рис.5 Рис.6
По теореме де Моргана и . Отсюда следует, что элемент И-НЕ выполняет операцию ИЛИ над инверсными значениями входных сигналов (рис.6, в), а элемент ИЛИ-НЕ операцию И над инверсными значениями входных сигналов (рис.5, в).
|
|
Введем далее важное понятие полярности логики, являющееся связующим звеном между реальным элементом и его логической функцией. Под полярностью логики понимается уровень сигнала (положительный или отрицательный, высокий или низкий), который соответствует логической единице. Уровни электрического потенциала, представляющие I и 0, не относятся к существенным характеристикам элементов, а выбираются перед началом логического синтеза. Так, например, элементы диодно–транзиоторной (ДТЛ) и транзисторно-транзисторной логики (ТТЛ) выполняют операцию И-НЕ только в том случае, если в качестве уровня единицы принят более высокий потенциал (положительная логика). Если же выбрать в качестве сигнала единицы низкий потенциал (отрицательная логика), то те же элементы будут реализовывать операцию ИЛИ-НЕ. Пусть, например, имеется элемент, выполняющий в положительной логике операцию И-НЕ . При изменении полярности логики (в качестве сигнала I выбирается более низкий уровень потенциала) на входы элемента будут поступать инверсные (обратные) значения ( переменных х1, х2, хn, а с выхода будет снижаться обратное значение функции у. Так как функция элемента, определяемая его структурой, сохраняется, то справедлива следующая подстановка в выражение Преобразуя последнее выражение в следующем порядке: , убеждаемся, что элемент реализует операцию ИЛИ-НЕ в отношении переменных х1, х2, …, хn.
|
|
Характеристика комбинационных схем. На рис.7 представлена КС, реализующая на элементах булевого базиса систему двух ПФ: . Как видно, в КС значения входных сигналов определяются путем последовательного преобразования входных сигналов в промежуточные и промежуточных - в выходные, т.е. путем многоуровневого преобразования.
При определении уровней КС используется правило: каждый элемент i-го уровня (i > I) должен иметь хотя бы один вход, подключенный к выходу элемента (i - 1)-го уровня. Нулевой уровень составляют входы КС, первый уровень - элементы, на все входы которых поступают сигналы непосредственно с входных проводов КС. Обратная связь, т.е. подключение выхода элемента какого-либо уровня ко входу элемента того же или младшего уровня, не допускается. Таким образом, число уровней r в КС равно максимальному числу элементов, проходя через которые сигнал от входа КС достигает ее выхода. Если на любом элементе сигнал задерживается на время t0, то значение D =rt0 будет определять быстродействие КС.
Сложность КС характеризуется суммарным числом S входов элементов, составляющих схему. В схеме рис.7 r = 5, S= 13.
Важными характеристиками системы элементов, используемых при построении КС, являются коэффициент объединения J и коэффициент разветвления F .
Коэффициент объединения J задает максимальное число входов элемента, т.е. максимальное число элементов, выходы которых могут быть объединены через входы данного. Одной из мер, позволяющих удовлетворить требуемое значение J в синтезируемой КС, является разделение входов с помощью дополнительных элементов. Процесс разделения входов при 7s 2. поясняетсясхемами на рис.8, а (для случая реализации в булевом базисе функции у1=х1х2х3х4) и 8, б (для случая реализации в базисе И-НЕ функции ). В первом случае используется преобразование: у1=х1х2х3х4=(х1х2)(х3х4), и вместо элемента И с четырьмя входами в КС вводятся 3 элемента И с двумя входами. Во втором случае вместо одного элемента И-НЕ
Рис.8
с четырьмя входами применены 5 элементов И-НЕ с двумя входами. Здесь .
Коэффициент разветвления задает максимальное число входов элементов, которые можно соединить с выходом данного элемента, не вызывая искажений сигналов 0 и I, превышающих заданные пределы. Если в КС оказался перегруженным какой-либо элемент, то принимаются меры к его разгрузке. Разгрузка может
Рис.9
выполняться дублированием выходного сигнала или дублированием элемента. Пусть F=4 и к выходу некоторого элемента А необходимо подключить 7 входов других элементов. Дублирование сигнала осуществляется по схеме рис.9, а. с помощью двух инверторов I и II . Недостатком способа является увеличение задержки сигналов в схеме. От этого недостатка свободен способ разгрузки дублированием элемента (рис.9.б).
Синтез КС на элементах универсального базиса сводится к выполнению следующих этапов: представление реализуемых ПФ в булевом базисе; минимизации ПФ; перевод минимальных выражений в базис И-НЕ либо ИЛИ-НЕ; построение КС с учетом требуемых значений J, F, D .
Порядок выполнения работы
Содержанием работы является: синтез КС, удовлетворяющей заданным требованиям, набор схемы на макете и контроль правильности ее работы.
Работу рекомендуется выполнять в следующей последовательности:
- представить заданную преподавателем систему из одной или нескольких ПФ в булевом базисе;
- получить минимальные нормальные формы для ПФ;
- перевести минимальные выражения в базис И-НЕ и ИЛИ-НЕ;
- на основе полученных выражений составить функциональные схемы (с учетом требуемых значений У , F- и S ) и выбрать из них минимальную;
- набрать схему на макете и подключить ее выход к гнезду "Контроль";
- проверить правильность синтезированной схемы, задавая на ее входах всевозможные наборы значений переменных.
Задания на лабораторную работу № 1
Вариант | F=V(...................) | Не определены |
1. | 0,2,4,8,10,12,14 | 1,9,13 |
2. | 0,3,4,8,10,13 | 2,6,14,15 |
3. | 0,2,5,8,11,12,14 | 1,4,7 |
4. | 0,2,4,9,10,12 | 3,7,13,15 |
5. | 0,2,3,5,7,8,11 | 4,6,14 |
6. | 0,3,5,7,12,15 | 6,9,10,13 |
7. | 0,4,8,9,11,13,15 | 2,3,10 |
8. | 0,4,6,8,10,13 | 2,7,11,14 |
9. | 0,3,5,8,10,12,13 | 2,6,11 |
10. | 0,4,5,7,9,13 | 3,6,8,11 |
11. | 0,1,3,5,8,11,15 | 7,9,12 |
12. | 0,1,4,7,10,12 | 2,3,8,13 |
13. | 0,1,5,6,10,12,14 | 3,7,9 |
14. | 0,1,5,7,9,13 | 4,6,14,15 |
15. | 0,2,5,9,10,12,15 | 3,8,13 |
16. | 1,6,9,11,13,15 | 2,4,12,14 |
17. | 1,2,6,9,11,14,15 | 3,10,12 |
18. | 1,3,7,9,10,14 | 2,5,11,15 |
19. | 1,3,5,8,10,12,14 | 4,9,13 |
20. | 1,3,6,11,13,15 | 2,6,9,14 |
21. | 1,4,6,8,10,12,13 | 3,7,11 |
22. | 1,5,6,7,9,15 | 2,3,8,10 |
23. | 1,6,7,8,10,11,15 | 3,8,14 |
24. | 1,2,4,5,7,13 | 6,8,10,15 |
25. | 1,3,8,9,11,14,15 | 4,6,10 |
26. | 1,7,9,12,14,15 | 2,3,5,10 |
27. | 1,5,7,10,11,13,14 | 0,3,8 |
28. | 1,2,7,9,10,12 | 0,5,6,13 |
29. | 1,2,7,8,10,12,14 | 3,11,15 |
30. | 1,3,5,9,13,15 | 0,6,10,12 |
31. | 2,3,5,8,11,13,14 | 1,4,10 |
32. | 2,6,8,9,11,13 | 7,10,12,15 |
33. | 2,5,7,8,10,12,15 | 0,6,11 |
34. | 2,4,8,9,12,13 | 1,5,10,14 |
35. | 2,3,7,9,11,14,15 | 4,5,10 |
36. | 2,5,6,9,10,12 | 1,7,8,15 |
37. | 2,4,6,8,13,14,15 | 0,9,10 |
38. | 2,5,9,11,13,15 | 1,6,7,10 |
39. | 2,3,4,6,8,10,12 | 0,5,9 |
40. | 2,3,6,9,12,13 | 1,4,8,14 |
41. | 2,3,7,9,11,13,15 | 0,8,10 |
42. | 2,4,7,9,11,14 | 5,8,10,15 |
43. | 2,5,8,9,11,13,15 | 1,6,7 |
44. | 2,4,8,10,13,15 | 0,5,9,14 |
45. | 3,5,8,10,11,13,15 | 1,6,12 |
46. | 2,6,7,10,12,14 | 0,8,11,15 |
47. | 3,4,6,7,9,12,14 | 5,8,10 |
48. | 3,5,7,8,13,15 | 4,6,9,11 |
49. | 3,4,6,9,10,13,14 | 1,5,8 |
50. | 3,6,8,9,11,13 | 0,7,10,15 |
51. | 3,6,7,10,12,13,15 | 4,5,9 |
52. | 3,7,8,10,12,15 | 1,4,9,13 |
53. | 3,4,5,7,9,11,13 | 6,10,14 |
54. | 3,7,9,11,12,15 | 0,5,10,13 |
55. | 3,5,6,9,10,12,14 | 1,7,11 |
56. | 4,5,7,9,11,12 | 1,3,8,14 |
57. | 4,6,7,9,12,14,15 | 0,2,5 |
58. | 4,8,10,12,13,15 | 1,3,7,11 |
59. | 4,6,8,10,11,13,14 | 1,3,9 |
60. | 4,8,9,11,13,14 | 0,3,10,15 |
Порядок выполнения работы
1. Произвести кодирование состояний, входных и выходных сигналов абстрактного автомата, заданного графическим или табличным способом.
2. Составить кодированную таблицу переходов, таблицу кодированных выходов и таблицу функций возбуждения триггеров заданного типа.
3. Получить минимальные выражения для функций кодированных выходов и функций возбуждения триггеров в булевом базисе.
4. Полученные выражения перевести в заданный универсальный базис.
5. Построить синхронизированную схему автомата в заданном базисе.
6. Набрать на макете схему автомата.
7. Используя в качестве синхронизирующих сигналы с кнопки "Такт I", проверить работу автомата в соответствии с таблицами переходов и выходов.
Примеры выполнения заданий на лабораторную работу
Синтез КС с одним выходом.
Представление реализуемой ПФ в рулевом базисе. По таблице истинности ПФ может быть получена совершенная дизъюнктивная нормальная форма (СДНФ) записи функции [1]. Для получения СДНФ нужно выписать произведения, соответствующие наборам значений аргументов, при которых функция обращается в I. При этом, если в данном наборе аргумент хi = I, то он вписывается в соответствующее произведение без изменения; если же хi = 0, то в произведение вписывается его отрицание . Все полученные произведения соединяются между собой знаками дизъюнкций. Для ПФ, заданной таблицей, можно записать СДНФ:
х1 | х2 | х3 | х4 |
0 0 0 0 1 1 1 1 | 0 0 1 1 0 0 1 1 | 0 1 0 1 0 1 0 1 | 0 0 0 1 1 1 0 0 |
Каждое из полученных произведений равно I только при определенном наборе значений всех аргументов функции и носит название минтерма.
Преобразуем полученную СДНФ следующим образом: . Такая дизъюнкция произведений, члены которой могут и не быть минтермами, называется дизъюнктивной нормальной формой (ДНФ). ДРФ, содержащая минимальное число букв, называется минимальной ДНФ (МДНФ).
ПФ может быть определена также и нулевыми ее значениями. Так, рассматриваемая функция (см. таблицу) равна 0, если равно I любое из произведений: ,т.е. . Или в соответствии с правилом де Моргана . Каждая дизъюнкция полученного произведения равна 0 только при определенном наборе значений всех аргументов функции и носит название макстерма. Форма представления ПФ в виде произведения макстермов есть совершенная конъюнктивная нормальная форма (СКНФ).Путем склеивания членов полученной СКНФ [l], можно получить выражение: . Такое произведение дизъюнкций, члены которого могут и не быть макстермами, есть конъюнктивная нормальная форма (КНФ). КНФ, содержащая минимальное число букв, называется минимальной КНФ (МКНФ).
Минимизация ПФ. Существуют различные методы, позволяющие получать МДНФ и МКНФ функций [l - 3]. Для функций с небольшим числом переменных (до 5-6) наиболее удобным методом минимизации является метод диаграмм Вейча, основанный на использовании операции склеивания: . Диаграмма Вейча является графическим представлением совокупности всех минтермов для данного числа переменных. Каждый минтерм изображается на диаграмме в виде клетки. Диаграмма образуется путем такого расположения клеток, при котором минтермы, находящиеся в соседних клетках, отличаются значением одной переменной.
Диаграммы Вейча для функций двух, трех и четырех переменных представлены на рис.11. В каждой из диаграмм наборы значений переменных, указанных по обе стороны диагональной черты в левом верхнем углу диаграммы, представлены о внешней стороны соответствующего столбца или строки, вдоль которых эти переменные остаются постоянными. Минтермы функции отмечаются единицами в соответствующих клетках диаграммы. Минтермы, не входящие в функцию, отмечаются в клетках нулями (либо клетки оставляются пустыми).
Рис.11
На основании операции склеивания два минтерма, находящиеся в соседних клетках, можно заменить одним произведением, содержащим на одну переменную меньше. Если соседними являются две пары минтермов, то такая группа из четырех минтермов заменяется произведением, уменьшенным на две переменные. В общем случае наличие единиц в 2п соседних клетках позволяет исключить п переменных.
Следует заметить, что в диаграммах соседними считаются также крайние клетки каждого столбца или строки, так как расположенные в них минтермы отличаются значением одной переменной.
Минимизация ПФ с помощью диаграммы сводится к такому объединению всех соседних единиц в группы, при котором каждая группа содержит максимальное число единиц, а количество групп минимально. Практически минимизацию выполняют следующим образом. Каждую группу единиц накрывают овалом (рис.12). Каждому овалу ставят в соответствие произведение, в котором отсутствуют переменные, изменяющие в данном овале свои значения. Переменная или ее отрицание остается в произведении, если она сохраняет в овале единичное или нулевое значение соответственно. При этом удобно пользоваться обозначениями переменных и их отрицаний, проставленными вне поля диаграммы. При минимизации следует иметь в виду, что одна и та же клетка диаграммы может накрываться несколькими различными овалами.
Рис.12
Для функций, диаграммы которых представлены на рис.12, можно получить следующие МДНФ: .
Диаграмма Вейча позволяет получить и МКНФ функции. Для этого сначала получают МДНФ для отрицания функции , объединяя на диаграмме пустые клетки. Так, из рис.12,б следует, что . Далее с помощью правила де Моргана получают МКНФ функции f. Для функции рис.12,в МКНФ имеет вид и является более простой, чем МДНФ.
Реализация ПФ на универсальных элементах. После нахождения МДНФ и МКНФ функции, реализуемой на элементах универсального базиса, в полученных выражениях осуществляется переход к базисам И-НЕ либо ИЛИ-НЕ.
Переход к базису И-НЕ. Представим операции НЕ, И и ИЛИ в базисе И-НЕ:
Отсюда следуют правила перехода: инверсия осуществляется подачей аргумента на элемент И-НЕ; конъюнкция реализуется подачей аргументов на элемент И-НЕ с последующей инверсией; дизъюнкция выполняется инвертированием аргументов с последующей подачейих на элемент И-НЕ.
Рис.13
В общем случае на свободные входы элемента И-НЕ должны быть поданы либо константы "I", либо подключены уже используемые в элементе входные сигналы (рис.13).В лабораторном макете сигналы на свободных входах элементов И-НЕ соответствуют константе "I", поэтому эти входа можно оставить незадействованными (на схемах свободные входы можно не показывать).
Преобразуем МДНФ и МКНФ функции (рис.12,б). Здесь и в дальнейшем предполагается, что исходные переменные КС поступают в парафазном коде (т.е. каждая переменная хi поступает по двум проводам: по одному – прямое значение хi, по другому - инверсное ).
МДНФ: .
Соответствующая КС приведенана рис.14, а. Здесь число уровней r = 2, число входов элементов S=9.
МКНФ:
Соответствующая КС приведена на рис.14,б. 3десь r =3, S =.12.
Из примера видно, что реализация на элементах И-НЕ МДНФ функции приводит к двухуровневой схеме, реализация МКНФ – трехуровневой схеме.
Переход к базису ИЛИ-НЕ
Правила перехода: инверсия реализуется подачей аргумента на элемент ИЛИ-НЕ; конъюнкция получается инвертированием аргументов с последующей подачей их на элемент ИЛИ-НЕ; дизъюнкция выполняется подачей аргументов на элемент ИЛИ-НЕ с последующей инверсией.
В общем случае на свободные входа элементы ИЛИ-НЕ должны быть подана либо константы 0 , либо подключены уже используемые в элементе входные сигналы. В лабораторном макете сигналы на свободных входах элементов ИЛИ-НЕ соответствуют константе 0 , поэтому эти входы можно оставить незадействованными (на схемах свободные входы можно не показывать).
Преобразуем МДНФ и МКНФ функции рис.12,б.
МДНФ:
В соответствующейсхеме (рис.15,а) r = 3, S = 10.
МКНФ:
В соответствующей схеме (рис.15,б) r = 2, S = II. Как видно, реализация на элементах ИЛИ-НЕ МДНФ функции приводит к трехуровневой схеме, реализация МКНФ - к двухуровневой схеме.
Рис.15
Из четырех схем, реализующих функцию рис.12,б .предпочтителен вариант на рис.14, а ( г = 2, S = 9). Если же в КС необходимо использовать элементы ИЛИ-НЕ и допускается использование трехуровневой схемы, то следует выбрать вариант на рис.15, а. (г = 3, S= 10), и т.д. В общем случае выбирается вариант КС, который при заданных значениях J и F является оптимальным в смысле минимума используемого в схеме оборудования при выполнении ограничений на быстродействие КС.
Следует также иметь в виду, что синтезируемые схемы часто можно дополнительно упростить, применяя скобочные формы представления функций [3]. Скобочные формы в булевом базисе получают путем вынесения за скобки общих частей нескольких произведений (в ДНФ) или нескольких дизъюнкций (в КНФ). Так, например, получим скобочную форму из МДНФ функции рис.12, а. :
.
Переведем МДНФ и скобочную форму в базис И-НЕ.
Скобочная форма:
Схемы, реализующие МДНФ ( r = 2, S = 9) и скобочную форму ( r = 3, S = 8), приведены на рис.16. Схема рис.16, б не только проще, но и требует лишь двухвходовых элементов. Но в любом случае скобочные формы приводят к увеличению числа уровней r в схеме.
На практике к скобочным формам прибегают, наряду с разделением входов, для получения схем, удовлетворяющих требуемому
Рис.16
значению коэффициента J[3]. При этом разделение входов используется в последнюю очередь, либо сопровождается увеличением числа входов S в КС.
Синтез КС со многими выходами
Задачу синтеза схемы с m выходами, работа которой описывается системой из т функций, можно свести к задаче синтеза КС с одним выходом, если каждую из функций реализовать отдельно. При этом получаем искомую схему с т выходами, состоящую из т независимых КС. Однако в общем случае схему можно существенно упростить, объединив участки схемы, реализующие одинаковые выражения в уравнениях нескольких функций.
Общая идея минимизации схем со многими выходами сводится к получению таких выражений для совокупности переключательных функций, в которых оптимально используются члены, общие для нескольких функций [I].
Рис.17
Пусть, например, требуется построить двухуровневую КС, реализующую на элементах булевого базиса систему трех функций, заданных в ДНФ. Диаграммы Вейча функций представлены на рис.17. При раздельной минимизации можно получить следующие МДНФ функций: . Схема, построенная по этим выражениям, будет содержать 24 входа элементов (S = 24). В то же время можно построить искомую схему с S = 21, если согласно рис.18 представить функции в виде следующих ДНФ:
При этом предполагается, что любой из дизъюнктивных членов , повторяющихся в выражениях для нескольких функций, будет реализовываться одним элементом, общим для этих функций.
Рис.18
Синтез схем с многими выходами, оптимальных по количеству оборудования, связан с практически неосуществимым перебором большого числа вариантов схемы. Известные методы синтеза [l,3] позволяют сократить перебор, однако при этом получаются не оптимальные, а только в той или иной степени близкие кним схемы.
Содержание отчета
1. Представление реализуемых ПФ таблицами истинности и диаграммами Вейча.
2. Получение минимальных нормальных форы ПФ.
3. Переход к базисам И-НЕ и ИЛИ-HЕ.
4. Функциональные схемы на элементах И-НЕ и ИЛИ-НЕ
Дата добавления: 2018-05-12; просмотров: 442; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!