Главная > Помехоустойчивое кодирование > Теория кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.6.2. Матрицы Адамара

Матрицы Адамара используются в теории планирования экспериментов, теории кодирования, теории связи и других областях. Хорошим введением в теорию матриц Адамара является работа Киясу [8]. Матрицей Адамара порядка называется квадратная матрица размера с элементами +1 и —1 из поля действительных чисел, такая, что

где I — единичная матрица, а матрица, транспонированная к Например,

Утвержцени 2.67. Если матрица Адамара и то .

Доказательство. Если матрица Адамара, то Это значит, что

Отсюда следует, что

Так как каждое слагаемое в левой части последнего равенства равно 0, 4 или —4, то кратно четырем.

Высказываются предположения, что существуют матрицы Адамара любого порядка кратного четырем. Однако эта гипотеза не доказана и не опровергнута. Для всех кратных четырем, за исключением матрицы Адамара найдены (для этого частично использовались вычислительные машины). Кроме того, известно также несколько конструктивных способов построения матриц Адамара. Один из этих способов дается следующим утверждением.

Утверждение 2.68. Если существуют матрицы Адамара то существует и матрица Адамара порядка

Доказательство. Пусть Тогда матрица является искомой.

Этим методом можно построить последовательность матриц Адамара, взяв, например, за основу матрицы

Рассмотрим еще один способ построения матриц Адамара, предложенный Палеем. Ряд других методов построения матриц Адамара можно найти также в книге Холла [7].

Пусть простое число. Введем функцию определив ее на множестве элементов поля следующим образом:

Утверждение 2.69.

Доказательство. Докажем утверждение 4. Пусть примитивный элемент поля Тогда

Однако так как все элементы различны, то Следовательно,

Но тогда

Утверждение 2.70. Если то

Доказательство. Если то Допустим, что Тогда в поле найдется, и притом единственный, элемент у, такой, что Когда а пробегает все ненулевые элементы поля у пробегает также все ненулевые элементы поля за исключением 1. Следовательно,

Используя приведенные выше утверждения и отождествляя элементы поля с вычетами по модулю построим следующую квадратную матрицу порядка

Утверждение простое число, такое, что то построенная выше матрица является матрицей Адамара.

Доказательство. Нужно показать, что Очевидно, что диагональные элементы матрицы равны Из части 3 утверждения 2.69 непосредственно следует, что

Покажем, что все остальные элементы матрицы В равны нулю Имеем

Положим Когда пробегает все значения от 1 до то I также пробегает все элементы поля Заметим, что в данном случае Кроме того, согласно утверждению Тогда из утверждения 2.70 следует, что

Как известно (см., например, [4]), существует бесконечная последовательность простых чисел таких, что Это означает, что описанная выше конструкция дает бесконечный класс матриц Адамара.

С помощью матриц Адамара можно строить некоторые двоичные коды. Один из таких классов кодов — это эквидистантные коды, описанные в разд. 1.4.2. Другой класс кодов, которые могут быть построены с помощью матриц Адамара, — это коды Рида — Маллера, рассматриваемые в разд. 4.5.1.

Утверждение 2.72.

1) При одновременной перестановке строк и столбцов, а также при умножении строк и столбцов матрицы Адамара на —1 опять получается матрица Адамара. В случае необходимости с помощью операций этих двух типов всегда можно получить приведенную матрицу Адамара, все элементы первой строки и первого столбца которой равны Рассмотрим матрицу размера получающуюся из приведенной матрицы Адамара порядка удалением первого столбца. Заменим в этой матрице элементы на 0, а —1 и каждую строку получающейся матрицы будем рассматривать как кодовое слово блокового кода длины Совокупность таких кодовых слов представляет собой эквидистантный код. Заметим, что этот код, вообще говоря, не является линейным.

2) Рассмотрим совокупность из векторов, первые из которых являются строками матрицы Адамара порядка а вторые получаются умножением первых на —1. Аналогично тому, как это мы сделали выше, заменим элементы на 0, а элементы —1 на 1. Полученная таким образом совокупность из двоичных векторов представляет собой блоковый код длины с кодовым расстоянием Вообще говоря, этот код также не является линейным. Однако коды этого типа, построенные на основе матриц Адамара являются не чем иным, как кодами Рида — Маллера первого порядка. Существование матриц Адамара для любого целого следует из утверждения 2.68,

<< Предыдущий параграф Следующий параграф >>
Оглавление