Информационные основы вычислительных систем

Введение 

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

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

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

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

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

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

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

    Над целыми двоичными числами (или двоичными дробями), выполняются операции сложения, вычитания, умножения и деления. 

    Сложение  чисел  

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

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

    В данной работе рассматривается алгебраическое сложение в дополнительном коде.

      Дополнительный  код (англ Two's complement) — наиболее распространенный способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения, чем упрощает архитектуру ЭВМ. Дополнительный код отрицательного числа получается инвертированием двоичного числа и прибавлением к нему единицы.

    Алгебраическое  сложение многоразрядных чисел обычно организуется как регулярный процесс, состоящий из «n» - одинаковых операций поразрядного сложения, вычитания (где «n» - количество разрядов в каждом из операндов). При этом в зависимости от знаков слагаемых возможны четыре случая:

1. Х₁ > 0, Х₂ > 0, Х₃ = Х₁ + Х₂ > 0;
2. Х₁ > 0, Х₂ < 0, Х₃ = Х₁ + Х₂ > 0;
3. Х₁ < 0, Х₂ > 0, Х₃ = Х₁ + Х₂ < 0;
4. Х₁ < 0, Х₂ < 0, Х₃ = Х₁ + Х₂ < 0;

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

1. Х₁ > 0, Х₂ > 0, Х₃ = Х₁ + Х₂ > 0. В этом случае правила сложения в дополнительном не отличается от правил сложения прямого кода.
2. Х₁ > 0, Х₂ < 0, Х₃ = Х₁ + Х₂ > 0. В этом случае на основании взаимосвязи между дополнительным кодом числа Х и его выражением можем записать:

    [ Х₁]_доп + [ Х₂]_доп =  Х₁ + 2 + Х₂

    Полученный  результат отличается от окончательного двойкой. Значит надо сделать поправку вычесть с первоначального результата двойку.

3. Х₁ < 0, Х₂ > 0, Х₃ = Х₁ + Х₂ < 0. В этом случае [ Х₁]_доп + [ Х₂]_доп =  Х₁ + 2 + Х₂ , как и в обратном коде получаем итоговый результат без поправки.

    4)  Х₁ < 0, Х₂ < 0, Х₃ = Х₁ + Х₂ < 0.

    В этом случае результат [Х₁]_доп + [ Х₂]_доп = 2 + Х₁ + 2 + Х₂ даёт первоначальный результат. Итоговый результат при этом [Х₁ + Х₂  < 0]_доп = 2 + Х₁ + Х₂ равен, а значит разница в двойке. Значит надо сделать поправку вычесть двойку с первоначального результата.

    Для контроля за переполнением разрядной  сетки арифметического устройства используются модифицированные коды слагаемых, в которых знаки чисел изображаются двумя цифрами: плюс изображается 00, а минус – 11. Остальные две комбинации (01 и 10) являются запрещёнными, и появление их в знаковых разрядах суммы говорит о переполнении разрядной сетки.

    Дополнительный  код используется для кодирования  отрицательных значений X = 1*2*3. . . хп, вступающих в операцию сложения.

    Дополнительный  код Хд можно формировать следующим образом

Хдоп = Хобр + 1, т. е. путем увеличения обратного кода на единицу. Это действие реализуется с помощью сумматора АУ. 

1. Разработка структуры операционной части автомата и алгоритма выполнения деления на нем 

    Операция  сложения с использованием дополнительного  кода X реализуется следующим алгоритмом:

      - если знак операнда положителен,  то операнд вступает в операцию  в прямом модифицированном коде. Если знак операнда отрицателен,  то операнд вступает в операцию  в дополнительном модифицированном коде.

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

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

      - если знак суммы имеет значение "00", то это означает, что  сумма имеет положительное значение  и представлена в прямом коде.

      - если знак суммы имеет значение "11", то это означает, что  сумма имеет отрицательное значение  и представлена в обратном  коде. Для получения прямого кода  необходимо инвертировать цифровые  коды суммы и прибавить единицу.

      - если знак суммы "01" "10", это означает, что результат переполняет разрядную сетку машины и в этом случае вырабатывается сигнал переполнения. 

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

      В этом случае операционный автомат для  реализации операции сложения по вышеприведенному алгоритму может выглядеть следующим образом (рис.1): 

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

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

      В операционной части автомата выполняется  следующие микрооперации:

  занесение в  сумматор дополнительного  кода

 занесение в  сумматор прямого  кода

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

   обнуление сумматора

  _{инвертирование}

 (для операции  вычитания)

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

    Логическое  условие р₁ - определяет знак числа в сумматоре,логическое условие р₂ –определяет есть ли переполнение знакового разряда в сумматоре, логическое условие р₃ – определяет знак числа в регистре

    Далее по данному алгоритму построим содержательную граф-схему алгоритма(ГСА)  

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

       Содержательная  граф-схема алгоритма операции сложения (вычитания) приведена на рис.2. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рис.2. Содержательная граф-схема  алгоритма операции сложения (вычитания) 

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

    После построения содержательной граф-схемы  алгоритма строится функциональная ГСА. Для этого в содержательной ГСА операторные вершины обозначаются символами микрокоманд (Y_i), а условные вершины - символами логических условий (P_i), которые вписываются внутрь соответствующих вершин. 

    Операторные вершины:

y₅=Y₁;

y₂y₃=Y₂;

y₁,y₃=Y₃;

y₉=Y₄  

    Условные  вершины:

SignSM=P₁, 

SignRG=P₂

      Функциональная  граф-схема алгоритма операции сложения (вычитания) приведена на рис.3. 

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

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

- символом "а₁" отмечаются начальный и конечный вершины;

- все операторные  вершины должны быть отмечены;

- различные операторные  вершины отмечаются различными  символами.

      На  рис.4 приведена отмеченная ГСА, в  случае синтеза управляющего автомата Мура: 

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

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

      Граф  автомата Мура строится по отмеченной ГСА следующим образом. Проставляются  вершины графа, соответствующих  состояниям автомата. Каждому пути перехода ставится в соответствие переход автомата из состояния а_i в состояние под воздействием входного сигнала P(a_i, a_j), в пути перехода a_ia_j – переход из a_i в a_j под воздействием сигнала единицы. 

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

      Кодирование состояния автомата заключается  в установлении взаимно-однозначного соответствия между множеством состояний  автомата и множеством элемента памяти. . Используем для кодирования в качестве элемента памяти T – триггеры, которые будем обозначать Т₁,…,Т_r.

      Для автомата Мура имеем шесть состояний, следовательно достаточно иметь три триггера, т. е. применяем трехразрядное кодирование (таблица 1): 

      Таблица 1

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

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

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

      В таблице 2 приведена прямая структурная таблица автомата Мура. 

      Таблица 2.

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

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

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

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

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

      Как говорилось выше, управляющий автомат  будет содержать три элемента памяти Т-триггер, при включении вычислительного устройства триггеры автомата устанавливаются в произвольное состояние. Для перевода автомата в начальное состояние используется сигнал "ПУСК". 

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

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

ЗАКЛЮЧЕНИЕ 

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

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

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

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ:

1. С.К. Ганиев, А.А. Ганиев. Методическое указание для выполнения курсовой работы по дисциплине "Информационные основы вычислительных систем"./ ТУИТ. 26с. Ташкент, 2008.
2. С.К.Ғаниев, М.М.Каримов, Н.М.Мамбетов. "Ҳисоблаш системаларининг информацион асослари: Олий ўқув юрт.талаб. учун дарслик. – Тошкент Давлат техника университети, 2002;
3. А.Я. Савельев. Основы информатики. Учеб. для ВУЗов- М.: Изд-во МГТУ им А.Э. Баумана, 2001;
4. Темников Ф.Е. «Теоретические основы информационной техники».