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

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

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

Полное математическое описание канала связи с помехами состоит в задании

• числа m – числа элементарных сигналов, передаваемых по данной линии связи;

• числа v_x – скорости передачи элементарных сигналов;

• канальной матрицы вероятностей.

Последовательность символов x₁, x₂, …, x_m, создаваемая источником, может претерпевать искажения по пути к приемнику.

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

Принимая во внимание, что до приема сигнала, мы располагали только информацией H(x), можно записать

I_k=H_апр – H_апост = H(x) – H(x/y_k)

Здесь H(x/y_k) – это та неопределенность, которая осталась у нас после приема сигнала y_k. Очевидно, что величина I_k является случайной и необходимо ее усреднить по всему множеству принимаемых символов:

I=M[I_k] = H(x) – M[H(x/y_k)]= H(x) – H(x/y)

M[H(x/y_k)] = P(y₁) H(x/y₁)+ P(y₂) H(x/y₂)+…+ P(y_m) H(x/y_m) =

=

Канальная матрица вероятностей определяет условную вероятность передачи сигнала x_i при условии, что принят был сигнал y_j.

Заметим, что H(x) ≠ H(y).

Пропускная способность бинарного симметричного канала с помехами

Определим пропускную способность двоичного симметричного канала (ДСК). Канал считается симметричным, если

P_0→1= P_1→0=P и P₁₁=P₀₀=1- P,

где p=р_ош.

Матрица для нахождения условной вероятности

Найдем полную условную энтропию системы y относительно x

График функции имеет следующий вид:

Рис.3.3. График функции С=f(p)

Наибольшее значение эта функция принимает при p=0 (то есть при отсутствии помех) и при p=1 (то есть при негативной передаче).

При p=1/2 пропускная способность минимальна.

Рассмотрим более общий случай передачи по дискретному каналу. Найдем пропускную способность m-ичного канала связи.

На рис. 3.4 представлена модель передачи m-ичных сигналов, где x₁,х₂,…,х_m источники информации, y₁,y₂,…,y_m приемники информации.

Рис.3.4. m-ичный канал передачи информации

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

Матрица условных вероятностей имеет вид

Полная условная энтропия системы Y относительно X

График функции С(p) пропускной способности канала связи при m=4 представлен на рис.3.5

Рис.3.5. График функции C(p)

Эта функция максимальна при p=0, при вероятности При p=1

Теоремы Шеннона для канала с шумами

Основная теорема о кодировании для канала с помехами аналогична теореме о кодировании для канала без помех.

Пусть

• K — длина блока, генерируемого источником

• L — длина блока, который будет передан по каналу (после кодирования)

• R — скорость передачи сообщений (производительность источника)

R = K / L

• C — пропускная способность канала, определяемая как максимум взаимной информации на входе и выходе канала (X и Y — представление входа и выхода канала как случайных величин)

C = max(I(X;Y))

• P_er — средняя вероятность ошибки декодирования блока

• Per,max – максимальная вероятность ошибки декодирования блока

Прямая теорема

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

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

Обратная теорема

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

Если канал связи обладает пропускной способностью С(бит/с), а энтропия источника равна H(z) (бит/сообщение), то

1. сообщение, вырабатываемое источником, всегда можно закодировать так, чтобы скорость v_z передачи была сколь угодно близка к величине

v_zm=C / H(Z) [символ/сек]

и чтобы вероятность ошибки в определении каждого переданного символа была меньше любого заданного числа

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

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

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