Перестановка бит-реверса

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

Множество Хаммерсли , координатами которого являются целые числа от 0 до 255 и их битовые инверсии.

В прикладной математике перестановка с обратным битом — это перестановка последовательности элементов , где — степень двойки . Она определяется индексацией элементов последовательности числами от до , представлением каждого из этих чисел его двоичным представлением (дополненным до длины, равной ), и сопоставлением каждого элемента с элементом , представление которого имеет те же биты в обратном порядке. ${\displaystyle n}$ ${\displaystyle n=2^{k}}$ ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle k}$

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

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

Пример

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

Записывая индексные числа в десятичной системе счисления (но, как и выше, начиная с позиции 0, а не с более традиционного начала 1 для перестановки), перестановки с обратным порядком битов для элементов выглядят следующим образом: ^[1] ${\displaystyle n=2^{k}}$ ${\displaystyle k=0,1,2,3,\dots }$

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

Обобщения

Обобщение для представлений с основанием , для и для , является перестановкой с обратным знаком , в которой базовые цифры индекса каждого элемента меняются местами для получения переставленного индекса. Та же идея может быть обобщена и для смешанных систем счисления с основанием. В таких случаях перестановка с обратным знаком должна одновременно менять местами цифры каждого элемента и основания числовой системы, так что каждая перевернутая цифра остается в пределах диапазона, определяемого ее основанием. ^[3] ${\displaystyle b}$ ${\displaystyle b>2}$ ${\displaystyle n=b^{k}}$ ${\displaystyle b}$

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

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

Второе расширение, называемое EBR (extended bit-reversal), по духу похоже на bit-reversal. При наличии массива размером , EBR заполняет массив перестановкой чисел в диапазоне за линейное время. Последовательные числа разделяются в перестановке по крайней мере позициями. ^[6] ${\displaystyle n}$ ${\displaystyle 0\ldots n-1}$ ${\displaystyle \lfloor n/4\rfloor }$

Приложения

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

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

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

Перестановки с обратным битом часто используются для поиска нижних границ динамических структур данных . Например, при определенных допущениях стоимость поиска целых чисел между и включительно в любом бинарном дереве поиска, содержащем эти значения, равна , когда эти числа запрашиваются в обратном порядке битов. Эта граница применима даже к таким деревьям, как раскидистые деревья , которым разрешено переставлять свои узлы между доступами. ^[9] ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle \Omega (n\log n)}$

Алгоритмы

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

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

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

Улучшение производительности инверсий битов как в однопроцессорных, так и в многопроцессорных системах получило серьезное внимание в области высокопроизводительных вычислений. Поскольку разработка алгоритмов с учетом архитектуры может наилучшим образом использовать аппаратные и программные ресурсы системы, включая кэши, TLB и многоядерные процессоры, значительно ускоряя вычисления. ^[13]

Ссылки

1. Слоан, Н. Дж. А. (ред.), «Последовательность A030109», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
2. Карп, Алан Х. (1996), «Реверсирование битов на однопроцессорных системах», SIAM Review , 38 (1): 1–26, CiteSeerX 10.1.1.24.2913 , doi :10.1137/1038001, MR  1379039 Карп рассматривает и сравнивает 30 различных алгоритмов инверсии битов, разработанных в период с 1965 года по публикацию его обзора в 1996 году.
3. Элстер, Энн К. (1989), «Быстрые алгоритмы реверсирования битов», Международная конференция IEEE по акустике, речи и обработке сигналов, ICASSP '89, Глазго, Шотландия, 23-26 мая 1989 г. , стр. 1099–1102, doi :10.1109/ICASSP.1989.266624, S2CID  15028026
4. Ян, Цинсюань; Эллис, Джон; Мамакани, Халег; Раски, Фрэнк (2013), «Перестановка на месте и идеальная перетасовка с использованием инволюций», Information Processing Letters , 113 (10–11): 386–391, arXiv : 1204.1958 , doi : 10.1016/j.ipl.2013.02.017, MR  3037467, S2CID  14672841.
5. Герман, Габор Т. (2009), Основы компьютерной томографии (2-е изд.), Лондон: Springer, стр. 209, ISBN 978-1-85233-617-2
6. Гордон, Дэн (июнь 2017 г.), «Дерандомизационный подход к восстановлению сигналов с ограниченной полосой пропускания в широком диапазоне случайных частот дискретизации», Численные алгоритмы , 77 (4): 1141–1157, doi :10.1007/s11075-017-0356-3, S2CID  254889989
7. Б. Голд и К. М. Рейдер, Цифровая обработка сигналов (Нью-Йорк: McGraw–Hill, 1969).
8. Фредериксон, Грег Н.; Линч, Нэнси А. (1984), «Влияние синхронной коммуникации на проблему выбора лидера в ринге» (PDF) , Труды шестнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '84) , стр. 493–503, doi : 10.1145/800057.808719 , ISBN 978-0897911337.
9. Уилбер, Роберт (1989), «Нижние границы для доступа к двоичным деревьям поиска с поворотами», 27-й ежегодный симпозиум по основам компьютерной науки (sfcs 1986) , стр. 61–70, doi :10.1109/SFCS.1986.28, ISBN 0-8186-0740-8.
10. Картер, Ларри; Гатлин, Кан Су (1998), «На пути к оптимальной программе перестановки битов с обратным порядком следования», Труды 39-го ежегодного симпозиума по основам компьютерной науки (FOCS) , стр. 544–553, CiteSeerX 10.1.1.46.9319 , doi :10.1109/SFCS.1998.743505, ISBN  978-0-8186-9172-0, S2CID  14307262.
11. Jeong, Jechang; Williams, WJ (1990), "Быстрый рекурсивный алгоритм инверсии битов", Международная конференция по акустике, речи и обработке сигналов (ICASSP-90) , т. 3, стр. 1511–1514, doi :10.1109/ICASSP.1990.115695, S2CID  122373780.
12. Harley, TR; Maheshwaramurthy, GP (2004), «Генератор адресов для отображения массивов в обратном порядке битов», IEEE Transactions on Signal Processing , 52 (6): 1693–1703, doi :10.1109/TSP.2004.827148, S2CID  10043478.
13. Чжан, Чжао; Чжан, Сяодун (2000), «Быстрые инверсии битов на однопроцессорных системах и многопроцессорных системах с общей памятью», SIAM Journal on Scientific Computing , 22 (6): 2113–2134, doi :10.1137/S1064827599359709, MR  1856305