Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Ускоренное умножение в прямом коде автомата Мили с использование T-триггера

Автор работы : студент группы 223-10 ИТр Гайнуллин Ильдар Рамилевич

Вариант №15 Ускоренное умножение в прямом коде автомата Мили с использование T-триггера

Аннотация

В данной курсовой работе был построен автомат Мили на элементе T-триггера для операции ускоренного умножения в прямом коде.

Курсовая работа выполнена в 19 листов в формате А4 14 шрифтом Times New Roman

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

-граф-схемы алгоритма в количестве 3 штук

-функциональные схемы 2 шт.

-таблица 1 шт.

Введение

Абстрактный автомат (АА) – дискретный преобразователь информации; представляет собой множество, состоящее из шести элементов:

S = {X, Q, Y, δ, λ, q₁}

S – абстрактный автомат;

X – множество входных символов (входной алфавит автомата):

X = {x₁, ... , x_m};

Q – множество состояний автомата:

Q = {q₁, ... , q_n};

Y – множество выходных символов (выходной алфавит автомата):

Y = {y₁, ... , y_p};

δ – функция переходов автомата из одного состояния в другое:

q_j= δ(q_i, x_k),

где: q_j – следующее (новое) состояние автомата; qi – текущее состояние автомата; x_k – текущий входной символ;

λ – функция выходов:

y_l = λ (q_i, x_k);

q₁ – начальное состояние автомата (применяется также обозначение q₀).

Автомат называется конечным, если множества X, Q, Y – конечны.

На рис. 1 t – дискретное время: t = nT, где T – интервал (такт), разделяющий дискретные моменты времени; если T = 1, то t = n, т. е. дискретное время сопоставляется упорядоченному ряду натуральных чисел.

Абстрактный автомат (АА) можно рассматривать как "черный ящик" с одним входом и одним выходом, с которым можно экспериментировать, не зная, что находится внутри.

Выходной символ (y_l * Y) зависит не только от входного символа (x * X), но и от того, в каком состоянии (q_i * Q) находится автомат. Автомат функционирует в дискретном времени; это означает, что элементы описания автомата заданы только в упомянутые выше дискретные моменты.

Представим, что с некоторого начального, например, нулевого момента времени на вход автомата подаются входные символы, образующие входное слово некоторой длины (длина любого i-го слова измеряется числом символов). На выходе получаем выходное слово той же длины (рис. 1а).

Рис. 1а

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

На практике широкое распространение получили две основные модели, описывающие функционирование АА:

1. Модель Мили (которую мы будем рассматривать);

2. Модель Мура.

Канонический метод структурного синтеза

Абстрактный автомат имеет один вход, один выход и конечные алфавиты для входных, выходных символов и символов, кодирующих состояния (мощности этих алфавитов обозначались m, p, n, соответственно). Структурный автомат имеет M входов и P выходов, причем каждый из этих параметров закодирован в структурном (двоичном) алфавите; состояния автомата закодированы двоичными векторами длины N. Значения M, P и N вычисляются исходя из соотношений:

M ≥ log2 * + 1; P ≥ ***2* + 1; N ≥ ***2*+ 1.

Если нумерация элементов алфавитов абстрактного автомата начинается с нуля (соответственно, x₀, y₀, q₀), то удобно использовать равенства:

M =log2 *; P =log2 *; N =***2*.

Существует общий конструктивный прием – канонический метод структурного синтеза, – позволяющий свести задачу построения автомата с памятью к задаче синтеза комбинационных схем (КС) [1]. Этот метод основан на представлении автомата схемами, приведенными на рис. 2 (для автомата Мили)

Рис. 2 Структурный автомат Мили

Каждый из автоматов построен на двух комбинационных схемах – КС1 и КС2, и двоичных элементах памяти, обозначенных через П, число которых равно N. В качестве элементов памяти мы будем далее использовать триггеры; совокупности двоичных значений их выходов (на рисунке это *₁, …, * _N ), образуют двоичные векторы, кодирующие состояния. На основе векторов X (x₁, …, x_M) и Γ (*₁, …, *_N ), поступивших на входы КС1 в момент t дискретного времени, последняя формирует сигналы возбуждения элементов памяти (*₁, …, *_N ), переводящие автомат в новое состояние в момент t + 1. КС2 служит для формирования выходных сигналов на основе векторов X и Γ (для автомата Мили)

Ускоренное умножение

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

С_*=*(*_*₊₁×*_*₊₂×…×*_*₊_*)

