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

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

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


Pages:   || 2 | 3 | 4 | 5 |   ...   | 9 |
-- [ Страница 1 ] --

ФЕДЕРАЛЬНОЕ КОСМИЧЕСКОЕ АГЕНТСТВО

Федеральное государственное унитарное предприятие

"Научно-производственный центр "Полюс"

В.И. Кочергин

ТЕОРИЯ

МНОГОМЕРНЫХ

ЦИФРО-ВЕКТОРНЫХ МНОЖЕСТВ

Издательство Томского университета

2006

У Д К 681.326

Б Б К 32.973.2

К 55

Кочергин В.И.

К 55 Теория многомерных цифро-векторных множеств. - Томск:

Изд-во Том. ун-та, 2006. - 380 с.

I S B N 5-7511-1987-2 Книга содержит систематическое и доступное изложение результатов по созданию теории многомерных цифро-векторных множеств. В основу теории положены классическая теория множеств, цифровая версия пространства и финитная точка зрения, которая рассматривает начала логики и арифметики в виде мысленных экспериментов над наглядно представляемыми овеществ­ ленными цифрами расширенного натурального ряда и при этом ограничивает теорию множеств конечными объектами.

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

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

УДК 681. ББК 32.973. I S B N 5-7511-1987-2 © В.И. Кочергин, Оглавление Предисловие Введение Список обозначений и сокращений Глава 1. Основные положения теории 1.1. Обычные двухзначные логические функции в многомерном циф¬ ровом пространстве 1.2. Позиционные системы счисления 1.3. Основные логические операции над подмножествами многомерно¬ го цифрового пространства 1.4. Бинарные логические операции в двухмерном цифровом про¬ странстве 1.5. Сложные логические функции в двухмерном цифровом простран¬ стве 1.6. Тернарные логические операции в трехмерном цифровом про¬ странстве 1.7. Сложные логические функции в многомерном цифровом про¬ странстве 1.8. Непрерывное множество ряда натуральных чисел в многомерном цифровом пространстве 1.9. Многозначные логические функции в многомерном цифровом пространстве 1.10. Алгоритмы синтеза двухзначных логических функций 1.11. Примеры синтеза одноразрядного устройства суммирования и вычитания 1.12. Пример анализа неизбыточных кодов позиционной системы счис¬ ления 1.13. Синтез суммирующих и вычитающих устройств в нетрадицион¬ ных двоичных кодах 1.

14. Синтез одноразрядных умножителей Глава 2. Синтез умножителей, делителей и счетчиков 2.1. Синтез устройств умножения 2.2. Синтез устройств деления 2.3. Синтез реверсивных счетчиков 2.4. Синтез управляемых делителей-счетчиков Глава 3. Контролеспособность позиционных систем счисления 3.1. Расположение ошибок позиционных систем счисления в много¬ мерном пространстве 3.2. Многофазный код 3.3. Анализ контролеспособности многофазного кода методом много¬ мерных цифровых множеств 3.4. Анализ контролеспособности кодов Хемминга методом многомер¬ ных цифровых множеств 3.5. Анализ контролеспособности обычного цифрового кода методом многомерных цифровых множеств 3.6. Анализ контролеспособности кода реверсивного двоичного дели¬ теля-счетчика 3.7. Геометрический синтез контролеспособных кодов позиционных систем счисления 3.7.1. Коды с обнаружением одиночных ошибок 3.7.2. Коды с исправлением одиночных ошибок 3.7.3. Коды больших оснований систем счисления с исправлением одиночных ошибок 3.8. Решение задачи повышения надежности логических и цифровых устройств в режиме реального времени Глава 4. Примеры синтеза комбинационных схем Пример 1. Синтез устройства исправления одиночных ошибок двоич­ ной системы счисления основания n =16 Пример 2. Синтез устройства исправления одиночных ошибок двоич­ ной системы счисления для любых синтезированных кодов осно¬ вания n =2 Пример 3. Синтез одноразрядного сумматора (A ± B ) с исправлением одиночных ошибок в системе счисления основания n = 16 Пример 4. Синтез сумматора основания n = 16 предельного быстро¬ действия с исправлением одиночных ошибок Пример 5. Синтез устройства исправления одиночных ошибок двоич¬ ной системы счисления основания n =2 без использования записи в ячейки пространства эквивалентных цифр его информационной части Глава 5. Систематический код с исправлением одиночных ошибок системы счисления основания n = 2 5.1. Синтез кода и его кодирующего устройства 5.2. Исправление одиночных ошибок в информационной части кода... 5.3. Исправление одиночных ошибок в контрольной части кода 5.4. Структурная схема исправления ошибок во всех разрядах система¬ тического кода Глава 6. Продолжение геометрического синтеза кодов, исправляю­ щих ошибки 6.1. Синтез кодов с информационной частью в основном двоичном коде основания n = 2, исправляющих одиночные и двойные ошибки 6.2. Синтез кодов с информационной частью в основном двоичном коде основания 2, исправляющих все группы ошибок 6.3. Синтез систематических многофазных и интегральных кодов.... 6.3.1. Двухфазный код 6.3.2. Трехфазный код 6.3.3. Многофазные коды с числом фаз m = 4, 8, 16, 6.3.4. Многофазные коды с числом фаз m = 6, 9, 12, 15, 18 6.3.5. Интегральные коды 6.3.6. Синтез декодирующих блоков для системных многофазных и интегральных кодов 6.3.7. Синтез кода, управляющего переключением транзисторов трехфазного инвертора напряжения и исправляющего все одиночные ошибки Заключение Литература Предисловие Теория многомерных цифро-векторных множеств может рассматриваться как один из многочисленных инструментов теории конечных автоматов. Н е ­ редко м о ж н о встретить определение, что теория автоматов является частью теории систем - научной дисциплины, появившейся в середине Х Х в. П р и этом в теорию систем включают также теорию информации, теорию линейных и нелинейных систем, теорию управления и т. д.

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

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

Автор придерживается именно этого более широкого понимания теории автоматов, которая полностью равноценна определению теории систем.

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

Существует огромное количество научных работ, например, по теории конечных автоматов. Ч е м не устраивают эти математические труды практиче­ ских инженеров - творцов искусственных автоматов? Ответ на этот вопрос на¬ сколько прост, настолько и сложен - все эти теоретические работы считают такие системы однородными, что не соответствует действительности. Только весьма простые автоматы можно условно считать однородными, где можно воспользоваться результатами этих теоретических исследований.

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

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

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

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

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

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

Инбридинг - скрещивание двух близкородных организмов (биол.).

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

А. Эйнштейн Введение Приступая к изложению математической теории, нужно дать определение этого понятия и предназначение её как для математиков, так и для инженеров, на которых, прежде всего, рассчитана книга.

П р и определении понятия «теория формальная» в математической науке дается ссылка на следующие определения: аксиоматический метод, формаль­ ная система, метатеория.

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

В математике аксиоматический метод зародился в работах древнегрече­ ских геометров («Начала» Евклида около 300 лет до н.э.). В е р ш и н а аксиома­ тического метода была достигнута в работах Д. Гильберта и его ш к о л ы в виде так называемого метода формализма в основаниях математики. В рамках этого направления была выработана следующая стадия уточнения понятия аксиома¬ тической теории, а именно понятие формальной системы.

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

