Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

И. В. Потапов элементы прикладной теории цифровых автоматов

Учебное пособие

Омск

Издательство ОмГТУ

2011

УДК 004.315(075)

ББК 32.973.2я73

П64

Рецензенты:

М. Ф. Шакиров, канд. техн. наук, доцент, зам. руководителя Управления Роскомнадзора по Омской области;

В. Т. Гиль, канд. техн. наук, доцент ОмА МВД России

Потапов, И. В.

П64 Элементы прикладной теории цифровых автоматов: учеб. пособие / И. В. Потапов. – Омск: Изд-во ОмГТУ, 2011. – 156 с.

ISBN 978-5-8149-1039-4

В пособии рассматриваются основы построения алгоритмов выполнения арифметических операций над числами, представленными прямыми и инверсными кодами в двоичной однородной позиционной системе счисления, а также в D-кодах. Даны подробные примеры выполнения арифметических операций. Рассмотрены различные способы представления числовой информации в ЭВМ. Описаны базовые принципы построения логических схем прямого распространения по их аналитическому описанию и методы минимизации таких схем. Рассмотрены базовые подходы к построению моделей функционирования и структурному синтезу цифровых автоматов с памятью.

Пособие предназначено для студентов технических вузов очной, заочной и дистанционной форм обучения, обучающихся по направлению «Информатика и вычислительная техника», изучающих базовые специальные дисциплины.

Печатается по решению редакционно-издательского совета

Омского государственного технического университета

УДК 004.315(075)

ББК 32.973.2я73

© ГОУ ВПО «Омский государственный

технический университет», 2011

ISBN 978-5-8149-1039-4

Оглавление

ВВЕДЕНИЕ 5

1. ПРЕДСТАВЛЕНИЕ ЧИСЕЛ В ЭВМ 8

1.1. Позиционные системы счисления 8

1.2. Обоснование применения в ЭВМ двоичной системы счисления 10

1.3. Представление двоичных чисел с фиксированной и плавающей запятой 12

1.4. Прямой и инверсные коды чисел 15

1.5. Двоично-десятичные коды чисел 18

Вопросы для самоконтроля 21

2. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ В ДВОИЧНЫХ КОДАХ 22

2.1. Сложение двоичных кодов 22

2.2. Вычитание двоичных кодов 25

2.3. Выполнение операции округления чисел 26

2.3.1. Округление прямых кодов 26

2.3.2. Округление инверсных кодов 29

2.4. Умножение двоичных кодов 29

2.4.1. Умножение прямых кодов чисел 30

2.4.2. Ускоренное выполнение операции умножения 34

2.4.3. Умножение инверсных кодов чисел 40

2.5. Деление двоичных кодов 42

2.5.1. Деление прямых кодов чисел 43

2.5.2. Ускоренное выполнение операции деления 47

2.5.3. Деление дополнительных кодов чисел 50

2.6. Извлечение квадратного корня 52

2.7. Выполнение арифметических операций в D-кодах 55

2.7.1. Сложение в D-кодах 55

2.7.2. Умножение в D-кодах 57

2.7.3. Деление в D-кодах 60

Вопросы для самоконтроля 62

3. ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ 64

3.1. Основные определения и способы задания ПФ 65

3.2. Элементарные логические функции 68

3.3. Основные законы алгебры логики 69

3.4. Полные системы переключательных функций 70

3.5. Канонические формы аналитического представления ПФ 72

3.6. Кубическое представление ПФ 76

3.7. Синтез комбинационных схем 78

3.7.1. Синтез КС на логических элементах 78

3.7.2. Синтез КС на дешифраторах 80

3.7.3 Синтез КС на мультиплексорах 83

3.7.4 Синтез многовыходных схем 85

3.8. Риски сбоя в комбинационных схемах 85

Вопросы для самоконтроля 88

4. МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ 89

4.1. Минимизация ПФ с помощью карт Карно 92

4.2. Минимизация ПФ методом Квайна 96

4.3. Минимизация методом Квайна – Мак-Класки 100

4.4. Минимизация ПФ методом Блейка – Порецкого 103

4.5. Минимизация ПФ, заданных в конъюнктивной форме 105

4.6. Минимизация не полностью определенных ПФ 107

4.7. Минимизация систем ПФ 109

4.8. Минимизация ПФ в универсальных базисах И-НЕ, ИЛИ-НЕ 115

Вопросы для самоконтроля 119

5. МОДЕЛИРОВАНИЕ РАБОТЫ И СИНТЕЗ АВТОМАТОВ С ПАМЯТЬЮ 120

5.1. Основные модели, понятия и определения 120

5.1.1. Общее понятие цифрового автомата с памятью 120

5.1.2. Основные модели цифровых автоматов 122

5.1.3. Описание функционирования цифровых автоматов 124

5.1.4. Задание цифровых автоматов 125

5.1.5. Правила перехода между моделями Мили и Мура 127

5.2. Минимизация числа состояний цифровых автоматов 129

5.2.1. Минимизация числа состояний синхронного автомата методом Полла-Ангера 130

5.2.2. Минимизация числа состояний автомата Мура методом l-эквивалентных разбиений 135

5.2.3. Минимизация числа состояний автомата Мили методом l-эквивалентных разбиений 137

5.3. Структурный синтез цифровых автоматов 140

5.3.1. Типы элементарных автоматов, обладающие полной системой переходов-выходов 141

5.3.2. Основные этапы структурного синтеза 144

5.4. Рациональный выбор варианта кодирования состояний синхронных автоматов 151

Вопросы для самоконтроля 153

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 154

ПРИЛОЖЕНИЕ. Задания для выполнения самостоятельных работ 155