비트역순열

Bit-reversal permutation
Hammersley 집합의 좌표는 0부터 255까지의 정수 및 비트역전

응용수학에서 비트역순열은 n개 항목의 순서를 순열하는 것으로 여기서 n = 2는k 2의 검정력이다. 이 값은 0부터 n - 1까지의 숫자로 시퀀스 요소를 인덱싱한 다음 이들 각 숫자의 이진 표현을 반대로 하여 정의된다(이진수 각각에 길이가 정확히 k가 되도록 패딩 처리). 그런 다음 각 항목은 이 역가치에 의해 주어진 새로운 위치에 매핑된다. 비트 역순열은 비자발적이므로 같은 순열을 두 번 반복하면 아이템의 원래 순서가 돌아온다.

이 순열은 단순 지수 계산만 수행하는 동안 선형 시간 내 모든 시퀀스에 적용할 수 있다. 저점화 시퀀스의 생성과 빠른 푸리에 변환의 평가에 응용이 가능하다.

예

8자 abcdefgh의 순서를 생각해 보라. 이들의 지수는 이진수 000, 001, 010, 011, 100, 101, 110, 001, 101, 011, 111로 역행하면 000, 100, 010, 110, 001, 101, 011, 111이 된다. 따라서 위치 000의 문자 a는 같은 위치(000)에 매핑되고, 위치 001의 문자 b는 다섯 번째 위치(100의 숫자)에 매핑되며, 새로운 순서에 aecgbfdh를 부여한다. 이 새로운 시퀀스에 동일한 순열을 반복하면 출발 시퀀스로 되돌아간다.

지수 번호를 십진수로 쓰는 것(그러나, 위와 같이, 순열의 경우 더 일반적인 1의 시작보다는 위치 0으로 시작하는 것), 크기 2의k 비트 역순열(k = 0, 1, 2, 3, ...)은 다음과 같다.

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

(OEIS에서 시퀀스 A030109)
이 시퀀스의 각 순열은 이전의 순열, 두 배의 순열, 그리고 각 값이 1씩 증가된 동일한 순열의 두 시퀀스를 연결함으로써 생성될 수 있다. 따라서 예를 들어 길이-4 순열 0 2 1 3을 곱하면 0 4 2 6이 되고, 1을 더하면 1 5 3 7이 되며, 이 두 시퀀스를 연결하면 길이 8 순열 0 4 2 6 1 5 3 7이 된다.

일반화

임의 정수 b > 1에 대해 n = b로m 일반화하는 것은 base-b 자릿수 역전 순열이며, 여기서 각 원소의 지수의 base-b(radix-b) 자릿수를 역전시켜 순열 지수를 얻는다. 임의의 합성 크기에 대한 추가 일반화는 혼합 radix 자릿수 반전이다(순열로 인해 자릿수가 역전되는 혼합 radix로 표현되는 숫자에 의해 시퀀스의 요소가 지수화된다).

지수의 이진 표현 내에서 연속적인 비트 블록의 연속적인 블록을 반전시켜 비트 역순열을 일반화하는 순열은 두 개의 동일한 길이의 데이터 시퀀스를 제자리에 놓는 데 사용할 수 있다.[1]

임의 길이의 순서에 대한 비트 역순열의 두 가지 확장자가 있다. 이러한 확장은 길이가 2의 검정력인 시퀀스의 비트역전과 일치하며, 카츠마르츠 알고리즘의 효율적인 작동을 위해 인접한 항목을 시퀀스로 분리하는 것이 목적이다. 이러한 확장들 중 첫 번째, Efficient Ordering이라고 불리는,[2] 복합적인 숫자로 작동하며, 그것은 그 숫자를 그것의 주요 성분으로 분해하는 것에 기초한다.

EBR(Extended Bit-Reversal)[3]이라고 불리는 두 번째 확장자는 심성이 비트-역전과 비슷하다. 의 배열이 주어진 경우, EBR은 에서 0 …n- 에 있는 숫자의 순열로 배열을 채운다 연속적인 숫자는 순열에서 n/ 위치에 의해 분리된다.

적용들

Radix-2 Cooly는 비트 역전이 가장 중요하다.Tukey FFT 알고리즘은 알고리즘의 재귀적 단계가 제자리에 작동하며 입력 또는 출력의 비트 반전을 의미한다. 유사하게, 혼합-라디ix Cooley-에서 혼합-라디ix 자릿수 역전이 발생한다.Tukey FFTs.[4]

비트 역행 순열은 분산 계산의 하한을 고안하는 데도 사용되었다.[5]

