Главная > Моделирование, обработка сигналов > Преобразование Хартли
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Ячеистая структура перестановочной диаграммы

Если проанализировать диаграммы, представленные на рис. 7.3, или данные табл. 7.1, то обнаружится их повторяющийся характер, что иллюстрируется на рис. 7.4. Выполняя разбиение перестановочной диаграммы для N = 32 на четыре ромбовидные ячейки и соединяя между собой атомы в пределах каждой ячейки, чтобы подчеркнуть форму соответствующих фигур, обнаруживаем наличие кристаллической структуры, периодически повторяющейся на непрямоугольном базисе в обоих направлениях. Интересно отметить, что контур фигуры в каждой ячейке повторяет по форме перестановочную диаграмму для N = 8, но по сравнению с последней имеет в два раза больший масштаб. Теперь если масштаб полной диаграммы для N = 32 увеличить в два раза, то получим периодически повторяющуюся структуру, соответствующую диаграмме, для которой N = 128.

Для нечетных показателей степени имеем одно семейство диаграмм, а для четных -другое семейство. Данная топология совсем не является очевидной из определения алгоритма, иллюстрируемого на рис. 7.2, но проявляется в явном виде в случае, когда мы располагаем информацией о числе перестановочных матриц с целью соответствующей проверки. Очевидно, имеются два семейства ячеек; семейство I включает в себя ячейки, содержащие по четыре атома, в совокупности образующие фигуру, напоминающую бумажного змея, тогда как семейство состоит из ячеек, содержащих восемь атомов, расположенных в форме лягушки. Легко убедиться в правомерности следующих характеристик:

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

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

Коэффициент 4 обусловлен тем, что шаг решетки атомов в пределах одной ячейки равен Подстрочный индекс 4 означает число ячеек вдоль одной оси координат. Так как общее количество атомов равно N, а в ячейке содержится 4 или 8 атомов, то полное число ячеек составляет или 8), а число ячеек вдоль одной оси координат есть корень квадратный из этой величины:

Шаг решетки в пределах одной ячейки равен «ширине» этой ячейки деленной на число содержащихся в ней атомов (т. е. на 4 или 8), и таким образом равен чем и обусловлено двукратное появление числа 4 в уравнениях для координат элементов ячеек. В общем случае имеем

Описанная здесь топологическая структура является основой алгоритма быстрой перестановки FASTPERMUTE, рассматриваемого ниже.

Медленная перестановка, которая является традиционной, выполняется следующим образом. Для определения при заданных и N осуществляются двоичное представление с использованием Р двоичных разрядов, а затем запись элементов полученного числа в обратном порядке их следования и возвращение к десятичному представлению этого числа. Например, нам известно, что для N = 16 имеем: . Двоичным представлением числа является , а числа .

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

этой процедуры, в формализованном представлении имеет вид

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

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