Методические указания к лабораторным работам по курсу "Дискретная математика". Домашова Д.В - 22 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

kn
kn
kn
nk
gg
gg
gg
G
−
−
−
=
...0...0
0...0...0
0...0...
0
0
0
,
Пример. Код (7,4) с g(x)=1+x+x
3
. Многочлену g(x) соответствует кодовое
слово (1101000)
X*g(x) =>(0110100)
X
2
*g(x)=>(0011010)
=
0001101
0011010
0110100
1101000
G
3=n-k=7-4
3.10.2 Получение проверочной матрицы
g(x) – порождающий многочлен (n, k) – код степени (n-k)
Проверочная матрица строится по произведению многочлена
h(x)=(x
n
-1)/g(x)
Если h(x)=h
0
+h
1
x+…+h
k
x
k
=>
0...0...
0...0...0
...0...0
01
0
0
,
hhh
hh
hh
H
k
k
k
nkn
=
−
По определению каждый кодовый многочлен v(x) цикличен (n, k) – кода с
порождающим многочленом g(x) имеет вид:
v(x)=m(x)g(x)=(m
0
+m
1
x+…+m
k-1
x
k-1
),
где : m(x)=m
0
+m
1
x+…+m
k-1
x
k-1
– произвольный многочлен с коэффициентами
из
GF(2) степени меньше k.
Если коэффициенты (m
0
,m
1
,…m
k-1
) многочлена m(x) – это k информаци-
онных символов => циклический код C(g(x)) кодирует их многочлен
v(x)=m(x)g(x)
Рассмотрим кодирование четырехразрядного без избыточного, кодового
многочлена циклического кода (7,4), имеющий порождающий многочлен
g(x)=1+x+x
3
Например, m=(0, 1, 0, 0), который соответствует многочлену m(x)=x ко-
дируется многочленом:
m(x)g(x)=x(1+x+x
3
)=x+x
2
+x
4
, которому отвечает вектор (0,1,1,0,1,0,0)
m=(1,0,1,0), m(x)=1+x
2
=> m(x)g(x)=(1+x
2
)(1+x+x
3
)=1+x+x
3
+x
2
+x
3
+x
5
=
=1+x+x
2
+x
5
=> (1110010)
3.11 Построение систематического кода
Закодируем m=(m
0
, m
1
, …, m
k-1
), соответствующий многочлен
m(x)=m
0
+m
1
x+…+m
k-1
x
k-1
умножим его на x
n-k
:
x
n-k
*m(x)= x
n-k
(m
0
+m
1
x+…+m
k-1
x
k-1
)=m
0
x
n-k
+ …+m
k-1
x
n-1
25
               g 0 ...g n − k 0...0
     Gk ,n = 0 g 0 ...g n − k 0...0
               0...0 g 0 ...g n − k
     Пример. Код (7,4) с g(x)=1+x+x3. Многочлену g(x) соответствует кодовое
слово (1101000)
     X*g(x) =>(0110100)
     X2*g(x)=>(0011010)

       1101000 
                
        0110100 
     G=                              3=n-k=7-4
         0011010 
                
        0001101 
                
     3.10.2 Получение проверочной матрицы

      g(x) – порождающий многочлен (n, k) – код степени (n-k)
      Проверочная матрица строится по произведению                 многочлена
h(x)=(xn-1)/g(x)
      Если h(x)=h0+h1x+…+hkxk =>
                  0...0hk ...h0
     H n − k ,n = 0...0hk ...h0 0
                  hk ...h1 h0 0...0
      По определению каждый кодовый многочлен v(x) цикличен (n, k) – кода с
порождающим многочленом g(x) имеет вид:
      v(x)=m(x)g(x)=(m0+m1x+…+mk-1xk-1),
где : m(x)=m0+m1x+…+mk-1xk-1 – произвольный многочлен с коэффициентами
из
      GF(2) степени меньше k.
      Если коэффициенты (m0,m1,…mk-1) многочлена m(x) – это k информаци-
онных символов => циклический код C(g(x)) кодирует их многочлен
v(x)=m(x)g(x)
      Рассмотрим кодирование четырехразрядного без избыточного, кодового
многочлена циклического кода (7,4), имеющий порождающий многочлен
g(x)=1+x+x3
      Например, m=(0, 1, 0, 0), который соответствует многочлену m(x)=x ко-
дируется многочленом:
      m(x)g(x)=x(1+x+x3)=x+x2+x4, которому отвечает вектор (0,1,1,0,1,0,0)
      m=(1,0,1,0), m(x)=1+x2 => m(x)g(x)=(1+x2)(1+x+x3)=1+x+x3+x2+x3+x5=
      =1+x+x2+x5 => (1110010)

                           3.11 Построение систематического кода

       Закодируем m=(m0, m1, …, mk-1), соответствующий многочлен
m(x)=m0+m1x+…+mk-1xk-1 умножим его на xn-k:
xn-k *m(x)= xn-k(m0+m1x+…+mk-1xk-1)=m0xn-k+ …+mk-1xn-1
                                                                           25

Страницы