Определение числа добавочных разрядов r.

Линейные коды. Общие медоды построения.

Лекция 7

Рассмотрим класс помехоустойчивых алгебраических кодов, называемых линейными или часто линейными групповыми.

Определение: Линейными называют блоковые коды, дополнительные разряды которых образуются путем линейных операций над информационными разрядами.

Здесь используется понятие линейная операция. В теории кодирования в качестве линейной операции сложения используется сложение по модулю 2 (+).

Для определения числа добавочных разрядов можно воспользоваться уже нам известной формулой границы Хэмминга:

Если s=l, то есть строится код, исправляющий максимум однократные ошибки, то :

,

откуда получаем

2^r≥r+k

С учетом последней формулы ищется наименьшее r при котором удовлетворяется это неравенство.

Пример: n=7, тогда путем простого перебора легко найти, что r=3. И соответствующий код имеет вид n(7,4).

7.3 Построение образующей(порождающей) матрицы |OM|.

Линейные коды обладают следующим свойством:

- из всего множества 2^k разрешенных кодовых слов, образующих линейную группу, можно выделить подмножества из k слов, обладающих свойством линейной независимости.

Линейная независимость означает, что никакое из слов, входящих в подмножество линейно-независимых кодовых слов, нельзя получить путем суммирования (с помощью линейного выражения) любых других слов, входящих в это подмножество.

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

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

Для образования n -разрядных кодовых слов из k- разрядных кодируемых слов (кодирования) используют матрицу, которая называется образующей(порождающей).

Образующая матрица получается путем записи в столбец k линейно-независимых слов.

Обозначим кодируемую информационную последовательность X и будем записывать ее в виде матрицы-строки ||X|| размерностью 1*k, например:

||X||=||11001||, где k=5.

Один из способов построения образующей (порождающей) матрицы следующий: Она строится из единичной матрицы ||I||размерностью k*k и приписанной к ней справа матрицы добавочных (избыточных) разрядов ||МДР|| размерности k*r.

где при k=4

Такая структура ОМ обеспечивает получение систематического кода.

Порядок построения матрицы МДР будет рассмотрен ниже.