Принцип построения кода Шеннона - Фано

Предисловие

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

При выполнении лабораторных работ используется пакет прикладных программ MathCAD.

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

Лабораторная работа № 3

КОД ШЕННОНА - ФАНО

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

Введение

При выполнении лабораторной работы №2 «Двоичный канал передачи информации» [1] установлено, что пропускная способность С_с двоичного симметричного канала при отсутствии шумов определяется длительностью τ одного символа кода, которым закодированы сообщения

, (1)

где m – число разрядов двоичного кода;

t – длительность символа кода с учетом того, что все символы обычно имеют одинаковую длительность;

T = m t –длительность одного сообщения;

H(X_T) – энтропия ансамбля n = 2^m сообщений на входе двоичного канала.

Пропускная способность канала, определяемая (1), принимает максимальное значение, когда энтропия ансамбля сообщений H(X_T) будет наибольшей. Из свойств энтропии (см. лабораторную работу №1 [1]) следует, что H(X_T) будет максимальна, если сообщения равновероятны. Таким образом, это максимальное значение может быть определено мерой Хартли и будет равно log n = log 2^m = m.

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

Поясним это обстоятельство на следующих примерах.

Пример 1. Пусть источник сообщений вырабатывает четыре сообщения х₁, х₂, х₃, х₄,(n = 4), вероятности которых одинаковые: P(x_i) = 1/n = 0,25. Для кодирования сообщений используется двоичный равномерный код, число символов (разрядов) в котором достаточно выбрать m = 2. Тогда исходные сообщения х₁, х₂, х₃, х₄ в этом примере будут представлены следующими кодами: 00, 01, 10, 11.

В этом случае энтропия источника сообщений

Скорость передачи информации определяется как отношение энтропии к средней длительности сообщения. Длительность каждого из четырех сообщений определяется длительностями соответствующих кодовых комбинаций и составляет t _с =2t.

Таким образом, скорость передачи информации определится как

В этом примере, как и следовало ожидать, скорость передачи информации равна пропускной способности канала: .

Пример 2. Источник сообщений и способ их кодирования такие же, как и в примере 1, но вероятности сообщения при этом не одинаковы:

Р(х₁) = 0,5; Р(х₂) = 0,25; Р(х₃) = Р(х₄) = 0,125.

Энтропия источника разновероятных сообщений х₁, х_2,х₃, х₄ (n = 4) определяется формулой Шеннона:

. (2)

Для данного примера H(X)=1,75 дв.ед/сообщ.

Длительность каждого сообщения остается такой же, как и в примере 1: t _с = 2t . Скорость передачи информации составит

В этом примере скорость передачи информации оказалась меньше пропускной способности двоичного канала C _с(0,875/ t <1/ t).

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

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

1. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

Возможность построения эффективных кодов согласуется с основной теоремой Шеннона для дискретного канала без помех [2].

Теорема формулируется следующим образом: если поток информации , вырабатываемой источником сообщений, равен , где x – сколь угодно малая величина, то всегда можно найти такой способ кодирования, который обеспечивает передачу всех сообщений, вырабатываемых источником, причем скорость передачи информации будет сколь угодно близка к пропускной способности канала: = С_с– x .

Обратное утверждение состоит в том, что невозможно обеспечить передачу всех сообщений источника, у которого .

К эффективным относится, в частности, код Шеннона.-.Фано, пригодный для кодирования статистически независимых сообщений.

Принцип построения кода Шеннона - Фано

Для согласования статистических характеристик источника сообщений с пропускной способностью канала связи сообщения с большей вероятностью появления кодируются меньшим количеством символов [3]. За счет этого средняя длительность сообщения становится меньше длительности сообщения при кодировании его равномерным кодом. А поскольку скорость передачи информации определяется, как отмечалось выше, отношением энтропии источника сообщений к средней длительности одногшо сообщения, то скорость передачи информации увеличивается.

Дата добавления: 2020-01-07; просмотров: 193; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 5 6 Следующая ⇒

Мы поможем в написании ваших работ!