Разработка структуры операционной части автомата

Аннотация

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

1. Основные понятия, используемые при построение автоматов

1.1 Назначение автоматов

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

По способу формирования функции выходов автоматы делятся на автоматы Мили (Mealy) и Мура (Moore).

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

В любом устройстве обработки цифровой информации можно выделить два основных блока — операционный автомат и управляющий автомат.

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

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

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

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

1.2 Деление восстановлением остатка

При деление числе без восстановления остатка делитель вычитается из делимого и определяется знак нулевого (по порядку) остатка. Если остаток положительный, т. е., то в псевдознаковом разряде частного проставляется 1, при появлении которой формируется признак переполнения разрядной сетки и операция прекращается. Если остаток отрицательный, то в псевдознаковом разряде частного записывается 0, а затем выполняется сдвиг текущего остатка на один разряд влево и прибавление к нему делителя. Знак получаемого таким образом остатка определяет первую значащую цифру частного: если остаток положителен, то в первом разряде частного записывается 1, если отрицательный, то записывается 0. Далее, если остаток положителен, то он сдвигается влево на 1 разряд и из него вычитается делитель для определения следующей цифры частного. Если остаток отрицателен, то к нему прибавляется делитель и определяется следующий остаток, знак которого определяет следующую цифру частного. Операция сдвигов и алгебраических сложений повторяется до тех пор, пока в частном не получается требуемое количество цифр.

1.3 Прямой код

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

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

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

Данное определение позволяет дать прямому коду такую интерпретацию:

Аналитическое выражение показывает, что прямой код дробного числа (J=0) формируется как сумма абсолютной величины исходного числа и единицы. Прямой код целого числа (J=n-1, причем знаковым является крайний левый разряд) формируется как сумма 10^n-1+|X|/

Прямой код получил широкое распространение в ЭЦВМ вследствие своей простоты. В нем удобно хранить числа в памяти, перемножать числа. Но, как оказалось, он плохо приспособлен для сложения чисел. Действительно, при алгебраическом сложении чисел в прямом коде требуется выполнить четыре действия.:

1. сравнить знаки слагаемых;

2. сравнить слагаемые по модулю при неравенстве их знаков;

3. выполнить соответствующую арифметическую операцию: сложение при равенстве знаков и вычитание из большего по модулю слагаемого меньшего при неравенстве их знаков;

4. присвоить алгебраической сумме знак большего по модулю слагаемого.

Так как операция сложения значительно проще вычитания, то возникает вопрос: нельзя ли каким-либо образом алгебраическое сложение свести к арифметическому? Оказывается, это возможно за счет более сложного кодирования.

2. Синтез управляющего автомата с жесткой (схемной) логикой

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

При деление числе без восстановления остатка делитель вычитается из делимого и определяется знак нулевого (по порядку) остатка. Если остаток положительный, т. е., то в псевдознаковом разряде частного проставляется 1, при появлении которой формируется признак переполнения разрядной сетки и операция прекращается. Если остаток отрицательный, то в псевдознаковом разряде частного записывается 0, а затем выполняется сдвиг текущего остатка на один разряд влево и прибавление к нему делителя. Знак получаемого таким образом остатка определяет первую значащую цифру частного: если остаток положителен, то в первом разряде частного записывается 1, если отрицательный, то записывается 0. Далее, если остаток положителен, то он сдвигается влево на 1 разряд и из него вычитается делитель для определения следующей цифры частного. Если остаток отрицателен, то к нему прибавляется делитель и определяется следующий остаток, знак которого определяет следующую цифру частного. Операция сдвигов и алгебраических сложений повторяется до тех пор, пока в частном не получается требуемое количество цифр.

2.1 Разработка структуры операционной части автомата

Структура операционной части автомата, предназначенная для реализации операции деление без восстановления остатка.

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

* два шестнадцатиразрядных регистра Рг, А и Рг В для хранения входных операндов и промежуточных результатов, причем регистр Рг, А должен обеспечить возможность сдвига своего содержимого влево;

* шестнадцатиразрядный регистр Рг С для размещения результата арифметической операции сложения или вычитания (в нашем случае в этом регистре формируется остаток): в конце операции в нем будет размещен результат — частное;

* шестнадцатиразрядный регистр Pг D с возможностью левого сдвига кода для размещения частного в процессе его формирования;

* шестнадцатиразрядный двоичный параллельный сумматор/вычитатель Сум/Выч;

* четырехразрядный вычитающий счетчик Сч и по модулю 16 для подсчета цифр частного;