получаемых умножением множимого на группу, состоящую из k соседних разрядов множителя (k = 2, 3, . . .). При k = 2 частичные произведения вычисляются следующим образом. Пара разрядов b_i+1b_i+2 множителя может иметь значения 00, 01, 10 и 11. Первым трем наборам соответствуют частичные произведения 0, А и 2А, последнее из которых представляет собой значение A, сдвинутое на 1 разряд влево. Набор 11 можно рассматривать в виде 11 = (100—1) и обрабатывать его в следующем порядке. Значение 100 может быть учтено путем корректировки множителя b₁b₂ ….b_i : = b₁b₂ . . . b_i+1 сводящейся к увеличению значения множителя на единицу 1-го разряда. В таком случае частичное произведение, соответствующее набору 11, будет равно (—А). Заметим, что в результате корректировки n-разрядный множитель может быть преобразован в (п +1)-разрядное число, т. е. количество формируемых и суммируемых частичных произведений будет равно М ≥ (п + 1)/2.

Корректировка множителя путем добавления 1 в разряд, предшествующий обрабатываемой паре цифр b_i+1b_i+2, легко реализуется в ОА с общими микрооперациями. При использовании автоматов с закрепленными микрооперациями выполнение корректировки потребует введения в регистр множителя микрооперации счета, т.е. приведет к значительному увеличению оборудования. Более экономичным является запоминание корректирующего значения d, равного 0 или 1. При обработке первой пары цифр b_п-1b_п имеем d = 0. Последующие пары цифр преобразуются с учетом ранее сформированного значения d. и при этом вычисляется новое значение d.

Прямой код

Пусть - правильная двоичная дробь (положительная или отрицательная). В частном случае равно нулю.

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

Иными словами, если где , то .

Если , то .

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

T-триггеры

T-триггер или триггер со счётным входом предназначен для подсчёта поступающих на вход импульсов. Название триггера берётся от слова Toggle –кувыркаться. Т-триггеры бывают асинхронные и синхронные. В синхронных триггерах имеется вход разрешения счёта или управления. Рассмотрим реализацию асинхронного Т-триггера на двухступенчатом RS-триггере (рисунок).

Асинхронный T-триггер на основе RS-триггера (а), его условное

обозначение (б) и временные диаграммы работы (в)

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

При С=1 первая ступень принимает новое состояние так, что в течение всего

интервала, пока С=1, триггеры оказываются в противоположных состояниях.

При переходе синхросигнала в ноль новое состояние триггера первой ступени

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

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

Таблица переходов Т триггера

T	Q(t)	Q(t+1)
0	0	0
0	1	1
1	0	1
1	1	0

Автомат Мили

Автомат Мили (англ. Mealy machine) — конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы.
Автомат Мили можно описать пятеркой (Q,X,Y,f,g), где Q - множество состояний автомата, X - множество входных символов, Y - множество выходных символов, q=f(Q,X) - функция состояний, y=g(Q,Y) - функция выходных символов.
Кодировка автомата Мили:
Вершина (операторная или логическая), стоящая после вершины "Начало", а также вход вершины "Конец" помечается символом S₁, вершины, стоящие после операторных помечаются символом S_n (n=2,3..).

Диаграмма состояний автомата Мили (Граф автомата)

Алгоритм ускоренного умножения

Алгоритм ускоренного умножения реализуется ОА. Предполагается , что n-четное . При нечетном n доина регистра B должна быть увеличена на один разряд. Функции реализуются комбинационной схемой F. Перед началом операции множимое и мнодитель поступают с шин А(n) и B(n) на регистры A и B. Произведение представляется 2-n разрядным словом :

с=СМ(3:n+3) и выводится по шинам С1 и С2. Операционный автомат реализуется следующий набор микроопераций :

n-1

n+2

n+3

СМ

y₁

y₃

y₂

y₅

y₄

y₈

y₇

y₆

F(3)

р₄

СЧТ

-1

Структура операционной части

Микропрограмма ускоренного умножения

y₁) B:=CM(n+2:n+3).R2(B);

y₂) CM:=0;

y₃) CM:=CM(1).CM(1).R2(CM);

y₄) CM:=CM+A;

y₅) CM:=CM+A.0;

y₆) CM:=CM+(A)обр+1;

y₇) CЧТ:=CЧТ-1;

y₈)CЧТ:=M

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

p₁= F(1);

p₂= F(2);

p₃= F(3);

p₄= (CЧТ=0);

p₅= CM(1);

При выполнении микрооперации y₁ прямой код двух младших разрядов произведения вводится в регистр множителя. В микрооперации сдвига y₃ в освобождающийся разряды сумматора CM y₂ засылается значение знакового разряда , что обеспечивает корректность сдвига как прямого, так и дополнительного кода суммы. Предполагается , что за счет структурных решений выполняемых на уровне логических схем микрооперация y₃ совместима с микрооперацией y₁. Микрооперация устанавливает на счетчике тактов СЧТ значение параметра M≥n/2, где M- ближайшее целое. y₄ в сумматор записывается значение A, y₄ в сумматор записываются значения А₀ , y₆ в сумматор записывается обратное значение A и прибавляется 1 , y₇ присваивается значение счетчику на -1 .

