Відмінності між версіями «БЧХ»

[неперевірена версія][неперевірена версія]
 
(Не показані 12 проміжних версій 9 користувачів)
Рядок 1: Рядок 1:
{{Без джерел|дата=червень 2017}}
'''Коди Боуза - Чоудхурі - Хоквінгема''' (БЧХ-коди, {{lang-en|BCH code}}) - в теорії [[кодування]] це широкий клас циклічних кодів, що застосовуються для захисту інформації від помилок (див. [[Попередня корекція помилок]]). Відрізняється можливістю побудови коду із заздалегідь визначеними коригувальними властивостями, а саме, мінімальною кодовою відстанню. Окремим випадком БЧХ-кодів є [[Код Ріда-Соломона]].<br>

Код винайшов в 1959 році А.Хоквінгем (Hocquenghem), і незалежноно в 1960 році Р.Боуз (Bose) і Д.Рой-Чоудхурі (Ray-Chaudhuri). Код отримав свою назву (BCH code) від прізвищ їх авторів.<br>
'''Коди Боуза&nbsp;— Чоудхурі&nbsp;— Хоквінгема''' (БЧХ-коди, {{lang-en|BCH code}})&nbsp;— в [[Теорія кодування|теорії кодування]] це широкий клас [[Циклічний надлишковий код|циклічних кодів]], що застосовуються для захисту інформації від помилок (див. [[Попередня корекція помилок]]). Окремим випадком БЧХ-кодів є [[Код Ріда-Соломона]].

Код винайшов в 1959 році А.Хоквінгем (Hocquenghem), і незалежно в 1960 році Р.Боуз (Bose) і Д.Рой-Чоудхурі (Ray-Chaudhuri). Код отримав свою назву (BCH code) від прізвищ їх авторів.

Коди БЧХ є узагальненням [[Коди Хеммінга|кодів Хеммінга]] і дозволяють виправляти кратні помилки.
Коди БЧХ є узагальненням [[Коди Хеммінга|кодів Хеммінга]] і дозволяють виправляти кратні помилки.


Рядок 7: Рядок 11:
Коди БЧХ є циклічними кодами, тому до них застосовні всі методи, використовувані для декодування циклічних кодів. Однак існують набагато кращі алгоритми, розроблені саме для БЧХ-кодів.
Коди БЧХ є циклічними кодами, тому до них застосовні всі методи, використовувані для декодування циклічних кодів. Однак існують набагато кращі алгоритми, розроблені саме для БЧХ-кодів.


Головною ідеєю в декодуванні БЧХ кодів є використання елементів [[Поле Галуа|кінцевого поля]] для нумерації позицій кодового слова (або, еквівалентно, в порядку коефіцієнтів асоційованого многочлена).
Головною ідеєю в декодуванні БЧХ кодів є використання елементів [[Поле Галуа|скінченного поля]] для нумерації позицій кодового слова (або, еквівалентно, в порядку коефіцієнтів асоційованого многочлена).


==Декодування==
==Декодування==
Рядок 21: Рядок 25:
==Обчислення синдрому помилки==
==Обчислення синдрому помилки==


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

==Побудова полінома помилки==
==Побудова полінома помилки==


Обчислений синдром помилки не вказує на становище помилок. Ступінь полінома синдрому дорівнює 2t, що багато менше ступеня кодового слова n. Для отримання відповідності між помилкою і її положенням у повідомленні будується поліном помилок. Поліном помилок реалізується за допомогою алгоритму Берлекемпа - Мессі, або за допомогою алгоритму Евкліда. Алгоритм Евкліда має просту реалізацію, але вимагає великих витрат ресурсів. Тому частіше застосовується більш складний, але менш затратний алгоритм Берлекемпа - Мессі. Коефіцієнти знайденого полінома безпосередньо відповідають коефіцієнтам помилкових символів у кодовому слові.
Обчислений синдром помилки не вказує на становище помилок. Ступінь полінома синдрому дорівнює 2t, що багато менше ступеня кодового слова n. Для отримання відповідності між помилкою і її положенням у повідомленні будується поліном помилок. Поліном помилок реалізується за допомогою алгоритму Берлекемпа&nbsp;— Мессі, або за допомогою [[Алгоритм Евкліда|алгоритму Евкліда]]. Алгоритм Евкліда має просту реалізацію, але вимагає великих витрат ресурсів. Тому частіше застосовується більш складний, але менш затратний [[алгоритм Берлекемпа - Мессі]]. Коефіцієнти знайденого полінома безпосередньо відповідають коефіцієнтам помилкових символів у кодовому слові.

==Знаходження коренів==
==Знаходження коренів==


На цьому етапі шукаються корені полінома помилки, що визначають положення спотворених символів в кодовому слові. Реалізується за допомогою процедури Ченя, повним перебором. У поліном помилок послідовно підставляються всі можливі значення, коли поліном звертається в нуль - корені знайдені.
На цьому етапі шукаються корені полінома помилки, що визначають положення спотворених символів в кодовому слові. Реалізується за допомогою процедури Ченя, повним перебором. У поліном помилок послідовно підставляються всі можливі значення, коли поліном звертається в нуль&nbsp;— корені знайдені.


