Дополнительная литература: 4[67:70, 87:89], 7[278:306].

Контрольные вопросы:

1.Сформулируйте правила склеивания и поглощения.

2.Сформулируйте правило построения диаграммы Вейча-Карно для

представления ФАЛ, зависящей от n−переменных.

3.Дайте определение n−мерного единичного куба.

4.Назовите основные этапы минимизация ФАЛ методом Квайна-Мак-Класски.

5.Сформулируйте правило нахождения первичных импликант.

Тема 9.

Анализ и синтез комбинационных логических схем.

Любое ЦУ можно рассматривать в виде устройства, имеющем п−входов и m−выходов. При m=1 устройство является одновыходной схемой, в противном случае − многовыходной.

На вход устройства поступают входные слова, составленные из символов входного алфавита Х={х1, х2, ... , хп }, на выходе − выходные слова, составленные из символов выходного алфавита У={у1, у2, ... , уm } . При n входах и m выходах длина входного слова − n, длина выходного слова − m. Общее число различных входных и выходных сигналов конечно в виду конечности алфавитов и конечности входных и выходных слов.

Если работа устройства в момент времени ti полностью определяется входным словом, поступившим в момент времени ti, то устройство называется комбинационной схемой или конечным автоматом без памяти.

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

При этом моделью одновыходной схемы является булевское уравнение у= f(х1, х2, ... , хп ), а моделью многовыходной схемы является система булевских уравнений:

у1 = f1(х1, х2,..., хi,..., хп );

. . . . . . . . . . . . . . . . . . .

уj = fj(х1, х2, ... , хi,..., хп );

. . . . . . . . . . . . . . . . . . .

уm =fm(х1, х2, ... , хi,..., хп ).

При проектировании комбинационных схем приходится решать задачи их синтеза и анализа.

Этапы синтеза комбинационных схем:

1)по физическому описанию составляется математическое описание (система булевских уравнений);

2)по математическому описанию составляют функциональную схему, предварительно решая задачу минимизации;

3)по функциональной схеме составляют принципиальную схему.

46

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

Таким образом, решая задачу синтеза комбинационной схемы, решают задачу реализации булевых функций. Основой для реализации булевых функций являются логические элементы. В настоящее время созданы логические элементы, которые реализуют все основные элементарные функции алгебры логики. Функция дизъюнкции реализуется элементом ИЛИ, функция конъюнкции − элементом И, функция инверсии − элементом НЕ, функция Шеффера − элементом И−НЕ, функция Вебба − элементом ИЛИ−НЕ. Булевы переменные и функции представляют собой значения сигналов входов и выходов логических элементов. Существуют элементы, выполняющие сложные логические функии. Например, элемент И−ИЛИ−НЕ реализует функцию f = x1 x2 x3 x4. Ниже представлены основные логические элементы (рис.9):

а) элемент ИЛИ (дизъюнктор);

б) элемент И (конъюнктор);

в) элемент НЕ (инвертор);

г) элемент И-НЕ;

д) элемент ИЛИ-НЕ.

а)

б)

в)

X1

&

f= x1&x2

X1

1

f = x1 x2

X

1

f =

X2

X2

x

г)						д)
	X1	&				X1	1	x2
	X2			f = x1	& x2	X2	f = x1

Рисунок 9. Основные логические элементы

Отдельные логические элементы можно соединять в схемы. Соединенные согласно булевскому выражению, они являются логической схемой (переключательной схемой), в которой выход полностью определен значениями сигналов на входе, т.е. комбинационной схемой. При синтезе комбинационных схем необходимо иметь функционально полный набор логических элементов. Набор логических элементов является функционально полным, если он реализует функционально полную систему ФАЛ.

Под системой логических элементов D понимается некоторое множество логических элементов, реализующих элементарные булевы операции на основе физических явлений. При этом подразумевается, что число различных типов элементов из D ограничено, но не ограничено число элементов каждого типа. Система элементов D характеризуется конечным набором логических операций, определяющих типы элементов (базис системы), коэффициентом объединения по входу I, коэффициентом разветвления по выходу U и задержкой сигнала на элементе Δτ.

Если в качестве системы булевых функций, реализуемой логическими

47

элементами, выбраны { , , }, то говорят, что реализован булев базис. Проектирование схем в булевом базисе осуществляется наиболее просто, т.к. методы минимизации в основном ориентированы на булев базис. Если в системе логических элементов реализованы функции Шеффера, Пирса (И−НЕ, ИЛИ−НЕ), то реализован одноэлементный базис (универсальный).

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

Ниже рассмотрен пример синтеза одноразрядного сумматора. Одноразрядный комбинационный сумматор представляет собой схему с тремя входами и двумя выходами (рис.10). Булевы функции Si и Pi-1 можно задать таблично (табл.7).

pi−1 =ai bi pi aibi pi aibi pi aibi pi =bi pi ai pi aibi Si =ai bi pi aibi pi aibi pi aibi pi

Таблица 7

аi	bi	p1	pi-1	Si
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1
		ai	bi pi

1	ai
1	bi
1	pi
	&	1
		pi-1
	&
	&
	&	1
		Si
	&
	&
	&

Рисунок 10. Схема в базисе И, ИЛИ, НЕ

48

Три входа для приема i-го разряда исходных чисел (ai и bi) и сигнала переноса из соседнего младшего разряда сумматора в данный разряд (pi-1). На двух выходах одноразрядного сумматора формируются i - ый разряд суммы (Si) и сигнал переноса в соседний старший разряд (Pi).

Основная литература: 1[220:230], 2[11:13]. Дополнительная литература: 4[70:78], 5[43:44], 7[222:237].

Контрольные вопросы:

1.Дайте определение логического элемента.

2.Приведите обозначения основных логических элементов.

3.Дайте определение комбинационной схемы.

4.Что собой представляют модели комбинационных схем?

5.В чем заключаются задачи анализа и синтеза комбинационных схем?

Тема 10.

Математические модели цифровых устройств с памятью. Абстрактный автомат.

В большинстве случаев работа определяется не только входным словом в момент времени ti, но и зависит также от входных слов, поступивших в предыдущие моменты времени. В этом случае имеют дело с устройством с памятью (часто называют просто конечный автомат). Конечные автоматы являются матаматическими моделями дискретных устройств и изучаются в теории автоматов. Общая теория автоматов делится на абстрактную и структурную теории автоматов.

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

Структурная теория автоматов интересуется, прежде всего его структурой, структурой входных и выходных сигналов, рассматривает схемную реализацию автомата.

Для абстрактного конечного автомата определены конечные алфавиты: входной алфавит X={x1, x2,…, xF}, выходной алфавит Y={y1, y2,…, yG} и алфавит состояний A={a1, a2,…, aM}. Число входных сигналов конечно и они рассматриваются как причина перехода из одного состояния в другое a(t- 1)→a(t). Число выходных сигналов конечно и каждому отличному от нуля моменту автоматного времени соответствует выходной сигнал y(t). Выходной сигнал y(t) может появиться во времени только после входного сигнала x(t), соответствующего этому же моменту времени, в момент перехода из состояния a(t-1) в a(t) или после перехода. В первом случае y(t) однозначно определяется парой a(t-1) и x(t). Во втором случае y(t) определяется только a(t). Для любого данного автомата всегда имеет место одна из двух возможностей. Поэтому различают автоматы 1 рода (автоматы Мили) и 2 рода (автоматы Мура). Абстрактные автоматы являются математическими моделями реальных физических устройств и задаются в виде совокупности шестёрки объектов: конечного множества X входных сигналов (входной алфавит); конечного множества Y выходных сигналов (выходной алфавит); множества A,

