Теория кодирования

     Защита  от ошибок в различных телекоммуникационных системах сводится к применению протоколов, содержащих описание двух основных функций: помехоустойчивого кодирования  и управления передачей на конкретном протокольном уровне (для канального, сетевого и сеансового уровней) эталонной модели взаимодействия открытых систем (ЭМВОС). Защита информации в таких системах сводится не только к борьбе с независимыми искажениями в канале связи (в двоичном – симметричном канале ДСК), но и к защите от группирующихся искажений (пакетов ошибок) и от преднамеренных искажений. Выше было показано, что в канале с более сложным распределением потока ошибок, чем в ДСК, применение кодов, исправляющих ошибки, затруднено. Применение кодов с исправлением ошибок преднамеренного характера до последнего времени считалось в принципе невозможным, хотя бы для классических алгебраических кодов.

     С учетом сказанного выше, можно сказать, что теория алгебраического кодирования  с алгоритмом декодирования по принципу максимального правдоподобия для исправления независимых ошибок является примером того, как ошибочная постановка задачи о независимых ошибках в канале связи сводит практически на нет труды целого поколения исследователей.

     Для обеспечения применения кодов, исправляющих ошибки, сформулируем два варианта постановки задачи. [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)/log m, 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 Пример к первой теореме Шеннона

 

     2.2 Пример построения кода Шеннона 

     В таблице 2.2 приведены промежуточные вычисления и результат построения кода Шеннона. Средняя длина кодовых слов l = 2,95. В данном случае избыточность кода Шеннона на 0,5 бита больше, чем избыточность кода Хаффмена. Из этого рисунка понятно, почему код неэффективен. Кодовые слова для букв b , d , e , f могут быть укорочены на 1 бит без потери свойства однозначной декодируемости. 

     Таблица 2.2 Построение кода Шеннона

 

     Докажем однозначную декодируемость кода Шеннона. Для этого выберем сообщения с номерами i и j , i < j . Кодовое слово c_i для i заведомо короче, чем слово c_j для j , поэтому достаточно доказать, что эти слова отличаются в одном из первых l_i символов.

     Рассмотрим  разность q_j − q_i =Σ p_k − Σ p_k =Σ p_k ≥ p_i