Permutacja z odwróceniem bitów

Zestaw Hammersleya , którego współrzędnymi są liczby całkowite od 0 do 255 i ich odwrócenie bitów

W matematyce stosowanej permutacja $k}}$ odwróceniem bitów jest permutacją sekwencji elementów , gdzie $\ displaystyle n=2 ^$ { jest potęgą dwójki . Jest $n-1}$ reprezentujących każdą $z$ liczb przez jej reprezentację binarną (wypełnioną, aby miała dokładnie długość $k}$ ${\ displaystyle$ ) i odwzorowanie każdego elementu na element, którego reprezentacja ma te same bity w odwrotnej kolejności.

Dwukrotne powtórzenie tej samej permutacji powoduje powrót do pierwotnego uporządkowania elementów, więc permutacja odwrócenia bitów jest inwolucją .

Tę permutację można zastosować do dowolnej sekwencji w czasie liniowym , wykonując tylko proste obliczenia indeksu. Ma zastosowanie w generowaniu sekwencji o niskiej rozbieżności oraz w ocenie szybkich transformat Fouriera .

Przykład

Rozważ sekwencję ośmiu liter abcdefgh . Ich indeksami są liczby binarne 000, 001, 010, 011, 100, 101, 110 i 111, które po odwróceniu stają się 000, 100, 010, 110, 001, 101, 011 i 111. Tak więc litera a w pozycja 000 jest odwzorowana na tę samą pozycję (000), litera b na pozycji 001 jest odwzorowana na piątą pozycję (tę o numerze 100) itd., dając nową sekwencję aecgbfdh . Powtórzenie tej samej permutacji w tej nowej sekwencji powoduje powrót do sekwencji początkowej.

Zapisywanie numerów indeksów w systemie dziesiętnym (ale, jak powyżej, zaczynając od pozycji 0, a nie od bardziej konwencjonalnego początku 1 dla permutacji), permutacje z odwróceniem bitów na ${\ Displaystyle n = 2 ^ {k}}$ pozycje, dla ${\ Displaystyle k = 0,1,2,3, \ kropki}$ to:

${\ displaystyle k}$	${\ displaystyle n = 2 ^ {k}}$	permutacja
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

Każdą permutację w tej sekwencji można wygenerować przez połączenie dwóch sekwencji liczb: poprzedniej permutacji z podwojonymi wartościami i tej samej sekwencji z każdą wartością zwiększoną o jeden. Tak więc na przykład podwojenie permutacji długości 4 0 2 1 3 daje 0 4 2 6 , dodanie jednego daje 1 5 3 7 , a połączenie tych dwóch sekwencji daje permutację długości 8 0 4 2 6 1 5 3 7 .

Uogólnienia

Uogólnienie na $reprezentacje$ podstawy $,$ dla i $cyfr$ _ _ gdzie podstawowe cyfry indeksu każdego elementu są odwracane w celu uzyskania permutowanego $indeksu$ Ten sam pomysł można również uogólnić na mieszane systemy liczbowe. W takich przypadkach permutacja odwrócenia cyfr powinna jednocześnie odwracać cyfry każdej pozycji i podstawy systemu liczbowego, tak aby każda odwrócona cyfra mieściła się w zakresie określonym przez jej podstawę.

Permutacje, które uogólniają permutację odwrócenia bitów poprzez odwrócenie ciągłych bloków bitów w binarnych reprezentacjach ich indeksów, mogą być użyte do przeplatania dwóch sekwencji danych o równej długości na miejscu.

Istnieją dwa rozszerzenia permutacji z odwróceniem bitów do sekwencji o dowolnej długości. Rozszerzenia te pokrywają się z odwróceniem bitów dla sekwencji, których długość jest potęgą liczby 2, a ich celem jest oddzielenie sąsiednich elementów w sekwencji dla wydajnego działania algorytmu Kaczmarza . Pierwsze z tych rozszerzeń, zwane Efficient Ordering , działa na liczbach złożonych i opiera się na rozkładzie liczby na jej składowe pierwsze.

Drugie rozszerzenie, zwane EBR (Extended Bit-Reversal), jest podobne w duchu do odwrócenia bitów. Mając tablicę o rozmiarze $w$ EBR wypełnia tablicę permutacją liczb z zakresu ${\ displaystyle 0 \ ldots n-1}$ czasie liniowym. Kolejne $są$ oddzielone w permutacji

Aplikacje

Odwrócenie bitów jest najważniejsze dla algorytmów radix-2 Cooley-Tukey FFT , gdzie rekurencyjne etapy algorytmu, działające w miejscu , implikują odwrócenie bitów wejść lub wyjść. Podobnie, odwrócenie cyfr z mieszaną podstawą powstaje w FFT Cooley-Tukey z mieszaną podstawą.

