Бауэр Ф.Л., Гооз Г. Информатика. Том 1

Подождите немного. Документ загружается.

4.3. Переключательные схемы 311

4.3.2.

Построение

переключательных

схем

Структуру, содержащую, с одной стороны, переменные па-

мяти

для двоичных слов и двоичных знаков, т. е. регистры и

элементы задержки (рис. 172, 173), а с другой — комбинацион-

ную

схему,

входы которой „питаются" от регистров и элементов

задержки и выходы которой задают новые установки регистрам

и элементам задержки, мы назовем

переключательной

схемой.

Такая

переключательная схема работает тактами, при этом

предполагается, что длительность такта велика по сравнению

•с временем срабатывания комбинационной схемы. Такая

тактированная

переключательная схема получает

тактовые

импульсы

либо от некоторых центральных часов

(синхронное

тактирование),

либо от

других

переключательных схем

(асин-

хронное

тактирование).

Регистры и элементы задержки переключательной схемы

/могут

находиться в конечном числе

внутренних

состояний

\ пе-

реключательная схема вызывает

переходы

состояний

. Эти пе-

реходы зависят также от

входных

параметров;

некоторые опре-

делённые функции состояния передаются „наружу" как резуль-

таты работы схемы.

4.3.2.1.

Последовательный

параллельный

сумматоры

На

рис. 175 изображена переключательная схема для под-

программы

binadd

из 4.3.1.1. Используется один полный сум-

матор, таблица значений которого (рис. 156) соответствует

восьмичленному разбору случаев в

binadd.

Элемент задержки

для переноса й имеет два внутренних состояния со значениями

»перенос

есть«

и О = ^переноса нет«.

В то время как комбинационная схема сложения

(рис.

167) выполняет сложение „одним махом"

, последова-

тельный сумматор

требует

для случая n-разрядных слагаемых

п единиц времени (тактов). В известном смысле последователь-

ный

сумматор более „способен", чем комбинаторная схема сло-

жения:

число разрядов слагаемых не ограничено

, так что сло-

жить можно любую пару чисел; арифметика натуральных чисел

ограничена лишь длиной регистра сдвига.

Состояния в смысле раздела 3.3.2.1.

В гл. 7 эта тема получит дальнейшее развитие в понятии конечного

автомата.

Строго говоря, это не так, поскольку перенос может „пробежать" все

разряды. Однако этого можно избежать с помощью особых мер

Нельзя сказать, что оно „бесконечно". Числа с бесконечным числом

разрядов вообще не

могут

быть сложены с помощью оканчивающегося ал-

горитма.

312 Гл.

Двоичные комбинационные

переключательные схемы

...

НА

—

Г~

НА

}

-и-

г-

-hi -

Рис.

175.

Переключательная

схема

последовательного сумматора.

Переключательная схема

с т

двоичными элементами

за-

держки может иметь

до 2

внутренних состояний,

по

числу

возможных комбинаций значений. Примером

максималь-

ным

числом внутренних состояний служит переключательная

схема

двоичного счётчика (рис. 176).

Она

получается, если соединить выходы

комбинационной

схемы двоичного счёт-

чика

(рис. 165) с

элементами задержки,

а выходы этих элементов

— с

входами

комбинационной

схемы.

Другой пример получается аналогич-

ным

образом

из

комбинационной схемы

сложения

(рис. 168).

Отдельные элемен-

ты задержки образуют совместно

ре-

гистр

— накапливающий регистр

(нако-

питель)

параллельного сумматора

(рис.

177). Для

сложения счётный

вход

постоянно

установлен

на О.

Параллельный (четырёхразрядный)

сумматор

на рис. 177

может сложить

лишь

два

четырёхразрядных числа

и в

случае

переполнения установить

выход

переноса

й на L.

Опять

мы имеем „кирпичик"; если связать й-выход такого параллель-

ного сумматора

с-входом

другого,

то

получится параллельный

сумматор

соответственно большим накопителем.

Фактически

этим способом всегда может быть реализовано

лишь

фиксированное число разрядов.

По

образцу переключа-

Рис.

176.

Переключа-

тельная

схема

двоично

го счётчика.

4.3. Переключательные схемы

313

Рис.

177. Параллельный сумматор с накопителем.

тельной схемы на рис. 175 это ограничение можно всё-таки

обойти,

заменив фигурирующий там полный сумматор на й-раз-

рядную комбинационную

схему

сложения. В таком

случае

слагае-

мые а и b также подготавливаются

последовательно-параллель-

но в

двух

й-элементных

батареях

регистров сдвига. На рис. 178

Рис.

178. Четырёхразрядный последовательно-параллельный сумматор.

представлена переключательная схема такого

последовательно-

параллельного

сумматора

для k = 4. Снова арифметика нату-

ральных чисел ограничена лишь длиной регистра сдвига.

314 Гл. 4. Двоичные комбинационные и переключательные

схемы

4.3.2.2.

Переключательная

схема

сдвига

В других переключательных схемах используются не все

комбинации

значений. Примером может служить

переключатель-

ная

схема

сдвига,

применяе-

