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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

Висновок

Висновок

Література

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

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

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

Позиційна система числення з основою 2 називається двійковою. Для запису чисел в двійковій системі використовуються лише дві цифри: 0 і 1. Число два, тобто основа системи подається як 10₂.

Зручність системи - в її надзвичайній простоті.

Недолік - основа системи мала, тому для запису навіть не дуже великих чисел треба використовувати багато знаків.

Переведення числа з двійкової системи числення в десяткову та з десяткової у двійкову.

Нам уже відомо, що число N, записане в системі числення з основою p як (±a_ka_k-1…a₁a₀) _p, рівне N=a_k∙p^k+a_k-1∙p^k-1+…+a₁∙p+a₀

Тому:

1001₂=1∙2³+0∙2²+0∙2¹+1∙2⁰=8+0+0+1=9₁₀

100001₂=1∙2⁵+0∙2⁴+0∙2³+0∙2²+0∙2¹+1∙2⁰=32+0+0+0+0+1=33₁₀

Щоб перевести число із десяткової системи числення у двійкову, треба послідовно ділити десяткове число і його десяткові частки на основу двійкової системи, тобто на число 2. Ділення продовжується до тих пір, поки одержана частка не буде менша основи нової системи числення, тобто 2.

1 |40|2_

0 |20|2_

0 |10|2

0|5|2

1|2|2

0|1

Отже число 81₁₀ в двійковій системі: 1010001₂

Переведемо число 100:

100|2_

0 |50|2_

0 |25|2_

1 |12|2

0|6|2

1|3|2

1|1

Отже, (100) ₁₀= (1100100) ₂

З переводом чисел з десяткової системи одиниць у двійкову приходиться постійно мати справу при роботі на ЕОМ.

Окрему позицію в записі числа називають розрядом. Число розрядів - розрядність (довжина). Номер позиції - номер розряду. Довжина числа - це к-сть позцій (розрядів) в записі числа. В технічному розумінні це довжина розрядної сітки.

Чим менша основа системи, тим більша довжина числа. Якщо довжина розрядної сітки n, то: A_{q max}=q^n-1; A_{q min}= - (qⁿ-1);

Діапазон представлення чисел в заданій системі:

A_{q max} ≥ДП≥ A_{q min.}

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

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

Таблиця додавання

0+0=0

0+1=1

1+0=1

1+1=10₂

(додавання нуля не міняє числа, а один плюс один буде два).

Таблиця множення

0∙0=0

0∙1=0

1∙0=0

1∙1=1

(число, помножене на нуль, є нуль; множення на один не міняє числа).

Додавання. Додавання багатозначних чисел відбувається так само, як і в десятковій системі, тобто порозрядно, починаючи з молодшого.

101101₂ - 1 доданок

+ 10100₂ - 2 доданок

1000001₂ - сума

Перевіримо правильність наших обчислень:

101101₂=1∙2⁵+0∙2⁴+1∙2³+1∙2²+0∙2¹+1∙2⁰=32+0+8+4+0+1=45₁₀

10100₂=1∙2⁴+0∙2³+1∙2²+0∙2¹+0∙2⁰=16+0+4+0+0=20₁₀

45₁₀+20₁₀=65₁₀

1000001₂=1∙2⁶+0∙2⁵+0∙2⁴+0∙2³+0∙2²+0∙2¹+1∙2⁰=64+0+0+0+0+0+1=65₁₀

Віднімання

0-0=0

1-0=1

1-1=0

10₂-1=1

Знайдемо: 111010111₂-1100001₂

111010111₂

- 1100001₂

101110110₂

Крапки, поставлені над деякими розрядами, показують, що в двійковій системі одиниця відміченого розряду роздроблюється на дві одиниці вищого розряду.

Множення

11101₂∙1101₂

11101_{2 -} множник

1101₂ - множник

11101 - множене

+11101 - множене, зсунуте на 2 розряди вліво

11101 - множене, зсунуте на 3 розряди вліво

101111001₂ - добуток

Перевірка:

11101₂=1∙2⁴+1∙2³+1∙2²+0∙2¹+1∙2⁰=16+8+4+1=29₁₀

1101₂=13₁₀; 29∙13=377₁₀

101111001₂=1∙2⁸+0∙2⁷+1∙2⁶+1∙2⁵+1∙2⁴+1∙2³+0∙2²+0∙2¹+1∙2⁰=256+0+64+32+16+8++0+1=377_10.

Отже, в двійковій арифметиці при множенні не потрібна таблиця множення. Не треба знаходити добутки першого множника на значення послідовних розрядів другого множника, так як значення цих розрядів або 1 або 0.

Достатньо записати значення першого множника одне під одним із зсувом на один розряд; у випадку рівності якого-небудь розряду другого множника нулю, його зсувають на два розряди.

1101111₂

101101₂

1101111

1101111

1101111

1101111 __

1001110000011₂

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

Ми розглянули алгоритм переводу чисел з двiйкової системи числення в десяткову i навпаки - з десяткової в двiйкову. Алгоритми залишаться цiлком аналогiчними, якщо замiсть двiйкової системи числення взяти будь-яку iншу.

Нехай, наприклад, деяке число записане в вiciмковiй системi числення. Це значить, що цифри в записі цього числа є коєфiцiєнти в його розкладi по степенях числа 8:

(a_na_n-1... a₁a₀, a_-1a_-2. .) ₈ =a_n*8ⁿ+a_n-1*8^n-1+... +a₁*8+a₀+a_-1*8^-1+...

Для того,щоб отримати зображення цього числа в десятковiй системi числення, достатньо виконати, користуючись десятковою арифметикою, всi операцiї в правiй частинi цього виразу. Приклад. Перевести число (276,54) ₈ з вiсiмкової системи числення в десяткову:

(276,54) ₈=2*8²+7*8¹+6*8⁰+5*8^-1+4*8^-2=128+56+6+5/8+4/64= (190,6875) ₁₀.

Нехай тепер потр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) ₁₀ з десяткової системи числення в вiсiмкову.

Переведемо цiлу частину:

190 | 8

16 | 23 | 8

30 16 | 2 | 8 (190)₁₀=(276)₈