Дуальный код и тождество Мак – Вильямс

Пусть u = (u₁….u_n) и v =(v₁…v_n) – векторы из С, а u×v = u₁ v₁ + ….+u_n v_n  - скалярное произведение u и v над F_q. Если u×v = 0, то u и v называются ортогональными.

Пусть С – линейный (n,k) – код над F_q . Дуальный (или двойственный, или ортогональный) код С для кода С определяется как ортогональное дополнение:

C  = {u  F_qⁿ  v  C : u×v = 0}.

Так как С является k-мерным подпространством n–мерного векторного пространства F_qⁿ, его ортогональное дополнение имеет размерность n-k и является (n, n-k)- кодом. Можно показать, что если код С имеет порождающую матрицу G и проверочную матрицу Н, то С  имеет порождающую матрицу H и проверочную матрицу G. Ортогональность двух кодов выражается равенствами GH^T=0, HG^T= 0.

Распределение весов кода указывает число кодовых слов каждого веса. Оно полезно для практического вычисления вероятности правильного декодирования и может быть задано в виде списка чисел А _i, где А _i – число кодовых слов веса i в данном коде, 0 ≤ i ≤ n. Для любого линейного кода А₀ всегда равно 1. Вычислим для примера распределение весов (7,4,3) – кода Хэмминга. Сумма строк порождающей матрицы этого кода равна а = (1,1,1,1,1,1,1), так что А₇ = 1. Другими ненулевыми весами могут быть только 3 и 4, так как 3 – минимальный вес, а вместе с каждым кодовым словом х коду принадлежит слово а + х. Получаем следующее распределение:

А₀ =А₇ = 1, А₃ =А₄ =7; все другие А_i равны 0.

Многочлен А(Х,У) =   называют нумератором весов кода С.

Теорема (тождество Мак - Вильямс). Пусть С – линейный ( n , k ) - код над F_q , а С - его дуальный код. Если А(Х,У) – нумератор весов кода С, А (Х,У) – нумератор весов кода С , то

А (Х,У) = 1/q^k ×A ( Y - X , Y + ( q -1) X ).

Задачи для самостоятельной работы

 

1. Какой код называют систематическим? Как выглядит проверочная матрица систематического (n,k) кода? Какая у неё размерность?

2. Что называют расстоянием Хэмминга между векторами?

3. Дайте определение минимального расстояния кода. Сколько ошибок код с минимальным расстоянием d исправляет и обнаруживает?

4. Докажите, что минимальное расстояние d линейного (n,k) кода С удовлетворяет неравенству: d £ n-k+1.

5. Напишите проверочные уравнения для линейного кода над полем F₃ с порождающей матрицей

G= .

Закодируйте информационные сообщения 101 и 221

А) не систематически; Б) систематически.

6. Определите количество кодовых слов, минимальное расстояние, число обнаруживаемых и исправляемых ошибок для кода из задания 1.

7. Приведите матрицу Н=  к стандартной форме H_сист.=(A;E). Постройте таблицу лидеров смежных классов и синдромов для систематического бинарного кода с проверочной матрицей H_сист. Декодируйте векторы 11011 и 10011.

8. Постройте поле F₉ с помощью неприводимого многочлена х²+2х+2, и проверочную матрицу кода Хэмминга С₂ над F₉. Какой вектор был передан, если получен вектор 010010a⁵0a0?

9. Найдите нумератор весов для кода С с проверочной матрицей Н= , и напишите тождество Мак-Вильямс для дуального к нему кода. Является ли код С самодуальным?

10. Докажите, что бинарные коды Хемминга совершенны.

ГЛАВА 6

 

---

Дата добавления: 2019-02-12; просмотров: 684; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!