Урок №7. Двоичное кодирование.
Для передачи информации обязательно нужно, чтобы свойства носителя как-то изменялись. Самый простой используемый код должен содержать, по крайней мере, два разных знака. Такое кодирование называют двоичным (от слова «два»), оно используется практически во всех современных компьютерах.
Двоичное кодирование — это кодирование с помощью двух знаков.
Например, сообщение АБАВГБ может быть закодировано с помощью кодовой таблицы
следующим образом: 000100101101.
Кодирование чисел с помощью нулей и единиц впервые применил в своей (механической) вычислительной машине немецкий мыслитель Готфрид Вильгельм Лейбниц в конце XVII века.
Затем, уже в середине XX века, двоичное кодирование информации стало повсеместно применяться для электронных компьютеров.
Чаще всего используется равномерный код, когда все символы исходного сообщения кодируются с помощью одинакового количества двоичных знаков. Каждый знак соответствует выбору одного из двух вариантов (0 или 1), поэтому несёт 1 бит информации.Длина кода определяется количеством вариантов, которые нужно закодировать.
Поскольку алфавит двоичного кода содержит 2 символа, применяя общую формулу, получаем количество различных сообщений длиной N битов:
Q=2N
Если заданное количество вариантов не равно степени числа 2, выбирают длину кода с запасом. Например, для кодирования номера спортсмена в интервале от 1 до 200 нужно использовать не меньше, чем 8 битов, поскольку
27 = 128 < 200 < 28 = 256.
Если нужно передать информацию о номерах первых 20 спортсменов, пришедших к финишу, информационный объём такого сообщения будет равен 8 • 20 = 160 битов = 20 байтов.
Двоичное кодирование информации обеспечивает простоту, надежность и дешевизну. Двоичная система счисления имеет преимущества перед другими системами счисления:
- для реализации нужны элементы с двумя состояниями, например высокий или низкий уровень тока, намагниченный и ненамагниченный участок;
- информация, представленная только двумя состояниями, надежна и помехоустойчива;
- можно использовать булеву алгебру для логических преобразований.
Среди недостатков двоичного кодирования стоит отметить:
- большую длину кодов, которая несколько замедляет их обработку;
- сложность восприятия двоичных комбинаций человеком без специального образования или подготовки.
Равномерный код — это код, в котором все кодовые слова имеют одинаковую длину.
Если алфавит языка состоит из М знаков (имеет мощность М), то количество различных сообщений длиной L знаков вычисляется как
N = ML
Двоичный код — это сообщение, использующее алфавит из двух знаков (0 и 1), поэтому для двоичного кода эта формула запишется в виде
N = 2L.
Например, восьмиразрядная ячейка памяти компьютера может хранить одно из 28 = 256 различных значений.
Если заданное количество вариантов не равно степени числа 2, выбирают длину кода с запасом. Например, для кодирования номера спортсмена в интервале от 1 до 200 нужно использовать не меньше, чем 8 двоичных разрядов (бит), поскольку 7 бит позволяют закодировать только 128 различных значений (этого мало!), а 8 бит — уже 256:
27 = 128 < 200 < 256 = 28.
В середине XX века в СССР была разработана электронно-вычислительная машина «Сетунь», в которой для хранения и обработки данных использовался троичный код с алфавитом {-1, 0, 1}. В таком компьютере восьмиразрядная ячейка памяти могла хранить одно из З8 = 6561 значения.
Правило умножения
При дополнительных ограничениях количество возможных знаков в разных позициях сообщения может различаться, поэтому нужно использовать более общее правило умножения:
N = М1 • М2 • … •ML.
Здесь Мk — это возможное количество вариантов выбора знака в позиции k.
Задача 1. Сколько существует различных сообщений длины 5 в четырёхбуквенном алфавите {А, В, С, X}, если известно, что буква «X» может появляться только на первом или на последнем месте?
Решение. По условию на первом и последнем местах может быть любая из четырёх букв, поэтому М1 = М5 = 4. В остальных трёх позициях могут быть любые буквы, кроме «X», поэтому М2 = M3 = М4 = 3. Тогда общее количество различных сообщений равно N = 4•3•3•3•4 = 432.
Ответ: 432.
Задача 2. Сколько существует пятизначных десятичных чисел, в которых каждая цифра встречается только один раз?
Решение. Представим себе, что нам нужно заполнить пять ячеек разными цифрами. У нас есть 10 цифр (от 0 до 9). Чтобы получить пятизначное число, в первой ячейке мы не можем использовать цифру 0, т. е. можем заполнить её девятью способами. Во вторую ячейку мы не можем записывать ту цифру, которую выбрали для первой ячейки, поэтому в ней может находиться одна из 9 оставшихся цифр. При заполнении третьей ячейки нужно учитывать, что для первых двух цифры уже выбраны и их использовать нельзя, остаётся 8 свободных цифр, и т. д.
Ответ: 27 216 чисел.
Задача 3. Вася составляет 5-буквенные слова, в которых есть только буквы «К», «Р», «О», «Т», причём буква «О» используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Решение. Единственная буква «О» может стоять в любой из 5 позиций. Предположим, что мы определили её место, тогда на каждом из оставшихся 4 мест может оказаться любая из остальных трёх букв («К», «Р» или «Т). Таким образом, при любой заданной позиции буквы «О» Вася может составить З4 = 81 слово, а всего существует 5 • З4 = 405 пятибуквенных слов с единственной буквой «О».
Ответ: 405.
Неравномерный код — это код, в котором кодовые слова имеют различную длину.
При неравномерном кодировании коды различных знаков могут иметь разную длину. Это делается для того, чтобы сократить длину сообщения, используя сведения о частотах встречаемости различных знаков. Знаки, которые встречаются в сообщениях чаще других (например, для текстов на русском языке — это пробел и буквы «О», «Е» и «А»), получают более короткие коды, а редко встречающиеся знаки — более длинные.
Задача 1. По каналу связи передаются сообщения, каждое из которых содержит 16 букв «А», 8 букв «Б», 4 буквы «В» и 4 буквы «Г» (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. Какой код из приведённых ниже следует выбрать, чтобы длина сообщения была как можно меньше?
Код 1: А — О, Б — 10, В — 110, Г — 111;
код 2: А — 00, Б — 01, В —10, Г — 11.
Решение. Считаем общее количество бит в сообщении для кода 1:
16*1 + 8*2 + 4*3 + 4*3 = 56 бит и общее количество бит в сообщении для кода 2:
16*2 + 8*2 + 4*2 + 4*2 = 64 бит.
Код 1 даёт наименьшую длину сообщения, поэтому выбираем его.
Ответ: код 1.
Задача 2. По каналу связи передаются сообщения, содержащие только 4 буквы: «А», «И», «С», «Т». В любом сообщении больше всего букв «А», следующая по частоте буква — «С», затем — «И». Буква «Т» встречается реже, чем любая другая. Для передачи сообщений нужно использовать один из следующих неравномерных двоичных кодов:
код 1: А — 1, И — 01, С — 001, Т — 000;
код 2: А — 101, И — 11, С — 0, Т — 100
так, чтобы сообщения были как можно короче. Какой код следует выбрать?
Решение. Для того чтобы длина сообщения была наименьшей, должно выполняться правило: «чем чаще встречается буква, тем короче её код». К сожалению, это правило не выполняется для кодов 1 и 2: в коде 1 длина кодового слова для буквы «С» больше, чем длина кодового слова для буквы «И» (а лучше было бы сделать наоборот!); для кода 2 длина кодового слова для буквы «А» — не самая маленькая из всех.
Предположим, что в сообщении буква «А» встречается α раз, буква «И» — β раз, буква «С» — γ раз и буква «Т» — δ раз, причём по условию задачи α > γ > β > δ. При кодировании с помощью кода 1 получаем сообщение длиной
S1 = α + 2β + 3γ + 3δ,
а при кодировании с помощью кода 2 длина сообщения равна
S2 =3α + 2β + γ + 3δ.
Находим разность: S2 — S1= (3α + 2β + γ + 3δ) — (α + 2β + 3γ + 3δ) =2α — 2γ. Поскольку α > γ, получаем: S2 — S1> 0, т. е. код 1 более экономичный.
Ответ: код 1.
Задача 3. Сколько символов можно закодировать с помощью кода Морзе, используя кодовые слова различной длины — от 1 до 5 знаков?
Решение. Кодовые слова длиной, скажем, 2 знака можно выбирать независимо от кодовых слов другого размера. Поэтому достаточно найти количество кодовых слов NL для каждого возможного значения длины кодового слова L и сложить эти числа:
N = N1 + N2 + N3 + N4 + N5.
Это правило называется правилом сложения.
Так как в коде Морзе используются всего два знака (точка и тире), из общей формулы получаем: NL = 2L. Поэтому N = 21 +22 + 23 + 24 + 25 = 62.
Ответ: 62.
Декодирование — это восстановление информационного сообщения из последовательности кодов.
Сообщения, записанные с помощью равномерного кода, всегда декодируются однозначно. Для этого достаточно разбить сообщение на группы известной длины и декодировать каждую группу по кодовой таблице.
В некоторых случаях даже при использовании неравномерного кода не требуется вводить символ-разделитель. Для этого достаточно выполнения условия Фано: ни одно кодовое слово не совпадает с началом другого кодового слова. Такой код называют префиксным.
Пример 1. Пусть для кодирования первых пяти букв русского алфавита используется кодовая таблица:
Это неравномерный код, поскольку в нём есть двух- и трёхзначные кодовые слова. Построим для этой кодовой таблицы дерево, в котором от каждого узла (кроме листьев) отходят два ребра, помеченные цифрами 0 и 1. Чтобы найти код символа, нужно пройти по стрелкам от корня дерева к нужному листу, выписывая метки стрелок, по которым мы переходим.
Заметим, что ни одна буква не лежит на пути от корня к другой букве. Это значит, что условие Фано выполняется, и любую правильную кодовую последовательность можно однозначно декодировать с начала. Например, рассмотрим цепочку 1100000100110. Букв с кодами 1 и 11 в таблице нет, поэтому сообщение начинается с буквы «Г» — она имеет код 110:
Следующий (единственно возможный) код — ООО, это буква «А»:
Аналогично декодируем все сообщение:
Пример 2. Рассмотрим другую кодовую таблицу:
Здесь условие Фано не выполняется, поскольку код буквы «Б» (01) совпадает с началом кода буквы «Г» (011), а код буквы «Д» (100) начинается с кода буквы «В» (10). Дерево для этой кодовой таблицы выглядит так.
Тем не менее по кодовой таблице можно проверить, что выполнено «обратное» условие Фано: ни одно кодовое слово не совпадает с окончанием другого кодового слова (такой код называют постфиксным). Поэтому закодированное сообщение можно однозначно декодировать с конца. Например, рассмотрим цепочку 011000110110. Последней буквой в этом сообщении может быть только «В» (код 10):
и так далее:
В общем случае декодировать сообщение удаётся только перебором вариантов.