Таблица У.2.1

Код Хемминга

двоично -кодированное десятичное число

Код Хемминга

к коду Хемминга. Разработайте на мультиплексорах схему, выполняющую это преобразование. (Использование этого кода описано в разд. 9.3.)

У.2.6. Аппаратные средства некоторых ЭВМ позволяют в программах пользоваться десятичной арифметикой. Примером могут служить ЭВМ фирмы Honeywell. Для десятичной .арифметики удобно использовать код с избытком 3, иллюстрируемый в табл. У.2.2. Это так называемый дополнитель-

Таблица У.2.2 Код с избытком 3

, Цбоично-Аодиробанное десятичное число

Под с изоыттм 3

ный код, а именно 0=9, 1=8, 2=7, 3=6, 4=5, 5=4 и т. д. Он удобен тем, что вычитание сводится к вычислению дополнения, единичному приращению и сложению. Разработайте на мультиплексорах 8X1 схему преобразования двоично-десятичного кода в код с избытком 3. Поскольку D=Z, в построении мультиплексора для D нет необходимости.

У.2.7. Постройте на мультиплексорах логическую схему для функции f(w,x,y,z) = ts!iy-\-x(w-\- уг).

У.2.8. Спроектируйте на мультиплексорах схему формирования бита четности Р для 6-разрядного кода ABCDEF.

У.2.9. Спроектируйте на мультиплексорах схему преобразования 6-разрядного двоичного числа в дополнительный двоичный код.

У.2.10. Постройте в соответствии с табл. У.2.3. на мультиплексорах схему преобразования двоично-десятичного кода в двоично-пятеричный код.

Таблица У.2.3

Двоичио-пятеричный код

двоично-Десятичное кодированное число десятичное число

двоично-плтеричный код

ГЛАВА 3

БАЗОВЫЕ ПОСЛЕДОВАТЕЛЬНОСТНЫЕ СХЕМЫ

Схемы, значения выходных сигналов (функций) которых зависят только от текущих значений входных сигналов (переменных), называются комбинационными. В этих схемах конкретные значения входных переменных однозначно определяют значение выходной функции. Функционирование последовательностных схем определяется и тем, в каких состояниях они пребывали ранее. Последовательностная схема в некотором смысле помнит о прощедщих событиях. Поэтому в зависимости от предшествовавшей последовательности событий значение функции-на выходе таких схем может быть различным при одних и тех же текущих значениях входных переменных. В связи с этим весьма существенным этапом проектирования и анализа схем оказывается выделение последовательностей событий. Реальная мощь любой ЭВМ определяется ее способностью выполнять в заданной последовательности многочисленные переходы из одного состояния в другое. В этой главе рассматриваются классические методы проектирования последовательностных схем [2- 8, 11-15]. При анализе этих схем приходится пользоваться как приемами анализа комбинационных схем, так и специальными методами. Основные определения и обозначения даны в разд. 3.1.

3.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ

На рис. 3.1 приведен пример типичного графа переходов, элементы которого - кружки, линии и стрелки - имеют определенный смысл. Стрелки представляют входные величины. Обозначения и порядок рассмотрения входных величин указываются в левом верхнем углу. Значения входных переменных записываются над каждой стрелкой. Ограничимся рассмотрением базовых последовательностных схем, в которых одновременно могут меняться состояния лишь одного из их входов. Одновременные изменения значений двух входных переменных считаются запрещенными. Кружки на графе переходов обозначают отдельные

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

Рис. 3.1. Граф переходов.

На рис. 3.1 входные величины обозначены как xixi. Можно считать, что работа схемы начинается с состояния 1 (кружок с цифрой 1), которому соответствует значение функции 0. При xixi=\G схема переходит в состояние 2 со значением на выходе 0. Следующее изменение на входе XiX2=ll вызывает переход в состояние 3 с сохранением на выходе 0. Когда значения входных переменных изменяется на X\Xz = \Q, значение функции на выходе становится равным 1. Изменение значений на входе на XiX2=ll вызывает переход в состояние 5 со значением функции на выходе 0. Последующее изменение x\Xi = Q\ приводит к переходу в состояние 6 с сохранением на выходе 0. При XiX2=00 схема возвращается в исходное состояние 1.

Блок заверши

Номбинационкая сшема

Рис. 3.2. Блок-схема последовательностного устройства.

> Устойчивой на данном шаге. - Прим. перев.

На рис. 3.2 изображена последовательностная схема [2]. Способность последовательностных схем сохранять память о прошлых событиях описывается так называемыми вторичными переменными, отображающими процесс установления в схеме определенного состояния. Одно или несколько последовательных состояний характеризуют режим работы схемы. Вторичным переменным присуще запаздывание между их возбуждаемыми и последующими установившимися значениями, соответствующими новому (изменившемуся) состоянию схемы. Схематически (рис. 3.2) это отображается введением блока задержки с обозначением возбуждаемых значений вторичных переменных прописными буквами (У), а установившихся значений, определяющих устойчивое состояние схемы, строчными буквами (у).

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

3.2. ПОНЯТИЕ УСТОЙЧИВОСТИ

