Содержание

Задание                                                                                                    2

Введение                                                                                                  3

1              Разработка микропрограммы выполнения операции деления c  восстановлением  остатка со сдвигом делителя…………………….3

1.1       Метод выполнения операции деления с восстановления остатка со сдвигом делителя  в двоично-десятичном коде 8421+3…………….3

1.2       Контрольный пример………………………………………………….5

1.3       Определение структуры операционного автомата ………………..11

1.4       Разработка блок схемы алгоритма ………………………………….12

1.5       Описание моделирующей программы………………………………13

1.6       Оценка времени выполнения операции и оценка аппаратурных затрат ………………………………………………………………….14

1.7       Контроль выполнения операции по модулю………………………..16

2               Синтез управляющего микропрограммного автомата……………..17

2.1       Кодирование микропрограммы и получение отмеченной ГСА…...17

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

2.3       Синтез  структурного микропрограммного автомата……………...20

2.4       Формирование выходных функций и функций переключения  элементов памяти……………………………………………………..21

2.5       Описание функциональной схемы, схема запуска…………………22

2.6        Расчет такта работы управляющего автомата……………………...23

Заключение…………………………………………………………………24

Список литературы………………………………………………………...25

Приложение А

Приложение Б

ЗАДАНИЕ

          Код 18-Б-а-II-а-2-III-R

18 — Деление с восстановлением остатка со сдвигом делителя

Б   — В форме с фиксированной запятой, формат {1,16}

a   —  В прямом коде

II  — Двоично-десятичная система счисления (в коде 8421+3)

а   — Контроль по модулю

2       — Синхронный автомат Мура

III  — Элементы «ИЛИ», «НЕ»

R  —  RS-триггер

Задание выдал «___» ____________ 2001 г. преподаватель Дрогнова Н.Ф.

Задание принял «___» _____________ 2001 г. студент Пожитков Д. В.

Введение

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

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

1.1 Метод выполнения операции деления с восстановления остатка со сдвигом делителя  в двоично-десятичном коде 8421+3

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

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

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

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

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

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

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

У данного способа деления можно выявить следующие недостатки:

1.                      Ацикличность процесса деления, обусловленная нерегулярностью появления микрооперации восстановления остатков, что приводит к усложнению устройства управления делением;

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

Для  двоично-десятичного кода 8421+3 характерны следующие особенности: при сложении двух чисел в коде 8421 с избытком 3 необходимо произвести их по тетрадное суммирование по правилам двоичной арифметики с передачей единиц переноса между тетрадами, после чего к тем тетрадам, на выходе которых вырабатывалась единица переноса, добавляется код поправки, равный 3 (10)=0011(2),  а ко всем  остальным тетрадам добавляется код поправки, равный 13 (10)=1101(2). Возникшие вторичные межтетрадные переносы блокируются. С учетом особенности метода деления с восстановлением остатка  со сдвигом остатка, а так же  особенностей системы счисления 8421+3, можно сделать вывод, что коррекция будет производится на каждом шаге деления, а в тетраду частного предварительно будут занесены нули в коде 8421+3 (0011) и к ним будут прибавляться 1 в коде 8421 (0001), это позволит не производить коррекцию тетрад частного, что приведет к снижению временных и аппаратных затрат.

1.2 Контрольный пример

а) Возьмем для примера любых два десятичных числа:

А=1286  и В=6324

|0,6234 0000 |1 0 1 1  1    1 1  2    1 1        3 3

          Cm:   0,1286 0000

9,3676 0000

9,4962 0000 R0<0

0,6324 0000 восст.

0,1286 0000 сдв.1                        сдвиги:

9,9367 6000                                 0) 0,6324 0000пк=9,3676 0000дк

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

0,0653 6000 R1>0                 сдв.1) 0,0632 4000пк=9,9367 6000дк

9,9367 6000                          сдв.2) 0,0063 2400пк=9,9936 7600дк

0,0021 2000 R2>0                 сдв.3) 0,0006 3240пк=9,9993 6760дк

9,9367 6000                          сдв.4) 0,0000 6324пк=9,9999 3676дк

9,9388 8000 R3<0

0,0632 4000 восст.

0,0021 2000 сдв.2

9,9936 7600

9,9957 9600 R4<0

0,0063 2400 восст.

0,0021 2000 сдв.3

9,9993 6760

0,0014 8760 R5>0

9,9993 6760

0,0008 5520 R6>0

9,9993 6760

0,0002 2280 R7>0

9,9993 6760

9,9995 9040 R8<0

0,0006 3240 восст.

0,0002 2280 сдв.4

9,9999 3676

0,0001 5956 R9>0

9,9999 3676

0,0000 9632 R10>0

9,9999 3676

0,0000 3308 R11>0

9,9999 3676

9,9999 6984 R12<0

Мы взяли два числа (А-делимое, В-делитель),  и разделили их модули по следующему алгоритму:

1)  Делитель вычитается из делимого и определяется остаток R0. Если R0>0, то вырабатывается признак переполнения и деление прекращается. Если R0<0, то в частное записывается 0 и производиться восстановление с помощью прибавления делителя в пк;

2)  Делитель сдвигается вправо на 1 разряд;

3)  Производится вычитание делителя и определяется знак остатка Ri. Если Ri>0, то к разряду частного прибавляется 1, иначе завершается формирование разряда частного (переходим формировать следующий разряд) и выполняется восстановление отрицательного остатка путем прибавления делителя в пк;

4)  Пункты 2 и 3 выполняются n раз чтобы получить n разрядов частного

б) Рассмотрим теперь пример для этих же чисел в двоично-десятичной системе:

(Используем алгоритм деления с учетом следующих особенностей:

1)    Тетрада рассматривается как единое целое и сдвиг выполняется на тетраду;

2)    Для формирования тетрады частного из делимого вычитается делитель и если остаток положительный, то в формируемую тетраду частного прибавляется 1 в младший разряд;

3)    Вычитание делителя выполняется до тех пор, пока не появиться отрицательный остаток, в этом случае остаток восстанавливается и выполняется  сдвиг на тетраду;

4)    После каждого алгебраического сложения необходима коррекция (если был перенос 1 в сл. тетраду то коррекия 0011, если не было, то коррекция 1101)

A пк =0,0100 0101 1011 1001 0011 0011 0011 0011 ₈₄₂₁₊₃

B пк =0,1001 0110 0101 0111 0011 0011 0011 0011 ₈₄₂₁₊₃

В дк =1,0110 1001 1010 1000 1100 1100 1100 1101₈₄₂₁₊₃

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

СМ: 0,0100 0101 1011 1001 0011 0011 0011 0011

1,0110 1001 1010 1000 1100 1100 1100 1101

1,1010 1111 0110 0010 0000 0000 0000 0000 (кр.)

1101 1101 0011 0011 0011 0011 0011 0011

1,0111 1100 1001 0101 0011 0011 0011 0011 R0<0

0,1001 0110 0101 0111 0011 0011 0011 0011 восст.

0,0001 0010 1110 1100 0110 0110 0110 0110

   0011 0011 1101 1101 1101 1101 1101 1101 (кр.)

0,0100 0101 1011 1001 0011 0011 0011 0011 сдв.1

1,1100 0110 1001 1010 1000 1100 1100 1101

0,0000 1100 0101 0011 1100 0000 0000 0000

   0011 1101 0011 0011 1101 0011 0011 0011 (кр.)

0,0011 1001 1000 0110 1001 0011 0011 0011 R1>0

1,1100 0110 1001 1010 1000 1100 1100 1101

0,0000 0000 0010 0001 0010 0000 0000 0000

   0011 0011 0011 0011 0011 0011 0011 0011 (кр.)

0,0011 0011 0101 0100 0101 0011 0011 0011 R2>0

1,1100 0110 1001 1010 1000 1100 1100 1101

1,1111 1001 1110 1110 1110 0000 0000 0000

   1101 1101 1101 1101 1101 0011 0011 0011  (кр.)

1,1100 0110 1011 1011 1011 0011 0011 0011 R3<0

0,0011 1001 0110 0101 0111 0011 0011 0011 восст.

0,0000 0000 0010 0001 0010 0110 0110 0110

   0011 0011 0011 0011 0011 1101 1101 1101 (кр.)

0,0011 0011 0101 0100 0101 0011 0011 0011 сдв.2

1,1100 1100 0110 1001 1010 1000 1100 1101

1,1111 1111 1011 1101 1111 1100 0000 0000

   1101 1101 1101 1101 1101 1101 0011 0011 (кр.)

1,1100 1100 1000 1010 1100 1001 0011 0011 R4<0

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

0,0011 0011 1001 0110 0101 0111 0011 0011 восст.

0,0000 0000 0010 0001 0010 0000 0110 0110

   0011 0011 0011 0011 0011 0011 1101 1101 (кр.)

0,0011 0011 0101 0100 0101 0011 0011 0011 сдв.3

1,1100 1100 1100 0110 1001 1010 1000 1101

0,0000 0000 0001 1010 1110 1101 1100 0000

   0011 0011 0011 1101 1101 1101 1101 0011 (кр.)

0,0011 0011 0100 0111 1011 1010 1001 0011 R5>0

1,1100 1100 1100 0110 1001 1010 1000 1101

0,0000 0000 0000 1110 0101 0101 0010 0000

   0011 0011 0011 1101 0011 0011 0011 0011 (кр.)

0,0011 0011 0011 1011 1000 1000 0101 0011 R6>0

1,1100 1100 1100 0110 1001 1010 1000 1101

0,0000 0000 0000 0010 0010 0010 1110 0000

   0011 0011 0011 0011 0011 0011 1101 0011 (кр.)

0,0011 0011 0011 0101 0101 0101 1011 0011 R7>0

1,1100 1100 1100 0110 1001 1010 1000 1101

1,1111 1111 1111 1011 1111 0000 0100 0000

   1101 1101 1101 1101 1101 0011 0011 0011 (кр.)

1,1100 1100 1100 1000 1100 0011 0111 0011 R8<0, сдв.4

0,0011 0011 0011 1001 0110 0101 0111 0011 восст.

0,0000 0000 0000 0010 0010 1000 1110 0110

   0011 0011 0011 0011 0011 1101 1101 1101 (кр.)

0,0011 0011 0011 0100 1000 1100 1000 1001 R9>0

1,1100 1100 1100 1100 0110 1001 1010 1001

0,0000 0000 0000 0000 1111 0110 0011 0010

   0011 0011 0011 0011 1101 0011 0011 0011 (кр.)

0,0011 0011 0011 0011 1100 1001 0110 0101 R10>0

1,1100 1100 1100 1100 0110 1001 1010 1001

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

0,0000 0000 0000 0000 0011 0011 0000 1110

   0011 0011 0011 0011 0011 0011 0011 1101 (кр.)

0,0011 0011 0011 0011 0110 0110 0011 1011 R11>0

1,1100 1100 1100 1100 0110 1001 1010 1001

1,1111 1111 1111 1111 1100 1111 1110 0100

   1101 1101 1101 1101 1101 1101 1101 0011 (кр.)

1,1100 1100 1100 1100 1001 1100 1011 0111 R12<0

Преобразования делителя во время деления:

0)    0,1001 0110 0101 0111 0011 0011 0011 0011 пк

1, 0110 1001 1010 1000 1100 1100 1100 1101 дк

сдв.1)   0,0011 1001 0110 0101 0111 0011 0011 0011 пк

             1,1100 0110 1001 1010 1000 1100 1100 1101 дк 

сдв. 2)  0,0011 0011 1001 0110 0101 0111 0011 0011 пк

             1,1100 1100 0110 1001 1010 1000 1100 1101 дк

сдв. 3)  0,0011 0011 0011 1001 0110 0101 0111 0011 пк

             1,1100 1100 1100 0110 1001 1010 1000 1101 дк

сдв. 4)  0,0011 0011 0011 0011 1001 0110 0101 0111 пк

             1,1100 1100 1100 1100 0110 1001 1010 1001 дк

Формирование частного в процессе деления:

0, 0011 0011 0011 0011

    0001          0001 0001

    0001          0001 0001

    0101          0001 0001

                      0110 0110

С=0,0101 0011 0110 0110=0,2033

1.3 Определение структуры операционного автомата Рассмотрим структура операционного автомата:

Рг 1

40

0

СМ

40

0

СМК

СчT

Сч

Рг 2

40

0

А

С

R4

L8

УА

 В

Рисунок 1.1

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

Рг1 – в этот регистр мы заносим делитель.

Рг2 – в этот регистр мы получим частное.

СМ – в сумматор заносим делимое.

СМК – сумматор коррекции.

СЧТ – счетчик тетрад.

СЧ – счетчик для коррекции.

1.4 Разработка блок схемы алгоритма

Алгоритм для деления со сдвигом делителя в коде 8421+3:

1) Делитель вычитается из делимого и определяется остаток R0. Если R0>0, то вырабатывается признак переполнения и деление прекращается. Если R0<0, то в частное записывается 0 и производиться восстановление с помощью прибавления делителя в пк;

2)       Делитель сдвигается вправо на 1 тетраду;

3)       Для формирования тетрады частного из делимого вычитается делитель и если остаток положительный, то в формируемую тетраду частного прибавляется 1 в младший разряд;

4)       Вычитание делителя выполняется до тех пор, пока не появиться отрицательный остаток, в этом случае остаток восстанавливается и выполняется  сдвиг делителя на тетраду;

5)       После каждого алгебраического сложения необходима коррекция (если был перенос 1 в сл. тетраду то коррекия 0011, если не было, то коррекция 1101)

6)       Пункты 2,3 и 4 выполняются 4 раза чтобы получить 4 тетрады частного

Реализуем алгоритм в виде содержательного графа микропрограммы для двоично-десятичной системы исчисления. Согласно ГОСТа язык ГСА используется для формальной записи алгоритмов операция и имеет 1 начальную и 1 конечную вершину.

Структура ГСА находится в приложении В, лист 1.

Таблица 1.1

№ блока	Описание
A02	Заносим в СМ делимое обходя контрольные разряды, в Рг1 заносим делитель, обходя контрольные разряды, Сч, СчТ, Рг2 и контрольные разряды в СМ и Рг1 – обнуляем.
А05	Выясняем знак частного путем сложения знаковых разрядов делимого и делителя по модулю два.
№ блока	Описание
А07	Обнуляем знаковый разряд в СМ и Рг1.
А09	Производим пробное вычитание: к СМ прибавляем Рг1 в дк. Для последующей операции коррекции заводим временную переменную i и присваиваю ей значение 1.
С01-С07	Блоки коррекции: с помощью переменной i  проверяем чему равны кр. разряды в СМ, если  1, т.е. был перенос, то прибавляем 0011, иначе 1101
С09	Проверяем равен ли СчТ нулю, если да, то мы формируем только знаковый разряд частного, иначе тетраду № СчТ
Е01	Сравниваем знак сумматора с 0
Е03	Знак частного обнуляем
Е05	Наращиваем СчТ на 1, Сч присваиваем 0011, и восстанавливаем СМ делителем в пк
Е07-G03	Пошаговая коррекция сумматора (корректируем каждую тетраду в отдельности)
G05	Сдвигаю делитель на тетраду
G07	Сравниваем Счт с 5, если равен, то сформированы все тетрады частного и деление завершено, иначе продолжаем деление
G09	Заносим в С полученное частное из Рг2

1.5 Описание моделирующей программы.

Моделирующая программа разработана на языке Borland Turbo Assembler v.4.1(16bit). В моделирующей программе регистрами Рг1, Рг2, сумматором СМ, а так же счётчиком СЧ ОА являются регистры самой ЭВМ и оперативная память.

Общее описание программы:

Определение переменных в сегменте данных (A, B, C).

В процедуре Vvod_Dannih осуществляется ввод чисел A и B с клавиатуры и перевод их в код 8421+3.

Производим сдвиг делителя в процедуре Sdvig.

Коррекцию осуществляет процедура Korek.

В процедуре PK_TO_DK осуществляется перевод  чисел из ПК в ДК

В процедуре Vivod выполняется перевод произведения в десятичный код и выводится на экран.

Конец.

Более подробно (с комментариями) программа представлена в Приложении А.

1.6 Оценка времени выполнения операции и оценка аппаратурных затрат .

Время выполнения операции.

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

Время, затрачиваемое на выполнение операции в ОА равно:

где P_k – вероятность выполнения коррекции, T_k – время, затрачиваемое на коррекцию. Так как в системе 8421+3 коррекция нужна всегда, то вероятность равна единице. Коррекция выполняется сразу  отдельно по 1 тетраде (и так 4 раза) , поэтому:

          Время деления в двоичном коде равно:

С учетом этого получаем, время проведение операции деления будет равно

Аппаратные затраты:

Аппаратные затраты.

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

Q_Рг1= Q_Рг2=Q_СМ=41

Q_РгК=4

Q_ОА=Q_СМ+Q_Рг1+Q_Рг2+Q_РгК1+Q_РгК2=127 э.п.

Есть важная причина, в связи с которой используются 2-10 системы счисления. Это то, что в двоичной системе счисления необходим перевод десятичных чисел в двоичные коды и наоборот. Для перевода десятичного числа в двоичный код, необходимо делить число на основание системы, т.е. на 2, получившийся остаток делить еще раз, и так до тех пор пока остаток не будет меньше основания системы. В двоично-десятичной системе счисления каждое число кодируется своим определенным двоичным кодом занимающим одну тетраду. Но, т.к. в двоично-десятичной системе счисления существуют не используемые  комбинации, то часто приходится делать коррекцию числа. Сравнивая эти два метода, можно сделать вывод что, двоично-десятичная система счисления быстрее, т.к. на коррекцию уходит на много меньше времени, чем на перевод числа.

1.7 Контроль выполнения операции по модулю

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

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

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

2. Должен быть таким, чтобы остаток от деления на него числа определялся простым и быстрым методом без непосредственного деления.

3. Должен быть небольшим, чтобы остатки получались малоразрядными, в противном случае потребуются большие дополнительные затраты оборудования.

В теории кодирования указано, что модуль можно выбирать из условия Р<(2^SSYMBOL 177 f "Symbol" s 12±1), где SSYMBOL 179 f "Symbol" s 12і2. Учитывая правила записанные выше выбираем модуль, он будет равен Р=3, а степень будет равна S=2.

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

Найдем контрольные коды для чисел N_1(п.к.), N_2(п.к.) и N_3(п.к.):

где - это остаток от деления N_i – того числа на модуль P (контрольные коды).

Используя следующее соотношение теории кодирования

сравниваем наши коды:

Отсюда следует, что операция сложения прошла успешно, т.е. без ошибок.

2. Синтез управляющего микропрограммного автомата

2.1.Кодирование микропрограммы и получение отмеченной ГСА

(см. приложение В).

В этом разделе осуществляется переход непосредственно к синтезу микропрограммного автомата по граф – схеме алгоритма (ГСА).

Начать следует с синтеза абстрактного автомата, который осуществляется по кодированной ГСА. Кодированная ГСА получается путём отметки каждой операторной вершины в содержательной ГСА (для автомата Мура).

Чтобы получить отмеченную ГСА, необходимо воспользоваться следующими правилами:

1.     начальная и конечная вершины обозначаются символом А₀

2.     каждая операторная вершина отмечается символами А₁, А₂, и т.д.

3.     каждая операторная вершина отмечается не более одного раза.

В результате получаем алфавит состоянии А={А₀, А₁, …, А_m}.

Используя вышесказанные правила, получаем отмеченную ГСА (см. Приложение В, лист 2).

Рисунок 2. граф схема автомата

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

В отмеченной ГСА путём перехода между состояниями А_m, А_s, называется последовательность следующего вида:

А_mX^l1_m1 X^l2_m2… X^lk_mk Y_t А_s,

где А_m – обозначение вершины, из которой осуществляется переход (обязательный элемент);

А_s – в которую осуществляется переход (обязательный элемент);

X^l1_m1 X^l2_m2… X^lk_mk – обозначение условия вершины, через которые проходит путь от А_m и А_s (необязательные элементы), причём l_mr ={1,0} (в зависимости от логического условия X_mk).

Y_t – сформировавшися выходной сигнал.

Когда нет ни одной условной вершины, путь имеет вид: A_mY_tA_s.

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

Выписывая пути перехода для нашей ГСА, составляем таблицу переходов и выходов (см. табл. 2.1).

Таблица 2.1. Таблица переходов и выходов абстрактного

автомата (Мура).

Аm	Аs(Y)	X(Am, As)
A1	A2(y1-y7)	1
A2	A3(y8)	1
A3	A4(y9,y10)	1
A4	A5(y11,y12)	1
A5	A6(y13,y14)	x1
A5	A7(y13,y15)	X1
A6	A8(y16,y17)	1
A7	A8(y16,y17)	1
A8	A6(y13,y14)	x1x2
A8	A7(y13,y15)	X1x2
A8	A1(y0)	X2X3X4
A8	A9(y22,y23)	X2x3X4
A8	A10(y18)	X2X3x4
A8	A11(y12,y19-y21)	X2x3x4
A9	A5(y11,y12)	1
A10	A11(y12,y19-y21)	1
A11	A12(y13,y14)	x1
A11	A13(y13,y15)	X1
A12	A14(y16,y17)	1
Продолжение таблицы 2.1
Аm	Аs(Y)	X(Am, As)
A13	A14(y16,y17)	1
A14	A12(y13,y14)	x1x2
A14	A13(y13,y15)	X1x2
A14	A15(y24)	X2
A15	A5(y12,y12)	x5
А15	A16(yk)	X5
A16	A0(yk)	1

2.3 Синтез структурного микропрограммного автомата

Для синтеза заданного типа автомата (структурный автомат Мура) необходимо построить прямую таблицу переходов, в которую вписываются пути перехода между соседними отметками. В таблицу переходов структурного автомата, в отличии от абстрактного автомата, добавляются три столбца: код состояния А_m – K(A_m), код состояния A_s – K(A_s), а также функция возбуждения F(A_m, A_s).

Коды состояний K(A_m) и K(A_s) будем кодировать двоичными кодами. У нас 16 состояний, а это значит, что для кодирования достаточно использовать четырех разрядные коды. В таблице 2.2 представлена структурная таблица переходов МПА Мура.

Таблица 2.2. Таблица переходов автомата.

Аm	K(Am)	Аs(Y)	K(As)	X(Am, As)	F(Am,As)
A1	0001	A2(y1-y7)	1011	1	S1, S3
A2	1011	A3(y8)	1110	1	S2,R4
A3	1110	A4(y9,y10)	1111	1	S4
A4	1111	A5(y11,y12)	0110	1	R1,R4
A5	0110	A6(y13,y14)	0100	x1	R3
A5	0110	A7(y13,y15)	1100	X1	S1,R3
A6	0100	A8(y16,y17)	0000	1	R2
Продолжение таблицы 2.2
Аm	K(Am)	Аs(Y)	K(As)	X(Am, As)	F(Am,As)
A7	1100	A8(y16,y17)	0000	1	R1,R2
A8	0000	A6(y13,y14)	0100	x1x2	S2
A8	0000	A7(y13,y15)	1100	X1x2	S1,S2
A8	0000	A1(y0)	0001	X2X3X4	S4
A8	0000	A9(y22,y23)	0010	X2x3X4	S3
A8	0000	A10(y18)	1010	X2X3x4	S1,S3
A8	0000	A11(y12,y19-y21)	1000	X2x3x4	S1
A9	0010	A5(y11,y12)	0110	1	S2
A10	1010	A11(y12,y19-y21)	1000	1	S3
A11	1000	A12(y13,y14)	1101	x1	S2,S4
A11	1000	A13(y13,y15)	1001	X1	S4
A12	1101	A14(y16,y17)	0101	1	R1
A13	1001	A14(y16,y17)	0101	1	S2,R1
A14	0101	A12(y13,y14)	1101	x1x2	S1
A14	0101	A13(y13,y15)	1001	X1x2	S1,R2
A14	0101	A15(y24)	0111	X2	S3
A15	0111	A5(y12,y12)	0110	x5	R4
А15	0111	A16(yk)	0011	X5	R2
A16	0011	A0(yk)	0001	1	R3

2.4 Формирование выходных функций и функций переключения элементов памяти

По таблице 2.2. составим функции возбуждения автомата:

R1=A4 v A7 v A12 v A13

S1=A1 v A5X1 v A8X1X2 v A8X2X3X4 v A8X2X3X4 v A14X1X2 v  A14X1X2

R2=A6 v A7 v A14X1X2 v A15X5

S2=A2 v A8X1X2 v A8X1X2 v A9 v A11X1 v A13

R3= A5X1 v A5X1 v A16=A5 v A16

S3= A1 v A8X2X3X4 v A8X2X3X4 v A10 v A14X2

R4=A2 v A4 v A15X5

S4=A3 v A8X2X3X4 v A11X1 v A11X1=A3 v A11 v A8X2X3X4

В заданном базисе (см. задание) отсутствует логический элемент «И», поэтому мы переводим функции в заданный базис (ИЛИ, НЕ) с помощью формулы де Моргана:

R1=A4 v A7 v A12 v A13

S1=A1 v A5vX1 v A8vX1vX2 v A8vX2vX4 v A14vX2  

R2=A6 v A7 v A14vX1vX2 v A15vX5

S2=  A2 v A8vX2 v A9 v A11vX1 v A13

R3=A5 v A16

S3= A1 v A8vX2vX3vX4 v A8vX2vX3vX4 v A10 v A14vX2

R4=A2 v A4 v A15vX5

S4=A3 v A11 v A8vX2vX3vX4

Y1=y1-y7=A2; Y2=y8=A3; Y3= y9,y10=A4; Y4= y11,y12=A5;

Y5= y13,y14=A6vA12; Y6=y13,y15=A7vA13; Y7=y16,17=A8vA14;

Y8=y22,y23=A9; Y9=y18=A10; Y10=y12,y19-y21=A11; Y11=y24=A15;

Y12=y25=A16;

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

A1=Q1Q2Q3Q4; A2=Q1Q2Q3Q4; A3=Q1Q2Q3Q4; A4=Q1Q2Q3Q4;

A5=Q1Q2Q3Q4; A6=Q1Q2Q3Q4; A7=Q1Q2Q3Q4; A8=Q1Q2Q3Q4;

A9=Q1Q2Q3Q4; A10=Q1Q2Q3Q4; A11=Q1Q2Q3Q4; A12=Q1Q2Q3Q4;

A13=Q1Q2Q3Q4; A14=Q1Q2Q3Q4; A15=Q1Q2Q3Q4; A16=Q1Q2Q3Q4;

2.5 Описание функциональной схемы, схема запуска.

Функциональная схема состоит из дешифратора, комбинационной схемы и элементов памяти. Дешифратор, дешифрируя состояния триггеров, вырабатывает сигнал состояния a_i, который соответствует выходному сигналу Y_j. Комбинационная схема, используя выходные сигналы дешифратора a_j и входные сигналы (X), формирует сигналы функций возбуждения триггера. Память (RS-триггеры) в свою очередь переключаются в новое состояние, и через шину Q состояния триггеров подаются на дешифратор. Функциональная схема включает схему запуска/остановки. При запуске производится установка памяти в начальное состояние. Остановка УА происходит автоматически, когда образуется выходной сигнал Y_k, означающий конец операции деления.

Схема запуска реализована на логических элементах «ИЛИ» и «НЕ» (D_._,D_._,D_._; а также D__._–D__._), и на RS-триггере (a₁ до a₁₆. Выходы из дешифратора используются для формирования выходной шины Y (Y₁-Y₁₂), и для комбинационной схемы. Входная шина X (X₁-X₅) имеет 5 проводов, т.к. нами используется X₁-X₅. Для получения инверсии входных сигналов используется 5 инверторов (X₁-X₅).

Комбинационная схема для функции возбуждения, использует логические элементы (D_._–D_._), соответствующие заданному базису. На комбинационную схему подаются текущее состояние (a_k) из дешифратора, и входные сигналы по шине X (X₁-X₅). Выходы комбинационной схемы подаются на RS-входы триггеров.

В качестве элементов памяти используется RS-триггера (Т₁-Т₄). В функциональной схеме (Приложение В) используется всего __ логических элементов «НЕ», __ логических элементов «ИЛИ», 5 – RS триггеров.

2.6 Расчет такта работы УА

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

Условно средняя задержка на элементах памяти считаем равной:

на логических элементах:

При определении Т_{возб.мах} используем функцию возбуждения равную последовательно переключающимся логическим элементам

Следовательно, тактовая частота генератора синхронных импульсов (ГСИ) равняется:

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

Заключение

В процессе разработки курсового проекта я более глубоко изучил курс «Прикладная теория цифровых автоматов».

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

Список использованной литературы

1. Проектирование управляющего автомата. Метод рекомендации Айтхажаева Е.Ж..

2. Прикладная теория цифровых автоматов. Савельев А.Я.

3. Савельев А.Я. Арифметические и логические основы цифровых автоматов.

4. Прикладная теория цифровых автоматов. Айтхажаева Е.Ж.

Содержание Задание                                                                                                    2 Введение                                                                                                  3 1 Разрабо

 

• 14:21 05 Июля 2016
  Российско-китайский медуниверситет откроет магистерскую программу по TCM
• 01:21 05 Июля 2016
  На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
• 11:00 04 Июля 2016
  Реморенко: "ЕГЭ-туризм" в России сходит на нет
• 10:52 04 Июля 2016
  Летняя российско-австрийская школа откроется в Москве
• 15:31 01 Июля 2016
  В СПбГУ могут воссоздать географический факультет

Заказать уникальную работу