Расчет и оптимизация характеристик дискретного канала

 

 

S_ОНК = 11111010011110000101010001110011100001011001101011000011010001011001110

000101100110101100001101000101101000111011000

 

 

3.3.2 КБР ОНК Шеннона–Фано

3.3.3 Информационные характеристики ОНК Шеннона–Фано

1. Средняя  длина ОНК:

L_ср =Σ L_i p(a_i) [бит]

L_ср = 0,48 + 3*0,36 + 6*0,24 + 0,18 + 2*0,15 = 3,52 (бит)

2. Энтропия  сообщения:

H(A) = – Σ p(a_i) log p(a_i) [бит/символ]

H(A) = – ( 0,24*log 0,24 + 3*0,09*log 0,09 + 7*0,06*log 0,06 + 2*0,03*

*log 0,03) = 3,46 (бит/символ)

3. Максимальная  энтропия:

H_max(A) = – log₂ N [бит]

H_max(A) = –log₂ 13 = 3,7 (бит)

4. Относительная  энтропия:

 

5. Информационная  избыточность показывает относительную  недогрузку на символ кода:

D = 1 – μ = 1 – 0,94 = 0,06

6. Абсолютная  недогруженность:

ΔD = H_max(A) – H(A)

ΔD = 3,7 – 3,46 = 0,24

7. Коэффициент  сжатия характеризует уменьшение  количества бинарных знаков на  символ сообщения при использовании  ОНК:

 

8. Коэффициент  эффективности

 

Эффективность ОНК: оптимальный код тем эффективнее, чем ближе средняя длина ОНК к H(A).

 

 

Построенный ОНК Шеннона–Фано имеет высокие информационные характеристики и этот код является эффективным  и оптимальным,

т.к. К_Э = 0,98.

3.4 Метод Хаффмена

3.4.1 Алгоритм Хафффмена:

• шаг 1: группируем («склеиваем») вместе два символа, которые имеют наименьшую вероятность и вычисляем их общую вероятность. Получаем новый объединенный символ.
• шаг 2: делаем второе сжимание; опять группируем вместе два символа, которые имеют наименьшие вероятности, и вычисляем их общую вероятность, проводим соединительные линии. И так далее, процесс пошагового сжимания символов осуществляется до тех пор, пока в ансамбле сообщения остается один объединенный символ с вероятностью p = 1 (корневой узел).
• завершающий шаг: кодовые слова ОНК получаем, передвигаясь по ветвям корневого дерева от корня к конечным узлам; при этом каждое ребро дерева определяет бит ОНК (0 или 1) в соответствии с направлением значений битов корневого дерева.

 

ai	Р(ai)	1 шаг	2 шаг	3 шаг	4 шаг	5 шаг	6 шаг	7 шаг	8 шаг	9 шаг	10 шаг	11 шаг	12 шаг	13 шаг	ОНК
А	0,24														00
О	0,09														010
Л	0,09														0110
Н	0,09														0111
В	0,06														1000
Д	0,06														1001
Е	0,06														1010
К	0,06														1011
Р	0,06														1100
С	0,06														1101
ПРОБЕЛ	0,06														1110
П	0,03														11110
Т	0,03														11111

 

3.4.2 КБД ОНК Хаффмена

 

3.4.3 Информационные характеристики ОНК Шеннона–Фано

 

ai	Р(ai)	ОНК	Li	Li*P(ai)	H(ai)
А	0,24	00	2	0,48	0,50
О	0,09	010	3	0,27	0,31
Л	0,09	0110	4	0,36	0,31
Н	0,09	0111	4	0,36	0,31
В	0,06	1000	4	0,24	0,25
Д	0,06	1001	4	0,24	0,25
Е	0,06	1010	4	0,24	0,25
К	0,06	1011	4	0,24	0,25
Р	0,06	1100	4	0,24	0,25
С	0,06	1101	4	0,24	0,25
ПРОБЕЛ	0,06	1110	4	0,24	0,25
П	0,03	11110	5	0,15	0,15
Т	0,03	11111	5	0,15	0,15
Сумма				3,48	3,46

 