В ы р а ж е н и я формальной системы рассматриваются как чисто формальные комбинации символов;

правила вывода определяют, в каких случаях одно формальное выражение А выводится из других формальных выражений Ei, В. Е с л и n=0, то А называется аксиомой. П р и этом выводы представля¬ п ю т собой либо последовательности, либо древовидные фигуры, составленные из формальных выражений согласно правилам вывода. Е с л и в вершинах дере¬ ва вывода находятся только аксиомы, то формальное выражение, завершаю¬ щее вывод, называется выводимым в формальной системе.

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

Н е о б х о д и м о отметить, что немецкие математики Д. Гильберт и П. Б е р найс признали эту критику. В двухтомной монографии, изданной уже после смерти Ф. Клейна (Гильберт Д., Бернайс П. Основания математики) в Герма­ нии в 30-х годах прошлого века и переизданной в 1968 г. издательством Шпрингера, они представили дополнительно финитную точку зрения, которая содержит «прямые содержательные рассуждения, совершаемые в виде мыс­ ленных экспериментов над наглядно представляемыми объектами и не зави­ сящие от предложений аксиоматического характера определенными геометри­ ческими фигурами. Рассуждения такого рода м ы для краткости будем назы­ вать финитными, а методическую установку, л е ж а щ у ю в основе этих рассуж­ д е н и й... финитной установкой или финитной точкой зрения. В том ж е самом смысле м ы будем говорить о финитных понятиях и утверждениях, подчерки¬ вая всюду словом финитный, что рассматриваемое рассуждение, утверждение или определение придерживается рамок принципиальной представимости объектов и принципиальной выполнимости операций, а тем самым происходит в рамках конкретного рассмотрения»». И далее: «Всеобщее суждение о цифрах финитно может быть истолковано в гипотетическом смысле, т. е. как выска¬ зывание о произвольно заданной цифре. Такое суждение провозглашает неко¬ т о р ы й закон, который должен подтверждаться в каждом конкретном случае».

Е щ е далее: «... и все-таки в арифметике потребность в выходе за пределы финитной точки зрения на самом деле не является такой уж ощутимой»»

Более определенно можно утверждать, что для рассмотрения законов арифметики и математической логики нет необходимости использовать ак¬ сиоматический метод, поскольку арифметика и математическая логика имеют дело только с наглядно представляемыми объектами - цифрами натурального ряда, которые не зависят от предложений аксиоматического характера, а, по словам немецкого математика Л. Кронекера, восходят к Богу: «Господь Бог создал натуральные числа, а все остальное дело рук человечества».

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

Кратко т е о р и ю многомерных цифро-векторных множеств м о ж н о охарак¬ теризовать единством следующих составляющих:

1. Классическая теория множеств Г. Кантора.

2. Р а с ш и р е н н ы й натуральный ряд чисел (0, 1, 2,... ), которые выступают в качестве элементарных подмножеств этого множества.

3. Векторное представление цифр разрядов числа, где вершина цифрово¬ го вектора обозначается максимальной (п-1)-й цифрой разряда n-го основания системы счисления.

4. И д е и великого русского ученого Е.С. Федорова [58] по упаковке физи¬ ческого пространства определенными геометрическими фигурами, например кубиками, и наше предложение нумерации их числами расширенного нату¬ рального ряда.

5. Представление мерности цифрового пространства разрядностью числа.

6. Введение в эту наглядную геометрию пространства мысленных пово¬ ротов относительно осей симметрии цифро-векторного пространства.

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

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

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

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

Следует также признать, что Д. Гильберт не считал аксиоматический ме¬ тод единственным для доказательства построения той и или иной теории. Об¬ ратимся к общеизвестной книге, изданной в Г е р м а н и и в 1932 г. и неоднократ­ но переиздаваемой в С С С Р [2], в предисловии к которой он написал: «В мате¬ матике, как вообще в научных исследованиях, встречаются две тенденции:

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

«... наглядное понимание играет первостепенную роль в геометрии, и притом не только как обладающее большой доказательной силой при исследовании, но и для понимания и оценки результатов исследования».

М н о г и е исследователи ссылаются на классиков, но, по словам канадского математика Г. Глинского (Международный симпозиум по теории релейных устройств и конечных автоматов, 1962 г.), «есть одна опасность в обращении к классическим работам. Кажется, что на них все ссылаются, но редко кто их действительно читает». П о этой причине аксиоматический метод многие ис¬ следователи считают единственным для построения математической теории, ссылаясь при этом на великого ученого Д. Гильберта, что не соответствует действительности.

Теория многомерных цифро-векторных множеств не является алгебраи¬ ческой, а скорее относится к геометрии, хотя и необычной. О н а опирается на идею академика Е. С. Федорова по упаковке физического пространства опре¬ деленными геометрическими фигурами. Здесь следует особо отметить, что Д. Гильберт является единственным из великих математиков Х Х в., кто уделил должное внимание математическим работам Е. С. Федорова. В отмеченной в ы ш е книге содержится несколько разделов, где о н рассматривает «кристалло¬ графические (Федоровские) группы движений на плоскости и пространстве»

[2. С. 78-101].

Теперь обратимся к философскому определению термина «теория» (Фи¬ лософский словарь. М.: Политиздат, 1968).

Теория - система обобщенного знания, объяснения тех или иных сторон действительности. Термин «теория» имеет различные значения: для того что¬ бы отличать ее от практики или для противопоставления гипотезе (как непро¬ веренному, предположительному знанию).

Этот термин, как н а м кажется, полностью применим и для математиче­ ской науки, в которой, по м н е н и ю известного польского математика А н д ж е я Мостовски, существует «единственная непротиворечивая точка зрения, согла¬ сующаяся не только со з д р а в ы м смыслом, но и с математической традицией, которая сводится по существу к д о п у щ е н и ю того, что источник и высший смысл понятия числа лежит в опыте и практической применяемости. То ж е от¬ носится и к теории множеств в т о м объеме, в каком они необходимы для клас¬ сических областей математики» [Клайн М. Математика. Утрата определенно­ сти. М.: М и р, 1984]. Поэтому, если угодно, представляемая теория многомер¬ ных цифро-векторных множеств относится к прикладной математике и пред¬ назначается для решения практических задач анализа и синтеза логических и цифровых систем, устанавливаемых непосредственно в системах автоматиче¬ ского управления, а также и к теории автоматов, история которых начинается в сороковых годах X X в. с исторических работ Дж. ф о н Неймана, который мечтал построить систематическую теорию, логико-математическую по фор¬ ме, позволяющую понять как естественные, так и искусственные автоматы.

П р и этом в качестве разновидности сложных автоматов и м рассматривались вычислительные машины, «которые выделяются тем, что дают нам надежду хоть что-то понять». Он считал, что естественные автоматы являются т е м идеалом, к которому д о л ж н ы приближаться искусственные автоматы.

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

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

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

