Кодирование инф. Курс лекций по темам раздела Кодирование информации, методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки
 Скачать 1.18 Mb.
|
|
0 1/3 2/3 1 7/12 5/12 2/3 1/3 Следующая буква в сообщении S — буква «а». Ее рабочий отрезок [1/3; 5/12). Вес буквы «а» увеличивается на единицу. Суммарный вес всех символов теперь равен 2 + 2 + 1 = 5. Вероятности использования символов: Р а =2/5, Р b =2/5, Р ! =1/5. Отношение вероятностей 2:2:1. Отрезок [1/3; 5/12) делим следующим образом: В сообщении S появляется новый символ: «b». Ей соответствовал отрезок [11/30; 12/30). Переходим к этому новому рабочему отрезку. Делим его на шесть равных частей, ведь суммарный вес символов увеличился на единицу, вследствие увеличения на единицу веса символа «b». Букве «а» соответствует две части из полученных шести, букве «b» - три части, символу «!» - одна часть: Последний символ сообщения S — признак конца строки «!». Его рабочий отрезок на данном этапе кодирования [71/180; 12/30). Любое число из этого отрезка может быть выбрано в качестве кода сообщения S. Например 71/180 ≈ 0,394. Полученный код должен быть переведен в двоичную систему счисления и в качестве конечного результата кодирования необходимо взять его битовое представление и его длину. Декодирование происходит следующим образом: на каждом шаге определяется интервал, содержащий данный код (выбранное число) – по этому интервалу однозначно задается исходный символ сообщения. Затем из текущего кода вычитается нижняя граница содержащего интервала, полученная 56 11/30 12/30 5/12 1/3 17/45 71/180 12/30 11/30 разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Получение символа конца сообщения или заданного перед началом работы алгоритма числа символов означает окончание работы. Вопросы для самопроверки: 1. Объясните алгоритм построения адаптивного арифметического кода. 2. Постройте адаптивный арифметический код сообщения S=«2+2=4!» для символов первичного алфавита А={«+», «=», «2», «4», «!»} (символ «!» не несет смысловой нагрузки и является признаком конца сообщения). 3. Декодируйте сообщение S, составленное из символов алфавита А={«1», «2», «3», «!»}, если известен его адаптивный арифметический код, записываемый в двоичной системе счисления как 0,1000101 2 Хранение чисел в памяти компьютера. Дополнительный код целого положительного числа. При ответе на данный вопрос необходимо рассказать о принципах хранения числа в памяти компьютера, а также сформулировать алгоритм получения дополнительного кода целого положительного числа без знака. Вся информация, которую обрабатывает компьютер, должна быть представлена двоичным кодом с помощью двух цифр — 0 и 1. С помощью двух цифр 1 и 0 можно закодировать любое сообщение. С точки зрения технической реализации использование двоичной системы счисления для кодирования информации оказывается намного более простым, чем применение других способов. Действительно, удобно 57 кодировать информацию в виде последовательности нулей и единиц, если представить эти значения как два возможных устойчивых состояния электронного элемента: • 0 — отсутствие электрического сигнала или сигнал имеет низкий уровень; • 1 — наличие сигнала или сигнал имеет высокий уровень. Для кодирования чисел в компьютере также используется двоичный код. При этом для представления целых чисел используется так называемый дополнительный код. В случае представления величины со знаком самый левый (старший) разряд указывает на положительное число, если содержит нуль, и на отрицательное, если — единицу. Известно, что диапазон значений величин зависит от количества бит памяти, отведенных для их хранения. Например, величины типа Integer языка Turbo Pascal лежат в диапазоне от – 32768 (–2 15 ) до 32767 (2 15 –1) и для их хранения отводится 2 байта; величины типа LongInt — в диапазоне от –2 31 до 2 31 –1 и размещаются в 4 байтах; величины типа Word — в диапазоне от 0 до 65535 (2 16 –1) (используется 2 байта) и т.д. Дополнительный код положительного числа совпадает с его прямым кодом. Прямой код целого числа может быть получен следующим образом: модуль числа переводится в двоичную систему счисления, а затем его двоичную запись слева дополняют таким количеством незначащих нулей, сколько требует тип данных, к которому принадлежит число. Например, необходимо получить дополнительный код числа 37 10 . Это целое положительное число. Получим его прямой код. Для этого переведем число 37 10 в двоичную систему счисления. Для этого последовательно поделим число на 2 и 58 запишем полученные остатки от деления в обратном порядке (справа налево). Получим, что 37 10 = 100101 2 . То есть двоичное представление числа содержит шесть цифр. Дополним его слева незначащими нулями. Как уже было сказано, их число зависит от типа числа. Если число объявлено величиной типа Integer (2 байта), то его прямым кодом будет 0000000000100101 (16 позиций), а если величиной типа LongInt, то его прямой код будет 00000000000000000000000000100101 (32 позиции). Дополнительный код рассматриваемого числа совпадает с его прямым кодом. Для более компактной записи чаще используют шестнадцатеричный код. Полученные коды можно переписать соответственно как 0025 16 и 00000025 16 Решим обратную задачу. Запишем число, соответствующее дополнительному коду: 0000000000010111. Поскольку в старшем разряде записан нуль, то результат будет положительным. Отбрасываем незначащие нули слева и переводим код 10111 из двоичной системы в десятичную. 1∙2 4 + 0∙2 3 + 1∙2 2 + 1∙2 1 +1∙2 0 = 16 + 0 + 4 + 2 + 1 = 23 10 Следовательно заданный код - это код числа 23. Вопросы для самопроверки: 1. Объясните алгоритм получения кода целого положительного числа. 59 2 36 37 1 2 18 18 0 2 8 9 1 2 4 4 0 2 2 2 2 0 1 2. Получите шестнадцатиразрядный дополнительный код числа 65 10 . 3. Определите число по его дополнительному коду: 0001110011100001 Хранение чисел в памяти компьютера. Дополнительный код целого отрицательного числа. При ответе на данный вопрос необходимо рассказать о принципах хранения числа в памяти компьютера, а также сформулировать алгоритм получения дополнительного кода целого отрицательного числа. Все данные в компьютере хранятся в виде набора двоичных кодов — последовательности нулей и единиц. Числовые данные могут быть интерпретированы как числа со знаками, так и без знаков. В случае представления величины со знаком самый левый разряд указывает на положительное число, если содержит нуль, и на отрицательное, если — единицу. Разряды нумеруются справа налево, начиная с 0. Дополнительный код целого отрицательного числа может быть получен по следующему алгоритму: • записать прямой код модуля числа; • инвертировать его (заменить единицы нулями, нули — единицами); • прибавить к инверсному коду единицу. Рассмотрим пример. Запишем дополнительный код числа (–37) 10 , интерпретируя его как величину типа LongInt, для хранения которой отводится 4 байта. 60 Для получения прямого кода модуля числа (–37) 10 переведем его модуль - число 37 10 - в двоичную систему счисления. Получим число 100101 2 . Так как для хранения отводится 4 байта, т. е. 32 бита или 32 ячейки памяти, то прямой код числа 37 10 есть 00000000000000000000000000100101. Инвертируем полученный прямой код: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 В результате получим инверсный код: 11111111111111111111111111011010. Прибавим к инверсному коду единицу: 11111111111111111111111111011010 1 11111111111111111111111111011011 Значит, дополнительный код числа (–37) 10 будет 11111111111111111111111111011011 или FFFFFFDB (16) Если необходимо получить число по его дополнительному коду, то прежде всего, определяем его знак по значению старшего бита. Если значение старшего бита будет равно единице, то число отрицательное. В этом случае необходимо выполнить следующие действия: • вычесть из дополнительного кода числа единицу; • инвертировать код; • отбросить незначащие нули слева и перевести полученный код в десятичную систему счисления; • полученное число записать со знаком минус. 61 + Например, пусть известно, что некоторое число имеет дополнительный код 1111111111000000. Необходимо определить само число. По значению старшего бита определяем знак числа. Число отрицательное. Вычитаем из его дополнительного кода единицу (действия производим в двоичной системе счисления): 1111111111000000 2 – 1 2 = 1111111110111111 2 Инвертируем полученный код: 0000000001000000 Отбрасываем незначащие нули и переводим полученное число в десятичную систему счисления: 1000000 2 = 1*2 6 = 64 10 Запишем найденное число со знаком «минус»: –64. Вопросы для самопроверки: 1. Объясните алгоритм получения кода целого отрицательного числа. 2. Получите четырехбайтный дополнительный код числа (- 48) 10 . 3. Определите число по его дополнительному коду: 1001110011100001 Хранение чисел в памяти компьютера. Дополнительный код вещественного числа. При ответе на данный вопрос необходимо рассказать о способе хранения в памяти компьютера вещественных чисел, привести пример нормализованного вида числа, мантиссы, порядка, объяснить алгоритм вычисления смещенного порядка вещественного числа. 62 Известно, что любое действительное число можно записать в стандартном виде M×10 p , где 1 ≤ M < 10, p — целое. Например, 120100000 = 1,201 × 10 8 . Поскольку каждая позиция десятичного числа отличается от соседней на степень числа 10, умножение на 10 эквивалентно сдвигу десятичной запятой на одну позицию вправо. Аналогично деление на 10 сдвигает десятичную запятую на позицию влево. Поэтому приведенный выше пример можно продолжить: 120100000 = 1,201 × 10 8 = 0,1201 × 10 9 = 12,01 × 10 7 Десятичная запятая «плавает» в числе и больше не помечает абсолютное место между целой и дробной частями. В приведенной выше записи M называют мантиссойчисла, а p — его порядком. Числа в компьютере сохраняются в виде набора двоичных кодов. Для того чтобы сохранить максимальную точность, вычислительные машины почти всегда хранят мантиссу в нормализованном виде, что означает, что мантисса в данном случае есть число, лежащее между 1 10 (в двоичной системе это 1 2 ) и 2 10 (в двоичной системе - 10 2 ). Способ хранения мантиссы с плавающей точкой подразумевает, что двоичная запятая находится на фиксированном месте. Фактически подразумевается, что двоичная запятая следует после первой двоичной цифры, т.е. нормализация мантиссы делает единичным первый бит, помещая тем самым значение между десятичной единицей и двойкой. Место, отводимое для числа с плавающей точкой, делится на два поля. Одно поле содержит знак и значение мантиссы, а другое содержит знак и значение порядка. Размер памяти отводимый под хранение числа определяется его типом. Так для хранения числа в самом распространенном вещественном формате real отводится шесть байт. Размеры памяти, отводимые для других вещественных форматов представлены в таблице: 63 Тип числа Диапазон значений Количество значащих цифр Байты Single 1,5 × 10 –45 .. 3,4 × 10 38 7–8 4 Real 2,9 × 10 –39 .. 1,7 × 10 38 11–12 6 Double 5,0 × 10 –324 .. 1,7 × 10 308 15–16 8 Extended 3,4 × 10 –4932 ..1,1 × 10 4932 19–20 10 Покажем преобразование действительного числа для представления его в памяти компьютера на примере величины типа Real. Как видно из таблицы, величина это типа занимает в памяти 6 байт или 48 бит. Как известно, биты нумеруются справа налево и нумерация начинается с нуля. Значит бит с номером 47 будет знаковым, следующие 11 бит отводятся на хранение смещенного порядка, далее ячейки памяти занимаются мантиссой. Ниже показано, как здесь представлены поля мантиссы и порядка: Знак Смещенный порядок Мантисса 47 46 36 35 0 Можно заметить, что старший бит, отведенный под мантиссу, имеет номер 35, т.е. мантисса занимает младшие 36 бит. Черта указывает здесь на положение двоичной запятой. Перед запятой должен стоять бит целой части мантиссы, но поскольку она всегда равна 1, здесь данный бит не требуется и соответствующий разряд отсутствует в памяти (но он подразумевается). Для упрощения вычислений и сравнения действительных чисел значение порядка в памяти компьютера хранится в виде смещенного числа, т.е. к настоящему значению порядка перед записью его в память прибавляется смещение. 64 Смещение выбирается так, чтобы минимальному значению порядка соответствовал нуль. Например, для типа Real порядок занимает 11 бит. Самое большое число, которое можно разместить в 11 битах, это число с дополнительным кодом 01111111111, т.е. число 1023. Самое маленькое число, хранимое в одиннадцати битах (-1023). Поэтому диапазон порядка будет от – 1023 до 1023. Для того чтобы минимальному значению порядка соответствовал нуль, необходимо, чтобы смещение было равно 1023 10 = 1111111111 2 Сформулируем алгоритм для получения представления действительного числа в памяти компьютера: • перевести модуль данного числа в двоичную систему счисления; • нормализовать двоичное число, т.е. записать в виде M × 2 p , где M — мантисса (ее целая часть равна 1 2 ) и p — порядок, записанный в десятичной системе счисления; • прибавить к порядку смещение и перевести смещенный порядок в двоичную систему счисления; • определить значение старшего бита по знаку числа (0 для положительного числа, 1 для отрицательного), выписать его представление в памяти компьютера. Рассмотрим пример. Запишем код числа –312,3125 интерпретируя его как число типа Real. Двоичная запись модуля этого числа имеет вид 100111000,0101. Нормализируем полученное двоичное представление. Имеем 100111000,0101 = 1,001110000101 × 2 8 Как уже было сказано, для типа Real смещение равно 1023. Прибавим его к порядку и получим смещенный порядок 8 + 1023 = 1031. Далее переводим смещенный порядок в двоичную систему счисления. Имеем 1031 10 = 10000000111 2 65 Окончательно получаем следующее представление числа -312,3125: 1 10000000111 001110000101000000000000000000000000 знак смещенный порядок мантисса Полученный код можно записать в шестнадцатиричной системе: C07385000000 16 Рассмотрим пример обратной задачи: перейдем от кода действительного числа к самому числу. Пусть дан код 3FEC60000000 16 . Переведя его в двоичную систему счисления получим: 001111111110110001100000000000000000000000000000 Прежде всего, замечаем, что это код положительного числа, поскольку в старшем разряде записан нуль. Следующие 11 бит отведены на смещенный порядок - 01111111110. Переведем это двоичное число в десятичную систему счисления: 01111111110 2 = 1022 10. Вычитая смещения, получим порядок числа: 1022 – 1023 = –1. Число имеет вид 1,1100011 × 2 –1 или 0,11100011. Переводом в десятичную систему счисления получаем 0,88671875. Вопросы для самопроверки: 1. Объясните алгоритм получения кода вещественного числа. 2. Переведите число (-56,375) 10 в двоичную систему счисления и запишите его в нормализированном виде. 3. Получите дополнительный код числа 65,025 10 , интерпритируя его как число типа Double. Цифровые коды. Двоично-десятичное кодирование. При ответе на данный вопрос необходимо рассказать о 66 способе построения двоично-десятичного кода, о требованиях, предъявляемых к весам разрядов двоично-десятичных кодов, о принципах работы двоично-десятичных сумматоров. В двоично-десятичном коде основной системой счисления является десятичная. Однако каждая значащая десятичная цифра в двоично-десятичном коде представляется четырьмя двоичными знаками и содержит десять значений сигнала от 0 до 9. Так, например, десятичное число 10 можно представить как 0001 0000, а десятичное число 99 можно представить как 1001 1001. Так как при кодировании четырьмя двоичными знаками можно получить 16 кодовых значений, то приведенное двоично- десятичное представление не является единственным. Например, широко используют двоично-десятичные коды с весами 2-4-2-1 и 5-1-2-1. Покажем как представляются в этих кодах десятичные цифры: Десятичный код Двоично-десятичный код 8-4-2-1 2-4-2-1 5-1-2-1 0 0000 0000 0000 0000 0000 0000 1 0000 0001 0000 0001 0000 0001 или 0000 0100 2 0000 0010 0000 0010 или 0000 1000 0000 0010 или 0000 0101 3 0000 0011 0000 0011 или 0000 1001 0000 0011 или 0000 0110 67 Десятичный код Двоично-десятичный код 8-4-2-1 2-4-2-1 5-1-2-1 4 0000 0100 0000 0100 или 0000 1010 0000 0111 5 0000 0101 0000 0101 или 0000 1011 0000 1000 6 0000 0110 0000 0110 или 0000 1100 0000 1001 или 0000 1100 7 0000 0111 0000 0111 или 0000 1101 0000 1101 или 0000 1010 8 0000 1000 0000 1110 0000 1110 или 0000 1011 9 0000 1001 0000 1111 0000 1111 Для формирования чисел мспользуем тот же принцип. Так, десятичное число 15 в двоично-десятичном коде с весами 8-4-2- 1 будет представлено в следующем виде 0001 0101. Как видно из таблицы, практически все двоично- десятичные коды не имеют однозначности в отображении. Исключением является код с весами 8-4-2-1. При построении двоично-десятичного кода с весами q 4 -q 3 - q 2 -q 1 необходимо учитывать следующие |