Циклический код

[Mikle1990]

Задача 2. Для циклического $(8,k)$ кода с образующим полиномом $g(x)=x^5+x^4+x+1$:

● Постройте образующую матрицу $G$.
● Приведите матрицу к каноническому виду.
● Определите вес гарантированно обнаруживаемых и исправляемых кодом ошибок, $t_{obn}$ и $t_{ispr}$.
● Определите долю обнаруживаемых кодом ошибок в общем числе возможных ошибок $K_{obn}$.
● Запишите вектор ошибки $e$, соответствующий одиночной ошибке, в двоичном символе с заданным номером # = 3.
● Найдите синдром $S$, соответствующий заданной одиночной ошибке (вектору $e$).
● Найдите вектор ошибки $e^{,}$ с весом больше $1$ , имеющий такой же синдром, как вектор $e$.

Решение

1) Построим образующую матрицу $G$.
$k=8-5=3$ (где $5$ - степень полинома)

$$G_{k,n}=\begin{bmatrix} 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\end{bmatrix}\qquad$$

2) Преобразуем матрицу $G$ к каноническому виду.

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

(Оффтоп)

Здесь я не стал записывать решение, т.к. долго. Вкратце так: поменял строки местами, транспонировал, сложил строки, транспонировал. Кстати говоря, $rangG=3$ , следовательно и единиц на главной диагонали должно быть три - т.е. как у меня и получилось.

3) Определим вес гарантированно обнаруживаемых и исправляемых кодом ошибок, $t_{obn}$ и $t_{ispr}$.

Запишем все возможные кодовые комбинации:

$00110011$

$01100110$

$11001100$

$10011001$

Минимальное кодовое расстояние $d_{min}$ равно минимальному весу ненулевого кодового слова.
В нашем случае $d_{min}=4$

$t_{obn}\le d_{min}-1$

$t_{ispr}<\frac{d_{min}}{2}$

$t_{obn}\le 3$

$t_{ispr}<2$

4) Определим долю обнаруживаемых кодом ошибок в общем числе возможных ошибок $K_{obn}$.

$$K_{obn}=\frac{O_{obn}}{O}\cdot 100\%=\frac{N-N_{p}}{N-1}\cdot 100\%$$

, где
$N$ - число возможных комбинаций ($N=2^n=2^8=256$).
$N_{p}$ - число разрешённых комбинаций ($N_{p}=4$)

$$K_{obn}=\frac{256-4}{256-1}\cdot 100\%=98\%$$

5) Запишем вектор ошибки $e$, соответствующий одиночной ошибке, в двоичном символе с заданным номером # = 3.

$e=00100000$ (в виде полинома: $x^5$)

6) Найдём синдром $S$, соответствующий заданной одиночной ошибке (вектору $e$).

$S(x)=e(x)\mod g(x)$

$S(x)=x^5\mod x^5+x^4+x+1$
$S(x)=x^4+x+1$
В виде вектора:
$S_{5}=10011$

7) Найдём вектор ошибки $e^{,}$ с весом больше $1$ , имеющий такой же синдром, как вектор $e$.

Жду вашей помощи, т.к. у меня за очень долгое время не получилось решить последний пункт

HELP ME, PLEASE!

P.S. Я пользовался учебником Вернер М. "Основы кодирования" и материалом из Интернета.

[Mikle1990]

Mikle1990 в сообщении #763663 писал(а):

$S(x)=x^4+x+1$

Ошибся. $S(x)=-x^4-x-1$

[Mikle1990]

Ошибка в 5-ом пункте.

Mikle1990 в сообщении #763663 писал(а):

5) Запишем вектор ошибки $e$, соответствующий одиночной ошибке, в двоичном символе с заданным номером # = 3.

$e=00001000$

$e=x^3$

В 6-ом пункте всё-таки

$S(x)=e(x)\mod g(x)$

$S(x)=x^3\mod x^5+x^4+x+1$
$S(x)=x^3$
В виде вектора: $S=1000$

-- Сб сен 14, 2013 17:17:01 --

7) Найдём вектор ошибки $e^{,}$ с весом больше $1$ , имеющий такой же синдром, как вектор $e$.

Необходимо найти такой вектор $e^{,}$, при котором при делении его на образующий полином $g(x)$ , будет получен синдром $S^{,}$ , равный синдрому $S$.

$e^{,}=q(x)\cdot (x^5+x^4+x+1)+x^3$

Положим $q(x)=x$ , тогда

$e^{,}=x(x^5+x^4+x+1)+x^3=x^6+x^5+x^3+x^2+x$
$e^{,}=0110 1110$ (вес больше $1$)

Проверка
$S^{,}=e^{,}\mod g(x)$
$S^{,}=x^6+x^5+x^3+x^2+x\mod x^5+x^4+x+1=x^3$
$S^{,}=S$