Аналіз теорії цифрових автоматів
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=00+1=11+0=11+1=102(додавання нуля не міняє числа, а один плюс один буде два).Таблиця множення0•0=00•1=01•0=01•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=4510101002=1•24+0•23+1•22+0•21+0•20=16+0+4+0+0=20104510+2010=651010000012=1•26+0•25+0•24+0•23+0•22+0•21+1•20=64+0+0+0+0+0+1=6510Віднімання0-0=01-0=11-1=0102-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.
Страницы: 1, 2, 3
|