Арифметические и логические основы вычислительной техники

Введение Основная цель настоящего учебного пособия - помочь студенту, присту- пившему к изучению арифметики вычислительных машин, приобрести теоре- тические знания и практические навыки выполнения основных арифметических операций. Правильное понимание алгоритмов рассматриваемых операций под- крепляется знанием структурных и логических схем, реализующих эти алго- ритмы и представляющих собой некоторые операционные устройства. В посо- бии уделяется внимание рассмотрению этих схемных решений. Достаточно подробно рассмотрен аппарат, основанный на правилах и законах булевой ал- гебры, ориентированный на упрощение (минимизацию) проектируемых логи- ческих схем. Кроме того, в пособии приводятся сведения об основных формах хранения и преобразования числовой информации, способах ее кодирования. Достаточное внимание уделено методам контроля правильности функциониро- вания цифрового автомата, возможным ошибкам, возникающим при его работе, и способам их устранения. Рассматриваемый в пособии теоретический материал сопровождается достаточным количеством примеров, что упрощает и делает более понятным излагаемый материал. В заключение следует отметить, что в течение ряда лет литература, осве- щающая арифметику вычислительных машин, не выпускалась. В пособии сде- лана попытка устранить этот информационный пробел. Материал пособия ба- зируется на работах [1-5]. Арифметические основы вычислительной техники Системы счисления В ЭВМ информация всегда представляется в виде чисел, записанных в той или иной системе счисления. Выбор системы счисления - один из важней- ших вопросов. От правильности его решения зависят такие характеристики ЭВМ, как скорость вычислений, сложность алгоритмов реализации арифмети- ческих операций и др. Система счисления - совокупность цифр, приемов и пра- вил для записи чисел цифровыми знаками. Любая система счисления должна обеспечивать:  возможность представления любого числа в рассматриваемом диа- пазоне величин; 藳 единственность этого представления; 砛 простоту оперирования числами. Различают два типа систем счисления - непозиционные и позиционные. Непозиционная система счисления - система, для которой значение сим- вола не зависит от его положения в числе. Примером может служить система счисления с одной цифрой 1. Для записи любого числа в ней необходимо напи- сать количество единиц, равное числу. Другой пример - это римская система счисления. Позиционной системой счисления называется система записи любых по величине чисел, в которой значение цифры зависит от ее положения в числе, т.е. веса. Число цифр в позиционной системе счисления ограниченно. Основание (базис) r позиционной системы счисления - максимальное ко- личество различных знаков или символов, используемых для изображения чис- ла в данной системе счисления. Таким образом, основание может быть любым числом, кроме 1 и бесконечности. Любое число в системе счисления с основанием r может быть записано в общем виде: A=a n·r n + a n-1·r n-1 +...+a 1·r 1 +a 0·r 0 + a -1·r --1 +...+a -rn-1·r -(rn-1) +a -rn·r -rn , (1) или i n m i i r a ∑ − = = i А , (2) где любая разрядная цифра a i ∈{0,…,r-1}, a r i - вес соответствующего разряда. Запись числа в форме (1) назовем записью числа в развернутой форме. Свернутой формой записи чисел называется запись чисел в виде A=a 1 a 2 … a k . Для любой системы счисления основание представляется как 1 (один) и 0 (ноль). Например: 9 1 F 7 + 1 + 1 + 1 + 1 10 10 10 2 10 16 10 8 Вес разряда p i числа выражается соотношением p i = r i /r 0 = r i , где i - номер разряда при отсчете справа налево. Если в i-м разряде накопилось значение единиц, равное или большее r, то должна происходить передача единицы в старший i+1 разряд. При сложении такая передача информации называется переносом. При вычитании передача из i+1 разряда в i-й – заем. Длина числа – количество позиций (разрядов) в записи числа. В техниче- ской реализации под длиной числа понимается длина разрядной сетки. Диапазон представления чисел в заданной системе счисления – интервал числовой оси, заключенный между максимальным и минимальным числами, представленными при заданной длине разрядной сетки. В вычислительной технике для представления данных и выполнения арифметических операций над ними удобно использовать двоичную, восьме- ричную и шестнадцатеричную системы счисления. Ниже коротко остановимся на них. Двоичная система счисления Для записи числа в двоичной системе счисления используются две циф- ры: 0 и 1. Основание системы записывается как 10 (2) (2 10 =1·2 1 +0·2 0 ). Используя данную систему, любое число можно выразить последовательностью высоких и низких потенциалов или группой запоминающих элементов, способных запо- минать одно из двух (0,1) значений. Арифметические операции в двоичной сис- теме счисления выполняются по тем же правилам, что и в десятичной системе счисления. Сложение Вычитание Умножение 0+0= 0 0-0=0 0 · 0=0 0+1= 1 1-0=1 0 · 1=0 1+0= 1 1-1=0 1 · 0=0 1+1=10 10-1=1 1 · 1=1 Рассмотрим несколько примеров, демонстрирующих выполнение ариф- метических операций: 11010001 10011 10011 10011 1011 10011 * 00010111 10010110 10101101 - 11101101 10010111 01010110 + + Восьмеричная система счисления В восьмеричной системе счисления используется восемь цифр: 0,1,2 … 7, а основание записывается как 10 (8) (8 10=1·8 1 +0·8 0 ). Рассмотрим выполнение опе- раций в восьмеричной системе счисления. При их выполнении используются правила, представленные в таблицах сложения и умножения восьмеричных цифр. Сложение Умножение 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 10 1 1 2 3 4 5 6 7 2 3 4 5 6 7 10 11 2 2 4 6 10 12 14 16 3 4 5 6 7 10 11 12 3 3 6 11 14 17 22 25 4 5 6 7 10 11 12 13 4 4 10 14 20 24 30 34 5 6 7 10 11 12 13 14 5 5 12 17 24 31 36 43 6 7 10 11 12 13 14 15 6 6 14 22 30 36 44 52 7 10 11 12 13 14 15 16 7 7 16 25 34 43 52 61 5607560 40630 142310 101460 264 20314 * 24315626 17352326 43670154 - 57033602 21764254 35047326 + + Пример: Пример: