Кодирование (стр. 2 из 3)
1. Символы сообщения располагаем в порядке убывания их априорных вероятностей.
2. Исходный ансамбль кодируемых символов разбиваем на две группы с примерно равными вероятностями (лучше, если суммарная вероятность верхней группы меньше).
3. Верхней группе присваиваем символ 1, а нижней 0.
4. Процесс деления повторяем до тех пор, пока в каждой подгруппе останется по одному символу.
Процесс построения кода приведем в таблице 3.
Таблица 3
| ai | p(ai) | Разбиение | Код | li | pili |
      a5a4a1a6a7a2a8a3 | 0,420,170,100,090,080,070,050,02 | }010}0 }110}0 }11}0}0}1 | 01001011100110111101111011111 | 13344455 | 0,420,510,30,360,320,280,250,1 |
. 
.Могут быть и другие варианты построения кода, но lср при этом не меняется.
Определим энтропию источника сообщений:
= -(0,42× log20,42+0,17 ×log20,17+0,1×log20,1+0,09×log20,09+0,08×log20,08+
+0,07×log20,07+0,05×log20,05+0,02×log20,02) = 0,5256+0,4346+0,3322+
+0,3126+0,2915+0,2686+0,2161+0,1129 = 2,49 бит/симв.
Оценим эффективность построенного кода, которая определяется коэффициентами относительной эффективности и статистического сжатия.
Коэффициент относительной эффективности равен
Коэффициент статистического сжатия равен
.Необходимая пропускная способность канала связи для передачи сообщений оптимальными кодами вычисляется по формуле
.Для полученного кода она равна
С = 103×2,54 = 2,54 Кбит/с.
Построим код по методу Хаффмена, используя следующий алгоритм:
1. Символы первичного алфавита располагаем в порядке убывания их вероятностей.
2. Последние два символа объединяем в один, с суммарной вероятностью.
3. Упорядочиваем символы с учетом вновь образованных и последние два символа объединяем в один с суммарной вероятностью. Эту процедуру повторяем до тех пор, пока не останется два символа.
4. Строим кодовое дерево, вершиной которого является 1 (суммарная вероятность всех символов сообщения).
При построении дерева символы, в принципе, можно не упорядочивать.
Процесс построения кода приведен в таблице 4.
Коэффициент статистического сжатия равен
.Коэффициент относительной эффективности
.Необходимая пропускная способность канала связи
Кбит/c.Tаблица 4
| аi | p(ai) | Кодовое дерево | Код | li | pili | ||
                a5a4a1a6a7a2a8a3 | 0,420,170,100,090,080,070,050,02 | 1 (1,0) 1 1 0 (0,34) (0,58) 0 1 0 (0,24) 1 0 (0,17) 0 1 (0,14) 1 0 (0,7) 0 | 10110010101010000010000100000 | 13344455 | 0,420,510,30,360,320,280,250,1 | ||
. 
.Построенные коды Шеннона – Фано и Хаффмена равноценны, т. к. они имеют одинаковые показатели эффективности. Оба кода отличаются от оптимального на 2%.
4. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
Помехоустойчивость- способность системы осуществлять прием информации в условиях наличия помех в линии связи и искажений во внутри аппаратных трактах. Помехоустойчивость обеспечивает надежность и достоверность передаваемой информации (данных). Мы будем в основном рассматривать двоичные коды. Двоичные (коды) данные передаются между вычислительными терминалами, летательными аппаратами, спутниками и т. д.
Передача данных в вычислительных системах чувствительна к малой доле ошибке, т. к. одиночная ошибка может существенно нарушить процесс вычислений.
Наиболее часто ошибки появляются в УВВ, шинах, устройствах памяти. УВВ содержат большое количество элементов, ошибки обуславливаются старением элементов, ухудшением качества электрических соединений, расфазировкой сигналов. Значительная часть ошибок приходится на ОП, вследствие отказа отдельных ИС либо всей ИС, ошибок связанных с флуктуацией напряжения питания и т. д.
В системах со многими пользователями и разделением по времени длинные двоичные сообщения разделяются на пакеты.
Сообщения, представленные длинными последовательностями битов, обычно разбиваются на более короткие последовательности битов, называемые пакетами. Пакеты можно передать по сети как независимые объекты и собирать из них сообщение на конечном пункте. Пакет, снабженный именем и управляющими битами в начале и в конце, называется кадром. Управление линией передачи данных осуществляется по специальному алгоритму, называемому протоколом.
Наличие помех ставит дополнительные требования к методам кодирования. Для защиты информации от помех необходимо вводить в том или ином виде избыточность: повышение мощности сигнала; повторение сообщений; увеличение длинны кодовой комбинации и т. д.
Увеличение мощности сигналов приводит к усложнению и удорожанию аппаратуры, кроме того, в некоторых системах передачи информации имеется ограничение на передаваемую мощность, например, спутниковая связь.
Повторная передача сообщений требует наличия буферов для хранения информации и наличия обратной связи для подтверждения достоверности переданной информации. При этом, значительно падает скорость передачи информации, кроме того этот метод не всегда м. б. использован, например, в система реального времени.
Одним из наиболее эффективных методов повышения достоверности и надежности передачи данных является помехоустойчивое кодирование, позволяющее за счет внесения дополнительной избыточности (увеличение минимального кодового расстояния) в кодовых комбинациях передаваемых сообщений обеспечить возможность обнаружения и исправления одиночных, кратных и групповых ошибок.
Минимальное кодовое расстояние характеризует помехоустойчивость и избыточность сообщений. В зависимости от величины минимального кодового расстояния существуют коды, обнаруживающие и исправляющие ошибки.
Кодовое расстояние - d определяется как количество единиц в результате суммирования по модулю два двух кодовых комбинаций. Минимальное кодовое расстояние d0 - минимальное из кодовых расстояний всех возможных кодовых комбинаций.
Для обнаружения r ошибок минимальное кодовое расстояние равно:
d0 ³ r+1. (8)
Для обнаружения r ошибок и исправления s ошибок минимальное кодовое расстояние равно:
d0³ r+s+1. (9)
Только для исправления ошибок минимальное кодовое расстояние равно:
d0³ 2s+1. (10)
5. ОБНАРУЖИВАЮЩИЕ КОДЫ
Обнаруживающие коды - это коды, позволяющие обнаружить ошибку, но не исправить ее. Простейший способ обнаружения ошибки это добавление к последовательности битов данных еще одного бита-бита проверки на четность (нечетность) значение, которого равно сумме по модулю два исходной последовательности битов. Чаще организуется проверка на нечетность.
В символьном коде ASCII к семи битам кода добавляется восьмой бит проверки на четность - k1.
S1 S2 S3 S4 S5 S6 S7 K1
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
Однобитовая проверка позволяет обнаружить любую единичную ошибку, две ошибки обнаружить нельзя, в общем случае обнаруживается любое нечетное количество ошибок.