49

называемого множеством состояний автомата; a0 A (начальное состояние автомата) и двух функций: δ(a,x) и λ(a,x), задающих однозначные отображения множества пар (a,x), где a A и x X, во множества A и Y. Функция δ(a,x) называется функцией переходов автомата, а функция λ(a,x) – функцией выходов. Если автомат задан функцией выходов, то это автомат 1 рода (Мили), сдвинутой функцией выходов – 2 рода (Мура).

Для автомата 1-го рода a(t) = δ (a (t-1), x(t)); y(t) = λ (a (t-1), x(t)).

Для автомата 2-го рода a(t) = δ (a (t-1), x(t)); y(t)= λ (a(t), x(t)) = λ (a(t)).

Для задания автоматов могут использоваться два типа языков: начальные и стандартные (автоматные языки). В стандартных языках задания автоматов функции выходов и перехода задаются в явном виде. В начальных языках эти функции в явном виде не задаются и поэтому они называются языками описания цифровых автоматов.

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

При табличном способе задания автомата Мили описание работы автомата задаётся таблицей переходов и выходов, в которых строки обозначаются входными сигналами xf (f=1,2,…,F), а столбцы – состояниями am (m=1,2,…,M). На пересечении f-й строки и m-го столбца в таблице переходов записывается функция переходов δ(am,xf)=as, в таблице выходов − функция выходов λ(am,xf)=yg (g=1,2,…,G). Для задания автомата Мили необходимо задать ещё начальное условие a0 A (обычно a0=a1).

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

При графическом способе задания автоматов, описание работы автомата задаётся в виде ориентированного связного графа, вершины которого соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины am и as графа автомата связаны между собой дугой, направленной от am к as, если в автомате имеется переход от состояния am к состоянию as, т.е. если δ (am, xf) = as при некотором xf X. Дуге (am,as) графа автомата Мили приписывается входной сигнал xf и выходной сигнал yg, если он определён, в противном случае ставится прочерк. Граф автомата Мура отличается от графа автомата Мили тем, что выходной сигнал yg приписан вершине графа.

Существуют неполностью определенные автоматы (частичные), в которых функции переходов и выходов заданы не для всех пар (a,x).

Автоматы реализуют отображения входных слов в выходные слова. Два абстрактных автомата с одинаковыми входными и выходными алфавитами называются эквивалентными, если они реализуют одинаковые алфавитные отображения X в Y (X→Y). Из этого определения видно, что автомат Мура и автомат Мили могут быть эквивалентны, если удовлетворяются условия, указанные

50

в определении эквивалентных автоматов. Переход от автомата Мура к эквивалентному автомату Мили и от автомата Мили к эквивалентному автомату Мура называется взаимной транспозицией автоматов.

Транспозиция автомата Мура в автомат Мили заключается в определении по заданной шестёрке объектов автомата Мура шестёрки объектов эквивалент-

ного ему автомата Мили. Задан автомат Мура SA = {XA, YA, AA, δA, λA,a0A}, где XA – входной алфавит, YA – выходной алфавит, AA − алфавит состояний, δA

– функция переходов, λA – функция выходов, a0A – начальное состояние автомата Мура (a0 AA). Требуется построить автомат Мили: SB = {XB, YB, AB, δB, λB, a0}, где XB – входной алфавит, YB – выходной алфавит, AB – алфавит состояний, δB – функция переходов, λB – функция выходов, a0B – начальное состояние ав-

томата Мили (a0B AB).

В эквивалентных автоматах входные и выходные алфавиты одинаковы, т.е. XB=XА, YB=YА. Можно допустить, что и алфавиты состояний равны:

AB=AА.

Равенство алфавитов состояний приводит к равенству начальных состояний автоматов a0В= a0А. Исходя из равенства входных алфавитов X и алфавитов состояний A, можно приравнять функции переходов δА =δB, так как функция переходов отображает пару (a,x) в a(a A, x X). Функция выходов

автомата Мура λA(as) = yg(as AA, yg YA).

Так как AB = AA , YB = YA , XB = XA , то в автомате Мили функция

выходов λB(am,xf) = yg(am AB, xf XB, yg YB), если в автомате Мура δА (am,xf)

=as и λА(as)=yg .

Переход от автомата Мура к эквивалентному автомату Мили заключается в том, что буква выходного алфавита yg, вырабатываемая автоматом Мура после некоторого перехода из состояния am в состояние as под воздействием буквы входного алфавита xf, должна в автомате Мили вырабатываться во время этого перехода (из am в as). Если таких переходов в состояние as несколько (из am1 под воздействием xf1, из am2 под воздействием xf2 и т. д.), то буква yg YB должна появляться при каждом таком переходе.

При графическом способе задания переход от автомата Мура к эквивалентному автомату Мили заключается в переносе выходной буквы yg, приписанной состоянию as автомата Мура, на все дуги, входящие в это состояние as.

При табличном способе задания таблица переходов автомата Мили δВ (a, x) совпадает с таблицей переходов автомата Мура δА (a, x), а таблица выходов λB(a, x) получается из таблицы переходов заменой символа as, стоящего на пересечении строки xf и столбца am, символом yg, отмечающего столбец as в таблице переходов δА (a, x).

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

51

Существование эквивалентных автоматов делает возможным решение задачи минимизации внутренних состояний автомата. В основе алгоритма минимизации полностью определённых автоматов Мили лежит идея разбиения всех состояний исходного абстрактного автомата на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Получающийся минимальный автомат будет иметь столько внутренних состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата. В один класс эквивалентности объединяются эквивалентные (неразличимые) состояния. Состояния am и as являются эквивалентными (am ≡ as), если реакция автомата в состоянии am совпадает с реакцией в состоянии as на всевозможные входные слова. В этом случае можно считать одно из этих состояний избыточным, т.к. состояние am можно заменить на состояние as или наоборот, а реакция автомата на всевозможные входные слова не изменится. Более слабой эквивалентностью является k − эквивалентность. Состояния am и as k − эквивалентны, если реакция автомата в состоянии am совпадает с реакцией автомата в состоянии as на всевозможные входные слова длины k.

Для определения эквивалентности состояний необходимо начать с определения слабой эквивалентности: 1–эквивалентности, 2–квивалентности, и т. д.

Два состояния абстрактного автомата являются 1 – эквивалентными в том случае, если автомат, находясь в любом из них, при подаче всякого входного сигнала выдаёт один и тот же выходной сигнал. Объединение всех 1 – эквивалентных состояний образует 1 − класс эквивалентности. Разбиение на классы 1 − эквивалентных состояний будет в дальнейшем обозначаться π1.

Два 1 − эквивалентных состояния называются 2 − эквивалентными, если они переводятся любым входным сигналом также в 1 − эквивалентные состояния. Объединение всех 2 − эквивалентных состояний образуют 2 − класс эквивалентности. Разбиение на классы 2 − эквивалентных состояний обозначается π2.

Эти определения можно распространить до k–эквивалентных состояний и до k − классов эквивалентности (разбиение πk). Признаком достижения разбиения на классы эквивалентных состояний является выполнение условия, которое формулируется теоремой, доказываемой в курсе высшей алгебры: если для некоторого k разбиение состояний автомата на (k+1) − классы эквивалентности совпадает с разбиением на k − классы эквивалентности, то оно является разбиением и на классы эквивалентных состояний. Существенным является тот факт, что разбиение множества состояний автомата на классы эквивалентных состояний может быть получено за конечное число шагов.

Основная литература: 1[244:248], 2[14:20, 27:31], 3[12:27,49:52].

Дополнительная литература: 7[36:150]. Контрольные вопросы:

1.Дайте определение конечного автомата.

2.Дайте определение абстрактного автомата.

52

3.Перечислите объекты, с помощью которых задается абстрактный автомат.

4.Дайте определение неполностью определенного автомата.

5.Назовите классы языков для задания автоматных отображений.

Тема 11.

Структурный автомат.

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

При синтезе структурного автомата необходимо выполнить переход от абстрактного автомата к структурному автомату. При этом решаются две основные задачи: кодирование входного X и выходного Y алфавитов, алфавита состояний A; определение системы логических функций возбуждения Ur и выходов Wn, которая является математической моделью комбинационной схемы автомата.

Для абстрактного автомата задаётся входной алфавит X={x1, x2, … , xF} и выходной алфавит Y={y1, y2, … , yG}, а также алфавит состояний A={a1, a2, … , aM}.

Каждый входной сигнал xf X кодируется вектором (ef1, … efp, … , efP), где efp {0,1}, P ≥ ]log2F[. Каждый выходной сигнал yg Y кодируется вектором

(eg1, egn,, …, egN), где egn {0,1}, N ≥ ]log2G[. Каждое состояние am A кодируется

вектором (em1, emr,… , emR), где emr {0,1}, R ≥ ]log2M[.

Удобно структурный автомат представить в виде двух частей: памяти и

комбинационной схемы (см. рис.11), где T1,T2,…,TR		- элементарные автоматы
памяти (хранение состояний), V1,V2,…,VR	-	сигналы обратной связи

(информация о состояниях), U1,U2,…,UN – сигналы для переключения автомата из одного состояния в другое (функции возбуждения памяти).

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

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

Автомат Мура обладает полнотой, если он обладает полнотой переходов и выходов.

53

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

Полнота переходов автомата Мура означает, что для любой пары состояний (bm,bs) найдётся входной сигнал qf, который переведёт автомат из состояния bm в состояние bs, т.е. в каждом столбце должны встречаться все состояния автомата. Полнота выходов автомата Мура означает, что каждое состояние отмечено своим, отличным от других, выходным сигналом di. В таком случае число выходных сигналов равно числу состояний автомата Мура. Следовательно, в автомате Мура с полной системой выходов можно отождествить состояние автомата с его выходными сигналами. В связи с этим для состояний и выходных сигналов в дальнейшем будут использоваться одни и те же обозначения, т.е. отмеченная таблица переходов в автоматах Мура с полной системой выходов превращается в таблицу переходов.

Противогоночное кодирование. Одной из задач структурного синтеза автомата является задача кодирования состояний. При кодировании различным состояниям автомата ставятся в соответствие различные двоичные коды. Переход автомата из одного состояния в другое осуществляется за счёт изменения состояний элементов памяти – триггеров.

При переключении элементов памяти возможно возникновение состязаний из-за различия во времени их срабатывания. Возникновению состязаний способствуют также различные задержки сигналов возбуждения, поступающих на входы элементов памяти по логическим цепям, имеющим неодинаковую длину. Если при переходе автомата из одного состояния в другое несколько элементов памяти меняют своё состояние, то между ними начинаются состязания. Запоминающий элемент, который изменит своё состояние раньше, чем другие элементы памяти, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как участвующие в состязании элементы изменят своё состояние. Это может привести к переходу, непредусмотренному графом автомата. Переходя из состояния am в состояние as под воздействием входного сигнала xf автомат может оказаться в некотором промежуточном состоянии ak, которое определяется тем, какой элемент памяти выиграл состязание. Если автомат из состояния ak под действием того же входного сигнала xf перейдёт в состояние as, то состязания являются некритическими (допустимыми). Если же в этом автомате есть переход под воздействием входного сигнала xf из состояния ak в

54

состояние al (al ≠ as), то автомат может перейти в состояние al, а не в as. Правильность работы автомата будет нарушена, поэтому такие состязания называются критическими или гонками.

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

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

-в графе автомата отсутствуют циклы с нечётным числом вершин;

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

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

Если (α,β) и (γ,δ) – две пары двоичных кодов длины R, то они называются развязанными, когда r-й разряд кода (1 ≤ ρ ≤ R) принимает одно значение в паре (α,β) и противоположное в паре (γ,δ). В противном случае пары двоичных кодов называются связанными.

Алгоритм противогоночного кодирования с развязыванием пар переходов предусматривает просмотр всех пар состояний, связанных дугой перехода: (am,as), (ak,al) и т.д. Если для этих пар имеется хотя бы один общий входной сигнал xf, осуществляющий эти переходы, то разрядам кодов этих состояний (α,β) и (γ,δ) присваиваются такие значения, чтобы пары кодов состояний были развязанными хотя бы по одной переменной.

Такой подход к кодированию исключает гонки в автомате, т.к. известна следующая теорема: в автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда, когда для любых двух переходов (am,as) и (ak,al) (as,al), проходящих под действием одного и того же входного сигнала, соответствующие пары кодов состояний развязаны.

Различные варианты кодирования состояний автомата приводят к различным выражениям функций возбуждения памяти и функций выхода, что приводит к изменению сложности комбинационной схемы.

Взаимодействие автомата с внешней средой. Существует несколько моделей взаимодействия автомата с внешней средой: синхронная, асинхронная

исогласованная.

Вслучае асинхронной модели автомат взаимодействует с внешней средой

только через входные сигналы z1,z1,…,zL, поступающие из внешней среды, и выходные сигналы W1,W2,…,WN, поступающие во внешнюю среду. Такая схема может функционировать, если все её состояния устойчивые. Состояние

55

as называется устойчивым, если для любого входного воздействия xf X, такого, что функция переходов δ(am,xf)= as, имеет место равенство δ(as,xf)=as. В асинхронном автомате все состояния устойчивые.

Всинхронном автомате помимо входов z1,z1,…,zL и выходов W1,W2,…,WN существует дополнительный внешний вход p, по которому поступают синхроимпульсы СИ от генератора синхроимпульсов (ГСИ) через равные промежутки времени. Синхроимпульсы позволяют организовать переключение синхронного автомата из одного состояния в другое через интервалы времени, равные периоду следования СИ. В момент прихода СИ р=1

иp=0 при его отсутствии. Происходит тактирование входных сигналов автомата импульсами p определённой длительности. Переход из одного состояния в другое может происходит лишь при p=1. При этом необходимо, чтобы длительность сигнала p(tp) была меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме, что позволяет избежать явление гонок в автомате.

Потактная работа автомата может осуществляться как путём непосредственного тактирования входных сигналов, так и использованием элементов памяти (триггеров) с дополнительными синхровходами, на которые

иосуществляется подача СИ с ГСИ. В последнем случае осуществляется тактирование функций возбуждения. Время между двумя соседними СИ называется тактом работы автомата. Он определяется временем, необходимым для переключения элементов памяти состояний (TП), временем на дешифрирование состояний (ТД) и максимальным временем формирования выходных функций или функций возбуждения (TВ).

Для автомата Мили такт работы Т=ТП+ТД+ТВ, т.к. формирование функций возбуждения и функций выхода происходит параллельно.

Для автомата Мура такт работы Т= ТП+ТД+ТВ+ТВЫХ, т.к. формирование выходных функций (ТВЫХ) происходит после переключения элементов памяти, которое осуществляется при наличии сигналов со схем формирования функций возбуждения (ТВ ).

Всогласованной модели взаимодействия автомата и внешней среды

помимо входов z1,z1,…,zL и выходов W1,W2,…,WN существует дополнительный внешний вход G и дополнительный внешний выход R.

При сигнале G=1 входные сигналы z1,z1,…,zL и могут быть считаны схемой автомата, т.е. сигналом G осуществляется своего рода тактирование входных сигналов. Автомат реагирует на входные сигналы только при G=1 (можно провести аналогии с сигналом p в синхронном автомате).

Выходные сигналы W1,W2,…,WN могут быть считаны внешней средой лишь при наличии сигнала R=1.

Сигналы G=1 и R=1 должны поступать поочерёдно, т.к. после считывания

автоматом из внешней среды входных сигналов z1,z1,…,zL (G=1) им будут выработаны выходные сигналы W1,W2,…,WN, которые должны быть считаны внешней средой (R=1).

Из рассматриваемых трёх моделей автомата наиболее надёжной является согласованная модель, наиболее быстродействующей – асинхронная модель.

56

Основная литература: 2[39:48], 3[86:97].

Дополнительная литература: 4[290:299], 7[165:190]. Контрольные вопросы:

1.Дайте определение структурного алфавита.

2.Задачи синтеза структурного автомата.

3.Приведите общую схему структурного автомата (в виде памяти и комбинационной схемы).

4.Что собой представляет автомат Мура, обладающий полнотой?

5.Сформулируйте теорему о структурной полноте.

Тема 12.

Элементарные цифровые автоматы с памятью.

При синтезе структурного автомата элементы памяти обычно выбираются из некоторого набора типов стандартных элементов памяти. Это упрощает синтез структурного автомата и его физическую реализацию. Наиболее часто в качестве элементов памяти используются различные триггеры: D – триггер, T – триггер, RS – триггер, JK – триггер. Триггеры представляют собой автоматы Мура, которые имеют два внутренних состояния, одно из которых кодируется цифрой 1, другое – 0. Каждому внутреннему состоянию соответствует свой выходной сигнал. Триггеры обладают полной системой переходов и выходов. У триггеров алфавит состояний совпадает с выходным алфавитом, поэтому состояния и выходные сигналы триггеров в момент времени t будут обозначаться Q(t). Обычно триггеры имеют два выхода: Q и инверсный ему Q.

Для описания функционирования триггеров используются таблицы переходов и характеристические уравнения, задающие зависимость Q(t+1) от Q(t) и входных сигналов. При использовании триггеров в качестве элементов памяти структурного автомата необходимо составить для них таблицы входов, представляющие собой функции входов (возбуждений): какой входной сигнал должен быть подан на входы триггера, чтобы перевести его из одного состояния в другое.

D – триггер (элемент задержки) имеет один вход и два выхода. Он осуществляет задержку поступающего на его вход сигнала на один такт.

Условное обозначение D – триггера представлено на рисунке 12.

T Q D Q

Рисунок 12. Условное обозначение D – триггера

Таблица переходов			Таблица входов
D Q	0	1		Q(t)	D	Q(t+1)
				0	0	0
0	0	0
				0	1	1
1	1	1		1	0	0
				1	1	1

57

Как видно из таблицы переходов состояние, в которое переходит D – триггер, совпадает с его выходным сигналом. Характеристическая функция D – триггера: Q(t +1) = D(t) .

T – триггер (триггер со счётным входом) имеет один вход и два выхода. С приходом входного сигнала, равного единице, T – триггер меняет своё состояние на противоположное. Условное обозначение T – триггера приведено

на рисунке 13.

T Q T Q

Рисунок 13. Условное обозначение T – триггера

Таблица переходов					Таблица входов
T	Q	0	1	Q(t)	T	Q(t+1)
		0	1	0	0	0
0				0	1	1
1		1	0	1	1	0
				1	0	1

Характеристическая функция T – триггера:

Q(t +1) = Q (t)T (t) Q(t)T (t) = Q(t) T (t) .

RS -триггер (триггер с раздельными входами) имеет два входа (R – нулевой, S - единичный) и два выхода. Условное обозначение RS – триггера приведено на рисунке 14.

При поступлении единицы на единичный S – вход триггер переходит в состояние 1. При поступлении единицы на нулевой R–вход триггер переходит в состояние 0. Одновременное поступление единицы на R-вход и S-вход (11) запрещено.

		S		T	Q
		R				Q
Рисунок 14. Условное обозначение RS – триггера
Таблица переходов									Таблица входов
	Q	0	1					Q(t)	RS	Q(t+1)
RS
		0	0					0	00 10	0
00
								0	01	1
01		1	1						10	0
								1	00 01	1
10		0	0
11		-	-

Характеристическая функция RS – триггера:

Q(t +1) = Q (t)R (t)S(t) Q(t)R (t)S (t) Q(t)R (t)S(t) = R (t)S(t) Q(t)R (t) .

58

JK-триггер (универсальный триггер ) имеет два входа (J-единичный вход, K-нулевой вход) и два выхода. Условное обозначение JK-триггера приведено на рисунке 15. При J=K=1 универсальный триггер работает как триггер со счётным входом, при остальных входных комбинациях он работает как RS-триггер.

		J		T	Q
		K				Q
Рисунок 15. Условное обозначение JK-триггера
Таблица переходов									Таблица входов
	Q	0	1					Q(t)	JK	Q(t+1)
JK
		0	1					0	00 01	0
00
								0	10 11	1
01
		0	0					1	01 11	0
								1	00 10	1
10		1	1
11		1	0

Характеристическая функция JK – триггера: Q(t +1) = Q (t)J (t) Q(t)K (t) . DV-триггер имеет два входа (D,V) и два выхода. Условное обозначение

DV-триггера приведено на рисунке 16. При V=1 триггер работает как элемент задержки, при V=0 триггер сохраняет текущее состояние.

D T Q

Q

V

Рисунок 16. Условное обозначение DV-триггера

Таблица переходов					Таблица входов
Q	0	1		Q(t)	DV	Q(t+1)
				0	00 01 10	0
DV
00	0	1
				0	11	1
01	0	0		1	01	0
				1	00 10 11	1
10	0	1
11	1	1

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

59

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

Поэтому при использовании D-триггеров в качестве элементов памяти автомата можно применять следующий алгоритм кодирования состояний:

1.Состояние as, в которое существует больше всего переходов, кодируется кодом 00…00;

2.Следующие состояния, в которые существует также большое количество переходов, кодируются кодами, содержащими одну единицу: (00…01, 00…10,…01…00, 10…00);

3.Для кодирования оставшихся состояний используют сначала все коды, содержащие единицы (из R компонент), затем три единицы и т. д. До тех пор, пока не будут закодированы все состояния.

Таким образом, чем чаще встречается состояние am в таблице переходов, тем меньше единиц должно быть в его коде.

Для упрощения выходных функций аналогичный подход можно

применить и для кодирования выходных сигналов yg: чем чаще встречается выходной сигнал yg в таблице выходов, тем меньше единиц должен содержать его код. Это приводит к минимизации той части комбинационной схемы

автомата, которая формирует выходные сигналы: Wn(n = 1, N ).

В том случае, когда таблица переходов не совпадает с таблицей входов, описанный выше алгоритм кодирования не даёт желаемого результата. Используются другие подходы к кодированию состояний. Например, при использовании в качестве элементов памяти T-, RS-, JKтриггеров необходимо кодировать состояния таким образом, чтобы суммарное число изменений состояний элементов памяти на всех переходах состояний было минимальным, что можно достичь используя соседнее кодирование.

Основная литература: 2[49:54, 57:61], 3[97:101, 104;114].

Дополнительная литература: 4[286:290], 5[45:46]. Контрольные вопросы:

1.Назовите стандартные элементы памяти, приведите их обозначения.

2.Опишите работу RS, JKтриггеров (таблицы переходов).

3.Опишите работу D, T - триггеров (таблицы переходов).

4.Сформулируйте алгоритм кодирования состояний при использовании в качестве элементов памяти D-триггеров.

5.Сформулируйте алгоритм кодирования состояний при использовании в качестве элементов памяти T-, RS-, JKтриггеров.

Тема 13.

Цифровые операционные устройства.

Концепция микропрограммирования предполагает, что преобразование информации выполняется некоторым операционным устройством и включает следующие основные положения:

60

1)Любое преобразование информации рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации;