==Визначення характеру помилки і її виправлення==
==Визначення характеру помилки і її виправлення==
По синдрому помилки і знайденим кореням полінома за допомогою алгоритму Форні визначається характер помилки і будується маска спотворених символів.<br>
По синдрому помилки і знайденим кореням полінома за допомогою алгоритму Форні визначається характер помилки і будується маска спотворених символів.<br>Після того як маска знайдена, вона накладається на кодове слово за допомогою операції [[XOR]] і спотворені символи відновлюються. Після цього відкидаються перевірочні символи і виходить відновлене інформаційне слово.
Після того як маска знайдена, вона накладається на кодове слово за допомогою операції XOR і спотворені символи відновлюються. Після цього відкидаються перевірочні символи і виходить відновлене інформаційне слово.


== Див. також ==
== Див. також ==
*[[Виявлення і виправлення помилок]]


== Посилання ==
== Посилання ==
*[http://posibnyky.vntu.edu.ua/e_s/index.htm Електронні cистеми: навчальний посібник / Й. Й. Білинський, К. В. Огороднік, М. Й. Юкиш. – Вінниця : ВНТУ, 2011. – 208 с.]
*[https://web.archive.org/web/20170531035748/http://posibnyky.vntu.edu.ua/e_s/index.htm Електронні системи: навчальний посібник / Й. Й. Білинський, К. В. Огороднік, М. Й. Юкиш. – Вінниця : ВНТУ, 2011. – 208 с.]


[[Категорія:Інформаційні технології]]


{{Доробити}}
{{Доробити}}

[[Категорія:Виявлення та виправлення помилок]]
[[Категорія:Теорія кодування]]

Поточна версія на 07:35, 19 червня 2020

Коди Боуза — Чоудхурі — Хоквінгема (БЧХ-коди, англ. BCH code) — в теорії кодування це широкий клас циклічних кодів, що застосовуються для захисту інформації від помилок (див. Попередня корекція помилок). Окремим випадком БЧХ-кодів є Код Ріда-Соломона.

Код винайшов в 1959 році А.Хоквінгем (Hocquenghem), і незалежно в 1960 році Р.Боуз (Bose) і Д.Рой-Чоудхурі (Ray-Chaudhuri). Код отримав свою назву (BCH code) від прізвищ їх авторів.

Коди БЧХ є узагальненням кодів Хеммінга і дозволяють виправляти кратні помилки.

Методи декодуванняРедагувати

Коди БЧХ є циклічними кодами, тому до них застосовні всі методи, використовувані для декодування циклічних кодів. Однак існують набагато кращі алгоритми, розроблені саме для БЧХ-кодів.

Головною ідеєю в декодуванні БЧХ кодів є використання елементів скінченного поля для нумерації позицій кодового слова (або, еквівалентно, в порядку коефіцієнтів асоційованого многочлена).

ДекодуванняРедагувати

Декодер, що працює по авторегресивному спектральному методу декодування, послідовно виконує наступні дії:

  • Обчислює синдром помилки
  • Будує поліном помилки
  • Знаходить корені даного полінома
  • Визначає характер помилки
  • Виправляє помилки

Обчислення синдрому помилкиРедагувати

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

Побудова полінома помилкиРедагувати

Обчислений синдром помилки не вказує на становище помилок. Ступінь полінома синдрому дорівнює 2t, що багато менше ступеня кодового слова n. Для отримання відповідності між помилкою і її положенням у повідомленні будується поліном помилок. Поліном помилок реалізується за допомогою алгоритму Берлекемпа — Мессі, або за допомогою алгоритму Евкліда. Алгоритм Евкліда має просту реалізацію, але вимагає великих витрат ресурсів. Тому частіше застосовується більш складний, але менш затратний алгоритм Берлекемпа - Мессі. Коефіцієнти знайденого полінома безпосередньо відповідають коефіцієнтам помилкових символів у кодовому слові.

Знаходження коренівРедагувати

На цьому етапі шукаються корені полінома помилки, що визначають положення спотворених символів в кодовому слові. Реалізується за допомогою процедури Ченя, повним перебором. У поліном помилок послідовно підставляються всі можливі значення, коли поліном звертається в нуль — корені знайдені.

Визначення характеру помилки і її виправленняРедагувати

По синдрому помилки і знайденим кореням полінома за допомогою алгоритму Форні визначається характер помилки і будується маска спотворених символів.
Після того як маска знайдена, вона накладається на кодове слово за допомогою операції XOR і спотворені символи відновлюються. Після цього відкидаються перевірочні символи і виходить відновлене інформаційне слово.

Див. такожРедагувати

ПосиланняРедагувати