Задача кодирования (стр. 6 из 7)
Защита от ошибок в различных телекоммуникационных системах сводится к применению протоколов, содержащих описание двух основных функций: помехоустойчивого кодирования и управления передачей на конкретном протокольном уровне (для канального, сетевого и сеансового уровней) эталонной модели взаимодействия открытых систем (ЭМВОС). Защита информации в таких системах сводится не только к борьбе с независимыми искажениями в канале связи (в двоичном – симметричном канале ДСК), но и к защите от группирующихся искажений (пакетов ошибок) и от преднамеренных искажений. Выше было показано, что в канале с более сложным распределением потока ошибок, чем в ДСК, применение кодов, исправляющих ошибки, затруднено. Применение кодов с исправлением ошибок преднамеренного характера до последнего времени считалось в принципе невозможным, хотя бы для классических алгебраических кодов.
С учетом сказанного выше, можно сказать, что теория алгебраического кодирования с алгоритмом декодирования по принципу максимального правдоподобия для исправления независимых ошибок является примером того, как ошибочная постановка задачи о независимых ошибках в канале связи сводит практически на нет труды целого поколения исследователей.
Для обеспечения применения кодов, исправляющих ошибки, сформулируем два варианта постановки задачи. [4]
При этом будем учитывать требования к защите информации в современных информационных и телекоммуникационных системах.. Особенностями таких глобальных систем является передача очень больших массивов информации и использование различных каналов связи наиболее простым образом без проведения исследования их свойств, в том числе модели ошибок в них.
Первая постановка, являющаяся «мягкой», состоит в том, что применяемые коды с исправлением ошибок должны обеспечивать в канале с естественными помехами (ошибками) подвергаемую количественной оценке вероятность ошибки декодирования отдельно по следующим характерным интервалам кратности ошибки:
- кратность ошибки t меньше половины величины кодового расстояния d, т.е. t £ [(d-1)/2]
- кратность ошибки t меньше величины кодового расстояния d, т.е. t < d
- кратность ошибки t больше величины кодового расстояния d, t > d³
Вторая постановка, являющаяся сильной, состоит в том, что применяемые коды с исправлением ошибок должны обеспечивать в канале с произвольным характером ошибок гарантированную верхнюю границу для вероятности ошибки декодирование на всем интервале возможной кратности ошибки t £ n; причем эта граница должна устанавливаться при проектировании выбором параметров кода.
Из эвристических соображений сформулируем свойства помехоустойчивого кода с исправлением ошибок, которые позволили бы обеспечить его применение для защиты информации в современных информационных и телекоммуникационных системах в любых из существующих задачах применения.[14]
1. Код имеет режимы обнаружения и исправления ошибок с обеспечением в обоих режимах гарантированной (наперед заданной) вероятности декодирования с ошибкой в произвольном канале связи и надежным отказом от декодирования при невозможности исправления ошибки.
2. Код имеет такую исправляющую способность и позволяет выбрать такие параметры n и k, что использующий их алгоритм передачи информации характеризуется нехудшими вероятностно-временными характеристиками по сравнению с применением альтернативных кодов.
3. Код обеспечивает в режиме исправления ошибок выделение с заданной точностью части правильно принятых символов даже при кратности ошибки, превышающей исправляющую способность кода.
4. Код позволяет декодировать несколько копий (одинаковых по содержанию информации кодовых блоков) блока с эффективностью, превышающей эффективность декодирования исходного кода с обнаружением или исправлением ошибок. Это свойство может применяться для работы по параллельным каналам, при многократной передаче сообщения по одному каналу или в канале с обратной связью при обработке копий после приема повторенного блока.
5. Процедуры кодирования и декодирования кода содержат, в основном, операции по модулю 2.
6. Метод кодирования должен обладать свойствами случайности сигналов на выходе кодера, обеспечивающими совместное решение задач обеспечения помехоустойчивости и секретности в постановке К. Шеннона.
1.4.3 Код Шеннона
Оптимальным кодом можно определить тот, в котором каждый двоичный символ будет передавать максимальную информацию. В силу формул Хартли и Шеннона максимум энтропии достигается при равновероятных событиях, следовательно, двоичный код будет оптимальным, если в закодированном сообщении символы 0 и 1 будут встречаться одинаково часто.[8]
Рассмотрим в качестве примера оптимальное двоичное кодирование букв русского алфавита вместе с символом пробела «-». Полагаем, что известны вероятности появления в сообщении символов русского алфавита, например, приведенные в таблице 3.
Таблица 3.Частота букв русского языка (предположение)
К. Шеннон и Р. Фано независимо предложили в 1948-1949 гг. способ построения кода, основанный на выполнении условия равной вероятности символов 0 и 1 в закодированном сообщении. [10]
Все кодируемые символы (буквы) разделяются на две группы так, что сумма вероятностей символов в первой группе равна сумме вероятностей символов второй группы (то есть вероятность того, что в сообщении встретится символ из первой группы, равна вероятности того, что в сообщении встретится символ из второй группы).
Для символов первой группы значение первого разряда кода присваивается равным «0», для символов второй группы – равными «1».
Далее каждая группа разделяется на две подгруппы, так чтобы суммы вероятностей знаков в каждой подгруппе были равны. Для символов первой подгруппы каждой группы значение второго разряда кода присваивается равным «0», для символов второй подгруппы каждой группы – «1». Такой процесс разбиения символов на группы и кодирования продолжается до тех пор, пока в подгруппах не остается по одному символу.
Пример кодирования символов русского алфавита приведен в табл. 4
Таблица 4. Пример кодирования букв русского алфавита с помощью кода Шеннна-Фано.
Анализ приведенных в таблице кодов приводит к выводу, что часто встречающиеся символы кодируются более короткими двоичными последовательностями, а редко встречающиеся - более длинными. Значит, в среднем для кодирования сообщения определенной длины потребуется меньшее число двоичных символов 0 и 1, чем при любом другом способе кодирования.
Вместе с тем процедура построения кода Шеннона-Фано удовлетворяет критерию различимости Фано. Код является префиксным и не требует специального символа, отделяющего буквы друг от друга для однозначного него декодирование двоичного сообщения.
Таким образом, проблема помехоустойчивого кодирования представляет собой обширную область теоретических и прикладных исследований. Основными задачами при этом являются следующие: отыскание кодов, эффективно исправляющих ошибки требуемого вида; нахождение методов кодирования и декодирования и простых способов их реализации.
Наиболее разработаны эти задачи применительно к систематическим кодам. Такие коды успешно применяются в вычислительной технике, различных автоматизированных цифровых устройствах и цифровых системах передачи информации.
2.Практическая реализация задачи кодирования
2.1 Пример к первой теореме Шеннона
Задача эффективного кодирования описывается триадой:
X = {X 4i 0} - кодирующее устройство - В.
Здесь Х, В - соответственно входной и выходной алфавит. Под множеством х 4i 0 можно понимать любые знаки (буквы, слова, предложения). В - множество, число элементов которого в случае кодирования знаков числами определяется основанием системы счисления 2 ( например 2, m = 2 2) . Кодирующее устройство сопоставляет каждому сообщению x 4i 0 из Х кодовую комбинацию, составленную из n 4i символов множества В. Ограничением данной задачи является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой комбинации.
Для решения данной задачи должна быть известна вероятность P 4i появления сообщения x 4i 0, которому соответствует определенное количество символов n 4i алфавита B. Тогда математическое ожидание количества символов из B определится следующим образом: n 4ср = n 4i P 4i (средняя величина).
Этому среднему количеству символов алфавита В соответствует максимальная энтропия H 4max = n 4ср log m. Для обеспечения передачи информации, содержащейся в сообщениях Х кодовыми комбинациями из В, должно выполняться условие H 4max >= H(x) 4, или n 4ср log m >= - P 4i log P 4i . В этом случае закодированное сообщение имеет избыточность
n 4ср >= H(x)/logm, n 4min= H(x)/log 4 m.
Коэффициент избыточности
Ku = (H 4max - H(x))/H 4max = (n 4ср- n 4min )/n 4ср .
Составим соответствующую таблицу. Имеем:
n 4min= H(x)/log 2 = 2.85, Ku = (2.92 - 2.85)/2.92 = 0.024,
т.е. код практически избыточности не имеет. Видно, что среднее количество двоичных символов стремится к энтропии источника сообщений.
Таблица 2.1 Пример к первой теореме Шеннона
| N0,1 | P(x,4i) | (x,4i) | код | n,4i | n,4i p,4i | Px 4i log Px 4i |
| 12345678 | 0.190.160.160.150.120.110.090.02 | X1X2X3X4X5X5X7X8 | 1000101110010111110111001 | 23333344 | 0.380.480.480.450.360.330.360.08 | -4.5522-4.2301-4.2301-4.1054-3.6706-3.5028-3.1265-3.1288 |
| Px 41 0=1,0 | =2.92 | H(x)=2.85 |
2.2 Пример построения кода Шеннона
В таблице 2.2 приведены промежуточные вычисления и результат построения кода Шеннона. Средняя длина кодовых слов l = 2,95. В данном случае избыточность кода Шеннона на 0,5 бита больше, чем избыточность кода Хаффмена. Из этого рисунка понятно, почему код неэффективен. Кодовые слова для букв b , d , e , f могут быть укорочены на 1 бит без потери свойства однозначной декодируемости.