Теоретические основы вычислительной техники 5 страница

Проведём тестирование построенной схемы на наборе аргументов А=1, В=0, С=1. Этому набору должны соответствовать значения S=0 и Р=1. Проставленные логические значения на входах и выходах элементов схемы показывают работоспособность схемы (на данном наборе).

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

Задание 75. Реализовать рассмотренную схему только на двухвходовых элементах «и-не» и, проведя сравнение полученной реализации со схемой, определить выигрыш (проигрыш) в количестве элементов схемы и её быстродействии.

Задание 76. Используя условия задания 70 синтезировать двухвыходную комбинационную схему методом последовательного наращивания.

Задание 77 Используя условия задания 71 синтезировать двухвыходную комбинационную схему методом последовательного наращивания.

1.5. Синтез и анализ конечных автоматов.

Определение. Если совокупность выходных сигналов (выходного слова) Y(t) зависит, как от совокупности входных сигналов (входного слова) X(t), так и от внутренних состояний S(t-1), то такой преобразователь информации называется конечным автоматом (автоматом с памятью).

Для описания функционирования конечного автомата (КА) задаются:

- множество входных дискретных сигналов, ;

Y(t)={y₁,…,y_j,…,y_m} – множество выходных дискретных сигналов, ;

S(t)={s₁,…,s_k,…s_r} – множество внутренних дискретных состояний, ;

s₀ – начальное состояние автомата;

FP – функция переходов, позволяющая определить новое внутреннее состояние автомата, если известно предыдущее внутреннее состояние и состояние входных сигналов в данных момент времени S(t+1)=FP[S(t),X(t)];

FV – функция выходов, позволяющая определить состояние выходных сигналов автомата, если известно внутреннее состояние и состояние входных сигналов Y(t)=FV[S(t),X(t)].

Таким образом, функционирования КА можно представить так:

S(t+1)=FP[S(t),X(t)],

Y(t)=FV[S(t),X(t)], где t=0,1,2…

S(t=0)=s₀

Автомат Мили

или так:

S(t+1)=FP[S(t),X(t)],

Y(t)=FV[S(t)], где t=0,1,2…

S(t=0)=s₀

Автомат Мура

Конечные автоматы делятся на 2 части:

Абстрактную – описание полноты FV, X, Y, S автомата, работоспособности

Структурную – отвечает на вопрос как построить КА.

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

таблицы состояний:

совмещённая таблица
	s0(t)	s1(t)	…
x1(t)			…
x2(t)			…
…	…	…	…
(фрагмент)

Задание КА графом (соответствует содержимому таблиц состояний).

Различают два основных типа КА: автомат Мили м автомат Мура. Различие между ними заключается в том, что в автомате Мура состояние выходных сигналов не зависит от состояния входных сигналов, а определяется лишь внутренним состоянием, т. е. Y(t)=FV[S(t)].

Структурная схема КА.

или несколько подробнее

КС – комбинационная схема,

БП – блок памяти,

БФВС – блок формирования выходных сигналов (комбинационная схема, реализующая FV),

БВЭА – блок возбуждения элементарных автоматов (комбинационная схема, реализующая FP),

БЭА – блок элементарных автоматов (память КА),

q – функция возбуждения.

1.5.1. Элементарные конечные автоматы и их техническая реализация.

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

Для построения памяти КА используются, в основном, четыре типа ЭА: два типа одновходовых и два двухвходовых.

Одновходовые ЭА:

Q₁(t+1)=q(t) – ЭА D-типа,

- ЭА T-типа.

Двухвходовые ЭА:

- ЭА RS-типа,

- ЭА JK-типа.

Техническая реализация ЭА:

q₁(t)=q_S(t), q₁(t)=q_J(t), q₀(t)=q_R(t), q₀(t)=q_K(t).

1.5.2. Алгоритм структурного синтеза конечного автомата.

1. Задать закон функционирования конечного автомата.

2. Определить n – требуемое количество ЭА. n=ù log₂(r+1) é , где r+1 – количество внутренних состояний ЭА, ù … é - ближайшее большее целое.

	тип ЭА
D	T	RS	JK
qD(t)	qT(t)	qS(t)	qR(t)	qJ(t)	qK(t)
			-	-	- -	- -

3. Выбрать тип ЭА по таблице. Для этого предварительно построить таблицу для требуемой функции возбуждения.

4. Построить функциональную схему БЭА.

5. Провести синтез комбинационной схемы БВЭА.

6. Провести синтез комбинационной схемы БФВС.

7. Составить из БЭА, БВЭА и БФВС схему конечного автомата.

8. Провести тестирование полученной схемы на соответствие закону функционирования.

1.5.3. Пример синтеза конечного автомата – двоично-десятичного счётчика.

Пример. Синтезировать схему двоично-десятичного счётчика.

Зададим закон функционирования двоично-десятичного счётчика. Этот КА имеет 10 внутренних состояний:

Так как n=ù log₂10 é=4, то для запоминания всех 10 состояний КА потребуется четыре ЭА.

Выберем Тим ЭА. Пусть это будет ЭА Т-типа. Тогда структурная схема синтезируемого КА будет иметь вид:

Выполним синтез БВЭА. Построим либо совмещённую таблицу состояний, либо диаграмму состояний:

Над дробью в диаграмме ничего нет, т. к. входные сигналы отсутствуют в данной схеме. Под дробью значение выхода С.

Построим карты Карно для выходных сигналов БВЭА (т. е. для сигналов q₀, q₁, q_2­, q₃).

