Введение
Код коррекции ошибок
В теории кодирования коды Бозе — Чаудхури — Хоккенгема (коды BCH) образуют класс циклических кодов, исправляющих ошибки, которые строятся с использованием многочленов над конечным полем (также называемым полем Галуа). Коды BCH были изобретены в 1959 году французским математиком Алексисом Хоккенгемом и независимо в 1960 году Раджем Чандрой Бозе и Д. К. Рэем Чаудхури. Название Bose–Chaudhuri–Hocquenghem (и аббревиатура BCH) происходит от инициалов фамилий изобретателей (ошибочно, в случае Рэя Чаудхури). Одной из ключевых особенностей кодов BCH является то, что при проектировании кода обеспечивается точный контроль над количеством символьных ошибок, которые код может исправить. В частности, можно разработать двоичные коды BCH, способные исправлять множественные битовые ошибки. Другим преимуществом кодов BCH является простота их декодирования, а именно с помощью алгебраического метода, известного как синдромное декодирование. Это упрощает разработку декодера для этих кодов, используя небольшое электронное оборудование с низким энергопотреблением. Коды BCH используются в таких приложениях, как спутниковая связь, проигрыватели компакт-дисков, DVD, дисководы, USB-накопители, твердотельные накопители и двумерные штрих-коды.
In coding theory, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of cyclic error correcting codes that are constructed using polynomials over a finite field (also called a Galois field). BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Chandra Bose and D. K. Ray Chaudhuri. The name Bose–Chaudhuri–Hocquenghem (and the acronym BCH) arises from the initials of the inventors' surnames (mistakenly, in the case of Ray Chaudhuri). One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding. This simplifies the design of the decoder for these codes, using small low power electronic hardware. BCH codes are used in applications such as satellite communications, compact disc players, DVDs, disk drives, USB flash drives, solid state drives, and two dimensional bar codes.
Примитивные коды BCH в узком смысле
При заданном простом числе q и степени простого числа q^(m) с положительными целыми числами m и d, таких что d ≤ q^(m) − 1, примитивный BCH-код в узком смысле над конечным полем (или полем Галуа) GF(q) с длиной кода n и расстоянием не менее d конструируется следующим методом. Пусть α – примитивный элемент GF(q^(m)). Для любого положительного целого числа i пусть mi(x) будет минимальным полиномом с коэффициентами в GF(q) элемента α^(i). Генераторный многочлен BCH-кода определяется как наименьшее общее кратное mi(x) для всех i, не делящихся на d. Можно показать, что g(x) – многочлен с коэффициентами в GF(q) и является делителем x^(n) − 1. Следовательно, полиномиальный код, заданный g(x), является циклическим кодом.
Кодирование
Поскольку любой многочлен, кратный генераторному многочлену, является допустимым кодовым словом BCH, кодирование BCH представляет собой просто поиск многочлена, имеющего генераторный многочлен в качестве делителя. Сам код BCH не определяет значения коэффициентов многочлена; концептуально, единственная задача алгоритма декодирования BCH — найти допустимое кодовое слово с минимальным расстоянием Хэмминга до принятого кодового слова. Следовательно, код BCH может быть реализован как систематический или несистематический, в зависимости от того, как разработчик решает встроить сообщение в закодированный многочлен.
Систематическое кодирование: сообщение как префикс
Систематический код – это код, в котором сообщение появляется дословно в составе кодового слова. Поэтому систематическое кодирование BCH включает в себя сначала встраивание полинома сообщения в полином кодового слова, а затем корректировку коэффициентов оставшихся (неинформационных) членов, чтобы обеспечить делимость на . Этот метод кодирования основан на том, что вычитание остатка из делимого дает кратное делителю. Следовательно, если взять полином сообщения, как и ранее, и умножить его на (чтобы "сдвинуть" сообщение, освобождая место для остатка), то можно использовать деление многочленов с остатком, чтобы получить:
This encoding method leverages the fact that subtracting the remainder from a dividend results in a multiple of the divisor. Hence, if we take our message polynomial as before and multiply it by (to "shift" the message out of the way of the remainder), we can then use Euclidean division of polynomials to yield:
Здесь видно, что является допустимым кодовым словом. Поскольку всегда имеет степень меньше, чем (которая является степенью ), его можно безопасно вычесть из , не изменяя коэффициенты сообщения, и тогда мы получим:
В поле GF(2) (то есть для бинарных кодов BCH) этот процесс неотличим от добавления контрольной суммы CRC. И если систематический бинарный код BCH используется только для обнаружения ошибок, то коды BCH являются обобщением математических принципов CRC. Преимущество систематического кодирования заключается в том, что приемник может восстановить исходное сообщение, отбросив все коэффициенты после первых, после выполнения коррекции ошибок.
Алгоритм Питерсона-Горенштейна-Цилерлера
Алгоритм Питерсона является вторым шагом обобщенной процедуры декодирования BCH. Алгоритм Питерсона используется для вычисления коэффициентов полинома определения ошибок. Теперь процедура алгоритма Петерсона — Горенштейна — Зирлера. Предположим, что у нас есть как минимум 2t синдромов sc, ..., sc+2t−1. Пусть v = t.
Now the procedure of the Peterson–Gorenstein–Zierler algorithm. Expect we have at least 2t syndromes sc, , sc+2t−1. Let v = t.
Полином локатора ошибок
Теперь, когда у вас есть многочлен, его корни можно найти перебором, например, с помощью алгоритма поиска Чиена. Экспоненциальные степени примитивного элемента определят позиции, в которых произошли ошибки в принятом слове; отсюда и название "полином определения позиций ошибок". Нули Λ(x) равны α−i1, α−i2, α−iv.
powers of the primitive element will yield the positions where errors occur in the received word; hence the name 'error locator' polynomial. The zeros of Λ(x) are α−i1, , α−iv.
Вычислить значения ошибок
После того, как местоположения ошибок определены, следующим шагом является определение величины ошибок в этих позициях. Эти величины ошибок затем используются для исправления принятых значений в этих позициях и восстановления исходного кодового слова. Для бинарного BCH (при условии, что все символы читаемы) это тривиально: достаточно инвертировать биты принятого слова в этих позициях, чтобы получить исправленное кодовое слово. В более общем случае, веса ошибок могут быть определены путем решения системы линейных уравнений.
Исправьте ошибки
Используя значения ошибок и их местоположение, внесите исправления в код, формируя исправленный вектор кода путем вычитания значений ошибок в соответствующих позициях.
Вторичные источники
Записи лекций, судя по всему, перерабатываются для 2012 года: http://www.stanford.edu/class/ee387/