Теория автоматов

 

Теория  автоматов. Введение.

 

Теория  автоматов. Арифметика ЦВМ

 

Теория  автоматов. Системы счисления

 

Теория  автоматов. Конечные цифровые автоматы.

Министерство общего и профессионального  образования  Российской федерации

Тверской государственный  технический  университет

 

 

Кафедра электронных вычислительных машин

 

 

 

 

 

 

 

Теория автоматов

 

 

Конспект лекций

для студентов специальности 22.01  (Вычислительные машины, системы, комплексы и сети)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тверь 2004

 

 

Курс «Теория автоматов» является одной из важнейших компонент федерального государственного образовательного стандарта по направлению «Информатика и вычислительная техника» и входит в естественнонаучный цикл дисциплин  российской высшей школы.

Курс служит формированию знаний и  умений, которые образуют теоретический  фундамент, необходимый для корректной постановки и решения проблем  в области проектирования элементов вычислительных устройств на нижнем логическом уровне на примере арифметики ЦВМ.

Освоение методов теории автоматов  необходимо для дальнейшего изучения специальных дисциплин, связанных  со схемотехническим проектированием  устройств вычислительной техники.

Методические указания предназначены для студентов специальности ЭВМ, изучающих курс "Теория автоматов".

Методические указания рассмотрены  на заседании кафедры №  от       и рекомендованы к изданию.

 

Автор АСЕЕВА Т.В

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

	ã Тверской государственный технический университет, 2002

 

 

.

 

Введение

Конечные автоматы и такие связанные с ними конструкции как линейные грамматики и регулярные выражения относятся  к важнейшим понятиям информатики. Различные варианты конечных автоматов и близкие им математические объекты служат для описания и анализа технических устройств,  различных систем и процессов, программ и алгоритмов.  Теория автоматов является одним из старейших разделов теоретической информатики.

В  читаемом курсе рассматриваются  цифровые автоматы как теоретическая  основа проектирования аппаратных средств ЭВМ последовательного типа. В этом случае принято рассматривать цифровой автомат как совокупность операционного  автомата (исполнительного устройства) и управляющего автомата (собственно конечного автомата), образующих операционное устройство.

Устройство, исполняющее алгоритм процедурного типа, называется операционным устройством (ОУ).  ОУ можно рассматривать как один синхронный автомат со сложно структурированной памятью - состоянием: часть памяти используется для идентификации  шага алгоритма, остальная память используется для запоминания промежуточных данных, вычисляемых в процессе последовательного (по шагам) выполнения алгоритма. Такая модель вычислителя особенно удобна для расчета продолжительности одного такта работы устройства.

УА инициирует действия  отдельных шагов алгоритма и участвует в их выполнении.

ОА выполняет все вычисления на отдельных шагах алгоритма  под управлением УА. Кроме того, к  ОА удобно отнести все вычисления  предикатов, оставив УА  только анализ вычисленных значений предикатов.

Конспект лекций включает разделы, относящиеся к арифметическим основам  ЭВМ, основные концепции которых  можно найти в учебниках¹,²

Каноническое описание синхронного  конечного автомата можно интерпретировать как одношаговый алгоритм процедурного типа. Исполнитель этого алгоритма состоит только из ОА. На каждом шаге этого алгоритма изменяется вся память устройства, поэтому управление памятью не требуется, нет необходимости идентифицировать шаги этого алгоритма.

Проектирование ОУ включает следующие  этапы:

• Изучение алгоритма выполнения операции,
• Определение необходимого состава структурных элементов ОА, таких как, регистры, сумматоры, оригинальные комбинационные схемы;
• Определение необходимых форматов структурных элементов;
• Составление граф схемы алгоритма (ГСА) выполнения операции;
• Построение управляющего автомата.

В ОА выполняются микрооперации  над данными, которые поступают  из памяти и хранятся в регистрах. Множество регистров образуют сверхбыструю память. Обработка данных в ОУ происходит с минимальным числом обращений к внешней памяти, а именно, обращение к внешней памяти происходит дважды за время работы автомата: первое обращение – получение данных, второе обращение – передача в память результатов обработки. Автомат такого типа называется автоматом с жесткой логикой.  В отличие от микропрограммных автоматов, которые выполняют те же функции с обращением к памяти на каждом такте. Так как обращение к внешней памяти требует больших затрат времени по сравнению с обращением к регистровой памяти, автоматы с жесткой логикой имеют повышенное быстродействие. Такие автоматы являются основой RISK – процессоров.

Автомат с жесткой логикой работает в дискретном времени. Поэтому на вход УА поступает синхронизирующий сигнал, который определяет это дискретное время. В каждом такте автоматного времени УА активизирует набор микроопераций (образующих микрокоманду), которые выполняются в ОА. Промежуточные результаты обработки данных, а также значения предикатов, отображающих состояния отдельных элементов ОА, также хранятся в регистровой памяти ОА.

Микрооперация - базисное (элементарное) действие, необходимое  для получения (вычисления) значения одной или более переменных.

Микрооперация присваивания: при любых  условиях разрядность левой и  правой частей равны. Неиспользуемые разряды в правой части микрооперации обозначаются  "*". Микрооперации  входят в состав микрооператоров.  Микрооператор - набор взаимосвязанных микроопераций (или одна микрооперация), выполняемых одновременно и необходимых для получения одного или более значений.

Микрокоманда - набор сигналов, поступающих из УА в ОА и интерпретируемый как управляющий, т.е. необходимый для выполнения всех микроопераций данного микрооператора.

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

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

Блок схема ОУ приведена на рисунке 1. Здесь Х – множество  осведомительных сигналов о состоянии  контролируемых элементов ОА. У –  множество микрокоманд,  вырабатываемых в УА в соответствии с ГСА.  G – команда, инициализирующая процесс выполнения задачи. СС – синхронизирующий сигнал. КР – сигнал окончания работы ОУ.

