автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Дискретные ортогональные преобразования с шумоподобными базисными функциями

на правах рукописи

БЕСПОЛИТОВ Олег Владимирович

ДИСКРЕТНЫЕ ОРТОГОНАЛЬНЫЕ ПРЕОБРАЗОВАНИЯ С ШУМОПОДОБНЫМИ БАЗИСНЫМИ ФУНКЦИЯМИ

Специальность 05.13.17 - Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Самара 2006

Работа выполнена в государственном образовательном учреждении

высшего профессионального образования «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» (СамГУ) на кафедре безопасности информационных систем

Научные руководители доктор физико-математических наук

В.М. Чернов

Официальные оппоненты: доктор физико-математических наук, профессор

С.Я. Шатских

кандидат физико-математических наук, доцент

Защита состоится « 2 » июня в 10.00 часов на заседании диссертационного совета Д 212.215.07 при Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева» по адресу: 443086, г. Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева».

Автореферат разослан 28 апреля 2006 г.

Ученый секретарь

Э.И. Коломиец

Ведущая организация:

Омский государственный университет.

диссертационного совета д.т.н., профессор

Общая характеристика работы

Диссертация посвящена разработке и исследованию нового класса дискретных ортогональных преобразований.

Актуальность исследования. В составе алгоритмического обеспечения компьютерных систем обработки сигналов и изображений одно из центральных мест занимают алгоритмы дискретных ортогональных преобразований (ДОП). Историю систематического использования методов дискретного спектрального анализа сигналов принято отсчитывать с 1965 г., когда Кули и Тьюки опубликовали быстрый алгоритм вычисления дискретного преобразования Фурье (ДПФ), хотя ранее Гуд (1960 г.) и Томас (1963 г.) опубликовали в практически незамеченных современниками работах быстрые алгоритмы ДПФ, базирующиеся на несколько ином подходе. За время, прошедшее с первых публикаций, дискретный спектральный анализ стал одним из основных средств решения задач цифровой обработки сигналов, распознавания образов, машинного зрения, компьютерной оптики и т.д.

Разработке различных аспектов теории и применения дискретного спектрального анализа с использованием различных ДОП посвящено большое количество публикаций как у нас в стране, так и за рубежом. Значительный вклад в развитие общей теории ДОП внесли С.С.Агаян, Н.Н.Айзенберг, В.А.Власенко, А.М.Крот, В.ГЛабунец, А.М.Трахтман, Л.ПЛрославский; Р.Агарвал, Ш.Виноград, Г.Нуссбаумер, Ч.Рейдер и др. Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны А.М.Григоряном, И.Е.Капориным, Е.Е.Тыртышниковым и др.

В настоящее время теория ДОП развивается, в частности, в следующих направлениях:

• синтез параметрических семейств новых ортогональных базисов со структурой быстрых алгоритмов, инвариантной по отношению к той или иной концепции синтеза таких алгоритмов;

• разработка новых конкретных алгоритмов ДОП, обладающих повышенной точностью и/или быстродействием, адекватных по структуре вычислений последним разработкам в области специализированных процессоров и характеристикам каналов передачи информации.

Именно последний этот аспект теории ДОП - разработка, синтез и исследование ДОП, адекватных особенностям реальных или целенаправленно созданных каналов передачи информации, представляется до сих пор мало исследованным, хотя широкое распространение методов дискретного спектрального анализа в разнообразных задачах передачи и обработки информации делает эту проблему весьма актуальной.

В частности, для "классических" дискретных ортогональных преобразований, определяющих возможность их эффективного применения к задачам кодирования цифровой видеоинформации, характерна концентрация энергии спектра в относительно небольшом числе спектральных компонент. В задачах, например, компрессии изображений это свойство во многом определяет эффективность конкретных алгоритмов компрессии. С другой стороны, при передаче кодированной видеоинформации по реальному каналу возникают помехи, искажения, зависящие от физической природы канала. И если специфика канала такова, что какая-то часть передаваемой информации случайным образом утрачивается (модель "канала с пропусками") или специальным образом изменяется с целью встраивания дополнительной "секретной" информации (стеганография), то при утрате или

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

Целью диссертационной работы является разработка и исследование нового класса дискретных ортогональных преобразований, базисные функции которых представляют реализации процесса построения последовательностей псевдослучайных чисел и точек двумерного пространства.

Методы исследования. В диссертационной работе используются методы современной алгебры и теории чисел: теория конечных полей, теория полей алгебраических чисел и канонических систем счисления в алгебраических структурах, а также методы цифровой обработки сигналов и методы арифметического моделирования случайных процессов.

Научная новизна работы. В диссертационной работе получены следующие новые научные результаты:

1) синтезированы одномерные дискретные ортогональные преобразования, базисные функции которых принимают <7 различных значений с равными частотами (<? -степень простого числа р);

2) синтезированы одномерные дискретные ортогональные преобразования, базисные функции которых принимают "случайным образом" значения в соответствии с полиномиальным законом распределения;

3) на основе синтезированных одномерных дискретных ортогональных преобразований с шумоподобными базисами синтезированы двумерные преобразования с базисами, согласованные с псевдослучайной разверткой (нумерацией) массива пикселей входного и выходного изображений.

Практическая значимость работы состоит в том, что разработанные в ней методы непосредственно направлены на решение практических задач и, в частности:

• создание программно-алгоритмических комплексов перспективных систем адаптивной обработки и анализа многомерной цифровой информации, обладающих свойством устойчивости к зашумлению и пропускам в информационных каналах

• пополнение банка данных дискретных ортогональных преобразований.

На защиту выносятся следующие результаты

1. Методы синтеза одномерных дискретных ортогональных М -преобразований, базисные функции которых принимают q различных значений с равными частотами (д — степень простого числа р);

2. Методы синтеза одномерных дискретных ортогональных М -преобразований, базисные функции которых принимают значения в соответствии с полиномиальным законом распределения;

3. Методы синтеза двумерных М -преобразований с базисами согласованными с псевдослучайной разверткой (нумерацией) массива пикселей входного и

выходного изображений.

Апробация работы. Основные результаты диссертационной работы докладывались на следующих научных конференциях: XII-я Всероссийская конференция "Математическое программирование и приложения", (г. Екатеринбург, 2003), Международная научная конференция "Интеллектуализация обработки информации ИОИ-2004", (Крым, г. Алушта, 2004), XII-ая Всероссийская школа-коллоквиум по стохастическим методам и VI-ой симпозиум по прикладной и промышленной математике (осенняя открытая сессия), (г. Сочи-Дагомыс, 2005), XII-ая Всероссийская конференция "Математические методы распознавания образов", (г. Москва, 2005), The 4th International Workshop on Security In Information Systems (WOSIS-2006), (Cyprus, 2006).

Публикации. По теме диссертации опубликовано 8 работ. Работы [5]-[7] выполнены автором лично, остальные работы написаны в соавторстве. На защиту выносятся только результаты, полученные лично соискателем.

Структура диссертации. Диссертационная работа, содержащая 127 стр., состоит из введения, четырех глав, заключения, списка использованной литературы, составляющего 121 наименование и 2 приложений объемом 16 страниц.

