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

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

ЛЕКЦИЯ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P(n,k)=	А11	А12	...	А1k	B11	B12	...	B1r
A21	A22	...	A2k	B21	B22	...	B2r
...	...	...	...	...	...	...	...
Ak1	Ak2	...	Akk	Bk1	Bk2	...	Bkr

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

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

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

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

U(k) =	А11	А12	...	А1k
...	...	...	...
Ak1	Ak2	...	Akk

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

H(r) =	B11	B12	...	B1r
...	...	...	...
Bk1	Bk2	...	Bkr

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

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

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

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

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

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

H^*(r) =	B11	B12	...	B1r
...	...	...	...
Bk1	Bk2	...	Bkr
		...
		...
...	...	...	...
		...

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

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

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

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

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

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

3. И т.д.

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

P(7,4)=

d(min) = 3

H^*(r) =	B1	B2	B3
			A1
			A2
			A3
			A4
			B1
			B2
			B3

B1 = A2+A3+A4

B2 = A1+A3+A4

B3 = A1+A2+A4

Дата добавления: 2014-01-13