Расчет информационных характеристик дискретного канала (стр. 4 из 6)
14) Коэффициент эффективности дискретного канала связи Kэ
Kэ=
= 
=0,982915) Критическая скорость передачи Rкр
Rкр=
= 
= 393,102 [бод]Оценка надёжности и эффективности дискретного канала связи
1. Оценка теоремы Шеннона по скорости
R<Rкр
749,8676> 393,102
2. Оценка выполнения теоремы по кодированию
H’(A) < C
970,3227 > 762,8716
3. Рекомендации по повышению надёжности и эффективности
Из-за невыполнения теоремы о скорости передачи невозможным становится восстановление исходного сообщения. При кодировании и декодировании информации вероятность ошибки может быть сколь угодно велика. Для улучшения эффективности необходимо увеличить емкость канала С.
Теоремы Шеннона не выполняются, а значит, наш канал связи не является эффективным и надежным.
Построение канальной матрицы объединения
Найдем безусловные вероятности появления сигналов на входе приемника по формуле:
Зная КМИ можно построить КМО: р(аi,,bj)= p(ai)p(bj/аi)
Построение канальной матрицы приемника
Зная КМО мы можем построить КМП, найдя элементы по формуле :
p(ai / bj)= p(ai,bj)/p(bj)
Часть 2. Теория кодирования
6. Оптимальное кодирование. Идея сжатия
Основной характеристикой дискретного канала связи является скорость передачи данных. При избыточности переданного сообщения скорость передачи уменьшается. Для исключения избыточности сообщения используют математические и программные средства компрессии данных без потери содержания информации, в том числе оптимальное кодирование.
Оптимальное кодирование применяют для того, чтобы:
· сжимать данные (компрессия);
· снижать время передачи данных при той же скорости передачи;
· уменьшить возможные потери и искажения данных;
· архивировать данные, эффективно использовать память.
Основная идея оптимального кодирования лежит в том, что символам сообщения, которые имеют большую вероятность, присваивают короткие бинарные коды, то есть образуются бинарные кодовые слова разной длины – неравномерные коды. Оптимальным неравномерным кодом (ОНК) называется такой код, для которого средняя длина кода есть минимальной.
Такая идея сжатия была применена в азбуке Морзе, где наиболее встречающимся символам соответствовали наиболее короткие коды. Сам алфавит состоял из точек и тире.
6.1 Равномерный двоичный код (РДК), корневое бинарное дерево РДК, длина кода РДК, сообщение в РДК
Составление сообщения
Нам дано сообщение:
Х= "Остановите землю, я сойду"
Длина сообщения Lx=24 [символа]
Алфавит сообщения
Найдём алфавит нашего сообщения:
A={о,с,т,а,н,в,и,е,з,м,л,ю,я,с,й,д,у,_. }
Длина алфавита La=21 [символ]
Вероятности
На данном этапе вычисления РДК нам требуется вычислить вероят-ности появления каждого символа в алфавите сообщения. Для этого мы воспользуемся формулой:
pi= vi/ ls
где vi- количество раз, которое символ встречается в сообщении.
Сумма vi должна соответствовать длине исходного сообщения.
Таблица данных, РДК
Таким образом, наше сообщение будет выглядеть:
SРДК=00001000110010001001001100000100111010000010000101000100101000100101011011000110100010011100001000011000001011111000010001
6.1.6 Длина сообщения
Длина сообщения, записанного в РДК равна:
lsрдк = ls ·lрдк
где lрдк = 5 бит.
Таким образом, длина сообщения:
lsрдк = 24·5 = 120 бит
6.2 Оптимальный неравномерный код ОНК Шеннона-Фано, алгоритм расчета ОНК, средняя длина, энтропия, коэффициент сжатия, коэффициент эффективности, сообщение в ОНК, критерий Фано, корневое бинарное дерево ОНК Шеннона-Фано
Расчёт ОНК
Оптимальный неравномерный код (ОНК) мы будем рассчитывать по методу Шеннона-Фано, который ещё называют методом бисекции.
Для вычисления ОНК вся работа разбивается на несколько этапов.
Предварительный шаг: вероятности появления символа в сообщении ранжируются по убыванию.
Шаг первый: все вероятности разбиваются на две равновероятные группы. Символам верхней секции назначим 0, символам нижней секции – 1. Первый бит ОНК вычислен.
Шаг второй: каждую группу делим на две равновероятные подгруппы. Верхним подгруппам присваивается 0, нижним – 1. и т. д.
Деление заканчивается, когда в подгруппе остаётся один символ.
Нахождение ОНК
Критерий Фано однозначного декодирования ОНК: ни одно слово ОНК не является началом другого слова ОНК. Это ещё называется свойством префиксности.
Критерий Фано позволяет однозначно декодировать сжатое сообщение SОНК . Сообщение в ОНК будет выглядеть:
SОНК=111101100101010111111011010110010011000110010011000010000011001010010010011010111100010001100000
Характеристики ОНК
1. Средняя длина ОНК
Lcp.онк= 4.23 [бит]
2. Энтропия ОНК
H(A)= 1,18 [бит/символ]
3. Максимальная энтропия
Hmax= log 17= 4,08 [бит/символ]
4. Относительная энтропия
5. Информационная избыточность
6. Абсолютная недогруженость
7. Коэффициент сжатия
Кс = 1- Lcp.онк/ LРДК = 0,15 = 15 %
8. Коэффициент эффективности Кэ
Кэ=Н/ Lcp.онк = 0,27
Эффективность ОНК тем выше, чем больше средняя длина ОНК стремится к энтропии.
6.3 Оптимальный неравномерный ОНК Хаффмана, алгоритм расчета ОНК, средняя длина, энтропия, коэффициент сжатия, коэффициент эффективности, сообщение в ОНК, КБД
Расчет ОНК Хаффмена
При расчёте оптимального неравномерного кода Хаффмена нам потребуются вероятности появления символов в нашем сообщении. Они у нас уже рассчитаны и выстроены в порядке убывания.
Сам оптимальный неравномерный код Хаффмена мы будем вычислять при помощи алгоритма Хаффмена:
Шаг 1. "Склеиваются" две самых маленьких вероятности.
Шаг 2. В усечённом алфавите снова "склеивают" две самых маленьких вероятности.
Объединение вероятностей заканчивается, когда в усечённом алфавите остаётся лишь одна вероятность.
Критерий Фано
Полученный ОНК Хаффмена обязан обладать свойством пре-фиксности, то есть ни одно слово ОНК не должно являться началом другого слова. Критерий Фано позволяет однозначно декодировать сжатое сообщение.
Cообщение примет вид:
S=1001101011011111001001010101100011101010011101000100001100010111101111111001100101101000
Характеристики ОНК
1. Средняя длина ОНК
Lcp.онк= 4.23 [бит]
2. Энтропия ОНК
H(A)= 1,18 [бит/символ]
3. Максимальная энтропия
Hmax= log 17= 4,08 [бит/символ]
4. Относительная энтропия
5. Информационная избыточность
6. Абсолютная недогруженость
7. Коэффициент сжатия
Кс = 1- Lcp.онк/ LРДК = 0,15 = 15 %
8. Коэффициент эффективности Кэ
Кэ=Н/ Lcp.онк = 0,27
Эффективность ОНК тем выше, чем больше средняя длина ОНК стремится к энтропии.
6.4Эффективность ОНК
Однозначно декодировать ОНК можно с помощью критерия Фано, который говорит о свойстве префиксности, которым обладают коды. Благодаря сжатию информации возможно значительно сократить исходный код.
Эффективность ОНК можно определить с помощью коэффициента эффективности, то есть чем ближе Кэ стремится к единице, тем эффективнее оптимальный неравномерный код.
ОНК не обладает избыточностью, так как к нему не прикрепляются контрольные биты.
7. Помехоустойчивое кодирование. Назначение
Назначение помехоустойчивого кодирования состоит в защите данных от действия помех.
Эти коды делятся на две группы:
· Обнаруживающие коды – коды только обнаруживают ошибки, но не указывают их адрес
· Корректирующие коды – обнаруживают наличие ошибки, вычисляют адрес ошибки (позицию), в котором появился ошибочный бит.
7.1 Обнаруживающие коды
Двоичный код становится обнаруживающим за счет добавления дополнительных контрольных бит.
Можно назвать следующие обнаруживающие коды: обнаруживающий код четности (ОКЧ), обнаруживающий код удвоения (ОКУ), обнаруживающий код инверсией (ОКИ), обнаруживающий код стандартный телеграфный код № 3 и другие.
7.1.1 Обнаруживающий код четности (ОКЧ)
Данный двоичный код дополняется одним контрольным битом в конце слова.
nи - длина информационной части, количество бит.
nк - длина контрольной части.
n= nи + nк - длина слова.