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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Вес E
i
определяется числом, исправленным разрядов.
Принятая одовая комбинация сравнивается с векторами в строке, соот-
ветствующей полученному в результате проверки синдрома.
к
Правильное кодовое слово – в первой строке того же столбца таблицы.
Векторы E
i
не должны быть равны ни одному из векторов кода, получи-
лись бы нулевые вектора.
Пример. (7, 4) код
H=
; V=(0110100) – полученный вектор
0010111
0101011
1001101
C=VH
t
=(110) совпадает с четвертым столбцом матрицы H. =>
e=(0001000) => v+e=(0110100)+(0001000)=(0111100)
3.9 Циклические коды
Рассмотрим GF(2
n
) над полем GF(2)
∀
a
~
=(a
0
,…,a
n-1
)∈GF(2
n
) можно в
дальнейшим однозначно поставить в соответствие множество a
0
+…+a
n-1
x
n-1
степени n с коэффициентами над GF(2).
Сумме двух векторов <=> сумма двух многочленов.
Произведению вектора на элемент поля <=> произведения многочленнов
на этот элемент.
Пространство GF(2
n
) можно реализовать как множество 2
n
многочленов
степени меньше n с обычными правилами сложения многочленов и умножения
на элемент поля GF(2
n
) М-ми все многочленов степени меньше n.
Существует единственный способ задавать линейное код пространство.
Фиксируем многочлен g(x)
∈
M и рассмотрим подмножество всех
многочленов f(x)
∈M, которые делятся на многочлен g(x) без остатка.
Если f
1
|g(x), f
2
|g(x)=>(f
1
+f
2
)|g(x)=> это подмножество линейное простран-
ство => определяет некоторый линейный код, которое называется полиномом.
g(x) – порождающий многочлен
C(g(x)) – полиномиальный код
C(g(x))={( a
0
,…,a
n-1
): a
0
+…+a
n-1
x
n-1
|g(x)}
Определение. Циклическим называется такой полиномиальный код
C(g(x)), которого вместе с каждым кодовым словом a=( a
0
,…,a
n-1
) содержит и
слово
a
~
=(a
n-1
,a
0
,a
1
,…,a
n-2
), полученный из a циклически сдвигом в право на одну
позицию.
Утверждение. Для того, чтобы полином код C(g(x)) был цикличным <=>
чтобы многочлен g(x) был делителем многочлена x
n
-1
g(x) – порождающий многочлен циклического кода.
Утверждение. Если многочлен g(x) имеет степень (n-k) и является дели-
телем многочлена x
n
-1, то код C(g(x)) – линейный циклический. (n,k) – код.
Замечание. Так как при
∀
n многочлен (x-1) и (x
n-1
+x
n-2
+…+1) является
делителями многочлена x
n
-1:
x
n
-1=(x-1)( x
n-1
+x
n-2
+…+1)
=> циклические коды
при ∃
∀
n
23
      Вес Ei определяется числом, исправленным разрядов.
      Принятая кодовая комбинация сравнивается с векторами в строке, соот-
ветствующей полученному в результате проверки синдрома.
      Правильное кодовое слово – в первой строке того же столбца таблицы.
      Векторы Ei не должны быть равны ни одному из векторов кода, получи-
лись бы нулевые вектора.
      Пример. (7, 4) код
         1001101 
                 
      H=  0101011 ; V=(0110100) – полученный вектор
          0010111
                 
     C=VHt=(110) совпадает с четвертым столбцом               матрицы    H.   =>
e=(0001000) => v+e=(0110100)+(0001000)=(0111100)

                              3.9 Циклические коды

      Рассмотрим GF(2n) над полем GF(2) ∀ a~ =(a0,…,an-1) ∈ GF(2n) можно в
дальнейшим однозначно поставить в соответствие множество a0+…+an-1xn-1
степени n с коэффициентами над GF(2).
      Сумме двух векторов <=> сумма двух многочленов.
      Произведению вектора на элемент поля <=> произведения многочленнов
на этот элемент.
      Пространство GF(2n) можно реализовать как множество 2n многочленов
степени меньше n с обычными правилами сложения многочленов и умножения
на элемент поля GF(2n) М-ми все многочленов степени меньше n.
      Существует единственный способ задавать линейное код пространство.
      Фиксируем многочлен g(x) ∈ M и рассмотрим подмножество всех
многочленов f(x) ∈ M, которые делятся на многочлен g(x) без остатка.
      Если f1|g(x), f2|g(x)=>(f1+f2)|g(x)=> это подмножество линейное простран-
ство => определяет некоторый линейный код, которое называется полиномом.
      g(x) – порождающий многочлен
      C(g(x)) – полиномиальный код
      C(g(x))={( a0,…,an-1): a0+…+an-1xn-1|g(x)}
      Определение. Циклическим называется такой полиномиальный код
C(g(x)), которого вместе с каждым кодовым словом a=( a0,…,an-1) содержит и
слово a~ =(an-1,a0,a1,…,an-2), полученный из a циклически сдвигом в право на одну
позицию.
      Утверждение. Для того, чтобы полином код C(g(x)) был цикличным <=>
чтобы многочлен g(x) был делителем многочлена xn-1
      g(x) – порождающий многочлен циклического кода.
      Утверждение. Если многочлен g(x) имеет степень (n-k) и является дели-
телем многочлена xn-1, то код C(g(x)) – линейный циклический. (n,k) – код.
      Замечание. Так как при ∀ n многочлен (x-1) и (xn-1+xn-2+…+1) является
делителями многочлена xn-1:
      xn-1=(x-1)( xn-1+xn-2+…+1)
      => циклические коды ∃ при ∀ n
                                                                               23

Страницы