Университет Кафедра "Вычислительная техника"

Вид материала

Пояснительная записка

Содержание Синтез функций возбуждения и выходов для D- триггера 7 Разработка функциональной схемы МПА 10 Разработка алгоритма работы управляющего автомата Тестирование, функциональное моделирование и корректировка алгоритма Проектирование автомата с жесткой логикой Переход к стандартному языку задания автомата Выбор оптимального варианта кодирования Синтез функций возбуждения и выходов для D- триггера Реализация ЦА на заданной элементной базе (К155) Реализация функций переходов и выходов Описание схемы пуска и инициализации Проектирование автомата с программируемой логикой Определение формата микрокоманд Разработка функциональной схемы МПА Составление таблицы прошивки ПЗУ Приложение №1 Приложение №2

Подобный материал:

• «Информатика и вычислительная техника», 723.11kb.
• Учебная программа (Syllabus) Дисциплина: Интерфейсы компьютерных систем (iks 3304), 321.31kb.
• Учебная программа (Syllabus) Дисциплина «Инструментальные средства разработки программ», 374.12kb.
• В. Ф. Пономарев математическая логика, 3033.04kb.
• Рабочая программа дисциплины «Методы оптимизации» по направлению подготовки дипломированного, 132.79kb.
• Рабочая программа дисциплины «Теория систем» по направлению подготовки дипломированного, 142.63kb.
• Рабочая программа дисциплины «Компьютерная графика» по направлению подготовки дипломированного, 108.6kb.
• Рабочая учебная программа по дисциплине вычислительная математика специальность: 230100, 133.73kb.
• Рабочая программа дисциплины «Параллельные вычислительные процессы» по направлению, 108.72kb.
• Рабочая программа дисциплины «Инструментальные средства 3D графики» по направлению, 112.55kb.

Пензенский Государственный Университет

Кафедра “Вычислительная техника”

Пояснительная записка

К курсовой работе по дисциплине “Теория автоматов”

На тему: “Проектирование управляющего автомата с жесткой и программируемой логикой для выполнения заданной макрооперации”


Выполнил: Верещагин А.В. группа 98ВВ2

Проверил: Калиниченко Е.И.

Пенза 2000

Содержание:

Разработка алгоритма работы управляющего автомата

Нам необходимо разработать алгоритм работы УА реализующего макрооперацию y=(a&b)². В соответствии с заданием разрядность операндов в зависимости от структуры ОА сможет быть: 8,16,32,64 бита. Так как никаких ограничений на ОА на нас не накладывает, то будим оперировать с 8 разрядными числами, а результат представим 16 разрядным. Операнды представлены в формате целых чисел в дополнительном коде.

Значение y=(a&b)² вычисляется в два действия: конъюнкция и возведение в квадрат. Специфика задачи состоит в том, что квадрат любого числа есть число неотрицательное  y>=0 всегда. Таким образом удобнее использовать алгоритм умножения для целых чисел без знака, проведя дополнительное действие:

• (a-b)=(a-b), если (а-b)>0
  
• (a-b)=-(a-b), если (a-b)<0
  

Умножение целых чисел без знака будим производить с использованием микроопераций сложение и микрооперации сдвиг(вариант №1)[1]. При этом нам понадобится:

• Регистр Р1 для хранения n-разрядного множимого.
  
• Регистр Р2 в который перед операцией умножения размещается n-разрядный множитель, а итоге находятся младшие разряды результата.
  
• Сумматор СМ и регистр сумматора РСМ объединенные в один блок и предназначенные для получения суммы частичных произведений и хранения их старших разрядов.
  
• Одноразрядный регистр С, служащий для фиксации из старшего разряда СМ переноса.
  
• Счетчик тактов СчТ, в который перед операцией умножение заносится число тактов, равное разрядности операндов (т.е. 16).
  

