Системы счисления

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

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

Одна из немногих непозиционных систем счисления, которая сохранила свое значение в настоящее время, – это римская система счисления. Алфавитом ее являются несколько заглавных латинских букв: I, V, X, L, C, D и М, с помощью которых записываются соответственно числа: I=1, V=5, X=10, L=50, C=100, D=500, М=1000. Конструкциями этого алфавита являются различные натуральные числа, причем одна и та же цифра, стоящая в разных местах (позициях) числа, не меняет своего значения, например, XII=12, МСМХСIX=1999, XLVIII=48 и т.д. Здесь цифры М, С, Х, I, независимо от их расположения в числе, сохраняют свое номинальное значение.

Синтаксис, или правила записи чисел в римской системе счисления:

• если более значимая цифра стоит перед меньшей цифрой или если подряд стоящие цифры одинаковы, то они арифметически складываются, например, XXXVI=36;

• если меньшая цифра стоит перед бóльшей, то она вычитается из бóльшей, причем меньшая цифра в этом случае повторяться подряд не может, например, XL=40, CDIV=404 (но нельзя IIV=3);

• цифры M, C, X, I могут повторяться в записи числа не более трех раз подряд, а цифры D, L, V– по одному разу.

Самое большое число в этой системе, очевидно, MMMCMXCIX=3999. Для записи еще больших чисел надо расширять алфавит языка, то есть вводить новые цифры (буквы). По этой причине, а также из-за отсутствия цифры 0 римская система счисления не годится для записи действительных чисел. Теперь попробуйте перемножить два числа CLVI и LXXIV, не прибегая к переводу их в привычную для нас систему счисления. Думаю, что это вам не удастся. Сейчас римская система счисления используется в основном для обозначения веков, томов книг, на циферблатах часов и т.д. Из рассмотренного вытекают следующие недостатки непозиционных систем счисления:

• в них нельзя записать любое число;

• запись чисел громоздка и неудобна;

• арифметические операции над числами крайне затруднены.

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

Каждая цифра позиционной системы счисления несет в себе двойную нагрузку: собственное значение и значение, принимаемое ею в зависимости от позиции в числе. Например, в числе 3983763 одна и та же цифра 3 принимает значение три, три тысячи и три миллиона в зависимости от ее позиции (разряда) в числе.

Десятичная система счисления возникла приблизительно в V веке новой эры в Индии. Первыми о ней узнали арабы, которые в VII-VIII веках завоевали обширные районы Азии и Средиземноморья. Поскольку Европа узнала о ней от арабов, то алфавит десятичной системы счисления стали называть арабскими цифрами. Правила выполнения основных арифметических операций в ней впервые были разработаны выдающимся восточным математиком и астрономом Мухаммедом аль-Хорезми и описаны им в труде, который назывался “Книга о сложении и вычитании по исчислению индийцев”.

Если обозначить в позиционной системе счисления разряд числа буквой R, то любое действительное число и его значение можно представить в виде полинома:

где n – количество цифр в целой части; m – количество цифр в дробной части числа (после запятой), К – основание системы счисления, а R – любые цифры, принятые в данной системе счисления (разряды). Задавая различные значения К, можно получить множество различных позиционных систем счисления. Откуда вытекают их общие свойства:

• благодаря поразрядной организации записи чисел в позиционной системе счисления с ними легко проводить арифметические операции;

• при переходе в числе на один разряд влево (вправо) значение цифры увеличивается (уменьшается) во столько раз, чему равно основание системы;

• в позиционных системах счисления запись чисел удобна и компактна: в них можно записать любое число – сколь угодно большое или сколь угодно малое, чего нельзя сделать в непозиционных.

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

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

Во-первых, числа в электронные схемы устройств не запишешь так, как ручкой или карандашом на бумаге. Это можно сделать, если каждой цифре ставить в соответствие какое-то фиксированное состояние технического элемента, причем таких состояний должно быть десять, и они друг от друга должны резко отличаться, иначе устройство не определит, с какой цифрой имеет дело. Но, практически какой бы элемент технической базы устройств мы ни взяли, обнаруживается только два резко отличных друг от друга состояния. Примеры: магнитный элемент – намагничен/размагничен; электрический конденсатор – заряжен/разряжен; контакт реле – замкнут/разомкнут; полупроводниковый прибор – проводит/не проводит ток и т.д. Отсюда вывод: с помощью имеющихся в настоящее время технических элементов электронных устройств можно отражать только две цифры – 0 и 1. При этом информация хранится до тех пор, пока хранится состояние элемента, соответствующее ей.

Во-вторых, информацию между устройствами нужно передавать какими-то сигналами, причем устройство должно четко и однозначно определять, что один сигнал – это цифра 2, а другой сигнал – цифра 7. При использовании десятичной системы счисления таких сигналов должно быть десять, и они должны так же четко отличаться друг от друга, как и состояния элементов. Учитывая, что устройства информационной техники – это в основном электрические устройства (электронные), то из резко отличных друг от друга дискретных сигналов можно выбрать опять только два – есть импульс тока/нет импульса тока. С помощью этих сигналов можно передавать только две цифры – 1 и 0.

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

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

Здесь отличие только в том, что разряд может принимать значения 0 или 1. Например:

100111,101=39,625₁₀.

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

1001011101 (605) 1001011101 (605) 1101 (13) 1011011 (91)│1101 (13)

+ 10111011 (187)  10111011 (187) х 111 (7) - 1101 111 (7)

1100011000 (792) 110100010 (418) 1101 10011

+ 1101 - 1101

1101 1101

1011011 (91) - 1101

0000

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

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

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

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

В восьмеричной системе счисления используются первые восемь арабских цифр, и основание ее – 8=2³ – записывается в виде 10, то есть одна восьмерка и ноль единиц.

В шестнадцатеричной системе счисления используется 16 символов для записи чисел – это десять арабских цифр и шесть начальных букв латинского алфавита: 0,1,2,...,9,A,B,C,D,E,F. Основание ее – 16=2⁴ – записывается также в виде 10, то есть одна шестнадцатеричка и ноль единиц. Для обозначения шестнадцатеричных чисел обычно за числом записывают латинскую букву H или h, например, 6АВ72EDC98h.

Каждая цифра в восьмеричной системе счисления записывается тремя двоичными цифрами (2 в степени 3), а каждая цифра шестнадцатеричной системы счисления – четырьмя двоичными цифрами (2 в степени 4). Разбиение двоичного числа на триады или тетрады производится справа. Недостающие цифры слева в самой левой триаде или тетраде дополняются нулями, например: 255₁₀=11111111₂=011 111 111=377₈=1111 1111=FF₁₆.

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

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

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

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

Лекция 7