Согласование дискретного источника с дискретным каналом

Задача № 3.23

Закодировать двоичным кодом Фано ансамбль сообщений {a_i}:

{0.08, 0.001, 0.06, 0.09, 0.017, 0.18, 0.4, 0.06, 0.003, 0.027, 0.014, 0.068}

Закодировать произвольную комбинацию, состоящую из 5 символов из ансамбля{a_i}. Определить потенциальный минимум среднего количества символов кода, приходящихся на одно сообщение ансамбля {a_i} и среднее количество символов, разработанного кода Фано, приходящихся на одно сообщение из ансамбля {a_i}. Рассчитать эффективность разработанного кода.

Решение.

Кодируется кодом Фано заданный ансамбль сообщений следующим образом.

Таблица 1 - Кодирование ансамбля сообщений {a_i} двоичным кодом Фано

Сообщения источника располагаются в порядке не возрастания их вероятностей, делятся на две части так, чтобы суммарные вероятности сообщений в каждой части были по возможности равны. Сообщениям первой части приписывается в качестве первого символа нуль, а сообщениям второй части единица. Затем каждая из этих частей (если она содержит более одного сообщения) опять делится на две примерно равные части и в качестве второго символа для первой из них берется 0, а для второй 1. Этот процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному сообщению.

После использования полученных комбинаций символов, закодируется произвольная комбинация, состоящая из 5 символов из ансамбля {a_i}: 101011111110010011110.

Среднее количество символов, приходящихся на одно сообщение, определяется по формуле 2.9 курса лекций:

,

где m_s – количество позиций, а p_s – вероятность сообщения из ансамбля {a_i}.

Определяется минимальное среднее количество символов, приходящихся на одно сообщение, по формуле

,

где M – объем алфавита кода, равный 2, а H(U) энтропия источника.

Далее находится энтропия:

Затем вычисляется величина ψ-эффективность кода, которая характеризует степень близости неравномерного статистического кода к оптимальному.

Задача № 3.56

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

Найти минимально возможную избыточность оптимального кода для симметричного канала при m = 8 и вероятности ошибки P = 0,08.

Решение:

Избыточность кода вычисляется по следующей формуле:

,

где H ¢ ( Z )= V_k * H ( Z )

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

H ¢ ( Z )= H ¢ ( U ),

где H ¢ ( U)- производительность источника, который передает информацию.

В соответствии с условием теоремы Шеннона

H ¢ ( U ) < C, а H ( U ) = С + ε = С; (ε→0),

тогда формула избыточности будет выглядеть следующим образом:

, при ε→0

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

C=V_k*[1+p*log₂p+(1-p)*log₂(1-p)]

Подставив известные значения в формулы, получается:

C=V_k *0.6