Квазирешетки в прикладных задачах обработки цифровой информации
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
О - кольцо целых чисел квадратичного поля , ' - сопряжение в F и [2]. Здесь в равенстве (1.9) J2 = J J - окно или внутреннее пространство, выделяющее квазирешетку F2 из всюду плотного множества O2 в виде (r, R) - системы Делоне, т.е. не слишком плотной и не слишком разреженной системы точек на плоскости R2.
Рисунок 1.1 - Квадратная решетка Фибоначчи F2
Двумерные квазирешетки F2 первым ввел и исследовал их физические свойства Лифшитц [3]. В данном случае F2 используеться как двумерная квазирешетка, которая содержит в себе все основные виды одномерных квазирешеток Фибоначчи, что и позволяет получить их полную классификацию [4].
Выберем две произвольные точки из F2 и проведем через них прямую L. Тогда данная прямая L порождает
(1.10)
одномерную квазирешетку L, вложенную в F2. В настоящей работе классифицируются все возникающие указанным способом квазирешетки L из F2. В основу положена параметризация
(1.11)
квазирешетки L точками t' из множества параметров , где ? - некоторый интервал из J, - примитивный направляющий вектор прямой L из уравнения (1.10) и ? - вектор сдвига.
Одномерные квазирешетки и называются подобными , если одна переводится в другую некоторым преобразованием подобия плоскости R2. Т. е. две квазирешетки L, L ' из квадратной квазирешетки F2 подобны:
. (1.12)
Вторая эквивалентность из (1.12) означает , где - подгруппа положительных единиц из группы единиц О кольца Фибоначчи О. Используя параметризацию (1.11) можно показать, что множество классов подобных квазирешеток находится во взаимно-однозначном соответствии с числами из множества .
Две одномерные квазирешетки L, L ' из F2 принадлежат к одному локальному типу или локально эквивалентны , если найдется такое преобразование подобия s, что квазирешетки имеют одно и то же множество расстояний между соседними точками. Это множество может состоять из двух g, e или трех g, e, g + e расстояний, где g/e = ?. Выберем произвольную точку x пусть x-, x+ ? L - соседние для x точки, упорядоченные, согласно направляющего вектора ?. Тогда найдется такая точка x' ? l', для которой соседние расстояния будут , и наоборот. Из определения следует, что локально эквивалентные квазирешетки l, l' локально не различимы.
В таблице. 1.1 для квазирешеток l локального типа j = 0,1, 2, 3 указаны все допустимые первые локальные окружения точек. Пусть, например, j = 0 и точка x ? L имеет соседние точки x- ,x+ ? L. Тогда расстояния могут принимать следующие три значения: (r-, r+) = (g, e), (e, g) или (e ,e). В таблице 1.1 можно видеть, как при изменении длины интервала ? для квазирешетки появляются или исчезают те или иные виды локальных окружений. Во втором столбце указано количество всех локальных окружений. Локальные типы j =0, 1, 2, 3 различны, а следующий локальный тип j =0' эквивалентен j =0. При переходе с одного уровня на другой происходит увеличение локальных расстояний в ? + 1 раз, что влечет периодичность j mod 4.
Таблица 1.1 - Локальные типы одномерных квазирешеток L из F2
j=03(g,e), (e,g)(e,e)j = 15(g,e), (e,g)(e,e)(e, g + e),(g + e, e)j = 24(g,e), (e,g)(e, g + e),(g + e, e)j = 35(,e), (e,g)(e, g + e),(g + e, e)(g + e, g + e)j =0'3(e, g + e),(g + e, e)(g + e, g + e)
Также известно, что любая одномерная квазирешетка l из двумерной квазирешетки Фибоначчи F2 имеет один из локальных типов j, где j =0, 1, 2, 3, и каждый такой локальный тип реализуется некоторой квазирешеткой l из F2.
Любые две решетки одной размерности над Z подобны. Данный факт резко контрастирует с существованием счетного множества классов подобных одномерных квазирешеток l из F2. Более того, даже на локальном уровне существуют четыре различных типа таких квазирешеток. Все они образуют класс одномерных квазирешеток Фибоначчи, которые характеризуются как квазирешетки, параметризуемые вращениями окружности и их индуцированными отображениями (отображениями Пуанкаре).
Уровень m = 0,1, 2,... квазирешетки определяется из соотношений
или
и соответственно квазирешетка L называется невырожденной или вырожденной. В первом случае интервал ? разбивается
(1.13)
на приложенные друг к другу полуинтервалы, и биекция ? представляет собой параметризацию квазирешеток L с помощью нециклического перекладывания полуинтервалов разбиения (1.13). Во втором случае из (1.12) полуинтервал в разбиении (1.13) исчезает. Поэтому квазирешетки L параметризуются перекладыванием двух полуинтервалов или, что равносильно, вращением окружности.
Разобьем множество точек квазирешетки L имно-жество ее параметров аналогично разбиению (1,13). Предположим, что ? ? 0 для направляющего вектора ? ? (?1, ?2 ),и пусть p r1x = x1 - проекция вектора x = (x1, x2) на ось OX .Для каждого вида точек x = xY из L , где Y = G, GE, E, определим частоту
его появления на квазирешетке . Если квазирешетка имеет четный уровень m, то частоты py ее точек xY ? L вычисляются по формулам
(1.14)
если L - невырожденная квазирешетка, и
(1.15)
если L вырожденная. Аналогичные формулы имеют место для нечетного уровня m. Пусть nL(X) обозначает количество точек x = (x1, x2) на квазирешетке L с 0 ? x1 ? X. Тогда для nL(X) имеет место асимптотическое равенство
при (1.16)
где .
Кольцо Фибоначчи является евклидовым. Оно обладает алгоритмом деления с остатком по норме [1]. Еще одно применение одномерных квазирешеток состоит в том, что нормированная квазирешетка задает, по терминологии Кука, одномерный 2-ступенчатый алгоритм Евклида, когда в качестве неполного частного для , где и , выбирается максимальное числ?/p>