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

Информатика. 8 класс

Система счисления – это совокупность правил для записи чисел.

Цифры – знаки, c помощью которых записываются числа.

Алфавит – множество всех цифр, используемых для записи чисел.

Система счисления называется позиционной, если количественный эквивалент цифры зависит от её положения (позиции) в записи числа.

Основание позиционной системы счисления равно количеству цифр, составляющих её алфавит.

Основанием позиционной системы счисления может служить любое натуральное число q > 1.

Алфавит десятичной системы состоит из десяти цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

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

Сегодня мы познакомимся с двоичной системой счисления – позиционной системой счисления с основанием 2. Для записи чисел в двоичной системе счисления используются только две цифры: 0 и 1.

Рассмотрим перевод целых чисел, представленных в двоичном коде, в десятичную систему счисления.

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

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

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

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

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

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

Арифметические операции в двоичной системе счисления осуществляются по тем же правилам, что и в десятичной системе счисления.

Рассмотрим операцию сложения.

В двоичной системе счисления один плюс один – это один-ноль, поэтому ноль остается в младшем разряде, а единица переносится в старший разряд.

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

Посмотрите, как происходит двоичное вычитание. При вычитании из нуля единицы занимаем единицу в старшем разряде.

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

Этих знаний и умений достаточно, чтобы объяснить секрет чудесной таблицы.

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

В строке I записаны все числа, в двоичном изображении которых есть единицы первого разряда (1); в строке II записаны все числа, у которых есть единицы второго разряда (2); в строке III — числа, имеющие единицы третьего разряда (4), и в строке IV — числа, имеющие единицу четвертого разряда (8).

Если задуманное вами число есть, например, только в строках IV и II, то оно может быть представлено суммой 8 и 2. Следовательно, это 10.

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

Вся компьютерная техника построена на использовании двоичных кодов: с их помощью представляют, хранят, обрабатывают и передают по компьютерным сетям самые разные виды информации!

Источник

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

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

Содержание

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

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

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

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

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

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

↑Схемная реализация булевых функций

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

↑Двоичная позиционная система записи целых чисел

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

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

Схемы для арифметических операций над многоразрядными двоичными числами. Сложение двух n-разрядных двоичных чисел (x_n,….,x₁)₂ и (y_n,….,y₁)₂ как и в десятичной системе приводит к появлению переносов в следующий разряд, которые необходимо учитывать в вычислении. Эти переносы также равны нулю или единице (если перенос равен нулю, то в ручном вычислении он фактически не выполняется, но логическая схема обязана правильно работать и в этом случае, ведь она «не знает», какой перенос пришел из предыдущего разряда). Обозначим перенос из (i-1)-го разряда в следующий i-й разряд через w_i (w₁=0, потому что предыдущего разряда в этом случае просто нет). Тогда для вычисления z_i (i-го бита результата) нужно сложить биты x_i и y_i и бит переноса w_i. Это сложение выполняем по формулам

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

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

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

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

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

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

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

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

Источник

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

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

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

Таблица умножения ещё проще. Здесь нужно твёрдо знать, что любое число, умноженное на нуль, есть нуль и что умножение на единицу не меняет числа.

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

Вычитание в двоичной системе выполняется по таким правилам:

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

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

Примеры. Выполнить умножение и деление:

Источник

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

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

Содержание

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

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

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

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

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

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

↑Схемная реализация булевых функций

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

↑Двоичная позиционная система записи целых чисел

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

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

Схемы для арифметических операций над многоразрядными двоичными числами. Сложение двух n-разрядных двоичных чисел (x_n,….,x₁)₂ и (y_n,….,y₁)₂ как и в десятичной системе приводит к появлению переносов в следующий разряд, которые необходимо учитывать в вычислении. Эти переносы также равны нулю или единице (если перенос равен нулю, то в ручном вычислении он фактически не выполняется, но логическая схема обязана правильно работать и в этом случае, ведь она «не знает», какой перенос пришел из предыдущего разряда). Обозначим перенос из (i-1)-го разряда в следующий i-й разряд через w_i (w₁=0, потому что предыдущего разряда в этом случае просто нет). Тогда для вычисления z_i (i-го бита результата) нужно сложить биты x_i и y_i и бит переноса w_i. Это сложение выполняем по формулам

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

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

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

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

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

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

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

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

Источник