2. 6. Нелинейные коды. Коды адамара

Для каждого линейного кода С и произвольных двух его кодовых слов х , у сумма х + у также кодовое слово, что не всегда выполняется для нелинейных кодов, хотя в большинстве случаев нелинейные коды более эффективные , чем соответствующие линейные коды .

Назовём ( n , M , d ) - кодом множество из М слов длины n ( в алфавите GF(q), в частности здесь рассмотрим алфавит GF(2) ) такое, что для любых двух слов х  у d(х , у)  d и d является наибольшим числом с таким свойством.

Из данного определения следует, что двоичный линейный [ n , k ,d ] - код является ( n , 2 ^k, d ) - кодом ( круглые скобки используются для кода, который может быть или не быть линейным ).

Будем говорить, что два ( n , M , d ) - кода эквивалентны, если один может быть получен из другого перестановкой n символов и добавлением фиксированного слова.

Скорость передачи для нелинейного кода определяется как

R = log _q M / n ,

что сводится к равенству

R = к / n ,

если код линеен.

Многие нелинейные коды строятся с помощью матриц Адамара. Это матрица H _n размерности n  n из элементов  1, такая, что

H _n H^Т_n = n Е ,

где Е -единичная матрица размерности n  n . Другими словами, скалярное произведение произвольных двух различных строк H _n в поле действительных чисел равно нулю. Так, например,

1 1 1 1

1 -1 1 -1

H ₄ = 1 1 -1 -1 .

1 -1 -1 1

Матрица Адамара H _n называется нормализованной матрицей, если её первый столбец и первая строка состоят из одних единиц ( как в матрице H ₄). Если существует матрица Адамара H _n порядка n, то n равно 1 или 2 или делится на 4 (наименьший порядок, для которого матрица Адамара ещё не построена равен 268 на 1977 г.).

Для построения матриц Адамара можно воспользоваться следующим способом. Пусть H _n и H _m - две матрицы Адамара порядков n и m соответственно. Тогда существует матрица Адамара H _nm порядка nm, для чего необходимо каждый элемент матрицы H _n заменить матрицей H _m , умноженная на этот элемент. Так, например, из матрицы

1 1

H₂ = 1 -1

можно получить матрицу H ₄ , а из H ₄ - матрицу Адамара H ₈ :

1 1 1 1 1 1 1 1

1 -1 1 -1 1 -1 1 -1

1 1 -1 -1 1 1 -1 -1

1 -1 -1 1 1 -1 -1 1

H ₈ = 1 1 1 1 -1 -1 -1 -1 .

1 -1 1 -1 -1 1 -1 1

1 1 -1 -1 -1 -1 1 1

1 -1 -1 1 -1 1 1 -1

Эти матрицы Адамара называются матрицами Сильвестра.

Назовём две матрицы Адамара эквивалентными, если одна может быть получена из другой перестановками строк и столбцов и умножением строк и столбцов на - 1.

Теперь перейдём к рассмотрению кодов Адамара.

Пусть H _n - нормализованная матрица Адамара порядка n. Если все элементы +1 заменить на 0, а элементы - 1 заменить на 1, то H _n превратится в двоичную матрицу Адамара А_n. Так как строки H _n ортогональны, то любые две строки матрицы А_n совпадают в n / 2 позициях и различаются в n / 2 позициях, и поэтому расстояние Хэмминга между ними равно n / 2.

Матрица А_n позволяет построить следующие три кода Адамара:

I. ( n - 1, n , n / 2 ) - код А_n , состоящий из строк матрицы А _n с выкинутым первым столбцом ( этот столбец состоит из одних нулей ).

Так, например, при n = 4 имеем:

А ₄ = 0 0 0 , 1 0 1 , 0 1 1 , 1 1 0 .

II. ( n - 1 , 2 n , n / 2 ) - код В₄ , состоящий из слов кода А _n и их дополнений.

При n = 4 имеем:

В₄ =  000 , 101 , 011 , 110 , 111 , 010 , 100 , 001 .

III. ( n , 2- n , n / 2 ) код С _n , состоящий из строк матрицы А _n и их дополнений.

При n = 4 имеем:

С₄ = 0000, 0101, 0011, 0110, 1111, 1010, 1100, 1001 .

В частности, если n = 2 ^r, то все три кода Адамара А _n , В_n и С_n являются линейными. В остальных случаях, коды получаемые из матриц Адамара Н _n (n 2^r), чаще всего являются нелинейными.

2.6.1. Доказать, что если n порядок матрицы Адамара, n  1 , 2, то n делится на 4.

2.6.2. Пусть u ₁,u ₂, . . . , u _n , n = 2^m, обозначают различные двоичные m- векторы. Доказать, что H _n= ( h _{i j} ) , где h _{i j} = ( - 1 )^{Ui Uj} является матрицей Адамара.

2.6.3. Построить коды Адамара А ₈ , В₈ и С₈ .

2.6.4. Установить корректирующие возможности кодов А _n , В_n и С_n .

2.6.5. Определить скорости кодов А _n , В_n и С_n .

2.6.6. Построить матрицу Адамара порядка n = P^m + 1, где Р - простое число.

2.6.7. Построить матрицы Адамара порядков 92, 116 и 172.

2.6.8. Построить коды Адамара для n = 92, 116 и 172.

2.6.9. Построить новые оптимальные коды на основе кодов Адамара

путём их склеивания.

2.6.10. Построить матрицу Адамара порядка 12n и соответствующие коды Адамара.

2.6.11. Определить, при каких n коды Адамара нелинейны.