ВУЗ:
Составители:
Разделим многочлен x
n-k
*m(x)/g(x) и заменим:
x
n-k
*m(x)=g(x)*q(x)+r(x) (1)
deg(g(x))=n-k => deg(r(x))<=n-k-1
r(x)=r
0
+r
1
x+…+r
n-k-1
x
n-k-1
Перепишем (1) в виде:
r(x)+x
n-k
*m(x)=g(x)*q(x)
Так как r(x)=-r(x) в GF(2))=> r(x)+x
n-k
*m(x) – кодовый многочлен:
r
0
+r
1
x+…+r
n-k-1
x
n-k-1
+m
0
x
n-k
+ …+m
k-1
x
n-1
соответствует кодовому слову:
(r
0
,r
1
,…,r
n-k-1
,m
0
,m
1
,…m
k-1
), записанного в систематическом виде (последние k
символов совпадают с передаваемым словом, а первые (n-k) являются прове-
рочными). Следовательно, чтобы закодировать сообщение m(x) систематиче-
ским циклическим кодом C(g(x)), нужно:
а) разделить многочлены x
n-k
*m(x)/g(x)
б) прибавить остаток от деления к многочлену: x
n-k
*m(x)+ r(x)
Пример. (7,4) n=7 k=4
m=(1011), m(x)=1+x
2
+x
3
x
n-k
*m(x)=x
3
(1+x
2
+x
3
)=x
3
+x
5
+x
6
Разделим x
3
+x
5
+x
6
на g(x)=1+x+x
3
x
6
+x
5
+x
3
|x
3
+x+1
x
6
+x
4
+x
3
|x
3
+x
2
+x+1=q(x)
x
5
+x
4
x
5
+x
3
+x
2
x
4
+x
3
+x
2
x
4
+x
2
+x
x
3
+x
x
3
+x+1
1=r(x)
=> r(x)+x
3
m(x)=1+x
3
+x
5
+x
6
=> кодовый вектор: (1001011)
3.12 Декодирование циклических кодов
Комбинация циклического кода имеет вид многочлена
f(x)=q(x)*g(x)=x
n-k
*m(x)+r(x)
При передачи по каналу могут произойти ошибки. Пусть было принято
p(x)
Декодирование циклических кодов основано на свойстве делимости их
кодовой комбинации без остатка на порождающий многочлен g(x).
Если при передачи ошибки не было => многочлен p(x)=f(x) делится на
g(x) без остатка.
При наличии ошибки, многочлен ошибок e(x)<>0 и p(x)=f(x)+e(x), p(x)
вообще говоря не делится на g(x) без остатка => обнаружена ошибка
Пусть m(x)=1+x
2
+x
3
+x
7
+x
9
=(1011000101) k=10
26
Разделим многочлен xn-k *m(x)/g(x) и заменим:
xn-k *m(x)=g(x)*q(x)+r(x) (1)
deg(g(x))=n-k => deg(r(x))<=n-k-1
r(x)=r0+r1x+…+rn-k-1xn-k-1
Перепишем (1) в виде:
r(x)+xn-k *m(x)=g(x)*q(x)
Так как r(x)=-r(x) в GF(2))=> r(x)+xn-k *m(x) – кодовый многочлен:
r0+r1x+…+rn-k-1xn-k-1+m0xn-k+ …+mk-1xn-1 соответствует кодовому слову:
(r0,r1,…,rn-k-1,m0,m1,…mk-1), записанного в систематическом виде (последние k
символов совпадают с передаваемым словом, а первые (n-k) являются прове-
рочными). Следовательно, чтобы закодировать сообщение m(x) систематиче-
ским циклическим кодом C(g(x)), нужно:
а) разделить многочлены xn-k *m(x)/g(x)
б) прибавить остаток от деления к многочлену: xn-k *m(x)+ r(x)
Пример. (7,4) n=7 k=4
m=(1011), m(x)=1+x2+x3
xn-k*m(x)=x3(1+x2+x3)=x3+x5+x6
Разделим x3+x5+x6 на g(x)=1+x+x3
x6+x5+x3 |x3+x+1
x6+x4+x3 |x3+x2+x+1=q(x)
x5+x4
x5+x3+x2
x4+x3+x2
x4+x2+x
x3+x
x3+x+1
1=r(x)
=> r(x)+x3m(x)=1+x3+x5+x6
=> кодовый вектор: (1001011)
3.12 Декодирование циклических кодов
Комбинация циклического кода имеет вид многочлена
f(x)=q(x)*g(x)=xn-k*m(x)+r(x)
При передачи по каналу могут произойти ошибки. Пусть было принято
p(x)
Декодирование циклических кодов основано на свойстве делимости их
кодовой комбинации без остатка на порождающий многочлен g(x).
Если при передачи ошибки не было => многочлен p(x)=f(x) делится на
g(x) без остатка.
При наличии ошибки, многочлен ошибок e(x)<>0 и p(x)=f(x)+e(x), p(x)
вообще говоря не делится на g(x) без остатка => обнаружена ошибка
Пусть m(x)=1+x2+x3+x7+x9=(1011000101) k=10
26
