Системы счисления и основы двоичных кодировок
Двенадцатеричная система счисления - ее происхождение тоже связано со счетом на пальцах: так как четыре пальца руки (кроме большого) имеют в совокупности двенадцать фаланг, то по этим фалангам, перебирая их по очереди большим пальцем, и ведут счет от одного до двенадцати. Затем двенадцать принимается за единицу следующего разряда и так далее. В устной речи остатки двенадцатеричной системы сохранились и до наших дней: вместо того, чтобы сказать "двенадцать" часто говорят "дюжина". Многие предметы (ножи, вилки, тарелки) очень часто считают именно дюжинами, а не десятками; сервизы бывают, как правило, на двенадцать или шесть персон. Другой пример: двенадцать месяцев в году, двенадцать цифр на циферблате часов.
Восьмеричная система счисления - позиционная система счисления с основанием 8. Для представления чисел в ней используются арабские цифры. Используется всего восемь цифр - 0, 1, 2, 3, 4, 5, 6, 7.Восьмеричная система часто используется в областях, связанных с цифровыми устройствами. Характеризуется лёгким переводом восьмеричных чисел в двоичные и обратно, путём замены восьмеричных чисел на триады двоичных. Широко использовалась в программировании в 1950-70-ые гг. и вообще в компьютерной документации, однако в настоящее время почти полностью вытеснена шестнадцатеричной.
Шестидесятеричная система счисления существовала и возникла в Древнем Вавилоне. Мнения историков по поводу того, как именно возникла эта система, расходятся. Одна из гипотез, состоит в том, что произошло слияние двух племен, одно из которых пользовалось шестеричной системой счисления, я второе - десятичной. Шестидесятеричная система возникла как компромисс между этими двумя системами. Другая гипотеза состоит в том, что вавилоняне считали продолжительность года равной 360 суткам, что, естественно, связывалось с числом 60. однако это предположение тоже нельзя считать достаточно обоснованным: астрономические познания древних вавилонян были довольно значительны, поэтому следует думать, что погрешность, с которой они определяли продолжительность года, была значительно меньше, чем пять суток.
Пятеричная система счисления была распространена у ряда африканских племен. Связь этой системы со строением человеческой руки - первоначальной "счетной машины" - достаточно очевидна. В Китае принято считать пятками, причем пятки группируются в пары; получается своеобразная система счисления, в которой каждая единица четного порядка в пять, а нечетного - в два раза больше предыдущей. Однако эта система счисления с двойным основанием, отражающая счет с помощью двух рук, довольно сложна. Гораздо чаще используется чистая пятеричная система, то есть позиционная система с основанием пять.
Двадцатеричная система счисления была принята у ацтеков и майя -народов, населявших в течение многих столетий обширные области американского континента и создавших там высокую культуру, почти полностью уничтоженную испанскими завоевателями в XVI - XVII вв. Та же двадцатеричная система была принята и у кельтов, населявших Западную Европу, начиная со II в. до нашей эры.
Из пяти перечисленных выше систем счисления, сыгравших, наряду с десятичной, заметную роль в развитии человеческой культуры, все, кроме шестидесятеричной, источники которой не ясны, связаны с тем или иным способом счета по пальцам рук (или и рук, и ног), то есть имеют несомненное "анатомическое" происхождение.
Все позиционные системы с любым натуральным основанием устроены одинаково. В любой позиционной системе счисления основание записывается в виде десяти, поскольку оно есть единица второго разряда. Все натуральные числа, меньше основания, должны быть однозначными и изображаться разными знаками. Поэтому количество цифр, используемых в данной позиционной системе, совпадает с основанием системы.
1.5 Арифметические операции в различных системах счисления
1.5.1 Сложение и вычитание
В системе с основанием я для обозначения нуля и первых ρ-1 натуральных чисел служат цифры 0, 1, 2, ..., ρ - 1. Для выполнения операции сложения и вычитания составляется таблица сложения однозначных чисел.
|
+ |
0 |
1 |
2 |
|
|
|
q-1 |
|
0 |
0 |
1 |
2 |
*** |
*** |
*** |
q-1 |
|
1 |
1 |
2 |
3 |
*** |
*** |
*** |
10 |
|
2 |
2 |
3 |
4 |
*** |
*** |
*** |
11 |
|
*** |
*** |
*** |
*** |
*** |
*** |
*** |
*** |
|
q-1 |
q-1 |
10 |
11 |
*** |
*** |
*** |
1(q-2) |
Например, таблица сложения в шестеричной системе счисления:
|
+ |
0 |
1 |
2 |
3 |
4 |
5 |
|
0 |
0 |
1 |
2 |
3 |
4 |
5 |
|
1 |
1 |
2 |
3 |
4 |
5 |
10 |
|
2 |
2 |
3 |
4 |
5 |
10 |
11 |
|
3 |
3 |
4 |
5 |
10 |
11 |
12 |
|
4 |
4 |
5 |
10 |
11 |
12 |
13 |
|
5 |
5 |
10 |
11 |
12 |
13 |
14 |
Сложение
любых двух
чисел, записанных
в системе счисления
с основанием
ρ,
производится
так же, как в
десятичной
системе, по
разрядам, начиная
с первого разряда,
с использованием
таблицы сложения
данной системы.
Складываемые
числа подписываются
одно за другим
так, чтобы цифры
одинаковых
разрядов стояли
по вертикали.
Результат
сложения пишется
под горизонтальной
чертой, проведенной
ниже слагаемых
чисел. Так же
как при сложении
чисел в десятичной
системе, в случае,
когда сложение
цифр в каком-либо
разряде дает
число двузначное,
в результат
пишется
последняя
цифра этого
числа, а первая
цифра прибавляется
к результату
сложения следующего
разряда.
Например,


Можно обосновать указанное правило сложения чисел, используя представление чисел в виде
![]()
Разберем один из примеров:
3547=3*72+5*71+4*70
2637=2*72+6*71+3*70
Имеем:
(3*72+5*71+4*70) + (2*72+6*71+3*70) =
=(3+2)*72+(5+6)*7+(3+4)
=5*72+1*72+4*7+7
=6*72+4*7+7
=6*72+5*7+0
=6507
Последовательно выделяем слагаемые по степени основания 7, начиная с низшей, нулевой, степени.
Вычитание производится также по разрядам, начиная с низшего, причем если цифра уменьшаемого меньше цифры вычитаемого, то из следующего разряда уменьшаемого "занимается" единица и из полученного двузначного числа вычитается соответствующая цифра вычитаемого; при вычитании цифр следующего разряда в этом случае нужно мысленно уменьшить цифру уменьшаемого на единицу, если же эта цифра оказалась нулем (и тогда уменьшение ее невозможно), то следует "занять" единицу из следующего разряда и затем произвести уменьшение на единицу. Специальной таблицы для вычитания составлять не нужно, так как таблица сложения дает результаты вычитания.
Например,

1.5.2 Умножение и деление
Для выполнения действий умножения и деления в системе с основанием ρ составляется таблица умножения однозначных чисел.
|
* |
0 |
1 |
2 |
|
|
|
q-1 |
|
0 |
0 | 0 | |||||
|
1 |
0 | q-1 | |||||
|
2 |
0 | 1(q-1) | |||||
|
*** |
*** | *** | |||||
|
q-1 |
0 | 1(q-2) |
Например, таблица умножения в шестеричной системе счисления:
|
* |
0 |
1 |
2 |
3 |
4 |
5 |
|
0 |
0 | 0 | 0 | 0 | 0 | 0 |
|
1 |
0 | 1 | 2 | 3 | 4 | 5 |
|
2 |
0 | 2 | 4 | 10 | 12 | 14 |
|
3 |
0 | 3 | 10 | 13 | 20 | 23 |
|
4 |
0 | 4 | 12 | 20 | 24 | 32 |
|
5 |
0 | 5 | 14 | 23 | 32 | 41 |
Умножение двух произвольных чисел в системе с основанием ρ производится так же, как в десятичной системе - "столбиком", то есть множимое умножается на цифру каждого разряда множителя (последовательно) с последующим сложением этих промежуточных результатов.
Например,

При умножении многозначных чисел в промежуточных результатах индекс основания не ставится:


Деление в системах с основанием ρ производится углом, так же, как в десятичной системе счисления. При этом используется таблица умножения и таблица сложения соответствующей системы. Сложнее дело обстоит, если результат деления не является конечной ρ-ичной дробью (или целым числом). Тогда при осуществлении операции деления обычно требуется выделить непериодическую часть дроби и ее период. Умение выполнять операцию деления в ρ-ичной системе счисления полезно при переводе дробных чисел из одной системы счисления в другую.
Например:

1.6 Перевод чисел из одной системы счисления в другую
Существует много различных способов перевода чисел из одной системы счисления в другую.
Способ деления.
Пусть дано число N=an an-1. . . a1 а0 р.
Для получения записи числа N в системе с основанием h следует представить его в виде:
N=bmhm+bm-1hm-1+... +b1h+b0 (1)
где 1<bm<h-1, 0 ≤ bi ≤ h-l (i=0, 1,... ,m-l), тогда
N=bmbm-1... b1boh (2)
Из (1) получаем:
N= (bmhm-1+...+b)*h +b0 = N1h+b0, где 0≤ b0 ≤h (3)
To есть цифра b0 является остатком от деления числа N на число h. Неполное частное Nl = bmhm-1+ . . . +b1 представим в виде:
Nl = (bmhm-2 + ... + b2)h + b1 = N2h+b1, где 0≤ b2 ≤h (4)
Таким образом, цифра bi в записи (2) числа N является остатком от деления первого неполного частного N1 на основание h новой системы счисления. Второе неполное частное N2 представим в виде:
N2 = (bmhm-3+ ... +b3)h+b2, где 0≤ b2 ≤h (5)
то есть цифра b2 является остатком от деления второго неполного частного N2 на основание h новой системы. Так как не полные частные убывают, то этот процесс конечен. И тогда мы получаем Nm = bm, где bm<h, так как:
Nm-1 = bmh+bm.1 = Nmh+bm.1
Таким образом, последовательность цифр bm, bm-1 . . ,b1,b0 в записи числа N в системе счисления с основанием h есть последовательность остатков последовательного деления числа N на основание h, взятая в обратной последовательности.
Рассмотрим пример: Выполнить перевод числа 123 в шестнадцатеричную систему счисления:

Таким образом, число 12310=7(11)16 либо можно записать как 7B16
Запишем число 340227 в пятеричной системе счисления:

Таким образом, получаем, что 340227=2333315
Перевод с использованием десятичной системы счисления.
Любое число в любой системе счисления представимо в виде:
N = anpn+...+a1p+a0
Таким образом, имея запись числа в таком виде, мы легко можем перевести его в привычную нам десятичную систему счисления. Например
22095=2*53+2*52+0*51+9*50=30910
Так же, число, представленное в десятичной системе счисления, мы можем расписать по степеням любого другого основания:
2208097=2*75+2*74+0*73+8*72+0*71+9*70=388177
Таким способом можно перевести числа из одной системы в другую. Например: переведем число 6257 в 3-ичную систему счисления.
6257=6*72+2*71+5*70=6*49+2*7+5=31310
31310=1*35+0*34+2*33+1*32+2*31+1*30=1*243+2*27+1*9+2*3+1=1021203
Ответ: 625т=1021203
Систематические дроби. Перевод дробей в различные системы счисления.
Известно, что десятичная дробь отличается от целого числа только наличием запятой, отделяющей целую часть от дробной, и такое сходство не случайно.
Можно сказать, что запись дробного числа в виде десятичной дроби представляет собой перенесение общего принципа записи чисел в позиционной десятичной системе счисления на дробные числа.
В самом общем случае смешанное число, содержащее целую и дробную части, представляется в виде суммы степеней десятки и

Десятичные дроби являются частным случаем систематических дробей, которые можно строить аналогичным образом для любой позиционной системы счисления.
Например, дробь 5-1 + 6-2 + 3-3 назвать восьмеричной и записать в виде: 0,5638.
Правила арифметических действий над ρ - ичными дробями (основание системы - q) такие же, как и над десятичными, но при действиях с однозначными числами нужно пользоваться таблицами сложения и умножения для данной системы.
Следует заметить, что не всякая простая дробь может быть записана в виде конечной десятичной дроби. Это явление наблюдается и в других позиционных системах счисления. При этом одно и то же число может в одной системе счисления записываться в виде конечной дроби, а в другой - в виде бесконечной.
Например:

При переводе дробей из одной позиционной системы счисления в другую необходимо иметь в виду возможность получения бесконечных дробей.
Общее правило перевода числа в систему счисления с основанием n:
Для перевода целого числа в систему счисления с основанием n его надо последовательно делить на n (отбрасывая остатки), при переводе дроби, меньшей единицы – последовательно умножить на n (отбрасывая целые). Цифрами числа в n – ичной системе счисления в первом случае будут остатки, записанные в обратном порядке, а во втором – целые части, записанные в порядке их получения. Целые и дробные части в смешанном числе переводятся отдельно.
Пример: 378,835937510 перевести в систему счисления с основанием q=8

