Смекни!
smekni.com

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

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

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

Содержание

Двійкова арифметика

Системи числення з довільною основою

Мішані системи числення

Форма з фіксованою крапкою

Форма з плаваючою крапкою

Прямий, зворотній та доповнюючий коди чисел

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

Аналітичне представлення булевих функцій

Мінімізація булевих функцій

Метод квайна-мак-класкі

Висновок

Висновок

Література


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

Двійкова система числення

Двійкова позиційна система числення

Позиційна система числення з основою 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сь однаковими. Ця властивість двійково-вісімкової системи числення дозволяє дуже просто переводити числа з двійкової системи в вісімкову (чи шістнадцяткову) і навпаки.

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