Равномерное кодирование

Задача кодирования

Пусть имеется некоторое множество А = {, ,…, }. Будем называть это множество алфавитом, а объекты – буквами. Кортеж из букв =, ,…, будем называть словом. Последовательность слов – S называется сообщением. Множество сообщений над алфавитом А будем обозначать А.

Пусть имеется алфавит В= {, ,…, }.

Задача кодирования заключается в том, что сообщение S, заданное над алфавитом А, преобразуется в сообщение S , заданное над алфавитом В (код). Функция f(), переводящая сообщение S в S, называется кодированием. Последовательность символов , ,…, , соответствующая букве алфавита А, называется элементарным кодом этой буквы.

Общее количество символов ─ длина кода.

Замечание:

В качестве буквы алфавита А, могут выступать и сообщения.

Функция, обратная функции кодирования F(), называется декодированием.

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

Примеры:

1. Кодирование должно допускать декодирование.
2. Произвести кодирование так, чтобы общая длина кода соответствующая сообщению S, была наименьшей.
3. Кодирование должно быть таким, чтобы при передаче его не было искажения информации.
4. Простота (сложность) декодирования. И т.д.

Равномерное кодирование – это кодирование, при котором каждый элементарный код имеет одинаковую длину.

Например, если выбрать в качестве алфавита В цифры, то одноразрядным кодом можно закодировать 10 символов, а двухразрядными числами – 100.

Пусть алфавит В содержит к букв, а длина элементарного кода n букв. Сколько символов (m) при равномерном кодировании можно закодировать?

Элементарные коды ─ это кортежи из n букв, взятых из данных к, поэтому они являются размещениями с повторениями. По известной формуле их число равно

m = кⁿ (1)

Поставим обратную задачу. Имеется m букв алфавита А. Сколько букв должны содержать элементарные коды при равномерном кодировании?

Из формулы (1), логарифмируя, получи

n = log _к m(2)

Если же алфавит В={0,1} – двоичный, то закодировать n – битным кодом можно в силу формулы (1) имеем букв

m = 2 ⁿ (3)

Пусть имеется алфавит А, состоящий из m символов. Сколько бит должен содержать каждый элементарный код при равномерном кодировании?

Из формулы (2) получим, если m – степень 2,

n = log ₂m(4)

Если m – не степень 2, то по формуле:

n=\ logm | + 1 (5)

где |logm | - целая часть logm..

Формулы (4) - (5) называются формулами Хартли.