Рис. 1.33. D-триггер и элемент запаздывания. а - представление; б - таблица состояний; в - таблица возбуждений; а - элемент запаздывания.

Г-триггер, изображенный на рис. 1.32, работает как (-триггер, у которого J = К. При Г = О он сохраняет текущее состояние, при Т = 1 переходит в следующее.

Обозначения, таблица состояний и таблица переходов £>-триггера приведены на рис. 1.33. Следующее состояние D-триггера равно текущему. Он ведет себя аналогично элементу задержки, выход у которого в момент времени t равен входу х в момент времени t - D; D - постоянная, называемая величиной задержки. Элементы задержки являются удобным средством анализа и синтеза цифровых цепей, так как реализующие их логические элементы обладают запаздыванием. На схемах элементы задержки изображаются как показано на рис. 1.33, г.

появление на обоих выходах триггера нулей. Если затем на вход подать входную комбинацию S = R = 0, то следующее состояние триггера оказывается неопределенным, так как оно зависит от порядка, в котором будут изменяться величины у и у. (-триггер (рис. 1.31) отличается от iS-триггера тем, что разрешена входная комбинация J = K=l, переводящая триггер из состояния у = I, у - О в состояние у = О, у = I и наоборот.

46 Гласа I

1.4.3. ЗАДЕРЖКИ И ТАКТОВЫЕ ГЕНЕРАТОРЫ

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

Рассмотрим комбинационную цепь с логическими элементами Gi, G2 и Сз, представленную на рис. 1.34, а. Обозначив через Gi, G2 и Сз логические элементы с нулевой задержкой, а через Дь Аг и Аз соответствующие им задержки, получим цепь, изображенную на рис. 1.34,6.

щ

-1 ц.

I---1----1 Гг

L J4

Рис. 1.34. Представление запаздывания в цепи.

Предположим, что в некоторый момент времени t на ее входы Xl, Х2 и Хз поданы одинаковые и равные 1 символы. Тогда выходной символ будет равен 1. В идеальном случае при изменении в момент времени to> t входных символов с 1 на О выходной символ должен остаться равным 1. Однако если Ai > Д2 хотя бы на очень малую величину е, то выход будет содержать 0-импульс. Эта ситуация иллюстрируется рис. 1.35, на котором представлена зависимость сигналов Хи С], Сг и Сз от времени.

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

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

Последовательностная цепь с тактовым генератором называется синхронной, так как состояние элементов памяти изменяется синхронно с изменением тактовых сигналов. Последовательностные цепи без тактового генератора называются асинхронными и рассматриваются в гл. 4.

Рис 1.35 Временные диаграммы следования сигналов.

время, в течение которого С = I) через Тр. Для нормальной работы цепи Тр должно быть выбрано таким, чтобы триггер имел возможность изменить состояние, но не успел бы дважды среагировать на одно и то же возбуждение, если его выход свя-

Входиые

Переметые состояния

Татовые сигналы Рис. 1.36. Синхронный триггер.

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

Если выходы триггера являются входами цепи Е формирования входных импульсов (рис. 1.37, я), то длительность тактовых

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

Тпктшые сит'т

Тактовые сигтпы

Г

-У У

а б

Рис. 1.37. Обратная связь в цепи (а); двухтактный триггер (б).

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

Другой метод решения задачи однократного изменения состояния элементов памяти в течение тактового импульса состоит в использовании триггеров, запускаемых фронтом импульса. Эти триггеры могут менять состояние только при изменении тактового импульса от 1 до О или наоборот (но не одновременно). Рассмотренные выше JK- и Г-триггеры часто используются как триггеры, запускаемые фронтом импульса.

1.4.4. СИНТЕЗ ПОСЛЕДОВАТЕЛЬНОСТНЫХ ЦЕПЕЙ

Процедура синтеза последовательностных цепей разбивается на следующие этапы: 1) составление таблицы состояний на основании словесного описания последовательностной функции, 2) реализация таблицы состояний последовательностной цепью.

импульсов должна быть такой, чтобы при прохождении выходного сигнала через цепь Е тактовый импульс отсутствовал (С = 0). Это достигается путем соответствующего ограничения ширины импульса или использованием двухтактного триггера, получаемого путем каскадного соединения двух триггеров (рис. 1.37,6). Переход первого триггера в новое состояние возможен только при С=\. Второй триггер переходит в то же состояние, что и первый, при С = 0. Если двухтактный триггер используется вместо iS-триггера, то при С = 1 наличие обратной связи не приводит к изменению его состояния. При С = О

Устрой-.

ления Мжетем

Светофор тпротекщ Штодюр нй улице

Рис. 1.38. Система управления дорожным движением.

В течение 1 мин разрешает движение по проспекту, а затем в течение того же времени по улице. При нажатии пешеходом кнопки на углу в светофоре к концу текущего минутного интервала должен загореться и гореть в течение 2 мин красный свет. Затем красный свет должен погаснуть, а светофор должен начать функционировать в описанной выше последовательности (как до перерыва).

Реализуем РДД в виде синхронной последовательностной цепи. Для этого необходимо, чтобы изменение входных сигналов цепи, связанное с нажатием пешехода на кнопку, происходило только тогда, когда тактовый импульс равен нулю. Поскольку выполнить это условие невозможно (пешеход может нажать кнопку в произвольный момент времени), реализуем систему управления РДД в виде, показанном на рис. 1.38. Здесь предполагается, что кнопка пешехода установлена на (-триг-гере, не снабженном тактовым генератором, что этот триггер подключается к ?5-триггеру в интервалах времени, когда тактовый импульс равен нулю, и что на выходе /?5-триггера формируется управляющий сигнал р, который подается на вход РДД.

Далее предположим, что РДД является синхронным после-Довательностным автоматом. Если через Zi и 22 обозначить

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

Пример 1.8. На пересечении проспекта А первой улицы установлен светофор, представляющий собой регулятор дорожного движения (РДД). Он снабжен тактовым генератором С с периодом следования тактовых сигналов, равным 1 мин. Светофор

ToKmoBbig снгнрш

ВХОДЫ триггеров, управляющих светофорами, то для обеспечения транспортного потока по проспекту на выходе цепи, реализующей РДД, должен быть сформирован сигнал Zi = I, а для обеспечения транспортного потока по улице - сигнал z-l. Третий выход 2з используется для возврата С-триггера в исходное положение (заметим, что если кнопка пешехода нажимается точно в момент, когда 23= 1, то триггер автоматически возвращается в исходное положение)). Теперь РДД можно представить последовательностным автоматом с шестью состояниями.

Состояние 1

Описание

Выход (2i, 22, 23) равен 100, следующий выход равен 010 при отсутствии прерывания

Выход равен 010, следующий выход равен 100 при отсутствий прерывания

Достигается, если прерывание произошло в состоянии 1 Достигается, если прерывание произошло в состоянии 2 Достигается из состояния 3, выход равен 001 Достигается из состояния 4, выход равен 001

Таблица состояний РДД пердставлена на рис. 1.39. Переходы в столбце /0 - 0, строки 1, 2 характеризуют нормальную

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

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

) Здесь Zl, Zl, 23 -двоичные выходные сигналы. Выходные символы соответствуют комбинациям этих сигналов.

Рис 1.39. Таблица состоя НИИ регулятора дорож ного движения.

МЗП

вильном кодировании состояний каждому состоянию соответствует свой, отличный от других код. Если каждому состоянию присвоен один код, то кодирование называется однозначным. При правильном однозначном кодировании для реализации таблицы п состояний требуется [log2n] элементов памяти. Здесь знаком Г 1 обозначено наименьшее целое число, большее или равное logzti.

Обозначим через х = (хь Xz, х„), у = (уь У2, Уд) и Z = {zi, 22, ..., Zft) соответственно входные переменные, переменные состояния и выходные переменные последовательностной цепи, а через Y = (Fi, Y2, Y) обозначим следующие состояния переменных состояния у. Так как следующее состояние и выход являются функциями входа и текущего состояния, то У, = fi (х, у), 1 < г < g и Zi = = gi{, у), lr. Общая модель последовательностной цепи имеет вид, показанный на рис. 1.40. Здесь через МЭП обозначено множество элементов памяти (триггеры), а через Ye - множество возбуждений, необхо-ходимых для получения следующего состояния переменных У. .Ясно, что соотношение между У и Уе зависит от типа используемых элементов памяти. При использовании D-триггеров (элементы задежки) Уд = У. Для RS-, JK- или Г-триггеров множество \е должно определять возбуждение каждого триггера, необходимое для перехода в следующее состояние У в соответствии с таблицами возбуждения, приведенными на рис. 1.30-1.33.

После кодирования состояний выходы и следующие значения Yi каждой переменной состояния определяются непосредственно из таблицы состояний. Таблица, в которой представлена функциональная зависимость от переменных состояния (у) и входных переменных (х), называется У-матрицей. Код элемента У-матрицы в строке qi и столбце должен соответствовать коду элемента N{qi, 1). Учитывая, что выходы также являются функцией входов х и переменных состояния у, их удобно включить в У-матрицу, которая в этом случае обозначается как У, -матрица.

Учитывая, что У-матрица (и У, 2-матрица) характеризует величину следующего состояния для каждого У,-, возбуждения соответствующих элементов памяти могут быть определены с помощью соответствующих таблиц возбуждений (рис. 1.30- 1-33). Получаемая при этом таблица называется матрицей

Тактовые сигтш

Рис 1.40. Модель последовательностной цепи.

возбуждений. При использовании £)-триггеров эта матрица идентична У-матрице.

