О глубине и площади клеточных схем

• Автор: Жуков, Дмитрий Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 77 с. : ил.

Глава 1 &-ичные (п, 2)-преобразователи
1.1 Схемы из функциональных элементов
1.2 Клеточные схемы
Глава 2 Оценки общего типа
2.1 Клеточные схемы для частичных функций
2.2 Моделирование СФЭ клеточными схемами
2.3 Нижние оценки площади в классе Т-схем
Глава 3 Клеточные схемы для арифметических операций
3.1 Префиксные клеточные схемы
3.2 Клеточные схемы для сложения
3.3 Клеточные схемы для вычитания
3.4 Клеточные схемы для умножения
3.5 Клеточные схемы для деления
Литература

Результаты диссертации относятся к математической теории синтеза и сложности управляющих систем [35]. Предметом исследования являются схемы из клеточных элементов (СКЭ, клеточные схемы) [9, 30] и схемы из функциональных элементов (СФЭ) [12, 34]. В диссертации изучаются площадь и глубина клеточных схем для всюду определённых и частичных булевых функций, а также схем, реализующих основные арифметические операции.

•ху
Определения и обозначения
Сложность Т(5) и глубина б?(5) схемы из функциональных элементов 5, как обычно, понимаются как число элементов в схеме и число элементов в самой длинной ориентированной цепи между её входами и выходами [12, 34]. Сведения о глубине и сложности арифметических схем из функциональных элементов можно найти, например, в [22, 32, 59].
Формальное определение схем из клеточных элементов было дано в работе [9]. Затем клеточные схемы были рассмотрены в [1, 29, 30]. Клеточная схема имеет вид прямоугольника на плоскости, составленного из клеточных элементов. Мы будем называть схему правильной, если все её входы и выходы расположены по краям. Везде далее клеточные схемы предполагаются правильными. Будем считать, что длина клеточной схемы измеряется по горизонтали, а ширина — по вертикали. Длину схемы 5 обозначим Д5), а ширину — /г(5'). Тогда площадь Л(5) схемы 5 равна произведению 2(5) х Л(5).
Напомним основные определения [9]. Клеточный элемент имеет вид единичного квадрата. На его сторонах расположены входы

и выходы — не более одного на каждой стороне. Клеточный элемент называется функциональным, если он реализует нетождественную функцию, и коммутационным, если он реализует тождественные функции. Кроме функциональных и коммутационных элементов имеется изолирующий клеточный элемент без входов и выходов. В работах [1, 9, 29, 30] исследовались схемы, построенные из двоичных клеточных элементов в базисе {&, V, } (рис. 1). Будем обозначать этот базис Б&)У,- • В последней главе будут также рассмотрены клеточные схемы, реализующие функции Лг-значной логики. Используемые при их построении Ачичные элементы изображены на рис. 2. В верхнем ряду приведены изолирующий элемент и четыре функциональных элемента (реализующие константу с, одноместную функцию д є Р* и двуместную функцию / Є Р*). В нижнем ряду изображены коммутационные элементы. Будем обозначать этот базис Б*. При построении схемы допускаются повороты клеточных элементов на углы, кратные |. Чтобы подчеркнуть, что в базис Б* входят элементы, реализующие функции Д /т, будем писать Базис Б&)У,- > дополненный функциональными элементами со входами на соседних сторонах (рис. 2, справа в верхнем ряду), реализующими функции двух переменных /ь • ■ • , /т ИЗ Рг, обозначим }т-

9{х)

9І*)
’9 (®)

Л®,у)

1(х,у)

:Н=р *-еЬ
■X X

Прямоугольник, составленный из клеточных элементов, будем называть клеточной схемой в том и только том случае, когда при замене клеточных функциональных элементов на соответствующие им обычные функциональные и при их соединении, определяемом коммутационными элементами, получается некоторая структура, удовлетворяющая обычному определению СФЭ. Так всякой клеточной
верхней стороной области Б ячейки (г,г), п + 1 ^ і ^ п + Ь и (г,п), 1 < г ^ п. Таким образом, на выходах верхней и правой сторон области О реализуются все функции, реализуемые её диагональными элементами.
Построенная система ячеек обладает ещё одним свойством: в силу выбора нумерации функциональных элементов, на одной горизонтали левее каждого элемента //, 1 ^ і ^ Ь находятся коммутационные элементы, реализующие все переменные и выходы других функциональных элементов, которые могут подаваться на его вход. То же самое можно сказать об элементах, лежащих ниже элемента /,; на одной вертикали с ним.
Воспользуемся этим наблюдением. Пусть в схеме 5 входы двуместного функционального элемента /, соединены с некоторыми вершинами а и Ь, где а, Ь Є {*ь ■. ■, ®п,/х, ■ ■ ■,Этим вершинам соответствуют диагональные ячейки а' и У из области Б. с координатами (к, к) и (1,1) соответственно. Без ограничения общности можно считать, что к ^ I < п + і. По построению коммутационные элементы (к, п + г) и (п + і, I) реализуют те же функции, что и элементы в ячейках а1 и У. Соединим коммутационный элемент (к, п+і) горизонтальным проводником 71 с ячейкой (п + г,п + г), в которой расположен функциональный элемент //. Соединим элемент (п+г, I) с ячейкой (п + і,п + і) вертикальным проводником 72. Ясно, что проводники 7і и 72 пересекают другие проводники только под прямым углом. Все коммутационные элементы в точках пересечения заменим мостами. Это не нарушит никаких цепей в Б. Аналогично поступим, если элемент /і реализует одноместную функцию.
Проделаем эту процедуру для всех г, 1 ^ і ^ Ь. В итоге получим структуру из клеточных элементов Б которая является вложением схемы А в прямоугольную решётку, а значит, реализует тот же оператор. К тому же по построению схема Б' — правильная. Очевидно, она обладает всеми заявленными в утверждении свойствами. Теорема 5 доказана. □
Замечание 1. В доказательстве теоремы 5 не использовалась двоичность оператора Б, а учитывалось только то, что все функциональные элементы схемы Б имеют не более двух входов. Отметим, что хотя эта теорема не будет далее применяться к к-ичным операторам, она справедлива и для них. Также отметим, что она справедлива и для не всюду определённых операторов.