Управление операцией умножения будет выполнять цифра множителя, зафиксированная в младшем разряде регистра Р2. Если эта цифра равна 1, то выполняется операция сложения множимого с текущим значением суммы частичных произведений, расположенном в регистре РСМ. Если цифра равна 0, то такого сложения не производится. После этого содержимое регистров С, РСМ, Р2 сдвигается вправо на один разряд для формирования новой суммы частичных произведений. Из содержимого СчТ вычитается единица и проверяется его новое значение; Если оно не равно нулю, то процесс повторяется. Таким образом результат зафиксируется в двух регистрах РСМ и Р2.

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

Тестирование, функциональное моделирование и корректировка алгоритма

Моделирование будим производить с помощью программы TASM на языке ассемблер. Так как исходные данные и результат хранятся в ОЗУ, то выделим память для:

• Чисел a и b – формат db.
  
• Результата c –формат dw.
  

Переведем полученный в предыдущем пункту алгоритм в ассемблерный код (Приложение №1). Дадим краткие комментарии.

• Конъюнкция (a-b), AX=P2:
  

mov ax,a

sub ax,b

• Анализ переполнения:
  

JO er

• Вычисление модуля |a-b|:
  

JNS met1

neg ax

• Занесение в Р1 множимого, BX=P1:
  

met1: mov bx,ax

• Инициализация счетчика (CX=СчТ=16):
  

mov cx,16

• Анализ текущей цифры множителя:
  

met2: test ax,1b

JZ met3

• Получение суммы частичных произведений:
  

add dx,bx

• Сдвиг (C->PCM->P2), обнуление С, причем С=CF, РСМ=DX, P2=AX:
  

met3: rcr dx,1

rcr ax,1

clc

• Возврат при СчТ=CX!=0:
  

dec cx

jnz met2

• Занесение результата в ОЗУ:
  

mov WORD PTR res,ax

mov WORD PTR res+2,dx

• Сигнал ошибки:
  

er: mov error,1


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

Результат работы алгоритма на тестовых наборах данных приведен в Приложении №2.

Проектирование автомата с жесткой логикой

Переход к стандартному языку задания автомата

Полученный и отлаженный алгоритм необходимо представить в виде удобном для проектирования цифрового автомата. Воспользуемся языком ГСА. В нем кроме вершин соответствующих шагам алгоритма также предусматривается вершины S₀(y₀) и S_k(y_k).


В результате получим ГСА приведенное в Приложении №3. По данной ГСА построим прямую таблицу переходов ЦА «Мура»:

ПТП ЦА “Мура”
№	Si(t)	Xi,j(t)	Sj(t+1)(yj)
1	S0	1	S1(y1)
2	S1	1	S2(y2)
3	S2	z Z	Sk(yk) S3(y3)
4	S3	1	S4(y4)
5	S4	1	S5(y5)
6	S5	1	S6(y6)
7	S6	z Z	S8(y8) S7(y7)
8	S7	1	S8(y8)
9	S8	1	S9(y9)
10	S9	1	S10(y10)
11	S10	Z z	S4(y4) S11(y11)
12	S11	1	Sk(yk)

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

Оптимальным вариантом кодирования будим считать такое кодирование при котором функции переходов и функции выходов наиболее просты. Так как ЦА необходимо реализовать на RS-триггере, то необходимо применить кодировку при которой состояние кодируется n-разрядным числом с минимальным количеством единиц. Причем состояния в которые переход осуществляется наиболее часто имеют приоритет при кодировке. Следует иметь ввиду, что автомат с жесткой логикой проектируется по критерию максимума быстродействия и  необходимо ориентироваться на вариант схемы (который напрямую зависит от варианта кодирования) при котором КС имеет наименьшую задержку. Число n имеет ограничение: n>ln(An), где An- число состояний автомата.