мая

для порождения трёхраз-

Q=Eh

рядного циклического кода

(см.

1.4.2).

Она представлена

на

рис. 179, где

—

Df(v

, v

или,

в „программистской" за-

писи,

(t>i.

, v

):=

, v

, f(v

, v

)).

Рис.

179. Порождение циклического

кода.

Это переключательная схема без входов, её внутренние состоя-

ния

будут

(рано или поздно) периодически повторяться. Для

случаев

(A)

(В)

(С)

/(и,, v

) = (и, Л v

) V (1 и, Л 1 v

) = о,

<-*•

будут

пробегаться следующие комбинации значений (vi, u

, v

(А)

[*(ООО)

(В)

(OLO)

(LQO)

rKOLL)

(LLO)

^(OOO)

(00

(OLL)

(LLL)

(LLO)

(LOO)

r>(LOL)

(OLO)

1+(000)

(00

(OLL)

(LLO)

<LOL)

(OLO)

(LOO)

В случае (С) получаются цикл r

>OOOL

'-OL-] и тривиальный

цикл

4.3. Переключательные схемы

313

Этот пример показывает также, каким образом можно по-

строить регистр сдвига, „нанизывая" один за другим элементы

задержки.

4.3.3.

Триггеры

Переключательная схема называется

мультистабильной,

если для неё существует такая комбинация входных значений,

которая

оставляет неизменным любое её внутреннее состояние.

Рис.

180. Управляемый тактовыми импульсами RS-триггер как переключа-

тельная схема.

Такую переключательную

схему

можно использовать для запо-

минания.

Основополагающим благодаря своей простоте являет-

ся

триггер

\ который

бистабилен:

у него два внутренних со-

стояния;

их можно характеризовать, скажем, значениями од-

ной

внутренней двоичной переменной v или

двух

переменных

{v\, v

), которые

могут

принимать лишь комбинации значений

(О,L) и (1_,О), так что всегда выполнено условие

=~]vi.

Самый

распространённый триггер (так называемый „RS-

триггер"

) имеет два симметричных

входа

(г, s), причём ком-

бинация

(L,L) исключается. Для комбинации входных зна-

чений

(0,0) внутреннее состояние остаётся неизменным;

В оригинале Flipflop — заимствованное из английского звукоподража-

тельное слово (flip— щёлкать,

flop

— хлопаться,

flap

— хлопать,

flip-flap

—

хлопанье). В немецком языке используется также термин

Trigger,

тоже анг-

лийского присхождение

(trigger

— защёлка, спусковой крючок). — Прим. изд.

ред.

S и R — соответственно от английских set (установка) и reset

{сброс).—Прим.

изд. ред.

316 Гл. 4. Двоичные комбинационные и переключательные схемы

Символическое

изображение

Формула

Название

г—

—•

у,

—

"ID,

триггер

Рис.

181. Символическое изображение управляемого тактовыми импульсами-

RS-триггера.

Рис.

182. Реализация элемента задержки с помощью триггера.

Рис.

183. Реализация регистра сдвига с помощью цепочки триггеров.

—

Рис.

184. Ж-триггер.

для (r,s) = (L,O)

будет

) = {L,O), а для (r,s) = (O,L)

будет

(vi,v

) = {OX).

Поведение

триггера описывается двумя симметричными

между

собой равенствами

y, = D((rV о,) Л Is),

= D((s V v

) Л 1 г)

4.3.

Переключательные схемы

317

с дополнительным условием V\ =

v%,

которые означают ровно

то же, что и групповое присваивание

(0i - о

)

