Перестановка с обращением битов - Википедия - Bit-reversal permutation

В прикладной математике перестановка с обращением битов это перестановка из последовательность из п предметы, где п = 2k это сила двух. Он определяется индексированием элементов последовательности числами от 0 до п - 1, а затем двоичные представления каждого из этих чисел (дополненных таким образом, чтобы каждое из этих двоичных чисел имело длину точноk). Затем каждый элемент сопоставляется с новой позицией, заданной этим обратным значением. Перестановка инверсии битов - это инволюция, поэтому повторение одной и той же перестановки дважды возвращает к исходному порядку элементов.

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

Пример

Рассмотрим последовательность из восьми букв abcdefgh. Их индексы представляют собой двоичные числа 000, 001, 010, 011, 100, 101, 110 и 111, которые при обратном преобразовании становятся 000, 100, 010, 110, 001, 101, 011 и 111. а в позиции 000 отображается на ту же позицию (000), буква б в позиции 001 отображается на пятую позицию (позиция с номером 100) и т. д., давая новую последовательность aecgbfdh. Повторение той же перестановки в этой новой последовательности возвращает к исходной последовательности.

Запись номеров индексов в десятичном формате (но, как и выше, начиная с позиции 0, а не с более обычного начала 1 для перестановки), перестановки с инверсией битов размера 2k, за k = 0, 1, 2, 3, ... являются

  • к = 0: 0
  • к = 1: 0 1
  • к = 2: 0 2 1 3
  • к = 3: 0 4 2 6 1 5 3 7
  • к = 4: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

(последовательность A030109 в OEIS )
Каждая перестановка в этой последовательности может быть сгенерирована путем конкатенации двух последовательностей чисел: предыдущая перестановка, удвоенная, и та же самая последовательность с каждым значением, увеличенным на единицу. Таким образом, например, удвоение перестановки длины 4 0 2 1 3 дает 0 4 2 6, добавление единицы дает 1 5 3 7, и объединение этих двух последовательностей дает перестановку длины 8 0 4 2 6 1 5 3 7.

Обобщения

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

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

Есть два расширения перестановки с обращением битов к последовательностям произвольной длины. Эти расширения совпадают с перестановкой битов для последовательностей, длина которых равна степени 2, и их цель - разделить соседние элементы в последовательности для эффективной работы Алгоритм Качмара. Первое из этих расширений, названное Эффективный заказ,[2] работает с составными числами и основан на разложении числа на его простые компоненты.

Второе расширение, называемое EBR (Extended Bit-Reversal),[3] По духу похож на бит-реверс. Учитывая массив размера п, EBR заполняет массив перестановкой чисел в диапазоне в линейное время. Последовательные числа разделяются при перестановке не менее чем на позиции.

Приложения

Реверс битов наиболее важен для Radix-2 Алгоритмы Кули – Тьюки БПФ, где рекурсивные этапы алгоритма, работающие на месте, подразумевают небольшое изменение входов или выходов. Точно так же в БПФ Кули – Тьюки со смешанным основанием возникают инверсии цифр.[4]

Перестановка с инверсией битов также использовалась для разработки нижняя граница в распределенных вычислениях.[5]

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

В музыкальных исследованиях перестановка с инверсией битов также использовалась для корреляции функций ранжирования метрического веса и частот начала классического корпуса в общем времени (4/4).[6]

Алгоритмы

В основном из-за важности быстрое преобразование Фурье алгоритмов, были разработаны многочисленные эффективные алгоритмы для применения перестановки с обращением битов к последовательности.[7]

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

Еще одно соображение, которое еще более важно для производительности этих алгоритмов, - это влияние иерархия памяти по времени работы. Из-за этого эффекта более сложные алгоритмы, учитывающие блочную структуру памяти, могут быть быстрее, чем это наивное сканирование.[7][8] Альтернативой этим методам является специальное компьютерное оборудование, которое позволяет обращаться к памяти как в обычном, так и в обратном порядке.[10]

Рекомендации

  1. ^ Ян, Цинсюань; Эллис, Джон; Мамакани, Халег; Раски, Фрэнк (2013), «Перестановка на месте и идеальная перестановка с использованием инволюций», Письма об обработке информации, 113 (10–11): 386–391, Дои:10.1016 / j.ipl.2013.02.017, МИСТЕР  3037467.
  2. ^ Герман, Габор Т. (2009). Основы компьютерной томографии (2-е изд.). Лондон: Спрингер. п.209. ISBN  978-1-85233-617-2.
  3. ^ Гордон, Дэн (июнь 2017 г.). «Дерандомизационный подход к восстановлению сигналов с ограниченной полосой пропускания в широком диапазоне случайных частот дискретизации». Численные алгоритмы. 77 (4): 1141–1157. Дои:10.1007 / s11075-017-0356-3.
  4. ^ Б. Голд и К. М. Рейдер, Цифровая обработка сигналов (Нью-Йорк: McGraw – Hill, 1969).
  5. ^ Фредериксон, Грег Н .; Линч, Нэнси А. (1984), «Влияние синхронного общения на проблему выбора лидера в ринге» (PDF), Материалы шестнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '84), стр. 493–503, Дои:10.1145/800057.808719, ISBN  978-0897911337.
  6. ^ Мерфи, Скотт (2020), «Общий ритм как дискретная производная от его счетчика общего времени» (PDF), MusMat: Бразильский музыкально-математический журнал, 4, стр. 1–11.
  7. ^ а б Карп, Алан Х. (1996), "Смена битов на однопроцессорах", SIAM Обзор, 38 (1): 1–26, CiteSeerX  10.1.1.24.2913, Дои:10.1137/1038001, МИСТЕР  1379039. Карп изучает и сравнивает 30 различных алгоритмов инвертирования битов, разработанных в период с 1965 по 1996 год, когда был опубликован его обзор.
  8. ^ а б Картер, Ларри; Гатлин, Кан Су (1998), "На пути к оптимальной программе перестановки с обращением битов", Материалы 39-го ежегодного симпозиума по основам информатики (FOCS), стр. 544–553, CiteSeerX  10.1.1.46.9319, Дои:10.1109 / SFCS.1998.743505, ISBN  978-0-8186-9172-0.
  9. ^ Чон, Чечанг; Уильямс, W.J. (1990), "Быстрый рекурсивный алгоритм обращения битов", Международная конференция по акустике, речи и обработке сигналов (ICASSP-90), 3, стр. 1511–1514, Дои:10.1109 / ICASSP.1990.115695.
  10. ^ Harley, T. R .; Махешварамурти, Г. П. (2004), "Генераторы адресов для отображения массивов в обратном порядке битов", Транзакции IEEE при обработке сигналов, 52 (6): 1693–1703, Дои:10.1109 / TSP.2004.827148.