* схема сравнения на «равно» знаковых разрядов исходных операндов;

*дешифратор DC «0» нулевой комбинации в разрядах C[1: 15], формирующий признак нулевого результата Z.

В операционной части автомата выполняется следующие микрооперации и логические условия, показанные на рис. 2.

Рис. 1. Структура операционного автомата

Рис. 2. Таблица микроопераций и логических условий

2.2 Построение содержательной ГСА

Содержательная граф-схема алгоритма операции деление без восстановления остатка приведена на рис. 3.

Алгоритм предусматривает формирование знака результата и сохранение его временно в переменной s. После этого производится деление модулей чисел (знаки операндов обнуляются).

Сначала производится пробное вычитание делителя из делимого. Поскольку знаки операндов — 0, то появление 1 в знаковом разряде разности означает, что, А < В, и можно продолжать деление (целая часть частного равна 0). При с₀ = 0 деление невозможно — формируется признак переполнения.

В процессе получения цифр частного значение очередного остатка принимает переменная С. Независимо от знака остатка она копируется в переменную А, которая затем увеличивается вдвое путем сдвига влево на один разряд. В зависимости от знака переменной С (знака остатка) формируется очередная цифра переменной D (частного) и принимается решение о действии на следующем шаге — добавлять или вычитать делитель из сдвинутого остатка. После арифметической операции выполняется сдвиг влево частного D (освобождается место для очередной цифры частного), изменяется счетчик цифр частного и проверяется условие выхода из цикла — получение шестнадцати цифр частного, включая самую первую цифру — «0 целых», на место которой копируется знак частного из переменной s.

Рис. 3. Содержательная ГСА операций деление без восстановления остатка

2.3 Получение функциональной ГСА

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

Y₁ = y₁; Y₂ = y_2; Y₃ = y₃, y_4; Y₄ = y₅; Y₅ = y₆, y₈; Y₆ = y₉;

Y₇ = y₁₀; Y₈ = y₁₁, y₅; Y₉ = y₁₂, y₁₃; Y₁₀ = y₁₄, y₁₅; Y₁₁ = y₁₆;

Y₁₂ = y₁₇.

Рис. 4. Функциональная ГСА

2.4 Получение отмеченной ГСА

При синтезе управляющего автомата на базе автомата Мура получение отмеченной ГСА производится по следующим правилам:

Рис. 5. Получение отмеченной ГСА

2.5 Построение графа автомата

Рис. 6. Граф автомат Мур

2.6 Кодирование состояния автомата

Кодирование состояния автомата заключается в установлении взаимно-однозначного соответствия между множеством состояний автомата и множеством элемента памяти. Для простоты ограничимся использованием в качестве элементов памяти RS — триггеров, которые будет обозначать Т₁,…, Т_n. Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния с кодом 0101 в состояние с кодом 1001, то это означает, что триггер Т₁ переходит из состояния «0» в состояние «1» триггер Т₂ — из состояния «1» в состояние «0», а состояние триггеров Т₃ и Т₄ не изменяются.

Рис. 7. Кодирование состояний автомата

2.7 Составление структурных таблиц переходов

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

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

Рис. 8. Автоматная таблица переходов

2.8 Определение систем логических функций для выходных сигналов и сигналов возбуждения и их совместная минимизация

Системы логических функций для выходных сигналов и сигналов возбуждения для рисунка 8 имеют следующий вид:

В результате минимизации данных систем логических функций получим:

2.9 Построение функциональной схемы управляющего автомата

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

Рис. 9. Функциональная схема автомата Мура

Заключение

В результате курсовой работы была достигнута цель приобретение практических навыков по ниже следующим разработкам:

— разработка структуры операционной части автомата

— построение содержательной, функциональной и отмеченной ГСА

— построение граф автомата и кодирование его состояние

— составление структурных таблиц переходов автомата Мура

— определение систем логических функций для выходных сигналов и сигналов возбуждения и их совместная минимизация

— построение функциональной схемы управляющего автомата.

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

2. А. П. Жмакин. Архитектура ЭВМ. Уч. пособие. Санкт Петербург, БХВ-Петербург, 2006.

3. Б. Я. Цилькер, С.А., Орлов. Организация ЭВМ и систем: Учебник для вузов. — СПб: Питер, 2004.

4. А. Я. Савельев. Основы информатики. Учеб. для ВУЗовМ.: Изд-во МГТУ им. А. Э. Баумана, 2001.