Возможности построения кодов с исправлением ошибок

 

Как уже упоминалось, s – кратная ошибка принципиально может быть исправлена, если d ≥ 2 s + 1. Существуют два метода построения кодов с исправлением ошибок:

1) группировка кодов спутников;

2) проверка на четность в определенных разрядах разделимого систематического кода (построение опознавателей ошибок).

Коды-спутники формируются путем суммирования по модулю 2 рабочих кодовых комбинаций с векторами возможных ошибок кратности ≤ s . При этом любая кодовая комбинация кодов-спутников может рассматриваться как рабочая, а следовательно, ошибки кратности ≤ s исправляются.

Пусть, например s = 1, следовательно, d_min = 3. Рабочие кодовые комбинации:

                V ₁ = 01001, V ₂ = 01110, V ₃ = 10010 .

Возможные векторы однократных ошибок: 00001, 00010, 00100, 01000, 10000. Тогда кодовые комбинации кодов-спутников, воспринимаемые соответственно как рабочие кодовые комбинации V ₁ , V ₂ , V ₃ , имеют вид:

V ₁ = 01001    V ₂ = 01110     V ₃ = 10010

       01000                01111             10011

       01011                 01100             10000

       01101                01010             10110

       00001                00110             11010

       11001                11110             00010

 

В разделимых систематических кодах все символы разделяются на информационные n _и и проверочные (защитные) n _з , т.е.

                                  n = n _и + n _з .                                  ( 10 )

Значения проверочных символов находятся по определенной системе.

Сокращенно разделимые систематические коды обозначаются ( n , n _и ) , т.е. в скобках указывается суммарное число символов в кодовой комбинации и число информационных символов.

Значение проверочных символов определяется как сумма по модулю определенных информационных символов. Количество проверочных символов совпадает с количеством проверок на четность и должно быть таким, чтобы можно было найти номер искаженного символа ( как информационного, так и проверочного). Значение номера искаженного символа позволяет восстановить исходную кодовую комбинацию. Таким образом, в результате проверок должен формироваться код-опознаватель, указывающий номер искаженного символа.

 

                                   Код Хэмминга         

 

Этот разделимый систематический код, например, ( 7,4 ), т.е. n = 7, n _и = 4, n _з = 3. Любой из семи символов кода может быть искажен. В табл. 11 даны номера разрядов кодовой комбинации кода Хэмминга и вектора кода-опознавателя, которые указывают номер разряда, символ в котором искажен. 

                                                                                       Таблица 11

№ разряда кода Хэмминга	1	2	3	4	5	6	7
Вектор кода-опознавателя	001	010	011	100	101	110	111

 

Проверки на четность (их число равно n _з , т.е. 3) должны сформировать вектор кода-опознавателя, указывающего номер искаженного разряда. Из табл. 11 ясно, что «1» в первом разряде вектора кода-опознавателя должна иметь место, если искажены символы в разрядах 1, 3, 5 или 7; «1» во втором разряде вектора опознавателя – при искажении разрядов 2, 3, 6 или 7; и «1» в третьем разряде опознавателя – при искажении разрядов 4, 5, 6 или 7 в кодовой комбинации кода Хэмминга, т.е.:

                                                                 ( 11 )

где u_i – содержимое i-го разряда кода Хэмминга. Проверочные разряды должны входить в условия ( 11 ) по одному разу, т.е. проверочным и являются разряды 1, 2 и 4. Их содержимое определяется из условий 

( 11 ), т.е.:

                                                                       ( 12 )

Пусть, например, передаваемое сообщение – двоичное число 1011, тогда содержимое информационных разрядов соответствующей кодовой комбинации кода Хэмминга: u ₃ = 1, u ₅ = 1, u ₆ = 0, u ₇ = 1, а содержимое проверочных разрядов согласно ( 12 ): u ₁ = 1, u ₂ = 0, u ₄ = 0, т.е. кодовая комбинация имеет вид 1010101.

 

                                        Циклический код

 

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

Циклический код, как и код Хэмминга, представляет собой разделимый систематический код, причем информационные символы занимают старшие, а проверочные символы – младшие разряды кодовой комбинации.

Запись кодовой комбинации циклического кода может быть представлена в виде полинома от х , например,

        F(x) = a_n-1·x^n-1 + a_n-2·x^n-2 + …+ a_i·xⁱ + … + a ₁ · x + a_o , ( 13 )

где n - число разрядов кода, a_i , (1 или 0) – разрядные коэффициенты. Например, кодовая комбинация 01001 может быть записана, как F ( x ) = x ³ + 1.

Циклический код характеризуется образующим (порождающим) полиномом Р(х) степени К = n _з = n – n _и . Вид Р(х) и его степень определяют корректирующую способность кода. Все рабочие комбинации циклического кода делятся на Р(х) без остатка. При делении на Р(х) запрещенной кодовой комбинации обязательно имеется остаток. По виду остатка возможна корректировка принятого сообщения.

Циклический код может быть образован путем умножения полинома Q ( x ) степени (n _и - 1), соответствующего кодовой комбинации двоичного безызбыточного кода с числом разрядов n _и , на образующий полином Р( x )  степени К, т.е.

                                    F ( x ) = Q ( x ) × P ( x )  .                     ( 14 )

Однако при таком способе получения кодовой комбинации циклического кода информационные и проверочные разряды оказываются неразделенными друг от друга, что затрудняет процесс декодирования (т.е. код оказывается неразделимым). Поэтому используется другой способ формирования кодовых комбинаций циклического кода. Полином Q ( x ) умножается на одночлен x^k , а затем делится на образующий полином Р( x ) :

                                                 .                     ( 15 )

Четное С( x ) имеет ту же степень, что и Q ( x ) (т.е. n _и - 1). Если Q ( x )· x^k не делится на Р( x ) нацело, появляется остаток, т.е.

                                           .                ( 16 )

Поскольку С( x ) имеет ту же степень, что и Q ( x ) , то оно является кодовой комбинацией исходного безизбыточного кода.

Степень остатка R ( x ) не может быть больше степени Р( x ) . Наивысшая степень R ( x ) есть (К – 1), следовательно, R ( x ) имеет число разрядов не более К.

Умножая обе части равенства ( 16 ) на Р( x ) и группируя члены произведения, можно получить следующее выражение для кодовой комбинации циклического кода, т.е.

                            .             ( 17 )

При таком способе формирования циклического кода информационные символы занимают в кодовой комбинации n _и старших разрядов, а проверочные

К = n _з младших разрядов.

Рассмотрим пример формирования циклического кода. Пусть

Q ( x ) = x ³ + x + 1 , P ( x ) = x ³ + x ² + l . При этом n _и = 4, К= n _з = 3, т.е. имеет место код (7,4). При записи в форме двоичного числа Q(1,0) = 1011; Р(1,0) = 1101. Найдем остаток от деления Q ( x )·х ^k на P ( x ), т.е.

                                .

Кодовая комбинация циклического кода имеет вид:

  .

 

⇐ Предыдущая123456Следующая ⇒

Поделиться: