Помехоустойчивые коды (корректирующие, избыточные). Блочные линейные коды. Матричная запись циклических кодов

Минимальное кодовое расстояние в  С k x m  должно быть не менее  d min – 2

Таким образом порождающая матрица имеет вид

                                                                                  

                         1000   ..…  0  e₁₁  e_{12   …..} e _k

M n x m  =      0100   ..…  0  e₂₁  e_{22   …..} e _k

………………………………                 

0000  ..…  1 e_m1 e_{m2  …..} e _mk

Пример :  Используя для расчета  k  границу Хэмминга построить порождающую матрицу для кода способного исправлять одиночную ошибку ( t = 1 )  при передаче   N =16 сообщений для N=16  m = 4   N = 2^m                    (d min -1 )/ 2

граница Хэмминга      k >=  log ₂ ( 1 +           ∑           c ⁱ_n   )       

i=1 для обнаружения  t ошибок  d min >= t + 1

для исправления  t ошибок  d min >= 2 t + 1

У нас d min >= 2*1 +1 = 3

1

k >=  log ₂ ( 1 + ∑ c ¹_n   )   ,     k >=  log ₂ ( 1 + n )    ,     k  =  3

1                   

 

1000   101                           1000  111

M _7,4  =        0100  011            или         0100  110            или   и т.д.

0010  110                           0010  011

0001  111                           0001  101 

Алгоритм образования значений контрольных разрядов кодовой комбинации по информационной части  с помощью матрицы M n x m выглядит так :

e₁  =  e₁₁ а₁  +  e₂₁ а₂  + _…..+  e _m1 а_m

e₂  =  e₁₂ а₁  +  e₂₂ а₂  + _…..+  e _m2 а_m

………………………………………

e_k  =  e_1k а₁  +  e_2k а₂  + _…..+  e _mk а_m

 

Гораздо удобнее проверочные уравнения  выполнить с помощью матрицы , состоящей из k строк  и m столбцов. Получим ее : сначала строится  единичная матрица Е k,k . К ней приписывается D m,k , содержащая m столбцов и k строк, причем каждая ее строка соответствует столбцу контрольных разрядов подматрицы  С k,m  , порождающей матрицы, другими словами  D k,m является транспонированной по отношению к С k,m.

 

  e₁₁  e_{21   …..} e_m1  100 ……0

H n x k  = [D m,k ; E_k ]      e₁₂  e_{22   …..} e_m2  010 …….0

………………………………                  

e_1k e_{2k  …..} e_mk    000  ..…  1

С помощью этой матрицы операция кодирования  осуществляется очень просто : позиции занимаемые единицами  в i – ой  строке  подматрицы D m,k  определяют те информационные разряды, которые должны участвовать в формировании контрольного разряда

Пример : Построить проверочную матрицу H кода 7,4 , порождающая матрица которого имеет вид :

 

                     1000   111                                 1110                               1110100

M _7,4  =        0100  110             D _4,3 =         1101             H _7,3 =     1101010  

0010  101                                 1011                               1011001

0001  011                           

 

Для расчета  контрольных разрядов при кодировании по этой матрице получают следующие контрольные соотношения

e₁  = a₁ + a₂ + a₃  

e₂  = a₁ + a₂ + a₄  

e₃  = a₁ + a₃ + a₄  

Закодируем  1    0   1   0    0  1  0

a₁  a₂  a₃  a₄  e₁ e₂ e₃

На основании матричного представления кодов можно сделать следующие выводы :

1)  С помощью порождающей матрицы M _{m x n}  можно представить весь набор кодовых комбинаций в удобной и компактной форме и довольно просто провести операцию кодирования.

2)  Проверочную матрицу   H _{m x k}  обычно используют при построении кодирующих и декодирующих  устройств, т.к. она определяет алгоритм нахождения  проверочных разрядов по информационным значениям. Кроме того данная очень удобна для указания места отсечки в кодовой комбинации

Метод исправления ошибок в линейных кодах. Понятие синдрома.

Обычно при декодировании информации используются проверочные соотношения полученные  по проверочной матрице H _{m x k} . При этом вычисляется синдром (контрольное число). Синдром рассчитывается как сумма по модулю 2 принятых контрольных разрядов и контрольных разрядов, вычисленных по принятым информационным. Характерной особенностью синдрома является то, что он независим от передаваемой кодовой комбинации, а зависит только от характера ошибок.

Пример : Задана проверочная матрицаH _{7 x 3}

0   1   1   1   1   0   0                      S₁ = e₁ + e₁ ^/

H _7,3 =     1   0   1   1  0   1   0                  S₂ = e₂ + e₂ ^/

1   1   0   1   0   0   1                      S₂ = e₃ + e₃ ^/

a₁  a₂  a₃  a₄  e₁ e₂ e₃

e₁ ^/ - контрольный разряд, вычисленный по принятым информационным

e₁ ^/  = a₂ + a₃ + a₄  

e₂ ^/  = a₁ + a₃ + a₄  

e₃ ^/  = a₁ + a₂ + a₄  

Возьмем  А =  1   0   1   1    0  1  0

a₁  a₂  a₃  a₄  e₁ e₂ e₃

Пришедшее число  1   0   1   1    1  1  0

a₁  a₂  a₃  a₄  e₁ e₂ e₃

 

S₁ = 1+0 = 1                                                           0111   100          

S₂ = 1+1 = 0                                                           1011   010

S₃ = 0+0 = 0        S =    1   0   0                             1101    001

(в этом разряде ошибка)   

Покажем, что синдром  не зависит  от вида передаваемой информации, а зависит только от  возникающих ошибок. Предположим произошла ошибка в информационном разряде  a_1.

 Составим  последовательность ошибок  1000  000

S₁ = 0+0 = 0

S₂ = 0+1 = 1                                                           

S₃ = 0+1 = 1     

Количество разрядов синдрома  для обнаружения одиночной ошибки определяется следующим выражением :

2^k  >=  n-1 

2^k+1  >=  n

k  >= C_n¹

Для  исправления одиночных и двоичных ошибок    2^k  + 1>=  C_n¹ + C_n²

Для  всех разрядов  2^k  + 1>=  C_n¹ + C_n²  + …. + C_n^e

Код с простым повторением

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

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

Инверсный код

Одной из разновидностей кода с простым повторением  является инверсный код. В этом коде, если  передаваемая информационная часть  содержит четное число  единиц