BC/NW 2008, №1 (12): 5.4

 

 

 

 

формированиЕ проверочных матриц
произвольных блоковых корректирующих кодов

 

Н. М. Охотникова, А. Ю. Чернышев

 

(Москва, Московский энергетический институт(технический университет), Россия)

 

 

 

 

В цифровых системах передачи информации с целью обнаружения и исправления ошибок широко применяются блоковые корректирующие коды. Наиболее эффективным считается их синдромное декодирование при помощи проверочных матриц [1, 2].

В литературе [1, 2] рассмотрены подходы к формированию проверочных матриц только для систематических кодов вида  или , где b – входное информационное слово, p – блок проверочных символов. Их порождающие матрицы соответственно имеют каноническую форму  или , где I – единичная подматрица,  P – подматрица формирования проверочных символов. Проверочная матрица имеет соответственно вид  или . Вычисление синдрома производится перемножением принятого кодового слова y  на матрицу H в поле GF2, причем

, mÎ[1; N-K],                                                                       (1)
где N – длина кодовых слов x и y, K – длина информационного слова b.

Анализ выражения (1) с учетом структуры матриц G и H приводит к выводу, что при отсутствии ошибок, т.е. при y=x, справедливо тождество

, mÎ[1; N-K],                                    (2)
где pkm – элементы подматрицы P. Первая сумма в выражении (2) обусловлена прямой трансляцией вектора b в слово x, а затем его перемножением на подматрицу P матрицы H. Вторая сумма – результат перемножения вектора b на подматрицу P матрицы G и последующей трансляции из слова x через подматрицу I матрицы H. Таким образом, при отсутствии ошибок синдром равен нулю.

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

а) в матрице G выделить K столбцов с единичными весами Хэмминга, свести их номера в множество Q;

б) оставшиеся столбцы объединить в матрицу P;

в) в строки матрицы H с номерами из множества Q поместить соответствующие строки матрицы P;

г) оставшиеся строки матрицы H заполнить строками распределенной единичной матрицы.

Вывод: получен и проверен обобщенный алгоритм формирования проверочных матриц для определенного класса блоковых корректирующих кодов.

 

ЛИТЕРАТУРА

1. Теория электрической связи: Учебник для вузов / А. Г. Зюко, Д. Д. Кловский, В. И. Коржик, М. В. Назаров; Под ред. Д. Д. Кловского. – М.: Радио и связь, 1998.

2. Вернер, М. Основы кодирования / Пер. с англ. – М.: Техносфера, 2004.