Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf

двувходовых элементов. Таким образом, сложность 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