Краткое содержание работы

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

На рис. 1(б)-(в) показаны примеры таких структурированных помех.

(а) Исходное изображение

(6) Восстановленное изображение при использовании преобразования Хартли

(в) Восстановленное изображение при использовании преобразования Адамара

Рис. 1. Искажения восстановленного цифрового изображения при утрате одинакового количества спектральных компонент при различных дискретных ортогональных _преобразований_

В работе Граллерта1 введено понятие дискретного ортогонального М-преобразования

(1)

п=0 и=0

значения базисных функций п), которого имеют шумоподобный характер. Именно функции кт (п) принимают "случайным" образом два значения с равными относительными частотами. Основой для построения семейства базисных функций в цитированной работе являлась т -последовательность, то есть, последовательность элементов конечного поля из двух элементов, удовлетворяющая линейному рекуррентному соотношению и имеющая максимально возможный период. Такие последовательности являются типичным математическим средством, применяемым при построении генераторов псевдослучайных чисел и точек многомерного пространства. В указанной работе Граллерта1, как уже отмечено, рассматривался исключительно случай одномерных базисных функций, принимающих два различных значения. Некоторые обобщения базовой методики и обоснование применимости таких преобразований к задачам кодирования двумерных сигналов (изображений) получены В.М.Черновым, Э.И.Коломийцем, А.Г.Дмитриевым. Однако разработка удовлетворительной методики экстраполяции теории синтеза базисов одномерных М -преобразований на многомерный случай представлялось до последнего времени только перспективной задачей.

Вышесказанное и определяет задачи диссертационного исследования:

1) синтез одномерных М -преобразований, базисные функции которых принимают ц различных значений с равными частотами (<? - степень простого числа р );

2) синтез одномерных обобщенных М -преобразований, базисные функции которых принимают "псевдослучайным образом" значения в соответствии с полиномиальным законом распределения;

3) синтез двумерных преобразований с базисами, ассоциированными с псевдослучайной разверткой (нумерацией) массива пикселей входного и выходного изображений;

4) разработка необходимого программного обеспечения для определения параметров рассматриваемых преобразований.

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

Сформулированные выше задачи определяют структуру диссертации и содержание отдельных глав.

В первой главе представлены необходимые сведения из теории алгебраических полей. Рассматриваются некоторые свойства показательных и рекуррентных функций в конечных полях, тригонометрические суммы и суммы

' Grallert H.-J. Application of orthonormalized m-sequences for data reduced and error protected transmission of pictures // Proc. IEEE Int. Symp. on Electromagnetic Compability. - Baltimore: MD, 1980. P. 282-287.

характеров с показательными функциями. Эта глава имеет вспомогательный характер, не содержит новых результатов и включена в диссертационную работу для замкнутости изложения и удобства ссылок.

Определение 1.1. Функция, являющаяся решением линейного рекуррентного соотношения

у(п)=сцу(п-1)+. ..+а5у(п-з), (2)

в конечном поле ОР(^), где

а,Ф0, Ч={у{\\...,уЩ, называется линейной рекуррентной последовательностью порядка ^ с начальными условиями (значениями) У=(>'(1),...,>'(-5)).

Определение 1.2. Рекуррентная последовательность с максимально возможным периодом, равным Т=д'-1, называется т -последовательностью.

Приведем в неполной формулировке лемму 1.1 диссертации, оставив только те свойства т -последовательностей, которые необходимы для дальнейшего понимания автореферата.

Лемма 1.1. Пусть рекуррентная последовательность (2) с ненулевыми начальными условиями У=У|=(у(1),...,>'(.у)) является от-последовательностью. Тогда справедливы следующие утверждения:

1) если п пробегает полный период от-последовательности, равный Т=д'-1, то элемент СМаебР(д) встретится раз, нулевой элемент ОеСР(^) встретится

раз;

2) в полном периоде "гусеницы"

V! ф(1)„. .,><.)),У2 ф(2),. • .,>'(*+!)), - =(>'(Г)„. „>'(Г+,-1)) т -последовательности (2) все ненулевые ^-мерные векторы пространства вР5 (д) встретятся ровно по одному разу;

3) если У](п), У2(") есть два различных решения рекуррентного соотношения с различными начальными условиями

^(лО),...,^)), ¥1>2=(72(1),...,у2(*)), (3)

то последовательность

Уз(п)=М")+М")

также есть решение рекуррентного соотношения (2), то есть, в частности, является либо от-последовательностью, либо нулевой последовательностью;

4) если (и), >>2(и) есть два различных решения рекуррентного соотношения (2) с различными начальными условиям (3), то существует такое натуральное т, что

ух{п)=у2{п+х).

Определение 1.3. Пусть П(У) есть нетривиальный гомоморфизм аддитивной группы поля | в группу комплексных корней степени р из единицы. Такой

гомоморфизм называется неглавным характером аддитивной группы поля вР^/?11. Лемма 1.2. а) Произвольный характер П=ПЬ имеет вид:

где yj — компоненты представления элемента Y в базисе поля GF^//j над GF(/j) , а

вектор b=(i1,...,6i) однозначно определяется значениями характера на элементах базиса.

б) Множество характеров образует мультипликативную группу с нейтральным элементом — главным характером П=Пе, где вектор в=(0,...,0) соответствует

нулевому элементу 9 поля j.

в) Мультипликативный сдвиг аргумента Kl—>£,7 (^^в) индуцирует автоморфизм группы характеров.

г) Для неглавного характера Q=Db справедливо равенство

„ Г 0, при А=в;

£ П(АХ)=\

