Васюков В.Н. - Введение в ТЭС (1275345), страница 3
Текст из файла (страница 3)
Если источник вырабатывает символы со скоростью 
, где 
– время передачи одного символа, то производительность источника определяется как 
и имеет размерность бит/с. Если количество информации на один символ составляет при передаче по каналу величину 
, определяемую выражением , то скорость передачи информации по каналу
бит/с.
Максимальная скорость передачи информации, которая может быть достигнута для данного канала, называется его пропускной способностью
бит/с.
Заметим, что нахождение пропускной способности реального канала связи представляет собой сложную задачу. В простейшем случае бинарного канала без помех (см. пример 2) пропускная способность равна скорости модуляции .
Объем алфавита источника и количество различных символов, передаваемых по каналу (канальных символов), могут не совпадать. В таких случаях один символ источника представляется (кодируется) последовательностью из нескольких кодовых символов (кодовым словом, или кодовой комбинацией). Если для всех символов источника длина кодовых слов одинакова, код называют равномерным, в противном случае – неравномерным. Примером равномерного кода является код Бодó, смысл которого состоит в представлении каждой из букв алфавита двоичным числом фиксированной разрядности (например, для алфавита из 32 символов, включающего 26 латинских букв и знаки препинания, достаточно пятиразрядного кода Бодо). При передаче сообщений неравномерным кодом говорят о средней длине кодового слова (усреднение длин кодовых слов производится по соответствующему распределению вероятностей).
Шеннону принадлежит следующая теорема (доказательство см., напр., в [1]), называемая основной теоремой о кодировании в отсутствие шумов.
ТЕОРЕМА. Среднюю длину кодовых слов для передачи символов источника 
при помощи кода с основанием 
можно как угодно приблизить к величине 
.
Смысл теоремы состоит в том, что она определяет нижнюю границу длины кодовых слов и устанавливает принципиальную возможность достичь этой границы, однако она не указывает способов достижения.
Пример 3. Если источник имеет объем алфавита 32, то при равновероятных символах его энтропия равна 5 битам. Тогда для двоичного кода наименьшая средняя длина составляет 5, следовательно, пятизначный код Бодо является оптимальным кодом. Однако при неравных вероятностях символов энтропия источника меньше чем 5 бит (избыточность источника отлична от нуля), следовательно, можно найти код со средней длиной кодового слова меньше пяти и таким образом повысить скорость передачи информации. Текст на русском языке, например, имеет энтропию около 2,5 бит, поэтому путем соответствующего кодирования можно увеличить скорость передачи информации вдвое против пятиразрядного равномерного кода Бодо (чтобы можно было использовать код Бодо для передачи русского текста, можно отождествить буквы «е» и «ё», а также «ь» «ъ»).
Практическое значение теоремы Шеннона заключается в возможности повышения эффективности систем передачи информации (систем связи) путем применения экономного кодирования (кодирования источника).
Очевидно, что экономный код должен быть в общем случае неравномерным. Общее правило кодирования источника (без памяти) состоит в том, что более вероятным символам источника ставятся в соответствие менее длинные кодовые слова (последовательности канальных символов).
Пример 4. Известный код Морзе служит примером неравномерного кода. Кодовые слова состоят из трех различных символов: точки (передается короткой посылкой), тире ― (передается относительно длинной посылкой) и пробела (паузы). Наиболее частой букве в русском тексте – букве «е» – соответствует самое короткое кодовое слово, состоящее из одной точки, относительно редкая буква «ш» передается кодовым словом из четырех тире, и т.д.
Кодирование источника по методу Шеннона – Фано.
Принцип построения кода Шеннона – Фано состоит в упорядочении всех символов алфавита (назовем их для краткости «буквами») по убыванию вероятностей. Затем все буквы делятся на две (неравные в общем случае) группы, так, что сумма вероятностей букв для обеих групп одинакова или примерно одинакова, и в качестве первого символа кодового слова каждой букве первой группы присваивается кодовый символ 0, а каждой букве второй группы – символ 1 (или наоборот). Далее первая и вторая группы делятся на подгруппы в соответствии с принципом равной вероятности, и эта процедура продолжается до тех пор, пока алфавит источника не будет исчерпан. Пример построения кода Шеннона – Фано приведен в табл. 1.
Таблица 1
Построение кода Шеннона – Фано
| Символ и его вероятность | Комбинация кодовых символов | Длина комбинации | ||||||
|
|
| 1-й | 2-й | 3-й | 4-й | 5-й | 6-й |
|
|
| 1/4 | 0 | 0 | 2 | ||||
|
| 1/4 | 0 | 1 | 2 | ||||
|
| 1/4 | 1 | 0 | 2 | ||||
|
| 1/8 | 1 | 1 | 0 | 3 | |||
|
| 1/16 | 1 | 1 | 1 | 0 | 4 | ||
|
| 1/32 | 1 | 1 | 1 | 1 | 0 | 5 | |
|
| 1/64 | 1 | 1 | 1 | 1 | 1 | 0 | 6 |
|
| 1/64 | 1 | 1 | 1 | 1 | 1 | 1 | 6 |
На первом шаге процедуры все символы алфавита источника делятся на две группы, причем в первую группу входят символы 
и 
, которым соответствует суммарная вероятность 1/2, а во вторую – все остальные символы. Символам и сопоставляется в качестве первого кодового символа символ 0, а всем остальным символам источника – кодовый символ 1. На втором шаге первая и вторая группы рассматриваются по отдельности, при этом в первой группе содержатся всего два символа, которые получают в качестве второго кодового символа 0 и 1 соответственно. Таким образом, символу источника сопоставляется кодовое слово 00, а символу – слово 01. Вторая группа символов источника, включающая символы 
, 
, 
и 
, делится на две части в соответствии с их вероятностями, при этом символ , которому соответствует вероятность 1/4, получает в качестве второго символа кодового слова символ 0, а остальные символы источника – символ 1. Далее процесс продолжается до тех пор, пока не останется группа из двух символов – в данном примере это символы 
и 
, – которым присваиваются кодовые символы 0 и 1.
Необходимо обратить внимание на следующее свойство полученного кода: ни одна кодовая комбинация не является началом какой-либо другой кодовой комбинации (так называемое префиксное правило). Такие коды называются неперекрываемыми (неприводимыми). Декодирование неприводимого кода может быть осуществлено в соответствии с деревом декодирования3(рис. 2), соответствующим некоторому конечному автомату, который переходит из начального состояния в другие состояния в соответствии с очередным символом кодовой последовательности.
Перед декодированием конечный автомат устанавливается в начальное состояние НС, а дальнейшие переходы зависят только от поступающих символов кода, при этом все концевые состояния («листья» дерева) соответствуют декодированным символам алфавита источника; по достижении листа автомат переходит вновь в начальное состояние. Поскольку с поступлением последнего кодового символа декодирование кодового слова всегда заканчивается, префиксные коды называют также мгновенными [2]. Существуют однозначно декодируемые коды, не обладающие префиксным свойством и не являющиеся мгновенными, однако их декодирование требует больших объемов памяти декодера и приводит к большим задержкам результата.
| |
| Рис. 2. Дерево декодирования |
Средняя длина кодовой комбинации для построенного кода
.
Согласно теореме Шеннона при оптимальном кодировании можно достичь средней длины
.
Таким образом, построенный код является оптимальным. Это произошло вследствие того, что на каждом шаге процедуры построения кода удавалось разделить символы на группы с равными вероятностями. Заметим, что восемь различных символов источника можно представить восемью комбинациями равномерного двоичного кода (Бодо), при этом длина каждой кодовой комбинации равняется, очевидно, 3. Уменьшение средней длины кодовой комбинации (и, следовательно, увеличение скорости передачи информации) составляет в данном примере около 22%. Если при делении символов на группы вероятности групп оказываются неравными, выигрыш может быть не столь значительным.
Определим вероятность появления определенного символа в кодовой комбинации (пусть это будет символ 1). Она находится, как сумма количеств единиц во всех кодовых словах с весами, равными вероятностям кодовых слов, отнесенная к средней длине кодового слова:
.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
