Методические указания к лабораторным работам по курсу "Дискретная математика". Домашова Д.В - 18 стр.

       Назначение проверочной матрицы – выделить из множества всех слов
длиной и кодовые слова., т.к. вектор а∈GF(2n) –кодовое слово    когда аНt=0
(Ht – транспонированная матрица Н) получаем (n-k) уравнений, которым долж-
ны удовлетворять координаты кодового слова а. Эти уравнения называются
проверочными:
      n

      ∑a h
      j =1
             j   ij
                      = 0 , a = (a1 ,..., a n ) , Н=||hij||,   i = 1, n − k   j = 1, n

      Порождающая матрица G и транспонированная проверочная матрица
связаны между собой следующим образом: GHt=HGt=0
      Свойства линейных кодов:
      – т.к. d(a,b)= ω(a+b)
        V-лин. => ∀a,b∈V и (a+b)∈V => d (V ) = min ω (a) - для нахождения d(V)
                                               a∈V

      достаточно |V| сравнений.
      – корректирующая способность линейных кодов определяется числом
линейно независимых столбцов проверочной матрицы.
   Если любые (d-1) столбцов матрицы Н линейно независимы => кодовое рас-
   стояние кода V не меньше чем d.
      Два кода называются эквивалентными, если существует такая перенуме-
рация координат, которое множество первого кода переводит в множество вто-
рого кода. Эквивалентные коды обладают одинаковыми корректирующими
свойствами.
      За счет выбора образующих элементов и перенумерации координат
порождающую матрицу линейного кода можно привести к каноническому
виду: [I:P], где I – в первых столбцах единичная матрица (k × k)
              P- k × (n-k) матрица
      Если порождающая матрица в каноническом виде, первые k координат
кодового вектора являются информационными, остальные (n-k) - проверочны-
ми.
      В линейных кодах каждый проверочный символ βj есть линейная комби-
нация информационного аi.
      Если используется линейный двоичный код, то любая линейная комбина-
ция информационных символов есть их сумма по модулю два.
      Если G=[IkP], Ik – единичная матрица k × k, P(k × (n-k)) =>H=[PTIn-k]

                                   3.7 Декодирование линейного кода

      При передаче информации по каналу с ошибками кодирование линейным
кодом может быть осуществлено по методу “минимум расстояния” Но, при
этом осуществляется большое число сравнений (все кодовые слова сравнива-
ются с принятым словом Y).
      Декодирование может быть осуществлено по синдрому (проверочному
вектору) это декодирование эквивалентно (можно доказать).
      В этом случае удобно для кодирования и декодирования задавать линей-
ный код с помощью проверочной матрицы H. Множество всех принятых слов
состоит из слов длинной n над алфавитом из поля GF(2)
                                                                                         21