2)Преобразование описывается алгоритмом (микропрограммой) в терминах элементарных операторов, называемых микрооперациями (МО), и элементарных предикатов, называемых логическими условиями (ЛУ);

3)Микропрограмма (МП) определяет порядок выполнения МО и проверки ЛУ;

4)Логические условия принимают значения 1 (истина) или 0 (ложь) в зависимости от значений слов, преобразуемых микрооперациями, и управляют порядком следования МО;

5)На основе МП определяются структура и порядок функционирования устройства во времени.

Вфункциональном и структурном отношении операционное устройство (ОУ) разделяется на две части: операционный автомат (ОА) и управляющий автомат (УА). УА генерирует последовательность управляющих сигналов, предписанную МП, и соответствующими значениями логических условий. ОА служит для выполнения элементарных действий над словами информации, которые определены этой последовательностью управляющих сигналов.

Функция ОА определяется множеством входных слов D (данные), множеством выходных слов R (результаты), множеством внутренних слов S, используемых для представления промежуточных результатов, множеством

МО Y={y1,y2,…,yN}, множеством ЛУ X={x1,x2,…,xL}. Функция ОА задана, если заданы множества D, R, S, Y, X.

Словам информации в ОА ставятся в соответствие регистры, разрядность

которых совпадает с разрядностью соответствующих слов. Любая МО yj выполняется над словами информации (или их полями) и изменяет состояние регистров. Выполнение микроопераций обеспечивается соответствующими комбинационными схемами ОА. Микрооперация, определяющая элементарное действие, записывается в виде левой части, знака присваивания (:=) и правой части. В правой части указываются идентификаторы слов, которые являются

