Зарегистрироваться

Двоичная арифметика

Категории Дискретная математика | Под редакцией сообщества: Математика

Эта версия статьи от 09 Декабрь 2010 18:27, редактировал Гашков Сергей Борисович
Список всех версий Перейти к списку версий
Перейти к последней версии

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

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

Таким образом,  с определенной точки зрения, все цифровые устройства  генерируют потоки целых чисел,  по некоторым правилам их преобразуют, обрабатывают, кодируют, декодируют и т.д.,  и передают другим цифровым устройствам.  Область  науки и техники, которая  занимается изучением подобных процессов, называется цифровой обработкой сигналов (английская аббревиатура DSP – Digital Signal Processing). 

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

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

 

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

 

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

 

            Двоичная позиционная система записи целых чисел. Произвольное натуральное число можно единственным способом представить в виде суммы степеней двойки, например 23 = 16+4+2+1. Обозначая входящие в эту сумму степени двойки единицами, а не входящие в ее степени нулями, можно кратко обозначить эту сумму булевым набором (в другой терминологии - вектором)  (10111)2. Индекс 2 напоминает о том, что число записано в двоичной системе. Единица, стоящая в младшем (самом левом) разряде,  означает слагаемое 1, единица во втором слева разряде означает слагаемое 2, единица в третьем разряде означает 4, а нуль в четвертом разряде означает отсутствие слагаемого 8, единица в четвертом (старшем) разряде означает присутствие слагаемого 16 (в большинстве случаев разумно рассматривать только такие записи чисел в двоичной системе, в которых в старшем разряде стоит единица).

Главное достоинство двоичной системы (помимо естественности ее применения в электронной цифровой технике ) – исключительная простота алгоритмов арифметических операций в ней. Таблица умножения в двоичной системе совсем не требует запоминания: любое число, умноженное на нуль дает нуль, а умноженное на единицу равно самому себе. Правило деления сводится к двум равенствам 0/1 = 0, 1/1 =1, благодаря чему деление столбиком в двоичной системе делается проще, чем в десятичной, и по существу сводится к многократному вычитанию. Таблица сложения в двоичной системе чуть сложнее таблицы умножения (в отличие от десятичной системы), так как 1+1 = (10)2 и возникает перенос в следующий разряд.

Правило сложения двух битов в двоичной системе задается формулами x+y = 2v+u, v = x&y, u = xÅy. В силу симметрии для их проверки достаточно рассмотреть не четыре, а три случая: 0+0 = (00)2, 1+0=0+1= (01)2, 1+1 = (10)2. Схема, выполняющая это сложение, называется полусумматором (в англоязычной литературе: half adder) и обозначается обычно HA или FA2. Эта схема (в базисе {AND, XOR})  изображена на рисунке.

 

                   Схемы для арифметических операций над многоразрядными двоичными числами.     Сложение двух n-разрядных двоичных чисел (xn,….,x1)2 и  (yn,….,y1)2 как и в десятичной системе приводит к появлению переносов в следующий разряд, которые необходимо учитывать в вычислении. Эти переносы также равны нулю или единице (если перенос равен нулю, то в ручном вычислении он фактически не выполняется, но логическая схема обязана правильно работать и в этом случае, ведь она «не знает», какой перенос пришел из предыдущего разряда). Обозначим перенос из  (i-1)-го разряда в  следующий i-й разряд через  wi (w1=0, потому что предыдущего разряда в этом случае просто нет). Тогда для вычисления zi (i-го бита результата) нужно сложить биты xi и yi и бит переноса wi. Это сложение выполняем по формулам  

xi + yi +wi= 2vi +ui, vi=m(xi ,yi ,wi), ui=l(xi ,yi ,wi)

с помощью схемы FA3. Тогда zi=ui=l(xi ,yi ,wi), а следующий бит переноса wi+1 = vi=m(xi ,yi ,wi). При сложении n-разрядных чисел получается вообще говоря n+1-разрядное число. Его старший бит zn+1= wn+1 равен последнему переносу.

 Схема сложения трехразрядных чисел приведена на следующем рисунке. Аналогичным образом выглядит и схема сложения n-разрядных чисел.

Сложность указанного n-разрядного сумматора равна 5n-3.  Н.П.Редькин доказал, что сумматоров для n-разрядных чисел меньшей сложности в базисе {AND,OR,XOR,NOT} не существует. Построенный сумматор  является поэтому минимальной схемой.  Но у этой схемы есть существенный недостаток – она имеет большую глубину. Глубиной схемы называется максимальное число ее элементов, образующих цепь, соединяющую какой-либо из входов схемы с одним из ее выходов.  Например, глубина указанной выше схемы FA3 равна 3.

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

Теоретически вычислить задержку реальной схемы очень сложно. Цепей элементов схемы, соединяющих ее входы с выходами (эти цепи также  называют путями), обычно довольно много и задержка схемы определяется задержкой по самому плохому в определенном смысле пути, который называется критическим. Например, на схеме FA3 критический путь, вероятно, соединяет входы X или Y с выходом m.  Задержка по любому  пути определяется не только суммой задержек всех элементов, лежащих на этом пути (в приведенном примере она равна 3, если считать задержку каждого элемента единичной).  Следует учитывать также задержку соединяющих эти элементы проводов. Задержка элемента зависит от того, между каким его входом и каким его выходом она измеряется, а также от электрических характеристик самого элемента и элементов непосредственно с ним связанных в рассматриваемой схеме, она зависит от температуры схемы и даже  от того, какие логические значения подаются в рассматриваемый момент на входы этого элемента и изменяется ли (и в какую сторону) значение на его выходе. Тем не менее, хотя и не очень точно, задержку пути можно оценить как сумму задержек его элементов. Если задержки всех элементов равны, то эта величина определяется глубиной схемы. Разумеется,  понятие глубины схемы можно расширить, допустив, что элементы базиса могут иметь произвольные неотрицательные задержки.

  Глубина указанной выше схемы n-разрядного сумматора на первый взгляд равна 3n-2. Но внимательный анализ возможных критических путей показывает, что она на самом деле равна 2n-1. Все равно это очень много и построенная таким образом реальная схема будет иметь большую задержку. На практике используются схемы, имеющие одновременно малую сложность, не превосходящую Cn (где С – небольшая константа) и малую глубину, приблизительно равную 2log2 n. В.М. Храпченко в 1970 г. построил схему малой сложности и глубины, асимптотически равной log2n (т.е. равную (1+ e(n)) log2n, где e(n) стремится к нулю с ростом n). Он же недавно доказал, что глубина сумматора не может быть меньше log2n + log2n (log2 (log2n))). Поэтому построенная им схема имеет асимптотически минимальную глубину. Однако схема Храпченко превосходит обычные схемы только при n порядка тысячи. Тем не менее существует некоторая модификация его схемы с глубиной приблизительно равной logjn, где j = (Ö5+1)/2, и эта схема имеет глубину меньшую, чем стандартные схемы, уже начиная с n = 8. В 2008 г. М.И.Гринчук построил схему глубины  не большей log2n+log2(log2n)+6, которая уже при малых n имеет меньшую глубину, чем все известные схемы.

Задача построения оптимальных схем для умножения n-разрядных чисел оказалась еще труднее, чем задача о построении оптимальных сумматоров. Легко построить схему для умножения  n-разрядных чисел в базисе {OR,AND,XOR,NOT} сложности приблизительно равной 6n2. Для этого можно использовать указанную выше схему для сумматора. Однако ее глубина будет велика. В начале 60-х годов несколько исследователей (в СССР Столяров и Офман, в США Авиценис и Уоллес) независимо построили схему для умножения сложности порядка n2 и глубины порядка log2n. В смысле глубины эти схемы по порядку оптимальны, но до сих пор остается нерешенной задача построения схемы для умножения асимптотически минимальной глубины. В смысле сложности эти схемы оказались далеки от оптимальных. А. А. Карацуба построил в 1962 г. схему для умножения, имеющую сложность по порядку не большую n1,6, потом А. Л. Тоом построил схему сложности n1+e(n), где e(n) стремится к нулю с ростом n. В определенном смысле этот результат окончательный, тем не менее он был уточнен на рубеже 70-х годов немецкими математиками А. Шенхаге и Ф. Штрассеном, которые получили для схем умножения верхнюю оценку сложности  по порядку не превосходящую  n log2 n log2(log2 n), а в 2008 г. эту оценку улучшил американский математик М. Фюрер, заменивший двойной логарифм крайне медленно растущей функцией.  Есть предположение, что сложность  схемы умножения по порядку не меньше n log2 n, но и это не доказано.

Американский математик С.Кук доказал, что можно построить схему для деления 2n-разрядного числа на n-разрядное, у которой сложность по порядку не превосходит сложности умножения n-разрядных чисел. Известно также, что нижняя оценка сложности схемы для деления по порядку не меньше нижней оценки сложности умножения. Поэтому в смысле оценок сложности деление не представляет ничего нового в сравнении с умножением. Однако долгое время наилучшей оценкой глубины деления по порядку было (log2n)2. Впоследствии были найдены схемы для деления с глубиной по порядку равной  log2n, но их сложность оказалась велика.  Американцы Рейф и Тейт построили схемы для деления  глубины по порядку не превосходящей  log2n log2(log2n)  и одновременно сложности по порядку не превосходящей n log2n log2 log2n, однако и эти схемы, как и схемы Шенхаге-Штрассена и Фюрера пока не нашли практических применений, так как в действительности начинают превосходить используемые на практике схемы лишь при огромных значениях n.

 

Рекомендуемая литература

  1. О.Б. Лупанов << Асимптотические оценки сложности управляющих систем >> изд. МГУ, 1984.
  2. О.Б. Лупанов <<Конспект лекций по математической логике >> изд. МГУ, 2009.
  3. Дж. Сэвидж <<Сложность вычислений >> М. изд. Факториал, 1998.
  4.  Д. Кнут << Искусство программирования на компьютере>>, т. 2, изд. Вильямс, 2000.
  5. С.Б. Гашков <<Системы счисления и их применения >>, М. изд. МЦНМО, 2004.
  6. С.Б. Гашков, В.Н. Чубариков <<Арифметика. Алгоритмы. Сложность вычислений >>, изд. Дрофа, 2005.

Эта статья еще не написана, но вы можете сделать это.