что такое двоичная арифметика в информатике
Двоичная арифметика
Категории Дискретная математика | Под редакцией сообщества: Математика
Содержание
↑Двоичная арифметика
Двоичная арифметика – краткое наименование системы арифметических операций (включающей сложение, вычитание, умножение, деление, иногда некоторые другие операции) над двоичными числами, т.е. целыми числами, представленными в двоичной позиционной системе; собирательное название схемных решений для выполнения арифметических операций над двоичными числами – сумматоров, умножителей, схем вычитания, деления и другие.
В последнее время почти вся техника, связанная с передачей и обработкой информации, стала цифровой. Цифровыми стали аудио и видеомагнитофоны, превратившись в DVD-плейеры и Айподы, телевизоры, фотоаппараты, а многие виды электронно-вычислительной техники и современные мобильные телефоны были цифровыми изначально. Это означает, что информация, циркулирующая в этих устройствах, представляется (или, как говорят, кодируется) в цифровом виде, т.е. как правило, в виде строк (или последовательностей), состоящих из нулей и единиц. Этим строкам можно сопоставить по некоторым правилам целые числа, для чего обычно используется двоичная позиционная система их записи.
Таким образом, с определенной точки зрения, все цифровые устройства генерируют потоки целых чисел, по некоторым правилам их преобразуют, обрабатывают, кодируют, декодируют и т.д., и передают другим цифровым устройствам. Область науки и техники, которая занимается изучением подобных процессов, называется цифровой обработкой сигналов (английская аббревиатура DSP – Digital Signal Processing).
Существенную роль в этом играют алгоритмические процедуры, выполняющие арифметические и логические операции с различными типами числовых данных. Проектированием подобных алгоритмов и устройств, их реализующих, занимается компьютерная арифметика. Ее математической основой является теория сложности так называемых булевых функций (более длинно именуемых функциями алгебры логики).
В большей своей части компьютерная арифметика является двоичной арифметикой. Этому есть две причины. Во-первых, алгоритмы арифметических операций двоичной арифметики (т.е. арифметики, использующей двоичную позиционную систему) очень просты и являются в определенном смысле простейшими среди подобных алгоритмов для всех позиционных числовых систем. Во-вторых, дискретные (не аналоговые) электронные схемы, как самые современные, так и использовавшиеся много лет назад, имеют в определенном смысле двоичную природу и легко описываются на языке алгебры логики. Алгебра логики применяется как для моделирования функционирования этих схем, так и для их проектирования (синтеза).
↑Схемная реализация булевых функций
Из функциональных элементов строятся схемы, реализующие булевы функции. Неформально говоря, схема из функциональных элементов может быть построена путем произвольного соединения выходов некоторых элементов с входами других элементов так, чтобы различные выходы не присоединялись к одному и тому же входу и не возникали ориентированные циклы из элементов. Пример схемы из функциональных элементов приведен на рисунке ниже. Под сложностью схемы понимается число входящих в нее функциональных элементов. Подробнее см. статью « Сложность булевых функций».
↑Двоичная позиционная система записи целых чисел
Главное достоинство двоичной системы (помимо естественности ее применения в электронной цифровой технике ) – исключительная простота алгоритмов арифметических операций в ней. Таблица умножения в двоичной системе совсем не требует запоминания: любое число, умноженное на нуль дает нуль, а умноженное на единицу равно самому себе. Правило деления сводится к двум равенствам 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. Эта схема (в базисе
Схемы для арифметических операций над многоразрядными двоичными числами. Сложение двух n-разрядных двоичных чисел (xn,….,x1)2 и (yn,….,y1)2 как и в десятичной системе приводит к появлению переносов в следующий разряд, которые необходимо учитывать в вычислении. Эти переносы также равны нулю или единице (если перенос равен нулю, то в ручном вычислении он фактически не выполняется, но логическая схема обязана правильно работать и в этом случае, ведь она «не знает», какой перенос пришел из предыдущего разряда). Обозначим перенос из (i-1)-го разряда в следующий i-й разряд через wi (w1=0, потому что предыдущего разряда в этом случае просто нет). Тогда для вычисления zi (i-го бита результата) нужно сложить биты xi и yi и бит переноса wi. Это сложение выполняем по формулам
Схема сложения трехразрядных чисел приведена на следующем рисунке. Аналогичным образом выглядит и схема сложения n-разрядных чисел.
Сложность указанного n-разрядного сумматора равна 5n-3. Н.П.Редькин доказал, что сумматоров для n-разрядных чисел меньшей сложности в базисе
Глубина схемы – не менее важная характеристика схемы, чем ее сложность. Сложность логической схемы в значительной степени определяет площадь соответствующей реальной схемы, расположенной на кремниевом кристалле. Глубина же логической схемы в значительной мере определяет задержку реальной схемы, т.е. время, за которое сигнал проходит от входов схемы к ее выходам, другими словами, время, которое должно пройти после стабилизации каких-либо значений на входах схемы до того момента, когда на всех выходах схемы также стабилизируются определенные логические значения. Сложность схемы часто не имеет существенного значения, так как современные технологии позволяют разместить на кристалле очень большие схемы. А минимизация задержки схемы очень важна, так как задержка комбинационной части многотактной схемы определяет ее тактовую частоту – чем меньше задержка, тем выше частота.
Теоретически вычислить задержку реальной схемы очень сложно. Цепей элементов схемы, соединяющих ее входы с выходами (эти цепи также называют путями), обычно довольно много и задержка схемы определяется задержкой по самому плохому в определенном смысле пути, который называется критическим. Например, на схеме 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 имеет меньшую глубину, чем все известные схемы.
Впоследствии были найдены схемы для деления с глубиной по порядку равной log2n, но их сложность оказалась велика. Американцы Рейф и Тейт построили схемы для деления глубины по порядку не превосходящей log2n log2(log2n) и одновременно сложности по порядку не превосходящей n log2n log2 log2n, однако и эти схемы, как и схемы Шенхаге-Штрассена и Фюрера пока не нашли практических применений, так как в действительности начинают превосходить используемые на практике схемы лишь при огромных значениях n.
↑Рекомендуемая литература
Эта статья еще не написана, но вы можете сделать это.
Двоичная арифметика
Категории Дискретная математика | Под редакцией сообщества: Математика
Содержание
↑Двоичная арифметика
Двоичная арифметика – краткое наименование системы арифметических операций (включающей сложение, вычитание, умножение, деление, иногда некоторые другие операции) над двоичными числами, т.е. целыми числами, представленными в двоичной позиционной системе; собирательное название схемных решений для выполнения арифметических операций над двоичными числами – сумматоров, умножителей, схем вычитания, деления и другие.
В последнее время почти вся техника, связанная с передачей и обработкой информации, стала цифровой. Цифровыми стали аудио и видеомагнитофоны, превратившись в DVD-плейеры и Айподы, телевизоры, фотоаппараты, а многие виды электронно-вычислительной техники и современные мобильные телефоны были цифровыми изначально. Это означает, что информация, циркулирующая в этих устройствах, представляется (или, как говорят, кодируется) в цифровом виде, т.е. как правило, в виде строк (или последовательностей), состоящих из нулей и единиц. Этим строкам можно сопоставить по некоторым правилам целые числа, для чего обычно используется двоичная позиционная система их записи.
Таким образом, с определенной точки зрения, все цифровые устройства генерируют потоки целых чисел, по некоторым правилам их преобразуют, обрабатывают, кодируют, декодируют и т.д., и передают другим цифровым устройствам. Область науки и техники, которая занимается изучением подобных процессов, называется цифровой обработкой сигналов (английская аббревиатура DSP – Digital Signal Processing).
Существенную роль в этом играют алгоритмические процедуры, выполняющие арифметические и логические операции с различными типами числовых данных. Проектированием подобных алгоритмов и устройств, их реализующих, занимается компьютерная арифметика. Ее математической основой является теория сложности так называемых булевых функций (более длинно именуемых функциями алгебры логики).
В большей своей части компьютерная арифметика является двоичной арифметикой. Этому есть две причины. Во-первых, алгоритмы арифметических операций двоичной арифметики (т.е. арифметики, использующей двоичную позиционную систему) очень просты и являются в определенном смысле простейшими среди подобных алгоритмов для всех позиционных числовых систем. Во-вторых, дискретные (не аналоговые) электронные схемы, как самые современные, так и использовавшиеся много лет назад, имеют в определенном смысле двоичную природу и легко описываются на языке алгебры логики. Алгебра логики применяется как для моделирования функционирования этих схем, так и для их проектирования (синтеза).
↑Схемная реализация булевых функций
Из функциональных элементов строятся схемы, реализующие булевы функции. Неформально говоря, схема из функциональных элементов может быть построена путем произвольного соединения выходов некоторых элементов с входами других элементов так, чтобы различные выходы не присоединялись к одному и тому же входу и не возникали ориентированные циклы из элементов. Пример схемы из функциональных элементов приведен на рисунке ниже. Под сложностью схемы понимается число входящих в нее функциональных элементов. Подробнее см. статью « Сложность булевых функций».
↑Двоичная позиционная система записи целых чисел
Главное достоинство двоичной системы (помимо естественности ее применения в электронной цифровой технике ) – исключительная простота алгоритмов арифметических операций в ней. Таблица умножения в двоичной системе совсем не требует запоминания: любое число, умноженное на нуль дает нуль, а умноженное на единицу равно самому себе. Правило деления сводится к двум равенствам 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. Эта схема (в базисе
Схемы для арифметических операций над многоразрядными двоичными числами. Сложение двух n-разрядных двоичных чисел (xn,….,x1)2 и (yn,….,y1)2 как и в десятичной системе приводит к появлению переносов в следующий разряд, которые необходимо учитывать в вычислении. Эти переносы также равны нулю или единице (если перенос равен нулю, то в ручном вычислении он фактически не выполняется, но логическая схема обязана правильно работать и в этом случае, ведь она «не знает», какой перенос пришел из предыдущего разряда). Обозначим перенос из (i-1)-го разряда в следующий i-й разряд через wi (w1=0, потому что предыдущего разряда в этом случае просто нет). Тогда для вычисления zi (i-го бита результата) нужно сложить биты xi и yi и бит переноса wi. Это сложение выполняем по формулам
Схема сложения трехразрядных чисел приведена на следующем рисунке. Аналогичным образом выглядит и схема сложения n-разрядных чисел.
Сложность указанного n-разрядного сумматора равна 5n-3. Н.П.Редькин доказал, что сумматоров для n-разрядных чисел меньшей сложности в базисе
Глубина схемы – не менее важная характеристика схемы, чем ее сложность. Сложность логической схемы в значительной степени определяет площадь соответствующей реальной схемы, расположенной на кремниевом кристалле. Глубина же логической схемы в значительной мере определяет задержку реальной схемы, т.е. время, за которое сигнал проходит от входов схемы к ее выходам, другими словами, время, которое должно пройти после стабилизации каких-либо значений на входах схемы до того момента, когда на всех выходах схемы также стабилизируются определенные логические значения. Сложность схемы часто не имеет существенного значения, так как современные технологии позволяют разместить на кристалле очень большие схемы. А минимизация задержки схемы очень важна, так как задержка комбинационной части многотактной схемы определяет ее тактовую частоту – чем меньше задержка, тем выше частота.
Теоретически вычислить задержку реальной схемы очень сложно. Цепей элементов схемы, соединяющих ее входы с выходами (эти цепи также называют путями), обычно довольно много и задержка схемы определяется задержкой по самому плохому в определенном смысле пути, который называется критическим. Например, на схеме 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 имеет меньшую глубину, чем все известные схемы.
Впоследствии были найдены схемы для деления с глубиной по порядку равной log2n, но их сложность оказалась велика. Американцы Рейф и Тейт построили схемы для деления глубины по порядку не превосходящей log2n log2(log2n) и одновременно сложности по порядку не превосходящей n log2n log2 log2n, однако и эти схемы, как и схемы Шенхаге-Штрассена и Фюрера пока не нашли практических применений, так как в действительности начинают превосходить используемые на практике схемы лишь при огромных значениях n.
↑Рекомендуемая литература
Эта статья еще не написана, но вы можете сделать это.
Тема урока: «Двоичная арифметика»
Программно-дидактическое обеспечение: ПК, программа Калькулятор.
I. Организационный момент
Приветствие, проверка отсутствующих.
1. Постановка целей урока
10001102 + 10101012;
1000111101112/1011012;11100011102 – 110102;
1011012 * 1000112
После предложенных ответов учащихся, комментирую и объясняю, что сегодня на уроке мы научимся правильно выполнять арифметические действия в двоичной системе счисления.
2. Человек не ведет счет в двоичной системе, т.к. она для него не удобна. А кто или что использует ее для счета и почему?
II. Изложение нового материала
Двоичная система счисления
Из всех позиционных систем счисления особенно проста и поэтому интересна двоичная система счисления.
– Чему равно основание двоичной системы счисления? (q = 2)
Двоичная система счисления издавна была предметом пристального внимания многих учёных. П.С.Лаплас писал о своём отношении к двоичной (бинарной) системе счисления великого математика Г.Ф.Лейбница: «В своей бинарной арифметике Лейбниц видел прообраз творения. Ему представлялось, что единица представляет божественное начало, а нуль – небытие и что высшее существо создает всё из небытия точно таким же образом, как единица и нуль в его системе выражают все числа ». Эти слова подчеркивают удивительную универсальность алфавита состоящего всего из двух символов.
Для того чтобы лучше освоить двоичную систему счисления, необходимо освоить выполнение арифметических действий над двоичными числами.
Все позиционные системы «одинаковы», а именно, во всех них арифметические операции выполняются по одним и тем же правилам:
Таблица сложения двоичных чисел проста.
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
1 + 1 + 1 = 11
При сложении двух единиц происходит переполнение разряда и производится перенос в старший разряд. Переполнение разряда наступает тогда, когда величина числа в нем становится равной или большей основания.
0 – 0 = 0
0 – 1 = 11
1 – 0 = 1
1 – 1 = 0
Вычитание многоразрядных двоичных чисел происходит в соответствии с вышеприведённой таблицей вычитания с учетом возможных заёмов из старших разрядов.
Операция умножения выполняется с использованием таблицы умножения по обычной схеме (применяемой в десятичной системе счисления) с последовательным умножением множимого на очередную цифру множителя.
При делении столбиком приходится в качестве промежуточных результатов выполнять действия умножения и вычитания.
III. Закрепление изученного
1001001 + 10101 (ответ 1011110);
101101 + 1101101 (ответ 10011010)
11000,11 + 11010,11 (ответ 110011,1)
10001000 – 1110011 (ответ 10101)
1101100 – 10110110 (ответ – 1001010)
110101,101 – 1001,111 (101011,11)
100001*111,11 (ответ: 11111111,11)
10011*1111,01 (ответ: 100100001,11)
Оценивание работу учащихся, назвать отличившихся на уроке.
V. Домашнее задание
Выучить правила выполнения арифметических действий в двоичной системе счисления, а так же таблицы сложения, вычитания и умножения в двоичной системе счисления.
Составьте таблицы сложения и умножения в троичной и пятеричной системе счисления.
Информатика. 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.
Сегодня на уроке мы познакомились с двоичной арифметикой – узнали, как выполняются арифметические операции с двоичными числами. Вы убедились, что все происходит по тем же правилам, что и в привычной нам десятичной системе счисления.
Вся компьютерная техника построена на использовании двоичных кодов: с их помощью представляют, хранят, обрабатывают и передают по компьютерным сетям самые разные виды информации!