Итак, 378,835937510=572,6548
Быстрый перевод чисел из двоичной системы счисления в восьмеричную и шестнадцатеричную и обратно.
Перевод чисел между системами счисления, основания которых являются степенями числа 2, может производиться более простым алгоритмом.
Для записи двоичных чисел используют две цифры, то есть в каждом разряде числа возможны два варианта записи. Для записи восьмеричных чисел используется восемь цифр, то есть возможны восемь вариантов. А для записи шестнадцатеричных чисел используется 16 цифр, то есть 16 возможных вариантов.
Таким образом, для перевода целого двоичного числа в восьмеричное его нужно разбить на группы по три цифры, справа налево, а затем преобразовать каждую группу в восьмеричную цифру. Если в последней, левой, группе окажется меньше трех цифр, то нужно его дополнить нулями слева.
Пример:
100 101 000 0102
4 5 0 28
111 111 101 000 010 000 1002
7 7 5 0 2 0 48
А для перевода целого двоичного числа в шестнадцатеричное, число разбивают на группы по 4 цифры и следуют тому же алгоритму, что и с
восьмеричной системой счисления.
Например:
1001 0000 1100 0111 00012
9 0 С 7 116
Например:
1111 1001 1101 0002
F 9 D 016
Данное правило работает и наоборот, то есть любое целое число можно перевести из восьмеричной в двоичную и из шестнадцатеричной в двоичную.
Например:
| 1 | 2 | 3 | 4 | 5 | 6 | 78 |
| 001 | 010 | 011 | 100 | 101 | 110 | 1112 |
| А | B | C | D | E | F | 1 | 2 | 3 | 4 | 5 |
| 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | 0001 | 0010 | 0011 | 0100 | 0101 |
| 6 | 7 | 8 | 916 |
| 0110 | 0111 | 1000 | 10012 |
2. ИСПОЛЬЗОВАНИЕ СИСТЕМ СЧИСЛЕНИЯ В КОМПЬЮТЕРНОЙ ТЕХНИКЕ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЯХ
Столь привычная для нас десятичная система оказалась неудобной для ЭВМ. Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент с множеством состояний (колесо с девятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Наиболее просто реализуется элементы с двумя состояниями - триггеры. Поэтому естественным был переход на двоичную систему, т.е. системы по основанию 2. В этой системе всего две цифры - 0 и 1 . Каждая цифра называется двоичной (от английского binary digit - двоичная цифра). Сокращение от этого выражения привело к появлению термина бит, ставшего названием разряда двоичного числа.
Бит - это минимальная единица измерения информации (0 mini). За битом следует байт, состоящий из восьми бит, затем килобайт (кбайт) - 1024 байта, мегабайт (мбайт) - 1024 кбайта, гигобайт (гбайт) - 1024мбайт.
2.1Двоичное кодирование информации в компьютере
Для обмена информацией с другими людьми человек использует естественные языки (русский, английский, китайский и т.д.), те есть информация представляется с помощью естественных языков. В основе языка лежит алфавит, то есть набор символов (знаков, которые человек различает по их начертанию. Последовательности символов алфавита в соответствии с правилами грамматики образуют основные объекты языка -слова. Правила, согласно которым образуются предложения из слов данного языка называются синтаксисом. Необходимо от метить, что в естественных языках грамматика и синтаксис языка формируются с помощью большого количество правил, из которых существуют исключения, так как такие правила складывались исторически.
Наряду с естественными языками были разработаны формальные языки (системы счисления, язык алгебры, языки программирования и др.). Основное отличие формальных языков от естественных состоит в наличии жестких правил грамматики и синтаксиса. Эти языки были разработаны людьми, для упрощения каких-либо действий. Как, например, системы счисления были придуманы для упрощения подсчетов чего-либо.
Создатели первых компьютеров столкнулись с проблемой представления и обработки информации. Так как компьютер это всего лишь машина у которой нет ни интеллекта, ни логики, и мыслить она не способна, разработчикам пришлось найти такой способ представления информации, который был бы максимально прост для восприятия компьютером. Столь привычная для нас десятичная система оказалась неудобной для ЭВМ. Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент с множеством состояний (колесо с девятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Наиболее просто реализуется элементы с двумя состояниями - триггеры. Поэтому естественным был переход на двоичную систему, т.е. системы по основанию 2. В этой системе всего две цифры - 0 и 1 . Каждая цифра называется двоичной (от английского binary digit - двоичная цифра). Сокращение от этого выражения привело к появлению термина бит, ставшего названием разряда двоичного числа.
Бит - это минимальная единица измерения информации (0 или1). За битом следует байт, состоящий из восьми бит, затем килобайт (кбайт) - 1024 байта, мегабайт (мбайт) - 1024 кбайта, гигобайт (гбайт) - 1024мбайт.
Таким образом, в компьютере для представления информации используется двоичное кодирование, так как удалось создать надежные работающие технические устройства, которые могут со стопроцентной надежностью сохранять и распознавать не более двух различных состояний (цифр). Все виды информации в компьютере кодируются на машинном языке, в виде логических последовательностей нулей и единиц.
Таким образом, информация представляется в виде конечной последовательности 0 и 1. Например целое неотрицательное число А2=Т 111100002 будет храниться в ячейке следующим образом:
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Значит, мы можем записать все числа от 0 до 255 в двоичной системе счисления в 1 ячейке памяти.
2.2 Представление чисел в компьютере
Целые числа в компьютере хранятся в ячейках памяти, в этом случае каждому разряду ячейки памяти соответствует всегда один и тот же разряд числа.
Для хранения целых неотрицательных чисел отводится одна ячейка памяти состоящая из восьми бит.
Например, число 1910 будет выглядеть:
| 0 | о | 0 | 1 | 0 | 0 | 1 | 1 |
Для хранения целых чисел со знаком (отрицательных) отводиться две ячейки памяти (16 битов), причем старший (левый) разряд отводиться под знак числа (если число положительное, то в знаковый разряд записывается 0, если отрицательное - 1).
Например, число -9810 будет выглядеть:
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
Представление целых чисел в компьютере в формате «знак - величина» называется прямым кодом числа. Например, число 200210=111110100102 будет представлено в шестнадцатиразрядном представлении следует следующим образом:
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
Для представления отрицательных чисел используется дополнительный код. Дополнительный код позволяет заменить арифметическую операцию
вычитания операцией сложения, что существенно упрощает работу процессора и увеличивает его быстродействие. Дополнительный код представляет собой дополнение модуля отрицательного числа А до О,
2n-|А|+|А| =0
поскольку в компьютерной 2n=0.
Алгоритм построения такого кода довольно прост:
1. Записать модуль числа в прямом коде.
2. Получить обратный код числа (то есть заменить все нули на единицы, а все единицы на нули).
3. К полученному результату прибавить единицу.
Запишем дополнительный код отрицательного числа -2002 для 16-разрядного представления:

Запишем дополнительный код отрицательного числа -16320 для 16-разрядного представления:

2.3 Способы построения двоичных кодов
Начиная с конца 60-х годов, компьютеры все больше использовать для обработки текстовой информации и в настоящее время большая часть компьютеров в мире занято именно обработкой текстовой информации.
Традиционно для кодирования одного символа используется количество информации равное 1 байту, то есть 8 бит. Если рассматривать символы как возможные события, то получаем, что количество различных символов, которые можно закодировать, будет равно 256. Такое количество символов вполне достаточно для представления текстовой информации, включая прописные и строчные буквы русского и латинского алфавитов, а так же цифры, знаки препинания и математических операций, графические символы и так далее.
Но способов построения таких кодов очень много, рассмотрим некоторые из них:
Алфавитное неравномерное двоичное кодирование
При алфавитном способе двоичного кодирования символы некоторого первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Оптимизировать кодирование можно за счет суммарной длительности сообщения.
Суммарная длительность сообщения будет меньше, если применить следующий подход: чем буква первичного алфавита, встречается чаще, то присваиваем ей более короткой по длине код. Следовательно, коды букв, вероятность появления которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов.
Возможны различные варианты двоичного кодирования, однако, не все они будут пригодны для практического использования - важно, чтобы закодированное сообщение могло быть однозначно декодировано, т.е. чтобы в последовательности 0 и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв.
Рассмотрим пример построения двоичного кода для символов русского алфавита:


Неравномерный код с разделителями
Для того что бы было проще декодировать сообщения был придуман код с разделителями.
Проще всего достичь однозначного декодирования, если коды будут разграничены разделителем - некоторой постоянной комбинацией двоичных знаков. Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов - 000 (признак конца слова - пробел). Довольно очевидными оказываются следующие правила построения кодов:
— код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);
— коды букв не должны содержать двух и более нулей подряд в
середине (иначе они будут восприниматься как конец знака);
— код буквы (кроме пробела) всегда должен начинаться с 1;
— разделителю слов (000) всегда предшествует признак конца знака;
при этом реализуется последовательность 00000 (т.е. если в конце кода встречается комбинация ...000 или ...0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на