Кодирование чисел. Системы счисления.

Кодирование информации

Код - это набор условных сигналов для записи или передачи некоторых заранее определенных понятий (рис.4.1).

Рис. 4.1 Примеры систем кодирования

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

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

Различают системы счисления позиционные и непозиционные. Пример позиционной системы счисления — арабская (современная десятичная), непозиционной — римская (см. табл. 4.1).

Таблица 4.1

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

Так, в десятичной системе счисления, основание которой равно 10, различают 10 арабских цифр: 0, 1, 2, ..., 9.

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

Двоичная система счисления имеет основание 2, и, следовательно, ее алфавит состоит из двух цифр - 0 и 1; алфавит восьмеричной системы счисления составляют цифры 0, 1, 2, 3, 4, 5, 6, 7; шестнадцатеричной - десять арабских цифр от 0 до 9 и еще шесть символов - А (10), В (11), С (12), D (13), E (14), F (15).

Для любой позиционной системы счисления справедливо следующее правило формирования n-разрядного числа на основании входящих в эту систему цифр:

, (4.1)

где y – число;

q – основание системы счисления;

y_i – цифры числа;

i – номер позиции (разряда) числа, начиная с 0.

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

Код (от лат. codex) — система условных знаков (символов) для представления различной информации.

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

Каждому разряду числа можно поставить в соответствие какой-либо параметр электрического сигнала, например амплитуду. На рис. 4.2 в качестве примера приведено изображение числа 35 в виде импульсов длительностью τ с разными амплитудами (при разных системах счисления).

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

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

Рис. 4.2 Изображение числа 35 в виде сигналов при различных системах счисления

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

Обозначим произведение основания системы q на длину разряд­ной сетки N, выбранную для записи чисел в этой системе, через С:

С = qN. (4.2)

Если принять, что каждый разряд числа представлен не одним элементом с q устойчивыми состояниями, a q элементами, каждый из которых имеет одно устойчивое состояние, то показатель (4.2)определит условное количество оборудования, которое необходимо затратить на представление чисел в этой системе. В связи с этим по­казатель (4.2) называют показателем экономичности системы.

Максимальное число, которое можно изобразить в системе с основанием q:

A_{q max}=q^N-1. (4.3)

Из (4.3) можно найти требуемую длину разрядной сетки:

N=log_q(A_{q max}+1). (4.4)

Тогда для любой системы счисления С=q log_q(A_{q max}+1).

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

F= q log_q(A_2max+1)/[2×log₂(A_2max+1)], (4.5)

позволяющий сравнить любую систему счисления с двоичной.

По правилу приведения логарифмов log_a(b)=log_c(b)/log_c(a) получим:

F=(q∙ln(2))/(2∙ln(q)).(4.6)

На рис. 4.3 представлена за­висимость величины F от осно­вания системы счисления q,если функция F непрерывна. Нижняя точка графика соответ­ствует минимуму функции F,оп­ределяемому из условия dF/dq=0, что соответствует значению q=e≈2,72.

Рис. 4.4 Зависимость относительного показателя экономичности

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

Следовательно, с точки зре­ния минимальных затрат услов­ного оборудования наиболее экономичной является система счисления с основанием 3. Незначительно уступают ей двоичная и четверичная. Системы с основанием 10 и более существенно менее эффективны.

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

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

Число, записанное в позиционной системе счисления с любым основанием, переводится в десятичную систему счисления по правилу (4.1).

Пример:

A₍₁₀₎=552,25=5´10² +5´10¹+ 2´10⁰ + 2´10^-1 +5´10^-2

В десятичном числе A₍₁₀₎ цифры 5 и 2, находящиеся на разных позициях, имеют различные количественные значения, при перемещении цифры на следующую позицию ее величина изменяется в 10 раз.

A₍₁₀₎ = 102,839 = 1´10² + 0´10¹ +2´10⁰ +8´10^-1 +3´10^-2 +9´10^-3

Если вместо 10 взять любое другое натуральное число p > 1, легко построить число в системе счисления с основанием p.

Пусть, например, p = 2. В этой двоичной системе счисления употребляются только две цифры: 0 и 1.

11011,011₍₂₎ = 1´2⁴ + 1´2³ + 0´2² +1´2¹ +1´2⁰ + 0´2^-1 + 1´2^-2 = 27,375₍₁₀₎

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

A₍₁₀₎= a_n´10ⁿ + a_n-1´10^n-1 + …+a₂´10² + a₁´10¹ +a₀ ´10⁰,

