Муниципальное общеобразовательное учреждение

«Сынтульская средняя общеобразовательная школа»

ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В КОМПЬЮТЕРЕ.
КОДИРОВАНИЕ ТЕКСТОВОЙ ИНФОРМАЦИИ.

РАВНОМЕРНЫЙ И НЕРАВНОМЕРНЫЙ КОД.

Составил: преподаватель информатики:

Симбирцев Владимир Евгеньевич

Касимов, 2018 год

Оглавление

ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В КОМПЬЮТЕРЕ        3

Кодирование текстовой информации        3

Равномерный код        3

Неравномерный код.  Условие Фа́но        6

ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В КОМПЬЮТЕРЕ

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

Кодирование текстовой информации

Как происходит кодирование текстовой информации в двоичной системе?

Предположим, нужно закодировать какое-то слово. Логично, что для этого необходимо каждой букве алфавита назначить какое-то двоичное число, например:

И попробуем закодировать слово ЗИМА

Таким образом: ЗИМА  => 1000100111010

А теперь попробуем его раскодировать.

И тут возникает проблема, потому что могут получиться совершенно разные слова.

ВАРИАНТ 1:

ВАРИАНТ 2:

И  так далее…, среди которых есть и ЗИМА.

Равномерный код

Что делать?

Например, поставить пробелы между числами, но у нас только нули и единицы. Тем не менее, выход есть, точнее два выхода.

Первое решение: «Сказать» компьютеру, что для кодирования одного символа будет использоваться одинаковое количество двоичных цифр в числе (в нашем случае четыре цифры):

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

Для того, чтобы определить какое максимальное количество символов алфавита можно закодировать в данной системе счисления, используя указанное количество разрядов (знакомест), нужно воспользоваться формулой:

где         N         – количество букв, мощность алфавита,

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

i         – количество цифр (знакомест) в числе, которым кодируется один символ в данной системе счисления с основанием а

   ВАЖНО: N,a,i – целые числа а   

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

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

Вообще, максимальное количество символов, которое можно закодировать в двоичной системе счисления, используя равномерный код из четырех битов^[1] (разрядов, знакомест).

 символов

А, самое большое число (в переводе на десятичную систему счисления), которое можно записать в данной системе счисления, используя  i – разрядов:

Действительно 1510=11112

Так происходит, потому что чисел всего 16 (от 0 до 15).

В информатике все начинается с НУЛЯ^[2] !!!

ЗАДАЧА: Какое минимально возможное битов потребуется, чтобы закодировать английский алфавит (в английском алфавите 26 букв).

РЕШЕНИЕ:

Используем формулу:

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

Используем метод подбора:

                                        24 = 16 символов

                                        25 = 32 символа

Четырьмя битами можно закодировать только 16 символов, а у нас – 26.

Пятью битами можно закодировать 32 символа.

Если можно 32 символа закодировать, то и 26 символов тем более закодируются, и еще останется☺.

Ответ: 5 бит.

ЗЫЖ Можно и шестью, и семью символами закодировать и т.д., но в данной задаче стоит условие: ЗАКОДИРОВАТЬ МИНИМАЛЬНО ВОЗМОЖНЫМ КОЛИЧЕСТВОМ БИТОВ

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

Существует множество кодировок. Вот две из них:

• Американская кодировка ASCII (англ. American standard code for information interchange – Американский стандартный код для обмена информацией , 8 бит)
• Советская кодировка КОИ-8 (код обмена информацией, 8 бит), Разработана для кодирования букв кириллических алфавитов. Нетрудно догадаться, что при использовании восьми бит можно закодировать 256 символов.

Неравномерный код.  Условие Фа́но

Никакое кодовое слово (буква)
не может быть началом другого кодового слова (буквы)

Другим выходом из данной ситуации про ЗИМУ будет использование неравномерного  кода. Правда придется воспользоваться условием Фа́но^[3] см.выше. Рассмотрим следующую задачу:

ЗАДАЧА:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова:

А – 010, Б – 1, В – 011.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

РЕШЕНИЕ:

Давайте разберем подробнее, что такое условие Фа́но:

Никакое кодовое слово (буква)
не может быть началом другого кодового слова(буквы)

Это значит:

1. Если буквы имею одинаковое количество разрядов, то они не должны быть одинаковыми. В самом деле, а = 10 и в = 10 не допускаются
2. Если же буквы имеют разное количество разрядов, то буква с меньшим количеством разрядов не должна быть началом буквы с бо́льшим количеством разрядов

Например:

А – 01,

Б – 011 – так быть не может, потому что буква А является началом
буквы Б

А вот так может:

А — 01,

Б — 001

Решим нашу задачу графически. Проще всего ее решать с помощью графов, а точнее частного случая графа – дерева.

Код букв может начинаться как с нуля, так и с единицы. По условию задачи буква Б – 1. Значит, код остальных букв будет начинаться с нуля. В противном случае буква Б будет являться началом для других букв.

Код буквы А, В, Г начинается с нуля. Второй символ у букв А, В по условию начинается с единицы, значит для буквы Г можно использовать ноль.

Графически описание этой задачи выглядит понятнее ☺.