Hashing and serial decoding techniques
A technique for generating a list of all N-bit unsigned binary numbers by starting with an initial number less than some power of 2, successively multiplying the number by that power of 2 and adding the largest non-negative number less than that power of 2 such that the new number is not a duplicate of any of those already generated, and using the resulting lists to generate efficient hashing and serial decoding hardware and software.
1. A method of serially accessing all data locations of a contiguous linear storage array, using a single address, before repeating an access to a data location, the array being of a size equal to a power of two elements, the method comprising:
beginning with a current address of a location in said array, accessing data stored at the location corresponding to said current address;
generating a next address of a location within said array, said generating comprising doubling said current address and inserting a least-order bit of said data into a least-order bit position of a result of doubling the current address to obtain said next address;
setting said current address equal to said next address; and
iterating said accessing, said generating and said setting until all data locations have been accessed.
2. A method as in claim 1 , wherein a portion of the data stored within the array is generated by sorting a backward-rotated list of least-order bits of an ordered list of numbers that cover the address space of said array, wherein said ordered list of numbers is generated by beginning with an initial value and successively choosing a power of 2 times said initial value plus an increment, modulo said size of said array, as a next number, wherein said increment is the largest number less than said power of 2 such that said next number has not already been chosen, and wherein said initial value is any non-negative number less than said power of 2, and wherein said next number replaces said initial value to generate another next number.
3. A method of defining connections in a serial shift register decoder for an array of size equal to a power of 2 elements, said decoder comprised of at least one circular shift register, the method comprising:
generating an ordered list of all numbers between zero and said size minus one, said generating comprising: beginning with an initial value and successively choosing a power of 2 times said initial value plus an increment, modulo said size of said decoder, as a next number, wherein said increment is the largest number less than said power of 2 such that said next number has not already been chosen, and wherein said initial value is any non-negative number less than said power of 2, and wherein said next number replaces said initial value to generate another next number;
defining address connections to bits of said at least one circular shift register according to low-order bits of the numbers of said ordered list; and
accessing said address connections to bits of said at least one circular shift register.