операндами, в левой части – идентификатор слова − результата.

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

МО установки обеспечивают присвоение слову или его полю значения константы (например, СМ:=0).

МО инвертирования обеспечивают изменение значения слова или его поля на инверсное (например, Рг1(0) := Рг1(0) ).

МО передачи выполняют присваивание слову или его полю значения другого слова или поля слова (например, Рг1:=Рг2, Рг2 (3÷15):=СМ(1÷13)).

МО сдвига служат для изменения положения разрядов слова (поля) по отношению к начальному путём перемещения каждого разряда на k−позиций

61

влево или вправо (например, Рг1:=L(k)Рг1−левый сдвиг содержимого Рг1, СМ:=R(k)СМ−правый сдвиг содержимого СМ).

МО счёта обеспечивают изменение значения слова на единицу

(например, Сч:=Сч+1).

МО сложения служат для присваивания слову значения суммы слагаемых

(например, СМ:=Рг1+СМ).

Бинарные логические МО присваивают слову или полю слова значение, получаемое поразрядным применением логических операций ( , , ) к соответствующим разрядам слагаемых (например,

СМ(0÷1):=СМ(0÷1) Рг(0÷1)).

Комбинированные МО содержат в себе несколько действий, присущих МО разного типа (например, СМ:=L1Рг1+Рг2).

Логические условия вычисляются в ОА в зависимости от значений слов (полей слов), преобразуемых микрооперациями, и подаются в УА в качестве осведомительных сигналов xi X.

Если несколько микроопераций (yt1, y t2,…, ytn) реализуются в ОА одновременно, то они образуют микрокоманду Yt={yt1, yt2,…, ytn}. Одновременно в ОА могут выполняться те МО, которые структурно и функционально совместимы. МО называются структурно совместимыми, если структура ОА допускает их параллельное выполнение. Функциональная совместимость МО имеет место в том случае, когда результаты выполнения микроопераций не зависят от последовательности их выполнения.

Функция УА определяется структурой микропрограммы, функциональные операторы которой {y1, y2,…, yN}=Y, а предикаты – {x1, x2,…, x L}=X. Управляющие сигналы yj, поступающие из УА в ОА и инициирующие МО, отождествляются с МО yj Y. Осведомительные сигналы xi, поступающие из ОА в УА, отождествляются с ЛУ xi X. Функция УА задана, если задана микропрограмма с множеством микроопераций Y и множеством логических условий X. УА, построенный по микропрограмме, называется микропрограммным автоматом.

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

Начальные языки описания автоматов задают алгоритм их функционирования. Алгоритм функционирования автомата задаётся в виде отображения входных последовательностей в выходные последовательности, т.е. отображения множества слов во входном алфавите X в множество слов в выходном алфавите Y.

Одним из распространённых начальных языков описания автоматов является язык операторных схем алгоритмов (ОСА). В настоящее время язык ОСА существует в трёх модификациях: логические схемы алгоритмов (ЛСА), матричные схемы алгоритмов (МСА), графические схемы алгоритмов (ГСА).

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

62

четырёх типов: одну начальную, одну конечную, операторные и условные вершины. ГСА удовлетворяет следующим требованиям:

1)имеет одну начальную вершину с одним выходом и без входа;

2)имеет одну конечную вершину с одним входом и без выхода;

3)содержит операторные вершины с одним входом и одним выходом;

4)содержит условные вершины с одним входом и двумя выходами;

5)вершины соединяются с помощью дуг, направленных от выхода к входу (каждый выход соединяется с одним входом и любой вход соединен, по крайней мере, с одним выходом);

6)один из выходов условной вершины может соединяться с её входом, что недопустимо для операторной вершины;

7)для любой вершины ГСА существует, по крайней мере, один путь в конечную вершину;

8)в каждой условной вершине записывается xi X;

9)в каждой операторной вершине записывается один или несколько

yj Y.

Если ГСА используется для задания микропрограммы, X представляет собой множество логических условий (x1, x2,…,xL), a Y−множество микроопераций (y1, y 2,…yN).

При составлении микропрограммы в операторных вершинах ГСА записывается содержательное обозначение микроопераций yj Y в виде операторов присваивания, а в условных вершинах – логические условия xi X в виде логических выражений. Такая ГСА называется содержательной.

Перечень микроопераций и логических условий, входящих в содержательную ГСА, является исходной информацией для синтеза операционного автомата ОУ. Функционально и структурно совместимые МО записываются в одной операторной вершине и образуют микрокоманду Yt. В процессе проектирования МПА от содержательной ГСА переходят к кодированной ГСА, путём выполнения кодирования микроопераций некоторыми символами yj Y, логических условий − символами xi X. В кодированной ГСА в операторных вершинах записываются символы из множества Y, в условных − символы из множества X.

Кодированные ГСА являются исходной информацией для синтеза УА с жёсткой логикой или программируемой логикой.

