2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Циклический код
Сообщение14.09.2013, 03:02 


14/12/09
306
Задача 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 


14/12/09
306
Mikle1990 в сообщении #763663 писал(а):
$S(x)=x^4+x+1$


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

 Профиль  
                  
 
 Re: Циклический код
Сообщение14.09.2013, 17:00 


14/12/09
306
Ошибка в 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 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group