Учебное пособие по информатике 2014. Основы информатики
 Скачать 4.61 Mb.
|
|
Основные понятия теории кодирования Задача кодирования информации представляется как некоторое преобразование числовых данных в заданной системе счисления. В частном случае эта операция может быть сведена к группированию символов (представление в виде триад или тетрад) или представлению в виде символов (цифр) позиционной системы счисления. Так как любая позиционная система не несет в себе избыточности информации и все кодовые комбинации являются разрешенными, использовать такие системы для контроля не представляется возможным. Систематический код - код, содержащий в себе кроме информационных контрольные разряды. В контрольные разряды записывается некоторая информация об исходном числе. Поэтому можно говорить, что систематический код обладает избыточностью. При этом абсолютная избыточность будет выражаться количеством контрольных разрядов k, а относительная избыточность - отношением k/n , где n = m + k - общее количество разрядов в кодовом слове (m - количество информационных разрядов). Понятие корректирующей способности кода обычно связывают с возможностью обнаружения и исправления ошибки. Количественно корректирующая способность кода определяется вероятностью обнаружения или исправления ошибки. Если имеем n-разрядный код и вероятность 86 искажения одного символа p, то вероятность того, что искажены k символов, а остальные n - k символов не искажены, по теореме умножения вероятностей будет w = p k (1–p) n-k . Число кодовых комбинаций, каждая из которых содержит k искаженных элементов, равна числу сочетаний из n по k: )! ( ! ! k n k n C k n Тогда полная вероятность искажения информации k i i n i p p i n i n P 1 ) 1 ( )! ( ! ! Так как на практике p = 10 -3 ...10 -4 , наибольший вес в сумме вероятностей имеет вероятность искажения одного символа. Следовательно, основное внимание нужно обратить на обнаружение и исправление одиночной ошибки. Корректирующая способность кода связана также с понятием кодового расстояния. Кодовое расстояние d(A, В) для кодовых комбинаций А и В определяется как вес третьей кодовой комбинации, которая получается поразрядным сложением исходных комбинаций по модулю 2 (операция "исключающее ИЛИ", XOR), а говоря проще - количество различающихся разрядов в двух кодовых комбинациях. Вес кодовой комбинации V(A) - количество единиц, содержащихся в кодовой комбинации. Рисунок 3.16 – Геометрическое Рисунок 3.17 – Кодовые расстояния представление кодов Коды можно рассматривать и как некоторые геометрические (пространственные) фигуры. Например, триаду можно представить в виде единичного куба, имеющего координаты вершин, которые отвечают двоичным символам (рисунок 3.16). В этом случае кодовое расстояние воспринимается как сумма длин ребер между соответствующими вершинами A 1 A 2 A 3 A 1 A 1 A 2 A 2 A 2 A 3 A 1 A 1 A 2 A 2 A 2 A 3 A 3 d min d min d min d min d min d min а б в 001 101 100 110 010 011 000 111 '' ' ' ' ' ' N N N 87 куба (принято, что длина одного ребра равна 1). Оказывается, что любая позиционная система отличается тем свойством, что минимальное кодовое расстояние равно 1 (рисунок 3.17а). В теории кодирования показано, что систематический код способен обнаружить ошибки только тогда, когда минимальное кодовое расстояние для него больше или равно 2t, т.е. d min 2t, (3.6) где t - кратность обнаруживаемых ошибок (в случае одиночных ошибок t = 1 и т. д.). Это означает, что между соседними разрешенными кодовыми словами должно существовать по крайней мере одно кодовое слово (рисунок 3.17б,в). В тех случаях, когда необходимо не только обнаружить ошибку, но и исправить ее (т. е. указать место ошибки), минимальное кодовое расстояние должно быть d min 2t+1. (3.7) Допустим, имеем следующий набор кодовых комбинаций: 000 001 010 011 100 101 110 111 Геометрическая модель этого кода – куб, представленный на рисунке 3.16 Для рассматриваемого кода d min = 1. Учитывая, что рассматриваемый код по построению является неизбыточным, можно утверждать, что любой неизбыточный код имеет d min = 1 и наоборот, если d min = 1, код является неизбыточным. Из геометрической модели кода видно, что любая, даже одиночная, ошибка не может быть обнаружена кодом с d min = 1, так как любая кодовая комбинация, в которой произошла ошибка, переместившись на один кодовый переход, совпадет с соседней кодовой комбинацией и будет разрешенной. Для построения простейшего избыточного кода, который может обнаруживать одну ошибку, нужно отобрать рабочие комбинации на расстоянии d(A, B) ≥ 2. В рассматриваемом коде можно выбрать следующие комбинации: где M р – число разрешенных (или рабочих) комбинаций. 88 Избыточность полученного кода Если требуется обнаруживать две ошибки, то рабочих комбинаций будет только две (например, 000 и 111), минимальное кодовое расстояние в этом случае d min = 3, избыточность Если требуется обнаруживать три ошибки, d min ≥ 4, что невозможно обеспечить в рассматриваемом коде, так как кодовое расстояние d(A, B) ≤ 3. Если бы сообщения кодировались неизбыточным кодом, то для получения четырех кодовых комбинаций потребовалось бы m = 2 информационных элементов. Далее для иллюстрации неравенства о возможности исправления ошибки (3.7) приведем следующий пример. Возьмем три рядом стоящих слова (термин «рядом стоящие» означает, что между этими словами других слов быть не может): a = 0100, b = 0110, c = 0010. Далее получим соответствующие им кодовые слова f a = 1110100, f b = 0010110, f c = 1100010. Кодовые расстояния между этими словами равны: d(f a , f b ) = 3, d(f b , f c ) = 4, d(f a , f c ) = 3. Предположим, что при передачи информации в канале связи произошел сбой и второе кодовое слово изменилось на f b ' = 0110110. Тогда по минимальному кодовому расстоянию мы все же сможем определить, что из трех возможных слов передавалось скорее всего слово f b , так как: d(f a , f b ') = 2, d(f b , f b ') = 1, d(f c , f b ') = 3. Если же были допущены две ошибки, например, в пятом и четвертом разрядах, то становится непонятным, какое из кодовых слов – f b или f c – на самом деле передавалось, так как f b '' = 0111110, d(f a , f b '') = 3, d(f b , f b '' ) = 2, d(f c , f b '' ) = 2. Отсюда, чем больше минимальное кодовое расстояние между словами, тем лучше защищен код от помех. По вышеприведенному неравенству можно установить, что при d min = 3 число обнаруженных и исправленных ошибок не может быть больше одной (m ≤ 1), поскольку m ≤ (d min – 1)/2. Существуют коды, в которых невозможно выделить абсолютную избыточность. Неявная избыточность характерна также для кодов типа «k из n». Примером является код «2 из 5», который часто используется для представления информации. Суть его в том, что в слове из пяти разрядов только два разряда имеют единичное значение. Методы эффективного кодирования информации Информационную избыточность можно ввести разными путями. Рассмотрим один из путей эффективного кодирования. 89 В ряде случаев буквы сообщений преобразуются в последовательности двоичных символов. Учитывая статистические свойства источника сообщения, можно минимизировать среднее число двоичных символов, требующихся для выражения одной буквы сообщения, что при отсутствии шума позволит уменьшить время передачи. Такое эффективное кодирование базируется на основной теореме Шеннона для каналов без шума, в которой доказано, что сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов на букву будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины. Теорема не указывает конкретного способа кодирования, но из нее следует, что при выборе каждого символа кодовой комбинации необходимо стараться, чтобы он нес максимальную информацию. Следовательно, каждый символ должен принимать значения 0 и 1 по возможности с равными вероятностями и каждый выбор должен быть независим от значений предыдущих символов. При отсутствии статистической взаимосвязи между буквами конструктивные методы построения эффективных кодов были даны впервые К.Шенноном и Н. Фано. Их методики существенно не различаются, поэтому соответствующий код получил название кода Шеннона-Фано. Код строится следующим образом: буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей. Затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним - 0. Каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве. Рассмотрим алфавит из восьми букв (таблица 3.9). Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа. Таблица 3.9 – Кодирование по методике Шеннона-Фано Буквы Вероятности Кодовые комбинации z 1 0,22 11 z 2 0,20 101 z 3 0,16 100 z 4 0,16 01 z 5 0,10 001 z 6 0,10 0001 z 7 0,04 00001 z 8 0,02 00000 Вычислим энтропию набора букв: 90 (z) = - 8 1 i p(z i )log p(z i ) 2,76 и среднее число символов на букву l cp = - 8 1 i p(z i ) n(z i ) 2,84, где n(z i ) - число символов в кодовой комбинации, соответствующей букве z i Значения z i и l cp не очень различаются по величине. Рассмотренная методика Шеннона-Фано не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу. Множество вероятностей в предыдущей таблице можно было разбить иначе (таблица 3.10). При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием q > 2 неопределенность становится еще больше. Таблица 3.10 – Кодирование по методике Шеннона-Фано (продолжение) Буквы Вероятности Кодовые комбинации z 1 0,22 11 z 2 0,20 10 z 3 0,16 011 z 4 0,16 010 z 5 0,10 001 z 6 0,10 0001 z 7 0,04 00001 z 8 0,02 00000 От указанного недостатка свободна методика Д. Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву. Рисунок 3.18 – Кодирование по методике Хаффмена Буквы Вероятности Вспомогательные столбцы 1 2 3 4 5 6 7 z 1 z 2 z 3 z 4 z 5 z 6 z 7 z 8 0,22 0,20 0,16 0,16 0,10 0,10 0,04 0,02 0,22 0,20 0,16 0,16 0,10 0,10 0,06 0,22 0,20 0,16 0,16 0,16 0,10 0,26 0,22 0,20 0,16 0,16 0,32 0,26 0,22 0,20 0,42 0,32 0,26 0,58 0,42 1 91 Для двоичного кода методика сводится к следующему. Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероятностей. Две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность. Вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние объединяются. Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице. Для составления кодовой комбинации, соответствующей данному сообщению, необходимо проследить путь перехода сообщений по строкам и столбцам таблицы. Для наглядности строится кодовое дерево. Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваивается символ 1, а с меньшей - 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до каждой буквы (рисунок 3.19). Рисунок 3.19 – Кодовое дерево Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию: Таблица 3.11 – Кодирование по методике Хаффмена z 1 z 2 z 3 z 4 z 5 z 6 z 7 z 8 01 00 111 110 100 1011 10101 10100 Кодирование по методу четности-нечетности Если в математическом коде выделен один контрольный разряд (k = 1), то к каждому двоичному числу добавляется один избыточный разряд и в него записывается 1 или 0 с таким условием, чтобы сумма цифр в каждом числе была по модулю 2 равна 0 для случая четности или 1 для случая нечетности. 1 Z 4 Z 1 Z 2 Z 3 Z 6 Z 7 Z 8 Z 5 0 1 0 1 0 1 0 1 0 1 0 1 0 92 Появление ошибки в кодировании обнаружится по нарушению четности (нечетности). При таком кодировании допускается, что может возникнуть только одна ошибка. В самом деле, для случая четности правильной будет только половина возможных комбинаций. Чтобы одна допустимая комбинация превратилась в другую, должно возникнуть по крайней мере два нарушения или четное число нарушений. Пример реализации метода четности представлен в таблице 3.12. Таблица 3.12 – Пример реализации метода четности Число Контрольный разряд Проверка 10101011 1 0 11001010 0 0 10010001 1 0 11001011 0 1-нарушение Такое кодирование имеет минимальное кодовое расстояние, равное 2. Можно представить и несколько видоизмененный способ контроля по методу четности - нечетности. Длинное число разбивается на группы, каждая из которых содержит l разрядов. Контрольные разряды выделяются всем группам по строкам и по столбцам согласно следующей схеме: Рисунок 3.20 – Выделение контрольных разрядов по строкам и столбцам Увеличение избыточности информации приводит к тому, что появляется возможность не только обнаружить ошибку, но и исправить ее. Пусть произошла неисправность в каком-то из разрядов этого числа (представим, что разряд а 18 изменил состояние, т. е. а 18 = 1). Это приведет к тому, что при проверке на четность сумма i (a i +k i ) по соответствующим строкам и столбцам изменится для значений, которые содержат элемент а 18 , т. е. это будет четвертая сверху строка и третий слева столбец. Следовательно, нарушение четности по этой строке и столбцу означает обнаружение не только самой ошибки, но и места, где возникла ошибка. Изменив содержимое отмеченного разряда (в данном случае а 18 ) на противоположное, можно исправить ошибку. а 1 а 2 а 3 а 4 а 5 а 6 а 7 а 8 а 9 а 10 а 11 а 12 а 13 а 14 а 15 а 16 а 17 а 18 а 19 а 20 а 21 а 22 а 23 а 244 а 25 k 6 k 7 k 8 k 9 k 10 k 1 k 2 k 3 k 4 k 5 93 Коды Хэмминга Коды, предложенные американским ученым Р. Хэммингом, способны не только обнаружить, но и исправить одиночные ошибки. Эти коды - систематические. Предположим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было проведено k проверок. Если результат проверки свидетельствует об отсутствии ошибки, то запишем 0, если есть ошибка, то запишем 1 . Запись полученной последовательности символов образует двоичное, контрольное число, указывающее номер позиции, где произошла ошибка. При отсутствии ошибки в данной позиции последовательность будет содержать только нули. Полученное таким образом число описывает n = (m + k + 1) событий. Следовательно, справедливо неравенство 2 k (m + k + 1). Определить максимальное значение m для данного k можно из следующего: n… 1 2 3 4… 8…15 16…31 32…63 64 m…0 0 1 1… 4…11 11…26 26…57 57 k… 1 2 2 3… 4…4 5…5 6…6 7 Определим теперь позиции, которые надлежит проверить в каждой из k проверок. Если в кодовой комбинации ошибок нет, то контрольное число содержит только нули. Если в первом разряде контрольного числа стоит 1, то, значит, в результате первой проверки обнаружена ошибка. Имея таблицу двоичных эквивалентов для десятичных чисел, можно сказать, что, например, первая проверка охватывает позиции 1, 3, 5, 7, 9 и т. д., вторая проверка — позиции 2, 3, 6, 7, 10. |