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

(2.42). В такой системе блоки U, W, Q и Р можно строить согласно следующим выражениям:

ственно не более п (8,5ft2 + 6,5ft + 1,5а — 0,5а2 + 17) — 2,5/г3 —■

— 0,5ft — 7 и n2 (8,5ft2 + 6,5ft + 1,5а — 0,5а2 + 17) — п (5ft2 + ft +

+18) + 3 элементов, где а = [0,5ft].

Если двухместные операции ху и л V у обладают таким свойством,

128

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

иболее 4k — 1 элементов.

Выражения для функций и, до, q, р, s в такой системе имеют вид

Блоки R и С строят согласно выражениям (4.71) и (4.72). Для построения многотактной и одиотактной множительных схем в рас­ сматриваемой избыточной полной системе при k > 3 требуется соответ­ ственно п (2\k — 9) — Ik — 3 и п2, (2\k — 9) — п {\4k + 6) + 3

элементов.

Во многих конкретных полных системах со всеми одноместными операциями возможно дальнейшее упрощение множительных схем. Рассмотрим некоторые из них.

Если a = \ , x \ l y = x + y (mod k), а ху соответствует операции (2.30), то в этой системе, где можно просто реализовать перенос при сложении

ной множительной схемы в данной системе при k >> 3 требуется n(4k + 17) — 14 элементов, а для однотактной и2 (4k + 17) — 28п + 3 элементов.

В системе, содержащей все двухместные операции, для построе­

При к — 2 для этих же целей соответственно надо 6п — 2 и 6/г2 — 7п + + 2 элементов.

Таким образом, в общем случае сложность (то есть, общее число

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

Отсюда видно, что при k >-3 существует такое /г0, при котором слож­ ность множительных схем минимальна. Значение /г0 зависит не только от Л, В, С, D, Е, F, G, Н ,М , определяемых конкретным набором ло­ гических элементов, но и от N. Подставляя в (4.80) полученные ранее значения коэффициентов Л, В, С, D, Е, F, G, Н и М, можно убе­ диться, что полной неизбыточной системы многозначных функций, включающей только двухместные операции, в которой при достаточно большом N для построения многотактной и однотактной множитель­ ных схем требовалось бы меньше логических элементов, чем для построения соответствующих двоичных схем, не существует. Введение избыточности в функционально полный набор элементов позволяет резко снизить сложность многозначных множительных схем. Однако и в этом случае проще двоичные схемы. Однотактную множительную схему проще соответствующей двоичной схемы можно построить в модулярной системе операций, дополненной всеми одноместными операциями. Тогда при k = 14 и достаточно большом N многозначная схема будет в 1,2 раза проще двоичной схемы [12]. В системе элемен­ тов, реализующих все двухместные операции, можно строить множи­ тельные схемы, сложность которых убывает с ростом к.

При достаточно большом N многозначные (многотактная и одно­ тактная) множительные схемы, построенные в такой системе, проще

ло

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

§ 4.11. Реализация схем сложения и умножения в системе теоретико-множественных операций

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

Вводя в систему теоретико-множественных операций (§ 2.3) новую функцию х + 1 (mod k), можно представить функцию сложения мето­

Для операции умножения по любому модулю справедливы следую­ щие тождественные соотношения:

(4.81)

Благодаря соотношению (4.81) существенно упрощается реализация операции умножения, поскольку можно рассматривать только неко­ торую часть таблицы истинности этой функции, которая связана со значениями аргументов, не превышающими [0,5 k]. Действительно, предположим, что какой-либо из аргументов принимает значение, большее [0,5 k\. В таком случае далее можно оперировать с его допол­ нением и затем получить дополнение результата. Таблица истинности функции умножения имеет несколько осей симметрии, каждая из ко­ торых соответствует одному из соотношений (4.81). Эти оси показаны