XeGF(,') IР*> "РИ А*в-

Из перечисленных свойств характеров следует, что теория рекуррентных функций порядка s над полем GF(p) "изоморфна", в некотором смысле, теории

показательных функций в поле GF^?S j, что гарантируется следующей леммой.

Лемма 1.3. Для произвольной рекуррентной функции y(n)=aly(n-\)+.. ,+asy(n-s) (mod р) с ненулевыми начальными значениями Y=(>'(l),...,>'(j)) существуют такой неглавный

характер Q=fib аддитивной группы поля GFjp1 j и такой элемент A'eGF^p1 j, что при всех neZ справедливо равенство

Замечание 1.1. Если Г=д,,-1, то есть, если рекуррентная последовательность является т -последовательностью, то значения модуля суммы

п=О

вычисляются точно:

II, при т=0;

Я

р/г, при

Приведенные выше утверждения позволяют в дальнейшем получить аналитические соотношения для определения параметров базисных функций М — преобразований в соответствии с требованием их ортогональности.

В Разделе 1.2 рассматриваются канонические системы счисления (КСС) в квадратичных полях, введенные в работах венгерских математиков И.Катаи и А.Петьо. Эти канонические системы счисления используются далее в

диссертационной работе для двумерной нумерации одномерного массива значений

одномерных линейных рекуррентных последовательностей (2).

Элемент квадратичного поля Q(Jd^={z=a+bJ~d\ a,6eQj называется целым, если

Norm(z)=(a+b^d){a-b^fd^a2-db2eZ и Tr(z)=(a+bJd)+(a-by/d)=2aeZ.

Целые элементы образуют кольцо s(yfd ) поля Q(V<?) •

Определение 1.4. Квадратичное целое число a=A+B~fd называется основанием канонической системы счисления в кольце целых поля Qесли

каждый целый элемент z поля Q^-Jd^J может быть единственным образом представлен в форме конечной суммы

k(z)

2=2>/*У' a;eN={0,l,...,|Norm(a)|-l}. (4)

у=О

В Разделах 1.2.1 и 1.2.2 подробно рассматриваются условия, при которых целое квадратичное число a=A+B-fd является основанием канонической системы счисления и алгоритмы определения "цифр" aj для различных квадратичных полей. Приведем для иллюстрации типичные результаты.

Лемма 1.4. Пусть поле о!-*/?) - вещественное, 0<d=2,3 (mod 4). Тогда алгебраическое число а= A+B-Jd является основанием канонической системы счисления в кольце Sтогда и только тогда, когда AeZ и 0<-2A<A2-dè2.

Лемма 1.5. Пусть d>2 и пусть при 0<rf=2,3 (mod 4) a=A+B-Jd является основанием канонической системы счисления в кольце S(V^) • Пусть далее для

Z=ZI+22 -JdeS^-Jd^, zj^eZ целые рациональные s^{z) определены рекуррентными соотношениями:

4+l(z)=2A

sk(z)

Norm(a)

Norm(a) j_l(z)=±r2Norm(a), s0(z)=zi±z2A.

Тогда справедливо равенство (4), где aj(z)=Sj(z) (mod Norm (a)].

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

В частности, нижеследующая лемма строго обосновывает выбор значений базисных функций преобразования в случае, рассмотренном в цитированной выше работе Граллерта.

Лемма 2.1. Пусть у(п) - рекуррентная функция

у{п)=а\у(п-\)+.. ,+asy(n-s) (mod 2) с ненулевыми начальными значениями Y=(.y(l),.. -,>"(5)) и периодом, равным T=qs-1. Пусть далее:

• при построении функции /¡о (я) члены последовательности у(п) заменяются вещественными числами

V SK J >ow при ^(nJ=osGF(2). v '

• функции hm{ri) получаются из /¡о(я) циклическим сдвигом:

hm{n)=h{m+n)> m=QX—N-\\ JV=(2s-l)-l. (6)

• числа А и В выбираются таким образом, чтобы для функций \hm (и)}

выполнялось условие ортогональности в форме

N-1

(7)

«=о

Тогда числа А и В являются решениями системы уравнений

^LB^a^N-,

(8)

4 2 4

Дискретное ортогональное преобразование (1) с базисными функциями, определенными в Лемме 2.1, в цитированной работе Граллерта названо М— преобразованием. В дальнейшем мы употребляем этот термин и по отношению к обобщениям этого преобразования, рассматриваемым в диссертационной работе.

Центральными результатами второй главы, обобщающими понятие М-преобразования, являются две теоремы.

Теорема 2.1. Пусть р - простое число, Ы=рг-\, числа Ао,...,Ар_1 удовлетворяют соотношению Ак=к +А<), (к=0,...,р-\). Пусть функции

определены соотношениями

\И0{п)=Ак> если у(п)=к\

Тогда существуют эффективно вычисляемые константы Ад и А/, такие, что семейство функций [}гт{п)\ гя,и=0,1,...,7/-1} образует ортонормированный базис и константы А=А$, С=Ар_1 являются решением системы уравнений

'Ы=А2(Рг-\)+АСрг{Р-\)+С2рг{р-1)^=1; р~\рЛ

¡=0 _>=0 где

p~2N+p~2-\, если j'=y=0; p~2N+p~x, если ¡"=0,yV0 или i*0,j=0; p~2N+p~2, если iVOJs'O.

Далее в главе рассматривается задача построения обобщенного М -преобразования, базисные функции которого принимают к различных значений ,.. с заданными частотами.

Пусть р — простое число, пусть

ак .

П=—.....Пс=> П+..лгк=1.

Р Р

Пусть далее Т|1,...,Т|£ — частоты, с которыми значения Л],...,^ встречаются в полном периоде базисной функции Нт (п).

Теорема 2.2. Существует семейство базисных функций Нт(п), обладающее следующими свойствами:

а) функции Нт{п) образуют ортонормированное семейство.

Т-1 г-1

£ят(и>Я,(л)=0, при т*Г,

л=0 п=0

б) для частот г|],.. справедливы равенства

PS 1

"ТТТм'при' ;

S

~—, при t* 1.

V-1

Теорема 2.1 обобщает результат леммы 2.1 на случай произвольного простого р или степени простого числа. Теорема 2.2 обосновывает метод построения базисных функций с заданными частотами их различных значений.

Как показано в работах В.М.Чернова и А.Г.Дмитриева, значительную проблему представляет собой отсутствие "иррегулярного" метода двумерного упорядочения одномерного массива значений т -последовательностей.

Поэтому в третьей главе рассматривается новый метод нумерации входных пикселей изображения и спектральных компонент М -преобразований основанных на теории канонических систем счисления (КСС) в квадратичных полях. Предлагается алгоритм нумерации и вводится определение двумерного ортогонального преобразования.

Метод синтеза базисных функций двумерного М-преобразования а) Пусть fif=2,3 (mod 4). Тогда S(%/<J)={z=a+6V^; а,беZj. Шаг 1. Пусть

z=a+b4d =Rat(r)+Vrf Irr(z)eS(Vrf). Рассмотрим отображение (*): , такое что

(*): г^г* =(«, ,П2)=(», (z),n2 (r))=(Rat(r),Irr(r)). (9)

Шаг 2. Пусть в кольце ) существует д -значная КСС с основанием а.

Рассмотрим от-последовательность

>'(«)=а1>(и-1)+...+агу(п-з); а/евР(д), О (10)

порядка х=2р с периодом Лг=р2р-1 и "гусеницей"

Y, =(><!),...

(П)

Шаг 3. С помощью "гусеницы" (11) сформируем последовательность элементов квадратичного поля S^Vrfj:

z(&)=>>(£)a0+>'(&+l)a1 +.. .+>(/t+j-l)aI_1 eS (-Jd). (12)

Пусть fi={z(£); ¿=0,1,.. . Элементы последовательности z*(/fc)eZ2

точек решетки Z2, определенные для последовательности (12) посредством (9) порождают на двумерной (плоской) решетке некоторую фундаментальную область Q*.

Шаг 4. Рассмотрим равенство множеств

C2+arS(>/^)={z+a''v: zeQ,veS(V^)}=Q+£.

В диссертационной работе показывается, что отображение множеств, индуцированное отображением (9) их элементов, порождает равенство

=Z2\^arS^/rf)j =Z2\2*. Другими словами, аддитивные сдвиги

области П* покрывают "почти всю" решетку Z2, за исключением точек множества 2*.

