Ускоренное умножение в прямом коде автомата Мили с использование 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 и Γ (для автомата Мили)

 

 

 

 

 

 

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

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

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

получаемых умножением множимого  на группу, состоящую из 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. Операционный автомат реализуется следующий набор микроопераций :

 

1

3

F

d

C2

n-1

2

B

2

n

1

n

n+2

n+3

2

n+3

1

СМ

3

2

y₁

y₃

y₂

y₅

y₄

1

y₈

y₇

y₆

1

n

А

F(3)

C1

B

р₄

СЧТ

А

-1

m

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 .

 

 

 

 

 

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

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