Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Линейные коды и их порождающие матрицы

Рассмотрим множество S всех 2n n–компонентных векторов x=(x1, x2, … , xn) , элементы которых xi принадлежат GF(2). Очевидно, S есть n-мерное векторное пространство. Выберем в нем k<n линейно независимых векторов g1, g2, … , gk , что всегда возможно в силу присутствия в S n линейно независимых векторов. Построим множество U, состоящее из всех 2k линейных комбинаций выбранных векторов:

Прямая проверка показывает, что U замкнуто относительно сложения векторов и умножения их на скаляры из GF(2) , и, следовательно, U есть векторное пространство, т.е. подпространством S. Это подпространство, имеющее размерность k,и является той конструкцией, которая именуется линейным кодом. Итак, двоичный (n,k)линейный код– это любоеk-мерное подпространство пространства векторов длиныn. Поскольку подпространство содержит M=2k, кодовых слов, k=logM есть не что иное, как число информационных битов, передаваемых кодом, длина которого, разумеется, равна n. Запишем векторы gi=(gi1, gi2, … , gin) один под другим как строки матрицы G:

Вводя k–компонентный вектор сообщения (данных) a=(a1, a2, … , ak), любое слово uлинейного кода U можно записать в форме

Как видно, кодовое слово линейного кода есть произведение информационного вектора aна матрицу G, по этой причине именуемую порождающей матрицей кода. Из определения векторного пространства следует, что:

1. Любой линейный код содержит нулевое слово 0=(0 0 … 0);

2. Любая сумма слов линейного кода есть вновь кодовое слово того же кода:

3. Теорема 4.3.1 Минимальное расстояние линейного кода равно наименьшему из весов ненулевых слов кода:

Последний результат является одним из оснований особой популярности линейных кодов: для нахождения расстояния линейного кода достаточно протестировать веса M–1 его ненулевых векторов взамен перебора M(M – 1)/2 >> M пар кодовых слов.

Любой линейный код можно преобразовать в эквивалентный (имеющий те же объем M, длину n и веса всех слов), задаваемый канонической порождающей матрицей

где Ik – k´k единичная матрица, а P – матрица размерности k´(n–k). Порождающая матрица этого вида отвечает систематическому линейному коду, в котором на первых k позициях каждого слова располагаются непосредственно биты передаваемого сообщения:

Проверочная матрица и ее связь с кодовым расстоянием

Рассмотрим систематический линейный код U с k´n порождающей матрицей
G=[Ik ¦ P] и построим (nkn проверочную матрицу H=[–PT ¦ In-k], где верхний индекс “T” означает транспонирование матрицы P. Для произвольного кодового вектора uÎU

т. е. умножение на транспонированную матрицу H дает нуль. Таким образом, любой линейный код есть нуль–пространство своей проверочной матрицы

Теорема 4.4.1 Линейный кодUимеет минимальное расстояниеd,если и только если любыеd–1столбцов проверочной матрицыHлинейно независимы, но какие-тоdстолбцов линейно зависимы.

Теорема 4.4.2 (Граница Синглтона). Расстояние линейного(n,k)кода не больше числа проверочных символов плюс единица:

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

Следствие 4.4.3 Граница Варшамова-Гилберта.

Хотя в определении параграфа 6.3 для облегчения ознакомления с линейными кодами фигурировал двоичный алфавит, все результаты последних двух параграфов без затруднений переносятся на q-ичные линейные коды.

Коды Хэмминга

Коды, фигурирующие в заголовке, замечательны как в познавательном, так и в практическом аспекте. Выпишем все различные ненулевые m–разрядные двоичные числа (m–компонентные векторы) как столбцы в некотором, скажем натуральном (возрастающем) порядке и используем полученную матрицу в качестве проверочной для линейного кода. Подобная матрица имеет размер m´(2m–1). Полученный код и есть код Хэмминга длины n= 2m–1. Так как число строк проверочной матрицы равно числу проверочных символов, код Хэмминга имеет k=nm=2mm–1 информационных символов, т.е. является (2m–1, 2mm–1) линейным кодом.

Пример 4.5.1 Столбцы проверочной матрицы двоичного кода Хэмминга (7,4) есть десятичные числа от 1 до 7, в двоичной записи.

Если нужен систематический код Хэмминга, достаточно переупорядочить столбцы проверочной матрицы H, выделив явно m´m единичную матрицу как составной блок проверочной. После этого легко строится и каноническая порождающая матрица.

Так как все столбцы матрицы H кода Хэмминга различны, любая их пара линейно независима, в то время как сумма пары любых столбцов является каким-то третьим столбцом H. Поэтому в силу теоремы 6.4.1 расстояние кода Хэмминга равно трем и такой код исправляет любую однократную ошибку.

Коды Хэмминга являются почти уникальным примером совершенных двоичных кодов. Известны и недвоичные коды Хэмминга.

В таблице приведены параметры нескольких кодов Хэмминга в порядке возрастания длин.

Расширенные и укороченные коды

Любой линейный (n,k) код U можно превратить в код U´ с параметрами (n+1, k) добавлением символа общей проверки на четность. Пусть, например, u=(u1, u2, … , un) – произвольное кодовое слово исходного (n,k) линейного кода U. Тогда соответствующее слово расширенного кода U´ строится по правилу u´=(u1, u2, … , un, un+1) , где un+1= u1+ u2+ … + un (разумеется с суммированием согласно двоичной арифметике, т.е. по модулю 2). В итоге

и, следовательно, вес любого слова в расширенном коде будет четным. Это, в свою очередь, означает, что при нечетном расстоянии d исходного кода U минимальное расстояние расширенного кода U´ увеличится на единицу: d´ = d+1. Тем самым, любой линейный (n,k) код нечетного расстояния d, исправляющий t=(d–1)/2 ошибок, можно трансформировать в расширенный (n+1, k) код, исправляющий ошибки прежней кратности t=(d–1)/2=(d´/2)–1 и, вдобавок, обнаруживающий ошибки кратности t+1. Порождающая матрица G´ расширенного кода получается из исходной G добавлением общих проверок на четность строк последней.

Коды Хэмминга весьма наглядны в части иллюстрации сказанного. Так как расстояние любого такого кода равно трем, в результате расширения получается (2m, 2m–m–1) код с расстоянием четыре, который, в дополнение к исправлению любых однократных, обнаруживает и любые двукратные ошибки. Поучительный пример реального применения расширенного (32,26) кода Хэмминга для передачи цифрового потока данных с искусственного спутника Земли дает глобальная радионавигационная система космического базирования GPS.

Другой популярный прием преобразования имеющихся кодов в новые – укорочение. Укороченный код получается из исходного систематического отбором лишь слов, имеющих l первых нулевых символов. Зная наперед об этом свойстве всех отобранных слов, нет нужды передавать упомянутые нулевые символы, уменьшив длину кода на l с одновременным сокращением на ту же величину числа информационных бит. Результирующий (n–l, k–l) код будет обладать расстоянием, не худшим, чем у исходного. Легко показать, что порождающая матрица G´ укороченного кода получается из канонической матрицы G исходного удалением первых l строк и столбцов.

Пример 4.6.1Удалив в канонической порождающей матрице (7,4) кода Хэмминга два левых столбца и две верхних строки, придем к канонической порождающей матрице укороченного линейного (5,2) кода

.

Разумеется, этот код – подобно исходному коду Хэмминга – исправляет любую однократную ошибку.

Последнее изменение этой страницы: 2016-06-09

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...