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

Набор одноместных операций J s (х), х1, (х)‘ и двухместных J (х\,

х2), J ((лу)', х2) назовем набором D, а указанные операции — символа­ ми из набора D. Конечное число символов из набора D, объединенных знаками конъюнкции, назовем произведением.

Элементарным произведением называется произведение конечного числа попарно различных символов из набора D и константы, причем: 1) среди всех членов произведения может встречаться только один какой-нибудь символ одноместной операции над данным аргументом

из набора D; 2) если в произведении есть символ J ((ху/, х2) либо сим­

вол J ((лу/, х2), то среди символов операций над аргументами хх и х2 в элементарном произведении может быть лишь один из 4-х символов:

х\, (хiY, где / = 1,2.

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

Нетрудно проверить справедливость следующих тождественных соотношений:

(k— l)J 0(x )\/(k — 2)J1(x)V ••• У \Jk- 2 {x) = ~x,

Js (х) ~ Js+i (х ).

J s (x) = J 7 (х).

В рассматриваемой системе помимо операций склеивания по опе­ раторам и аргументам, согласно соотношениям (2.48) и (2.49), справе­ дливы также операции склеивания, согласно следующим соотношениям

1201:

Это утверждение очевидно, ибо любая простая импликанта как эле­ ментарное произведение может включать в себя в качестве сомножите­ лей лишь символы из набора D, получение которых обеспечивается приведенными соотношениями. Однако при больших k и п выбор ми­ нимальной ДНФ затруднителен, так как необходимо перебрать боль­ шое количество простых импликант.

Правила поглощения одного элементарного произведения другим очевидны и почти повторяют описанные в § 2.7. Для того чтобы эле­ ментарное произведение Р х поглощало элементарное произведение Р 2,

а в Р 2 входит функция Js (х), где s + / > С2 в первом случае и h —

— s — 1 >• С2 — во втором;

Таким образом, использование избыточной базисной системы приводит к усложнению алгоритма минимизации и к возрастанию пе­ ребора при выборе минимальной ДНФ в связи с увеличением количе­

71

ства простых импликант. Между тем, при построении соотношений (2.51)—(2.55) учитывались далеко не все возможные суперпозиции даже среди одноместных функций [20]. Поэтому для некоторого упро­ щения алгоритма минимизации введены ограничения в определение элементарного произведения. Дополнительные трудности возникают также из-за необходимости сравнения сложности реализации простых импликант и элементарных произведений, которые ими накрываются.

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

§ 2.10. Минимизация многозначных функций в системе со всеми одноместными операциями

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

СДНФ [21 ]. Например, СДНФ функции х — k — 1 — х (mod k) имеет вид

X = V {k— \ — i) Ji (х),

( = 0

а соотношение склеивания для той же функции

Р V (& — 1— i)Ji(x) = Рх.

i = 0

В рассматриваемой системе таких соотношений будет kk, и любое из них можно легко использовать. Алгоритм отыскания простых им­

вует следующий простой пример.

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

Если же в систему функций (например Россера — Тьюкетта) вклю­ чить только одноместные функции х‘ = х + i (mod As), t = 1, 2, ...

..., k — 1,' о в результате такой же операции (если столбец или строка не содержат 0) получается k + 1 простая импликанта [20]. Очевидно^

72

что перебор при выборе минимальной ДНФ данной функции в первом случае значительно меньше.

Выбрать нужное из kk соотношений склеивания легко, сгруп­ пировав склеиваемые произведения. Например, пусть для функции, заданной табл. 18, выполняется операция склеивания над произведе­ ниями, соответствующими строке с лу = 2,

3J2 (Хх) J0 (Х2) V 2</2 (-^l) J l (X2) V 1*^2 (Xl) (-^2) V 2«/jj (xy) J3 (x2).

Вынеся функции J2 (xx) за скобки, внутри скобок получаем СДНФ

какой-то одноместной функции, то есть одно из kk соотношений склеи­ вания. В данном случае

V ' рш)*= pr.

1=0

Для произвольной одноместной функции соотношение склеивания

получают из ее канонической формы. Например, для функции х оно имеет вид

к- 1 (xi) ?/?—I —i

V р

где Р, R £ М к, а М к — множество всех подмножеств множества Е'к.

§ 2.11. Минимизация многозначных функций в других полных системах

Минимизация многозначных функций во многих других полных системах операций основывается на использовании соотношений, подобных соотношениям склеивания (2.48), (2.49) и поглощения (2.50).

73

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

Введение избыточности в функционально полную систему приво­ дит к увеличению числа соотношений склеивания и, следовательно, открывает дополнительные возможности минимизации. Наряду с

При включении в эту же систему функций ср (х) к описанным выше

V P P f X) ... PmX)

или при m = 0

VP (ix)W) = v ' P (ix)W) V -Рф (x). 1=0 1=0

В [16] обсуждаются возможности минимизации в системе, содер­ жащей двухместные операции min (хъ х2), max (хъ х2) и одноместные операции /у (х) = — х, f2 (х, s) = J s (х).

При этом аргументы и функции принимают значения из множества Ез = {— 1, 0, 1}. Каждой из п троичных переменных соответствует

74

Г Л А В А 3

МНОГОЗНАЧНЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

§ 3.1. Выбор полного набора логических элементов

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

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

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

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

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

76

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

Таким образом, основные требования, предъявляемые к наборам логических элементов, следующие:

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

2)схемная простота и надежность элементов;

3)ограниченное количество различных типов логических эле­ ментов;

4)наличие операций, на базе которых строится одна из стандарт­

ных канонических форм или, в крайнем случае, допускается простая реализация таких операций в данной системе функций;

типовых переключательных функций.

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

§ 3.2. Многозначные логические элементы при фазо-импульсном принципе представления информации

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

При фазо-импульсном принципе представления информации носи­ телем информации служит фазовый сдвиг периодической последова­ тельности импульсов относительно следующих с той же частотой опорных импульсов, соответствующих нулевому значению истинности. На рис, 36 для случая k = 10 изображены: периодическая последо­

77

вательность опорных импульсов (а); периодическая последователь­ ность импульсов, соответствующих значению 1 (е), значению 8 (с), значению 9 (d); синхронизирующие импульсы и шкала состояний при прямом (е) и обратном (/) кодировании.

Временной интервал между двумя соседними импульсами опор­ ной последовательности называется тактом.

Рис. 36. Временная диаграмма работы многозначного логического эле­ мента при фазоимпульсном принципе представления информации.

Рассмотрим функциональную полную систему Россера— Тьюкетта, включающую операции шах (х , у), min (х, у), Js (х).

Функция шах (х, у) при прямом кодировании реализуется схемой, выделяющей второй из пришедших на ее входы импульсов (рис. 37).

В этой схеме есть накопитель на кон­ денсаторах, компаратор К и регене­ ратор Р. Входные конденсаторы имеют 5 ^ 7 равные номиналы. Импульс на любом из входов х или у обеспечивает при­ ращение напряжения на емкостном накопителе. Сигнал на выходе схемы появляется только после второго им­ пульса, поступающего на накопитель­ ную емкость, что соответствует боль­ шему числу, или же при одновремен­

ном появлении импульсов на обоих входах. Для предотвращения ложного срабатывания схемы сброса, если в данном такте нет како­ го-либо из входных сигналов, накопительный конденсатор разряжа­ ется перед началом такта серий импульсов, соответствующих значе­ нию k — 1 и подаваемых через линию задержки. При обратном ко­ дировании схема реализует функцию min (х, у).

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

78

мому, простейшей реализацией является схема, изображенная на рис. 38. Чтобы восстановить исходный режим на обмотку 2 феррито­ вого сердечника, подается периодическая последовательность импуль­ сов, которые соответствуют значению k — 1. Эта последовательность задержана на время перемагничивания ферритового сердечника для предотвращения сбоя при х = у = k — 1. При обратном кодирова­ нии входных импульсов схема будет реализовать функцию max (х, у).

ки, выполненной, например, на двух ферритовых сердечниках (рис. 39, а, если s ф 0 и рис. 39, б, если s — 0).

Исходное состояние схемы (рис. 39, а) устанавливается импульса­ ми 03 и k — 1, проходящими по обмоткам 7 и 8 соответственно (03— импульс константы 0, задержанный на время перемагничивания

Рис. 39. Схемы регулируемой задержки, реализующие функцию Js (х)\

а — при s^tO; б — при s = О,

сердечника). Входная цепь обеспечивает перемагничивание обоих сердечников лишь при х = s. При этом на выходе импульса нет, так как обмотки считывания 5 и б включены встречно. Сердечник 1 возвра­ щается в исходное состояние импульсом k — 1, который проходит на выход через диод D, Если же х Ф s, сердечник 1 не перемагничи-

79