= ((г V о,) Л Is, (s V о

) Л "1 г)

с условием-предохранителем гЛ«==О.

На

рис. 180 изображена соответствующая переключательная

схема с двумя элементами задержки, а на рис. 181 представлено

символическое изображение

триггера.

По

техническим причинам

как

отдельные элементы за-

держки, так и целые регистры

экономичнее

всего реализовы-

вать с помощью триггеров или

соответственно батарей триг-

геров

(триггерные

регистры).

Для отдельного элемента за-

держки соответствующая схе-

ма изображена на рис. 182;

комбинация

(1,1.) здесь авто-

матически исключается. В слу-

чае регистра сдвига выходы

одного триггера используют в

качестве входов следующего

(рис.

183).

Во всех случаях на

входе

каждого триггера должно вы-

полняться

условие sAr=O.

В случае необходимости его

можно обеспечить, как на

рис.

184, за счёт обратных связей и включения конъюнк-

ций

перед триггерами („JK-триггер"). Иногда работают

также с

двойным

сигналом,

т. е. вместе со всякой пере-

ключательной переменной поступает и её отрицание, тогда

на

входах

и выходах RS-триггеров всегда

будут

нужные пары.

Примерами

служат цепочка триггеров на рис. 183, а также при-

ведённый на рис. 185

кольцевой

(циклический)

счётчик,

в кото-

ром „циркулирует" пара (О,1_).

При

двойном сигнале комбинация значений (0,0) никогда

не

появляется на

входе

триггера. Однако её использование

часто оказывается выгодным (см. рис. 184).

4.3.4.

Триггерные

переключательные

схемы

Переключательная схема на триггерах, или

триггерная

пере-

ключательная

схема,

— это комбинационная схема, выходы ко-

торой через триггеры соединяются Обратной связью со входами.

Рис.

185.

Кольцевой

счётчик на триг-

герах.

318 Гл. 4. Двоичные комбинационные и переключательные схемы

В принципе обычную переключательную

схему

можно сразу

заменить триггерной, поскольку в соответствии с рис. 182 каж-

дый элемент задержки можно заменить на триггер. Дополни-

тельно требуемое на

входе

отрицание обеспечивается за счёт

того, что выходом мы располагаем вместе с его отрицанием.

Последнее обстоятельство позволяет, в частности, осуществлять

непосредственное взаимодействие переключательных

схем

на

триггерах с двухэтапными перекодировщиками рассмотренного

4.1.5.4

вида. В общем

случае

отрицание можно „протаскивать"

по

схеме, используя законы де Моргана, и тем самым строить

любую

переключательную

схему

на триггерах без привлечения

отрицания

либо же строить двухкаскадные схемы из одних

NOR-элементов.

4.3.4.1.

Триггерные

переключательные

схемы

для

арифметики

В качестве примера триггерной переключательной схемы

рассмотрим изображённую на рис. 186а

схему

параллельного

сумматора с триггерным накопителем; обратите внимание, что

полусумматоров здесь используется в два раза меньше, чем

обычной переключательной

схеме

(рис. 177). На рис. 186Ь

показано,

как можно дополнить эту

схему

комбинационной

схемой сдвига и тем самым сделать пригодной и для умноже-

ния.

С помощью команд сложения или сдвига открываются

нужные для выполнения соответственно сложения или сдвига

пути

(„шины");

при отсутствии новых команд в точке отсчета

времени содержимое накапливающего регистра сохраняется не-

изменным.

Умножение на натуральное число можно реализовать как

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

должно быть доступно в продолжение всего процесса умноже-

ния,

то его, как правило, помещают в специальный

регистр

множимого

(„MD-регистр"'). Схематично это показано на

рис.

187. АС-регистр

, накопитель, удлиняется вправо (вместе

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

всё произведение. Командой В (как на рис. 186Ь) открывают

шины,

нужные для сдвига

, командой А открывают шины от

MD-регистра в комбинационную

схему

сложения; управляются

команды И-элементом из позиции множителя. Множитель сам

может располагаться в некотором регистре сдвига („MR-pe-

гистре"),

тогда

очередная используемая позиция всегда нахо-

дится в правом конце этого регистра и

оттуда

считывается.

M.D — от латинского multiplicand (множимое), а появляющееся ниже

— от mutliplicator (множитель). —

Прим

изд. ред.

АС — от английского accumulator (накопитель). —

Прим.

изд. ред.

Сдвиг вправо с заполнение" освободившихся мест „нулями" О.

fi-i

команда

сложения

НА

команда

сложения

команда

сдвига

Рис.

186. Фрагмент схемы триггерного параллельного сумматора (а) без

комбинационной

схемы сдвига, (Ь) со схемой сдвига.

320

Гл. 4. Двоичные комбинационные и переключательные схемы

Из

соображений экономии часто

качестве MD-регистра

ис-

пользуется правая, первоначально незаполненная половина

АС-

регистра.

Для выполнения вычитания достаточно,

как

было сказано

4.2.3, образовать

MD-регистре обратный

код

вычитаемого,

т.

е.

подключиться

выходам-отрицаниям триггеров MD-ре-

гистра

снабдить комбинационную

схему

сложения

(рис. 167)

АВ

111

IM.Ql

11 11

iixijiixjjjy

переключательная

сложения

"тттттттттттт

Переключательная 11

111

c*e*ia

сдвига - ' ^Л

».'»;*

Рис.

187. Реализация

последовательного

умножения

помощью

параллель-

ного сложения.

полным

сумматором также

и для

разряда единиц, причем

на

вход

переноса этого сумматора

при

сложении

будем

подавать

О,

а при

вычитании

Деление очевидным образом сводится

повторному вычита-

нию

сдвигу.

Для этого нужно попеременно уменьшать

увеличивать

(на

единицу) содержимое регистра частного,

котором форми-

руется частное,

управление процессом вычитания

сложения

должно учитывать знак остатка.

При

этом остаток обычно

по-

мещается

АС-регистре, делитель

— в

MD-регистре,

частное

формируется

MR-регистре

или,

ради экономии,

освобождаю-

щейся

части АС-регистра.

остальном

по

сравнению

со

схемой

умножения ничего

не

меняется.

В настоящее время

при

реализации операций монтажными

схемами почти всегда ограничиваются четырьмя основными

арифметическими

действиями.

4.3.4.2.

Триггерные

переключательные схемы

для неарифметических операций

Различные

части триггерных переключательных схем,

по-

строенных

для

реализации базовых операций арифметики,

можно использовать

и для

реализации операций

над

нечисло-

выми объектами,

при

условии

что мы всё

время работаем