8.4: Матриці перевірки парності та генератора
- Page ID
- 64268
Потрібно знайти систематичний спосіб генерації лінійних кодів, а також швидкі методи декодування. Вивчаючи властивості матриці\(H\) і ретельно\(H\text{,}\) вибираючи можна розробити дуже ефективні методи кодування і декодування повідомлень. З цією метою ми введемо стандартні генераторні і канонічні матриці перевірки парності.
Припустимо, що\(H\) це\(m \times n\) матриця з записами в\({\mathbb Z}_2\) і\(n \gt m\text{.}\) Якщо останні\(m\) стовпці матриці утворюють матрицю\(m \times m\) ідентичності,\(I_m\text{,}\) то матриця є канонічною матрицею перевірки парності. Більш конкретно,\(H= (A \mid I_m)\text{,}\) де\(A\) знаходиться\(m \times (n-m)\) матриця
\[ \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n-m} \\ a_{21} & a_{22} & \cdots & a_{2,n-m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{m,n-m} \end{pmatrix} \nonumber \]
і\(I_m\) є матрицею\(m \times m\) ідентичності
\[ \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}\text{.} \nonumber \]
З кожною канонічною матрицею перевірки парності ми можемо зв'язати\(n \times (n-m)\) стандартну матрицю генератора
\[ G = \left( \frac{I_{n-m}}{A} \right)\text{.} \nonumber \]
Нашою метою буде показати, що\(\mathbf x\) задовольняє\(G {\mathbf x} = {\mathbf y}\) існує тоді і лише тоді, коли\(H{\mathbf y} = {\mathbf 0}\text{.}\) задано блок повідомлень, який\({\mathbf x}\) потрібно закодувати, матриця\(G\) дозволить нам швидко закодувати його в лінійне кодове слово.\({\mathbf y}\text{.}\)
Припустимо, що у нас є наступні вісім слів для кодування:
\[ (000), (001), (010), \ldots, (111)\text{.} \nonumber \]
Для
\[ A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\text{,} \nonumber \]
пов'язаний стандартний генератор і канонічні матриці перевірки парності є
\[ G= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \nonumber \]
і
\[ H = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \nonumber \]
відповідно.
Рішення
Зверніть увагу, що рядки в\(H\) представляють перевірку парності на певні бітові позиції в\(6\) -tuple. \(1\)S в матриці ідентичності служать перевіркою парності для\(1\) s в тому ж рядку. Якщо\({\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)\text{,}\) тоді
\[ {\mathbf 0} = H{\mathbf x} = \begin{pmatrix} x_2 + x_3 + x_4 \\ x_1 + x_2 + x_5\\ x_1 + x_3 + x_6 \end{pmatrix}\text{,} \nonumber \]
яка дає систему рівнянь:
\ почати {вирівнювати*} x_2 + x_3 + x_4 & = 0\\ x_1 + x_2 + x_5 & = 0\\ x_1 + x_3 + x_6 & = 0\ текст {.} \ end {вирівнювати*}
Тут\(x_4\) служить контрольним бітом для\(x_2\) і\(x_3\text{;}\)\(x_5\) є контрольним бітом для\(x_1\) і\(x_2\text{;}\) і\(x_6\) є контрольним бітом для\(x_1\) і\(x_3\text{.}\) Матриця ідентичності зберігає\(x_4\text{,}\)\(x_5\text{,}\) і\(x_6\) від необхідності перевіряти один на одного. Отже,\(x_1\text{,}\)\(x_2\text{,}\) і\(x_3\) може бути довільним, але\(x_4\text{,}\)\(x_5\text{,}\) і\(x_6\) повинні бути обрані для забезпечення паритету. Нульовий простір легко обчислюється, щоб бути\(H\)
\[ \begin{array}{cccc} (000000) & (001101) & (010110) & (011011) \\ (100011) & (101110) & (110101) & (111000). \end{array} \nonumber \]
Ще простішим способом обчислення нульового простору є матриця генератора\(G\) (Таблиця\(8.24\)).
\(Table \text { } 8.24\). Код, згенерований матрицею
| Слово повідомлення\(\mathbf x\) | Кодове слово\(G \mathbf x\) |
| \(000\) | \(000000\) |
| \(001\) | \(001101\) |
| \(010\) | \(010110\) |
| \(011\) | \(011011\) |
| \(100\) | \(100011\) |
| \(101\) | \(101110\) |
| \(110\) | \(110101\) |
| \(111\) | \(111000\) |
Якщо\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) є канонічною матрицею перевірки парності, то\(\Null(H)\) складається з усіх,\({\mathbf x} \in {\mathbb Z}_2^n\) чиї перші\(n-m\) біти є довільними, але чиї останні\(m\) біти визначаються\(H{\mathbf x} = {\mathbf 0}\text{.}\) кожним з останні\(m\) біти служать парним бітом перевірки парності для деяких з перших\(n-m\) бітів. Отже,\(H\) породжує код\((n, n-m)\) -block.
Доказ цієї теореми ми залишаємо як вправу. У світлі теореми перші\(n - m\) біти в\({\mathbf x}\) називаються інформаційними бітами, а останні\(m\) - контрольними бітами. У прикладі 8.23 перші три біти є інформаційними бітами, а останні три - контрольними бітами.
Припустимо, що\(G\) це\(n \times k\) стандартна матриця генератора. Потім\(C = \left\{{\mathbf y} : G{\mathbf x} ={\mathbf y}\text{ for }{\mathbf x}\in {\mathbb Z}_2^k\right\}\) - код\((n,k)\) -block. Більш конкретно,\(C\) це груповий код.
- Доказ
-
\(G {\mathbf x}_2 ={\mathbf y}_2\)Дозволяти\(G {\mathbf x}_1 = {\mathbf y}_1\) і бути двома кодовими словами. Тоді\({\mathbf y}_1 + {\mathbf y}_2\) знаходиться\(C\) з тих пір
\[ G( {\mathbf x}_1 + {\mathbf x}_2) = G {\mathbf x}_1 + G {\mathbf x}_2 = {\mathbf y}_1 + {\mathbf y}_2\text{.} \nonumber \]
Ми також повинні показати, що два блоки повідомлень не можуть бути закодовані в одне кодове слово. Тобто ми повинні показати, що якщо\(G {\mathbf x} = G {\mathbf y}\text{,}\) тоді\({\mathbf x} = {\mathbf y}\text{.}\) Припустимо, що\(G {\mathbf x} = G {\mathbf y}\text{.}\) Тоді
\[ G {\mathbf x} - G {\mathbf y} = G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\text{.} \nonumber \]
Однак перші\(k\) координати в\(G( {\mathbf x} - {\mathbf y})\) точності,\(x_1 -y_1, \ldots, x_k - y_k\text{,}\) оскільки вони визначаються матрицею ідентичності,\(I_k\text{,}\) частиною\(G\text{.}\) Отже,\(G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\) саме коли\({\mathbf x} = {\mathbf y}\text{.}\)
Перш ніж ми зможемо довести зв'язок між канонічними матрицями перевірки парності та стандартними матрицями, що генерують, нам потрібно довести лему.
\(H = (A \mid I_m )\)Дозволяти бути\(m \times n\) канонічною матрицею перевірки парності і\(G = \left( \frac{I_{n-m} }{A} \right)\) бути відповідною\(n \times (n-m)\) стандартною матрицею генератора. Тоді\(HG = {\mathbf 0}\text{.}\)
- Доказ
-
Нехай\(C = HG\text{.}\) запис у\(C\) нас\(ij\)
\ почати {вирівнювати*} c_ {ij} & =\ сума_ {k=1} ^n h_ {ik} g_ {kj}\\ & =\ сума {k=1} ^ {n-м} h_ {ik} g_ {kj} +\ sum_ {k=n-м+1} ^n h_ {ik} g_ {kj}\\ & =\ sum_ k=1} ^ {н-м} a_ {ik}\ дельта_ {кдж} +\ сума_ {k=n-м+1} ^n\ дельта_ {i- (м-н), k} a_ {kj}\ & = a_ {ij} + a_ {ij}\\ & = 0\ текст {,}\ кінець {align*}
де
\[ \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} \nonumber \]
- дельта Кронекера.
\(H = (A \mid I_m )\)Дозволяти бути\(m \times n\) канонічною матрицею перевірки парності і нехай\(G = \left( \frac{I_{n-m} }{A} \right) \) буде\(n \times (n-m)\) стандартна матриця генератора, пов'язана з\(H\text{.}\)\(C\) Дозволяти бути код, згенерований\(G\text{.}\) Тоді\({\mathbf y}\) знаходиться в\(C\) якщо і тільки якщо,\(H {\mathbf y} = {\mathbf 0}\text{.}\) зокрема,\(C\) лінійний код з канонічною матрицею перевірки парності\(H\text{.}\)
- Доказ
-
Спочатку припустимо, що\({\mathbf y} \in C\text{.}\) тоді\(G {\mathbf x} = {\mathbf y}\) для деяких\({\mathbf x} \in {\mathbb Z}_2^m\text{.}\) Лемма 8.27,\(H {\mathbf y} = HG {\mathbf x} = {\mathbf 0}\text{.}\)
І навпаки, припустимо, що\({\mathbf y} = (y_1, \ldots, y_n)^\transpose\) знаходиться в нульовому просторі\(H\text{.}\) Ми повинні знайти\({\mathbf x}\) в\({\mathbb Z}_2^{n-m}\) такий, що\(G {\mathbf x}^\transpose = {\mathbf y}\text{.}\) Оскільки\(H {\mathbf y} = {\mathbf 0}\text{,}\) наступний набір рівнянь повинен бути задоволений:
\ почати {вирівнювати*} a_ {11} y_1 + a_ {12} y_2 +\ cdots + a_ {1, n-м} y_ {n-м} + y_ {n-m+1} & = 0\\ a_ {21} y_1 + a_ {22} y_2 +\ cdots + a_ {2, n-m} y_ {2, n-m} y_ {n-m} + y_ {n-м+2} & = 0\\ &\ vdots\\ a_ {m1} y_1 + a_ {м2} y_2 +\ cdots + a_ {m, n-м} y_ {n-м} + y_ {n-м+м} & = 0\ текст {.} \ end {вирівнювати*}
Аналогічно,\(y_{n-m+1}, \ldots, y_n\) визначаються\(y_1, \ldots, y_{n-m}\text{:}\)
\ почати {вирівнювати*} y_ {n-м+1} & = a_ {11} y_1 + a_ {12} y_2 +\ cdots + a_ {1, n-м} y_ {n-м}\\ y_ {n-м+2} & = a_ {21} y_1 + a_ {22} y_2 +\ cdots + a_ {2, н-м} y_ {2} y_ {n-m}\\ &\ vdots\\ y_ {n} & = a_ {m1} y_1 + a_ {м2} y_2 +\ cdots + a_ {m, n-m} y_ {n-m}\ текст {.} \ end {вирівнювати*}
Отже, ми можемо дозволити\(x_i = y_i\)\(i= 1, \ldots, n - m\text{.}\)
Було б корисно, якби ми могли обчислити мінімальну відстань лінійного коду безпосередньо від його\(H\) матриці, щоб визначити можливості виявлення помилок та виправлення помилок коду. Припустимо, що
\ почати {align*} {\ mathbf e} _1 & = (100\ cdots 0) ^\ транспонувати\\ {\ mathbf e} _2 & = (010\ cdots 0) ^\ транспонувати\\ &\ vdots\\ {\ mathbf e} _n & = (000\ cdots 01) ^\ транспонувати\ кінець {align*}
є\(n\) -кортежі у\({\mathbb Z}_2^n\) вазі\(1\text{.}\) Для\(m \times n\) двійкової матриці\(H\text{,}\)\(H{\mathbf e}_i\) - це саме\(i\) той стовпець матриці\(H\text{.}\)
Зауважте, що
\[ \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\text{.} \nonumber \]
Ми констатуємо цей результат у наступній пропозиції і залишаємо доказ як вправу.
\({\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 { . }\
\(H\)Дозволяти\(m \times n\) двійкову матрицю. Тоді нульовий простір\(H\) є єдиним кодом виявлення помилок, якщо і тільки тоді, коли жоден стовпець не\(H\) складається повністю з нулів.
- Доказ
-
Припустимо, що\(\Null(H)\) це єдиний код виявлення помилок. Тоді мінімальна відстань коду повинна бути принаймні\(2\text{.}\) Оскільки нульовий простір є груповим кодом, достатньо вимагати, щоб код не містив кодових слів менше ваги,\(2\) крім нульового кодового слова. Тобто, не\({\mathbf e}_i\) повинно бути кодовим словом для\(i = 1, \ldots, n\text{.}\) Оскільки\(H{\mathbf e}_i\) це\(i\) той стовпець\(H\text{,}\) єдиного способу, яким\({\mathbf e}_i\) може бути в нульовому просторі, якщо\(H\) б у стовпці були всі нулі, що неможливо; отже, код повинен мати можливість\(i\) виявити хоча б поодинокі помилки.
І навпаки, припустимо, що жоден стовпець не\(H\) є нульовим стовпцем. За пропозицією\(8.30\),\(H{\mathbf e}_i \neq {\mathbf 0}\text{.}\)
Якщо розглядати матриці
\[ H_1 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
і
\[ H_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \nonumber \]
Рішення
то нульовий простір\(H_1\) є єдиним кодом виявлення помилок, а нульовий простір не\(H_2\) є.
Ми навіть можемо зробити краще, ніж теорема\(8.31\). Ця теорема дає нам умови на матриці\(H\), які говорять нам, коли мінімальна вага коду, утвореного нульовим простором,\(H\) є\(2\text{.}\) Ми також можемо визначити, коли мінімальна відстань лінійного коду,\(3\) досліджуючи відповідну матрицю.
Якщо ми дозволимо
\[ H = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} \nonumber \]
і хочете визначити, чи\(H\) є канонічною матрицею перевірки парності для коду, що виправляє помилки,
Рішення
необхідно переконатися, що\(\Null(H)\) не містить ніяких\(4\) -кортежі ваги\(2\text{.}\) Тобто,\((1100)\text{,}\)\((1010)\text{,}\)\((1001)\text{,}\)\((0110)\text{,}\)\((0101)\text{,}\) і не\((0011)\) повинно бути в Наступна теорема\(\Null(H)\text{.}\) стверджує, що ми дійсно можемо визначити, що код, згенерований \(H\)виправляє помилки, вивчаючи стовпці\(H\text{.}\) Notice в цьому прикладі, що не тільки не\(H\) має нульових стовпців, але і те, що немає двох стовпців однакових.
\(H\)Дозволяти двійкову матрицю. Нульовий простір\(H\) - це єдиний код, що виправляє помилки, якщо і тільки тоді, коли\(H\) не містить жодних нульових стовпців і жодних двох стовпців\(H\) однакових.
- Доказ
-
\(n\)-кортеж\({\mathbf e}_{i} +{\mathbf e}_{j}\) має\(1\) s в\(i\) ї і\(j\) й записи і 0s в іншому місці, і\(w( {\mathbf e}_{i} +{\mathbf e}_{j}) = 2\) для\(i \neq j\text{.}\) Since
\[ {\mathbf 0} = H({\mathbf e}_{i} +{\mathbf e}_{j}) = H{\mathbf e}_{i} + H{\mathbf e}_{j} \nonumber \]
може відбуватися тільки в тому випадку, якщо\(i\)\(j\) th і th стовпці ідентичні, нульовий простір\(H\) - це єдиний код, що виправляє помилки.
Припустимо, що тепер у нас є канонічна матриця перевірки парності\(H\) з трьома рядками. Тоді ми могли б запитати, скільки ще стовпців ми можемо додати до матриці і все ще мають нульовий простір, який є єдиним виявленням помилок і єдиним кодом виправлення помилок. Оскільки кожен стовпець містить три записи,\(2^3 = 8\) можливі різні стовпці. Ми не можемо додати стовпці
\[ \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\text{.} \nonumber \]
Таким чином, ми можемо додати цілих чотири стовпці і як і раніше підтримувати мінімальну відстань\(3\text{.}\)
Взагалі, якщо\(H\)\(m \times n\) канонічна матриця перевірки парності, то в кожному кодовому слові є\(n-m\) інформаційні позиції. Кожен стовпець має\(m\) біти, тому\(2^m\) можливі різні стовпці. Необхідно,\({\mathbf 0}, {\mathbf e}_1, \ldots, {\mathbf e}_m\) щоб стовпці були виключені,\(2^m - (1 + m)\) залишаючи інші стовпці для інформації, якщо ми все ще збережемо можливість не тільки виявляти, але і виправляти поодинокі помилки.