Циклический код в матлабе, циклический код схема

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

Содержание

1 Введение
2 Алгебраическое описание
3 Кодирование
- 3.1 Несистематическое
- 3.2 Систематическое
4 Примеры
- 4.1 Двоичный (7,4,3) код
- 4.2 Двоичный (15,7,5) БЧХ код
5 См. также
6 Ссылки

Введение

Пусть слово длины n над алфавитом из элементов конечного поля и полином, соответствующий этому слову, от формальной переменной . Видно, что это соответствие не просто взаимнооднозначное, но и изоморфное. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации пары слов и , равен линейной комбинации полиномов этих слов

Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n-1 над полем

Алгебраическое описание

Если кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова , то соответствующий ему полином получается из предыдущего умножением на x:

, пользуясь тем, что ,

Сдвиг вправо и влево соответственно на разрядов:

Если — произвольный полином над полем и — кодовое слово циклического кода, то тоже кодовое слово этого кода.

Порождающий полином

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

Теорема 1

Если — циклический код и — его порождающий полином, тогда степень равна и каждое кодовое слово может быть единственным образом представлено в виде

где степень меньше или равна .

Теорема 2

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

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

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

Полиномы линейно независимы, иначе при ненулевом , что невозможно.

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

$\overline{m}G=(m_0,m_1,\dots,m_{k-1}) \begin{bmatrix} g(x) \\ xg(x) \\ \dots \\ x^{k-1}g(x) \end{bmatrix} = m(x)g(x)$ , где является порождающей матрицей, — информационным полиномом.

Матрицу можно записать в символьной форме: $G = \begin{bmatrix} g_0 & g_1 & \dots & g_{r-1} & g_r & 0 & \dots & 0 \\ 0 & g_0 & \dots & g_{r-2} & g_{r-1} & g_r & \dots & 0 \\ . & . & \dots & . & . & . & \dots & . \\ 0 & 0 & \dots & 0 & g_0 & g_1 & \dots & g_r \end{bmatrix}$

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

Для каждого кодового слова циклического кода справедливо . Поэтому проверочную матрицу можно записать как:

$H = \begin{bmatrix} 1 & x & x^2 & \dots & x^{n-2} & x^{n-1} \\ \end{bmatrix}\mod g(x)$

Тогда:

Кодирование

Несистематическое

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

Оно может быть реализовано при помощи перемножителей полиномов.

Систематическое

При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного

Пусть информационное слово образует старшие степени кодового слова, тогда

Тогда из условия , следует

Это уравнение и задает правило систематического кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров(МЛФ)

Примеры

Двоичный (7,4,3) код

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

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

$G = \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$ ,

где первая строка представляет собой запись полинома коэффициентами по возрастанию степени. Остальные строки — циклические сдвиги первой строки.

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

$H = \begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{bmatrix}$ ,

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

Так, например, 4-ий столбец получается , или в векторной записи .

Легко убедиться, что .

Двоичный (15,7,5) БЧХ код

В качестве порождающего полинома можно выбрать произведение двух делителей ^

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

Например, информационному слову соответствует полином , тогда кодовое слово , или в векторном виде

См. также

Ссылки

Механизмы контроля целостности данных.

Циклический код в матлабе, циклический код схема.

Light-industry-up.ru

Экосистема промышленности

Публикации