Линейный код

[Mikle1990]

Задача 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$

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

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

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

[warlock66613]

По-идее, матрица проверочных элеметов - это часть производящей матрицы. К ней надо слева дописать единичную матрицу:

$$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 --

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

[Mikle1990]

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}$

(Оффтоп)

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

[Mikle1990]

Попробую изложить свои мысли относительно системы уравнений, задающих символы кода $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}$ ", имелось ввиду именно то, что я написал выше?

[Mikle1990]

Исходя из той системы уравнений, которую я получил, можно построить кодовую таблицу (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}$$

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

(Оффтоп)

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

[Mikle1990]

Букву перепутал

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}$