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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

«ХПІ»

Кафедра “Обчислювальна техніка та програмування”

ЗВІТ

З лабораторних робіт

з курсу «Теорія інформації та кодування»

                          Виконав:

                          Ст. гр КIТЗI - 12  

                          Перевірив:

                          доц. Грінченко О.Г.

Ізюм 2005

Лабораторная работа №1

Линейный групповой код

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

    Задание:

   1. Построить линейный групповой код способный передавать сообщения в виде последовательности 16-ричных цифр первичного алфавита с исправлением одиночной ошибки. Показать процесс кодирования, декодирования и исправления однократной ошибки для произвольно выбранного  информационного слова (например, 1010).

   2. Составить программу,  реализующую процесс кодирования, декодирования и исправления однократной ошибки с использованием линейного группового кода.

Порядок выполнения работы

1. Построение линейного группового кода

      Решение:

    1. Выполним первичное кодирование, т. е. определим информационное  слово для каждого символа первичного алфавита. Число информационных разрядов k для заданного объема кода можно определить из соотношения N = 16= 2^k = 2⁴

    Строим первичный код. При этом старшинство разрядов принимаем слева на право, в соответствии с их поступлением на вход кодера.

                                                ‘0’ => 0000         ‘4’ => 0010        ‘8’ => 0001        ‘C’ =>0011

                                                ‘1’ => 1000          ‘5‘=>1010         ‘9’  =>1001        ‘D’ =>1011

                                                ‘2’ => 0100          ‘6’ =>0110         ‘A’ => 0101       ‘E’ =>0111

                                                ‘3’ => 1100          ‘7’ =>1110         ‘B’ =>1101        ‘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.  Строим образующую (производящую, порождающую) матрицу

.

     где:    I_kk - информационная матрица, которая представляет  единичную матрицу ранга k;   R_km, проверочная матрица, каждая строка которой содержит число единиц больше или равно двум (r₁ £  d₀-1).

   Таким образом, в качестве производящей можно принять  одну из матриц

 и т.д.

  4. Процесс кодирования состоит во взаимно - однозначном соответствии k-разрядных информационных слов - I и n-разрядных  кодовых слов - с             

                                                      c=IG

        Например: информационному слову I=[ 0 1 0 1] соответствует следующее кодовое слово

      Аналогично получим все остальные кодовые комбинации

  5. Процесс декодирования состоит в определении соответствия принятого кодового слова, переданному информационному слову и осуществляется с помощью проверочной матрицы H(7, 4).   Для построенного (7, 4)- кода проверочная матрица имеет вид

.

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

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

                               F = 0 1 0 1  1 1 0

                              F¹ = 0 1 1 1  1 1 0

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

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

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

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

2. Программа реализации линейного группового кода

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

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

  uses crt;

  const  n=7;              {Длина кодовой комбинации}

             k=4;              {Длина кодового слова}