книги из ГПНТБ / Цифровые многозначные элементы и структуры учеб. пособие

нумерации цифровых шин, то есть аппаратурные затраты на реали­ зацию таких операций равны нулю. На рис. 51, например, изображе­ на схема элемента, реализующего функцию х1 = х + 1 (mod 4).

которых соответствующая им функция принимает равные значения.

у

Элементы, выполняющие двухместные операции х V У — max (х, у) и ху = min (х, у), можно реализовать так, как показано на рис. 53 и 54 соответственно (к = 3).

Y

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

90

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

рис. 53 и 54.

Описанное построение многозначных логических схем можно прос­ то реализовать методами интегральной технологии.

Операции объединения, пересечения и характеристические функ­ ции, составляющие полную схему, описанную в § 2.3, при пространст­ венном принципе представления информации можно реализовать схе­ мами из двоичных элементов ИЛИ и И, как показано на рис. 55—57, где k = 3. Пустому множеству 0 здесь соответствует отсутствие сиг­ налов на всех k шинах. Для синтеза комбинационных схем в этом

случае удобно пользоваться канонической формой (2.16), так как само задание агрументов Xj предполагает наличие сигналов Oxj,

1X), .... ( k — 1) Xj.

Пространственное представление информации, как и фазо-импульс­ ное, допускает реализацию множества логических операций посредст­ вом одной и той же схемы, причем чаще всего это достигается простым изменением нумерации цифровых шин логической схемы. Так, напри­ мер, при нумерации шин переменной х (рис. 54) всевозможными пере­ становками символов 0, 1, 2, кроме функции min (х, у), можно также реализовать функции min (3 — х, у), min (2 — х, у), min (1 — х, у), min (1 + х, у), min (2 + х, у).

Здесь сложение и вычитание выполняется по mod 3.

91

Г Л А В А 4

СИНТЕЗ ТИПОВЫХ МНОГОЗНАЧНЫХ КОМБИНАЦИОННЫХ СХЕМ

§ 4.1. Сложность многозначных комбинационных схем

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

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

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

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

Для того чтобы схема реализовала отображение ф, необходимо

ным в [14], то для построения схемы, реализующей систему функций (4.1), потребуется при конечном k и N, М -*■ оо

92

двувходовых элементов. Известно также, что в общем случае умень­ шить оценку (4.4) невозможно. Подставляя в (4.4) значения п а т , выраженные формулами (4.2) и (4.3), получаем

зом доопределив функции у} на этих наборах. Окончательно получим

Из (4.5) следует, что сложность реализации произвольной комби­ национной схемы не зависит от количества k букв структурного алфавита логических элементов, из которых состоит схема. При этом предполагается, что сложность логических элементов также не зави­ сит от k.

Рассмотрим некоторые частные случаи.

Пусть комбинационная схема реализует систему функций

не более чем от h аргументов. Следовательно, для ее реализации трс» буется не более

Л- = kh

двувходовых элементов. Для реализации подсистемы (4.8) требуется

п

у

/=Л +1 *

93

двувходовых элементов. Таким образом, сложность Lk (N, N) реа­ лизации системы (4.6) будет следующей:

