Коды с обнаружением и исправлением ошибок

Матричное описание порождающих кодов: Порождающая матрица

Порождающая матрица является сжатым описанием линейного кода. Двоичный линейный (100,50)-код, для описания которого требуется 100×50 = 5000 битов,

невозможно даже при использовании современных компьютеров.

Однако порождающая матрица не предоставляет возможности определить кодовое расстояние, а также разработать процедуры обнаружения и исправления ошибок.

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

понедельник, 3 июня 13 г.

Матричное описание порождающих кодов: Проверочная матрица

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

HG = 0

Матрица

порождает следующую систему уравнений:

понедельник, 3 июня 13 г.

Матричное описание порождающих кодов: Проверочная матрица

Основная матрица системы совпадает с матрицей G. Неизвестные x1 x2 и x3, для которых существует минор, не равный 0, можно объявить главными неизвестными. Тогда неизвестные x 4 и x5 являются свободными. Мы выбираем для них линейно независимые значения 01 и 10 и получаем системы уравнений:

Из первой системы получаем x 1= 1, x2 = 0, x3 = 1, т. е. решением исходной системы является вектор 10101. Из второй системы получаем x1= 1, x2 = 1, x3 = 0, т. е. вторым решением в фундаментальной системе решений является вектор 11010. Таким образом, получаем проверочную матрицу:

понедельник, 3 июня 13 г.

Матричное описание порождающих кодов: Проверочная матрица

Связь кодового расстояния линейного кода и проверочной матрицы устанавливается следующей теоремой:

Теорема. Каждое не нулевое кодовое слово имеет вес не менее w, тогда и только тогда, когда любая совокупность из w столбцов матрицы Н является линейно независимой.

Следствие. Расстояние линейного кода не менее w, если и только если любая совокупность из w-1 столбцов матрицы Н является линейно независимой.

Согласно сформулированным выше утверждениями, для того чтобы найти (п,k)-код, исправляющий t ошибок, достаточно построить матрицу Н размерности (п - k) × n, в

которой любые 2t столбцов линейно независимы.

понедельник, 3 июня 13 г.

Матричное описание порождающих кодов: Стандартное расположение

В качестве примера рассмотрим код V = {10111, 01101, 00000, 11010} с порождающей матрицей

.

В качестве примера рассмотрим код V = {10111, 01101, 00000, 11010} с порождающей матрицей

.

.

понедельник, 3 июня 13 г.