Код Хэмминга

Наименование  и цель работы:

Код Хэмминга –  минимальное количество различий между  двумя допустимыми кодовыми словами.

      Кодом Хэмминга называется (n,k) – код, проверочная матрица которого имеет r n-k строк и столбцов, причем столбцами являются все различные ненулевые последовательности.

    Исправляющая способность кода Хэмминга определяется по следующему принципу: для обнаружения  ошибок d>r, для исправления ошибок d>2r.

     Схема Р.Хэмминга по конструированию кода , обнаруживающего и исправляющего одиночную ошибку, универсальна , т.к . код может быть построен для произвольной пары значений n и k, удовлетворяющих уравнению : .

     Заметим  также, что вовсе не обязательно,  чтобы набор из m информационных символов представлял собой код какой то определенной буквы. На практике сначала можно осуществить оптимальное или (близкое к оптимальному) кодирование текста. Затем уже закодированный текст можно делить на блоки по n двоичных символов в каждом , причем из возможных значений n (k = 3, 4,…), его конкретное значение следует выбирать исходя из эксплуатационной необходимости.

      Цель нашей работы : Произвести первичное кодирование и декодирование принятого сообщения, закодированного кодом Хэмминга. При этом осуществить обнаружение и исправление ошибок в кодовых словах, используя методику исправления с вычислением синдрома. 

Исходные данные для выполнения работы: 

 A= 6, Б = 111001101010, В = 101001100010.

Результаты  выполнения работы :

r = n-6

n = r +6

2^r     ≥  r     + 7 

  r = 4

 n,k

k  = 6

n = 4 + 6 = 10

   Отсюда, количество строк и столбцов в  проверочной матрице будет (10,6).

  Построим  проверочные матрицы кода в упорядоченном и модифицированном (с проверкой на чётность) виде:

  Матрица кода в упорядоченном виде:

H _(10,6) = 
 
 
 
 

  Матрица кода в  модифицированном (с проверкой  на чётность) виде:

H _(10,6) = 
 
 
 
 
 
 
 
 
 
 
 
 

Передадим сообщение 111001101010, для этого составим таблицу разбив сообщение на 2 части 111001 и 101010.

1) Оформим позицию  и значение бита:

 

Сформируем контрольную  сумму: сложение по mod 2 над кодами ненулевых битов:

10 = 1010

9 = 1001

7 =  0111

3  =  0011

         0101

Пусть данное слово  передано и получено принимающей  стороной. Определим позицию ошибки:

 

2)Оформим позицию  и значение бита:

 

Сформируем контрольную  сумму: сложение по mod 2 над кодами ненулевых битов:

10 = 1010

7  =  0111

5  =  0101

         1000

Пусть данное слово  передано и получено принимающей  стороной. Определим позицию ошибки:

       

       3) Сформируем системы проверочных и синдромных уравнений. Сформируем кодовое слово исследуемого кода, введём одиночную ошибку и покажем её исправление путём вычисление  синдрома, а также по схеме декодера в процессе работы.

   v = 111001101010 – переданное слово;

   v’ = 101001100010 – принятое слово; 

   Разделив  принятое сообщение на 2 части, составим таблицу 1:

 
 

   R1=k1+k2+k4  + K 5=1+0+1+1 = 1

   R2=k1+k3+k4  + K6 = 1+ 0+ 1+ 1 =1

        R3=k2+k3+k4=0+0+0=1

        R4 = k5 + k6 = 1 +1 = 0

   Синдромы:

   S1=  R1 + k1+k2+k4  + K 5=1+1+0+1+ 0 = 1

   S2= R2 + k1+k3+k4  + K6 = 1+ 1+ 0+ 1 + 1 =0

       S3 = R3+k2+k3+k4=1+0+0 + 11=0

       S4 = R4 + k5 + k6 = 0 + 0 +1 = 1

   Ошибка  в 9 позиции (1001). 

   Разделив  принятое сообщение на 2 части, составим таблицу 2:

 
 

   R1=k1+k2+k4  + K 5=0

   R2=k1+k3+k4  + K6 = 0

        R3=k2+k3+k4=0+0+0=0

        R4 = k5 + k6 = 1 +1 = 1

   Синдромы:

   S1=  R1 + k1+k2+k4  + K 5=1

   S2= R2 + k1+k3+k4  + K6 = 0

       S3 = R3+k2+k3+k4=0

       S4 = R4 + k5 + k6 = 0

   Ошибка  в 8 позиции (1000). 
 
 
 
 
 
 
 
 

   4) Переданное слово v_а = 111001101010, а принятое слово v’_a = 101001100010 тогда синдром будет следующим:

1001001111*                       = (1001) = 9

                                  0010

                                  0011

                                  0100

                                  0101

                                  0110

                                  0111

                                  1000

                                  1001

                                  1010

                                   
 

1010010000*                       = (1000) = 8

                                  0010

                                  0011

                                  0100

                                  0101

                                  0110

                                  0111

                                  1000

                                  1001

                                  1010

                                   
 
 
 
 
 
 
 
 
 
 

Вывод.

    Коды  Хемминга позволяют автоматически обнаруживать наиболее вероятные ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.