Lk (N, N) — (k_ 1( lnN .

Из этого выражения видно, что с уменьшением k число двувходо­ вых логических элементов, необходимых для реализации системы (4.6), уменьшается и при k = 2 минимально.

Предположим, что систему функций (4.1) можно представить в виде

ФУНКЦИИ fjt (Xj, xt).

Вели в базисном наборе функций, реализуемых логическими эле­ ментами, существует каноническая форма типа дизъюнктивной нор­ мальной формы, можно утверждать, что для реализации любой функ­ ции f {хъ х2) потребуется не более чем ak2 двувходовых логических элементов, где а — постоянная для данного базиса величина. Тогда

L*k (N, М) = am (п — 1) k2

94

Нетрудно проверить, что (4.13) имеет минимум при k = 3.

В некоторых полных системах (например, содержащих все одноме­ стные операции) для реализации любой двухместной функции требуется не более чем ак двувходовых логических элементов (а — постоянная данного базиса). Тогда при N, М -> оо

В этом случае комбинационная схема будет иметь минимальную слож­

Из (4.15) заключаем, что сложность комбинационной схемы умень­ шается с ростом к.

Таким образом, существуют отдельные классы комбинационных схем, сложность которых зависит от к (формулы (4.13) — (4.15)). Значит существует такое к0, при котором сложность данного класса комбинационных схем минимальна. Поэтому при построении таких схем целесообразно производить оценку сложности схемы и опреде­ лять оптимальное k0. Если к0 ф k ( k — число устойчивых состояний запоминающих элементов), то для получения дополнительного сокра­ щения оборудования при построении комбинационных схем иногда следует строить эти схемы, используя &0-значный алфавит, а для согласования работы памяти и комбинационной схемы использовать преобразователи кодов (разумеется, если аппаратурные затраты на них не превосходят получаемого выигрыша).

§ 4.2. Быстродействие многозначных комбинационных схем

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

Пусть дана комбинационная схема, описываемая системой пере­ ключательных функций (4.1). Если функции у} существенно зависят от всех аргументов х{ (/ = 1, 2, ..., т\ i = 1, 2, ..., п), то каждый входной полюс х( схемы соединен с каждым выходным полюсом yh по крайней мере, одной цепью С (/, /, г) логических элементов

95

(г = 1, 2, 1ц\ 1ц > 1 — число таких цепей). Обозначим задержки, вносимые логическими элементами, через ть т2, та, где ос— число базисных функций, реализуемых логическими элементами. Тогда задержка t (i, /, г), вносимая цепью С (i, j, г), состоящей из s (с, j, г) последовательно соединенных логических элементов, будет равна

где tpv (i, /, г) — задержка, вносимая логическим элементом, стоя­ щим на у месте цепи С (г, /, г), fiv (/, /, г) — номер базисной функции, реализуемой этим элементом.

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

Tk (N, М) = пьх/(», j, t).

Чтобы получить оценки для Tk {N, М), поступим следующим образом. Из элементов, реализующих базисные функции, строим схемы, моде­ лирующие конъюнкции ху, дизъюнкции х V У и функции Js (х). В этом случае переключательную функцию можно представить кано­ нической формой (2.43). Схему, реализующую систему функций (4.1), будем строить из отдельных последовательно соединенных блоков.

Второй блок состоит из элементов типа ху и реализует все выраже­

означает ближайшее к z большее целое число, если z дробное, или же само z, если z целое).

Третий блок состоит из элементов типа х \] у и реализует все функции системы (4.1), согласно (2.43). При раздельной реализации

96

С другой стороны, известно из [14], что есть функция, для реали-

зации которой требуется не менее kn двувходовых элементов. Задерж-

где е„ -> 0 при N -> со. Из соотношений (4.16) и (4.17) следует, что при N -> оо

Th(N,M) = % - ^ .

Вобщем случае, если элементы, реализующие функцию х \/ у, имеют

рвходов, то

T k(N,M)=>Qa^ .

Рассмотрим частные случаи. Пусть комбинационная схема реали­ зует систему функций вида (4.11). Многие практически важные ком­ бинационные схемы (например, сумматоры) реализуют системы функ­ ций, которые могут быть сведены к системам, подобным (4.11). Задерж­

ка Т*к (N , М), вносимая такой схемой,

Из (4.20) заключаем, что с ростом k значение Tl (N, М ) уменьша­ ется. Такая оценка времени срабатывания комбинационной схемы справедлива, например, для многоразрядного сумматора, в цепи рас­ пространения переноса которого стоит не зависящее от k число эле­ ментов.

Предположим, что в выражении (4.11) функции обладают свойством

fit (//« -и W , z) = f ii+ i (fu {У, 2). х).

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

Оценка (4.22) справедлива, на­ пример, для времени срабаты­ вания многозначного дешифра­ тора на N выходов.

Таким образом, задержка, вносимая комбинационной схе­ мой, в общем случае не зависит от k, если быстродействие &-знач- ных логических элементов, из

Рис. 58. Структура комбинационной схемы. которых построена схема, также

не зависит от k. Однако сущест­ вует ряд типов многозначных комбинационных схем, время сраба­ тывания которых уменьшается с ростом к.

§ 4.3. Реализация симметричных переключательных функций

Среди множества многозначных переключательных функций, как и в булевой алгебре, особое место занимают симметричные функции, то есть функции, значения которых не меняются при произвольной перестановке их аргументов. К этому типу многозначных функций при­ надлежат, в частности, важные для вычислительной техники функции сложения и умножения по mod к. Ниже исследуются особенности синтеза схем, реализующих симметричные функции в классе полных систем, для каждой из которых характерно каноническое представле­ ние типа совершенной ДНФ (§ 2.6).

В этом случае операции полной системы х \J у, ху и Js (х) удовле­ творяют условиям (2.42).

Пусть а = (ocj, а2, ..., а„) — произвольный набор.

Назовем множеством симметричных наборов {а}, образованных

набором а, все наборы, получающиеся из набора а при всевозможных перестановках его компонент аи аг, ..., а „ П 0 ].

98

Введем следующие обозначения:

Anl = xl V х2. V *■■V

^ /1 2 = %\Х2 V *И'3V ‘ ‘ ‘ V ^н—l-’Oj»

Теорема. Если на каком-либо множестве симметричных наборов

щие всем наборам множества (а), то среди них найдется и такая конъюнкция, у которой s, = ViТаким образом, согласно соотноше­

ниям (2.42), левая часть выражения (4.24) на наборе у принимает

значение / (s). В свою очередь, поскольку

A \r ~ = Pi,

т\х—у

правая часть выражения (4.24) также принимает значение / (s) на

выбранном наборе.

—* —►

Пусть теперь х = у не совпадает ни с одним из наборов множест-

ва {а}. Тогда левая часть соотношения (4.24) равна Ь. Но так как

V 6 {а}, то -у не может быть решением системы уравнений (4.23). Поэтому найдется такое г, для которого

99