в соответствии с теоремой шеннона можно найти такой способ кодирования чтобы избыточность кода была
Помехоустойчивое кодирование. Теорема Шеннона
Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных им в виде теоремы:
Хотя доказательство этой теоремы, предложенной Шенноном, в дальнейшем подвергалось более глубокому и строгому математическому представлению, идея его осталась неизменной. Доказывается только существование искомого способа кодирования, для чего находят среднюю вероятность ошибки по всем возможным способам кодирования и показывают, что она может быть сделана сколь угодно малой. При этом существует хотя бы один способ кодирования, для которого вероятность ошибки меньше средней.
Источник создает информацию со скоростью Vх букв в секунду и энтропией каждой буквы в среднем Н(х), т.е. его производительность:
В соответствии с теоремой о эффективном кодировании среднее количество символов на одну букву lср ≥ Н(х), т.е. в первом приближении можно получить, что
При наличии помех пропускная способность канала связи падает, т.е. при двоичном симметричном канале имеем:
Теорема о помехоустойчивом кодировании требует чтобы
где lср – средняя длина кодовой комбинации для записи одной буквы.
По сравнению с эффективным кодом lср увеличивается до:
Однако, такой величины lср1 помехоустойчивые коды не достигают. Это можно рассматривать как теоретический предел.
Теорема Шеннона для канала без помех
Рассмотрим две фундаментальные теоремы идеального кодирования, носящие имя Шеннона. Первая из них рассматривает случай отсутствия помех в канале, вторая учитывает наличие помех, приводящих к ошибкам.
Первая теорема Шеннона:если пропускная способность канала без помех превышает производительность источника сообщений, т.е. удовлетворяется условие Ck >Vu,
то существует способ кодирования и декодирования сообщений источника, обеспечивающий сколь угодно высокую надежность передачи сообщений. В противном случае, т.е. если Ck Vu.
| Получив одну из последовательностей Вк на выходе канала, мы должны принять решение относительно переданной последовательности. Как это сделать? Разобьем множество Вк на непересекающиеся подмножества Sk так, чтобы каждой переданной последовательности соответствовало своё подмножествоSk.. При этом выберем подмножества так, чтобы для каждой вход- ной последовательности вероятность попадания в своё подмножество была больше, чем в остальные. Принимая последовательность на выходе, смотрим, к какому подмножеству она относится, и в соответствии с этим принимаем решение о переданной типичной последовательности. |
Очевидно, что при этом велика вероятность правильно определить переданную последовательность, однако, возможны и ошибки. Ошибка возникает, если входная последовательность перейдет в несоответствующее ей множество Sk (на рис. 19 показан этот случай). Передача будет всегда безошибочной, если удастся так выбрать входные последовательности канала и разбиение Sk, что переходы в несоответствующие подмножества будут невозможны или, по крайней мере, будут иметь сколь угодно малую вероятность для больших Т. Возможна ли такая ситуация? Оказывается возможна.
Теорема Шеннона для канала с помехами оказала огромное влияние на становление правильных взглядов на возможности передачи сообщений и на разработку технически реализуемых методов помехоустойчивого кодирования. Шеннон показал, что для безошибочной передачи сообщений вовсе не обязательно вводить бесконечную избыточность и уменьшать скорость передачи информации до нуля. Достаточно ввести в сообщения источника такую избыточность, которая равна потерям количества информации в канале из-за действия помех.
Первая теорема Шеннона
Первая теорема Шеннона
смысл которого в том, что операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднее информационное содержание знака, т. е.:
Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информации на знак первичного и вторичного алфавитов.
Минимально возможным значением средней длины кода будет:
В качестве меры превышения К(А, В) над 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 %, что заметно меньше избыточности кода Шеннона-Фано.
Код Хаффмана важен в теоретическом отношении, поскольку можно доказать, что он является самым экономичным из всех возможных, т. е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана.
1. Первая теорема Шеннона. Основные понятия
Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе, необходимо отнести следующие:
Для представления дискретных сообщений используется некоторый алфавит. Однако однозначное соответствие между содержащейся в сообщении информацией и его алфавитом отсутствует.
В целом ряде практических приложений возникает необходимость перевода сообщения хода из одного алфавита к другому, причем, такое преобразование не должно приводить к потере информации.
Код — (1) правило, описывающее соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторичного алфавита.
(2) набор знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфавита.
Кодирование — перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.
Декодирование — операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов.
Кодер — устройство, обеспечивающее выполнение операции кодирования.
Декодер — устройство, производящее декодирование.
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.
Не обсуждая технических сторон передачи и хранения сообщения (т.е. того, каким образом фактически реализованы передача-прием последовательности сигналов или фиксация состояний), дается математическая постановка задачи кодирования.
смысл которого в том, что операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднее информационное содержание знака, т.е.:
Как следует из (3.4), минимально возможным значением средней длины кода будет:
Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информации на знак первичного и вторичного алфавитов.
Из (3.5) видно, что имеются два пути сокращения К min (А,В):
В качестве меры превышения К(А,В) над K min (А,В) можно ввести относительную избыточность кода (Q(А,В):
Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, Q(A,B) → 0 при К(А,В) → К min (А,В). Следовательно, решение проблемы оптимизации кода состоит в нахождении таких схем кодирования, которые обеспечили бы приближение средней длины кода к значению К min (А,В), равному отношению средних информации на знак первичного и вторичного алфавитов. Чем меньше Q(A,B), тем Ifin(В) ближе к Ist(A)), т.е. возникает меньше информации, связанной с кодированием, более выгодным оказывается код и более эффективной операция кодирования.
Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
и первая теорема Шеннона получает следующую интерпретацию:
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Применение формулы (3.7) для двоичных сообщений источника без памяти при кодировании знаками равной вероятности дает:
При декодировании двоичных сообщений возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) кодовых слов (групп элементарных сигналов), соответствующих отдельным знакам первичного алфавита. При этом приемное устройство фиксирует интенсивность и длительность сигналов, а также может соотносить некоторую последовательность сигналов с эталонной (таблицей кодов).
Возможны следующие особенности вторичного алфавита, используемого при кодировании:
Комбинации перечисленных особенностей определяют основу конкретного способа кодирования, однако, даже при одинаковой основе возможны различные варианты построения кодов, отличающихся своей эффективностью.
В соответствии с теоремой шеннона можно найти такой способ кодирования чтобы избыточность кода была
4.6. Теорема кодирования для канала с помехами
Пропускная способность канала, определенная в § 4.5, характеризует потенциальные возможности передачи информации. Они раскрываются в фундаментальной теореме теории информации, известной как основная теорема кодирования К. Шеннона. Применительно к дискретному источнику она формулируется так: если производительность источника сообщений Н(А) меньше пропускной способности канала С:
при сколь угодно малом положительном ε.
Положительный ответ на этот вопрос очевиден в тривиальном случае, когда в канале нет помех и сигнал В принимается безошибочно. При этом I'(В, B̂) = Н’ (В), и если между A и В установлено взаимно-однозначное соответствие, то по принятому сигналу можно однозначно восстановить сообщение. В общем же случае в канале имеются помехи и сигнал В принимается с ошибками, так что I'(В, B̂) H'(Л).
Это значит, что производительность сигнала В должна быть выше производительности источника сообщения A и, следовательно, В содержит кроме информации об A дополнительную собственную информацию. Часть информации о сигнале В в канале теряется. Вопрос сводится к следующему: можно ли осуществить кодирование так, чтобы терялась только дополнительная (избыточная) часть собственной информации В, а информация об A сохранялась?
Теорема Шеннона дает на этот вопрос почти положительный ответ, с той лишь поправкой, что скорость «утечки информации» (или ненадежность) Н'(А|Â) не равна в точности нулю, но может быть сделана сколь угодно малой. Соответственно сколь угодно малой может быть сделана вероятность ошибочного декодирования. При этом чем меньше допустимая вероятность ошибочного декодирования, тем сложнее должен быть код.
Существует несколько строгих доказательств теоремы Шеннона. Одно из них можно найти в [9]. Все они довольно сложны и поэтому здесь не приводятся. Они основаны на идее случайного кодирования. Для этого рассматривают не какой-либо конкретный код, а множество всех возможных кодов для данного источника и данного канала. Так, например, если канал двоичный, то рассматривают все коды, преобразующие всякую последовательность сообщений длительностью Т в различные последовательности двоичных символов, каждая из которых может быть передана за то же время Т.
Заметим, что если бы двоичный канал был без помех и допускал передачу двоичных символов со скоростью vК, символ/с, то пропускная способность в расчете на секунду была бы
В этом случае обсуждаемая теорема свелась бы к изложенной выше теореме для источника. Действительно, согласно (4.28), в этом случае можно было бы закодировать последовательность сообщений так, чтобы передавать их со скоростью vc, сколь угодно близкой к vk/H(A) сообщений в секунду, т. е. так, чтобы vcH(A) было как угодно близко к vK. Но vcH(A) = Н'(А) по определению, а vK для канала без помех совпадает с С, так что условие (4.51) сводится к (4.28).
Если это неравенство справедливо для средней вероятности ошибочного декодирования по всем кодам, то существуют такие коды, для которых неравенство (4.58) тем более справедливо.
Функция E(R) называется показателем случайного кодирования. Основание степени 2 связано с тем, что здесь R и С измеряются в битах на секунду. Если бы они измерялись в натуральных единицах, то было бы удобнее применить основание степени е.
Предположим теперь, что задана скорость передачи информации R 0, то всегда можно выбрать такое достаточно большое значение T, при котором
Теорема кодирования Шеннона справедлива для весьма широкого класса каналов, во всяком случае для всех каналов, которые были описаны в гл. 3, и для всех других каналов, представляющих практический интерес. В частности, она верна и при передаче дискретных сообщений по непрерывному каналу. В этом случае под кодированием понимают отбор некоторого количества реализаций u(t) входного сигнала на интервале Т и сопоставление с каждой из них последовательности элементарных сообщений, выдаваемой источником за тот же интервал Т.
Подчеркнем важный результат, непосредственно следующий из формул (4.57) и (4.58): верность связи тем выше, чем больше Т, т. е. чем длиннее кодируемый отрезок сообщения (а следовательно, и больше задержка при приеме информации), и чем менее эффективно используется пропускная способность канала (чем больше разность С-Н'(А), определяющая «запас пропускной способности» канала). Итак, существует возможность обмена между верностью, задержкой и эффективностью системы. С увеличением Т существенно возрастает сложность кодирования и декодирования (число операций, число элементов и стоимость аппаратуры). Поэтому практически чаще всего предпочитают иметь умеренное значение задержек Т, которые, кстати, не во всех системах связи можно произвольно увеличивать, и добиваются повышения верности за счет менее полного использования пропускной способности канала.
Примеры практического применения кодирования для повышения верности передачи информации будут приведены в последующих главах.