Permutacja odwrócenia bitów została również wykorzystana do opracowania dolnych granic w obliczeniach rozproszonych.

Sekwencja Van der Corputa , sekwencja liczb o niskiej rozbieżności w przedziale jednostkowym , jest tworzona przez reinterpretację indeksów permutacji odwrócenia bitów jako binarnych reprezentacji stałoprzecinkowych diadycznych liczb wymiernych .

Permutacje z odwróceniem bitów są często używane do znajdowania dolnych granic dynamicznych struktur danych . Na przykład, przy pewnych założeniach, koszt wyszukania liczb całkowitych między ${\ displaystyle 0}$ a ${\ displaystyle n-1}$ włącznie, w dowolnym drzewie wyszukiwania binarnego przechowującym te wartości, wynosi ${\ Displaystyle \ Omega (n \ log n)},$ gdy te liczby są sprawdzane w odwróconej kolejności bitów. Ta granica ma zastosowanie nawet do drzew, takich jak drzewa splay , które mogą zmieniać kolejność swoich węzłów między dostępami.

Algorytmy

Głównie ze względu na znaczenie szybkich algorytmów transformaty Fouriera, opracowano wiele wydajnych algorytmów stosowania permutacji z odwróceniem bitów do sekwencji.

Ponieważ permutacja z odwróceniem bitów jest inwolucją, można ją łatwo wykonać w miejscu (bez kopiowania danych do innej tablicy) poprzez zamianę par elementów. W maszynie o swobodnym dostępie, powszechnie używanej w analizie algorytmów, prosty algorytm, który skanuje indeksy w kolejności wejściowej i zamienia je za każdym razem, gdy skanowanie napotka indeks, którego odwrócenie jest większą liczbą, wykonałby liniową liczbę przesunięć danych. Jednak obliczenie odwrócenia każdego indeksu może wymagać niestałej liczby kroków. Alternatywne algorytmy mogą wykonywać permutację odwrócenia bitów w czasie liniowym, używając tylko prostych obliczeń indeksu. Ponieważ permutacje z odwróceniem bitów mogą być powtarzane wiele razy w ramach obliczeń, pomocne może być oddzielenie kroków algorytmu obliczającego dane indeksowe używane do reprezentowania permutacji (na przykład przy użyciu metody podwajania i łączenia) od kroki, które wykorzystują wyniki tych obliczeń do permutacji danych (na przykład poprzez skanowanie indeksów danych w kolejności i wykonywanie zamiany, gdy zamieniona lokalizacja jest większa niż bieżący indeks, lub przy użyciu bardziej wyrafinowanych operacji zbierania i rozpraszania wektorów ) .

Inną kwestią, która jest jeszcze ważniejsza dla wydajności tych algorytmów, jest wpływ hierarchii pamięci na czas działania. Z powodu tego efektu bardziej wyrafinowane algorytmy, które uwzględniają blokową strukturę pamięci, mogą być szybsze niż to naiwne skanowanie. Alternatywą dla tych technik jest specjalny sprzęt komputerowy, który umożliwia dostęp do pamięci zarówno w normalnej, jak i odwróconej kolejności bitów.

Poprawie wydajności odwracania bitów zarówno w procesorach jednoprocesorowych, jak i wieloprocesorowych poświęcono poważną uwagę w dziedzinach obliczeń o wysokiej wydajności. Ponieważ opracowywanie algorytmów uwzględniających architekturę może najlepiej wykorzystać zasoby sprzętu i oprogramowania systemowego, w tym pamięci podręczne, TLB i wielordzeniowość, znacznie przyspieszając obliczenia.

