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

прикладной математике перестановка с обращением битов это перестановка последовательности В — $n$ предметы, где $n=2^{k}$ это степень двойки . Он определяется путем индексации элементов последовательности числами из $0$ к $n-1$ , представляющий каждое из этих чисел в его двоичном представлении (дополненном так, чтобы его длина была ровно $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 для перестановки), перестановки с обращением битов на $n=2^{k}$ предметы, для $k=0,1,2,3,\dots$ , являются: ^[1]

$k$	$n=2^{k}$	перестановка
0	1	0
1	2	0 1
2	4	0 2 1 3
3	8	0 4 2 6 1 5 3 7
4	16	0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

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

Обобщения

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

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

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

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

Приложения

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

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

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

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

Алгоритмы

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

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

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

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

Ссылки

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

[1] Слоан, Нью-Джерси (редактор), «Последовательность A030109» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS

[karp-2] Jump up to: ^а ^б ^с ^д Карп, Алан Х. (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 , МР 3037467 , S2CID 14672841 .

[5] Герман, Габор Т. (2009), Основы компьютерной томографии (2-е изд.), Лондон: Springer, стр. 209 , ISBN 978-1-85233-617-2

[6] Гордон, Дэн (июнь 2017 г.), «Подход к дерандомизации для восстановления сигналов с ограниченной полосой пропускания в широком диапазоне частот случайной выборки», Numerical Algorithms , 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, номер домена : 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 .

[cg98-10] Jump up to: ^а ^б Картер, Ларри; Гатлин, Кан Су (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] Чон, Чечанг; Уильямс, WJ (1990), «Быстрый рекурсивный алгоритм реверсирования битов», Международная конференция по акустике, речи и обработке сигналов (ICASSP-90) , том. 3, стр. 1511–1514, номер документа : 10.1109/ICASSP.1990.115695 , S2CID 122373780 .

[12] Харли, ТР; Махешварамурти, 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]