Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Матрица генератора

При больших k реализация таблицы соответствия кодера становится слишком громоздкой. Для кода (127,92) существует 2⁹² или приблизительно 5 х 10²⁷ кодовых векторов. Если кодирование выполняется с помощью простой таблицы соответствия, то представьте, какое количество памяти нужно для такого огромного числа кодовых слов! К счастью, задачу можно значительно упростить, по мере необходимости генерируя необходимые кодовые слова, вместо того чтобы хранить их в памяти постоянно. Поскольку множество кодовых слов, составляющих линейный блочный код, является k-мерным подпространством n-мерного двоичного векторного пространства (k < n), всегда можно найти такое множество n-кортежей (с числом элементов, меньшим 2^k), которое может генерировать все 2^k кодовых слова подпространства. О генерирующем множестве векторов говорят, что оно охватывает подпространство. Наименьшее линейно независимое множество, охватывающее подпространство, называется базисом подпространства, а число векторов в этом базисном множестве является размерностью подпространства. Любое базисное множество k линейно независимых n-кортежей можно использовать для генерации нужных векторов линейного блочного кода, поскольку каждый вектор кода является линейной комбинацией . Иными словами, каждое из множества 2^k кодовых слов {U} можно представить следующим образом.

Здесь = (0 или 1) — цифры сообщения, a i = 1,..., k.

Вообще, матрицу генератора можно определить как массив размером k x n.

(6.24)

Кодовые векторы принято представлять векторами-строками. Таким образом, сообщение m (последовательность k бит сообщения) представляется как вектор-строка (матрица 1 x k, в которой 1 строка и k столбцов).

В матричной записи генерация кодового слова U будет выглядеть как произведение m и G

U = mG, (6.25)

где умножение матриц С = АВ выполняется по следующему правилу.

Здесь А — матрица размером l х п, В — матрица размером n х т, а результирующая матрица С имеет размер l х т. Для примера, рассмотренного в предыдущем разделе, матрица генератора имеет следующий вид.

(6.26)

Здесь . — три линейно независимых вектора (подмножество восьми кодовых векторов), которые могут сгенерировать все кодовые векторы. Отметим, что сумма любых двух генерирующих векторов в результате не дает ни одного генерирующего вектора (противоположность свойству замкнутости). Покажем, как с использованием матрицы генератора, приведенной в выражении (6.26), генерируется кодовое слово U4 для четвертого вектора сообщения 110 в табл. 6.1.

Таким образом, кодовый вектор, соответствующий вектору сообщения, является линейной комбинацией строк матрицы G. Поскольку код полностью определяется матрицей G, кодеру нужно помнить лишь k строк матрицы G, а не все 2^k кодовых вектора. Из приведенного примера можно видеть, что матрица генератора размерностью 3 x 6, приведенная в уравнении (6.26), полностью заменяет исходный массив кодовых слов размерностью 8 x 6, приведенный в табл. 6.1, что значительно упрощает систему.