Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2004
Тип роботи:
Навчальний посібник
Предмет:
Схемотехніка комп’ютерів
Група:
К
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
"ЛЬВІВСЬКА ПОЛІТЕХНІКА"
Лукащук Л. О.
Схемотехніка логічних та послідовнісних схем
(навчальний посібник з курсу "Схемотехнiка комп` ютерів")
Львiв 2004
К 681.142.6
Схемотехніка логічних та послідовнісних схем (доцент кафедри АСУ, доцент, кандидат технічних наук Леонід Олексійович Лукащук, НУ”ЛП”, 2004- ( Ac)
Розглянутi питання проектування логічних та послідовнісних схем. Значна увага придiлена синтезу різномонітних схем цифрової техніки та боротьбi з завадами, що виникають внаслiдок ефекту змагань.
Призначений для студентів факультету комп’ютерних та інформаційних технологій ( спеціальності 0804) та інженерно-технічних працівників відповідного профілю.
Вiдповiдальний за випуск
Доцент, к.т.н. Шпак З.Я.
Рецензенти:
професор, д.т.н. Ткаченко Р.О.
доцент, к.т.н. Вітер Ю.С.
Львів, НУ ”ЛП”, 2004.
ЗМІСТ
Зміст
3
Вступ
4
1.Логічні схеми
5
Алгебра логiки Буля (короткий словник)
5
Визначення та представлення логiчних функцiй
6
Методи мiнiмiзацiї логiчних функцiй
7
Метод мінімізації карт Карно (К-метод)
7
Метод мiнiмiзацї Квайна Мак-Класкi (КМК-метод)
10
Компенсація гоночних завад в логічних схема
20
Використання мультиплексорів для відтворення логічних функцій
26
2.Послідовнісні схеми
32
Синтез асинхронних RS - тригерів як АПС
32
Синхронні тригери
36
Синхронний одноступеневий RS – тригер з прямим управлінням
37
Синхронний одноступеневий RS – тригер з інверсним управлінням
38
Синхронний двохступеневий RS – тригер з прямим управлінням
39
Установочні входи тригера
40
JK - тригери
41
D - тригери
41
T- тригери
42
Синтез синхронних послідовнісних схем
44
Синтез структури регістрів та лічильників як СПС
44
Синтез структури регістрів
45
Синтез структури лічильників
48
Інтерфейсні схеми
55
Зведені правила проектування ПС
62
3.Проектування управляючих та функціональних вузлів комп`ютерів, постановка задачі
69
Розробка блок-схеми алгоритму операції (додавання)
71
Граф цифрового автомата
74
Вибір тригерів для ЦА та кодування станів
74
Розробка структурної схеми управляючого автомата
75
Вибір логічних елементів та інтегральних схем
76
Розрахунково-графічна робота № 1
80
Розрахунково-графічна робота № 2
82
Розрахунково-графічна робота № 3
84
Література
87
Вступ
Логічні схеми є основою цифрової технiки. Теоретичною основою їх проектування є алгебра логiки, яка є окремою математичною дисциплiною чи складовою частиною математики, що вивчається студентами кiбернетичних спецiальностей на молодших курсах. Роздiл схемотехнiки комп`ютерів “Логічні схеми” базується на основних положеннях алгебри логiки, трансформуючи їх в iнженернi методи проектування з врахуванням реальних характеристик логiчних елементiв.
В учбовому посібнику детально викладенi два основних методи синтезу логiчних схем - метод карт Карно (К-метод) i Квайна-Мак Класкi (КМК-метод) і розв`язано ряд типових прикладiв, кожен з яких демонструє тi чи iншi особливостi проектування.
Важливим є роздiл "Компенсація гоночних завад в логічних схемах", де детально розглянутi питання виникнення завад, що виникають внаслідок ефекту перегонів, i способiв боротьби з ними.
Послідовнісна схема ( ПС ) має в своєму складі логічні і запам’ятовуючі елементи. До ПС можна віднести, практично, всі вузли цифрової техніки, що не відносяться до комбінаційних схем.
В посібнику розглядаються питання асинхронних і синхронних ПС ( АПС і ПС ). В якості прикладів синтезу ПС приведені такі вузли цифрової техніки, як тригери, багатофункціональні регистри та лічильники, інтерфейсні та інші схеми. Як результат цього викладені зведені правила проектування послідовнісних схем.
В останньому розділі викладені питання проектування пристроїв та вузлів цифрової техніки в плані виконання студентами розрахунково – графічних робіт та запропоновані відповідні завдання.
В основу учбового посібника покладений матеріал, що використовується автором при читаннi курсу "Схемотехнiка комп`ютерів" для студентiв кiбернетичних спецiальностей.
Логічні схеми
Алгебра логiки Буля (короткий словник).
Логiчна змiнна - змiнна, що може приймати тiльки одне iз значень - нуль або одиницю.
Логiчна функцiя - функцiя логiчних змiнних, є також логiчною змiнною.
Логiчний вираз - сукупнiсть логiчних змiнних i операцiй, що об`єднують змiннi.
Стандартна сума - сума р-термiв.
Р-терм - повний добуток аргументiв логiчної функції, де кожний аргумент представлений безпосередньо або своїм доповненням. Аналогiчно р-термовi може бути визначене таке поняття як конституєнта.
S-терм - повна сума аргументiв логiчної функції, де кожний аргумент представлений безпосередньо або своїм доповненням.
Стандартний добуток - добуток S-термiв.
Мiнiмiзована логiчна функцiя - функцiя, що немає надлишкових членiв i змiнних.
Мiнiмальна логiчна сума (добуток) - мiнiмiзована функцiя.
Простi iмплiканти - члени мiнiмiзованої логiчної функції:
Наведений короткий словник дає змогу читачевi пригадати основнi термiни iз алгебри логiки, що використовуються в посібнику при розглядi питань мiнiмiзації логiчних функцiй i є важливим роздiлом схемотехнiки комп`ютерів Детальне викладення теорії алгебри логiки є в численнiй лiтературi. Зокрема, в кожнiй iз праць, розмiщених в роздiлi "Лiтература", в тiй чи iншiй мiрi викладенi питання теорії алгебри логiки. Особливий iнтерес представляє переклад книги С.Колдуелла, виданої в 1958 р., що вийшла в перекладi на росiйську мову в 1962 р.[Л.5]. Вона в значнiй мiрi i сьогоднi не втратила свого значення. Викладений в нiй матерiал вiдрiзняється яснiстю, простотою i фундаментальнiстю.
Визначення та представлення логiчних функцiй.
Логiчна функцiя повнiстю визначається таблицею iстинностi.
В таблиці істинності в однiй iз чотирьох можливих комбiнацiй аргументiв функцiя невизначена (Табл. 1.1). У вiдповiдному рядку стоїть лiтера d. Це, як правило, значить, що ця комбiнацiя аргументiв (в прикладi АВ`) не може мати мiсця. Тому можна вважати, що тут є одиниця або нуль Це використовується при мiнiмiзації.
На основi таблицi iстинностi можна записати вiдповiдну їй функцiю - синтез по одиницях (1.1) або її доповнення - синтез по "0" (1.2):
F=A'B'+AB, (1.1)
F'=A'B+AB'; (1.2)
Якщо прийняти, що АВ' = 1,то логічні функції запишуться так:
F = A'B' + AB + AB'; (1.3)
F'=A'B. (1.4)
Примітка. Тут і далі для познчення заперечення деякої логічної змінної або виразу X використовується один із наступних рівноцінних записів:
X' або .
Широко використовується запис, в якому кожна кон'юнкцiя представляється у виглядi терма з iндексом (номером), що вiдповiдає двiйковому числу – номеру терма або просто двійковому номеру p – терма.Такий запис здійснюється так, як показано в наступних прикладах:
F=P0+P3=((P0,P3)=((0,3), (1.5)
F=P1+P4=((P1,P2)=((1,2), (1.6)
і вiдповiдно до вищенаведеного прикладу:
F=P0+P2+P3=((P0,P2,P3)=((0,2,3), (1.7)
F`=P1=((P1)=((1) . (1.8)
Методи мiнiмiзації логiчних функцiй.
Існує декiлька методiв мiнiмiзації. Найбiльш популярними з них є два такі методи: карт Карно (скорочено, тут К-метод) i Квайна i Мак-Класкi (тут КМК-метод). Цi методи перекривають всi можливi потреби. К-метод наочний, але ж його застосування ефективне для функцiй з числом аргументiв не бiльшим 4-5. КМК-метод перекриває весь можливий дiапазон логiчних функцiй i може вiдносно легко бути запрограмований з метою його автоматизації.
Метод мiнiмiзації з допомогою карт Карно (К-метод).
Для заданої функції складається таблиця, кожна клiтка якої вiдповiдає однiй з можливих комбiнацiй її аргументiв, наприклад, таблиця (1.2.). Ця таблиця відповідає функції чотирьох змінних і є картою Карно. Карти Карно для функцій з іншою кількістю змінних мають інший вигляд і подаються нижче.
В клiтках, що вiдповiдають комбiнацiям значень аргументiв, при яких функцiя дорiвнює одиницi, проставленi вiдповiдно одиницi, нулю - нулi або нiчого не проставлено, не визначена - перекресленi нулi або буква d.
До порядку нумерації рядкiв i стовбців у картi Карно є така вимога: номери двох сумiжних рядкiв чи стовбців повиннi вiдрiзнятись тiльки в одному з розрядiв. Ця вимога виконується i для крайнiх рядкiв i стовбців, тому вони також є сумiжними.Ця вимога є прямим наслідком наступногоного правила алгебри логіки, на якому грунтується розглядуваний метод карт Карно або, як тут прийнято, К – метод, а саме:
RX+RX'=R, (1.9)
R – будь яка комбiнацiя булевих змiнних.
Враховуючи прийнят в карті Карно позначення аргументів (табл.1.2), наступну задану функцію можна представити так:
F = ((1,3,4,(5),6,7,(11),(15)) = A'B'C'D + A'B'CD + A'BC'D' +
(A'BC'D) + A'BCD' + A'BCD + (AB'CD) + (ABCD) (1.10)
У цій функції члени, що відповідають її невизначеним значенням, взяті в дужки.
Правило (1.9) застосовується так:
1) Сумiжнi клiтки з однаковими значеннями функції об'єднуються в прямокутники, кожна сторона якого має одну або парну кiлькiсть клiток. При цьому слiд прагнути одним прямокутником охопити, по можливостi, бiльше клiток. Об'єднуючи клiтки з одиницями, шукають мiнiмiзоване значення функції, а при об'єднаннi клiток з нулями - її доповнення. Клiтка з невизначеним значенням функції може бути вiднесена як до одиниць, так i до нулiв, а може залишатись i незайманою.
2) Мiнiмiзований вираз має стiльки складових, скiльки утворено прямокутникiв, плюс одна складова на кожну одиницю (нуль), що не увiйшла нi в один iз прямокутникiв.
Кожна складова є кон'юнкцiя всiх аргументiв, що залишаються незмiнними в межах кожної сторони прямокутника, яка охоплює одиниці (нулі) в межах таблиці істинності.
Звiдси очевидний висновок, що потрiбно прагнути до збiльшення розмiрiв вищеназваних прямокутникiв.
У таблиці 1.3 показанi можливi способи мiнiмiзації функції F та її доповнення F', в результатi чого отримано
F = A' B + A' D і F' = A + B'D'. (1.11)
Із прикладiв видно, що iз-за сумiжностi крайнiх рядкiв i стовбчикiв сумiжними є також кутовi клiтки, утворюючи окремий квадрат.
При мiнiмiзації функції п'ятьох змiнних остання розділяється на суми двох функцiй чотирьох змiнних наступним чином:
F(A,B,C,D,E)=F1(A,B,C,D)(E`+F2(A,B,C,D)(E. (1.12)
Функції F1 i F2 мiнiмiзуються так, як це показано вище. Однойменнi елементи в їх таблицях є сумiжними, що дозволяє створювати сумiснi уявнi прямокутники i визначати мiнiмiзованi складовi для функції п'ятьох змiнних. Проте це потребує певних навикiв. Тому часто дальшу мiнiмiзацiю пiсля отримання мiнiмiзованих функцiй F1 i F2 проводять аналiтичним шляхом.
Мiнiмiзацiю функції шiстьох змiнних можна проводити на основi очевидного спiввiдношення:
F (A,B,C,D,E,F ) =F1(A,B,C,D)(E`F`+F2(A,B,C,D)(E`F+
+F3(A,B,C,D)(EF`+F4(A,B,C,D)(EF. (1.13)
Але ж ясно, що це буде тiльки часткова мiнiмiзацiя, яка потребуватиме наступного етапу.
Карти Карно для мiнiмiзації функцiй двох, i трьох змiнних будують зi слiдуючим розмiщенням змiнних на сторонах таблиці:
А\B - для функції двох змiнних, А\BC - для функції трьох змiнних (табл..1.4).
Метод мінімізації Квайна-Мак-Класкі ( КМК - метод )
Функцію, що мінімізується, потрібно представити в досконалiй диз'юнктивно-кон'юктивнiй формi.тобто у виглядi суми конституєнт [1,11]. В основу першого етапу мінімізації КМК - методу покладено, як i в К-методi, правило (1.1). На завершальному другому етапi використовується правило відоме під назвою принцип поглинання,а саме:
RX+R=R, (1.14)
R – логічний вираз, в тому числі логічна змінна.
Послідовність мінімізації при застосуванні КМК – методу наступна:
Констуєнти (P – терми) представляються у виглядi двiйкових чисел i розбиваються на групи з одинаковою кiлькiстю одиниць в кожному числi.
Найменша кiлькiсть одиниць в першiй групi, найбiльша - в останнiй.
Вiд першої до останньої групи йде послідовне зростання кiлькостi одиниць.
До чисел кожних двох сусiднiх груп застосовується правило (1.1).
Пiсля перебору всiх можливих варiантiв йде порiвняння на основi принципу поглинання отриманих таким чином простих iмплiкант i конституєнт з метою виявленн зайвих iмплiкант. Зайвими виявляються такi, без яких всi конституєнти перекритi.
Бiльш детальне роз'яснення цього методу та виявлення деяких його особливостей зручно проводити паралельно з розглядом прикладів.
На рис. 1.1 представлені обидві частини мінімізації. Перша грунтується на правилі (1.1),друга – на правилі (1.14). Детальне пояснення проведеної мінімізації приведено нижче в описі розв`зку приклада 1.1.
Приклад 1.1. Потрiбно мiнiмiзувати слiдуючу функцiю:
. (1.15)
Розв'язок здiйснюється в такiй послiдовностi:
Конституєнти записуються в стовбчик у виглядi двiйкових чисел в порядку зростання кiлькостi одиниць, а злiва вiд них - їх десятковi номери. Стовбчик чисел роздiляється на групи з рівною кiлькiстю одиниць.
В прикладі є 3 групи, вони розділені прямими лініями.
В другому стовбчику, що розміщається справа від першого, записанi можливi об'єднання конституєнт. Злiва цi об'єднання позначенi вiдповiдними об’єднаннями десяткових номерів.
В пр.1.1 дальшi об'єднання неможливi, тому будується таблиця простих iмплiкант, тобто здiйснюється перехiд до другої частини методу. Використанi члени груп вiдмiчаються галочкою "(".
В таблицi вiдмiченi хрестиком перехрестя ліній конституент i простих iмплiкант у вiдповiдностi з їх десятковими номерами. Так здiйснюється фiксацiя операції поглинання. Хрестик у тих стовбчиках, де він зустрiчається один раз, обведений кружечком. Так вiдмiчаються першi базовi простi iмплiканти, тобто такi, якi не можуть бути видаленi iз загальної суми мiнiмiзованої функції.
В прикладi 1.1 проста iмплiканта (7-15) зайва, бо вона перекривається базовими iмплiкантами.
В результаті мінімальна мiнiмiзована суми дорiвнює
F=A`BD+ABC. (1.16)
Для порiвняння виконана мiнiмiзацiя також К-методом (табл.1.5).
Отриманий результат можна вважати остаточним тiльки при умовi, якщо в загальнiй схемi пристрою, для якого проектується дана логiчна схема, прийнятi такi мiри, що вона не чутлива до завади, що виникає в результатi ефекту гонок [Л.6]. В iншому випадку потрiбно прийняти мiри, щоб така завада не виникала. До цього та результатiв, отриманих в iнших прикладах, з точки зору аналiзу наявностi ефекту гонок та способiв його усунення повернемося в наступному роздiлi. А поки що розглянемо iншi характернi приклади.
Приклад 1.2 Потрiбно мiнiмiзувати функцiю
F=((0,1,4,5,6,7,8,9,10,12,14). (1.17)
Таблиця розв`язку прикладу 1.2 на етапі застосування правила 1.1.
При мiнiмiзації згiдно першої частини методу КМК тут зроблено двi iтерації, що вiдображено з допомогою слiдуючих стовбчикiв чисел (табл.1.6) :
Дальше застосування правила (1.1) не можливе. Отже, кiнцевий результат першого етапу мiнiмiзації має вигляд:
F = A`C` + B`C` + C` D` + AD` + BD` + A`B. (1.18)
Читачевi доцiльно уважно прослiдкувати за утворенням i способом запису отриманих результатiв.
В другiй частинi на основi принципу поглинання (1.14) дослiджується можливiсть дальшої мiнiмiзації. Для цього будується таблиця з координатами простi iмплiканти - конституєнти (Рис.1.2).
Кiлькiсть рядкiв дорiвнює кiлькостi простих iмплiкант, а кiлькiсть стовбчикiв - кiлькостi конституєнт. Рядки iдентифiкуються послiдовнiстю десяткових чисел - iдентифiкаторiв простих конституєнт, що перекриваються вiдповiдними iмплiкантами, а також буквенними iдентифiкаторами.
В таблиці простих імплікант стовбчики iдентифiкуються десятковими числами -- iдентифiкаторами конституєнт. На перетинi лiнії рядка з лiнiєю стовбчика, що вiдповiдає одному з десяткових номерiв простої iмплiканти ставиться хрестик "х". Якщо хрестик тiльки один на вертикальнiй лiнії, то вiн обводиться кружком i таким чином iдентифiкує базову iмплiканту першого порядку, тобто такий, який обов'язково залишиться в мiнiмальнiй сумi. Одночасно базовий iмплiкант першого порядку помiчається зiрочкою "*".
Зверху вертикальна лiнiя конституєнти перекреслена, якщо вона має хрестик на перетинi з лiнiєю базової iмплiканти. В даному прикладi всi вертикальнi лiнії перекресленi, а це значить, що базовi iмплiканти першого порядку перекривають всi конституєнти, тому остаточний результат є сумою трьох базових імплікант:
F = A`B + AD` + B`C`. (1.19)
Приклад 1.3 Мiнiмiзувати функцiю:F=((0,1,2,3,4,5,6,7,9,11,13,23,27,30,31).
В результатi першої iтерації,представленої в табл.1.7 -- 1, створений другий стовбчик ( табл 1.7 – 2), при цьому використанi всi числа (конституєнти) попередньої таблиці (табл.1.7 – 1).Всi вони вiдмiченi галочками.
В створеннi третього стовбчика (табл.1.7 -- 3) вдалося використати тiльки три першi групи попереднього стовбчика (табл.1.7 -- 2), двi останнi групи не вдалося об'єднати з iншими iмплiкантами. Частково також використаний третiй стовбчик. Всi невикористанi числа (iмплiканти) не вiдмiченi галочками.В третьому i четвертому стовбчиках (табл.1.7 -- 3 і 1.7 -- 4) є .ряд однакових iмплiкант, в яких вiдрiзняється тiльки послідовність розміщення їх десяткових номерiв. Очевидно, що це одна проста iмплiканта.
На основі аналізу отриманих в процесі мінімізації результатів будується таблиця. В даному випадку це рис.1.3,що по змісту відповідає такій таблиці.Тут горизонтальні лінії відповідають рядкам таблиці і відображають отримані в процесі попередньої мінімізації імпліканти В прикладі.1.3 є вісім імплікант – це ті “числа”,які залишились без “галочок”.Фактично таких чисел є 12.Але ж “числа”,в склад яких входять одні і ті ж конституєнти,що знаходяться на різних місцях в “числах”,відображають одну і ту ж імпліканту.Так,наприклад,”числа” (1,5,9,13) і (1,9,5,13) відображають одну і ту ж імпліканту A`D`E.
Вертикальні лінії відповідають колонкам таблиці.Кожна з цих ліній відображає одну із конституєнт.
По краях горизонтальних ліній записані числові і буквенні вирази конституєнт,що цим лініям відповідають.На верхньому краї кожної вертикальної лінії записано числовий вираз відповідної конституєнти.Їх є стільки,скільки p – термів входить в диз`юнктивно – кон`юнктивний вираз функції,що мінімізується.У прикладі 1.3 їх є 15.
Якщо імпліканта перекриває контитуєнту,а це має місце тоді,коли серед чисел іпліканти є номер конституєнти,то на перетині таких горизонтальної і вертикальної ліній ставиться хрестик.Це означає,що ця імпліканта перекриває відмічену конституєнту.
Якщо нема більше імплікант,що перекривали б цю конституєнту,то така імпліканта називається базовою
В таблицi (рис.1.3) виявлено три базових iмплiканти першого порядку (вони помiченi зiрочкою).У верхній частині вертикальна лiнія, що перекриваються тією чи іншою імплікантою, помічаються косою рисочкою (квадранти I - ІIІ).У пр.1.3 неперекритими базовими iмплiкантами першого порядку залишились дві конституенти (23 i 27).Вони можуть бути перекриті двома небазовими імплікантами,наприклад, В`CDE і DC`DE або іншою парою,що перекривають конституєнти 23 і 27.
Таким чином,мінімізована функція з прикладу 1.3 може бути представлена так:
F = (A`B`)* + (A`DE`)* + ABCD* + B`CDE + BC`DE. (1.20)
В таблицях 1.8 показаний розв'язок прикладу 1.3 з допомогою К-методу.
Прямокутники A`B` і ABCD мають місце при E = 0 і при E = 1,решту знаходяться в таблиці,що відповідає E = 1.
Логічна фнркція,отримана на основі аналізу карт Карно, співпадає з вищевиведеною логічною функцією КМК – методом.
Наступний приклад демонструє мінімізацію так званих циклічних функцій
Приклад 1.4. Мiнiмiзувати функцiю F = ( (0,1,5,7,8,10,14,15)
Список конституєнт розділяється на чотири групи,які утворюють першу колонку .Застосовуючи доцієї колонки правило виключення змінного аргумента (RX + RX` = R),створюємо наступну колонку,до якої,як це видно з отриманого результату,це правило більше не можна застосувати.тому будуємо таблицю простих імплікант (Рис.1.10),до якої в загальному випадку з метою подальшої мінімізації застосовується правило поглинання (.RX + R = R).
В цій таблиці нема базових імплікант, бо кожна конституєнта перекривається двома імплікантами.На її основі можна визначити два рівноцінні розв`язки,а саме:
F = A`B`C` + AB`D` + A`BD + ABC (1.21)
і
F* = B`C`D` + A`C`D + ACD` + BCD (1.22)
Для здiйснення мотивованого вибору того чи іншого розв`язку потрiбнi додатковi умови.
На рис.1.4 прості імпліканти першого ров`язку F відмічені зірочкою,а другого F* - хрестиком. Такi логiчнi схеми дiстали назву циклiчних [Л.5].
Для порiвняння розв'язок здiйснений також К-методом (табл..1.10).
Результат, звичайно, iдентичний. Як і в попередньому прикладі, для здійснення мотивованого вибору потрібні додаткові умови.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора