Размещено на http://www.allbest.ru/

Содержание

• Техническое задание
• Введение
• 1. Разработка структуры устройства и алгоритма его работы
• 1.1 Выбор формата данных
• 1.2 Тестовые примеры
• 1.3 Алгоритм работы автомата
• 2. Синтез функциональной схемы операционного автомата
• 2.1 Синтез функциональной схемы
• 2.2 Описание функциональной схемы
• 2.3 Граф схема алгоритма управления на F-языке
• 2.4 Входной выходной алфавит автомата
• 2.5 Граф схема алгоритма управления в мнемонической форме
• 3. Разработка логических схем управляющего автомата
• 3.1 Разработка мнемонической формы структурной таблицы
• 3.2 Кодированная форма структурной таблицы
• 3.3 Выбор элементов памяти
• 3.4 Построение структурного автомата
• 3.5 Построение и минимизация функций алгебры логики. Метод Квайна-Мак-Класки
• 3.6 Описание принципиальной схемы
• Выводы
• Перечень литературы
• цифровой автомат деление двоичный число


Техническое задание

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

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

Вариант реализации управляющего автомата - упрощенный, полностью факторизованный автомат Мура.

Основные технические параметры проектирования представлены ниже.

1. Характеристики операционного устройства:

- арифметическая операция - деление;

- алгоритм - деление с восстановлением остатка;

- тип сумматора - двоичный сумматор дополнительного кода (ДСДК);

- разрядность слова данных - 32 бит;

- разрядность слова результата - 32 бит;

- формат представления данных - плаващая точка, ANSI/IEEE 754-1985;

- разрядность битового поля экспоненты - 6 бит;

- способ кодирования знака - модифицированный код;

- устройство управления - сосредоточено в управляющем автомате (УА);

- тип устройства управления - конечный автомат.

2. Характеристики операционного автомата:

- тип операционного автомата - последовательный;

- способ хранения результата - в регистре делимого;

- способ адресации регистров - индексная адресация.

2.1 функциональная схема ОА (входит в проектную документацию):

- структурная оптимизация - не выполнять;

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

2.2 логическая схема ОА (не входит в проектную документацию):

- тип елементов памяти - не выполнять;

- логическая минимизация - не выполнять;

- алгоритм логической минимизации - не выполнять;

- логическая факторизация - не выполнять;

- физическая факторизация - не выполнять;

- расчет эквивалентной логической емкости - не выполнять.

3. Характеристики управляющего автомата:

- тип управляющего автомата - автомат Мура.

3.1 функциональная схема УА (входит в проектную документацию):

- структурная оптимизация - не выполнять (тривиальный автомат);

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

3.2 логическая схема УА (входит в проектную документацию):

- тип елементов памяти - D-триггер;

- логическая минимизация - несовместимая (упрощенный автомат);

- алгоритм логической минимизации - Квайна-Мак-Класки;

- логическая факторизация - не выполнять;

- физическая факторизация - не выполнять;

- расчет эквивалентной логической емкости - выполнять.

Введение

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

Алгоритм деления двоичных чисел бывает 2-х видов:

- с восстановлением остатка;

- без восстановления остатка.

Выбирается метод с восстановлением остатка

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

- с плавающей запятой;

- с фиксированной запятой.

Выбирается формат с плавающей запятой. Числа будут представлены в формате IEEE 754.

Виды цифровых автоматов:

- автомат Мура;

- автомат Мили.

Выбирается автомат Мура.

Варианты представления числе при работе над ними:

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

- Прямой код;

- Обратный код.

Выбирается дополнительный код.

1. Разработка структуры устройства и алгоритма его работы

1.1 Выбор формата данных

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

Система счисления - это совокупность приемов и правил для записи чисел цифровыми знаками. Запись числа в некоторой системе счисления часто называют кодом числа.

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

До 80-х годов каждый производитель поддерживал собственный формат чисел с плавающей точкой. Все они отличались друг от друга. Более того, в некоторых из них арифметические действия выполнялись неправильно, поскольку арифметика с плавающей точкой имеет некоторые тонкости, которые не очевидны для среднестатистического разработчика аппаратного обеспечения. Чтобы изменить эту ситуацию, в конце 70-х годов институт IEEE учредил комиссию по стандартизации арифметики с плавающей точкой. Целью было не только дать возможность переносить данные с одного компьютера на другой, но и обеспечить разработчиков аппаратного обеспечения заведомо правильной моделью. В результате в 1985 г. вышел стандарт IEEE 754. В настоящее время большинство процессоров (в том числе Intel, SPARC и JVM) содержат команды с плавающей точкой, которые соответствуют этому стандарту. В отличие от многих стандартов, ставших плодом неудачных компромиссом и мало кого устраивавших, этот стандарт неплох, причем в значительной степени благодаря тому, что его изначально разрабатывал один человек, профессор математики университета Беркли Вильям Каган (William Kahan). Рассмотрим этот стандарт. Стандарт IEEE 754 определяет три формата: с одинарной точностью (С2 бита), с удвоенной точностью (F4 бита) и с повышенной точностью (80 бит). Формат с повышенной точностью предназначен для уменьшения ошибки округления. Он применяется главным образом в арифметических устройствах с плавающей точкой, поэтому мы не будем о нем говорить. В форматах с одинарной и удвоенной точностью используются основание степени 2 для мантисс смещенная экспонента.

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

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

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

Старший разряд двоичного представления вещественного числа всегда кодирует знак числа. Остальная часть разбивается на две части: экспоненту и мантиссу. Вещественное число вычисляется как: (-1)S·2E·M, где S - знаковый бит числа, E - экспонента, M - мантисса. Если 1M<2, то такое число называется нормализованным. При хранении нормализованных чисел сопроцессор отбрасывает целую часть мантиссы (она всегда 1), сохраняя лишь дробную часть. Экспонента кодируется со сдвигом на половину разрядной сетки, таким образом, удается избежать вопроса о кодировании знака экспоненты.

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

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

На сегодняшний день IEEE 754 -- широко распространен стандарт формата представления числа с плавающей запятой, используемый как в программных реализациях арифметических действий, так и во многих аппаратных (CPU и FPU) реализациях. Много компиляторов используют этот стандарт для хранения и выполнения математических операций.

Стандарт определяет следующие положения:

- определение форматов хранения мантиссы, экспоненты и знака, форматы позитивного и негативного нуля, плюс и минус бесконечности, а также определение "не числа";

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

- обработка исключительных ситуаций, таких как деление на нуль, переполнение и так далее.

Поскольку данная система является наиболее распространенной, имеет выгодные для нас стандарты, то для проектирования ЦА возьмем именно ее. Согласно с техническим заданием на вход поступает числа с разрядностью 32 бит, представление этих числе в формате IEEE 754 будет выглядеть следующим образом:

- разрядность поля мантисс - 25 бит(7:31);

- разрядность поля порядка (Экспонента) - 6 бит(1:6);

- признак знака несет в себе 0-й бит числа - это поле будет необходимо в дальнейшем для определения знака результата.

Графически всё вышесказанное представлено на рисунке 1.1

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
Знак	Экспонента	Мантисса

Рисунок 1.1 - Представление числа в формате IEEE 754

1.2 Тестовые примеры

Пример 1:

A = 39; B = -3

A754 = 1.1100.00111000, Am = 0.100111000

B754 = 1.1000.10000000, Bm = 0.110000000, Bm, доп = 0.010000000

Знак: SC = SA SB = 1 1 = 0

Экпонента:

EC = 1100 - 1000 = 0100

00.1100

+11.1000

00.0100

Мантисса:

00.100111000

+11.010000000

11.110111000> 0, восстановление остатка

+00.110000000

100.100111000

>01.001110000

+11.010000000

100.011110000> 1

>00.111100000

+11.010000000

100.001100000> 1

>00.011000000

+11.010000000

11.101000000> 0, восстановление остатка

+00.110000000

100.011000000

>00.110000000

+11.010000000

100.000000000> 1

MC = 0.1101

Ответ: С754 = 0.1010.10100000

Пример 2:

A = -21; B = 3

A754 = 1.1101.01010000, Am = 0.101010000

B754 = 0.1010.10000000, Bm = 0.110000000, Bm, доп = 0.010000000

Знак: SC = SA SB = 1 0 = 1

Экпонента:

EC = 1101 - 1010 = 0011

00.1101

+11.0110

100.0011

Мантисса:

00.101010000

+11.010000000

11.111010000 > 0, восстановление остатка

+00.110000000

100.101010000

>01.010100000

+ 11.010000000

100.100100000> 1

>01.001000000

+11.010000000

100.011000000> 1

>00.110000000

+11.010000000

100.000000000> 1

MC = 0.111000000

Ответ: С754 = 1.0011.10000000

Таблица истинности функции mod2 () представлена в таблице 1.1

Таблица 1.1 - Таблица истинности функции mod2

A	0	0	1	1
B	0	1	0	1
C	0	1	1	0

1.3 Алгоритм работы автомата

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

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

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

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

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

1) определение знака результата деления. Определяется взятием суммы по mod2 знаков делимого и делителя Зн(C) = Зн(A) Зн(B);

2) представить делимое в прямом коде со знаком «+», делитель в прямом и дополнительном коде со знаком «-»;

3) сложить необходимые разряды делимого и делителя (в дополнительном коде);

4) проверить знак промежутного результата: если знак положительный, то записать в результат 1, иначе записать 0 и произвести возобновление остатка - сложить промежуточный результат с делителем в прямом коде со знаком +;

5) если промежутный результат равен 0, то алгоритм заканчивается, иначе продолжается с пункта №6;

6) сдвинуть делитель влево и снести следующий разряд делимого, перейти в пункт 3.

Проанализировав вышесказанное, мы можем установить алгоритм работы разрабатываемого цифрового автомата и изобразить его в виде блок-схемы (рисунок 1.2):

Рисунок 1.2 - Алгоритм работы цифрового автомата. Часть 1



Рисунок 1.2 - Алгоритм работы цифрового автомата. Часть 2 (продолжение)



Рисунок 1.2 - Алгоритм работы цифрового автомата. Часть 3 (продолжение)

Описание алгоритма:

1. Начало алгоритма.

2. Инициализация триггеров и счетчиков:

TrZ := 0, TrOf := 0, TrE := 0;

Cnt := 0.

Получение входных данных:

SA(0:1) := [A(0), A(0)]; SB(0:1) := [B(0), B(0)];

EA(0:5) := A(1:6); EB(0:5) := B(1:6);

MA(0:24) := A(7:31); MB(0:24) := B(7:31).



3. Если мантисса MA = 0, то переход в пункт 4, иначе переход в пункт 5.

4. Результат равен 0: MC := 0; EC := 0; SC := 0.

Переход в пункт 27.

5. Если мантисса MB == 0, то переход в пункт 6, иначе переход в пункт 7.

6. Ошибка деления на ноль: TrZ := 1.

Переход в пункт 28.

7. Нормализация операндов(сдвиг враво, освободишийся разряд заполняется единицей):

A := R(MA, 1, 1);

MB := R(MB, 1, 1);.

8. Определение знака результата:

SC := SA SB.

9. Перевод экспоненты второго операнда в дополнительный код:

EB := EBдоп.

10. Определение экспоненты результата:

EC := EA + EB.

11. Если произошло переполнения разрядной сетки экпоненты, то переход в пункт 12, иначе переход в пункт 13.

12. Ошибка переполнения разрядной сетки экпоненты: TrE := 1.

Переход в пункт 24.

13. Сброс знаков операндов:

SA := 00;

SB := 00.

14. Преобразование второго операнда:

SB := НЕ(SB);

MB := MBдоп.

15. Сложение операндов:

[SA,MA] := [SA,MA] + [SB,MB].

16. Если произошло переполнение разрядной сетки мантиссы, то переход в пункт 17, иначе переход в пункт 18.

17. Установить триггер переполнения в 1: TrOf := 1

Вернуть знак:

SA(0:1) := [SA(0), SA(0)].

Заполнить все разряды делимого вторым знаковым разрядом:

MA(0:25) := [SA(1)х25].

18. Преобразование второго операнда:

SB := НЕ(SB);

MB := MBдоп.



19. Запись нового разряда результата:

MС(CntI) := НЕ(SA(0)).

20. Если знак SA(0) == 1, то переход в пункт 21, иначе переход в пункт 22.

21. Сложение операндов:

[SA,MA] := [SA,MA] + [SB,MB].

22. Формирование левого сдвига делимого:

MA := L(MA, 1, 0);

Cnt ++

23. Если Cnt < 28, то переход в пункт 14, иначе переход в пункт 24.

24. Если MC(0) == 0, то переход в пункт 25, иначе переход в пункт 28.

25. Формирование левого сдвига результата:

MC := L(MC, 1, 0).

26. Уменьшение экпоненты на 1:

EC := EC - 1.

27. Если произошло переполнение разрядной сетки экпоненты, то переход в пункт 12, иначе переход в пункт 24.

28. Формирование окончательного результата:

A(7:31) := МС(1:25);

A(1:6) := EС(0:5);

A(0) := SС(0).

29. Конец алгоритма.

Пояснения к алгоритму:

- A, B - регистры, хранящие операнды деления в формате IEEE754;

- TrZ - триггер ошибки деления на 0;

- TrE - триггер переполнения разрядной сетки экпоненты;

- TrOf - триггер переполнения разрядной сетки мантиссы;

- Cnt - счетчик цикла, в котором производится сложение операндов;

- MA(0:25), MB(0:25), MC(0:25) - регистры, хранящие мантиссы(разряды (7:31)) соответствующих операндов;

- SA(0:1), SB(0:1), SC(0:1) - регистры, хранящие знаки(разряд 0)) соответствующих операндов;

- EA(0:5), EB(0:5), EC(0:5) - регистры, хранящие экпоненты(разряды (1:6)) соответствующих операндов.

2. Синтез функциональной схемы операционного автомата

2.1 Синтез функциональной схемы

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

Синхронный автомат характеризуется тем, что функционирует под управлением тактовых (или синхронизирующих) сигналов - ТС, с постоянной длительностью t и постоянной частотой f, если квантование времени равномерное. Такт (квант) времени ti совмещается с фронтом i-того сигнала ТС. Входные сигналы могут воздействовать на автомат лишь при наличии сигнала ТС и не изменяются в течение t. Период следования сигналов ТС должен быть больше или равен времени, которое необходимо реальному автомату для перехода из одного состояния в другое. Когда рассматривается абстрактный автомат, то считается, что изменение внутренних состояний автомата происходит в интервалы времени между смежными ТС, а выходные сигналы формируются по фронту очередного ТС.

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

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

У автоматов Мура выходные сигналы в момент времени t однозначно определяются состоянием автомата в этот же момент времени и в явном виде не зависят от значения входных сигналов xi(t).

Функции переходов и выходов автомата Мура, заданного на множестве входных сигналов X, множестве внутренних состояний A = {a0, a1, …, an} и множестве выходных сигналов Y, можно записать в виде:

a(t + 1) = f[a(t), x(t)],

y(t) = [a(t)].

Общая функциональная схема цифрового автомата представлена на рисунке 2.1.

Рисунок 2.1 - Общая функциональная схема ЦА

2.2 Описание функциональной схемы

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



Рисунок 2.2 - Установка триггера ошибки деления на ноль в 1

Рисунок 2.3 - Проверка мантиссы MA на равенство нулю

Рисунок 2.4 - Определение знака частного

Рисунок 2.5 - Получение следующего разряда частного

Рисунок 2.6 - Перевод второго операнада в дополнительный код



В общем виде функциональная схема операционного автомата представлена на рисунке 2.7

Рисунок 2.7 - Функциональная схема операционного автомата

2.3 Граф схема алгоритма управления на F-языке

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

- 0010 - константа;

- A(1:6) - четырехразрядная двоичная переменная;

- Чт[A] - функция чтения регистра А.

Например, A(1:4):=1010 означает, что в первом разряде слова A будет 1, во втором - 0 и так далее. A(2:3) - часть слова A, размещенная во втором и третьем разрядах.

Наиболее частые операции Ф-языка:

- присваивание;

- инвертирование.

Функции, использованные в нашем алгоритме:

- чтение регистра Х: Чт[X];

- запись регистра Х: Зп[X];

- сброс регистра Х: Сброс[X];

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

C(0:n):=A(0:n)+B(0:n)

Развернутая граф схема управления операционым автоматом представлена на рисунке 2.8



Рисунок 2.8 - Граф схема управления операционным автоматом на F-языке. Часть 1



Рисунок 2.8 - Граф схема управления операционным автоматом на F-языке. Часть 2 (продолжение)



Рисунок 2.8 - Граф схема управления операционным автоматом на F-языке. Часть 3 (продолжение)



Рисунок 2.8 - Граф схема управления операционным автоматом на F-языке. Часть 4 (продолжение)



Рисунок 2.8 - Граф схема управления операционным автоматом на F-языке. Часть 5 (продолжение)



Рисунок 2.8 - Граф схема управления операционным автоматом на F-языке. Часть 6 (продолжение)

2.4 Входной выходной алфавит автомата

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

Микрооперации описаны в таблице 2.1



Таблица 2.1 - Микрооперации операционного автомата

Y	Описание микрооперации
y1	Чтение регистров A,B
y2	Запись регистра A
y3	Чтение регистра SA
y4	Чтение регистра SB
y5	Чтение регистра SC
y6	Чтение регистра EA
y7	Чтение регистра EB
y8	Чтение регистра EC
y9	Чтение регистра MA
y10	Чтение регистра MB
y11	Чтение регистра MC
y12	Запись регистра SA
y13	Запись регистра SB
y14	Запись регистра SC
y15	Запись регистра EA
y16	Запись регистра EB
y17	Запись регистра EC
y18	Запись регистра MA
y19	Запись регистра MB
y20	Запись регистра MC
y21	Сброс регистров SA, SB
y22	Сброс регистров SC, EC, MC
y23	Левый свдиг регистра MA
y24	Левый свдиг регистра MC
y25	Правый сдвиг регистра MA, MB
y26	Чтение блока Const1
y27	Чтение блока Const2
y28	Чтение блока Const3
y29	Продолжение счета Cnt1
y30	Продолжение счета Cnt2
y31	Сброс счетчика Cnt1, сброс триггера TrC
y32	Сброс счетчика Cnt2
y33	Включение блока НЕ[1]
y34	Включение блока НЕ[2]
y35	Включение блока НЕ[3] и инвертирование входящих данных
y36	Инвертирование входящих данных в блоке НЕ[1]
y37	Инвертирование входящих данных в блоке НЕ[2]
y38	Установка триггера TrZ в 1
y39	Установка триггера TrOf в 1
y40	Установка триггера TrE в 1

Входные условия описаны в таблице 2.2

Таблица 2.2 - Входные условия операционного автомата

X	Описание условия
	MA != 0
	MB != 0
x3	Cnt1 == 110
x4	Cnt1 == 11001
x5	Cnt1 == 11011
x6	Cnt2 == 11001
	SA(0) == 0
	MC(0) == 0
x9	TrC == 1

Начальное и конечное состояния автомата - а1. Из граф схемы, изображенной на рисунке 2.8, можно определить количество состояний ЦА: А = {a1, …, a37}.

Алфавит входных слов Z = {z1, …, z18}, приведен в таблице 2.3.

Таблица 2.3 - Алфавит входных слов операционного автомата

Z	Описание
z1
z2
z3
z4
z5
z6
z7
z8
z9
z10
z11
z12
z13
z14
z15
z16
z17
z18

Алфавит микрокоманд W = {w1,…,w30} представлен в таблице 2.4

Таблица 2.4 - Алфавит микрокоманд операционного автомата

W	Y
w1	y31, y32, y1, y12, y13, y15, y16, y18, y19
w2	y9
w3	y22
w4	y10
w5	y38
w6	y25
w7	y3, y4, y14
w8	y21
w9	y7, y34, y37, y27, y29
w10	y16
w11	y40
w12	y31
w13	y6, y7, y34, y17, y29
w14	y4, y31, y35
w15	y13
w16	y10, y33, y36, y26, y29
w17	y19
w18	y31, y30
w19	y3, y4, y9, y10, y33, y29
w20	y12, y18
w21	y3, y39
w22	y12, y18
w23	y3
w24	y3, y20, y23
w25	y11
w26	y24, y31
w27	y8, 28, y29
w28	y17
w29	y5, y8, y11, y2
w30	y20

2.5 Граф схема алгоритма управления в мнемонической форме

Граф схема управления операционым автоматом в закодированной форме представлена на рисунке 2.9

Рисунок 2.9 - Граф схема управления операционным автоматом в закодированной форме. Часть 1

Рисунок 2.9 - Граф схема управления операционным автоматом в закодированной форме. Часть 2 (продолжение)



Рисунок 2.9 - Граф схема управления операционным автоматом в закодированной форме. Часть 3 (продолжение)



Рисунок 2.9 - Граф схема управления операционным автоматом в закодированной форме. Часть 4 (продолжение)



Рисунок 2.9 - Граф схема управления операционным автоматом в закодированной форме. Часть 5 (продолжение)



Рисунок 2.9 - Граф схема управления операционным автоматом в закодированной форме. Часть 6 (продолжение)



3. Разработка логических схем управляющего автомата

3.1 Разработка мнемонической формы структурной таблицы

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

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

Таблица 3.1 - Мнемоническая форма структурной таблицы

№	ai	ai+1	X(ai ,ai+1)	Y(ai)	тип перехода
1	a1	a2	1	-	безусловный
2	a2	a3	1	y31, y32, y1, y12, y13, y15, y16, y18, y19	безусловный
3	a3	a4	!x1	y9	условный
4	a4	a34	1	y22	безусловный
5	a34	a1	1	y5, y8, y11, y2	безусловный
6	a3	a5	x1	y9	условный
7	a5	a6	!x2	y10	условный
8	a6	a1	1	y38	безусловный
9	a5	a7	x2	y10	условный
10	a7	a8	1	y25	безусловный
11	a8	a9	1	y3, y4, y14	безусловный
12	a9	a10	1	y21	безусловный
13	a10	a11	1	y7, y34, y37, y27, y29	безусловный
14	a11	a10	!x3	y16	условный
15	a11	a12	x3 x9	y16	условный
16	a12	a1	1	y40	безусловный
17	a11	a13	x3 !x9	y16	условный
18	a13	a14	1	y31	безусловный
19	a14	a14	!x3	y6, y7, y34, y17, y29	условный
20	a14	a15	x3	y6, y7, y34, y17, y29	условный
21	a15	a16	1	y4, y31, y35	безусловный
22	a16	a17	1	y13	безусловный
23	a17	a18	1	y10, y33, y36, y26, y29	безусловный
24	a18	a17	!x4	y19	условный
25	a18	a19	x4	y19	условный
26	a19	a20	1	y31, y30	безусловный
27	a20	a21	1	y3, y4, y9, y10, y33, y29	безусловный
28	a21	a20	!x5	y12, y18	условный
29	a21	a22	x5 x9	y12, y18	условный
30	a22	a23	1	y3, y39	безусловный
№	ai	ai+1	X(ai ,ai+1)	Y(ai)	тип перехода
31	a23	a24	1	y12, y18	безусловный
32	a24	a25	1	y3	безусловный
33	a21	a25	x5 !x9	y12, y18	условный
34	a25	a26	1	y4, y31, y35	безусловный
35	a26	a27	1	y13	безусловный
36	a27	a28	1	y10, y33, y36, y26, y29	безусловный
37	a28	a27	!x4	y19	условный
38	a28	a29	x4	y19	условный
39	a29	a30	!x7	y3, y20, y23	условный
40	a29	a33	x7	y3, y20, y23	условный
41	a30	a31	1	y31	безусловный
42	a31	a32	1	y3, y9, y4, y33, y10, y29	безусловный
43	a32	a31	!x4	y12, y18	условный
44	a32	a15	x4 !x5	y12, y18	условный
45	a32	a33	x4 x5	y12, y18	условный
46	a33	a34	x8	y20	условный
47	a34	a35	1	y24, y31	безусловный
48	a35	a36	1	y8, y28, y29	безусловный
49	a36	a35	!x3	y17	условный
50	a36	a12	x3 x9	y17	условный
51	a36	a34	x3 !x9 x8	y17	условный
52	a36	a37	x3 !x9 !x8	y17	условный
53	a37	a1	1	y5, y8, y11, y2	безусловный

3.2 Кодированная форма структурной таблицы

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

- Количество состояний M=37

- Количество микроопераций - 40

- Разрядность слова микрокоманд N=30

Разрядность кода состояния:

Коды состояний цифрового автомата приведены в таблице 3.2

Таблица 3.2 - Таблица кодов состояний цифрового автомата

№	ai		Y(ai)
1	a1	000000	-
2	a2	000001	y31, y32, y1, y12, y13, y15, y16, y18, y19
3	a3	000010	y9
4	a4	000011	y22
5	a5	000100	y10
6	a6	000101	y38
7	a7	000110	y25
8	a8	000111	y3, y4, y14
9	a9	001000	y21
10	a10	001001	y7, y34, y37, y27, y29
11	a11	001010	y16
12	a12	001011	y40
13	a13	001100	y31
14	a14	001101	y6, y7, y34, y17, y29
15	a15	001110	y4, y31, y35
16	a16	001111	y13
17	a17	010000	y10, y33, y36, y26, y29
18	a18	010001	y19
19	a19	010010	y31, y30
20	a20	010011	y3, y4, y9, y10, y33, y29
21	a21	010100	y12, y18
22	a22	010101	y3, y39
23	a23	010110	y12, y18
24	a24	010111	y3
25	a25	011000	y4, y31, y35
26	a26	011001	y13
27	a27	011010	y10, y33, y36, y26, y29
28	a28	011011	y19
29	a29	011100	y3, y20, y23
30	a30	011101	y31
31	a31	011110	y3, y9, y4, y33, y10, y29
32	a32	011111	y12, y18
Продолжение таблицы 3.2 - Таблица кодов состояний цифрового автомата
№	ai		Y(ai)
33	a33	100000	y20
34	a34	100001	y24, y31
35	a35	100010	y8, y28, y29
36	a36	100011	y17
37	a37	100100	y5, y8, y11, y2

Кодированая форма структурной таблицы - функции входа описаны в таблице 3.3, функции выхода - в таблице 3.4.

Таблица 3.3 - Функции входа цифрового автомата

№	T1T2T3T4T5 T6	D1D2D3D4D5 D6	x1x2x3 x4x5x6 x7x8x9
1	000000	000001	---------
2	000001	000010	---------
3	000010	000011	0--------
4	000011	100001	---------
5	100001	000000	---------
6	000010	000100	1--------
7	000100	000101	-0-------
8	000101	000000	---------
9	000100	000110	-1-------
10	000110	000111	---------
11	000111	001000	---------
12	001000	001001	---------
13	001001	001010	---------
14	001010	001001	--0------
15	001010	001011	--1-----1
16	001011	000000	---------
17	001010	001100	--1-----0
18	001100	001101	---------
19	001101	001101	--0------
20	001101	001110	--1------
21	001110	001111	---------
22	001111	010000	---------
23	010000	010001	---------
24	010001	010000	---0-----
25	010001	010010	---1-----
26	010010	010011	---------
Продолжение таблицы 3.3 - Функции входа цифрового автомата
№	T1T2T3T4T5 T6	D1D2D3D4D5 D6	x1x2x3 x4x5x6 x7x8x9
27	010011	010100	---------
28	010100	010011	----0----
29	010100	010101	----1---1
30	010101	010110	---------
31	010110	010111	---------
32	010111	011000	---------
33	010100	011000	----1---0
34	011000	011001	---------
35	011001	011010	---------
36	011010	011011	---------
37	011011	011010	---0-----
38	011011	011100	---1-----
39	011100	011101	------0--
40	011100	100000	------1--
41	011101	011110	---------
42	011110	011111	---------
43	011111	011110	---0-----
44	011111	001110	---10----
45	011111	100000	---11----
46	100000	100001	-------1-
47	100001	100010	---------
48	100010	100011	---------
49	100011	100010	--0------
50	100011	100011	--1-----1
51	100011	100001	--1----10
52	100011	100100	--1----00
53	100100	000000	---------

Таблица 3.4 - Кодированая форма структурной таблицы (функции выхода)

№	y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15 y16 y17 y18 y19 y20 y21 y22 y23 y24 y25 y26 y27 y28 y29 y30 y31 y32 y33 y34 y35 y36 y37 y38 y39 y40
1	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2	1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
3	0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5	0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6	0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7	0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
9	0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11	0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13	0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0
14	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
17	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
18	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
19	0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
20	0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
21	0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
22	0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
23	0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0
24	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
25	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
26	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
27	0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
28	0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
29	0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
30	0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
31	0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
32	0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
33	0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
34	0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
35	0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
36	0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0
37	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
38	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
39	0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
40	0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
41	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
42	0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
43	0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
44	0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
45	0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
46	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
47	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
48	0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
49	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
50	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
51	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
52	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
53	0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

3.3 Выбор элементов памяти

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

Триггерные схемы классифицируют по следующим признакам:

- числу целочисленных устойчивых состояний;

- принципу построения;

- функциональным возможностям;

- способу приёма логических сигналов.

По способу работы с сигналами различают асинхронные, синхронные и смешанные триггерные схемы, а также статические и динамические.

Асинхронный триггер изменяет своё состояние непосредственно в момент появления соответствующего информационного сигнала.

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

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

Динамические триггеры воспринимают информационные сигналы при изменении (перепаде) сигнала на входе С от 0 к 1 (прямой динамический С-вход) или от 1 к 0 (инверсный динамический С-вход).

Статические триггеры в свою очередь подразделяют на одноступенчатые (однотактные) и двух-ступенчатые (двухтактные).

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

По структурному построению -- однотактные (триггеры защёлки), двухтактные и триггеры с динамическим управлением. По способу реакции на помехи -- прозрачные и непрозрачные. Непрозрачные, в свою очередь, делятся на проницаемые и непроницаемые. По функциональному назначению -- RS, D, JK, T, RR, SS, EE, DV.

При изготовлении триггеров применяются преимущественно полупроводниковые приборы (обычно полевые транзисторы), в прошлом -- электромагнитные реле, электронные лампы. В настоящее время логические схемы, в том числе с использованием триггеров, создают в интегрированных средах разработки под различные программируемые логические интегральные схемы (ПЛИС).

Используются в основном в вычислительной технике для организации компонентов вычислительных систем: регистров, счётчиков, процессоров, ОЗУ.

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

- с раздельной установкой состояния 0 и 1 (RS-триггеры). Если триггер является синхронным -- добавляется вход синхронизации C.;

- универсальные (JK-триггеры);

- с приёмом информации по одному входу D (D-триггеры, или триггеры задержки);

- со счётным входом Т (Т-триггеры).

Каждый тип триггера имеет собственную таблицу истинности. Выходное состояние триггера обычно обозначают буквой Q. Индекс возле буквы означает состояние до подачи сигнала (t) или после подачи сигнала (t+1).

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

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

RS-триггер.

RS-триггер -- триггер, который сохраняет своё предыдущее состояние при нулевых входах и меняет своё выходное состояние при подаче на один из его входов единицы. При подаче единицы на вход S (от англ. Set -- установить) выходное состояние становится равным логической единице. А при подаче единицы на вход R (от англ. Reset -- сбросить) выходное состояние становится равным логическому нулю. Если RS-триггер синхронный, то состояние его входов учитывается только в момент тактирования, например по переднему фронту импульса. Состояние, при котором на оба входа R и S одновременно поданы логические единицы, является запрещённым. Так, например, схема RS-триггера, изображённая на рисунке, при подаче на оба инверсных входа логического нуля, перейдёт в состояние, когда на обоих выходах будут единицы, что не соответствует логике выхода триггера, поскольку инверсный выход будет равен неинверсному.

S R Q(t) Q(t+1) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 * 1 1 1 *
Рисунок 3.5 - Таблица истинности RS-триггера	Рисунок 3.6 - RS-триггер

JK-триггер

JK-триггер работает так же как RS-триггер, с одним лишь исключением: при подаче логической единицы на оба входа J и K состояние выхода триггера изменяется на противоположное. Вход J (от англ. Jump -- прыжок) аналогичен входу S у RS-триггера. Вход K (от англ. Kill -- убить) аналогичен входу R у RS-триггера. При подаче единицы на вход J и нуля на вход K выходное состояние триггера становится равным логической единице. А при подаче единицы на вход K и нуля на вход J выходное состояние триггера становится равным логическому нулю. JK-триггер в отличие от RS-триггера не имеет запрещённых состояний на основных входах, однако это никак не помогает при нарушении правил разработки логических схем. На практике применяются только синхронные JK-триггеры, то есть состояния основных входов J и K учитываются только в момент тактирования, например по положительному фронту импульса на входе синхронизации.

На базе JK-триггера возможно построить D-триггер или Т-триггер. Как можно видеть в таблице истинности JK-триггера, он переходит в инверсное состояние каждый раз при одновременной подаче на входы J и K логической 1. Это свойство позволяет создать на базе JK-триггера Т-триггер, объединив входы J и К.



J K Q(t) Q(t+1) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0
Рисунок 3.7 - Таблица истинности JK-триггера	Рисунок 3.8 - JK-триггер

T-триггер

Т-триггер по каждому такту изменяет своё логическое состояние на противоположное при единице на входе Т, и не изменяет выходное состояние при нуле на входе T. Т-триггер часто называют счётным триггером. Т-триггер может строиться как на JK, так и на D-триггерах. Как можно видеть в таблице истинности JK-триггера, он переходит в инверсное состояние каждый раз при одновременной подаче на входы J и K логической 1. Это свойство позволяет создать на базе JK-триггера Т-триггер, объединяя входы J и К. Наличие в D-триггере динамического С входа позволяет получить на его основе T-триггер. При этом вход D соединяется с инверсным выходом, а на вход С подаются счётные импульсы. В результате триггер при каждом счётном импульсе запоминает значение , то есть будет переключаться в противоположное состояние.

T Q(t) Q(t+1) 0 0 0 0 1 1 1 0 1 1 1 0
Рисунок 3.9 - Таблица истинности T-триггера	Рисунок 3.10 - T-триггер



D-триггер

D-триггер (D от англ. delay -- задержка) -- запоминает состояние входа и выдаёт его на выход. D-триггеры имеют, как минимум, два входа: информационный D и синхронизации С. Сохранение информации в D-триггерах происходит в момент прихода активного фронта на вход С. Так как информация на выходе остаётся неизменной до прихода очередного импульса синхронизации, D-триггер называют также триггером с запоминанием информации или триггером-защёлкой. Рассуждая чисто теоретически, D-триггер можно образовать из любых RS- или JK-триггеров, если на их входы одновременно подавать взаимно инверсные сигналы.

D Q(t) Q(t+1) 0 0 0 0 1 0 1 0 1 1 1 1
Рисунок 3.11 - Таблица истинности D-триггера	Рисунок 3.12 - D-триггер

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

3.4 Построение структурного автомата

Для построения цифрового автомата на базисных логических элементах будем использовать автомат Мура. В качестве аппаратной реализации логических элементов выбираем D триггеры. Схема D триггера изображена на рисунке:



Рисунок 3.13 - D-триггер

где D - информационный вход триггера,

Т - прямой выход триггера,

- инверсный выход триггера,

С - тактовый вход,

R - вход сброса.

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

Рисунок 3.14 - Блок НЕ

где Х - входной сигнал,

У - выходной(инверсный) сигнал.

Таблица истинности выглядит следующим образом:

Х	0	1
	1	0

Рисунок 3.15 - Таблица истинности блока НЕ



Операция логического умножения (И), необходима для проверки деления на ноль. Логическая реализация элементов И представлена на рисунке 3.16.

Рисунок 3.16 - Элемент логики И

Таблица истинности операции логического умножения (И) выглядит следующим образом:

Х1	0	0	1	1
Х2	0	1	0	1
У	0	0	0	1

Рисунок 3.17 - Таблица истинности блока И

Операция сума по модулю 2 необходима для определения знака частного. Логическая реализация может быть осуществлена на блоках И-ИЛИ и представлена на рисунке 3.18

Рисунок 3.18 - Сумма по модулю 2



Аппаратная реализация данной схемы представлена на рисунке 3.19:

Рисунок 3.19 - Сумма по модулю 2

Таблица истинности выглядит следующим образом:

X1	0	0	1	1
X2	0	1	0	1
Y	0	1	1	0

Рисунок 3.20 - Таблица истинности блока mod2

Общая функциональная схема управляющего автомата изображена на рисунке 3.21

Рисунок 3.21 - Общая функциональная схема УА



Описание сигналов на схеме:

- D1-D6 - играют роль функций возбуждения

- T1-T6 - являются функциями выходов триггеров

- CLK - есть постоянный дискретный сигнал с помощью которого регулируется скорость работы D триггера

- RESET - сигнал сброса триггера

- yn - управляющие сигналы

- xn - условия

3.5 Построение и минимизация функций алгебры логики. Метод Квайна-Мак-Класки

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

Метод Квайна-Мак-Класки состоит из последовательного выполнения нескольких этапов:

1. Нахождение первичных импликант.

Все минтермы данной функции сравниваются попарно. Если минтеры отличаются одной координатой, то выписывается коньюнкция F, являющаяся минтермом (r+1)-го ранга. Минтермы r-го ранга, для которых произошло склеивание, отмечаются. Другими словами, нахождение простых импликант сводится к построению комплекса кубов. При построении последующих кубов, образующие предыдущие кубы отмечаются, чтобы выявить неометченные кубы. Этап заканчивается, когда ни один (r+1)-куб не может быть построен.

2. Составление таблиц покрытий

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

3. Определение существенных импликант

Если в столбце таблицы покрытий имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной импликантой, и ее выписывают в новое минимальное покрытие С(f). Из таблицы покрытий исключаются строки, соответствующие существенным импликантам и столбцы минтермов, покрываемые этими существенными импликантами.

4. Вычеркивание лишних столбцов

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

5. Вычеркивание простых лишних импликант

Если после вычеркивания столбцов в таблице появляются строки без меток, то импликанты этих строк вычеркиваются.

6. Выбор минимального покрытия

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

Попробуем минимизировать одну из функций состояний методом Метод Квайна-Мак-Класки.

D1 = !T1*!T2*!T3*!T4* T5* T6 + !T1* T2* T3* T4*!T5*!T6* X7 + !T1* T2* T3* T4* T5* T6* X4* X5 + T1*!T2*!T3*!T4*!T5*!T6* X8 + T1*!T2*!T3*!T4*!T5* T6 + T1*!T2*!T3*!T4* T5*!T6 + T1*!T2*!T3*!T4* T5* T6*!X3 + T1*!T2*!T3*!T4* T5* T6* X3*!X8*!X9 + T1*!T2*!T3*!T4* T5* T6* X3* X8*!X9 + T1*!T2*!T3*!T4* T5* T6* X3* X9



1. Нахождение первичных импликант

Таблица 3.5 - Вершины кубов (0-КУБЫ)
0-КУБЫ
№	T1T2T3T4T5T6X1X2X3X4X5X6X7X8X9	Метка
1	000011xxxxxxxxx	*
2	011100xxxxxx1xx
3	011111xxx11xxxx
4	100000xxxxxxx1x
5	100001xxxxxxxxx
6	100010xxxxxxxxx	*
7	100011xx0xxxxxx	*
8	100011xx1xxxx00	*
9	100011xx1xxxx10	*
10	100011xx1xxxxx1	*

Таблица 3.6 - 1-КУБЫ
1-КУБЫ
№	T1T2T3T4T5T6X1X2X3X4X5X6X7X8X9	Метка
1	100011xxxxxxxxx	*
2	x00011xxxxxxxxx
3	10001xxxxxxxxxx	*
4	1000x0xxxxxxxxx	*

Таблица 3.7 - 2-КУБЫ
2-КУБЫ
№	T1T2T3T4T5T6X1X2X3X4X5X6X7X8X9	Метка
1	10001xxxxxxxxxx
2	1000x1xxxxxxxxx

2. Составление таблицы покрытий

Таблица 3.7 - Таблица покрытия
Импликанты
№	T1T2T3T4T5T6X1X2X3X4X5X6X7X8X9	000011xxxxxxxxx	011100xxxxxx1xx	011111xxx11xxxx	100000xxxxxxx1x	100001xxxxxxxxx	100010xxxxxxxxx	100011xx1xxxx00	100011xx1xxxx10	100011xx1xxxxx1
1	011100xxxxxx1xx		+
2	011111xxx11xxxx			+
3	100000xxxxxxx1x				+
4	10001xxxxxxxxxx					+	+	+	+	+
5	1000x1xxxxxxxxx					+		+	+	+
6	x00011xxxxxxxxx	+
7	100001xxxxxxxxx					+

3. Определение существенных импликант

Таблица 3.7 - Существенные импликанты
№	T1T2T3T4T5T6X1X2X3X4X5X6X7X8X9
1	011100xxxxxx1xx
2	011111xxx11xxxx
3	100000xxxxxxx1x
4	10001xxxxxxxxxx
5	x00011xxxxxxxxx

4. Выбор минимального покрытия

Таблица 3.8 - Минимальное покрытие функции
№	T1T2T3T4T5T6X1X2X3X4X5X6X7X8X9
1	011100xxxxxx1xx
2	011111xxx11xxxx
3	100000xxxxxxx1x
4	10001xxxxxxxxxx
5	1000x1xxxxxxxxx
6	x00011xxxxxxxxx

Запишем полученную МДНФ:

D1 = !T1* T2* T3* T4*!T5*!T6* X7 + !T1* T2* T3* T4* T5* T6* X4* X5 + T1*!T2*!T3*!T4*!T5*!T6* X8 + T1*!T2*!T3*!T4* T5 + T1*!T2*!T3*!T4* T6 + !T2*!T3*!T4* T5* T6



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

Функции состояний до минимизации:

D1 = !T1*!T2*!T3*!T4* T5* T6 + !T1* T2* T3* T4*!T5*!T6* X7 + !T1* T2* T3* T4* T5* T6* X4* X5 + T1*!T2*!T3*!T4*!T5*!T6* X8 + T1*!T2*!T3*!T4*!T5* T6 + T1*!T2*!T3*!T4* T5*!T6 + T1*!T2*!T3*!T4* T5* T6*!X3 + T1*!T2*!T3*!T4* T5* T6* X3*!X8*!X9 + T1*!T2*!T3*!T4* T5* T6* X3* X8*!X9 + T1*!T2*!T3*!T4* T5* T6* X3* X9

D2 = !T1*!T2* T3* T4* T5* T6 + !T1* T2*!T3*!T4*!T5*!T6 + !T1* T2*!T3*!T4*!T5* T6*!X4 + !T1* T2*!T3*!T4*!T5* T6* X4 + !T1* T2*!T3*!T4* T5*!T6 + !T1* T2*!T3*!T4* T5* T6 + !T1* T2*!T3* T4*!T5*!T6*!X5 + !T1* T2*!T3* T4*!T5*!T6* X5*!X9 + !T1* T2*!T3* T4*!T5*!T6* X5* X9 + !T1* T2*!T3* T4*!T5* T6 + !T1* T2*!T3* T4* T5*!T6 + !T1* T2*!T3* T4* T5* T6 + !T1* T2* T3*!T4*!T5*!T6 + !T1* T2* T3*!T4*!T5* T6 + !T1* T2* T3*!T4* T5*!T6 + !T1* T2* T3*!T4* T5* T6*!X4 + !T1* T2* T3*!T4* T5* T6* X4 + !T1* T2* T3* T4*!T5*!T6*!X7 + !T1* T2* T3* T4*!T5* T6 + !T1* T2* T3* T4* T5*!T6 + !T1* T2* T3* T4* T5* T6*!X4

D3 = !T1*!T2*!T3* T4* T5* T6 + !T1*!T2* T3*!T4*!T5*!T6 + !T1*!T2* T3*!T4*!T5* T6 + !T1*!T2* T3*!T4* T5*!T6*!X3 + !T1*!T2* T3*!T4* T5*!T6* X3*!X9 + !T1*!T2* T3*!T4* T5*!T6* X3* X9 + !T1*!T2* T3* T4*!T5*!T6 + !T1*!T2* T3* T4*!T5* T6*!X3 + !T1*!T2* T3* T4*!T5* T6* X3 + !T1*!T2* T3* T4* T5*!T6 + !T1* T2*!T3* T4*!T5*!T6* X5*!X9 + !T1* T2*!T3* T4* T5* T6 + !T1* T2* T3*!T4*!T5*!T6 + !T1* T2* T3*!T4*!T5* T6 + !T1* T2* T3*!T4* T5*!T6 + !T1* T2* T3*!T4* T5* T6*!X4 + !T1* T2* T3*!T4* T5* T6* X4 + !T1* T2* T3* T4*!T5*!T6*!X7 + !T1* T2* T3* T4*!T5* T6 + !T1* T2* T3* T4* T5*!T6 + !T1* T2* T3* T4* T5* T6*!X4 + !T1* T2* T3* T4* T5* T6* X4*!X5

D4 = !T1*!T2*!T3*!T4* T5*!T6* X1 + !T1*!T2*!T3* T4*!T5*!T6*!X2 + !T1*!T2*!T3* T4*!T5*!T6* X2 + !T1*!T2*!T3* T4* T5*!T6 + !T1*!T2* T3*!T4* T5*!T6* X3*!X9 + !T1*!T2* T3* T4*!T5*!T6 + !T1*!T2* T3* T4*!T5* T6*!X3 + !T1*!T2* T3* T4*!T5* T6* X3 + !T1*!T2* T3* T4* T5*!T6 + !T1* T2*!T3*!T4* T5* T6 + !T1* T2*!T3* T4*!T5*!T6* X5* X9 + !T1* T2*!T3* T4*!T5* T6 + !T1* T2*!T3* T4* T5*!T6 + !T1* T2* T3*!T4* T5* T6* X4 + !T1* T2* T3* T4*!T5*!T6*!X7 + !T1* T2* T3* T4*!T5* T6 + !T1* T2* T3* T4* T5*!T6 + !T1* T2* T3* T4* T5* T6*!X4 + !T1* T2* T3* T4* T5* T6* X4*!X5 + T1*!T2*!T3*!T4* T5* T6* X3*!X8*!X9

D5 = !T1*!T2*!T3*!T4*!T5* T6 + !T1*!T2*!T3*!T4* T5*!T6*!X1 + !T1*!T2*!T3* T4*!T5*!T6* X2 + !T1*!T2*!T3* T4* T5*!T6 + !T1*!T2* T3*!T4*!T5* T6 + !T1*!T2* T3*!T4* T5*!T6* X3* X9 + !T1*!T2* T3* T4*!T5* T6* X3 + !T1*!T2* T3* T4* T5*!T6 + !T1* T2*!T3*!T4*!T5* T6* X4 + !T1* T2*!T3*!T4* T5*!T6 + !T1* T2*!T3* T4*!T5*!T6*!X5 + !T1* T2*!T3* T4*!T5* T6 + !T1* T2*!T3* T4* T5*!T6 + !T1* T2* T3*!T4*!T5* T6 + !T1* T2* T3*!T4* T5*!T6 + !T1* T2* T3*!T4* T5* T6*!X4 + !T1* T2* T3* T4*!T5* T6 + !T1* T2* T3* T4* T5*!T6 + !T1* T2* T3* T4* T5* T6*!X4 + !T1* T2* T3* T4* T5* T6* X4*!X5 + T1*!T2*!T3*!T4*!T5* T6 + T1*!T2*!T3*!T4* T5*!T6 + T1*!T2*!T3*!T4* T5* T6*!X3 + T1*!T2*!T3*!T4* T5* T6* X3* X9

D6 = !T1*!T2*!T3*!T4*!T5*!T6 + !T1*!T2*!T3*!T4* T5*!T6*!X1 + !T1*!T2*!T3*!T4* T5* T6 + !T1*!T2*!T3* T4*!T5*!T6*!X2 + !T1*!T2*!T3* T4* T5*!T6 + !T1*!T2* T3*!T4*!T5*!T6 + !T1*!T2* T3*!T4* T5*!T6*!X3 + !T1*!T2* T3*!T4* T5*!T6* X3* X9 + !T1*!T2* T3* T4*!T5*!T6 + !T1*!T2* T3* T4*!T5* T6*!X3 + !T1*!T2* T3* T4* T5*!T6 + !T1* T2*!T3*!T4*!T5*!T6 + !T1* T2*!T3*!T4* T5*!T6 + !T1* T2*!T3* T4*!T5*!T6*!X5 + !T1* T2*!T3* T4*!T5*!T6* X5* X9 + !T1* T2*!T3* T4* T5*!T6 + !T1* T2* T3*!T4*!T5*!T6 + !T1* T2* T3*!T4* T5*!T6 + !T1* T2* T3* T4*!T5*!T6*!X7 + !T1* T2* T3* T4* T5*!T6 + T1*!T2*!T3*!T4*!T5*!T6* X8 + T1*!T2*!T3*!T4* T5*!T6 + T1*!T2*!T3*!T4* T5* T6* X3* X8*!X9 + T1*!T2*!T3*!T4* T5* T6* X3* X9



Функции состояний после минимизации:

D1 = !T1* T2* T3* T4*!T5*!T6* X7 + !T1* T2* T3* T4* T5* T6* X4* X5 + T1*!T2*!T3*!T4*!T5*!T6* X8 + T1*!T2*!T3*!T4* T5 + T1*!T2*!T3*!T4* T6 + !T2*!T3*!T4* T5* T6

D2 = !T1*!T2* T3* T4* T5* T6 + !T1* T2*!T3*!T4*!T5* T6 + !T1* T2*!T3* T4*!T5*!T6 + !T1* T2* T3*!T4* T5* T6 + !T1* T2* T3* T4*!T5*!T6*!X7 + !T1* T2*!T4*!T6

D3 = !T1*!T2* T3*!T4* T5*!T6 + !T1*!T2* T3* T4*!T5* T6 + !T1* T2*!T3* T4*!T5*!T6* X5*!X9 + !T1* T2* T3*!T4* T5* T6 + !T1* T2* T3* T4*!T5*!T6*!X7 + !T1* T2* T3* T4* T5* T6* X4*!X5 + !T1*!T3* T4* T5* T6 + !T1* T3*!T4*!T5

D4 = !T1*!T2*!T3*!T4* T5*!T6* X1 + !T1*!T2*!T3* T4*!T5*!T6 + !T1*!T2* T3*!T4* T5*!T6* X3*!X9 + !T1*!T2* T3* T4*!T5* T6 + !T1*!T2* T3* T4*!T6 + !T1* T2*!T3*!T4* T5* T6 + !T1* T2*!T3* T4*!T5*!T6* X5* X9 + !T1* T2* T3*!T4* T5* T6* X4 + !T1* T2* T3* T4*!T5*!T6*!X7 + !T1* T2* T3* T4* T5* T6*!X4 + !T1* T2* T3* T4* T5* T6* X4*!X5 + !T1* T2* T4*!T5* T6 + T1*!T2*!T3*!T4* T5* T6* X3*!X8*!X9

D5 = !T1*!T2*!T3*!T4* T5*!T6*!X1 + !T1*!T2*!T3* T4*!T5*!T6* X2 + !T1*!T2* T3*!T4* T5*!T6* X3* X9 + !T1*!T2* T3* T4*!T5* T6* X3 + !T1* T2*!T3*!T4*!T5* T6* X4 + !T1* T2*!T3* T4*!T5*!T6*!X5 + !T1* T2* T3* T4* T5* T6* X4*!X5 + !T1* T2* T3* T5* T6*!X4 + !T1* T2* T4*!T5* T6 + !T1* T4* T5*!T6 + T1*!T2*!T3*!T4* T5*!T6 + T1*!T2*!T3*!T4* T5* T6*!X3 + T1*!T2*!T3*!T4* T5* T6* X3* X9

D6 = !T1*!T2*!T3*!T4* T5*!T6*!X1 + !T1*!T2*!T3*!T4* T5* T6 + !T1*!T2*!T3* T4*!T5*!T6*!X2 + !T1*!T2* T3*!T4* T5*!T6*!X3 + !T1*!T2* T3*!T4* T5*!T6* X3* X9 + !T1*!T2* T3* T4*!T5* T6*!X3 + !T1* T2*!T3* T4*!T5*!T6*!X5 + !T1* T2*!T3* T4*!T5*!T6* X5* X9 + !T1* T2* T3* T4*!T5*!T6*!X7 + !T1*!T4*!T5*!T6 + !T1* T4* T5*!T6 + T1*!T2*!T3*!T4*!T5*!T6* X8 + T1*!T2*!T3*!T4* T5*!T6 + T1*!T2*!T3*!T4* T5* T6* X3* X8*!X9 + T1*!T2*!T3*!T4* T5* T6* X3* X9