Васюков В.Н. - Теория электрическо связи - Часть 3. Теория информации и теория помехоустойчивости (1275348), страница 3
Текст из файла (страница 3)
В простейшем случае бинарногоканала без помех (см. пример 2) пропускная способность равна скорости модуляции vп = 1/ Tп .Объем алфавита источника и количество различных символов, передаваемых по каналу (канальных символов), могут не совпадать. В таких случаях один символ источника представляется (кодируется) последовательностью из нескольких кодовых символов (кодовым словом, или кодовой комбинацией). Если для всех символов источника длина кодовых слов одинакова,код называют равномерным, в противном случае – неравномерным. Примером равномерного кода является код Бодó, смысл которого состоит в представлении каждой из букв алфавита двоичным числом фиксированной разрядности (например, для алфавита из 32 символов, включающего 26 латинских букв и знаки препинания, достаточно пятиразрядного кода Бодо). Припередаче сообщений неравномерным кодом говорят о средней длине кодового слова (усреднение длин кодовых слов производится по соответствующемураспределению вероятностей).Шеннону принадлежит следующая теорема (доказательство см., напр.,в [1]), называемая основной теоремой о кодировании в отсутствие шумов.16ТЕОРЕМА.
Среднюю длину кодовых слов для передачи символов источника Α при помощи кода с основанием m можно как угодно приблизитьк величине H ( Α) / log m .Смысл теоремы состоит в том, что она определяет нижнюю границудлины кодовых слов и устанавливает принципиальную возможность достичьэтой границы, однако она не указывает способов достижения.Пример 3. Если источник имеет объем алфавита 32, то при равновероятных символах его энтропия равна 5 битам. Тогда для двоичного кода наименьшая средняя длина составляет 5, следовательно, пятизначный код Бодоявляется оптимальным кодом.
Однако при неравных вероятностях символовэнтропия источника меньше чем 5 бит (избыточность источника отлична отнуля), следовательно, можно найти код со средней длиной кодового словаменьше пяти и таким образом повысить скорость передачи информации.Текст на русском языке, например, имеет энтропию около 2,5 бит, поэтомупутем соответствующего кодирования можно увеличить скорость передачиинформации вдвое против пятиразрядного равномерного кода Бодо (чтобыможно было использовать код Бодо для передачи русского текста, можноотождествить буквы «е» и «ё», а также «ь» «ъ»).♦Практическое значение теоремы Шеннона заключается в возможностиповышения эффективности систем передачи информации (систем связи) путем применения экономного кодирования (кодирования источника).Очевидно, что экономный код должен быть в общем случае неравномерным.
Общее правило кодирования источника (без памяти) состоит в том,что более вероятным символам источника ставятся в соответствие менеедлинные кодовые слова (последовательности канальных символов).Пример 4. Известный код Морзе служит примером неравномерногокода. Кодовые слова состоят из трех различных символов: точки • (передается короткой посылкой), тире ― (передается относительно длинной посылкой) и пробела (паузы). Наиболее частой букве в русском тексте – букве «е»– соответствует самое короткое кодовое слово, состоящее из одной точки,17относительно редкая буква «ш» передается кодовым словом из четырех тире,и т.д. ♦Кодирование источника по методу Шеннона – Фано.Принцип построения кода Шеннона – Фано состоит в упорядочениивсех символов алфавита (назовем их для краткости «буквами») по убываниювероятностей. Затем все буквы делятся на две (неравные в общем случае)группы, так, что сумма вероятностей букв для обеих групп одинакова илипримерно одинакова, и в качестве первого символа кодового слова каждойбукве первой группы присваивается кодовый символ 0, а каждой букве второй группы – символ 1 (или наоборот).
Далее первая и вторая группы делятсяна подгруппы в соответствии с принципом равной вероятности, и эта процедура продолжается до тех пор, пока алфавит источника не будет исчерпан.Пример построения кода Шеннона – Фано приведен в табл. 1.Таблица 1Построение кода Шеннона – ФаноСимвол и егоДлинаКомбинация кодовых символоввероятностькомбинацииαip (α i )1-й2-йα11/4002α21/4012α31/4102α41/8110α51/161110α61/3211110α71/641111106α81/6411111163-й184-й5-й6-йµi345На первом шаге процедуры все символы алфавита источника делятсяна две группы, причем в первую группу входят символы α1 и α 2 , которымсоответствует суммарная вероятность 1/2, а во вторую – все остальные символы. Символам α1 и α 2 сопоставляется в качестве первого кодового символа символ 0, а всем остальным символам источника – кодовый символ 1.
Навтором шаге первая и вторая группы рассматриваются по отдельности, приэтом в первой группе содержатся всего два символа, которые получают в качестве второго кодового символа 0 и 1 соответственно. Таким образом, символу источника α1 сопоставляется кодовое слово 00, а символу α 2 – слово01.
Вторая группа символов источника, включающая символы α 3 , α 4 , α 5 иα 6 , делится на две части в соответствии с их вероятностями, при этом символ α 3 , которому соответствует вероятность 1/4, получает в качестве второгосимвола кодового слова символ 0, а остальные символы источника – символ1. Далее процесс продолжается до тех пор, пока не останется группа из двухсимволов – в данном примере это символы α 7 и α8 , – которым присваиваются кодовые символы 0 и 1.Необходимо обратить внимание на следующее свойство полученногокода: ни одна кодовая комбинация не является началом какой-либо другойкодовой комбинации (так называемое префиксное правило). Такие коды называются неперекрываемыми (неприводимыми). Декодирование неприводимого кода может быть осуществлено в соответствии с деревом декодирования3(рис.
2), соответствующим некоторому конечному автомату, которыйпереходит из начального состояния в другие состояния в соответствии с очередным символом кодовой последовательности.Перед декодированием конечный автомат устанавливается в начальноесостояние НС, а дальнейшие переходы зависят только от поступающих символов кода, при этом все концевые состояния («листья» дерева) соответствуют декодированным символам алфавита источника; по достижении листа ав3Деревом называется граф, не имеющий циклов (замкнутых путей)19томат переходит вновь в начальное состояние. Поскольку с поступлениемпоследнего кодового символа декодирование кодового слова всегда заканчивается, префиксные коды называют также мгновенными [2].
Существуют однозначно декодируемые коды, не обладающие префиксным свойством и неявляющиеся мгновенными, однако их декодирование требует больших объемов памяти декодера и приводит к большим задержкам результата.1101α41100α3НС10α5α80α6α701α20α1Рис. 2. Дерево декодированияСредняя длина кодовой комбинации для построенного кода8µ = ∑ p (α i )µi =i =1= 0,75 ⋅ 2 + 0,125 ⋅ 3 + 0,0625 ⋅ 4 + 0,03125 ⋅ 5 + 0,03125 ⋅ 6 = 2,469 .Согласно теореме Шеннона при оптимальном кодировании можно достичь средней длины8µ min = H ( Α) / log 2 = − ∑ p(α i )log p(α i ) = 2.469 .i =120Таким образом, построенный код является оптимальным. Это произошло вследствие того, что на каждом шаге процедуры построения кодаудавалось разделить символы на группы с равными вероятностями.
Заметим,что восемь различных символов источника можно представить восемью комбинациями равномерного двоичного кода (Бодо), при этом длина каждой кодовой комбинации равняется, очевидно, 3. Уменьшение средней длины кодовой комбинации (и, следовательно, увеличение скорости передачи информации) составляет в данном примере около 22%. Если при делении символов нагруппы вероятности групп оказываются неравными, выигрыш может быть нестоль значительным.Определим вероятность появления определенного символа в кодовойкомбинации (пусть это будет символ 1).
Она находится, как сумма количествединиц во всех кодовых словах с весами, равными вероятностям кодовыхслов, отнесенная к средней длине кодового слова:p (1) =0, 25 + 0,25 + 2 ⋅ 0,125 + 3 ⋅ 0,0625 + 4 ⋅ 0,03125 + (5 + 6) ⋅ 0,015625= 0,5 .2,469Итак, при оптимальном кодировании источника кодовые символы равновероятны; такое кодирование является безызбыточным. Источник вместе скодером можно рассматривать, как новый источник с алфавитом, состоящимиз кодовых символов; энтропия и избыточность этого источника – это энтропия и избыточность кода.
Оптимальный код имеет максимальную энтропиюи нулевую избыточность.Кодирование источника по методу Хаффмена.Другим широко известным методом кодирования источника являетсяметод Хаффмена4. Процедура кодирования состоит из следующих шагов.1. Все символы алфавита записываются в порядке убывания вероятностей.4Доказана оптимальность кода Хаффмена в смысле наименьшей средней длины кодовых слов [2]212. Два нижних символа соединяются скобкой, из них верхнему приписывается символ 0, нижнему 1 (или наоборот).3. Вычисляется сумма вероятностей, соответствующих этим символамалфавита.4.
Все символы алфавита снова записываются в порядке убывания вероятностей, при этом только что рассмотренные символы «склеиваются», т.е. учитываются, как единый символ с суммарной вероятностью.5. Повторяются шаги 2, 3 и 4 до тех пор, пока не останется ни одногосимвола алфавита, не охваченного скобкой.Скобки в совокупности образуют дерево. Код Хаффмена для некоторого символа алфавита находится путем последовательной записи нулей и единиц, встречающихся на пути от корня дерева (корню соответствует суммарная вероятность 1) до листа, соответствующего данному символу. Полученное дерево, очевидно, является деревом декодирования.Для примера, приведённого в таблице 2, получаются следующие кодовые комбинации: α1 →01; α 2 →11; α 3 →001: α 4 →000; α 5 →101; α 6 →1000;α 7 →10011; α8 →10010.Энтропия алфавита H ( Α) = 2,628 . Средняя длина кодового словаnµ = ∑ pi µi = 0,3⋅2+0,2⋅2+0,15⋅3+0,15⋅3+0,1⋅3+0,04⋅4+0,03⋅5+0,03⋅5=2,66.
Слеi =1довательно, код не оптимален, но очевидно, что он довольно близок к оптимальному. Для сравнения: равномерный код для этого случая имеет среднююдлину кодового слова 3 (совпадающую для равномерного кода с длиной каждого кодового слова).Вероятность символа 1 в последовательности кодовых комбинаций находится как среднее количество единиц, отнесённое к средней длине кодового словаp (1) =0,3 + 0, 4 + 0,15 + 0,2 + 0,04 + 0,09 + 0,06= 0,466 .2,6622Неоптимальность кода проявляется в неравенстве вероятностей кодовых символов (0,466 для «1» и 0,534 для «0»).Таблица 2Кодирование по методу Хаффменаα1 :α1 :α1 :α1 :0,30,30,30,3α2 :α2 :α2 :0,20,20,2α3 :α3 :0,150,150,2α4 :α4 :α3 :0,150,150,15α5 :α5 :α4 :0,10,10,4α1 :0,30,3α2 :0,20,30,20,15α6 :0,040,06α7 :α6 :0,030,04α8 :0,03Замечания1.Из рассмотренных примеров не должно составиться ложноевпечатление, будто код Шеннона – Фано оптимален, а код Хаффмена– нет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
