Что такое булева функция? Это функция, у которой несколько аргументов, принимающих значения 0 или 1, и сама функция тоже принимает значение 0 или 1. В каком-то смысле булевы функции — это самые простые функции, которые встречаются в математике. Они гораздо проще, чем, например, синус.
Что такое функциональные элементы, из которых построены микросхемы? Это устройства, которые имеют несколько — обычно два — входов и обычно один, а иногда несколько выходов. И входы, и выходы могут находиться в двух резко различимых состояниях, которые обозначаются, естественно, 0 и 1. Причем значение выхода однозначно определяется значениями входов. Тем самым каждый такой элемент реализует некоторую булеву функцию.
Надо, наверное, пояснить, что это за слово. Это слово появилось в честь английского математика XIX века Джорджа Буля. Но есть и синоним для булевых функций, который, наверное, лучше отражает суть дела, чем просто имя этого математика. Это функции алгебры логики. Потому что наука, которой впервые стал заниматься Джордж Буль, называлась алгебра логики. Он, конечно, понятия не имел, что все это будет потом применяться в компьютерах и микросхемах.
Элементы, из которых состоят микросхемы, реализуют на самом деле очень простые булевы функции, например конъюнкцию (конъюнкция — это всего-навсего умножение: ноль умножить на ноль — получим ноль; один на один — единица), дизъюнкцию. Дизъюнкцию иногда называют логическим сложением, но она от обычного сложения отличается тем, что один дизъюнкция один — это один, потому что двойка не появляется в определении булевых функций. Есть еще элементы, которые называют «сложение по модулю два». Они отличаются от дизъюнкции тем, что один плюс один равно нулю.
Эти элементы можно друг с другом комбинировать, то есть выходы каких-то элементов присоединять ко входам. Главное, чтобы не образовывались циклы, которые будут приводить к тому, что схема будет работать неустойчиво. То есть если выход какого-то элемента присоединится ко входам другого, он, в свою очередь, еще к какому-то и в конце концов последний элемент присоединится ко входу первого и образуется цикл, то совершенно невозможно будет понять, как работает схема. Работать она будет, но неустойчиво. Такие циклы в чисто логических схемах избегаются. А в конечноавтоматных схемах они могут присутствовать и даже обязательно есть.
В связи с необходимостью конструирования таких схем возникла такая математическая задача. Вот дана произвольная булева функция от n переменных, и дан набор элементарных операций, которые можно использовать для ее вычисления, другими словами, для построения логической схемы, которая будет реализовывать эту функцию. Схема реализует функцию — это означает, что выход этой схемы зависит от ее входов в точности так же, как это предписывается этой функцией. И под сложностью этой функции естественно понимать число элементов, из которых построена эта схема.
В реальности любая микросхема так или иначе реализует какую-то булеву функцию или систему булевых функций, если речь идет о так называемых комбинационных схемах, которые не содержат элементов памяти, то есть триггеров или флипфлопов (flip-flop), как их называют англоязычные инженеры. А автоматные схемы с триггерами и флипфлопами устроены так, что значительную их часть занимает как раз комбинационная схема. И в связи с необходимостью конструирования таких схем возникла задача, которая, собственно, и привела к созданию теории сложности булевых функций. Ее основателем был знаменитый американский математик и инженер Клод Шеннон. Он, правда, реализовывал булевы функции не схемами из функциональных элементов, а так называемыми контактными схемами. В то время, в 30–40-е годы, вся техника как раз основывалась на этих контактных схемах, потому что современной электроники тогда еще не было. Но выяснилось, что методы построения этих схем довольно похожи на методы построения схем из функциональных элементов. И дальнейшее развитие этой теории осуществил Олег Борисович Лупанов. Он, в частности, доказал, например, такой удивительный результат, что, во-первых, любую булеву функцию от n переменных можно построить схемой, в которой число элементов приблизительно равно 2n ÷ n. Точнее, он доказал, конечно, не приблизительно, а написал асимптотически точную формулу, в которой это выражение является главным членом. При этом он доказал, что почти для всех функций его метод построения схем дает асимптотически оптимальные схемы. Что значит почти для всех функций? Это значит, что если посчитать, сколько таких функций, для которых этот метод дает оптимальный результат, и поделить на общее число функций, то в пределе мы получим единицу.
Разумеется, есть небольшое количество функций, которые имеют гораздо меньшую сложность. Потому что теорема Лупанова говорит о том, что почти все функции имеют колоссальную сложность, асимптотически равную сложности самой сложной функции. Этот факт в какой-то степени отражает сложность нашего окружающего мира.
Но надо сказать, что те схемы, которые используют в современной электронике, конечно, реализуют не самые сложные функции, а какие-то конкретные, которые, естественно, нужны в электронике. И эти схемы имеют небольшую сложность, иначе не было бы никакой электроники. К числу этих схем относятся, например, схемы для сложения двух равноразрядных чисел, умножения двух равноразрядных чисел, схемы для деления с остатком тоже соответствующих чисел. Например, два n-разрядного на n-разрядное поделить — получается n-разрядное частное и n-разрядный остаток. Вот эти схемы содержатся в любом процессоре любого компьютера. Не только в процессорах компьютеров, но и в процессорах, управляющих различными электронными устройствами тоже. К счастью, сложность реализации таких схем гораздо меньше, чем 2n ÷ n. Например, для реализации схем умножения и деления обычным школьным методом, скажем n2. Но придуманы способы, как строить схемы гораздо меньшей сложности.
Первую такую схему приблизительно в 1962 году придумал аспирант механико-математического факультета Анатолий Карацуба. Сложность этой схемы для умножения n-разрядных чисел была приблизительно n в степени двоичный логарифм числа три. Почти через год была придумана лучшая схема, которая имела сложность приблизительно n1+ε, где эпсилон стремилась к нулю. Сложность оценки задавалась более запутанной формулой. Но выяснилось, что и это не предел, хотя, казалось бы, уже оценка типа 1+ε в показателе — улучшать ее уже некуда, потому что меньше единицы она быть уже не может. Но немецкие математики придумали схему сложности n умножить на логарифм n умножить на двойной логарифм n. А 40 лет спустя американский математик Мартин Фюрер придумал схему, у которой оценка сложности вместо двойного логарифма n содержала совсем медленно растущую функцию от n. Правда, выяснилось, что на практике эти схемы применять невозможно, потому что они превосходят схему Карацубы, начиная со многих тысяч или даже миллионов n. Понятно, что в компьютере мы умножаем только 32-разрядные и 64-разрядные числа. Но надо сказать, что схема Карацубы для умножения чисел в процессорах все-таки не применяется. Хотя, скажем, для умножения 64-разрядных чисел она уже дает чуть-чуть меньшую сложность. Но дело в том, что сложность схемы сейчас мало кого волнует: важно ее быстродействие. А это все зависит от глубины схемы, то есть, грубо говоря, от длины пути, по которому сигнал по схеме проходит от входа к выходу. То есть практическая задача, которая интересует инженеров, — это минимизация глубины.
Оказывается, и для сложения, и для умножения n-разрядных чисел можно предложить схемы, как говорят, логарифмической глубины, то есть у которых глубина по порядку равна логарифму n. Эти схемы работают очень быстро. Причем несложно доказать, что быстрее, чем логарифм n, они работать и вовсе не могут. То есть глубина меньше, чем логарифм n, быть не может. Правда, для умножения в этой оценке логарифм умножается на какое-то достаточно большое число, скажем на 4. А для сложения глубина асимптотически равна логарифму n. И такая замечательная схема была построена Валерием Михайловичем Храпченко приблизительно в 70-е годы.
К сожалению, оказалось, что схема Храпченко превосходит другие схемы с малой глубиной тоже начиная с n = 1000, но выяснилось, что у нее есть модификации, а точнее, даже упрощения, превосходящие стандартные схемы, которые обычно использовались, хотя асимптотически они и уступают.
Приблизительно в 2008 году Михаил Иванович Гринчук — бывший доцент кафедры дискретной математики мехмата, а ныне сотрудник фирмы Intel — придумал схему для сложения n-разрядных чисел, у которой глубина равна двоичному логарифму n прибавить двойной логарифм плюс небольшая константа типа шести. Вот эта схема уже при сравнительно небольших значениях n, порядка 20 или 30, является одной из лучших. А при больших n она дает асимптотически наилучший результат, такой же, какой уже был достигнут схемой Храпченко.
