Оглавление
- 1 Код BCH
- 1.1 История и определение
- 1.2 Особенности и преимущества
- 1.3 Примитивные коды BCH узкого смысла
- 1.4 Общие коды BCH
- 1.5 Свойства и применение
- 1.6 Несистематическое кодирование
- 1.7 Систематическое кодирование
- 1.8 Расшифровка BCH-кодов
- 1.9 Алгоритм Петерсона-Горенштейна-Зирлера
- 1.10 Многочлен определения коэффициента ошибки
- 1.11 Вычисление значений ошибок
- 1.12 Объяснение алгоритма Форни
- 1.13 Вычисление произведения корней
- 1.14 Декодирование на основе расширенного евклидова алгоритма
- 1.15 Процесс декодирования
- 1.16 Примеры декодирования
- 1.17 Многочлен степени не более 3
- 1.18 Поиск значений ошибок
- 1.19 Расшифровка с небольшим количеством ошибок
- 1.20 Расширенный евклидов алгоритм
- 1.21 Полный текст статьи:
- 2 Код BCH
Код BCH
-
История и определение
- Коды Бозе–Чаудхури–Хокенгема (BCH) были изобретены в 1959 году Алексисом Хокенгемом и независимо в 1960 году Раджем Чандрой Боузом и Д. К. Рэй-Чаудхури.
- BCH-коды строятся с использованием полиномов над конечным полем (полем Галуа).
- Коды BCH имеют точное управление количеством ошибок, которые могут быть исправлены.
-
Особенности и преимущества
- BCH-коды просты в декодировании с помощью алгебраического метода синдромного декодирования.
- Коды BCH используются в спутниковой связи, проигрывателях компакт-дисков, DVD-дисках, дисководах, USB-флэш-накопителях, твердотельных накопителях и двумерных штрих-кодах.
-
Примитивные коды BCH узкого смысла
- Примитивные узконаправленные коды BCH строятся с использованием примитивного элемента GF(qm) и минимального многочлена mi(x) для каждого i.
- Многочлен генератора g(x) определяется как наименьшее общее кратное mi(x).
- Коды BCH с d = 2, 3 имеют минимальное расстояние Хэмминга не менее 3 и исправляют до одной ошибки.
- Коды BCH с d = 4, 5 имеют минимальное расстояние Хэмминга не менее 5 и исправляют до двух ошибок.
- Коды BCH с d = 6, 7 имеют минимальное расстояние Хэмминга не менее 7 и исправляют до трех ошибок.
- Коды BCH с d = 8 и выше имеют минимальное расстояние Хэмминга 15 и исправляют 7 ошибок.
-
Общие коды BCH
- Общие коды BCH отличаются от примитивных кодов BCH узкого смысла тем, что α может быть не примитивным элементом GF(qm).
- Длина кода изменяется с qm – 1 на ord(α).
- Последовательные корни образующего многочлена могут начинаться от αc, …, αc+d-2 вместо α, …, αd-1.
-
Свойства и применение
- Многочлен генератора имеет степень не более (d-1)m.
- Код BCH имеет минимальное расстояние Хэмминга, по крайней мере, d.
- Код BCH является циклическим, если его порождающий многочлен делится на xn – 1.
- Кодирование BCH – это процесс нахождения многочлена, кратного многочлену генератора.
- Код BCH может быть реализован как систематический код или нет, в зависимости от встраивания сообщения в закодированный полиномиал.
-
Несистематическое кодирование
- Сообщение представляется как многочлен над GF(2)
- Кодовое слово вычисляется как произведение сообщения и генератора
- Приемник использует биты сообщения для исправления ошибок
-
Систематическое кодирование
- Сообщение встраивается в кодовое слово
- Кодовое слово корректируется для обеспечения делимости на генератор
- Процесс аналогичен циклической проверке на избыточность
-
Расшифровка BCH-кодов
- Вычисление синдромов для определения ошибок
- Определение количества ошибок и полинома локатора ошибок
- Вычисление корней полинома для нахождения местоположения ошибок
- Вычисление значений ошибок для исправления
-
Алгоритм Петерсона-Горенштейна-Зирлера
- Создание матрицы синдромов и вектора неизвестных коэффициентов
- Решение матричного уравнения для нахождения коэффициентов
- Остановка процедуры при нулевом определителе матрицы
-
Многочлен определения коэффициента ошибки
- Вычисление полинома локатора ошибок с помощью грубой силы
- Определение позиций ошибок по нулям полинома
-
Вычисление значений ошибок
- Определение значений ошибок по полиному вычислителя ошибок
- Использование алгоритма Форни для эффективного вычисления
-
Объяснение алгоритма Форни
- Использование интерполяции Лагранжа и методов генерации функций
- Вычисление неизвестных величин ej через полином вычислителя ошибок
-
Вычисление произведения корней
- Можно вычислить произведение корней непосредственно из уже вычисленных корней.
- Формальная производная позволяет упростить процесс.
-
Декодирование на основе расширенного евклидова алгоритма
- Альтернативный процесс нахождения многочлена Λ и локатора ошибок основан на расширенном евклидовом алгоритме.
- Исправление нечитаемых символов легко включается в алгоритм.
-
Процесс декодирования
- Цель — найти кодовое слово, минимально отличающееся от полученного слова на читаемых позициях.
- Синдромы ограничивают слово ошибки по условию.
- Замена синдромов на новые позволяет найти местоположение ошибок.
-
Примеры декодирования
- Расшифровка двоичного кода без нечитаемых символов.
- Расшифровка с помощью нечитаемых символов.
-
Многочлен степени не более 3
- Достигнут многочлен степени не более 3
- Получен многочлен Λ(x) = α3 + α-5x + α6×2
- Корень Λ(x) равен α2 и α10
-
Поиск значений ошибок
- Используется формула для поиска значений ошибок
- e3 = e4 = 1, что не вызывает удивления
- Исправленный код: [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0]
-
Расшифровка с небольшим количеством ошибок
- Получено слово [1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0]
- Создан многочлен Γ(x) = (α8x – 1)(α11x – 1)
- Вычислены синдромы: s1 = α4, s2 = α-7, s3 = α1, s4 = α1, s5 = α0, s6 = α2
- Создан многочлен синдрома
-
Расширенный евклидов алгоритм
- Получен многочлен Λ(x) = α3 + α1x
- Корень Λ(x) равен α3 – 1
- e3 = 1, что не вызывает удивления