Теоретические основы использования систем счисления в процессе кодирования информации

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

1.2. Позиционные и  непозиционные системы  счисления 

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

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

        I обозначает 1, V - 5, X - 10, L - 50, C - 100, D - 500, M -1000.

      Натуральные числа записываются при помощи повторения этих цифр.

      Например, II = 1 + 1 = 2, здесь символ I обозначает 1 независимо от места в числе.

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

      Пример: число 1988. Одна тысяча M, девять сотен CM, восемьдесят LXXX, восемь VIII. Запишем  их вместе: MCMLXXXVIII.

      MCMLXXXVIII = 1000+(1000-100)+(50+10+10+10)+5+1+1+1 = 1988

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

      Запись произвольного числа X в позиционной системе счисления основывается на представлении этого числа в виде развёрнутой формы:

      X = a_nKⁿ+a_n-1K^n-1+…+a₁K¹+a₀K⁰+a_-1K^-1+…+a_-mK^-m+…, где каждый коэффициент a_i может быть одним из базисных чисел и изображается одной цифрой [9,40].

      Примером позиционной системы счисления служит двоичная, троичная,…,шестнадцатеричная,… системы счисления.

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

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

      В восьмеричной системе счисления базисными числами являются 0,1,2,3,4,5,6,7. Запись любого числа в этой системе основывается на его разложении по степеням числа восемь с коэффициентами, являющимися указанными  выше базисными числами [9,41].

      Например, десятичное число 83,5 в восьмеричной системе счисления будет изображаться в виде 123,4. Действительно, эта запись по определению означает представление числа в виде полинома:

      123,4₈ =1×8²+2×8¹+3×8⁰+4×8^-1 = 64+16+3+4/8 = 83,5₁₀.

      В шестнадцатеричной системе счисления  базисными являются числа от нуля до пятнадцати. Эта система отличается от рассмотренных ранее тем, что  в ней общепринятых (арабских) цифр не хватает для обозначения всех базисных чисел, поэтому приходиться  вводить в употребление новые символы. Обычно для обозначения первых десяти целых чисел  от нуля до десяти используют арабские цифры, а для следующих целых чисел о т десяти до пятнадцати используются буквенные обозначения A,B,C,D,E,F.

      Например, десятичное число 175,5 в шестнадцатеричной системе будет записываться в виде AF,8. Действительно, AF,8₁₆=10×16¹+15×16⁰+8×16^-1 = 160+15+8/16 = 175,5₁₀. Отсюда следует, что 175,5₁₀= AF,8₁₆

      Алфавит – это множество символов, используемых для записи числа.

      Количество  используемых цифр называется основанием системы счисления. Основание принято располагать справа от числа, используя подстрочный индекс. В данном примере AF,8₁₆ основанием является число 16.  

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

 

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

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

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

 

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

      Например:

      Возьмём число 1 0 1, 1 0 1₂, в нём 6 цифр. Запишем его в развёрнутом виде, т.е. умножим каждую цифру этого числа на соответствующую степень двойки и затем сложим эти произведения. Удобно расставить номера над цифрами. 

2   1  0   -1  -2 -3

1 0 1, 1 0 1

      101,101₂=1×2²+0×2¹+1×2⁰+1×2^-1+0×2^-2+

      +1×2^-3=1×4+0×2+1×1+1×¹/₂+0×¹/₄+1×¹/₈=4+0+1+0,5+0+0,125=5,625₁₀

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

      Возьмём любое двоичное число, например 10,11₂. Запишем его в развёрнутой форме и произведём вычисления:

      10,11₂ = 1×2¹ + 0×2⁰ + 1×2^-1 + 1×2^-2 = 1×2+0×1+1×1/2+1×1/4 = 2,75₁₀.

      Аналогично  осуществляется перевод целого двоичного  числа в десятичную систему счисления. Рассмотрим это на примере:

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

      11001101₂=1×2⁷+1×2⁶+0×2⁵+0×2⁴+1×2³+1×2²+0×2¹+1×2⁰=128+64+0+0+8+4+0+1=205₁₀ [9,40]

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

      Например:  95₁₆ = 9×16¹+5×16⁰=144+5=149₁₀ 

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

 

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

      Действуем так:

      20:2=10 (ост.0)

      10:2=5 (ост.0)

      5:2=2           (ост.1)

      2:2=1           (ост.0)

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

        _20 |  2 

          20   10|   2

             0  10   5 |  2

                   0     4    2|  2

         1    2    1

                  0 
 

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

      10100₂

      Это и будет искомое представление.

      Проверим: 10100₂=1×2⁴+0×2³+1×2²+0×2¹+0×2⁰ = 16+0+4+0+0 = 20₁₀

      Итак, 10100₂ = 20₁₀ [10,106].

      Преобразование  из десятичной в прочие системы счисления  производятся в соответствии  с правилами умножения и деления. При этом целая и дробная части переводятся отдельно. Рассмотрим алгоритм перевода на примере целого числа 137 в двоичную систему. Разделим его нацело на 2, получим 137:2 = 68, остаток 1. Полученный результат можно записать следующим образом: 137=68×2¹+1×2º. Продолжим операцию деления дальше.

      68:2=34, остаток 0,

      137=(34×2+0) ×2¹+1×2º = 34×2²+0×2¹+1×2º;

      34:2=17, остаток 0,

      137=(17×2+0) ×2²+0×2¹+1×2º= 17×2³+0×2²+0×2¹+1×2º;

      17:2=8, остаток 1,

      137= (8×2+1) ×2³+0×2²+0×2¹+1×2º=8×2⁴+1×2³+0×2²+0×2¹+1×2º;

      8:2=4, остаток 0,

      137=(4×2+0)×2⁴+1×2³+0×2²+0×2¹+1×2º=4×2⁵+0×2⁴+1×2³+0×2²+0×2¹+

      +1×2º;

      4:2 = 2, остаток 0,

      137=(2×2+0)×2⁵+0×2⁴+1×2³+0×2²+0×2¹+1×2º=2×2⁶+0×2⁵+0×2⁴+1×2³+0×2²+0×2¹+1×2⁰;

      2:2 = 1, остаток 0,

      137=(1×2+0)×2⁶+0×2⁵+0×2⁴+1×2³+0×2²+0×2¹+1×2⁰=1×2⁷+0×2⁶+0×2⁵+0×2⁵+1×2⁴+0×2³+0×2²+0×2¹+1×2⁰

      Далее процесс продолжать нельзя, т.к. 0 не делится нацело на 2. Таким образом, последовательное деление нацело на 2 позволяет разложить число по степеням двойки, а это в краткой  записи и есть двоичное изображение числа: 137₁₀ = 10001001₂. Все приведённые выкладки можно сократить, записав процесс деления в виде следующей схемы:

               

      _137|2

        136|68|2                                      

             1 68| 34| 2

      0  34| 17| 2

                           0  16| 8| 2

                                 1 8| 4| 2

        0  4| 2| 2

 0 2| 1

                                             0  

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