Data reordering memory for use in prime factor transform

Claim 1

Apparatus for writing a set of N data values into memory and then reading the data values out of the memory so as to reorder the data values into N/N i groups, each group consisting of N i data values, where N is the product of a set of prime factors N 1 , N 2 , . . . N L , and N i is one of said prime factors, comprising: a memory having N storage locations for storing N data values, the storage locations being designated by addresses respectively numbered from 1 to N; an address register for providing to the memory the address of a storage location to be accessed; and an address selector circuit, for storing successive values of the address in the address register, comprising a first register for storing a first increment, a second register for storing a second increment, a third register for storing a first quantity equal to the first increment minus N, a fourth register for storing a second quantity equal to the second increment minus N, first adder means for adding the address in said address register to said first increment for N i -1 values in each group of N i data values and for adding the address in said address register to said second increment on the remaining one of the N i values in each group, second adder means for adding the address in said address register to the first quantity for N 1 -1 values in each group and for adding the address in said address register to the second quantity for the remaining one of the N i values in each group, means for selecting a starting address as the first address for said address register, and means for storing in said address register as the next successive address the sum from either the second adder or the first adder, according to whether the sum from the second adder is positive or negative, respectively.