Кодирование с использованием линейного группового кода, страница 4

           ‘1’ => 0001         ‘5‘ => 0101         ‘9’  =>1001        ‘D’ => 1101

           ‘2’ => 0010         ‘6’ => 0110         ‘A’ => 1010       ‘E’ => 1110

           ‘3’ => 0011         ‘7’ => 0111         ‘B’ => 1011        ‘F’ => 1111

     2. Определим основные параметры кода: количество контрольных бит –m  и длину кодовой комбинации – n по числу информационных бит (k = 4) и количеству исправляемых ошибок (S=1,d_o=3)

m=[log₂ {(k+1)+ [log₂(k+1)]}]=[log₂ {(4+1)+ [log₂(4+1)]}]=3.

      Длина кодовой комбинации равна n = k + m = 4 +3 = 7. При этом получили (7,4) – код.

  3. Определим структуру кодовой комбинации, а так же расположение и значение информационных  и контрольных бит в  кодовой комбинации.

      Номера  контрольных бит определяются  по закону 2ⁱ,  где i=1, 2, 3,...  т.е. они равны 1, 2, 4, 8, 16,… а остальные биты являются информационными.

                                   1       2        3     4      5     6       7

k1

k1

a1

k1

a2

a3

a4

     Значения контрольных разрядов (0 или 1) определим при помощи проверок составленных на основании проверочной матрицы H(7,4), столбцы которой представляют запись в двоичной системе всех целых чисел от 1 до  n. Для m = 3 проверочная матрица имеет вид

                                        .                          

    Количество разрядов m - определяет количество проверок.

                    k₃ Å a₂Å a₃Å a₄ =0;    k₃ = a₂Å a₃Å a₄ =0 Å 1 Å 0  = 1;

                    k₂ Å a₁Å a₃Å a₄ = 0;   k₂ = a₁Å a₃Å a₄ =1 Å 1 Å 0 = 0;

                    k₁Å a₁Å a₂Å a₄ = 0;   k₁ = a₁Å a₂Å a₄ =1 Å 0 Å 0  = 1.

    6. Пусть F переданная кодовая комбинация, а F¹ принятая, т. е. в третьем бите произошла ошибка

                              F  = 1 0 1 1 0 1 0

                              F¹ = 1 0 0 1 0 1 0

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

      Синдром  011 показывает, что ошибка произошла в 3-м информационном разряде, который необходимо проинвертировать.

      Отбросив контрольные биты, получим исходное информационное слово 

                                               I = [0101] => 1010 => ‘A’.

Схема кодера и декодера

 

                                 

Рис. 1. Схема кодера -а и декодера –б для простого (7, 4)    кода Хэмминга

     Применение кода Хэмминга. Код Хэмминга используется как при параллельной, так и при последовательной записи.  В ЭВМ код Хэмминга чаще всего используется для обнаружения и исправления ошибок в ОП, памяти с обнаружением и исправлением ошибок ECC Memory (Error Checking and Correcting).

2. Программа реализации  кода Хэмминга

{   Построить код Хэмминга,  используя его матричное представление, для передачи данных, представляющих последовательность десятичных цифр, каждая из которых кодируется 4-х значным  двоичным кодом. Показать процесс обнаружения и исправления одиночной ошибки в передаваемой кодовой комбинации. Составить программу,  реализующую алгоритм кодирования, декодирования и исправления ошибки при передаче данных с использованием кода Хэмминга.}

program chem7_4;           {Программа реализации линейного группового кода}

 uses crt;

 const n=7; k=4; m=3;

       H : array[1..m,1..n] of byte=((0,0,0,1,1,1,1),

                                                     (0,1,1,0,0,1,1),

                                                    (1,0,1,0,1,0,1));

 type vec =array[1..n] of byte;