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

Первая теорема Шеннона

Первая теорема Шеннона

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

Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:

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

Минимально возможным значением средней длины кода будет:

В качестве меры превышения К(А, В) над Kmin(А, В) можно ввести относительную избыточность кода (Q(А, В):

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

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

и первая теорема Шеннона получает следующую интерпретацию:

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

Для двоичных сообщений источника без памяти при кодировании знаками равной вероятности имеем:

Способы построения двоичных кодов

Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды

Префиксные коды без разделителей знаков

Суть первой проблемы состоит в нахождении такого варианта кодирования сообщения, при котором последующее выделение из него каждого отдельного знака (т. е. декодирование) оказывается однозначным без специальных указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условию Фано):

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом*) какого-либо иного более длинного кода.

Префиксный код Шеннона-Фано

Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, код является префиксным. Средняя длина кода равна:

I1(A) = 2,390 бит. Подставляя указанные значения в (3.5), получаем избыточность кода Q(A,2) = 0,0249, т. е. около 2,5%. Однако, данный код нельзя считать оптимальным, поскольку вероятности появления 0 и 1 неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода 0,0147.

Префиксный код Хаффмана

Из процедуры построения кодов вновь видно, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода, как и в предыдущем примере оказывается:

К(А,2) = 0,3 ∙ 2 + 0,2 ∙ 2 + 0,2 ∙ 2 +0,15 ∙ 3 + 0,1 ∙ 4 + 0,05 ∙ 4 = 2,45.

Избыточность снова оказывается равной Q(A, 2) = 0,0249, однако, вероятности 0 и 1 сблизились (0,47 и 0,53, соответственно).

Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточности кодов для какого-либо естественного языка. Применение описанного метода для букв русского алфавита порождает коды, представленные в таблице

Средняя длина кода оказывается равной К(r,2) = 4,395; избыточность кода Q(r,2) = 0,0090, т. е. не превышает 1 %, что заметно меньше избыточности кода Шеннона-Фано.

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

Источник

Эффективное статистическое кодирование сообщений. Теорема Шеннона для каналов без помех

Для дискретных каналов без помех К. Шенноном была доказана следующая теорема (первая теорема Шеннона):

Если производительность источника R = C – ε, где ε – сколь угодно малая величина, то всегда существует способ кодирования, позволяющий передавать по каналу все сообщения источника. Передачу всех сообщений при R > Cосуществить невозможно.

Как бы ни была велика избыточность источника, все его сообщения могут быть переданы по каналу, если R

, где τ₀ – длительность одного элемента кода.

При этом средняя длина кода определяется как . (4.5)

Соответственно тогда τ = K∙τ₀.

Величина V/K определена ранее как среднее число знаков первичного алфавита, транслируемых по каналу в единицу времени. Соответственно, величина K/V – это средняя длительность трансляции одного знака первичного алфавита, т.е. τ = K/V.

Значит, в соответствии с формулой (4.4) скорость передачи в канале . Подставляя выражения для средней длительности и энтропии, получим:

. (4.6)

Пример 4.2. Первичный алфавит состоит из трех знаков A, B, C с вероятностями p_A = 0,2; p_B = 0,7; p_C = 0,1. Для передачи по каналу без помех используются код Шеннона-Фано. Частота тактового генератора 500 Гц. Какова пропускная способность канала и скорость передачи?

Решение. Поскольку код Шеннона-Фано – двоичный, то m = 2; C =V = 500 бит/с.

Энтропия источника: H = – 0,2·log₂0,2 – 0,7·log₂0,7 – 0,1·log₂0,1 = 1,16бит

Длительность одного бинарного разряда в канале τ₀=1/V=0.002 c.

Закодируем первичный алфавит кодом Шеннона-Фано: A→10, B→0, C→11, длины кодов будут равны: n_A = 2; n_B = 1; n_C = 2

Средняя длина кода K = 0.2·2 + 0.7·1 + 0.1·2 = 1.3

(бит/с).

По сравнению с равномерным двоичным кодом (см. пример 4.1) скорость передачи возросла на 54% и приблизилась к пропускной способности.

Пример 4.3. Можно ли с помощью кодирования еще больше увеличить скорость передачи?

Решение. Первичный алфавит из примера 4.2 будем кодировать по парам символов (это так называемое укрупнение кодов). Пары символов, их вероятности, коды Шеннона-Фано и длины кодовых последовательностей приведены в таблице:

Средняя длина кодового слова для пары (см. формулу (4.5)) равна 2.42, следовательно, для одного символа – 1.21.

Скорость передачи (бит/с).

Скорость передачи еще больше приблизилась к своему пределу – пропускной способности канала.

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

Источник

Теорема Шеннона для канала без помех

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

Первая теорема Шеннона:если пропускная способность канала без помех превышает производительность источника сообщений, т.е. удовлетворяется условие C_k >V_u,

то существует способ кодирования и декодирования сообщений источника, обеспечивающий сколь угодно высокую надежность передачи сообщений. В противном случае, т.е. если C_k

2. Теорема Шеннона для канала с помехами

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

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

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

Источник

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

4.6. Теорема кодирования для канала с помехами

Пропускная способность канала, определенная в § 4.5, характеризует потенциальные возможности передачи информации. Они раскрываются в фундаментальной теореме теории информации, известной как основная теорема кодирования К. Шеннона. Применительно к дискретному источнику она формулируется так: если производительность источника сообщений Н(А) меньше пропускной способности канала С:

при сколь угодно малом положительном ε.

