ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА МЕТОДОМ СКАРПИ
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев
УДК 519.61:511-33
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА МЕТОДОМ СКАРПИ
Н.А. Балонинa, Ю.Н. Балонинa, М.Б. Сергеевa, b
a Санкт-Петербургский государственный университет аэрокосмического приборостроения (ГУАП), Санкт-Петербург, Россия, korbendfs@mail.ru b НИИ информационно-управляющих систем, Университет ИТМО, Санкт-Петербург, Россия, mbse@mail.ru
Постановка проблемы. Основные обобщения матриц Адамара связывают с матрицами максимального детерминанта или с не оптимальными по детерминанту матрицами с ортогональными столбцами (взвешенные матрицы, матрицы Мерсенна, Эйлера и т.п.); способы вычисления квазиортогональных матриц Мерсенна локального максимума детерминанта изучены недостаточно полно. Целью работы является развитие теории матриц Мерсенна и Адамара изучением обобщенного метода Скарпи. Методы. Экстремальные решения ищутся, в общем, минимизацией максимума абсолютных значений элементов исследуемых матриц с последующей классификацией их по количеству и значениям уровней, зависящих от порядков. Менее универсальные, но более эффективные методы опираются на структурные инварианты квазиортогональных матриц (методы Сильвестра, Пэли, Скарпи и т.п.). Результаты. Рассматриваются обобщения матриц Адамара и Белевича на нечетные порядки в виде семейства квазиортогональных матриц, в частности, к ним принадлежат двухуровневые матрицы Мерсенна. Даны определения слоя и сечения на множестве всех обобщенных матриц. Приведены алгоритмы вычисления матриц соседствующих слоев и сечений по матрицам меньшего порядка. Приводятся примеры аппроксимации, вплоть до критичного порядка 22, структур матриц Белевича матрицей Мерсенна третьего порядка. Приводится новая формулировка модифицированного метода Скарпи аппроксимации матриц Адамара высоких порядков матрицами Мерсенна низких порядков. Метод Вильямсона раскрывается примером приближения модульно одноуровневых матриц матрицами с малым количеством уровней. Практическая значимость. Обосновывается эффективность развиваемого направления для построения полосовых фильтров. Алгоритмы нахождения матриц Мерсенна методом Скарпи использованы при построении исследовательского программного комплекса. Субоптимальные по детерминанту матрицы составляют основу фильтров Мерсенна и применяются для сжатия и маскирования изображений.
Ключевые слова: ортогональные матрицы, матрицы Адамара, матрицы Белевича, матрицы Мерсенна, числа Мерсенна, метод Скарпи, массив Вильямсона, защита видеоданных.
MERSENNE AND HADAMARD MATRICES CALCULATION BY SCARPIS METHOD
N.A. Balonina, Yu.N. Balonina, M.B. Sergeeva, b
a Saint Petersburg State University of Aerospace Instrumentation (SUAI), Saint Petersburg, Russia, korbendfs@mail.ru b Research Institute of Information and Control Systems, ITMO University, mbse@mail.ru
Purpose. The paper deals with the problem of basic generalizations of Hadamard matrices associated with maximum determinant matrices or not optimal by determinant matrices with orthogonal columns (weighing matrices, Mersenne and Euler matrices, ets.); calculation methods for the quasi-orthogonal local maximum determinant Mersenne matrices are not studied enough sufficiently. The goal of this paper is to develop the theory of Mersenne and Hadamard matrices on the base of generalized Scarpis method research. Methods. Extreme solutions are found in general by minimization of maximum for absolute values of the elements of studied matrices followed by their subsequent classification according to the quantity of levels and their values depending on orders. Less universal but more effective methods are based on structural invariants of quasi-orthogonal matrices (Silvester, Paley, Scarpis methods, ets.). Results. Generalizations of Hadamard and Belevitch matrices as a family of quasi-orthogonal matrices of odd orders are observed; they include, in particular, two-level Mersenne matrices. Definitions of section and layer on the set of generalized matrices are proposed. Calculation algorithms for matrices of adjacent layers and sections by matrices of lower orders are described. Approximation examples of the Belevitch matrix structures up to 22-nd critical order by Mersenne matrix of the third order are given. New formulation of the modified Scarpis method to approximate Hadamard matrices of high orders by lower order Mersenne matrices is proposed. Williamson method is described by example of one modular level matrices approximation by matrices with a small number of levels. Practical relevance. The efficiency of developing direction for the band-pass filters creation is justified. Algorithms for Mersenne matrices design by Scarpis method are used in developing software of the research program complex. Mersenne filters are based on the suboptimal by determinant matrices and are used for image masking and compression.
Keywords: orthogonal matrices, Hadamard matrices, Belevitch matrices, Mersenne matrices, Mersenne numbers, Scarpis method, Williamson array, video information protection.
Введение
Матрицы, в том числе ортогональные и квазиортогональные, нашли применение в задачах обработки изображений с целью их сжатия, маскирования, помехоустойчивого кодирования [1–3]. В работе [4] приведены алгоритм и программа поиска и исследования М-матриц [5], частными представителями которых являются матрицы Адамара [6], Мерсенна [7], Эйлера [8] и Ферма [9]. Матрицы перечислены в последовательности убывания переменной d в значении их порядка n = 4k–d, где d = 0, 1, 2, 3.
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
103
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА ... .
Тема матриц Адамара возникла после публикации им в работе [6] неравенства для оценки значения модуля определителя матрицы сверху и пары оригинальных матриц 12-го и 20-го порядка (помимо основной последовательности Сильвестра), на которых достигается максимальная оценка.
Спустя четыре года итальянский математик Умберто Скарпи опубликовал первый оригинальный метод их нахождения [10], содержание которого сводится к тому, чтобы рассчитывать матрицы высоких порядков на основании матриц более низких порядков. В отношении некоторых матриц результат не был превзойден более поздним подходом Пэли [11], нашедшим применение теории конечных полей Галуа для построения матриц Адамара с помощью символов Лежандра. Отметим, что порядки матриц, найденных Скарпи, (n–1)n для n = 4k, где k = 1, 2, 3…, кратны порядкам матриц Мерсенна. Настоящая работа раскрывает это обстоятельство глубже и показывает новые способы вычисления матриц Мерсенна, Белевича [12] и Адамара, а также их приближений на основании того, что мы будем называть подходом или методом Скарпи.
Слои и сечения матриц
Напомним: матрица Мерсенна Mn [7] – квадратная матрица порядка n = 4k–1 с элементами {1, –b},
такая, что
М
Т n
Мn
In .
Здесь
In
–
единичная
матрица,
(n
1)
(n 2
1)b 2
,
причем
b
1 2
при n = 3, в
остальных
случаях
b
q 4q q4
,
где
q=
n+1.
Количество
элементов
b
в
каждом
столбце
матрицы
на
еди-
ницу меньше количества единичных элементов. В качестве примера на рис. 1 приведена матрица третьего порядка, построенная для первого числа
Мерсенна n = 2k–1 = 3 при k =2. Название матриц связано с числами Мерсенна, для которых в [7] опубли-
кован алгоритм их нахождения. Здесь черный цвет соответствует –b (или 1 у матриц Адамара), а белый – единице.
аб Рис. 1. Портрет матрицы M3 (а) и гистограмма модулей ее элементов (б)
Определение. Слоем матриц семейства Адамара будем называть совокупность квазиортогональных матриц с известными функциями зависимости значений элементов (уровней) матриц слоя от заданных показателем d значений порядков.
Матрицы Адамара, Мерсенна и Эйлера, согласно [6–8], образуют слои для n = 4k–d при d = 0, 1, 2 соответственно. Матрицы Ферма такого непрерывного слоя не образуют, поскольку для них функции уровня определены на узком множестве значений n = 2k+1 при четных k [9].
Следствием такого подхода к классификации матриц семейства Адамара является представление о том, что все названные выше объекты являются проявлением одного математического объекта, данного совокупностью слоев и сечений – матриц соседних слоев для заданных показателем k значений порядков.
Нахождение любой матрицы сечения автоматически влечет за собой нахождение всех остальных, поскольку они отражают одно и то же: матрицы сечения взаимно зависимы. Например, матрица Адамара H4 получается из приведенной выше матрицы Мерсенна M3 округлением ее отрицательных элементов до значения –1 с добавлением каймы в виде строки и столбца с отрицательными элементами для соблюдения баланса положительных и отрицательных элементов. Этот алгоритм построения матриц Адамара напрямую использует свойство общности, вытекающие из близости матриц сечения соседствующих слоев. На рис. 2 он продемонстрирован на примере нахождения матрицы Адамара 12-го порядка (предложенного в работе [6]), но на основе матрицы Мерсенна M11.
Помимо матриц одного сечения, в соответствии с подходом Скарпи, можно опираться на близость матриц соседствующих сечений – данный аспект темы раскроем на примере алгоритма построения матриц Белевича.
104
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 3 (91)
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев
аб Рис. 2. Портреты матриц Мерсенна (M11) (а) и Адамара (H12) (б)
Построение матриц Белевича на основе матриц Мерсенна
Из матриц, на два порядка меньших матриц Адамара и тесно связанных с ними, известны симмет-
ричные конференц-матрицы Белевича Cn [12] – квадратные матрицы порядков n с элементами {1, –1} и
нулевой
диагональю,
такие,
что
C
Т n
Cn
(n 1) In
.
Известно,
что
они
не
существуют
для
значений
n–1,
не
разложимых на сумму квадратов двух целых чисел. Для n = 22, например, найдена иная – шестиуровне-
вая квазиортогональная матрица с экстремальным значением определителя [13]. Хотя такие матрицы
слоя не образуют, с их помощью можно найти некоторые матрицы Адамара согласно алгоритму Пэли в
виде
H2n
Cn I
Cn
I
Cn Cn
I I
.
Вопрос возможности построения матриц Белевича достаточно сложен для исследования, посколь-
ку нет достоверных сведений относительно пропуска в последовательности этих матриц уже при n = 66.
Первый проблемный порядок матриц Адамара – 668. Приведенный выше критерий существования каса-
ется не столько матриц Белевича, сколько вообще всех рациональных матриц, и ничего на эту тему не
говорит. Тем больший интерес представляет использование для их вычисления М-матриц, включающих
матрицы с иррациональными значениями коэффициентов [5].
Матрица Белевича связана с матрицей Адамара удвоенного порядка, в отношении которой уже из-
вестна ее связь с матрицами Мерсенна порядка n–1. Следовательно, по матрице М131 можно найти, например, проблемную для 66-го порядка матриц Белевича матрицу H132. Но больший интерес сейчас для нас представляет возможность построения матриц Белевича (и Адамара) с помощью матриц Мерсенна
значительно меньших по сравнению с ними порядков.
В том, что это возможно, убеждают примеры, дающие представление о связности того единого
объекта, который они собой представляют. В самом деле, анализ показывает, что первые две матрицы
Белевича С6 и С10 строятся без видимого изменения структуры матрицы M3 ее округлением и копированием с добавлением обязательных нулевых элементов диагонали, отображаемых на рис. 3 клетками се-
рого цвета.
аб Рис. 3. Портреты матриц Белевича: вариант С6 (а); вариант С10 (б)
Для согласования размерности матрица десятого порядка С10 снабжается каймою из 1. Несложно заметить, что знаки блоков матриц Белевича отвечают логике знаков элементов матриц H2 и М3 (обобщение правила кронекерова произведения при нахождении сложносоставных матриц Пэли). На этом
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
105
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА ... .
возможности структуры третьего порядка должны, казалось бы, исчерпаться. Однако еще Скарпи заметил, что остается степень свободы в том, чтобы, не меняя структуры, циклически сдвигать столбцы блоков, например, по мере удаления их от диагонали (рис. 4).
аб Рис. 4. Портреты матриц Белевича: вариант С14 (а); вариант С18 (б)
Матрица С14 (рис. 4, а) имеет двойную кайму, у блоков за пределами первой и второй блочных диагоналей смещены столбцы. У матрицы С18 (рис. 4, б) возникают моноблоки (специфический разрыв, обеспечивающий ортогональность столбцов с потерей структуры блока) – шесть закрашенных черным внедиагональных блоков третьего порядка.
Вычисление матриц высокого порядка на основе матриц Адамара низкого порядка характерно для альтернативного конструкциям Пэли метода Скарпи. Очевидно, рассмотренный способ его развивает, но касается он уже матриц Белевича. Замещение элементов, возникающее здесь, впервые встречается в алгоритме построения конструкций Пэли (при замене нулевых элементов единичными). В рассматриваемом варианте замещаются не элемент, а цепочки блоков, которые тоже можно разместить на диагонали.
Следующей матрицы С22, как известно, не существует, поскольку число n–1 = 21 не разлагается на сумму двух квадратов.
Таким образом, напрашивается парадоксальный вывод: все матрицы Адамара порядка n, кратного 4, до n = 40 включительно строятся на основе лишь матрицы Мерсенна M3: матрицы M3, H4 принадлежат одному сечению, из H4 получаем H8, H16, H32, матрицы С6, С10, С14, С18 связаны с M3 и дают промежуточные матрицы H12, H20, H24, H28, H36, H40, удвоениями порядка по Сильвестру можно получить и большее количество таких матриц. Матрица H44 – рубежная как раз потому, что С22 не существует, т.е. возникает кризис структуры с переходом к следующей «ведущей» матрице Мерсенна. Распространение структурных инвариантов матриц малых порядков на старшие порядки представляет существенный практический интерес.
Приближение матриц Адамара матрицами Мерсенна
Проблемные порядки матриц Адамара, для которых производительность современных вычисли-
тельных машин не позволяет пока их вычислить методом Вильямсона [14], хорошо известны – это 668,
716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964 и т.п. Отметим, что вчетверо меньшие
значения – это порядки матриц Мерсенна относительно небольших порядков.
Иными словами, здесь правомерно применение разновидности метода Скарпи с использованием
блочно-составных структур четвертого порядка. Ограничение на число блоков (четыре) препятствует
точной аппроксимации матриц Адамара меньшими по размерам их матрицами, но это путь получения
(как было видно выше на матрицах Белевича) точного или достаточно близкого к ним приближения.
Среди ортогональных структур четвертого порядка хорошо известен массив Вильямсона [14]
w1 w2 w3 w4
W
=
w2 w3 w4
w1 w4 w3
w4 w1 w2
w3
.
w2 w1
Замещение элементов этого массива четырьмя так называемыми матрицами Вильямсона (или, для
близкой структуры, матрицами Гетхальса–Зейделя) позволило найти перебором элементов все предыду-
щие столь же проблемные матрицы Адамара. К сожалению, количество операций перестановок их эле-
ментов слишком велико (даже при упрощении структур матриц Вильямсона до некоторых циклических,
связанных с задающими их векторами), а, главное, это не имеет серьезной перспективы, поскольку не
дает принципиального решения – обнаружение очередной матрицы отодвигает проблемный порядок, и
только.
106
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 3 (91)
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев
Так как в нашем распоряжении находится только одна матрица Мерсенна (или Эйлера [8], что также возможно) вчетверо меньшего порядка, удвоим ее, взяв в качестве первой матрицы Вильямсона модульно двухуровневую матрицу Мерсенна, а в качестве остальных трех – ее же, но с коэффициентами, округленными до значений {1, –1}. Тем самым относительное количество вещественных коэффициентов убывает вчетверо, и остается возможность обеспечить ортогональность расчетом варьируемого уровня b. Приравняем друг к другу последние три коэффициента массива Вильямсона, инвертируем по знаку три нижних его строки и переставим местами второй и третий столбец. Такая структура встречается, например, при симметрировании матрицы Белевича С4, при которой она утрачивает свой диагональный вид. Для большей определенности будем называть структуру Пропусом (Propuses, Близнец), поскольку матрицы Эйлера и Мерсенна всегда идут парами и дают парные матрицы.
Работоспособность подхода Скарпи подтверждается тем, что стартовые матрицы Мерсенна М3 и Эйлера Е6 сразу переходят в матрицы Адамара H12 = W12 и H24 = W24. Отрыв от аппроксимируемой таким способом структуры матриц Адамара начинается только с применения матрицы М7. Не меняя существенно матрицу W28, предложенный в работе [4] алгоритм сжатия ее адамаровой нормы позволяет свести итог к матрице Адамара H28, что демонстрируется на рис. 5.
аб Рис. 5. Портреты матриц Вильямсона W28 (а) и Адамара H28 (б)
аб Рис. 6. Портрет матрицы M167 (а) и гистограмма модулей ее элементов (б)
аб Рис. 7. Портрет матрицы приближения к H668 (а) и гистограмма модулей ее элементов (б)
Задача нахождения матрицы Адамара H28 решается редукцией структуры: измененная сжатием одна из четырех матриц Вильямсона содержит в явном виде не М7, а уже встречавшиеся при построении матриц Белевича моноблоки и матрицу Мерсенна М3. То, что за матрицами Вильямсона стоят матрицы Мерсенна, ранее в литературе не обсуждалось. Заметим, что и сами по себе матрицы Мерсенна стремятся
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
107
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА ... .
с ростом порядка к матрицам Адамара, поскольку их коэффициент b приближается к 1. Например, матрица Мерсенна относительно малого 167-го порядка, судя по гистограмме ее уровней, уже немногим отличается от матрицы Адамара (рис. 6).
Даже без сжатия (адаптации структуры) коэффициент b, характеризующий приближение массива Вильямсона с этой матрицей Мерсенна к матрице Н668, составляет около 70% от максимально возможного уровня (рис. 7).
Модификация метода Скарпи
Наиболее интересный результат можно получить, находя при помощи матриц Мерсенна низкого порядка тот же самый сорт матриц порядка более высокого. Для учета условий ортогональности применим циклическую перестановку столбцов блоков, принесшую заметный успех при построении матриц Белевича. Поскольку в оригинале [10] еще отсутствует понятие матриц Мерсенна с их естественным разделением множества всех элементов на целые (1) и вещественные (–b), идея прежнего метода Скарпи не может быть выражена в столь простой формулировке, как приводимая ниже.
Модифицированный алгоритм. Любую матрицу Мерсенна порядка n, где n – простое число, можно вставить саму в себя с циклическим сдвигом, пропорциональным ее положению, используя в качестве каймы замещаемый элемент матрицы: после нормализации и усечения каймы получим снова матрицу Мерсенна.
Величина циклического сдвига столбцов равна произведению индексов элементов расширяемой матрицы, отсчет их начинается с 0.
Стартовый элемент каймы блока (пересечение первых его строки и столбца) выбирается отрицательным. Под нормализацией подразумевается выравнивание знаков первого столбца и строки итоговой матрицы так, чтобы они были отрицательными – усечение каймы воспроизводит их количественный дефицит на единицу в матрице Мерсенна, но теперь уже порядка n2+n–1. Коэффициент –b ее рассчитывается заново согласно определению. Отметим, что полином n2+n–1=0 имеет корни, равные по модулю числам золотого сечения, т.е. известная в математике пропорция, так или иначе, лежит в основе этого построения.
В качестве примера возьмем матрицу Мерсенна M7, применим ее не для построения матрицы Вильямсона, а увеличим число блоков составной матрицы до значения ее порядка, вставляя матрицу саму в себя согласно алгоритму. После нормализации и усечения общей каймы получим матрицу Мерсенна M55. Побочный продукт этого алгоритма – промежуточная матрица Адамара, поскольку это матрицы одного сечения (рис. 8). Показана матрица Адамара H56 до ее нормализации, что позволяет наблюдать структуру и характер сдвигов столбцов размножаемой матрицы.
аб Рис. 8. Портреты матриц Мерсенна (M7) (а) и Адамара (H56) (б)
Фильтр Мерсенна
Для многих приложений вычислительной математики, теории кодирования, цифровой обработки сигналов и др. важным требованием является простота и конечность множества значений функций ортонормированных систем. Первая из таких систем – система Радемахера – была построена как существенное упрощение аналога тригонометрической системы функций. Функции Радемахера имеют всего два значения {1, –1}, но их недостаток состоит в том, что система неполна и, следовательно, не является базисом в гильбертовом пространстве L2. Полная система впервые была введена Дж. Уолшем. В отличие от функций Радемахера, функции Уолша можно разделить на четные и нечетные, этим они аналогичны синусам и косинусам. Такие функции применяются в практике помехоустойчивого сжатия и маскирования изображений, заменяя матрицу дискретного косинусного преобразования матрицей Адамара–Уолша в классическом тракте JPEG-алгоритма сжатия изображения [1, 3, 5].
Фильтр, построенный на матрице Мерсенна, будем называть фильтром Мерсенна.
108
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 3 (91)
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев Матрицы Мерсенна − двухуровневые, они содержат только элементы двух значений {1, −b} и до-
пускают упорядочивание их строк и столбцов перестановками, результаты которых представлены на рис. 9.
аб Рис. 9. Портрет матриц Мерсенна-Уолша M7 (a) и Мерсенна-Уолша M31 (б)
Пример применения фильтра Мерсенна на основе матрицы M7 к модельному изображению приведен на рис. 10.
аб Рис. 10. Модельное изображение «Мария» (a) и матрица прореженных фильтром Мерсенна значений
ее двухмерного спектра (б)
Исходное и отфильтрованное изображения сравнивались по объемам, достигаемым алгоритмом статистической компрессии PNG (Portable Network Graphics). Исходное изображение перед обработкой имеет объем 37 кБ, обработанное фильтром Мерсенна составляет 32 кБ при малом сжатии, которое уменьшается до 26 кБ и ниже при высоком, более детально технология раскрыта в работах [15, 16].
Систему ортогональных функций, порождаемых упорядоченными по частоте столбцами матриц Мерсенна, будем называть системой функций Мерсенна–Уолша по аналогии с классическими функциями Уолша. Перечислим ее отличительные особенности и назовем причины, по которым такой базис сигналов может быть интересным. Система функций Мерсенна–Уолша − двухуровневая, такая же, как и классическая система. Она отличается от функций Уолша пониженным по амплитуде нижним значением −b, которое с ростом размерности системы стремится к −1. В этом смысле она не совпадает с системой функций Уолша, но является достаточно близкой аппроксимацией ее на нечетных значениях порядка. Систему функций Мерсенна–Уолша характеризует пониженное на единицу количество порождающих ее элементов столбцов матрицы Мерсенна, т.е. она более проста для вычисления, чем классическая.
Любой базис отличает предпочтительная область его применения. Система функций Мерсенна– Уолша более высокочастотная, чем система функций Уолша, в ее составе нет функции нулевой частоты (константы). Таким образом, она более предпочтительна для построения полосовых фильтров изображений (для обработки рисунков, где отсутствует монотонный фон). Первые единичные столбец и строка нормализованных матриц Адамара представляют собой ненужную составляющую, которая у полосовых фильтров никакой нагрузки не несет, поскольку отвечает частоте, которую они фильтруют. Иначе говоря, она означает лишние затраты процессорного времени. Однако заметим, что простое удаление канвы матрицы Адамара отбрасыванием ее первых строки и столбца нарушает ортогональность столбцов усеченной матрицы.
Заключение
Для ряда приложений квазиортогональных матриц к помехоустойчивому кодированию информации, маскированию изображений и защите видеоданных целочисленные значения их элементов далеко
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
109
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА ... .
не столь важны, как высокая размерность решаемой задачи и наличие экстремальных качеств [1, 3–5, 17], которыми обладают матрицы Адамара и все близкие к ним матрицы их семейства. В работе подведены некоторые итоги использования алгоритма и программы исследования М-матриц [4].
Построение матриц Белевича при помощи матриц Мерсенна в настоящей работе публикуется впервые. Это означает, что матрицы Адамара и Белевича более высоких порядков достижимы не только при помощи матриц Мерсенна ближайшего к ним среза – имеются и более дальние связи. Приведенный в работе подход показывает вариант замены известного кронекерова произведения матриц Адамара, введенный еще Пэли, операциями с каймой и сдвигами столбцов матриц Мерсенна. Отсутствие некоторых матриц Белевича получило объяснение естественным исчерпанием комбинаторной возможности, сопровождаемой появлением в их составе моноблоков (разрыв структуры).
Матрицы Белевича и Адамара далеко не всегда являются конечной целью таких алгоритмов, поскольку известны приложения, например, при моделировании квазикристаллов [18, 19], в которых содержательная сторона задачи связывается c модульно двухуровневыми матрицами. По простоте и надежности поиска матрицы Мерсенна предпочтительнее матриц Адамара. Они занимают в тетраде матриц Адамара, Мерсенна, Эйлера и Ферма наиболее удаленное положение от матриц порядка 4k–3, на котором наблюдается отсутствие явно выделенного и проходящего по всем порядкам матриц слоя. Справа и слева (по порядкам) от матриц Мерсенна находятся связанные с ними взаимно-однозначным соответствием матрицы Адамара и Эйлера.
Модификация алгоритма поиска матриц Белевича с циклической перестановкой столбцов позволяет непосредственно вычислять матрицы Мерсенна и Адамара высоких порядков, недостижимых при использовании метода Пэли [11]. Снижение числа блоков и отказ от перестановок элементов матрицы Мерсенна позволяет эффективно находить приближения матриц Адамара высоких проблемных порядков при имеющейся мощности вычислительной техники.
Литература
1. Мироновский Л.А., Слаев В.А. Стрип-метод преобразования изображений и сигналов. СПб: Политехника, 2006. 163 с.
2. Ерош И.Л., Сергеев А.М., Филатов Г.П. О защите цифровых изображений при передаче по каналам связи // Информационно-управляющие системы. 2007. № 5. С. 20–22.
3. Балонин Ю.Н., Востриков А.А., Сергеев М.Б. О прикладных аспектах применения М-матриц // Информационно-управляющие системы. 2012. № 1. С. 92–93.
4. Балонин Ю.Н., Сергеев М.Б. Алгоритм и программа поиска и исследования М-матриц // Научнотехнический вестник информационных технологий, механики и оптики. 2013. № 3 (85). С. 82–86.
5. Балонин Н.А., Сергеев М.Б. М-матрицы // Информационно-управляющие системы. 2011. № 1. С. 14– 21.
6. Hadamard J. Résolution d'une question relative aux determinants // Bulletin des Sciences Mathématiques. 1893. V. 17. P. 240–246.
7. Балонин Н.А., Сергеев М.Б., Мироновский Л.А. Вычисление матриц Адамара-Мерсенна // Информационно-управляющие системы. 2012. № 5. С. 92–94.
8. Балонин Н.А., Сергеев М.Б. О двух способах построения матриц Адамара-Эйлера // Информационноуправляющие системы. 2013. № 1 (62). С. 7–10.
9. Балонин Н.А., Сергеев М.Б., Мироновский Л.А. Вычисление матриц Адамара-Ферма // Информационно-управляющие системы. 2012. № 6 (61). С. 90–93.
10. Scarpis U. Sui determinanti di valore Massimo // Rendiconti della R. Istituto Lombardo di Scienze e Lettere. 1898. V. 31. P. 1441–1446.
11. Paley R.E.A.C. On orthogonal matrices // Journal of Mathematics and Physics. 1933. V. 12. P. 311–320. 12. Belevitch V. Theorem of 2n-terminal networks with application to conference telephony // Electronic Com-
munications. 1950. V. 26. P. 231–244. 13. Балонин Ю.Н., Сергеев М.Б. М-матрица 22-го порядка // Информационно-управляющие системы.
2011. № 5. С. 87–90. 14. Williamson J. Hadamard’s Determinant Theorem and the Sum of Four Squares // Duke Math. J. 1944. V.11.
P. 65–81. 15. Балонин Н.А., Сергеев М.Б. О расширении ортогонального базиса в задачах сжатия видеоизображе-
ний // Вестник компьютерных и информационных технологий. 2014. № 2 (116). С. 11–15. 16. Востриков А.А., Балонин Ю.Н. Матрицы Адамара-Мерсенна как базис ортогональных преобразова-
ний в маскировании видеоизображений // Изв. вузов. Приборостроение. 2014. Т. 57. № 1. С. 15–19. 17. Балонин Н.А., Сергеев М.Б. Матрицы локального максимума детерминанта // Информационно-
управляющие системы. 2014. № 1 (68). С. 2–15. 18. Балонин Н.А., Сергеев М.Б. Матрица золотого сечения G10 // Информационно-управляющие системы.
2013. № 6 (67). С. 2–5.
110
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 3 (91)
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев
19. Балонин Н.А., Сергеев М.Б. М-матрицы и кристаллические структуры // Вестник Магнитогорского государственного технического университета им. Г.И. Носова. 2013. № 3 (43). С. 58–62.
Балонин Николай Алексеевич Балонин Юрий Николаевич Сергеев Михаил Борисович
– доктор технических наук, доцент, профессор, Санкт-Петербургский государственный университет аэрокосмического приборостроения
(ГУАП), Санкт-Петербург, Россия, korbendfs@mail.ru – программист, Санкт-Петербургский государственный университет
аэрокосмического приборостроения (ГУАП), Санкт-Петербург, Россия, tomaball@mail.ru
– доктор технических наук, профессор, зав. кафедрой, СанктПетербургский государственный университет аэрокосмического приборостроения (ГУАП), Санкт-Петербург, Россия; директор, НИИ
информационно-управляющих систем, Университет ИТМО, mbse@mail.ru
Nikolai A. Balonin
Yuri N. Balonin Mikhail B. Sergeev
– Professor, D.Sc., Associate professor, Saint Petersburg State University of Aerospace Instrumentation (SUAI), Saint Petersburg, Russia,
korbendfs@mail.ru – programmer, Saint Petersburg State University of Aerospace Instrumentation
(SUAI), Saint Petersburg, Russia, tomaball@mail.ru – D.Sc., Professor, Department head; Saint Petersburg State University of
Aerospace Instrumentation (SUAI), Saint Petersburg, Russia; Director, Research Institute of Information and Control Systems, ITMO University,
mbse@mail.ru
Принято к печати 18.02.2014 Accepted 18.02.2014
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
111
УДК 519.61:511-33
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА МЕТОДОМ СКАРПИ
Н.А. Балонинa, Ю.Н. Балонинa, М.Б. Сергеевa, b
a Санкт-Петербургский государственный университет аэрокосмического приборостроения (ГУАП), Санкт-Петербург, Россия, korbendfs@mail.ru b НИИ информационно-управляющих систем, Университет ИТМО, Санкт-Петербург, Россия, mbse@mail.ru
Постановка проблемы. Основные обобщения матриц Адамара связывают с матрицами максимального детерминанта или с не оптимальными по детерминанту матрицами с ортогональными столбцами (взвешенные матрицы, матрицы Мерсенна, Эйлера и т.п.); способы вычисления квазиортогональных матриц Мерсенна локального максимума детерминанта изучены недостаточно полно. Целью работы является развитие теории матриц Мерсенна и Адамара изучением обобщенного метода Скарпи. Методы. Экстремальные решения ищутся, в общем, минимизацией максимума абсолютных значений элементов исследуемых матриц с последующей классификацией их по количеству и значениям уровней, зависящих от порядков. Менее универсальные, но более эффективные методы опираются на структурные инварианты квазиортогональных матриц (методы Сильвестра, Пэли, Скарпи и т.п.). Результаты. Рассматриваются обобщения матриц Адамара и Белевича на нечетные порядки в виде семейства квазиортогональных матриц, в частности, к ним принадлежат двухуровневые матрицы Мерсенна. Даны определения слоя и сечения на множестве всех обобщенных матриц. Приведены алгоритмы вычисления матриц соседствующих слоев и сечений по матрицам меньшего порядка. Приводятся примеры аппроксимации, вплоть до критичного порядка 22, структур матриц Белевича матрицей Мерсенна третьего порядка. Приводится новая формулировка модифицированного метода Скарпи аппроксимации матриц Адамара высоких порядков матрицами Мерсенна низких порядков. Метод Вильямсона раскрывается примером приближения модульно одноуровневых матриц матрицами с малым количеством уровней. Практическая значимость. Обосновывается эффективность развиваемого направления для построения полосовых фильтров. Алгоритмы нахождения матриц Мерсенна методом Скарпи использованы при построении исследовательского программного комплекса. Субоптимальные по детерминанту матрицы составляют основу фильтров Мерсенна и применяются для сжатия и маскирования изображений.
Ключевые слова: ортогональные матрицы, матрицы Адамара, матрицы Белевича, матрицы Мерсенна, числа Мерсенна, метод Скарпи, массив Вильямсона, защита видеоданных.
MERSENNE AND HADAMARD MATRICES CALCULATION BY SCARPIS METHOD
N.A. Balonina, Yu.N. Balonina, M.B. Sergeeva, b
a Saint Petersburg State University of Aerospace Instrumentation (SUAI), Saint Petersburg, Russia, korbendfs@mail.ru b Research Institute of Information and Control Systems, ITMO University, mbse@mail.ru
Purpose. The paper deals with the problem of basic generalizations of Hadamard matrices associated with maximum determinant matrices or not optimal by determinant matrices with orthogonal columns (weighing matrices, Mersenne and Euler matrices, ets.); calculation methods for the quasi-orthogonal local maximum determinant Mersenne matrices are not studied enough sufficiently. The goal of this paper is to develop the theory of Mersenne and Hadamard matrices on the base of generalized Scarpis method research. Methods. Extreme solutions are found in general by minimization of maximum for absolute values of the elements of studied matrices followed by their subsequent classification according to the quantity of levels and their values depending on orders. Less universal but more effective methods are based on structural invariants of quasi-orthogonal matrices (Silvester, Paley, Scarpis methods, ets.). Results. Generalizations of Hadamard and Belevitch matrices as a family of quasi-orthogonal matrices of odd orders are observed; they include, in particular, two-level Mersenne matrices. Definitions of section and layer on the set of generalized matrices are proposed. Calculation algorithms for matrices of adjacent layers and sections by matrices of lower orders are described. Approximation examples of the Belevitch matrix structures up to 22-nd critical order by Mersenne matrix of the third order are given. New formulation of the modified Scarpis method to approximate Hadamard matrices of high orders by lower order Mersenne matrices is proposed. Williamson method is described by example of one modular level matrices approximation by matrices with a small number of levels. Practical relevance. The efficiency of developing direction for the band-pass filters creation is justified. Algorithms for Mersenne matrices design by Scarpis method are used in developing software of the research program complex. Mersenne filters are based on the suboptimal by determinant matrices and are used for image masking and compression.
Keywords: orthogonal matrices, Hadamard matrices, Belevitch matrices, Mersenne matrices, Mersenne numbers, Scarpis method, Williamson array, video information protection.
Введение
Матрицы, в том числе ортогональные и квазиортогональные, нашли применение в задачах обработки изображений с целью их сжатия, маскирования, помехоустойчивого кодирования [1–3]. В работе [4] приведены алгоритм и программа поиска и исследования М-матриц [5], частными представителями которых являются матрицы Адамара [6], Мерсенна [7], Эйлера [8] и Ферма [9]. Матрицы перечислены в последовательности убывания переменной d в значении их порядка n = 4k–d, где d = 0, 1, 2, 3.
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
103
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА ... .
Тема матриц Адамара возникла после публикации им в работе [6] неравенства для оценки значения модуля определителя матрицы сверху и пары оригинальных матриц 12-го и 20-го порядка (помимо основной последовательности Сильвестра), на которых достигается максимальная оценка.
Спустя четыре года итальянский математик Умберто Скарпи опубликовал первый оригинальный метод их нахождения [10], содержание которого сводится к тому, чтобы рассчитывать матрицы высоких порядков на основании матриц более низких порядков. В отношении некоторых матриц результат не был превзойден более поздним подходом Пэли [11], нашедшим применение теории конечных полей Галуа для построения матриц Адамара с помощью символов Лежандра. Отметим, что порядки матриц, найденных Скарпи, (n–1)n для n = 4k, где k = 1, 2, 3…, кратны порядкам матриц Мерсенна. Настоящая работа раскрывает это обстоятельство глубже и показывает новые способы вычисления матриц Мерсенна, Белевича [12] и Адамара, а также их приближений на основании того, что мы будем называть подходом или методом Скарпи.
Слои и сечения матриц
Напомним: матрица Мерсенна Mn [7] – квадратная матрица порядка n = 4k–1 с элементами {1, –b},
такая, что
М
Т n
Мn
In .
Здесь
In
–
единичная
матрица,
(n
1)
(n 2
1)b 2
,
причем
b
1 2
при n = 3, в
остальных
случаях
b
q 4q q4
,
где
q=
n+1.
Количество
элементов
b
в
каждом
столбце
матрицы
на
еди-
ницу меньше количества единичных элементов. В качестве примера на рис. 1 приведена матрица третьего порядка, построенная для первого числа
Мерсенна n = 2k–1 = 3 при k =2. Название матриц связано с числами Мерсенна, для которых в [7] опубли-
кован алгоритм их нахождения. Здесь черный цвет соответствует –b (или 1 у матриц Адамара), а белый – единице.
аб Рис. 1. Портрет матрицы M3 (а) и гистограмма модулей ее элементов (б)
Определение. Слоем матриц семейства Адамара будем называть совокупность квазиортогональных матриц с известными функциями зависимости значений элементов (уровней) матриц слоя от заданных показателем d значений порядков.
Матрицы Адамара, Мерсенна и Эйлера, согласно [6–8], образуют слои для n = 4k–d при d = 0, 1, 2 соответственно. Матрицы Ферма такого непрерывного слоя не образуют, поскольку для них функции уровня определены на узком множестве значений n = 2k+1 при четных k [9].
Следствием такого подхода к классификации матриц семейства Адамара является представление о том, что все названные выше объекты являются проявлением одного математического объекта, данного совокупностью слоев и сечений – матриц соседних слоев для заданных показателем k значений порядков.
Нахождение любой матрицы сечения автоматически влечет за собой нахождение всех остальных, поскольку они отражают одно и то же: матрицы сечения взаимно зависимы. Например, матрица Адамара H4 получается из приведенной выше матрицы Мерсенна M3 округлением ее отрицательных элементов до значения –1 с добавлением каймы в виде строки и столбца с отрицательными элементами для соблюдения баланса положительных и отрицательных элементов. Этот алгоритм построения матриц Адамара напрямую использует свойство общности, вытекающие из близости матриц сечения соседствующих слоев. На рис. 2 он продемонстрирован на примере нахождения матрицы Адамара 12-го порядка (предложенного в работе [6]), но на основе матрицы Мерсенна M11.
Помимо матриц одного сечения, в соответствии с подходом Скарпи, можно опираться на близость матриц соседствующих сечений – данный аспект темы раскроем на примере алгоритма построения матриц Белевича.
104
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 3 (91)
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев
аб Рис. 2. Портреты матриц Мерсенна (M11) (а) и Адамара (H12) (б)
Построение матриц Белевича на основе матриц Мерсенна
Из матриц, на два порядка меньших матриц Адамара и тесно связанных с ними, известны симмет-
ричные конференц-матрицы Белевича Cn [12] – квадратные матрицы порядков n с элементами {1, –1} и
нулевой
диагональю,
такие,
что
C
Т n
Cn
(n 1) In
.
Известно,
что
они
не
существуют
для
значений
n–1,
не
разложимых на сумму квадратов двух целых чисел. Для n = 22, например, найдена иная – шестиуровне-
вая квазиортогональная матрица с экстремальным значением определителя [13]. Хотя такие матрицы
слоя не образуют, с их помощью можно найти некоторые матрицы Адамара согласно алгоритму Пэли в
виде
H2n
Cn I
Cn
I
Cn Cn
I I
.
Вопрос возможности построения матриц Белевича достаточно сложен для исследования, посколь-
ку нет достоверных сведений относительно пропуска в последовательности этих матриц уже при n = 66.
Первый проблемный порядок матриц Адамара – 668. Приведенный выше критерий существования каса-
ется не столько матриц Белевича, сколько вообще всех рациональных матриц, и ничего на эту тему не
говорит. Тем больший интерес представляет использование для их вычисления М-матриц, включающих
матрицы с иррациональными значениями коэффициентов [5].
Матрица Белевича связана с матрицей Адамара удвоенного порядка, в отношении которой уже из-
вестна ее связь с матрицами Мерсенна порядка n–1. Следовательно, по матрице М131 можно найти, например, проблемную для 66-го порядка матриц Белевича матрицу H132. Но больший интерес сейчас для нас представляет возможность построения матриц Белевича (и Адамара) с помощью матриц Мерсенна
значительно меньших по сравнению с ними порядков.
В том, что это возможно, убеждают примеры, дающие представление о связности того единого
объекта, который они собой представляют. В самом деле, анализ показывает, что первые две матрицы
Белевича С6 и С10 строятся без видимого изменения структуры матрицы M3 ее округлением и копированием с добавлением обязательных нулевых элементов диагонали, отображаемых на рис. 3 клетками се-
рого цвета.
аб Рис. 3. Портреты матриц Белевича: вариант С6 (а); вариант С10 (б)
Для согласования размерности матрица десятого порядка С10 снабжается каймою из 1. Несложно заметить, что знаки блоков матриц Белевича отвечают логике знаков элементов матриц H2 и М3 (обобщение правила кронекерова произведения при нахождении сложносоставных матриц Пэли). На этом
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
105
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА ... .
возможности структуры третьего порядка должны, казалось бы, исчерпаться. Однако еще Скарпи заметил, что остается степень свободы в том, чтобы, не меняя структуры, циклически сдвигать столбцы блоков, например, по мере удаления их от диагонали (рис. 4).
аб Рис. 4. Портреты матриц Белевича: вариант С14 (а); вариант С18 (б)
Матрица С14 (рис. 4, а) имеет двойную кайму, у блоков за пределами первой и второй блочных диагоналей смещены столбцы. У матрицы С18 (рис. 4, б) возникают моноблоки (специфический разрыв, обеспечивающий ортогональность столбцов с потерей структуры блока) – шесть закрашенных черным внедиагональных блоков третьего порядка.
Вычисление матриц высокого порядка на основе матриц Адамара низкого порядка характерно для альтернативного конструкциям Пэли метода Скарпи. Очевидно, рассмотренный способ его развивает, но касается он уже матриц Белевича. Замещение элементов, возникающее здесь, впервые встречается в алгоритме построения конструкций Пэли (при замене нулевых элементов единичными). В рассматриваемом варианте замещаются не элемент, а цепочки блоков, которые тоже можно разместить на диагонали.
Следующей матрицы С22, как известно, не существует, поскольку число n–1 = 21 не разлагается на сумму двух квадратов.
Таким образом, напрашивается парадоксальный вывод: все матрицы Адамара порядка n, кратного 4, до n = 40 включительно строятся на основе лишь матрицы Мерсенна M3: матрицы M3, H4 принадлежат одному сечению, из H4 получаем H8, H16, H32, матрицы С6, С10, С14, С18 связаны с M3 и дают промежуточные матрицы H12, H20, H24, H28, H36, H40, удвоениями порядка по Сильвестру можно получить и большее количество таких матриц. Матрица H44 – рубежная как раз потому, что С22 не существует, т.е. возникает кризис структуры с переходом к следующей «ведущей» матрице Мерсенна. Распространение структурных инвариантов матриц малых порядков на старшие порядки представляет существенный практический интерес.
Приближение матриц Адамара матрицами Мерсенна
Проблемные порядки матриц Адамара, для которых производительность современных вычисли-
тельных машин не позволяет пока их вычислить методом Вильямсона [14], хорошо известны – это 668,
716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964 и т.п. Отметим, что вчетверо меньшие
значения – это порядки матриц Мерсенна относительно небольших порядков.
Иными словами, здесь правомерно применение разновидности метода Скарпи с использованием
блочно-составных структур четвертого порядка. Ограничение на число блоков (четыре) препятствует
точной аппроксимации матриц Адамара меньшими по размерам их матрицами, но это путь получения
(как было видно выше на матрицах Белевича) точного или достаточно близкого к ним приближения.
Среди ортогональных структур четвертого порядка хорошо известен массив Вильямсона [14]
w1 w2 w3 w4
W
=
w2 w3 w4
w1 w4 w3
w4 w1 w2
w3
.
w2 w1
Замещение элементов этого массива четырьмя так называемыми матрицами Вильямсона (или, для
близкой структуры, матрицами Гетхальса–Зейделя) позволило найти перебором элементов все предыду-
щие столь же проблемные матрицы Адамара. К сожалению, количество операций перестановок их эле-
ментов слишком велико (даже при упрощении структур матриц Вильямсона до некоторых циклических,
связанных с задающими их векторами), а, главное, это не имеет серьезной перспективы, поскольку не
дает принципиального решения – обнаружение очередной матрицы отодвигает проблемный порядок, и
только.
106
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 3 (91)
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев
Так как в нашем распоряжении находится только одна матрица Мерсенна (или Эйлера [8], что также возможно) вчетверо меньшего порядка, удвоим ее, взяв в качестве первой матрицы Вильямсона модульно двухуровневую матрицу Мерсенна, а в качестве остальных трех – ее же, но с коэффициентами, округленными до значений {1, –1}. Тем самым относительное количество вещественных коэффициентов убывает вчетверо, и остается возможность обеспечить ортогональность расчетом варьируемого уровня b. Приравняем друг к другу последние три коэффициента массива Вильямсона, инвертируем по знаку три нижних его строки и переставим местами второй и третий столбец. Такая структура встречается, например, при симметрировании матрицы Белевича С4, при которой она утрачивает свой диагональный вид. Для большей определенности будем называть структуру Пропусом (Propuses, Близнец), поскольку матрицы Эйлера и Мерсенна всегда идут парами и дают парные матрицы.
Работоспособность подхода Скарпи подтверждается тем, что стартовые матрицы Мерсенна М3 и Эйлера Е6 сразу переходят в матрицы Адамара H12 = W12 и H24 = W24. Отрыв от аппроксимируемой таким способом структуры матриц Адамара начинается только с применения матрицы М7. Не меняя существенно матрицу W28, предложенный в работе [4] алгоритм сжатия ее адамаровой нормы позволяет свести итог к матрице Адамара H28, что демонстрируется на рис. 5.
аб Рис. 5. Портреты матриц Вильямсона W28 (а) и Адамара H28 (б)
аб Рис. 6. Портрет матрицы M167 (а) и гистограмма модулей ее элементов (б)
аб Рис. 7. Портрет матрицы приближения к H668 (а) и гистограмма модулей ее элементов (б)
Задача нахождения матрицы Адамара H28 решается редукцией структуры: измененная сжатием одна из четырех матриц Вильямсона содержит в явном виде не М7, а уже встречавшиеся при построении матриц Белевича моноблоки и матрицу Мерсенна М3. То, что за матрицами Вильямсона стоят матрицы Мерсенна, ранее в литературе не обсуждалось. Заметим, что и сами по себе матрицы Мерсенна стремятся
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
107
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА ... .
с ростом порядка к матрицам Адамара, поскольку их коэффициент b приближается к 1. Например, матрица Мерсенна относительно малого 167-го порядка, судя по гистограмме ее уровней, уже немногим отличается от матрицы Адамара (рис. 6).
Даже без сжатия (адаптации структуры) коэффициент b, характеризующий приближение массива Вильямсона с этой матрицей Мерсенна к матрице Н668, составляет около 70% от максимально возможного уровня (рис. 7).
Модификация метода Скарпи
Наиболее интересный результат можно получить, находя при помощи матриц Мерсенна низкого порядка тот же самый сорт матриц порядка более высокого. Для учета условий ортогональности применим циклическую перестановку столбцов блоков, принесшую заметный успех при построении матриц Белевича. Поскольку в оригинале [10] еще отсутствует понятие матриц Мерсенна с их естественным разделением множества всех элементов на целые (1) и вещественные (–b), идея прежнего метода Скарпи не может быть выражена в столь простой формулировке, как приводимая ниже.
Модифицированный алгоритм. Любую матрицу Мерсенна порядка n, где n – простое число, можно вставить саму в себя с циклическим сдвигом, пропорциональным ее положению, используя в качестве каймы замещаемый элемент матрицы: после нормализации и усечения каймы получим снова матрицу Мерсенна.
Величина циклического сдвига столбцов равна произведению индексов элементов расширяемой матрицы, отсчет их начинается с 0.
Стартовый элемент каймы блока (пересечение первых его строки и столбца) выбирается отрицательным. Под нормализацией подразумевается выравнивание знаков первого столбца и строки итоговой матрицы так, чтобы они были отрицательными – усечение каймы воспроизводит их количественный дефицит на единицу в матрице Мерсенна, но теперь уже порядка n2+n–1. Коэффициент –b ее рассчитывается заново согласно определению. Отметим, что полином n2+n–1=0 имеет корни, равные по модулю числам золотого сечения, т.е. известная в математике пропорция, так или иначе, лежит в основе этого построения.
В качестве примера возьмем матрицу Мерсенна M7, применим ее не для построения матрицы Вильямсона, а увеличим число блоков составной матрицы до значения ее порядка, вставляя матрицу саму в себя согласно алгоритму. После нормализации и усечения общей каймы получим матрицу Мерсенна M55. Побочный продукт этого алгоритма – промежуточная матрица Адамара, поскольку это матрицы одного сечения (рис. 8). Показана матрица Адамара H56 до ее нормализации, что позволяет наблюдать структуру и характер сдвигов столбцов размножаемой матрицы.
аб Рис. 8. Портреты матриц Мерсенна (M7) (а) и Адамара (H56) (б)
Фильтр Мерсенна
Для многих приложений вычислительной математики, теории кодирования, цифровой обработки сигналов и др. важным требованием является простота и конечность множества значений функций ортонормированных систем. Первая из таких систем – система Радемахера – была построена как существенное упрощение аналога тригонометрической системы функций. Функции Радемахера имеют всего два значения {1, –1}, но их недостаток состоит в том, что система неполна и, следовательно, не является базисом в гильбертовом пространстве L2. Полная система впервые была введена Дж. Уолшем. В отличие от функций Радемахера, функции Уолша можно разделить на четные и нечетные, этим они аналогичны синусам и косинусам. Такие функции применяются в практике помехоустойчивого сжатия и маскирования изображений, заменяя матрицу дискретного косинусного преобразования матрицей Адамара–Уолша в классическом тракте JPEG-алгоритма сжатия изображения [1, 3, 5].
Фильтр, построенный на матрице Мерсенна, будем называть фильтром Мерсенна.
108
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 3 (91)
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев Матрицы Мерсенна − двухуровневые, они содержат только элементы двух значений {1, −b} и до-
пускают упорядочивание их строк и столбцов перестановками, результаты которых представлены на рис. 9.
аб Рис. 9. Портрет матриц Мерсенна-Уолша M7 (a) и Мерсенна-Уолша M31 (б)
Пример применения фильтра Мерсенна на основе матрицы M7 к модельному изображению приведен на рис. 10.
аб Рис. 10. Модельное изображение «Мария» (a) и матрица прореженных фильтром Мерсенна значений
ее двухмерного спектра (б)
Исходное и отфильтрованное изображения сравнивались по объемам, достигаемым алгоритмом статистической компрессии PNG (Portable Network Graphics). Исходное изображение перед обработкой имеет объем 37 кБ, обработанное фильтром Мерсенна составляет 32 кБ при малом сжатии, которое уменьшается до 26 кБ и ниже при высоком, более детально технология раскрыта в работах [15, 16].
Систему ортогональных функций, порождаемых упорядоченными по частоте столбцами матриц Мерсенна, будем называть системой функций Мерсенна–Уолша по аналогии с классическими функциями Уолша. Перечислим ее отличительные особенности и назовем причины, по которым такой базис сигналов может быть интересным. Система функций Мерсенна–Уолша − двухуровневая, такая же, как и классическая система. Она отличается от функций Уолша пониженным по амплитуде нижним значением −b, которое с ростом размерности системы стремится к −1. В этом смысле она не совпадает с системой функций Уолша, но является достаточно близкой аппроксимацией ее на нечетных значениях порядка. Систему функций Мерсенна–Уолша характеризует пониженное на единицу количество порождающих ее элементов столбцов матрицы Мерсенна, т.е. она более проста для вычисления, чем классическая.
Любой базис отличает предпочтительная область его применения. Система функций Мерсенна– Уолша более высокочастотная, чем система функций Уолша, в ее составе нет функции нулевой частоты (константы). Таким образом, она более предпочтительна для построения полосовых фильтров изображений (для обработки рисунков, где отсутствует монотонный фон). Первые единичные столбец и строка нормализованных матриц Адамара представляют собой ненужную составляющую, которая у полосовых фильтров никакой нагрузки не несет, поскольку отвечает частоте, которую они фильтруют. Иначе говоря, она означает лишние затраты процессорного времени. Однако заметим, что простое удаление канвы матрицы Адамара отбрасыванием ее первых строки и столбца нарушает ортогональность столбцов усеченной матрицы.
Заключение
Для ряда приложений квазиортогональных матриц к помехоустойчивому кодированию информации, маскированию изображений и защите видеоданных целочисленные значения их элементов далеко
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
109
ВЫЧИСЛЕНИЕ МАТРИЦ МЕРСЕННА И АДАМАРА ... .
не столь важны, как высокая размерность решаемой задачи и наличие экстремальных качеств [1, 3–5, 17], которыми обладают матрицы Адамара и все близкие к ним матрицы их семейства. В работе подведены некоторые итоги использования алгоритма и программы исследования М-матриц [4].
Построение матриц Белевича при помощи матриц Мерсенна в настоящей работе публикуется впервые. Это означает, что матрицы Адамара и Белевича более высоких порядков достижимы не только при помощи матриц Мерсенна ближайшего к ним среза – имеются и более дальние связи. Приведенный в работе подход показывает вариант замены известного кронекерова произведения матриц Адамара, введенный еще Пэли, операциями с каймой и сдвигами столбцов матриц Мерсенна. Отсутствие некоторых матриц Белевича получило объяснение естественным исчерпанием комбинаторной возможности, сопровождаемой появлением в их составе моноблоков (разрыв структуры).
Матрицы Белевича и Адамара далеко не всегда являются конечной целью таких алгоритмов, поскольку известны приложения, например, при моделировании квазикристаллов [18, 19], в которых содержательная сторона задачи связывается c модульно двухуровневыми матрицами. По простоте и надежности поиска матрицы Мерсенна предпочтительнее матриц Адамара. Они занимают в тетраде матриц Адамара, Мерсенна, Эйлера и Ферма наиболее удаленное положение от матриц порядка 4k–3, на котором наблюдается отсутствие явно выделенного и проходящего по всем порядкам матриц слоя. Справа и слева (по порядкам) от матриц Мерсенна находятся связанные с ними взаимно-однозначным соответствием матрицы Адамара и Эйлера.
Модификация алгоритма поиска матриц Белевича с циклической перестановкой столбцов позволяет непосредственно вычислять матрицы Мерсенна и Адамара высоких порядков, недостижимых при использовании метода Пэли [11]. Снижение числа блоков и отказ от перестановок элементов матрицы Мерсенна позволяет эффективно находить приближения матриц Адамара высоких проблемных порядков при имеющейся мощности вычислительной техники.
Литература
1. Мироновский Л.А., Слаев В.А. Стрип-метод преобразования изображений и сигналов. СПб: Политехника, 2006. 163 с.
2. Ерош И.Л., Сергеев А.М., Филатов Г.П. О защите цифровых изображений при передаче по каналам связи // Информационно-управляющие системы. 2007. № 5. С. 20–22.
3. Балонин Ю.Н., Востриков А.А., Сергеев М.Б. О прикладных аспектах применения М-матриц // Информационно-управляющие системы. 2012. № 1. С. 92–93.
4. Балонин Ю.Н., Сергеев М.Б. Алгоритм и программа поиска и исследования М-матриц // Научнотехнический вестник информационных технологий, механики и оптики. 2013. № 3 (85). С. 82–86.
5. Балонин Н.А., Сергеев М.Б. М-матрицы // Информационно-управляющие системы. 2011. № 1. С. 14– 21.
6. Hadamard J. Résolution d'une question relative aux determinants // Bulletin des Sciences Mathématiques. 1893. V. 17. P. 240–246.
7. Балонин Н.А., Сергеев М.Б., Мироновский Л.А. Вычисление матриц Адамара-Мерсенна // Информационно-управляющие системы. 2012. № 5. С. 92–94.
8. Балонин Н.А., Сергеев М.Б. О двух способах построения матриц Адамара-Эйлера // Информационноуправляющие системы. 2013. № 1 (62). С. 7–10.
9. Балонин Н.А., Сергеев М.Б., Мироновский Л.А. Вычисление матриц Адамара-Ферма // Информационно-управляющие системы. 2012. № 6 (61). С. 90–93.
10. Scarpis U. Sui determinanti di valore Massimo // Rendiconti della R. Istituto Lombardo di Scienze e Lettere. 1898. V. 31. P. 1441–1446.
11. Paley R.E.A.C. On orthogonal matrices // Journal of Mathematics and Physics. 1933. V. 12. P. 311–320. 12. Belevitch V. Theorem of 2n-terminal networks with application to conference telephony // Electronic Com-
munications. 1950. V. 26. P. 231–244. 13. Балонин Ю.Н., Сергеев М.Б. М-матрица 22-го порядка // Информационно-управляющие системы.
2011. № 5. С. 87–90. 14. Williamson J. Hadamard’s Determinant Theorem and the Sum of Four Squares // Duke Math. J. 1944. V.11.
P. 65–81. 15. Балонин Н.А., Сергеев М.Б. О расширении ортогонального базиса в задачах сжатия видеоизображе-
ний // Вестник компьютерных и информационных технологий. 2014. № 2 (116). С. 11–15. 16. Востриков А.А., Балонин Ю.Н. Матрицы Адамара-Мерсенна как базис ортогональных преобразова-
ний в маскировании видеоизображений // Изв. вузов. Приборостроение. 2014. Т. 57. № 1. С. 15–19. 17. Балонин Н.А., Сергеев М.Б. Матрицы локального максимума детерминанта // Информационно-
управляющие системы. 2014. № 1 (68). С. 2–15. 18. Балонин Н.А., Сергеев М.Б. Матрица золотого сечения G10 // Информационно-управляющие системы.
2013. № 6 (67). С. 2–5.
110
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 3 (91)
Н.А. Балонин, Ю.Н. Балонин, М.Б. Сергеев
19. Балонин Н.А., Сергеев М.Б. М-матрицы и кристаллические структуры // Вестник Магнитогорского государственного технического университета им. Г.И. Носова. 2013. № 3 (43). С. 58–62.
Балонин Николай Алексеевич Балонин Юрий Николаевич Сергеев Михаил Борисович
– доктор технических наук, доцент, профессор, Санкт-Петербургский государственный университет аэрокосмического приборостроения
(ГУАП), Санкт-Петербург, Россия, korbendfs@mail.ru – программист, Санкт-Петербургский государственный университет
аэрокосмического приборостроения (ГУАП), Санкт-Петербург, Россия, tomaball@mail.ru
– доктор технических наук, профессор, зав. кафедрой, СанктПетербургский государственный университет аэрокосмического приборостроения (ГУАП), Санкт-Петербург, Россия; директор, НИИ
информационно-управляющих систем, Университет ИТМО, mbse@mail.ru
Nikolai A. Balonin
Yuri N. Balonin Mikhail B. Sergeev
– Professor, D.Sc., Associate professor, Saint Petersburg State University of Aerospace Instrumentation (SUAI), Saint Petersburg, Russia,
korbendfs@mail.ru – programmer, Saint Petersburg State University of Aerospace Instrumentation
(SUAI), Saint Petersburg, Russia, tomaball@mail.ru – D.Sc., Professor, Department head; Saint Petersburg State University of
Aerospace Instrumentation (SUAI), Saint Petersburg, Russia; Director, Research Institute of Information and Control Systems, ITMO University,
mbse@mail.ru
Принято к печати 18.02.2014 Accepted 18.02.2014
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 3 (91)
111