При проектировании последовательностных схем используется описание условий перехода схем из одного состояния в другое. Смена состояний связана с изменением значения хотя бы одной вторичной переменной. Ниже рассматриваются схемы с одновременным изменением значения лишь одной переменной. Когда возбуждаемое значение вторичной переменной совпадает с ее установившимся значением iY=y), эта переменная не претерпевает изменений и называется устойчивой. Если возбуждаемое и установившееся значения переменной не совпадают (Уфу), переменная неустойчива, и должна произойти смена состояний. При у = 0 я У=0 смена состояния не требуется, и вторичная переменная устойчива. То же можно сказать и о случае, когда у=1 и У=1. Если же у = 0, а У=1, смена состояния необходима, и вторичная переменная неустойчива. Она неустойчива и при у=1, У=0, а в результате установления нового состояния у = 0.

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

3.3. ФУНКЦИОНИРОВАНИЕ ПОСЛЕДОВАТЕЛЬНОСТНОЙ СХЕМЫ

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

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

3.4. ПОСТРОЕНИЕ ГРАФА ПЕРЕХОДОВ

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

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

3.5. ТАБЛИЦА ПЕРЕХОДОВ

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

Рис. 3.3. Пример таблицы переходов.

Все события в схемах порождаются изменениями значений входных переменных. В таблице переходов каждой комбинации значений входных переменных соответствует определенный столбец. Смена значений входных переменных означает смену столбца в таблице. На рис. 3.3 изображена таблица переходов для графа переходов на рис. 3.1. Для каждого возможного сочетания значений x\Xi выделен отдельный столбец и каждому возможному состоянию схемы соответствует цифра на пересечении столбца и строки таблицы переходов (рис. 3.3).

Устойчивые состояния выделены кружками, а неустойчивые не выделяются. Построение таблицы начинается с помещения символа (1) в столбец xiX2=00. При изменении входных сигналов на Х\Х2 - \ происходит переход к неустойчивому состоянию 2, что отображается сменой столбца таблицы переходов. Это можно рассматривать как изменение значения возбуждаемой вторичной переменной. Последнее приводит к переходу на новую строку таблицы, от 2 к (2). Поскольку с каждым из устойчивых состояний связывают определенные значения функций на выходе, эти значения для удобства приводят в дополнительном столбце таблицы. Аналогично при появлении входных сигналов XiX2 = ll происходит переход из состояния (2) в неустойчивое состояние 3. Как следствие возбуждения новых зна-

чений вторичных переменных имеет место переход в состояние <3)

Последующее изменение входных переменных с jciX2=11 на xiX2=10 приводит к очередной смене столбца и переходу из состояния (3) в состояние 4. Возникающее при этом изменение возбуждаемых вторичных переменных приводит к переходу из состояния 4 в состояние (4), т. е. к очередной строке таблицы. Согласно графу переходов, состоянию (4) соответствует значение выходной функции, равное единице, о чем свидетельствует 1 в столбце значений функции. Появление на входе Х1д;2 = 11 приводит к переходу от столбца таблицы с состоянием (4) к столбцу с состоянием 5, что сопровождается изменением вторичных переменных и переходом из состояния 5 в состояние (5). Последующее появление на входе XiX2 = 01 отображается в таблице переходов сменой столбца и состояния (5) на 6, а вызванное этим изменение вторичных переменных влечет за собой переход к следующей строке таблицы, т. е. из состояния 6 в состояние (6).

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

3.6. ИСКЛЮЧЕНИЕ ИЗБЫТОЧНЫХ УСТОЙЧИВЫХ СОСТОЯНИЙ

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

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

1) им соответствуют одни и те же значения входных сигналов (т. е. они появляются в одном и том же столбце таблицы);

2) им соответствуют одинаковые значения функций на выходе;

3) при любых допустимых изменениях входных сигналов переход из этих состояний происходит в одинаковые или эквивалентные состояния.

Граф переходов на рис. 3.3 не содержит избыточных состояний. Поэтому рассмотрим еще один пример таблицы переходов с избыточными состояниями (рис. 3.4,а). Состояния (2) и (4) эквивалентны друг другу. Им соответствуют одни и те же значения входных сигналов X\Xi=Q\ и одни и те же значения функций на выходе fif2 = 10. Переходы из состояний (4) и (2) происходят в 1 и 5. В силу идентичности всех элементов соответствующих строк таблицы изменения входных сигналов вызывают пе-

Рис. 3.4. Таблица переходов с эквивалентными состояниями (2) и (4). а - исходная избыточная форма; б - после удаления четвертой строки.

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

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

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

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

3:X2

00 01

00 01

Ji JOf,f

Рис. 3.5. Пример оптимального определения состояния, в которое может перейти схема.

а - фрагмент таблицы переходов с псевдоэквивалентными строками; б - удаление из -быточиой строки.

На рис. 3.5 приведен пример таблицы переходов с псевдоэквивалентными состояниями. Во второй строке при входном сигнале XiX2 = 10 символом - помечена возможность перехода в произвольное состояние.

3.7. ПРОЦЕДУРА СЛИЯНИЯ СТРОК

На рис. 3.6 изображена та же таблица переходов, что и на рис. 3.3 после процедуры слияния отдельных строк. В частности, попарному слиянию подверглись строки (1) и (2), (3) и (6), а также (4) и (5). В такой вариант таблицы не включают ко-

. 00 01 11

Рис. 3.6. Таблица после процедуры строк.

переходов

слияния

Рис. 3.7. Диаграмма слияний.

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

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