авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |   ...   | 9 |

«ФЕДЕРАЛЬНОЕ КОСМИЧЕСКОЕ АГЕНТСТВО Федеральное государственное унитарное предприятие "Научно-производственный центр "Полюс" В.И. Кочергин ТЕОРИЯ ...»

-- [ Страница 2 ] --

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

1.4. Бинарные логические операции в двухмерном цифровом пространстве Общепринятое аналитическое рассмотрение бинарных логических опера¬ ций, как правило, начинается с представления Л Ф двух аргументов x x, что b представлено табл. 1.4.1.

Таблица 1.4. оцк Х2 X i y y y y y y y y y y y y y y y y 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0* 1* 0* 1* 0* 1* 0* 1* 0* 1* 0* 1* 0* 1* 0* 1* * * 1 0* 0* 1* 1* 0* 0* 1* 1* 0* 0* 1* 1* 0* 0* 1* 1* 0 * * 2 0* 0* 0* 0* 1* 1* 1* 1* 0* 0* 0* 0* 1* 1* 1* 1* 1 3 0* 0* 0* 0* 0* 0* 0* 0* 1* 1* 1* 1* 1* 1* 1* 1* * * 1 Н е будем перечислять известные из учебной литературы названия и обо¬ значения логических операций, представленных в этой таблице.

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

Н а рис. 1.5 п р и в е д е н ы г е о м е т р и ч е с к и е о б р а з ы всех ш е с т н а д ц а т и бинар¬ н ы х Л Ф в д в у х м е р н о м п р о с т р а н с т в е E, которое и м е е т пять осей с и м м е т ­ рии 1-5. Допуская, что входы и в ы х о д ы логических блоков и м е ю т ш и н ы п р я м ы х и инверсных сигналов, число рассматриваемых фигур в пространстве л ю б о й кратности значительно сокращается. Д л я нашего случая y = y, y = 1 16 = y15, y3 = y14, y9= y8, y5= y12, y4 = y13, УН = y6, УЮ = y7.

О E C =y = C ° = yi 4 i X! C4*(1) = У C '(1) = y 4 C4 (2) = уз C4 (2) = У C4 (3) = У9 C4 (3) = У C4 (4) = У5 C4 (4) = y i * * * C4 (l) = У4 C4 (6) = У 2 C4 (2) = У11 C4 (5) = У C4 (4) = y C4 (3) = У Рис. 1. Дальнейшее сокращение количества рассматриваемых фигур связано с симметрией пространства E. М ы с л е н н ы й п о в о р о т вокруг оси 1 п р и в о д и т к записи аргумента x Л Ф в обратном коде x —» x ;

п о в о р о т вокруг оси 2 - к записи аргумента x в ис­ 1 1 х о д н о й Л Ф в обратном коде x — x2;

п о в о р о т вокруг оси 3 приводит к смене местами аргументов (x, x ) — (x, x ) ;

поворот вокруг оси 4 приводит к сме­ 1 2 2 не местами аргументов, а т а к ж е записи и х в обратном коде (x, x ) — ( x, x ) ;

1 2 к а ж д ы й последовательный м ы с л е н н ы й поворот вокруг оси 5 на 90° против ча¬ совой стрелки п р и в о д и т к смене местами аргументов с о д н о в р е м е н н о й запи¬ сью первого из н и х в обратном коде, что иллюстрируется с л е д у ю щ и м обра­ зом: — (x1, x2) — — (x2, x1) — (x1, x2) — (x2, x 1 ) — (x1, x 2 ), а при вращении в противоположном направлении - к смене аргументов в обратном направлении.

И с х о д я из симметрии двухмерного цифрового пространства и убрав из рас­ смотрения тривиальные функции у = 0 = 0*, у = E = 1*, конструкцию л ю б о 1 16 го логического блока двух аргументов определяем только одной из первообраз­ н ы х фигур y, y, у ю, а остальные фигуры получаются соответствующими 2 м ы с л е н н ы м и поворотами вокруг осей симметрии.

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

И з фигур, получаемых сочетанием из четырех по одному, это функция x у = C ( 1 ), а остальным, которые получаются соответствующим м ы с л е н н ы м по­ 2 1 воротом, присвоим с л е д у ю щ и е порядковые номера: у = C ( 2 ), у = C ( 3 ), 3 4 9 У5 = C 4(4).

И з фигур, получаемых сочетанием из четырех по два, первая первообраз¬ ная - у = C ( 1 ), а о с т а л ь н ы е будут и м е т ь с л е д у ю щ и е о б о з н а ч е н и я : у = 4 4 2 2 = C ( 2 ), у = C ( 3 ), у = C ( 4 ) ;

вторая первообразная - сочетания из четырех 4 13 4 6 2 по два - у = C ( 5 ), а ее образующая - у = C ( 1 ).

10 4 4 Фигурам, получаемым сочетанием из четырех по три, присвоим порядковые 3 3 3 номера их дополнений: у = C ( 1 ), у = C ( 2 ), у = C ( 3 ), у = C ( 4 ).

15 4 14 4 8 4 12 1.5. Сложные логические функции в двухмерном цифровом пространстве П р и рассмотрении арифметических и логических операций нами использу­ ется финитная точка зрения, которая совершается «в виде мысленных экспери­ ментов над наглядно представляемыми объектами и не зависит от предложений аксиоматического характера. Рассуждения такого рода называются финитными, а методическая установка, л е ж а щ а я в основе таких рассуждений, называется финитной установкой или финитной точкой зрения».

Известно, что л ю б ы е арифметические операции совершаются над конкрет¬ н ы м и значениями цифровых данных, которые обычно называются операндами.

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

П у с т ь логическая функция состоит из двух аргументов A, B, которые, в свою очередь, эквивалентны цифрам натурального ряда 0, 1,..., (n - 1) и за¬ кодированы л ю б ы м известным способом.

П р я м о й порядок следования цифр натурального ряда м о ж е т быть пред¬ ставлен вектором, в начале которого р а с п о л о ж е н « э л е м е н т а р н ы й кубик», ну¬ м е р о в а н н ы й ц и ф р о й 0, а в конце вектора - « э л е м е н т а р н ы й кубик» под номе¬ р о м (n -1). И с х о д я из векторного представления аргументов, на рис. 1.6 графи¬ чески показаны преобразования аргументов A, B логических функций при соответствующих м ы с л е н н ы х поворотах вокруг осей симметрии 1-5. В них ис­ х о д н ы е положения векторов аргументов записываются в виде F (A, B), а при соответствующем повороте изменяется порядок их следования либо (и) проис¬ х о д и т преобразование кода аргументов из прямого в обратный, когда новое по¬ л о ж е н и е вектора противоположно исходному вектору в функции F (A, B).

F (В,А) F (А,В) F (А,В) F (А,В) F (В,А) •V Л А в F (В,А) А 90° •4 F (А,В) в 180° F (В,А) \\ 270°" Рис. 1. М ы с л е н н ы й поворот вокруг оси 1 производит перевод аргумента A из пря­ мого кода в обратный, когда новое положение фигуры логической функции и ее покрытие будут определяться первообразной логической функцией, где аргу­ м е н т A взят в обратном коде, что запишется следующим образом: F (A*, B).

Н а рисунке, соответствующем этому повороту вокруг оси 1, новое положе­ ние вектора аргумента A противоположно исходному п о л о ж е н и ю этого же век­ тора и обозначено A*, при этом вектор B сохраняет свое первоначальное на¬ правление.

Е щ е один пример мысленного поворота относительно оси 5, из которого станут более понятны все преобразования рис. 1.6.

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

F (B,A*) и т.д.

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

М ы с л е н н ы е повороты относительно осей 1-4 - это простые повороты, а поворот относительно оси 5 - сложный поворот, который может быть осуще¬ ствлен двумя последовательными поворотами вокруг осей 1 - 4.

Н а рис. 1.7 представлены все возможные положения аргументов A, B, кото¬ р ы е достигаются соответствующими м ы с л е н н ы м и поворотами относительно осей симметрии пространства.

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

AB Рис. 1. AB AB BA BA AB AB б) a) Рис. 1. К числу таких циклических кодов относятся о б ы ч н ы й цифровой код, кото­ р ы й составляет основу многозначной логики, а также многофазные коды, ле­ ж а щ и е в основе большинства устройств электротехники. М н о г о ф а з н ы е коды относятся также к числу так называемых геометрических кодов, где под терми­ ном «геометрический код» понимается то, что эквивалентная цифра натураль­ ного ряда в этих типах кодов может определяться не только соответствующей конъюнкцией максимального ранга, но и взаимным геометрическим положе­ нием их сигналов. К слову сказать, алгебра Буля не применима для синтеза и анализа устройств, использующих геометрические коды.

Для выполнения всех приведенных в ы ш е мысленных поворотов и их анали¬ тического представления наиболее удобно ограничиться последовательным ис¬ пользованием только поворотов относительно осей 1-3. Поворот относительно осей 1 и 2 приводит к переводу соответствующего вектора (аргумента) из пря­ мого кода в обратный и наоборот. Аналитически это записывается с л е д у ю щ и м образом: либо, а поворот вокруг оси 3, который соответствует смене местами векторов, запишется как (AB) Н а рис. 1.8, а показаны все возможные мысленные положения аргументов A и B, которые реализуются соответствующим мысленным поворотом отно¬ сительно осей 1-5. В отличие от предыдущего (см. рис. 1.7), здесь показаны только переходы из одного мысленного положения системы координат в дру¬ гие, а на рис. 1.8, б - то ж е самое, но с использованием таких поворотов отно¬ сительно только осей 1-3.

Для большей прозрачности и наглядности преобразований геометрического образа логической функции в двухмерном цифровом пространстве при мыслен ных поворотах этого образа относительно осей 1-5 представим, например, ар¬ гументы A и B в системе счисления основания n = 4. Тогда исходная нумерация ячеек двухмерного цифрового пространства, которая всегда остаётся неизмен¬ ной, будет совпадать с нумерацией кодовых слов, определяющих каждое еди A 3 0 I 2 о/о 1/1 2/2 3/ B 6/ 5/ 4/4 7/ 2 1о/1о 11/ 8/8 9/ 12/12 13/13 14/14 15/ \ F ( A B) 0/3 1/2 2/1 3/0 0/12 1/13 2/14 3/15 0/0 1/4 2/8 3/12 0/15 2/7 3/ 1/ 4/7 5/6 6/5 7/4 4/8 5/9 6/10 7/11 4/1 5/5 6/9 7/13 4/14 5/10 6/6 7/ 8/11 9/10 10/9 11/8 8/4 9/5 10/6 11/7 8/2 9/6 10/10 11/14 8/13 9/9 10/5 11/ 12/15 13/14 14/13 15/12 12/0 13/1 14/2 15/3 12/3 13/7 14/11 15/15 12/12 13/8 14/4 15/ Ось 3, F(B A) Ось 1, Ось 2, Ось 4, A' F ( A ' B) F ( A B') F(B' 0/3 1/7 2/11 3/15 0/15 1/14 2/13 3/12 0/12 1/8 2/4 3/ 4/2 5/6 6/10 7/14 4/11 5/10 6/9 7/8 4/13 5/9 6/5 7/ 90° 180° 270° 8/1 9/5 10/9 11/13 8/7 9/6 10/5 11/4 8/14 9/10 10/6 11/ 12/0 13/4 14/8 15/12 12/3 13/2 14/1 15/0 12/15 13/11 14/7 15/ Ось 5, F ( B Ось 5, Ось 5, F ( B ' ' A) F ( A ' B') A) Рис. 1.9а ничное множество геометрического образа логической функции. Это положение подтверждено рис. 1.9а, где исходная логическая функция занимает место в ячейках пространства, например, с номерами 1, 2, 5, a 6, 8. Следовательно, в этих ячейках цифрового про­ странства должны быть помещены, как м ы услови­ a лись выше, знаки логической функции 1*. Пусть, например, цифры натурального ряда 0 - 3 представ­ 0 1 3 лены двумя вариантами кодирования: в двоичном a, 2 3 0 a и двухфазном a, a кодах. Н а рис. 1.9б показаны 2 1 соотношения между сигналами для прямого A и об¬ а ратного A' следования цифр этого операнда.

( А* П р я м о е (0 - 3) и обратное (3 - 0) следование а ц и ф р операнда A определяет взаимно однозначные Рис. 1.9б соотношения между аргументами этих кодов: для двоичного п р и н ц и п а кодирования это общеизвест н ы е соотношения a = a, a = a ;

для двухфазного - это еще более простое соот 1 1 a2. Н а данном примере очевиден принцип получения взаимно ношение: a однозначных соотношений между аргументами л ю б ы х типов кодов для любого основания системы счисления при переводе кода из прямого в обратный.

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

Геометрический образ исходной логической функции F(A B) размещается в ячейках пространства, где номер ячейки (числитель дроби) всегда совпадает с номером кодового слова (знаменатель дроби), определяющего при выбранном способе кодирования определенную к о н ъ ю н к ц и ю соответствующего ранга.

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

Это изменение представлено числителем дроби в соответствующих ячейках пространства.

С учетом этого м о ж н о представить соответствующие логические функции при двоичном принципе кодирования с л е д у ю щ и м о б р а з о м :

F(A B) = a1 a2 b v a a2 b v a a2 b b2, F(A* B) = a1 a2 b2 v a1 a2 b2 v a1 a2 b1 b2, F(A B*) = a1 a2 b2 v a1 a2 b2 v a1 a2 b1 b, F(A* B*) = a1 a2 b2 v a1 a2 b2 v a1 a2 b1 b, F(B A) = b b2 a2 v b1 b2 a2 v b b a1 a2, F(B* A) = b b2 a2 v b1 b a2 v b1 b2 a1 a2, F(B A*) = b b a2 v b1 b2 a2 v b b a1 a2, F(B* A*) = b b a v b b a v b b a a. (1.5.1) 2 2 1 2 1 2 1 Аналогично при двухфазном принципе кодирования э т и логические функ¬ ции будут п р о щ е :

F(A B) ai bj v ai Q2 bi b2, * F(A B) ai bj v ai a2 bi b2, * F(A B ) ai b2 v ai a2 bi h, * * F(A B ) •- ai b2 v ai a2 bi bj, F(B A) bi a2 v h bj ai a, * F(B A) bi a2 v h b2 ai a2, * F(B A ) bi a2 v h bj ai a2, F(B* A*) :

b a v b b a a. (1.5.2) i 2 i 2 i К а ж д а я логическая функция в (1.5.1), а также в (1.5.2) реализуется одной и той ж е принципиальной схемой, где на её входных шинах меняется только по¬ рядок их соединения с сигналами операндов.

Теперь представим, что в операндах использованы различные принципы кодирования оснований системы счисления: операнд A поступает в двухфазном коде, а операнд B - в двоичном коде. В этом случае рассматриваемые нами ло¬ гические функции будут иметь иной вид F(A B) = a b v a bb, 1 1 1 F(A* B) = a b v a a b b, 1 2 1 2 1 F(A B*) = a b v a a2 b b, 1 2 1 1 F(A* B*) = a b v a a b b, 1 2 1 2 1 F(B A) = a2 b1 b_2 v a2 b1 b2 v a1 a2 b b_2, F(B* A) = a2 b1 b2 v a2 b1 b_2 v a1 a2 b b2, F(B A*) = a2 b1 b_2 v a2 b b2 v a1 a2 b b_2, F(B* A*) = a b b v a b b v a aa b b. (1.5.3) 2 1 2 2 1 2 1 1 И з выражений (1.5.3) следует, ч т о при использовании операндов с одина¬ ковым значением основания системы счисления, но разным способом его коди¬ рования число принципиальных схем, реализующих покрытие подобных фигур, будет равно числу операндов.

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

1) геометрический образ конкретной логической функции может иметь «лучшее покрытие», т. е. минимальные затраты оборудования для определенно¬ го принципа кодирования этого основания системы счисления;

2) алгебра Буля не позволяет анализировать и синтезировать логические функции, находящиеся вне правил двоичного принципа кодирования;

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

1.6. Тернарные логические операции в трехмерном цифровом пространстве Число тернарных логических операций весьма значительно (2 = 256) и по¬ этому они, в отличие от бинарных, в литературе отдельно не рассматриваются.

В м е с т е с тем, используя геометрические аналоги логических функций в трех¬ мерном цифровом пространстве, все геометрические образы этих логических функций могут быть представлены не 2 5 6 фигурами, а только 22. Э т и геометрические образы логических функций приведены на рис. 1.10.

Н а рис. 1.10 показаны только такие представители геометриче¬ ского образа Л Ф, где отчетливо видны все элементарные кубики.

С учетом того, что входы и вы¬ х о д ы логических блоков являются С*.(3) С\(6) С«(5) бинарными, можно записать:

0 8 1 С 8(1) = С 8(1), С 8(1) = С 8(1), 2 6 2 С 8(1) = С 8(1), С 8(2) = С 8(2), У- У 2 6 3 С 8(3) = С 8(3), С 8(1) = С 8(1), С'.(2) 3 5 3 С 8(2) = С 8(2), С 8(3) = С 8(3).

П р и этом, если не учитывать л— пустое и универсальное множест¬ У- У ва, число этих функций сокраща¬ ется до 13. cVi) Это следующие функции:

1 у1 = С 8 ( 1 ) = Х1 Х2 Х3;

у2 = С 8 ( 1 ) = Рис. 1. = Х2 Х3;

у3 = С 8(2) = Х1 Х2 Х3 v v Х1 Х2 Х3;

у4 = С \ ( 3 ) = Х1 Х2 Х3 v 3 3 v Х1 Х2 Х3;

у5 = С 8(1) = Х2 Х3 v Х1 Хь у6 = С 8(2) = Х2 Х3 v Х1 Х2 Х3;

у7 = С 8(3) = = Х1 Х2 Х3 v Х1 Х2 Х3 v Х1 Х2 Х3;

у8 4 С 8(1) = Х3;

у9 = С 8(2) = Х2 Х1 v Х1 Х3;

у ю = С 8(3) = Х2 Х3 v Х1 Х3 v Х1 Х3 Х2;

- у и = С 8(4) = Х2 Х3 v Х1 Х3 v Х1 Х2;

4 у12 = С 8(5) = Х2 Х3 v Х2 Х3;

у13 С 8(6) = Х1 Х2 Х3 v Х1 Х2 Х3 v Х1 Х2 Х3 v Х1 Х2 Х3.

Представленные здесь оптимальные покрытия «объемов» этих 13 фигур оп¬ ределяют также все 2 5 4 тернарные логические операции. Правила пользования этими 13 фигурами для определения всех остальных фигур будут понятны по¬ сле изучения симметрии трехмерного цифрового пространства.

1.7. Сложные логические функции в многомерном цифровом пространстве В полном соответствии с определениями п. 1.5 рассмотрим изображения с л о ж н ы х логических функций от трех аргументов, определяемых их цифровы¬ ми векторами A, B, C, в трехмерном цифровом пространстве. П р и этом иссле¬ дуем преобразование фигур логических функций в трехмерном цифровом про¬ странстве, осуществляемое соответствующим м ы с л е н н ы м поворотом либо не¬ сколькими такими поворотами относительно осей симметрии этого пространст¬ ва. И з кристаллографии известно 13 осей симметрии кубика, которыми, однако, не исчерпываются все оси симметрии рассматриваемого цифрового простран­ ства, поскольку в нем возможно еще и «послойное», т.е. двухмерное выполне­ ние соответствующих м ы с л е н н ы х поворотов.

Число в о з м о ж н ы х взаимных положений векторов аргументов можно опре­ делить чисто аналитически путем соответствующего перебора всех размещений из шести (A, B, C, Л*, Б*, C*) по три, из которых необходимо будет исключить такие, где встречаются взаимно и с к л ю ч а ю щ и е сочетания ( A, Л*;

Б, Б*;

C, C*).

Однако такое определение весьма трудоёмко и особенно для большой мерно­ сти пространства. Оно не обладает необходимой прозрачностью для дальней¬ шего использования.

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

Повороты относительно осей симметрии под номерами 1—9 выполняются одновременными операциями над всеми «слоями» элементарных кубиков циф¬ рового пространства. Остальные повороты осуществляются относительно из¬ вестных из кристаллографии 13 осей симметрии кубика. П о в о р о т ы с номерами 10 —12 выполняются последовательно через 90° (три поворота), повороты с но­ мерами от 13 до 18 — одиночные через 180°, а с номерами от 19 до 22 — после­ довательные двойные повороты через 120°.

АВС АВС АВС ВАС СВА АСВ а) СВА ВАС АСВ •• •• АВС АВС АВС СВА ВАС АСВ /О Рис. 1.11 (начало) / Л ВАС СВА ВАС У 13 ••• ••• АСВ АСВ СВА 16 7f. CAB ВСА •• ВСА CAB б) г ВСА CAB •• ВСА CAB У Рис. 1.11 (продолжение) В з а и м н ы е расположения векторов аргументов (их вместе с исходным 33), представленных выше, не определяют всего их числа. Другие 15 положений векторов аргументов образуются с л о ж н ы м и поворотами, например, новое по­ л о ж е н и е векторов A*B*C* может быть получено следующими поворотами из первоначального положения: A B C 1—» A * B C 2—» A*B*C 3—» A*B*C* ли­ бо A B C 17— A*C*B* 7— A*B*C* и т.д. Здесь, например, запись A B C 1— A * B C означает, что исходное положение координат аргументов A B C при осуществ¬ лении поворота относительно оси 1 приведет к смене аргумента A в исходной системе координат из прямого кода в обратный, что в этом случае будет запи­ сано как A * B C, и т.д.

П р и в е д е м графическое представление изменений исходной системы коор¬ динат A B C при осуществлении соответствующих поворотов относительно при¬ в е д е н н ы х в ы ш е осей симметрии трехмерного цифрового пространства.

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

Е с л и для одномерного цифрового пространства A - это один поворот A ^, то для двухмерного пространства A B к нему необходимо добавить поворот второго вектора и поворот ( A B ) ^ (иное обозначение: ( A B ) ^ 180°).

Д л я трехмерного цифрового пространства ABC к этим поворотам необхо­ д и м о добавить поворот C ^ и два поворота относительно оси под номером (см. рис. 1.11, б), которые представляются с л е д у ю щ и м образом: (ABC) ^ 120°, (ABC ) ^ 240°.

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

BAC„--' 240° ABC • •• CAB/Л с ACB AcB О CBA CBAo BCA ' - - A - - ' CBA BAC v -'« ( BCA BAC ABC Рис. 1. В о б щ е м случае м о ж н о утверждать, что гипотетическая асимметричная от¬ носительно всех осей симметрии фигура сложной логической функции трех¬ мерного цифрового пространства может занять в пространстве 48 положений.

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

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

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

Для рассмотрения симметрии цифрового пространства большей мерности продолжим расширение минимального базиса осей поворотов и представим его следующей табличной схемой:

A A* AB A° B° AB° ABC A° AB* CA* ABC ° 120 ABC ° DA*-* ABC ° 120 BCD° 120 CDA ° 120 DAB° ABCD ABC° 240 BCD° 240 CDA° 240 DAB° A B C D ° 90 ABCD °180 A B C D ° 270 и т.д.

И з н е ё следует, что если и з в е с т н ы все в з а и м н ы е п о л о ж е н и я векторов ар­ г у м е н т о в с л о ж н о й ф у н к ц и и д л я (k - 1)-мерного ц и ф р о в о г о пространства, н а п р и м е р с ч и с л о м S( ), т о д л я k-й м е р н о с т и ц и ф р о в о г о п р о с т р а н с т в а вза¬ K- и м н о е п о л о ж е н и е векторов будет о п р е д е л я т ь с я с о о т в е т с т в у ю щ и м и поворо¬ т а м и (k - 1)-мерности пространства. Ч и с л о р а з л и ч н ы х п о л о ж е н и й векторов аргументов сложной функции определяется следующей зависимостью:

K S K = S(K-1) 2 K = 2 ( K ! ).

Для одномерного пространства это значение равно 2, двухмерного - 8, трехмерного - 48, четырехмерного - 384, пятимерного - 3840 и т.д. Значение этих чисел резко возрастает с увеличением мерности пространства, но о н и с та¬ кой ж е интенсивностью у м е н ь ш а ю т и общее число логических функций мно¬ гомерного цифрового пространства, которые нам необходимо изучать.

Для большей прозрачности представленных в этом разделе материалов рас¬ смотрим трехмерное цифровое пространство A B C, где основание системы счис¬ ления равно 2, а в его ячейках размещены некоторые цифровые подмножества геометрические образы логических функций F - F. Тогда на основании изложен¬ 0 ного выше покажем новые положения этих подмножеств цифрового пространства при выполнении мысленных преобразований координат (см. рис. 1.12), что пред¬ ставляется следующим образом:

ABC A* B C Fo F2 F i F3 F2 Fo F3 F i Fo F i F2 F3 Fi F F F o 3 F4 F5 F6 F 7 F4 F6 F5 F7 F6 F4 F7 F F5 F F F 4 7 * A* B* C A B!* C B A* C C B I* V V V V F2 F i Fo F F F i i F7 Zl_ F6 F4 F5 F7 F4 F F7 F6 F4 F2 l 4 _ F A* B* C* A B* C* B* A* C* B A* C* F6 F F F F F F F F F F 7 4 5 7 5 6 4 7 4 I I I I I I I I I F3 F2 F i Fo F F F F F F F F F F F F 2 3 o i 3 1 2 o 1 3 o * J C* * B A C* A B C* B A C* l A F6 F5 F F F F 6 6 F2 F3 Fi Fo F2 F i F3 Fi Fo F i F2 F2 Fo B CA CBA I Fo F2 F4 F6 F2 F F F F F F F F F F F o 6 4 o 4 2 6 o 6 I I I I I I I F i F3 F5 F7 F3 F F F F F F F F F F i 7 5 1 5 3 7 1 7 B* C* A B C* A C* B* A ~ C B* A | | I F"4~ Fo F6 ' F F4 F2 Fo F F F F F F F F 4 6 o 2 6 o I I I I 5I1 I I F3 F i F7 F7 3 F F F F F F F F F F F 5 7 i 3 7 1 * B* C* A* B C* A* CBA C B* A* T7 T7 T7 T7 T F7 F5 F3 F i F F F F F F F F F F 5 7 3 7 3 5 3 7 1 F6 F 4 F2 F Fo F4 l 6 _ I o _ F2 F6 l 4 _ Fo I o _ F F B C A* B* C A* C B A* C* B A* F i F3 F5 F7 F3 F i F7 F5 F i F5 F3 F7 F5 F i F7 F Fo F2 F4 F6 F6 F4 Fo F4 F2 F6 F4 Fo F6 F F * AB CAB ACB A* C B C T7 T Fo F4 F i F5 Fo F i F4 F5 F i Fo F F F 4 i F2 F6 F3 F7 F2 F3 F6 F F6 F3 F2 F F * с* B AC в :* с A* в C* A* B A i I F i F4 Fo Fo Fi F F5 F F F F i 5 o 4 F F 5 T?

I3I6I2 I I I F7 F6 F3 F F F F F F F F F 7 3 7 2 F71 F21 F * :* в* C* A* B* с A* в* A V V F3 F F F F F F F F 7 3 6 2 7 2 6 F F 7 T?

I I I I I F4 F i Fo F F F F F F F 5 i 4 o 5 o 1 Fo1 F i F4 F C A B* C* A B* A C B* * f I)* F3 F6 F7 F3 F2 F7 F F6 F3 F7 F6 F2 F7 F Fo F4 F i F5 F4 Fo F5 F i Fo F i F4 F5 F i Fo F5 F И з этого пояснения становится ясно, каким образом изложенные в п. 1.5 оп¬ т и м а л ь н ы е покрытия «объемов» 13 первообразных фигур трехмерного цифро¬ вого пространства определяют все 254 варианта выполнения трехвходового ло¬ гического блока.

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

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

подмножества этих множеств в результате таких м ы с л е н н ы х операций не раз¬ биваются на более мелкие и не объединяются в более крупные подмножества.

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

1.8. Непрерывное множество ряда натуральных чисел в многомерном цифровом пространстве И з предыдущего рассмотрения нетрудно представить физический образ не¬ прерывного множества натуральных чисел от 0 до ( N - 1) для л ю б ы х оснований систем счисления и принципов их кодирования. Этот физический образ с уве¬ личением N непрерывно изменяет свою форму. Т е м не менее м о ж н о записать оптимальное покрытие этой многомерной фигуры, т. е. определить логическую тупиковую ф у н к ц и ю в базисе Д Н Ф [3].

Логическая функция этого непрерывного множества, определяемого числом его элементарных кубиков и нулевым началом отсчета вектора, это его «длина»

L. Например, для четырехразрядного представления «длины» числа а4аза2Й она может быть записана следующим образом:

L= ц(а4 -1) v М(а )ц(а - 1) v М(а )М(а )ц (а - 1) v 4 3 4 3 v М(а4)М(аз)М(а2)ц(а1-1). (1.8.1) Здесь приняты следующие обозначения:

- 1) - цифровое непрерывное множество в пределах цифр разряда (i = а, а, а, а ), которое содержит все ц и ф р ы от 0 до ( i - 1), т.е.

4 3 2 Ki - 1) = 0 v... v (i - 1);

М © - цифровое множество, не обязательно непрерывное в пределах цифр разряда, но обязательно содержащее цифру i, т.е. М(Г) = 0 v... v i = 1 v... v i = =... = i, где конкретный выбор этого множества определяется только принци¬ пом кодирования цифр основания системы счисления и весьма прозрачен.

П р и этом если i = 0, то |U-(i - 1) = 0* (логический нуль), если i = (n-1), то М(Г) = 1* (логическая единица).

а ai О 123 4 56 78 9 10 11 12 13 14 а Р Ц0001) Ц0010) ЦООП) Ц0100) Ц0101) ЦОПО) Ц0111) ЦЮОО) Ц1001) Ц1010) Ц1011) ЦПОО) Ц1101) Ц1110) Ц1111) Рис. 1. Очевидно, что если «длина» непрерывного множества задана с началом от­ счета о т максимального номера кубика пространства, то все аргументы в (1.8.1) д о л ж н ы быть изменены н а обратные (для двоичного кода - инвертированы).

Следовательно, если начало вектора непрерывного цифрового множества задано в цифровом пространстве номером ячейки N, а конец вектора - номе­ р о м ячейки N, то, определяя непрерывное множество с нулевым началом от­ a счета вектора L ( N ) и непрерывное множество с началом отсчета вектора от e максимального номера ячейки цифрового пространства L ( N ), искомое непре­ р ы в н о е множество будет представлено следующей логической зависимостью:

a p L(N1,N2) = L ( N 2 ) L ( N 0. (1.8.3) С увеличением количества двоичных разрядов число слагаемых в (1.8.1) увеличивается и возникают аппаратурные трудности ее реализации. В этом случае наиболее целесообразно перейти н а большие основания систем счисле­ ния, например n= 16. Тогда цифровые и непрерывные в пределах разряда м н о ­ жества ц(;

- 1) п о л н о с т ь ю определяются логическим выражением (1.8.2), а о п ­ тимальные цифровые множества M(i), которые содержат в пределах разряда только ц и ф р у i, определяются п р и м и н и м а л ь н ы х аппаратурных затратах по¬ следними слагаемыми в (1.8.2). Эти слагаемые в (1.8.2) выделены светлым шрифтом.

Оптимальные цифровые множества M(i) (i =0,..., i4) в пределах разряда приведены н а рис. 1.14.

а а 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 р М(0) _ М(1) М(2) М(3) М(4) _ М(5) М(6) М(7) М(8) М(9) М(10) М(11) М(12) М(13) М(14) Рис. 1. После формирования в каждом разряде сигналов ) и M ( i ) они посту­ пают в логический блок, конструкция которого определяется выражением (1.8.1).

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

В дальнейшем, при рассмотрении конкретных устройств в этих областях техники, сведения об этих типах множеств будут расширяться и дополняться.

Несколько слов относительно терминологии для этих ц и ф р о в ы х множеств.

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

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

В 1943 г. в С Ш А была начата и выполнена такая разработка электронной ма­ ш и н ы E N I A C для расчета баллистических таблиц по заказу военного ведомст­ ва. В 1945 г. к этой работе в качестве консультанта б ы л приглашен Дж. фон Нейман. В результате дискуссий трех главных идеологов построения вычисли­ тельных м а ш и н Дж. фон Неймана, Г. Гольдстайна, Ф. Беркса возникла идея ис¬ пользования в дальнейшем п р и создании вычислительных м а ш и н двоичной системы счисления.

Э т и ученые изложили (1946) основные принципы построения вычислитель­ ных м а ш и н нового поколения в ставшей теперь классической статье «Предва­ рительное рассмотрение логической конструкции электронного устройства»

(Кибернетический сборник. М.: М и р, 1964. № 9).

Г л а в н ы е положения этой статьи - обоснование использования двоичной системы счислений для представления чисел и принцип «хранимой програм¬ мы». Наряду с обоснованием применения двоичной системы счислений и «хра¬ нимой программы» в работе предлагался ряд важных рекомендаций по конст¬ руированию м а ш и н и методике программирования.

Ряд отечественных исследователей в своих публикациях [23-25] о б р а щ а ю т внимание на необходимость использования не двоичной, а многозначной логи¬ ки, в частности трехзначной [2o], как основы построения высокопроизводи¬ тельных цифровых систем.

В М Г У была создана м а ш и н а «Сетунь» - единственная в мире Э В М, в ко¬ т о р о й использована такая т р о и ч н а я система счисления, и, как у т в е р ж д а л и ав¬ т о р ы разработки, самая э к о н о м и ч н а я с т о ч к и зрения использования аппарат¬ ных средств.

Н е у д а ч н ы й опыт использования трехзначной логики в вычислительной ма¬ ш и н е «Сетунь» вызвал критику такого подхода в ряде зарубежных публика¬ ций, из которых наиболее острой является статья американского ученого Б. Байцера, в которой о н пишет: «В течение многих лет близорукие теоретики, не давая себе труда проанализировать о ш и б о ч н ы е допущения, на которых ба¬ зировалось это "доказательство", усиленно пропагандировали скрытые пре¬ имущества основания 3 как наилучшего приближения к е. М а ш и н а, исполь¬ з у ю щ а я систему счисления с основанием 3, была построена в СССР, но она оказалась не столь у ж хорошей. Пусть э т о послужит нам напоминанием того, что такое изящное доказательство, основанное на недействительных предпо¬ сылках, представляет собой некоторый курьез;

о ш и б о ч н ы м и оказываются обычно допущения, положенные в основу некоторого исследования, а не сам ход этого исследования» [13].

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

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

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

О б ы ч н о й р-значной логической функцией, в дальнейшем логической функ¬ цией y = f ( x,..., x ), называется функция, принимающая, как и ее аргументы p L K x,..., x, значения, которые обозначим символами o*, 1*,..., (р - 1)*.

L K Поскольку число различных наборов значений аргументов логической К функции конечно и равно р, любая логическая функция может быть задана К таблицей истинности с р строками, например для р=3 (табл. 1.9.1).

Таблица 1.9. ОЦК Xi X2 y p= o* o* o* 1 1* o* o* 2* o* 2* o* 1* 2* 1* 1* o* 2* 1* o* o* 2* 1* 1* 2* o* 2* 2* o* Если всем наборам значений аргументов функции y = f ( x..., x ) поставить p L K К в соответствие сигналы О Ц К от 0 до ( р - 1), то каждый аргумент x - (i = o,..., K ;

y j = o*,..., (p - 1)*) и сама функция будут являть собой определенные цифровые множества, которые могут быть представлены как на цифровой «прямой», так и в многомерном цифровом пространстве, где каждая координата определяется соответствующим разрядом либо группой разрядов. pk p.

Число различных логических функций определяется зависимостью Эта зависимость (аналогично двухзначным функциям) может быть представ¬ лена через все возможные сочетания. Перед тем как представить эти зависимо¬ сти, сделаем некоторые пояснения. Если значения двухзначных логических функций в многомерном цифровом нумерованном пространстве заполняют все его ячейки символами o* и 1*, где одно крайнее заполнение соответствует «пус­ тому» множеству, т.е. пустому для значений 1*, а другое - «универсальному»

множеству, т.е. полному для 1*, которое может рассматриваться как «пустое»

для символов o*, т о многозначная логическая функция будет иметь р таких крайних значений, каждое из которых будет «универсальным» для одного кон¬ кретного значения р и «пустым» для остальных (р - 1) значений логической функции.

Число различных двухзначных логических функций, определяемое зависи­ мостью (1.1.1), может быть записано в несколько ином виде К K i=2 1*=i I IC 2 =.

i k 2) ( K i =0 0*=(2 -1) (19 1) Тогда число трехзначных логических функций может быть записано следую¬ щ и м образом:

К K j (3K-i) i=3 • = 2*=i 1*=i 3= (1.9.2) I (C i k (2) 1 C J 3K-i ) I K ( ^ K i=0 K K 1*, 0*=(2 -1) j=0 0*=(3 - i -j) и т. д.

Xi o 12 L C 9(C9) 1Г X 2L 2 C 9(C9) 3 C 9(C9) j *"*"| ** *— * * * * * * 4 C 9(C9) *** ** * ** ** ** * ** ** * ** * * * * * Рис. 1. П р и в е д е м пример перечисления всех трехзначных логических функций для К = 2 и будем размещать символы o*, 1*, 2 * в двухмерном цифровом простран­ стве. В соответствии с (1.9.2) получим:

0. 1*=0 1 1*=1 2 1*=2 3 1*=3 4 1*=. 2*= (С С С С С СГ 1 1 + 9 0*=9 9 0*=8 9 0*=7 9 0*=6 9 0*= 9 1*,0*= 1*= 9 8 7 6 1*=8 1*=7 1*=6 1*= +С С С С С )+ 1 9 0*=9 9 0*=1 9 0*=2 9 0*=3 9 0*= 1*= 1*= 0. 1*=0 1 2 3 1*=2 1*= 1. 2*= (С С С С С 1 +С | + 8 0*=8 8 0*=7 8 0*=6 8 0*=5 8 0*= 9 1*,0*= 1*= 8. 1*=8 7 6 1*=6 1*= +С )+ С С С 8 0*=0 8 0*=1 8 0*=2 8 0*= 1*= 0. 1*=0 1 2 1*=2 1*= 2. 2*= + (С С С С +С | 7 0*=7 7 0*=6 7 0*=5 7 0*= 9 1*,0*= 7. 1*=7 6 5 1*=6 1*=5 1*= +С )+ С С С 7 0*=0 7 0*=1 7 0*=2 7 0*= 1*= 0. 1*=0 1 2 1*=2 1*= 3 2*= + (С С С С +С | 6 0*=6 6 0*=5 6 0*=4 6 0*= 9 1*,0*= 1*=5 1*= 6. 1*=6 5 +С +. + С С 1 1 ) 6 0*=0 6 0*=1 6 0*= 1*= 0 1 9 2*= 1*= 2*= +С| (С + С1 С 1 = 19683.

) + 1 0*=1 1 0*=0 9 1*,0*= 9 1*,0*= Здесь первое подмножество множества сочетаний определяется отсутстви­ ем в девяти ячейках пространства символов 2* и размещением во всех этих ячейках только символов 1*,0*, что выражается суммой сочетаний (С +... + 9 +С ) = 2 ;

второе подмножество определяется наличием в девяти ячейках про¬ странства одного символа 2* и размещением во всех остальных восьми ячейках символов 1*,0*, что также представлено суммированием сочетаний (С + + +С 8 ) = 2 и т.д.

О б щ е е число всех трехзначных логических функций д л я двух аргументов весьма значительно, что, на первый взгляд, сулит большие сложности их пред¬ ставления и обозрения. Однако даже краткое изложение основ теории много¬ мерных ц и ф р о в ы х множеств, симметрии поворотов и переносов фигур в двух¬ мерном пространстве позволяет представить все первообразные (без учета «пустого» и «универсального» множеств) только 15 фигурами. Э т и фигуры приведены на рис. 1.15.

Очевидно, что д л я е щ е более значной логики, например д л я четырехзнач¬ ной при К =2, где общее число всех логических ф у н к ц и й равно 4 294 967 296, невозможно обойтись без применения приведенной в ы ш е методики их пред¬ ставления.

1.10. Алгоритмы синтеза двухзначных логических функций И д е я синтеза логических функций в базисе Д Н Ф с п о м о щ ь ю вычислитель­ ных устройств всегда привлекала внимание многих исследователей и сулила им большие надежды, которые возрастали с появлением нового более быстродей­ ствующего поколения Э В М. Однако «победить» огромную трудоемкость, глав­ н ы м образом временную, получения оптимальных решений синтеза л ю б ы х Л Ф с достаточно большим числом аргументов до настоящего времени не удалось.

Очевидно, эта идея может быть реализована при весьма ограниченном числе аргументов.

В настоящее время создано несколько комплексов алгоритмов, каждый из которых имеет свое назначение, использует свой набор эвристических приемов и свои языки программирования [1, 2, 15].

Большинство из этих известных алгоритмов является т е м или и н ы м пере¬ ложением на язык вычислительных м а ш и н широко известного метода синтеза, предложенного К в а й н о м [27] и модифицированного Мак-Класки [26]. М е т о д К в а й н а - Мак-Класки предполагает, что минимизируемая Л Ф задана в совер¬ ш е н н о й Д Н Ф и все дальнейшие преобразования основаны на одном и том ж е математическом приеме алгебры логики: преобразование Д Н Ф достигается пу¬ т е м применения операции «склеивания» пар интервалов, на которых значения Л Ф отличны от нуля (0*).

П о и с к этих интервалов осуществляется перебором ряда вариантов, где с п о м о щ ь ю эвристических приемов стараются управлять перебором с ограниче¬ нием их числа.

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

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

В е р н е м с я к двухзначным Л Ф и их геометрическому образу в многомерном нумерованном цифровом пространстве.

М е т о д геометрического синтеза на основе построения геометрических об¬ разов логических и арифметических функций в многомерном цифро-векторном пространстве, а также изучение симметрии цифрового пространства и симмет¬ рии геометрических образов Л Ф позволяют успешно решать задачи автомати¬ зированного синтеза логических блоков при л ю б о й значности и л ю б о м числе аргументов ЛФ.

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

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

С у щ н о с т ь рассматриваемого способа синтеза и реализующего его алгорит¬ ма заключается в последовательном рассмотрении заполнения клеток нумеро¬ ванного цифрового пространства, начиная с клеток старших, чем элементарные клетки, заполненные символами 0 * и 1*, и определения всех двухзначных ЛФ.

П о с л е этого (второй шаг программы) рассматриваются следующие по старшинству ячейки пространства, в которых располагаются не символы 1* и 0 *, а непосредственно геометрические образы ЛФ, определенные на первом шаге программы, и находятся все четырехзначные Л Ф цифрового пространства.

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

Определение покрытия этой ячейки пространства и является искомой Л Ф в ДНФ.

Н а каждом шаге программы поиск Л Ф, определяющих покрытие фигуры ячейки пространства, исходя из фигур младших на единицу ячеек, выполняется в соответствии с геометрическим образом:

Fi Fo F2 F Xi- по логическому выражению, представленному в общем виде Q = Fo X i Xi+i v F i X i Xi+i v F2 X i Xi+i v F3 X i x + i.

Это выражение может быть уменьшено в том случае, если функции F F 0;

1;

F2, F3 п р и н и м а ю т значения 0 * или i *, а также, если некоторые из них являются подмножествами других.

Например, если F = 0 *, а F = F и F = F,то Q = F X v F X + v F X X + ;

o 3 2 3 1 1 2 i i i i i i если Fo = 0 *, а F i = F2 = F3 = F, то Q = F X i v F X i + i, и т.д.

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

Представленная программа поясняется на Х примере синтеза шестизначной Л Ф, геомет­ — — Х 1 —— рический образ которой приведен в двухмер­ "Т ~Т "Т ном цифровом пространстве н а рис. 1.16. т Х 10 01 Н а первом шаге программы определяет­ L L L Х4 1 1 - ж 10 ся 16 элементарных двухзначных ЛФ F - • (Loo, (L01, (L02,.........

, L30),, L31),, L32), L L L L 20 21 (L03,..., L ).

1. () Хб Н а втором шаге программы с учетом вза¬ имного включения фигур в каждой группе из L L L L 02 12 четырех двухзначных функций определяются 1 20 1 1 30 F F четыре четырехзначные функции F,..., F. 00 L L L L Н а третьем, заключительном для данно¬ 22 32 _L _L _L _L го примера шаге программы, определяется, также с учетом взаимного включения фигур Р 116 и с в этой группе, шестизначная логическая функция Qoo, которая и определяет покрытие соответствующей фигуры цифро­ вого пространства в базисе Д Н Ф.

Представленная программа синтеза «жесткой» конструкции логического блока является универсальной и м о ж е т служить основой для построения про¬ граммируемого асинхронного устройства, реализующего — 264 варианта шес- л тизначных Л Ф.

У у1 •t 1 L03 L13 L L L o i L n L21 L31 L()2 L l Loo L i o L20 L L 1-й шаг 2 1 X 1 X4 1x | x I i X X4 x x 3 4 3 3 F20^/ \ F Foo 2-й шаг 1 x x 5 3-й шаг Qo Рис. 1. Здесь следует, однако, заметить, что когда среди логических функций Ln, Fa имеются одинаковые, т.е. их геометрические образы совпадают, либо они пре¬ образуются одна в другую соответствующими поворотами относительно осей симметрии многомерного пространства, то программы синтеза «жесткой» кон¬ струкции могут претерпеть существенные упрощения.

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

У1- У •• • •• • •• • •• • Ую Ую Уоо Узо У02 У12 У22 У У01 У п У21 У31 Уоз У13 У23 Узз L Lio Loo L Рис. 1. В схеме имеются генератор двухзначных Л Ф 1 с шестнадцатью в ы х о д н ы м и х х ш и н а м и У1(х1,Х2) - У 1 б ( ъ 2 ) и четыре о д н о т и п н ы х мультиплексных блока 2, о с у щ е с т в л я ю щ и х к о м м у т а ц и ю сигналов функций y ( x, x ) - y ( x x ) на со­1 1 2 16 1? ответствующие ш и н ы L i,..., L i (первый шаг программы). Эта коммутация 0 выполняется по сигналам у п р а в л я ю щ и х команд Y, Y, Y, Y. Схема блока 2, 1 2 3 состоящая из четырех стандартных мультиплексоров, приведена на рис. 1.18.

Н а втором шаге программы формируются на выходе логических схем функции F ^ F ^ F ^ F, а на третьем - логическая функция Q.

0 1( 2 30 Рассматриваемая теория м н о г о м е р н ы х ц и ф р о в ы х м н о ж е с т в м о ж е т быть у с п е ш н о п р и м е н е н а для л ю б ы х м н о г о з н а ч н ы х л о г и ч е с к и х ф у н к ц и й как при синтезе « ж е с т к и х » л о г и ч е с к и х конструкций, так и при синтезе п р о г р а м м н ы х л о г и ч е с к и х блоков.


Это подтверждается ш и р о к о известной к о н ц е п ц и е й об эк¬ вивалентности аппаратных и п р о г р а м м н ы х средств, к о т о р ы е лежат в о с н о в е м е т о д о в п р о г р а м м и р о в а н и я и позволяют «какой-нибудь с п е ц и а л ь н ы й прием, и с п о л ь з у е м ы й при п р о е к т и р о в а н и и аппаратуры, использовать и при програм¬ м и р о в а н и и » [13]. П р и этом м о ж н о утверждать, что если имеется геометриче¬ ский образ л о г и ч е с к о й функции л ю б о й значности в м н о г о м е р н о м ц и ф р о в о м пространстве, то задача синтеза как предмета изобретательской деятельности не существует, а эта работа м о ж е т быть выполнена при п о м о щ и вычислитель¬ ной техники или д а ж е р у ч н ы м способом г р а м о т н ы м специалистом. Достиг¬ нуть этого стало в о з м о ж н ы м потому, что получен четкий ответ на в о п р о с ы «как» и «почему».

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

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

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

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

1.11. Примеры синтеза одноразрядного устройства суммирования и вычитания С целью более четкого представления принципа построения геометриче¬ ского образа Л Ф в многомерном цифровом пространстве рассмотрим примеры синтеза одноразрядного суммирующего и вычитающего устройства для осно¬ вания системы счисления n = 8. Э т о выполним для двух вариантов кодирования данного основания: двоичного и многофазного.

Основой построения геометрического образа сигналов результата этих операций являются общеизвестные таблицы Пифагора. В табл. 1.11.1 представ¬ лен результат арифметической операции суммирования (A+B) п р и отсутствии сигнала переноса с предыдущего младшего разряда, а в табл. 1.11.2 - при нали¬ чии такого сигнала.

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

Таблица 1.11.1 Таблица 1.11. A A 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1.0 0.2 0.3 0.4 0.5 0.6 0.7 1.0 1. 1 0.2 0.3 0.4 0.5 0.6 0.7 1.0 1.1 0.3 0.4 0.5 0.6 0.7 1.0 1.1 1. 2 0.3 0.4 0.5 0.6 0.7 1.0 1.1 1. B B 0.4 0.5 0.6 0.7 1.0 1.1 1.2 1. 3 0.4 0.5 0.6 0.7 1.0 1.1 1.2 1.3 0.5 0.6 0.7 1.0 1.1 1.2 1.3 1. 4 0.5 0.6 0.7 1.0 1.1 1.2 1.3 1.4 0.6 0.7 1.0 1.1 1.2 1.3 1.4 1. 5 0.6 0.7 1.0 1.1 1.2 1.3 1.4 1.5 0.7 1.0 1.1 1.2 1.3 1.4 1.5 1. 6 0.7 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1. 7 Д л я двоичного кодирования цифр 0 - 7 используются на примере первого операнда т р и сигнала a = 1 v 3 v 5 v 7, a = 2 v 3 v 6 v 7, a = 4 v 5 v 6 v 7. В со¬ 1 2 ответствии с представлением сигналов как множества цифр натурального ряда от 0 до 7 в ячейках нумерованного двухмерного цифрового пространства со¬ держатся цифры, которые есть элементы подмножества сигналов разряда опе¬ рандов. Д л я каждого сигнала результата операции в ячейках пространства рас¬ полагается логическая единица 1* (звездочка), а остальные ячейки заполнены логическими нулями 0* (пустая ячейка).

i-1 i- P = 0*, Z = 0* A ' ( a a2, a3) b _* * * *\ ** ** * *** I if * * *I ** ** ** ** * * ** ** ** *** * II * * * * * **** * * ** i P 1(q) q'2 q' q'1 ** ** **** ** ** I If * *** * i (A+B)' = Q * ** ** ** ** ** I I* * * * * * *** * * I I ! I ! * * * * * * i Z 1(r) r' * * * Г'2 r' * * * * * (B-A)' = R * * * h* * * * * * * * * * *** * * * ** * * * ** * * * * * *** * Z\(s) s'1 * * S'2 s'3 * * **** * ** * * **** ( A - B ) ' = S' * *** * * --***** - * * * * *** * * *** Рис. 1. 1- = 1* Z = 1* - pi A ' ( a a2, a3) b * * * * ** ** **** * * * * * ** ** **** * * **** * * * * * * * * * * * II * *** **** ** ** * * * * P 2(q) * * q''2 * * q'' * * * * q''1 ** * * * * * ** * * * * * * **** ** ** ** * * 1 (A+B) = Q ** * * * * * **** * * * * ** ** II * *** *** * * * * * **** ** ** * * * * * * * * * * * * * * * * Z 2(r) * * * * r"2 r" * * * * 1 (B-A) = R * * * * * * * * * * * П* * ---- * zz * * * * ** П* * * * * * *_ _ ** * *** ** * * * * * *** *** _ Z 2(S) H * s1 S"2 * * * S"3 * * * * ** * * * *** * p * * * * ZD ZE * * * 1 (A-B) = S *** *** * **** * * * * *** * *** * Рис. 1. В соответствии с этим на рис. 1.19 показаны геометрические образы сигналов i i-го разряда q'1, q'2, q'3 и переноса в старший разряд P (q) для операции сумми­ рования (A + B). Эти геометрические образы получаются при отсутствии сигнала 1- переноса результата операции в младшем разряде P (q)=0*, а на рис. 1.20 приве­ i д е н ы аналогичные сигналы q", q", q", P (q) п р и наличии такого сигнала пе­ 1 2 3 1- реноса P (q)=1*.

П р о в о д я аналогичные действия, начиная с таблиц Пифагора, для операций 1 вычитания (B - A), (A - B) м о ж е м получить соответствующие им геометриче­ ские образы. Э т и фигуры приведены на этих ж е рисунках соответственно для 1 i операции вычитания (B - A) [сигналы i-го разряда r', r', r', Z (r) при отсутст­ 1 2 3 i-1 i вии сигнала заёма из старшего разряда Z = 0 * и сигналы r", r", r", Z (r) п р и 1 2 3 i- наличии сигнала заема для младшего разряда Z =1*] и операции вычитания 1 i (A - B) [сигналы i-го разряда s', s', s', Z (s) при отсутствии сигнала заема для 1 2 3 i-1 i младшего разряда Z = 0 * и сигналы s", s", s", Z (s) при наличии сигнала за­ 1 2 3 i- ема для младшего разряда Z =1*].

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

Поскольку выполнение всех арифметических операций для двоичного ко¬ дирования оснований систем счисления ш и р о к о известно и без знания теории многомерных цифровых множеств, остановимся только на связях выходных сигналов с их базовыми геометрическими образами, которыми в данном случае будут образы сигналов q' (AB), q' (AB), q' (AB), P'(AB).

1 2 Остальные фигуры получаем соответствующими м ы с л е н н ы м и поворотами относительно осей симметрии двухмерного цифрового пространства, а именно:

q"1 = q'1(AB) = q'1(A*B*) = q\(AB*) = q\(A*B), q"2 = q^A'B'), q"3 = q^A'B');

r'1 = q'1(AB) = q'1(A*B*) = q\(AB*) = q\(A*B), r'2 = q^AB'), r'3 = q^AB');

r"1 = q'1(AB) = q'1(A*B*) = q\(AB*) = q\(A*B), r"2 = q^A'B), r"3 = q^A'B);

s'1 = q'1(AB) = q'1(A*B*) = q\(AB*) = q\(A*B), s"2 = q^A'B), r"3 = q^A'B);

s"1 = q'1(AB) = q'1(A*B*) = q\(AB*) = q\(AB*), s"2 = q^AB'), s"3 = q^AB');

i Z'(r) = P (AB•), Z'(s) = P'(A'B). (1.11.1) Следовательно, зная покрытие базовых фигур логических функций опера¬ ции суммирования q'1(AB), q'2(AB), q'3(AB) при отсутствии сигнала переноса с - младшего разряда P' (AB) = 0*, не представляет сложности получить анало¬ гичные сигналы для операции суммирования п р и наличии такого переноса - (P' (AB) = 1*). Э т о справедливо также для операции вычитания как для случая, когда AB, т а к и для AB, п р и л ю б о м значении сигналов заёма со старшего разряда сумматора. Замечательным свойством п р и этом обладают сигналы пер¬ вого разряда сумматора, которые имеют полную с и м м е т р и ю геометрического образа и при различных м ы с л е н н ы х поворотах относительно осей симметрии пространства остаются неизменными.

Очевидно, что для любого ' - г о разряда базовой операции q = qj' Г + qj" P ".

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

Д л я четных оснований систем счисления в сигналах кода операнд имеется сигнал, который является непрерывным множеством второй половины цифр основания системы счисления. В приведенном в ы ш е примере это - сигналы a3, b3, q3, которые позволяют определить сигнал переноса P' п о следующему логическому выражению:


P' = q'3 a W q'3 b W aS. (1.11.2) В (1.11.2) нет сигнала переноса с младшего (' - 1)-го разряда, но он при­ сутствует в формировании переноса P ' и интегрирован в сигнале q'. Н а рис. 1.21, а, б показаны соответственно геометрические образы сигнала -1 - q' при P ' = 0* и P ' = 1*, из которых ясен принцип формирования цифровых подмножеств a' b' и q' a' v q' b', составляющих цифровое множество P'.

3 3 3 3 3 a a 3 * * * ** ** ** * * ** * * * ** **** b * * * *** **** * *** * ** **** * q * ** * ** **** * * *** **** * * * * ** **** * q3a3 v q3b * ** * ** **** * * *** * ****** * а) б) * * * *** * ******** * * P ' = q3a3 v q3b3 v b3a Рис. 1. Формула (1.11.2) - общая для любого принципа кодирования четных осно¬ ваний систем счисления, где операнды содержат в коде разряда сигнал, являю¬ щийся непрерывным множеством цифр второй половины этого основания. То¬ гда выражение для л ю б ы х оснований (1.11.2) будет преобразовано к виду ' ' ' P ' = q'k a' v q'k b ' v a' b', (1.11.3) k k k k где q', a', b' - непрерывные цифровые множества операндов, содержащие k k k ц и ф р ы второй половины основания системы счисления.

Значение выражения (1.11.3) заключается не только в его простоте, а и в том, что если в них сигналы q', a', b' безошибочны, то также будет безошибо¬ k k k ' чен сигнал переноса P '-го разряда.

П р и многофазном принципе кодирования цифр 0-7, когда, на примере сигналов первого операнда, a = 1 v... v 4, a = 2 v... v 5, a = 3 v... v 6, 1 2 a = 4 v... v 7, геометрические образы сигналов результата сложения (A+B)' и вычитания (B - A)' и (A - B)' приведены на рис. 1.22 и 1.23. Э т и рисунки анало гичны рис. 1.19 и 1.20 двоичного принципа кодирования этого ж е основания системы счисления.

Н а рис. 1.22 построены в двухмерном цифровом пространстве координат операндов A, B геометрические образы сигналов i-го разряда q\,..., q'4 и пере­ i носа в старший разряд P (AB) операции суммирования (A+B), когда i-1 i P (AB) = 0*, а на рис. 1.23 приведены такие ж е сигналы q ".., q " и P (AB) 1 1v 4 i- при наличии сигнала переноса с младшего разряда P (AB) =1*. i A (a1,a2,a3,a4) 1 (A+B) = Q * * * I* * * i B (b1,b2,b3,b4) * * * * * * * * * * ** * * * *** * * * * * * * ** * * * q' q2 q3 P 1(q) 1 (B-A) = R 1- P =0* *** * ** * - ** * -* * * * * 1- Z =0* ** * * ** ** * ** ** ** ** * ** * * ** **** **** ** * * **** * ** ** r Г3 Z 1(r) 1 (A-B) = S * * 1111 * **** * ** * *** 2 ПК 0 123456 * I* I* I* * I*I* I* * I* I 7 654321 s'3 s' s2 ОК Z 1(s) Рис. 1. Н а этих ж е рисунках показаны геометрические образы сигналов д л я опе¬ раций вычитания. Э т и фигуры приведены соответственно д л я операции вычи¬ 1 тания (B-A) [сигналы i-го разряда r '..., r', Z (r) п р и отсутствии сигнала за­ b 4 1-1 ема д л я младшего разряда Z = 0 * и сигналы г "..., r", Z (r) п р и наличии сиг­ ь 4 1-1 нала заема д л я младшего разряда Z =1*] и для операции вычитания (A-B) [сигналы i-го разряда s'..., s', Z (s) при отсутствии сигнала заема для младше­ b 4 1-1 го разряда Z = 0 * и сигналы s"..., s", Z (s) п р и наличии сигнала заема для b 4 1- младшего разряда Z =1*].

A'(ai,a2,a3,a4) ( A + B ) = (Q B'(bl,b2,b3,b4) **** 1 1 * * * * * - **** * * * ** ** * * *** * **** **** q qз q''i P2(q) I- P =1* (B-A) =R _ **** * ** **** **** * * * * * -* * * * * - Z' =1* * *** * *** * * * * * ---* * * * * ** ** ** ** * * * * * * * * * ** ** * *** * ** * **** *** * * ** * * * * * **** *** * * * * ** * ** **** ** * * **** *** * ** * * * r" r Z2(r) (A-B) = S * * * * * * * --— * * * * * * * * * * * * * * * * ** * * * * *** **** * * * * * * * S2 S3 Z2(S) Рис. 1. И з геометрических образов логических функций операций суммирования и вычитания видно, что, принимая в качестве базовых фигуры сигналов q' (AB) и q' (AB), сигналы второй и четвертой фаз результата суммирования запишутся с л е д у ю щ и м образом: q' (AB) = q' (A*B*), q' (AB) = q' (A*B*), а все другие сигна­ 2 1 4 л ы фаз операций суммирования и вычитания, а также сигналы заема определя­ ются выражениями:

r'1 = q'3(AB*), r'2 =q\(A*B), r'3 = q\(AB*), r'4 = q'3(A*B);

s'1 = q'3(A'B), s'2 = q\(AB*), s'3 = q\(A*B), s'4 = q^AB');

q"1 = q'3(A'B'), q"2 = q\(AB), q"3 = q^A'B*), q% = q'3(AB);

Л = q'1(A'B), r"2 = q'1(A*B*), r"3 = q^A'B), r% = q^AB');

s"1= q'3(AB'), s"2 = q'1(A'B), s"3 = q^AB"), s% = q^A'B);