Кодированная ПТП ЦА «Мили»
Ai	Ai(t)	Xi,j	Aj	Aj(t)	yi,j(t)	qdi
	Q1Q2Q3…Q12			Q1Q2Q3…Q12		qd1qd2qd3qd4qd5qd6qd7qd8qd9qd10qd11qd12
A0	000000000001	1	A1	100000000000	y1	1
A1	100000000000	1	A2	010000000000	y2	1
A2	010000000000	x1	A11	000000000010	y14	1
		X1x2	A3	001000000000	y3	1
		X1X2	A4	000100000000	y4y5	1
A3	001000000000	1	A4	000100000000	y4y5	1
A4	000100000000	1	A5	000010000000	y6	1
A5	000010000000	x3	A6	000001000000	y7	1
		X3	A7	000000100000	y8	1
A6	000001000000	1	A7	000000100000	y8	1
A7	000000100000	1	A8	000000010000	y9	1
A8	000000010000	1	A9	000000001000	y10y11	1
A9	000000001000	X3	A10	000000000100	y12	1
		X3	A5	000010000000	y6	1
A10	000000000100	1	A11	000000000010	y13	1
A11	000000000010	1	A12		yk

Кодировку состояния А₁₂ я выполнять не стал так как это автомат Мили и сигнал окончания работы yk(по которому автомат сбрасывается в начальное положение) выдается при переходе из состояния А₁₁. Такое положение соответствует кодировке состояния А₁₂ как 000000000000.

Синтез функций возбуждения и выходов для D- триггера

По полученной кодированной ПТП определим функции выходов y_i:

y1=A₀=Q₁₂

y2=A₁=Q₁

y3=A₂X1x2=Q₂X1x2

y4=y5=A₂X1X2|A₃=Q₂X1X2|Q₃

y6=A₄|A₉X3=Q₄|Q₉X3

y7=A₅x3=Q₅x3

y8=A₅X3|A₆=Q₅X3|Q₆

y9=A₇=Q₇

y10=y11=A₈=Q₈

y12=A₉x3=Q₉x3

y13=A₁₀=Q₁₀

y14=A₂x1=Q₂x1

yk=A₁₁=Q₁₁


Функции переходов имеют вид:

q_d1=A₀=Q₁₂

q_d2=A₁=Q₁

q_d3=A₂X1x2=Q₂X1x2

q_d4=A₂X1X2|A₃=Q₂X1X2|Q₃

q_d5=A₄|A₉X3=Q₄|Q₉X3

q_d6=A₅x3=Q₅x3

q_d7=A₅X3|A₆= Q₅X3|Q₆

q_d8=A₇=Q₇

q_d9=y11=A₈=Q₈

q_d10=A₉x3=Q₉x3

q_d11=A₂x1|A₁₀=Q₂x1|Q₁₀


Как видно почти все функции возбуждения дублируются с функциями выходов, (за исключением: y13, y14, q_d11), поэтому одна и та же КС будет реализовывать и функции возбуждения и функции выходов. Простейшие функции (Пример: y9=Q₇), будим снимать прямо с выходов элементов памяти. Функции типа y14=A₂x1 реализуем на элементах 2-И(3-И). Для того, чтобы уложиться в один ряд логики необходимо привести некоторые функции к виду И-ИЛИ-НЕ (реализация на элементах ЛР):

q_d4=y4=y5= Q₂X1X2|Q₃=Q₂Q₃|Q₃x1|Q₃x2

q_d5=y6=Q₄|Q₉X3=Q₄Q₉|Q₄x3

q_d7=y8=Q₅X3|Q₆=Q₅Q₆|x3Q₆

q_d11=Q₂x1|Q₁₀=Q₂Q₁₀|X1Q₁₀


Следует обратить внимание на функцию y1. Этот сигнал должен выдастся при переходе из состояния A₀. При y1=Q₁₂ он будит выдаваться все время которое автомат находится в состоянии A₀. Для устранения этого казуса представим y1=Q₁₂x_p, где х_р-выход триггера отвечающего за работу всего автомата в целом.

