Передача информации по каналу с решающей обратной связью (стр. 3 из 11)

При n=1 n-мерный куб превращается в прямую длиной d=1, на одном конце которой располагается 1, а на другом — 0. При n = 2 четыре возможные комбинации (N=2²=4) располагаются на четырех вершинах квадрата. При этом комбинации 00 и 11, а также 10 и 01 отличаются друг от друга в двух разрядах, т.е. d=2.

Кодовое расстояние между двумя комбинациями двоичного кода равно числу единиц, полученных при сложении этих комбинаций по модулю 2, например 10

01=11 и 00 11=11. Такое определение кодового расстояния удобно при большой разрядности кодов. Так, складывая комбинации

10110101101

10000000010

00110101111,

определяем, что кодовое расстояние между ними d = 7.

При n = 3 восемь кодовых комбинаций размещаются в вершинах трехмерного куба.

Рис.1.2. Геометрическая модель двоичных кодов

Трехмерный куб строится так (рис.1.2), что одна из его вершин лежит в начале координат. Каждой вершине куба приписывается кодовая комбинация по следующему правилу: на i-м месте кодовой комбинации ставится 0, если проекция этой вершины на i-ю ось координат равна нулю, и 1, если проекция равна единице. Например, требуется узнать, какую следует записать комбинацию в вершине A₆ (рис.1.2). Проецируя эту вершину на ось Х₁, получим единицу. На втором месте комбинации запишется также 1 (проекция на ось X₂ равна единице). Так как проекция на ось Х₃ равна нулю (проекция в начало координат), то на третьем месте комбинации запишется 0. Следовательно, вся комбинация в вершине A₆ запишется как 110.

Если использовать все восемь слов, записанных в вершинах куба, то образуется двоичный код на все сочетания. Как было показано, такой код является непомехоустойчивым. Если же уменьшить число используемых комбинаций с восьми до четырех, то появится возможность обнаружения одиночных ошибок. Для этого выберем только такие комбинации, которые отстоят друг от друга на расстояние d = 2, например 000, 110, 011 и 101. Остальные кодовые комбинации не используются. Если будет принята комбинация 100, то очевидно, что при ее приеме произошла одиночная ошибка.

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

Кроме указанной группы комбинаций в том же трехмерном кубе может быть получена еще одна группа комбинаций с кодовым расстоянием d=2 (111, 001, 010 и 100). В этих кодовых комбинациях нечетное число единиц и каждая из комбинаций могут быть использованы для обнаружения ошибки, возникшей при передаче, так как при одиночном искажении в комбинации будет четное число единиц. Однако, если необходимо получить код с обнаружением одиночной ошибки, в передаче может участвовать только одна группа, т. е. четыре комбинации из возможных восьми. В противном случае получится непомехоустойчивый код, в котором будут встречаться комбинации с d=l.

Таким образом, в помехозащищенных кодах есть комбинации разрешенные, составленные по определенному правилу, и запрещенные, не соответствующие этому правилу.

Так, если из восьми комбинаций трехразрядного кода образованы четыре комбинации, позволяющие обнаружить одиночную ошибку (например, 111, 001, 010 и 100), то эти комбинации являются разрешенными, а остальные четыре (000, 011, 101 и 110) — запрещенными, которые должны фиксироваться на приеме как искаженные. Иногда совокупность разрешенных кодовых комбинаций, которые при заданных возможных искажениях не могут перейти друг в друга, называют системой непереходящих сигналов.

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

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

Выберем в трехмерном кубе такие вершины, кодовые обозначения которых отличались бы друг от друга на d=3. Такие вершины расположены на концах пространственных диагоналей куба. Их может быть только четыре пары: 000 и 111, 001 и 110, 100 и 011, 010 и 101. Однако из этих четырех пар для передачи можно брать только одну любую пару, так как большее число пар приведет к тому, что в передаче будут использоваться комбинации, отличающиеся друг от друга на d<3.

Код, образованный по такому правилу, может исправить одиночную ошибку или обнаружить две ошибки без их исправления. Пусть, например, передается код, состоящий из комбинаций 001 и 110. На приеме получена комбинация 100. Сравнение ее с исходными комбинациями показывает, что от комбинации 110 она отличается в одном (втором) разряде, а от комбинации 001 — в двух разрядах. Если считать, что сделана одна ошибка, то полученную комбинацию 100 следует исправить на 110.

