ТВ растр с чересстрочной разверткой

избыточность может быть устранена без потери информации, исходные данные при

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

символ

При статистическом кодировании изображений степень сжатия – 1,5-3
При устранении визуальной

избыточности отдельных изображений – 8-12 раз без видимых искажений

генерация кода
хранение описания способа кодирования

алфавита X = {a1, …, aN} на двоичную строку C(ai), называемую кодовым словом. Количество

бит в кодовом слове C(ai) называется его длиной l(ai).
Кодовые слова передаются последовательно без указания их границ. Декодер должен уметь различать границы кодовых слов, начиная с какой-то стартовой позиции. Отсюда вытекает необходимость однозначной декодируемости кодов переменной длины. При этом предполагается, что начальное положение декодирования известно (проведена начальная синхронизация).
Однозначная декодируемость требует, во-первых, чтобы C(ai) ≠ C(aj) для любых i ≠ j. Также необходимо, чтобы кодовые слова были различимы в строке, составленной из любой их последовательности.

для любой последовательности символов источника данных x1, x2, …, xn соответствующая последовательность кодовых

слов C(x1)C(x2)…C(xn) отличается от последовательности кодовых слов C(x'1)C(x'2)…C(x'n) любой другой последовательности символов источника x'1, x'2, …, x'n.
Рассмотрим, например, два варианта кодов для алфавита, состоящего из трех символов: X = {a1, a2, a3}.
Первый вариант кодов: C1(x1) = 1; C1(x2) = 00; C1(x3) = 01. Такие коды однозначно декодируемы.
Второй вариант кодов: C1(x1) = 1; C1(x2) = 0; C1(x3) = 01. Такие коды не обладают свойством однозначной декодируемости, так как коды последовательности символов x2, x1 совпадают с кодом символа x3.
Свойство однозначной декодируемости зависит от множества кодовых слов и не зависит от способа отображения символов алфавита на кодовые слова.

коды формируются:
- гамма-код: унарное представление числа k, за которым следует

двоичное представление числа (n - 2k) (длина кода – 2k + 1 бит);
- дельта-код: гамма-код для числа (k + 1), за которым следует двоичное представление числа (n - 2k) (длина кода – 2L + k + 1 бит, L = [log2(k + 1)].

представить этот номер в виде: n = qm + r,

где q и r - целые положительные числа, 0 ≤ r < m, m – параметр кодов.
Кодируемое число разбивается на две независимо кодируемые части: частное и остаток от деления на m: q = [n/m] и r = n - mq.
Частное q кодируется унарным кодом, а остаток r, представляющий собой число в диапазоне [0, …, m − 1], кодируется бинарным кодом длиной [log2m]. Полученные двоичные последовательности объединяются в результирующее слово.

Пример: параметр кода m = 4, кодируемое число n = 13.
q = [n/m] = [13/4] = 3, унарный код a(q) = a(3) = 1110
r = n ‑ m•q = 13 ‑ 4•3 = 1 (число в диапазоне [0, …, m − 1] = [0, …, 3]), бинарный код b(r) = b(1) = 01
результирующее кодовое слово - a(q) | b(r) = a(3) | b(1) = 1110 | 01.

Коды Райса – частный случай кодов Голомба, когда m - степень двойки.
Коды Райса различаются параметром k, связанным со значением m соотношением m = 2k (при k = 0, m = 1, коды Голомба и Райса соответствуют стандартному унарному коду).

L1, L2, L3, …, Lm бит, которые начинаются с 1,

а в конце последовательности следует 0.
Длина каждой следующей (n + 1)-й группы задается значением битов предыдущей n-й группы. Значение битов последней группы является итоговым значением всего кода (первые m − 1 групп служат для указания длины последней группы).
В омега-кодах Элиаса длина первой группы – 2 бита. Длина следующей группы на единицу больше значения предыдущей. Первое значение (1) задается отдельно.
В кодах Ивэн-Родэ длина первой группы – 3 бита, а длина каждой последующей группы равна значению предыдущей. Первые четыре значения (0 - 3) заданы особым образом.

длин кодовых слов, то можно легко построить уникально-префиксный код с

таким же набором длин кодовых слов
кодовое слово уникально-префиксного кода может быть декодировано сразу после получения последнего бита этого кодового слова
при заданном распределении вероятностей символов источника данных можно легко сконструировать уникально-префиксный код минимально возможной длины
Префиксом строки a1a2…an называется начальная подстрока этой строки a1a2…am, где m < n. Код является уникально-префиксным, если ни одно кодовое слово этого кода не является префиксом никакого другого кодового слова.

не обязательно обладают уникальными префиксами. Например, коды C(a) = 0; C(b) = 01; C(c) = 011

могут быть однозначно декодированы, так как 0 в данном случае означает начало нового кодового слова, но эти коды имеют одинаковые префиксы.

с ошибками декодер может потерять синхронизацию и допустить ошибочное декодирование

одного или более символов. Поэтому важным вопросом является синхронизируемость кодов переменной длины.
Например, уникально-префиксный код {0, 10, 110, 1110, 11110} является мгновенно самосинхронизируемым, потому что каждый 0 является признаком окончания кодового слова.
Более короткий код {0, 10, 110, 1110, 1111} является вероятностно самосинхронизируемым: каждый 0 является признаком окончания кодового слова, но так как может встречаться последовательность кодовых слов 1111 произвольной длины, время до повторной синхронизации является случайной величиной.

для заданного алфавита X = {a1, …, aM} при заданном множестве длин кодовых слов

{l(aj); 1 ≤ j ≤ M}.
Теорема о неравенстве Крафта формулируется следующим образом: любой уникально-префиксный код для алфавита X = {a1, …, aM} с длинами кодовых слов {l(aj); 1 ≤ j ≤ M} удовлетворяет следующему условию:


И наоборот, если это условие выполнено, то существует уникально-префиксный код с длинами кодовых слов {l(aj); 1 ≤ j ≤ M}. Более того, любой полный уникально-префиксный код удовлетворяет неравенство Крафта при строгом равенстве, а любой неполный уникально-префиксный код удовлетворяет неравенство Крафта при строгом неравенстве.
Например, эта теорема означает, что существует полный уникально-префиксный код с длинами кодовых слов {1, 2, 2}, но не существует уникально-префиксных кодов с длинами кодовых слов {1, 1, 2}.

двоичной системе счисления. Двоичная дробь 0,y1y2…yl представляет собой запись действительного

числа:
Как и в случае десятичных дробей, двоичные дроби можно использовать для аппроксимации действительных чисел с определенной точностью. Двоичная дробь 0,y1y2…yl является аппроксимацией чисел из интервала:
Этот интервал размером 2-l включает все числа, представление которых в виде двоичной дроби начинается с 0,y1y2…yl.
Любое кодовое слово C(aj) длины l можно записать в виде действительного числа на интервале [0, 1), представляющего интервал размером 2-l, который включает все строки, содержащие C(aj) как префикс.

коды имеют различное количество бит;
- коды символов, обладающих меньшей вероятностью,

имеют больше бит, чем коды символов с большей вероятностью;
- хотя коды имеют различную битовую длину, они могут быть декодированы единственным образом.
Символы алфавита сортируются по убыванию вероятностей их появления, упорядоченный ряд разбивается на две части, чтобы суммы вероятностей появления символов, отнесенных к каждой части были бы примерно равны. Символам первой части присваивается код «0», а второй части – «1».
Разделенным на две составляющие первой части присваиваются коды соответственно «00» и «01», а второй части – «10» и «11» и.т.д.

подход: кодовые схемы используют коды только тех информационных последовательностей, которые

реально порождаются информационным источником
Словарные модели опираются на информационную структуру, реализуемую словарем; словарь включает в себя части уже обработанной информации, на основе которых осуществляется кодирование
Составляющие последовательности символов информационного источника кодируются посредством ссылок на идентичные им элементы словаря (совпадения)
Словарные методы отличаются друг от друга способом организации словаря, схемой поиска совпадений и видом ссылки на найденное совпадение
Впервые эти методы были описаны в работах А. Лемпела (A. Lempel) и Я. Зива (J. Ziv), первый вариант словарного алгоритма был описан в 1977 году и был назван LZ-77 по первым буквам фамилий авторов

из них M = N - n – уже закодированные символы, являющиеся словарем. Предположим,

к текущему моменту закодировано m символов: s0, s1, s2, …, sm-1, часть из которых sm-M, …, sm-2, sm-1 записаны в словаре, а в буфере записаны ожидающие кодирования символы sm, sm+1, …, sm-1+n.

обозначенную далее как «пакуемая строка».

Закодированная последовательность представляет предысторию, пакуемая строка

– постисторию:
..111101011100001010010001010100101110|0100010111..

Выпишем все подпоследовательности из предыстории, которые совпадают с первым и более начальными битами предыстории (отсчет бит ведется справа налево, в данном случае первый бит равен «0»):

При этом анализируется последовательность символов справа налево начиная от символа

«|». Т.е. последовательность ..110000| лексикографически меньше последовательности ..001000|. Слева проставлен номер строки. Пакуемой строке (с ее предысторией) присваивается номер 0, от нее номера вверх возрастают, а вниз убывают:

..11110101110000|1010010001010100101110
14 ..11110101110000101001000|1010100101110
13 ..1111010111000|01010010001010100101110
12 ..1111010111000010100100|01010100101110
11 ..1111010111000010100|10001010100101110
10 11101011100001010010001010100|101110
9 ..111101011100|001010010001010100101110
8 ..1111010111000010|10010001010100101110
7 ..1111010111000010100100010|10100101110
6 ..111101011100001010010|001010100101110
5 ..11110101110000101001000101010010|1110
4 ..111101011100001010|010001010100101110
3 ..111101011100001010010001010|100101110
2 ..11110101110000101001000101010|0101110
1 ..1111010|11100001010010001010100101110
0 ..111101011100001010010001010100101110|0100010111..
-1 ..11110101110|0001010010001010100101110
-2 ..11110|1011100001010010001010100101110

Этот список называют левосторонним ассоциативным списком или «воронкой аналогий» в терминологии автора алгоритма.

(в противоположном направлении - слева направо после «|», т.е. последовательность

|110000.. лексикографически больше последовательности |001000..):
-1 ..11110101110|0001010010001010100101110
9 ..111101011100|001010010001010100101110
6 ..111101011100001010010|001010100101110
4 ..111101011100001010|010001010100101110
0 ..111101011100001010010001010100101110|0100010111..
13 ..1111010111000|01010010001010100101110
12 ..1111010111000010100100|01010100101110
2 ..11110101110000101001000101010|0101110
11 ..1111010111000010100|10001010100101110
8 ..1111010111000010|10010001010100101110
3 ..111101011100001010010001010|100101110
15 ..11110101110000|1010010001010100101110
7 ..1111010111000010100100010|10100101110
14 ..11110101110000101001000|1010100101110
10 ..111101011100001010010001010100|101110
-2 ..11110|1011100001010010001010100101110
1 ..1111010|11100001010010001010100101110
5 ..11110101110000101001000101010010|1110

пакуемой строке:
4

..111101011100001010|010001010100101110
0 ..111101011100001010010001010100101110|0100010111..
13 ..1111010111000|01010010001010100101110
Код пакуемой строки состоит из трех частей.

1. Номер строки, максимально совпадающей с пакуемой строкой. В данном случае – 4. Этот номер кодируется любым эффективным префиксным или арифметическим кодом. В качестве эквивалента вероятности автор алгоритма предложил использовать длину совпадения строки предыстории пакуемой строки со строками предысторий из рассмотренного списка с соответствующей нормировкой.

2. Бит различия – первый бит пакуемой строки, отличающий ее от строки, максимально с ней совпадающей. В данном случае – 1 (отмечен подчеркиванием):
- в пакуемой строке – 010001011,
- в максимально близкой к ней 4-й строке – 010001010100101110.
Этим битом определяется положение максимально близкой строки: если бит 0 – то эта строка выше, если 1, то ниже. В данном случае пакуемая строка ниже.

количество нулей или единиц в той части пакуемой строки (ниже

отмечено подчеркиванием значений 0101), которая находится между битом различия максимально совпадающей строки (бит отмечен подчеркиванием в нижней строке) и битом различия второй строки (бит отмечен подчеркиванием в верхней строке). Если пакуемая строка лексикографически старше строки, максимально совпадающей с ней, то передается количество нулей, а если младше – то количество единиц. В данном случае подсчитывается количество нулей, которое равно 2.
01010010001010100101110
0100010111..
010001010100101110
Длина «вытяжки» также кодируется адаптивным статистическим кодером.

Таким образом, упакована строка 010001011 (до бита различия включительно).
Операция восстановления строки осуществляется следующим образом:

строки максимального совпадения (в данном случае 4).
2. По биту различия

определяется положение запакованной строки (и соседней строки) – если бит «0», то она выше (лексикографически младше, длина «вытяжки» - количество единиц), в противном случае – ниже (лексикографически старше, длина «вытяжки» - количество нулей) (в данном случае номер соседней строки – 13, она лексикографически старше).
3. Копируется в искомую строку совпадающая часть строки максимального совпадения (4, 010001010100..) и соседней (13, 010100100010..), а также следующий бит из строки максимального совпадения (в данном случае совпадающая часть - 010, а следующий бит – 0).
4. Декодируется длина «вытяжки» (2).
5. Восстанавливается следующая часть искомой строки по «вытяжке» - копируются из строки максимального совпадения следующие биты, включающие соответствующее длине вытяжки количество нулей или единиц (в данном случае два нуля, так как искомая строка лексикографически старше; строка максимального совпадения – 010001010100.., из нее уже скопировано 4 бита, 0100, значит, копируется 010). Далее копируется из строки максимального совпадения все биты до следующего нуля или единицы (в данном случае – до следующего нуля, то есть 1). Таким образом, восстановленная по «вытяжке» часть строки - 0101.
6. Дописывается в искомую строку бит различия (в данном случае – 1, а в строке максимального совпадения следующий бит, естественно, 0).
7. Таким образом, восстановлена строка 010001011, что и требовалось.