1 1 [ Z (r) = P(q)(AB"), Z (s) = P (q)(A*B). (1.11.4) П о д в е д е м итог синтеза выполнения операции суммирования и вычитания для двоичного и многофазного принципов кодирования основания системы счисления. П р и этом будем считать базовым вариантом операцию суммирова¬ ния, а операцию вычитания будем выполнять соответствующим переключени¬ ем сигналов на входных и выходных шинах устройства.

A **** **** **** B ** * *** * ** 2 * * * *** * ** ** * 3 * * * **** *** * ** *** **** **** * * * ** * *** * *** * * * ** ** ** ** ** * * ** * *** * *** * Рис. 1. Н а рис. 1.25 приведен геометрический образ сигнала первой фазы q ре¬ зультата суммирования в трехмерном цифровом пространстве сложных аргу¬ ментов A, B, Q. Все геометрические образы остальных сигналов фаз для опера¬ ций суммирования и вычитания могут быть получены, исходя из образа сигнала q соответствующим м ы с л е н н ы м поворотом относительно осей симметрии пространства, а также параллельным перемещением этой фигуры. Это возмож¬ но выполнить, поскольку здесь используется циклический принцип кодирова¬ ния сигналов операндов. Следовательно, при многофазном принципе кодирова¬ ния число базовых фигур может быть уменьшено здесь до одной, например q1.

Q(q1, q2, q3, q4) B(b1, b2, b3, b4) A(a1, a2, a3, a4) Рис. 1. Традиционно в вычислительной технике используется д в о и ч н ы й принцип кодирования оснований систем счисления, а многофазный является естествен­ н ы м для устройств преобразовательной техники и электропривода. П р и управ­ лении такими устройствами от Ц В М необходимо рассмотреть возможность их работы не только в многофазных кодах [5-11], но и для применения смешанно¬ го кодирования, если один из операндов представлен, например, в двоичном коде, а другой - в многофазном.

Е с л и результат операции суммирования или вычитания реализуется в мно¬ гофазном коде, что обычно и требуется в изучаемых нами разделах техники, то Л Ф этих операций по аналогии с (1.11.5) и задании, например, операнда A в многофазном коде, а операнда B - в двоичном, будут следующими:

3 2 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 3 2 2 1 4 3 2 1 4 3 1 4 3 2 1 4 3 2 3 2 1- 3 2 1.

1 4P v2 1 4 3 2 1 4 Q =(3 2 1 4 3 2 1 ) 3 2 3 2 1 4 3 2 1 4| 4 3 2 1 4 3 2 1 • 3 2 A A 3 2 1B 3 2 (1.11.8) П р и этом геометрические образы сигналов операций суммирования и вы¬ 1 1 читания Q, R, S полностью определяются рис. 1.22 и 1.23.

Н е о б х о д и м о отметить, что для реализации каждой из Л Ф в (1.11.9) можно использовать интегральную схему мультиплексора, которая представляет собой многовходовый логический элемент с одним выходом, где входы подразделены на информационные и управляющие. П р и подключении к у п р а в л я ю щ и м вхо¬ 1 дам двоичных сигналов операнда B(b,b,b ) и переноса P, а к информацион¬ 1 2 н ы м входам в определенной последовательности - многофазных сигналов опе¬ ранда A к выходу мультиплексора типа (1 из 16) подключается один из его ин¬ формационных входов, и, следовательно, на выходе будет в соответствии с (1.11.8) сформирован сигнал одной из фаз.

П р и параллельном формировании сигналов всех фаз необходимо использо¬ вать такое ж е количество мультиплексоров, а п р и последовательном определе¬ нии сигналов фаз потребуется одна схема мультиплексора.

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

П р и м е м для л ю б ы х типов кодов позиционной системы счисления неизмен¬ ность кодового слова для ц и ф р ы 0 (0 о a... aj.). В этом случае число кодов будет у м е н ь ш е н о до значения (n - 1)!. Д а л ь н е й ш и м решением, что следует из предыдущих рассмотрений задач синтеза устройств м а ш и н н о й арифметики, яв¬ ляется использование только четных оснований систем счисления. П р и ч е м в коде этих систем счисления обязательное условие - наличие сигнала, который является непрерывным множеством цифр второй половины основания системы счисления.

П р и этом оставшиеся (' - 1) комбинации сигналов кода могут быть одина¬ ковыми на первой и второй половине цифр основания либо иметь симметрич¬ ное расположение комбинаций на второй половине относительно первой поло¬ вины цифр основания системы счисления.

Представленные в ы ш е ограничения на использование кодов в позиционных системах счисления позволяют весьма просто, например в с у м м и р у ю щ е м либо в ы ч и т а ю щ е м устройствах, формировать сигналы переноса и заёма непосредст¬ венно по в ы х о д н ы м и входным сигналам старших разрядов кода. Это м о ж н о реализовать, не используя отдельного полного логического блока для формиро¬ вания сигнала переноса. Тогда каждому виду симметрии оставшихся (i - 1) ко­ довых слов будет соответствовать (n/2 - 1)! кодов.

Для пояснения сказанного обратимся к основанию системы счисления, на¬ пример n=8.

Н а рис. 1.26, а под № 1 представлен двоичный принцип кодирования этого основания, где сигнал a = 4 v 5 v 6 v 7 и будет оставаться неизменным при л ю б ы х принципах кодирования этого основания системы счисления. Ц и ф р а определяется логической зависимостью 0 = a a a^, а сигнал ц и ф р ы 4 будет оп¬ 1 ределяться при других принципах кодирования выбранным соответствием ко¬ дов на первой и второй половине цифр основания. Так ж е в зависимости от это¬ го выбора будут р а з л и ч н ы м образом кодироваться ц и ф р ы 1, 5;

2, 6;

3, 7. Е с л и в исходном двоичном коде для цифр 1, 5 принять обозначение состояния сигна¬ лов кода A о a a ;

для цифр 2, 6 - B о a a ;

для цифр 3, 7 - C о a a, то в со¬ 1 2 1 2 1 ответствии с выражением (1.2.2) число перестановок, определяющих число ко¬ дов, равно шести: ABC, ACB, BAC, BCA, CAB, CBA.

0 1 3 5 6 7 0 1 2 3 4 5 6 2 й D D D D й _й _й a № a A B A B A B B A C C C C № й й a a № a A B A B A B B A C C C C № a a №3 № a B A B A B A A B C C C C a a №4 № a B A B A B A A B C C C C a a №5 № a A B A B A B B A C C C C a a №6 № a B A B A B A A B C C C C a) 6) Рис. 1. Все эти коды приведены под своими номерами на рис. 1.26, а, а на рис. 1.26, б изображены коды для симметричного расположения (1 - 1) сигна¬ лов на второй половине цифр основания системы счисления.

Таким образом, м ы получили двенадцать кодов, которые, как все возмож¬ ные коды, могут быть использованы для выполнения л ю б ы х арифметических операций. П р и ч е м пары кодов № 1, № 3 ;

№ 2, № 4 ;

№ 5, № 6, а также № 7, № 9 ;

№ 8, № 1 0 ;

№ 1 1, № 1 2 имеют одинаковые возможности по выполнению арифметиче¬ ских операций. Поэтому будем рассматривать только первые из них: № 1, № 2, № 5, № 7, № 8, № 1 1. Из этих шести кодов только два имеют официальное назва­ ние: № 1 - двоичный код, № 8 - код Грея.

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

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

Н а рис. 1.26 переход от одной ц и ф р ы к другой, когда это происходит изме¬ нением сигналов более чем в одном разряде, отмечен знаком П р и этом коды 8.

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

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

Общеизвестно, что большим достижением индийской математики было создание системы счисления с нулем. О с н о в н ы м здесь было предложение или, вернее сказать, изобретение обозначать особым знаком (нуль) соответствую¬ щ и й (пустой) разряд. Разряда нет, но само его отсутствие было представлено как наличие «ничего», хотя его нет, но оно имеет обозначение. Нетривиаль­ ность этого изобретения, по словам А. Д. Александрова, блестяще выражена в афоризме Дирака, высказанного им в связи с «теорией дырок» (теория позитро¬ на): «Ничто, помещенное во что-нибудь, вполне эквивалентно чему-нибудь, помещенному в ничто».

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

Поскольку геометрия исходит из наглядных представлений, и в этом ее главная сила, то «она позволяет ухватить в одном представлении то, к чему ал¬ гебра и анализ приходят последовательными шагами». Следовательно, там, «где удается провести геометрическую точку зрения и геометрический метод, всегда достигается успех настолько существенный, насколько геометрический взгляд соответствует сущности предмета». В этом нам представится возмож¬ ность убедиться в последующих разделах книги.

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

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

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

П р и н ц и п и а л ь н о это могут быть л ю б ы е двоичные коды, которые при представ¬ лении цифр оснований систем счисления отличаются от основного двоичного кода перестановками его кодовых комбинаций. Эти кодовые комбинации наи¬ более удобно представлять суммой весовых W;

(1, 2, 4, 8...) значений их дво¬ ичных разрядов, которые для краткости будем называть весовыми значениями.

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

W |0|7|з|2|б|7|5|^ W;

a аз а2 ai 2 4 °IlI l3l ICM_ Рис. 1. Будем в обозначении цифр оснований систем счисления использовать ш р и ф т красного цвета, а для весовых значений кодовых комбинаций - ш р и ф т черного цвета и курсив. В соответствии с этим на рис. 1.27 в качестве одного из примеров такого кода представлен код Грея для основания системы счисления n = 8, где одновременно с сигналами разрядов кода ( a a, a ) приведены циф­ b 2 ровые 0-7 и весовые 0-7 значения его кодовых комбинаций.

A C = (A + B), A, B, C - в коде Грея, Pn-i = 0* 0 1 2 3 4 5 0 1326754 01326 754 01 326754 0 0 0 0 0 * 1 1 1 1 * * **** *** * * * * 2 3 * 3* 3 * * * **** ** * 3 2 ** 2*** *2 ** * *** *** 4 6 6 6 * * 5 7 7* * 7** * * * * * * **** * * * 6 5 *5 * 5* * * * * * * ****** * * * 7 4 **4 4* *** ** ** ** ******* 01234567 0 1234567 01234567 0 0 * * * ** * ** * * * * 1 1 * ** *** * * * * * * * 2 2 ** * ** * * *** ** * * * 3 3 ** ** ** ** ** ** ** ** * * = 0* Pn-i 4 4 * ** * * * * ** * **** * * * * * 5 5 * * * * ** ** ** *** * * * * * 6 *6 * * ** ** **** * * * * * 7 **7 * ** * ** ** ** * * * * * 0 1 2 34 567 0 * ** *** * * * * * * * * * * **** ** * ** * * * * * ** ** **** **** * ** * * ** ** ** ** ** ** ** * * Pn-1 = 1* 4* * * * * * * ** * ** * *** * * * * ** * * * * * ** * *** *** * * * * ** * ** * ** ** * *** * * * * * ** * ** ** ** **** * * Pn Ci C2 C Рис. 1. Ц и ф р о в ы е значения кодовых комбинаций всегда используются для п о ­ строения геометрических образов сигналов разрядов на основании соответст­ в у ю щ и х арифметических таблиц. Н а основании такой таблицы суммирования на рис. 1.28 построены геометрические образы выходных сигналов сумматора C = (A + B), когда во входных и выходных сигналах применяется код Грея, п р и входных сигналах переносов Pn-1 = 0* и Pn-1 = 1*.

01234567 0 1234567 01234567 0 0 0 ** ** ** ** ** ** * * * 1 1 *1 * ** * * * * ** * * * 2* 2 *2 * * ** ** ** ** * * 3* 3 *3 * * ** ** ** ** * * Zn-1 = 0* 4 4 4 ** * * * * ** ** ** ** ** ** * * * * 5* 5 5 * * * **** ** **** * * * * 6 6 6 * * ** ** **** **** * 7 7 7 **** ** ** *** * **** * 0 1 2 34 567 01 234567 01234567 0 0 ** 0 * ** * * ** ** ** * ** * * * * 1 * 1* * 1* * * ** ** ** * * 2 * 2** 2**** * * ** **** * C = (A - B) 3 * * ** 3 ** 3 ** * * ** ** * * ** ** ** * Zn-1 = 1* 4 *4 4 * ** ** ** * * * ** ** * * * * * * * ** * * * * * **5 5 * 5* * ** * * **** *** * * * 6 6** 6 ** * * * *** **** * * * - 7* 7 * * * **** ** ** **** * * Zn C1 C Рис. 1. Для входного сигнала переноса P = 0* построение геометрических о б ­ n- разов выходных сигналов c, c, c, P первоначально выполнено в цифровых 1 2 3 n значениях координат входных сигналов A, B (первый ряд геометрических фи¬ гур этих сигналов на рис. 1.28), а в дальнейшем представлены изменения этих фигур п р и последовательном переходе к весовым значениям координат основ¬ ного двоичного кода.

Н а этом ж е рисунке в четвертом ряду фигур изображены геометрические фигуры выходных сигналов сумматора при P = 1*, минуя промежуточные n- преобразования, сразу в координатах основного двоичного кода.



Pages:     | 1 || 3 | 4 |   ...   | 9 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.