Файл: Каган Б.М. Цифровые вычислительные машины и системы учеб. пособие.pdf

КС не содержит запоминающих элементов. Поэтому КС называют автоматом без памяти или примитивным автоматом.

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

Структурная схема автомата, представленная на рис. 3-4,6, содержит запоминающие элементы и комбинаци­ онные схемы / и II.

Состояния запоминающих элементов, определяющие состояние автомата, передаются в форме сигналов Qj поцепям прямой связи на входы комбинационной схемы II и по цепям обратной связи на входы комбинационной схемы I. На входы комбинационных схем поступают так­ же сигналы х и. .., хп с входа автомата.

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

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

117

В ряде случаев при анализе автомата его заменяют автоматом с одним эквивалентным входом и одним экви­ валентным выходом и считают, что эквивалентные вход­ ной сигнал х(і) и выходной сигнал y(t) принимают зна­ чения из соответствующим образом преобразованных алфавитов Р и 5 входных и выходных сигналов.

Для задания цифрового автомата должны быть ука­

4)начальное состояние автомата qо;

5)и 6) фуянкции переходов A(q, х) и выходов B(q,x),

однозначно определяющие зависимость соответственно состояния автомата <7(^ + 1) в момент дискретного вре­ мени £+1 и выходного сигнала y(t) от состояния автома­ та q(i) и входного сигнала x(t) в момент дискретного времени t.

Используя функции переходов и выходов, можно по­ ведение автомата описать уравнениями:

Уравнениям (3-5) и (3-6) соответствует автомат, вы­ ходной сигнал которого зависит от состояния, в котором находится автомат, и от сигнала на его входе. Такой ав­ томат называется автоматом Мили.

В устройствах ЦВМ широко применяются автоматы другого типа, так называемые автоматы Мура, у кото­ рых выходной сигнал y(t) в момент дискретного време­ ни t зависит исключительно от состояния автомата q(i) в этот момент времени и не зависит от входного сигнала. x{t).

Функционирование автомата Мура описывается уравнениями:

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

118

Pi и столбца для состояния qj в таблицу переходов запи­ сывается состояние, в которое автомат переходит из со­ стояния qi под действием входного сигнала ри а в табли­ цу выходов — выдаваемый при этом выходной сигнал.

В табл. 3-1 и 3-2 приведены примеры таблиц перехо­ дов и выходов для некоторого автомата Мили, алфави­ ты которого содержат пять состояний, два входных и три выходных сигнала.

Т а б л и ц а 3-1

Кстати говоря, приведенные таблицы определяют ав­ томат-экзаменатор, который в каждом из своих пяти состояний задает студенту соответствующий вопрос. На каждый из них возможны ответы: «Да» (р\) и «Нет» (рД. При неправильном ответе автомат переходит в на­ чальное состояние и выдает сигнал «Незачет» (si). При правильном ответе автомат выдает ответ «Опрос про­ должается» (s2) и переходит в следующее состояние, в котором задается следующий вопрос. При правильном ответе на последний вопрос автомат выдает ответ «За­ чет» (s3) и переходит в начальное состояние.

В случае автоматов Мура строится «отмеченная таб­ лица переходов» (табл. 3-3), содержащая дополнитель­ ную строку, в которой каждое состояние автомата отме­ чается соответствующим выходным сигналом.

119

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

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

ивыходной алфавиты и начальное состояние.

Втеории автоматов вводятся понятия полной систе­ мы переходов и полной системы выходов автомата. Если для двух любых состояний qi и qj автомата имеется вход­ ной сигнал, переводящий автомат из состояния qi в q^

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

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

3-3. Э Л Е М Е Н Т Ы Т Е О Р И И Б У Л Е В Ы Х Ф У Н К Ц И И

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

Переменные Х\, х%, ..., хп называются двоичными, ес­ ли они могут принимать только два значения 0 и 1.

120

Булевы функции двух переменных

121