Положительный ответ на этот вопрос очевиден в тривиальном случае, когда в канале нет помех и сигнал В принимается безошибочно. При этом I'(В, B̂) = Н’ (В), и если между A и В установлено взаимно-однозначное соответствие, то по принятому сигналу можно однозначно восстановить сообщение. В общем же случае в канале имеются помехи и сигнал В принимается с ошибками, так что I'(В, B̂) H'(Л).

Это значит, что производительность сигнала В должна быть выше производительности источника сообщения A и, следовательно, В содержит кроме информации об A дополнительную собственную информацию. Часть информации о сигнале В в канале теряется. Вопрос сводится к следующему: можно ли осуществить кодирование так, чтобы терялась только дополнительная (избыточная) часть собственной информации В, а информация об A сохранялась?

Теорема Шеннона дает на этот вопрос почти положительный ответ, с той лишь поправкой, что скорость «утечки информации» (или ненадежность) Н'(А|Â) не равна в точности нулю, но может быть сделана сколь угодно малой. Соответственно сколь угодно малой может быть сделана вероятность ошибочного декодирования. При этом чем меньше допустимая вероятность ошибочного декодирования, тем сложнее должен быть код.

Существует несколько строгих доказательств теоремы Шеннона. Одно из них можно найти в [9]. Все они довольно сложны и поэтому здесь не приводятся. Они основаны на идее случайного кодирования. Для этого рассматривают не какой-либо конкретный код, а множество всех возможных кодов для данного источника и данного канала. Так, например, если канал двоичный, то рассматривают все коды, преобразующие всякую последовательность сообщений длительностью Т в различные последовательности двоичных символов, каждая из которых может быть передана за то же время Т.

Заметим, что если бы двоичный канал был без помех и допускал передачу двоичных символов со скоростью v_К, символ/с, то пропускная способность в расчете на секунду была бы

В этом случае обсуждаемая теорема свелась бы к изложенной выше теореме для источника. Действительно, согласно (4.28), в этом случае можно было бы закодировать последовательность сообщений так, чтобы передавать их со скоростью v_c, сколь угодно близкой к v_k/H(A) сообщений в секунду, т. е. так, чтобы v_cH(A) было как угодно близко к v_K. Но v_cH(A) = Н'(А) по определению, а v_K для канала без помех совпадает с С, так что условие (4.51) сводится к (4.28).

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

Функция E(R) называется показателем случайного кодирования. Основание степени 2 связано с тем, что здесь R и С измеряются в битах на секунду. Если бы они измерялись в натуральных единицах, то было бы удобнее применить основание степени е.

Предположим теперь, что задана скорость передачи информации R 0, то всегда можно выбрать такое достаточно большое значение T, при котором

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

Подчеркнем важный результат, непосредственно следующий из формул (4.57) и (4.58): верность связи тем выше, чем больше Т, т. е. чем длиннее кодируемый отрезок сообщения (а следовательно, и больше задержка при приеме информации), и чем менее эффективно используется пропускная способность канала (чем больше разность С-Н'(А), определяющая «запас пропускной способности» канала). Итак, существует возможность обмена между верностью, задержкой и эффективностью системы. С увеличением Т существенно возрастает сложность кодирования и декодирования (число операций, число элементов и стоимость аппаратуры). Поэтому практически чаще всего предпочитают иметь умеренное значение задержек Т, которые, кстати, не во всех системах связи можно произвольно увеличивать, и добиваются повышения верности за счет менее полного использования пропускной способности канала.

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

Источник

Основная теорема Шеннона о эффективном кодировании

В любом реальном сигнале всегда присутствуют помехи. Однако, если их уровень настолько мал, что вероятность искажения практически равна нулю, можно условно считать, что все сигналы передаются неискаженными. В этом случае среднее количество информации, переносимое одним символом, можно считать:

так как H(Y) = H(Z) и H(Y/Z) = 0, а max<J(Z; Y)> = H_max(Y) – max энтропия источника сигнала, получающаяся при равномерном распределении вероятностей символов алфавита Y.

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

где M_k – должно быть max возможное количество уровней, допустимое для передачи по данному каналу (конечно, M_k = M_y);

V_k – определяется частотными переключательными способностями канала:

Если источник информации создает поток информации

а канал связи обладает пропускной способностью С ед. информации в единицу времени, то при H(x) ≤ C:

Согласно сформулированной теореме существует метод кодирования, позволяющий при:

H(x) ≤ C – передавать всю информацию, вырабатываемую источником при ограниченном объеме буфера;

H(x) > C – такого метода кодирования не существует, так как требуется буфер, объем которого определяется превышением производительности источника над пропускной способностью канала, умноженной на время передачи.

Из этой теоремы вытекает следующее следствие: если источник информации имеет энтропию H(X), то сообщения всегда можно закодировать так, чтобы средняя длина кода l_ср (количество символов сигнала на одну букву сообщения) была сколь угодно близкой к величине:

где p_i – вероятность встречи данного элемента алфавита;

l_i – количество символов в i-ой кодовой комбинации;

ε – бесконечно малая величина ≥ 0, т.е. lim l_ср = H(x).

Это следует из равенства:

Таким образом, l_ср выступает критерием эффективности кодирования. Чем ближе l_ср к H(x), тем лучше мы закодировали. В инженерной практике это различие можно считать допустимым 3÷5% (до 10%). http://peredacha-informacii.ru/ Из этого же критерия следует, что если буквы имеют равномерное распределение вероятностей их употребления, то

а l_ср тоже равно log₂ M. Пределы эффективного кодирования:

Источник