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

Страницы работы

Фрагмент текста работы

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

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

                                                                                  

                         1000   ..…  0  e11  e12   ….. e k

M n x m  =      0100   ..…  0  e21  e22   ….. e k

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

0000  ..…  1 em1 em2  ….. e mk

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

граница Хэмминга      k >=  log 2 ( 1 +           ∑           c in   )       

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

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

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

1

k >=  log 2 ( 1 + ∑ c 1n   )   ,     k >=  log 2 ( 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 выглядит так :

e1  =  e11 а+  e21 а2  + …..+  e m1 аm

e2  =  e12 а+  e22 а2  + …..+  e m2 аm

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

ek  =  e1k а+  e2k а2  + …..+  e mk аm

 

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

 


  e11  e21   ….. em1  100 ……0

H n x k  = [D m,k ; Ek ]      e12  e22   ….. em2  010 …….0

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

e1k e2k  ….. emk    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                           

 

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

e1  = a1 + a2 + a3  

e2  = a1 + a2 + a4  

e3  = a1 + a3 + a4  

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

a1  a2  a3  a4  e1 e2 e3

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

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                      S1 = e1 + e1 /

H 7,3 =     1   0   1   1  0   1   0                  S2 = e2 + e2 /

1   1   0   1   0   0   1                      S2 = e3 + e3 /

a1  a2  a3  a4  e1 e2 e3

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

e1 /  = a2 + a3 + a4  

e2 /  = a1 + a3 + a4  

e3 /  = a1 + a2 + a4  

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

a1  a2  a3  a4  e1 e2 e3

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

a1  a2  a3  a4  e1 e2 e3

 


S1 = 1+0 = 1                                                           0111   100          

S2 = 1+1 = 0                                                           1011   010

S3 = 0+0 = 0        S =    1   0   0                             1101    001

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

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

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

S1 = 0+0 = 0

S2 = 0+1 = 1                                                           

S3 = 0+1 = 1     

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

2>=  n-1 

2k+1  >=  n

k  >= Cn1

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

Для  всех разрядов  2k  + 1>=  Cn1 + Cn2  + …. + Cne

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

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

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

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

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

Похожие материалы

Информация о работе