8.5: Ефективне декодування
- Page ID
- 64267
Зараз ми знаходимося на етапі, коли ми можемо генерувати лінійні коди, які досить легко виявляють та виправляють помилки, але все ще трудомісткий процес декодування отриманого\(n\) -кортежу та визначення того, який є найближчим кодовим словом, оскільки отриманий\(n\) -кортеж потрібно порівнювати з кожним можливим кодове слово для визначення правильної розшифровки. Це може стати серйозною перешкодою, якщо код дуже великий.
Задано двійкову матрицю
і\(5\) кортежі\({\mathbf x} = (11011)^{t}\) і\({\mathbf y} = (01011)^{t}\text{,}\)
Рішення
ми можемо обчислити
Отже,\({\mathbf x}\) є кодовим словом і не\({\mathbf y}\) є, так як\({\mathbf x}\) знаходиться в нульовому просторі і\({\mathbf y}\) немає. Зверніть увагу,\(H{\mathbf y}\) що ідентично першому стовпчику\(H\text{.}\) Насправді, саме тут сталася помилка. Якщо ми перевертаємо перший біт\({\mathbf y}\) від\(0\) до,\(1\text{,}\) то отримаємо\({\mathbf x}\text{.}\)
Якщо\(H\)\(m \times n\) матриця і\({\mathbf x} \in {\mathbb Z}_2^n\text{,}\) тоді ми говоримо, що синдром\({\mathbf x}\) є\(H{\mathbf x}\text{.}\) Наступна пропозиція дозволяє швидко виявити і виправити помилки.
Нехай\(m \times n\) двійкова матриця\(H\) визначає лінійний код і нехай\({\mathbf x}\) буде отриманий\(n\) -кортеж. Пишіть\({\mathbf x}\) як\({\mathbf x} = {\mathbf c} +{\mathbf e}\text{,}\) де\({\mathbf c}\) передане кодове слово і\({\mathbf e}\) є помилкою передачі. Тоді синдром\(H{\mathbf x}\) отриманого кодового слова\({\mathbf x}\) - це теж синдром помилки.\({\mathbf e}\text{.}\)
- Доказ
-
Доказ випливає з того, що
\[ H{\mathbf x} = H({\mathbf c} +{\mathbf e}) = H{\mathbf c} + H{\mathbf e} = {\mathbf 0} + H{\mathbf e} = H{\mathbf e}\text{.} \nonumber \]
Це судження говорить нам про те, що синдром прийнятого слова залежить виключно від помилки, а не від переданого кодового слова. Доказ наступної теореми випливає відразу з Пропозиції\(8.36\) і з того, що\(H{\mathbf e}\) є\(i\) м стовпцем матриці.\(H\text{.}\)
Нехай\(H \in {\mathbb M}_{ m \times n} ( {\mathbb Z}_2)\) і припустимо, що лінійний код, що відповідає\(H\) є єдиним виправленням помилок. \({\mathbf r}\)Дозволяти бути отриманим\(n\) -кортеж, який був переданий щонайменше з однією помилкою. Якщо синдром\({\mathbf r}\) є\({\mathbf 0}\text{,}\) то помилки не сталося; в іншому випадку, якщо синдром\({\mathbf r}\) дорівнює якомусь стовпчику\(H\text{,}\) скажімо\(i\) го стовпця, то помилка сталася в \(i\)го біт
Розглянемо матрицю
і припустимо, що\(6\) -кортежі\({\mathbf x} = (111110)^{t}\text{,}\)\({\mathbf y} = (111111)^{t}\text{,}\) і\({\mathbf z} = (010111)^{t}\) були отримані.
Рішення
Тоді
Отже,\({\mathbf x}\) має помилку в третьому біті і\({\mathbf z}\) має помилку в четвертому біті. Передані кодові слова для\({\mathbf x}\) і\({\mathbf z}\) must були\((110110)\) і\((010011)\text{,}\) відповідно. Синдром\({\mathbf y}\) не виникає ні в одному з стовпців матриці,\(H\text{,}\) тому множинні помилки повинні були виникнути, щоб спричинити\({\mathbf y}\text{.}\)
Розшифровка косетів
Ми можемо використовувати теорію груп для отримання іншого способу декодування повідомлень. Лінійний код\(C\) - це підгрупа\({\mathbb Z}_2^n\text{.}\) Coset або стандартне декодування використовує косети\(C\) in\({\mathbb Z}_2^n\) для реалізації декодування з максимальною ймовірністю. Припустимо, що\(C\) це\((n,m)\) -лінійний код. Косет in\({\mathbb Z}_2^n\) пишеться\(C\) у вигляді,\({\mathbf x} + C\text{,}\) де\({\mathbf x} \in {\mathbb Z}_2^n\text{.}\) За теоремою Лагранжа (теорема\(6.10\)) існують\(2^{n-m}\) різні косети\(C\) in\({\mathbb Z}_2^n\text{.}\)
\(C\)Дозволяти\((5,3)\) - лінійний код, заданий матрицею перевірки парності
Рішення
Код складається з кодових слів
Є\(2^{5-2} = 2^3\) косети\(C\) в\({\mathbb Z}_2^5\text{,}\) кожному з порядком\(2^2 =4\text{.}\) Ці косети наведені в табл\(8.40\).
\(Table \text { } 8.40.\)Косети з\(C\)
| Косет | Косет |
| Представник | |
| \(C\) | \((00000) (01101) (10011) (11110)\) |
| \((10000) + C\) | \((10000) (11101) (00011) (01110)\) |
| \((01000) + C\) | \((01000) (00101) (11011) (10110)\) |
| \((00100) + C\) | \((00100) (01001) (10111) (11010)\) |
| \((00010) + C\) | \((00010) (01111) (10001) (11100)\) |
| \((00001) + C\) | \((00001) (01100) (10010) (11111)\) |
| \((10100) + C\) | \((00111) (01010) (10100) (11001)\) |
| \((00110) + C\) | \((00110) (01011) (10101) (11000)\) |
Наше завдання - з'ясувати, як знання косетів може допомогти нам розшифрувати повідомлення. Припустимо, що\({\mathbf x}\) було відправлено оригінальне кодове слово, і\({\mathbf r}\) це\(n\) -кортеж отриманий. Якщо\({\mathbf e}\) помилка передачі, то\({\mathbf r} = {\mathbf e} + {\mathbf x}\) або, еквівалентно,\({\mathbf x} = {\mathbf e} + {\mathbf r}\text{.}\) Однак, це саме те твердження, яке\({\mathbf r}\) є елементом у косеті.\({\mathbf e} + C\text{.}\) У декодуванні з максимальною ймовірністю ми очікуємо, що помилка\({\mathbf e}\)\({\mathbf e}\) буде якомога меншою; тобто матиме найменшу вагу. \(n\)-кортеж найменшої ваги в косеті називається лідером косети. Після того, як ми визначили лідера косети для кожної косети, процес декодування стає завданням обчислення\({\mathbf r} + {\mathbf e}\) для отримання\({\mathbf x}\text{.}\)
У таблиці 8.40 зверніть увагу, що ми вибрали представника найменшої можливої ваги для кожної косети.
Рішення
Ці представники є косетними лідерами. Тепер припустимо, що\({\mathbf r} = (01111)\) це отримане слово. Для декодування\({\mathbf r}\text{,}\) ми виявляємо, що він знаходиться в косеті,\((00010) + C\text{;}\) отже, спочатку передане кодове слово повинно бути\((01101) = (01111) + (00010)\text{.}\)
Потенційна проблема з цим методом декодування полягає в тому, що нам, можливо, доведеться вивчити кожну косету для отриманого кодового слова. Наступна пропозиція дає метод реалізації косетного декодування. У ньому зазначено, що ми можемо пов'язати синдром з кожною косетою; отже, ми можемо скласти таблицю, яка позначає лідера косети, відповідного кожному синдрому. Такий список називається таблицею розшифровки.
\(Table \text { } 8.42\). Синдроми для кожного косету
| Синдром | Лідер косету |
| \((000)\) | \((00000)\) |
| \((001)\) | \((00001)\) |
| \((010)\) | \((00010)\) |
| \((011)\) | \((10000)\) |
| \((100)\) | \((00100)\) |
| \((101)\) | \((01000)\) |
| \((110)\) | \((00110)\) |
| \((111)\) | \((10100)\) |
\(C\)Дозволяти бути\((n,k)\) -лінійний код, заданий матрицею\(H\) і припустимо, що\({\mathbf x}\) і\({\mathbf y}\) знаходяться в\({\mathbb Z}_2^n\text{.}\) Тоді\({\mathbf x}\) і\({\mathbf y}\) знаходяться в той самий coset\(C\) якщо і тільки якщо\(H{\mathbf x} = H{\mathbf y}\text{.}\) Тобто, два\(n\) -кортежі знаходяться в одному косеті, якщо і тільки тоді, коли їх синдроми однакові.
- Доказ
-
Два\(n\) -кортежі\({\mathbf x}\) і\({\mathbf y}\) знаходяться в одному косеті\(C\) точно, коли,\({\mathbf x} - {\mathbf y} \in C\text{;}\) однак, це еквівалентно\(H({\mathbf x} - {\mathbf y}) = 0\) або\(H {\mathbf x} = H{\mathbf y}\text{.}\)
Таблиця\(8.42\) - це таблиця декодування коду,\(C\) наведеного в прикладі\(8.39\). Якщо\({\mathbf x} = (01111)\) отримано,
Рішення
то його синдром можна обчислити, щоб бути
Розглядаючи таблицю розшифровки, визначаємо, що лідером косети\((00010)\text{.}\) є тепер легко розшифрувати отримане кодове слово.
З огляду на код\((n,k)\) -block, виникає питання про те, чи є декодування косетів керованою схемою. Таблиця декодування вимагає списку косетів і синдромів, по одному для кожної з\(2^{n - k}\) косетів\(C\text{.}\) Припустимо, що у нас є код\((32, 24)\) -block. У нас величезна кількість кодових слів,\(2^{24}\text{,}\) але є тільки\(2^{32 - 24} = 2^{8} = 256\) косети.