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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Обнаружение ошибок.
Для
∀ слова x
∈
GF(2
n
) определяет соответствие ему синдром:
C=xH
t
На этом основывается метод обнаружения ошибок по синдрому.
C=0, если x – кодовое слово, иначе C
≠
0
Применение (декодирования) вычисляет по принятому слову x синдром C
Если C
0 => есть ошибки. ≠
3.8 Исправление ошибок
Рассмотрим два слова: x и x+a, где a – кодовое слово
Найдем синдромы C=xH
t
и С′=(x+a)H
t
, C′=(x+a)H
t
=xH
t
+aH
t
=xH
t
=C => все
слова полученные из некоторого слова x путем прибавления к нему всех кодо-
вых слов, имеют один и тот же синдром.
Множества таких слов образуют смежный класс x+V по подгруппе V.
Любое слово, которому соответствует синдром C, принадлежит этому же
смежному классу
Пусть x′ – некоторое слово с синдромом C: C=x′H
t
заметим : x′=x+a => C= x′H
t
=(x+a)H
t
=xH
t
+aH
t
=C+aH
t
=>aH
t
=0 => a кодо-
вое слово => x′ принадлежит смежному классу x+V.
Назовем слово минимум веса из этого смежного класса представлением
смежного класса.
∀ x∈ GF(2
n
) соответствует единственный синдром C, а каждому синдро-
му C соответствует единственный представитель смежного класса.
Декодирование
а) по принятому слову x вычисляют синдром C=xH
t
б) по виду синдрому C принятую комбинацию x относят к одному из
смежных классов ej+V.
в) в качестве результата декодирования (исправленного слова) выдается
кодовое слово x+ej
x=u+e: u – переданное слово, e – ошибка.
C=xH
t
=(u+e)H
t
=eH
t
Таблица декодера.
Вектор
ошибки e
j
Векторы образующие смежные классы e
j
+V
0 A
1
A
2
… A
2
k
-1
E
1
E
1
+A
1
E
1
+A
2
… E
1
+A
2
k
-1
E
2
E
2
+A
1
E
2
+A
2
… E
2
+A
2
k
-1
… … … … …
E
2
(n-k)
-1
E
2
(n-k)
-1
+A
1
E
2
(n-k)
-1
+A
2
… E
2
(n-k)
-1
+A
2
k
-1
A
i
– кодовые векторы
E
i
– векторы ошибок
22
     Обнаружение ошибок.
     Для ∀ слова x ∈ GF(2n) определяет соответствие ему синдром:
     C=xHt
     На этом основывается метод обнаружения ошибок по синдрому.
     C=0, если x – кодовое слово, иначе C ≠ 0
     Применение (декодирования) вычисляет по принятому слову x синдром C
     Если C ≠ 0 => есть ошибки.

                            3.8 Исправление ошибок

      Рассмотрим два слова: x и x+a, где a – кодовое слово
      Найдем синдромы C=xHt и С′=(x+a)Ht, C′=(x+a)Ht=xHt+aHt=xHt=C => все
слова полученные из некоторого слова x путем прибавления к нему всех кодо-
вых слов, имеют один и тот же синдром.
      Множества таких слов образуют смежный класс x+V по подгруппе V.
      Любое слово, которому соответствует синдром C, принадлежит этому же
смежному классу
      Пусть x′ – некоторое слово с синдромом C: C=x′Ht
      заметим : x′=x+a => C= x′Ht=(x+a)Ht=xHt+aHt=C+aHt =>aHt=0 => a кодо-
вое слово => x′ принадлежит смежному классу x+V.
      Назовем слово минимум веса из этого смежного класса представлением
смежного класса.
                 n
      ∀ x ∈ GF(2 ) соответствует единственный синдром C, а каждому синдро-
му C соответствует единственный представитель смежного класса.
      Декодирование
      а) по принятому слову x вычисляют синдром C=xHt
      б) по виду синдрому C принятую комбинацию x относят к одному из
смежных классов ej+V.
      в) в качестве результата декодирования (исправленного слова) выдается
кодовое слово x+ej
      x=u+e: u – переданное слово, e – ошибка.
      C=xHt=(u+e)Ht=eHt

     Таблица декодера.

  Вектор          Векторы образующие смежные классы ej+V
 ошибки ej
     0             A1            A2         …             A2k-1
    E1          E1+A1         E1+A2         …          E1+A2k-1
    E2          E2+A1         E2+A2         …          E2+A2k-1
    …              …             …          …              …
  E2(n-k)-1     (n-k)
              E2 -1+A1        (n-k)
                            E2 -1+A2        …        E2 -1+A2k-1
                                                       (n-k)



     Ai – кодовые векторы
     Ei – векторы ошибок
22

Страницы