Коды Боуза-Чоудхури-Хоквингема (стр. 1 из 2)
РЕФЕРАТ
По курсу “Теория информации и кодирования”
на тему:
"КОДЫ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА"
БЧХ коды
Коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс циклических кодов, исправляющих кратные ошибки, т. е. две и более (d0 ³ 5).
Теоретически коды БЧХ могут исправлять произвольное количество ошибок, но при этом существенно увеличивается длительность кодовой комбинации, что приводит к уменьшению скорости передачи данных и усложнению приемо-передающей аппаратуры (схем кодеров и декодеров).
Методика построения кодов БЧХ отличается от обычных циклических, в основном, выбором определяющего полинома P(х). Коды БЧХ строятся по заданной длине кодового слова n и числа исправляемых ошибок S , при этом количество информационных разрядов k не известно пока не выбран определяющий полином.
Рассмотрим процедуру кодирования с использованием кода БЧХ на конкретных примерах.
Пример Построить 15-разрядный код БЧХ, исправляющий две ошибки в кодовой комбинации (т. е. n = 15, S = 2).
Решение:
1. Определим количество контрольных m и информационных разрядов k
m £ h S .
Определим параметр h из формулы
n = 2h-1, h = log2(n+1) = log216 = 4,
при этом: m £ h S = 4×2 = 8; k = n-m = 15-8 = 7.
Таким образом, получили (15, 7)-код.
2. Определим параметры образующего полинома:
- количество минимальных многочленов, входящих в образующий
L = S = 2;
- порядок старшего (все минимальные - нечетные) минимального многочлена r = 2S-1 = 3;
- степень образующего многочленаb = m £ 8.
3. Выбор образующего многочлена.
Из таблицы для минимальных многочленов для кодов БЧХ (см. приложение 4) из колонки 4 (т. к. l = h = 4) выбираем два минимальных многочлена 1 и 3 (т. к. r = 3):
M1(x) = 10011;
M2(x) = 11111.
При этом
P(x) =M1(x)×M2(x)=10011´11111=111010001= x8+ x7+ x6+ x4+1.
4. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 15. Остальные строки матрицы получаем в результате k-кратного циклического сдвига справа налево первой строки матрицы.
Строки образующей матрицы представляют собой 7 кодовых комбинаций кода БЧХ, а остальные могут быть получены путем суммирования по модулю 2 всевозможных сочетаний строк матрицы.
Процедура декодирования, обнаружения и исправления ошибок в принятой кодовой комбинации такая же, как и для циклических кодов с d0 < 5
Пример Построить 31-разрядный код БЧХ, исправляющий три ошибки в кодовой комбинации (т. е. n = 31, S = 3).
Решение:
1. Определим количество контрольных разрядов m и информационных разрядов k.
m £ h S.
Определим параметр h из формулы
n = 2h-1,h = log2(n+1) = log232 = 5,
при этом: m £ h S = 5×3 = 15; k = n-m = 31-15 = 16.
Таким образом, получили (31, 16)-код.
2.Определим параметры образующего полинома:
- количество минимальных многочленов, входящих в образующий
L = S = 3;
- порядок старшего минимального многочлена
r = 3S-1 = 5;
- степень образующего многочлена
b = m £ 15.
1. Выбор образующего многочлена.
Из таблицы для минимальных многочленов для кодов БЧХ ( приложение 4) из колонки 5 (т. к. l = h = 5) выбираем три минимальных многочлена 1, 3 и 5 (т. к. r = 5):
M1(x) =100101;
M2(x) =111101;
M3(x) =110111.
При этом
P(x) = M1(x) ×M2(x) ×M3(x) =1000111110101111=
= x15+ x11 +x10+ x9+ x8+ x7+ x5+ x3 + x2+x+ 1.
4. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 31. Остальные строки матрицы получаем в результате k-кратного циклического сдвига справа налево первой строки матрицы.
000000000000000100011111011111
G(31,16)=000000000000001000111110111110
. . .
100011111011111000000000000000
Строки образующей матрицы представляют собой 16 кодовых комбинации кода БЧХ, а остальные могут быть получены путем суммирования по модулю 2 всевозможных сочетаний строк матрицы.
Декодирование кодов БЧХ
Коды БЧХ представляют собой циклические коды и, следовательно, к ним применимы любые методы декодирования циклических кодов. Открытие кодов БЧХ привело к необходимости поиска новых алгоритмов и методов реализации кодеров и декодеров. Получены существенно лучшие алгоритмы, специально разработанные для кодов БЧХ. Это алгоритмы Питерсона, Бэрлекэмпа и др.
Рассмотрим алгоритм ПГЦ (Питерсона-Горенстейна-Цирлера). Пусть БЧХ код над полем GF(q) длины n и с конструктивным расстоянием d задается порождающим полиномом g(x), который имеет среди своих корней элементы
, 
— целое число (например 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что 
. Принятое слово r(x) можно записать как r(x) = c(x) + e(x), где e(x) — полином ошибок. Пусть произошло 
ошибок на позициях 
(t максимальное число исправляемых ошибок), значит 
, а 
— величины ошибок.Можно составить j-ый синдром Sj принятого слова r(x):
.Задача состоит в нахождений числа ошибок u, их позиций
и их значений при известных синдромах Sj.Предположим, для начала, что u в точности равно t. Запишем (1) в виде системы нелинейных уравнений в явном виде:
Обозначим через
локатор k-ой ошибки, а через 
величину ошибки, 
. При этом все Xk различны, так как порядок элемента β равен n, и поэтому при известном Xk можно определить ik как ik = logβXk. 
Составим полином локаторов ошибок:
Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на
. Полученное равенство будет справедливо для 
: 
Положим
и подставим в (3). Получится равенство, справедливое для каждого 
и при всех 
: 
Таким образом для каждого l можно записать свое равенство. Если их просуммировать по l, то получиться равенство, справедливое для каждого
: 
.Учитывая (2) и то, что
(то есть
меняется в тех же пределах, что и ранее) получаем систему линейных уравнений: 
.
Или в матричной форме
,Где
Если число ошибок и в самом деле равно t, то система (4) разрешима, и можно найти значения коэффициентов
. Если же число u < t, то определитель матрицы S(t) системы (4) будет равен 0. Это есть признак того, что количество ошибок меньше t. Поэтому необходимо составить систему (4), предполагая число ошибок равным t − 1. Высчитать определитель новой матрицы S(t − 1) и т. д., до тех пор, пока не установим истинное число ошибок.После этого можно решить систему (4) и получить коэффициенты полинома локаторов ошибок. Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля GF(qm). К ним найти элементы, обратные по умножению, — это локаторы ошибок
. По локаторам можно найти позиции ошибок (ik = logβXk), а значения Yk ошибок из системы (2), приняв t = u. Декодирование завершено.