а) При малом числе состояний (N < 12) для каждого состояния автомата a(t) предусмотрим независимый триггер Z(t). Тогда переход из состояния Z i в состояние Z j приведет к тому, что триггер Z i, установленный в состояние 1 в момент t, в момент (t + 1) будет приведен в состояние «0», а триггер Z j в момент (t + 1) будет приведен в состояние «1». Т.е. для представления памяти автомата потребуется столько триггеров, сколько состояний в автомате (для данного примера i = ), и переменные Z i будут совпадать со значениями состояний a i (i = ). Однако поскольку необходимо разносить во времени Z i (t) и Z j (t + 1), то для реализации памяти автомата потребуется 2N триггеров, ведь не исключена ситуация перехода a i (t)→a i (t + 1), когда, находясь во втором состоянии, например, автомат снова должен вернуться во второе состояние при некоторых условиях.
Такой способ кодирования номеров состояний автомата называется унитарным, т.к. каждому десятичному номеру состояния соответствует независимый элемент памяти (код с одной «1»).
|
|
б) Двоичное кодирование номеров состояний в памяти автомата.
При числе состояний N > 12 число триггеров, равное 2N, становится большим. Затраты элементов памяти и логических схем «И» для передачи кодов Z1, Z2, …, Z p (t) становятся неприемлемыми для экономичной реализации. В этом случае номера состояний автомата представляются двоичными кодами в виде ДПК или ДКГ. Тогда число триггеров P при N состояниях a(t) определится из соотношения:
2P ≥ N, т.е. p = Int(log2N), где Int обозначает целую часть числа. Для приведенного примера N = 10, следовательно, p = 4, и память автомата есть два четырехразрядных регистра с парафазной связью между ними. Т.е. вместо Z1, Z2, …, Z9 в случае унитарного кодирования для ДПК (и для ДКГ) потребуется всего 4 переменных Z0, Z1, Z2, Z3 рис. 59. Следовательно, число триггеров с 18 снизится до 8.
Рассмотрим еще раз структурную схему рис. 58. Для правильного функционирования автомата (отсутствие неуправляемой смены состояний, т.е. отсутствие гонок в автомате) требуется наличие двух сигналов синхронизации, действующих в разное время, т.е. пересечение сигналов во времени должно давать пустое множество Ø.
Память автомата с оптимальным кодированием состояний. Во многих известных способах организации памяти не рассматривались другие способы кодирования, кроме ДПК, ДКГ или унитарного кода. Кодирование внутренних состояний можно осуществлять, исходя из требований уменьшения аппаратурных затрат или увеличения надежности функционирования автомата*.
Память быстродействующих автоматов. При организации памяти на двух последовательно соединенных регистрах а (t) и a (t +1) автомат работает по двухтактной схеме (τ и ). Но ведь полезной функцией автомата являются не его внутренние переходы из состояния в состояние, а генерация выходных сигналов с1, с2,..., сk (или Аl, A2,..., A k) в определенной логической взаимосвязи и временной последовательности.
|
|
О.Ф. Лобов и Н.А. Гасников [23] предложили параллельную организацию (рис. 60) памяти, позволяющую генерировать выходные микрооперации как по сигналу τ, так и по , сохраняя при этом временную последовательность переходов a (t) и a (t + 1). Для этого используются два параллельно работающих регистра, выходы которых объединены схемами «ИЛИ», т.е. по входам комбинационных схем работа производится как бы от единого регистра памяти. Синхронизация в параллельных блоках перекрестная: считывание кода происходит по синхроимпульсу τ с первого регистра памяти, а со второго – по сигналу . Пусть в Pг1 код a (t) через сборку схем «ИЛИ» передан на комбинационные блоки в этот же временной промежуток (τ). Найденное значение a (t + 1) запишется в Рг2, а по сигналу Pг1 и Рг2 изменяют свою функцию на противоположную, т.е. в Pг1 окажется a (t + 1), а считывание a (t) произойдет с Рг2. Такая организация памяти позволяет повысить быстродействие МПА в два раза на той же элементной базе.
Если для технологических процессов фактор быстродействия не является определяющим (главным является надежность и безотказность), то в системах передачи и приема дискретной информации надежность связана с использованием корректирующих помехозащищенных кодов, причем кодирование и декодирование производится в реальном масштабе времени, а обработка (во время самой передачи и приема) осуществляется по сложным алгоритмам. Для таких задач фактор времени является одним из важнейших.
На рис. 60 буквами F1 и F2 обозначены комбинационные схемы для реализации соответствующих систем булевых функций, т.е. комплекс F1F2 и есть та схема СА, которая представлена на рисунке.
Рис. 60
Блок с буквой Ш представляет собой шифратор для того случая, когда F2 реализует функции формирования унитарных кодов f 0, f 1, …, f 9, а в Pг1 и Pг2 производится запись Z0, Z1, Z2, Z3 в ДПК.
Память автомата на счетчике. В большинстве случаев в графе переходов автомата можно выделить замкнутый контур с последовательным чередованием номеров состояний. Для примера на рис. 59 такой контур образуется последовательностью вершин графа с номерами 0, 1, …, 8. Номер следующего состояния определяется из выражения а(t + 1) = а(t) + 1 или а(t + 1) = а(t) + 1. Символ «~» над α показывает, что может быть записано значение как α, так и . Вне этого контура лежат переходы
.
Следовательно, если в качестве одного из регистров памяти автомата взять счетчик, то всегда, когда функция R= f 0 + f 1 + f 2 + f 5 равна 1, необходимо использовать счетчик как регистр памяти состояния а (t) с переносом кода из регистра a (t + 1) по сигналу . Но если функция R= 0, то эта «связь» должна быть прервана, т.к. достаточно прибавить 1 к счетчику для изменения (увеличения) номера его состояния. Может также использоваться универсальный счетчик, работающий как на сложение, так и на вычитание. Очевидно, что этот более сложный случай должен быть рассмотрен отдельно и подробно.
В этом случае реализация функций при наличии счетчика вместо регистра может быть «экономически» более оправданной по сравнению с вариантом реализации функций F2 без счетчика.