Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

1.2. Матричное описание линейных блоковых кодов

1.2.1. Порождающая матрица линейного кода

Пусть VÍBn - линейный (n,k) - код. Код можно задать, перечислив все кодовые слова. Однако, при больших n и k порядка сотен или тысяч представление оказывается слишком громоздким. Так как V является подпространством линейного пространства, то для задания линейного кода достаточно задать его базис. В этом случае линейный код задается как пространство строк порождающей матрицы.

Матрица G состоящая из всех базисных векторов линейного кода V называется порождающей матрицей кода V. Строки матрицы G линейно независимы, и число k строк равно размерности кода. Таким образом, порождающая матрица (n,k) - кода имеет размерность k×n.  .

В качестве примера рассмотрим порождающую матрицу:

Соответствующий (5,3) - код V = {00000, 10011, 11001, 11100, 01010, 01111, 00101, 10110} содержит 23 = 8 кодовых слов.

Чтобы закодировать информационное слово, достаточно найти соответствующую линейную комбинацию вектор-строк порождающей матрицы. Иными словами, если i = a1 ...ak - информационное слово, то соответствующее кодовое слово c = iGT, где GT используется для обозначения транспонированной матрицы G.

Например, информационное слово i=(0 1 1) будет преобразовано в кодовое слово равно c = 0 × 1 0 0 1 1 + 1 × 1 1 0 0 1 + 1 × 1 1 1 0 0 = 0 0 1 0 1, если для кодирования используется порождающая матрица G, приведенная выше.

Так как множество базисных векторов линейного пространства можно выбрать различными способами, то для одного и того же кода существуют различные порождающие матрицы. Соответственно выбор кодового слова для каждого информационного набора зависит от выбора порождающей матрицы. Например, если в качестве порождающей матрицы кода V = {00000, 10011, 11001, 11100, 01010, 01111, 00101, 10110} выбрать другую матрицу:

,

то информационное слово i = (0 1 1) будет преобразовано в кодовое слово равно c = 0 × 0 1 1 1 1 + 1 × 0 0 1 0 1 + 1 × 1 0 1 1 0 =  1 0 0 1 1.

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