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

Введение 

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

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

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

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

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

      

        

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

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

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

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

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

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

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

      Дополнительный  код (англ 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 под воздействием сигнала единицы.