5.7. Кодер для кодирования с предсказанием

Допустим, что исходное сообщение обладает некоторой структурой, которую можно выявить и использовать для предсказания следующего символа. Независимо от типа структуры, предположим, что существует программа, предсказывающая следующий символ. Метод предсказания может быть либо фиксированным, либо адаптивным в том смысле, что он может изменяться в зависимости от качества предыдущих предсказаний. Он может быть линейным или нелинейным; о существе метода предсказания ничего не говорится.

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

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

Рис. 5.7.1. Кодирование с предсказанием

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

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