Полученные функции переходов и выходов минимизации не подлежат.

Реализация ЦА на заданной элементной базе (К155)

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

В задании указано, что необходимо реализовать автомат на D-триггерах. У него должен быть вход синхронизации (по фронту) и вход сброса. Среди серии К155 таким требованиям удовлетворяют триггеры К155ТМ2 и К155ТМ8. Отдадим предпочтение триггеру К155ТМ8 так как его использование дает больший выигрыш коэффициента по оборудованию, чем К155ТМ2. Микросхема имеет четыре D-триггера (D1, D2, D3, D4), общий вход синхронизации (С), общий вход сброса (R), прямые и инверсные выходы(Q_i, Q_i). Синхронизация осуществляется по переднему фронту. В корпусе имеется одна микросхема. Задержка данной микросхемы равна 35нс. На принципиальной схеме это элементы: D2, D3, D4.

Реализация функций переходов и выходов

Р
еализация функций переходов и выходов осуществляется на элементах К155ЛР1, К155ЛР3, К155ЛИ1, К155ЛИ4. На принципиальной схеме это элементы: D9.1, D9.2, D10.1, D11, D7.2, D12.1, D7.3, D7.4, D13.1. Максимальная задержка этих элементов равна 22нс. Так как синхроимпульсы поступающие на схему имеют скважность равную двум, то максимальная частота работы схемы будит высчитана по следующей формуле:

Где T_{зд_тр} – время задержки триггера, а Т_{зд_кс} – время задержки комбинационной схемы. При такой работе схемы во время присутствия низкого уровня синхросигнала УА будет формировать выходные сигналы, а при высоком уровне ОА – входные сигналы УА.

Описание схемы пуска и инициализации

По сигналу инициализации, который подается при включении питания схема должна устанавливаться в исходное состояние. По сигналу «пуск» автомат начинает свою работу. Исходным состоянием схемы является состояние триггеров 000000000000. Это обеспечивается тем, что при приходе сигнала «иниц» на вход R триггера D6.1 на его выходе появится 0. Этот 0 поступает на входы R триггеров D2, D3, D4 и поддерживает их в нулевом состоянии. Сигналом «пуск» D6.1 и D6.2 устанавливаются в 1. Сброс триггеров D2, D3, D4 прекращается и на входы синхронизации через элемент D7.1 начинают поступать синхроимпульсы. Особенностью схемы является несоответствие кода начального события S₀ исходному состоянию элементов памяти. Это устраняется при помощи элемента D6.2 который имеет на выходе единицу только для первого такта работы автомата. Этот сигнал подан на 4-й вход триггера D4:

q_d12=x_н

Триггер D6.2 сбрасывается в ноль первым положительным уровнем синхросигнала прошедшего на схему. По окончанию работы выдается сигнал yk который сбрасывает триггер D6.1 в ноль: схема опять находится в исходном состоянии.

Проектирование автомата с программируемой логикой

Определение формата микрокоманд

В соответствии с заданием мне необходимо спроектировать микропрограммный управляющий автомат с естественной адресацией. Для такой адресации в [1] предусмотрено два формата микрокоманд: операционная и управляющая:

Г
де:

• первый бит определяет тип МК;
  
• Y1, Y2 – код выходных сигналов на данном такте;
  
• П – поле прямой (инверсной) проверки условия;
  
• ЛУ – код логического условия;
  
• Адрпер –адрес перехода в случае выполнения (невыполнения) логического условия.
  

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

У
нас 16 выходных сигналов  на поле Y необходимо минимум 4 бита; 3 логических условия  ЛУ займет 2 бита; для поля Адрпер будет достаточно 5 бит (32 адреса). Таким образом необходимый размер МК – 8 бит  легко найти ПЗУ и регистр такого формата.

Закодируем выходные сигналы и ЛУ:

y0=0000 x1=01

y1=0001 x2=10

y2=0010 x3=11

y3=0011

y4=0100

y5=0101

y6=0110

y7=0111

y8=1000

y9=1001

y10=1010

y11=1011

y12=1100

y13=1101

y14=1110

yk=1111

Разработка функциональной схемы МПА

В отличии от автомата с жесткой логикой, МПА имеет вполне определенную структуру [1]. В него входит:

• ПЗУ разрядности N – в ней хранятся микрокоманды определенного формата.
  
• РСЛ – регистор слова. Производит выборку микрокоманды из памяти и обеспечивает синхронность работы схемы.
  
• РА- регистор адреса. Формирует адрес следующей микрокоманды по данным предыдущей.
  

Кроме этошо нам понадобятся:

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

При разработке функциональной схемы будем ориентироваться на реальные элементы:

1. ПЗУ. Нам необходима микросхема постоянной памяти работающая с 8-ми разрядными словами и имеющая как минимум 2⁵ адресов. Это обеспечит микросхема К155РЕ3(328).
   
2. РСЛ. Этот регистр должен быть 8-ми разрядным и работать по переднему фронту. Этим требованиям отвечает микросхема К155ИР13.
   
3. РА. Должен выполнять функции:
   

• Сброс в ноль
  
• Увеличение содержимого на единицу
  
• Параллельное занесение информации со входов данных
  

Для эти целей может быть использованы две четырех разрядные микросхемы К155ИЕ7 соединенные по входу переноса.

4. MS. Необходим ммультиплексор имеющий возможность коммутировать 4 входных сигнала – микросхема К155КП2
   
5. DC. Дешифратор 4-16, имеющий вход разрешения –микросхема К155ИД3. При этом активным выходным сигналом считается ноль.
   

Управление работой РА будим осуществлять комбинационной схемы КС. Необходимо реализовать функцию:

РСЛ[0]	ЛУ	Команда РА
0	0 1	РА=РА+1
1	0 1	РА=РСЛ[3/7] РА=РА+1

Примечание: функцию РА=РА+1 легче реализовать как отрицание функции РА=РСЛ[3/7].

Следует учесть, что занесение РА=РА+1 должно происходить по фронту и  сигнал РА=РА+1 в КС следует соединить с синхроимпульсом по И.

Схема работает следующим образом:

При приходе сигнала ПУСК триггер устанавливается в единицу и разрешает проход синхроимпульсов и сигнала РА=0 на регистр адреса РА. Этот сигнал производит пуск автомата (выполнение микропрограммы начинается с нулевого адреса). По сигналу «чтение» который формирует КС производится выборка микрокоманды из ПЗУ (адрес МК находится в РА) и передача её на выход РСЛ. Если РСЛ[0]=0, то разрешается работа дешифратора управляющих сигналов. Кроме этого КС выдает сигнал РА=РА+1 на РА для выборки следующей микрокоманды. Если РСЛ[0]=1, то блокируется работа DC и через MS пропускается значение ЛУ x_i, номер которого указан в РСЛ[1/2]. Если это ЛУ положительно, то на РА через КС поступает сигнал РА=РА+1, если отрицательно, то сигнал РА=РСЛ[3/7]. Если РСЛ[0]=1, а РСЛ[1/2]=00, то происходит БПУ по адресу РСЛ[3/7] – КС выдает сигнал РА=РСЛ[3/7]. Признаком конца микропрограммы является выдача сигнала yk, который сбрасывает управляющий триггер.

Составление таблицы прошивки ПЗУ

