Учебные вопросы занятия.

Лекция 8 Основы матричного построения кодов

ЛЕКЦИЯ

Защиты информации

по учебной дисциплине "Теория информации "

для студентов специальности 075500 (090105) – Комплексное обеспечение информационной безопасности автоматизированных систем

Ставрополь 2009 г.

Цель занятия: Изучить общие принципы и методы построения систематических кодовых конструкций. Ознакомиться с корректирующими кодами Хемминга.

1. Построение порождающей и проверочной матриц систематического кода

2. Коды Хэмминга

1. Построение порождающей и проверочной матриц систематического кода.

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

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

1. В число этих к.к не должна входить нулевая к.к.

2. Кодовое расстояние между двумя любыми парами больше либо равно d(min)

3. Каждая исходная комбинация должна содержать количество единиц больше либо равно d(min), т.е. вес ее должен быть равным либо превышать d(min).

4. Все исходные к.к должны быть линейно независимы (ни одна из них не должна представлять сумму других к.к)

Исходную к.к можно получить из матрицы, которая содержит k строк и n столбцов.

k первых столбцов являются информационными ;

r последних - проверочные символы;

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

· Информационной

· Проверочной

Для построения порождающей матрицы информационную матрицу удобно представить в виде единичной матрицы (единицы по диагонали). Тогда проверочная матрица должна строиться с соблюдением следующих условий:

1. Количество единиц строки должно быть больше либо равно d(min) - 1.

2. Сумма по модулю два любых двух комбинаций (строк) должна содержать не менее d(min) - 2 единиц.

Проверочные символы образуются за счет линейных операций над информационными символами. Для каждой к.к. должной быть построено r независимых сумм по модулю два. Выбор информационных символов участвующих в получении проверочных символов зависит от способов декодирования кода. Весьма удобно проверочные суммы составлять с помощью проверочной матрицы, строящейся следующим образом:

1. В начале строится матрица H(r).

2. Затем снизу дописывается единичная матрица.

Произведение порождающей матрицы на проверочную равно нулю.

P(n,k)* H^*(r) = 0

Совокупность комбинаций линейного кода - есть множество разрешенных последовательностей Bi для которых произведение Bi* H^*(r) = 0, где Bi матрица строка.

Алгоритм определения проверочных символов следующий:

1. Позиции, занимаемые в первом столбце должны участвовать в формировании первого проверочного символа.

2. Единицы во втором столбце участвуют в формировании второго проверочного символа.

3. И т.д.

Пример: построить порождающую и проверочные матрицы для кода (7,4).

d(min) = 3

B1 = A2+A3+A4

B2 = A1+A3+A4

B3 = A1+A2+A4