Вопрос 1. Понятие ЦА с памятью

Вопросы

Методика синтеза цифровых автоматов с памятью

Схема ускоренного умножения

Основную задержку в процессе выработки произведения вносит суммирование частичных произведений. Уменьшение их числа сократило бы время суммирования. Этот факт положен в основу модифицированного алгоритма Бута, позволяющего строить схемы ускоренного умножения. Процесс ускоренного умножения по алгоритму Бута сводится к следующему: уменьшению числа частных произведений, входящих в состав общего произведения операндов А и В. Если уменьшение вдвое, то говорят об умножении «сразу на два разряда».

Схема умножения «сразу на два разряда»

Множимое А поступает в этой схеме на ряд преобразований, формирующие все возможные варианты частичных произведений, кроме А и 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), то АП называют частичными или неполностью определёнными.

Работа конечного автомата состоит в следующем: в начальный момент времени t₀=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-ого сигнала на выходе автомата появится выходной сигнал w_i=λ(s_i-1, v_i), а сам автомат перейдёт в состояние s_i=δ(s_i-1, v_i).

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

Состояния/ Входной сигнал	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=