1. Средняя  длина ОНК:

L_ср =Σ L_i p(a_i) [бит]

L_ср = 0,48 + 0,27 + 2*0,36 + 7*0,24 + 2*0,15 = 3,48 (бит)

2. Энтропия  сообщения:

H(A) = – Σ p(a_i) log p(a_i) [бит/символ]

H(A) = – ( 0,24*log 0,24 + 3*0,09*log 0,09 + 7*0,06*log 0,06 + 2*0,03*

*log 0,03) = 3,46 (бит/символ)

3. Максимальная  энтропия:

H_max(A) = – log₂ N [бит]

H_max(A) = –log₂ 13 = 3,7 (бит)

4. Относительная  энтропия:

 

5. Информационная  избыточность показывает относительную  недогрузку на символ кода:

D = 1 – μ = 1 – 0,94 = 0,06

6. Абсолютная  недогруженность:

ΔD = H_max(A) – H(A)

ΔD = 3,7 – 3,46 = 0,24

7. Коэффициент  сжатия характеризует уменьшение  количества бинарных знаков на  символ сообщения при использовании  ОНК:

 

8. Коэффициент  эффективности

 

Эффективность ОНК: оптимальный код тем эффективнее, чем ближе средняя длина ОНК к H(A).

 

 

Построенный ОНК Шеннона–Фано имеет высокие информационные характеристики, и этот код является эффективным и оптимальным,

т.к. К_Э = 0,99.

4. Помехоустойчивое кодирование

 

Назначение помехоустойчивого  кодирования: защита данных от действия помех. Эти коды делятся на 2 группы:

• обнаруживающие коды – коды, которые только обнаруживают ошибки, но не указывают её адрес;
• корректирующие коды – коды, которые обнаруживают наличие ошибки, вычисляют адрес ошибки (позицию, в которой появился ошибочный бит).

4.1 Обнаруживающие  коды

Двоичный код становится обнаруживающим за счёт добавления дополнительных контрольных бит.

4.1.1 Обнаруживающий код чётности (ОКЧ)

Двоичный код дополняется  одним контрольным битом в  конце слова:

n = n_и + n_k

где n – длина обнаруживающего кода; n_и – длина информационной части, количество бит; n_k – длина контрольной части, количество бит.

Пример:

а) Генерация

Дан исходный код: 1000001.

Макет: .

K – контрольный бит. К равняется сумме по модулю 2 информационных бит исходника.

_.

ОКЧ ()

ОКЧ (8,7) = 10000010.

б) Диагностика:

 ошибки;

 ошибки.

[S – синдром;  - квантор существования, в нашем случае: - ошибка существует,  - ошибки не существует].

 

Количество ошибок	Передано	Принято	Наличие ошибки
Нет ошибки	10000010	10000010	S = 0 ошибки
1 ошибка	10000010	00000010	S = 1 ошибки
2 ошибки	10000010	00000011	S = 2 ошибки
3 ошибки	10000010	00101011	S = 3 ошибки
4 ошибки	10000010	01101011	S = 4 ошибки
5 ошибки	10000010	01111011	S = 5 ошибки
6 ошибки	10000010	01111111	S = 6 ошибки
7 ошибки	10000010	01111101	S = 7 ошибки

 

ОКЧ позволяет определить наличие ошибки при нечётном их количестве и не определяет ошибку при их чётном количестве.

в) Эффективность ОКЧ:

• минимальное количество контрольных бит;
• простой, удобный алгоритм генерации кода и диагностики (обнаружения кода);
• ОКЧ обнаруживает нечетное количество ошибок.

2. Обнаруживающий код удвоения (ОКУ)

а) Генерация ОКУ.

Макет: .

Контрольные биты равны соответствующим  информационным битам: .

ОКУ(14; 7) = .

б) Диагностика ОКУ

При диагностике суммируются  по модулю 2 информационная и контрольная  части ОКУ.