лекции / Lekciya6RavisdvbBChH
.pdf
Пример 2. Построить двоичный примитивный циклический код БЧХ для m = 4 |
11 |
|
и t = 3.
В этом случае длина кодовой комбинации равна n = 2m – 1 = 15, а вектор {f(х)} будет принадлежать этому циклическому коду, если 2t элементов поля GF(24)
ε, ε2, ε3, ε4,. ε5, ε6 будут корнями многочлена f(х). Кроме того, отметим, что ε – примитивный элемент поля GF(24) , а минимальной функцией для него пусть будет примитивный неприводимый многочлен m1(х) = 1+х + x4.
|
Степень |
|
|
Корни многочлена |
Многочлен |
многочлена |
|
|
|
m (x) |
4 |
|
|
, 2, 4, 8 |
1 |
|
|
|
|
m (x) |
4 |
|
|
3, 6, 9, 12 |
3 |
|
|
|
5, 10 |
m (x) |
2 |
|
|
|
5 |
|
|
|
7, 11, 13, 14 |
m (x) |
4 |
|
|
|
7 |
|
|
|
|
m (x) |
1 |
|
|
15=1 |
0 |
|
|
|
|
|
|
|
|
|
m0(х) |
m5(х) |
m1(х) |
m7(х) |
|
Таблица 2.2.
G(х) = m1(х) m3(x) m5(х)=
= 1 + х + x2 + x4 + x5+ x8 + x10.
m3(х)
(х15 1) = (х 1) (х2 + х + 1) (х4 + х+ 1) (x4 + x3 + 1) (х4+ х3 + х2 + х+ 1).
0 |
5 |
|
-1= 14 |
3 |
|
10 |
2 |
-2= 13 |
6 |
|
|
4 |
-4= 11 |
12 |
|
|
8 |
-8= 7 |
9 |
Порождающий многочлен G(x)=1 + х + x2 + x4 + x5+ x8 + x10.
|
|
|
|
111011001010000 |
|
||
|
011101100101000 |
|
|
|
|
||
|
|||
G 110101111000100 |
|
||
|
011010111100010 |
|
|
|
|
||
|
|||
|
|
|
|
110110010100001 |
|
||
|
|
||
GHT=0
10000100
0010
0001
11000110
0011 H T 1101
10100101
11100111
1111
10111001
1000
0001
0011
0101
1111
1000
0001
0011
0101
1111
1000
0001
0011
0101
1111
1000
0110
1110
1000
0110
1110
1000
0110 (3.6)
1110
1000
0110
1110
1000
0110
1110
Образованный таким образом циклический (n,k) = (15, 5) код БЧХ позволяет исправить любую совокупность ошибок кратности t = 3 или менее.
Принципы исправления ошибок кодами БЧХ на основе алгоритма Питерсона- Горенштейна-Цирлера
f(х) = с0 + с1х + ... + сn-1 хn-1.
h(x)={f(х) + е(х)} = {f(х)} + {e(x)}, где {е(х)} - вектор ошибок.
. h(х) = h0 + h1х + h2х2 +... + hn-1 хn-1
|
1 |
|
|
|
|
2 |
|
|
... |
|
|
n 1 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
3 |
( |
3 ) |
2 |
|
... |
( |
3 )n 1 |
|
|
||||||||||
|
1 |
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
H |
|
|
5 |
( |
5 |
) |
2 |
|
... |
( |
5 |
) |
n 1 |
|
. |
||||||
1 |
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
. |
|
|
. |
|
|
|
... |
|
|
|
|
. |
|
|
|
|
||
|
|
|
2t 1 |
( |
2t 1 |
) |
2 |
... |
( |
2t 1 |
) |
n 1 |
|
|
|||||||
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[h(ε), h(ε3), ..., h(ε2t-1)] ≡ [e(ε), e( ε3), |
|
.., e( ε2t-1)}, |
||||||||||
e(ε i) = e |
+ e |
ε i + e |
2 |
(ε i)2 |
+... + e |
n-1 |
(ε i)n-1. |
|||||
0 |
1 |
|
|
|
|
|
|
|
|
|||
h(ε) = e(ε) = e |
0 |
+ e |
1 |
ε + e ε 2 +... + e |
n-1 |
ε n-1 |
||||||
|
|
|
|
|
2 |
|
|
|
||||
|
|
|
t |
|
|
|
t |
|
|
|
|
|
h( ) e( ) ik |
X k . |
|
|
|
|
|||||||
|
|
|
k 1 |
|
|
k 1 |
|
|
|
|
||
|
|
|
t |
|
t |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||
S1 h( ) e( ) ik X k X1 |
X 2 ... X t ; |
|
|
|
||||||||
|
|
|
k 1 |
|
k 1 |
|
|
|
|
|
|
|
|
|
|
|
t |
t |
|
|
|
|
|
|
|
S2 |
h( 2 ) e( 2 ) ( 2 )ik X k2 |
( X1 )2 ( X 2 )2 ... ( X t )2 S12 ; |
||||||||||
|
|
|
k 1 |
k 1 |
|
|
|
|
|
|
|
|
....................................................... |
|
|
|
|
|
|
|
|||||
|
|
|
|
t |
t |
|
|
|
|
|
|
|
S2t |
h( 2t ) e( 2t ) |
( 2t )ik X k2t ( X1 )2t |
( X 2 )2t ... ( X t )2t |
St2t . |
||||||||
|
|
|
|
k 1 |
k 1 |
|
|
|
|
|
|
|
Ψ(X) = X t + p |
X t-1 |
+ p |
X t-2 |
+ … + p |
= (X−X |
)(X−X |
) … (X−X |
) ; |
|
|
||
|
1 |
|
2 |
|
t |
|
1 |
2 |
t |
|
|
|
Где Ψ(X) - многочлен локаторов ошибок, корни которого Xi можно найти через синдромы Si . Однако это трудоёмкая задача, но решаемая!
Значительно проще решается эта задача, если в качестве многочлена локаторов ошибок выбрать многочлен
(z) (1 X |
z)(1 X |
2 |
z) ... (1 X |
z), |
|
|
|
|
|||
1 |
|
|
t |
|
|
|
|
|
|
|
|
Корнями которого теперь будут |
|
Z X 1 |
, Z |
2 |
X 1 |
,..., Z |
t |
X 1 |
, |
||
|
|
|
1 1 |
|
|
2 |
|
t |
|
||
Для двоичных кодов БЧХ (-)=(+), поэтому перепишем многочлен локаторов ошибок в виде:
(z) (1 X z)(1 X |
|
z) ... |
(1 X z) |
|
z ... |
z |
. |
|
|
|
|
|
|
|
|
t |
|
1 |
2 |
|
t |
0 |
1 |
t |
|
|
Перемножив сомножители левой части и приравняв коэффициенты при одинаковых степенях z, получим элементарные симметрические
функции: |
|
0 |
1; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
( X |
1 |
X |
2 |
... |
X |
); |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
t |
|
|
|
|
|||
|
|
2 |
( X |
X |
2 |
X |
X |
3 |
... |
X |
t 1 |
X |
); |
||||
|
|
|
|
1 |
|
|
|
1 |
|
|
|
t |
|
||||
|
...................................................... |
||||||||||||||||
|
|
t |
X |
1 |
X |
2 |
... |
X |
. |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
t |
|
|
|
|
|
|
|||
' (z) X i (1 X j z). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
i |
j i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Найдем |
отношение : |
|
|
|
|
|||
|
z ' (z) |
|
X1 z |
|
X 2 z |
|
... |
X t z |
|
|
(z) |
1 X1 z |
1 X 2 z |
1 X t z |
|||||
X1 z ( X1 z)2 ( X1 z)3 ..... |
|
|
|
|
|||||
X 2 z ( X 2 z)2 ( X 2 z)3 ..... |
|
|
|
|
|||||
.................................................. |
|
|
|||||||
X t z ( X t z)2 ( X t z)3 ..... |
|
... |
|
|
|||||
2t
(z)( Sl zl ) z ' (z)
l 1
2t
z( X1 X 2 ... X t ) z 2 ( X12 X 22 ... X t2 ) ... z 2t ( X12t X 22t ... X t2t ) Sl zl .
l 1
(1 |
|
z |
|
|
z |
2 |
... |
|
t |
)(S z S |
z |
2 |
... S |
|
z |
2t |
|||||||
|
2 |
|
z |
|
2t |
|
|||||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
t |
|
1 |
|
2 |
|
|
|
|
|
||||
z( |
|
|
2 |
|
|
z 3 |
|
z |
2 |
... t |
z |
t 1 |
). |
|
|
|
|
||||||
1 |
2 |
3 |
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
t |
|
|
|
|
|
|
|
|
|||||
)
Перемножив левую часть и приравняв коэффициенты при одинаковых степенях z
получим тождества Ньютона:
S |
1 |
0, |
|
|
|
|
|
|
|
|
|
|
|
|||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
S |
2 |
S |
1 |
2 |
2 |
0, |
|
|
|
|
|
|
|
|
||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
S |
3 |
S |
1 |
S |
2 |
3 |
3 |
0, |
|
|
|
|
|
|||||
|
|
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
||||
S |
4 |
S |
1 |
S |
2 |
S |
3 |
4 |
4 |
0, |
|
|
||||||
|
|
3 |
|
|
2 |
|
1 |
|
|
|
|
|
|
|||||
S |
5 |
S |
1 |
S |
2 |
S |
3 |
S |
4 |
5 |
5 |
0, |
||||||
|
|
4 |
|
|
3 |
|
2 |
|
1 |
|
|
|
||||||
.............................................................. |
||||||||||||||||||
Возьмём из 2t уравнений только линейно-независимые:
S1 1,
S3 S2 1 S1 2 3 3 ,
S5 S4 1 S3 2 S2 3 S1 4 5 5 ,
..............................................................
S2t 1 S2t 2 1 S2t 3 2 S2t 4 3 ... St 1 t .
Из последних уравнений составим следующее матричное уравнение:
|
|
1 |
|
0 |
|
0 |
|
0 |
0 |
|
|
|
1 |
|
|
S |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
S |
|
S |
|
1 |
|
0 |
0 |
|
|
S |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
2 |
|
|
3 |
||||||
|
S |
|
S |
|
S |
|
|
S |
0 |
|
|
|
|
|
|
S |
|
|
||||||
|
|
|
4 |
|
|
3 |
|
|
2 |
|
1 |
|
|
|
|
|
|
3 |
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
S |
|
|
S |
|
|
S |
|
S |
|
|
|
|
|
|
|
|
S |
|
|
|
|
2t 4 |
2t 5 |
2t 6 |
2t 7 |
t 3 |
|
|
t |
1 |
|
|
2t 3 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
S |
2t 2 |
S |
2t 3 |
S |
2t 4 |
S |
2t 5 |
S |
t 1 |
|
|
t |
|
S |
2t 1 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
Решая эту систему, найдем коэффициенты многочлена локаторов ошибок, а затем по процедуре Ченя найдём корни многочлена (z).
Далее берем от них обратные элементы поля GF(2m) и получаем номера ошибочных позиций.
Для закрепления этого алгоритма рассмотрим ряд примеров.
ПРИМЕР. Код БЧХ: n=15, t=3, GF(24), поле образовано по примитивному
многочлену
P(x) 1 x x4 , |
корни : , 2 , 4 , 8 . |
Корни порождающего многочлена G(x) : , 2 , 3 , 4 , 5 , 6 . |
|
G(x) m1 (x)m3 (x)m5 (x). |
|
Принятая комбинация: |
|
h(x) h0 h1x h2 x2 h3 x3 ... h14 x14 x x2 x3 x5 x6 x8 x12 .
Многочлен локаторов ошибок:
t
(z) (1 zi z) 1 1z 2 z2 3 z3.
i1
ЗАДАНИЕ: декодировать комбинацию по алгоритму Питерсона (ПГЦ), определить ошибочные позиции в комбинации и исправить ошибки.
Литература
1.Когновицкий О.С.,Охорзин В. М. Теория помехоустойчивого кодирования. Часть 1. Циклические коды.: Учебное пособие/ СПбГУТ. – СПб., 2013. – 94 с.
(Материал к лекции – стр.36 – 65)
2.Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р. Морелос-Сарагоса; пер. с англ. – М. : Техносфера,
2006. – 319 с. (Материал к лекции – стр. 65 – 103)