Лекции по теории информации. Фурсов teoria_informacii. Лекции по теории информации под редакцией Н. А. Кузнецова
 Скачать 1.32 Mb.
|
|
10.2 Общие принципы построения помехоустойчивых кодов Повышение достоверности передачи и хранения информации достигается введением избыточности (дополнительных символов). При выборе этих симво- лов используются условия, проверка которых при декодировании дает возмож- ность обнаруживать и исправлять ошибки. Коды, обладающие этим свойством, называют помехоустойчивыми. Обычно указанные условия связаны с алгебраической структурой кода, при этом соответствующий код называют алгебраическим. Алгебраические ко- ды могут строиться как блоковые или непрерывные. В случае блоковых кодов процедура кодирования заключается в сопоставлении k информационным сим- волам, соответствующих кодируемому знаку, блока из n символов. Если n по- стоянно для всех знаков кодируемого сообщения, блоковый код называют рав- номерным. Предположим, что на вход кодирующего устройства поступает последова- тельность из k (соответствующих кодируемому знаку) информационных сим- волов, которые преобразуются в кодовую комбинацию из n символов, причем n k . Всего возможно 2 k различных входных и 2 n выходных последователь- ностей. Среди указанных выходных последовательностей только 2 k так назы- ваемых разрешенных последовательностей, соответствующих входным инфор- мационным последовательностям. Остальные 2 2 n k комбинаций являются за- прещенными. Ясно, что любая из 2 k разрешенных комбинаций может быть трансформирована помехой в любую из 2 n комбинаций. При этом возможны следующие случаи; 1) 2 k случаев безошибочной (неискаженной) передачи; 90 2) 2 (2 2 ) k n k случаев, когда разрешенные комбинации помехой трансфор- мируются в запрещенные, но обнаруживаемые; 3) 2 (2 1) k k случаев перехода в другие разрешенные комбинации. Такие ошибки не могут быть обнаружены. Поскольку всего случаев передачи 2 2 k n , относительное число обнаружи- ваемых ошибок (вероятность обнаружения ошибки) составит 2 (2 2 ) 1 1 2 2 2 k n k k n n k p Нетрудно заметить, что при n вероятность обнаружения ошибки стремит- ся к единице. Из соображений простоты реализации число n k проверочных разрядов, характеризующих избыточность кода, ограничивают. Избыточность является одной из основных характеристик помехоустойчи- вого кода. Относительную избыточность определяют как 1 n k R n или n k R k При n предельное значение 1 R равно 1, а R – бесконечности. Процедуры определения проверочных символов обычно строятся как ли- нейные операции над определенными информационными символами. Поэтому эти коды называют линейными. 10.3 Математическое введение к линейным кодам Кодовые комбинации можно рассматривать как элементы некоторого множества. Множество элементов, в котором определена одна основная опера- ция, выполняются аксиомы замкнутости и ассоциативности, имеется нулевой (если основная операция – сложение) или единичный (если основная операция – умножение) и для всякого элемента существует противоположный (обрат- ный) элемент называется группой. Если основная операция коммутативна, группа называется коммутатив- ной или абелевой. Число элементов в конечной группе называют порядком группы. Для построения двоичных кодов используется коммутативная опера- 91 ция сложения по модулю 2, при выполнении которой число разрядов кода не увеличивается. Поэтому множество n -разрядных комбинаций двоичного кода является конечной абелевой группой. Подмножество группы, само являющееся группой относительно операции, заданной в группе, называют подгруппой. Пусть в абелевой группе задана подгруппа и элемент j b . Множество элементов, образованное как суммы (по модулю 2) элемента j b с каждым из элементов подгруппы : , j j b b a a называется смежным классом, а сам элемент j b – образующим элементом. Задавая образующие элементы группы так, чтобы они не входили в уже образованные классы, можно разложить всю группу на смеж- ные классы по подгруппе . Заметим, что в соответствии с теоремой Шеннона любой метод кодирова- ния можно рассматривать, как правило разбиения множества запрещенных ко- довых комбинаций на 2 k непересекающихся подмножества, в каждом из кото- рых лишь одна разрешенная комбинация. Операция разложения на классы смежности указывает формальное правило такого разбиения. 92 Лекция 11 Построение групповых кодов 11.1 Понятие корректирующей способности кода Кодовое расстояние d выражается числом символов, в которых последо- вательности отличаются друг от друга. Для определения кодового расстояния между двумя комбинациями двоичного кода достаточно сложить их по модулю 2, и подсчитать число единиц в полученном результате. Минимальное расстоя- ние, подсчитанное по всем парам разрешенных кодовых комбинаций, называют минимальным кодовым расстоянием данного кода. Вес (Хэмминга) кодовой последовательности определяется как число нену- левых компонент этой последовательности. Ясно, что кодовое расстояние меж- ду двумя последовательностями равно весу некоторой третьей последователь- ности, являющейся их суммой, которая (в силу свойства операции сложения по модулю два) также обязана быть последовательностью данного кода. Следова- тельно, минимальное кодовое расстояние для линейного кода равно минималь- ному весу его ненулевых векторов. Вектором ошибок называют n -разрядную двоичную последовательность, содержащую единицы в разрядах, подверженных ошибкам, и нули в остальных разрядах. Любая искаженная комбинация может рассматриваться как результат сложения по модулю 2 исходной разрешенной комбинации и вектора ошибки. Число r искаженных символов кодовой комбинации называют кратно- стью ошибки. При кратности ошибок r всего может быть r n C n -разрядных двоичных векторов ошибок. Ошибки символов, при которых вероятность появ- ления любой комбинации зависит только от числа r искаженных символов и вероятности p искажения одного символа, называют взаимно независимыми. При взаимно независимых ошибках вероятность искажения любых r символов в n -разрядной кодовой комбинации 1 n r r r r n p C p p 93 Корректирующая способность кода характеризуется значениями кратно- сти r ошибок, которые обнаруживаются, и кратностью s ошибок, которые мо- гут исправляться корректирующим кодом. Подчеркнем, что конкретный кор- ректирующий код не обязан исправлять любую комбинацию ошибок. Он может обнаруживать и исправлять лишь ошибки заданной кратности, которые прини- мались в расчет при его построении. 11.2 Общая схема построения группового кода Исходными данными для построения группового кода являются: объем кода Q (количество передаваемых дискретных сообщений) и заданная коррек- тирующая способность. Задача заключается в определении числа разрядов n кода и правила формирования проверочных разрядов. Количество информационных разрядов k по заданному Q определяется из условия 2 1 k Q (11.1) (здесь учтено, что нулевая комбинация обычно не используется, т.к. не изменя- ет состояния канала связи). Далее каждой из этих 2 1 k ненулевых информаци- онных последовательностей необходимо поставить в соответствие n - разрядный избыточный код (разрешенную комбинацию). Множество 2 k n -разрядных разрешенных комбинаций (вместе с нулевой) образует подгруппу группы всех 2 n n-разрядных комбинаций. Разложим группу на смежные классы по этой подгруппе. В качестве образующих элементов смежных классов примем векторы ошибок, которые мы намерены исправлять. Если, например, ставится задача исправлять все одиночные ошибки (крат- ность 1 s ), то в качестве образующих элементов должны быть взяты n разных векторов, содержащих по одной единице в одном из n разрядов. Если кроме одиночных необходимо исправлять также все двойные ошибки (кратность 2 s ), то добавится 2 s n n С С векторов ошибок (образующих элементов классов) и т.д. 94 Кроме самой подгруппы разрешенных комбинаций в результате разложе- ния группы всех n-разрядных комбинаций может быть образовано 2 1 n k не- пересекающихся смежных классов. Если число подлежащих исправлению век- торов ошибок не превышает числа смежных классов, каждому из них можно поставить в соответствие некоторый класс смежности. Таким образом, для того чтобы обеспечивалась возможность определения и исправления ошибок крат- ности до s включительно, в общем случае должно выполняться неравенство 1 2 2 1 n k s n n n С С С или 0 2 s n k i n i С (11.2) В соответствии с (11.2) число разрядов корректирующего кода, предназначен- ного для исправления ошибок кратности s , определяется неравенством: 2 0 log s i n i n k C (11.3) Для исправления ошибок необходимо определить, какому классу смежно- сти принадлежит принятая кодовая последовательность, а затем соответствую- щий этому классу образующий элемент (вектор ошибки) сложить (по модулю два) с принятой последовательностью. Для определения класса смежности каж- дому из них ставится в соответствие последовательность n k символов, назы- ваемая опознавателем или синдромом. Исправление ошибок возможно лишь при взаимнооднозначном соответствии между множеством смежных классов (векторов ошибок) и множеством опознавателей. 11.3 Связь корректирующей способности с кодовым расстоянием Обычно декодирование осуществляется таким образом, что любая приня- тая запрещенная кодовая комбинация отождествляется с разрешенной комби- нацией, находящейся от неё на минимальном кодовом расстоянии. Если мини- мальное кодовое расстояние данного кода 1 d , т.е. все комбинации кода яв- ляются разрешенными, то обнаружить ошибку не удастся. Если 2 d , то удаст- ся обнаружить единичную ошибку и т.д. В общем случае при необходимости 95 обнаружения ошибки кратности до r включительно, минимальное кодовое рас- стояние должно удовлетворять условию min 1 d r . (11.4) Для исправления ошибок кратности s , в соответствии с описанной в раз- деле 11.2 общей схемой построения группового кода, каждой разрешенной ко- довой комбинации необходимо поставить в соответствие подмножество запре- щенных комбинаций так, чтобы эти подмножества не пересекались. Для этого должно выполняться неравенство min 2 1 d s . (11.5) Число комбинаций, расположенных на расстоянии i от заданной разрешенной, равно i n C . Следовательно, при выполнении условия (11.5) число исправляемых ошибок будет равно числу запрещенных комбинаций, находящихся в подмно- жестве, соответствующем разрешенной комбинации: 1 s i n i C Для исправления ошибок кратности s и одновременного обнаружения всех ошибок кратности r ( r s ) минимальное кодовое (хэммингово) расстоя- ние должно удовлетворять неравенству min 1 d r s . (11.6) Дадим геометрическую трактовку приведенным выше соотношениям. Любая n -разрядная двоичная кодовая комбинация может быть интерпре- тирована как вершина n -мерного гиперкуба с длиной ребра равной 1. Напри- мер, при 2 n это квадрат, при 3 n – единичный куб. В общем случае n - мерный гиперкуб содержит 2 n вершин, что совпадает с возможным числом n - разрядных двоичных кодовых комбинаций. Кодовое расстояние можно интерпретировать, как наименьшее число ре- бер, которое надо пройти, чтобы попасть из одной разрешенной комбинации в другую. В подмножество каждой разрешенной комбинации в соответствии с (11.5) относят все вершины, оказавшиеся в сфере радиуса 1 2 s d (11.7) 96 Если в результате действия шума разрешенная комбинация переходит в точку, принадлежащую сфере, то она может быть исправлена. 11.4 Построение опознавателей ошибок В соответствии с общей схемой построения группового кода, каждой из 2 1 k ненулевых информационных последовательностей ставится в соответст- вие n -разрядная разрешенная кодовая комбинация, в которой n k символов проверочные. Они должны быть заполнены опознавателями так, чтобы имело место взаимнооднозначное соответствие множеств исправляемых ошибок (классов смежности) и опознавателей. Предположим, что двоичный код, предназначенный для исправления всех ошибок кратности до s включительно, построен так, что в (11.2), (11.3) имеет место равенство: 1 2 1 s n k i n i C В частности, если исправлению подлежат только одиночные ошибки, имеем 2 1 n k n Этому равенству удовлетворяют, например, 7 n и 4 k . Для указанных зна- чений можно построить 3 7 4 2 2 1 2 1 7 классов смежности. Каждому из этих 7-ми классов смежности можно поставить в соответствие трехразрядный опознаватель вектора ошибки. В данном случае в качестве опознавателей мож- но взять двоичные числа, указывающие номер разряда, в котором произошла ошибка (таблица 11.1). При построении опознавателей ошибок более высокой кратности (векторы ошибок имеют единицы в нескольких разрядах) их можно строить как суммы по модулю два опознавателей одиночных ошибок. При этом, (выбирая очеред- ной опознаватель одиночной ошибки в следующем разряде), необходимо 97 следить за тем, что очередная кодовая комбинация и формируемые с ее ис- пользованием опознаватели векторов ошибок более высокой кратности еще не использованы в качестве опознава- телей одиночных и кратных ошибок в предшествующих разрядах. Такую проверку необходимо делать при пере- ходе к одиночной ошибке каждого следующего разряда. Заметим, что при использовании указанной процедуры формирования опо- знавателей для составления проверочных равенств, о которых пойдет речь в следующем разделе, достаточно знать лишь опознаватели одиночных ошибок в каждом разряде. 11.5 Определение проверочных равенств и уравнений кодирования Как указывалось выше, для обеспечения возможности исправления оши- бок на этапе построения кода необходимо обеспечить взаимнооднозначное со- ответствие между множеством векторов ошибок, смежных классов и множест- вом опознавателей. На этапе декодирования процедура определения символов опознавателя реализуется с использованием так называемых проверочных равенств как про- верка на четность. При отсутствии ошибок в декодируемой последовательности в результате всех проверок на четность, должен получиться опознаватель из одних нулей. При наличии ошибок в соответствующих разрядах опознавателя появляются единицы. Рассмотрим общие принципы построения проверочных равенств и уравнений кодирования. Для наглядности изложение проведем на примере построенного выше кода (7,4), который носит исключительно иллюст- ративный характер. Таблица 11.1 Вектор ошибки № разряда Опозна- ватель 0000001 0000010 0000100 0001000 0010000 0100000 1000000 1 2 3 4 5 6 7 001 010 011 100 101 110 111 98 Разряды, которые должны входить в каждую из проверок на четность оп- ределяются по таблице опознавателей (таблица 11.1). В коде (7,4) число прове- рочных разрядов, а, следовательно, и проверочных равенств должно быть три: 7 4 3 n k В данном случае в качестве опознавателей взяты двоичные коды номеров разрядов, в которых произошла ошибка. Каждое проверочное равенство стро- ится по значениям символов в соответствующем этому равенству разряде опо- знавателей. Единица в первом (младшем) разряде опознавателя является след- ствием ошибки в одном из следующих разрядов: 1, 3, 5, 7; поэтому в качестве первого проверочного равенства можно взять 1 3 5 7 0 a a a a . (11.8) Единица во втором разряде опознавателей является следствием ошибки в одном из следующих разрядов: 2, 3, 6, 7. Поэтому второе проверочное равенст- во определяется как 2 3 6 7 0 a a a a . (11.9) Аналогично, единица в третьем разряде опознавателей является следстви- ем ошибки в одном из следующих разрядов: 4, 5, 6, 7; т.е. третье проверочное равенство можно записать в виде: 4 5 6 7 0 a a a a . (11.10) Номера проверочных разрядов целесообразно выбирать так, чтобы каждый из них входил только в одно проверочное равенство (11.8)-(11.10). Это обеспе- чит однозначное определение значений символов в проверочных разрядах при кодировании: 1 3 5 7 2 3 6 7 4 5 6 7 a a a a a a a a a a a a (11.11) В данном случае проверочными будут первый, второй и четвертый разряд, ко- торые заполняются на этапе формирования разрешенных комбинаций в соот- ветствии с уравнениями кодирования (11.11). 99 В рассматриваемом примере min 3 d , поэтому в соответствии с (11.4), (11.5) данный код может использоваться либо для обнаружения единичных и двойных ошибок, либо для исправления одиночных ошибок. Из таблицы 11.1. видно, что сумма любых двух опознавателей единичных ошибок дает ненуле- вой опознаватель, который и может использоваться для обнаружения двойной ошибки. Для того, чтобы одновременно исправлять одиночные и обнаруживать двойные ошибки необходимо в соответствии с (11.6) построить код с min 4 d , например, путем добавления еще одного (8-го разряда) для дополнительной проверки на четность. |