63701 (695429), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Помножимо обидві частини рівності, що визначає цей багаточлен, на і покладемо . Тоді ліва частина звернеться в нуль, і ми одержимо

або

.

Ця рівність виконується при кожному l і при кожному j. Підсумуємо ці рівності по l від 1 до v. Для кожного j це дає

Або

Кожна сума в лівій частині останньої рівності є компонентом синдрому, так що рівняння приводиться до виду

Тому що , то для j в інтервалі всі індекси задають відомі компоненти синдрому. Таким чином, одержуємо систему рівнянь

,

тобто систему лінійних рівнянь, що зв'язує компоненти синдрому з коефіцієнтами багаточлена (х). Якщо матриця невироджена, то цю систему можна вирішити шляхом Рисунок 1 - Декодер Питерсона-Горенстейна-Цирлера.

Оскільки число елементів поля обмежено, звичайно найпростішим шляхом знаходження корінь багаточлена є метод проб і помилок, відомий як процедура Ченя. Ця процедура складається просто в послідовному обчисленні для кожного j і перевірки отриманих значень на нуль. Найбільш простим способом обчислення значення в точці є схема Горнера:

.

Для обчислення за схемою Горнера потрібно тільки v множень і v додавань.

Як приклад процедури декодування, розглянемо декодування (15,5)-коду БЧХ, що виправляє три помилки і має породжуючий багаточлен g(х) = х10 + х9 + х6 + х4 + х2 + х + 1.

Алгоритм декодування представлений на рис. 1.

Для приклада будемо вважати прийнятий багаточлен рівним v(х) = x7 + x2. Ясно, що якби відбулося не більше трьох помилок, то кодове слово повинно було б бути нульовим і v(х) = е(х), але декодер не може зробити такого висновку. Виконаємо всі кроки алгоритму декодування. Спочатку обчислимо компоненти синдрому, використовуючи арифметику в полі GF(16):

Нехай v = 3, тоді

Визначник М дорівнює нулю; отже, припускаємо v = 2. Тоді

Визначник не дорівнює нулю; отже, відбулося дві помилки. Далі,

та

отже,

Використовуючи процедуру Ченя, одержуємо розкладання

Багаточлен локаторів помилок має корні й , а локатори помилок дорівнюють елементам, зворотним корінням. Таким чином, помилки відбулися в другій і сьомій позиціях. Оскільки код є двійковим, значення помилок рівні 1 і .

Характеристики

Список файлов реферата