БЧХ. Корневой подход

1. БЧХ

2. Постановка задачи

• Корректирующий циклический (n, k) код
c (cn 1, cn 2 ,...,c0 ) ( F2 )n
• представляется в полиномиальном виде как
C ( x) cn 1x n 1 cn 2 x n 2 ... c0 F2[ x]
• где F2[x] - кольцо многочленов над полем F2 .

3. Корневой подход

y( x) c( x) e( x)
e( x) e0 e1 x e2 x 2 ... en 1 x n 1
sj
n 1
i
e
i
j
i 0

4. Пример

• Обозначим примитивный элемент конечного
поля GF(2m) как α.
• Определим проверочную матрицу H кода C ,
столбцы которой равны n – 1, n – 2, …, 0 ,
где n = 2m – 1 .
• Произведению (cHT) соответствует полином
C( ) cn 1 n 1 cn 2 n 2 ... c2 2 c1 c0
• Если c( ) = 0 , то получим циклический код
Хэмминга

5. Пример

6. Корневой подход

( 1,..., 2t ) ( , 2 , 3 ,..., 2t )

7. Алгоритм формирования кода

• 1. Строится поле
• GF(pm) ,
• для которого - примитивный элемент поля.
• 2. Определяются минимальные полиномы
mi ( x) m i ( x)
i , i 1,...,2t
• 3. Порождающий полином g(x) вычисляется как
g ( x) НОК (m1 ( x), m2 ( x),..., m2t ( x))

8. Теорема

• Пусть циклический код C длины n задан
порождающим полиномом g(x) над
полем
GF(p)
и
пусть
имеется
наименьшее целое m такое, что n|pm – 1, а
GF(pm) – примитивный корень из
единицы n-й степени.
• Тогда, если элементы
поля GF(pm)
определяют нули кода для целых b 0 и
2, то код имеет dmin .

9. Определение БЧХ

• Зададим циклический код C длины n над
полем GF(p), определив наименьшее целое m
такое, что n | pm – 1 и GF(pm) –
примитивный корень из единицы n-й степени.
• Тогда можно определить БЧХ код C с
заданным значением кодового расстояния и
порождающим полиномом
g ( x) НОК{mb ( x), mb 1( x),..., mb 2 ( x)}
• где mb (x) минимальный многочлен элемента
• b GF(pm), b – целое положительное число.

10. БЧХ

• Если b = 1 то говорят, что код БЧХ определен
в узком смысле.
• Если же n = pm – 1 ( – примитивный элемент
GF(pm)), то БЧХ код называют примитивным.
• Теорема. БЧХ код длины n с заданным
значением
кодового
расстояния
,
построенный над полем GF(p), имеет dmin и
размерность k n – m( – 1)
• Для p = 2, b = 1 и = 2t + 1, k n – mt.

11. Соотношение между параметрами кода

• Для p = 2, b = 1, n = 2m – 1 и = 2t +1 код БЧХ
• имеет dmin = 2t + 1, если
t 1
i
mt
C
2
• .
n
i 0
• Если b = 1, n = v, тогда dmin = .
• Если b = 1, n = pm – 1 и = pv – 1, тогда dmin = .
• Если n = pm – 1, тогда dmin p – 1 .

12. Проверочная матрица БЧХ

1
b
2b
b 1
2(b 1)
1
H
b 2
2 (b 2 )
1
( n 1)b
( n 1)(b 1)
( n 1)(b 2)
1 a a 2 a n 1
1
1
1
2
n 1
1 a2 a2 a2
МатрицаВандермонда
2
n 1
1 an an an
aj – элементы поля. Определитель 0, если aj – различны.
n 1 n
det (ai a j )
j 1i j 1

13. Galois Field

• GF(23) с неприводимым полиномом: x3 + x + 1
• = x примитивный элемент
x
010
2
2
x2
100
3
3
x+1
011
4
4
x2 + x
110
5
5
x2 + x + 1
111
6
6
x2 + 1
101
7
7
1
001
1

14. GF Discrete Fourier Transform (DFT) GF-DFT

• Интерполяция полинома в n точках через умножение на матрицу:
• – примитивный n-й корень из единицы ( n = 1) – генератор
1
1
1
2
1
4
T 1 2
n 1
2 ( n 1)
1
n 1
2( n 1)
( n 1)(n 1)
1
c0
m0
c
m
k 1 T k 1
ck
0
0
c
n 1
Оценка полинома mk-1xk-1 + + m1x + m0
вt n различных корнях из 1, 1, , 2, 3, , n-1
1
Обратное ДПФm T c

15. Вычисление минимальных полиномов через циклотомические классы

, , ( ) , ( )
2
2 2
4
4 2
8
( 8 ) 2

16. Сопряженные элементы

• Так для поля