Для различных типов описанных выше триггеров возбуждения определяются по величине Уг и заданному следующему значению Yi, записанному в рассматриваемой строке. Для Г-триг-геров Ti ~ 1 для всех переходов, в которых уг изменяет значение (т. е. УгФ yi), VL Тг = Q в противном случае. Следовательно, Тг = Yiyi + УгУг. Для /?5-триггеров Si = 1 для всех переходов, в которых г/г переходит из состояния О в состояние 1 (т. е.

= О, Yi - I), Si = 0 для всех переходов, в которых следующее состояние имеет код = О, и не определено для всех других элементов (т. е. элементов, в которых г/ остается равным 1). Ri - 1 для всех переходов, в которых Уг меняет состояние от 1 до о (т. е. = 1, Yi - 0),ki = 0 для всех переходов, в которых переменная уг становится или остается единицей. Ri не определена для всех других элементов. У С-триггеров / = 1 для каждого перехода т О к I, К = 1 для каждого перехода от i к О, / = О для каждого О-0-перехода, К=0 для 1-1-перехода. Все остальные элементы не определены.

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

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

Пример 1.9. Для таблицы состояний, приведенной на рис. 1.41, однозначное кодирование состояний требует flogs 41 = = 2 переменных состояния. Одно из этих кодирований показано на рис. 1.41, У, z-матрица для которого изображена на рис. 1.42,0. Заметим, что эта матрица составлена в форме карты Карнау, т. е. смежные строки отличаются только на одну переменную. Это упрощает последующую задачу выбора логики для комбинационной цепи. Карта получена непосредственно из таблицы состояний путем заполнения ячеек, соответствующих состояниям qi (указанным в скобках слева от таблицы), и входов соответствующими кодами для состояний N{qi, 1) и Z{qi, 1). Например, элемент в строке yi = = О и столбце х = 1 характеризует переход из состояния 1 (представленного кодом 00) с входом х= I. Из таблицы состояний видно, что следующее

Рис. 1.41 Таблица состояний и кодирование.

рис. 1.42, а под У, 2г-матрицей. При использовании D-триггеров в качестве элемента памяти эта реализация исходит из множества уравнений возбуждения, так как следующее значение Y

V V Z

у, = У, Уг + У1 + Уг Vj = ху, + У,У2 + *У, У2

Т, = ху, Уг + ху, + хуг

Т2 = ХУ, +У,У2+*У1У2

Рис, 1.42. Синтез последовательностной цепи.

равно возбуждению. Логика для реализации z не зависит от типа элементов памяти. Например, состояния Г-триггера определяются из матрицы возбуждений, показанной на рис. 1.42,6. Эта матрица получена из У, 2-матрицы (рис. 1.42, а) с помощью Таблицы возбуждений Г-триггера (рис. 1.32,в). Элемент в строке 11 и ряду О характеризует переход из состояния 4 со входом Из У, z-матрицы видно, что следующее состояние имеет

состояние при х = 1 равно 4 и (в соответствии с таблицей кодирования) имеет код И, при этом на выходе будет 0. Так как выходная переменная равна О, то соответствующий элемент F, 2-матрицы записывается в виде 11,0, т. е. Yi = У2= 1, г = 0.

Минимальная двухступенчатая реализация каждого следующего значения Yi переменной состояния t/i приведена на

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

Стори, Гаррисон и Рейнгард [18] разработали алгоритм получения оптимального кодирования состояний в терминах входных символов логических элементов, основанный на безусловном переборе всех возможных вариантов. Для каждого столбца г/г и типа триггера точки 1 и неопределенные точки возбуждений определяются как функции входов и состояний таблицы состояний. Затем для любого кодирования состояний, содержащего yi, находится нижняя граница стоимости, связанная с этими возбуждениями. Эти нижние границы служат для кодирования состояний. Операция перебора заканчивается, когда фактическая стоимость выбранного кода состояний становится меньше нижней границы стоимости. Алгебраический подход к кодированию состояний, основанный на анализе структуры автоматов, рассмотрен в гл. 5.

Для таблицы п состояний, где п ф 2, однозначное кодирование состояний может быть представлено в виде У-матрицы, в которой некоторые строки соответствуют неназначенным

КОД 01 Поскольку код текущего состояния равен 11, переменная t/i меняет состояние, а уг нет. Следовательно, для этого перехода Ti = 1 и Гг = 0. Минимальные реализации для рассмотренного случая показаны под таблицей.

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

Рассмотрим таблицу п состояний. При однозначном кодировании 5о= flogs ! переменных состояний каждая переменная соответствует отдельному двоичному столбцу. Для таблицы п состояний существует С(п) возможных переменных состояний [18], которое для п^5 много меньше числа возможных кодирований состояний S{n) [12]. Например:

п S{n) С (п)

4 3 3

5 140 15

6 420 25

7 840 35

8 840 35

9 10, 810, 800 255