Понятие о теоремах Шеннона

Кодирование букв и знаков (таблица ASCII кодов)

Код с проверкой четности. Для этого к двоичному коду добавляем контрольный разряд. Суммируем единицы по .

Это все отправляется в канал. Декодер вычисляет для каждого четвертого разряда наличие ошибок. Для исправления ошибок используется код Хемминга. В коде Хемминга к информационным разрядам добавляется некоторое число контрольных разрядов.

Шеннон сформулировал две теоремы.

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

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

Алгоритм создания кода Шеннона-Фанно:

1) n сообщений расположить в порядке убывания вероятностей их поступления;

2) разбиваем полученное множество на две группы так, чтобы суммы вероятностей групп были примерно равны;

3) одной группе ставим в соответствие 0, другой – 1;

4) каждая из групп снова разбивается на две группы (второй шаг) и т.д. до тех пор, пока все сообщения не будут закодированы.

Вычислим энтропию:

Вычислим среднюю длину кода: