Последовательность

Коды с памятью

Обычно рассматривают два типа кодов с памятью:

- блочные коды;

- коды с конечной памятью.

Блочный код делит вектор данных на блоки заданной длины и затем каждый блок заменяют кодовым словом из префиксного множества двоичных слов. Полученную последовательность кодовых слов объединяют в результирующую двоичную строку на выходе кодера. О блочном коде говорят, что он - блочный код k -го порядка, если все блоки имеют длину, равную k .

Контекстное моделирование

Итак, нам необходимо решить задачу оценки вероятностей появления символов в каждой позиции обрабатываемой последовательности. Для того чтобы разжатие произошло без потерь, мы можем пользоваться только той информацией, которая в полной мере известна как кодеру, так и декодеру. Обычно это означает, что оценка вероятности очередного символа должна зависеть только от свойств уже обработанного блока данных.

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

Идея словарных методов

Входную последовательность символов можно рассматривать как после­довательность строк, содержащих произвольное количество символов. Идея словарных методов состоит в замене строк символов на такие коды, что их можно трактовать как индексы строк некоторого словаря. Образующие сло­варь строки будем далее называть фразами. При декодировании осуществ­ляется обратная замена индекса на соответствующую ему фразу словаря.

Можно сказать, что мы пытаемся преобразовать исходную последова­тельность путем ее представления в таком алфавите, что его "буквы" явля­ются фразами словаря, ...

Линейно-предсказывающее кодирование

Английское название метода - Linear Prediction Coding (LPC).

Цель - сжатие потока Я-битовых элементов в предположении, что зна­чение каждого из них является линейной комбинацией значений h преды­дущих элементов. Где S/ - i-й Л-битовый элемент; Kj - некоторые коэффициенты, в общем случае непостоянные.

Основная идея состоит в том, чтобы в формируемый поток записывать ошибки предсказаний: разности между реальными S, и предсказанными значениями:

Размер данных в результате применения LPC не изменяется. Более того, размер ...

Коды переменной длины

Первое правило построения кодов с переменной длиной вполне очевидно. Короткие коды следует присваивать часто встречающимся символам, а длинные - редко встречающимся. Однако есть другая проблема. Эти коды надо назначать так, чтобы их было возможно декодировать однозначно, а не двусмысленно. Маленький пример прояснит это.

Рассмотрим четыре символа ai, a2, аз и 04- Если они появляются в последовательности данных с равной вероятностью (=0.25 каждая), то мы им просто присвоим четыре двухбитовых кода 00, 01, 10 и 11. Все вероятности равны, и поэтому коды переменной длины не сожмут ...