Xreferat.com » Рефераты по информатике и программированию » Аналіз теорії цифрових автоматів

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

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

Содержание


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

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

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

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

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

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

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

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

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

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

Висновок

Висновок

Література

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

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

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

Позиційна система числення з основою 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 розряди. Нехай один розряд відведено для знаку числа, а другий для знаку

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: