Аналіз теорії цифрових автоматів (стр. 3 из 7)

Байт - вісім послідовно розміщених бітів, пронумерованих від 0 до 7, при цьому біт 0 є самим молодшим значущим бітом.

Слово - послідовність з двох байтів, які мають послідовну адресу. Розмір слова 16 біт; біти в слові нумеруються від 0 до 15. Байт який містить нульовий біт, називається молодшим байтом, а байт, який містить 15-й біт називають старшим байтом. Мікропроцессори Intel мають важливу особливіть - молодший байт завжди зберігається за молодшою адресою. Адресою слова рахується адреса молодшого байта. Адреса старшого байта може бути використана для доступа до старшої половини слова.

Подвійне слово - послідовність з чотирьох байтів (32 біта), які мають послідовну адресу. Нумерація цих бітів проводиться від 0 до 31. Слово, яке містить нульовий біт називається молодшим словом, а слово яке містить 31-й біт старшим словом. Молодше слово зберігається за меншою адресою. Адресою подвійного слова рахується адреса молодшого слова. Адреса старшого слова може бути використана для доступа до старшої частини подвійного слова. .

Чотирьохкратне слово - послідовність з восьми байт (64 біта). які мають послідовну адресу. Номерація цих бітів проводиться від 0 до 63. Слово яке містить нульовий біт називається молодшим подвійним словом словом, а слово яке містить 63-й біт старшим подвійним словом. Молодше подвійне слово зберігається за молодшою адресою. Адресою подвійного слова рахується адреса молодшого слова. Адреса старшого подвійного слова може бути використана для доступа до старшої половини чотирьохкратного слова.

Поняття про булеві функції

Ф-ція f, яка залежить від n змінних x₁,x₂,…,x_n називається булевою, або переключаючою, якщо ф-ція f і любий з її аргументів x_i, i

приймають значення тільки змножини {0,1}. Аргументи булевої ф-ції також називаються булевими.

Довільна булева ф-ція задається одним із трьох способів: матричним (табличним), геометричним і аналітичним.

При матричному способі булева ф-ція f (x₁, x₂, …, x_n) задається таблицею істинності (табл.1 та 2),

В лівій частині якої представлені всі можливі двійкові набори довжини n, а в правій вказується значення ф-ції на цих наборах.

Під двійковим набором

= < >, {0,1} розуміють сукупність значень аргументів х₁, х₂,…, х_n булевої ф-ції f. Двійковий набір має довжину n, якщо він представлений n цифрами із множини {0,1}. В табл.1 та 4 перечислені всі двійкові набори відповідної довжини 3 і 4.

Іноді двійкові набори в таблиці істиності булевої ф-ції зручно представляти номерами наборів. Запишемо аргументи x₁,x_2,…x_n в порядку зростання їх індексів. Тоді любий двійковий набір =<>, {0,1} можна розглядати як ціле двійкове число N: N=2^n-1+2^n-2+…+, яке називають номером набору . Наприклад, двійкові набори 0101 і 1000 мають номера 5 і 8 відповідно. Очевидно будь-яка булева ф-ція може бути задана таблицею істинності, в якій двійкові набори замінені своїми номерами (табл.2).

Булеві ф-ції, залежать від великого числа змінних, задавати таблицею істиності незручно, в силу її громіздкості. Наприклад таблиця істинності булевої функції 8 змінних буде містити 2⁸=256 рядків. Тому для задання ф-ції багатьох змінних зручно використати модифікацію таблиці істинності.

Розглянемо спосіб побудови такої таблиці істинності для ф-ції n змінних. Множина із n змінних ф-ції розбивається на дві підмножини: x₁, x₂, …,x_j-1 і х_j, x_j+1,…, x_n. Змінні x₁, x₂, …,x_j-1 відмічають рядки таблиці істинності, задаваючи в кожному рядку значення відповідного двійкового набору довжини j-1. Змінними х_j, x_j+1,…, x_n відмічають її стовбці, задаваючи в кожному стовбці значення відповідного двійкового набору довжини n-j+1. Значення функції записуються в клітинці на перетині відповідного рядка і стовбця (табл 3).

При геометричному способі булева ф-ція f (x₁, x₂, …, x_n) задається з допомогою n-мірного куба. В геометричному смислі кожний двійковий набір

=<>, {0,1} є n-мірний вектор, визначаючий точку n-мірного прстору. Виходячи з цього, вся множина наборів, на яких визначена ф-ція n змінних, представляється вершинами n-мірного куба. Відмічаючи точками вершини куба, в яких функція приймає одиничне значення (або нульове), одержимо геометричне представлення функції. Наприклад, булева функція, задана табл.1, геометрично представляється 3-мірним кубом

При аналітичному способі булева функція задається формулами, тобто аналітичними виразами, побудованими на основі операцій булевої алгебри. Аналітичний спосіб задання булевих функцій займає особливе місце в проектуванні цифрових машин. Фактично, всі перетворення над булевими ф-ціями, необхідні для побудови цифрових машин, ведуться на аналітичному рівні.

Розглянемо області визначення булевоі ф-ції. Як уже відмічалось, між двійковими наборами і двійковими числами існує взаємнооднозначна відповідність. Отже, існує 2ⁿ різних наборів двійкових змінних.

Таким чином, областю визначення булевої ф-ції n змінних при матричному способі задання являється множина всіх можливих двійкових довжин n наборів, а при геометричному способі задання множина всіх вершин n-мірного одиничного куба.

Булеву ф-цію, визначену на всіх своїх наборах, називають повністю визначеною. Булеву ф-цію n змінних називають неповністю визначеною, або частинною, якщо вона визначена не на всіх двійкових наборах довжини n. Неповністю визначена булева ф-ція не попадає під визначення, дане на початку глави, але при довільному довизначенні (на всіх наборах, на яких вона не визначена) ця невідповідність знімається.

Існує не більше як 2ⁿ різних булевих функцій n змінних. До цього висновку легко прийти, користуючись простими комбінаторними міркуваннями, і згадавши, що на кожному із 2ⁿ наборів функції можуть приймати два значення.

Розглянемо найбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієї змінної представлені таблиці 5, де

f₀ (x) =0 - тотожній нуль (константа 0);

f₁ (x) =x - тотожна ф-ція;

f₂ (x) =

- заперечення x (інверсія);

f₃ (x) =1 - тотожна одиниця (константа 1).

Ф-ції двох змінних представлені в табл.6.

Найбільш часто використовуються такі:

f₀ (x₁,x₂) =0 - тотожній нуль (константа 0);

f₁ (x₁,x₂) =x_1*x₂ - кон’юнкція. Замість знака “_*” інколи використовують знак & або

. Цю ф-цію часто називають логічним перетворенням або логічним множенням;

f₃ (x₁,x₂) =x₁ - повторення х₁;

f₅ (x₁,x₂) =x₂ - повторення х₂;

f₆ (x₁,x₂) =x₁

х₂ -додавання по модулю, або сума mod 2;

f₇ (x₁,x₂) =x₁

x₂-диз’юнкція (логічне або);