Bit-reversal permutation: Difference between revisions

Revision as of 10:30, 5 January 2024

Latest revision as of 21:21, 22 July 2025

(4 intermediate revisions by 4 users not shown)

Line 30:

==Generalizations==

The generalization to [[radix]] <math>b</math> representations, for <math>b > 2</math>, and to <math>n=b^k</math>, is a '''digit-reversal permutation''', in which the base-<math>b</math> digits of the index of each element are reversed to obtain the permuted index. The same idea can also been generalized to [[mixed radix]] number systems. In such cases, the digit-reversal permutation should simultaneously reversesreverse the digits of each item and the bases of the number system, so that each reversed digit remains within the range defined by its base.<ref>{{citation

| last = Elster | first = Anne C.

| contribution = Fast bit-reversal algorithms

Line 121:

| title = Address generators for mapping arrays in bit-reversed order

| volume = 52

| year = 2004| s2cidbibcode = 100434782004ITSP...52.1693H

| s2cid = 10043478

}}.</ref>

TheSignificant performanceattention improvementhas ofbeen bit-reversalsgiven into bothimproving uniprocessorthe andperformance multiprocessorsof hasbit-reversal beenoperations paidwithin athe seriousfield attention inof high-performance computing fields. BecauseDeveloping architecture-aware algorithmalgorithms developmentis cancrucial bestfor utilizeenabling optimal use of hardware and system software resources, includingsuch as caches, TLBTLBs, and multicores, significantly accelerating themulticore computationprocessors.<ref>{{citation

| last1 = Zhang | first1 = Zhao

| last2 = Zhang | first2 = Xiaodong