- •1. Место информатики во множестве наук
- •2. Понятие об информации
- •Рассмотрим ещё одно определение понятия «информация».
- •3. Информационные процессы
- •4. Свойства информации
- •5. Операции над данными
- •6. Условия, обеспечивающие передачу информации (данных) от одного человека другому человеку и от одного поколения человечества другому поколению.
- •7. Язык
- •7.1. Типы языков
- •7.2. Стадии эволюции естественного языка:
- •7.3. Элементы языка
- •7.4. Знания
- •7.5. Некоторые особенности естественных языков
- •7.6. Некоторые особенности простых языков
- •8. Количественное измерение информации
- •9. Системы счисления
- •9.1. Основные определения
- •9.2. Непозиционные системы счисления
- •9.3. Позиционные системы счисления
- •Запись целых чисел в различных системах счисления
- •9.4. Выполнение арифметических операций в позиционных системах счисления
- •Операция «сложение»
- •Операция «вычитание»
- •Операция «умножение»
- •9.5. Преобразование кодов чисел из одной системы счисления в другую
- •9.5.1. Преобразование целой части числа
- •9.5.2. Преобразование дробной части числа
9.5. Преобразование кодов чисел из одной системы счисления в другую
Обычно говорят и пишут «перевод чисел из одной системы в другую», например, «перевод чисел из двоичной системы счисления в десятичную». Практически во всех предметных областях нередки случаи, когда вместо длинной, но точной формулировки какого-то утверждения применяется более короткая формулировка, и это допустимо. Однако при этом нельзя забывать об истинном смысле утверждения. Смысл рассматриваемой фразы состоит в том, что имеется в виду одно число, но исходными данными в задаче является код этого числа в двоичной системе счисления, а результатом, который необходимо получить путём обработки исходных данных, является другой код этого же числа в другой - десятичной системе счисления.
В общем виде задача формулируется следующим образом.
Имеется код числа Аp= ak-1ak-2ak-3…a2a1a0,a-1a-2…a-m в первичной системе счисления с основанием p. Необходимо преобразовать код этого числа в новый код Аq = bn-1bn-2bn-3…b2 b1b0,b-1b-2…b-m во вторичной системе счисления с основанием q.
9.5.1. Преобразование целой части числа
Имеются 4 системы счисления с различными основаниями: 10, 2, 8, 16. В таблице на Рис. 9.5.1.1. с помощью знака ↑ «стрелка» представлены варианты преобразований.
Например, знак ↑, находящийся в ячейке таблицы на пересечении строки, соответствующей основанию 2, и столбца, соответствующего основанию 10, указывает на преобразование кодов чисел из 2-ичной системы счисления в 10-ичную. Записи в каждой ячейке указывают на способ преобразования, которые мы рассмотрим:
ст – используется представление числа в виде степенного ряда (полинома);
Горнер – используется метод Горнера;
Основание |
10 |
2 |
8 |
16 |
10 |
× |
↑ (дел) |
↑ (дел) |
↑ (дел) |
2 |
↑ (ст, Горнер) |
× |
↑ (гр) |
↑ (гр) |
8 |
↑ (ст, Горнер) |
↑ (цифр) |
× |
↑ (комб) |
16 |
↑ (ст, Горнер) |
↑ (цифр) |
↑ (комб) |
× |
Рис. 9.5.1.1.
дел – используется операция «деление»;
гр – используется группировка цифр кода;
цифр – используется преобразование отдельно каждой цифры кода;
комб – используется комбинация из двух методов.
В данной таблице можно выделить 3 группы пар кодов:
1 группа пар кодов – один из кодов представляет собой запись числа в 10-ичной системе счисления;
2 группа пар кодов - один из кодов представляет собой запись числа в 2-ичной системе счисления;
3 группа пар кодов – 2 кода представляют собой записи числа в 8 –ичной и 16-ичной системах счисления.
Правила преобразования основываются на трёх разных видах записи полинома - развёрнутой формы записи любого числа F.
1 вид (исходная формула): F = fn-1*qn-1+ fn-2*qn-2+…+ f2*q2 +f1*q1+ f0*q0
2 вид: F = (fn-1*qn-1+ fn-2*qn-2+… + f2*q2 +f1*q1) + f0
3 вид: F = (…(( fn-1*q+fn-2)*q+fn-3)*q)+fn-4)*q)…+ f2)*q+f1)*q+ f0
Первый вид (исходная формула) является универсальным, т.е. этот вид может использоваться для любых кодов в паре. Два остальных вида устанавливают определённые процедуры преобразования кодов. В общем случае можно утверждать, что выбор того или иного вида записи и способа преобразования кодов определяется удобством выполнения преобразования для человека.
Рассмотрим решение задачи с применением второго вида развёрнутой формы записи числа. Цифры первичного кода известны: Аp= ak-1ak-2ak-3…a2a1a0. Необходимо найти цифры bi вторичного кода. С учётом решения нашей задачи вместо просто записи числа необходимо рассматривать следующее равенство:
ak-1ak-2ak-3…a2a1a0 = bn-1*qn-1+ bn-2*qn-2+…+ b2*q2 +b1*q1+ b0*q0 =
= (bn-1*qn-1+ bn-2*qn-2+… + b2*q2 +b1*q1) + b0
Это равенство показывает, что если проводить операцию деления числа в виде кода Аp= ak-1ak-2ak-3…a2a1a0 в первичной системе счисления на основание q вторичной системы счисления, то при каждой операции деления будет получаться остаток bi, равный цифре кода числа во вторичной системе счисления.
Первая операция деления (результат операции – первое частное с остатком b0):
ak-1ak-2ak-3…a2a1a0/q = (bn-1*qn-2+bn-2*qn-3+… +b2*q1+ b1*q0) + b0 /q =
= (bn-1*qn-2+ bn-2*qn-3+… +b2*q1+ b1) + b0 /q
Во второй операции деления (делимым является целая часть первого частного) результатом операции является второе частное с остатком a1:
[ak-1ak-2ak-3…a2a1a0 / q] / q = (bn-1*qn-3+ bn-2*qn-4+… +b2) + b1 /q
Таким образом, выполнив последовательно операцию деления до момента, когда целая часть текущего частного окажется меньше основания вторичной системы счисления q, мы получим в виде остатков цифры кода числа во вторичной системе счисления q. Отметим ещё раз, что деление проводится в первичной системе счисления p. Учитывая это условие, очевидно, что этот способ удобно использовать при преобразовании кода из 10-ичной системы счисления в любую другую. В таблице этот способ указывается с помощью записи «(дел)».
Проверим реализацию этого правила на примерах.
Пример 1. Преобразовать код числа 15710 из 10-ичной системы в 2-ичную (Рис. 9.5.1.2.).
|
157 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
156 |
|
78 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
78 |
|
39 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
38 |
|
19 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
18 |
|
9 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
8 |
|
4 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
4 |
|
2 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 9.5.1.2.
Стрелка на этом и последующих рисунках указывает направление «от младшего разряда к старшему».
15710 = 100111012
Пример 2. Преобразовать код числа 15310 из 10-ичной системы в 8-ичную (Рис. 9.5.1.3.).
|
153 |
|
8 |
|
|
|
|
152 |
|
19 |
|
8 |
|
|
|
|
1 |
16 |
|
2 |
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 9.5.1.3.
Результат: 15310 = 2318.
Пример 3. Преобразовать код числа 772310 из 10-ичной системы в 16-ичную (Рис. 9.5.1.4.).
|
7723 |
|
16 |
|
|
|
|
|
64 |
|
482 |
|
16 |
|
|
|
|
|
132 |
48 |
|
30 |
|
16 |
|
|
128 |
|
2 |
16 |
|
1 |
|
||
|
43 |
|
|
|
14 |
|
|
|
32 |
|
|
|
|
|
|
||
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 9.5.1.4.
Результат: 772310 = 1E2B16
Теперь рассмотрим обратное преобразование: в 10-ичную систему. Способ преобразования делением можно использовать и в данном случае, когда вторичной системой является 10-ичная. Однако в данном случае его сложно использовать, т.к. деление необходимо проводить в 2-ичной или 8-ичной или 16-ичной системе. Вспомним, деление необходимо проводить в той системе счисления, в которой записан исходный код числа.
В данном случае целесообразнее использовать третий вид развёрнутой формы записи числа. Анализируя третий вид развёрнутой формы, можно увидеть, что преобразование реализуется циклическим выполнением пары действий. Первый цикл: цифра старшего разряда кода умножается на основание исходной системы счисления и суммируется с цифрой соседнего более младшего разряда. Второй цикл: полученное в предыдущем цикле число умножается на основание исходной системы счисления и суммируется с цифрой соседнего более младшего разряда. И т.д. Операции «умножение» и «сложение» выполняются, естественно, в привычной 10-ичной системе, и результатом является число в 10-ичной системе, что и необходимо. При этих преобразованиях применяется специальная форма записи. Этот способ преобразования назван «метод Горнера» по имени автора.
Пример 4. Преобразовать код числа 100111012 из 2-ичной системы в 10-ичную (Рис. 9.5.1.5.).
Исходный код числа |
Промежуточные результаты |
Пояснение |
1 (a7) |
1 |
Записывается цифра старшего разряда |
0 (a6) |
2 |
U1 = a7*p+a6 = 1*2+0 =2 |
0 (a5) |
4 |
U2 = U1*p+a5 = 2*2+0=4 |
1 (a4) |
9 |
U3 = U2*p+a4 = 4*2+1=9 |
1 (a3) |
19 |
U4 = U3*p+a3 = 9*2+1=19 |
1 (a2) |
39 |
U5 = U4*p+a2 = 19*2+1=39 |
0 (a1) |
78 |
U6 = U5*p+a1 = 39*2+0=78 |
1 (a0) |
157 |
U7 = U6*p+a0 = 78*2+1=157 |
Рис. 9.5.1.6.
Пример 5. Преобразовать код числа 47358 из 8-ичной системы в 10-ичную (Рис. 9.5.1.7.).
Исходный код числа |
Промежуточные результаты |
Пояснение |
4 (a3) |
4 |
Записывается цифра старшего разряда |
7 (a2) |
39 |
U1 = a3*p+a2 = 4*8+7 =39 |
3 (a1) |
315 |
U2 = U1*p+a1 = 39*8+3=315 |
5 (a0) |
2525 |
U3 =U2*p+a0 =315*8+5=2525 |
Рис. 9.5.1.7.
Пример 6. Преобразовать код числа A9F516 из 16-ичной системы в 10-ичную (Рис. 9.5.1.8.).
Исходный код числа |
Промежуточные результаты |
Пояснение |
A (a3) |
A (10) |
Записывается цифра старшего разряда |
9 (a2) |
169 |
U1 = a3*p+a2 = 10*16+9 =169 |
F (a1) |
2719 |
U2 = U1*p+a1 = 169*16+15 = 2719 |
5 (a0) |
43509 |
U3 = U2*p+a0 = 2719*16+5=43509 |
Рис. 9.5.1.8.
При преобразовании в 10-ю систему счисления можно использовать исходную развёрнутую запись кода числа виде степенного ряда (полинома):
ak-1ak-2ak-3…a2a1a0 = ak-1*pk-1+ ak-2*pk-2+…+ a2*p2 +a1*p1+ a0*p0
и проводить вычисления в 10-ичной системе счисления.
Пример 7. Преобразовать код числа 100111012 из 2-ичной системы в 10-ичную.
100111012 = 1*27+1*24+1*23+1*22+1 = 128+16+8+4+1 = 157
Пример 8. Преобразовать код числа 47358 из 8-ичной системы в 10-ичную.
47358 = 4*83+7*82+3*8+5 = 4*512+7*64+24+5 = 2048+448+24+5 = 2525
Пример 9. Преобразовать код числа A9F516 из 16-ичной системы в 10-ичную.
A9F516 = 10*163+9*162+15*16+5 = 10*4096+9*256+240+5 = 43509
Теперь рассмотрим преобразование для второй группы пар кодов: 8→2, 16→2, 2→8, 2→16.
Особенность этих трёх систем состоит в том, что системы с основаниями 8=23 и 16=24 являются кратными для 2-ичной системы счисления. На этом основаны способы преобразования. Пусть исходный код числа А представлен в 8-ичной системе счисления:
А8 = ak-1*8k-1+ ak-2*8k-2+…+ a2*82 +a1*81+ a0*80
Каждая цифра ai <=7. Это значит, что каждую цифру первичного кода можно представить в двоичном коде или .
Для простоты рассмотрим в 8-ичной системе трёхразрядное число A8=a2a1a0.
В этом выражении все цифры записаны в 2-ичной системе счисления: bi<=1. Приведя подобные члены, можно получить следующее выражение:
A2= b8*28+ b7*27+b6*26+ b5*25+ b4*24 +b3*23+ b2*22 +b1*21+ b0
Обратите внимание на следующее обстоятельство: цифра в старшем разряде первичного кода может быть меньше 4. Это значит, что в двоичном коде она представляется только двумя разрядами. Это очень важное обстоятельство, определяющее преобразование 2→8, 2→16.
Правило преобразования кода числа из 8-ичной системы в 2- ичную: каждую цифру 8-ичного кода представить кодом в двоичной системе счисления.
Правило преобразования кода числа из 16-ичной системы в 2- ичную: каждую цифру 16-ичного кода представить кодом в двоичной системе счисления в виде 4 разрядов.
Пример 10. Преобразовать код числа 17358 из 8-ичной системы в 2-ичную.
Каждую цифру восьмеричного кода записываем в двоичном коде:
17358=001 111 011 1012 = 11110111012
Для удобства чтения первая запись двоичного кода выполнена со знаками «пробел». В последней записи удалены незначащие цифры «0» в двух старших разрядах.
Пример 11. Преобразовать код числа 69F516 из 16-ичной системы в 2-ичную.
69F516= 0110 1001 1111 01012 =1101001111101012
Правило преобразования кода числа из 2-ичной системы в 8- ичную: начиная с младшего разряда, сгруппировать цифры 2-ичного кода по три (в триады), затем каждую тройку цифр (триаду) 2-ичного кода представить кодом цифры в 8-ичной системе счисления.
Правило преобразования кода числа из 2-ичной системы в 16- ичную: начиная с младшего разряда, сгруппировать цифры 2-ичного кода по четыре (в тетрады), затем каждую четвёрку цифр (тетраду) 2-ичного кода представить кодом цифры в 16-ичной системе счисления.
Пример 12. Преобразовать код числа 11110111012 из 2-ичной системы в 8-ичную.
Код числа разбиваем на триады, начиная с младшего разряда.
1001110111012 =1 111 011 1012 = 17358
Пример 13. Преобразовать код числа 1101001111101012 из 2-ичной системы в 16-ичную.
Код числа разбиваем на четвёрки цифр, начиная с младшего разряда.
1101001111101012 = 110 1001 1111 01012 = 69F516
Рассмотрим преобразования для последней группы пар кодов: 8→16, 16→8.
Наиболее удобный для человека способ – это 2-этапная процедура: на первом этапе провести преобразование в 2-ичную систему, а затем в необходимую вторичную систему.
Пример 14. Преобразовать код числа 17358 из 8-ичной системы в 16-ичную.
17352=1 111 011 1012 = 11110111012 = 11 1101 11012 = 3DD16
Пример 15. Преобразовать код числа 69F516 из 16-ичной системы в 8-ичную.
69F516= 110 1001 1111 01012 =1101001111101012 = 110 100 111 110 1012 = 647658