Address generators for mapping arrays in bit reversed order

An address pair generator for reordering the elements of a 2{circumflex over ( )}(log2N) length input array in bit reversed order, comprising:

• three sets of array element addresses;
• said first set having a corresponding bit reversed address in said second set, and said third set containing all of the self reversed addresses from said array element addresses;
• advancing through said first set elements to define the first address of each said address pair;
• defining the second address of each said address pair using the appropriate complimentary bit reversed increment;
• and
• a sequence of unique address pairs generated such that no said self-reversed address appears in said sequence.

A method for address pair generation for reordering the elements of a 2{circumflex over ( )}(log2N) length input array in bit reversed order, comprising:

• organizing said array element addresses into three sets, said first set having a corresponding bit reversed address in said second set, and said third set containing all of the self reversed addresses from said array element addresses;
• advancing through each of said first set elements to define the first address of each said address pair;
• defining the second address of each said address pair using the appropriate complimentary bit reversed increment;
• generating a sequence of unique address pairs such that no said self-reversed address appears in said bit reversed address sequence.

A method for address pair generation using out of place bit reversal for reordering the elements of a 2{circumflex over ( )}(log2N) length input array in bit reversed order, comprising:

• removing the start address from the said generated address pair sequence;
• generating self-reversed address pairs with a second address generator;
• and
• transferring data only once for each self reversed address pair.