2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Циклический код
Сообщение14.09.2013, 03:02 
Задача 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$. :?: :!:

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

HELP ME, PLEASE!

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

 
 
 
 Re: Циклический код
Сообщение14.09.2013, 12:43 
Mikle1990 в сообщении #763663 писал(а):
$S(x)=x^4+x+1$


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

 
 
 
 Re: Циклический код
Сообщение14.09.2013, 17:00 
Ошибка в 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$

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group