Вопросы
Методика синтеза цифровых автоматов с памятью
Схема ускоренного умножения
Основную задержку в процессе выработки произведения вносит суммирование частичных произведений. Уменьшение их числа сократило бы время суммирования. Этот факт положен в основу модифицированного алгоритма Бута, позволяющего строить схемы ускоренного умножения. Процесс ускоренного умножения по алгоритму Бута сводится к следующему: уменьшению числа частных произведений, входящих в состав общего произведения операндов А и В. Если уменьшение вдвое, то говорят об умножении «сразу на два разряда».
Схема умножения «сразу на два разряда»
Множимое А поступает в этой схеме на ряд преобразований, формирующие все возможные варианты частичных произведений, кроме А и 0, которые не требуют аппаратной реализации. Множитель В поступает на логический преобразователь, который анализирует тройки разрядов, декодирует их и даёт мультиплексорам сигналы выбора того или иного варианта частичных произведений. Окончательный результат получается суммированием произведений с учётом сдвига по разрядной сетке 4х4 разрядностью.
|
|
Приведенные выше примеры касались операций с прямыми кодами. В этом случае умножение знакопеременных чисел свёдется только к выработке знакового разряда, как суммы по модулю 2 знаковых разрядов множителей. Если же числа представлены не прямыми кодами, то рассмотренные выше умножители можно дополнить преобразователями дополнительного кода в прямые на выходах и преобразователями прямого кода в дополнительный на выходах.
10042012 Лекция 11
1.Понятие ЦА с памятью
2.Способ задания ЦАсП
3.Элементарные ЦА с памятью
4.Канонический метод синтеза ЦА с памятью
АП – цифровой узел или устройство, содержащее в своём составе элементы памяти (ЭП). Совокупность состояний всех элементов памяти определяет состояние АП.
Под воздействием входных сигналов АП выдаёт выходные сигналы и переходит из одного состояние в другое, которые хранится в интервале между сигналами.
Математической моделью АП является абстрактный автомат, который задается множеством из 6 элементов:
A= {V, W, S, δ, λ, s0}
V – множество входных сигналов (входной алфавит)
W – множество выходных сигналов
S – множество внутренних состояний
δ – функции переходов
λ – функции выходов
s0 – начальное состояние АП
Если первые три множества конечны, то АП – конечный.
Функционирование автомата рассматривается в дискретные моменты времени. При этом функции переходов определяют состояние автомата в момент времени t+1 в зависимости от состояния автомата и значение входного сигнала в момент времени t, то есть выражение 1:
|
|
s(t+1)=δ[s(t), v(t)]
Функция выходов определяет зависимость выходного сигнала автомата от состояния автомата и входного сигнала в момент времени t, то есть выражение 2:
w(t)=λ[s(t), v(t)]
Если функции, описанные в выражениях 1 и 2, определенны на всех значениях, то такие автоматы называют полными или полностью определёнными.
Если функции переходов и выходов определены не на всех значениях s(t) и v(t), то АП называют частичными или неполностью определёнными.
Работа конечного автомата состоит в следующем: в начальный момент времени t0=0 автомат находится в состоянии s0. Затем в дискретные моменты времени 0, 1, 2, …, t, t+1, … на его вход подаются входные сигналы (тоже дискретные) v(0), v(1), …, v(t), v(t+1),... В соответствии с выражением 2 автомат формирует выходные сигналы, а в соответствии с выражением 1 переходит, начиная с s0, переход в нужные состояния. Внутри интервалов значения (t, t+1) состояния не меняются.
В настоящее время различают несколько обобщенных структур конечных автоматов, среди которых наибольшее распространение получили автоматы Мили и Мура.
Закон функционирования автомата Мили задаётся уравнением:
s(t+1) = δ[s(t), v(t)]
w(t) = λ[s(t), v(t)]
А автомата Мура:
s(t+1) = δ[s(t), v(t)]
w(t) = λ[s(t)]
Из этих уравнений видно, что у Мура выходные значения зависит только от исходного состояния.
Вопрос 2. Способы задания АП
Задание конечного АП состоит в описании элементов множества А одним из трёх способов: табличным, графическим и матричным.
2.1.Табличный способ
При табличном способе автомата Мили функции переходов и выходов описываются таблицами переходов и выходов соответственно или совмещенными таблицами переходов и выходов.
Пример 1
V={v1, v2} S={s0, s1, s2, s3} W={w0, w1, w2}
Состояния/ Входной сигнал | s0 | s1 | s2 | s3 |
v1 | s1/w1 | s2/w2 | s3/w3 | s0/w3 |
v2 | s0/w2 | s1/w3 | s2/w1 | s3/w3 |
Используя таблицу, рассмотрим работы АП. последовательно входные сигналы v1v2v2v1v2v2. На выходе автомата появится выходные сигналы w1w2w3w2w1w1 и автомат будет переходить в состояния s0s1s1s1s2s2s2.
Порядок функционирования АП:
1. Начиная с t=0 на вход конечного автомата, установленного в состояние s0, поступают последовательно входные сигналы.
2. Тогда под действием i-ого сигнала на выходе автомата появится выходной сигнал wi=λ(si-1, vi), а сам автомат перейдёт в состояние si=δ(si-1, vi).
При табличном способе задания автомата Мура используется одна таблица переходов, в которой каждому столбцу, кроме состояния, задаётся выходной сигнал.
Состояния/ Входной сигнал | w1, s0 | w2, s1 | w2, s2 | w1, s3 |
v1 | s1 | s2 | s3 | s0 |
v2 | s2 | s3 | s1 | s3 |
На практике часто условия функционирования ЦАП может быть задано совмещенной таблицейпереходов-выходов с линейной структурой. Каждый переход определяется одной его строкой.
Автомат Мили
Исходное состояние (t) | Входной сигнал (t) | Состояние перехода (t+1) | Выходной сигнал (t) | |
s0 | v1 | s1 | w1 | |
s0 | v2 | s0 | w2 | |
s1 | v1 | s2 | w2 | |
s1 | v2 | s1 | w3 | |
s2 | v1 | s3 | w3 | |
s2 | v2 | s2 | w1 | |
s3 | v1 | s0 | w3 | |
s3 | v2 | s3 | w3 |
2.2.Графический способ
Наиболее наглядный. Автомат передается направленным графом. Вершины графа указывают состояние автомата, ветви – переходы (отображают входные сигналы, участвующие в переходе).
2.3.Матричный способ
Автомат Мили задаётся квадратной матрицей М, строки которой соответствуют исходным состояниям, а столбцы – состояниям перехода. В узлах – входной сигнал и выходной сигнал. Если не возможен переход – прочерк.
M =
Автомат Мура задаётся матрицей, в узлах которых находятся только значения входного сигнала, а выходной сигнал описывается векторами выходов.
W =; M=