Как найти проверочную матрицу кода

Любой циклический
(n, k)
– код может быть задан в соответствии
с определением 2, порождающим многочленомg(x)
или проверочным многочленом.

Знание этих
многочленов позволяет построить
порождающую матрицу и матрицу проверок.
Для циклического (n,
k) – кода существует
простой способ нахожденияkлинейно независимых кодовых комбинаций,
образующих порождающую матрицу.
Этот способ состоит в следующем.
Записывается порождающий многочленg(x).
В соответствии с определением 2 комбинация,
соответствующая порождающему многочлену,
принадлежит циклическому (n,
k) – коду. В соответствии
с определением 1 циклические сдвиги
комбинации, соответствующейg(x),
также должны принадлежать этому же
коду. Алгебраически сдвиг соответствует
умножению кодовой комбинации нах.
Так как степеньg(x)равнаn—k,
то подобным образом мы можем получить
кодовые комбинации

Легко проверить,
что эти кодовые комбинации линейно
независимы, хотя бы потому, что степени
всех этих многочленов различны, поэтому
данный набор многочленов может быть
использован в качестве
:

.

Путем элементарных
преобразований эта матрица может быть
приведена к канонической форме.

Аналогичным образом
по проверочному многочлену
можно построить матрицу проверок

.

Пример 6.4.Для
циклического (7,4) – кода с порождающим
многочленом(см. пример 6.3.) построить порождающую
матрицу.

Находим

Следовательно,
порождающая матрица для данного кода
имеет вид:

Полученные
результаты и рассуждения относительно
алгебраической структуры циклических
кодов, приведенные в разделе 6.2, позволяют
подметить одно важное свойство циклических
кодов, определенное их циклической
структурой.

Свойство 6.1.
Произведение кодовой комбинации
циклического кодана произвольный многочлендает
кодовую комбинацию этого же циклического
кода.

Действительно
,
а любое произведение такого вида равно
нулю, т.е. принадлежит кодовому
подпространству (раздел 6.2).

Более элементарное
доказательство:

.

Полученная сумма
есть сумма циклических сдвигов кодовых
комбинаций, что по свойству замкнутости
группового кода должно дать комбинацию
того же циклического кода.

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

Коэффициент при
хв произведенииравен

.

Слагаемые, содержащие
,
появляются вследствие слагаемых в
произведении,
которые содержат.
Но так как,
т.е.,
то.
Равенство дляможно
представить в виде скалярного произведения:

.

В этом произведении
первый вектор соответствует а(х).
Второй вектор содержит коэффициентыb(х), расположенные
в обратном порядке и сдвинутые циклически
наj+1 элемент вправо.

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

.

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

Пример 6.5.
Построить матрицу проверок для
циклического (7,4) – кода из предыдущего
примера.

Для построения
матрицы проверок найдем проверочный
многочлен

Отсюда

В силу того, что
условие равенства нулю произведения
многочленов и скалярного произведения
соответствующих им векторов не совпадают,
для выполнения равенства
при построении матрицыкомпоненты
векторов, соответствующихh(x),
xh(x)
и x²h(x)записываем в обратном порядке

.

В полученной
матрице проверок в качестве столбцов
записаны все 7 ненулевых последовательностей
длины 3. Следовательно, данный код
является кодом Хэмминга.

Вообще говоря,
циклические коды Хэмминга строятся на
основе порождающих многочленов степени
m, являющихся
сомножителями двучленов
и не являющихся сомножителями никаких
двучленов меньшей степени. Корни этих
многочленов имеют порядок 2^m-1,
т.е они являются примитивными элементами
поляGF(2^m).Это означает, что порождающий многочлен
кода Хэмминга порождает полеGF(2^m).

Условимся в любом
циклическом коде первые n—kэлементов кодовой комбинации, то есть
коэффициенты прииспользовать в качестве проверочных
элементов, а последниеkэлементов, то есть коэффициенты при,
— в качестве информационных (рис. 6.1).

a₀a,
….., a_n-1
= a₀x⁰+a₁x¹+
…. + a_n-1xⁿ⁺¹

x⁰
x¹
x²
x^n-k-1
x^n-k
x^n-2
x^n-1

a0

a1

a2

… … … … ..

an-k-1

an-k

… … … …

an-2

an-1

Избыточные
элементы
Информационные элементы

Рис
6.1

Структура кодовой
комбинации циклического кода

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

Всякий циклический
(n, k)
– код приводится к этой форме следующим
образом.