В 80-х годах X X в. многие ученые считали, что «модели одиночного вы¬ числителя исчерпаны, а скорость работы элементов близка к теоретической.

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

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

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

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

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

О д н и м из путей решения этих задач является использование программи¬ руемых логических интегральных схем [ П Л И С или П Л У - Programmable Logic Devices (PLDs)]. Это новая технология проектирования электронных схем, где в основу архитектуры положена структура программируемых матриц логики [ П Л М - Programmable Array Logic (PALs)]. Основу П Л М составляют две мат¬ р и ц ы «И» и «ИЛИ», где программируется матрица «И», а матрица « И Л И »

имеет фиксированную настройку.

Проектирование таких устройств получило название двухуровневого син¬ теза, в отличие от многоуровневого, который используется при проектирова¬ нии цифровых систем на основе F P G A (Field Programmable Gate Array) или C P L D (Copmlex P L D ).

В отечественной литературе нет четкости в определении таких схем, ко¬ т о р ы е обычно называются П Л И С или П Л У. Поэтому остановимся на этих оп¬ ределениях более подробно.

И с т о р и я P L D начинается с 70-х годов X X в. с появлением программи¬ руемых постоянных з а п о м и н а ю щ и х устройств [ППЗУ - Programmable Read Only Memory ( P R O M ) ]. В дальнейшем для реализации систем булевых функ¬ ций стали выпускаться программируемые логические матрицы [ П Л М Programmable Logic Array (PLAs)], которые м о ж н о считать первыми P L D. Со¬ вершенствование архитектуры P L D привело к созданию программируемых матриц логики П М Л. В дальнейшем при расположении на одном кристалле нескольких P A L, которые объединялись программируемыми соединениями, были созданы сложные П Л У [Copmlex P L D ( C P L D ) ], а созданные ранее P L D стали называть стандартными [Standart P L D (SPLD)].

Одновременно с P L D создавались структуры вентильных матриц [Gate Array (GA)] и матриц логических ячеек [Logic Cell Array ( L C A ) ], которые в дальнейшем превратились в программируемую пользователем вентильную матрицу [Field Programmable Gate Array ( F P G A ) ].

Теоретическую основу методов синтеза этих устройств составляют алгеб¬ ра Буля (булева алгебра), математическая логика [18, 61, 65] и др. Методы двух¬ уровневого синтеза комбинационных схем используют теорию булевых или пе¬ реключательных функций, которые также применяются на ранних этапах мно¬ гоуровневого синтеза [11]. Р е ш е н и ю задач минимизации булевых функций по¬ священо такое большое количество работ, что простое их перечисление вызы¬ вает значительные сложности. Остановимся только на некоторых из них.

Классическим решением задачи минимизации булевых функций принято считать работу E. J. M c Cluskey [101], а все последующие м о ж н о разбить на группы: эвристические алгоритмы [32, 41, 69, 81, 82];

точные алгоритмы [32, 65, 92, 120];

алгоритмы минимизации частично определенных булевых функ­ ций [105];

алгоритмы минимизации слабо определенных булевых функций [104], алгоритмы минимизации системы булевых функций [30] и многие дру¬ гие.

В [75] для операции с булевыми функциями используется диаграмма дво¬ ичных р е ш е н и й [Dinary Decision Diagrams (DDs)], а в [111] предложено ис¬ пользовать графическое представление этих функций [IF-decision Diagrams (IFDs)], которое, по м н е н и ю авторов, позволяет повысить уровень параллель ности логических вычислений. Метод неявного представления простых им пликант [81] позволяет осуществлять минимизацию булевых функций с боль¬ ш и м числом аргументов.

Классические методы декомпозиции булевых функций лежат в основе ме¬ тодов многоуровневого синтеза. В [66] представлен метод дизъюнктивной де­ композиции на основе декомпозиционных диаграмм, который в [83] был рас¬ пространен на множественную композицию. Более компактная форма пред¬ ставления булевых функций в виде покрытия нулевых и единичных значений была выполнена в [115]. Все эти методы были развиты в [84], где приведены точные и приближенные алгоритмы минимизации многовыходной логической сети при ограничениях на число уровней сети и на коэффициенты расширения выходных вентилей. Однако представленные здесь методы приспособлены только для решения задач малой размерности, а для практического применения возможно использование только приближенных методов многоуровневого син¬ теза, которые основаны на локальных преобразованиях логических сетей [57].

П е р в ы е методы для решения задач многоуровневого синтеза были осно¬ ваны на дизъюнктивном разложении К.А. Ш е н н о н а [Shannon C. A symbolic analisis of relay and switching circuts // Trans. of American Inst. of Electrical Engineirs. 1938. № 57], который был создан им для контактных схем, но они не привлекли внимания разработчиков аппаратуры. В [31] представлено несколь¬ ко подходов к р е ш е н и ю задачи декомпозиции при синтезе комбинационных схем на P L A, которые получили названия: стандартная декомпозиция [31];

ортогонализация интервалов [4];

тождественные отображения и эвристи¬ ческие алгоритмы реализации метода тождественных отображений [62], которые в работах большого числа авторов [63, 64, 71, 74, 80, 94, 113] были усовершенствованы и позволили решать задачи декомпозиции с точки зрения минимизации числа входов P L A нижнего уровня и числа используемых про­ межуточных ш и н P L A.

Наиболее популярными подходами к синтезу P L A комбинационных схем с б о л ь ш и м числом входов являются методы матричной факторизации [30, 38, 37] и метод дизъюнктивно-конъюнктивного разложения [52].

Методы совместной декомпозиции рассматриваются в [3], а задача со¬ вместного дизъюнктивно-инверсного разложения системы булевых функций в [5]. В [10] рассматривается множественная декомпозиция булевых функций, сводящихся к задаче решения логического уравнения.

Другие способы многоуровневого синтеза у с п е ш н о используют при про¬ ектировании логической сети алгебраические методы [70, 71, 73], которые, в отличие от булевых методов, могут применяться на технологически независи¬ м о м уровне. Они быстрее булевых и поэтому позволяют решать задачи боль¬ шого размера, но булевы методы, по м н е н и ю ряда авторов, более точные, и поэтому в [72] используется сочетание алгебраических и булевых методов.

П р и многоуровневом синтезе, как и в двухуровневом, используются мно¬ гозначные функции [3, 96], в т о м числе с многозначными входами и выходами [107].

Другие методы и программы многоуровневого синтеза логических функ¬ ций приведены в работах [30, 78, 80, 90, 95, 97-99, 107-109, 114, 121].

П о д р о б н ы е обзоры методов синтеза комбинационных схем м о ж н о найти в работах [116, 118, 119] и в отечественных: [4, 53, 60].

Н е о б х о д и м о отметить недостатки, которые не позволяют непосредствен¬ но применять ряд этих методов для синтеза комбинационных схем на совре¬ менных П Л И С. К н и м следует отнести следующие:

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

в) некоторые методы ориентированы на очень узкий класс р е ш а е м ы х за¬ дач, и нередко примеры, которые приводятся в этих работах, весьма просты;

б) почти все методы не позволяют эффективно использовать архитектур¬ ные особенности современных схем П Л И С ;

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

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

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

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