Шаг 5. Будем говорить, что точки z*=(z],z2),w*=(w[,w2)ez2 конгруэнтны (mod Z), если их прообразы, определяемые отображением (9) удовлетворяют соотношению (z-w)eS. В диссертационной работе показывается также, что каждая точка

w*=(>vi,w2)eAAr конгруэнтна (mod 2) некоторой точке z*=(z],z2)sQ*

фундаментальной области. Отсюда следует, что существует взаимнооднозначное

соответствие между точками фундаментальной области П* и элементами (парами чисел) множества £2, которое одномерным. образом нумерует согласно (9)

подмножества ficzZ2.

Шаг 6. Суммируя вышесказанное, мы получаем одномерную нумерацию для элементов множества Д^-области определения цифрового изображения:

w*eAN (m°d V4„r2)A4)^EZ. (13)

С другой стороны, функции hm(n) порождают базисные функции //m(vj,v2), определенные на двумерной области AN.

Действительно, рассмотрим, например, h(n)=h<)(n). Тогда, аналогично (13), имеем:

„_02Ц„)ЦКа((2(„)), Irr(2(i)))^l(»1,«2)eQ,i^l>(v1>v2)eA,v (14) и мы полагаем

M")=M"+OT)=//m(vl.vг)- (15)

б) Пусть d=1 (mod 4). Тогда

aMZ, a=b (mod 2)1.

2

В этом случае отображение (9) и шаг 1 несколько изменяются. Шаг 1А. Пусть

Тогда отображение (9) заменяется на отображение >2?

(^гк^Х^ИМФ^^М2)-1"^)' 1Ш(г)+1гг(г)). (16) Определение 3.1. Двумерное ортогональное ^-преобразование функции х(у1,У2)еК, 0<г1)у2<Л:-1=рр-1, (^,У2)*(0,0) определим посредством равенства

¿(ИЫ-^Ь Е т=0,1,...,Л^-1; (17)

0<уьУ2=0

(П^М0'0)

где пара индексов (|11,р.2)<->т определена для целого т соотношением аналогичным соотношению (14).

Отметим, что свойства базисных функций, полученных этим построением, действительно удовлетворяют определению хаотического отображения метрического пространства, принятого в теории детерминированного хаоса. В диссертационной работе доказывается теорема, которая характеризует в некоторой степени "независимость" значений базисных функций и их "хаотическое поведение". Теорема 3.1. Пусть

Тогда существует 0=6^=^1—такое, что при справедливо неравенство

Д^ЭЛГ. (18)

В Разделе 3.3 приводится обоснование того, что вычисление М — преобразований можно свести к вычислению циклической свертки, которую, в свою очередь, можно вычислить по обычной спектральной схеме с применением дискретного преобразования Фурье. Действительно, рассмотрим М -преобразование

и=0

Так как базисные функции связаны друг с другом циклическим сдвигом аргумента:

то после замены т\=-п аргумента получаем представление преобразования (19) в форме циклической свертки лч

*И=Их(")Мот-г0=(**Ао)('")> ™=о,-..,лм. (20)

л=1

Массив (20) может быть найден по обычной спектральной схеме вычисления свертки стандартным применением дискретного преобразования Фурье.

, ч ДПФ . .

ОДПФ , , ,, ч ®-К**/го)(т)

у„)ДШиЯо

В четвертой главе описывается разработанное алгоритмическое обеспечение, необходимое для решения поставленных задач. В частности, описываются и анализируются следующие алгоритмы:

• Алгоритм 4.1. Алгоритм (ёе^сапзуэ) определения характеристик квадратичных полей, в которых существуют КСС;

• Алгоритм 4.2. Алгоритм (с1ес2сап) представления целых чисел в канонической системе счисления;

• Алгоритм 4.3. Алгоритм ^еп_йтге§) генерирования "фундаментальных" областей для квадратичных полей, в которых существуют КСС;

• Алгоритм 4.4. Алгоритм (БШип^Адт^) нумерации элементов фундаментальной области;

• Алгоритм 4.5. Алгоритм (51пип1_Й1пге§1ши1) нумерации элементов периодического ограничения фундаментальной области;

• Алгоритм 4.6. Алгоритм (т^гапэГогш) синтеза базисных функций двумерных М -преобразований.

Значительная часть материала, относящегося к реализации разработанного программного обеспечения, содержится в Приложениях 1-2 и на защиту не выносится.

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

Наличие локальных экстремумов (рис. 2 (а)-(б), 3 (а)-(б)) у функций автокорреляции характеризует коррелированность этих искажений для дискретных ортогональных преобразований Хартли и Адамара. Однако для М -преобразования функция автокорреляции (рис. 2 (в), 3 (в)) представляет собой один центральный пик и отсутствие ярко выраженных локальных экстремумов, что говорит о декоррелированности поля ошибок.

Ь* < ' „ ' -Л*' * * 1■ .»ч -•.. Г ' / г' " * * - • 1 " К"ч ( •. ;; . ( & ) !

(а) При использовании преобразования Хартли (б) При использовании преобразования Адамара (в) При использовании М — преобразования

Рис. 2. Поля ошибок восстановленного изображения для дискретных ортогональных преобразований

(а) При использовании преобразования Хартли (б) При использовании преобразования Адамара (в) При использовании М — преобразования

Рис. 3. Автокорреляционные функции поля ошибок

Заключение

В рамках диссертационной работы получены следующие результаты:

1. Получен метод синтеза одномерных дискретных ортогональных М-преобразований, базисные функции которых принимают д различных значений с равными частотами (¡7 - степень простого числа р );

2. Получен метод синтеза одномерных дискретных ортогональных М -преобразований, базисные функции которых принимают значения в соответствии с полиномиальным законом распределения;

3. Получены аналитические оценки, относящиеся к исследованию распределения значений базисных функций по отношению к некоторым тестам (тест серий, покер-тест);

4. Предложен метод одномерной нумерации двумерного массива пикселей изображения, основанный на теории КСС;

5. Получен метод синтеза двумерных М -преобразований с базисами согласованными с псевдослучайной разверткой (нумерацией) массива пикселей входного и выходного изображений;

6. Разработано необходимое программное обеспечение для определения параметров рассматриваемых преобразований.

Основные результаты опубликованы в следующих работах:

1. Бесполитов О.В., Чернов В.М. Быстрое вычисление дискретной свертки в редуцированных системах счисления для комплексных полей Мерсенна // Компьютерная оптика, 24. - 2002. - С. 126-129.

2. Бесполитов О.В., Ананьин М.А. Позиционные системы счисления в комплексных полях Мерсенна // Информационный бюллетень Ассоциации математического программирования № 10. Конференция "Математическое программирование и приложения". - Екатеринбург: Уро РАН, 2003. - С. 26-27.

3. Бесполитов О.В., Чернов В.М. Параллельные алгоритмы вычисления свертки в редуцированных канонических системах счисления для квадратичных полей // Тезисы докладов международной научной конференции "Интеллектуализация обработки информации (ИОИ-2004)". - Симферополь, 2004. - 170 с.

4. Бесполитов О.В., Чернов В.М. Параллельные алгоритмы вычисления свертки в редуцированных канонических системах счисления для квадратичных полей // Искусственный интеллект. - 2004. - № 2. - С. 197-200.

