Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Двоичное кодирование информации.
Для представления информации в компьютере используется двоичное кодирование, т.к. технические устройства компьютера могут сохранять и распознавать не более двух различных состояний (цифр): намагничен / размагничен (участок поверхности магнитного носителя информации), отражает/не отражает (участок поверхности лазерного диска); и т.д.
Информация на компьютере представлена в машинном коде, алфавит которого состоит из цифр (0 и 1). Каждая цифра машинного кода несет информацию в 1 бит.
Системы счисления
Система счисления – это знаковая система, в которой числа записываются по определенным правилам с помощью символов некоторого алфавита, называемыми цифрами.
Системы счисления делятся на непозиционные и позиционные.
Непозиционная система счисления – система счисления, в которой значение цифры не зависит от ее позиции в записи числа.
Примеры непозиционных систем счисления: унарная (единичная) система счисления, римская система счисления, алфавитная система счисления.
Унарная (единичная) система счисления характеризуется тем, что в ней для записи чисел применяется только один вид знаков – палочка. Каждое число в этой системе счисления обозначалось с помощью строки, составленной из палочек, количество которых равнялось обозначаемому числу. Неудобства такой системы счисления очевидны: это громоздкость записи больших чисел, значение числа сразу не видно, чтобы его получить, нужно сосчитать палочки.
В римской системе счисления для обозначения чисел используются заглавные латинские буквы, являющиеся «цифрами» этой системы счисления:
|
1 |
5 |
10 |
50 |
100 |
500 |
1000 |
|
I |
V |
X |
L |
C |
D |
M |
Число в римской системе счисления обозначается набором стоящих подряд «цифр». Значение числа равно:
Примеры.
1. Число 32 в римской системе счисления имеет вид:
XXXII = (X+X+X)+(I+I) =30+2 (две группы первого вида)
2. Число 444 в римской системе счисления имеет вид:
CDXLIV = (D-C)+(L-X)+(V-I) (= 400 + 40 + 4 – три группы второго вида)
MCMLXXIV = M+(M-C)+L+(X++X)+(V-I) = 1000+900+50+20+4 (наряду с группами обоих видов в формировании числа участвуют отдельные «цифры»)
MMV = (M+M) +V = 1000+1000+5 (две группы первого вида)
Позиционные системы счисления характеризуется тем, что количественное значение цифры зависит от ее позиции в числе. Каждая позиционная система счисления имеет определенный алфавит цифр и основание, равное количеству цифр (знаков в ее алфавите).
Наиболее распространенными позиционными системами счисления являются десятичная, двоичная, восьмеричная и шестнадцатеричная.
Десятичная система счисления имеет алфавит из десяти цифр: 0, 1, …, 9.
Двоичная система счисления имеет алфавит из двух цифр: 0, 1.
Например, в числе 198710 цифра «1» обозначает одну тысячу (1*103),
цифра «9» обозначает девять сотен (9*102),
цифра «8» обозначает восемь десятков (8*101),
цифра «7» обозначает семь единиц (7*100).
В общем виде, если запись числа в системе счисления с основанием n>1 выглядит как abcd, то само число равно значению выражения an3+bn2+cn1+dn0.
Перевод целого числа из двоичной системы счисления в десятичную.
Пример.
1012 = 1*22 + 0*21 + 1*20 = 1*4 + 0 +1 = 510
Задание 1.
Переведите число 1011012 в десятичную систему счисления.
Решение.
1011012=1*25+0*24+1*23+1*22+0*21+1*20=32+8+4+1=4510
Ответ: 1011012=4510
Перевод целого числа из десятичной системы счисления в двоичную.
Алгоритм
1. Последовательно выполнить деление исходного целого десятичного числа и получаемых целых частных на основание системы (на 2) до тех пор, пока не получится частное, меньшее делителя (т.е. меньшее 2).
2. Записать полученные остатки в обратной последовательности.
Пример. Решение.
|
32510 = 1010001012 |
325 |
2 |
||||||||||
|
-324 |
162 |
2 |
||||||||||
|
1 |
-162 |
81 |
2 |
|||||||||
|
0 |
-80 |
40 |
2 |
|||||||||
|
1 |
-40 |
20 |
2 |
|||||||||
|
0 |
-20 |
10 |
2 |
|||||||||
|
0 |
-10 |
5 |
2 |
|||||||||
|
0 |
-4 |
2 |
2 |
|||||||||
|
1 |
-2 |
1 |
||||||||||
|
0 |
Задание 2.
Как представляется число 2510 в двоичной системе счисления?
|
1) 10012 |
2) 110012 |
3) 100112 |
4) 110102 |
Решение.
|
25 |
2 |
|||||||||||
|
24 |
12 |
2 |
||||||||||
|
1 |
-12 |
6 |
2 |
|||||||||
|
0 |
-6 |
3 |
2 |
|||||||||
|
0 |
-2 |
1 |
||||||||||
|
1 |
2510=100112, что соответствует ответу №2.
Ответ: 2.
Перевод дробного числа из двоичной системы счисления в десятичную.
Пример.
111,012 = 1*22 + 1*21 + 1*20 + 1*2-1 + 1*2-2 = 1*4 + 1*2 +1+ 0*+1* =
= 4+2+1+0,5+0,25 = 7,7510
Перевод дробного числа из десятичной системы счисления в двоичную.
Алгоритм.
Пример.
0,562510 = 0,10012.
Решение.
|
0, |
5625 |
|
|
х |
2 |
|
|
1 |
1250 |
|
|
х |
2 |
|
|
0 |
2500 |
|
|
х |
2 |
|
|
0 |
5000 |
|
|
х |
2 |
|
|
1 |
0000 |
Арифметические операции в двоичной и кратных ей системах счисления.
Арифметические операции в позиционных системах счисления производится по единому алгоритму. Так, сложение двоичных чисел происходит по классическому алгоритму «столбиком» с переносом числа, кратного двум, единицей в следующий разряд.
Рассмотрим этот алгоритм на примере двух двоичных чисел 10101012 и 1101112:
|
Дописывание единицы |
1 |
1 |
1 |
1 |
1 |
1 |
||
|
Первое слагаемое |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
Второе слагаемое |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
|
Сумма |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
Результат сложения выглядит как 100011002. Проверим результат сложения, для чего переведем все числа в десятичную систему счисления:
10101012=8510, 1101112=5510, 100011002=14010, 8510+5510=14010.
Двоичная система, являющаяся основой компьютерной арифметики, весьма громоздка и неудобна для использования человеком. Поэтому программисты используют две кратные двоичной системы счисления: восьмеричную и шестнадцатеричную. В случае шестнадцатеричной системы арабских цифр не хватает, и в качестве цифр используются первые шесть заглавных букв латинского алфавита. Примеры записи натуральных чисел от 1 до 16 в четырех системах счисления помещены в Таблице 1.
Таблица 1. Примеры записи натуральных чисел от 1 до 16
в четырех системах счисления
|
10-чная |
2-чная |
8-чная |
16-ичная |
|
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
|
2 |
10 |
2 |
2 |
|
3 |
11 |
3 |
3 |
|
4 |
100 |
4 |
4 |
|
5 |
101 |
5 |
5 |
|
6 |
110 |
6 |
6 |
|
7 |
111 |
7 |
7 |
|
8 |
1000 |
10 |
8 |
|
9 |
1001 |
11 |
9 |
|
10 |
1010 |
12 |
А |
|
11 |
1011 |
13 |
В |
|
12 |
1100 |
14 |
С |
|
13 |
1101 |
15 |
D |
|
14 |
1110 |
16 |
E |
|
15 |
1111 |
17 |
F |
|
16 |
10000 |
20 |
10 |
Из Таблицы 1 видно, что в двоичной системе запись чисел второй восьмерки (от 8 до 15) отличается от записи первой восьмерки (от 0 до 7) наличием единицы в четвертом (справа) разряде. На этом основан алгоритм перевода двоичных чисел в восьмеричные «по триадам». Для применения этого алгоритма надо разбить двоичное число на тройки цифр (считая справа) и записать вместо каждой из троек восьмеричную цифру:
101011012 → 10 101 101 → 2558.
2 5 5
Крайняя левая тройка может быть неполной (как в примере), для получения полных троек можно приписать слева недостающие нули.
Убедимся в правильности алгоритма:
101011012 → 1*27+1*25+1*23+2*21+1*20=17310;
2558 →2*26+5*23+5*20=17310.
Для перевода чисел из восьмеричной системы в двоичную используется обратный алгоритм: восьмеричные цифры заменяются на тройки двоичных цифр (при необходимости слева дописываются недостающие нули):
3258 → 3 2 5 → 11 010 101 → 110101012.
011 010 101
Для перевода чисел из двоичной системы в шестнадцатеричную используется алгоритм «по тетрадам». Строка двоичных цифр разбивается на четверки и вместо них записываются шестнадцатеричные цифры:
101011012 → 1010 1101 → AD16.
А D
Аналогично работает и обратный алгоритм: вместо шестнадцатеричных цифр подставляются четверки двоичных цифр.
Из восьмеричной системы в шестнадцатеричную и обратно проще переводить через двоичную систему:
D516→ D 5 →1101 0101 → 110101012 → 11 010 101 → 3258.
D 5 3 2 5
При выполнении заданий на сложение чисел разных систем счисления их нужно перевести в одну систему счисления. Лучше всего пользоваться той системой, в которой должен быть представлен результат.
Задание 3. (Задание А6 демоверсии 2004 г.)
Вычислите значение суммы в десятичной системе счисления:
102+108+1016 = ?10
Решение.
Переведем все числа в десятичную запись:
102+108+1016 = (1*21+0*20) + (1*81+0*80) + (1*161+0*160) = 2+8+16=2610.
Ответ: 26.
Задание 4.
Найдите сумму x+y, если x=11101012 , y=10110112. Ответ представьте в восьмеричной системе.
Решение.
Найдем сумму: 11101012 + 10110112 :
|
Дописывание единицы |
1 |
1 |
1 |
1 |
1 |
1 |
||
|
Первое слагаемое |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
|
|
Второе слагаемое |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
Сумма |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
11101012 + 10110112 = 110100002
Переведем получившееся число из двоичной системы счисления в восьмеричную:
11 010 000 → 3208.
3 2 0
Ответ: 320.
Задание 5. (Задание B1 демоверсии 2004 г.)
В системе счисления с некоторым основанием число 12 записывается в виде 110. Найдите это основание.
Решение.
Обозначим искомое основание через n. Исходя из правил записи чисел в позиционных счислениях 110n=n2+n1+0. Составим уравнение: n2+n=12, найдем корни: n1=-4, n2=3. Корень n1=-4 не подходит, так как основание системы счисления, по определению, натуральное число большее единицы. Проверим, подходит ли корень n=3:
1103=1*32+1*31+0=9+3=1210
Ответ: 3.
Задание 6.
В классе 11112 девочек и 11002 мальчиков. Сколько учеников в классе?
Решение.
11112=1*23+1*22+1*21+1*20→8+4+2+1=1510.
11002=1*23+1*22+0*21+0*20→8+4=1210
1510+1210=2710
Ответ: в классе 27 учеников.
Задание 7.
В саду 100х фруктовых деревьев, из них 33х яблони, 22х груши, 16х слив и 5х вишен. В какой системе счисления посчитаны деревья?
Решение.
100х = 33х + 22х + 16х + 5х
1*х2=3*х1+3*х0+2*х1+2*х0+ 1*х1+6*х0+5*х0
х2=3х+3+2х+2+ 1х+6+5
х2-6х-16=0
D=b2-4ac=36+4*16=36+64=100
x1,2= = (6±10)/2
x1= - 2 – не удовлетворяет смыслу задачи,
x2= 8 – основание искомой системы счисления.
Ответ: деревья посчитаны в восьмеричной системе счисления.
Задание 8.
Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 17 оканчивается на 2.
Решение.
Последняя цифра в записи числа представляет собой остаток от деления числа на основание системы счисления. Поскольку 17-2=15, то искомые основания систем счисления будут являться делителями 15, это: 3, 5, 15.
Проверим наш ответ, представив число 17 в соответствующих системах счисления:
|
17 |
3 |
17 |
5 |
17 |
15 |
||||||
|
-15 |
5 |
2 |
-15 |
3 |
2 |
-15 |
1 |
||||
|
2 |
-4 |
2 |
2 |
2 |
-2 |
1 |
2 |
||||
|
1 |
-2 |
1 |
1 |
||||||||
|
0 |
|||||||||||
|
1710 = 10123 |
1710 = 1125 |
1710 = 1215 |
Ответ: 3, 5, 15.
Задание 9.
В системе счисления с некоторым основанием число 17 записывается как 101. Укажите это основание.
Решение.
1710 = 101х = 1*х2 + 0*х1+ 1 х0
17=х2+1,→ х2=16,→ x1,2=±=±4
x1= - 4 – не удовлетворяет смыслу задачи,
x2= 4 – основание искомой системы счисления.
Ответ: 4.
Пример.
0,710 ≈ х 2
Решение.
|
0, |
7 |
|
|
х |
2 |
|
|
1 |
4 |
|
|
х |
2 |
|
|
0 |
8 |
|
|
х |
2 |
|
|
1 |
6 |
|
|
х |
2 |
|
|
1 |
2 |
|
|
х |
2 |
|
|
0 |
4 |
…
Очевидно, что этот процесс может продолжаться до бесконечности. Обрывают процесс на шаге, когда получена требуемая точность вычисления (количество знаков после запятой) .
0,710 ≈ 0,10110 2