От разрешённой комбинации 001 отличаются нa d=l комбинации 011, 000 и 101, а от комбинации 110 — комбинации 111, 100 и 010. Они и являются своеобразными комбинациями-спутниками, которые после приема можно относить к той или иной исходной комбинации.

Когда говорят об исправлении одиночной ошибки, считают, что вероятность двойной ошибки в канале связи пренебрежимо мала. Если такая вероятность достаточно велика, то код с d = 3 можно использовать для обнаружения двойных ошибок, но при этом исправить одиночную ошибку он уже не может. Действительно, если в нашем примере была принята комбинация 100, то нельзя утверждать, что была передана комбинация 110, так как при двойных ошибках это могла быть и искаженная комбинация 001.

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

Корректирующая способность кода зависит от кодового расстояния: а) при d=1 ошибка не обнаруживается; б) при d = 2 обнаруживаются одиночные ошибки; в) при d = 3 исправляются одиночные ошибки или обнаруживаются двойные ошибки. В общем случае

d = r + s + 1,

где d — минимальное кодовое расстояние; r — число обнаруживаемых ошибок; s — число исправляемых ошибок.

При этом обязательным условием является r≥s. Так, в нашем примере d = 3, и если r = s = l, то код может обнаружить одну ошибку и исправить ее. Если r =2, s=0, то код может только обнаружить две ошибки. Как следует из уравнения, для исправления одной ошибки и обнаружения двух ошибок необходимо, чтобы d = 2 + 1 + 1 =4. При d=4 может быть также вариант, когда r=3, s=0. Если d=5, то могут быть три варианта: r = s = 2; r=3, s=l; r = 4, s=0.

Если код только обнаруживает ошибки, то

d=r + l, т.е. r = d - 1.

Если код только исправляет ошибки, то

d=2s+1, т.е. s=(d – 1)/2

Итак, геометрические модели позволяют просто строить малоразрядные корректирующие коды. Однако при длине кода n>3 геометрической моделью пользоваться трудно, так как она должна быть многомерной. Поэтому для построения многоразрядных помехоустойчивых кодов используют различные правила и методики, к рассмотрению которых и перейдем.

1.2.3 Помехозащищенные коды. Циклический код

Циклические коды относятся к числу блоковых систематических кодов, в которых каждая комбинация кодируется самостоятельно (в виде блока) таким образом, что информационные k и контрольные m символы всегда находятся на определенных местах.

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

Теория циклических кодов базируется на теории групп и алгебре многочленов над полем Галуа.

Многочлен (полином), который можно представить в виде произведения многочленов низших степеней, называют приводимым (в данном поле), в противном случае — неприводимым. Неприводимые многочлены играют роль, сходную с простыми числами в теории чисел. Неприводимые многочлены Р(Х) можно записать в виде десятичных или двоичных чисел либо в виде алгебраического многочлена (табл. 1.1).

Таблица 1.1 Неприводимые многочлены и их эквиваленты

Р(Х1)=Х+1→3→11	Р(Х5)= Х5+Х3+Х2+Х+1→47→101111
Р(Х2)=Х2+Х+1→7→111	Р(Х5)= Х5+Х4+Х2+Х+1→55→110111
Р(Х3)=Х3+Х+1→11→1011	Р(Х5)= Х5+Х4+Х3+Х+1→59→111011
Р(Х3)= Х3+Х2+ 1→13→1101	Р(Х5)= Х5+Х4+Х3+Х2+1→61→111101
Р(Х4)=Х4+Х+1→19→10011	Р(Х6)= Х6+Х+1→67→1000011
Р(Х4)=Х4+Х3+1→25→11001	Р(Х7)= Х7+Х3+1→137→10001001
Р(Х4)= Х4+Х3+ Х2+Х+1→31→11111	Р(Х8)= Х8+Х4+Х3+ Х2+1→285→100011101
Р(Х5)= Х5+Х2+1→37→100101	Р(Х9)= Х9+Х4+1→1041→1000010001
Р(Х5)= Х5+Х3+1→41→101001	Р(Х10)= Х10+Х3+ 1→2057→10000001001

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