Пусть
есть многочлен степениk-1,
соответствующий комбинации простогоk – элементного
кода, которую необходимо закодировать
циклическим (n, k)
– кодом. В комбинации циклического (n,
k) – кода этуk— элементную комбинацию необходимо
поместить на позиции информационных
элементов, для чего помножим многочленна.
В результате получаем многочлен,
степень которого равна n-1.
Так как по определению циклического
кода каждая кодовая комбинация должна
делиться на порождающий многочленg(x)степениn—k,
то проверим выполнение этого условия.
В общем случае в результате деления
получим частноеq_i(x)степениk-1 и остаток,
степень которого не превышаетn—k-1.
Результат деления представим в следующем
виде:

.

Рассмотрим многочлен
.
Коэффициенты приэтого многочлена являются коэффициентами
остатка,
а коэффициенты при степеняхэлементами первичной кодовой комбинации.

С другой стороны

,

то есть многочлен
делится наg(x).
Итак,и есть искомая кодовая комбинация
циклического (n, k)
– кода. Отсюда получаем правило построения
порождающей матрицы циклического (n,
k) – кода в канонической
форме:

,

где I_k– единичная матрица размерности,
соответствующая информационным элементам
кодовых комбинаций,;

— матрица размерности
,j-я— строка, которой
соответствует остатку от делениянаg(x).

Матрица проверок
строится на основании матрицыпо правилу

.

Пример 6.6.Построить порождающую матрицу и матрицу
проверок в канонической форме для
циклического (7,4) – кода с порождающим
многочленом.
Находим частное и остаток от делениянаg(x)и записываем результат деления в форме
равенства

I₃

R_4×3

О

R_4×3

I₄

кончательно получаем

.

Из рассмотренного
примера видно, что проверочная матрица
циклического (n, k)
– кода содержит в качестве столбцов
остатки от деленияна порождающий многочленg(x).Сравнение
столбцов найденной проверочной матрицы
с элементами поляGF(2³)показывает их полное совпадение с
ненулевыми элементамиGF(2³).Результаты рассмотренного примера
будут использованы для обоснования
эквивалентности различных столбцов
вычисления синдрома.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Порождающая и проверочная матрицы линейного кода

Поиск эффективных и простых в обработке корректирующих кодов осуществляется с использованием компьютерного моделирования и алгебраических методов. В теории кодирования n — разрядному двоичному слову ставится в соответствие многочлен степени n или вектор в  n — мерном пространстве с компонентами, принимающими значения 1 и 0 (например, слову 101101 – многочлен х⁵+х³+х²+1).  Преобразования кодовых слов рассматриваются как операции над многочленами или векторами.

 Любое кодовое слово V  линейного блокового кода (n, k) можно получить умножением вектора  U, представляющего информационное слово, на порождающую матрицу G размерности  k x n:  V =U G.

 Принятое слово можно проверить на отсутствие ошибок умножением его на транспонированную проверочную матрицу H^т . Если слово принято без ошибок, результат умножения нулевой:  V H^т=0. 

 Проверочная матрица (parity-check matrix) связана с порождающей матрицей соотношением G H^т=0.

Порождающая матрица выбирается неоднозначно. Для упрощения кодирования и декодирования удобно использовать порождающую матрицу, составленную из двух матриц: единичной матрицы размерности k x k  и дописываемой справа матрицы-дополнения, или контрольной подматрицы, размерности  k x (n-k). Такая матрица порождает систематический код: первые  k  символов слова совпадают с исходным информационным словом, а остальные символы являются проверочными.

Пример

Информация в лекции «32 Конфликты социально-психологического уровня» поможет Вам.

Помехоустойчивая кодовая комбинация V  = 1010101 получена умножением информационного слова U = 1010  на порождающую матрицу G.

Если в принятом слове (V) нет ошибки, при умножении этого слова на проверочную матрицу Н^Т код синдрома нулевой:  V Н^Т =0.

При ошибке в первом разряде слова  V₁  код синдрома V₁ Н^Т = 110.

Номер строки матрицы H^т с этим кодом синдрома совпадает с номером ошибочного разряда принятой кодовой комбинации (№1).

При ошибке во втором разряде слова V₂  результат проверки V₂ Н^Т = 101. Полученный синдром находится во второй строке матрицы H^т, следовательно ошибочен разряд №2 принятой кодовой комбинации.

Реализация матричных операций на интегральных микросхемах не представляет технических трудностей.