Перед тем, как начать прошивку, несколько преобразуем ГСА указанную в Приложение №3. Так как в соответствии с определенным форматом микрокоманд необходимо, что бы выдавался только один сигнал за такт, то разделим вершины 4 и 9 на (4^/ и4^//) и (9^/ и 9^//) соответственно. Дадим обозначение условным вершинам (по порядку их следования на ГСА): 14, 15, 16, 17. В результате получим следующую таблицу:

Адрес слова ПЗУ	Микрокоманда		Номер вершин схемы алгоритма
	Признак МК	Основные поля управляющей и операционной МК
0	0	0 0 0 0 0 0 0	0
1	0	0 0 0 0 0 0 1	1
2	0	0 0 0 0 0 1 0	2
3	1	0 1 0 0 1 1 0	14
4	0	0 0 0 1 1 1 0	12
5	1	0 0 1 0 1 0 0	БПУ
6	1	1 0 0 1 0 0 0	15
7	0	0 0 0 0 0 1 1	3
8	0	0 0 0 0 1 0 0	4/
9	0	0 0 0 0 1 0 1	4//
10	0	0 0 0 0 1 1 0	5
11	1	1 1 0 1 0 1 1	16
12	0	0 0 0 0 1 1 1	6
13	0	0 0 0 1 0 0 0	7
14	0	0 0 0 1 0 0 1	8
15	0	0 0 0 1 0 1 0	9/
16	0	0 0 0 1 0 1 1	9//
17	1	1 1 0 1 0 1 0	12
18	0	0 0 0 1 1 0 0	10
19	0	0 0 0 1 1 0 1	11
20	0	0 0 0 1 1 1 1	13

Литература:

1. Сергеев Н.П., Вашкевич Н.П. Основы вычислительной техники. Москва «Высшая школа» 1988.
   
2. Шило В.Л. Популярные цифровые микросхемы. Челябинск «Метталургия» 1988.
   
3. Справочник по интегральным микросхемам. Под редакцией Б.В. Тарабрина. Москва «Энергия» 1980.
   
4. Вашкевич Н.П. Синтез микропрограммных управляющих автоматов. Пенза 1990.
   

Приложение №1

stseg segment para stack

dw 16 dup (?)

stseg ends

dseg segment para

a dw 2531h

b dw 47F0h

error db 0

res dd ?

dseg ends

cseg segment para public

assume cs:cseg,ds:dseg,ss:stseg

kurs proc

push ds ; //Всегда

mov ax,0 ; //

push ax ; //

mov ax,dseg ; //

mov ds,ax ; //


;Мой код

mov ax,a

sub ax,b ;AX=a-b

JO er ;Если переполнение мантиссы, то выход

JNS met1

neg ax ;Если a-b<0 ,то меняем знак

met1: mov bx,ax

mov cx,16 ;CX- счетчик=16(разрядность)

;Цикл умножения причем AX=P2, DX=PCM ,BX=(a-b)

met2: test ax,1b ;Анализируем AX[0]

JZ met3

add dx,bx ;Если AX[0]=1 то PCM=PCM+(a-b)

met3: rcr dx,1 ;CF->PCM->CF

rcr ax,1 ;CF->P2->CF

clc

dec cx

jnz met2

mov WORD PTR res,ax

mov WORD PTR res+2,dx

jmp exit

er: mov error,1

;Конец моего кода


exit:mov ax,4c00h

int 21h

ret

кurs endp

cseg ends

end kurs

Приложение №2

Turbo Debugger Log

Begin:

Regs

ax 29D7

bx 0000

cx 0000

dx 0000

si 0000

di 0000

bp 0000

sp 001C

Regs

c=0

z=0

s=0

o=0

p=0

a=0

i=1

d=0

Watches

error byte ' ' 0 (00h)

res dword 0 (0h)

a word 9521 (2531h)

b word 18416 (47F0h)

End:

Regs

ax 4A81

bx 22BF

cx 0000

dx 04B7

si 0000

di 0000

bp 0000

sp 001C

Regs

c=0

z=1

s=0

o=0

p=1

a=0

i=1

d=0

Watches

error byte ' ' 0 (00h)

res dword 79121025 (4B74A81h)

a word 9521 (2531h)

b word 18416 (47F0h)

Приложение №3