Синтез управляющего автомата осуществляется по кодированной ГСА. В результате получают УА, вырабатывающий управляющие сигналы Y={y1, y2,…,yN}, порядок следования которых зависит от микропрограммы и значения логических условий X={x1, x2, …, xL}. УА с жёсткой логикой строится на базе использования логических элементов и элементов памяти. Изменить алгоритм его работы нельзя, не изменяя соединений между элементами.

Интерпретация МП конечным автоматом с памятью получила название интерпретационного метода синтеза УА. В интерпретационном методе синтеза выделяют несколько этапов синтеза автомата:

1) получение отмеченной ГСА;

63

2)определение путей перехода;

3)построение графа автомата;

4)кодирование состояний;

5)построение функции выхода yj Y;

6)построение функций возбуждения с учётом выбранного элемента памяти;

7)совместную минимизацию функций возбуждения и функций выхода и построение схемы структурного автомата.

Существуют некоторые особенности выполнения интерпретационного метода синтеза, связанные с выбранной моделью автомата (Мили или Мура).

Основная литература: 1[249:252], 2[64:77], 3[168:181].

Дополнительная литература: 4[324:328], 7[414:431]. Контрольные вопросы:

1.Дайте определение микрооперации, приведите классификацию микроопераций.

2.Дайте определение микрокоманды.

3.Дайте определение МПА.

4.Назовите начальные языки описания МПА.

5.Дайте определение ГСА (графические схемы алгоритмов), сформулируйте требования, которым должны удовлетворять ГСА.

Тема 14.

Контроль и диагностика цифровых устройств.

Для работы ЦУ (УА и ОА) в целом характерно наличие отказов и сбоев, которые приводят к ошибкам в работе. Ошибки вызываются выходом из строя какой-либо детали, или отклонением от нормы параметров (напряжения питания), или воздействием внешних помех.

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

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

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

64

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

При организации контроля обычно рассматривается класс одиночных неисправностей одного логического элемента. Вероятность возникновения такой неисправности намного больше по сравнению с вероятностью возникновения кратных неисправностей, организовать обнаружение которых намного сложнее. Одиночные неисправности могут быть типа константы 0 (постоянно держится на входе или выходе элемента сигнал 0) или константы 1 (постоянный сигнал 1).

Различают контроль комбинационных схем и автоматов с памятью. Для последних контроль усложняется в связи с тем, что схемы имеют элементы памяти и любая одиночная неисправность приводит к кратным ошибкам из-за наличия обратной связи в схемах. Контроль комбинационных схем проще, хотя и там возможны разветвления, приводящие одиночную неисправность к кратным ошибкам.

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

Функциональный контроль осуществляется во время работы контролируемого объекта и осуществляется чаще всего с помощью специальной аппаратуры, встроенной в объект контроля.

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

Избыточность может быть внесена при кодировании информации. Код, содержащий дополнительные разряды, в которых содержится избыточная информация, называется систематическим кодом. В систематическом коде различают m информационных разрядов и k контрольных разрядов (для избыточной информации). При этом число контрольных разрядов k характеризует абсолютную избыточность, а отношение k/n (n=m+k – общее количество разрядов в кодовом слове) – относительную избыточность.

Не всякий код, имеющий ненулевую избыточность, обладает способностью обнаруживать ошибки. Корректирующая способность кода связана с понятием 'дозволенного' и 'недозволенного' кодов.

При правильной работе ЦА существуют только дозволенные коды. Появление недозволенного кода является признаком одиночной ошибки. Для перехода от одного дозволенного кода к другому дозволенному коду необходимо не менее двух одиночных ошибок. Указанное требование может быть сформулировано через понятие расстояния между двумя кодами.

Посылочные корректирующие коды. Простейшим примером кода с избыточной информацией, позволяющим обнаружить одиночные ошибки, является код, в котором к n-основным разрядам добавляется один

65

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

Если n-основных разрядов содержат четное число '1', то в контрольный разряд записывается '0', в противном случае '1'.

Сумма значений всех разрядов, включая и контрольный, должна равняться '0' в случае отсутствия одиночных ошибок при передаче кода. Появление одиночной ошибки в любом из разрядов изменит эту сумму на '1', что и является признаком ошибки.

Пример. Если необходимо передать байт данных 11011010, то в дополнительный контрольный разряд записывается '1' и источник данных передает 9 разрядов 110110101. Приемник данных суммирует по модулю 2 содержимое 9-и разрядов. Если сумма равна'0', ЦА продолжает свою работу, в противном случае формируется сигнал ошибки и передача повторяется. Многократное появление ошибки позволяет диагностировать отказ.

Этот принцип получения значения контрольного разряда лег в основу названия кода: "код с проверкой на четность". Код с проверкой на четность является самым простым посылочным корректирующим кодом и широко применяется при передаче информации.

Добавление дополнительного контрольного разряда в двоичный код равносильно увеличению кодовых комбинаций в два раза. Все эти комбинации можно разбить на две группы: дозволенные кодовые комбинации и недозволенные. Причем расстояние между двумя дозволенными кодовыми комбинациями увеличивается до двух (d= 2).

Контроль по модулю. Посылочные корректирующие коды не применимы для выявления ошибок при выполнении арифметических операций. Для их контроля получили широкое распространение методы, основанные на свойствах сравнения. Один из таких методов, получивший название - контроль по модулю, рассматривается ниже.

При контроле по модулю в код числа вводятся дополнительные контрольные разряды, в которые записывается остаток от деления исходного кодируемого числа на целое, заранее заданное число p (модуль). При этом все машинные числа условно рассматриваются, как целые.

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

К величине модуля p предъявляются следующие требования:

1)модуль должен обеспечивать обнаружение как можно большего числа ошибок при обязательном выявлении одиночных ошибок;

2)модуль должен быть таким, чтобы остаток от деления на него

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

66

3) модуль должен быть небольшим с тем, чтобы и остатки от деления на него получились мало разрядными. В противном случае потребуются большие затраты дополнительного оборудования для хранения остатков и выполнения действий над ними.

Всоответствии с первым требованием нельзя брать в качестве модуля p основание системы счисления, так как в этом случае будут обнаруживаться ошибки только в младшем разряде. Ошибки в старших разрядах, вследствие их кратности основанию системы счисления, выявляться не будут.

Для того, чтобы удовлетворялось второе требование, можно воспользоваться не числовым кодом, а цифровым кодом числа. При использовании последнего, остаток от деления на модуль определяется путем деления суммы цифр числа на выбранный модуль p. Если сумма цифр числа меньше модуля p , то сумма цифр и является остатком. В общем случае этот остаток не равен остатку от деления на модуль p данного числа, но в частном случае они могут быть равны. И в этих частных случаях нахождение остатка числового кода можно заменить нахождением остатка цифрового кода. Совпадение остатков происходит в том случае, если p=h-1, где h-основание системы счисления.

Вдвоичной системе счисления (h=2) в непосредственном виде этот способ неприменим, так как h-1=1 (при h=2). Но можно использовать

некоторую вспомогательную систему счисления h'=2i (i>=2). Тогда p=2i- 1, и при различных значениях i получают ряд модулей, пригодных для контроля операций в двоичной системе счисления.

Чтобы удовлетворялось третье требование к величине модуля, рекомендуется брать модуль p<=15. С ростом модуля повышается как объем контрольного оборудования, так и корректирующая способность кода.

Процедуру нахождения остатка цифрового кода от деления на модуль p можно реализовать, используя только одну операцию - суммирование, выполняя так называемую свертку числа по модулю. Алгоритм свертки двоичного n-разрядного числа по модулю p=2i-1 состоит в следующем:

