Как составить таблицу переходов выходов

Время на прочтение
5 мин

Количество просмотров 110K

Статья написана, собрана и сверстана Brotherofken. Спасибо ему огромное.
В предыдущей статье я попытался изложить все основные определения и принципы, чтобы сделать эту статью максимально понятной. Все не уместилось, так что я настоятельно советую ознакомиться с этими файлами:
Базис, Базис2, Минимизация. Далее в этой статье я оставил несколько разъясняющих пометок курсивом.

В этой статье я попробую объяснить доступным языком что такое абстрактный автомат, способы его представления. Так как теория автоматов полна математики и сложна, постараюсь писать человеческим языком, чтобы неподготовленный читатель смог понять о чём идёт речь.

Электронные цифровые схемы формально можно разделить на 2 класса:

• Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.
• Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.

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

Абстрактный автомат

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

Или, если перейти от иллюстрации к математическому описанию:
A = <A, B, C, δ, λ>

Обозначения:

1. Множество {A} – представляет собой множество значений на физических входах автомата. На входе в нашем случае будет какая-то последовательность высоких и низких уровней напряжения, которые будут кодировать логические нули и единицы.
2. Множество {B} – представляет собой множество значений на физических выходах автомата.
3. Множество {C} – а множество, которое представляет внутреннее состояние автомата – память. На будущее C0 будем обозначать начальное состояние автомата.
4. δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.
5. λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.

δ и λ не показаны на схеме для визуального упрощения.

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

Выделяют 2 типа автоматов:

1. Автоматы Мили. Описывается системой уравнений:
   c(t) = δ( a(t), c(t-1) );
   b(t) = λ( a(t), c(t-1) ).
2. Автоматы Мура. Описывается уравнениями:
   c(t) = δ( a(t), c(t-1) );
   b(t) = λ( a(t), c(t) ).

Как видно

состояние автомата c(t) в текущий момент времени является функцией его состояния в предыдущий момент времени и входного сигнала

.
Отличаются автоматы видом функции выхода. В автомате Мили выходной сигнал определяется входным сигналом a(t) и состоянием автомата в предыдущий момент времени c(t-1). Выходной сигнал автомата Мура определяется парой входного сигнала a(t) и состояния в данный момент c(t).
Так же можно отметить, что от одного типа можно перейти ко второму и наоборот, причем при переходе от автомата Мили к автомату Мура число внутренних состояний автомата останется прежним, а при обратном переходе число внутренних состояний может возрасти. На этом останавливаться подробно не будем, считая, что синтезировали(нарисовали граф) автомат того типа, который надо.
Итак, на этом с матчастью окончено. Попробуем описать автоматы.

Т.е. автомат типа Мили вырабатывает выходной сигнал когда у него меняется входной, в зависимости от его предыдущего состояния. При этом длительность выходного сигнала не зависит от длительности входного, а только от его присутствия. В автоматах типа Мура выходной сигнал зависит от состояния автомата в текущий момент времени т.е. автомат будет вырабатывать определенный выходной сигнал пока не изменит свое состояние.

Способы задания автоматов

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

Есть два основных способа задания автомата:

1. При помощи графов.
2. При помощи таблиц переходов и выходов.

Графы

Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.

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

Для графа автомата Мура на дугах записываются только входные буквы, выходные же указываются около вершин.

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

полным

. Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат

Мили является полным

, а автомат

Мура – частичным

.
И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется

недетерминированным

. Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к

детерминированному

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

Таблицы переходов и выходов.

Графы нагляднее для человека, а таблицы — для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.
Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.

ТПВ графа Мили

В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3.

ТПВ графа Мура

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

Пример синтеза автомата

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

Кодируем входной и выходной алфавиты:
A = {a0, a1}, где a0 – логическая 1 на входе R, a1 – логическая единица на входе S.
B = {b0, b1}, где b0 – логический 0 на выходе Q, b1 – логическая единица на выходе Q.
Строим граф автомата Мили:

Вот такая забавная чебурашка получилась :-). Теперь можно построить таблицу переходов и выходов:

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

Нанесём полученную функцию на карту Вейча и минимизируем:

Выпишем, что получилось:

Строим по функции схему (Выполняли домашнее задание?):

Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём:

А на схеме асинхронный RS триггер обозначается вот так:

Теперь если приложить немного старания, то можно самостоятельно синтезировать простую новогоднюю гирлянду.

Таблицы
переходов и выходов.
При этом способе каждая функция –
переходов и выходов – задается в виде
таблицы, называемой, соответственно,
таблицей переходов и таблицей выходов.
Столбцы обеих таблиц соответствуют
различным состояниям входа автомата
(элементам множества {X}),
строки обеих таблиц – внутренним
состоянием автомата (элементам множества
{S}).

На
пересечении i–й
строки и
ј-го
столбца таблицы переходов указывается
то внутреннее состояние S(t+1),
в которое автомат перейдет из внутреннего
состояния s_i
­
(i
-я строка) под действием входных сигналов,
соответствующих состоянию входа x­_ј
(ј-й
столбец).

Поскольку
S(t+1)
есть
значение, которое принимает функция
переходов φ
при
X(t)=
x­_ј
и S(t)=
s_i
­­,
то, следовательно, задание S(t+1)
и есть задание функции φ.
На пересечении i–й
строки и
ј-го
столбца таблицы выходов указывается
то состояние выхода Z(t),
которое будет иметь место, если на
автомат, находящийся в момент
t
во внутреннем состоянии S_i­,
входной сигнал, соответствующий состоянию
входа x­_ј­.

Поскольку
Z(t),
есть значение функции выходов f
при
S(t)=
s_i
­­
и X(t)=
x­_ј,
то, следовательно, задание Z(t)
это и есть задание функции f.
Часто внутренние состояния автомата
обозначаются не символами s_i­,
а просто цифрой i,
соответствующей номеру внутреннего
состояния (рисунок 7)

Рисунок
7 – Таблицы переходов и выходов

Таблицу
переходов и выходов можно совместить
в одну таблицу. Тогда записью в каждой
клетке таблицы является значение функции
φ­_­
­
в виде S(t+1),
и f
– в виде Z(t),
которые отделяются друг от друга запятой

(рисунок
8)

Рисунок
8 – Совместная таблица переходов и
выходов

Графы
переходов и выходов.
Граф переходов представляет собой
некоторую структуру, состоящую из
вершин, изображаемых кружками, и
ориентированных (направленных) дуг,
изображаемых в виде линий между парами
вершин и снабженных стрелками, указывающими
направление от одной вершины к другой.
Каждая вершина графа переходов
соответствует внутреннему состоянию,
которое указывается внутри кружка.
Направленные дуги, соединяющие две
вершины i
и j,
отмечаются записью того состояния входа
х_к,
который вызвал переход автомата из
состояния i
в состояние
j,
а так же записью того состояния выхода
z₁,
которое имело место при этом. Такая
двойная запись х_к,
z₁
носит название пары «вход-выход».
Например, если над дугой записано х_к,
z₁,то
это значит, что переход автомата в
состояние j
произошел
под действием входного сигнала,
соответствующего состоянию входа х_к,
при этом сигнал на выходе принял значение
z­₁.
В общем случае переход из состояния i
в j
может
происходить под действием различных
входных сигналов; для обозначения этого
используется знак дизъюнкции «V»,
которым связываются все пары вход-выход,
соответствующие этому переходу. Например,
(х₁/z₁)V(x₂/z₂)V…V(x_r/z_r).
Граф переходов автомата приведен на
рисунке 9.

Рисунок
9 – Задание автомата в виде графа

5.2 Способы задания асинхронного автомата

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

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

Поясним
рисунок 10, рассмотрев первую и вторую
строки. Прежде всего, в таблице четыре
строки, следовательно, автомат имеет
четыре внутренних состояния: s­₁,
s­₂,
s₃,
s₄,
хотя устойчивых состояний у него шесть.
В первой строке указано устойчивое
состояние 1, которое имеет место, если
автомат находится во внутреннем состоянии
s­₁
и
состояние входа есть x₁.
Если происходит изменение состояния
входа с x₁
на
x₂,
то, следуя по строке 1 и переходя к столбцу
2, видим, что там указано неустойчивое
состояние 2. Значит, автомат из состояния
1 перейдет в неустойчивое состояние 2,
а затем, поскольку состояние входа
сохраняется равным x₂,
перейдет в устойчивое состояние 2. Если
затем произойдет изменение состояния
входа с x₂
на x₃,
то, двигаясь по второй строке таблицы
до столбца x₃,
видим, что там указано устойчивое
состояние 6. Это значит, что при таком
изменении входа автомат из устойчивого
состояния 2 в устойчивое 6 перейдет
непосредственно, без изменения его
внутреннего состояния. Если теперь
произойдет изменение состояния входа
с x₃
на x₄,
то из таблицы определяем, что автомат
перейдет в неустойчивое состояние 4
(столбец x₄,
вторая строка). Поскольку состояние
входа x₄
сохраняется до конца изменений памяти
автомата, то автомат достигает устойчивого
состояния 4. Чтобы завершить задание
автомата, необходимо задать его функцию
выходов. С этой целью строится таблица
выходов, которая имеет два столбца:
столбец устойчивых состояний и столбец
соответствующих им выходных сигналов.
Иногда таблицы выходов и переходов
совмещают.

Рисунок
10 – Таблица переходов и выходов
асинхронного автомата

Граф
переходов асинхронного автомата по
построению не отличается от синхронного,
вершины его соответствуют внутренним
состояниям, а направленные дуги отличаются
соответствующими парами вход-выход
(рисунок 11)

Рисунок
11 – Задание асинхронного автомата в
виде графа

Всем
устойчивым состояниям автомата
соответствуют вершины с замкнутыми
петлями, отмеченными теми состояниями
входа, при которых, при данном внутреннем
состоянии автомат будет находиться в
устойчивом состоянии. Например, вершина
2 имеет петлю, отмеченную парой x₂/z₁
и x₃/z₂,
как видно из таблицы, это соответствует
устойчивым состояниям 2 и 6, имеющим
место при втором внутреннем состоянии
автомата и соответственно состоянии
входа x₂
и x_3­.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Занятие 14. Граф автомата, таблица переходов и выходов

Цель занятия. Изучение еще одного класса дискретных автоматов – автоматов с памятью, познакомится со способами описания работы этих устройств.

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

Работа последовательностного автомата определяется не только входным набором, но и собственным состоянием автомата. В свою очередь состояние Si автомата зависит от начального S0 его состояния и последовательности входных наборов, приведших его в это состояние(рис. 1).

Рисунок 58. Дискретное устройство с памятью (yi = F(x1,…,xn, Si)

Si {S0,S1,…,SL}, 2< L < m).

Мы рассматриваем дискретные устройства с конечным числом L состояний S. Рассмотрим представление автомата с памятью графом автомата. Начнем с представления триггера – автомата с 2 состояниями. Состояния представим вершинами, а связи между ними – стрелками. Стрелки снабдим условиями переходов.

Рисунок 59. D – триггер (задержка – сигнал х задерживается на один такт T).

Рисунок 60. Изображение D-триггера на схемах

Рисунок 61. С синхросигнал с периодом Т.

Сигнал D запоминается в момент, когда С=1 и хранится весь оставшийся период Т.

Теперь выполним проектирование так называемого “Секретного замка” – последовательного автомата запирающего дверь и открывающего ее, или поднимающего сигнал тревоги в зависимости от последовательностей входных воздействий.

Рисунок 62. “х1, х2”- входные переменные, “y1,y2” – выходные переменные.

1,дверь открывается,

y1=

0, дверь закрывается;

1, тревога звучит,

y2=

0, тревога не звучит.

Задана всего одна открывающая последовательность входных наборов. Еще один набор – нейтральный (х1х2 = 00), автомат остается в том же состоянии. На всех остальных последовательностях звучит сигнал тревоги.

Для нашего автомата открывающая входная последовательность пусть будет такой – х1х2= 01 11 10. Последовательности, например, начинающиеся с наборов 11 иди 10, вызовут сигнал тревоги автомата. Если дверь открыта, то она остается в этом состоянии при нейтральном входном наборе(00), любое нажатие входных кнопок вызовет закрытие двери. Наконец, если нечаянно сам владелец замка нажал неверную входную последовательность, то он может вывести автомат из тревоги, набрав единственную верную последовательность выхода из тревоги, например, х1х2 = 11 10.

Построим граф автомата “секретный замок” для уже сформулированных данных. Вначале автомат находится в некотором начальном состоянии( S0, x1x2=00, y1y2 = 00). Набираем первый набор открывающей последовательности. Автомат переходит в следующее состояние(S1, y1y2=00), но в этом состоянии автомат ждет уже второй набор открывающей последовательности. Поучив его (х1х2 =11), автомат переходит в следующее состояние(S2, y1y2 =00), в котором автомат ждет третий правильный входной набор. Получив его автомат переходит в состояние S3. Но в этом состоянии автомат, уже получив всю правильную открывающую входную последовательность, должен открыть дверь (S3, y1y2= 10). При входном нейтральном наборе (00) дверь остается открытой, после нажатия любого набора (01, или 11, или 10), дверь закрывается (S0, y1y2 =00).

Рисунок 63. Описание работы по открытию замка.

Остается реализовать режимы входа в тревогу и выхода из нее. В состоянии S1 наборы 00 и 01 уже задействованы, остаются наборы 10 и 11, при них нужно реализовать переход в тревогу – состояние (S4 y1y2 =01). В состоянии S1 нейтральный набор возвращает в то же состояние S1, наборы 01 и 10 переводят автомат в состояние тревоги S4. Аналогично в состоянии S2 нейтральный набор 00 возвращает автомат в состояние S2, наборы 11 и 01 – в состояние тревоги S4.

Рисунок 64. Описание работы по правильной последовательности и формированию сигнала тревоги.

Остается реализовать поведение автомата при выходе из тревоги. В состоянии S4 набор 11 переводит автомат в состояние S5 (y! y2 = 01). Из состояния S5 набор 10 сбрасывает тревогу (S0, y1y2 =00). При остальных наборах – возврат в состояние тревоги.

Рисунок 65. Полное описание графа автомата ”Секретный замок”.

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

Рисунок 66. Таблица переходов и выходов автомата “Секретный замок”.

Полученная таблица переходов и выходов еще представлена на так называемом абстрактном уровне. Чтобы перейти к комбинационным схемам необходимо заменить абстрактные символы состояний комбинациями наборов двоичных переменных, т. е. произвести кодирование состояний автомата. Необходимое условие правильного кодирования состояний – каждому состоянию нужно поставить свой, отличный от других состояний код. Отсюда число к внутренних переменных z1z2…zk, кодирующих состояния, вычисляется по следующей формуле k=]log2(L +1)[.Состояния переменных zi представляются состояниями памяти автомата, отсюда схема последовательностного автомата выглядит следующим образом.

Первоначально проведем так называемое тривиальное кодирование состояний, состояние Si закодируем k-разрядным двоичным кодом числа i. k=]log2(5+1)[=3.

	z3	z2	z1
S0	0	0	0
S1	0	0	1
S2	0	1	0
S3	0	1	1
S4	1	0	0
S5	1	0	1

Рисунок 67. Кодированная таблица переходов и выходов.

Прежде всего обратим внимание на расстановку состояний по столбцам кодированной таблицы переходов и выходов. Они расставлены согласно их кодированию. Состояния Sx обозначают не использованные коды 110 и 111.

Итак, мы перешли от абстрактного представления автомата к системе булевых функций: первый столбец кодированной таблицы переходов и выходов представляет булеву функцию z1(t+1), второй столбец – булеву функцию z2(t+1), третий столбец – булеву функцию z3(t+1).

Чтобы построить выходные функции автомата, поступим следующим образом. Разместим состояния автомата на матрице трех переменных – z1z2z3:

Рисунок 68. Размещение состояний автомата “Секретный замок” на матричной форме переменных z1, z2, z3.

Функция у1 принимает единичное значение на единственном наборе, соответствующему состоянию S3 – это набор 011. И кроме того она не определена на наборах, соответствующих состояниям Sx. Функция у2 Принимает единичное значение на наборах, соответствующих состояниям S4, S5 и не определена на наборах для состояний Sx.

Рисунок 69. Выходные функции автомата “Секретного замка”.

Домашнее задание. Построить граф автомата “Секретный замок” по заданию[3, стр. 12], номер варианта определяется по i, младшая цифра задает открывающую последовательность, старшая – последовательность сброса тревоги. Построить таблицу переходов и выходов автомата, провести кодирование состояний и построить кодированную таблицу переходов и выходов. Построить функции z1,z2,z3,у1 и y2.

1

М.:
1. iОглавление
Введение 2
1. Абстрактный цифровой автомат 3
1.1. Основные определения 3
1.2. Функционирование абстрактного автомата во времени 7
1.3. Граф-схема алгоритма и построение таблицы переходов/выходов абстрактного автомата 8
1.2.1. Алгоритм получения меток состояний в ГСА для автомата Мили 9
1.2.2. Алгоритм получения меток состояний в ГСА для автомата Мура 11
2. Структурный синтез цифровых автоматов 12
2.1. Канонический метод структурного синтеза цифровых автоматов 14
2.2. Элементы памяти цифрового автомата 17
2.3. Построение расширенной таблицы переходов/выходов и логической схемы автомата Мили 20
2.4. Построение расширенной таблицы переходов/выходов и логической схемы автомата Мура 24
1. Пример проектирования цифрового автомата Мили 26
3.1. Постановка задачи 26
3.2. Алгоритм перевода целого двоичного числа в код D1 27
3.3. Пример перевода целого числа из двоичной системы счисления в код D1 28
3.4. Схема операционного автомата для перевода целого двоичного числа в код D1. 29
3.5. Кодированная ГСА 31
3.6. Создание универсальных внешних переменных 34
3.7. Расширенная таблица переходов/выходов 41
3.8. Определение функций возбуждения элементов памяти 42
3.9. Кодирование микрокоманд 44
3.10. Логическая схема управляющего автомата Мили в булевом базисе 45
4. Пример проектирования управляющего автомата Мура 47
5. Реализация цифровых автоматов на базе ПЛМ и ПЛИС 53
5.1. Матричная реализация комбинационных схем 54
5.2. Матричная реализация микропрограммных автоматов 57
5.3. Программируемые логические интегральные схемы (ПЛИС) 59
6. Представление числовой информации в ЭВМ 61
6.1. Системы счисления 61
6.2. Формы представления числовой информации в ЭВМ 64
6.2.1. Представление чисел в форме с фиксированной запятой. 65
6.2.2. Представление чисел в форме с плавающей запятой 65
7. Представление чисел со знаком в ЭВМ 67
7.1. Прямой код 68
7.2. Дополнительный код 68
7.3. Обратный код 70
8. Переполнение разрядной сетки 71
8.1. Операция сдвига 71
8.2. Модифицированные коды. 72
9. Перевод чисел из одной системы счисления в другую 73
9.1. Переводы в системах счисления с основанием кратным 74
9.2. Перевод целых чисел из D-кода в двоичную систему счисления 74
9.2.1. Схема операционного автомата для перевода целого числа из кода D4 в двоичную систему счисления 75
9.2.2. Схема операционного автомата для перевода целого числа из двоичной системы счисления в код D1 79
9.3. Перевод правильной дроби из одной системы счисления в другую 82
9.3.1. Перевод правильной дроби из кода D4 в двоичную систему счисления 83
9.3.2. Перевод правильной дроби из двоичной системы счисления в код D1 86
9.3.3. Коррекция тетрад кода D4 при сдвиге влево 89
Введение
Цифровой автомат – это устройство приема, хранения, преобразования данных, работающее автономно и возвращающее результат вычислений во внешнюю (по отношению к автомату) память. Такие устройства могут встраиваться в структуру ЭВМ для решения отдельных часто исполняемых вычислительных задач, таких как:
• стандартные алгебраические и арифметические – SIN, COS, SQRT, MIN, MAX и др.;
• стандартные строчные – выделение, удаление подстроки, проверка типа переменной и т.д.;
• нестандартные функции, в том числе описание операций и форматов ввода/вывода данных; преобразование типов данных; описание операций над данными, специфичными для конкретной системы программирования, операционной системы или типа ЭВМ.
Математическое описание цифрового автомата является теоретической основой проектирования аппаратных средств ЭВМ. По степени детализации описания ЦА различают абстрактную и структурную теорию автоматов. В абстрактной теории автомат рассматривают его как “черный ящик”, функционирующий во внешней среде подобно тому, как это описано в теории алгоритмов (машина Тьюринга), без исследования структуры автомата. В структурной теории исследуется структура автомата и способы ее реализации на основе теории булевых функций.
Простейшим типом дискретных цифровых автоматов являются автоматы без памяти или комбинационные схемы, реализующие булевы функции, выход которых в каждый момент времени определяется исключительно состояниями входов и не зависит от предыстории. В реальных системах поведение систем часто зависит не только от текущего состояния входов, но и от некоторой предыстории, т.е. от значений сигналов, поступавших на вход системы ранее. Такие системы называют системами с памятью.
1. Абстрактный цифровой автомат
1.1. Основные определения
Математической моделью систем с памятью является абстрактный автомат, рассматриваемый как черный ящик, имеющий один вход и один выход, рис. 1. Автомат работает в дискретном времени, принимающем целые неотрицательные значения =0,1,2,…,K. K означает общее время работы автомата.
Рис. 1.1. Изображение абстрактного автомата
Абстрактный автомат определяется кортежем , где А – множество состояний автомата, Z – множество входных слов, W – множество выходных слов, и – реализуемые в автомате отображения, .
Функционирование абстрактного автомата описывается отображениями переходов/выходов, которые определяют связи между элементами множеств A, Z, W. Описание абстрактного автомата позволяет определить его отклик на последовательно поступающие на его вход сигналы, не уточняя внутреннюю структуру автомата. Опишем элементы, которыми определяется абстрактный автомат:
• – множество состояний (алфавит состояний), содержащее не менее двух элементов, , – начальное состояние автомата. Выделение в множестве состояний начального состояния объясняется чисто практическими соображениями, связанными с необходимостью фиксировать условия начала работы дискретного устройства. Автомат с выделенным начальным состоянием называется инициальным. В каждый момент дискретного времени автомат находится в некотором состоянии .
• – множество входных сигналов (входной алфавит), .
• W={w1,w2, …, wG} – множество выходных сигналов (выходной алфавит), .
• – функция переходов, реализующая отображение пары “состояние, входной сигнал” в момент времени τ в состояние автомата в момент времени +1: ,где .
• – функция выходов для автомата Мили. Она ставит в соответствие паре “состояние автомата, входной сигнал” в момент времени некоторый выходной сигнал в этом же такте автоматного времени.
• l:A®W – функция выходов для автомата Мура, т.е.,. Это отображение в момент времени τ формирует выходной сигнал, соответствующий состоянию автомата, полученному в предыдущем такте автоматного времени.
Чтобы задать абстрактный цифровой автомат, необходимо явно описать состав всех компонент кортежа S=(A,Z,W,d,l,), т.е. входной алфавит Z, выходной алфавит W, алфавит состояний A, и определить явно отображения переходов d и выходов l. Для задания отображений используются таблицы переходов/выходов либо ориентированные графы автомата.
При табличном задании автомата отображения d и l изображаются таблицами переходов и выходов. Эти две таблицы можно совместить, получив отмеченную таблицу переходов/выходов, в которой представлены одновременно оба отображения. Отмеченные таблицы переходов/выходов абстрактных цифровых автоматов Мура и Мили представлены в табл. 1 и 2.
Табл. 1.1. Таблица переходов/выходов автомата Мили
Z
A
Табл. 1.2. Таблица переходов/выходов автомата Мура
Z
A
W
На пересечении i-й строки и j-го столбца в таблице автомата Мили записывают пару , а в таблице автомата Мура – состояние , а для записи выходных сигналов используют добавленный справа столбец выходных сигналов W.
Автомат называется полностью определенным, если функции переходов /выходов определены для всех пар . Если функции переходов и выходов определены не для всех пар , автомат называется частичным. В ячейке таблицы переходов/выходов автомата Мили, соответствующей паре , для которой переход не определен, ставится (-/-). Т.е., если не определен переход, то выход также не определен. Однако, если переход определен, то выходной сигнал может отсутствовать.
В автомате Мура, если для некоторой пары переход не определен, это не влияет на наличие выходного сигнала, зависящего по определению отображения выходов автомата Мура только от текущего состояния. Ячейка таблицы, соответствующая не определенному переходу, отмечается прочерком (-).
Большинство автоматов является частично определенными.
При задании автомата орграфом, его вершины и дуги помечают именами состояний, входных и выходных сигналов. Вершины орграфа, представляющего каждый из автоматов, обозначаются именами состояний из множества А. Графы автоматов Мили и Мура, представленные на рис. 2,3, отображают содержимое табл. 1,2.
Ориентированные ребра графа автомата Мили помечаются парой , где – сигнал, инициирующий переход из состояния в состояние , и – выходной сигнал в этом же такте автоматного времени.
Рис. 1.2. Граф автомата Мили
В графе автомата Мура входные сигналы помечают дуги, а выходной сигнал записывается непосредственно у вершины, обозначающей состояние автомата. Это отражает тот факт, что в автомате Мура выходной сигнал определяется только текущим состоянием автомата ().
Рис. 1.3. Граф автомата Мура
Автомат называется конечным, если конечны множества A,Z,W. Далее мы будем рассматривать только конечные автоматы, заданные таблицами переходов/выходов.
Автомат называется детерминированным, если выполнено условие однозначности переходов. Автомат, заданный таблицей переходов, всегда детерминированный, т.е. дуги, выходящие из вершины графа в разные вершины графа, помечаются разными входными сигналами. Автомат, заданный таблицей переходов, всегда детерминированный.
Состояние автомата называется устойчивым, если для любого входа такого, что , имеет место . Это означает, что если автомат пришел в состояние под воздействием входного сигнала , то выйти их этого состояния он может только при поступлении на вход другого сигнала.
Автомат называется асинхронным, если каждое его состояние устойчиво. В противном случае автомат называется синхронным.
Все построенные на практике автоматы – асинхронные, устойчивость их состояний достигается каким-либо способом, например, введением сигналов синхронизации.
Цифровой автомат имеет дискретное множество внутренних состояний, и переход из одного состояния в другое происходит скачкообразно. Дискретность информации, преобразуемой в автомате, проявляется в том, что она представляется посредством дискретного множества слов. Автомат функционирует в дискретном времени, т.е. изменение внутреннего состояния ЦА и выдача выходных сигналов происходит в строго определенные моменты времени, определяемые периодом синхронизирующего сигнала.
В момент времени автомат воспринимает входной сигнал , находясь в состоянии . В соответствии с функцией переходов в момент времени ( +1) автомат переходит в состояние и вырабатывает выходной сигнал в соответствии с функцией выходов: в случае автомата Мили, и в случае автомата Мура. Таким образом, автомат S отображает множество слов входного алфавита Z в множество слов выходного алфавита W.
1.2. Функционирование абстрактного автомата во времени
Построение абстрактного цифрового автомата является необходимым этапом проектирования цифрового автомата с жесткой логикой. Очевидно, что автомат не имеет интерпретации до тех пор, пока не указана структура входных и выходных сигналов и способ реализации отображения переходов/выходов. Но некоторые свойства автомата, например, функционирование цифрового автомата во времени можно промоделировать, задавая входные условия. В силу различия отображения выходов в автоматах Мили и Мура их реакция на одну и ту же входную последовательность сигналов будет различной. Рассмотрим примеры поведения во времени автоматов обоих типов.
Пусть , – множество входных сигналов, – множество состояний, – множество выходных сигналов. В каждый момент дискретного времени на единственный вход автомата поступает один из входных сигналов из последовательности . Последовательности состояний и значений выходов автомата Мили заданного табл. 1, представлены в табл. 3.
Табл. 1.3. Отклик автомата Мили на последовательность входов
t
1
2
3
4
5
6
7
8
Z
A
W
Последнее по времени состояние автомата называется заключительным. Оно относится к моменту автоматного времени, следующему за последним по времени поступления входным сигналом. Выходной сигнал в автомате Мили появляется в том же такте автоматного времени, что и инициирующий его входной сигнал.
Отклик автомата Мура на те же входы представлен в табл. 4.
Табл. 1.4. Отклик автомата Мура на последовательность входов
t
1
2
3
4
5
6
7
8
Z
A
W
В автомате Мура отклик на входной сигнал запаздывает по отношению ко входу на один такт автоматного времени. В начальном состоянии выход автомата не связан со значением входного сигнала и не определяется. Отклик автомата Мура на последний вход определяется в следующем такте автоматного времени, если определено заключительное состояние, соответствующее этому входному слову.
Множество выходных сигналов, последовательно появляющихся на выходе автомата по мере появления новых входов, называется реакцией автомата.
Автомат применим к слову, если в каждом последующем такте автоматного времени определена функция переходов для пары . В табл. 3,4 полужирным шрифтом выделены заключительное состояние и заключительный выход автоматов Мили и Мура для заданной последовательности входов.
Абстрактный автомат может быть также задан матрицей соединений. Матрица соединений абстрактного автомата является квадратной и содержит столько столбцов (строк), сколько различных состояний имеет рассматриваемый автомат. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. На пересечении i-й строки и j-го столбца матрицы записывается входной сигнал, инициирующий переход из состояния в состояние . Если матрицей соединений задан автомат Мили, то в соответствующей ячейке матрицы соединений записывают пару . В случае автомата Мура матрицу соединений дополняют столбцом справва, в ячейки которого записывают идентификаторы выходных сигналов, соответствующих состоянию автомата, обозначающему строку.
1.3. Граф-схема алгоритма и построение таблицы переходов/выходов абстрактного автомата
Цифровой автомат предназначен для решения конкретной задачи. Задача может быть решена с помощью цифрового автомата, если существует алгоритм ее решения. В предыдущем описании не указывается, каким образом таблица переходов/выходов абстрактного автомата может быть связана с алгоритмом выполняемой автоматом задачи. Рассмотрим механизм, позволяющий установить соответствие алгоритма решения задачи с таблицей переходов/выходов.
Процедура построения абстрактного автомата основана на представлении выполняемого алгоритма обработки данных на естественном языке. В качестве такого языка может быть использован язык граф-схем алгоритмов (ГСА). ГСА – это орграф, содержащий вершины трех типов: операторные, уловные и вершины «Начало» и «Конец».
В каждой операторной вершине указывают список микроопераций, выполняемых в соответствующем такте автоматного времени. Множество микроопераций (возможно одна микрооперация), указанных в операторной вершине, составляют микрокоманду, выполняемую за один такт автоматного времени. В условных вершинах записывают предикаты, логические значения которых проверяются в ходе выполнения алгоритма.
Операторная вершина имеет один вход и один выход условная вершине – один вход и два выхода. Ориентированные дуги определяют переходы в ГСА.
Алгоритм начинает работу из вершины «Начало» и заканчивает – в вершине «Конец».
Построенная таким образом ГСА называется содержательной. Чтобы построить таблицу переходов/выходов абстрактного автомата необходимо сопоставить элементам ГСА множество состояний автомата (А) и указать соответствующие им переходы в ГСА.
Множество состояний абстрактного автомата определяется с помощью алгоритмов отметки ГСА для автоматов Мили и Мура, которые будут рассмотрены ниже. Для отметки ГСА использую кодированную ГСА, в которой внутри операторной вершины записывают идентификатор микрокоманды , а в условных вершинах записывают идентификаторы проверяемых условий . Такое представление ГСА более компактно по сравнению с содержательной ГСА, но его необходимо сопровождать таблицей расшифровки всех обозначений, использованных в кодированной ГСА в соответствии с содержательной ГСА.
Построением кодированной таблицы переходов-выходов завершается этап проектирования абстрактного автомата.
1.2.1. Алгоритм получения меток состояний в ГСА для автомата Мили
Алгоритм получения меток состояний в кодированной ГСА для построения таблицы переходов/выходов абстрактного автомата Мили состоит в следующем:
• Меткой а0 отмечается вход вершины, следующей за начальной вершиной, и вход конечной вершины.
• Метками отмечаются входы всех вершин, следующих за операторными вершинами, где M – наибольший индекс состояния автомата.
• Вход вершины отмечается не более одного раза.
После того как в ГСА поставлены метки, рассматриваются следующие переходы из метки в метку :
• Условные переходы: , где содержит перечень идентификаторов условий, выполняемых при переходе из метки в метку , с инверсией или без (осведомительные сигналы), которым сопоставляется конъюнктивный терм, для перехода .
• Безусловные переходы: , где прочерку соответствует конъюнкция ранга 0, равная по определению 1.
• Переходы без образования выходного сигнала допускаются только для переходов вида: .
Далее строится таблица переходов-выходов абстрактного автомата Мили, включающая следующие столбцы:
• Первый столбец таблицы помечается меткой текущего состояния
• Второй столбец таблицы помечается меткой , в котором заканчивается переход из метки ,
• В случае безусловного перехода строка таблицы, помеченная состоянием , содержит действительно одну строку, в которой указывается состояние в которое переходит автомат в следующем такте автоматного времени.
• Если из состояния возможно несколько переходов в разные метки, включая и саму метку (условный переход), то метке соответствует множество подстрок, которые отображают различные пути перехода в соответствии со значениями проверяемых условий. Чем больше условных вершин участвует в переходах из метки , тем больше подстрок содержит данная строка.
• В следующем столбце таблицы указывается кортеж, содержащий список идентификаторов условий, выполняемых при переходе из метки в метку , с инверсией или без (осведомительные сигналы).
• Рассматриваются условные и безусловные пути перехода. Путь перехода в ГСА вида: обозначает условный переход из метки в метку . Ему сопоставляется конъюнктивный терм ранга r, содержащий идентификаторы всех условий, участвующих в переходе из состояния в данной подстроке вместе с их логическими значениями на рассматриваемом переходе, r – число условных вершин в соответствующем переходе. Если какой-либо переход включает одну и ту же переменную с разными логическими значениями, то он не рассматривается. Безусловному переходу сопоставляется пустая конъюнкция, равная по определению 1.
• В автомате Мили реализуется отображение выходов вида: , где А – множество состояний автомата, Z – множество входов, W – множество выходов. Отсутствие выходного сигнала в условном переходе допускается только для путей вида . Поэтому при перемещении по цепочке условий автомат не может остановиться на метке, отличной от , поставленной после условной вершины, так как в этом случае выходной сигнал не может быть определен.
Структура таблицы переходов-выходов абстрактного автомата Мили представлена в табл. 5.
Табл. 1.5. Таблица переходов/выходов абстрактного автомата Мили
x1x2…xn
В первом столбце таблицы находятся обозначения состояний, из которых начинается переход, во втором – обозначения состояний, в которых переход заканчивается. В столбце указываются значения предикатов, участвующих в данном переходе. – код выходного сигнала для соответствующей строки.
Построением таблицы переходов/выходов завершается проектирование абстрактного автомата Мили.
1.2.2. Алгоритм получения меток состояний в ГСА для автомата Мура
Для создания таблицы переходов/выходов автомата Мура необходимо выполнить следующий алгоритм отметки кодированной ГСА:
1. отметить все операторные вершины, поставив в соответствие каждой операторной вершине некоторое состояние – идентификатор метки;
2. если в ГСА имеются одинаковые операторные вершины (в них записана одна и та же микрокоманда), им сопоставляются разные метки, означающие разные состояния автомата;
3. начальной и конечной вершинам присваивается метка .
Далее построение таблицы переходов-выходов включает следующие этапы:
• просматриваются все пути перехода между смежными операторными вершинами из в вида , где – имена всех предикатов, логические значения которых σi1,σi2,…,σik проверяются на переходе из метки в .
• каждому пути из вершины в вершину сопоставляется конъюнкция ранга k всех предикатов, проверяемых на этом переходе; при этом переменная входит в конъюнкцию с отрицанием, если (этому пути соответствует выход из условной вершины , помеченный значением 0), и без отрицания – в противном случае. Если k=0 , то имеет место безусловный переход из в . Если в путь X(am,as) содержит вхождения какой-либо переменную одновременно с отрицанием и без него, то соответствующий переход при проектировании автомата не рассматривается;
• метка соответствует состоянию автомата в момент времени , а метка – состоянию автомата в момент времени τ+1;
• строится таблица переходов/выходов автомата Мура, в которой перечисляются все пути переходов между отметками в ГСА; каждому состоянию автомата сопоставляется выходной сигнал, вырабатываемый в данном такте автоматного времени.
В таблице 1 представлена структура таблицы переходов/выходов абстрактного автомата Мура.
Табл. 1.6. Таблица переходов-выходов абстрактного автомата Мура
x1x2…xn
В столбце табл. 6 указаны идентификатор текущего состояния автомата и значение текущего выходного сигнала. Таким образом, в табл. 6 представлено отображение выходов автомата Мура, имеющего вид: λ:AW, где А – множество состояний автомата, W – множество выходов. Столбец обозначает вершину, в которой переход завершается. – список осведомительных сигналов, активных в данном такте автоматного времени.
2. Структурный синтез цифровых автоматов
В структурной теории цифровых автоматов предметом проектирования и исследования является как структура входных и выходных сигналов, так и состав элементов автомата, реализующих его функции. Цифровой автомат – это автономное устройство, исполняющее алгоритм процедурного типа, называемый также операционным устройством (ОУ). Он представляет собой композицию исполнительного устройства (операционный автомат – ОА) и управляющего устройства (управляющий автомат – УА). Цифровой автомат, реализованный как автономное аппаратное средство в составе вычислительной системы, называется цифровым автоматом с жесткой логикой. Блок-схема цифрового автомата с жесткой логикой представлена рис. 1.
Рис. 2.1. Блок-схема цифрового автомата
Здесь X – множество осведомительных сигналов, Y – множество управляющих сигналов, КР – конец работы, Din – входные данные, полученные из внешней памяти, и Dout – выходные данные (результат обработки).
Обработка данных в автомате происходит с минимальным числом обращений к внешней памяти, а именно, обращение к внешней памяти происходит дважды за время работы автомата: первое обращение – получение входных данных для обработки, второе обращение – передача в память результатов обработки (конец работы автомата). Начало работы ОУ инициализируется сигналом Код команды (Запрос), поступающим из внешнего по отношению к УА устройства (например, процессора ЭВМ) на вход управляющего блока автомата с жесткой логикой, называемого Управляющим автоматом (УА). Получив Запрос, УА посылает в исполнительное устройство (ОА) управляющий сигнал по шине Y – «Управляющие сигналы», который инициирует загрузку входных данных (Din) в регистры ОА. После загрузки входных данных ОУ отключается от внешней памяти и работает автономно под управлением УА. По окончании процесса обработки, УА выдает сигнал Конец работы (КР) и отправляет в ОА команду на вывод результата во внешнюю память, через порт Dout (Выход). В УА имеется регистр состояния, в котором сохраняется текущее состояние автомата.
Операционный автомат (ОА) является исполнительной частью автомата с жесткой логикой. Коды входных и выходных данных и результаты промежуточных вычислений сохраняются в регистрах ОА, образующих сверхбыструю регистровую память. Данные о состоянии регистров или отдельных разрядов регистров в ОА образуют слово осведомительных сигналов в алфавите {0,1}, поступающих на вход УА. Последовательность выполняемых в ОА микрокоманд определяется сигналами, поступающими на вход ОА по шине Управляющие сигналы, вырабатываемые УА, которые являются в каждом такте автоматного времени результатом обработки осведомительных сигналов и кода текущего состояния автомата.
Автомат с жесткой логикой работает в дискретном времени под управлением синхронизирующего сигнала (СС), который определяет каждый момент времени натуральным числом, что позволяет по числу тактов определить реальное время, затраченное на обработку данных. В каждом такте автоматного времени УА генерирует одну микрокоманду, состоящую из одного или более микрооператоров, и по шине «Управляющие сигналы» отправляет ее в ОА. Под микрокомандой понимается множество микроопераций, выполняемых одновременно (в одном такте автоматного времени) в ОА, при условии, что эти микрооперации выполняются на разных структурных элементах ОА. Говорят, что в цифровом автомате происходит распараллеливание обработки данных за счет использования аппаратных средств ОА (сверхбыстрой регистровой памяти).
Цифровой автомат с жесткой логикой можно рассматривать как один синхронный автомат со сложно структурированной памятью, содержащей две части. Память управляющего автомата сохраняет текущее состояние автомата. Память операционного автомата – это сверхбыстрая регистровая память, в которой хранятся входные данные и промежуточные результаты вычислений. Из ОА конечный результат вычислений отправляется во внешнюю память.
Управляющий автомат — это конечный автомат, задающий порядок выполнения действий в операционном автомате в соответствии с алгоритмом обработки информации. Компонентами управляющего автомата являются комбинационные схемы, регистры и логические схемы, выпускаемые промышленностью или создаваемые на базе аппаратных средств самого автомата.
Различают цифровые автоматы с жесткой логикой и микропрограммные автоматы. Цифровой автомат, реализованный в виде автономного вычислительного блока (микросхемы) в структуре ЭВМ, называется автоматом с жесткой логикой, в отличие от микропрограммных автоматов, которые выполняют те же функции с обращением к памяти в каждом такте. Автомат с жесткой логикой не позволяет оперативно вносить изменения в схему при обнаружении ошибок функционирования автомата. Микропроцессорный автомат, предложенный в 1951 году М.В. Вилкесом, моделирует цифровой автомат с помощью микроинструкций, которые хранятся в памяти процессора. Микропрограммный автомат может использоваться для тестирования и отладки структуры автомата с жесткой логикой. Так как обращение к внешней памяти требует больших затрат времени по сравнению с обращением к регистровой памяти, быстродействие автомата с жесткой логикой выше быстродействия микропрограммного автомата. Примером цифрового автомата с жесткой логикой является RISK1 –процессор.
Обработка осведомительных сигналов с созданием выходных сигналов в виде кодов микрокоманд выполняется в УА с использованием комбинационных схем и элементов памяти, в качестве которых используются триггеры. Минимизация реализуемых в УА булевых функций в классе ДНФ способствует уменьшению сложности схемы УА.
2.1. Канонический метод структурного синтеза цифровых автоматов
Канонический метод структурного синтеза УА – это метод проектирования, который состоит из четко определенной последовательности шагов, выполняемых в соответствии с таблицей переходов/выходов абстрактного автомата. Цифровой автомат или ОУ был определен выше как композиция ОА (исполнительное устройство) и УА (устройство управления процессом реализации алгоритма решения задачи, исполняемой с помощью ОУ). Проектирование ОА предваряет проектирование УА, так как на этом этапе решаются все вопросы, связанные с выбором функциональных элементов, определением их форматов, определением информационных потоков внутри ОА, назначением осведомительных сигналов (Х, рис. 4), с помощью которых реализуется алгоритм решения задачи.
Для создания цифрового автомата с жесткой логикой предварительно необходимо описать алгоритм решения задачи на естественном языке. В практике разработки цифровых автоматов с жесткой логикой языком описания задачи является граф-схема алгоритма (ГСА) решения задачи. ГСА используется для создания абстрактного автомата с заданной структурой (Мили или Мура), описанного таблицей переходов/выходов. Вслед за этапом синтеза абстрактного автомата следует этап структурного синтеза, целью которого является построение логической схемы, реализующей автомат из элементов заданного типа.
Если абстрактный автомат является математической моделью дискретной системы и может быть представлен схемой, рис. 4, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутреннее устройство на уровне комбинационных схем и регистров. Задачей структурной теории автоматов является нахождение общих приемов построения схемы УА на основе композиции элементарных автоматов (комбинационных схем и элементов памяти), из которых затем строится логическая схема автомата Мили или Мура, полученного на этапе абстрактного синтеза.
Входами УА являются осведомительные сигналы, поступающие по шине Х, рис. 4. Осведомительные сигналы по своей природе являются двоичными, поскольку каждый разряд в этой шине является логическим значением одного из предикатов, определенным в множестве {0,1}.
Выходами УА являются управляющие сигналы, также определенные в множестве {0,1}и передаваемые в ОА по шине Y, разрядность которой определяется числом различных микрокоманд, выполняемых в ОА.
Существует общий конструктивный прием (канонический метод структурного синтеза), позволяющий свести задачу структурного синтеза произвольных автоматов к задаче синтеза комбинационных схем.
Теоретическим основанием канонического метода структурного синтеза автоматов является теорема Глушкова о структурной полноте:ii Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов-выходов, и какую-либо функционально полную систему логических элементов, является структурно полной.
Комбинационная схема – это автомат с тривиальной памятью, т.е. выход комбинационной схемы зависит только от ее входа в данный момент времени и не зависит от значений предыдущих входов. В качестве автомата с нетривиальной памятью с полной системой переходов/выходов в теории автоматов используются выпускаемые промышленностью электронные схемы, называемые триггерами.
Канонический метод структурного синтеза цифровых автоматов включает следующие этапы:
• разработка граф-схемы алгоритма (ГСА), реализуемого автоматом;
• отметка (ГСА) и определение множества состояний автомата;
• проектирование абстрактного автомата.
• кодирование входных и выходных сигналов и состояний автомата
• выбор элементов памяти.
• создание расширенной таблицы переходов/выходов структурного автомата.
• выбор логического базиса для реализации УА.
• определение булевых функций возбуждения элементов памяти и выходных сигналов автомата в выбранном (заданном) логическом базисе, реализация которых превращает математическую модель автомата в функционирующее устройство, выполняющее конкретный алгоритм обработки входных данных
• построение логической схемы УА.
В расширенной таблице переходов/выходов таблица абстрактного автомата дополняется кодами состояний автомата, функциями возбуждения элементов памяти и кодами функций выходов (для автомата Мили). Полученные при этом булевы функции являются слабо определенными. Далее производится минимизация всех полученных функций в классе ДНФ. Результатом канонического метода структурного синтеза является система логических уравнений, определяющих выходные сигналы автомата и функции возбуждения элементов памяти.
Рис. 2.2. Блок-схема УА: a) автомат Мили, b) автомат Мура
В соответствии с определением отображения переходов в цифровом автомате множество внутренних переменных автомата образуется на выходах триггеров памяти в момент поступления внешних (осведомительных) сигналов из ОА. Если не принять специальных мер, то эти сигналы, попадая в этом же такте автоматного времени на вход схемы УА, могут приводить к неправильному функционированию автомата. Для правильной работы УА выходы запоминающих элементов не должны попадать на его входы в качестве внутренних переменных в текущем такте автоматного времени. Поэтому в качестве элементов памяти в УА используются автоматы Мура. Логические блок-схемы этих двух типов цифровых автоматов различаются, как показано на рис. 5.
Код микрокоманды в автоматах обоих типов можно преобразовать в единственный бит с помощью дешифратора.
2.2. Элементы памяти цифрового автомата
Триггер представляет собой автомат Мура с двумя устойчивыми состояниями, обозначаемыми как 0 и 1 (нетривиальная память). Полнота системы переходов означает, что для любой пары состояний автомата существует входной сигнал, переводящий автомат из одного состояния в другое, возможно, в исходное. Полнота системы выходов означает, что разным состояниям автомата соответствуют разные выходные сигналы. Значение выходного сигнала триггера совпадает со значением состояния, в котором находится триггер. Граф такого автомата приведен на рис 6. Вершины графа соединяются ориентированными дугами, помеченными обозначением сигнала , которые инициируют переход автомата из состояния в состояние , . На схемах триггер обозначается прямоугольником, состоящим из двух полей: в левом поле указаны информационные входы (один или два), а также входы синхронизации и начальной установки, в правом – выходы триггера и его условное обозначение “Т”. Сигналы, которые нужно подать на вход триггера, чтобы обеспечить указанные индексами направления переключения: , зависят от типа триггера. Надпись внутри вершины графа автомата означает состояние автомата, а надпись под вершиной – выходной сигнал автомата Мура.
Рис. 2.3. Обобщенная блок-схема триггера
Обозначение базового RS-триггера на схемах приведено на рис. 7.
Рис. 2.4. Обозначение RS-триггера на схемах
Кроме RS-триггера используются также JK- триггеры с двумя информационными входами и два типа триггеров с одним информационным входом, D – триггер (триггер – защелка) и T – триггер (триггер со счетным входом), рис. 8.
Рис. 2.5. Обозначения триггеров на схемах
Обозначения входов:
• R (reset) – вход установки в 0;
• S (set) – вход установки в 1;
• K – вход установки универсального триггера в состояние 0;
• J – вход установки универсального триггера в состояние 1;
• T – счетный вход;
• D (delay) – установка триггера в состояние, соответствующее логическому уровню на этом входе;
• C – управляющий (синхронизирующий вход).
• Выходы: q – прямой, – инверсный.
Кроме того у триггеров имеются входы начальной установки, не показанные на приведенных схемах:
• R0 (reset) – раздельный вход установки в 0;
• S1 (set) – раздельный вход установки в 1;
По характеру реакции на входные воздействия различают синхронные и асинхронные триггеры.
Асинхронный триггер – входные сигналы управляют состоянием триггера непосредственно с момента подачи их на входы.
Синхронный триггер – входные сигналы действуют на состояние триггера только при подаче синхроимпульса на управляющий вход С. Далее предполагается, что при проектировании автоматов применяются синхронные триггеры.
Работа триггера описывается подобно описанию комбинационной схемы таблицей истинности. Входами схемы являются значения информационных входов и текущего состояния триггера, выход триггера совпадает с состоянием, в которое триггер переходит после прихода синхронизирующего сигнала.
Рассмотрим описание и логическую схему триггера на примере базового RS-триггера.
Табл. 2.1. Таблица истинности RS триггера
0 0 0
0 0 1
1
0 1 0
0 1 1
*
1 0 0
1
1 0 1
1
1 1 0
1 1 1
*
Таблица истинности базового RS-триггера приведена в табл. 5.
Прямой выход триггера q описывается МДНФ
Схема, реализующая RS-триггер в базисе {|}, изображена на Рис. 8.
Рис. 2.6. Логическая схема RS-триггера
По характеру реакции на входные воздействия различают синхронные и асинхронные триггеры. В асинхронном триггере входные сигналы управляют состоянием триггера непосредственно с момента подачи их на входы. В синхронном – входные сигналы действуют на состояние триггера только при подаче синхроимпульса на управляющий вход С. При построении цифровых автоматов чаще используют синхронные триггеры.
При построении таблицы переходов/выходов УА удобнее пользоваться матрицей переходов триггера. Для четырех основных типов триггеров матрицы переходов приведены в табл. 6.
Табл. 2.2. Матрицы переходов JK, RS, D и Т триггеров
qt®qt+1
J
K
R
S
D
T
0 ® 0
*
*
0 ® 1
1
*
1
1
1
1 ® 0
*
1
1
1
1 ® 1
*
*
1
2.3. Построение расширенной таблицы переходов/выходов и логической схемы автомата Мили
Математическая модель автомата Мили модель содержит два отображения:
• Отображение переходов: , которому соответствуют функции , где – код состояния в момент времени , – множество внешних переменных, -состояние автомата в следующем такте автоматного времени.
• Отображение выходов: .
Блок-схема автомата Мили представлена на рис. 5,а. Отображение переходов не может быть реализовано непосредственно комбинационной схемой КС1, так как в комбинационной схеме выходной сигнал появляется в момент поступления на входы схемы всех входных сигналов (осведомительных сигналов и внутренних переменных). Поэтому реализация этого отображения состоит из двух этапов:
1. получение сигналов возбуждения элементов памяти, подаваемых на информационные входы элементов памяти;
2. переключение элементов памяти в нужное состояние после поступления на входы триггеров синхронизирующего сигнала, после которого начинается очередной такт автоматного времени.
Выходные сигналы управляющего автомата реализуются комбинационной схемой КС1 в текущем такте автоматного времени.
На первом этапе канонического метода синтеза цифровых автоматов строится таблица переходов/выходов абстрактного автомата. Затем производится расширение этой таблицы с использованием кодирования состояний и выходных сигналов автомата. Рассмотрим этот процесс применительно к автомату Мили, заданному отмеченной таблицей переходов выходов, табл. 9.
Табл. 2.3. Таблица переходов/выходов абстрактного автомата Мили
Z
A
z1
z2
z3
a0
a0/w1
a1/w2
a2/w3
a1
a1/w2
a0/w1
-/-
a2
a2/w2
a1/w3
a0/w1
Закодируем элементы множества состояний, множества входов и множества выходов двоичными последовательностями, длина которых должна быть достаточной для представления каждого элемента в каждом множестве уникальным кодом. Так как три указанных множества содержат по три элемента каждое, для кодирования символов каждого из этих множеств понадобится 2 бита.
Табл. 2.4. Таблицы кодирования состояний, входов, выходов
A
[ai]
Z
[zj]
W
[wk]
a0
00
z1
01
w1
01
a1
01
z2
10
w2
10
a2
10
z3
11
w3
11
Способ кодирования может быть выбран произвольно. Пример кодирования приведен в табл. 10.
Далее непосредственно по отмеченной таблице переходов/выходов абстрактного автомата составляется кодированная таблица переходов/выходов структурного автомата, в которой идентификаторы состояний и выходных сигналов заменены их кодами, табл. 11.
Табл. 2.5. Кодированная таблица переходов/выходов автомата Мили
Переменные , кодирующие состояния автомата, называются внутренними переменными УА, а переменные x1,x2, кодирующие входные сигналы УА, – его внешними переменными. Внешние переменные УА – это осведомительные сигналы, приходящие из ОА по шине Х. Значения внутренних переменных в каждом такте автоматного времени определяются выходами элементов памяти (они совпадают с состояниями триггеров).
В текущем такте автоматного времени на входы элементов памяти нужно подать такие сигналы (функции возбуждения элементов памяти), которые обеспечат переключение их в новое состояние после поступления синхронизирующего сигнала. В качестве элементов памяти будем использовать RS-триггеры.
Чтобы обеспечить правильное переключение элементов памяти автомата, соответствующее отображению переходов автомата, необходимо подать на информационные входы триггеров сигналы (функции возбуждения элементов памяти), обеспечивающие переход в соответствии с матрицей переходов выбранного типа триггеров, табл. 6. Следующий шаг проектирования состоит в выборе элементов памяти УА и построение расширенной таблицы переходов/выходов. Для определенности выберем в качестве элементов памяти RS – триггеры.
Коды текущего состояния УА указаны в крайнем левом столбце табл. 11. Например, выделенные ячейки табл. 11 указывают на переключение автомата из состояния с кодом (10) в состояние с кодом (01). При этом первый элемент памяти должен переключиться из состояния 1 в состояние 0, а второй элемент памяти – из состояния 0 в состояние 1.
В табл. 12, 13 приведены значения функций возбуждения элементов памяти R1S1.
Выходные сигналы элементов памяти образуют код нового состояния УА (множество внутренних переменных), который поступает на его вход вместе с множеством осведомительных сигналов () в следующем такте автоматного времени после прихода очередного синхронизирующего сигнала (СС).
Табл.2.6. Функции возбуждения первого элемента памяти, R1S1
Табл. 2.7. Функции возбуждения второго элемента памяти, R2S2
Запишем все определенные функции в привычном обозначении булевых функций, табл. 14.
Табл. 2.8. Функции возбуждения элементов памяти и функции выходов
t1t2x1x2
R1S1
R2S2
y1y2
0000
**
**
**
0001
*0
*0
01
0010
*0
01
10
0011
01
*0
11
0100
**
**
**
0101
*0
0*
10
0110
*0
10
01
0111
**
**
**
1000
**
**
**
1001
0*
*0
10
1010
10
01
11
1011
10
*0
01
1100
**
**
**
1101
**
**
**
1110
**
**
**
1111
**
**
**
Определим МДНФ обозначенных в табл. 14 функций:
;
;
;
;
;
.
Логическая схема управляющего автомата, реализованная в булевом базисе , при таком способе проектирования независимо от местности реализуемых булевых функций является двухслойной.
Для преобразования кода команды в единственный бит, управляющий инициализацией соответствующих данной микрокоманде функциональных элементов ОА, можно использовать дешифратор.
В первом слое вычисляются все конъюнктивные термы. Во втором слое находятся дизъюнкторы, вычисляющие логические значения конкретных функций. Логическая схема управляющего автомата Мили в булевом базисе представлена на рис. 10.
Рис. 2.7. Логическая схема автомата Мили
2.4. Построение расширенной таблицы переходов/выходов и логической схемы автомата Мура
Автомат Мура отличается от автомата Мили только отображением выходов: Соответственно в таблице переходов/выходов автомата Мура каждому состоянию автомата сопоставляется соответствующее значение выходного сигнала . Рассмотрим абстрактный автомат Мура, заданный табл.15. Отображение переходов автомата Мура совпадает с отображением переходов для автомата Мили, табл. 9.
Табл. 2.9. Таблица переходов/выходов абстрактного автомата Мура
Состояния автомата,
А
Входные сигналы, Z
Выходные сигналы,
W
z1
z2
z3
a0
a0
a1
a2
w1
a1
a1
a0
–
w2
a2
a2
a1
a0
w3
Произведем кодирование состояний и входов так же, как это было сделано для автомата Мили, табл. 10. Элементы множества выходов кодировать не требуется, так как пока автомат находится в некотором состоянии , код выходного сигнала совпадает с кодом текущего состояния: .
Рис. 2.8. Логическая схема автомата Мура
Так как таблица переходов в данном примере совпадает с таблицей переходов автомата Мили, то при выборе в качестве элементов памяти RS-триггеров, функции возбуждения элементов памяти будут такими же, как и определенные ранее для автомата Мили.
Блок-схема автомата Мура приведена на рис. 5b, а логическая схема автомата, заданного таблицей переходов/выходов табл. 15, – на рис. 11.
Управляющие сигналы для ОА вырабатываются на выходе дешифратора (DC), на входы которого поступают коды текущего состояния УА.
Дешифратор – это выпускаемая промышленностью комбинационная схема. Дешифратор имеет n – входов и выходов . Если все входы дешифратора определены в множестве {0,1}, то единица получается на единственном выходе, номер которого равен десятичному эквиваленту входного вектора:
Здесь n – число входов дешифратора, – десятичный номер входного вектора,
2. Пример проектирования цифрового автомата Мили
3.1. Постановка задачи
Рассмотрим применение описанного выше канонического метода структурного синтеза цифровых автоматов (ЦА). Сформулируем задачу следующим образом: построить ЦА для перевода трехразрядных целых десятичных чисел со знаком, , представленных в обратном коде, из двоичной системы счисления в код D1.
Код двоичного числа со знаком загружается в ОА после поступления кода команды на вход УА. После окончания работы автомата во внешнюю память возвращается D1 – код этого числа со знаком.
Данные для обработки – это в общем случае числа со знаком. Для кодирования знака используется один бит, помещаемый перед старшим разрядом числа. Знаковый разряд числа А обозначается SgA (от Sign).
Для представления чисел со знаком существует две формы представления: дополнительный и обратный коды.
Для представления числовой информации в ЭВМ могут использоваться различные системы счисления. Но в любом случае данные представляются двоичными словами конечной длины. Для хранения таких слов используются регистры. Регистр – линейка триггеров, число которых равно числу двоичных разрядов кода числа, включая знаковый разряд.
Код D1 – это двоично-кодированная десятичная система счисления, в которой каждая десятичная цифра кодируется двоичным словом длины 4 (тетрадой). Код использует десять допустимых кодовых комбинаций с весами разрядов в тетраде 8-4-2-1. Таким образом, код D1 трехразрядного числа содержит числовых разрядов. С учетом знака число бит в представлении десятичного числа равно 12+1=13.
Следует иметь в виду, что при использовании для представления чисел в ЭВМ любой двоично-кодированной системы счисления код числа представляется двоичным словом, хранящимся в регистре. В регистре отсутствуют какие-либо признаки, указывающие на вид системы счисления и расположение знакового разряда.
В D – кодах для представления десяти цифр используется десять кодовых комбинация из 16 возможных. Поэтому в процессе вычислений могут образовываться недопустимые в данном коде тетрады, которые требуют коррекции. Коррекции тетрад в D – кодах выполняются в ОА комбинационными схемами, т.е. автоматами без памяти.
Для представления любого числа из заданного диапазона в двоичной системе счисления потребуется бит. Следовательно, в рассматриваемом примере формат двоичного кода числа, загружаемого из внешней памяти, включает 10 числовых разрядов и один знаковый. Всего 11 разрядов.
3.2. Алгоритм перевода целого двоичного числа в код D1
Приступая к проектированию ЦА, необходимо вначале тщательно проанализировать алгоритм выполнения операции, которая должна выполняться ЦА в автономном режиме, и проверить его работу на примерах. После этого можно проектировать операционный автомат, в котором устанавливается соответствие форматов всех функциональных элементов (регистров и комбинационных схем) алгоритму решения задачи.
Рассмотренный в данном примере алгоритм перевода основан на использовании схемы Горнера, предполагающей определение десятичного эквивалента положительного числа, записанного в двоичной системе счисления, как сумму произведений всех его разрядов, умноженных на веса разрядов. Пусть – булев вектор, обозначающий числовую часть кода n+1 – разрядного положительного двоичного числа. Будем рассматривать перевод положительных чисел, т.е. SgA=0. Десятичное значение числовой части записанного таким образом положительного числа определяется как номер вектора :
Требуется построить алгоритм перевода целого двоичного числа в код D1 и возвратить полученный результат со знаком в обратном коде. Алгоритм состоит в последовательной загрузке числовых разрядов регистра двоичного кода, начиная со старшего разряда, к промежуточному значению D1-кода, находящегося в регистре РгD1. Значения весов загружаемых разрядов обеспечиваются сдвигом регистра РгD1 влево на один двоичный разряд при загрузке в него каждого очередного бита двоичного кода (микрооперация РгD1:=L(1)РгD1). Работа алгоритма перевода состоит в циклическом применении микрооперации присваивания: РгD1[12]:=РгB[0],с последующим сдвигом регистра РгD1 влево на один разряд. При этом веса всех ранее загруженных в РгD1 разрядов автоматически удваиваются. Одновременно РгВ также сдвигается на один разряд влево, обеспечивая загрузку следующего разряда двоичного числа. В каждом цикле обрабатывается один бит двоичного кода и производится коррекция всех тетрад РгD1. Число циклов назначается равным длине кода двоичного числа, в нашем случае это 10. Выполняется следующая последовательность действий:
1. загрузка двоичного кода из внешней памяти в регистр ОА (РгВ);
2. загрузка очередного бита из РгВ[0] в РгD1[12], что эквивалентно подсуммированию очередного бита к текущему значению кода D1;
3. коррекция всех тетрад кода D1 с помощью комбинационных схем во всех циклах, исключая такт подсуммирования младшего бита двоичного числа;
4. сдвиг на один разряд влево обоих регистров и переход в начало цикла, а после подсуммирования младшего бита – переход к выдаче полученного результата во внешнюю память без коррекции тетрад.
3.3. Пример перевода целого числа из двоичной системы счисления в код D1
Рассмотрим пример применения описанного алгоритма. Пусть задан десятиразрядный двоичный код целого числа без знака: В=00101100112. Такой код позволяет представить любое трехразрядное десятичное число. Десятичный эквивалент заданного числа равен 17910. Последовательность шагов, выполняемых при исполнении описанного алгоритма, представлена в табл.
Табл. 3.1. пример перевода целого двоичного числа в код D1
№
п.п.
Код D1
РгD1[0-11]
Двоичное
число,
РгВ[0-9]
Счетчик
Комментарии
1.
0000 0000 0000
0010110011
10
Задание начальных значений
2.
0000 0000 0000
9
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
3.
0000 0000 000-
010110011-
CТ=0? Нет. Тетрады кода D1 >4? Нет. Пропускаем такт коррекции. Выполняем сдвиг влево на 1 разряд обоих регистров.
4.
0000 0000 0000
8
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
5.
0000 0000 000-
10110011–
CТ=0? Нет. Тетрады кода D1 >4? Нет. Пропускаем такт коррекции. Выполняем сдвиг влево на 1 разряд обоих регистров.
6.
0000 0000 0001
7
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
7.
0000 0000 001-
0110011—
CТ=0? Нет. Тетрады кода D1 >4? Нет. Пропускаем такт коррекции. Выполняем сдвиг влево на 1 разряд обоих регистров.
8.
0000 0000 0010
6
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
9.
0000 0000 010-
110011—-
CТ=0? Нет. Тетрады кода D1 >4? Нет. Пропускаем такт коррекции. Выполняем сдвиг влево на 1 разряд обоих регистров.
10.
0000 0000 0101
5
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
11.
0000 0000 1000
CТ=0? Нет. Тетрады кода D1 >4? Младшая (третья) тетрада >4, коррекция +3.
12.
0000 0001 000-
10011—–
Сдвиг влево на 1 разряд обоих регистров.
13.
0000 0001 0001
4
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
14.
0000 0010 001-
0011——
CТ=0? Нет. Тетрады кода D1 >4? Нет. Пропускаем такт коррекции. Выполняем сдвиг влево на 1 разряд обоих регистров.
15.
0000 0010 0010
3
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
16.
0000 0100 010-
011——-
CТ=0? Нет. Тетрады кода D1 >4? Нет. Пропускаем такт коррекции. Выполняем сдвиг влево на 1 разряд обоих регистров.
17.
0000 0100 0100
2
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
18.
0000 1000 100-
11——–
CТ=0? Нет. Тетрады кода D1 >4? Нет. Пропускаем такт коррекции. Выполняем сдвиг влево на 1 разряд обоих регистров.
19.
0000 1000 1001
1
РгD1[11]:=РгВ[0]; СТ:=СТ-1;
20.
0000 1011 1100
CТ=0? Нет. Тетрады кода D1 >4? Две младших тетрады >4, коррекция +3.
21.
0001 0111 100-
1———
Сдвиг влево на 1 разряд обоих регистров.
22.
0001 0111 1001
СТ=0? ДА. Коррекции в тетрадах не выполняются. Выход из цикла.
23.
Возврат полученного D1 кода.
Из рассмотренного примера следует, что для выполнения операции потребуется два регистра, счетчик и комбинационные схемы для коррекции тетрад кода D1. Что касается самого алгоритма, важно обратить внимание на то, что после загрузки в РгD1 младшего бита двоичного кода числа коррекции тетрад и сдвиг регистра не производится.
3.4. Схема операционного автомата для перевода целого двоичного числа в код D1.
Для хранения кода двоичного числа, промежуточных значений кода D1, получаемых в процессе вычислений, и D1 кода результата используются сдвиговые регистры, обозначаемых как РгВ[] и РгD1[] соответственно. Регистр состоит из ячеек, в каждой из которых хранится один бит, соответствующий одному разряду двоичного кода. Младший разряд числа хранится в крайнем правом разряде регистра, знаковый – в крайнем левом. В обозначении регистра содержится идентификатор регистра, в рассматриваемом примере – Рг В и РгD1. В квадратных скобках, следующих за идентификатором регистра, содержится разрядный указатель, который указывает номера старшего и младшего разрядов регистра. Разрядные указатели используются также, если требуется указать, к каким разрядам регистра производится обращение в процессе обработки.
Схема ОА представлена на Рис. 12. Эта схема не содержит никаких указаний на последовательность выполнения действий над загруженными данными. Вся информация о последовательности выполняемых микроопераций содержится в логической схеме управляющего автомата. Промежуточные результаты вычислений хранятся в сверхбыстрой регистровой памяти. Обращение к внешним устройствам происходит только при загрузке данных из внешней памяти и в момент возврата результата во внешнюю память.
Этап построения ОА очень важен, так как именно в это время определяются состав и форматы всех структурных элементов схемы, определяются группы разрядов, участвующих в передачах данных при выполнении этапов алгоритма, формулируются выражения для всех предикатов, логические значения которых составляют слово в шине «Осведомительные сигналы».
Рис. 3.1. Схема операционного автомата
На схеме ОА, изображенного на рис. 12, имеются следующие функциональные элементы:
• – регистр двоичного кода;
• РгD – регистр кода D1;
• Компаратор – выпускаемая промышленностью комбинационная схема, проверяющая содержимое регистра на 0;
• Инвертор – инвертирует значения всех разрядов РгВ (по правилу инвертирования обратного кода);
• КС1 – комбинационная схема для коррекции тетрад во время выполнения алгоритма перевода;
• КС2 – комбинационная схема для инвертирования тетрад кода D1 в случае отрицательного числа.
• СТ – счетчик числа шагов алгоритма.
• TSg – триггер, сохраняющий значение знака числа.
Комбинационная схема КС1, заданная таблицей истинности, табл. 18, вносит коррекцию «+3» в каждую тетраду, десятичный эквивалент которой превышает 4.
Табл. 3.2. Функции коррекции тетрад кода D1
0000
0000
0001
0001
0010
0010
0011
0011
0100
0100
0101
1000
0110
1001
0111
1010
1000
1011
1001
1100
1010
****
1011
****
1100
****
1101
****
1110
****
1111
****
Схема операционного автомата позволяет перейти к построению содержательной граф-схемы алгоритма (ГСА), определяющей структуру управляющего автомата (УА).
3.5. Кодированная ГСА
Далее строится содержательная ГСА. Опустим эту фазу проектирования автомата и построим кодированную ГСА.
Кодированная граф-схема алгоритма (ГСА) перевода представлена на рис. 13. Построение кодированной ГСА следует логически за построением содержательной ГСА. Последняя строится после того, как построена схема операционного автомата. В операторных вершинах кодированной ГСА указаны идентификаторы микрокоманд, выполняемых в одном такте автоматного времени. Микрокоманда может содержать одну или несколько микроопераций, выполняемых на разных структурных элементах ОА.
В условных вершинах указаны идентификаторы предикатов, логические значения которых проверяются на данном шаге алгоритма.
Полный список идентификаторов, обозначающих операторные и условные вершины в кодированной ГСА, содержится в табл. 19.
Рис. 3.2. Кодированная ГСА, отмеченная для автомата Мили
Табл. 3.3. Спецификация команд в кодированной ГСА
Идентификатор микрокоманды
Состав микроопераций в микрокоманде
Содержание микрокоманды
Начало, Конец
Нет
Нет
Y1
Y11, Y12, Y13,Y14
Y11: РгB:=
Y12:CT:=10,
Y13: TSg:=0,
Y14: РгD1:=0
Y2
Y21, Y22
Y21:
Y22: TSg:=1
Y3
Y3
Y3:=L(1)РгB
Y4
Y41, Y42
Y41: РгD1[12]:=РгB[0], CT:=CT-1
Y5
Y5
Y5: [1
Y6
Y6
Y6: ШД:= РгD1
Y7
Y71, Y72
Y71: РгD1:=L(1) РгD1,
Y72: РгB:=L(1) РгB,
Y8*
Y8: [1
Условия (семантика предикатов, определяющих последовательность шагов алгоритма)
X1
X1: Проверка наличия обращения внешнего устройства к ЦА
X2
X2: РгВ=0?
X3
X3: SgB=0?
X4
X4: CT=0?
X5
X5: TSg=1?
• В микрокомандах Y5 и Y8 используется операция конкатенации («склеивания») выходных сигналов комбинационных схем КС1 и КС2 в одно слово с последующей загрузкой результата обратно в регистр, из которого эти данные получены.
• Выполнение одной или более микроопераций, выполняемых в одном такте автоматного времени возможно за счет использования сверхбыстрой регистровой памяти при условии, что все микрооперации выполняются на разных функциональных устройствах ОА.
Далее следует этап отметки ГСА в соответствии с типом проектируемого автомата (Мили или Мура). Так как в данном примере требуется спроектировать автомат Мили, воспользуемся описанным выше алгоритмом отметки. Метки состояний на рис. 14 обозначены кружочками.
На основании отмеченной ГСА строится таблица переходов/выходов абстрактного автомата Мили, табл. 20. Строки таблицы пронумерованы. Каждая строка содержит все данные для построения всех булевых функций, обеспечивающих переход автомата из состояния в состояние . Каждому состоянию в таблице соответствует одна, две или более подстрок данной строки. Одна подстрока соответствует безусловному переходу из состояния в состояние , две строки – переход управляется одним предикатом. Если при переходе проверяется более одного условия, число подстрок, соответствующих переходам из состояния , значительно возрастает.
Табл. 3.4. Таблица переходов/выходов абстрактного автомата Мили
№ п/п
строки
1
2
*
3
4
5
,
,
6
*
7
*
8
9
10
,
,
11
*
12
*
3.6. Создание универсальных внешних переменных
Следующим шагом, который полезно выполнить после построения таблицы переходов/выходов абстрактного автомата, является замена множества внешних переменных (осведомительных сигналов) на меньшее число универсальных переменных, которые будут в каждом такте автоматного времени инициировать выполнение тех же микрокоманд, что и сами осведомительные сигналы.
Сложность логических схем УА определяется числом элементов памяти, размерностью шины осведомительных сигналов Х и сложностью комбинационных схем, реализующих функции возбуждения элементов памяти и выходов УА (для автомата Мили). Оба отображения требуют построения булевых функций, местность которых равна суммарному числу внутренних и внешних переменных автомата. При решении даже простых задач число внешних переменных управляющего автомата может быть очень велико и логическая схема управляющего автомата оказывается громоздкой, требующей больших затрат аппаратных ресурсов для реализации.
Полный список всех внутренних переменных всегда входит в число аргументов всех, реализуемых в УА булевых функций, тогда как список внешних переменных в каждом такте автоматного времени составляет лишь малую часть от их общего числа. Если заменить множество внешних переменных (осведомительных сигналов) меньшим числом новых универсальных переменных, можно уменьшить местность функций, определяемых при разработке автомата. Идея такого подхода состоит в следующем.
После построения таблицы переходов/выходов абстрактного автомата находят строку с наибольшим числом внешних переменных, участвующих в переходе. Принимают число универсальных переменных равным числу предикатов в этой строке, присваивают новым переменным имена и составляют для них уравнения, которые определяют эти переменные как функции от всех внутренних переменных и всех исходных внешних переменных.
Табл. 3.5. Введение двух универсальных переменных
Функции универсальных переменных
Коды состояний
[]
–
000
110
–
–
010
–
–
011
101
–
–
001
–
–
111
Максимальное число проверяемых переменных в строках табл. 19 равно двум. Введем две универсальные переменные , задав их, как показано в табл. 20. Если логическое значение одного и того же предиката участвует в списке проверяемых переменных при переходах из разных меток , то все вхождения переменной записываются в один и тот же столбец универсальной переменной . Обозначения осведомительных сигналов, инициирующих переход из метки размещают в столбцах универсальных переменных так, чтобы число разных значений в столбцах было по возможности одинаковым. Прочерк в ячейке табл. 20 означает безусловный переход из соответствующей метки.
Данные табл. 20 определяют уравнения ДНФ для и :
,
где кратные дизъюнкции меток, из которых начинаются безусловные переходы, инвариантные к значениям осведомительных сигналов, можно объединить в отдельные дизъюнкты:
и
и переписать выражения для универсальных переменных следующим образом:
=∨
=
Каждая из универсальных переменных должна быть реализована комбинационной схемой в виде ДНФ. В рассматриваемом примере число меток в ГСА равно 7 и для кодирования состояний достаточно трех бит.Сложность ДНФ (число вхождений переменных в формулу), задающих универсальные переменные, можно минимизировать подходящим размещением меток состояний в вершинах единичного трехмерного куба
Для выбора подходящего размещения меток и последующей кодировки состояний можно использовать табличные методы минимизации булевых функций в классе ДНФ, размещая индексы меток так, чтобы метки , из которых происходят условные переходы, вошли в максимальные интервалы, включающие также метки, из которых начинаются безусловные переходы, и неиспользованные для размещения состояний ячейки таблицы. В такие интервалы не могут входить метки состояний , из которых начинаются условные переходы, инициированные предикатами, отличными от указанных в строке табл. 21, помеченной меткой . Тогда коду каждой метки будет соответствовать конституента единицы, соответствующая номеру вершины единичного k-мерного куба, в которой метка находится (k – число внутренних переменах автомата). Пример возможного размещения меток и соответствующих интервалов для приведен на рис. 14. Индексы состояний, из которых происходят условные переходы, выделены заливкой: , и . Если метки остальных состояний удается расположить таким образом, чтобы получить максимальные интервалы наименьшего ранга2, то сложность схем, реализующих универсальные переменные, можно существенно уменьшить.
Возможный вариант размещения меток в пространстве внутренних переменных УА показан на рис. 14. ТВ этом случае МДНФ для имеет вид:
Рис. 3.3. Вариант размещения меток для р1
Далее нужно проверить, подходит ли такой вариант размещения меток для . В столбце для переменной условные переходы происходят из меток и . Вариант выбора максимальных интервалов для определения МДНФ для приведен на рис. 15. Критерием пригодности полученного способа размещения является сложность МДНФ для второй универсальной переменной. Если вариант размещения удовлетворяет разработчика, он может быть принят.
Произведенное таким образом размещение меток позволяет существенно уменьшить суммарную сложность формул, реализующих универсальные переменные по сравнению с исходными формулами. Если для второй переменной первоначальное размещение меток в клетках диаграммы Вейча, оказалось не очень удачным в смысле построения МДНФ(), можно попробовать другой вариант расстановки меток для , который окажется более удачным и для .
Рис. 3.4. Определение максимальных интервалов для p2
ДНФ, реализующая p2 при выбранном размещении меток, является МДНФ и, следовательно, выбранный вариант размещения может быть принят:
После того как определены универсальные переменные кодирование состояний перестает быть произвольным, а должно соответствовать, кодам вершин единичного k-мерного куба, в которых эти метки расположены. Описанная процедура может приводить к различным вариантам кодирования состояний, что не влияет на правильность функционирования УА. Для реализации универсальных переменных в схеме УА используется еще одна комбинационная схема в дополнение к уже имеющимся, показанным на рис. 5а. Блок-схема автомата Мили, в котором производится замена внешних осведомительных сигналов универсальными переменными, приведена на рис. 16. При существующих в настоящее время технологиях реализации логических схем на комбинационных схемах не экономят, если это целесообразно с точки зрения уменьшения трудоемкости проектирования автомата в целом.
Рис. 3.5. Блок-схема автомата Мили с универсальными переменными
Существует способ уменьшения трудоемкости проектирования управляющего автомата, при котором в ГСА добавляются новые операторные вершины (пустые), которые не сопровождаются выполнением каких либо микрокоманд. Пустые операторные вершины, вводятся между последовательными условными вершинами. В результате каждый переход содержит не более одной условной вершины, а число подстрок в каждой строке переходов выходов оказывается не больше двух. При этом число состояний автомата может увеличиться, как и число внутренних переменных автомата, но суммарная трудоемкость проектирования существенно уменьшается. Если к этому добавить описанную выше методику кодирования состояний, то сложность логической схемы УА, реализующей универсальную переменную, можно существенно уменьшить.
Учитывая сказанное, введем в ГСА, рис. 14, две пустые операторные вершины, чтобы разделить пары условных вершин: () и . Соответствующая ГСА приведена на рис. 17. Первоначальное число меток равнялось 7, в результате введения двух дополнительных вершин их стало 9. Число внутренних переменных также увеличилось на 1.
Рис. 3.6. Отмеченная ГСА с пустыми операторными вершинами
Новая таблица переходов/выходов абстрактного автомата Мили представлена табл.21. Число строк таблицы возросло по сравнению с предыдущим вариантом. Но теперь каждая строка содержит одну подстроку (безусловный переход) или две подстроки (условный переход с проверкой логического значения одного предиката). Это означает, что множество внешних переменных, означающих логические значения пяти предикатов, можно заменить одной универсальной переменной.
Табл. 3.6. Таблица переходов/выходов абстрактного автомата Мили после добавления пустых операторных вершин
№ п/п
строки
1
2
*
3
4
5
*
6
*
7
8
9
*
10
*
11
12
13
14
Построим новую таблицу переходов/выходов абстрактного автомата Мили, соответствующую новой ГСА, табл. 22. В новой таблице каждая строка содержит не более двух подстрок, т.е. переход из любого состояния контролируется не более чем одной переменной (в разные моменты автоматного времени такой переменной может быть любая переменная из множества осведомительных сигналов).
Теперь можно ввести одну универсальную переменную, которая в каждом такте автоматного времени будет воспроизводить действие одной из внешних переменных в каждом такте автоматного времени в соответствии с табл.22:
Сложность полученной формулы равна .
Обозначим D= дизъюнкцию состояний, из которых начинаются безусловные переходы. Так как каждое из этих состояний инвариантно к значениям любых осведомительных сигналов, дизъюнкт D может быть добавлен как логическое слагаемое к любой из меток, из которых начинаются условные переходы. Так же, как в рассмотренном выше случае, можно произвести минимизацию функции , воспользовавшись доступным методом минимизации булевых функций в классе ДНФ.
Для кодирования 9 меток состояния автомата, рис. 16, необходимо 4 внутренних переменных. Чтобы построить формулу с минимальной сложностью, задающую универсальную переменную, можно использовать диаграмму Вейча для четырех переменных. Диаграмма Вейча, рис. 18, содержит 16 ячеек, соответствующих вершинам единичного 4-мерного куба. Так как число меток в ГСА, рис. 17, равно 9, в семи оставшихся после расстановки меток вершинах куба функция универсальной переменной p не будет определена. Эта избыточность числа ячеек диаграммы вместе с наличием в ГСА меток состояний, из которых начинаются безусловные переходы, позволяет уменьшить сложность МДНФ для р.
Далее нужно разместить метки состояний таким образом, чтобы метки , переходы из которых управляются переменными , можно было включить в интервалы диаграмм Вейча с максимальным числом ячеек, отмеченных метками , из которых начинаются безусловные переходы, а также не использованные для размещения меток ячейки диаграммы. Интервалы для меток не должны включать метки, переходы из которых управляются переменными, отличными от переменной . В приведенном на рис. 18 варианте размещения меток выделены с помощью заливки ячейки таблицы, содержащие метки состояний, из которых начинаются условные переходы. Каждая выделенная ячейка может склеиваться с любыми не окрашенными ячейками, включая пустые. Соответствующее выражение для МДНФ, задающей универсальную переменную, примет вид
Сложность полученного выражения равна , т.е. меньше полученной выше оценки сложности Комбинационная схема, задающая универсальную переменную, может быть размещена в одном блоке с электронными схемами, которые реализуют управляющий автомат.
Рис. 3.7. Вариант размещения меток для одной универсальной переменной
На этом завершается стадия проектирования абстрактного цифрового автомата.
3.7. Расширенная таблица переходов/выходов
После создания одной универсальной переменной кодирование состояний автомата определяется размещением меток состояний в ячейках диаграммы Вейча, рис. 18. Для кодирования состояний понадобилось четыре внутренних переменных и, следовательно, число элементов памяти автомата также будет равно 4. Семантика универсальной переменной определяется кодом текущего состояния автомата (множеством внутренних переменных) и множеством внешних переменных автомата, поступающих по шине осведомительных сигналов. Универсальная переменная реализуется на выходе комбинационной схемы КС2, рис. 16, входами которой являются все осведомительные сигналы и множество внутренних переменных управляющего автомата. В каждом такте автоматного времени универсальная переменная имеет смысл именно той переменной, которая управляет переходом в этом конкретном такте.
Выберем в качестве элемента памяти для управляющего автомата Т-триггер. Т-триггер – это триггер со счетным входом. Он переключается в новое состояние при подаче единицы на его единственный информационный вход.
Расширенная таблица переходов/выходов дополняется справа следующими столбцами: обозначение новой переменной (р), код состояния :
(), код состояния ), логические значения функций возбуждения для каждого элемента памяти: (T1T2T3T4), коды выходного сигнала: .
Табл. 3.7. Расширенная таблица переходов/выходов автомата Мили
№ п/п
строки
p
T1T2T3T4
y1y2y3y4
1
2
3
4
5
6
7
8
9
10
1
2
*
1
0000
0000
0001
0000
0001
0000
0001
3
4
1
0001
0000
1101
0001
1100
0110
0000
5
*
*
0010
0011
0001
0011
6
*
*
0011
1111
1100
0100
7
8
1
1111
0110
0101
1001
1010
0111
0000
9
*
*
0100
0000
0100
0110
10
*
*
0110
0011
0101
1000
11
12
1
1101
0010
0011
1111
1110
0010
0011
13
14
1
0101
0100
0000
0001
0101
0101
0110
3.8. Определение функций возбуждения элементов памяти
Определим МДНФ для управления каждым из элементов памяти в соответствии с данными 9-го столбца в Табл. 23, определяющими значения аргументов отображения переходов
Переход в новое состояние происходит после поступления единичного значения синхронизирующего сигнала на входы триггеров памяти.
В качестве примера рассмотрим построение функции , которая является единственным информационным входом триггера . Все функции, определяемые столбцами 9 и 10 Табл. 4, являются частично определенными. Для построения МДНФ этих функций используется информация о единичном и нулевом множествах вершин единичного пятимерного куба, в вершинах которого определены значения этих функций.
Для построения единичного множества зафиксируем 5-элементные кортежи , в которых принимает значения 1 (множество ) и множество вершин , в которых принимает значение 0, с помощью двоичных кодов этих вершин, полученных из данных 7-го и 6-го столбцов Табл. 4, и укажем множество восьмеричных эквивалентов этих кортежей: Значения восьмеричных номеров кортежей потребуются при определении МДНФ каждой из функций методом симметричных таблиц.
,
.
Рис. 3.8. Минимизация функции Т1
На Рис. 19 показан вариант склеивания единичных и неопределенных вершин единичного пятимерного куба для функцииТ1, которому соответствует формула
Аналогичным образом можно получить и все остальные функции, находящиеся в столбцах 9, 10 табл. 19.
Определим множества единичных и нулевых вершин единичного пятимерного куба для функций возбуждения остальных элементов памяти:
для триггера Т2:
, .
для триггера Т3:
, .
для триггера Т4:
, /
Соответствующие выражения для функций возбуждения триггеров Т2, Т3, Т4:
,
,
.
3.9. Кодирование микрокоманд
О кодировании микрокоманд имеет смысл говорить только в случае автомата Мили. Отображение выходов автомата Мили определяется как:
Если число различных микрокоманд в ГСА равно К, то длина вектора кода микрокоманды .
В пустых операторных вершинах, в которых вырабатываемый сигнал обозначен , никакие микрооперации не выполняются, как и при переходе в метку , когда переход не содержит операторную вершину. Поэтому во всех таких случаях выходной сигнал автомата Мили может быть закодирован одной и той же кодовой комбинацией. Следовательно, общее число кодируемых микрокоманд в автомате Мили на единицу больше, чем число содержательных операторных вершин. Для ГСА, рис. 17, К=8, что соответствует длине кода микрокоманды 4. Определим булевы функции, задающие вектор . Коды микрокоманд представлены в соответствующем столбце табл. 22.
Определим МДНФ, представляющие каждую из компонент кода микрокоманд подобно тому, как это было сделано для функций возбуждения элементов памяти.
,
=,
,
.
,
,
,
Используя для минимизации полученных функций симметричные таблицы, получим:
,
,
,
.
3.10. Логическая схема управляющего автомата Мили в булевом базисе
Заключительный этап проектирования управляющего автомата – построение логической схемы управляющего автомата с использованием заранее выбранной или заданной функционально полной системы булевых функций. Выберем в качестве функционально полной в системы булев базис .
Построим логическую схему автомата Мили, реализующего алгоритм перевода целого числа со знаком из двоичной системы счисления в код D1.
Схема реализует следующие функции:
• ДНФ, задающая универсальную переменную р:
1. ДНФ, задающие функции возбуждения Т-триггеров:
,
,
.
2. ДНФ, задающие код выходных сигналов
,
,
,
.
Полученные формулы содержат 28 различных элементарных конъюнкций. Следовательно, ПЛМ должна содержать не менее 28 горизонтальных шин, формирующих эти конъюнкции.
Рис. 3.9. Логическая схема УА Мили
Число входов ПЛМ определяется суммарным числом внутренних и внешних переменных УА, к которым следует добавить еще один входной полюс для универсальной переменной.
На рис. 20 представлена вентильная логическая схема автомата Мили, выполненная в булевом базисе.
4. Пример проектирования управляющего автомата Мура
Рассмотрим проектирование управляющего автомата Мура на примере рассмотренного в разделе 3алгоритма перевода целого числа из двоичной системы счисления в код D1.
Рис. 4.1. Отмеченная ГСА УА Мура
Опуская рассмотрение алгоритма перевода и построения схемы операционного автомата, которые не зависят от модели управляющего автомата, перейдем к отметке ГСА для построения автомата Мура. Согласно алгоритму отметки ГСА для автомата Мура меткой отмечаются начальная и конечная вершины. Метками отмечаются все операторные вершины. Отмеченная ГСА автомата Мура представлена на рис. 21.
Семантика операторных и условных вершин та же, что в табл. 19. Так же, как и в случае с автоматом Мили, выполним замену множества внешних переменных универсальной переменной р, добавив две пустые операторные вершины, разбивающие пары условных вершин () и (), рис. 22.
Рис. 4.2. Отмеченная ГСА автомата Мура
Опуская рассмотрение алгоритма перевода и построения схемы операционного автомата, которые не зависят от модели управляющего автомата, перейдем к отметке ГСА для построения автомата Мура. Согласно алгоритму отметки ГСА для автомата Мура меткой отмечаются начальная и конечная вершины. Метками отмечаются все операторные вершины. Отмеченная ГСА автомата Мура представлена на рис. 21.
Построим таблицу для задания универсальной переменной рв соответствии с отмеченной ГСА, в которую добавлены пустые операторные вершины, табл. 23.
Табл. 4.1. К определению универсальной переменной
Начало перехода
Универсальная переменная,
Коды состояний
0000
0001
–
0010
–
0001
1111
–
0101
–
0110
–
0111
–
1000
1100
0100
На рис. 23 представлен вариант размещения меток в диаграмме Вейча, и определены максимальные интервалы, задающие коды меток. Заливкой выделены метки состояний, из которых начинаются условные переходы. Коды состояний автомата соответствуют размещению меток на рис. 23.
Рис. 4.3. Размещение меток и определение максимальных интервалов для автомата Мура
Уравнение универсальной переменной в виде ДНФ имеет вид:
.
Сложность этой формулы равна .
Выполнив минимизацию функции в классе ДНФ, получим окончательное выражение для р=МДНФ.
.
Сложность полученной МДНФ равна .
Как и в случае автомата Мили в результате обработки меток при выбранном способе их размещения в вершинах единичного 4-мерного куба, получено ощутимое уменьшение сложности представления универсальной переменной, что уменьшает затраты аппаратных средств на создание УА.
В качестве элементов памяти выберем триггер Т и составим расширенную таблицу переходов/выходов автомата Мура, .
Табл. 4.2. Расширенная таблица переходов/выходов автомата Мура
№ п/п
строки
p
T1T2T3T4
1
2
3
4
6
7
8
9
1.
0000
0000
0011
0000
0011
2.
p
0011
0110
0100
0101
0111
3.
1
1
0010
0001
0011
4.
1
0001
1111
1110
5.
1111
0111
1100
1000
0011
6.
1
0101
0110
0011
7.
1
0110
0000
0110
8.
1
0111
1000
0111
9.
1
1000
1111
0111
10.
1100
0101
0110
1001
1010
11.
0100
0010
0001
0110
0101
Следующим этапом разработки УА является определение ДНФ для функций возбуждения всех элементов памяти и построение логической схемы управляющего автомата.
Приведем построение МДНФ(). Вначале определим множество единичных вершин единичного 5-мерного куба:
,
.
Построим МДНФ(), с помощью симметричной таблицы.
Рис. 4.4. Минимизация функции Т1
Согласно рис. 24 функция возбуждения для Т1 имеет вид:
.
Аналогичным образом находим МДНФ для Т2, Т3, Т4:
,
,
.
Теперь все готово для построения логической схемы управляющего автомата. Для получения выходных сигналов используем дешифратор.
Отображение выходов автомата Мура имеет вид:
Поэтому выходные сигналы автомата Мура кодируются в соответствии с кодами состояний в каждом такте автоматного времени. Микрокоманда, поступающая по шине управляющих сигналов в исполнительное устройство (ОА), формируются на выходе специальной комбинационной схемы (дешифратора). Выходной сигнал в каждом такте автоматного времени появляется на выходе дешифратора, номер которого соответствует номеру кода вектора состояний, поступающего на входы дешифратора.
Логическая схема автомата Мура, управляющего переводом чисел из двоичной системы счисления в код D1, приведена на рис. 25.
Соответствие выходов дешифратора кодам микрокоманд (и кодам состояний) очевидно из сопоставления табл. 24 и рис. 25.
Рис. 4.5. Логическая схема автомата Мура
5. Реализация цифровых автоматов на базе ПЛМ и ПЛИС
Проектирование цифровых устройств на базе традиционных серий ИС (вентильных схем) насчитывает более 30 лет. Проектирование схем в этом случае сопряжено с такими проблемами, как: большой размер плат, невысокая надёжность из-за значительного числа корпусов и соединений между ними, при которых теряется быстродействие устройства и возрастает энергопотребление, сложность и трудоемкость отладки и настройки таких устройств.
В последнее время все более распространенной элементной базой для разработчиков цифровых устройств становятся программируемые логические интегральные схемы (ПЛИС). В последние годы произошло резкое увеличение плотности упаковки элементов на кристалле, многие ведущие производители либо начали серийное производство, либо анонсировали ПЛИС с эквивалентной емкостью более 1 миллиона логических вентилей.
Развитие микроэлектроники привело в начале 1960-х годов к появлению ИС, которые представляют собой функциональные узлы электронной аппаратуры, все компоненты и соединительные проводники которых изготавливаются в объеме или на поверхности полупроводникового кристалла. Сложность ИС принято оценивать числом логических элементов, необходимых для выполнения ее функций. С этой точки зрения все ИС разделяются на следующие классы: МИС (1-10 ЛЭ): СИС (10-100 ЛЭ): БИС ( более 100 ЛЭ): СБИС (Свыше 1000 ЛЭ).
В зависимости от функционального назначения различают следующие БИС:
• БИС памяти – ЗУ;
• логические БИС, реализующие логические функции:
• линейные БИС, предназначенные для построения различных преобразователей информации, усилителей.
Использование логических схем большой степени интеграции неизбежно связано с возникновением избыточности возможностей, предоставляемых схемой, и реальными потребностями разработчика конкретной схемы. Уменьшить или вообще исключить избыточность при реализации нерегулярных логических схем на БИС можно путем перехода от стандартных БИС к заказным. Недостатками заказных БИС являются:
• возможное отсутствие их на момент проектирования схемы,
• высокая стоимость при малой серийности;
• как следствие малой серийности, – низкая надежность.
Применение заказных БИС оправдано при относительно высокой серийности.
Недостатки вентильных схем в значительной степени устраняются в случае использования программируемых логических матриц (ПЛМ) и программируемых логических интегральных схем (ПЛИС). Они представляют собой полупроводниковые матрицы, состоящие из базовых логических схем с унифицированной структурой соединений. Такие матричные структуры позволяют реализовывать произвольные булевы функции, число которых зависит от информационной емкости матричной схемы и сложности самих реализуемых функций. Логическая структура разрабатываемого вычислительного устройства программируется при помощи специального программного обеспечения, предназначенного для работы с конкретными типами матричных микросхем.
Выпускаемые промышленностью матричные кристаллы имеют размерность не менее 128 128. Поэтому их можно использовать их для реализации достаточно больших схем УА.
В настоящее время предпочтение при разработке электронных схем отдается программируемым логическим матрицам (ПЛМ) и программируемым логическим интегральным схемам (ПЛИС).
Программируемые логические матрицы — наиболее традиционный тип ПЛИС, имеющий программируемые матрицы “И” и “ИЛИ”. Основным отличием ПЛИС от базовых матричных кристаллов (БМК) и заказных ИС является возможность проектирования отладки и тиражирования специализированной схемы самим разработчиком непосредственно на рабочем месте. Это обусловлено как технологией изготовления ПЛИС (EPROM3/EEPROM4), так и наличием развитых средств автоматизации. Программируемые логические интегральные схемы (ПЛИС) — удобная в освоении и применении элементная база. Последние годы характеризуются резким ростом плотности упаковки элементов на кристалле, многие ведущие производители либо начали серийное производство, либо анонсировали ПЛИС с эквивалентной ёмкостью более 1 млн. логических вентилей. Цены на ПЛИС неуклонно падают. Так, ещё в 1998г. ПЛИС ёмкостью 100 тысяч вентилей стоила в Москве от 1500 до 3000 у.е., а спустя 2 года такая микросхема стоила от 100 до 350 у.е., и эта тенденция устойчива.
5.1. Матричная реализация комбинационных схем
Первым представителем большого класса программируемых логических устройств стали программируемые логические матрицы (ПЛМ). В зарубежной литературе они называются PLA — Programmable logic Array. ПЛМ используются для реализации логических функций, представленных в дизъюнктивной нормальной форме. Конъюнктивная матрица М1позволяет реализовать любой конъюнктивный терм от входных переменных . В каждой шине дизъюнктивной матрицы М2 образуется одна из заданных в форме ДНФ булевых функций . Обобщенная структура ПЛМ приведена на рис. 5.1.
Любая ДНФ системы булевых может быть реализована двухуровневой схемой, на первом уровне которой формируются все различные термы , а на втором дизъюнкции этих термов .
Рис. 5.1. Обозначение простой матричной схемы
На рис. 5.2. представлено изображение ПЛМ на схемах.
Рис. 5.2. Изображение простой матричной схемы
Блоки М1 и М2 представляют собою систему ортогональных шин, в местах пересечения которых при изготовлении схемы могут быть установлены полупроводниковые элементы – транзисторы или диоды. Каждая горизонтальная шина матрицы М1 формирует конъюнктивный терм , где , а каждая вертикальная шина матрицы М2 образует дизъюнкцию некоторых термов, полученных в матрице М1. Иначе, матрица М1 формирует H различных конъюнкций, из которых в матрице М2 реализуется М различных дизъюнкций. При построении матриц М1 и М2 используются полупроводниковые биполярные и МОП -элементы5.
Примерами реализации программируемых логических матриц являются отечественные микросхемы K556PT1, PT2, PT21. В этих микросхемах программирование осуществлялось при повышенном напряжении питания. Там, где требовалось сохранить плавкую перемычку на ее вход и выход подавалось высокое напряжение, там, где соединение не требовалось, на вход подавался потенциал корпуса (логический ноль), а на выход — напряжение питания. Перемычка из поликристаллического кремния под воздействием высокой температуры, вызванной током короткого замыкания, испарялась.
Логический элемент “И”, реализующий конъюнктивный терм в строке конъюнктивной матрицы, изображается горизонтальной линией с условно-графическим обозначением схемы И. К входам этого элемента подводится многоразрядная шина, а на выходе подключен одиночный проводник. Если входной проводник подключается к входу логического элемента “И” (перемычка сохранена), то это место обозначается черной точкой, а если соединение отсутствует (перемычка сожжена), то точка не проставляется. Аналогично обозначаются и многовходовые элементы “ИЛИ”.
Рассмотрим матричную реализацию комбинационных схем на примере системы булевых функций, представленных в ДНФ:
;
;
.
Блок-схема реализации этой системы функций на ПЛМ показана на рис.5.3. Точками на схеме обозначены места межсоединений вертикальных и горизонтальных шин, необходимые для реализации термов, входящих в систему функций. Эти межсоединения образуются в матричной структуре при программировании матрицы.
Сложность матричной реализации комбинационной схемы принято оценивать суммарной информационной емкостью (площадью) матриц, которая для структуры на Рис.2 равна
S(M) = S(M1) + S(M2) = 2LH + HM [бит]
Для сокращения требуемой информационной емкости матричной схемы при реализации системы отображений управляющего автомата нужно представить каждую функцию в МДНФ. После этого производится программирование матриц М1 и М2 с помощью таблиц программирования, как показано в табл. 5.1. В левой части таблицы в каждой строке таблицы нулями отмечаются все переменные () какого-либо конъюнктивного терма, входящие в этот терм с инверсиями, и единицами – переменные, всходящие в этот же терм без инверсии. Если какая-либо переменная не входит в конъюнктивный терм, отображаемый в этой строке, то в соответствующей ячейке в левой части таблицы ставится звездочка.
В столбцах правой части таблицы единицами указаны строки, содержащие один из конъюнктивных термов данной МДНФ (). Если какой-либо конъюнктивный терм не входит в ДНФ (), то в соответствующей ячейке столбца в правой части ставится звездочка.
Табл. 5.1. Таблица программирования ДНФ для матричной схемы
1
*
*
1
1
*
1
*
1
*
*
1
*
1
1
1
*
*
*
1
*
1
1
1
*
1
*
*
1
*
*
1
*
1
*
*
*
1
1
*
*
*
*
1
Матричная схема, реализующая три МДНФ, которая реализует функции, заданные в табл.5.1, изображена на рис. 5.3.
Рис. 5.3. Пример реализации ДНФ с помощью матричной БИС
В представленной матрице L=, H=8, M=3. Ее суммарная информационная емкость S(M) = 2LH + HM=8 + 83=88, тогда как число реально использованных соединений равно 28. Таким образом, эффективность использования матрицы составляет .
5.2. Матричная реализация микропрограммных автоматов
Проиллюстрируем матричную реализацию микропрограммного автомата, использующего в качестве элементов памяти R D-триггеров. МПА может быть реализован тривиальным образом в виде структуры, изображенной на рис. 5.4. Матрица М1 формирует термы , соответствующие строкам структурной таблицы МПА, а матрица реализует функции выходов и функции возбуждения элементов памяти для автомата Мили в виде ДНФ, представленных кратными дизъюнкциями конъюнктов ранга r, где R. В каждый конъюнкт входит полный список внутренних переменных и те внешние переменные, которые участвуют в переходах в тех строках таблицы переходов, в которых значение функции возбуждения соответствующего триггера равно 1.
Регистр представляет собой блок элементов памяти в виде D-триггеров.
Если для построения матриц используются биполярные элементы, то все вычисляемые в автомате булевы функции реализуются в булевом базисе .
Рис. 5.4. Тривиальная матричная реализация цифрового автомата с памятью
На схемах матричная схема с памятью изображается, как показано на рис. 5.5.
Рис. 5.5. Изображение матричной схемы с памятью
Достоинства такой матричной реализации очевидны. Прежде всего – это простота проектирования автомата, которое сводится к отображению структурной таблицы переходов/выходов автомата на матрицы М1 и M2. Кодирование состояний в этом случае может быть произвольным.
Потенциальную сложность схемы автомата оценивают информационной емкостью (площадью) реализующих ее матриц, которая определяется числом точек пересечения вертикальных и горизонтальных шин.
бит.
Эффективность использования матричной схемы оценивается отношением числа активных межсоединений к потенциальной емкости схемы.
5.3. Программируемые логические интегральные схемы (ПЛИС)
Программируемая логическая интегральная схема (ПЛИС) — электронный компонент, используемый для создания цифровых интегральных схем. Логика работы ПЛИС не определяется при изготовлении, а задаётся посредством программирования при проектировании. Для программирования используются программаторы и отладочные среды, позволяющие задать желаемую структуру цифрового устройства в виде принципиальной электрической схемы или программы на специальных языках описания аппаратуры: Verilog, VHDL, AHDL и др.
Альтернативой ПЛИС являются: программируемые логические контроллеры (ПЛК), базовые матричные кристаллы (БМК), требующие заводского производственного процесса для программирования; ASIC — специализированные заказные большие интегральные схемы(БИС), которые при мелкосерийном и единичном производстве существенно дороже; специализированные компьютеры, процессоры или микроконтроллеры, которые из-за программного способа реализации алгоритмов имеют меньшее быстродействие.
Основным отличием ПЛИС от базовых матричных кристаллов (БМК) и заказных ИС является возможность проектирования, отладки и тиражирования специализированной схемы самим разработчиком непосредственно на рабочем месте.
Основными преимуществами ПЛИС являются:
• высокое быстродействие;
• возможность реализации сложных параллельных алгоритмов;
• наличие средств САПР, позволяющих провести полное моделирование системы;
• возможность программирования или изменения конфигурации непосредственно в системе;
• совместимость при переводе алгоритмов на уровне языков описания аппаратуры (VHDL, AHDL, Verilog и др.)
• архитектурные особенности ПЛИС как нельзя лучше приспособлены для реализации таких операций, как умножение, свертка и т.п.
В настоящее время быстродействие ПЛИС достигло 250 –300 МГц,
Устройства на основе ПЛИС можно быстро и с малыми затратами модернизировать, не прерывая процесс эксплуатации, благодаря наличию во многих типах ПЛИС встроенных систем программирования и конфигурирования, позволяющих перепрограммировать их на месте без внешних программаторов, Уже сегодня ведущие производители программируемой логики обеспечивают поддержку upgrade ПЛИС через интернет. Кроме того, сроки проектирования и выпуска готовой продукции на ПЛИС неизмеримо меньше, чем разработка и производство заказных СБИС, что в условиях динамично изменяющегося рынка может иметь иногда решающее значение.
При одинаковом числе логических элементов в проекте стоимость суммарного числа стандартных микросхем больше, чем стоимость ПЛИС, а преимущество в стоимости заказных СБИС проявляется только при очень большом объеме производства идентичных микросхем.
Одним из мировых лидеров в области производства СБИС с программируемой логикой является американская фирма ALTERA. Быстродействие, потребление энергии, степень интеграции, стоимость делают СБИС ПЛ фирмы ALTERA идеальным средством для построения плат расширения ПЭВМ, систем управления и телекоммуникации, устройств цифровой обработки сигналов для стационарных и мобильных систем связи.
Решающую роль в расширении областей применения ПЛИС, сокращении времени и снижении трудозатрат на проектирование сыграли успехи в создании инструментальных средств для разработки и выпуска конечных изделий на ПЛИС, основу которых составляют специальные пакеты программ, обеспечивающие весь производственный цикл по созданию цифровых устройств на ПЛИС: от разработки схем до выпуска готовых изделий. ПЛИС каждой фирмы требуют применения своих программных пакетов.
Все пакеты интегрированной среды разработки цифровых устройств на ПЛИС фирмы «Altera» обеспечивают полный производственный цикл выпуска готовых цифровых устройств на ПЛИС, включающий:
• разработку проекта устройства (задание требуемой логики функционирования устройства);
• проверку корректности проекта и локализацию ошибок;
• синтез внутренней структуры устройства с минимизацией требуемых ресурсов;
• компиляцию проекта (создание файла для программирования или конфигурирования ПЛИС);
• моделирование процесса функционирования устройства, временной анализ и, наконец, программирование (конфигурирование) ПЛИС.
Имеют развитые и удобные в пользовании средства разработки проектов, в состав которых входят:
• Редактор Схем (Graphic Editor), несколько похожий на редакторы САПР печатных плат (ORCAD, PCAD), но более удобный в работе;
• Редактор Временных Диаграмм (Waveform Editor);
• Текстовый Редактор проектов на языке AHDL (Text Editor), самое мощное, но и самое сложное средство создания проектов.
• Все редакторы могут использоваться для создания различных частей основного проекта, который в этом случае должен создаваться только с помощью Редактора Схем.
• Имеют большую библиотеку элементов различного вида (логических примитивов, аналогов дискретной логики 74-й серии, параметризированных логических функций), позволяющих создавать проекты цифровых устройств любой сложности.
• Позволяют создавать проекты в виде многоуровневой иерархии вложенных функциональных модулей и создавать с помощью различных редакторов собственные библиотеки модулей, которые могут использоваться в различных проектах.
• Обеспечивают оптимальный синтез и минимизацию используемых для реализации проекта ресурсов микросхем.
• Обеспечивают проверку и локализацию ошибок при создании исходного проекта и при его компиляции. При этом учитываются формальные и эмпирические правила проектирования цифровых устройств и достаточность имеющихся ресурсов. Работоспособность успешно скомпилированного проекта гарантируется (кроме ошибок при задании разработчиком алгоритма функционирования устройства).
• Имеют возможность автоматического выбора наиболее подходящей микросхемы требуемого объема или распределения проекта между несколькими микросхемами малого объема.
• Обеспечивают возможность закрепления назначенных компилятором выводов микросхем для постоянной привязки к внешним компонентам целевого устройства или переназначения выводов.
• Имеют встроенные средства функционального и временного моделирования, обеспечивающие быструю верификацию и отладку проектов.
6. Представление числовой информации в ЭВМ
6.1. Системы счисления
Системой счисления называется совокупность приемов обозначения чисел. В общем случае, это специальный язык, в котором алфавитом являются символы, называемые цифрами, а синтаксисом правила, позволяющие однозначно сформировать запись числа. Запись числа в некоторой системе счисления называют кодом числа. Для целого числа она имеет вид
Отдельную позицию в записи числа называют разрядом, а номер позиции – номером разряда. Число разрядов в записи числа называется его разрядностью, она совпадает с длиной числа. Длина числа интерпретируется как длина разрядной сетки.
Система счисления называется однородной, если все цифры в записи числа выбираются из одного и того же алфавита, называемого базой системы счисления. Мощность алфавита называется основанием системы счисления.
Система счисления называется позиционной, если каждый разряд числа имеет вес, определяемый позицией разряда в слове и равный , . Базис системы счисления – это множество весов разрядов. Например, базис двоичной системы счисления – множество, N –множество натуральных чисел, r – число разрядов дробной части, n+1 – число разрядов целой части числа. Код числа в однородной позиционной системе счисления с основанием р в общем случае имеет вид
.
Любая система счисления, предназначенная для практического использования, должна обеспечивать:
1. Возможность представления любого числа в заданном диапазоне чисел.
2. Однозначность представления.
3. Краткость и простоту записи чисел.
4. Легкость овладения системой, простоту и удобство работы с нею.
Основными обрабатывающими информацию элементами в ЭВМ являются комбинационные схемы, а для хранения данных любых типов используются регистры. Поэтому вся обрабатываемая аппаратными средствами информация представлена двоичными кодами.
В однородных позиционных системах счисления множество весов последовательных разрядов образует геометрическую прогрессию со знаменателем p. Поэтому десятичный эквивалент числа может быть представлен суммой произведений значений каждого разряда числа на его вес следующим образом:
+.
В арифметике ЭВМ применяются также двоично-кодированные однородные позиционные системы счисления с основанием, отличным от 2. В числе таких систем счисления выделяют системы счисления с основанием . Это системы счисления с основаниями 2,4,8,16. В этих системах счисления буквы записываются двоичными словами длины 1,2,3,4 соответственно. Группы бит кодируют каждую цифру единственным образом. Такие коды не имеют избыточности. Например, в системе счисления с основанием 4 алфавитом является множество букв {0,1,2,3}. Определим десятичные эквиваленты чисел, записанных в разных системах счисления:
С двоичным числом удобно работать при поразрядных операциях, однако двоичная запись больших чисел получается довольно громоздкой. Для наиболее компактной записи чисел в алфавите {0,1} можно использовать шестнадцатеричную систему счисления, которая использует 16 цифр: {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}, каждая из которых кодируется двоичным кодом длины 4. Соответственно, основание шестнадцатеричной системы равно 16. Шестнадцатеричное число является компактным и лёгким для чтения. Его легко преобразовать в двоичное и наоборот. Каждый разряд шестнадцатеричного числа – это тетрада. Каждую тетраду легко преобразовать в двоичное число и наоборот, табл. 6.1.
Табл. 6.1 Соответствие десятичных чисел их шестнадцатеричным начертаниям и кодам
Десятичная
Шестнадцатеричная
Двоичная
0000
1
1
0001
2
2
0010
3
3
0011
4
4
0100
5
5
0101
6
6
0110
7
7
0111
8
8
1000
9
9
1001
10
A
1010
11
B
1011
12
C
1100
13
D
1101
14
E
1110
15
F
1111
Используются также двоично-кодированные десятичные системы счисления, называемые D-кодами, в которых каждая десятичная цифра кодируется четырьмя битами. В этом случае в коде образуется избыточность, связанная с возможностью выбора 16 различных кодовых слов длины 4, из которых востребованы будут только 10 кодовых комбинаций. Это создает издержки при вычислениях в этих кодах в связи с тем, что промежуточные результаты могут содержать недопустимые кодовые комбинации и требуют коррекции. С другой стороны, эти коды легко читаются. Число различных D-кодов равно , однако не все они одинаково удобны. В настоящее время используются три вида D-кодов, представленные в табл. 1-1. Коды десятичного числа А=86410 при каждого из трех представленных в табл. 6.2 кодов имеют вид:
Табл. 6.2. Двоично-кодированные десятичные системы счисления
Десятичная цифра
Код D1
8-4-2-1
Код D2
2-4-2-1
Код D4
(8-4-2-1)+3
0000
0000
0011
1
0001
0001
0100
2
0010
0010
0101
3
0011
0011
0110
4
0100
0100
0111
5
0101
1011
1000
6
0110
1100
1001
7
0111
1201
1010
8
1000
1110
1011
9
1001
1111
1100
В коде D1 разряды в каждой тетраде имеют естественные веса и тетрады читаются как обычные двоичные числа.
В коде D2 цифры 0,1,2,3,4 кодируются так же, как в коде D1. Для получения кодов цифр 5,6,7,8,9 к каждой из них прибавляется 6 с последующим кодированием результата двоичным кодом с естественными весами разрядов.
Каждая кодовая комбинация кода D4 образуется прибавлением к десятичной цифре 3 с последующим кодированием результата двоичным кодом с естественными весами разрядов. Поэтому код D4 называется кодом с избытком 3.
Коды D2 и D4 называются самодополняющимися кодами в силу зеркальной симметрии верхней и нижней частей таблицы разделенных двойной линией в табл. 2.6. Отличительным свойством этих кодов является то, что две любые цифры, сумма которых равна 9, дают сумму кодов равную 15. Обозначим – две какие-либо десятичные цифры, а их коды обозначим и . Для кодов D2 и D4 справедливо следующее:
Эти два кода очень удобны при выполнении арифметических операций в D-кодах.
6.2. Формы представления числовой информации в ЭВМ
Числа в ЭВМ представляют в формах с фиксированной и с плавающей запятой.
6.2.1. Представление чисел в форме с фиксированной запятой.
Числа с фиксированной запятой бывают двух типов. В случае целых чисел запятая фиксирована справа от младшего разряда. Диапазон представимых n-разрядных чисел, определяемый как отношение максимального числа в заданной разрядной сетке к модулю минимального представимого в этой разрядной сетке числа, равен
В случае правильных дробей запятая фиксирована слева, т.е. перед старшим разрядом числа. Диапазон представимых n-разрядных чисел определяется в этом случае как
Основное преимущество данной формы – простота арифметических операций, недостаток – слишком узкий диапазон представления чисел.
6.2.2. Представление чисел в форме с плавающей запятой
Для того чтобы автоматизировать действия по эффективному использованию всей разрядной сетки, а также значительно увеличить диапазон изображения чисел, в ЭВМ введена еще одна форма представления чисел – с плавающей точкой, или полулогарифмическая. Эта форма основана на представлении числа в форме мантиссы и порядка: .
Так как в некоторых, преимущественно англоязычных, странах при записи чисел целая часть отделяется от дробной точкой, то в терминологии этих стран фигурирует название «плавающая точка» (floating point). Так как в России целая часть числа от дробной традиционно отделяется запятой, то для обозначения того же понятия исторически используется термин «плавающая запятая», однако в настоящее время в русскоязычной литературе и технической документации можно встретить оба варианта.
Число с плавающей запятой имеет фиксированную относительную точность и изменяющуюся абсолютную. Реализация математических операций над числами с плавающей запятой в вычислительных системах может быть как аппаратная, так и программная.
Число с плавающей запятой содержит следующие компоненты:
• знак мантиссы,
• мантисса,
• знак порядка,
• порядок
В ЭВМ двоичные числа с плавающей запятой представляют в нормализованной форме, ограничивающей диапазон допустимых значений мантиссы полуинтервалом:
В отличие от чисел с фиксированной запятой, сетка чисел, которые способна отобразить арифметика с плавающей запятой, неравномерна: она более густая для чисел с малыми порядками и более редкая — для чисел с большими порядками. Но относительная погрешность записи чисел одинакова и для малых чисел, и для больших. Поэтому можно ввести понятие машинной эпсилон. Машинной эпсилон называется наименьшее положительное число ε такое, что . Это значит, что числа a и b, для которых , машина не различает.
В ЭВМ числа представляются машинным словом, имеющим для конкретной ЭВМ всегда фиксированное число разрядов (бит). Это число является одной из важнейших характеристик любой ЭВМ и называется разрядностью машины. Разные разряды слова при кодировании команд и данных имеют несовпадающие функциональные назначения. При рассмотрении их функций используют также термин «разрядная сетка машины».
В числах с фиксированной запятой положение запятой в разрядной сетке машины заранее обусловлено для всех чисел раз и навсегда. Место запятой, отделяющей целую часть числа от дробной, определяется на этапе конструирования ЭВМ. Сразу же указывается количество разрядов, отводимых для изображения целой и дробной частей.
Необходимо также упомянуть о «переполнении разрядной сетки». Переполнение разрядной сетки возникает, когда результат выполнения операции превышает максимально возможное для данной разрядности значение. Переполнение разрядной сетки порядка является в ЭВМ исключительной ситуации и специально обрабатывается либо аппаратными методами, если это предусмотрено алгоритмом, либо вырабатывается требование прерывания, которое обрабатывается либо процессором, либо программистом. Переполнение разрядной сетки мантиссы не вызывает катастрофических последствий и устраняется аппаратным методами, заложенными в алгоритм
Порядок числа – всегда целое число, представленное в двоичной системе счисления. Порядок определяет положение числа в множестве возможных значений, представимых в ЭВМ.
Мантисса предназначена для записи цифр числа, а порядок – для указания положения запятой.
Разрядная сетка машины содержит на несколько частей, положение которых определяется на этапе разработки: один разряд – для кодирования знака числа, n разрядов – для записи мантиссы; один разряд – для записи знака порядка, k разрядов – для записи порядка
Знак порядка определяет, является ли число целым или дробным, а знак мантиссы определяет знак всего числа.
Порядок числа определяет положение запятой в записи мантиссы. При изменении порядка соответствующим образом меняется и положение запятой – запятая как бы «плавает». Отсюда и название метода представления чисел.
Для повышения точности представления чисел используется запись чисел с двойной точностью. В этом случае число записывается не в одной, а в двух подряд идущих ячейках памяти, причем вторая ячейка используется для записи последующих цифр мантиссы.
В случае k-разрядной сетки порядка (k числовых разрядов) порядок принимает значения –(2k-1) £ П £ 2k-1. Поэтому диапазон представимых чисел в форме с плавающей запятой в случае нормализованного представления равен
Последнее выражение показывает, что диапазон представимых чисел в этом случае определяется разрядностью порядка. Мантисса же определяет точность представления чисел. Вычисления в форме с плавающей запятой являются принципиально не точными. Ошибка вычислений связана, с одной стороны, с погрешностью исходного представления числа, обусловленная ограниченностью разрядной сетки мантиссы, и с другой стороны, с алгоритмическими особенностями выполнения операций с плавающей запятой.
7. Представление чисел со знаком в ЭВМ
Важнейшей функцией большинства вычислительных устройств является выполнение арифметических операций, аргументами которых являются числа со знаком.
Для кодирования знака числа А используется один бит, который обозначается SgA.
В формате регистра знаковому разряду отводится определенное место.
Для позиционных систем счисления с естественными весами разрядов все допустимые числа являются полиномами по основанию системы счисления (p). Все арифметические операции выполняются по правилам алгебраического сложения, умножения и деления полиномов.
Основной операцией в ЭВМ является операция сложения. В арифметических устройствах последовательного действия производится последовательное суммирование всех n разрядов и слагаемых А и В, причем в сложении могут участвовать только числа с фиксированной запятой (мантиссы и порядки), которые могут иметь четыре различных комбинации знаков слагаемых. В составе функциональных устройств операционного автомата для сложения используются только сумматоры. Поэтому правильный результат операции сложения может быть получен только при условии соответствующего кодирования чисел со знаком.
Для представления чисел со знаком применяют три вида кодов. Правило записи чисел со знаком не зависит от того, в каком месте фиксирована запятая. Мы будем в дальнейшем подразумевать, что запятая фиксирована слева от старшего разряда, имея в виду, что при выполнении действий с плавающей запятой операции сложения, умножения, деления выполняются над мантиссами, а порядки в соответствии с логикой операции выравниваются, складываются или вычитаются. Для представления чисел со знаком существует три кода: прямой, дополнительный и обратный. Положительные числа во всех трех кодах имеют естественную форму записи: в знаковом разряде записывают 0, а в числовой части все цифры записываются в естественной последовательности. Отличия между кодами имеются только в случае отрицательных чисел. Рассмотрим правила образования этих кодов.
7.1. Прямой код
Прямой код представляет числа со знаком в соответствии с правилом:
Знаковый разряд несет в случае прямого кода смысловую, но не арифметическую нагрузку и не может участвовать в подсуммированиях.
В прямом коде нуль имеет два представления: . Оба изображения эквивалентны.
Алгебраическое сложение в прямом коде невозможно. Поэтому прямой код не применяется для выполнения арифметических операций.
7.2. Дополнительный код
В дополнительном коде операция вычитания заменяется операцией алгебраического сложения, благодаря правилу образования дополнительного кода отрицательного числа.
Пусть число представлено в виде
и запятая фиксирована справа от младшего разряда. Тогда значение числа, записанного в системе счисления с основанием р, определяется суммированием всех разрядов числа с их весами, и его можно определить как
В случае положительного числа SgA=0 и естественная запись числа правильно его представляет. В случае отрицательного числа
и А<0. Следовательно, всегда выполняется равенство
Таким образом, правило образования дополнительного кода для целых чисел имеет вид
а для правильных дробей
где p – основание системы счисления.
При сложении знаковый разряд и цифровая часть числа рассматриваются как единое целое, т.е. знаковый разряд участвует во всех операциях как числовой разряд. Правильный знак суммы получается автоматически в результате суммирования знаковых разрядов и символа переноса из числовой части, если он есть. Если образуется перенос из знакового разряда, он спадает с разрядной сетки и теряется.
Основание любой системы счисления представляется как 10. Пусть
А=–0,1101 – правильная дробь, записанная в двоичной системе счисления. Дополнительный код определится следующим образом:
–
10.0000
0.1101
1.0011
Общее правило образования дополнительного кода, не зависящее от положения запятой в числе: чтобы получить дополнительный код числа А, достаточно инвертировать все цифры в естественной записи числа, включая знаковый разряд, до последней значащей цифры. Последняя значащая цифра не инвертируется.
Чтобы инвертировать отрицательное число, записанное в дополнительном коде, достаточно выполнить обратную операцию, т.е. проинвертировать все цифры в записи числа, включая знаковую, за исключением последней значащей цифры.
Если при сложении двух чисел образуется перенос из знакового разряда, то единица переноса теряется.
Примеры алгебраического сложения в дополнительном коде:
7.3. Обратный код
Если знаковый разряд имеет вес , то количественный эквивалент целого (n+1)-разрядного числа А, заданного в системе счисления с основанием p, определяется как
Коды правильных дробей в обратном коде образуются в соответствии с правилом:
где n – число разрядов в записи числа после запятой, р – основание системы счисления.
Преимуществом обратного кода перед дополнительным является простая связь с естественной записью числа. Для образования обратного кода отрицательного числа необходимо просто проинвертировать все цифры в естественной записи числа, включая знаковую независимо от положения запятой в числе (справа от младшего разряда или слева от старшего разряда). Для обратного преобразования обратного кода отрицательного числа в естественную форму нужно проделать то же преобразование.
Операция алгебраического сложения в обратном коде так же, как в дополнительном, приводит автоматически к получению результата в обратном коде с правильным знаком. В отличие от сложения в дополнительном коде единица переноса, спадающая со знакового разряда, не теряется, а подсуммируется в младший разряд суммы. Примеры алгебраического сложения:
Из правила образования обратного кода следует, что для получения дополнительного кода отрицательного двоичного числа достаточно прибавить 1 в младший разряд его обратного кода.
Сформулированные правила справедливы для любой системы счисления. Необходимо иметь в виду, что в системе счисления с любым основанием разряды, занимающие позиции знакового разряда (слева от старшего разряда числа), складываются как двоичные.
8. Переполнение разрядной сетки
При выполнении арифметических операций возможно получение результата, не помещающегося в разрядной сетке машины. Такие ситуации должны быть обработаны соответствующим образом. Прежде всего, необходимо сформулировать критерии переполнения разрядной сетки. Переполнение разрядной сетки имеет место, если:
1. при сложении чисел с одинаковым знаком получается результат другого знака;
2. при сложении двух чисел имеется перенос из старшего числового разряда в знаковый разряд, но отсутствует перенос из знакового разряда;
3. при сложении двух чисел имеет место перенос из знакового разряда, но отсутствует перенос из старшего числового разряда в знаковый;
4. при наличии обоих переносов (из старшего числового разряда в знаковый и из знакового разряда) переполнение разрядной сетки отсутствует.
При наличии жестких ограничений на разрядность аппаратных средств эти критерии позволяют обнаруживать переполнение разрядной сетки. Однако более удобный критерий переполнения имеет место при использовании модифицированных кодов.
8.1. Операция сдвига
Операция сдвига чисел часто используется при выполнении арифметических операций в операционной автомате. Если число хранится в (n+1)-разрядном регистре, и знаковый разряд находится перед старшим числовым разрядом, то для обозначения операции сдвига используются микрооперации сдвига следующего вида:
• РгА:=R(1)РгА – для обозначения сдвига на один разряд вправо;
• РгА:=L(1)РгА – для обозначения сдвига на один разряд влево.
При сдвиге на один разряд вправо все разряды числа, включая знаковый, перемещаются на одну ячейку регистра РгА вправо, и затем знаковый разряд восстанавливается на первоначальном месте. Таким образом, при сдвиге вправо в двух старших разрядах РгА образуется два одинаковых последовательно записанных разряда с одинаковым начертанием.
При сдвиге на один разряд влево цифра, записанная в старшем разряде регистра «сваливается» с разрядно сетки, а в младший разряд регистра записывается
• 0 – в случае, если число представлено в дополнительном коде;
• SgA – в случае, если число представлено в обратном коде.
Сдвиг числа вправо на k разрядов эквивалентен делению этого числа на . Сдвиг числа на k разрядов влево эквивалентен умножению этого числа на .
8.2. Модифицированные коды.
В модифицированных кодах вслед за знаковым разрядом вводится разряд переполнения, имеющий формат цифр используемой системы счисления. В двоичной системе счисления разряд переполнения занимает один бит. В десятичной и шестнадцатеричной – четыре бита. В восьмеричной – три бита. При выполнении алгебраического сложения первый знаковый разряд, он обозначается Sg1, всегда сохраняет правильное значение знака результата. Разряд переполнения, он обозначается Sg2, служит для контроля переполнения разрядной сетки.
В двоичной системе счисления запись числа в модифицированном коде имеет вид: , где точка после второго знакового разряда поставлена для обозначения границы между знаковой и числовой частями числа и служит исключительно для удобства чтения чисел, так как в разрядной сетке регистра отсутствует какой-либо разделитель этих двух частей в записи числа. Положение запятой при такой записи обозначается только в пояснениях, которые содержатся в сопровождающей документации. Собственно знаковый разряд Sg1 и разряд переполнения Sg2 содержат один бит каждый.
Критерий переполнения d разрядной сетки формулируется следующим образом: . Символ здесь имеет смысл «тогда и только тогда…».
Если 2, и =0, говорят о положительном переполнении разрядной сетки.
Если, и, говорят об отрицательном переполнении разрядной сетки.
При обработки целых чисел с фиксированной запятой переполнение разрядной сетки является фатальным и сопровождается выработкой требования прерывания.
Отрицательное переполнение разрядной сетки не требует прерывания. В этом случае результату присваивается значение 0.
При представлении чисел в форме с плавающей запятой данные представляются в нормализованном виде. Нарушение нормализации означает, что мантисса результата вычислений не удовлетворяет установленному для нее допустимому диапазону значений. Как было отмечено выше, допустимые значения нормализованной мантиссы находятся в диапазоне . Переполнение разрядной сетки мантиссы называется нарушением нормализации справа, критерием нарушения нормализации справа является .
Нарушение нормализации справа требует выполнения определенных действий: если Sg1 ¹ Sg2, необходимо выполнить арифметический сдвиг мантиссы на один разряд вправо и прибавить единицу к значению порядка. Поскольку при сложении двух чисел может произойти переполнение разрядной сетки не более, чем на один разряд, процедура нормализации при этом занимает один такт автоматного времени.
Если нарушена левая часть приведенного неравенства, говорят о нарушении нормализации слева. Критерием нарушения нормализации слева является величина: , где – старший числовой разряд мантиссы.
l=1 Û Sg2=c1. Т.е. в случае равенства значений знакового разряда и старшего числового разряда при отсутствии переполнения разрядной сетки. Очевидно, l=1 означает, что значение мантиссы меньше, чем р-1. Для нормализации числа требуется выполнить сдвиг мантиссы на один разряд влево и вычесть 1 из значения порядка. В табл 8.1 приведены правила сдвига правильной дроби при сдвигах.
Таблица 8.1 Сдвиги правильной дроби
Содержимое РгА
Результат выполнения операции
РгА:=R(1)РгА
Результат выполнения операции
РгА:=L(1)РгА
Не выполняется
Не выполняется
При представлении чисел в форме с плавающей запятой положительное переполнение разрядной сетки порядка сопровождается выработкой требования прерывания. При отрицательном переполнении разрядной сетки вырабатывается машинный нуль, т.е. порядок и мантисса обнуляются.
1. Перевод чисел из одной системы счисления в другую
Исторически существует два основных метода перевода чисел из одной системы счисления в другую: табличный и расчетный.
Табличный метод прямого перевода основан на сопоставлении таблиц соответствия чисел в разных системах счисления. Этому методу требуется большой объем памяти для хранения таблиц эквивалентных записей каждого числа в разных системах.
Алгоритмизируемые методы перевода чисел с фиксированной запятой основаны на правилах взаимного преобразования в системах с основаниями , либо на использовании схемы Горнера.
9.1. Переводы в системах счисления с основанием кратным
Расчетный метод использует представление числа в однородной позиционной системе счисления с помощью полинома, в котором слагаемые определяются произведением каждой цифры числа на ее вес в системе счисления с заданным основанием. Проще всего выполняется перевод между системами с основаниями, кратными . Это системы счисления с основаниями 2,4,8,16.
Для перевода из двоичной системы счисления в восьмеричную необходимо разбить целое двоичное число справа налево на кортежи по три бита в каждом и прочесть каждую тройку, как восьмеричную цифру. Если в старшей тройке число разрядов окажется меньше трех, то ее дополняют слева нулями. Например,
Чтобы перевести двоичный код в шестнадцатеричную систему счисления, надо разбить запись двоичного кода на группы по четыре бита, называемые тетрадами, справа налево, дополнив старшую тетраду нулями, если в ней окажется менее четырех разрядов, и затем прочесть каждую тетраду как шестнадцатеричную цифру. Например,
Точки в двоичных кодах поставлены исключительно для удобства чтения. Они не являются элементами числа.
Для перевода чисел, записанных в восьмеричной (шестнадцатеричной) системе, достаточно записать каждую цифру тройкой (четверкой) бит двоичного кода, убирая старшие нули как незначащие.
Для перевода правильных дробей разбиение двоичного кода на тройки (четверки) выполняют слева направо с последующей заменой каждой двоичной кодовой группы на соответствующие восьмеричные (шестнадцатеричные) цифры, дополняя исходный двоичный код справа нулями, если число разрядов младшей группы меньше 3 (4) бит.
Для определения алгоритма перевода чисел с фиксированной запятой с основанием не кратным , используют схему Горнера. Схема Горнера представляет число в виде полинома степени n, где n – количество числовых разрядов.
9.2. Перевод целых чисел из D-кода в двоичную систему счисления
Для перевода целого числа из десятичной системы счисления в двоичную систему счисления с основанием 2 поступают следующим образом. Число делят нацело на основание новой системы, запоминая остатки от деления, до получения нулевого частного. Приведем пример перевода десятичного целого 2610 в двоичную систему счисления.
Таблица 9.1. Пример перевода целого числа из десятичной системы счисления в двоичную
Номер такта
1
2
3
4
5
6
Целое число, целая часть частного
26
13
6
3
1
Остатки от деления исходного числа и частного на 2
1
1
1
1
После того как частное от деления очередного остатка станет равным нулю, запишем цифры двоичного кода из нижней строки таблицы, считывая их справа налево. Результат работы алгоритма: 2610= 110102. Для выполнения перевода понадобилось 6 тактов деления с последующим сохранением остатков от деления в каждом такте.
Алгоритм перевода целого числа, записанного в системе счисления с основанием q=10 в систему счисления с основанием р=2, основан на представлении двоичного числа взвешенной суммой его разрядов.
=
.
Если , то при каждом очередном делении текущего значения частного на образуется текущая младшая цифра двоичного кода, и результат перевода будет автоматически иметь правильный вид. Очевидно, что алгоритм перевода должен иметь циклическую структуру. В каждом цикле выполняется одна и та же процедура деления десятичного числа на 2 и запоминание очередного бита двоичного числа.
При реализации этого алгоритма для хранения кодов десятичного и двоичного чисел используются сдвиговые регистры. Благодаря этому одна и та же микрокоманда инициирует считывание и запись очередного бита во всех циклах.
9.2.1. Схема операционного автомата для перевода целого числа из кода D4 в двоичную систему счисления
Рассмотрим схему перевода целых чисел с фиксированной запятой, представленных в одном из D-кодов, в двоичную систему счисления и спроектируем схему операционного автомата, выполняющего такой перевод.
Операционный автомат является исполнительной компонентой цифрового автомата с жесткой логикой. При разработке цифрового автомата прежде всего необходимо понять алгоритм решения задачи и какие функциональные элементы потребуются для ее решения. Затем нужно определить состав функциональных элементов и выбрать подходящие форматы устройств, позволяющих решить задачу. Рассмотрим структуру алгоритма перевода числа из десятичной системы счисления в двоичную. Сформулируем задачу следующим образом: спроектировать операционный автомат для перевода целых чисел со знаком, в диапазоне значений , представленных в обратном коде, из кода D4 в двоичную систему счисления. Код десятичного числа со знаком загружается в РгD операционного автомата, рис. 9.1. После окончания работы автомата во внешнюю память возвращается двоичный код этого числа со знаком.
Код D4 – это двоично-кодированный десятичный код с избытком 3. Код D4 трехразрядного числа содержит числовых разрядов. С учетом знака число бит в представлении десятичного числа равно 12+1=13.
Для представления любого числа из заданного диапазона в двоичной системе счисления потребуется бит. Операция определяет ближайшее целое, не меньшее чем находящееся в скобках число. В рассматриваемом примере для правильного представления трехразрядного десятичного числа в двоичной системе счисления потребуется десять числовых разрядов и один знаковый. Всего 11 разрядов.
В ОА для хранения кодов двоичного числа и кода D4 используются сдвиговые регистры, обозначаемых как РгВ[] и РгD[] соответственно, рис. 9.1. Регистр состоит из ячеек, в каждой из которых хранится один бит, соответствующий одному двоичному разряду. Младший разряд числа хранится в крайнем правом разряде регистра, знаковый – в крайнем левом. В обозначении регистра содержится идентификатор регистра и разрядный указатель. Разрядный указатель записывают в квадратных скобках, следующих за идентификатором регистра. Он указывает номера старшего и младшего разрядов регистра. Если в какой-либо микрооперации участвуют все разряды числа, разрядный указатель не используется. Он нужен только в тех случаях, когда в микрооперации участвуют лишь некоторые разряды. Например, знак двоичного числа обозначается, как Sg1=РгВ[0]. Разрядные указатели используются также, если требуется указать, к каким разрядам регистра производится обращение в процессе обработки.
Так как для выполнения перевода числа из десятичной системы счисления в двоичную требуется делить десятичное число на 2, для его хранения используется сдвиговый регистр со сдвигом вправо. Пример перевода целого положительного десятичного числа в двоичную систему счисления представлен в табл. .
Работа алгоритма перевода состоит в циклическом применении микрооперации присваивания: РгB[0]:= РгD[12] с последующим сдвигом регистров РгD и РгВ на один разряд вправо и выполнения коррекции всех тетрад кода D4. В каждом цикле обрабатывается один бит десятичного кода и производится коррекция всех тетрад. Число циклов назначается равным количеству числовых разрядов кода двоичного числа, в нашем случае это 10.
Таблица 9.2. Пример перевода целого числа из кода D4 в двоичную систему счисления
Десятичное число
РгD
(код D4)
РгВ
(Двоичный)
СТ
Комментарии
27
0101.1010
*******
7
Начальные присваивания
1******
6
СТ=0? НЕТ
РгВ[0]:=¬РгD[8], CT:=CT-1
1010.11010
*1*****
РгВ:=R(1)РгВ, РгD:=R(1)РгD
13
0100.0110
РгD:=кор(РгD)
11*****
5
СТ=0? НЕТ
РгВ[0]:=¬РгD[8], CT:=CT-1
1010.00110
*11****
РгВ:=R(1)РгВ, РгD:=R(1)РгD
6
0011.1001
РгD:=кор(РгD)
011****
4
СТ=0? НЕТ
РгВ[0]:=¬РгD[8], CT:=CT-1
3
1001.11001
*011***
РгВ:=R(1)РгВ, РгD:=R(1)РгD
0011.0110
РгD:=кор(РгD)
1011***
3
СТ=0? НЕТ
РгВ[0]:=¬РгD[8], CT:=CT-1
1
1001.10110
*1011**
РгВ:=R(1)РгВ, РгD:=R(1)РгD
0011.0100
РгD:=кор(РгD)
11011**
2
СТ=0? НЕТ
РгВ[0]:=¬РгD[8], CT:=CT-1
1001.10100
*11011*
РгВ:=R(1)РгВ, РгD:=R(1)РгD
0011.0011
РгD:=кор(РгD)
011011*
1
СТ=0? НЕТ
РгВ[0]:=¬РгD[8], CT:=CT-1
1001.1001
*011011
РгВ:=R(1)РгВ, РгD:=R(1)РгD
0011.0011
РгD:=кор(РгD)
0011011
СТ=0? НЕТ
РгВ[0]:=¬РгD[8], CT:=CT-1
СТ=0? ДА. Выход из цикла
Выполняется следующая последовательность действий:
1. загрузка кода D4 десятичного числа в РгD из внешней памяти;
2. загрузка очередного бита из РгD[12] в РгВ[0] через инвертор;
3. коррекция всех тетрад кода D4 с использованием комбинационных схем КС во всех циклах;
4. сдвиг на один разряд вправо обоих регистров и переход в п.2, а при подсуммировании младшего бита – переход к выдаче полученного результата во внешнюю память без коррекции тетрад.
Схема ОА, выполняющего эту операцию, представлена на рис. 9.1. Эта схема не содержит никаких указаний на последовательность выполнения действий над загруженными данными. Вся информация о последовательности выполняемых микроопераций содержится в логической схеме управляющего автомата.
Рис. 9.1. Схема операционного автомата для перевода целого числа из кода D4 в двоичную систему счисления
На схеме, изображенной на рис. 9.1, имеются следующие функциональные элементы:
• – регистр двоичного кода;
• РгD – регистр кода D4;
• Компаратор (CPR) – выпускаемая промышленностью комбинационная схема, проверяющая содержимое регистра на 0;
• Инвертор – инвертирует значения всех разрядов РгD в начале выполнения алгоритма, и РгВ, если исходное число было отрицательным. (по правилу инвертирования обратного кода);
• КС – комбинационная схема для коррекции тетрад во время выполнения алгоритма перевода;
• СТ – счетчик числа шагов алгоритма.
• TSg – триггер, сохраняющий значение знака числа.
Промежуточные результаты вычислений хранятся в сверхбыстрой регистровой памяти. Обращение к внешним устройствам происходит только при загрузке данных из внешней памяти и в момент возврата результата во внешнюю память.
9.2.2. Схема операционного автомата для перевода целого числа из двоичной системы счисления в код D1
В рассмотренном выше алгоритме основание исходной системы счислении (q=10) больше, чем в целевой системе счисления (p=2), и разряды числа в новой системе счисления получались в правильном начертании автоматически. Теперь рассматривается случай, когда а именно, q=2, p=10. Теперь цифры числа в новой системе счисления будут получаться в виде двоичных кодов десятичных цифр.
Основанием для алгоритма перевода является схема Горнера.
Сформулируем задачу следующим образом: спроектировать операционный автомат для перевода целых чисел со знаком, в диапазоне значений , представленных в обратном коде, из двоичной системы счисления в десятичную, используя для представления десятичного числа код D1. После окончания работы автомата во внешнюю память возвращается десятичный код числа со знаком.
Код D1 – это двоично-кодированный десятичный код, использующий десять допустимых кодовых комбинаций с весами разрядов в тетраде 8-4-2-1. С учетом знака число бит в представлении десятичного числа равно 12+1=13.
Как и в рассмотренном выше примере, число разрядов, необходимое для представления любого числа из заданного диапазона значений, представленного в двоичной системе счисления, равно 11 и состоит из 10 числовых разрядов и одного знакового.
В ОА для хранения кодов двоичного числа В и десятичного числа D используются сдвиговые регистры, обозначенные на схеме, рис. 9.2, как РгВ[] и РгD[] соответственно.
Рассмотренный в данном примере алгоритм перевода основан на использовании схемы Горнера и представляет способ получения десятичного эквивалента двоичного числа как взвешенную сумму всех разрядов двоичного кода. Пусть
булев вектор, обозначающий обратный код числовой части кода n+1 – разрядного положительного двоичного числа.
Алгоритм получения десятичного эквивалента целого числа, записанного в двоичной системе счисления, состоит в последовательной загрузке числовых разрядов регистра двоичного кода, начиная со старшего разряда, к промежуточному значению D1-кода, находящегося в регистре РгD. Значения весов загружаемых разрядов возрастают по мере сдвига РгD влево на один разряд, выполняемого в каждом цикле после загрузки в него очередного бита двоичного кода (микрооперация РгD1:=L(1)РгD1).
Табл. 9.3. Пример перевода целого числа из двоичной системы счисления в код D1.
РгD1
(вычисляемый код)
РгВ
Двоичный код
СТ
Комментарии
0000.0000
0011011
7
Начальная загрузка двоичного числа. Установка счетчика
0000.0000
6
РгD[12]:=РгВ[0], Ст:=СТ -1
0000.000*
011011*
СТ¹0, РгВ:=L(1)РгВ, РгD:=L(1)РгD
0000.0000
5
РгD[12]:=РгВ[0], Ст:=СТ -1
0000.000*
11011**
СТ¹0, РгВ:=L(1)РгВ, РгD:=L(1)РгD
0000.0001
4
РгD[12]:=РгВ[0], Ст:=СТ -1
0000.001*
1011***
СТ¹0, РгВ:=L(1)РгВ, РгD:=L(1)РгD
0000.0011
3
РгD[12]:=РгВ[0], Ст:=СТ -1
0000.011*
011****
СТ¹0, РгВ:=L(1)РгВ, РгD:=L(1)РгD
0000.0110
2
РгD[12]:=РгВ[0], Ст:=СТ -1
0000.1001
РгD[]:=кор(РгD[])
0001.001*
11*****
СТ¹0, РгВ:=L(1)РгВ, РгD:=L(1)РгD
0001.0011
1
РгD[12]:=РгВ[0], Ст:=СТ -1
0010.011*
1******
СТ¹0, РгВ:=L(1)РгВ, РгD:=L(1)РгD
0010.0111
РгD[12]:=РгВ[0], Ст:=СТ -1
СТ=0. Коррекция и сдвиг не выполняются. Конец.
Работа алгоритма перевода состоит в циклическом применении микрооперации присваивания: РгD1[12]:=РгB[0],с последующим сдвигом регистра РгD влево на один разряд. При этом веса всех ранее загруженных в РгD1 разрядов автоматически удваиваются. К моменту выхода из цикла вес старшего двоичного разряда, загруженного в РгD, оказывается равным . Одновременно с регистром РгD регистр РгВ также сдвигается на один разряд влево, обеспечивая загрузку в РгD следующего разряда двоичного числа. В каждом цикле обрабатывается один бит двоичного кода и производится коррекция всех тетрад РгD1. Число циклов назначается равным количеству числовых разрядов кода двоичного числа, в нашем случае это 10. Пример перевода приведен в табл. 9. .
Выполняется следующая последовательность действий:
1. загрузка двоичного кода в регистр РгВ операционного автомата из внешней памяти;
2. загрузка очередного бита из РгВ[0] в РгD[12], что эквивалентно подсуммированию очередного бита к текущему значению кода D1;
3. коррекция всех тетрад кода D1 с использованием комбинационных схем КС1 во всех циклах, исключая такт подсуммирования младшего бита двоичного числа;
4. сдвиг на один разряд влево обоих регистров и переход в начало цикла, а при подсуммировании младшего бита – переход к выдаче полученного результата во внешнюю память без коррекции тетрад.
Промежуточные результаты вычислений хранятся в сверхбыстрой регистровой памяти. Обращение к внешним устройствам происходит только при загрузке данных из внешней памяти и в момент возврата результата во внешнюю память.
Схема операционного автомата для перевода целого числа из двоичной системы счисления в код D1 представлена на рис. 9.2.
Рис. 9.2. Схема операционного автомата для перевода целого числа из двоичной системы счисления в код D1.
На схеме, изображенной на Рис. 9.2, имеются следующие функциональные элементы:
• – регистр двоичного кода;
• РгD – регистр кода D1;
• Компаратор – выпускаемая промышленностью комбинационная схема, проверяющая содержимое регистра на 0;
• Инвертор – инвертирует значения всех разрядов РгВ (по правилу инвертирования обратного кода);
• КС1 – комбинационная схема для коррекции тетрад во время выполнения алгоритма перевода;
• КС2 – комбинационная схема для инвертирования тетрад кода D1 в случае отрицательного числа.
• СТ – счетчик числа шагов алгоритма.
• TSg – триггер, сохраняющий значение знака числа.
Комбинационная схема КС1 выполняет коррекции +3 во всех тетрадах кода D1, если десятичный эквивалент содержащихся в них кодов превышает 4.
Код D1 – это не самодополняющийся код. Поэтому инвертирование отрицательного числа выполняется отдельно в каждой тетраде собственной комбинационной схемой, обозначенной на рис. 9.2 как КС2. Для получения инверсного кода нужно к каждой тетраде прибавить 6 и затем проинвертировать результат. Инвертирование результата производится в том случае, если в регистр РгВ было загружено отрицательное число в обратном коде, и знак числа был перед выполнением перевода сохранен в специальном триггере знака, TSg.
9.3. Перевод правильной дроби из одной системы счисления в другую
Пусть имеется правильная дробь, представленная в однородной позиционной системе счисления с основанием р. Представление правильной дроби в схеме Горнера имеет вид:
(*)
Чтобы перевести правильную дробь из системы счисления с основанием q в систему счисления с основанием p, можно подобно переводу целых чисел делить обе части записанного выше выражения на р-1, т.е. умножать на р. Если умножить обе части записанного выражения на 2, получим
где – дробная часть произведения, а – целая часть результата. Полученная цифра целой части результата будет старшей цифрой искомого числа. Выполняя эту процедуру нужное число раз, получим представление правильной дроби в системе счисления с основанием p. Следовательно, при переводе выражение (*) можно представить схемой Горнера:
(**)
Умножая его последовательно k раз на основание р, получим искомое число в новой системе счисления.
В отличие от целых чисел, точный перевод возможен не для всех правильных дробей. Погрешность перевода равна половине младшего разряда дроби в новой системе счисления.
Чтобы перевести правильную дробь из позиционной системы счисления с основанием q в систему счисления с основанием р, необходимо дробную часть исходного числа последовательно умножать на основание новой системы счисления, записанное в исходной системе счисления до получения заданной точности. Дробь в новой системе счисления запишется в виде целых частей произведений, начиная с первой цифры, полученной в левой части.
Определим двоичный код правильной десятичной дроби с двумя знаками после запятой. В этом случае число двоичных разрядов, при котором точность двоичной дроби буде такой же, как и десятичной, равна семи знакам после запятой. Пример перевода показан в таблице .
Табл. 9.4. Перевод правильной дроби из десятичной системы счисления в двоичную
Целая часть
Дробная часть
37
74
1
48
96
1
92
1
84
1
68
1
36
72
Таким образом, .
Количество разрядов дроби в новой системе счисления можно определить из соотношения
Откуда
9.3.1. Перевод правильной дроби из кода D4 в двоичную систему счисления
Перевод выполняется за k тактов, где k – число двоичных разрядов, обеспечивающих точность перевода такую же, как у исходной десятичной дроби, имеющей n разрядов. Необходимое число десятичных разрядов может быть определено из выражения
где n – число разрядов десятичного числа, определяющее его точность.
Определим алгоритм перевода правильной дроби из десятичной системы счисления, представленной кодом D4, в двоичную на основании схемы Горнера (**). Определяемая им последовательность действий состоит в последовательном умножении дробной части на основание новой системы счисления, т.е. на 2, и сохранении цифр, получаемых справа от запятой. В данном алгоритме это будет бит переноса из старшего числового разряда.
Табл. 9.5. Пример перевода правильной дроби из кода D4 в двоичную систему счисления
РгВ[0-7]
РгD[0-8]
CT
Комментарии
0,37
*******
0.0110.1010
7
РгD:=РгВ:=0;CT:=7;
0.74
*******
0.1101.0100
РгD:=L(1)РгD; РгВ:=L(1)РгВ
0.1010.0111
Коррекция обеих тетрад РгD;
******0
6
РгВ[7]:=РгD[0]; CT:=CT-1;
1.48
*****0*
1.0100.1110
РгD:=L(1)РгD; РгВ:=L(1)РгВ
1.0111.1011
Коррекция обеих тетрад РгD;
*****01
5
РгВ[7]:=РгD[0]; CT:=CT-1;
0.96
****01*
0.1111.0110
РгD:=L(1)РгD; РгВ:=L(1)РгВ
0.1100.1001
Коррекция обеих тетрад РгD;
***010
4
РгВ[7]:=РгD[0]; CT:=CT-1;
1.92
***010*
1.1001.0010
РгD:=L(1)РгD; РгВ:=L(1)РгВ
1.1100.0101
Коррекция обеих тетрад РгD;
***0101
3
РгВ[7]:=РгD[0]; CT:=CT-1;
1.84
**0101*
1.1000.1010
РгD:=L(1)РгD; РгВ:=L(1)РгВ
1.1011.0111
Коррекция обеих тетрад РгD;
**01011
2
РгВ[7]:=РгD[0]; CT:=CT-1;
1.68
*01011*
1.0110.1110
РгD:=L(1)РгD; РгВ:=L(1)РгВ
1.1001.1011
Коррекция обеих тетрад РгD;
*010111
1
РгВ[7]:=РгD[0]; CT:=CT-1;
1.36
010111*
1.0011.0110
РгD:=L(1)РгD; РгВ:=L(1)РгВ
1.0110.1001
Коррекция обеих тетрад РгD;
0101111
Выход из цикла. Завершение операции
В операционном автомате, в котором выполняется операция перевода правильной десятичной дроби в двоичную систему счисления, для умножения числовой части правильной дроби, представленной в коде D1, на 2 используется сдвиговый регистр РгD со сдвигом влево на один разряд. Это возможно, так как D – код является битовой последовательностью. Если точность десятичной записи числа равна , то нужно определить двоичных цифр после запятой. Цифра переноса, образующаяся при сдвиге влево, после коррекции тетрад кода означает очередную цифру дроби в двоичной системе счисления. Для сохранения цифры переноса в РгD нужно предусмотреть дополнительный разряд слева от старшего числового разряда. Этот разряд является знаковым. Однако если рассматривать перевод только положительных чисел, то для выполнения алгоритма перевода необходимо в начале выполнения процедуры сохранить значение знакового разряда в триггере знака TSg, чтобы после окончания перевода возвратить во внешнюю память двоичное число со знаком. Этот разряд можно после сохранения знака исходного числа использовать для хранения цифры переноса из старшего числового разряда. После окончания процедуры перевода числа в новую систему счисления необходимо проверить значение знака числа и при необходимости инвертировать результат.
Для выполнения перевода удобно использовать обратный код, так как образование кода отрицательного числа состоит в инверсии всех цифр, включая знаковую цифру. Если число D отрицательное, его удобно вначале проинвертировать, чтобы можно было следить за правильностью каждой получаемой двоичной цифры. Так как код D4 самодополняющийся, для его инвертирования можно использовать 8-разрядный инвертор с одновременным обнулением РгD[0].
В табл. 9.3.1 представлен пример выполнения алгоритма перевода правильной дроби из кода D4 в двоичную систему счисления. Примем значение исходного числа равным . Для представления этого числа понадобится 8+1=9 разрядов, включая знаковый разряд. Для кода двоичного числа понадобится 8 разрядов.
В коде D4 наше число будет иметь вид:. Исходное число со знаком загружается в РгD, Двоичный код записывается в РгВ последовательно разряд за разрядом, начиная со старшего разряда, путем сдвига РгВ влево. В таблице, представляющей алгоритм перевода, будем также записывать результат умножения десятичного числа на 2 в десятичной системе счисления (столбец ), чтобы контролировать результат выполнения операций сдвига и коррекции в коде D4. Таблица также содержит столбец СТ, в котором отображается число оставшихся тактов. Критерием завершения операции перевода является обнуление счетчика (СТ=0).
Схема операционного автомата для выполнения рассмотренной операции приведена на рис. 9.3.
Рис. 9.3. Схема ОА для перевода правильной дроби из кода D4 в двоичную систему счисления
В этой схеме два варианта возвращения результата во внешнюю память (В ШД). Если во внешнюю память возвращается положительный результат, то он уходит из РгВ. Если же возвращается отрицательный результат, то он загружается вначале в РгD, инвертируется и поступает снова в РгD, и уже оттуда во внешнюю память.
9.3.2. Перевод правильной дроби из двоичной системы счисления в код D1
Для перевода правильной дроби из двоичной системы счисления в десятичную нужно умножать ее дробную часть на основание новой системы счисления, записанное в исходной, т.е. двоичной системе счисления, до тех пор, пока не будет получена требуемая точность перевода. Особенностью этой схемы является то, что для умножения дробной части двоичного числа на основание новой системы счисления нельзя как в трех рассмотренных выше схемах использовать только сдвиговые регистры, так как никакая целая степень 2 не равна 10. Умножение на 10 в данной схеме заменено сложением, учитывая, что . Во время выполнения умножения на двоичный код десяти фактически выполняется вычисление2В и 8В. Эти значения можно получить с использованием сдвигового регистра, если на регистре РгВ выполнить два сдвига: сначала на один разряд, а потом еще на два разряда, последовательно подсуммируя получающиеся коды с помощью двоичного сумматора.
Пусть В – правильная двоичная дробь. В рассматриваемом алгоритме в цикле выполняется операция:
В результате сложения целых частей слагаемых и , записанных в двоичных кодах, в четырех старших разрядах сумматора получается десятичная цифра в двоичной кодировке. Поскольку веса разрядов в данном случае имеют естественные значения, то в четырех разрядах целой части числа 10В, находящихся слева от запятой, веса разрядов будут иметь 8-4-2-1, т.е. как в D1-коде. В этом алгоритме непосредственное получение других кодов (D2 и D4) невозможно. Если это требуется по условиям использования кода десятичного числа, перевод его в коды D2 или D4 из кода D1 можно получить с помощью специальных комбинационных схем.
Рассмотрим пример перевода двоичного кода правильной дроби в код D1. Для получения исходной двоичной дроби для перевода рассчитаем обычным образом двоичный код правильной дроби D=0.631, умножая ее дробную часть на 2, пока не получим десять цифр кода. Получим 0.63110=0,101.000.011.02.
Табл. 9.6. ОА для перевода правильной дроби из двоичной СС в код D1
№ п/п
Десятичная цифра
Эволюция дробной части двоичного числа
Комментарии
1.
0000
1010000110
Исходное число
2.
0001
0100001100
Результат сдвига L(1)B=2В
3.
0101
0000110000
Сдвиг еще на два разряда, 8В
4.
0110
0100111100
Сумма: 10В.
Старшие четыре бита дают значение старшей цифры дроби01102
5.
0000
0100111100
Формируем новое число для образования 10В
6.
0000
1001111000
Результат сдвига L(1)B=2В
7.
0010
0111101111
Сдвиг еще на два разряда, 8В
8.
0011
0001011000
Сумма: 10В.
Старшие четыре бита дают значение второй цифры дроби
9.
0000
0001011000
Формируем новое число для образования 10В
10.
0000
00101100000
Результат сдвига L(1)B=2В
11.
0000
1011100000
Сдвиг еще на два разряда, 8В
12.
0000
111001000
Сумма: 10В.
Старшие четыре бита дают значение второй цифры дроби
Используем полученный результат для выполнения примера. Загружаем это число в предварительно обнуленный регистр: РгВ[4-13]:=[B]. После этого начинается вычисление первой цифры результата. Оно включает следующие шаги:
1. Загрузка числовой части двоичной дроби в РгВ. Обнуление сумматора.
2. Сдвиг L(1)РгВ с дописыванием нулей справа.
3. Выполнение подсуммирования: СМ:=СМ+РгВ.
4. Сдвиг РгВ:=L2Рг(В).
5. Снова подсуммирование: СМ:= СМ+РгВ
6. Сохранение полученной в четырех старших разрядах сумматора тетрады в РгD.
7. Обнуление РгВ и декремент счетчика.
1. Загрузка дробной части двоичного кода, полученного на предыдущем этапе, в Ргв: РгВ[4-13]:= CM[4-13].
8. Сдвиг РгD: РгD:= L(4)РгD.10
9. Повторение всех этих этапов для получения следующей десятичной цифры.
10. Выход из цикла, когда счетчик обнулится, и завершение работы.
Рис. 9.4. ОА для перевода правильной дроби из двоичной системы счисления в код D1
9.3.3. Коррекция тетрад кода D4 при сдвиге влево
Рассмотрим пример комбинационной схемы коррекции тетрад кода D4 при сдвиге влево на один разряд. Код D4 образуется прибавлением 3 к каждой из десяти двоичных цифр с последующим кодированием результата естественным двоичным кодом с весами разрядов 8-4-2-1. Вследствие такой особенности кода схему коррекций при сдвигах кода D4 целесообразно выполнять путем непосредственного определения кода каждой тетрады, как показано в табл. .
Табл.9.7. Коррекции тетрад при сдвиге кода D4 влево на один разряд
Десятичный номер строки,
Код, полученный в результате сдвига влево,
Результат коррекции тетрады,
0.
00000
*****
1.
00001
*****
2.
00010
*****
3.
00011
*****
4.
00100
*****
5.
00101
*****
6.
00110
0011
7.
00111
0100
8.
01000
0101
9.
01001
0110
10.
01010
0111
11.
01011
1000
12.
01100
1001
13.
01101
1010
14.
01110
1011
15.
01111
1100
16.
10000
011
17.
10001
0100
18.
10010
0101
19.
10011
0110
20.
10100
0111
21.
10101
1000
22.
10110
1001
23.
10111
1010
24.
11000
1011
25.
11001
1100
26.
11010
*****
27.
11011
*****
28.
11100
*****
29.
11101
*****
30.
11110
*****
31.
11111
*****
Во втором столбце таблицы записаны пятерки, в которых четыре старших бита представляют сдвинутую на один разряд влево тетраду. Символ  означает бит, пришедший из предыдущей (младшей) тетрады числа. Первые шесть строк третьего столбца таблица и последние шесть строк означают, что на наборах значений входных переменных код D4 не определен.
1. Савельев А.Я. Прикладная теория цифровых автоматов. [Текст]/ М.: «Высшая школа», 1987
2. Самофалов К.Г. и др. Прикладная теория цифровых автоматов. [текст]/Киев: «Вища школа», 1987. – 375 с.
3. Глушков В.М. Синтез цифровых автоматов.[Текст]/ М.: Физматгиз, 1962.
4. Угрюмов Е. П. Глава 7. Программируемые логические матрицы, программируемая матричная логика, базовые матричные кристаллы / Цифровая схемотехника. [Текст] Учеб. пособие для вузов/ Изд.2, БХВ-Петербург, 2004. С. 357.
Асеева Т.В. Функции алгебры логики: учебное пособие, 1-е изд. Тверь: ТГТУ, 2006, 12 с