- •Министерство образования и науки украины
- •Содержание
- •Глава 1 Арифметико-логические основы эвм
- •1.1 Информационные процессы
- •1.2. Обмен информацией между различными информационными устройствами
- •1.3. Аппаратные средства хранения и обработки информации
- •Глава 2 представление числовой информации в цифровом автомате
- •2.1. Системы счисления и понятие кода
- •2.2. Выбор системы счисления
- •2.3. Формальные правила двоичной арифметики
- •2.4. Перевод числа из одной позиционной системы счисления в другую
- •Глава 3 формы представления чисел в цифровых автоматах
- •3.1. Форма представления двоичных чисел с фиксированной запятой
- •3.2. Представление отрицательных чисел в формате с фиксированной запятой
- •3.3. Форма представление чисел с плавающей запятой
- •3.4. Перевод чисел из формата с фиксированной запятой в формат с плавающей запятой и обратно
- •3.5. Погрешности представления чисел
- •20 [A]ф2n- 1 для целых чисел
- •Глава 4. Арифметические действия с двоичными числами
- •4.1. Сложение двоичных чисел
- •4.1.1. Алгебраическое сложение чисел, представленных в форме с фиксированной запятой
- •4.1.2. Переполнение разрядной сетки
- •4.1.3. Модифицированный прямой, обратный и дополнительный код
- •4.1.4. Алгебраическое сложение чисел, представленных в форме с плавающей запятой
- •4.2. Умножение двоичных чисел
- •4.2.1. Методы умножения двоичных чисел
- •4.2.2. Умножение чисел, представленных в форме с фиксированной запятой
- •4.2.3. Умножение чисел, представленных в форме с плавающей запятой
- •4.2.4. Ускорение операции умножения
- •4.3. Деление двоичных чисел
- •4.3.1. Деление двоичных чисел, представленных в форме с фиксированной запятой.
- •4.3.2. Деление двоичных чисел, представленных в форме с плавающей запятой.
- •4.4. Оценка точности выполнения арифметических операций
- •4.4.1. Погрешность округления
- •Глава 5. Выполнение операций над двоично-десятичными числами
- •5.1. Представление десятичных чисел в д-кодах
- •5.2. Формальные правила поразрядного сложения в д-кодах
- •5.3. Представление отрицательных чисел в д-кодах
- •5.4. Выполнение операций сложения и вычитания в д-кодах
- •5.5. Умножение чисел в д-кодах
- •5.6. Деление чисел в д-кодах
- •5.7. Перевод чисел из д-кода в двоичный и из двоичного в д-код
- •Глава 6 Информационные основы цифровых автоматов
- •6.1. Понятие об информации и её преобразованиях
- •6.2. Преобразования алфавитной информации
- •6.3 Понятие об алгоритме
- •6.4 Понятие о дискретном (цифровом) автомате
- •Глава 7 Основы логического проектирования ца. Основные понятия алгебры логики.
- •7.1. Свойства элементарных функций алгебры логики
- •7.2. Аналитическое представление функций алгебры логики
- •7.3. Совершенные нормальные формы
- •7.4. Системы функций алгебры логики
- •7.5. Числовое и геометрическое представление фал
- •Глава 8 Минимизация функций алгебры логики
- •8.1 Метод Квайна
- •Ядро: мднф:
- •8.2 Метод Квайна-Мак-Класки
- •Простые импликанты: *111, 111*, 0**1
- •8.3 Метод Нельсона
- •8.4 Метод диаграмм Вейча
- •8.5 Метод самопонижающихся циклов
- •8.6 Минимизация монотонных функций
- •8.7 Минимизация конъюнктивных нормальных форм
- •8.8 Минимизация частично определенных булевых функций
- •8.9 Минимизация функций в базисах и-не и или-не
- •8.10 Минимизация систем булевых функций
- •Глава 9 Абстрактная теория автоматов
- •9.2 Декомпозиция абстрактных автоматов
- •Глава 10 Структурная теория автоматов
- •10.1 Композиция автоматов
- •Глава 11 Проектирование асинхронных цифровых автоматов
- •11.1 Проектирование комбинационных схем (кс) с учетом кобъед по входу и по выходу
- •11.2 Проектирование кс на дешифраторах и мультиплексорах
- •11.3 Проектирование кс на пзу
- •11.4 Проектирование кс на плм
- •Глава 12 Канонический метод структурного синтеза ца с памятью
- •12.1 Кодирование
- •12.2 Выбор элементов памяти автомата
- •12.3 Выбор структурно-полной системы элементов
- •12.4 Построение уравнений булевых функций возбуждения и выходов автомата
- •12.5 Построение функциональной схемы автомата
- •Глава 13 Обеспечение устойчивости функционирования ца
- •13.2 Проблема синтеза надёжных схем из ненадёжных элементов
- •13.3 Коды Хэмминга
- •Глава 14 Микропрограммные автоматы
- •14.2 Граф-схемы алгоритмов
6.2. Преобразования алфавитной информации
В наиболее общем виде преобразование алфавитной информации может быть следующим способом. Пусть даны два конечных алфавита и. Обозначим черезсовокупность всех слов конечной длины в алфавите Х, через- совокупность всех слов конечной длины в алфавитеY. Если исходная информация записывается в алфавите Х, а конечная информация – в алфавитеY, то произвольное преобразование информациибудет представлять собой не что иное, как отображение множестваFв множествеG.
В дальнейшем мы будем рассматривать только детерминированныепреобразования информации, при которых входное слово полностью определяет слово на выходе преобразователя. Т.о. требование детерминированности есть не что иное, как требованиеоднозначностиотображения.
Целесообразно в общем случае считать частичнымотображением, т.е. задавать отображениене обязательно на всем множествеF, а лишь на части этого множества. Введение частичных отображений позволяет вместо отображений одного множества слов в другое рассматривать лишь отображение таких множеств в себя. Для этой цели достаточно ввести объединенный алфавити множествослов в этом алфавите. Ясно, что вместо отображения (или частичного отображения) множестваFв множествоGможно рассматривать частичное отображение множества Н в себя. Это частичное отображение будет определено для слов, состоящих только из букв.
Однозначность отображения множестваfв множествоGне означает однозначности обратного отображения. Если же такая однозначность имеет место, то отображениеназываетсявзаимнооднозначным, в этом случае отображениеосуществляетэквивалентноепреобразование информации.
Пример 1 (зеркало) – эквивалентное. Пример 2 (сумма двух чисел) – не эквивалентное.
Преобразования, заключающиеся в замене каждой буквы исходного алфавита некоторой определенной комбинацией букв нового алфавита с фиксированной длиной, называются простейшимиилипобуквенными.
С помощью простейших эквивалентных преобразований, информацию, заданную в любом конечном алфавите, можно записать в алфавите, содержащем только 2 буквы. Это – стандартный двухбуквенныйилидвоичныйалфавит.
Если число букв в исходном алфавите А – n, то число слов, отображающих буквы алфавита А в двоичный алфавит должно быть, где- разрядность (длина) слова. Такое преобразование называетсядвоичнымкодированиеминформации и оно неоднозначно. Т.о. при двоичных преобразованиях информации можно предполагать. Что как исходная, так и заключительная информация задана в некотором стандартном алфавите.
Пример сведения сложного процесса преобразования информации к преобразованию слов в двоичном алфавите – распознавание рисунков.
,.
6.3 Понятие об алгоритме
С дискретной точки зрения произвольное преобразование информации – это отображение множества слов в некотором конечном алфавите в множестве слов в том же самом или любом другом конечном алфавите. Будем называть такие отображения алфавитнымиоператорами.
Каковы способы задания алфавитных операторов?
Алфавитные операторы, задаваемые с помощью конечных систем правил, называются алгоритмами.
Примеры: сложение двух чисел – алгоритм состоит из правила поразрядного сложения, правила сложения цифр (таблица сложения) и правила переноса.
Недостаток определения алгоритма – отсутствие математической точности.
В качестве способа точного задания произвольного алгоритма можно привести нормальныеалгоритмыА.А. Маркова, который преобразует слова, заданные в любом конечном алфавитев слова в том же самом алфавите, причем, обычно, алгоритм задает лишь частичное отображение.
Нормальный алгоритм задается конечной таблицейподстановокслов в данном алфавите.
Пример: существует алфавит ; таблица подстановок:
1. ;
2. ;
3. .
Пусть задано слово . Алгоритм преобразования:
1) ;
2) ;
3) ;
4) далее не применима ни одна формула.
Результат: .
Установлено, что любой алгоритм эквивалентен некоторому нормальному алгоритму.