Задание №2. Исследование тракта кодер-декодер источника.
2.1) Посчитаем:
Энтропия источника - среднее количество информации, приходящее на один символ.
-
алфавит из 16 символов.
Избыточность источника
Производительность источникa
2.2) Полагая, что производится примитивное двоичное кодирование символов источника, найдем:
минимально необходимое число разрядов кодового слова
среднее количество двоичных символов
,
приходящееся на один
символ
источника
Для случая
примитивного кодирования
будет равно
,
поскольку все символы представляются
комбинациями с одинаковым числом
разрядов
.
2.3) Полагая что производится экономное кодирование символов источника двоичным кодом, выполним следующее:
построим кодовое дерево для кода Шеннона – Фано
запишем кодовые комбинации для представления всех 16 символов источника и найдем число разрядов каждой полученной комбинации. Результаты представлены в таблице
|
|
|
Кодовые комбинации |
|
|
|
|
а |
0,279 |
00 |
2 |
2 |
0 |
|
л |
0,2 |
01 |
2 |
1 |
1 |
|
р |
0,175 |
100 |
3 |
2 |
1 |
|
и |
0,15 |
101 |
3 |
1 |
2 |
|
в |
0,082 |
1100 |
4 |
2 |
2 |
|
к |
0,039 |
1101 |
4 |
1 |
3 |
|
д |
0,018 |
1110 |
4 |
1 |
3 |
|
н |
0,011 |
111100 |
6 |
2 |
4 |
|
з |
0,01 |
111101 |
6 |
1 |
5 |
|
г |
0,009 |
1111100 |
7 |
2 |
5 |
|
п |
0,0075 |
1111101 |
7 |
1 |
6 |
|
м |
0,006 |
11111100 |
8 |
2 |
6 |
|
о |
0,006 |
11111101 |
8 |
1 |
7 |
|
е |
0,005 |
11111110 |
8 |
1 |
7 |
|
б |
0,002 |
111111110 |
9 |
1 |
8 |
|
с |
0,001 |
111111111 |
9 |
0 |
9 |
-
число разрядов кодовой комбинации.
-вероятность 
-го
символа.
и 
- число нулей и единиц в кодовой комбинации
-го
символа.
найдем среднее количество двоичных символов, приходящееся на один символ источника
незначительно больше H(A)
средняя скорость выдачи двоичных символов на выходе кодера источника
рассчитаем вероятности двоичных символов на выходе кодера источника
Избыточность на выходе кодера:
Вывод: при экономном кодировании среднее число двоичных символов, приходящееся на один символ источника меньше, чем в примитивном кодировании, это доказывает эффективность экономного кодирования. Избыточность при экономном кодировании намного меньше, чем в примитивном кодировании. Примитивный равномерный код не может обеспечить эффективного согласования источника с каналом связи.
2.4) Опишем процедуру кодирования и декодирования символов экономным кодом
Алгоритм построения кодового дерева Шеннона – Фано. Построение дерева в отличии от кода Хаффмана идет не от листьев к корню а от корня к листьям. Символы исходного алфавита образуют список свободных узлов ( листьев дерева), вес каждого из которых равен вероятности символа.
Алгоритм кодирования Шеннона – Фано. Каждый символ источника заменяется соответствующей кодовой комбинацией. Для однозначного декодирования, кодовые комбинации экономного кода должны удовлетворять условию префиксности, которое состоит в том, что ни одна кодовая комбинация не должна быть началом любой другой кодовой комбинации. При декодировании из всей последовательности кодовых символов выделяются кодовые комбинации экономного кода, каждая из которых на выходе декодера заменяется соответствующим символом источника (то есть происходит процедура обратная кодированию). В результате устранения избыточности из сообщения, при возникновении одиночной ошибки в кодовом символе приведёт к тому, что оставшаяся (следующая за ошибочным символом) часть сообщения восстановится декодером неверно