Содержательная граф-схема алгоритма

Начало

СM:=0,

СЧТ:=M

F(1)

F(2)

F(3)

CM:=CM+A

CM:=CM+A.0

CM:=CM+111.(A)обр+1

B:=CM(n+2:n+3).R2(B)

CM:=CM(1).CM(1).R2(CM)

CЧТ:=CЧТ-1

СЧТ=0

CM(1)

CM:=CM+A

Конец

Функциональная граф-схема

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

Начало

Y₁

p₁

p₂

p₃

Y₂

Y₃

Y₄

)обр+1

Y₅

p₄

p₅

Y₂

Конец

y₂y₈=Y₁;

y₄=Y₂;

y₅=Y₃;

y₆=Y₄;

y₁y₃ y₇ =Y₅;

p₁=F(1);

p₂=F(2);

p₃=F(3);

p₄=(СЧТ=0);

p₅=CМ(1);

Отмеченная граф-схема алгоритма

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

- символом «а₁» отмечаются вход вершины следующим за начальным и вход конечной вершины;

-входы всех вершин, следующих за операторным, должны быть отмечены;

-если входы вершин отмечаются, только одним символом;

-входы всех вершин , за исключением конечной, отмечаются различными символами.

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

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

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

Отмеченная граф-схема алгоритма ускоренного умножения

Начало

Y₁

p₁

p₂

p₃

Y₂

Y₃

Y₄

)обр+1

Y₅

p₄

p₅

Y₂

Конец

a₁

a₂

a₃

a₄

a₅

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

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

a₁

a₂

a₃

a₄

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

Кодирование состояния автомата заключается в установлении взаимно-однозначного соответствия между множеством состояний автомата и множеством элемента памяти.

В нашем примере для автомата Мили имеет четыре состояний, следовательно достаточно иметь два триггер, т.е.

*₁==00

*₂= =10

*₃==01

*₄=*₁*₂=11

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

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

Исходное состояние	Код исходного состояния	Состояние перехода	Код состояния перехода	Входные сигналы	Выходные сигналы	Сигналы возбуждения
a₄ a₄ a₄	11 11 11	а₁ а₁ а₁	00 00 00	₄ ₄₅ ₄*₅	-- *2 --	T₁ T₂ T₁ T₂ T₁ T₂
a₁	00	a₂	10	--	Y₁	T₁
a₂ a₂ a₂ a₂	10 10 10 10	a₃ a₃ a₃ a₃	01 01 01 01	₁₂₃ ₁₂ ₁ ₁₂*₃	Y₄ Y₃ Y₂ --	T₁T₂ T₁T₂ T₁T₂ T₁T₂
a₃	01	a₄	11	-	Y₅	T₁

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

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

Производим упрощение системы , получаем:

Заключение

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

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

1) Методические указания к курсовой работе по дисциплине «Информационные основы вычислительных систем»

2) А.П.Жмакин. Архитектура ЭВМ. Уч.пособие. Санкт Петербург, БХВ-Петербург, 2006.

3) Б.Я. Цилькер, С.А., Орлов. Организация ЭВМ и систем: Учебник для вузов. – СПб: Питер,2004.

4) С.К.Ғаниев, М.М.Каримов, Н.М.Мамбетов. "Ҳисоблаш системаларининг информацион асослари: Олий ўқув юрт.талаб. учун дарслик. – Тошкент Давлат техника университети, 2002.

5) А.Я. Савельев. Основы информатики. Учеб. для ВУЗов- М.: Изд-во МГТУ им А.Э. Баумана, 2001.

Содержание

Введение…………………………………………………………………………….3

1)Алгоритм выполнения операции ускоренного умножения………..………9

2) Разработка операционного автоматического устройства, реализующего функцию ускоренного умножения……………………………………………………………………………9

3)Микропрограмма ускоренно умножения…………………………………….10

3)Составление содержательной, функциональной и отмеченной ГСА…………………………………………………………………………………..11

5) Разработка графа автомата и кодирование его состояний…………………………………………………………………….……..15

6)Составление структурной таблицы переходов…………………………………………………………..……………….16

7) Определение функций возбуждения и функций выходов………………………………………………………………………..…….17

8)Построение функциональной схемы автомата ……………………………………………………………………………………..…18

9)Заключение ……………………………………………………………………...19

10) Литература……………………………………………………………………..20