Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Відповіді до теоретичних питань
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Державний іспит
Предмет:
Прикладна теорія цифрових автоматів
Частина тексту файла (без зображень, графіків і формул):
1. Поняття про інформацію та її види. Три підходи до вивчення теорії інформації. Порівняння аналогової та цифрової обчислювальної техніки
Інформацію назив. відомістю, які можна отримати, передати, керувати, обробляти, зберігати.
Інформація є міра різноманітності або однорідності в матеріалі , речовині та енергії у просторі та часі.
Порівняння АТ та ЦТ
1. Точність АТ=102/1=103/1=104/1
Відношення Сигнал/Завада ЦТ=1010/1
2. Швидкодія
АТ властивий паралельний алгоритм роботи.
3. Універсальність
ЦОМ – універсальні,спеціалізовані ,а АОМ – спеціалізовані
4. Вартість
EMBED Visio.Drawing.11
3 підходи до вивчення теорії інформації:
1. Структурна теорія інформації
2. Статистична (поняття ентропії)
3. Семантична (Акад. Маркевич О.О. Вартість інфи тим вища, чим більше змін робиться в сфері керування)
2. Поясніть, у чому полягає зміст та значення теореми Котельникова.
При дискретизації сигналів доводиться вирішувати питання про те, як часто слід проводити відліки функції, тобто який повинен бути крок дискретизації.
Кожній процес має обмеження на частоту спектру Fm.
Згідно теоремі В.А.Котельникова, якщо функція s(t) не містить частот вище за деяку Fm, то вона повністю визначається своїми миттєвими значеннями в моменти часу, віддаленими один від одного на величину 1/(2Fm ), тобто де до - порядковий номер відліку функції; = 1/(2Fm) - крок дискретизації по времени,sk = s(tk) - миттєві значення сигналу s(t) в к-ой відліковій точці tk = kp/wm = k/(2Fm) = kЧDt.
З цієї теореми виходить, що для однозначного представлення функції з обмеженим спектром на інтервалі часу Т досить мати деякі n значень цієї функції, де n = T / = 2FmT.
При виконанні цієї рівності (умови) безперервна і дискретна функції обратіми між собою, тобто тотожні. Таким чином, довільний сигнал, спектр якого не містить частот вище за Fm може бути представлений у вигляді послідовності імпульсів, амплітуда яких рівна значенню початкового сигналу в дискретні моменти часу kt= а інтервали між ними = 1/(2Fm).
З приведеного вище формулювання теореми Котельникова однозначно витікає, що для вибору оптимального кроку дискретизації необхідно заздалегідь провести кількісні оцінки всіх значущих гармонік спектрального розкладання початкового безперервного сигналу, для знаходження величини Fm, т.е.wm.
3. Основні ознаки алгоритму. Навести підхід до формального визначення алгоритму. Універсальні формальні алгоритмічні системи. Основна гіпотеза теорії алгоритмів.
Сукупність правил переходу автомата з одного стану в інший залежно від вхідної інформації і внутрішніх станів автомата називається алгоритмом перетворення (переробки) інформації. Взагалі алгоритмом називається кінцева сукупність точно сформульованих правил рішення какойто задачі.
Можна привести ще одне визначення поняття алгоритму. Алгоритм - це строго формальний опис кінцевої послідовності деяких "елементарних" дій або процедур, яку треба виконати над початковими даними і над проміжними результатами, що виникли в ході виконання цих операцій, для того, щоб дійти інформації, обробки початкових даних, що є результатом.
Ознаки алгоритму:
1. Справа з данімі (вхідні, провідні, вихідні)
2. Пам'ять для зберігання
3. Алгор. виконується по кроках, к-ть яких скінченна
4. Алгор. мусить буті детермінований
5. Результативність
Більш строге візначеня можна даті в рамках теорії Формальніх Алгор. Системах (ФАС):
1. Рекурсивні ф-ції
2. Машина Тюрінга
3. Машина Поста
4. Нормальні алгор. Маркова
5. Схема Колмагорова
6. Цифрові автоматі Мілі та Мура
7. Сист Черкаського
Основна гіпотеза теорії алгоритмів: будь-який алгоритм може бути вікорістаний із допомогою ФАС.
Перераховані, в цьому розділі поняття відносяться до абстрактної теорії цифрових автоматів, в якій розглядаються автомати, що мають один вхід і один вихід. Тому застосувати все це до ЕОМ можна тільки в найзагальнішому вигляді, обмежуючи круг даних пристроїв пристроями, що входять до складу процесора, чи ж у разі коли розглядається взагалі деякий вузол ЕОМ, призначений для достатньо елементарної обробки цифрової інформації. Насправді, залежно від команд, що подаються пристроєм управління процесора, арифметично-логічний пристрій здійснює відповідні дії (зміна внутрішніх станів) з видачею необхідних результатів. Проте зміна внутрішніх станів всієї ЕОМ в цілому носить настільки складний характер, що цей процес неможливо відобразити в аналітичному вигляді. Тому поняття цифрового автомата доцільно використовувати стосовно алгоритмів, що реалізовують некотору. програму або послідовність операцій. При цьому кожна операція представляється як елементарна дія, здійснювана в процесі переробки інформації.
4. Автомат. Класифікація автоматів. Поняття про модель цифрового автомата типу Мілі та Мура.
Цифровий автомат цей пристрій, що характеризується набором деяких внутрішніх станів A = {a1(t), a2(t), ..., an(t)}= у які воно потрапляє під впливом вхідних сигналів і команд програми рішення задачі.
Хай є автомат з одним входом і одним виходом:
A = {ai(t)}
z(t)
(t)
Рис.1.3. Цифровий автомат
Цифрові автомати можуть бути з "жорсткою", або схемної, логікою і з логікою, що зберігається в пам'яті. Розрізняють два класи автоматів: асинхронні і синхронні.
Синхронний автомат характеризується тим, що функціонує під управлінням тактових (або що синхронізують) сигналів - ТС, з постійною тривалістю tТС і постійною частотою fТС, якщо квантування часу рівномірне. Такт (квант) часу ti поєднується з фронтом i-того сигналу ТС. Вхідні сигнали можуть впливати на автомат лише за наявності сигналу ТС і не змінюються протягом tТС. Період проходження сигналів ТС повинен бути більше або рівний часу, який необхідний реальному автомату для переходу з одного стану в інший. Коли розглядається абстрактний автомат, то вважається, що зміна внутрішніх станів автомата відбувається в інтервали часу між суміжними ТС, а вихідні сигнали формуються по фронту чергового ТС.асинхронных
В автоматах тривалість інтервалу часу, протягом якого залишається незмінним стан вхідних сигналів, є величиною змінної і визначається часом, який необхідний автомату для установки відповідних вихідних сигналів і завершення переходу в новий стан. Отже, асинхронний автомат повинен формувати яким-небудь відповідним способом сигнал про завершення чергового такту, по якому поточні вхідні сигнали можуть бути зняті, після чого може початися наступний такт, тобто можливо надходження нових вхідних сигналів.
Як наголошувалося у розділі 1, абстрактний автомат з одним входом і одним виходом можна представити таким чином:
A
X
Y
Для завдання кінцевого автомата фіксуються три кінцеві множини (алфавіту): - безліч можливих вхідних сигналів: X = {x1, x2, ..., xm};
- безліч можливих вихідних сигналів: Y = {y1, y2, ..., yk};
- безліч можливих внутрішніх станів автомата: A = {a0, a1, ..., an}.
На цих множинах задають двох логічних операторів: - функцію переходів f, що визначає стан автомата а(t + 1) у момент дискретного часу t + 1 залежно від стану автомата а(t) і значення вхідного сигналу x(t) у момент часу t: а(t + 1)= f[а(t), x(t)]; (10.1) - функцію виходів , що визначає залежність вихідного сигналу автомата у(t) від стану автомата а(t) і вхідного сигналу x(t) у момент часу t: y(t) = [a(t), x(t)]. (10.2) Крім того, на безлічі станів автомата фіксують один з внутрішніх станів а0 як початковий стан. Поняття стан автомата використовується для опису систем, вихідні сигнали яких залежать не тільки від вхідних сигналів в даний момент часу, але і від деякої передісторії, тобто сигналів, які поступали на входи системи раніше. Отже, цифрові автомати відносяться до последовательностним схем, які, як вже наголошувалося, володіють пам'яттю. Поняття стан автомата відповідає деякій пам'яті про минуле, тому введення цього поняття дозволяє усунути час як явну змінну і виразити вихідні сигнали як функцію станів і вхідних сигналів. Роботу абстрактного автомата слід розглядати стосовно конкретних інтервалів часу, оскільки кожному інтервалу дискретності t відповідатиме свій вихідний сигнал у(t). Отже, функціонування автомата розглядається через дискретні інтервали часу кінцевої тривалості. У абстрактній теорії цифрових автоматів вважається, що вхідні сигнали впливають на синхронний автомат у момент початку кожного i-того інтервалу (кванта) часу, виділеного відповідним синхроімпульсом (тактом), а зміна внутрішніх станів автомата відбувається в інтервали часу між суміжними синхроімпульсами, коли немає дії вхідних сигналів. Оператори, що описують роботу автомата, звичайно задають таблицею переходів і таблицею виходів. У таблиці переходів показують в який стан потрапляє автомат від того або іншого вхідного сигналу. У таблиці виходів показують який вихідний сигнал генерує автомат залежно від типу вхідного сигналу і поточного стану автомата. Наприклад, розглянемо таблиці переходів і виходів деякого автомата.
Таблиця переходів автомата Таблиця виходів автомата
У клітку таблиці переходів, що знаходиться на перетині стовпця з буквою аi і рядки з буквою xj, записується стан автомата, в який він переходить із стану аi при подачі на вхід сигналу xj. У аналогічну клітку таблиці виходів записується вихідний сигнал yi, який формується автоматом при такому переході. Оператори переходів і виходів можуть бути задані однією таблицею, по якій однозначно визначаються переходи і виходи автомата.
Таблиця переходів і виходів автомата
велику наочність забезпечує завдання кінцевих автоматів за допомогою графів або діаграм станів.
Граф автомата складається з вузлів, сполучених гілками. Вузли (кухлі на схемі графа) ототожнюють внутрішні стани автомата. Кожна гілка графа, тобто орієнтована лінія, стрілка якої указує наступний стан автомата, наголошується вхідним сигналом, що викликає в автоматі відповідний даній гілці перехід, і вихідним сигналом, який виникає при цьому переході. Вхідний і відповідний йому вихідний сигнали розділяються на кресленні комою або косою межею. Якщо деякий вхідний сигнал не міняє стану автомата, то відповідна гілка замикається на кружку (вузлі), з якого вона виходить. Оскільки таблиця станів і граф (діаграма) станів несуть одну і ту ж інформацію, їх можна перетворити один в одного. Кожен стан представляється кружком, а кожен елемент таблиці перетвориться у відрізок орієнтованої лінії, що сполучає відповідні кухлі. Процедура зворотного перетворення очевидна. В даний час в класі синхронних атоматов розглядають, в основному, два типу автоматів: автомат Милі і автомат Мура. Графа атомата Милі, заданого вищенаведеними таблицями, відображений на мал. 10.1. Закон функціонування автоматів Милі може бути заданий таким чином: а(t + 1)= f[а(t), x(t)]; y(t) = [a(t), x(t)], де t = 1, 2 ..... Відмітна особливість автоматів Милі полягає в тому, що їх вихідні сигнали в деякий момент часу не залежать як від стану автомата, так і від значення вхідного сигналу в цей же момент часу.
Мал. 10.1. Граф автомата Милі.
У автоматів Мура вихідні сигнали у момент часу t однозначно визначаються станом автомата в цей же момент часу і в явному вигляді не залежать від значення вхідних сигналів xi(t). Функції переходів і виходів автомата Мура, заданого на безлічі вхідних сигналів X, безлічі внутрішніх станів A = {a0, a1,,an} і безлічі вихідних сигналів Y, можна записати у вигляді а(t + 1)= f[а(t), x(t)] (10.3) y(t) = [a(t)]. (10.4) цих операторів зручно задавати відміченою таблицею переходів. Такі таблиці будуються так само, як і таблиці переходів автомата Милі, але над символами кожного внутрішнього стану записуються вихідні сигнали, які видає автомат в даному стані. Відмічена таблиця переходів автомата
Граф автомата Мура, заданого цією таблицею, приведений на мал. 10.2. На цьому малюнку стану автомата позначаються сиволамі bi. На графах автомата Мура значення вихідних сигналів записуються біля вузлів.
Між автоматами Милі і Мура існує відповідність, що дозволяє перетворити закон функціонування одного з них в іншій або назад. Автомат Мура можна розглядати як окремий випадок автомата Милі, маючи на увазі, що послідовність станів виходів автомата Милі випереджає на один такт послідовність станів виходів автомата Мура, т.е відмінність між автоматами Милі і Мура полягає в тому, що в автоматах Милі стан виходу виникає одночасно із зухвалим його станом входу, а в автоматах Мура - із затримкою на один такт, т.к в автоматах Мура вхідні сигнали змінюють тільки стан автомата. Крім автоматів Милі і Мура виділяють ще, так званий, суміщений автомат - С-автомат. Абстрактний С-автомат можна представити у вигляді пристрою з одним входом, на який поступають вхідні сигнали X, і двома виходами, на яких з'являються вихідні сигнали Y і U.
A
Y мал. 10.3
X
U
Тут X - вхідний алфавіт; A - безліч станів; Y - вихідний алфавіт першого типа; U = {u1(t) ... um(t)} - вихідний алфавіт другого типа. Відмінність С-автомата від моделей Милі і Мура полягає в тому, що він одночасно реалізує дві функції виходів 1 і 2, кожна з яких характерна для цих моделей окремо. Цей автомат можна описати наступною системою рівнянь:
а(t+1)= f [а(t), x(t)]; (10.5) y(t) = 1[a(t), x(t)]; u(t) = 2[a(t)]. Вихідний сигнал u = 2 (as) виділяється весь час, поки автомат знаходиться в стані as. Вихідний сигнал yk = 1(as, xn) видається під час дії вхідного сигналу xn при знаходженні автомата в стані as. Від С-автомата легко перейти до автоматів Милі або Мура (з урахуванням можливих зміщень в часі на один такт), так само як можлива трансформація автомата Милі в автомат Мура і навпаки.
5. Буква, слово, алфавіт. Переваги, фізична реалізація та форми представлення дволітерних алфавітів.
Буква – сигнал, який поступає на вхід ЦА в момент часу ti (проміжна, вихідна)
Слово – послідовність вхідних букв.
Алфавіт – це множина всіх букв, які відрізняються.
A
X Y
Для завдання кінцевого автомата фіксуються три кінцеві множини (алфавіту):
- безліч можливих вхідних сигналів: X = {x1, x2, ..., xm};
- безліч можливих вихідних сигналів: Y = {y1, y2, ..., yk};
- безліч можливих внутрішніх станів автомата:A = {a0, a1, ..., an}.
Причини застосування двозначного алфавіту:
У внутрішньому алфавіті кожна буква з двох являє зоною чи смугою.
EMBED Visio.Drawing.11
Відрізняються стани не тільки кількісно, але і якісно.
Арифметичні та логічні операції виконуються простіше в двохбуквених алфавітах.
Простіше реалізовуються пристрої памяті.
Фізичне представлення
Форми представлення
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
Потенціальна (статична) 4. Фазова
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
Імпульсна (динамічна)
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
Частотні
6. Алгебра логіки. Поняття про аналіз і синтез. Операції суперпозиції та перестановки.
Логічною основою цифрових автоматів або комп'ютерів є алгебра логіки (булева алгебра) - одна з основних частин математичної логіки. Теорія логічних основ цифрових автоматів надзвичайно насищена достатньо специфічними термінами, поняттями. Тому в цьому розділі і у всіх подальших буде приведено багато визначень цих понять. Причому, нерідко для одного і того ж поняття буде використано декілька визначень для чіткішого розуміння його суті і взаємозв'язку з іншими специфічними поняттями теорії логічних основ цифрових автоматів. Отже, приведемо перший варіант визначення понять логічної змінної і логічної функції.
Функція f(x1, x2, ..., xn) називається логічною (перемикача), або булевої, якщо вона, так само як і її аргументи xi, може приймати тільки два значення: 0 або 1.
Логічна (булева) змінна ця така величина x, яка може приймати тільки два значення: 0 або 1.
Таким чином, логічні функції, їх аргументи і просто логічні змінні можуть приймати тільки два значення 0 або 1. Причому, в цих випадках цифри 0 і 1 є символами стану, а не числами. Алгебра логіки є алгеброю станів, а не алгеброю чисел, тому цю алгебру називають також алгеброю висловів.
Сукупність значень аргументів логічної функції називається набором (або крапкою) і може позначатися, зокрема, як х1, х2..., хn, де xi рівне нулю або одиниці (i = 1, 2, ..., n). Очевидно, що набір значень аргументів фактично є деяким двійковим числом. Кожному набору значень аргументів приписується номер, рівний двійковому числу, яке відповідає значенню даного набору. Наприклад, для чотирьох аргументів 0, 0, 0, 0 - нульовий набір; 0, 0, 0, 1 - перший набір;0, 0, 1, 0 - другий набір; 1, 0, 1, 0 - десятий набір і т.д.
Суперпозиція
Підстановка в логічну функцію замість її аргументів інших логічних функцій називається суперпозицією.
xyz=x (yz), xyz=x(yz), xyzx(yz)
Перестановка
xy= yx, xy=yx, xyyx
7. Змінна, набір, функції алгебри логіки (ФАЛ) нуля, однієї та двох змінних
Сукупність значень аргументів логічної функції називається набором (або крапкою) і може позначатися, зокрема, як х1, х2..., хn, де xi рівне нулю або одиниці (i = 1, 2, ..., n). Очевидно, що набір значень аргументів фактично є деяким двійковим числом. Кожному набору значень аргументів приписується номер, рівний двійковому числу, яке відповідає значенню даного набору. Наприклад, для чотирьох аргументів 0, 0, 0, 0 - нульовий набір; 0, 0, 0, 1 - перший набір;0, 0, 1, 0 - другий набір; 1, 0, 1, 0 - десятий набір і т.д. Таким чином, логічна функція (функція алгебри логіки) це функція f(x1, x2, ..., xn) яка приймає значення 0 або 1 на наборі логічних змінних x1, x2, ..., xn. Кожної логічної функції даного набору аргументів, також прийнято приписувати номер: 0, 1, 2....... Будь-яка логічна функція n аргументів визначена на 2n наборах, тобто може мати 2n наборів. Число різних логічних функцій n аргументів звичайно і рівне 2.
Неповністю певна логічна функція n змінних, це функція, задана на числі наборів меншому 2n. Для наборів, на яких функція не визначена, її значення можна прийняти довільним. Наприклад, для одного аргументу маємо 21, тобто 2 набори і 22, 4, тобто чотири логічні функції від однієї змінної, які приведені в таблиці 7.1. Т а б л і ц а 7.1
У зв'язку з тим, що функція f0(x) рівна одиниці при будь-яких значеннях аргументу, то ця функція називається абсолютно істинною (константа одиниці), тоді функція f1(x) - абсолютно помилкова функція (константа нуля). Функція f2(x), що повторює абсолютне значення логічної змінної, - тотожна функція: f2(x) є x. Функція f3(x), що приймає значення, зворотне значенню x, - логічне заперечення (інверсія), або функція НЕ (NOT), яка позначається одним з наступних способів:f3(x) = x = x.
Логічне заперечення або інверсія деякої логічної змінної, наприклад змінною А, це також логічна змінна, що приймає значення зворотне значенню змінної А, і що позначається як `А. Якщо А =1, то `А = 0, якщо ж А = 0, то `А = 1. Але потрібно врахувати, що часто за допомогою заперечення, тобто інверсії змінної просто позначають випадок, коли її значення рівне нулю.
ФАЛ 2-х
Диз'юнкція (логічне складання) або функція АБО (OR) - це функція f7(x1, x2), яка істинна тоді, коли істинна хоч би одна з її змінних. Умовні позначення цієї функції:
f7(x1, x2) = x1 + x2 = x1 x2 = x1 ! x2
Це читається таким чином: функція істинна, тобто рівна одиниці, коли аргумент x1 = 1, тобто істинний, або аргумент x2 = 1, чи ж обидва аргументи істинні одночасно.
Т а б л і ц а 7.2
Кон'юнкція (логічне множення) або функція І (AND) - це функція f1(x1, x2), яка істинна тоді, коли все її змінні одночасно істинні. Цю функцію умовно позначають таким чином: f1(x1, x2) = x1 x2 = x1 x2 = x1 & x2 Це читається таким чином: функція істинна, тобто рівна одиниці, коли обидва аргументи одночасно істинні, тобто рівні одиниці.
Функція (штрих) Шеффера або функція І-НЕ - це функція f14(x1, x2), яка помилкова тоді, коли всі змінні істинні. Умовне позначення цієї фнкциі: f14(x1, x2) = x1/x2
Це читається таким чином: функція помилкова, тобто рівна 0, коли обидва аргументи одночасно істинні, тобто рівні одиниці, і функція істинна, тобто рівна одиниці, коли або обидва аргументи одночасно помилкові, чи ж хоч би один з них помилковий.
Функція (стрілка) Пірсу (Вебба) або функція ІЛІ-НЕ - це функція f8(x1, x2), яка істинна тільки тоді, коли всі змінні помилкові. Умовне позначення цієї функції: f8(x1, x2) = x1 x2 = x1 O x2. Це читається таким чином: функція помилкова, тобто рівна 0, коли хоч би один з її аргументів істинний, чи ж обидва одночасно істинні, тобто рівні одиниці, і функція істинна, тобто рівна одиниці, коли обидва аргументи одночасно помилкові.
Імплікація або функція ЕСЛІ-ТО (IF-THEN) це функція f13(x1, x2), яка помилкова тоді і тільки тоді, коли x1 істинно і x2 помилково. Аргумент х1 називається посилкою, а х2 - слідством. Її умовне позначення f13(x1, x2) = x1 x2..
Що Виключає АБО (XOR) - це функція f6(x1, x2), яка позначається знаком . Ця операція, як видно з таблиці, реалізує функцію нерівнозначності, тобто фактично реалізується процедура підсумовування по модулю 2, яка позначається знаком :
f6(x1, x2) = x1 x2 = x1 x2
Всі розглянуті функції є елементарними. Зі всіх приведених вище за определеніїй ясно, що в алгебрі логіки всі знаки дій: или &, или +, , і т.д, у відмінності від звичайної алгебри, є знаками логічних зв'язок, тобто логічних дій, а не знаками арифметичних дій. Введемо ще три специфічні поняття алгебри логіки. Дві функції вважаються рівносильними один одному, якщо вони приймають на всіх можливих наборах своїх аргументів одні і ті ж значення. Логічна змінна xi дійсна, якщо значення логічної функції f(x1, x2, ..., xn) змінюється при зміні xi. Інакше ця змінна для даної функції фіктивна, тобто не є її аргументом. Необхідність введення цих двох останніх понять виникла з наступної причини. При аналізі деякої невідомої логічної функції (логічної схеми), для якої необхідно сформувати аналітичний вираз, не всі логічні змінні, що підключаються для цього аналізу, можуть бути аргументами цієї функції, що і виявляється у результаті проведеного аналізу. Як буде показано надалі, будь-які логічні операції над логічними змінними можна звести до певної сукупності елементарних логічних функцій, наприклад, таких як і, АБО, НЕ і ісьключающе АБО. Елементарні логічні операції в компьтерах виконуються також над двійковими числами, по розрядно. Розглянемо декілька простих прикладів виконання логічних операцій над двома двійковими числами:
І АБО Іськл. АБО НЕ
01011010 0101010 0101010 01011010
11110000 1111000 1111000 10100101
01010000 1111010 1010010
Підстановка в логічну функцію замість її аргументів інших логічних функцій називається суперпозицією.
Система логічних функцій називається функціонально повною, якщо за допомогою функцій, що входять в цю систему, застосовуючи операції суперпозиції і підстановки, можна одержати будь-яку скільки завгодно складну логічну функцію.
8. Основні властивості ФАЛ за Постом. Методи виявлення ФПС ФАЛ із цими властивостями.
Для побудови ПС(повна система) ФАЛ(Функція Алгебри-Логіки) яка має хоч би одну функцію, яка не зберігає константу 0, не зберігає константу 1, нелінійна, немонотонна, несамодвоїста.
Якщо функція на нульовому наборі змінних дорівнює 0, то ф-ція зберігає конст. 0.
Якщо функція на одиничному наборі змінних дорівнює 1, то ф-ція зберігає конст. 1.
ФАЛ назив. монотонною, якщо при будь-якому зростанні кількості 1 у послідовності сусідніх( тобот на тих, які відрізняються тільки в одному розряді) на наборі змінних значення функції не змінюється або збільшується.
ФАЛ назив. самодвоїстою, якщо на кожній парі протилежних наборів (х0,х1,..) та (#х0, #х1,..) вона приймає протилежні значення.
EMBED Equation.3
ФАЛ назив. лінійною , якщо її можна зобразити поліномом 1 порядку в базисі Жегалкіна без добутків змінних ВСАС1 – нелінійна
АС1 - лінійна
EMBED Equation.3
Приклад
нелінійна
лінійна
9. Базис Жегалкіна. Основні тотожності. Синтез комбінаційних схем на прикладі однорозрядних суматорів на два та на три входи.
EMBED Equation.3
{&, , 1}
Реалізація комбінаційних схем
Однорозрядний суматор на 2 входи
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
S=AB
P=AB
Однорозрядний суматор на 3 входи
S=ABC
P=ABCABCABCABC=(A1)BCA(B1)CAB
EMBED Visio.Drawing.11
(C1) ABC=ABCBCABCACABCABABC=
=BCACAB
EMBED Visio.Drawing.11
10. Базис Буля. Основні тотожності.
{&, , }
Розглянемо основні закони, аксіоми і теореми алгебри логіки
Деякі закони звичайної алгебри застосовні і до алгебри логіки. Наприклад:
Закон коммутатівності:
для множення АВ = ВА
для складання A B = B A
Закон асоціативності:
для множення A(BC)= (AB)З
для складання A (B З) = (A B) З
Закон дістрібутівності множення по відношенню до складання:
A(B З)= AB AC
У алгебрі логіки діє також закон дістрібутівності складання по відношенню до множення:
A A B)(A З)
Алгебра логіки має ряд специфічних аксіом і теорем, основні з яких, необхідні для аналізу і синтезу логічних ланцюгів або схем, приведені нижче.
У алгебрі логіки широко використовується також специфічний закон склеювання:
11. Форми завдання ФАЛ у базисі Буля. Класифікація аналітичних форм завдання ФАЛ у базисі Буля.
Таблиці
Скорочені Квадратні таблиці
2. Аналітичний
EMBED Visio.Drawing.11
Досконала – будь-які нормальні форми можуть бути дизюктивними та конюктивними, кожний терм має усі змінні.
Мінімальна – яка має мінімальну к-ть букв.
Скорочена – коли хоча б 1 терм не має всіх змінних.
Найкоротша – має мінімальну к-ть термів, змінних, букв.
Наприклад, якщо деяка, задана табличний, функція f(x1, x2, x3) приймає значення одиниці на наборах з номерами 0, 3, 4 і 6, то її можна представити таким чином: f(x1, x2, x3)= VF(0, 3, 4, 6)
1
або f(x1, x2, x3)= VF(0, 3, 4, 6)
Якщо ця ж функція на наборах 1, 2, 5, 7 - приймає значення 0, то її можна представити так:
f(x1, x2, x3)= F(1, 2, 5, 7)
0
або f(x1, x2, x3)= П F(1, 2, 5, 7)
Таку форму запису називають числовою. Перший вид такої форми використовують коли функція представляється в СНДФ, а другий - коли в СНКФ. Багато перетворень, що виконуються над логічними функціями, іноді зручно інтерпретуються з використанням їх геометричних уявлень. Наприклад, функцію двох змінних можна інтерпретувати як деяку площину, задану в системі координат х1, х2. Якщо відкласти по кожній осі одиничні відрізки х1 і х2, то вийде квадрат, вершини якого відповідають комбінаціям змінних.
x1x2 x1 x1x2
x2 x2
x1x2 x1 x1x2
Звідси витікає, що дві вершини, що належать одному і тому ж ребру і звані сусідніми, "склеюються" по змінній, змінній уздовж цього ребра. Наприклад
x1x2 + x1x2 = x2,
т.к, як нам вже відомо, з властивостей логічних функцій, що
x1x2 + x1x2 = (x1 + x1)x2 = 1x2 = x2
Для функцій трьох змінних геометричне уявлення виконують у вигляді тривимірного куба. Ребра куба поглинають вершини. Грані куба поглинають свої ребра і, отже, вершини.
У разі ж чотирьох змінних - "чотиривимірного" куба. У геометричному сенсі кожен набір змінних x1, x2, x3,...., xn можна рассмарівать як n-мірний вектор, що визначає точку n-мірного простанства. Тому вся безліч наборів, на яких визначена функия n змінних, представляється у вигляді вершин n-мірного куба. Координати вершин куба указуються в порядку, відповідному порядку переліку змінних в записі функції. Відзначаючи крапками вершини, в яких функція приймає значення, рівне одиниці, одержуємо геометричне уявлення ФАЛ.
12. Проблема мінімізації у базисі Буля. Канонічна та загальна задачі мінімізації. Огляд методів розв’язання.
EMBED Visio.Drawing.11
1.
EMBED Visio.Drawing.11
2. Карта Карно
EMBED Equation.3
EMBED Visio.Drawing.11
EMBED Equation.3
EMBED Equation.3
3.
4. Метод глобального винесення за дужки:
EMBED Equation.3
11 букв
9 букв
8 букв
Чим більше винесення за дужки, тим менша швидкодія
5.Введення надлишковості з глобальним винесенням за дужки:
x1x2x3x1x3x4x5x1x2x4x6x4x5x6 = – 14 букв
=x1x2(x1x3x4x6) x4x5(x1x3x4x6)=(x1x3x4x6)(x1x2x4x5) – 8 букв
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).
14. Особливості та додаткові можливості застосування методу карт Карно.
Карти Карно (їх різновидом є карти Вейча, які будуються як розгортки куба на площині), є графічним представленням таблиць істинності. Тому вони будуються або по таблиці істинності аналізованої функції, чи ж по її СНДФ. Нагадаємо, що кожен рядок таблиці істинності, для якої функція рівна одиниці, відповідає конкретному мінтерму функції, представленій в СНДФ. Рядок, для якого функція рівна нулю є визначеним макстермом функції, представленій в СНКФ. Карта Карно є прямокутником, розбитим на квадрати, число яких рівне загальному числу наборів для даної функції n змінних, тобто воно рівне 2n. Так, для функції чотирьох змінних квадратів буде 16, для п'яти змінних - 32 і т.д. Кожен квадрат відповідає певному набору або терму, причому набори розташовуються так, щоб сусідні набори або терми, як по горизонталі, так і по вертикалі, відрізнялися б тільки значенням однієї змінної: у одному квадраті вона з інверсією, а в другом, сусідньому - без. Функцію в СНДФ наносять на карту, відзначаючи, наприклад, знаком 1 квадрати, відповідні тим наборам, на яких функція рівна одиниці, тобто в СНДФ функції відповідний мінтерм. Решта квадратів наголошується знаком 0. Іноді в кутку квадрата ставлять номер набору. Такий спосіб використовується, якщо функція задана числовим чином, але він неудо-бен для процедури мінімізації. Логічна функція двох змінних, де а) - таблиця істинності; а б) - карта Карно.
У результаті карту Карно можна оформляти будь-яким відповідним чином, але тільки так, щоб кожен квадрат відповідав певному набору або терму і вони, як вже наголошувалося, розташовувалися б так, щоб сусідні набори або терми, як по горизонталі, так і по вертикалі, відрізнялися б тільки значенням однієї змінної: у одному квадраті вона з інверсією, а в другом, сусідньому - без. Причому, треба врахувати, що квадрати, розташовані на протівополжних кінцях кожного рядка або стовпця, також є сусідніми. Перерахуємо послідовність дій, що виконуються для мінімізації функції по методу Карно.
(1) Початкова функція, що підлягає мінімізації, повинна бути представлена в НДФ. Потім її треба представити в СНДФ. Чи ж складається таблиця істинності функції, що мінімізується. Як вже наголошувалося, між рядками таблиці істинності і клітками (осередками) на карті Карно існує взаємно однозначна відповідність. Коли карта Карно складається по СНДФ функції, що мінімізується, то очевидно, що кожна змінна без заперечення замінюється її значенням 1, а із запереченням - 0. (2) Потім будується карта Карно за принципом, описаним раніше. Представимо систему координат, в якій, наприклад, для функції двох аргументів по горизонтальній осі відкладаються значення одного аргументу, а по вертикалі - іншого. На перетині відповідних координат одержуємо осередок, куди записується значення функції (0 або 1), відповідне даному набору. Якщо функція представлена в СНДФ, то в осередку відповідної що існує мінтерму записується 1, а в осередку неіснуючого мінтерма - 0. (3) Після цього об'єднуються в групи суміжні осередки, в яких записані одиниці, таким чином: об'єднується обов'язково парна кількість сусідніх осередків з одиницями як по вертикалі, так і по горизонталі. Причому, кожен осередок з 1 може потрапити одночасно в дві групи, одержані в результаті об'єднання одиниць як по вертикалі, так і по горизонталі. (4) Кожній такій групі ставиться у відповідність новий мінтерм для зображення початкової функції у формі мінімальної НДФ. (5) Зображення кожного нового мінтерма формується по наступному алгоритму: а) змінна, яка в кожному осередку освіченої групи має значення тільки 0, зображається її інверсією; б) змінна, яка в кожному осередку групи має значення тільки 1, зображається без інверсії; в) змінна, яка в межах освіченої групи міняє своє значення, не зображається, тобто відкидається. Таким чином, карту Карно можна розглядати як графічне представлення сукупності всіх (сушествующих і що не існують) мінтермов функції в СНДФ даного числа логічних змінних. На підставі закону дістрібутівності і теорем (F +A) = 1 и AA = 0= а также A + 0 = A и A0 = 0, два мінтерма, що знаходяться в сусідніх клітках, можуть бути замінені одним новим мінтермом, що містять на одну змінну менше. Якщо сусідніми являютя дві пари мінтермов, то така група з 4 мінтермов може бути замінена новим мінтермом, який містить на дві змінні менше і т.д. У загальному випадку наявність одиниць в 2n сусідніх клітках дозволяє виключити n змінних. При формуванні на базі карти Карно нових мінтермов для представлення функції в мінімальній НДФ, чи ж в мінімальній НКФ, значення відповідних змінних, рівних 1, замінюються зображенням змінних без заперечення, а при значеннях рівних 0 - із запереченням.
15. Метод функціональної декомпозиції.
y1
ym
1(y-y1)
Z1
Zr
X1
Xn
F (x1…xn)
f(x1 x2…xn)= 2(1(y1-ym), Z1,..Z2
m<n, R<n
m+R=r; m=R; m = R
Класифікація методів функціональної декомпозиції
Ф. декомп.
одноразова
багаторазова
не перетина.
перетина
f( x1,x2,x3,x4)=x1 x2 x4 V x2 x3 V x1 x3 =min ДНФ
=x1Vx2 x4Vx3(x1Vx2)= x4Vx3
=x1Vx2
1
1
1
X1
X2
X3
16. Позиційні цілочисленні СЧ. Порівняння та класифікація. Двійкова СЧ. Правила дії. Основні переваги.
Непозиційна система числення - це система, для якої значення символу, тобто цифри, не залежить від його положення в числі. До таких систем відноситься, зокрема, римська система (правда з деякими обмовками). Тут, наприклад, символ V завжди означає п'ять, незалежно від місця його появи в записі числа. Є і інші сучасні непозиційні системи.
Позиційна система числення - це система, в якій значення кожної цифри залежить від її числового еквівалента і від її місця (позиції) в числі, тобто один і той же символ (цифра) може приймати різні значення. У позиційній системі числення справедливо рівність:
Aq = anqn + an-1qn-1 + ... + a1q1 + a0q0 + a-1q-1 + ... + a-mq-m, (2.1)
EMBED Equation.3
де Aq це довільне число, записане в системі числення з підставою q; ai - коефіцієнти ряду, тобто цифри системи числення; n, m - кількість цілих і дробових розрядів відповідно.Наприклад, згідно (2.1)
1961,3210 = 1103 + 9102 + 6101 + 1100 + 310-1 + 210-2,
124,5378 = 182 + 281 + 480 + 58-1 + 38-2 + 78-3,
1001,11012 = 123 + 022 + 021 + 120 + 12-1 + 12-2 + 02-3 + 12-4.
Формальні правила двійкової арифметики
Перед тим, як розглянути формальні правила двійкової арифметики підкреслимо загальний принцип складання і віднімання чисел представлених будь-якої позиційної системи числення. У загальному випадку процедури складання і віднімання двох чисел A B = C в будь-якої позиційної системи числення починаються з молодших розрядів. Код суми каждго i-того розряду сi виходить в результаті складання ai + bi +1, де одиниця...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора