из электронной библиотеки / 93525013187900.pdf

Тема 1. Системы счисления. Двоичная, восьмеричная, десятичная, шестнадцатеричная системы счисления

Представление о системах счисления

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

Но, тем не менее, числа люди все равно как-то записывали. У каждого народа была своя собственная или позаимствованная у соседа система записи чисел. Одни использовали буковки, другие - значки, третьи - закорючки. У кого-то получалось удобнее, у кого-то не очень.

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

Система счисления - очень сложное понятие. Оно включает в себя все законы, по которым числа записываются и читаются, а так же те, по которым производятся операции над ними.

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

Такая система счисления использовалась, и до сих пор используется в основном народами, не имеющими письменности. Но это удобно, пока числа небольшие. Трудно представьте себе число 1 000 записанное с помощью кучки камушков или 1 000 000.

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

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

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

должны выглядеть по-разному. Например в Египте единицы записывали палочками ,

а десяток палочек заменяли на изображение пут для коров, десяток пут - одна мерная

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

Такая система счисления уже годится для записи чисел, но она крайне неудобна для счета.

Такой системой счисления пользовались египтяне, ацтеки, племена майя.

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

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

61

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

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

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

Но далеко не все народы делали свои записи с помощью алфавита или слоговых знаков. В Китае иероглифы не позволили появиться такой системе счисления, и тогда ученые изобрели немного другую систему, названную мультипликативная система счисления. Эта система имела одно очень важное свойство: в ней одна и та же цифра, в зависимости от расположения в записи числа могла иметь разные значения. Именно такой системой счисления мы сейчас и пользуемся.

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

Например 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 11, 12, …, 99, 100, 101 …

Запись числа 1999 означает, что 1*1000 + 9*100 + 9*10 + 9. Для того, чтобы "собрать" такое число используется умножение (multiplication англ.), из-за чего систему и назвали "мультипликативной".

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

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

Впервые такая система, вернее ее зачатки появилась в Древнем Вавилоне, почти в то же время она была изобретена в Китае, потом в Индии, откуда перекочевала на Аравийский полуостров, а затем и в Европу. Здесь эту систему счисления назвали арабской, и под этим именем она разошлась по всему миру. Так что, говоря «арабские числа» надо иметь в виду, ну, хотя бы индийские.

Понятие системы счисление

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

чисел.

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

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

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

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

62

Для того чтобы лучше понять различие позиционной и непозиционной систем счисления, рассмотрим пример сравнения двух чисел. В позиционной системе счисления сравнение двух чисел происходит следующим образом: в рассматриваемых числах слева направо сравниваются цифры, стоящие в одинаковых позициях. Большая цифра соответствует большему значению числа. Например, для чисел 123 и 234, 1 меньше 2, поэтому число 234 больше, чем число 123. В непозиционной системе счисления это правило не действует. Примером этого может служить сравнение двух чисел IX и VI. Несмотря на то, что I меньше, чем V, число IX больше, чем число VI.

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

нижним индексом. Например, 5557 - число, записанное в семеричной системе счисления. Если число записано в десятичной системе, то основание, как правило, не указывается.

Вообще, число x может быть представлено в системе с основанием p, как x=an*pn+an-1*pn-1+ a1*p1+a0*p0,

где an...a0 - цифры в представлении данного числа. Так, например,

103510=1*103+0*102+3*101+5*100; 10102 = 1*23+0*22+1*21+0*20 = 10.

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

Наибольший интерес при работе на ЭВМ представляют системы счисления с основаниями 2, 8 и 16. Вообще говоря, этих систем счисления обычно хватает для полноценной работы как человека, так и вычислительной машины.

Вповседневной жизни мы привыкли пользоваться десятичной системой счисления,

инам не требуется никакая другая. Люди предпочитают десятичную систему, вероятно, потому, что с древних времен считали по пальцам, а пальцев у людей по десять на руках и ногах. Не всегда и не везде люди пользуются десятичной системой счисления. В Китае, например, долгое время пользовались пятеричной системой счисления.

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

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

представление информации посредством только двух состояний надежно и помехоустойчиво;

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

двоичная арифметика намного проще десятичной.

Недостаток двоичной системы — быстрый рост числа разрядов, необходимых для записи чисел.

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

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

Основные позиционные системы счисления

63

Двоичная система счисления.

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

Восьмеричная система счисления. Использует восемь цифр – 0, 1, 2, 3, 4, 5, 6, и 7, а также символы + и – для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. Широко использовалась в программировании в 1950-70-ые гг. К настоящему времени практически полностью вытеснена шестнадцатеричной системой счисления, однако функции перевода числа из десятичной системы в восьмеричную и обратно сохраняются в микрокалькуляторах и многих языках программирования.

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

Например, 5028 = 101 000 0102

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

Например, 1 111 1102 = 001 111 1102 = 1768

Десятичная система счисления. Использует десять обычных цифр – 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9, а также символы + и – для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа.

Шестнадцатеричная система счисления. Использует шестнадцать цифр – 0, 1, 2, 3,

4, 5, 6, 7, 8 и 9 в их обычном смысле, а затем B=11 ,C=12, D=13, E=14, F=15 . Также использует символы + и – для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. Внедрена американской корпорацией IBM. Широко используется в программировании для IBM-совместимых компьютеров.

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

Основные системы счисления

000

001

010

64

Перевод чисел из десятичной системы счисления в систему с основанием P

При переводе чисел из десятичной системы счисления в систему с основанием P > 1 обычно используют следующий алгоритм:

1)если переводится целая часть числа, то она делится на P, после чего запоминается остаток от деления. Полученное частное вновь делится на P, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на P выписываются в порядке, обратном их получению;

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

Целые части выписываются после двоичной запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая двоичная дробь. Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием P.

Пример: Перевести данное число из десятичной системы счисления в двоичную: а)

464(10); б) 380,1875(10);

65

а) 464(10) = 111010000(2); б) 380,1875(10) = 101111100,0011(2);

Если необходимо перевести число из двоичной системы счисления в систему счисления, основанием которой является степень двойки, достаточно объединить цифры двоичного числа в группы по столько цифр, каков показатель степени, и использовать приведенный ниже алгоритм. Например, если перевод осуществляется в восьмеричную систему, то группы будут содержать три цифры (8 = 23). Итак, в целой части будем производить группировку справа налево, в дробной — слева направо. Если в последней группе недостает цифр, дописываем нули: в целой части — слева, в дробной — справа. Затем каждая группа заменяется соответствующей цифрой новой системы.

Пример: Переведем из двоичной системы в шестнадцатеричную число

1111010101,11(2).

0011 1101 0101,1100(2) = 3D5,C(16).

При переводе чисел из системы счисления с основанием P в десятичную систему счисления необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и в дробной части, начиная с разряда сразу после запятой слева направо (начальный номер -1). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления.

Пример: Перевести данное число в десятичную систему счисления.

а) 1000001(2).

1000001(2)=1× 26+0× 25+0× 24+0× 23+0× 22+ 0× 21+1× 20 = 64+1=65(10).

Замечание. Очевидно, что если в каком-либо разряде стоит нуль, то соответствующее слагаемое можно опускать.

б) 1000011111,0101(2).

1000011111,0101(2)=1×29 + 1×24 + 1×23 + 1×22 + 1×21 + 1×20 + 1×2-2 + 1×2-4 = 512 + 16 + 8 + 4 + 2 + 1 + 0,25 + 0,0625 = 543,3125(10).

в) 1216(8).

1216,04(8)=1×83+2×82+1×81+6×80 = 512+128+8+6

г) 29A5(16).

29A5(16) = 2×162+9×161+10×160 = 512+144+10.

Тема 2.2. Кодирование информации. Представление информации в компьютере

Понятие кодирования

Кодирование информации - процесс представления информации в виде кода.

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

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

Например, при вводе в компьютер каждая буква кодируется определенным числом, а при выводе на внешние устройства (экран или печать) для восприятия человеком по

66

этим числам строятся изображения букв. Соответствие между набором букв и числами называется кодировкой символов.

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

соответственно, надо знать определенные правила - законы записи этих кодов, т.е. уметь кодировать.

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

Кодировать информацию можно различными способами: устно, письменно, жестами или сигналами любой другой природы.

Представление числовой информации в компьютере Существуют два основных формата представления чисел в памяти компьютера.

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

Целые числа без знака

Обычно занимают в памяти компьютера один или два байта. В однобайтовом формате принимают значения в двоичной системе счисления от 000000002 до 111111112, что эквивалентно в десятичной системе счисления от 0 до 255.

В двубайтовом формате — от 00000000 000000002 до 11111111 111111112, от 0

до 65535.

Пример.

Получить внутреннее представление целого числа 1607 в 2-х байтовой ячейке. Переведем число в двоичную систему: 160710 = 110010001112. Внутреннее

представление этого числа в ячейке будет следующим: 0000 0110 0100 0111. число 7210 = 10010002 в однобайтовом формате:

это же число в двубайтовом формате:

число 65535 в двубайтовом формате:

Целые числа со знаком

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

Диапазон значений целых чисел со знаком в однобайтовом формате от –128 до 127, в двухбайтовом формате от –32768 до 32767.

Рассмотрим особенности записи целых чисел со знаком на примере однобайтового формата, при котором для знака отводится один разряд, а для цифр абсолютной величины

– семь разрядов.

Для записи внутреннего представления целого отрицательного числа (-N) необходимо:

1)получить внутреннее представление положительного числа N;

2)построить обратный код этого числа заменой 0 на 1 и 1 на 0;

3)полученному числу прибавить 1.

Пример.

Получим внутреннее представление целого отрицательного числа -1607. Воспользуемся результатом предыдущего примера и запишем внутреннее представление

67

положительного числа 1607: 0000 0110 0100 0111. Инвертированием получим обратный код: 1111 1001 1011 1000. Добавим единицу: 1111 1001 1011 1001 - это и есть внутреннее двоичное представление числа -1607.

Числа с плавающей точкой

Любое действительное число можно записать в стандартном виде M*10p, где

1<=M<10, p - целое.

Например, 120100000=1,201*108 . Поскольку каждая позиция десятичного числа отличается от соседней на степень числа 10, умножение на 10 эквивалентно сдвигу десятичной запятой на одну позицию вправо. Аналогично деление на 10 сдвигает десятичную запятую на позицию влево. Поэтому приведенный выше пример можно продолжить: 120100000=1,201*108 = 0,1201*109 = 12,01*107 ... Десятичная запятая "плавает" в числе и больше не помечает абсолютное место между целой и дробной частями.

В приведенной выше записи М называют мантиссой числа, а р - его порядком.

Чаще всего в ЭВМ используют нормализованное представление числа в форме с плавающей точкой. Мантисса в таком представлении должна удовлетворять условию: 1 <=М < 2.

Алгоритм для получения представления действительного числа в памяти ЭВМ:

1.Перевести модуль данного числа в двоичную систему счисления;

2.Нормализовать двоичное число, т.е. записать в виде М*2р , где М - мантисса (ее целая часть равна 1(2) и р - порядок, записанный в десятичной системе счисления;

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

4.Учитывая знак заданного числа (0 - положительное; 1 - отрицательное), выписать его представление в памяти ЭВМ.

Пример.

Запишем код числа -312,3125.

1.Двоичная запись |-312,3125| = 312,3125 = 100111000,0101.

2.Имеем 100111000,0101=1,001110000101*28 .

3.Получаем смещенный порядок 8 + 1023 = 1031. Далее имеем 103110 = 100000001112

4.Окончательно

Тема 2. Логические основы ПК

Историческая справка о возникновении алгебры логики Алгебра логики — это математический аппарат, с помощью которого записывают,

вычисляют, упрощают и преобразовывают логические высказывания.

Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Логическое высказывание — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.

68

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

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

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

Употребляемые в обычной речи слова и словосочетания "не”, “и”, “или”, “если... , то”, “тогда и только тогда” и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

Над высказываниями можно выполнять следующие логические операции: отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность.

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

Определение логической формулы:

Всякая логическая переменная и символы “истина” (“1”) и “ложь” (“0”) — формулы.

Если А и В — формулы, то , (А • В), (А v В), (А ® B), (А « В) — формулы. Никаких других формул в алгебре логики нет.

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.

Из этого следует два вывода:

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

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

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

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

Логический элемент компьютера — это часть электронной логичеcкой схемы, которая реализует элементарную логическую функцию.

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и другие (называемые также вентилями), а также триггер.

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

69

Чтобы представить два логических состояния — “1” и “0” в вентилях, соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения. Например, +5 вольт и 0 вольт.

Высокий уровень обычно соответствует значению “истина” (“1”), а низкий — значению “ложь” (“0”).

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

Работу логических элементов описывают с помощью таблиц истинности.

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

1.Инверсия (отрицание). Операция отрицания высказывания х обозначается х и читается «не х» или «неверно, что х».

2.Операция конъюнкции (логическое умножение) высказываний х и у обозначается символом (), а выражение х у читается «х и у». Высказывания х и у называются членами конъюнкции.

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

Из определения операции конъюнкции и отрицания ясно, что высказывание х АХ всегда ложно.

3.Операция дизъюнкции высказываний х и у обозначается символом v, а выражение х v у читается как «х или у». Высказывания х и у называются членами дизъюнкции.

В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.

Из определения операции дизъюнкции и отрицания ясно, что высказывание х v х всегда истинно.

Операция импликации высказываний х и у обозначается символом Э, а выражение х у читается как «если х, то у». Высказывание х называют условием, или посылкой,

70