WikiSort.ru - Не сортированное

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

Определение Порождающим полиномом циклического ${\displaystyle (n,k)}$ кода ${\displaystyle C}$ называется такой ненулевой полином ${\displaystyle g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i}}$ из ${\displaystyle C}$ , степень которого наименьшая и коэффициент при старшей степени ${\displaystyle g_{r}=1}$ .

Теорема 1

Если ${\displaystyle C}$  — циклический ${\displaystyle (n,k)}$ код и ${\displaystyle g(x)}$  — его порождающий полином, то степень ${\displaystyle g(x)}$ равна ${\displaystyle r=n-k}$ , и каждое кодовое слово может быть единственным образом представлено в виде

${\displaystyle c(x)=m(x)g(x)}$ ,

где степень ${\displaystyle m(x)}$ меньше или равна ${\displaystyle k-1}$ .

Теорема 2

${\displaystyle g(x)}$  — порождающий полином циклического ${\displaystyle (n,k)}$ кода — является делителем двучлена ${\displaystyle x^{n}-1}$ .

Следствия: таким образом в качестве порождающего полинома можно выбирать любой полином, делитель ${\displaystyle x^{n}-1}$ . Степень выбранного полинома будет определять количество проверочных символов ${\displaystyle r}$ , число информационных символов ${\displaystyle k=n-r}$ .

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

Полиномы ${\displaystyle g(x),xg(x),x^{2}g(x),\dots ,x^{k-1}g(x)}$ линейно независимы, иначе ${\displaystyle m(x)g(x)=0}$ при ненулевом ${\displaystyle m(x)}$ , что невозможно.

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

${\displaystyle {\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)}$ , где ${\displaystyle G}$ является порождающей матрицей, ${\displaystyle m(x)}$  — информационным полиномом.

Матрицу ${\displaystyle G}$ можно записать в символьной форме:

${\displaystyle 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}}}$

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

Для каждого кодового слова циклического кода справедливо ${\displaystyle c(x)=0\mod g(x)}$ . Поэтому проверочную матрицу можно записать как:

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

Тогда:

${\displaystyle {\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x)}$

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

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

${\displaystyle c(x)=m(x)g(x)}$ .

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

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

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

${\displaystyle c(x)=[s(x)\;m(x)]}$

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

${\displaystyle c(x)=x^{r}m(x)+s(x),\quad r=n-k}$

Тогда из условия ${\displaystyle c(x)=x^{r}m(x)+s(x)=0\mod g(x)}$ , следует

${\displaystyle s(x)=-x^{r}m(x)\mod g(x)}$

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

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

В качестве делителя ${\displaystyle x^{7}-1}$ выберем порождающий полином третьей степени ${\displaystyle g(x)=x^{3}+x+1}$ , тогда полученный код будет иметь длину ${\displaystyle n=7}$ , число проверочных символов (степень порождающего полинома) ${\displaystyle r=3}$ , число информационных символов ${\displaystyle k=4}$ , минимальное расстояние ${\displaystyle d=3}$ .

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

${\displaystyle 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}}}$ ,

где первая строка представляет собой запись полинома ${\displaystyle g(x)}$ коэффициентами по возрастанию степени.

Остальные строки — циклические сдвиги первой строки.

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

${\displaystyle 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-го, представляет собой остаток от деления ${\displaystyle x^{i-1}}$ на полином ${\displaystyle g(x)}$ , записанный по возрастанию степеней, начиная сверху.

Так, например, 4-й столбец получается ${\displaystyle h_{4}(x)=x^{3}\mod g(x)=x+1}$ , или в векторной записи ${\displaystyle [110]}$ .

Легко убедиться, что ${\displaystyle GH^{T}=0}$ .

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

В качестве порождающего полинома ${\displaystyle g(x)}$ можно выбрать произведение двух делителей ${\displaystyle x^{15}-1}$ :

${\displaystyle g(x)=g_{1}(x)g_{2}(x)=(x^{4}+x+1)(x^{4}+x^{3}+x^{2}+x+1)=x^{8}+x^{7}+x^{6}+x^{4}+1}$ .

Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома ${\displaystyle m(x)}$ со степенью ${\displaystyle k-1}$ таким образом:

${\displaystyle c(x)=m(x)g(x)}$ .

Например, информационному слову ${\displaystyle {\overline {m}}=[1000111]}$ соответствует полином ${\displaystyle m(x)=x^{6}+x^{5}+x^{4}+1}$ , тогда кодовое слово ${\displaystyle c(x)=(x^{6}+x^{5}+x^{4}+1)(x^{8}+x^{7}+x^{6}+x^{4}+1)=x^{14}+x^{12}+x^{9}+x^{7}+x^{5}+1}$ , или в векторном виде ${\displaystyle {\overline {c}}=[1000010101001010]}$