Правила построения кода Шеннона - Фано
Рассмотрим построение кода Шеннона.-.Фано на следующем примере.
Источник сообщений формирует ансамбль статистически независимых событий
, (3)
где xi – одно из n независимых событий,
p(xi) – вероятность наступления i -го события.
Для несовместных событий выполняется условие
. (4)
Процедура построения эффективного кода Шеннона - Фано заключается в следующем [4].
1. Все сообщения располагают (сортируют) в порядке убывания вероятности их появления.
2. Проводят первое деление всех сообщений на две подгруппы I и II так, чтобы сумма вероятностей сообщений в подгруппах I была бы по возможности одинаковой с суммой вероятностей сообщений в подгрупе II или близка к ней.
3. Проводят второе аналогичное деление для каждой из полученных подгрупп сообщений. Процесс последовательных делений сообщений на подгруппы I и II прекращается в том случае, когда в каждой подгруппе останется по одному сообщению.
4. Номер подгруппы, в которую попадает данное сообщение при каждом делении, определяет символ на соответствующей позиции кода этого сообщения. В рассматриваемой таблице принадлежность к подгруппе I обозначается символом 0, а к подгруппе II – символом 1.
Пример построения кода Шеннона - Фано приведен в табл. 1. Первый столбец содержит сортированные по убыванию вероятностей сообщения. Второй столбец содержит вероятности этих сообщений. Последующие столбцы иллюстрируют процесс деления сообщений на подгруппы и присвоения символам кода значений «0» или «1» в зависимости от того, в какую подгруппу попадает сообщение при очередном делении. Последний столбец показывает длительность кода каждого сообщения, выраженную в количестве элементарных символов, где τ – длительность элементарного символа.
|
|
|
Таблица 1. Построение кода Шеннона – Фано
| Сооб-щение | Вероят- ность, р(х i) | Деление на подгруппы | Код | Длитель- ность сигнала, τc i | |||||
| х1 х2 х3 х4 х5 х6 х7 х8 х9 | 0,49 0,14 0,14 0,07 0,07 0,04 0,02 0,02 0,01 |
|
|
|
|
|
| 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 | t 3t 3t 4t 4t 4t 5t 6t 6t |
Как следует из табл. 1, код Шеннона - Фано является неравномерным, т.е. сигналы разных сообщений имеют различное число символов, следовательно, разную длительность. При этом выполняется упомянутый выше принцип построения кода – наиболее вероятному сообщению соответствует самая короткая кодовая комбинация, наименее вероятному – длинная.
Скорость передачи информации при использовании кода Шеннона - Фано
|
|
|
Посмотрим, как изменится скорость передачи сообщений х1…х9 при кодировании их кодом Шеннона - Фано по сравнению со скоростью при кодировании этих же сообщений равномерным двоичным кодом.
Определим энтропию источника сообщений (3), используя формулу Шеннона (2): H(X)=2.313 дв.ед./сообщ.
Для кодирования сообщений из ансамбля (3) равномерным двоичным кодом потребуется четыре разряда. При этом длительность каждого сообщения и соответственно средняя длительность одного сообщения будут равны 4τ.
Скорость передачи информации в этом случае равна:
. (5)
Для кода Шеннона - Фано средняя длительность одного сообщения определяется как
, (6)
где τс i – длительность i-го сообщения.
Из выражения (5) и табл. 1 получим: τср=2.33τ.
Скорость передачи информации в этом случае равна:
. (7)
Из сравнения (7) и (5) следует, что учет статистических характеристик источника сообщений (вероятностей их появления) при построении кода Шеннона - Фано позволил в 1.7 раза увеличить скорость передачи информации, практически приблизив ее к максимально возможному значению, т.е. к пропускной способности канала связи, определяемой выражением (1).
|
|
|
2. ПОДГОТОВКА К РАБОТЕ
Варианты заданий
Исходные данные для формирования задания.
2.1.1. Базовый источник сообщений Х и вероятности каждого сообщения представлены в табл. 2
Таблица 2. Базовый источник сообщений
| Сообщение, X i | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | Х7 | Х8 |
| Вероятность, Р[Xi] | 0.05 | 0.07 | 0.11 | 0.15 | 0.17 | 0.22 | 0.12 | 0.11 |
2.1.2. Каждой бригаде сформировать задание на выполнение работы по следующим правилам.
1. Номер бригады n - четное число.
Вероятности элементов ансамбля сообщений Х определяются по правилу:
Р[Х(1-4)]=P[Х(1-4)]+n/100 ;
P[Х(5-8)]=P[Х(5-8)] – n/100.
2. Номер бригады n- нечетное число.
Вероятности элементов ансамбля сообщений Х определяются по правилу:
Р[Х(1-4)]=P[Х(1-4)]+(n–1)/100 ;
P[Х(5-8)]=P[Х(5-8)] – (n–1)/100.
2.1.3. Длительность одного символа сообщения τ = n мс.
Дата добавления: 2020-01-07; просмотров: 178; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!