Помехозащищенное кодирование.

Кодирование длин повторений.

Хорошо работает при кодировании черно-белых изображений, например, чертежей.

Например, нужно закодировать: 3)

Заштрихованные – 1, пустые – 0.

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

Другой вариант:

В результате кодирования получаются относительно длинные последовательности нулей. 0000740000130000

В этом случае закодировать можно следующим образом: записывается флаг 0, затем количество нулей, затем значение оттенка, темнее или светлее. 04730514. Все кодируется по-своему.

Дифференциальное кодирование.

Его смысл – при сканировании изображения получаются величины освещенности точек.

154 149 157 164 160

Кодирование:

154 -5 +8 +7 -4

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

Помехозащищенное кодирование.

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

Эта теория базируется на результатах исследований, проведенных Шенноном. Его теоремы:

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

2) Не существует способа кодирования, который позволяет вести передачу информации со сколь угодно малой вероятностью ошибки, если производительность источника сообщений больше пропускной способности канала.

Отсюда следует, что помехи в канале не накладывают ограничений на скорость передачи, при которой может быть достигнута сколь угодно высокая точность. Сколь угодно малая вероятность ошибки достигается лишь при безграничном увеличении длительности кодируемых последовательностей. Таким образом, безошибочная передача при наличии помех возможно лишь теоретически. Весьма малую вероятность ошибки можно достичь при кодировании чрезвычайно длинными последовательностями. На практике точность передачи ограничивается двумя факторами:

· Размер и стоимость аппаратуры

· Временем задержки передаваемого сообщения

Пример помехозащищенного кодирования:

Применяется для обнаружения и/или исправления ошибок в результате действия помех. Например, пусть:

A₁, a₂, … a_k – сообщения

B₁, b₂, … b_k – действие помех

С₁ … с_n – принимаемые сообщения

A_i b_i c_i принимают значения 0 или 1.

A1a2…an + b1b2…bn = c1c2…cn., где с – искаженные кодовые комбинации.

Пусть передаваемые сообщения

A b c d

00 01 10 11

С возникающими ошибками связано понятие ее кратности (q). Это число искажаемых ошибкой разрядов, то есть число 1 в коде. Пусть для данных сообщений кратность ошибки равна 1, то есть в соответствии кодовой комбинации 01 и 10.

Предположим, передаем сообщение С, то е комбинация 10. Тогда возможны искажения:

Сообщение ошибка принимаем

10 01 11 D

10 10 00 A

То есть вместо символа С они получат либо Д, либо А, и ошибка не обнаружения.

Есть понятие кодовое расстояние и корректирующая способность кода. Под корректирующей способностью кода понимается его свойство обнаруживать и/или исправлять ошибку максимальной кратности q, и она связана с кодовым расстоянием. Кодовое расстояние d_ij между кодовыми комбинациями – число различных разрядов в кодовых комбинациях i и j, например, если есть коды 01 и 10, то расстояние между ними равно двум, так как они различаются в двух разрядах. Кодовое расстояние d для кода, содержащего m кодовых комбинаций – это минимальное расстояние между всеми парами кодовых комбинаций. Для рассмотренной ранее таблицы D_ab=1, d_ad=d_bc=2, d_bd=d_ac=d_cd=1. То есть здесь d=1. Это расстояние можно увеличить вводом в кодовые комбинации дополнительного разряда, и тогда исходные коды называют информационными, а дополнительные – проверочными. Значение одного дополнительного разряда определяется, как результат суммирования по модулю 2 информационных разрядов.

Провер. Код результирующий

A 00 0 000

B 01 1 011

C 10 1 101

D 11 0 110

Здесь для результирующих кодов все кодовые расстояния равны 2. D=2.

Предположим, передаем сообщение, соответствующее С, то е 101, и на него накладывается ошибка кратностью 1. Так как код трехразрядный, то ошибка может быть 001, 010, 100. Тогда на принимающей стороне будут комбинации 100, 111 или 001. НО! Результат декодирован быть не может, ибо ни один из вариантов не присутствует в результирующем коде.

НОМЕР РАСЧЕТКИ 6

Найти энтропии дискретных случайных величин икс игрек зет и количество информации содержащейся в зет = икс + игрек относительно игрек. Икс и игрек – независимы и задаются распределениями