5. Бесполитов О.В. Дискретные ортогональные преобразования с "хаотическими" базисными функциями // Вестник Самарского гос. Университета. Естественнонаучная серия. — 2005. — № 3(37). - С. 5-19.

6. Бесполитов О.В. Дискретные ортогональные преобразования с "хаотическими" базисными функциями // Обозрение прикладной и промышленной математики. -М.:ТВП, 2005.-Т. 12.-В. 4. - 850 с.

7. Бесполитов О.В. Кодирование цифровых изображений с помощью дискретных ортогональных преобразований с "хаотическими" базисными функциями // Сборник докладов XII Всероссийской конференции "Математические методы распознавания образов". — М.: МАКС Пресс, 2005. - С. 32-34.

8. Chernov V.M., Bespolitov O.V. A new method for embedding secret data to the container image using 'chaotic' discrète orthogonal transforms // Proceedings of The 4th International Workshop on Security In Information Systems (WOSIS-2006). - Springer, 2006.

Подписано в печать 27.04.06 г. Гарнитура Times New Roman. Формат 60x84/16. Бумага офсетная. Печать оперативная. Усл.-печ. л. 2,75. Уч.-изд. л. 2,54. Тираж 100 экз. Заказ 4 73

Отпечатано ООО "Универс-групп"

Введение.

ГЛАВА 1. ВСПОМОГАТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ АЛГЕБРАИЧЕСКИХ ПОЛЕЙ.

1.1. Рекуррентные функции в конечных полях.

1.1.1. Некоторые свойства показательных и рекуррентных функций в конечных полях.

1.1.2. Тригонометрические суммы и суммы характеров с показательными функциями.

1.2. Канонические системы счисления в квадратичных полях.;.

1.2.1. Классификация канонических систем счисления.

1.2.2. Представление данных в канонических системах счисления.

ГЛАВА 2. ОДНОМЕРНЫЕ ДИСКРЕТНЫЕ ПРЕОБРАЗОВАНИЯ С ШУМОПОДОБНЫМ БАЗИСОМ.

2.1. М -преобразования.

2.1.1. Шумоподобные базисы с равномерным распределением значений.

2.1.2. Шумоподобные базисы с полиномиальным законом распределения значений.

2.1.3. Специальный случай: редуцированные базисы, порожденные показательной функцией в конечном поле.

2.2. Статистические свойства значений базисных функций

М -преобразований.

2.2.1. Проверка равномерности и независимости, следующих друг за другом пар.

2.2.2. Проверка комбинаций (Покер-тест).

ГЛАВА 3. ДВУМЕРНЫЕ ПРЕОБРАЗОВАНИЯ

С ШУМОПОДОБНЫМ БАЗИСОМ.

3.1. Синтез базисов двумерных шумоподобных преобразований.

3.2. Хаотичность последовательности значений базисных функций.

3.3. Быстрые алгоритмы М-преобразований.

ГЛАВА 4. ОПИСАНИЕ АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ И ЭКСПЕРИМЕНТАЛЬНЫХ РЕЗУЛЬТАТОВ.

4.1. Алгоритмы и программы определения параметров

М -преобразований.

4.1.1. Алгоритм определения характеристик квадратичных полей, в которых существуют КСС.

4.1.2. Алгоритм представления целых чисел в канонических системах счисления.

4.1.3. Алгоритм генерации "фундаментальных" областей для квадратичных полей, в которых существуют КСС.

4.1.4. Алгоритм нумерации элементов "фундаментальной" области.

4.1.5. Алгоритм нумерации элементов периодического ограничения "фундаментальной" области.

4.1.6. Алгоритм синтеза базисных функций двумерных

М -преобразований.

4.2. Корреляционные свойства поля ошибок.

Целью диссертационной работы является разработка и исследование нового класса дискретных ортогональных преобразований, базисные функции которых имеют "шумоподобную" структуру.

Актуальность темы. В составе алгоритмического обеспечения компьютерных систем обработки сигналов и изображений одно из центральных мест занимают алгоритмы дискретных ортогональных преобразований (ДОП). Историю систематического использования методов дискретного спектрального анализа сигналов принято отсчитывать с 1965 г., когда Кули и Тьюки опубликовали свой быстрый алгоритм вычисления дискретного преобразования Фурье (ДПФ), хотя ранее Гуд (1960 г.) и Томас (1963 г.) опубликовали в практически незамеченных современниками работах свои быстрые алгоритмы ДПФ, базирующиеся на несколько ином подходе. За время, прошедшее с первых публикаций, дискретный спектральный анализ стал одним из основных средств решения задач цифровой обработки сигналов, распознавания образов, машинного зрения, компьютерной оптики и т.д.

Разработке различных аспектов теории и применения дискретного спектрального анализа с использованием различных ДОП посвящено большое количество публикаций как у нас в стране, так и за рубежом. Значительный вклад в развитие общей теории ДОП внесли С.С. Агаян, Н.Н. Айзенберг, В.А. Власенко, A.M. Крот, В.Г. Лабунец, A.M. Трахтман, Л.П. Ярославский, Р. Агарвал, Ш. Виноград, Г. Нуссбаумер, Ч. Рейдер и др. Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны A.M. Григоряном, И.Е. Капориным, Е.Е. Тыртышниковым и др.

В настоящее время теория ДОП развивается, в частности, в следующих направлениях:

• синтез параметрических семейств новых ортогональных базисов со структурой быстрых алгоритмов, инвариантной по отношению к той или иной концепции синтеза таких алгоритмов;

• разработка новых конкретных алгоритмов ДОП, обладающих повышенной точностью и/или быстродействием, адекватных по структуре вычислений последним разработкам в области специализированных процессоров и характеристикам каналов передачи информации.

Именно последний этот аспект теории ДОП — разработка, синтез и исследование ДОП, адекватных особенностям реальных или целенаправленно созданных каналов передачи информации, представляется до сих пор мало исследованным, хотя широкое распространение методов дискретного спектрального анализа в разнообразных задачах передачи и обработки информации делает эту проблему весьма актуальной.

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

N-1 и=0

N-1

0.1)

0.2) информации случайным образом утрачивается ("канал с пропусками"), то при утрате "энергетически значимых" компонент спектра на изображение накладываются "структурированные помехи", к которым зрительная система человека более чувствительна, чем к точечному шуму. На рисунках 0.1 (б)-(в) показаны примеры таких структурированных помех, отличающиеся от точечного шума (рисунок 0.1 (г)). а) Исходное изображение б) Искажения при применении преобразования Хартли в) Искажения при применении (г) Искажения при применении преобразования Адамара хаотического преобразования

Рис. 0.1. Примеры структурированных помех от применения различных дискретных ортогональных преобразований

В связи с этим целесообразно рассматривать такие преобразования, которые не обладают свойством концентрации энергии в нескольких спектральных компонентах. В частности, желательно, чтобы влияние канальных ошибок было бы менее заметно, чем при применении классических дискретных ортогональных преобразований Фурье, Уолша, Хартли и др. Другими словами, мы намерены рассматривать дискретные ортогональные преобразования, базисные функции которых имеют шумоподобный характер. Для таких преобразований спектральные компоненты "энергетически равноправны".

Такие одномерные преобразования (0.1), базисные функции hm(n) которых принимают "хаотическим" образом два различных значения, введены в [89]. В работах [88], [100], [107] рассмотрены приложения таких преобразований к кодированию видеоинформации. Различные обобщения основной конструкции работы [106] рассматривались в [59], [71], [79], [80] для случая к-значных функций hm(n).

Основой для построения семейства базисных функций исследуемых дискретных ортогональных преобразований является линейная рекуррентная последовательность (т-последовательность [14], [40]) y(n)=aly(n-l)+.+asy(n-s); ajeGF(q), а3Ф0 (0.3) элементов конечного поля GF(#) из q=ps элементов (р — простое число) с максимально возможным периодом T=qs-1.

При построении базисных функций преобразования (0.1) члены последовательности >>(/2)eGF(#) заменяются вещественными числами hm(n) таким образом, чтобы для функций выполнялось условие ортогональности (0.2).

Одной из основных проблем, препятствующих экстраполяции методов цитированных работ на двумерный случай, является проблема построения "хорошей" одномерной нумерации двумерного массива ,«2)» п1>п2еЩ.

В работах [96], [97] введено понятие канонической системы счисления в кольце S^V^j целых элементов квадратичного поля

Q^\[d^={z=a+byjd; a,6eQj, позволяющих представить элементы zeS^V^j в форме конечной суммы z=^zjaj, k(z)=s, (0.4) j=0 где "цифры" zj принадлежат некоторому конечному подмножеству NczZ, а элемент а (основание системы счисления) есть некоторый элемент кольца s(V^).

В настоящей работе мы устанавливаем взаимнооднозначное соответствие между элементами "гусеницы"

Y0=(>>(0),. • Y1 =(^(1),. • • ->YN-1 =(y{N~0" • -1+*)) (0.5)

A^-периодической m -последовательности (0.3) и элементами кольца S^/jj, представимыми s -членными суммами (0.4). На основе такого соответствия мы вводим двумерные ортогональные преобразования

N-1 N-1 х(тьт2)= £ Z хЫ'ПгЖч/пг0пЪп2) (°-6)

1=0 «2=0 с условием ортогональности

N-1 N-1

Е Е hm\("1 ,к2 ("1 '"2^ Лг

1=0 и2=0 и с шумоподобным поведением значений базисных функций («1,^2).

Эти факторы и определяют в основном задачи диссертационного исследования.

Задачи диссертационной работы.

1. Синтез одномерных М -преобразований, базисные функции которых принимают q различных значений с равными частотами (q - степень простого числа р).

2. Синтез одномерных обобщенных М -преобразований, базисные функции которых принимают "случайным образом" значения в соответствии с полиномиальным законом распределения.

3. Синтез двумерных преобразований с шумоподобными базисами, ассоциированными с псевдослучайной разверткой (нумерацией) массива пикселей входного и выходного изображений.

4. Разработка необходимого программного обеспечения для определения параметров рассматриваемых преобразований.

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

Перечисленные задачи определяют структуру работы и содержание отдельных глав.

Краткое содержание диссертации. Диссертационная работа, содержащая 127 стр., состоит из введения, четырех глав, заключения, списка использованной литературы, составляющего 121 наименование и 2 приложений объемом 16 страниц.

ЗАКЛЮЧЕНИЕ

Перечислим наиболее важные на наш взгляд выводы, следующие из диссертационного исследования.

1. Синтезированы одномерные дискретные ортогональные преобразования, базисные функции которых принимают q различных значений с равными частотами (q - степень простого числа р);

2. Синтезированы одномерные дискретные ортогональные преобразования, базисные функции которых принимают "случайным образом" значения в соответствии с полиномиальным законом распределения;

3. На основе синтезированных одномерных дискретных ортогональных преобразований с "шумоподобными" базисами синтезированы двумерные преобразования с "шумоподобными" базисами согласованные с псевдослучайной разверткой (нумерацией) массива пикселей входного и выходного изображений.

1. Бахтурин Ю.А. Основные структуры современной алгебры. - М.: Наука, 1990.

2. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. — М.: Мир, 1989.

3. Боревич З.И., Шафаревич И.Р. Теория чисел. 3-е изд., доп. - М.: Наука, 1985.

4. Боровков А.А. Теория вероятностей. М.: Наука, 1986.

5. Брейсуэлл Р. Преобразование Хартли. М.: Мир, 1990.

6. Бесполитов О.В., Чернов В.М. Быстрое вычисление дискретной свертки в редуцированных системах счисления для комплексных полей Мерсенна // Компьютерная оптика, 24. 2002. - С. 126-129.

7. Бесполитов О.В., Чернов В.М. Параллельные алгоритмы вычисления свертки в редуцированных канонических системах счисления для квадратичных полей // Искусственный интеллект. 2004. - № 2. - С. 197-200.

8. Бесполитов О.В. Дискретные ортогональные преобразования с "хаотическими" базисными функциями // Вестник Самарского гос. Университета. Естественнонаучная серия. 2005. - № 3(37). - С. 5-19.

9. И. Бесполитов О.В. Дискретные ортогональные преобразования с "хаотическими" базисными функциями // Обозрение прикладной и промышленной математики. М.: ТВП, 2005. - Т. 12. - В. 4. - 850 с.

10. Ван дер Варден Б.Л. Алгебра. М.: Наука, 1979.

11. Виноградов И.М. Основы теории чисел. 8-е изд. - М.: Наука, 1972.

12. Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра. М.: Мир, 1991.-352 с.

13. Елизаров В.П. Конечные кольца. М.: 1993.

14. Ивченко Г.И., Медведев Ю.И. Математическая статистика. М.: Высшая школа, 1984.

15. Камловский О.В. Распределение элементов на циклах линейных рекуррентных последовательностей над кольцами Галуа // Успехи мат. наук, 53. 1998. -№ 2. - С. 149-150.

16. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. 2-е изд. М.: Наука, 1977.

17. Кейперс JL, Нидеррейтер Г. Равномерное распределение последовательностей. М.: Мир, 1985. - 408 с.

18. Кнут Д.Е. Искусство программирования для ЭВМ. М.: Мир, 1977. - Т. 2.

19. Коробов Н.М. О распределении дробных долей показательных функций // Вестник МГУ. Серия матем., мех. 1966. - № 4. - С. 42-46.

20. Коробов Н.М. Числа с ограниченным отношением и их приложения к вопросам диофантовых приближений // Изв. АН СССР, 19. 1955. — С. 361-363.

21. Коробов Н.М. Распределение невычетов и первообразных корней в рекуррентных рядах // Докл. АН СССР, 88. 1953. - № 4. - С. 603-606.

22. Коробов Н.М. Тригонометрические суммы и их приложения. М.: Наука, 1989.-240 с.

23. Кострикин А.И. Введение в алгебру. М.: Наука, 1977.

24. Кроновер P.M. Фракталы и хаос в динамических системах. Основы теории. -М.: Постмаркет, 2000.

25. Лаксов Д. Линейные рекуррентные последовательности над конечными полями // Математика (Сб. переводов), 11.- 1967. -№ 6. С. 145-158.

26. Ленг С. Алгебра.-М.: Мир, 1968.-564 с.

27. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988. - Т. 1,2.- 824 с.

28. Макклеллан Дж.Х., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов / Под ред. Манина Ю.И. М.: Радио и связь, 1983.

29. Марпл С.Л. (мл.) Цифровой спектральный анализ и его приложения. -М.: Мир, 1990.

30. Морозов А.Д. Введение в теорию фракталов. Москва-Ижевск: Институт компьютерных исследований, 2002.

31. Мун Ф. Хаотические колебания. М.: Мир, 1990.

32. Ноден П., Китте К. Алгоритмическая алгоритмика. М. Мир, 1999.

33. Нечаев В.И. Линейные рекуррентные сравнения с периодическими коэффициентами // Мат. заметки, 3. 1968. - № 6. - С. 625-632.

34. Нечаев В.И. Линейные сравнения по модулю простого идеала и линейные рекуррентные последовательности // Уч. зап. Моск. пед. инст. им. В.И. Ленина, 375. 1971. - С. 124-132.

35. Нечаев В.И., Полосуев A.M. О распределении невычетов и первообразных корней в последовательности, удовлетворяющей конечно-разностному уравнению с полиномиальными коэффициентами // Вестник Моск. унив. Серия матем., мех., 6. 1964. - С. 75-84.

36. Нечаев В.И. Рекуррентные последовательности // Уч. зап. Моск. пед. инст. им. В.И. Ленина, 375. 1971. - С. 103-123.

37. Нечаев В.И., Степанова Л.Л. Распределение невычетов и первообразных корней в рекуррентных последовательностях над полем алгебраических чисел // Успехи мат. наук, 20. 1965. - № з. - С. 197-203.

38. Нечаев В.И. Тригонометрические суммы для рекуррентных последовательностей элементов конечного поля // Мат. заметки, 11.-1972.-№5. с. 597-607.

39. Нечаев В.И. Тригонометрические суммы для рекуррентных последовательностей // Докл. АН СССР, 206. 1972. - № 4. - С. 811814.

40. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. -М.: Радио и связь, 1985.

41. Оппенгейм А., Шафер Р. Цифровая обработка сигналов. М.: Связь, 1979.

42. Применение цифровой обработки сигналов / Под ред. Э. Оппенгейма. -М.: Мир, 1980.

43. Постников А.Г. Арифметическое моделирование случайных процессов // Труды Матем. ин-та им. В.А. Стеклова. М.: Изд-во АН СССР, 1960. -Т. 57.-84 с.

44. Постников А.Г. Эргодические вопросы теории сравнений и теории диофантовых приближений // Труды Матем. ин-та им. В.А. Стеклова. -М.: Наука, 1966.-Т. 82.

45. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. -М.: Мир, 1978.

46. Сидельников В.М. Оценки для числа появлений знаков на отрезке рекуррентной последовательности над конечным полем // Дискрет, мат., 3.- 1991.-№ 2.-С. 87-95.

47. Общая алгебра / Под ред. Л.А. Скорнякова. -М.: Наука, 1990. Т. 1,2.

48. Соболь И.М. Численные методы Монте-Карло. — М.: Наука, 1973. 311 с.

49. Солонина А.И., Улахович Д.А., Яковлев Л.А. Алгоритмы и процессоры обработки сигналов. СПб.: БХВ-Петербург, 2001.

50. Таусворт Р. Случайные числа, порождаемые линейными рекуррентными соотношениями по модулю 2 // Киберн. сбор. 1979. - Вып. 16. - С. 6273.

51. Усольцев Л.П. Задача на построение, связанная с равномерным распределением дробных долей показательных функций // Изв. ВУЗов. Математика. 1967. - № 12. - С. 75-83.

52. Федер Е. Фракталы / Пер. с англ. Данилов Ю.А. М.: Мир, 1991.

53. Хассе X. Лекции по теории чисел. М.: ИЛ, 1953.

54. Чебышев П.Л. Теория вероятностей. Лекции 1879-1880. М.-Л., 1936. -С. 139-147.

55. Чернов В.М., Коломиец Э.И. Дискретные ортогональные преобразования с шумоподобным базисом // Труды коллоквиума "Стохастические методы геометрии и анализа". М., 1994. - С. 59-61.

56. Шпарлинский И.Е. О распределении значений рекуррентных последовательностей // Проблемы передачи информации, 25. 1989. -№2.-С. 46-53.

57. Шпарлинский И.Е. Распределение дробных долей рекуррентных последовательностей // Журн. вычисл. мат. и мат. физ., 21. 1981. — № 6.-С. 1588-1591.

58. Шпарлинский И.Е. Распределение невычетов и первообразных корней в рекуррентных последовательностях // Мат. заметки, 24. 1978. - № 5. -С. 605-615.

59. Шредер М. Фракталы, хаос, степенные законы. Ижевск: Изд. Дом "Удмуртский университет", 2000.

60. Шустер Г. Детерминированный хаос. М.: Мир, 1988.

61. Adier R.J. The Geometry of Random Fields. New York: John Wiley & Sons, 1981.

62. Akiyama S., Petho A. On canonical number systems // Theoretical Computer Science, 270. 2002. - P. 921-933.

63. Assaf D., Gadbois S. Definition of Chaos // American Mathematical Monthly. 1992. - Vol. 99. - № 9. - 865 p.

64. Barnsley M.F. Fractals everywhere. New York: Academic Press, 1988.

65. Brillart J., Lehmer D.H., Selfridge J.L., Tuckerman В., Wagstaff S.S.

66. Factorization of b"± 1, 6=2,3,5,6,7,10,11,12 up high powers // Contemp.1. Math.- 1988.-Vol. 22.

67. Cerlienco L., Mignotte M., Piras F. Linear recurrent sequences: algebraic and arithmetical properties // Enseign. Math., 33. 1987. - № 1, 2. - P. 67-108.

68. Chernov V.M., Dmitriyev A.G. Image Compression Using Discrete Orthogonal Transforms with the "Noise-Like" Basis Functions // Компьютерная оптика, № 19. 1999.

69. Chernov V.M., Bespolitov O.V. A new method for embedding secret data to the container image using 'chaotic' discrete orthogonal transforms // Proceedings of The 4th International Workshop on Security In Information Systems (WOSIS-2006). Springer, 2006.

70. Chin W., Goldman J. Bialgebras of linearly recursive sequences // Commun. Algebra, 21. 1993. - № 11. - P. 3935-3952.

71. Clark W.E., Liang J.J. Enumeration of finite commutative chain rings // J. of Algebra, 27. 1973. -№ 3. - P. 445-453.

72. Crownover R.V. Introduction to Fractals and Chaos. Jones Barlett Publ., 1995.

73. Davio M, Deschamps J.P., Gossart C. Complex arithmetic. — Brussels: Philips M.B.L.E. Research Lab, 1978. Report 369.

74. Davis C., Knuth D.E. Number Representations and Dragon Curves // Journal of Recreational Mathematics. 1970. - Vol. 3. - P. 66-81 and 133-149.

75. Devaney R.L. An Introduction to Chaotic Dynamical Systems. Addisson-Wesley, Reading, Mass., 1993.

76. Dmitriev A.G., Chernov V.M. Generating Pseudostochastic Basis Function for Discrete Orthogonal Transforms // Pattern Recognition and Image Analysis.-2001.-Vol. 11.-№ l.-P. 155-157.

77. Dmitryev A.G., Chernov V.M. Two-dimensional Discrete Orthogonal Transforms with the "Noise-like" Basis Functions // Proc. Int. Conf. GraphiCon 2000. P. 36-41.

78. Falconer K. Fractal Geometry: Mathematical Foundations and Applications. -New York: John Wiley & Sons, 1990.

79. Fraenkel A.S. Arrays, numeration systems and Frankenstein games // Theoretical Computer Science, 282. 2002. - P. 271-284.

80. Gilbert W.J. Arithmetic in complex bases // Math. Mag. 1984. - Vol. 57. -P. 77-81.

81. Gilbert W.J. Radix representations of quadratic fields // J. Math. Anal. Appl. 1981. - Vol. 83. - P. 264-274.

82. Gilbert W.J. Complex numbers with three radix expansions // J. Math. -1982.-Vol. 34. — P. 1335-1348.

83. Gilbert W.J. Fractal Geometry derived from Complex Bases // Math. Intelligencer. 1982. - Vol. 4. - P. 78-86.

84. Gilbert W.J. The Fractal Dimension of Sets derived from Complex Bases // Math. Bull. 1986. - Vol. 29. - P. 495-500.

85. Grallert H.-J. Source encoding and error protected transmission of pictures with help of orthonormalized m-sequences // Proc. 12-th Int. Television Symp. Switzerland: Montreux, 1981. - P. 441-454.

86. Grallert H.-J. Application of orthonormalized m-sequences for data reduced and error protected transmission of pictures // Proc. IEEE Int. Symp. on Electromagnetic Compability. Baltimore: MD, 1980. - P. 282-287.

87. Gulick D. Encounters with Chaos. NY: McGraw-Hill, 1992.

88. Haukkanen P. On a convolution of linear recurring sequences over finite fields//J. of Algebra, 149.- 1992.-№ l.-P. 179-182.

89. Herlestam T. On functions of linear shift register sequences // Lect. Notes Comput. Sci., 219. 1986. - P. 119-129.

90. Herlestam T. On the complexity of functions of linear shift register sequences // Int. Symp. Inform. Theory. France: Les Arc, 1982.

91. Hutchinson J.E. Fractals and self similarity // Math. J. Indiana Univ., 1981. -Vol. 30.-P. 713-747.

92. Ifeachor E.C., Jervis B.W. Digital Signal Processing. Prentice Hall, 2001.

93. Katai I. Generalized number systems in Euclidean spaces // Mathematical and Computer Modelling, 38. 2003. - P. 883-892.

94. Katai I., Ко vacs B. Canonical Number Systems in Imaginary Quadratic Fields. Hungaricae: Acta Math. Acad. Sci., 1981. - Vol. 37. - P. 159-164.

95. Katai I., Kovacs B. Kanonische Zahlensysteme in der Theorie der quadratischen algebraischen. Szeged: Acta Sci. Math., 1980. - Vol. 42. - P. 99-107.

96. Katai I., Szabo J. Canonical number systems for complex integers. Szeged: Acta Sci. Math., 1975. - Vol. 37. - P. 255-260.

97. Keesen W.G, Riemann U, Grallert H.-J. Codierung von Farbensehsignalen mittels modifizierten M-Transformmationen fuer die Uebertragung ueber 34-Mbit/s-Kanaele. German: Frequenz, 1984. - Vol. 38. - № 10. - P. 238243.

98. Kovacs A., Petho A. Number systems in integral domains, especially in orders of algebraic number fields // Szeged: Acta Sci. Math., 1991. Vol. 55. -P. 287-299.

99. Kovacs A. Generalized binary number systems // Sci. Sect. Сотр., 20. -Budapest: Annales, 2001. P. 195-206.

100. Kovacs A. On expansions of Gaussian integers with non-negative digits // Mathematica Pannonica, 10/1. 1999. - P. 177-191.

101. Lu P., Song G. Feasible calculation of the generator for combined LFSR sequences //Led. Notes Comput. Sci., 508. 1991. - P. 86-95.

102. Lu P., Song G., Zhou J. Tensor product with application to linear recurring sequences // J. Math. Res. Exposition, 12. 1992. - № 4. - P. 551-558.

103. Mac Williams F.J., Sloane N.J. Pseudo-random sequences and arrays //Proc. IEEE, 64. 1976. -№ 11. - P. 1715-1729.

104. Musmann H.G, Pirsch P., Grallert H.-J. Advances in picture coding // IEEE Proc., 1985. Vol. 73. - № 4. - P. 523-548.

105. Peitgen H.-O, Jurgens H, Saupe D. Chaos and Fractals: New Frontiers of Science. New York: Springer-Verlag, 1992.

106. Reeds J.A., Sloane N.J. Shift-register synthesis (modulo m) // J. on computing, 14.- 1985.-№ 3. -P. 505-513.

107. Rees C.S, Shah S.M., Stanojevic C.V. Theory and Applications of Fourier Analysis. New York: Marcel Dekker, 1981.

108. Rees D. Note on a paper by I.J. Good // J. London Math. Soc., 213. 1946. -№ 83.-169 p.

109. Safer T. Polygonal radix representations of complex numbers // Theoretical Computer Science, 210. 1999. - P. 159-171.

110. Selmer E.S. Linear recurrence relations over finite fields. Norway: Univ. of Bergen, 1966.

111. Sylvester J.J. Note on Complex Integers // J. Pure and Applied Math. 1861. -Vol. 4.-P. 94-96.

112. Thuswaldner J.M. Elementary Properties of Canonical Number Systems in Quadratic Fields. In: Applications of Fibonacci Numbers. Kluwer, 1998. -Vol. 7.-P. 405-409.

113. Vajda I., Nemetz T. Substitution of characters in q-oiy m -sequences I I Lect. Notes Comput. Sci., 508. 1991. - P. 96-105.

114. Ward M. Arithmetical properties of sequences in rings // Ann. Math., 39. -1938.-P. 210-219.

115. Ward M. The arithmetical theory of linear recurring series // Trans. Amer. Math. Soc., 35. 1933. -№ 3. - P. 600-628.

116. Zierler N. Linear recurring sequences and error-correcting codes. Error Correcting Codes. New York: Wiley, 1968. - P. 47-59.

117. Zierler N. Linear recurring sequences // J. Soc. Ind. Appl. Math., 7. 1959. -№ 1. - P. 31-48. / Русский перевод: Цирлер H. Линейные возвратные последовательности // Кибернетический сб., 6. - М.: ИЛ, 1963. - С. 5579.

118. Zierler N., Mills W.H. Products of linear recurring sequences // J. of Algebra, 27.-1973.-№ l.p. 147-157.