Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Білет 13
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2011
Тип роботи:
Державний іспит
Предмет:
Інші
Варіант:
13
Частина тексту файла (без зображень, графіків і формул):
Особливості застосування методу мінімізації Квайна-Мак-Класкі-Петріка в базисі Буля.
Метод отримання скороченої диз'юнктивної нормальної форми логічної функції називається методом Квайна. При мінімізації по методу Квайна в базисі 1 передбачається, що початкова функція задана в СНДФ. Нагадаємо, що імпліканта функції - це деяка логічна функція, що обертається в нуль при наборі змінних, на яких сама функція також рівна нулю. Тому будь-якої мінтерм у складі СНДФ, або групи мінтермов, сполучених знаками диз'юнкції, є імплікантамі початкової НДФ. Первинна або проста імпліканта функції - це імпліканта типу елементарної кон'юнкції деяких змінних, ніяка частина якої вже не є імплікантой даній функції. Диз'юнкція простих імплікант, жодну з яких виключити не можна, називається тупиковій НДФ заданій функції. Деякі функції мають декілька тупикових форм. Тупикові форми, що містять найменшу кількість букв, будуть мінімальними. Завдання мінімізації по методу Квайна полягає в попарному порівнянні всіх імплікант, що входять в СНДФ, з метою виявлення можливості поглинання якоїсь змінної: Fxi Fxi = F. Таким чином, вдається понизити ранг термів. Ця процедура проводиться до тих пір, поки не залишиться жодного члена, що допускає поглинання з яким-небудь іншим термом. Терми, що піддалися поглинанню, наголошуються. Невідмічені терми є первинними імпліканти. Одержаний логічний вираз не завжди виявляється мінімальним. Тому досліджується можливість подальшого спрощення. Для цього складається таблиця, в рядках якої записуються знайдені первинні імпліканти, а в стовпцях указуються терми початкового рівняння. Клітки цієї таблиці наголошуються у випадку, якщо первинна імпліканта входить до складу якого-небудь терма. Після цього завдання спрощення зводиться до того, щоб знайти таку мінімальну кількість первинних імплікант, які покривають всі стовпці. У цьому методі використовуються операції неповного склеювання (повним склеюванням, як нам відомо, будет: xy xy = x) і поглинання (x xy = x). Вживана в методі Квайна операція неповного склеювання визначається формулою: xy xy = x xy xy.. Відмітимо, що в правій частині рівності, окрім члена ч, одержаного в результаті повного склеювання, залишаються обидва члени, що беруть участь в склеюванні. Теорема Квайна. Якщо в довершеній диз'юнктивній нормальній формі логічної функції провести всі операції неповного склеювання і потім всі операції поглинання, то в результаті виходить скорочена диз'юнктивна нормальна форма цієї функції, тобто диз'юнкція всіх її простих імплікант. Метод Квайна виконується у декілька етапів і скорочену НДФ зручно знаходити в наступній послідовності. Провести в СНДФ функції всі можливі операції склеювання констітуєнт одиниці. В результаті цього утворюються твори, що містять (n - 1) букв. Підкреслимо, що склеюватися можуть тільки твори з однаковим числом букв. Тому після цієї процедури проводиться операція поглинання, а потім виконуються всі можливі склеювання членів з (n - 1) буквою. Після цього проводиться поглинання членів з (n - 1) буквою і знов виконується операція склеювання членів з числом букв, рівним (n - 2), і т.д. На підставі вищевикладеного сформулюємо алгоритм отримання мінімальних НДФ логічній функції.
1. Логічну функцію представляють в здійсненій НДФ, застосовуючи або запис "по одиницях" функції, якщо функція задана табличний, або застосовуючи операції розгортання, правила де Морганаї і інші формули алгебри логіки, якщо функція задана в довільній аналітичній формі.
2. У одержаній здійсненій НДФ проводять всі операції неповного склеювання і поглинання. В результаті виходить скорочена НДФ заданій функції.
3. Знаходять мінімальні НДФ по імплікантной матриці. Якщо кількість членів в скороченій НДФ невелике, то можна знайти тупикові форми методом випробування членів і вибрати серед них мінімальні.
Операція неповного склеювання і поглинання для кон'юнктивної форми визначається відповідно наступними співвідношеннями:
(x + y)(x +y) = x(x + y)(x +y),
x(x + y) = x,
а формули розгортання мають вигляд:
x = (x + y)(x +y),
(x + y) = (x + y + z)(x + y +z).
Статичні та динамічні оперативні запам’ятовувальні пристрої.
Запам’ятовуючі пристрої довільної вибірки
По принципу дії вони поділяються на 2 класи:
Статичні, що можуть виконуватися на будь-якій технології
Динамічні, виконуються лише по МОН-технології
По принципу побудови пам’ять поділяється на:
із словарною організацією
із матричною організацією
Пам’ять із словарною організацією:
М=2n*m
Де m – розрядність даних
N – кількість млів, що формується на вихідному дешифраторі
РА – регістр адрес
D – дешифратор
ЗЕ – запам’ятовуючий елемент
ПЧТ – підсилювач читання
ВхРД – вхідний регістр даних
Вихід – вихідний регістр даних
Після дешифрації збуджується один з виходів цього дешифратора, який потрапляє на вхід ЗЕ цілого рядка. При читанні спрацьовує ПЧТ та інформація, що зберігається в цьому рядку фіксується у вих РД. В операції запису на вибраній словарній лінії ЗЕ по бітовим лініям подають сигнали від формувачів, зв’язаних з вхідним регістром даних. Слова з Вхід записуються у ЗЕ вибраного рядка. Як правило в ІМС вхідні і вихідні РД об’єднуються і через 2-напрямлені буферні елементи під’єднуються до ШД системи.
Пам’ять з матричною організацією
Якщо довжина слова більша 1 біту, то на кристалі розташовують кілька матриць із загальними колами від дешифратора адрес.
Елементи мікросхем оперативної пам’яті
Елемент на біполярних транзисторах
Ічит – струм читання
Аі – адрес і-го елемента
Uа – напруга, що подається на адресну шину.
На розрядну шину Рі подають опорну напругу, яка є загальною для всіх ЗЕ. Співвідношення між Uоп і Uр при наявності Ua визначає режим роботи запам’ятовуючого елементу: режим зберігання, запису та читання.
Режим зберігання Ua < (Uоп = Uр)
Схема знаходиться з однаковою стійкістю станів: VT2 відкритий і струм протікає по емітеру 1 відритого транзистора, а по емітеру 2 обох транзисторів струм не протікає.
Режим читання VT2 відкритий і струм протікає в його емітер. Щоб транслювалась інформація в розрядну шину Рі необхідно перемкнути струм емітеру, тобто закрити схему по емітеру VT1 і відкрити VT2, залишивши поперелній стна транзистора.
Напругу на адресній шині треба зробити рівною: Ua > (Uоп = Uр), тоді струм через емітер 2 перейде в Рі. Наявність струму в шині відповідає читанню „1”, а відсутність „0”. Умови режиму запису залежать від стану. В якій по Рі необхідно подати Uр>Uоп, зберігаючи Uа>Uр. При цьому тригер переходить в швидкий стан (VT2 закрито, а VT1 відкритий). Для запису в ЗЕ „1” на виході Рі необхідно подати Uр<Uоп і забезпечити Uа>Uоп. Усі елементи мають високу швидкодію (tсер = 10..70нс), та досить мале споживання потужності.
Динамічні ЗЕ
ЗЕ на МОН-транзисторах
ЗЕ на КМОН транзисторах
БЛ – бітові лінії, СЛ – словарні лінії
Якщо на VT „1” – запис інформації в СЛ, якщо ні VT „0” – читання інформації з СЛ. Головний недолік динамічного ЗЕ – конденсатор має особливість, його розряд з часом зменшується, і тому потрібно виконувати його регенерацію. Переваги – динамічні ЗЕ – прості і дозволяють будувати на їх основі ВІС
Елементи ПЗП
на діоді на МОН-транзисторі
К155РЕ5
Формати інструкцій скалярного RISC процесора. Множина інструкцій RISC процесора.
Формати інструкцій подано наступним рисунком.
Пояснення щодо форматів інструкцій.
1. I - тип інструкції опрацьовує безпосередній операнд (Immediate ).
2. R - тип інструкції отримує пару операндів із джерельних регістрів (Registers) регістрового файла процесора та повертає результат знов таки до регістру призначення цього файла. 3. J – тип є інструкцією безумовного переходу (jump). 4. Opcode є полем коду операції, довжина 6 бітів. 5. rs1,rs2 є полями з довжиною 5 бітів, що визначають номери регістрів-джерел операндів (register of source) та програмно обираються серед регістрів R0..R31 регістрового файла. 6. rd є п'яти бітовим полем номера регістра призначення, приймача результату дії (register of destination), регістр призначення також обирають із множини R0..R31 регістрового файла.
7. Immediate - це 16-ти бітове поле, що містить безпосередній операнд; при цьому найлівіший розряд immediate розглядають як знаковий; при використанні безпосередній операнд знаково розширюють вліво за правилами доповняльного коду до 32-х бітів. 8. Function - це поле, що визначає функцію, яка розширює на 211 – 1 = 2047 комбінацій обмежену кількість дозволених кодів операції. 9. Offset added to PC - це 26-ти бітова константа, яку додають до вмістимого регістру наступної адреси при виконанні інструкції безумовного переходу.
Особливості поданих форматів інструкцій: 1. Довжина усіх форматів – 32 біти. 2. Реалізовано дизайн архітектури load/store. 3. Реалізовано фіксовану систему поділу форматів на поля. 4. Усі інструкції з погляду їхньої обробки поділено на три групи:
- АЛП операції,
- операції load/store,
- операції керування виконанням програми.
Формати АЛП операцій є три адресувальними, а саме, OP RX,RY,RZ. Вони є майже збіжними з форматами інструкцій М88X00 RICS-мікропроцесора фірми Motorola. Останній разом із IBM801 та AMD29000 у середині 80-х років утворив історично першу трійку серійних RICS-процесорів .
Інструкції керування виконанням програми, до яких належать умовні й безумовні переходи, і деякі інші інструкції, наприклад, TRAP (остання тимчасово, на короткий термін ніби "передовіряє" керування системою деякому модулю операційної системи), а також інструкція повернення з виключення (обробка особливої ситуації, що може виникнути при виконанні операції) RFE (Return From Exception).
Інструкції обробки чисел з рухомою комою, за допомогою яких виконується додавання, віднімання, множення, ділення й низка інших операцій над відповідними кодами, як правило, у двох варіантах, із стандартною та подвійною точністю.
Пересилання даних поміж регістрами та пам'яттю даних, або поміж регістрами цілих операндів і регістрів операндів із рухомою комою та спеціальними регістрами; адресування пам'яті виконують за допомогою лише однієї адресувальної моди (mode), де 16-бітовий зсув, що міститься у форматі інструкції, додають до вмістимого одного з регістрів загального призначення (тобто регістра, що містить базову адресу).
Ще раз пригорнемо увагу до того, що саме інструкції завантаження (load) чи збереження (store), які належать до цього типу, вивільнено від додаткової функції арифметичного, логічного чи будь-якого іншого опрацювання операндів. Це, по-перше, задовольняє необхідній умові створення множини інструкцій (машинних команд) RISC-архітектури, а, по-друге, дозволяє визнати архітектуру, що зараз розглядається як load/store.
Пояснимо на ілюстративному прикладі синтаксис запису алгоритмів виконання окремих машинних інструкцій DLX (див. таблицю 2). Розглянемо запис:
Regs[R19]16..31=16(DM[Regs[R8]]0 )8 ## DM [ Regs[R8]].
Запис фіксує наступне. Оновлюють лише 16 молодших (правих) бітів регістру R19. До них пересилають двобайтовий бінарний код, в якому молодший правий байт береться з пам’яті даних DM за адресою, що є збіжною з вмістимим регістру R8. Старший лівий байт утворюють вісімразовим повторюванням нульового (старшого) розряду щойно згаданого правого байта. Парою символів ## позначено операцію конкатенації (зчеплення) двох байтів до двох байтового напівслова.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора