Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
H · H T = (det H) 2 = n n . Имеем H −1 · H · H T = nH −1 ⇒ H T = nH −1 и H T · H = nH −1 · H = nE n , т. е. H T · H = nE n . Отсюда следует также, что столбцы матрицы H обладают теми же свойствами, что и строки матрицы H. Очевидно, что перестановка строк или столбцов матрицы H, а также умножение строк или столбцов матрицы H на −1, переводят H в другую матрицу Адамара H 0 Такие матрицы Адамара будем называть эквивалентными. Это равносильно тому, что H 0 = P · H · Q, где P и Q — мономиальные матрицы перестановки длины n с элементами +1 и −1. Напомним, что матрица называется мономиальной, если в каждой строке и каждом 93 94 Глава 9. Другие коды столбце имеется точно один ненулевой элемент. В нашем случае для P и Q эти нену- левые элементы равны +1 или −1. Матрица P осуществляет перестановку и меняет знаки у строк H, а матрица Q — у столбцов. Для данной матрицы Адамара H всегда можно найти эквивалентную ей матрицу Адамара, первая строка и первый столбец которой целиком состоят из +1. Такая матрица Адамара называется нормализованной. Пример 9. При n = 1 имеем H(1) = (1), при n = 2, H(2) = µ 1 1 1 −1 ¶ , при n = 4, H(4) = 1 1 1 1 1 −1 1 −1 1 1 −1 −1 1 −1 −1 1 . Перестановка строк, кроме первой, и столбцов, кроме первого, не нарушают нор- мализованности матрицы Адамара. Но, вообще говоря, могут существовать эквива- лентные нормализованные матрицы, которые не получаются одна из другой простой перестановкой строк и столбцов. Упражнение 45. Показать, что матрицы Адамара порядков 2 и 4 существуют и единственны с точностью до эквивалентности. Матрицы Адамара порядков 8 и 12 также единственны с точностью до эквива- лентности. Существует пять неэквивалентных матриц Адамара порядка 16 и три неэквивалентных матрицы порядка 20. Для n = 24 число неэквивалентных матриц Адамара равно 60, для n = 28 таких матриц 487. Теорема 52. Если существует матрица Адамара порядка n > 2, то n кратно 4. Доказательство. Без ограничения общности предположим, что H представлена в нормализованном виде и пусть n > 2. Найдется матрица, эквивалентная матрице 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 −1 −1 · · · −1 | {z } i | {z } j | {z } k | {z } l Тогда из ортогональности строк имеем следующую систему уравнений i + j + k + l = n, i + j − k − l = 0 (умножая 1-ю и 2-ю строки), i − j − k + l = 0 (умножая 2-ю и 3-ю строки), i − j + k − l = 0 (умножая 1-ю и 3-ю строки). Решая эту систему, получаем i = j = k = l = n/4, откуда следует, что 4 делит n. N Гипотеза. Матрицы Адамара существуют для всех n ≡ 0(mod 4). 9.1. Матрицы Адамара, коды Адамара 95 Существует большое количество методов построения матриц Адамара. Наимень- ший порядок, для которого матрица Адамара не построена, равен n = 428 = 4 · 107 (2002 г.). Приведем неполный спектр значений n, для которых построены матрицы Ада- мара: 1) n = 2 r ; 2) n = p r + 1 ≡ 0(mod 4) для простого p; 3) n = h(p r + 1), где h ≥ 2 — порядок матрицы Адамара; 4) n = h(h − 1), где h — произведение чисел вида 1 и 2; 5) n = h(h + 3), где h и h + 4 — произведения чисел вида 1 и 2; 6) n = h 1 h 2 (p r + 1)p r , где h 1 , h 2 > 1 — порядки матриц Адамара. Рассмотрим два особенно важных в теории кодирования метода построения мат- риц Адамара. 9.1.2. Матрица Сильвестра Прямым, или кронекеровым, произведением двух матриц A = (a ij ) порядка m × m и B = (b ij ) порядка n × n называется матрица A × B порядка (mn × mn): A × B = a 11 B a 12 B . . . a 1m B · · · · a m1 B a m2 B . . . a mm B . Упражнение 46. Доказать свойства: 1) A × (B 1 + B 2 ) = A × B 1 + A × B 2 ; 2) (A × B)(C × D) = AC × BD. Теорема 53. Если существуют матрицы Адамара порядков m и n, то их пря- мое произведение есть матрица Адамара порядка m · n. Доказательство. Пусть H m и H n — две матрицы Адамара порядков m и n соответственно. Тогда (H m × H n )(H m × H n ) T = (H m × H n )(H T m × H T n ) = = H m · H T m × H n · H T n = mE m × nE n = mnE mn . N Отсюда легко вытекает следующий метод построения матриц Адамара. 96 Глава 9. Другие коды Теорема 54. Если H n — матрица Адамара порядка n, то H 2n = · 1 1 1 −1 ¸ × H n = · H n H n H n −H n ¸ — матрица Адамара порядка 2n. Пример 10. Матрица Адамара порядка 4, полученная из матрицы Адамара H(2): H(4) = 1 1 1 1 1 −1 1 −1 1 1 −1 −1 1 −1 −1 1 . Начиная с тривиальной матрицы H(1) = (1), методом, описанным в теореме 54, получим последовательность матриц H(1), H(2), H(4), . . . , H(2 k ) . . . Такие матрицы называются матрицами Сильвестра. Они имеют порядки, равные степени двойки 2 k , k ≥ 1. Упражнение 47. Построить матрицу Адамара H 8 9.1.3. Матрица Адамара по типу Пэйли Для описания конструкции Пэйли построения матриц Адамара, потребуются квад- ратичные вычеты и некоторые их свойства. Определение. Пусть p > 2 — простое число. Числа b 6≡ 0(mod p) делятся на два класса, называемые квадратичными вычетами и квадратичными невычетами в зависимости от того, имеет сравнение x 2 ≡ b (mod p) решение по модулю p или не имеет. Пример 11. При p = 7: 2 2 = 4(mod 7) — вычет; 3 2 ≡ 2(mod 7) — вычет (число 2 представимо в виде 3 2 , где 3 < 7); 3 — невычет, так как сравнение x 2 ≡ 3(mod 7) не имеет решения, в чем легко убедиться простым перебором; 4 2 = 16 ≡ 2(mod 7); 5 2 = 25 ≡ 4(mod 7); 6 2 = 36 ≡ 1(mod 7). Новых вычетов не получили, следовательно, 1, 2 и 4 — все вычеты по модулю 7. Для того чтобы найти все вычеты по модулю p, нужно рассмотреть все числа 1, 2, . . . , p − 1, но достаточно рассмотреть квадраты чисел от 1 до (p − 1)/2, так как (p − a) 2 ≡ a 2 (mod p). 9.1. Матрицы Адамара, коды Адамара 97 Свойства квадратичных вычетов 1. Произведение двух квадратичных вычетов или невычетов является квадра- тичным вычетом, произведение квадратичного вычета на невычет является невы- четом. 2. Критерий Эйлера. Пусть p > 2 — простое. Число a, взаимно простое с p, является квадратичным вычетом по модулю p тогда и только тогда, когда a (p−1)/2 ≡ 1(mod p) и является невычетом по модулю p тогда и только тогда, когда a (p−1)/2 ≡ −1(mod p). 3. Если p = 4k + 1, то число −1 является квадратичным вычетом, если p = 4k − 1, то число −1 является невычетом. Для доказательства этого свойства полезен следующий факт. 4. Если α — примитивный элемент поля Галуа GF (p), где p — простое, то, нетрудно показать, что квадратичные вычеты задаются четными степенями эле- мента α. Определение. Пусть p — простое нечетное число. Функция χ(i), называемая символом Лежандра, определяется на множестве целых чисел следующим образом: χ(i) = 0, если i ≡ 0(mod p); χ(i) = 1, если остаток от деления i на p является квадратичным вычетом по модулю p; χ(i) = −1, если остаток от деления i на p является квадратичным невычетом по модулю p. Теорема 55. Для любого c 6≡ 0(mod p) справедливо p−1 X b=0 χ(b)χ(b + c) = −1. Доказательство. Так как произведение двух квадратичных вычетов или невы- четов есть вычет, а произведение вычета на невычет есть невычет, то χ(xy) = χ(x)χ(y) при 0 ≤ x, y ≤ p − 1. Если b = 0, то χ(0) = 0 и вклад в сумму слагаемого при b = 0 χ(0)χ(c) = 0. Пусть b 6= 0 и пусть z такое число, что zb ≡ b + c(mod p). Если b пробегает мно- жество {1, 2, . . . , p − 1}, то z пробегает множество {0, 2, 3, . . . , p − 1} (действительно, 98 Глава 9. Другие коды так как c 6≡ 0(mod p), имеем z 6= 1). Разным числам b отвечают разные z. Пусть это не так, т. е. zb ≡ b + c (mod p) zb 0 ≡ b 0 + c (mod p) , b 6= b 0 и b, b 0 ≤ p − 1. Тогда z(b − b 0 ) ≡ b − b 0 (mod p), или (z − 1)(b − b 0 ) ≡ 0(mod p), т. е. в силу b 6= b 0 имеем z ≡ 1(mod p), что невозможно. Рассмотрим исходную сумму: p−1 X b=0 χ(b)χ(b + c) = p−1 X b=1 χ(b)χ(zb) = p−1 X b=1 (χ(b)) 2 χ(z) = p−1 X b=1 χ(b 2 )χ(z) = = p−1 X z=0 z6=1 χ(z) = p−1 X z=0 χ(z) − χ(1) = −1. Здесь p−1 P z=0 χ(z) = 0, так как половина чисел от 1 до p − 1 (p — нечетно) являются квадратичными вычетами и χ(z) для них равен 1, а половина — невычетами и χ(z) для них равен −1. N Метод построения Пэйли дает построение матрицы Адамара порядка n = p+1, кратного 4 (или порядка n = p m + 1, кратного 4, если используются квадратичные вычеты над полем GF (p m )), где p — простое. Для конструкции Пэйли потребуется матрица Джекобстола Q = (q ij ), которая является (p × p)-матрицей, где q ij = χ(j − i), строки и столбцы матрицы Q пронуме- рованы числами 0, 1, . . . , p − 1. Пример 12. При p = 7 числа 1, 2 и 4 являются квадратичными вычетами, сле- довательно, χ(1) = χ(2) = χ(4) = 1. Матрица Джекобстола имеет вид Q = 0 1 1 −1 1 −1 −1 −1 0 1 1 −1 1 −1 −1 −1 0 1 1 −1 1 1 −1 −1 0 1 1 −1 −1 1 −1 −1 0 1 1 1 −1 1 −1 −1 0 1 1 1 −1 1 −1 −1 0 . При p = 4k − 1 число −1 является квадратичным невычетом по свойству 2 и χ(−1) = −1. Поэтому q ij = χ(j − i) = χ(−1)χ(i − j) = −χ(i − j) = −q ij , следовательно, матрица Q — кососимметрическая, т. е. Q T = −Q. Имеет место следующее утверждение. Лемма 9. Справедливо QQ T = pE − J и QJ = JQ = 0 p , где J — матрица, элементами которой являются единицы, а 0 p — матрица, состоящая из нулей. 9.1. Матрицы Адамара, коды Адамара 99 Доказательство. Пусть P = (p ij T . Тогда p ii = p−1 X k=0 q 2 ik = p − 1. Если i 6= j, то p ij = p−1 X k=0 q ik q jk = p−1 X k=0 χ(k − i)χ(k − j) = p−1 X k=0 χ(k − i)χ(k − i + (i − j)) = = p−1 X b=0 χ(b)χ(b + c) = −1, где b = k − i и c = i − j по предыдущей теореме. Легко проверяется утверждение QJ = JQ = 0 p (действительно, каждый столбец и строка матрицы Q содержит равное число (p − 1)/2 элементов 1 и −1). N Построим, используя Q, матрицу H. Обозначим, как и прежде, через 1 и 0 век- торы длины p, состоящие из единиц и нулей соответственно. Теорема 56. Матрица H = µ 1 1 1 T Q − E p ¶ является матрицей Адамара (типа Пэйли). Доказательство. Рассмотрим произведение H · H T = µ 1 1 1 T Q − E p ¶ · µ 1 1 1 T Q T − E p ¶ = µ p + 1 0 0 T J + (Q − E p )(Q T − E p ) ¶ Используя предыдущую лемму и тот факт, что по определению матрицы Q выпол- няется Q + Q T = 0, получаем J + (Q − E p )(Q T − E p ) = J + Q · Q T − (Q + Q T ) + E p = J + (pE p − J) + E p = (p + 1)E p . Следовательно, H · H T = µ p + 1 0 0 T (p + 1)E p ¶ = (p + 1)E p+1 . N Другими словами, получили нормализованную матрицу Адамара типа Пэйли поряд- ка p + 1. 100 Глава 9. Другие коды 9.1.4. Коды Адамара Пусть H n — нормализованная матрица Адамара. Заменим всюду 1 на 0, а −1 на 1, тогда H n превращается в двоичную матрицу Адамара A n . Так как строки H n ортого- нальны, то любые две строки матрицы A n совпадают в n/2 позициях, следовательно, расстояние Хэмминга между ними равно n/2. Из матрицы A n построим три кода Адамара. 1. Код A n с параметрами (n − 1, n, n/2), состоящий из строк матрицы A n с выко- лотой первой координатой. Пример 13. Код Адамара A 8 с параметрами (7, 8, 4), полученный из матрицы Адамара типа Пэйли. Кодовые слова — это все циклические сдвиги вектора (1001011) и нулевой вектор длины 7. Иначе говоря, [(1001011)] = (1 0 0 1 0 1 1) (1 1 0 0 1 0 1) (1 1 1 0 0 1 0) (0 1 1 1 0 0 1) (1 0 1 1 1 0 0) (0 1 0 1 1 1 0) (0 0 1 0 1 1 1) . Пример 14. Код Адамара A 12 с параметрами (11, 12, 5), полученный из матрицы Адамара типа Пэйли: [(11011100010)], содержащий также нулевой вектор длины 11. 2. Код B n с параметрами ( |