Операционный автомат выполняет  все операции над числами на основании  последовательных алгоритмов.

 

Арифметика ЦВМ

Формы представления чисел в  ЭВМ

Числа в ЭВМ представляют в формах с фиксированной и с плавающей  запятой.

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

Представление целых  чисел: запятая фиксирована слева от младшего разряда. В случае правильных дробей запятая фиксирована справа от старшего разряда. В обоих случаях диапазон представимых чисел, определяемый как отношения максимального числа в заданной разрядной сетке к модулю минимального представимого в этой разрядной сетке числа,  равен D_ФТ= 2ⁿ-1.

Представление чисел  в форме с плавающей запятой

Эта форма представления называется также логарифмической. Число представляют в виде произведения мантиссы, которая  удовлетворяет в случае нормализованного представления неравенству p^-1£ |m| < 1, и p^П, где П – двоичное число, формат которого определяет диапазон представимых чисел, p – основание системы счисления. В случае k-разрядной сетки порядка (k числовых разрядов) порядок принимает значения –(2^k-1) £ П £ 2^k-1. Поэтому диапазон представимых чисел в форме с плавающей запятой в случае нормализованного представления равен

Последнее выражение показывает, что  диапазон представимых чисел  в этом случае определяется разрядностью порядка. Мантисса же  определяет точность представления чисел. Вычисления в форме с плавающей запятой  являются принципиально не точными. Ошибка вычислений связана, с одной стороны, с погрешностью исходного представления числа, обусловленная ограниченностью разрядной сетки мантиссы, и с другой стороны, с алгоритмическими особенностями выполнения операций с плавающей запятой.

Представление чисел со знаком в  ЭВМ

Для кодирования знака используется один бит, который принимается равным 0 в случае положительного числа, и 1 – отрицательного. В формате регистра знаковому разряду отводится определенное место. Для представления чисел со знаком  применяют три вида кодов. Правило записи чисел со знаком не зависит от того, в каком месте фиксирована запятая. Мы будем в дальнейшем подразумевать, что запятая фиксирована слева от старшего разряда, имея в виду, что при выполнении действий с плавающей запятой операции сложения, умножения, деления выполняются над мантиссами, а порядки в соответствии с логикой операции выравниваются, складываются или вычитаются.

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

Например, [0,1101]_П=0,1101; [-0,1101]_П=1,1101. Знаковый разряд несет в случае прямого кода смысловую, но не арифметическую нагрузку и не может участвовать в подсуммированиях.  Алгебраическое сложение в прямом коде невозможно. Поэтому прямой код, как правило, не применяется для выполнения арифметических операций. 

Дополнительный код:

 где p – основание системы счисления.

Основание любой системы счисления  представляется как 10.  Пусть А=-0,1101. Дополнительный код определится следующим образом:

10,0000

-0,1101

1,0011 -  это дополнительный  код числа А. Чтобы получить  его, достаточно инвертировать все цифры в естественной записи числа, включая знаковый разряд, до последней значащей цифры. Последняя значащая цифра не инвертируется. Знаковая цифра в дополнительном коде имеет вес 2⁰=1. Поэтому он может принимать участие в выполнении арифметических операций наравне с числовыми разрядами.  Дополнительный код позволяет выполнять операции алгебраического сложения. Результат при этом получается автоматически с правильным знаком. Если при сложении со знакового разряда спадает 1, она теряется.

Обратный код образует код числа в соответствии с правилом:

 

где n – количество числовых разрядов,  p – основание системы счисления.

Для представления отрицательного двоичного числа в обратном коде достаточно инвертировать все цифры в естественной записи числа, включая знаковую цифру. Например,

[-0,1101]_О = 1,0010; [0,1101]_О = 0,1101.

Знаковый разряд в обратном коде, так же, как в дополнительном, имеет вес 1 и участвует в подсуммированиях наравне с числовыми разрядами.  Из правила образования обратного кода следует, что для получения дополнительного кода отрицательного двоичного числа достаточно прибавить 1 в младший разряд его обратного кода.

Алгебраическое сложение двоичных чисел в обратном коде дает автоматически  результат с правильным знаком.

Сформулированные правила справедливы  для любой системы счисления. Необходимо иметь в виду, что в  системе счисления с любым основанием разряды, занимающие позиции знакового разряда (слева от старшего разряда числа), складываются как двоичные.

Переполнение разрядной сетки

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

1. При сложении чисел с одинаковым знаком получается результат другого знака.
2. При сложении двух чисел имеется перенос из старшего числового разряда в знаковый разряд, но отсутствует  перенос из знакового разряда.
3. При сложении двух чисел имеет место перенос из знакового разряда, но отсутствует перенос из старшего числового разряда в знаковый.
4. При наличии обоих переносов (из старшего числового разряда в знаковый и из знакового разряда) переполнение разрядной сетки отсутствует.

При наличии очень жестких ограничений  на разрядность аппаратных средств  эти критерии позволяют обнаруживать переполнение разрядной сетки. Однако, более удобный критерий переполнения имеет место при использовании модифицированных кодов.

Модифицированные коды.

В модифицированных кодах вслед  за знаковым разрядом  вводится разряд переполнения, имеющий формат цифр используемой системы счисления. Т.е. в двоичной системе счисления разряд переполнения занимает один бит. В десятичной и шестнадцатеричной – четыре бита. В восьмеричной – три бита. При выполнении алгебраического сложения первый знаковый разряд, он обозначается Sg1, всегда сохраняет правильное значение знака результата. Разряд переполнения служит для контроля переполнения разрядной сетки.