БЧХ: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Shynkar (обговорення | внесок) |
Shynkar (обговорення | внесок) |
||
Рядок 18: | Рядок 18: | ||
* Визначає характер помилки |
* Визначає характер помилки |
||
* Виправляє помилки |
* Виправляє помилки |
||
==Обчислення синдрому помилки== |
|||
Обчислення синдрому помилки виконується синдромних декодером, який ділить кодове слово на породжувальний многочлен. Якщо виникає залишок, то у слові є помилка. Залишок від ділення є синдромом помилки. |
|||
==Побудова полінома помилки== |
|||
Обчислений синдром помилки не вказує на становище помилок. Ступінь полінома синдрому дорівнює 2t, що багато менше ступеня кодового слова n. Для отримання відповідності між помилкою і її положенням у повідомленні будується поліном помилок. Поліном помилок реалізується за допомогою алгоритму Берлекемпа - Мессі, або за допомогою алгоритму Евкліда. Алгоритм Евкліда має просту реалізацію, але вимагає великих витрат ресурсів. Тому частіше застосовується більш складний, але менш затратний алгоритм Берлекемпа - Мессі. Коефіцієнти знайденого полінома безпосередньо відповідають коефіцієнтам помилкових символів у кодовому слові. |
|||
==Знаходження коренів== |
|||
На цьому етапі шукаються корені полінома помилки, що визначають положення спотворених символів в кодовому слові. Реалізується за допомогою процедури Ченя, повним перебором. У поліном помилок послідовно підставляються всі можливі значення, коли поліном звертається в нуль - корені знайдені. |
|||
== Див. також == |
== Див. також == |
Версія за 10:28, 12 квітня 2013
Коди Боуза - Чоудхурі - Хоквінгема (БЧХ-коди, англ. BCH code) - в теорії кодування це широкий клас циклічних кодів, що застосовуються для захисту інформації від помилок (див. Попередня корекція помилок). Відрізняється можливістю побудови коду із заздалегідь визначеними коригувальними властивостями, а саме, мінімальною кодовою відстанню. Окремим випадком БЧХ-кодів є Код Ріда-Соломона.
Код винайшов в 1959 році А.Хоквінгем (Hocquenghem), і незалежноно в 1960 році Р.Боуз (Bose) і Д.Рой-Чоудхурі (Ray-Chaudhuri). Код отримав свою назву (BCH code) від прізвищ їх авторів.
Коди БЧХ є узагальненням кодів Хеммінга і дозволяють виправляти кратні помилки.
Методи декодування
Коди БЧХ є циклічними кодами, тому до них застосовні всі методи, використовувані для декодування циклічних кодів. Однак існують набагато кращі алгоритми, розроблені саме для БЧХ-кодів.
Головною ідеєю в декодуванні БЧХ кодів є використання елементів кінцевого поля для нумерації позицій кодового слова (або, еквівалентно, в порядку коефіцієнтів асоційованого многочлена).
Декодування
Декодер, що працює по авторегресивному спектральному методу декодування, послідовно виконує наступні дії:
- Обчислює синдром помилки
- Будує поліном помилки
- Знаходить корені даного полінома
- Визначає характер помилки
- Виправляє помилки
Обчислення синдрому помилки
Обчислення синдрому помилки виконується синдромних декодером, який ділить кодове слово на породжувальний многочлен. Якщо виникає залишок, то у слові є помилка. Залишок від ділення є синдромом помилки.
Побудова полінома помилки
Обчислений синдром помилки не вказує на становище помилок. Ступінь полінома синдрому дорівнює 2t, що багато менше ступеня кодового слова n. Для отримання відповідності між помилкою і її положенням у повідомленні будується поліном помилок. Поліном помилок реалізується за допомогою алгоритму Берлекемпа - Мессі, або за допомогою алгоритму Евкліда. Алгоритм Евкліда має просту реалізацію, але вимагає великих витрат ресурсів. Тому частіше застосовується більш складний, але менш затратний алгоритм Берлекемпа - Мессі. Коефіцієнти знайденого полінома безпосередньо відповідають коефіцієнтам помилкових символів у кодовому слові.
Знаходження коренів
На цьому етапі шукаються корені полінома помилки, що визначають положення спотворених символів в кодовому слові. Реалізується за допомогою процедури Ченя, повним перебором. У поліном помилок послідовно підставляються всі можливі значення, коли поліном звертається в нуль - корені знайдені.