Проведём синтез БФВС. Построим карту Карно для выходных сигналов комбинационной схемы БФВС. (т. е. для сигнала С).

С=Q₃Q₀.

Составим из БЭА, БВЭА и БФВС схему конечного автомата:

Вспомним соответствие с общей структурой КА:

Проверим работоспособность схемы на примере перехода из состояния 9 в 0 и формирования С. В этом состоянии Q₃=1, Q₂=0, Q₁=0, Q₀=1 (см. 1 и 0 в схеме). При этом сформируются сигналы возбуждения: q₃=1, q₂=0, q₁=0, q₀=1 и, следовательно, следующим состоянием КА будет: Q₃=Q₂=Q₁=Q₀=0 и С=1, что соответствует правильной работе двоично-десятичного счётчика.

Задание 78. Синтезировать схему КА, который, при подаче на вход счётных импульсов, переходит последовательно в состояния в соответствии с рисунком.

Задание 79. Синтезировать схему КА, который на входные счётные импульсы последовательно формирует на выходах двоичные коды, соответствующие числам 0, 2, 4, 5, 7, 9. В качестве ЭА выбрать Т-триггеры.

Задание 80. Синтезировать схему КА в соответствии с заданием №79, но с использованием в качестве ЭА RS-триггеров.

2. Организация ЭВМ.

2.1. Типовые структурные элементы цифровой техники.

2.1.1. Основные характеристики и классификация цифровых элементов вычислительной техники.

Типовыми структурными элементами называются наименьшие функциональные части из которых состоят устройства цифровой техники.

Это:

- элементы реализующие логические функции,

- элементы преобразующие информацию,

- элементы запоминающие информацию,

- вспомогательные элементы (генерирующие, формирующие и усиливающие сигналы).

По способу представления информации структурные элементы делятся на:

- импульсные («0» - отсутствие импульса напряжения, «1» - наличие импульса напряжения)

- потенциальные («0» - один уровень напряжения, «1» - другой уровень напряжения)

Условные обозначения схем.

0123456 – номера элементов обозначения

0 – буква «К» или « »

1+2 – обозначение серии

3 – буква, указывающая на функциональный класс

4 – буква, указывающая на группу данного функционального класса

5 – число, указывающее номер разработки данной микросхемы в серии

6 – буква, цветная точка или др. – маркировка по разбросу параметров, предельным эксплутационным режимам и другим признакам, вызванным отклонением технологического процесса.

Микросхема дана в технических условиях на серию.

К – широкое потребление

серия – ряд функционально различных микросхем объединённых по технологии, параметрам, конструктивному оформлению.

Обозначение серии:

1 элемент – цифра, указывающая на технологический признак

1, 5, 7 – полупроводниковые микросхемы

2, 4, 6 – гибридные микросхемы

3 – плёночные микросхемы

например:

К155ЛАЗ

2.1.2. Мультиплексоры и дешифраторы.

I. Мультиплексор – схема, передающая сигналы с одной из нескольких входных линий в выходную линию

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

Реализация логических функций на мультиплексорах. (любых КС).

Пусть задана функция трёх переменных на мультиплексорах. Составим ТИ.

Для функции 4-х переменных:

Для функции 5-ти переменных:

II. Дешифратор – КС преобразующая код, подаваемый на входы, в сигнал на одном из выходов.

n – входов, 2ⁿ – выходов

функциональное обозначение

Следовательно:

Прямоугольные дешифраторы:

1 ступень – 2 линейных дешифратора

2 ступень – матричная схема

Синтез матричного дешифратора при n=4, n⁴=16 выходов.

Пример 3-х ступенчатого матричного дешифратора при n=8:

плюс – меньше аппаратуры

минус – быстродействие

Пирамидальные дешифраторы:

элемент i-ой ступени нагружен

только на 2 элемента i+1-ой ступени

Промежуточное значение между

линейным и матричным.

2.1.3. Сумматоры.

- КС для выполнения арифметических и логических операций над числами

Замечание: операция сложения в ЭВМ сложнее операции суммирования, т. к. учитывает: знаки чисел, выравниваются порядки, проводится нормализация и др.

одноразрядные или многоразрядные.

суммирование: последовательное, параллельное, параллельно последовательное (по группам).

I. Сложение многоразрядных чисел.

Последовательный сумматор:

слова А и В поступают с младших разрядов

- элемент задержки на 1 такт

Параллельный сумматор:

Параллельно последовательный сумматор:

Пример:

в 155 серии

полный 2-х разрядный параллельный сумматор

(реализация многоразрядного сумматора на ИМ1)

2.1.4. Триггеры.

Это КА с двумя устойчивыми состояниями. Хранит 1 бит

- регенеративная схема (собственно триггер)

- схема управления

Триггер RS-типа

CRS-триггер

(синхронизируемый RS-триггер).

S и R – информационные входы, С – вход синхронизации (clock – времязадающий)

D-триггер (“delay” – задержка)

Исключается возможность одновременной подачи 2-х единиц на S и R входы.

Нет запрещённых состояний.

Двухтактный RS-триггер.

триггер состоит из двух RS-триггеров и инвертора.

Т-триггер (счётный)

JK-триггер

Тоже на базе двухтактного (универсален)

С	J	K	Q(t+1)
			Q(t)
	Q(t)

2.1.5. Регистры и счётчики.

I. Регистры.

КА предназначенный для записи, хранения и считывания слов.

Кроме того можно:

- сдвиг слова влево или вправо на требуемое число разрядов;