2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Линейный код
Сообщение07.09.2013, 07:50 


14/12/09
306
Задача 1.
Задана матрица проверочных элементов линейного кода $M=\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix} \qquad$.

1. Определите параметры кода $(n,k) $ и запишите систему уравнений, задающих символы кода $V_{i}$
2. Запишите образующую матрицу линейного кода $G$ и проверочную матрицу $H$
3. Рассчитайте скорость кода $R$ и избыточность кода $W$
4. Найдите вероятность необнаруженной ошибки при применении этого кода в ДСК без памяти с вероятностью ошибки в двоичном символе $\varepsilon=0,01$

Я изучил материал по этой теме в своей методичке, читал книги из списка литературы, указанного в конце методички, но так и не нашёл материал, необходимый для решения данной задачи :facepalm:

Всё, что я понял, так это то, что $n=3$, а $k=4$.
$n$ - длина кода, т.е. длина кодовых слов.
$k$ - число информационных символов.
Что-то я запутался, как $n$ может быть меньше $k$? :?
А что вообще такое Матрица проверочных элементов? Я не могу нигде найти чёткое определение этого понятия :cry:

И как вообще записать систему уравнений, задающих символы кода $V_{i}$? Если можете подсказать в каком учебнике про это написано, то было бы тоже неплохо, особенно если ещё и страницу укажите.

 Профиль  
                  
 
 Re: Линейный код
Сообщение07.09.2013, 10:46 
Заслуженный участник


02/08/11
7003
По-идее, матрица проверочных элеметов - это часть производящей матрицы. К ней надо слева дописать единичную матрицу:
$$G=\begin{bmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix} \qquad$$
$G$ - это производящая матрица, таким образом $n=7$, $k = 4$.

-- 07.09.2013, 11:53 --

Вот тут кое-что есть Линейные коды

 Профиль  
                  
 
 Re: Линейный код
Сообщение08.09.2013, 09:19 


14/12/09
306
warlock66613, Вы правы. (см. Вернер М. Основы кодирования стр. 133)

Тогда проверочная матрица будет выглядеть так:
$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} \qquad$

Скорость кода:
$R=\frac{k}{n}=\frac{4}{7}=0.571$

Избыточность кода:
$W=\frac{n-k}{n}=\frac{r}{n}=\frac{3}{7}=0.428$

Вероятность необнаруженной ошибки при применении этого кода в ДСК без памяти:
(см. Вернер М. Основы кодирования стр. 145)
$$P_{r}= \sum^{n}_{i={d_{\min}}}A_{i}P_{e}^{i}(1-P_{e})^{n-i}$$
$i= $ от $3$ до $7$ :?:
Из условия задачи $P_{e}=\varepsilon=0,01$ :?:

Откуда мне узнать $A_{i}$? И вообще правильно ли я начал решать?

Также, должен признаться – я не смог записать систему уравнений, задающих символы кода $V_{i}$ :-(

(Оффтоп)

Кажется, мне попался вариант задания, который очень похож на пример в учебнике Вернера :-)

 Профиль  
                  
 
 Re: Линейный код
Сообщение09.09.2013, 19:55 


14/12/09
306
Попробую изложить свои мысли относительно системы уравнений, задающих символы кода $V_{i}$

В моей методички написано
Кодовое слово $V$ формируется из последовательности $U$ по следующему правилу:
$v_{i}=u_{i}$ , при $1 \leq i \leq k$

$v_{i}=\sum^{k}_{l=1}u_{i}\cdot a_{l, i}$ , при $k+1 \leq i \leq n$

(Оффтоп)

Напоминаю, что у меня $n=7$, $k = 4$

Таким образом, я вроде бы могу записать систему уравнений, задающих символы кода $V_{i}$ :

$v_{1}=u_{1}$
$v_{2}=u_{2}$
$v_{3}=u_{3}$
$v_{4}=u_{4}$
$v_{5}=u_{1}\cdot a_{1,5}\oplus u_{2}\cdot a_{2,5}\oplus u_{3}\cdot a_{3,5}\oplus u_{4}\cdot a_{4,5}$
$v_{6}=u_{1}\cdot a_{1,6}\oplus u_{2}\cdot a_{2,6}\oplus u_{3}\cdot a_{3,6}\oplus u_{4}\cdot a_{4,6}$
$v_{7}=u_{1}\cdot a_{1,7}\oplus u_{2}\cdot a_{2,7}\oplus u_{3}\cdot a_{3,7}\oplus u_{4}\cdot a_{4,7}$

Произведя подстановку($u\rightarrow v$ , $a_{k,n}\rightarrow матрица G$), я получаю:

$v_{5}=v_{1}\cdot 1\oplus v_{2}\cdot 0\oplus v_{3}\cdot 1\oplus v_{4}\cdot 1$
$v_{6}=v_{1}\cdot 1\oplus v_{2}\cdot 1\oplus v_{3}\cdot 1\oplus v_{4}\cdot 0$
$v_{7}=v_{1}\cdot 0\oplus v_{2}\cdot 1\oplus v_{3}\cdot 1\oplus v_{4}\cdot 1$

т.е. получаю систему уравнений:

$v_{5}=v_{1}\oplus v_{3}\oplus v_{4}$
$v_{6}=v_{1}\oplus v_{2}\oplus v_{3}$
$v_{7}=v_{2}\oplus v_{3}\oplus v_{4}$

Как думаете, под словами "система уравнений, задающих символы кода $V_{i}$ ", имелось ввиду именно то, что я написал выше?

 Профиль  
                  
 
 Re: Линейный код
Сообщение09.09.2013, 21:44 


14/12/09
306
Исходя из той системы уравнений, которую я получил, можно построить кодовую таблицу (7,4) кода Хэмминга:

Изображение

Для (7,4) кода Хэмминга значения $A_{i}$ (распределение весов) можно получить из таблицы выше.
Имеем $A_{0}=1$ , $A_{1}=A_{2}=0$ , $A_{3}=A_{4}=7$ , $A_{5}=0$ , $A_{6}=0$, $A_{7}=1$.

Для нахождения вероятности $P_{r}$ необнаруженной ошибки, используем формулу:
$$P_{r}= \sum^{n}_{i={d_{\min}}}A_{i}P_{e}^{i}(1-P_{e})^{n-i}$$
$$P_{r}= \sum^{7}_{3}A_{i}\cdot 0,01^{i}(0,99)^{7-i}$$
$$P_{r}= 7\cdot 0,01^{3}(0,99)^{4}+ 7\cdot 0,01^{4}(0,99)^{3}+1\cdot 0,01^{7}(0,99)^{0}=6,792\cdot 10^{-6}$$

Ура! Задача решена! :-)
Впереди ещё две задачи: циклический код и свёрточный код. Скоро создам соответствующие темы.

(Оффтоп)

Спасибо всем, что смотрели на мои страдания))

 Профиль  
                  
 
 Re: Линейный код
Сообщение18.09.2013, 19:22 


14/12/09
306
Букву перепутал :wink:

Mikle1990 в сообщении #762029 писал(а):
$v_{i}=\sum^{k}_{l=1}u_{i}\cdot a_{l, i}$

$v_{i}=\sum^{k}_{l=1}u_{l}\cdot a_{l, i}$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

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



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

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


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

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