Пример линейного кода
|
1000 |
111 |
|
|
|
|
|
|
|
Код Хемминга (7,4) |
G = 0100 011 = I ,P |
|||
|
|
|
k |
|
|
0010 |
101 |
|
|
|
0001 |
110 |
|
|
1011 100
H = 1101 010 = −PT ,In−k1110 001
y = xG = (x,c ), где c = xP
x =1100
111
c = xP =1100 011 =100101
110
y =1100100
|
Если в кодовом слове |
y возникает ошибка e (при его |
|
|
|
передачепо каналу связи или при хранении), т. е. y = y e (где |
||
e |
имеет единицы в позициях с ошибками и нули в остальных |
|
позициях, а означает поэлементное суммирование по mod 2), то, используя свойства кода, некоторые ошибки можно исправить (восстановить информационную~ последовательность x по искаженному кодовому слову y ).
Исправляющие свойства кода задаются его так называемым
минимальным кодовым расстоянием dmin , которое опреде-
ляется как минимальное число позиций, в которых отличаются любые несовпадающие между собой кодовые комбинации.
y
e y′
x
|
|
|
|
• |
• |
|
• |
• |
• |
|
• |
|
|
|
|
y =1100100 e = 0010000 y′ =1110100 x =1100
Если код имеет минимальное кодовое расстояние dmin , то он гарантированно (т. е. полностью) исправляет все ошибки
кратностине более t = |
dmin |
, где [x] означает целую часть числа |
|
||
2 |
|
|
x, а кратность ошибки – число искаженных позиций, т. е. число |
||
единицв образце ошибки |
e . |
|
В теории кодирования [4] разработаны методы построения ЛК (т. е. фактически их порождающих матриц), которые обеспечивают максимально возможные величины при заданныхпараметрах (n, k).
Как видно из соотношения (3.14), процедура кодирования для ЛК оказывается достаточно простой. Более того, для некоторых классов ЛК (например, для так называемых циклических кодов) онаможет быть еще более упрощена [4].
Декодирование линейных кодов
1.По максимуму правдоподобия – подобрать кодовое слово, имеющее мин. хемминговское расстояние от принятого слова.
2.Синдромное декодирование
y H |
= (y e )H |
|
= yH |
|
eH |
|
= 0 eH |
|
. |
eH |
|
|
|
|
′ T |
|
T |
|
T |
|
T |
|
T |
|
|
T -синдром |
|||
-найти синдром eHT |
|
|
|
|
|
|
e |
|
|
|
|
|
||
- по синдрому найти вектор ошибок (по таблице) |
; |
|
|
|
|
|||||||||
- сложить принятое слово и вектор ошибок y = y′ e ; |
|
|
111 |
|
|
|||||||||
- выделить информационную часть кодового слова. |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
011 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
101 |
|
|
|
|
|
|
|
|
|
eHT = (0010000) |
110 |
|
= (101) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. Конструктивные способы декодирования |
|
|
|
010 |
|
|||||||||
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
001 |
|
|
Однако процедура декодирования (т. е. исправления ошибок) остается весьма сложной для произвольных линейных кодов. Действительно, если известно, что данный код имеет заданное
dmin и произошла ошибка кратности |
t ≤[dmin / 2] |
, то для |
декодирования достаточно вычислить |
расстояния |
Хэмминга |
(т. е. число различных позиций) между принятым искаженным |
||
словом |
~ |
ивсеми возможными кодовыми словами y V и |
y |
||
принять решение о передаче того кодового слова, для которого это расстояние минимально. Однако число кодовых слов в коде с параметрами (n, k) равно 2k и при больших значениях k это число оказывается непереборно большим, т. е. такая процедура является практически нереализуемой.
y2 y j
y' |
yi |
y1 |
y2k |
|
Более того, в теории вычислительной сложности [9] доказывается утверждение, что если бы для любых ЛК был
найден полиномиально сложный алгоритм исправления ошибок по минимуму расстояния Хэмминга, то его можно было бы
использовать и для решения множества других трудных задач, которые до сих пор не имеют полиномиально сложных решений. Поэтому задача нахождения простого алгоритма декодирования для произвольных ЛК является весьмасложной.
Для того чтобы упростить процедуру исправления ошибок в задачах связи, используют подоптимальные алгоритмы
декодирования для подклассов ЛК (например, для так называемых кодов Гоппы, для которых сложность декодирования задается соотношением O(n2 ) [3]).
Особенность ЛК, выражающаяся в простоте кодирования и сложности декодирования, где последняя может быть преодолена при переходе к некоторым подклассам ЛК и используется для построения КС Мак-Элис.
Валерий
Денисович
Гоппа
Первым (1981) осознал связь между алгебраической геометрией и теорией кодирования.