Избыточные коды

Страница: 3/8

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

где I- единичная kXk подматрица, P-kX(n-k)- подматрица проверочных символов, определяющая свойства кода. Матрица задает систематический код. Можно показать, что для лю­бого линейного кода существует эквивалентный систематический код.

Линейный (п, k) код может быть задан про­верочной матрицей Н размерности (rХп). При этом комбинация В принадлежит коду только в том случае, если вектор В ортого­нален всем строкам матрицы Н, т. е. если выполняется равенство (7.9)

где т—символ транспонирования матрицы. Так как это равенство справедливо для любой кодовой комбинации, то

Каноническая форма матрицы Н имеет вид (7.10)

где P - подматрица, столбцами которой служат строки подмат­рицы Р (7.8), I-единичная rXr подматрица. Подставляя (7.10) в (7.9), можно получать п—k уравнений вида (7.11)

которые называются уравнениями проверки. Из (7.11) следует, что проверочные символы кодовых комбинаций линейного кода образуются различными линейными комбинациями информаци­онных символов. Единицы в любой j-й строке подматрицы Р, входящей в проверочную матрицу (7.10), указывают, какие информационные символы участвуют в формировании j-го провероч­ного символа.

Очевидно, что линейный (п, k) код можно построить, исполь­зуя уравнения проверки (7.11). При этом первые k символов ко­довой комбинации информационные, а остальные п-k симво­лов - проверочные, образуемые в соответствии с (7.11).

С помощью проверочной матрицы сравнительно легко можно построить код с заданным кодовым расстоянием. Это построение основано на следующей теореме: кодовое расстояние линей­ного (п, k) кода равно d тогда и только тогда, когда любые d-1 столбцов проверочной матрицы этого кода линейно независимы, но некоторые d столбцов проверочной матрицы линейно зависимы.

Заметим, что строки проверочной матрицы линейно независи­мые. Поэтому проверочную матрицу можно использовать в ка­честве порождающей для некоторого другого линейного кода (п, п-k), называемого двойственным.

Кодирующее устройство для линейного (п,k) кода (рис. на предыдущей стр.) состоит из k-разрядного сдвигающего регистра и r=п-k бло­ков сумматоров по модулю 2. Информационные символы одно­временно поступают на вход регистра и на выход кодирующего устройства через коммутатор К. С поступлением k-го информаци­онного символа на выходах блоков сумматоров в соответствии с уравнениями (7.11) формируются проверочные символы, которые затем последовательно поступают на выход кодера. Процесс декодирования сводится к выполнению операции

Реферат опубликован: 27/03/2007