Аналіз теорії цифрових автоматів
(курсова робота)
Содержание
Двійкова арифметика
Системи числення з довільною основою
ііМшан системи числення
Форма з фіксованою крапкою
Форма з плаваючою крапкою
Прямий, зворотній та доповнюючий коди чисел
Поняття про булеві функції
Аналітичне представлення булевих функцій
Мінімізація булевих функцій
Метод квайна-мак-класкі
Висновок
Висновок
Література
Теорія цифрових автоматів закладає теоретичні основи роботи комп’ютерної техніки. У даній курсові роботі проводиться аналіз математичного підгрунтя даної дисципліни.
Двійкова система числення
Двійкова позиційна система числення
Позиційна система числення з основою 2 називається двійковою. Для запису чисел в двійковій системі використовуються лише дві цифри: 0 і 1. Число два, тобто основа системи подається як 102.
Зручність системи - в її надзвичайній простоті.
Недолік - основа системи мала, тому для запису навіть не дуже великих чисел треба використовувати багато знаків.
Переведення числа з двійкової системи числення в десяткову та з десяткової у двійкову.
Нам уже відомо, що число N, записане в системі числення з основою p як (±akak-1…a1a0) p, рівне N=ak∙pk+ak-1∙pk-1+…+a1∙p+a0
Тому:
10012=1∙23+0∙22+0∙21+1∙20=8+0+0+1=910
1000012=1∙25+0∙24+0∙23+0∙22+0∙21+1∙20=32+0+0+0+0+1=3310
Щоб перевести число із десяткової системи числення у двійкову, треба послідовно ділити десяткове число і його десяткові частки на основу двійкової системи, тобто на число 2. Ділення продовжується до тих пір, поки одержана частка не буде менша основи нової системи числення, тобто 2.
1 |40|2_
0 |20|2_
0 |10|2
0|5|2
1|2|2
0|1
Отже число 8110 в двійковій системі: 10100012
Переведемо число 100:
100|2_
0 |50|2_
0 |25|2_
1 |12|2
0|6|2
1|3|2
1|1
Отже, (100) 10= (1100100) 2
З переводом чисел з десяткової системи одиниць у двійкову приходиться постійно мати справу при роботі на ЕОМ.
Окрему позицію в записі числа називають розрядом. Число розрядів - розрядність (довжина). Номер позиції - номер розряду. Довжина числа - це к-сть позцій (розрядів) в записі числа. В технічному розумінні це довжина розрядної сітки.
Чим менша основа системи, тим більша довжина числа. Якщо довжина розрядної сітки n, то: Aq max=qn-1; Aq min= - (qn-1);
Діапазон представлення чисел в заданій системі:
Aq max ≥ДП≥ Aq min.
Двійкова арифметика
Арифметичні дії в двійковій системі (двійковій арифметиці) виконуються за звичайними для позиційних систем правилами (алгоритмами), які нам відомі з десяткової арифметики, але при цьому, звичайно, використовуються таблиці додавання і множення двійкової системи.
Таблиця додавання
0+0=0
0+1=1
1+0=1
1+1=102
(додавання нуля не міняє числа, а один плюс один буде два).
Таблиця множення
0∙0=0
0∙1=0
1∙0=0
1∙1=1
(число, помножене на нуль, є нуль; множення на один не міняє числа).
Додавання. Додавання багатозначних чисел відбувається так само, як і в десятковій системі, тобто порозрядно, починаючи з молодшого.
1011012 - 1 доданок
+ 101002 - 2 доданок
10000012 - сума
Перевіримо правильність наших обчислень:
1011012=1∙25+0∙24+1∙23+1∙22+0∙21+1∙20=32+0+8+4+0+1=4510
101002=1∙24+0∙23+1∙22+0∙21+0∙20=16+0+4+0+0=2010
4510+2010=6510
10000012=1∙26+0∙25+0∙24+0∙23+0∙22+0∙21+1∙20=64+0+0+0+0+0+1=6510
Віднімання
0-0=0
1-0=1
1-1=0
102-1=1
Знайдемо: 1110101112-11000012
1110101112
- 11000012
1011101102
Крапки,
поставлені
над деякими
розрядами,
показують, що
в двійковій
системі одиниця
відміченого
розряду роздроблюється
на дві одиниці
вищого розряду.
Множення
111012∙11012
111012 - множник
11012 - множник
11101 - множене
+11101 - множене, зсунуте на 2 розряди вліво
11101 - множене, зсунуте на 3 розряди вліво
1011110012 - добуток
Перевірка:
111012=1∙24+1∙23+1∙22+0∙21+1∙20=16+8+4+1=2910
11012=1310; 29∙13=37710
1011110012=1∙28+0∙27+1∙26+1∙25+1∙24+1∙23+0∙22+0∙21+1∙20=256+0+64+32+16+8++0+1=37710.
Отже, в двійковій арифметиці при множенні не потрібна таблиця множення. Не треба знаходити добутки першого множника на значення послідовних розрядів другого множника, так як значення цих розрядів або 1 або 0.
Достатньо записати значення першого множника одне під одним із зсувом на один розряд; у випадку рівності якого-небудь розряду другого множника нулю, його зсувають на два розряди.
11011112
1011012
1101111
1101111
1101111
1101111 __
10011100000112
Системи числення з довільною основою
Ми розглянули алгоритм переводу чисел з двiйкової системи числення в десяткову i навпаки - з десяткової в двiйкову. Алгоритми залишаться цiлком аналогiчними, якщо замiсть двiйкової системи числення взяти будь-яку iншу.
Нехай, наприклад, деяке число записане в вiciмковiй системi числення. Це значить, що цифри в записі цього числа є коєфiцiєнти в його розкладi по степенях числа 8:
(anan-1... a1a0, a-1a-2. .) 8 =an*8n+an-1*8n-1+... +a1*8+a0+a-1*8-1+...
Для того,щоб отримати зображення цього числа в десятковiй системi числення, достатньо виконати, користуючись десятковою арифметикою, всi операцiї в правiй частинi цього виразу. Приклад. Перевести число (276,54) 8 з вiсiмкової системи числення в десяткову:
(276,54) 8=2*82+7*81+6*80+5*8-1+4*8-2=128+56+6+5/8+4/64= (190,6875) 10.
Нехай тепер потрiбно перевести число з десяткової системи числення в вiсiмкову. Як i у випадку переводу в двiйкову систему числення, розглянемо окремо цiлу i дробову частини чисел. Для цiлої частини скористаємось алгоритмом дiлення, а для дробової - множення. В першому випадку ми отримаєм шукане вiсiмкове зображення цiлого числа, зiбравши в зворотньому порядку залишки вiд дiлення на 8, а у другому випадку отримаємо вiсiмкове зображення дробу, зiбравши в прямому порядку цiлi частини при послiдовному множеннi на 8. Приклад. Перевести число (190,6875) 10 з десяткової системи числення в вiсiмкову.
Переведемо цiлу частину:
190 | 8
16 | 23 | 8
30 16 | 2 | 8 (190)10=(276)8
6 7 2 | 0
Переведемо дробову частину:
0 | 6875 (0,6875)10=(0,54)8
5 | 5000
4 | 0
тобто (190,6875)10 =(276,54)8.
Цей приклад разом з попереднiм iлюструє, як можна перевiряти правильнiсть переводу з однiєї системи числення в iншу зворотнiм переводом.
Виконання арифметичних дій в СЧ з основою р.
Змішані СЧ. Запис чисел в змішаних СЧ. Системи з кратними основами. Теорема для СЧ з кратними основами
Мішані системи числення
Існує простий спосіб запису десяткових чисел за допомогою двійкових цифр - представлення чисел в мішаній двійково-десятковій системі числення. В ній кожна цифра десяткового зображення числа записується в двійковій системі числення.
Причому для того, щоб такий запис був однозначним, для представлення будь-якої десяткової цифри відводиться одна і та ж кількість двійкових розрядів - чотири. Якщо десяткова цифра вимагає для свого представлення менше значущих двійкових цифр, то попереду цих цифр дописуються нулі (так щоб загальна кількість двійкових знаків залишалась рівною чотирьом). Наприклад, десяткове число 834,25 в двійково-десятковій системі запишеться так:
(834,25) 10 = (1000 0011 0100,0010 0101).
Кожна четвірка (тетрада) двійкових цифр тут відповідає одній десятковій цифрі:
(8)10 = (1000)2-10 (2)10 = (0010)2-10
(3)10 = (0011)2-10 (5)10 = (0101)2-10
(4)10 = (0100)2-10
Теорема.
Якщо P = Qn (P, Q, n - цілі
додатні
числа), то запис
любого числа
в мішаній
(Q - P) - й системі
числення тотожньо
співпадає
з записом цього
ж числа в системі
числення з
основою Q (з точністю
до нулів
на початку
запису цілої
частини числа
і
на кінці
дробової).
Якщо P=8, Q=2, n=3, то 8=23 і, отже, згідно даної теореми запис будь-якого числа в двійково-вісімковій системі співпадає з записом того ж числа в двійковій системі. (Зауважимо, що за тією ж теоремою записи будь-якого числа в двійковій і двійково-шістнадцятковій системах теж співпадуть). Переведемо, наприклад, все теж число (405) 10 з десяткової системи числення в шістнадцяткову:
405|16
32 |25|16
85 9|1 |16
80 |0
5
Збираючи залишки від ділення, отримаємо (405) 10 = (195) 16.
Представимо тепер число (195) 16 в двійково - шістнадцятковому записі: (195) 16 = (1 1001 0101) 2-6.
Видно, що записи числа в двійковій і двійково-шістнадцятковій системах вuявuлuсь однаковими. Ця властивість двійково-вісімкової системи числення дозволяє дуже просто переводити числа з двійкової системи в вісімкову (чи шістнадцяткову) і навпаки.
Справді, будь-який двійковий запис розглядаємо як двійково-вісімковий код деякого вісімкового числа, розбиваємо його на трійки (тріади) двійкових цифр ліворуч і праворуч від коми. Кожній такій трійці ставимо у відповідність одну вісімкову цифру і отримаємо число в вісімковій системі числення.
Візьмемо, наприклад, код:
(10 011 110,001 1)2 = (236,14)8 .
2 3 6 1 4
Тут,
як і
в двійково-десятковому
записі, в цілій
частині
відкинуті
крайні
зліва
нулі,
а в дробовій
частині
- крайні
справа. Безумовно,
треба їх
враховувати
як недостатні
у відповідних
тріадах
двійкових
цифр. Зворотній
перевід
чисел з вісімкової
системи числення
в двійкову
також простий.
Кожну цифру
вісімкового
числа записуємо
трійкою
двійкових
символів,
тобто записуємо
його в двійково-вісімковій
системі,
а так як цей
запис співпадає
з двійковим,
то ми одержимо
число в двійковій
системі.
Переведемо,
наприклад,
число (3514,72) 8 з
вісімкової
системи в двійкову:
(3514,72)8 = (11 101 001 100,111 01)2 .
3 5 1 4 7 2
Звідси слідує, що вісімкову систему числення можна використовувати для скороченого запису любого двійкового коду. При цьому використовується приблизно в двічі менше символів, якщо розбити їх на трійки цифр і кожну записати однією вісімковою цифрою. Так само запис будь-якого числа в шістнадцятковій системі числення можна використовувати для скороченого запису двійкового коду. В цьому випадку кожному шістнадцятковому символу взаємно однозначно відповідає набір з чотирьох двійкових цифр:
(0)16 = (0000)2 (8)16 = (1000)2
(1)16 = (0001)2 (9)16 = (1001)2
(2)16 = (0010)2 (а)16 = (1010)2 = (10)10
(3)16 = (0011)2 (b)16 = (1011)2 = (11)10
(4)16 = (0100)2 (c)16 = (1100)2 = (12)10
(5)16 = (0101)2 (d)16 = (1101)2 = (13)10
(6)16 = (0110)2 (e)16 = (1110)2 = (14)10
(7)16 = (0111)2 (f)16 = (1111)2 = (15)10 .
Так як записи числа в двійково-шістнадцятковій і двійковій системах за сформульованою вище теоремою співпадають, то, замінивши всі шістнадцяткові цифри деякого числа на відповідні четвірки двійкових цифр, отримаємо таке ж число в двійковій системі числення. При цьому запис числа буде використовувати приблизно в чотири раза менше цифр, ніж в двійковій системі числення. Наприклад, число (3c2e9) 16 може бути представлене в двійковій системі числення наступним чином: (11 1100 0010 1110 1001) 2.
3 c 2 e 9
Під
кожною четвіркою
двійкових
цифр ми записали
відповіднийі
шістнадцятковий
символ. Дві
форми комп’ютерного
представлення
числових даних.
Їх переваги
і недоліки.
Форма з фіксованою крапкою
В сучасних ЕОМ застосовуються два способу представлення чисел: з фіксованою крапкою і плаваючою крапкою.
В першому випадку місце коми, яка відділяє цілу частину числа від дробової, визначається на етапі конструювання ЕОМ. Зразу ж вказується кількість розрядів, які відводяться для зображення цілої і дробової частин. Причому кожному розряду комірки відповідає завжди один і той же розряд числа, що суттєво спрощує виконання арифметичних дій.
Нехай, наприклад, комірка пам’яті машини має 24 двійкових розряда. Як ми знаємо, в комірку можна записати будь-яке машинне слово, тобто довільний набір з нулів і одиниць. Якщо це слово - число, то в конструкції машини може бути передбачено його представлення в формі з фіксованою комою. Наприклад, воно може бути таким: крайній зліва розряд - знаковий, потім наступні 9 розрядів відводяться під цілу частину і, накінець, 14 розрядів, які залишилися, під дробову частину числа, тобто кома тут завжди на одному і тому ж місці - після десятого розряду машинного слова (з врахуванням знакового розряду). Тоді найбільше число, яке можна представити, буде: (111111111,11111111111111) 2.
Видно, що воно менше, ніж 29 = (512) 10. А найменше за модулем відмінне від нуля число дорівнює
(000000000,00000000000001) 2 = 2-14.
Тобто, діапазон чисел, які можна записати в комірку пам’ті машини, тут такий:
2-14 < |a| < 29.
Форма з плаваючою крапкою.
Для того, щоб збільшити діапазон чисел, використовують другу форму запису чисел - з плаваючою комою. Будь-яке число в системі числення з основою Q можна записати так:
a=A*Qp.
A називають мантисою числа, а P - порядком.
Наприклад,
в десятковій
системі
числення число
3,14 представимо
у вигляді
3,14 = 0,314*101.
Тут мантиса дорівнює 0,314, а порядок 1. Очевидно, таке представлення далеко не однозначне. Число 3,14 записати так:
3,14=3,14*100 = 31,4*10-1 = 0,0314*102 =...
Порядок числа визначає положення коми в запису мантиси. При коректуванні порядку відповідним чином змінюється і положення коми - кома ніби ”плаває".
Звідси і назва методу представлення чисел. З плаваючою комою число, як ми тільки що бачили, представляється неоднозначно. Одне з цих представлень називають нормалізованим.
В цьому випадку мантиса повинна задовільняти вимозі 1/10 <|А|< 1 (мова йде про десяткову систему числення). Iншими словами, перша цифра мантиси після коми повинна бути відмінною від нуля.
9. Представлення довільного числа в формі з плаваючою крапкою. Мантиса та порядок числа. Нормалізована форма представлення числа.
Форма з плаваючою крапкою
Для того, щоб збільшити діапазон чисел, використовують другу форму запису чисел - з плаваючою комою. Будь-яке число в системі числення з основою Q можна записати так:
a=A*Qp.
A
називають
мантисою числа,
а P - порядком.
Наприклад, в
десятковій
системі
числення число
3,14 представимо
у вигляді
3,14 = 0,314*101.
Тут мантиса дорівнює 0,314, а порядок 1. Очевидно, таке представлення далеко не однозначне. Число 3,14 записати так:
3,14=3,14*100 = 31,4*10-1 = 0,0314*102 =...
Порядок числа визначає положення коми в запису мантиси. При коректуванні порядку відповідним чином змінюється і положення коми - кома ніби ”плаває". Звідси і назва методу представлення чисел. З плаваючою комою число, як ми тільки що бачили, представляється неоднозначно. Одне з цих представлень називають нормалізованим. В цьому випадку мантиса повинна задовільняти вимозі 1/10 <|А|< 1 (мова йде про десяткову систему числення). Iншими словами, перша цифра мантиси після коми повинна бути відмінною від нуля. В нашому прикладі десяткове число а=3,14 в нормалізованій формі має вигляд
3,14=0,314*101.
Запишемо кілька чисел в двійковій системі числення в нормалізованій формі:
(7) 10 = (111) 2 = 111*20 = 111*100 = 0,111*23 = 0,111*1011
(-9,5) 10 = (-1001,1) 2 = - 0,10011*24 = - 0,10011*10100.
Нехай для представлення чисел з плаваючою комою в нас відведено 24 розряди. Нехай один розряд відведено для знаку числа, а другий для знаку