- Циклические коды
-
Циклический код — линейный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).
Содержание
Введение
Пусть слово длины n над алфавитом из элементов конечного поля и полином, соответствующий этому слову, от формальной переменной x. Видно, что это соответствие не просто взаимнооднозначное, но и изоморфное. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации пары слов и , равен линейной комбинации полиномов этих слов
Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n-1 над полем
Алгебраическое описание
Если кодовое слово, получающееся циклическим сдвигом на один разряд вправо из слова , то ему соответствующий полином c1(x) получается из предыдущего умножением на x:
, пользуясь тем, что ,
Сдвиг вправо и влево соответственно на j разрядов:
Если m(x) — произвольный полином над полем GF(q) и c(x) — кодовое слово циклического (n,k) кода, то m(x)c(x)mod(xn − 1) тоже кодовое слово этого кода.
Порождающий полином
Определение Порождающим полиномом циклического (n,k) кода C называется такой ненулевой полином из C, степень которого наименьшая и коэффициент при старшей степени gr = 1.
Теорема 1Если C — циклический (n,k) код и g(x) — его порождающий полином, тогда степень g(x) равна r = n − k и каждое кодовое слово может быть единственным образом представлено в виде
c(x) = m(x)g(x),
где степень m(x) меньше или равна k − 1.
Теорема 2g(x) — порождающий полином циклического (n,k) кода является делителем двучлена xn − 1
Следствия: таким образом в качестве порождающего полинома можно выбирать любой полином, делитель xn − 1. Степень выбранного полинома будет определять количество проверочных символов r, число информационных символов k = n − r.Порождающая матрица
Полиномы линейно независимы, иначе m(x)g(x) = 0 при ненулевом m(x), что невозможно.
Значит кодовые слова можно записывать, как и для линейных кодов, следущим образом:
, где G является порождающей матрицей, m(x) — информационным полиномом.
Матрицу G можно записать в символьной форме:
Проверочная матрица
Для каждого кодового слова циклического кода справедливо . Поэтому проверочную матрицу можно записать как:
Тогда:
Кодирование
Несистематическое
При несистематическом кодирование кодовое слово получается в виде произведения информационного полинома на порождающий
c(x) = m(x)g(x).
Оно может быть реализовано при помощи перемножителей полиномов.
Систематическое
При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного
Пусть информационное слово образует старшие степени кодового слова, тогда
c(x) = xrm(x) + s(x),r = n − k
Тогда из условия , следует
Это уравнение и задает правило систематичекого кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров(МЛФ)
Примеры
Двоичный (7,4,3) код
В качестве делителя x7 − 1 выберем порождающий полином третьей степени g(x) = x3 + x + 1, тогда полученный код будет иметь длину n = 7, число проверочных символов (степень порождающего полинома) r = 3, число информационных символов k = 4, минимальное расстояние d = 3.
Порождающая матрица кода:
,
где первая строка представляет собой запись полинома g(x) коэффициентами по возрастанию степени. Остальные строки — циклические сдвиги первой строки.
Проверочная матрица:,
где i-ый столбец, начиная с 0-ого, представляет собой остаток от деления xi на полином g(x), записанный по возрастанию степеней, начиная сверху.
Так, например, 3-ий столбец получается , или в векторной записи [110].
Легко убедиться, что GHT = 0.
Двоичный (15,7,5) БЧХ код
В качестве порождающего полинома g(x) можно выбрать произведение двух делителей x15 − 1^
g(x) = g1(x)g2(x) = (x4 + x + 1)(x4 + x3 + x2 + x + 1) = x8 + x7 + x6 + x4 + 1.
Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома m(x) со степенью k − 1 таким образом:
c(x) = m(x)g(x).
Например, информационному слову соответствует полином m(x) = x6 + x5 + x4 + 1, тогда кодовое слово c(x) = (x6 + x5 + x4 + 1)(x8 + x7 + x6 + x4 + 1) = x14 + x12 + x9 + x7 + x5 + 1, или в векторном виде
См. также
Ссылки
Wikimedia Foundation. 2010.