Определение:

Линейный код (англ. Linear code) — код фиксированной длины (блоковый код), исправляющий ошибки, для которого любая линейная комбинация кодовых слов также является кодовым словом.

Линейные коды обычно делят на блоковые коды и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.^[1]

По сравнению с другими кодами, линейные коды позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации (см. синдромы ошибок).

Формальное определение

Определение:

Линейный код длины и ранга является линейным подпространством размерности векторного пространства , где — конечное поле (поле Галуа) из элементов. Такой код с параметром называется -арным кодом (напр. если  — то это 5-арный код). Если или , то код представляет собой двоичный код, или тернарный соответственно.

Векторы в называют кодовыми словами. Размер кода — это количество кодовых слов, т.е. .

Весом кодового слова называют число его ненулевых элементов. Расстояние между двумя кодовыми словами определяется как расстояние Хэмминга. Расстояние линейного кода — это минимальный вес его ненулевых кодовых слов или равным образом минимальное расстояние между всеми парами различных кодовых слов.

Линейный код длины , ранга и с расстоянием называют -кодом (англ. [n,k,d] code). Параметр d в обозначении кода часто опускается, потому что через него не задается структура кода. В таком случае пишут просто -код. В литературе встречается обозначение как в квадратных, так и в круглых скобках.^[2][3]

Порождающая матрица

Определение:

Порождающая матрица — это матрица, столбцы которой задают базис линейного кода.

Так как линейный код является линейным подпространством , целиком код (может быть очень большим) может быть представлен как линейная оболочка набора из кодовых слов (т.е. базис). Этот базис часто объединяют в столбцы матрицы и называют такую матрицу порождающей матрицей кода .

В случае, если , где — это единичная матрица размера , а — это матрица размера говорят, что матрица находится в каноническом виде.

Имея матрицу можно получить из некоторого входного вектора кодовое слово линейного кода

,

где и — векторы-строки. Порождающая матрица линейного -кода имеет вид . Число избыточных бит тогда определяется как .

Проверочная матрица

Определение:

Проверочная матрица линейного кода — это порождающая матрица ортогонального дополнения . Другими словами, это матрица, которая описывает правила, которым должны удовлетворять части кодового слова.

Используется, чтобы определить, является ли некий вектор кодовым словом, а также в алгоритмах декодирования (напр. syndrome decoding).

Кодовое слово принадлежит коду тогда и только тогда, когда или, что то же самое, .

Проверочную матрицу можно получить из порождающей и наоборот: пусть дана порождающая матрица в каноническом виде , тогда проверочную матрицу можно получить по формуле

,

так как .

Кодирование и декодирование, примеры

Предположим, что имеется линия связи, по которой мы можем пересылать и принимать биты. В среднем какой-то известный процент переданных битов будет поврежден, ошибочен. Такая модель называется двоичным симметричным каналом.

Блок из символов сообщения будет кодироваться в кодовое слово , где ; эти кодовые слова образуют код.

Первая часть кодового слова состоит из информационных битов сообщения:

,

за которым следуют проверочных битов . Проверочные биты выбраны так, чтобы кодовые слова удовлетворяли уравнению

,

где — проверочная матрица.

Пример

Проверочная матрица

определяет код с и . Для этого кода

.

Сообщение кодируется в кодовое слово , которое начинается с самого сообщения:

,

а последующих три проверочных символа выбираются так, чтобы выполнялось уравнение .

Если сообщение , то , и проверочные биты легко определяются: , так что кодовое слово .

Минимальное расстояние и корректирующая способность

Линейность гарантирует, что расстояние Хэмминга между кодовым словом и любым другим кодовым словом не зависит от . Так как — тоже кодовое слово, а , то

Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода.

Минимальное расстояние кода однозначно определяет количество ошибок, которое способен обнаружить () и исправить () данный код.

Синдромы и метод обнаружения ошибок в линейном коде

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

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

Преимущества и недостатки линейных кодов

+ Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.

— Хотя линейные коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Примечания

Источники информации

• wikipedia.org — Линейный код
• wikipedia.org — Linear code
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М: Связь, 1979. — 744 с., стр. 12-33
• Ф.И. Соловьева — Введение в теорию кодирования
• В. А. Липницкий, Н. В. Чесалин — Линейные коды и кодовые последовательности: учеб.-метод. пособие для студентов мех.-мат. фак. БГУ. Минск: БГУ, 2008. — 41 с.