^ Sloane, NJA (red.), „Sekwencja A030109” , The On-Line Encyclopedia of Integer Sequences , Fundacja OEIS
Referencje ^_^_^_^_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Karp bada i porównuje 30 różnych algorytmów odwracania bitów, opracowanych między 1965 a publikacją swojej ankiety w 1996 roku.
^ Elster, Anne C. (1989), „Szybkie algorytmy odwracania bitów”, IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '89, Glasgow, Szkocja, 23-26 maja 1989, s. 1099–1102 , doi : 10.1109/ICASSP.1989.266624
^ Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013), „Permutacja w miejscu i doskonałe tasowanie za pomocą inwolucji” , Information Processing Letters , 113 (10–11): 386–391, doi : 10.1016 / j.ipl.2013.02.017 , MR 3037467 .
^ Herman, Gabor T. (2009), Podstawy tomografii komputerowej (wyd. 2), Londyn: Springer, s. 209 , ISBN 978-1-85233-617-2
Bibliografia _ _ _ _ _ _ _ _
^ B. Gold i CM Rader, Cyfrowe przetwarzanie sygnałów (Nowy Jork: McGraw – Hill, 1969).
^ Frederickson, Greg N.; Lynch, Nancy A. (1984), „Wpływ komunikacji synchronicznej na problem wyboru lidera w ringu” (PDF) , Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84) , s. 493 –503, doi : 10.1145/800057.808719 , ISBN 978-0897911337 .
^ Wilber, Robert (1989), „Dolne granice dostępu do drzew wyszukiwania binarnego z obrotami” , 27. doroczne sympozjum na temat podstaw informatyki (sfcs 1986) , s. 61–70, doi : 10.1109/SFCS.1986.28 , ISBN 0- 8186-0740-8 .
^ ^a ^b Carter, Larry; Gatlin, Kang Su (1998), „W kierunku optymalnego programu permutacji odwrócenia bitów”, Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS) , s. 544–553, CiteSeerX 10.1.1.46.9319 , doi : 10.1109 /SFCS.1998.743505 , ISBN 978-0-8186-9172-0 .
Bibliografia _ Williams, WJ (1990), „Szybki rekurencyjny algorytm odwracania bitów”, International Conference on Acoustics, Speech and Signal Processing (ICASSP-90) , tom. 3, s. 1511–1514, doi : 10.1109/ICASSP.1990.115695 .
Bibliografia _ Maheshwaramurthy, GP (2004), „Generatory adresów do mapowania tablic w odwróconej kolejności bitów”, IEEE Transactions on Signal Processing , 52 (6): 1693–1703, doi : 10.1109/TSP.2004.827148 .
^ Zhao Zhang i Xiaodong Zhang (2001). „Szybkie odwracanie bitów w procesorach jednoprocesorowych i wieloprocesorach z pamięcią współdzieloną” (PDF) . SIAM Journal o obliczeniach naukowych. s. 2113–2134.

[1] Sloane, NJA (red.), „Sekwencja A030109” , The On-Line Encyclopedia of Integer Sequences , Fundacja OEIS

[karp-2] Referencje ^_^_^_^_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Karp bada i porównuje 30 różnych algorytmów odwracania bitów, opracowanych między 1965 a publikacją swojej ankiety w 1996 roku.

[3] Elster, Anne C. (1989), „Szybkie algorytmy odwracania bitów”, IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '89, Glasgow, Szkocja, 23-26 maja 1989, s. 1099–1102 , doi : 10.1109/ICASSP.1989.266624

[4] Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013), „Permutacja w miejscu i doskonałe tasowanie za pomocą inwolucji” , Information Processing Letters , 113 (10–11): 386–391, doi : 10.1016 / j.ipl.2013.02.017 , MR 3037467 .

[5] Herman, Gabor T. (2009), Podstawy tomografii komputerowej (wyd. 2), Londyn: Springer, s. 209 , ISBN 978-1-85233-617-2

[6] Bibliografia _ _ _ _ _ _ _ _

[7] B. Gold i CM Rader, Cyfrowe przetwarzanie sygnałów (Nowy Jork: McGraw – Hill, 1969).

[8] Frederickson, Greg N.; Lynch, Nancy A. (1984), „Wpływ komunikacji synchronicznej na problem wyboru lidera w ringu” (PDF) , Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84) , s. 493 –503, doi : 10.1145/800057.808719 , ISBN 978-0897911337 .

[9] Wilber, Robert (1989), „Dolne granice dostępu do drzew wyszukiwania binarnego z obrotami” , 27. doroczne sympozjum na temat podstaw informatyki (sfcs 1986) , s. 61–70, doi : 10.1109/SFCS.1986.28 , ISBN 0- 8186-0740-8 .

[cg98-10] Carter, Larry; Gatlin, Kang Su (1998), „W kierunku optymalnego programu permutacji odwrócenia bitów”, Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS) , s. 544–553, CiteSeerX 10.1.1.46.9319 , doi : 10.1109 /SFCS.1998.743505 , ISBN 978-0-8186-9172-0 .

[11] Bibliografia _ Williams, WJ (1990), „Szybki rekurencyjny algorytm odwracania bitów”, International Conference on Acoustics, Speech and Signal Processing (ICASSP-90) , tom. 3, s. 1511–1514, doi : 10.1109/ICASSP.1990.115695 .

[12] Bibliografia _ Maheshwaramurthy, GP (2004), „Generatory adresów do mapowania tablic w odwróconej kolejności bitów”, IEEE Transactions on Signal Processing , 52 (6): 1693–1703, doi : 10.1109/TSP.2004.827148 .

[13] Zhao Zhang i Xiaodong Zhang (2001). „Szybkie odwracanie bitów w procesorach jednoprocesorowych i wieloprocesorach z pamięcią współdzieloną” (PDF) . SIAM Journal o obliczeniach naukowych. s. 2113–2134.