где n – некоторое соответствующее неотрицательное число; числа a_n, a_n-1, …, a₂, a₁, a₀ — знаки цифр из алфавита а_i Ì {0…9}.

Запись некоторого числа в другой системе чисел. Любое число в позиционной системе счисления при любом основании q > 1 может быть записано в естественной форме

может быть представлено степенным рядом

,

где а_k — любая цифра из алфавита системы основания p, m, 1 — число позиций (разрядов) соответственно для целой и дробной частей числа. Для удобства преобразования чисел из одной системы счисления в другую степенной ряд для целой и дробной частей числа представляется эквивалентными выражениями по схеме Горнера:

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

Прибавление единицы к более старшему (k+1)–му разряду происходит, когда число, составленное из оставшихся более младших k разрядов составляет p^k - 1.

Пример: p = 2, число 0111₍₂₎+1 дает переход единицы из нулевого разряда в первый (в нулевом разряде остался 0), далее из первого во второй (в первом разряде остался 0), и далее в третий, в результате чего получится число 0111₍₂₎ + 1 = 7₍₁₀₎ +1 = 8₍₁₀₎ = 2³ = 1000₍₂₎, k = 3.

Для проверки правильности заполнения пустых клеток необходимо выполнить обратный перевод записанных чисел. Для этого нужно использовать формулу для перевода числа из системы счисления с основанием p в систему счисления с основанием 10 следующим образом. Вписанное число 221₍₃₎ =

= A₍₁₀₎ = 2´3²+2´3¹+1´3⁰ = 25, что соответствует числу, расположенному в соответствующей ячейке десятичной системы счисления.

Перевод чисел с основаниями, являющимися степенью другой системы.Если между основаниями p и q соблюдается связь р¹ = q^k , где k – целое, то каждая цифра числа с основанием p представляется k цифрами алфавита основания q. Так, если p¹ = 8¹ = q^k = 2³ или

p¹ = 27¹ = q^k = 3³ то каждая цифра p–го числа (восьмеричного или двадцатиcемиричного) представляется k (тремя) цифрами q–ричного (двоичного или троичного) числа и наоборот — каждая группа из kцифр (от запятой влево и вправо) q–ричного числа заменяется одной p–ричной цифрой (см. в таблице столбцы, выделенные жирным шрифтом и выделенные другим шрифтом).

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

1. А₍₈₎ = 407,15 = A₍₂₎=100 000 111,001 101 и обратно А₍₂₎=10 011 011,010 11 = =A₍₈₎= 233,26.

2. B₍₂₇₎ = 23D,23 = B₍₃₎=2 010 111,002 01 и обратно B₍₃₎ = 210110,22102 = B₍₉₎ = =713,836.

3. B₍₉₎ = 78.457 = B₍₃₎ = 2122.111221 и обратно B₍₃₎ = 221221001.12021 = B₍₂₇₎ = =PP1.FK

4. C₍₁₆₎ = 4F0E,1C = С₍₂₎ = 0100111100001110,00011100;

C₍₂₎= 11001101011,111101 = C₍₁₆₎ = =66B,F4

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

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

Перевод целых чисел из одной системы счисления p в другую систему с основанием q. Целое число в системе счисления p может быть представлено эквивалентным числом в системе счисления q:

A_p = A_q = (…((b_n-1q + b _n-2)q + b_n-3)­q +… +b₁)q + b₀

Задача перевода числа из одной системы счисления (p) в другую (q) заключается в отыскании значений цифр b_k числа в новой системе счисления.

Заметим, или А_p = А_q = (А_q)₁×q + b₀, где (А_q)₁ — целое частное, полученное при делении А_p на основание q, b₀ – остаток, являющийся первой младшей цифрой числа в новой системе счисления, выражен цифрами исходной системы счисления.

При следующем делении частного на основание q будут получены новое целое частное и новый остаток: А_p = А_q = (А_q)₂×q + b₁, где b₁ - вторая младшая цифра числа. Продолжая деление целых частных до нулевого значения, находят все цифры числа в новой системе.

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

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

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

3) Составить число в новой системе, начиная с последнего остатка.

Примеры.

1) Перевести число А₍₁₀₎= 53 в А₍₂₎ .

2) Перевести число А₍₁₀₎= 53 в А₍₈₎, а затем в А₍₂₎.

Перевод восьмеричного числа в двоичное проще выполнить, учитывая, что основание 8 является кубической степенью основания 2. Поэтому достаточно каждый разряд восьмеричного числа представить тремя разрядами двоичного числа: 65₍₈₎=110101₍₂₎.

3) Перевести число А₍₁₀₎= 53 в А₍₁₆₎, а затем в А₍₂₎.

Перевод шестнадцатеричного числа в двоичное проще выполнить, учитывая, что основание 16 является четвертой степенью основания 2. Поэтому достаточно каждый разряд восьмеричного числа представить четырьмя разрядами двоичного числа: 35₍₁₆₎=00110101₍₂₎.

4) Перевести число А₍₃₎= 22 в А₍₂₎.

5) Перевести число А₍₄₎= 33 в А₍₈₎.

Основание 8 в системе счисления с основанием 4 будет представлено числом 20₍₄₎.

6) Перевести число А₍₂₎= 11010 в А₍₁₀₎.

Воспользуемся основной формулой позиционной системы чисел.

11010 ₍₂₎ = 1´2⁴ + 1´2³ + 0´2² _­+1´2¹ + 0´2⁰ = 1´16 + 1´8 + 0´4 + 1´2 + 0´1 = 26₍₁₀₎

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

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

Правило перевода дробных чисел из системы счисления с основанием p в систему счисления с основанием q:

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

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

3) Составить дробную часть числа в новой системе, начиная с целой части первого произведения.

Пример.Перевести число А₍₁₀₎= 0,65625 в А₍₂₎ различными способами, используя перевод непосредственно в двоичную систему, а также через восьмеричную и шестнадцатеричную системы.

а) А₍₁₀₎ ® А_(2)­ б) А₍₁₀₎ ® А₍₈₎ ® А_(2)­ в) А₍₁₀₎ ® А₍₁₆₎ ® А_(2)­

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

Например, число А₍₁₀₎ = 0,3 в двоичной системе представляется бесконечной периодической дробью 0.01001100110011….= 0,0(1001)₍₂₎.

Перевод чисел из любой системы счисления p в десятеричную систему чисел. Перевод чисел в десятичную систему может выполняться либо по правилам перевода, либо по формулам степенного ряда, либо по формулам разложения по схеме Горнера. Рассмотрим последовательно применение этих алгоритмов на примерах.

1) Перевести число А₍₂₎= 10101101 в А₍₁₀₎.

q Выполним перевод по правилу перевода целого числа. Для этого представим новое основание системы 10 в двоичной системе: 10₍₁₀₎= 1010₍₂₎, и будем делить двоичное число на новое основание следующим образом:

По формуле степенного ряда перевод А₍₂₎= 10101101 в А₍₁₀₎ производится следующим образом:

10101101₍₂₎= 1´2⁷+ 0´2⁶ + 1´2⁵_­+0´2⁴ + 1´2³ + 1´2² _­+0´2¹ + 1´2⁰ =

= 1´128 + 0´64 + 1´32+ 0´16+ 1´8 +1´4+ 0´2+ 1´1 = 173₍₁₀₎

q Перевод А₍₂₎= 10101101 в А₍₁₀₎ по формуле Горнера:

((((((1×2+0)×2+1)×2+0)×2+1)×2+1)×2+0)×2+1=173₍₁₀₎

2) Перевести дробные числа А₍₂₎= 0,10101; B₍₈₎= 0,52; C₍₁₆₎ = 0,A8 в десятичную систему различными способами.

q Перевод по формуле степенного ряда:

А₍₂₎= 0,10101=1´2 ^-1+ 0´2 ^-2 + 1´2 ^-3+0´2 ^-4 + 1´2 ^-5 = 0,5+0,125+0,03125 = =0,65625;

В₍₈₎=0,52=5´8^-1+ 2´8^–2=0,625+0,03125= 0,65625;

С₍₁₆₎=0,А8=10´16^–1 + 8´16^–2=0,625+0,03125= 0,65625;

q Перевод по схеме Горнера:

A = ((((1×2^-1+0)×2^-1+1)×2^-1+0)×2^-1+1)×2^-1=0,65625₍₁₀₎;

B = (5×8^-1+2)×8^-1=0,65625₍₁₀₎;

C = (10×16^-1+8)×16^-1=0,65625₍₁₀₎;

q Выполним перевод по правилу перевода дробного числа. Для этого представим новое основание системы 10 в двоичной системе: 10₍₁₀₎=1010₍₂₎, в восьмеричной системе: 10₍₁₀₎=12₍₈₎, в шестнадцатеричной системе: 10₍₁₀₎=А₍₁₆₎. Умножение и сложение производится в соответствующей системе.