Алгоритм сжатия jpeg кратко. Сжатие изображений: JPEG и JPEG2000. Старый добрый JPEG, несмотря на массу неоспоримых достоинств, все же имеет и существенные ограничения. Снять их был призван новый метод сжатия изображений, разработки которого велись уже да

Граф переходных вероятностей для такого канала может быть представлен на рис. 9.

Определим С:

Рис. 9. Граф переходных вероятностей К-ичного симметричного канала связи.

Канал со стиранием

Канал со стиранием

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

Рассмотрим двоичный симметричный канал связи со стиранием.

Рис. 10 Граф переходных вероятностей двоичного симметричного канала со стиранием

q – вероятность правильного приема;
p0 – вероятность ошибочного приема символа;
pC – вероятность получения стертого символа;
yЗ – символ стирания.

Если UС> UП2 , то фиксируется символ “1”.
Если UС< UП1 , то фиксируется символ “0”.
Если UП1 Ј UC Ј UП2 , то фиксируется символ стирания.

В канале связи могут возникать ошибки двух типов: ошибки трансформации и ошибки стирания.

Ошибка трансформации возникает с вероятностью p 0и для двоичного канала связи физически означает трансформацию “0” в “1” или “1” в “0”.

Ошибка стирания возникает с вероятностью pC . Под ней понимают прием вместо “1” или “0” какого-то третьего символа (символа стирания), который указывает на позицию искаженного символа.

Для двоичного симметричного канала связи ошибки трансформации и стирания не зависят от значения передаваемого символа.

Для канала со стиранием выполняется соотношение

p 0+ pC+ q = 1.

Определим скорость передачи информации в таком канале связи.

c = B [H (Y ) – H (Y/X )];

max H [Y ] обеспечивается при p (x 1) = p (x 2) = 0,5.

Равная вероятность приема символа yi имеет место при условии равной вероятности передачи xi , которое является необходимым, но еще недостаточным.

Будем считать, что p (x1 ) = p (x2 ) = 0,5. Тогда энтропия приемника будет максимальной.

В силу симметрии

Окончательно можно записать

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

1. pC= 0

· pC = 0, p 0= 0 (двоичный симметричный канал связи без стирания); c = B .

· pC № 0, p 0= 0 ; этот случай иллюстрирует ситуацию при отсутствии помех в канале связи и применении стирания. При этом скорость передачи информации уменьшается за счет применения стирания;

pC № 0, p 0№ 0 ; в этой ситуации канал связи может быть более “скоростным” лишь при выполнении определенных условий, о которых будет сказано ниже.

Обобщим изложенное по поводу ошибок, возникающих в канале связи.

В “обычном” канале связи возможна ошибка только одного вида: символ одного значения преобразуется в символ другого значения (то есть трансформируется). Такая ошибка называется ошибкой трансформации.

В канале связи со стиранием возможны ошибки двух видов: трансформации и стирания, когда символы переходят не друг в друга, а в символ стирания.

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

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

Все полученные результаты можно обобщить для k -ичного канала связи со стиранием, в котором на входе присутствует k символов, а на выходе – (2k – 1).

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

В перечисленных выше процессах передачи можно усмотреть определенное сходство. Общая схема передачи информации , , показана на рис.7.1 .

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

Рис. 7.1.

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

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

Некоторые типы ошибок:

Чаще других встречается замена знака. Этот тип ошибок исследован наиболее полно.

Способы повышения надежности передачи сообщений

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

Тогда закодированное сообщение имеет вид 011011100110. Если в первом знаке произойдет ошибка, то будет принято сообщение 111011100110, которое декодируется в слово . Полное искажение сообщения из-за одной ошибки происходит вследствие того, что одно кодовое слово переходит в другое кодовое слово в результате замены одного или нескольких знаков. Пример показывает, что оптимальное кодирование плохо защищает сообщения от воздействия ошибок.

На практике необходим компромисс между экономностью кода и защитой от ошибок.

Сначала удаляется "бесполезная" избыточность (в основном статистическая), а затем добавляется "полезная" избыточность , которая помогает обнаруживать и исправлять ошибки.

Рассмотрим некоторые методы повышения надежности передачи данных. Широко известными методами борьбы с помехами являются следующие :

1. передача в контексте;
2. дублирование сообщений;
3. передача с переспросом.

Рассмотрим подробней каждый из этих способов.

1. Передача в контексте. С этим хорошо известным и общепринятым способом сталкивался каждый, кто, пытаясь передать по телефону с плохой слышимостью чью-либо фамилию, называл вместо букв, ее составляющих, какие-нибудь имена, первые буквы которых составляют данную фамилию. В данном случае правильному восстановлению искаженного сообщения помогает знание его смыслового содержания.
2. Дублирование сообщений . Этот способ тоже широко применяется в житейской практике, когда для того, чтобы быть правильно понятым, нужное сообщение повторяют несколько раз.
3. Передача с переспросом . В случае, когда получатель имеет связь с источником сообщений , для надежной расшифровки сообщений пользуются переспросом, т. е. просят повторить все переданное сообщение или часть его.

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

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

Естественно выбирать такие формы введения избыточности, которые позволяют при минимальном увеличении объема сообщения обеспечивать максимальную помехоустойчивость.

Принципы обнаружения и исправления ошибок с использованием кодов

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

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

Рассмотрим схему передачи данных, показанную на рис.7.3 .

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

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

В геометрической интерпретации эти блоки можно рассматривать как точки n-мерного пространства , где . Точки этого пространства представляют собой последовательности чисел 0 и 1 длины . Пространства для можно представить в виде угловых точек единичного интервала (), вершин квадрата со стороной, равной 1 (), и вершин куба с ребрами длины 1 (). Эти пространства условно изображены на рис.7.5 .

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

Дискретный канал связи с помехами

Мы будем рассматривать дискретные каналы связи без памяти.

Каналом без памяти называется канал, в котором на каждый передаваемый символ сигнала, помехи воздействуют, не зависимо от того, какие сигналы передавались ранее. То есть помехи не создают дополнительные коррелятивные связи между символами. Название «без памяти» означает, что при очередной передаче канал как бы не помнит результатов предыдущих передач.

При наличии помехи среднее количество информации в принятом символе сообщении - Y , относительно переданного - X равно:

Для символа сообщения X T длительности T, состоящего из n элементарных символов среднее количество информации в принятом символе сообщении - Y T относительно переданного - X T равно:

I(Y T , X T ) = H(X T ) - H(X T /Y T ) = H(Y T ) - H(Y T /X T ) = n }