Передача информации по каналу с шумом.

Рассмотрим теперь следующую более общую схему.

Источник

Кодер

Кодер II

Код

F

Канал

F-1

Декодер II

Декодер I

Получатель

 

Потери информации

Избыточность

 

 

Часть рисунка вне овала соответствует изучаемой раньше схеме, т.е.кодер (Кодер I) и декодер (Декодер I) – это, например, устройства реализующие алгоритм Хаффмена или что-то подобное. Но в отличие от предыдущего случая (канала без шума) добавился еще один кодер (Кодер II) и декодер (Декодер II). Их задача – обеспечить защиту передаваемой информации от шума в канале. Под шумом можно понимать самые разные искажения сигнала при передаче по каналу. Примеры моделей этих искажений приведены в следующем разделе.

Модели каналов.

1) Двоичный симметричный канал

P

1-P

1-P

P

1 1

P > 1/2

 

0 0

Канал называется двоичным, потому, что по нему передаются два сигнала: 0 и 1. Симметричность заключается в том, что они подвергаются искажениям в одинаковой степени. Вероятность правильной передачи P>1/2. (Ниже вероятность ошибки для удобства будем обозначать через p=1-P. При этом всегда будет понятно, о чем идет речь. Заметим, что критичный случай именно p=1/2. Если, например, p>1/2, то на приеме можно поменять местами 0 и 1. Ниже будет показано, что случай p=1/2 соответствует нулевой пропускной способности канала. Но это понятно и без всякой математики: что бы не попало в канала – на выходе с равной вероятностью будет принят или 0 или 1.

 

2)

P

1-P

1-Q

Q

Двоичный ассиметричный канал

1 1

P> 1/2, Q> 1/2

0 0

 

3) Двоичный стирающий канал

P

1-P

1 1

 

1-P

x – стирание

P

0 0

Пример:

Передаем 11011, p = 4/5, ошибка в четвертом символе.

Для двоичного канала на приеме может быть получена последовательность: 11001

Для канала со стиранием в этом случае будем иметь: 110х1.

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

4) Канал с выпадением.

P

1-P

1 1

 

1-P

Выпадение сомвола.

P

0 0

Пример:

Передаем 11011, p = 4/5, ошибка в четвертом символе.

Для двоичного канала на приеме может быть получена последовательность: 11001

Для канала с выпадением в этом случае будем иметь: 1101.

Для дальнейшего рассмотрения мы ограничимся одним случаем: двоичным симметричным каналом. Технически все полученные для этого случая результаты могут быть обобщены как на случай ассиметричного канала, так и на случай канала, передающего не два символа, а q символов.

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

8.2 Необходимые определения.

Пусть Bⁿ - булев куб размерности n.

Опр. Кодом C называется произвольное подмножество .

ПустьM– мощность множества C. Элементы этого подмножества будем называть кодовыми словами.

Опр. Пропускная способность канала - C (p) = 1 – H (p), где - энтропия канала.

Как раз для случаяp=1/2 энтропия равна единице, что соответствует полной неопределенности (абсолютному беспорядку), а пропускная способность канала нулевая.

Опр. Скорость передачи кода .

Если число слов, подлежащих передаче в канал, равно 2 ^k, то

- скорость передачи.

Опр. Расстояние Хемминга - это количество различных бит в x и y.

Пусть | x | -количество единиц в (норма или весx). Тогда очевидно, что

.

Опр. Кодовое расстояние .

Опр. (n,M,d)-код – это код C,такой, что | C | = M, C = { xⁱ }, xⁱ Bⁿ, d (C) = d.

 

Пример кода для канала с выпадением.

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

Пусть дан код C, α=(α₁,α₂,…,α_n) – кодовое слово. Положим .

Опр. C_nk – кодом называется множество слов α из Bⁿтаких, чтоw(α)=0 (modk).

Утв. C_nk – код является кодом с исправлением одного выпадения при k>n.

Доказательство. Пусть в слове αвыпал символ. В результате получилось слово β=(β₁, β₂,…, β_n-1) длины n-1. Пусть правее выпавшего символа расположено N₁ единиц и N₀нулей.Тогда, если выпал 0, тоw(α)-w(β)= N₁, а, если 1, тоw(α)-w(β)= N -N₀.В обоих случаях

0≤w(α)-w(β)≤N<k.

ПустьΔβ – наименьший неотрицательный вычет числа w(β) поmodk(Это разность kp-w(β), где kp –минимальное число, кратноеk и не меньшееw(β)).

Тогда из того, что w(α)=0 (modk) получаемw(α)-w(β)=Δβ. Так как N₁≤|β|<N -N₀, то на основании сравнения чисел |β| и Δβ можно определить выпавший символ.

1. Если |β| ≥ Δβ, то нужно вставить в слово символ 0 так, чтобы правее него было Δβ единиц.

2. В противном случае вставляется 1 так, чтобы правее нее было n- Δβ нулей.

Утверждение доказано.

Пример.

Пусть N=6 и k=7. Если в слове α=110100 выпал первый символ, то получилось β=10100. В этом случае:|β| =2,w(β)=4, поэтому Δβ=3.Так как |β| <Δβ, то исходное слово получается, если в принятом слове отсчитать справа n-Δβ нулей и поставить перед ними 1.

Упражнение. В качестве упражнения можете проверить, что подобный код может исправлять одну ошибку типа вставки (вместо выпадения появляется лишний символ) или замещения 0 на 1. А при k≥2nон может исправлять одну любую из этих трех видов ошибок.

Если же выпадает несколько символов, то задача декодирования может сводится к задаче восстановления слова по фрагментам.

Опр. Фрагментом слова α называется любое слово β, буквы которого образуют подпоследовательность последовательности букв слова α.

Зная n иp можно прогнозировать длины фрагментов l. Критерий восстановления слова по фрагментам с использованием этих параметров даст k– необходимое количество фрагментов для восстановления. Отсюда можно построить алгоритм декодирования с перезапросами: декодер, получив фрагмент принимает решение о его перезапросе. Набрав необходимое количество фрагментов, декодер произведет декодирование.

Заметим, что проколы такого типа (Ack – Nac)используются на втором уровне моделиOSI для случая кодов с обнаружением ошибок. (В таких кодах декодер не производит исправления ошибки, а только фиксирует ее появление. В случае же этого самого появления и используется протокол с перезапросом.)