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

Автор: Пользователь скрыл имя, 11 Марта 2012 в 17:54, курсовая работа

Краткое описание

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

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

Файлы: 1 файл

Курсовая 2.docx

— 433.40 Кб (Скачать)

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

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

 

Аннотация

 

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

 

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

 

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

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

S = {X, Q, Y, δ, λ, q1}

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

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

X = {x1, ... , xm};

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

Q = {q1, ... , qn};

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

Y = {y1, ... , yp};

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

qj = δ(qi, xk),

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

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

yl = λ (qi, xk);

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

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


 

 

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

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

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

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


 

 

Рис. 1а

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

 

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

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

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

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

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

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

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

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

 

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

 

 

 

 

 

 

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

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


 

 

 


 

 

 

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

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

С*=*(**+1×**+2×…×**+*)

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

Корректировка множителя  путем добавления 1 в разряд, предшествующий обрабатываемой паре цифр bi+1bi+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) - функция выходных символов. 
Кодировка автомата Мили: 
Вершина (операторная или логическая), стоящая после вершины "Начало", а также вход вершины "Конец" помечается символом S1, вершины, стоящие после операторных помечаются символом Sn (n=2,3..).


 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

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

 

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

 

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

 

1


3


F



d


C2



n-1


2


B



2


n


1


n





n+2


n+3



2


n+3


1


СМ


3


2



y1


y3


y2



y5


y4



1


y8


y7


y6


1


n


А




F(3)


C1


B


р4


СЧТ


А



-1


m


1



 

 

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

 

 

 

 

 

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

 

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

y2) CM:=0;

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

y4) CM:=CM+A;

y5) CM:=CM+A.0;

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

y7) CЧТ:=CЧТ-1;

y8)CЧТ:=M

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

p1= F(1);

p2= F(2);

p3= F(3);

p4= (CЧТ=0);

p5= CM(1);

При выполнении микрооперации  y1 прямой код двух младших разрядов произведения вводится в регистр множителя. В микрооперации сдвига y3 в освобождающийся разряды сумматора CM y2 засылается значение знакового разряда , что обеспечивает корректность сдвига как прямого, так и дополнительного кода суммы. Предполагается , что за счет структурных решений выполняемых на уровне логических схем микрооперация y совместима с микрооперацией y1. Микрооперация устанавливает на счетчике тактов СЧТ значение параметра M≥n/2, где M- ближайшее целое. y4 в сумматор записывается значение A, y4 в сумматор записываются значения А0 , y6 в сумматор записывается обратное значение A  и прибавляется 1 , y7 присваивается значение счетчику на -1 .

 

 

 

 

 

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

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

Конец

1

1

1

1


 

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