8.7: Вправи

1

Чому наступна схема кодування не прийнятна?

Інформація	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)
Кодове слово	\(000\)	\(001\)	\(010\)	\(011\)	\(101\)	\(110\)	\(111\)	\(000\)	\(001\)

2

Не роблячи жодного додавання, поясніть, чому наступний набір\(4\) -кортежів в\({\mathbb Z}_2^4\) не може бути кодом групи.

\[ (0110) \quad (1001) \quad (1010) \quad (1100) \nonumber \]

3

Обчислити відстані Хеммінга між наступними парами\(n\) -кортежів.

1. \(\displaystyle (011010), (011100)\)
2. \(\displaystyle (11110101), (01010100)\)
3. \(\displaystyle (00110), (01111)\)
4. \(\displaystyle (1001), (0111)\)

4

Обчислити ваги наступних\(n\) -кортежів.

1. \(\displaystyle (011010)\)
2. \(\displaystyle (11110101)\)
3. \(\displaystyle (01111)\)
4. \(\displaystyle (1011)\)

5

Припустимо, що лінійний код\(C\) має мінімальну вагу\(7\text{.}\) Що таке можливості виявлення помилок та виправлення помилок\(C\text{?}\)

6

У кожному з наступних кодів, яка мінімальна відстань для коду? На яку найкращу ситуацію ми можемо сподіватися у зв'язку з виявленням помилок та виправленням помилок?

1. \(\displaystyle (011010) \; (011100) \; (110111) \; (110000)\)
2. \(\displaystyle (011100) \; (011011) \; (111011) \; (100011) \\ (000000) \; (010101) \; (110100) \; (110011)\)
3. \(\displaystyle (000000) \; (011100) \; (110101) \; (110001)\)
4. \(\displaystyle (0110110) \; (0111100) \; (1110000) \; (1111111) \\ (1001001) \; (1000011) \; (0001111) \; (0000000)\)

7

Обчислити нульовий простір кожної з наступних матриць. Який тип\((n,k)\) -block кодів є нульовими пробілами? Чи можете ви знайти матрицю (не обов'язково стандартну матрицю генератора), яка генерує кожен код? Чи унікальні ваші матриці генератора?

1. \[ \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \nonumber \]
2. \[ \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
3. \[ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \nonumber \]
4. \[ \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \end{pmatrix} \nonumber \]

8

Побудувати код\((5,2)\) -block. Обговоріть можливості виявлення помилок та виправлення помилок вашого коду.

9

\(C\)Дозволяти код, отриманий з нульового простору матриці

\[ H = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}\text{.} \nonumber \]

Розшифрувати повідомлення

\[ 01111 \quad 10101 \quad 01110 \quad 00011 \nonumber \]

якщо це можливо.

10

Припустимо, що передається\(1000\) бітове двійкове повідомлення. Припустимо, що ймовірність однієї помилки є\(p\) і що помилки, що виникають в різних бітах, не залежать один від одного. Якщо\(p = 0.01\text{,}\) яка ймовірність виникнення більш ніж однієї помилки? Яка ймовірність виникнення рівно двох помилок? Повторіть цю проблему для\(p = 0.0001\text{.}\)

11

Які матриці є канонічними матрицями перевірки парності? Для тих матриць, які є канонічними матрицями перевірки парності, які відповідні стандартні матриці генератора? Які можливості виявлення помилок та виправлення помилок у коду, що генерується кожною з цих матриць?

1. \[ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
2. \[ \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
3. \[ \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
4. \[ \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]

12

Перерахуйте всі можливі синдроми для кодів, створених кожною з матриць у Вправі\(8.6.11\).

13

Нехай

\[ H = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \end{pmatrix}\text{.} \nonumber \]

Обчислити синдром, викликаний кожною з наступних помилок передачі.

1. Помилка в першому біті.
2. Помилка в третьому біті.
3. Помилка в останньому біті.
4. Помилки в третьому і четвертому бітах.

14

\(C\)Дозволяти код групи в\({\mathbb Z}_2^3\) визначається кодовими словами\((000)\) і\((111)\text{.}\) Обчислити косети\(C\) в\({\mathbb Z}_2^3\text{.}\) Чому не було необхідності вказувати праві або ліві косети? Дайте одиничну похибку передачі, якщо така є, якій відповідає кожна косет.

15

Для кожної з наступних матриць знайдіть косети відповідного коду.\(C\text{.}\) Дайте таблицю декодування для кожного коду, якщо це можливо.

1. \[ \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \nonumber \]
2. \[ \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
3. \[ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \nonumber \]
4. \[ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} \nonumber \]

16

\({\mathbf z}\)Дозволяти\({\mathbf x}\text{,}\)\({\mathbf y}\text{,}\) і бути\(n\) двійковими -кортежами. Доведіть кожне з наступних тверджень.

1. \(\displaystyle w({\mathbf x}) = d( {\mathbf x}, {\mathbf 0})\)
2. \(\displaystyle d( {\mathbf x}, {\mathbf y}) = d( {\mathbf x} + {\mathbf z}, {\mathbf y} + {\mathbf z} )\)
3. \(\displaystyle d({\mathbf x}, {\mathbf y}) = w({\mathbf x}- {\mathbf y})\)

17

Метрика на множині\(X\) - це карта, яка\(d: X \times X \rightarrow {\mathbb R}\) задовольняє наступним умовам.

1. \(d( {\mathbf x}, {\mathbf y}) \geq 0\)для всіх\({\mathbf x}, {\mathbf y} \in X\text{;}\)
2. \(d( {\mathbf x}, {\mathbf y}) = 0\)саме коли\({\mathbf x} = {\mathbf y}\text{;}\)
3. \(d( {\mathbf x}, {\mathbf y})= d( {\mathbf y}, {\mathbf x})\text{;}\)
4. \(d( {\mathbf x}, {\mathbf y}) \leq d( {\mathbf x}, {\mathbf z}) + d( {\mathbf z}, {\mathbf y})\text{.}\)

Іншими словами, метрика - це просто узагальнення поняття відстані. Доведіть, що відстань Хеммінга є метрикою на\({\mathbb Z}_2^n\text{.}\) Розшифровка повідомлення насправді зводиться до вирішення, яке найближче кодове слово з точки зору відстані.

18

\(C\)Дозволяти лінійний код. Показати, що або\(i\) ті координати в кодових словах\(C\) є нулями, або рівно половина з них дорівнює нулям.

19

\(C\)Дозволяти лінійний код. Покажіть, що або кожне кодове слово має рівну вагу або рівно половина кодових слів мають рівну вагу.

20

Показати, що кодові слова парної ваги в лінійному коді також\(C\) є лінійним кодом.

21

Якщо ми хочемо використовувати лінійний код, що виправляє помилки, для передачі 128 символів ASCII, яку матрицю розміру потрібно використовувати? Який розмір матриці необхідно використовувати для передачі розширеного набору символів ASCII з 256 символів? Що робити, якщо нам потрібно лише виявлення помилок в обох випадках?

22

Знайдіть канонічну матрицю перевірки парності, яка дає рівний код перевірки парності з трьома інформаційними позиціями. Що таке матриця для семи інформаційних позицій? Які відповідні стандартні матриці генераторів?

23

Скільки чекових позицій потрібно для одного коду виправлення помилок з 20 інформаційними позиціями? З 32 інформаційними позиціями?

24

\({\mathbf e}_i\)Дозволяти двійковий\(n\) -кортеж з a\(1\) в\(i\) ї координати і\(0\) в іншому місці і припустимо, що\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Показати, що\(H{\mathbf e}_i\) це\(i\) -й стовпець матриці\(H\text{.}\)

25

\(C\)Дозволяти бути\((n,k)\) -лінійний код. Визначте подвійний або ортогональний код\(C\) to be

\[ C^\perp = \{ {\mathbf x} \in {\mathbb Z}_2^n : {\mathbf x} \cdot {\mathbf y} = 0 \text{ for all } {\mathbf y} \in C \}\text{.} \nonumber \]

1. Знайти подвійний код лінійного коду\(C\), де\(C\) задається матрицею

   \[ \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}\text{.} \nonumber \]

2. Показати, що\(C^\perp\) це\((n, n-k)\) -лінійний код.
3. Знайдіть стандартний генератор і матриці перевірки парності\(C\) і\(C^\perp\text{.}\) Що взагалі відбувається? Доведіть свою здогадку.

26

\(H\)Дозволяти\(m \times n\) матриця над\({\mathbb Z}_2\text{,}\) де\(i\) th стовпець - це число,\(i\) записане в двійковій системі з\(m\) бітами. Нульовий простір такої матриці називається кодом Хеммінга.

1. Показати, що матриця

   \[ H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \nonumber \]

   генерує код Хеммінга. Які властивості коду Хеммінга виправляють помилки?

2. Колонка, відповідна синдрому, також позначає біт, який був помилковим; тобто\(i\) той стовпець матриці\(i\) записується як двійкове число, а синдром відразу говорить нам, який біт знаходиться в помилці. Якщо отримане слово\((101011)\text{,}\) обчислити синдром. В якому розряді виникла помилка в даному випадку, і яке кодове слово спочатку передавалося?
3. Двійкову матрицю\(H\) для коду Хеммінга з шістьма інформаційними позиціями і чотирма контрольними позиціями. Що таке чекові позиції та які інформаційні позиції? Кодувати повідомлення\((101101)\) і\((001001)\text{.}\) розшифрувати отримані слова\((0010000101)\) і\((0000101100)\text{.}\) Які можливі синдроми для цього коду?
4. Яка кількість контрольних бітів та кількість інформаційних бітів у коді Хеммінга\((m,n)\) -block? Дайте як верхню, так і нижню межу на кількість інформаційних бітів через кількість контрольних бітів. Коди Хеммінга, що мають максимально можливу кількість інформаційних бітів з\(k\) контрольними бітами, називаються ідеальними. Кожен можливий синдром крім\({\mathbf 0}\) виникає у вигляді колони. Якщо кількість інформаційних бітів менше максимального, то код називається скороченим. У цьому випадку наведемо приклад, який показує, що деякі синдроми можуть представляти множинні помилки.