1)все число разбивается на S=n/i групп по i двоичных разрядов каждая;

2)все группы последовательно, начиная с младшей, суммируются на обычном двоичном i- разрядном сумматоре по модулю p , то есть с циклическим переносом единицы переполнения в младший разряд (сумматор

обратного кода). Циклический перенос учитывает тот факт, что любая степень числа 2- в данном случае это единица переносапри делении ее на 2i-1 будет давать в остатке единицу.

Полученное на сумматоре число и будет искомым остатком. При выполнении операции алгебраического сложения А+В от деления на модуль p должна равняться остатку от деления на этот же модуль p их суммы z: А(modp)+B(modp)=Z(modp). В противном случае будет вырабатываться признак ошибки.

Пример. Выполнить контроль по модулю p=3 операции сложения А+В=Z, если А=00,001101, В=00,100110, Z=00,110011.

67

Число А разбивается на диады (00,00,11,01), которые складываются на двухразрядном двоичном сумматоре обратного кода: А(mod3)=01. Число В разбивается на диады (00,10,01,10), сложение которых на двухразрядном сумматоре обратного кода дает: А(mod3)=10. Сумма 01+10=11. разбиение числа Z на диады (00,11,00,11) с последующей их сверткой образует Z (mod3)=11.

Ответ: А(mod3)+В(mod3)=Z(mod3)=11, операция выполнена верно. При выполнении операции умножения А×В=Z:

А(modp)×В(modp)=Z(modp). Невыполнение этого равенства является признаком ошибки.

Пример. Выполнить контроль по модулю p=3 операции умножения А×В=Z, если: А=0,1010, В=0,1001, Z=0,01011010.

Осуществляется свертка модулей чисел А и В по модулю 3:

А(mod3)×В(mod3)=01×11=11. Свертка модуля числа Z дает: Z(mod3)=11.

Ответ: А (mod3)*B(mod3)=Z(mod3)=11, операция умножения выполнена верно.

При выполнении операции деления А на В необходимо учитывать частное Z и остаток R, получаемый при делении. Чтобы избежать выполнения сложной операции деления остатков для контроля обычно используют соотношение А(mod3)=Z(mod3)×B(mod3)+R(mod3). При этом должна осуществляться свертка положительного остатка R.

Пример. Выполнить контроль по модулю p=3 операции деления А:В=Z, если делимое А=0,1001, делитель В=0,1011, полученное частное Z=0,1101,

остаток R=0,0001.

Свертка модулей данных чисел по модулю 3 дают следующие остатки.

А(mod3)=11, B(mod3)=10, Z(mod3)=01, R(mod3)=01.

B(mod3) ×Z(mod3)+R(mod3)= =10×01+01=10+01=11.

Ответ: А(mod3)=B(mod3)×Z(mod3)+R(mod3)=11, деление выполнено верно.

Контроль по модулю может применяться для проверки правильности промежуточных сумм при выполнении операции умножения и деления (шаговый контроль), так как реализация этих операций идет через многократное выполнение операции сложения. В этом случае окончательный результат не проверяется. При выполнении операции в 2-10 системах счисления в основном применяется шаговый контроль.

Чтобы можно было не только обнаружить, но и исправить ошибку, необходимо контроль выполнять по нескольким модулям (не менее двух модулей). Но при этом все равно останутся необнаруженные ошибки, которые изменяют проверяемое число на величину, кратную всем модулям.

Контроль по модулю носит также название контроля по наименьшим вычетам.

Корректирующий AN-код. Для выявления пакетов ошибок можно использовать корректирующий AN-код. При этом в контролируемое число А вносится избыточность путем умножения его на модуль N, отсюда и название - АN-код. Весом AN-кода принято считать количество нулевых символов в кодовой комбинации, а расстоянием (арифметическим) - вес разности кодовых

68

комбинаций. Все числа при использовании AN-кода делятся на разрешенные и запрещенные.

Основная литература: 1[140:160]. Дополнительная литература: 4[222:254], 7[398:413]. Контрольные вопросы:

1. Перечислите основные понятия контроля и диагностики цифровых автоматов.

2.Сформулируйте назначение тестового и функционального контроля, их отличие.

3.Перечислите виды избыточности при проведении контроля.

4.Сформулируйте принцип действия посылочного корректирующего кода, приведите пример.

5.Сформулируйте принцип действия контроля по модулю.

Тема 15.

Управляющие устройства с программируемой логикой.

Управляющее устройство (управляющий автомат - УА) может быть построено на основе принципа программного управления – с программируемой логикой. УА с программируемой логикой реализует микропрограмму, записанную в управляющую память в виде микрокоманд. В этом случае микрокоманды содержат информацию о микрооперациях, которые должны выполняться в данном такте работы устройства, и об адресе следующей микрокоманды.

Можно предложить несколько различных форматов микрокоманд УА с программируемой логикой. Один из форматов микрокоманд приведён на рисунке 17: ОЧ – операционная часть, АЧ – адресная часть. Операционная часть состоит из нескольких операционных полей МО1,…, МOm , число которых определяет максимальное число одновременно выполняемых микроопераций. В одном операционном поле записывается двоичный код микрооперации yj, подлежащей выполнению в данном такте работы устройства. Число операционных полей и структура ОА оказывают влияние друг на друга, т.к. микрооперации подлежат выполнению в операционном автомате. Возможно нулевое содержание ОЧ, что соответствует отсутствию микрооперациий.

Адресная часть состоит из полей логического условия (X) и адреса перехода (A).

МО1…МОm Х А

ОЧ АЧ

Рисунок 17. Формат МК

В поле логического условия записывается двоичный код логического условия xi, которое проверяется после выполнения микрооперации yj в данном

69

такте. Если логическое условие xi = 0, то адресом текущей МК является А из поля Ax(A=Ax). В противном случае (xi = 1) адрес следующей МК определяется адресом выполняемой МК, увеличенным на 1 (A=Aтек+1). Если содержимое поля X равно нулю, что соответствует отсутствию логического условия, то адрес следующей МК содержится в адресе перехода Ax текущей МК (A=Ax).

В описанном выше формате используется способ принудительной адресации микрокоманд. Способ адресации задаёт правила определения адреса следующей МК и определяет структуру УА, реализующего данную МП.

На рисунке 18 представлена структура УА с программируемой логикой, использующего формат МК с принудительной адресацией (см. рис.17).

РгA

ЧТ УП

РгМК		У		X
		ДШ Y
y1 y2 y3			yk
		в ОА

А=А+1

								x	=0
								i
										x	=1
AX				x						i
					1			&	1
		.
		.						.		1
ДШ	X							.
		.
				x				.
					L			&
					x	.. .x
					1		L

из ОА

Рисунок 18. Структурная схема УА с программируемой логикой

Микрокоманды хранятся в управляющей памяти (УП) и считываются в регистр микрокоманд по каждому сигналу “чтение” (ЧТ). Адрес считываемой МК определяется содержанием регистра адреса (РгА), которое обнуляется сигналом “Пуск” (xi=0).

