Коды, учитывающие частоту информационных элементов

В некоторых системах кодирования значение кода определяется частотой встречаемости кодируемого символа. Как правило, такие частоты известны для букв алфавитов естественных языков, например, английского или русского, и используются уже давно при размещении клавиш клавиатуры: наиболее часто используемые буквы располагаются на клавишах в середине клавиатуры, наиболее редко используемые – на периферии, что создает удобство работы для человека.

Учет частоты символов позволяет строить «экономные» для техники коды постоянной длины. Например, для первых ламповых компьютеров двоичная единица технически реализовалась включенной лампочкой накаливания, а двоичный ноль – выключенной лампочкой. Поэтому использовали коды с учетом частоты символов: чем больше частота символа, тем меньше в соответствующем коде единиц, т.е. тем меньше включенных лампочек применяется для представления символа в компьютере, а значит, меньше тратится электроэнергии.

Пусть известны частоты букв русского алфавита:

И	5/14
Л	3/14
Ь	3/14
Н	1/14
Ч	1/14
Я	1/14

Построим коды, учитывающие частоту, для символов кириллицы (заданные символы русского алфавита уже упорядочены в соответствии с их частотой по невозрастанию).

И	000
Л	001
Ь	010
Н	100
Ч	011
Я	101

Можно утверждать, что для кодирования одного символа в нашей задаче требуется 3 двоичных разряда. Будем с помощью перебора так формировать кодовые комбинации, чтобы число единиц в соответствующих кодовых комбинациях было минимальным:

Как видно из таблицы, минимальное число единиц, равное нулю, у символа с максимальной частотой – буквы «и».

Закодируем, например, слово «илья» с помощью построенной нами кодовой таблицы: 000001010101. Как видно, здесь только 4 единицы (читай – включенные лампочки).

Коды Грея

В качестве кодового алфавита используются двоичные символы.

Одношаговые. Это означает, что в кодовой таблице рядом расположенные кодовые комбинации, использующие двоичную систему исчисления, различаются только одним разрядом.

Код постоянной длинны. Отличительной особенностью является особое требование к исходному алфавиту при построении кодовой таблицы. Символы исходного алфавита должны быть упорядочены по какому-либо признаку.

Например: лексикографическому. {0,1,2,…….,9}

1 шаг. 0 соответствует 0, 1 соответствует 1

2 шаг. Полученные коды Грея позволяют сформировать квадратную матрицу, кол-во строк и столбцов которой соответствуют кол-ву кодов Грея, полученному к данному моменту.

1. 1

0	1
3	2

0

1 Строки и столбцы матрицы нумеруются полученными кодовыми комбинациями.

3 шаг. В ячейках матрицы размещаем символы исходного алфавита начиная с первого символа по схеме «Змейка»

4 шаг. Для размещения в матрице символов вновь строятся коды Грея. К № столбца приписывается № строки. 000 , 110, 211, 301

5 шаг. Если исходный алфавит выбран не весь возвращаемся ко 2 шагу.

00 10 11 01

0	1	2	3
7	6	5	4
8	9

00

10

11

01

Результат: 00000 11000 21100 30100 40110 51110 61010 70010 80011 91011.