Аналіз теорії цифрових автоматів

9

Аналіз теорії цифрових автоматів

(курсова робота)

Содержание

• Двійкова арифметика
• Системи числення з довільною основою
• Мшан системи числення
• Форма з фіксованою крапкою
• Форма з плаваючою крапкою
• Прямий, зворотній та доповнюючий коди чисел
• Поняття про булеві функції
• Аналітичне представлення булевих функцій
• Мінімізація булевих функцій
• Метод квайна-мак-класкі
• Висновок
• Висновок
• Література
• Теорія цифрових автоматів закладає теоретичні основи роботи комп'ютерної техніки. У даній курсові роботі проводиться аналіз математичного підгрунтя даної дисципліни.
• Двійкова система числення
• Двійкова позиційна система числення
• Позиційна система числення з основою 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 розряди. Нехай один розряд відведено для знаку числа, а другий для знаку порядку:

0 1 2 3 4 5 6 7 8 9 10 11 23

Страницы: 1, 2, 3