Материалы сайта
Это интересно
Системы счисления
1. Происхождение и история развития систем счисления 1.1 Границы счета На ранних ступенях развития общества люди почти не умели считать. Они отличали друг от друга совокупности двух и трех предметов; всякая совокупность, содержавшая большее число предметов, объединялась в понятии «много». Это был еще не счет, а лишь его зародыш. Впоследствии способность различать друг от друга небольшие совокупности развивалась; возникли слова для обозначений понятий «четыре», «пять», «шесть», «семь». Последнее слово длительное время обозначало также неопределенно большое количество. Наши пословицы сохранили память об этой эпохе («семь раз отмерь – один раз отрежь», «у семи нянек дитя без глазу», «семь бед – один ответ» и т.д.). С усложнением хозяйственной деятельности людей понадобилось вести счет в более обширных пределах. Для этого человек пользовался окружавшими его предметами, как инструментами счета: он делал зарубки на палках и на деревьях, завязывал узлы на веревках, складывал камешки в кучки и т.п. Такой вид счета носит название унарной системы счисления, т.е. система счисления, в которой для записи числа применяется только один вид знаков. Это удобно, так как сразу визуально определяется количество знаков и сопоставляется с количеством предметов, которые эти знаки обозначают. Все мы ходили в первый класс и считали там на счетных палочках – это отзвук той далекой эпохи. Кстати, от счета с помощью камешков ведут свое начало различные усовершенствованные инструменты, как, например, русские счеты, китайские счеты («сван-пан»), древнеегипетский «абак» (доска, разделенная на полосы, куда клались жетоны). Аналогичные инструменты существовали у многих народов. Более того, в латинском языке понятие «счет» выражается словом «calculatio» (отсюда наше слово «калькуляция»); а происходит оно от слова «calculus», означающего «камешек». Особо важную роль играл природный инструмент человека – его пальцы. Этот инструмент не мог длительно хранить результат счета, но зато всегда был «под рукой» и отличался большой подвижностью. Язык первобытного человека был беден; жесты возмещали недостаток слов, и числа, для которых еще не было названий, «показывались» на пальцах. Поэтому, вполне естественно, что вновь возникавшие названия «больших» чисел часто строились на основе числа 10 – по количеству пальцев на руках; у некоторых народов возникали также названия чисел на основе числа 5 – по количеству пальцев на одной руке или на основе числа 20 – по количеству пальцев на руках и ногах. На первых порах расширение запаса чисел происходило медленно. Сначала люди овладели счетом в пределах нескольких десятков и лишь позднее дошли до сотни. У многих народов число 40 долгое время было пределом счета и названием неопределенно большого количества. В русском языке слово «сороконожка» имеет смысл «многоножка»; выражение «сорок сороков» означало в старину число, превосходящее всякое воображение. На следующей ступени счет достигает нового предела: десяти десятков, и создается название для числа 100. Вместе с тем слово «сто» приобретает смысл неопределенно большого числа. Такой же смысл приобретают потом последовательно числа тысяча, десять тысяч (в старину это число называлось «тьма»), миллион. На современном этапе границы счета определены термином «бесконечность», который не обозначает какое либо конкретное число. 1.2 Десятичная система счисления В современном русском языке, а также в языках других народов названия всех чисел до миллиона составляются из 37 слов, обозначающих числа 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 , 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000 (например, восемьсот пятнадцать тысяч триста девяносто четыре). В свою очередь названия этих 37 чисел, как правило, образованы из названий чисел первого десятка (1, 2, 3, 4, 5, 6, 7, 8, 9) и чисел 10, 100, 1000 (например, 18 = восемь на десять, 30 = тридесять и т.д.). В основе этого словообразования лежит число десять, и поэтому наша система наименований называется десятичной системой счисления. Из упомянутого правила в разных языках имеются различные исключения, объясняющиеся историческими особенностями развития счета. В русском языке единственным исключением является наименование «сорок». Это исключение можно поставить в связь с тем, что число 40 играло некогда особую роль, означая неопределенно большое количество. В тюркских языках (узбекском, казахском, татарском, башкирском, турецком и др.) исключение составляют наименования чисел 20, 30, 40, 50, тогда как названия чисел 60, 70, 80, 90 образованы из наименований для 6, 7, 8, 9. Во французском языке сохранились недесятичные названия чисел 20 и 80, причем 80 именуется quatrevingt, т.е. «четыре двадцать». Здесь мы имеем остаток древнего двадцатеричного счисления (по числу пальцев на руках и ногах). В латинском языке наименование числа 20 тоже недесятичное (viginti). Наименования чисел 18 и 19 образованы из названия 20 с помощью вычитания: 20–2 и 20–1 (duodeviginti, undeviginti, т.е. «два от двадцати», «один от двадцати»). 1.3 Развитие понятия числа При счете отдельных предметов единица есть наименьшее число; делить ее на доли не нужно, а часто и невозможно (при счете камней прибавление к двум камням половины третьего дает три камня, а не два с половиной). Однако делить единицу на доли приходится уже при грубых измерениях величин, например при измерении длины шагами (два с половиной шага и т.д.). Поэтому уже в отдаленные эпохи создалось понятие дробного числа. Так, в вавилонской системе мер веса (и денег) 1 талант составлял 60 мин, а одна мина – 60 шекелей. Соответственно с этим в вавилонской математике широко употреблялись шестидесятиричные дроби. В древнеримской весовой (и денежной) системе 1 асс делился на 12 унций; сообразно с этим римляне пользовались двенадцатиричными дробями. Наши «обыкновенные дроби» широко употреблялись древними греками и индийцами. Правила действий с дробями, изложенные индийским ученым Брамагуптой (VIII век н.э.), лишь немногим отличаются от наших. Наша запись дробей тоже совпадает с индийской; только дробной черты индийцы не писали; греки записывали сверху знаменатель, а снизу числитель. Индийской обозначение дробей и правила действий над ними были усвоены в IX веке в мусульманских странах благодаря узбекскому ученому Мухаммеду Хорземскому (аль-Хваризми). Они были перенесены в Западную Европу итальянским купцом и ученым Леонардо Фибоначчи из Пизы (XIII век). Наряду с «обыкновенными» дробями до XVII века применялись (преимущественно в астрономии) шестидесятиричные дроби. Они были вытеснены десятичными дробями, введенными голландским купцом и выдающимся инженером- ученым Симоном Стевином (1548 - 1620). В дальнейшем оказалось необходимым еще больше расширить понятие числа; последовательно появились числа иррациональные, отрицательные и комплексные. Довольно поздно к семье чисел присоединился нуль. Первоначально слово «нуль» означало отсутствие числа (буквальный смысл латинского слова nullum – «ничто»). Для того чтобы это «ничто» считать числом, появились основания лишь в связи с рассмотрением отрицательных чисел. 1.4 Системы нумерации некоторых народов 1.4.1 Древнегреческая нумерация В древнейшее время в Греции была распространена т.н. аттическая нумерация. Числа 1, 2, 3, 4 обозначались черточками [pic], [pic],[pic],[pic]. Число 5 записывалось знаком [pic] (древнее начертание буквы «пи», с которой начинается слово «пенте» – пять); числа 6, 7, 8, 9 обозначались [pic], [pic], [pic], [pic]. Число 10 обозначалось [pic] (начальной буквой слова «дека» – десять). Числа 100, 1000 и 10000 обозначались [pic], [pic], [pic]. Числа 50, 500, 5000 обозначались комбинациями знаков 5 и 10, 5 и 100, 5 и 1000. Общую запись чисел в аттической нумерации иллюстрирует пример 1.1. Пример 1.1 Запись чисел в аттической системе счисления |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic]. | В третьем веке до н.э. аттическая нумерация была вытеснена так называемой ионийской системой. В ней числа 1 – 9 обозначались первыми девятью буквами алфавита; числа 10, 20, 30, … , 90 – следующими девятью буквами; числа 100, 200, … , 900 – последними девятью буквами. Таблица 1.1 Обозначение чисел в ионийской системе нумерации |Обозна-|Название|Значе-|Обозна-|Название|Значе-|Обозна-|Назва-н|Значе-| | | |ние |чение | |ние |чение |ие |ние | |Чение | | | | | | | | | |[pic] |Альфа |1 |[pic] |Йота |10 |[pic] |Ро |100 | |[pic] |Бета |2 |[pic] |Каппа |20 |[pic] |Сигма |200 | |[pic] |Гамма |3 |[pic] |Лямбда |30 |[pic] |Тау |300 | |[pic] |Дельта |4 |[pic] |Мю |40 |[pic] |Ипсилон|400 | |[pic] |Эпсилон |5 |[pic] |Ню |50 |[pic] |Фи |500 | | |Фауб |6 |[pic] |Кси |60 |[pic] |Хи |600 | |[pic] |Дзета |7 |[pic] |Омикрон |70 |[pic] |Пси |700 | |[pic] |Эта |8 |[pic] |Пи |80 |[pic] |Омега |800 | |[pic] |Тэта |9 | |Коппа |90 | |Сампи |900 | Следует отметить, что буквы «фау», «коппа» и «сампи» отсутствуют в современном греческом алфавите. Для обозначения тысяч и десятков тысяч пользовались теми же цифрами с добавлением особого значка ` сбоку. Для отличия цифр от букв, составлявших слова, писали черточки над цифрами. Обозначение чисел в ионийской нумерации представлены в таблице 1.1, а примеры написания различных чисел в примере 1.2. Пример 1.2 Запись чисел в ионийской системе счисления |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic]. | Такую же алфавитную нумерацию имели в древности евреи, арабы и многие другие народы Ближнего Востока. 1.4.2 Славянская нумерация Южные и восточные славянские народы для записи чисел пользовались алфавитной нумерацией. У одних славянских народов числовые значения букв установились в порядке славянского алфавита, у других же (в том числе у русских) роль цифр играли не все буквы, а только те, которые имеются в греческом алфавите. Над буквой, обозначавшей цифру, ставился специальный значок: [pic] («титло»). Таблица 1.2 Обозначение чисел в древнеславянской системе нумерации |Обозна-|Название|Значе-|Обозна-|Название|Значе-|Обозна-|Назва-н|Значе-| |чение | |ние |чение | |ние |чение |ие |ние | |[pic] |Аз |1 |[pic] |И |10 |[pic] |Рцы |100 | |[pic] |Веди |2 |[pic] |Како |20 |[pic] |Слово |200 | |[pic] |Глаголь |3 |[pic] |Люди |30 |[pic] |Твердо |300 | |[pic] |Добро |4 |[pic] |Мыслите |40 |[pic] |Ук |400 | |[pic] |Есть |5 |[pic] |Наш |50 |[pic] |Ферт |500 | |[pic] |Зело |6 |[pic] |Кси |60 |[pic] |Хер |600 | |[pic] |Земля |7 |[pic] |Он |70 |[pic] |Пси |700 | |[pic] |Иже |8 |[pic] |Покой |80 |[pic] |Омега |800 | |[pic] |Фита |9 |[pic] |Червь |90 |[pic] |Цы |900 | В России славянская нумерация сохранилась до конца XVII века. При Петре I возобладала так называемая «арабская нумерация», которой мы пользуемся и сейчас. Славянская нумерация сохранялась только в богослужебных книгах. В таблице 1.2 приведены славянские цифры. При записи чисел, больших 10, цифры писались слева направо в порядке убывания десятичных разрядов (однако иногда для чисел от 11 до 19 единицы записывались ранее десяти). Для обозначения тысяч перед числом их (слева внизу) ставился особый знак [pic]. Пример 1.3 иллюстрирует написание чисел в славянской системе нумерации. Пример 1.3 Запись чисел в древнеславянской системе счисления |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic]. | 1.4.3 Римская нумерация Древние римляне пользовались нумерацией, которая сохраняется до настоящего времени под именем «римской нумерации». Мы пользуемся ей для обозначения веков, юбилейных дат, наименования съездов и конференций, для нумерации глав книги или строф стихотворения. В позднейшем своем виде римские цифры выглядят так: [pic], [pic], [pic], [pic], [pic], [pic], [pic]. В римской нумерации явственно сказываются следы пятиричной системы счисления. В языке же римлян (латинском) никаких следов пятиричной системы нет. Значит, эти цифры были заимствованы римлянами у другого народа (предположительно у этрусков). Все целые числа (до 5000) записываются с помощью повторения вышеприведенных цифр. При этом, если большая цифра стоит перед меньшей, то они складываются, если же меньшая стоит перед большей (в этом случае она не может повторяться), то меньшая вычитается из большей. Подряд одна и та же цифра ставится не более трех раз. Рассмотрим примеры. Пример 1.4 Запись чисел римскими цифрами |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic], | |[pic] |[pic]. | Выполнение арифметических действий над многозначными числами в этой записи очень громоздко и трудно. Тем не менее римская нумерация преобладала в Италии до XIII века, а в других странах Западной Европы - до XVI века. 1.4.4 Вавилонская поместная нумерация В древнем Вавилоне примерно за 40 веков до нашего времени создалась поместная (позиционная) нумерация, т.е. такой способ изображения чисел, при котором одна и та же цифра может обозначать разные числа, смотря по месту, занимаемому этой цифрой. Наша теперешняя нумерация - тоже поместная, однако в вавилонской поместной нумерации ту роль, которую играет у нас число 10, играло число 60, и потому эту нумерацию называют шестидесятиричной. Числа, меньшие 60, обозначались с помощью двух знаков: для единицы [pic] и для десятка [pic]. Они имели клинообразный вид, так как вавилоняне писали на глиняных дощечках палочками треугольной формы. Эти знаки повторялись нужное число раз. При отсутствии промежуточного разряда применялся знак[pic]. Запись чисел до 60 показана в примере 1.5. Способ обозначения чисел, больших 60 сведен в таблицу 1.3. Пример 1.5 Запись вавилонской клинописью чисел до 60 |[pic] |[pic], | |[pic] | | | |[pic], | |[pic] |[pic], | |[pic] |[pic]. | Таблица 1.3 Запись вавилонской клинописью чисел, больших 60 |Обозначение |Значение |Способ образования | |[pic] |302 |[pic] | |[pic] |1295 |[pic] | |[pic] |3725 |[pic] | |[pic] |7203 |[pic] | Шестидесятиричная запись целых чисел не получила распространения за пределами ассиро-вавилонского царства, но шестидесятиричные дроби проникли далеко за эти пределы: в страны Среднего Востока, Средней Азии, в Северную Африку и Западную Европу. Они широко применялись, особенно в астрономии, вплоть до изобретения десятичных дробей. Следы шестидесятиричных дробей сохраняются и поныне в делении углового и дугового градуса (а также часа) на 60 минут и минуты на 60 секунд. 1.4.5 Индийская поместная нумерация В различных областях Индии существовали разнообразные системы нумерации. Одна из них распространилась по всему миру и в настоящее время является общепринятой. В ней цифры имели вид начальных букв соответствующих числительных на древнеиндийском языке – санскрите (алфавит «деванагари»). Первоначально этими знаками представлялись числа 1, 2, 3, … , 9, 10, 20, 30, … , 90, 100, 1000; с их помощью записывались другие числа. Впоследствии был введен особый знак (жирная точка или кружок) для указания пустующего разряда; знаки для чисел, больших 9, вышли из употребления, и нумерация «деванагари» превратилась в десятичную поместную систему. К середине VIII века позиционная система нумерации получает в Индии широкое применение. Примерно в это время она проникает и в другие страны (Индокитай, Китай, Тибет, в Иран и др.). Решающую роль в распространении индийской нумерации в арабских странах сыграло руководство, составленное в начале IX века узбекским ученым Мухаммедом из Хорезма (аль-Хваризми). Оно было переведено в Западной Европе на латинский язык в XII веке. В XIII веке индийская нумерация получает преобладание в Италии. В других странах Западной Европы она утверждается в XVI веке. Европейцы, заимствовавшие индийскую нумерацию от арабов, называли ее «арабской». Это исторически неправильное название удерживается и поныне. Из арабского языка заимствовано и слово «цифра» (по-арабски «сыфр»). Форма индийских цифр претерпевала многообразные изменения. Та форма, в которой мы их пишем сейчас, установилась в XVI веке. 2 Основные понятия и определения Выше мы говорили о системах счисления, не вдаваясь в подробности этого понятия. Каково же научное определение системы счисления? Системой счисления называют систему приемов и правил, позволяющих устанавливать взаимно-однозначное соответствие между любым числом и его представлением в виде совокупности конечного числа символов. Множество символов, используемых для такого представления, называют цифрами. В зависимости от способа изображения чисел с помощью цифр системы счисления делятся на позиционные и непозиционные. В непозиционных системах любое число определяется как некоторая функция от численных значений совокупности цифр, представляющих это число. Цифры в непозиционных системах счисления соответствуют некоторым фиксированным числам. Пример непозиционной системы – рассмотренная ранее римская система счисления. Дpевние египтяне пpименяли систему счисления, состоящую из набоpа символов, изобpажавших pаспpостpаненные пpедметы быта. Совокупность этих символов обозначала число. Расположение их в числе не имело значения, отсюда и появилось название. Исторически первыми системами счисления были именно непозиционные системы. Одним из основных недостатков является трудность записи больших чисел. Запись больших чисел в таких системах либо очень громоздка, либо алфавит системы чрезвычайно велик. В вычислительной технике непозиционные системы не применяются. Систему счисления называют позиционной, если одна и та же цифра может принимать различные численные значения в зависимости от номера разряда этой цифры в совокупности цифр, представляющих заданное число. Пример такой системы – арабская десятичная система счисления. Количества и количественные составляющие, существующие реально могут отображаться различными способами. В общем случае в позиционной системе счисления число N может быть представлено как: [pic], где: (2.1) [pic] – основание системы счисления (целое положительное число, равное числу цифр в данной системе); [pic] – любые цифры из интервала от нуля до [pic]. Основание позиционной системы счисления определяет ее название. В вычислительной технике применяются двоичная, восьмеричная, десятичная и шестнадцатеричная системы. В дальнейшем, чтобы явно указать используемую систему счисления, будем заключать число в скобки и в нижнем индексе указывать основание системы счисления. Каждой позиции в числе соответствует позиционный (разрядный) коэффициент или вес. Покажем это на примере десятичного числа: Пример 2.1 Способ образования десятичного числа [pic] Для десятичной системы соответствия между позицией и весом следующее: [pic] (2.2) в общем случае: [pic] (2.3) В настоящее время позиционные системы счисления более широко распространены, чем непозиционные. Это объясняется тем, что они позволяют записывать большие числа с помощью сравнительно небольшого числа знаков. Еще более важное преимущество позиционных систем - это простота и легкость выполнения арифметических операций над числами, записанными в этих системах. Вычислительные машины в принципе могут быть построены в любой системе счисления. Но столь привычная для нас десятичная система окажется крайне неудобной. Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент со множеством состояний (колесо с десятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Наиболее удобной для построения ЭВМ оказалась двоичная система счисления, т.е. система счисления, в которой используются только две цифры: 0 и 1, т.к. с технической точки зрения создать устройство с двумя состояниями проще, также упрощается различение этих состояний. Для представления этих состояний в цифровых системах достаточно иметь электронные схемы, которые могут принимать два состояния, четко различающиеся значением какой-либо электрической величины – потенциала или тока. Одному из значений этой величины соответствует цифра 0, другому – 1. Относительная простота создания электронных схем с двумя электрическими состояниями и привела к тому, что двоичное представление чисел доминирует в современной цифровой технике. При этом 0 обычно представляется низким уровнем потенциала, а 1 – высоким уровнем. Такой способ представления называется положительной логикой. 3 Двоичная система счисления: основные сведения 3.1 История возникновения двоичной системы счисления Двоичная система счисления, т.е. система с основанием [pic], является «минимальной» системой, в которой полностью реализуется принцип позиционности в цифровой форме записи чисел. В двоичной системе счисления значение каждой цифры «по месту» при переходе от младшего разряда к старшему увеличивается вдвое. История развития двоичной системы счисления – одна из ярких страниц в истории арифметики. Официальное «рождение» двоичной арифметики связывают с именем Г. В. Лейбница, опубликовавшего статью, в которой были рассмотрены правила выполнения всех арифметических операций над двоичными числами. До начала тридцатых годов XX века двоичная система счисления оставалась вне поля зрения прикладной математики. Потребность в создании надежных и простых по конструкции счетных механических устройств и простота выполнения действий над двоичными числами привели к более глубокому и активному изучению особенностей двоичной системы как системы, пригодной для аппаратной реализации. Первые двоичные механические вычислительные машины были построены во Франции и Германии. Утверждение двоичной арифметики в качестве общепринятой основы при конструировании ЭВМ с программным управлением состоялось под несомненным влиянием работы А. Бекса, Х. Гольдстайна и Дж. Фон Неймана о проекте первой ЭВМ с хранимой в памяти программой, написанной в 1946 году. В этой работе наиболее аргументированно обоснованы причины отказа от десятичной арифметики и перехода к двоичной системе счисления как основе машинной арифметики. 3.2 Основные понятия машинной арифметики В двоичной системе счисления используются только два символа, что хорошо согласуется с техническими характеристиками цифровых схем. Действительно очень удобно представлять отдельные составляющие информации с помощью двух состояний: . Отверстие есть или отсутствует (перфолента или перфокарта); . Материал намагничен или размагничен (магнитные ленты, диски); . Уровень сигнала большой или маленький. Существуют специальные термины, широко используемые в вычислительной технике: бит, байт и слово. Битом называют один двоичный разряд. Крайний слева бит числа называют старшим разрядом (он имеет наибольший вес), крайний справа – младшим разрядом (он имеет наименьший вес). Восьмибитовая единица носит название байта. Многие типы ЭВМ и дискретных систем управления перерабатывают информацию порциями (словами) по 8, 16 или 32 бита (1, 2 и 4 байта). Двоичное слово, состоящее из двух байт, показано на рис. 3.1. 4 Взаимный перевод двоичных и десятичных чисел и элементарные двоичные арифметические действия 4.1 Представление двоичных чисел и перевод их в десятичные Совершенно очевидно, что двоичное число представляется последовательностью нулей и единиц – разрядов. Как и в любой позиционной системе, каждому разряду присвоен определенный вес – показатель степени основания системы. Веса первых 10 позиций представлены в таблице 4.1. Таблица 4.1 Веса первых десяти позиций двоичной системы счисления | 148 |–74|2 | | | | | | | | | 74|–37|2 | | | | | | |1 | | | | | | | | | | |0 | 36|–18|2 | | | | | | | |1 | 18|–9 |2 | | | | | | | |0 | 8 |–4 |2 | | | | | | | |1 | 4 |–2 |2 | | | | | | | |0 | 2 |–1 |2 | | | | | | | |0 | 0 |0 | | | | | | | | |1 |( |старший | | | | | | | | | | |разряд | |(10010101)2=(149)10 |( ответ | | 4.2.3 Метод умножения И, наконец, метод умножения. Метод применяется для преобразования десятичных дробей (чисел меньших единицы). Число умножается на 2, если результат ( 1, то в старший разряд записывается единица, если нет, то нуль. Умножаем на 2 дробную часть результата и повторяем процедуру. И так далее до получения нужной степени точности или до обнуления результата. Пример 4.4 Перевод десятичного числа [pic] в двоичное методом умножения [pic] 4.3 Арифметические действия над двоичными числами Арифметика двоичной системы счисления основана на использовании таблиц сложения, вычитания и умножения. Эти таблицы чрезвычайно просты: |Таблица | |сложения | |0 |+|0|=|0 | |0 |+|1|=|1 | |1 |+|0|=|1 | |1 |+|1|=|10| |Таблица | |умножения | |0 |*|0|=|0 | |0 |*|1|=|0 | |1 |*|0|=|0 | |1 |*|1|=|1 | |Таблица | |вычитания | |0 |–|0|=|0 | |1 |–|0|=|1 | |1 |–|1|=|1 | |10|–|1|=|1 | 4.3.1 Двоичное сложение Двоичное сложение выполняется по тем же правилам, что и десятичное, с той лишь разницей, что перенос в следующий разряд производиться после того, как сумма достигнет не десяти, а двух. Пример 4.5 Сложение двоичных чисел [pic] и [pic] |+|10110| | | |1 | | | |11111| | | |0 | | | |01001|– поразрядная сумма без учета переносов | | |1 | | |+|101100|– переносы | | |0 | | | |001001| | | |1 | | | |100101|– поразрядная сумма без учета повторных | | |1 |переносов | |+|010000|– повторные переносы | | |0 | | | |100101| | | |1 | | | |110101|– окончательный результат | | |1 | | Легко произвести проверку: [pic], [pic], [pic], [pic]. Пример 4.6 Сложение двоичных чисел [pic] и [pic] |+|110, |1011 | | |10111|10101 | | |, | | | |10001|0001|– поразрядная сумма без учета | | |, |1 |переносов | |+|11 | 1 |– переносы | | |1, | | | | |10001|00011 | | |, | | | |11100|0101|– поразрядная сумма без учета повторных | | |, |1 |переносов | |+|1 , | |– повторные переносы | | |11100|01011 | | |, | | | |11110|0101|– окончательный результат | | |, |1 | | Сложение нескольких чисел вызывает некоторые трудности, так как в результате поразрядного сложения могут получится переносы, превышающие единицу. 4.3.2 Двоичное вычитание Вычитание в двоичной системе выполняется аналогично вычитанию в десятичной системе счисления. При необходимости, когда в некотором разряде приходится вычитать единицу из нуля, занимается единица из следующего старшего разряда. Если в следующем разряде нуль, то заем делается в ближайшем старшем разряде, в котором стоит единица. При этом следует понимать, что занимаемая единица равна двум единицам данного разряда, т. е. вычитание выполняется по следующему правилу: Пример 4.7 Вычитание двоичных чисел [pic] и [pic] |–|11010|1011 | | |, | | | |1101,|01111 | | |1101,|0011| | | | |1 | | Конечно, математически вычитание выполнить несложно. Однако, если поступать таким образом, то к примеру в ЭВМ придется для выполнения сложения и вычитания иметь два блока: сумматор и вычитатель. Поэтому поступают следующим образом: вычитание можно представить как сложение положительного и отрицательного чисел, необходимо только подходящее представление для отрицательного числа. Рассмотрим четырехразрядный десятичный счетчик, какие в автомобиле отсчитывают пройденный путь. Пусть он показывает число 2, если вращать его в обратном направлении, то сначала появится 1, затем 0, после 0 появится число 9999. Сложим, к примеру, 6 с этим числом: |+ |6 | | | |9999 | | | |10005| | | Если пренебречь единицей переноса и считать 9999 аналогом –1, то получим верный результат: [pic]. Число 9999 называется десятичным дополнением числа 1. Таким образом, в десятичной системе счисления отрицательные числа могут быть представлены в форме десятичного дополнения, а знак минус можно опустить. Двоичное дополнение числа определяется как то число, которое будучи прибавлено к первоначальному числу, даст только единицу переноса в старшем разряде. Пример 4.8 Двоичное дополнение числа [pic] |+ |010101111|– число | | |101010001|– двоичное дополнение | | |100000000|– сумма | | |0 | | | ( – единица переноса | Для получения двоичного дополнения необходимо: . получить обратный код, который образуется инвертированием каждого бита: |010101111|– число | |101010000|– обратный код | . прибавить к обратному коду единицу, образовав таким образом дополнительный код: |+ |101010000|– обратный код | | |1 | | | |101010001|– дополнительный код | Пример 4.9 Вычитание в дополнительном коде [pic] [pic] – обратный код, [pic] – дополнительный код. [pic] 1001012=510 (верно). 4.3.3 Двоичное умножение Умножение двух двоичных чисел выполняется так же, как и умножение десятичных. Сначала получаются частичные произведения и затем их суммируют с учетом веса соответствующего разряда множителя. Отличительной особенностью умножения в двоичной системе счисления является его простота, обусловленная простотой таблицы умножения. В соответствии с ней, каждое частичное произведение или равно нулю, если в соответствующем разряде множителя стоит нуль, или равно множимому, сдвинутому на соответствующее число разрядов, если в соответствующем разряде множителя стоит единица. Таким образом, операция умножения в двоичной системе сводится к операциям сдвига и сложения. Умножение производится, начиная с младшего или старшего разряда множителя, что и определяет направление сдвига. Если сомножители имеют дробные части, то положение запятой в произведении определяется по тем же правилам, что и для десятичных чисел. Пример 4.10 Умножение двоичных чисел [pic] и [pic] [pic] 4.3.4 Двоичное деление Деление чисел в двоичной системе производится аналогично делению десятичных чисел. Рассмотрим деление двух целых чисел, так как делимое и делитель всегда могут быть приведены к такому виду путем перениесения запятой в делимом и делителе на одиноаковое число разрядов и дописывания необходимых нулей. Деление начинается с того, что от делимого слева отделяется минимальная группа разрядов, которая, рассматриваемая как число, превышает или равна делителю. Дальнейшие действия выполняются по обычным правилам, причем последняя целая цифра частного получается тогда, когда все цифры делимого исчерпаны. Пример 4.11 Деление двоичных чисел |1) 18:2| | |2) 14:4 | | | | | | | | | | |10010 |10 | | 1110 |100 | | |10 |1001=(9)1| | 100 |11,1=(3,5)| | | |0 | | |10 | | | 00 | | | 110 | | | | 00 | | | 100 | | | | 001 | | | 100| | | | 000 | | | 100| | | | | | | | | | |10 | | |0 | | | | | | | | | | |10 | | | | | | | | | | | | | |00 | | | | | | Таким образом, выполнение арифметических операций в двоичной системе счисления достаточно просто. Особенно просто выполнять операции сложения, вычитания и умножения. Благодоря этому, применение двоичной системы в вычислительных машинах позволяет упростить схемы устройств, в которых осуществляются операции над числами. 5 Представление чисел в ЭВМ, кодирование 5.1 Представление чисел с фиксированной и плавающей запятой При представлении числа в двоичном коде с цифрами 0,1 в каждом разряде записываются цифры 0 или 1. Так как в ЭВМ «запись» числа осуществляется с помощью технических устройств, то для представления его в такой форме необходимо располагать устройствами с двумя надежно различными состояниями, которым могут быть сопоставлены значения 0 или 1. Комбинация таких устройств, число которых соответствует количеству разрядов записываемого числа, может быть использована для представления чисел в ЭВМ. В качестве таких устройств, могут быть использованы триггеры. Набор триггеров, предназначенных для представления чисел в ЭВМ, а также для выполнения над ними некоторых логических преобразований, называется регистром. Разумеется, число разрядов, отведенное для записи числа, соответствующее числу триггеров, в ЭВМ всегда конечно. Выбор количества разрядов для представления чисел в ЭВМ является одним из самых ответственных этапов конструирования вычислительной машины и обуславливается целым рядом требований, среди которых одно из важнейших – необходимая точность вычислений. В ЭВМ применяются две основные формы представления чисел: полулогарифмическая – с плавающей запятой и естественная – с фиксированным положением запятой. При представлении чисел с фиксированной запятой положение запятой закрепляется в определенном месте относительно разрядов числа и сохраняется неизменным для всех чисел, изображаемых в данной разрядной сетке. Обычно запятая фиксируется перед старшим разрядом или после младшего. В первом случае в разрядной сетке могут быть представлены только числа, которые по модулю меньше 1, во втором – только целые числа. Использование представления чисел с фиксированной запятой позволяет упростить схемы машины, повысить ее быстродействие, но представляет определенные трудности при программировании. В настоящее время представление чисел с фиксированной запятой используется как основное только в микроконтроллерах. В универсальных ЭВМ основным является представление чисел с плавающей запятой. Широкий диапазон представления чисел с плавающей запятой удобен для научных и инженерных расчетов. Для повышения точности вычислений во многих ЭВМ предусмотрена возможность использования формата двойной длины, однако при этом происходит увеличение затрат памяти на хранение данных и замедляются вычисления. Рассмотрим подробнее эти два формата. 5.1.1 Числа с фиксированной запятой Формат для чисел с запятой, фиксированной перед старшим разрядом. В этом формате могут быть с точностью до [pic] представлены числа (правильные дроби) в диапазоне [pic]. Первые ЭВМ были машинами с фиксированной запятой, причем запятая фиксировалась перед старшим разрядом числа. В настоящее время, как правило, форму с фиксированной запятой применяют для представления целых чисел (запятая фиксирована после младшего разряда). Используют два варианта представления целых чисел: со знаком и без знака. В последнем случае все разряды разрядной сетки служат для представления модуля числа. В ЕС ЭВМ применяются оба указанных варианта представления целых чисел, причем каждый из вариантов реализуется как в формате 32-разрядного машинного слова этих машин, так и в формате 16- разрядного полуслова. При выполнении арифметических действий над правильными дробями могут получаться двоичные числа, по абсолютной величине больше или равные единице, что называется переполнением разрядной сетки. Для исключения возможности переполнения приходится масштабировать величины, участвующие в вычислениях. Достоинство представления чисел в форме с фиксированной запятой состоит в простоте выполнения арифметических операций. Недостатки – в необходимости выбора масштабных коэффициентов и в низкой точности представления с малыми значениями модуля (нули в старших разрядах модуля приводит к уменьшению количества разрядов, занимаемых значащей частью модуля числа). 5.1.2 Числа с плавающей запятой При использовании плавающей запятой число состоит из двух частей: мантиссы m, содержащей значащие цифры числа, и порядка p, показывающего степень, в которую надо возвести основание числа q, чтобы полученное при этом число, умноженное на мантиссу, давало истинное значение представляемого числа: [pic] (5.1) Мантисса и порядок представляются в двоичном коде. Обычно число дается в нормализованном виде, когда его мантисса является правильной дробью, причем первая значащая цифра (единица) следует непосредственно после запятой: например, [pic] где m=0,1010; p=10; q=2 Порядок указывает действительное положение запятой в числе. Код в приведенном формате представляет значение числа в полулогарифмической форме: [pic]. Точность представления значений зависит от количества значащих цифр мантиссы. Для повышения точности числа с плавающей запятой представляются в нормализованной форме, при которой значение модуля мантиссы лежит в пределах [pic]. Признаком нормализованного числа служит наличие единицы в старшем разряде модуля мантиссы. В нормализованной форме могут быть представлены все числа из некоторого диапазона за исключением нуля. Нормализованные двоичные числа с плавающей запятой представляют значения модуля в диапазоне: [pic], где [pic] – максимальное значение модуля порядка. Так, при p=7 [pic]–1=[pic]=63 и диапазон представления модулей нормализованных чисел: [pic], [pic] Таким образом, диапазон чисел: [pic] Для расширения диапазона представляемых чисел при фиксированной длине разрядной сетки (m+p) в качестве основания системы счисления выбирается [pic]. При этом число, представляемое в разрядной сетке, приобретает значения [pic]. Нормализованная мантисса 16-ричного числа с плавающей запятой имеет значения, лежащее в диапазоне [pic]. Признаком нормализации такого числа является наличие хотя бы одной единицы в четырех старших разрядах модуля мантиссы. Диапазон представления чисел в этом случае существенно расширяется, находясь при том же количестве разрядов в пределах от [pic] до [pic]. 5.2 Прямой, обратный и дополнительный коды. Модифицированный код При рассмотрении элементарных арифметических операций над двоичными числами мы уже коснулись темы отрицательных двоичных чисел. Теперь рассмотрим ее подробнее. Для кодирования знака двоичного числа используется старший ("знаковый") разряд (ноль соответствует плюсу, единица – минусу). Такая форма представления числа называется прямым кодом. В ЭВМ прямой код применяется только для представления положительных двоичных чисел. Для представления отрицательных чисел применяется либо дополнительный, либо обратный код, так как над отрицательными числами в прямом коде неудобно выполнять арифметические операции. Правила для образования дополнительного и обратного кода состоят в следующем: . для образования дополнительного кода отрицательного числа необходимо в знаковом разряде поставить единицу, а все цифровые разряды инвертировать (заменить 1 на 0, а 0 – на 1), после чего прибавить 1 к младшему разряду; . для образования обратного кода отрицательного числа необходимо в знаковом разряде поставить единицу, а все цифровые разряды инвертировать; . при данных преобразованиях нужно учитывать размер разрядной сетки. Прямой код можно получить из дополнительного и обратного по тем же правилам, которые служат для нахождения дополнительного и обратного кодов. В таблице 5.1 пpиведены десятичные числа и их двоичные пpедставления в тpех pазличных фоpмах. Интеpесно в ней вот что. Если начать счет с числа 1000 (–8) и двигаться вниз по столбцам, то в дополнительном коде каждое последующее число получается пpибавлением единицы к пpедыдущему без учета пеpеноса за пpеделы четвеpтого pазpяда Так пpосто эту опеpацию в пpямом и обpатном кодах не осуществить. Эта особенность дополнительного кода и явилось пpичиной пpедпочтителного пpименения его в совpеменных микpо и миниЭВМ. Итак, числа, пpедставленные в дополнительном коде, складываются по пpавилам двоичного сложения, но без учета каких либо пеpеносов за пpеделы стаpшего pазpяда. Рассмотpим это на пpимеpах 5.1. Таблица 5.1 Прямой, обратный и дополнительный коды . |Десятичное|Прямой |Обратный |Дополнительный | | |код |код |код | |число | | | | |-8 |– |– |1000 | |-7 |1111 |1000 |1001 | |-6 |1110 |1001 |1010 | |-5 |1101 |1010 |1011 | |-4 |1100 |1011 |1110 | |-3 |1011 |1100 |1101 | |-2 |1010 |1101 |1110 | |-1 |1001 |1110 |1111 | |0 |1000 |1111 |0000 | | |0000 |0000 | | |1 |0001 |0001 |0001 | |2 |0010 |0010 |0010 | |3 |0011 |0011 |0011 | |4 |0100 |0100 |0100 | |5 |0101 |0101 |0101 | |6 |0110 |0110 |0110 | |7 |0111 |0111 |0111 | Пример 5.1 Двоичное сложение в дополнительном коде |0 |0 |000 000 |0 |0000 | |1 |1 |000 001 |1 |0001 | |2 |2 |000 010 |2 |0010 | |3 |3 |000 011 |3 |0011 | |4 |4 |000 100 |4 |0100 | |5 |5 |000 101 |5 |0101 | |6 |6 |000 110 |6 |0110 | |7 |7 |000 111 |7 |0111 | |8 |10 |001 000 |8 |1000 | |9 |11 |001 001 |9 |1001 | |10 |12 |001 010 |А |1010 | |11 |13 |001 011 |В |1011 | |12 |14 |001 100 |С |1100 | |13 |15 |001 101 |D |1101 | |14 |16 |001 110 |Е |1110 | |15 |17 |001 111 |F |1111 | |16 |20 |010 000 |10 |10000 | В таблице 7.1 пpиведены числа в десятичной, восьмеpичной и шестнадцатеpичной системах и соответствующие гpуппы бит в двоичной системе. 16-pазpядное двоичное число со знаковым pазpядом можно пpедставить 6- pазpядным восьмеpичным, пpичем стаpший байт в нем будет пpинимать значения лишь 0 или 1. В шестнадцатеpичной системе такое число займет 4 pазpяда. Пример 7.1 Получение восьмеричных и шестнадцатеричных чисел [pic] Аpифметические опеpации над числами в восьмеpичной или шестнадцатеpичной системах пpоводятся по тем же пpавилам, что и в десятичной системе. Только надо помнить, что если имеет место пеpенос, то пеpеносится не после 10, а 8 или 16. Таблица 7.2 дает представление о переводе чисел в различные системы. Таблица 7.2 Перевод чисел из одной системы счисления в другую |Двоичные |Восьмеричные|Десятичные |Шестнадцатеричные| | | |числа |числа | |числа |числа | | | |0,0001 |0,04 |0,0625 |0,1 | |0,001 |0,1 |0,125 |0,2 | |0,01 |0,2 |0,25 |0,4 | |0,1 |0,4 |0,5 |0,8 | |1 |1 |1 |1 | |10 |2 |2 |2 | |11 |3 |3 |3 | |100 |4 |4 |4 | |101 |5 |5 |5 | |110 |6 |6 |6 | |111 |7 |7 |7 | |1000 |10 |8 |8 | |1001 |11 |9 |9 | |1010 |12 |10 |A | |1011 |13 |11 |B | |1100 |14 |12 |C | |1101 |15 |13 |D | |1110 |16 |14 |E | |1111 |17 |15 |F | |10000 |20 |16 |10 | В СССР в 1957 г. была построена экспериментальная модель ЭВМ "Сетунь", арифметика которой базировалась на троичной системе счисления. К сожалению, несмотря на ряд особенностей, привлекших внимание, в машине были реализованы далеко не все полезные свойства троичного кода и трехзначной логики, а также не было операций с плавающей запятой, для которых преимущества троичного кода особенно существенны. Список использованной литературы 1. Выгодский М.Я. Справочник по элементарной математике, М.: Государственное издательство технико-теоретической литературы, 1956. 2. Каган Б.М. Электронные вычислительные машины и системы, М.: Энергоатомиздат, 1985. 3. Майоров С.А., Кириллов В.В., Приблуда А.А., Введение в микроЭВМ, Л.: Машиностроение, 1988. 4. Фомин С.В. Системы счисления, М.: Наука, 1987. ----------------------- [pic] [pic] [pic] [pic] [pic] [pic] Рис. 3.1 Бит, байт и слово