Файл: Методы кодирования данных (Процесс формирования цифровых сигналов).pdf

Из эвристических соображений сформулируем свойства помехоустойчивого кода с исправлением ошибок, которые позволили бы обеспечить его применение для защиты информации в современных информационных и телекоммуникационных системах в любых из существующих задачах применения.[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.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

Вспомним, что длина слова и его вероятность связаны соотношением

l_i = [− log p_i ]≥ − log p_i .

Поэтому p_i ≥2^-li .

С учетом этого неравенства

q _j − q _i ≥ 2^-li

В двоичной записи числа в правой части мы имеем после запятой l_i −1 нулей и единицу в позиции с номером li. Это означает, что по меньшей мере в одном из l_i разрядов слова c_i и c_j отличаются и, следовательно, c_i не является префиксом для c_j. Поскольку это верно для любой пары слов, то код является префиксным.

Заметим, что длины кодовых слов в коде Шеннона точно такие же, какие были выбраны при доказательстве прямой теоремы кодирования. Повторяя выкладки, получим уже известную оценку для средней длины кодовых слов

l ≤ H +1.

Примечательно, что при построении кода Шеннона мы выбрали длины кодовых слов приблизительно равными (чуть большими) собственной информации соответствующих сообщений. В результате средняя длина кодовых слов оказалось приблизительно равной (чуть большей) энтропии ансамбля.

2.3 Пример Кода Шеннона

Допустим, нужно закодировать некоторое сообщение: AABCDAABC

Имеем :

A - 5 5/10 = 0.5

B - 2 2/10 = 0.2

C - 2 2/10 = 0.2

D - 1 1/10 = 0.1

Длина всего сообщения 10 (Вычисляется вероятность встречаемости каждого символа и располагаем их в столбик в порядке убывания вероятностей)

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

0.5 - первая часть = 0.5

-----

0.2 \

0.2 | - вторая часть = 0.5

0.1 /

Напротив вероятностей верхней части проставляем нули, напротив нижней - единицы. В нашем примере получим.

0.5 0

0.2 1

0.2 1

0.1 1

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

А 0.5 0

B 0.2 10

C 0.2 110

D 0.1 111

Итого - AABCDAABC = 0 0 10 110 111 0 0 10 110

Причём закодированное сообщение (это видно) не может быть раскодировано несколькими способами, хотя длина кодов символов отличается. Чтобы прочитать закодированное сообщение стpоится бинаpное деpево. В нашем слyчае оно бyдет такое.

()

/ \

0(A) 1

/ \

0(B) 1

/ \

0(C) 1(D)

Вот еще пример составления кодовых комбинаций по вероятностям:

0.3 00

0.25 01

--------------- (первое деление)

0.1 100

0.1 101

------------- (второе деление)

0.1 1100

0.05 1101

----------- (третье деление)

0.05 1110

0.05 1111

2.4 Пример кодирования и декодирования методом Шеннона-Фано

С помощью табл. 4 можно закодировать и декодировать любое сообщение. В виде примера запишем двоичным кодом фразу: "Теория информаций"

0 111 010000 11 01 000 11 011 11 0000

01101000111111 111 00110 100