반데르 코퍼트 시퀀스(Van der Corput sequence)는 단위 간격의 숫자가 낮은 순서에 따라 비트 역순열의 지수를 이차적 합리수의 고정점 이진법으로 재해석하여 형성된다.

비트 역순열은 동적 데이터 구조에서 하한을 찾는 데 종종 사용된다. 예를 들어, 특정 가정에 따라, 해당 값을 포함하는 이진 검색 에서 0{\ 과n - 사이의 정수를 조회하는 비용은 해당 숫자가 비트 역순으로 쿼리될 때 이다. 이 바운드는 접근 사이에 노드를 재배열할 수 있는 splay 트리 같은 트리에도 적용된다. [6]

알고리즘

주로 빠른 푸리에 변환 알고리즘의 중요성 때문에, 비트 역순열을 시퀀스에 적용하기 위한 수많은 효율적인 알고리즘이 고안되었다.[7]

비트역순열은 비자발적이기 때문에 요소 쌍을 교환하여 (데이터를 다른 배열로 복사하지 않고) 제자리에 쉽게 수행될 수 있다. 알고리즘 분석에 일반적으로 사용되는 랜덤 액세스 머신에서, 검색이 더 큰 반전이 많은 인덱스와 마주칠 때마다 입력 순서에 따라 인덱스를 스캔하고 스왑하는 간단한 알고리즘은 데이터 이동의 선형 수를 수행하게 된다.[8] 그러나 각 지수의 역전을 계산하는 것은 일정하지 않은 수의 단계를 취할 수 있다. 대체 알고리즘은 단순 지수 계산만 사용하면서 선형 시간 내에 비트 역전 순열을 수행할 수 있다.[9]

이러한 알고리즘의 성능에 더욱 중요한 또 다른 고려사항은 메모리 계층이 실행 시간에 미치는 영향이다. 이러한 효과 때문에 메모리의 블록 구조를 고려하는 보다 정교한 알고리즘이 이 순진한 스캔보다 빠를 수 있다.[7][8] 이러한 기법의 대안은 메모리에 정상 순서와 비트 역순으로 모두 접근할 수 있는 특수한 컴퓨터 하드웨어다.[10]

참조

  1. ^ Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013), "In-place permuting and perfect shuffling using involutions", Information Processing Letters, 113 (10–11): 386–391, doi:10.1016/j.ipl.2013.02.017, MR 3037467.
  2. ^ Herman, Gabor T. (2009). Fundamentals of Computerized Tomography (2nd ed.). London: Springer. p. 209. ISBN 978-1-85233-617-2.
  3. ^ Gordon, Dan (June 2017). "A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates". Numerical Algorithms. 77 (4): 1141–1157. doi:10.1007/s11075-017-0356-3.
  4. ^ B. Gold 및 C. M. Rader, 신호의 디지털 처리(뉴욕: McGraw-Hill, 1969).
  5. ^ Frederickson, Greg N.; Lynch, Nancy A. (1984), "The impact of synchronous communication on the problem of electing a leader in a ring" (PDF), Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84), pp. 493–503, doi:10.1145/800057.808719, ISBN 978-0897911337.
  6. ^ Wilber, Robert (1989), "Lower Bounds for Accessing Binary Search Trees With Rotations", 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pp. 61–70, doi:10.1109/SFCS.1986.28, ISBN 0-8186-0740-8.
  7. ^ a b Karp는 그의 조사의 1965년과 1996년 사이에 개발된 비트 반전을 위한 30개의 다른 알고리즘을 조사하고 비교한다Karp, Alan H. (1996), "Bit reversal on uniprocessors", SIAM Review, 38 (1): 1–26, CiteSeerX 10.1.1.24.2913, doi:10.1137/1038001, MR 1379039.
  8. ^ a b Carter, Larry; Gatlin, Kang Su (1998), "Towards an optimal bit-reversal permutation program", Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 544–553, CiteSeerX 10.1.1.46.9319, doi:10.1109/SFCS.1998.743505, ISBN 978-0-8186-9172-0.
  9. ^ Jeong, Jechang; Williams, W.J. (1990), "A fast recursive bit-reversal algorithm", International Conference on Acoustics, Speech, and Signal Processing (ICASSP-90), vol. 3, pp. 1511–1514, doi:10.1109/ICASSP.1990.115695.
  10. ^ Harley, T. R.; Maheshwaramurthy, G. P. (2004), "Address generators for mapping arrays in bit-reversed order", IEEE Transactions on Signal Processing, 52 (6): 1693–1703, doi:10.1109/TSP.2004.827148.