П р и м е н е н и е AN-кодов требует предварительного у м н о ж е н и я исходных чисел на некоторое заранее выбранное число A с п о с л е д у ю щ и м выполнением арифметических операций над числами вида A N, где в дальнейшем осуществ¬ ляется декодирование с исправлением или обнаружением ошибок, которые также требуют проверки определенных вычислений. Исследования AN-кодов начинались с работ [85, 76], а в дальнейшем развивались в работах зарубеж¬ ных [40, 112, 86-89] и отечественных авторов [6-8, 33, 94, 16, 122].

Теория AN-кодов интенсивно развивалась в 70-е годы Х Х в., но затем многие из исследователей п р и ш л и к выводу, что для практического примене¬ ния в вычислительных системах наиболее приспособлены остаточные коды.

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

Теория остаточных кодов впервые была представлена в [110] и очень успешно развивалась в работах отечественных авторов [1, 15 19-26, 28, 39]. В дальней¬ ш е м исследователи обратили внимание на необходимость использования цик¬ лической структуры AN-кодов, где существовала аналогия между цикличе­ скими AN-кодами и кодами для передачи информации в системах связи, на¬ пример кодами Хемминга. Теоретическим исследованиям циклических A N кодов с контролем по модулю посвящено большое количество работ, среди которых необходимо отметить следующие: [17, 27, 36, 56, 51, 102, 103, 67, 77, 106, 93, 117].

Однако в практическом плане радужные перспективы применения этих кодов в цифровых устройствах не дали каких-либо положительных результа¬ тов и ограничились только контролем четности (нечетности). Недостатки при¬ менения этих кодов рассматриваются в работах [12-14]. С а м ы й существенный из них заключается в у м е н ь ш е н и и номинального быстродействия цифровых вычислительных систем, по м н е н и ю Е. И. Брюховича, не менее чем вдвое. Эта оценка явно занижена, так как быстродействие будет е щ е ниже, поскольку и м учитывалась только операция обнаружения о ш и б о к и не учтено время на ис¬ правление этих ошибок.

Известно, что кодирование для л ю б ы х типов кодов, в т о м числе и ариф¬ метических, не составляет проблемы, и процесс кодирования сводится к вы¬ числению наименьших вычетов по заданному модулю. П о д о б н у ю задачу не¬ обходимо решать на первом этапе декодирования (обнаружение ошибок) при вычислении синдрома, для чего используются схемы свертки [42, 44]. Органи¬ зация работы на втором этапе декодирования (исправление ошибок) вычисли¬ тельного комплекса, использующего арифметические коды, обсуждается в ра¬ ботах [39, 43, 59, 55], а перестановочное декодирование - в [91] и частично в [122].

Декодирование при исправлении одиночных пакетов ошибок для цикличе¬ ских AN-кодов было исследовано в [9], а для двойных пакетов ошибок - в [54].

Ш и р о к о е применение в технике связи для операции исправления ошибок методов мажоритарного декодирования циклических кодов вызвало попытку р е ш и т ь подобную задачу в вычислительных комплексах для AN-кодов [79, 93], но кроме теоретических предпосылок это не принесло практических результа¬ тов. Это также можно сказать о декодировании m - м е р н ы х итеративных цикли¬ ческих кодов [6].

Рассмотрение арифметических кодов проводится всеми исследователями для реализации только одной арифметической операции - суммирования, ко¬ торая считается ими базовой для всех других операций (умножения, деления, возведения в степень и т. д.). Такой подход нельзя считать корректным, но да¬ ж е при таком у п р о щ е н н о м решении возникают сложности с сигналами пере¬ носа. В [122] рассматривается в теоретическом плане использование весовых соотношений, связывающих операнды, сумму и переносы, для исправления одиночных ошибок в работе сумматора.

Р е ш е н и е задач обнаружения и исправления о ш и б о к цифровых систем ви¬ дится Ю.Г. Дадаевым в «создании специального процессора исправления, ра¬ ботающего независимо и параллельно с выполнением Э В М основных функ¬ ций. Такой процессор можно использовать для исправления ошибок, возни¬ к а ю щ и х не только при выполнении операций, но и при продвижении операн¬ дов на всем пути от м а ш и н ы до исполнительных устройств» [28]. Это предло¬ жение решения задачи м о ж н о принять к реализации, но только не для систем реального времени, где необходимо иметь подобный «сопроцессор», превос¬ х о д я щ и й по быстродействию основной вычислительный комплекс, быстро¬ действие которого здесь находится на пределе возможного.

Ряд исследователей видит решение задачи повышения помехоустойчиво¬ сти цифровых систем в использовании систем счисления с иррациональным основанием типа «золотой пропорции», которая была предложена в [68]. Из¬ быточные самосинхронизирующие коды Фибоначчи [100] рассматриваются в [45-50] как альтернатива с у щ е с т в у ю щ и м позиционным системам счисления и, по м н е н и ю А. П. Стахова, сохраняют все их известные преимущества: «про¬ стота сравнения чисел по величине и "наглядность" в изображении чисел, про¬ стота арифметических правил, возможность представления чисел с фиксиро¬ ванной и плавающей запятой, однородность и итеративность реализующих арифметику структур и др.». Однако здесь ж е говорится о том, что применение этих кодов в вычислительной технике «является спорным и его решение тре¬ бует дальнейших исследований».

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

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

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

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

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

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

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

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

Это пожелание автор стремился реализовать в данной книге. Основатель теории автоматов Дж. фон Н е й м а н [7], несмотря на большое значение матема¬ тической логики в теории автоматов, которое он отмечал, был убежден, что она не адекватна «истинной» логике автоматов, и считал, что это будет новая логика, которая будет объединять различные дисциплины. Эту цель поставил перед собой автор данной работы, стараясь при этом избежать, по словам Д. И. Менделеева, трех губительных крайностей: «утопий мечтательности, же¬ л а ю щ е й всё постичь одним порывом мысли;

ревнивой косности, самодоволь¬ ствующейся обладаемым;

кичливостью скептицизма, ни на чем не решающе¬ гося остановиться».

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

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

[Конвей Дж., Слоен Н. Упаковки шаров, решетки и группы: В 2 т. / Пер. с англ.

М.: М и р, 1990].

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

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

В е л и к и й Леонардо да В и н ч и восклицал: «Неужели не видишь ты, что глаз объемлет красоту всего мира?.. О н направляет и справляет все искусства чело¬ веческие, двигает человека в разные части света. О н - начало математики.

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

К этому утверждению необходимо добавить высказывание нашего совре¬ менника А. Д. Гончарова: «Точный язык науки и техники, язык положений и выводов, цифр и формул х у д о ж н и к должен обогатить образами, чтобы чита¬ тель мог усвоить нужную и н ф о р м а ц и ю легко, в краткий срок, в формах зри¬ тельно ясных и эстетически полноценных».

П е р е й д е м к изложению «неглубокой» математики по укладке кубиков в Е в к л и д о в о м пространстве и будем решать задачи, которые пока не р е ш е н ы «глубокой» математикой.

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

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

П П З У - программируемое постоянное запоминающее устройство ( P R O M Programmable Read Only Memory)] Б И С - большая интегральная схема С Б И С - сверхбольшая интегральная схема П Л И С - программируемая логическая интегральная схема или П Л У программируемое логическое устройство ( P L D - Programmable L o g i c Device) П Л М - программируемая логическая матрица ( P L A s - Programmable Logic Arrays) П М Л - программируемая матрица логики ( P A L - Programmable Array Logic) G A (Gate Array) - вентильная матрица L C A (Logic Cell Array) - матрица логических ячеек F P G A (Field Programmable Gate Array) - программируемая пользователем вентильная матрица C P L D (Complex P L D ) - сложное П Л У S P L D (Standard P L D ) - стандартное П Л У О Ц К - о б ы ч н ы й цифровой код Л Ф - k-значная логическая функция к Л Ф ( Л Ф ) - двухзначная логическая функция N - расширенный натуральный ряд чисел Д Н Ф - дизъюнктивная нормальная форма записи Л Ф A, B, C,... - запись операндов в прямом коде A", B*, C*,... - запись операндов в обратном коде 0, 1, 2,... - ц и ф р ы О Ц К 1* - логическая единица 0* - логический нуль X - отрицание X - рабочая область многомерного цифрового пространства A, B, C,. - операнды, множества, векторы, одномерное цифровое про¬ странство AB, A C, BC,. - двухмерные цифровые пространства ABD, ACD, BCD,... - трехмерные цифровые пространства и т.д.

Uj - вектор напряжения, соответствующий кодовой комбинации много¬ фазного кода для цифры i ц (i - 1) = 0 v... v (i - 1) - непрерывное множество цифр О Ц К M(i) = 0 v... v i = 1 v... v i =... = i - л ю б о е цифровое множество, содер­ ж а щ е е цифру i d (i) - кодовое расстояние между к о д о в ы м и комбинациями из i разрядов a операнда A w (i) - весовые значения кодовых комбинаций из i разрядов операнда A a d, - кодовые расстояния между к о д о в ы м и комбинациями систематиче­ a x ского кода (A - информационная часть кода, X - контрольная часть кода) d (2,3) - кодовые расстояния контрольной части квазисовершенного двух¬ x фазного кода dx(3,3) - кодовые расстояния контрольной части квазисовершенного трех¬ фазного кода d (m;

2,3) - кодовые расстояния системного многофазного кода (m - чис­ a;

X ло фаз информационной части кода;

2,3 - контрольная часть квазисовер¬ шенного двухфазного кода) d (m;

3,3) - кодовые расстояния системного многофазного кода (m - чис¬ a;

X ло фаз информационной части кода;

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

И.М. Яглом Пространство есть не что иное, как ча стн ый случай трижды протяженной величины.

К.Ф. Гаусс Глава ОСНОВНЫЕ ПОЛОЖЕНИЯ ТЕОРИИ П р е д л о ж е н н ы й в [17] нестандартный подход к у п р а в л я ю щ и м дискретным логическим устройствам и цифровой технике включает в их состав не только машинную арифметику и цифровые системы управления, но и электропривод, преобразовательную измерительную и силовую технику и т.д. Предлагаемая вниманию теория многомерных цифро-векторных множеств является инстру¬ ментом для синтеза в этих областях техники оптимальных устройств, исходя из расширенного натурального ряда чисел N. 1.1. Обычные двухзначные логические функции в многомерном цифровом пространстве П е р в ы е понятия, с которых начинается любая теория, д о л ж н ы быть яс¬ н ы и приведены к самому наименьшему числу. Только тогда они могут слу¬ ж и т ь прочным и достаточным фундаментом этой теории.

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

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


э., когда вавилоняне [18] употребляли шестидесятеричную систему счисления с позиционным принципом записи числа. Современное представление позици­ онной системы счисления определяется следующим образом: «Систему счис¬ ления называют позиционной, если одна и та ж е цифра может принимать раз¬ л и ч н ы е численные значения в зависимости от номера местоположения (разря­ да) этой ц и ф р ы в совокупности цифр, представляющих заданное число. Пози¬ ционные системы разделяют на однородные и смешанные. В о всех разрядах числа, представленного в однородной системе, используются ц и ф р ы из одного и того ж е множества. Например, в обычной десятичной системе во всех разря­ дах л ю б о г о числа используются ц и ф р ы из множества {0, 1,..., 9}, в двоичной системе - ц и ф р ы из множества {0, 1} и т.п. В смешанных системах множества цифр различны для разных разрядов. В тех случаях, когда в позиционной сис­ теме для каждой ц и ф р ы имеется отдельный символ, её называют системой с непосредственным представлением чисел. В позиционных системах с кодиро¬ ванием чисел количество символов меньше, чем количество цифр, а каждая цифра кодируется определенной комбинацией из нескольких символов» [21].

Во-вторых, под кодом будем понимать «правило преобразования сообще­ ния из одной символьной ф о р м ы представления (исходного алфавита) в дру­ гую (объектный алфавит)» [22]. В нашем случае ц и ф р ы натурального ряда конкретного основания системы счисления составляют одну символьную сис¬ тему (систему с непосредственным представлением чисел). Другая символьная система определяет принцип кодирования, где обычно количество символов меньше, чем количество цифр кодируемого основания системы счисления.

В-третьих, поскольку в большей части коды, в т о м числе и система с непо¬ средственным представлением чисел, являются циклическими, то необходимо дать определение циклического кода: «Подпространство V наборов д л и н ы n называется циклическим подпространством или циклическим кодом, если для любого вектора V = ( a, a„, a ) из подпространства V вектор V' = n-1 -2 = (a, a, a, a ), получаемый в результате циклического сдвига компонен­ 0 n-1 n-2 та вектора V на единицу вправо, также принадлежит подпространству V'» [19].

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

О б ы ч н о й двухзначной логической функцией, в д а л ь н е й ш е м логической функцией ( Л Ф либо, опуская индекс 2, Л Ф ) y = f (x,..., x ) называется 2 1 k функция, п р и н и м а ю щ а я, как и её аргументы x,..., x, два значения, кото­ 1 k р ы е обозначим, чтобы отличать от сигналов 0 и 1 обычного цифрового кода (ОЦК), с и м в о л а м и 0* и 1*.

П о с к о л ь к у число различных наборов значений аргументов Л Ф конечно и к равно 2, любая Л Ф м о ж е т быть задана (на примере k = 3) таблицей истинно¬ сти (табл. 1.1.1).

Таблица 1.1. ОЦК x xs x2 y 0 0* 0* 0* 0* 1 0* 0* 1* 1* 2 0* 1* 0* 1* 3 0* 1* 1* 0* 4 1* 0* 0* 1* 5 1* 0* 1* 0* 6 1* 1* 0* 0* 7 1* 1* 1* 1* В таблице наборы значений аргументов расположены в порядке возрастания:

сначала идет набор (иное название набора - кодовое слово или кодовая комби¬ нация), представляющий собой двоичное расположение числа 0 (0*,..., 0*), затем следует набор, я в л я ю щ и й с я д в о и ч н ы м расположением числа 1;

за н и м записывается набор, соответствующий числу 2, и т.д. Последний набор со­ стоит из К единиц (1*,..., 1*) и является двоичным разложением числа на­ К турального ряда ( 2 - 1). Такое кодирование цифр натурального ряда называ¬ ется двоичным.

Е с л и всем наборам значений аргументов Л Ф y = f (x... x ) поставить в 1;

;

K К соответствие сигналы О Ц К от 0 до ( 2 - 1), т.е. ц и ф р ы расширенного нату­ рального ряда, то каждый аргумент x (i = 1, K ) и сама Л Ф будут представ¬ i лять собой определенные цифровые множества, что для нашего примера будет выражено с л е д у ю щ и м образом:

x = 1 v 3 v 5 v 7;

x = 2 v 3 v 6 v 7;

x = 4 v 5 v 6 v 7;

y = 1 v 2 v 4 v 7.

1 2 Н а отрезке конечной длины цифровой «прямой» (рис. 1.1) графически представлены соотношения между этими ц и ф р о в ы м и множествами. jx^ Определение ж е бесконечной цифровой x «прямой» следующее: геометрическое изо- x бражение бесконечного множества натураль­ ных действительных чисел N o, когда нату- ральное число получается последователь- y н ы м прибавлением 1, начиная с 0, причем является равноправным элементом наряду со * всеми другими цифрами 1, 2, 3 и т.д. Р 11ис Следовательно, если на бесконечной «прямой» g заданием начала отсчета и положительного направления цифро¬ вого вектора откладывать последовательно единичные отрезки, соответст¬ в у ю щ и е цифрам 0, 1, 2,..., то каждый единичный отрезок L «прямой» g однозначно определяется своей координатой N o. Таким образом, каждому единичному отрезку L «прямой» g соответствует одно действительное нату¬ ральное число N o, и обратно: каждому натуральному числу N o соответствует один элемент, расположенный на конце цифрового вектора.

К П р и таком соответствии каждая последовательность 2 различных набо¬ ров значений аргументов с учетом порядка их расположения определяет К принцип кодирования сигналов О Ц К от 0 до ( 2 - 1).

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

И с х о д я из этого, последовательность набора аргументов, соответствующую двоичному принципу кодирования, будем считать стандартной [24] формой представления, что и выполнено в табл. 1.1.1 и на рис. 1.1.

П р и основном двоичном кодировании так же, как и при других способах кодирования, м о ж н о рассматривать цифровую «прямую» с элементами от 0 до К ( 2 - 1) как графическое представление системы счисления одного основания, К равного 2, либо как часть системы счисления с одним основанием, большим К чем 2. Эту бесконечную «прямую» м о ж н о представить также последователь¬ н ы м соединением разрядов числа с м е н ь ш и м и основаниями, равными по зна K L S T ч е н и ю либо различными 2 = 2 2 2... ( K = L + S + T +...). Такое пред­ ставление числа позволяет изобразить графически каждый аргумент x и са­ i му функцию y = f (xi, _ x ) не только на цифровой «прямой» (одномерное ;

K цифровое пространство), но и в многомерном варианте этого пространства.

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

П р и этом Л Ф y = f (x, _ x ), п р и н и м а ю щ а я для всех наборов аргумен­ 1 ;

K тов Х{ значение 1*, представляет собой непрерывное цифровое множество сигналов от 0 до (2 - 1), т.е. то многомерное цифровое пространство Е (уни версальное цифровое множество), в котором размещается «объем» л ю б о й Л Ф y = f (x _ x ) с м е н ь ш и м числом наборов аргументов xi, равных 1*.

1,, K Рис. 1. Для трехместной (тернарной) логической операции y = f (x, x, x ) Л Ф, 1 2 заданная табл. 1.1.1 и представленная (см. рис. 1.1) на цифровой «прямой»

(одномерное пространство), может быть также изображена в двухмерном про¬ странстве (см. рис. 1.2, а), трехмерном пространстве (см. рис. 1.2, б) либо в трехмерном пространстве, нарисованном послойно (см. рис. 1.2, в). В этом случае м о ж н о говорить, что геометрический образ логической функции y = f (x _ x ) одномерного цифрового пространства однозначно может ото¬ 1,, K бражаться на двухмерных и трехмерных ц и ф р о в ы х пространствах.

Во всех этих представлениях число ячеек пространства одно и то же, а число разрядов и их оснований различно. Цифровые пространства с равным количеством ячеек будем называть эквивалентными. Здесь и в дальнейшем значение Л Ф, равное 1*, обозначим звёздочкой (*), а соответствующая ячейка пространства, где Л Ф равна o*, будет пустой.

Для того чтобы увидеть все ячейки многомерного цифрового пространст¬ ва, у м е н ь ш и м их масштаб, но сохраним их положение в декартовой системе координат. Тогда геометрический образ ло¬ гической функции рис. 1.2 в трехмерном цифровом пространстве координат x1, x2, x будет преобразован в рис. 1.3.

Н а этих рисунках «длина», «площадь», «объем» определяются мерностью про¬ странства (одно-, двух-, трех-) и эквива¬ лентны друг другу, а также полностью оп¬ ределяют логическую функцию У = x1 x2 x3 v x1 x2 x3 v x1 x2 x3 v x1 x2 x3.

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

В общем случае м о ж н о утверждать, что покрытие (определение термина «покрытие» приведем ниже) «объема» цифрового множества Л Ф, располо¬ женного в многомерном цифровом пространстве, определяет все возможные варианты построения Л Ф. Здесь следует напомнить, что число таких логиче¬ ских функций в научно-технической литературе известно, но подсчет их числа осуществляется только путем просмотра (или, как говорят, «перебора»). П р и этом утверждается, что «уже при сравнительно небольших значениях K ( K 6) перебор становится практически невозможным даже с использованием вычис¬ лительной техники» [25].

Использование геометрического образа логических функций позволяет по¬ лучить т о ч н ы й ответ: это число определяется суммой всех возможных сочета¬ К ний из 2 элементов цифрового множества соответственно по нулю (во мно­ жестве нет логических единиц - пустое множество 0), по 1 (во множестве со¬ держится одна логическая единица), по 2 (в множестве содержится по две ло¬ К К гических единицы) и т.д. вплоть до сочетания из 2 по 2 (в множестве все элементы равны логической единице - универсальное множество Е).


Отмеченное записывается следующим образом:

(1.1.1) В формуле (1.1.1) первое и последнее слагаемые определяют соответственно пустое и универсальное множества, сумма которых, как очевидно, равна двум.

Следует отметить, что значения Л Ф могут быть представлены не н а всех К 2 в о з м о ж н ы х наборах значений аргументов, и тогда н а некоторых из н и х о н и не определены. Названия т а к и х Л Ф и и х «объемов» - неполностью определен¬ н ы е или частичные.

x A' i= АЦОД} а) !

А={0,...,15} б) Рис. 1.4 (начало) A А A в) г) ж) Рис. 1.4 (продолжение) Для более четкого представления многомерного цифрового пространства, использующего декартову систему координат, на рис. 1.4, а изображено двена­ дцатимерное цифровое пространство, где каждый разряд имеет основание сис­ т е м ы счисления 2 (цифры 0, 1), а на рис. 1.4, б - эквивалентное ему трехмерное цифровое множество, где каждый разряд имеет основание системы счисления 16 (цифры 00,..., 15), которые могут быть, в свою очередь, закодированы раз¬ личными способами, например четырьмя разрядами двоичного кода.

Таким образом, для геометрического представления Л Ф может быть вы­ брано цифровое пространство мерности от 1 до K, где все пространство упако K вывается элементарными фигурами от 0 до (2 - 1) (нумерованное цифровое K пространство). Объединение всех этих 2 элементарных фигур представляет собой универсальное цифровое множество E, в к л ю ч а ю щ е е все возможные на­ боры значений K аргументов. Выделение в универсальном множестве E под¬ множеств элементарных фигур, соответствующих наборам аргументов, при которых Л Ф y = f (x... x ) равна 1*, образует ее геометрический образ.

1;

;

K В качестве измерения мерности пространства нами выбрано число разря¬ дов соответствующего основания системы счисления, из которых может быть K составлено любое действительное натуральное число N, нумерующее 2 на боров аргументов Л Ф. Поэтому геометрический образ многомерного цифрово¬ го пространства должен обладать аналогично цифрам разряда свойством замк¬ нутости этих цифр на себя. Представить физическое существование одномер¬ ного либо двухмерного цифрового пространства, где цифры разрядов, опреде¬ л я ю щ и х мерность пространства, замкнуты на себя, не сложно. Для одномер¬ ного цифрового пространства, «склеивая» между собой свободную грань эле¬ ментарного кубика, соответствующего цифре 0 и перпендикулярного свобод¬ ной гранью к цифровой оси, со свободной гранью такого ж е кубика, соответ¬ K ствующего цифре (2 - 1) и также перпендикулярного свободной гранью к цифровой о с и, получим « п о л ы й » тор. Проводя аналогичные «склеивания»

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

Таким путем может быть получено достаточно сложное тороидальное многомерное цифровое пространство.

Однако здесь необходимо остановиться и сделать следующее замечание.

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

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

П р и сдвиге этой фигуры, которая, как м ы условились ранее, является гео¬ метрическим образом ЛФ, вдоль координаты A 1 на одну цифру (см. рис. 1.4, г) в большую сторону она появится одной своей половинкой в начале координа¬ т ы A. Аналогичные положения займет эта фигура при сдвиге на одну цифру относительно координат A и A (см. рис. 1.4, д, е).

2 О д н о в р е м е н н ы й сдвиг этой фигуры, например, по всем трем координатам A1, A 2, A3 (см. рис. 1.4, ж), приведет к тому, что она будет присутствовать своими частями в начале и конце всех трех координат.

Здесь следует помнить, что исходная геометрическая фигура (см. рис. 1.4, а) при л ю б о м сдвиге её вдоль координат преобразуется в аналогичные образы (см.

рис. 1.4, г - ж ), которые все эквивалентны между собой, т.е. всегда сохраняют свою форму (не дробятся и не объединяются в более крупные образования) и всегда при этом находятся внутри многомерного цифрового пространства.

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

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

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

У ж е в начале изложения основ теории многомерных цифровых множеств, где размещаются геометрические образы логических функций, сделаны два серьёзных вывода. Эти выводы, по нашему мнению, не могли быть получены, исходя из чисто аналитических логических рассуждений. Это полностью под¬ тверждает высказывание Ф. Клейна (F.C. Klein), критикующего чисто фор¬ мальную т е о р и ю чисел: «Попытка совершенно изгнать созерцание и удержать только логическое исследование представляется мне в полной мере неосуще¬ ствимой. Н е к о т о р ы й остаток, некоторый минимум интуиции всегда должен сохраниться...». И далее: «...совершенно невозможно чисто логическим путем показать, что законы, в которых м ы обнаружили отсутствие логического про¬ тиворечия, действительно имеют силу по о т н о ш е н и ю к числам, столь х о р о ш о нам известным эмпирически, что неопределенные объекты могут быть ото¬ ждествлены с реальными числами, а выкладки, которые м ы над ними произво¬ дим, - с реальными эмпирическими процессами» [16].

1.2. Позиционные системы счисления Позиционные системы счисления занимают основную, главную роль во всей математике, и их использование при двоичном принципе кодирования ос¬ нований имеет в машинной арифметике также всеобщий характер. Тем не менее использование двоичного кодирования не может определить все возможные ва¬ рианты кодирования оснований систем счисления. Нетрудно показать, что чис¬ K K ло кодов, эквивалентных сигналам О Ц К от 0 до (2 - 1), равно 2 !.

K В самом деле, каждой цифре от 0 до (2 - 1) основания системы счисления K 2 сопоставляется его код - слово из алфавита {x, x, x }. П р и двоичном 1 2 k неизбыточном законе кодирования, например для К = 3, это будут следующие слова (кодовые комбинации): 0 о x x x, 1 О x x x, • •, 7 О x x x. Здесь 1 2 3 1 2 3 1 2 K ц и ф р ы 0,..., (2 - 1) и конъюнкции К-го ранга находятся во взаимно одно¬ значном соответствии, что определяется постановкой между н и м и соответст¬ вующего знака ( о ). Другие взаимно однозначные соответствия могут быть получены перестановкой конъюнкций К-го ранга.

K Обозначим конъюнкции K-го ранга простыми цифрами 0,..., ( 2 - 1), сов¬ п а д а ю щ и м и с двоичным принципом кодирования. Тогда взаимно однозначные соответствия двоичного принципа кодирования представятся записью: 0 О 0, 1 О 1, 2 О 2, 3 О 3, 4 О 4, 5 О 5, 6 О 6, 7 О 7, а другой вариант кодирова­ ния будет представлен, например, иной записью соответствия: 0 О 0, 1 О 2, 2 О 1, 3 О 3, 4 О 4, 5 О 5, 6 О 6, 7 О 7 и т.д.

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

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

( 0 1) ( 1 0).

n =2 (1.2.1) Для основания n=3 число различных перестановок представляется также весьма просто матрицей размерами 3 х ( 0 1 2) ( 0 2 1) ( 1 0 2) ( 1 2 0) ( 2 1 0) ( 2 0 1) n=3 (1.2.2) В (1.2.2) содержится шесть перестановок, а дальнейшее представление принципов кодирования оснований n = 4, 5, 6,... может быть сформулировано с л е д у ю щ и м правилом.

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

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

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

Тогда следующая матрица размерами 4 х 6 определяет все коды основания n = 4:

( 0 1 2 3) ( 0 2 1 3) ( 0 3 2 1) ( 0 1 3 2) ( 0 2 3 1) ( 0 3 1 2) ( 1 0 2 3) ( 1 2 0 3) ( 1 3 2 0) ( 1 0 3 2) ( 1 2 3 0) ( 1 3 0 2) ( 2 3 0 1) ( 2 1 3 0) ( 2 1 0 3) ( 2 0 1 3) ( 2 0 3 1) ( 2 3 1 0) ( 3 0 1 2) ( 3 2 0 1) ( 3 2 1 0) ( 3 1 2 0) ( 3 1 0 2) ( 3 0 2 1) n=4 (1.2.3) и т. д.