По сигналу ЧТ производится выборка МК из УП и занесение её в регистр микрокоманд (РМК). ОЧ микрокоманды из РМК поступает на дешифратор ДШ Y. Каждое операционное поле МОj дешифрируется своим дешифратором, на выходе которого вырабатываются сигналы, инициирующие выполнение микроопераций в ОА. Так как возможна выработка одних и тех же сигналов yj при различных микрокомандах различными дешифраторами, то одноимённые сигналы y1, y2,…, ym объединяются схемой объединения и отправляются в операционный автомат. Поле X дешифрируется дешифратором ДШ X, выходы которого подключены к входам схем И, на вторые входы которых подаются логические условия x1, x2,…, xL из ОА. На i-ю схему И подаётся xi из ОА и i-й выход ДШ X, на котором будет присутствовать “1” в случае наличия в поле X кода логического условия xi. Выходы всех схем И объединяются, и на выходе схемы И-ИЛИ-НЕ будет присутствовать 0 или 1 в зависимости от значения логического условия xi в ОА. Это приведёт к тому, что в Рг А будет записываться адрес Ax из РгМК (xi=0) или содержимое РгА будет увеличиваться на 1 (xi=1).

Формированием адреса следующей МК (A=Ax или A=A+1) завершается такт работы УА.

70

Признаком конца выполнения микропрограммы является появление конечного оператора yk, который поступает на ТЗ и переводит его в нулевое состояние, запрещая тем самым считывание микрокоманд из УП.

Возможно использование микрокоманд с естественной адресацией, когда АЧ в МК отсутствует, а адрес следующей МК образуется путём прибавления к адресу текущей микрокоманды 1. В этом случае для реализации условных переходов используются специальные управляющие МК. Структура УА с естественной адресацией МК будет отличаться от рассмотренной выше.

Структура УА с программируемой логикой зависит как от способа адресации МК и их формата, так и от метода кодирования МО и ЛУ. Любое изменение из указанных выше, приводит к изменению структуры УА.

Сравнение управляющих автоматов с жёсткой и программируемой логикой. Один и тот же алгоритм работы ОУ, записанный в виде МП, может быть реализован как автоматом с жёсткой, так и автоматом с программируемой логикой. Эти УА будут отличаться своими характеристиками: затратами оборудования, быстродействием, гибкостью и т. д.

Количество оборудования в автомате в основном зависит от сложности реализуемой МП. В качестве критерия сложности МП (S) можно взять суммарное количество операторных и условных вершин в МП. В этом случае зависимость количества оборудования Q от сложности микропрограммы S изобразится графиками, представленными на рисунке 19: 1 – для автоматов с жёсткой логикой, 2 – для автоматов с программируемой логикой.

Q

1

2

150200

S

Рисунок 19. Сравнение УА с жесткой и программируемой логикой

Для автоматов с жёсткой логикой затраты оборудования возрастают почти пропорционально сложности МП. Для автоматов с программируемой логикой характерно резкое возрастание Q при малых значениях S, а с дальнейшим увеличением сложности МП возрастание затрат оборудования Q происходит незначительное. Поэтому при 0<S<S0 (см. рис.3) более экономичны автоматы с жёсткой логикой, при S>S0 – автоматы с программируемой логикой. Обычно S0 ≈ 150-250 вершин ГСА.

Быстродействие автоматов с жёсткой логикой более высокое, чем автоматов с программируемой логикой. Это объясняется тем, что затраты на формирование управляющих сигналов y1, y2,…,yM в УА с программируемой логикой включают в себя время считывания МК из УП. Таким образом, такт

71

работы УА с жёсткой логикой τП = τЖ + TУП, где τЖ – такт работы УА с жёсткой логикой, TУП – длительность цикла управляющей памяти.

Если под гибкостью подразумевать возможность внесения изменений в МП, реализуемую автоматом, то УА с жёсткой логикой не обладает гибкостью. При изменении МП необходимо синтезировать новый УА с жёсткой логикой, в то время как изменение МП для УА с программируемой логикой может привести лишь к изменению содержимого УП (изменению микрокоманд, внесению дополнительных микрокоманд). Поэтому УА с программируемой логикой обладает гибкостью.

Основная литература: 2[77:82]. Дополнительная литератуар: 7[447:463]. Контрольные вопросы:

1.Дайте определение УА с программируемой логикой.

2.Приведите пример формата микрокоманд УА с программируемой логикой.

3.Приведите структурную схему УА с программируемой логикой.

4.Объясните принцип работы УА с программируемой логикой.

5.Приведите сравнительные характеристики упраляющих автоматов с жесткой и программируемой логикой.

2.3 Планы лабораторных занятий Перечень тем лабораторных занятий:

Лабораторное занятие № 1. Перевод чисел из одной системы счисления в другую.

Лабораторное занятие №2. Алгебраическое сложение в двоичной системе счисления с фиксированной запятой.

Лабораторное занятие №3. Алгебраическое сложение в двоичной системе счисления с плавающей запятой.

Лабораторное занятие №4. Алгебраическое сложение в двоичнодесятичных системах счисления.

Лабораторное занятие №5. Умножение в двоичной системе счисления. Лабораторное занятие №6. Деление в двоичной системе счисления. Лабораторное занятие №7. Способы задания функций алгебры логики

(ФАЛ), запись ФАЛ в СДНФ, их преобразование. Лабораторное занятие №8. Минимизация ФАЛ. Лабораторное занятие № 9. Синтез комбинационных схем.

Лабораторное занятие №10. Способы задания абстрактных автоматов. Лабораторное занятие №11. Синтез абстрактных микропрограммных ав-

томатов Мили.

Лабораторное занятие №12. Синтез абстрактных микропрограммных автоматов Мура.

Лабораторное занятие №13. Синтез структурных микропрограммных автоматов Мили.

Лабораторное занятие №14. Синтез структурных микропрограммных автоматов Мура.

Лабораторное занятие №15. Контроль посылочных операций.

72

Лабораторное занятие № 1 Тема: Перевод чисел из одной системы счисления в другую.

Задания к лабораторному занятию №1

1.Перевести десятичное число N10 =324,4310 в двоично − десятичную

(N2−10), восьмеричную (N8), шестнадцатеричную (N16) и двоичную (N2) (с точностью до пяти знаков после запятой) системы счисления.

2.Перевести восьмеричное число N8 =341,218 в двоичную (N2),

шестнадцатеричную (N16), десятичную (N10), двоично − десятичную (N2−10) системы счисления.

3. Записать в форме с фиксированной запятой в прямом коде представление десятичного числа -0,928 в формате {1.8} (первый двоичный разряд − знак числа, следующие восемь двоичных разрядов − модуль числа).

Основная литература: 1[46:67]. Дополнительная литература: 4[18:56]. Контрольные вопросы:

1.Сформулируйте правила перевода из одной системы счисления в другую и целесообразность использования различных методов перевода чисел.

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

3.Дайте определение нормализованного и ненормализованного представления числа.

4.Перечислите преимущества и недостатки представления чисел с плавающей и фиксированной запятой.

5.Приведите формы машинного представления числа.

Лабораторное занятие № 2 Тема: Алгебраическое сложение в двоичной системе счисления с

фиксированной запятой.

Задания к лабораторному занятию №2

1. Записать числа N1 и N2, представленные в форме с фиксированной запятой с использованием модифицированного обратного и дополнительного кодов:

а)	N1= − 0,01010110;	б) N1=− 0,10101011;
	N2= +0,10101011.	N2= − 0,01010110.

2.Выполнить по машинному алгоритму операцию алгебраического

сложения над числами N1 и N2, представленными в форме с фиксированной запятой с использованием модифицированного обратного кода (см. задание 1).

3.Выполнить по машинному алгоритму операцию алгебраического

сложения над числами N1 и N2, представленными в форме с фиксированной запятой с использованием модифицированного дополнительного кода (см. задание 1).

Основная литература: 1[68:81]. Дополнительная литература: 4[109:121].

73