Для неизбыточных кодов, где основание системы счисления кратно двум к n = 2, матрицы перестановок непосредственно определяют все т и п ы возмож­ ных кодов. Если первая перестановка и ее цифровые эквиваленты от 0 до K (2 - 1) соответствуют кодовым комбинациям двоичного принципа кодирова¬ ния, то все остальные перестановки этих цифр дают только порядок располо¬ жения этих кодовых комбинаций в других принципах кодирования, а эквива¬ лентные и м сигналы О Ц К д о л ж н ы также располагаться в последовательности K от 0 до (2 - 1).

П р и н и м а я для л ю б ы х типов кодов неизменность кодового слова для циф¬ р ы 0, равенство нулю всех сигналов кода, число кодов для основания n уменьшается до значения (n - 1)!, а с учетом необходимости иметь каждому коду его обратный код число кодов равно 2[(n - 1)!]. Так, для основания n = число прямых кодов будет определяться первой строкой матрицы (1.2.3).

К р о м е понятия «нулевых» кодов введем понятие «дружественных» кодов, в которых, дополнительно к постоянству кодовой комбинации сигналов циф¬ р ы 0, устанавливается такое ж е постоянство комбинации сигналов для ц и ф р ы (n - 1) - равенство их всех логической единице. Число «дружественных» ко¬ дов равно (n - 2)!.

Число эквивалентных кодов S, т.е. кодов одинаковой структуры, опреде¬ K ляет число классов неизбыточного кода мерности K. Очевидно, что число классов неизбыточного кода мерности K равно n!/ SK.

Число «дружественных» кодов каждого класса определяется числом пере¬ становок K аргументов кода, в образовании которых будем также придержи¬ ваться представленного выше порядка.

к Для избыточных кодов n 2 их общее число кодов определяется зависи­ n мостью C x(n!), а с учетом равенства нулю всех сигналов кода, эквивалент¬ 2K ных цифре 0 основания системы счисления, число кодов уменьшается до ве¬ (n-1) л и ч и н ы 2 C ( ) X [ ( n - 1)!]. Ч и с л о избыточных кодов огромно и не поддает¬ 2K- ся счету.

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

л ы х чисел, а последние, в свою очередь, - подмножеством множества всех ра¬ циональных чисел.

Известно [14], что «множества, встречающиеся в рассуждениях той или иной математической теории, являются подмножествами некоторого фиксиро¬ ванного множества E, называемого универсальным для данной теории». Уни¬ версальным для нашего случая является множество, где во всех ячейках мно¬ гомерного цифрового пространства расположены логические единицы 1*.

М н о ж е с т в а A и B называются равными, A = B, если они состоят из одних и тех ж е элементов на всех ступенях иерархии.

Е с л и все элементы множества A являются также элементами множества B, то A - подмножество B, или A включается в B, что обозначается как A c B.

Е с л и A с B, причем A Ф B, то записывается A a B. Знак а в, отличие от знака с, называется знаком строгого включения.

Для любого множества A выполняется включение 0 a A, A a A (реф лексность).

М н о ж е с т в а A и 0 называются несобственными подмножествами множест¬ ва A, а все остальные подмножества A - его собственные подмножества.

Е с л и A с B и B с C, то A с C (транзитивность).

Е с л и в качестве э л е м е н т о в м н о ж е с т в а и с п о л ь з у ю т с я д р у г и е м н о ж е с т в а, ;

;

н а п р и м е р A = {A, A, A }, то это с е м е й с т в о м н о ж е с т в { A | i е I}, где ;

A - некоторое множество, например, i-го разряда натурального числа A, а I - множество индексов, которое может быть конечным или бесконечным.

Очевидно, что множества, состоящие из конечного числа элементов, назы¬ ваются конечными;

в противном случае говорят о бесконечных множествах.

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

Говорят, что «элементы множеств А и В находятся во взаимно однозначном соответствии, если каждому элементу a множества А сопоставлен по некоторому закону единственный элемент в множестве В, причем каждый элемент Ь е В ока­ зывается сопоставленным одному и только одному элементу a еА». Взаимно однозначное соответствие элементов множеств А и В обозначается как a - b.

Множества А и В называются эквивалентными или равномощными (А ~ В), если можно установить взаимно однозначное соответствие их элементов. Это определение распространяется на конечные и бесконечные множества. Очевид¬ но, что конечные множества А и В эквивалентны лишь тогда, когда они содер¬ жат одинаковое число элементов. Причем если А ~ В', где В ' а В, то множество А содержит меньше элементов, чем множество В. Таким образом, понятие чис¬ ла элементов множества эквивалентно понятию мощности множества.

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

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

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

Для бесконечных множеств можно также задать вопрос: нельзя ли «беско¬ нечность» одного множества считать большей, равной или меньшей, чем «бес¬ конечность» другого множества? Здесь ответ заключается в понятии одинако¬ вой мощности этих множеств, если между их элементами м о ж н о установить взаимно однозначное соответствие, т. е. если одно множество м о ж н о также отобразить на другое, что каждому элементу первого взаимно однозначно со¬ ответствует некоторый элемент второго. Е с л и ж е подобное отображение не¬ осуществимо, то множества имеют различную мощность;

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

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

Фиксированное множество Е, определяющее все многомерное цифровое пространство, где множества А, В,... являются его подмножествами, как уже отмечалось выше, называется универсальным.

К а ж д о м у подмножеству A с Е сопоставим функцию y такую, что y = 1*, a a если подмножество A не пустое (A Ф 0 ), и y = 0*, если A =0. Тем самым a достигается полное соответствие: между операцией объединения и и логиче­ ским сложением v, между операцией пересечения п и логическим умножени­ ем &, между операцией дополнения А Е и логической операцией отрицания А.

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

Классической постановкой задачи определения покрытия «длины», «пло¬ щади», «объема» цифровых множеств является поиск нормальной минималь¬ ной дизъюнктивной ф о р м ы (ДНФ), когда лучшей считается логическая схема, соответствующая этой Д Н Ф и з а н и м а ю щ а я меньшую п л о щ а д ь кристалла большой интегральной схемы (БИС). Представленный критерий оптимизации в тесном сочетании с технологическими требованиями регулярности структу¬ р ы Б И С привел к отображению на плоскости либо объеме кристалла Д Н Ф ло гической функции или системы функций в виде матричных схем, которые по­ лучили название программируемых логических матриц (ПЛМ), а также других микросхем программируемой матричной логики (ПМЛ).

Предлагаемая теория многомерных ц и ф р о в ы х множеств является инстру­ ментом, наилучшим образом ориентированным на автоматизацию синтеза та­ ких Б И С, когда конструкция каждой из них имеет не только аналитическую запись в Д Н Ф, но и физический геометрический образ цифрового множества многомерного цифрового пространства.

Это есть стремление к наглядности, которая, по мнению Д. Гилберта, «стремится к живому п о н и м а н и ю объектов и их внутренних соотношений».

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



Pages:   || 2 | 3 | 4 | 5 |   ...   | 9 |
 





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

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