Hashing and serial decoding techniques

• US 8,166,278 B2
• Filed: 10/18/2010
• Issued: 04/24/2012
• Est. Priority Date: 08/23/2005
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Inventors: Cooke, Laurence H.
• Primary Examiner(s): SONG, HUA JASMINE
• Application Number:
  US12/906,285
• Publication Number:
  US 20110035566A1
• Time in Patent Office: 554 Days
• Field of Search: 711216-219, 711/E12.078
• US Class Current: 711/219
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06

Abstract

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.

Claims

1. An apparatus comprising:

a first memory device configured to store an increment array, the increment array comprising one or more bits per array element;

a second memory device configured to store at least 2^N data items, where N is a positive integer;

an address shift register coupled to receive an increment from the first memory device and coupled to provide an address to the second memory device, wherein the increment is coupled to enable insertion of the increment into one or more lowest-order positions of the address shift register; and

a comparison device coupled to the second memory device to compare at least a portion of an output data item from the second memory device corresponding to the address provided by the address shift register with at least a portion of a data item to be located in the second memory device to generate a comparison result,

wherein if the comparison result indicates a difference between the output data item and the data item to be located, the address shift register is shifted with the increment inserted into the one or more lowest-order positions of the address shift register.

2. The apparatus of claim 1, wherein if the comparison result indicates that there is no output data item in the second memory device in a location corresponding to the address provided by the address shift register, the apparatus is controlled to store the data item to be located in the second memory device at the location corresponding to the address provided by the address shift register.

3. The apparatus of claim 1, wherein the first memory device and the second memory device are a single memory device.

4. The apparatus of claim 1, wherein the increment array contains a set of increments generated by generating a non-repeating list of all addresses of locations of the second memory device by doubling a current address, module 2^N, adding the resulting address to the list if it is not already in the list or adding the resulting address minus one to the list if the resulting address is already in the list, and iterating until all addresses are in the list;

and generating either a 0 or 1 increment corresponding to an associated location of the increment array based on which address value was added to the list of addresses.

5. The apparatus of claim 1, wherein an index is generated based on the data item to be located, and wherein the index is loaded into the address shift register as an initial address value.

6. A processor-readable storage medium containing instructions that, upon execution, result in the implementation of operations comprising:

beginning with a current address of a location in a storage array of a size corresponding to a number of elements equal to a power of two, accessing data stored at the location corresponding to a current address;

generating a next address of a location within the storage array, said generating comprising doubling the current address and inserting a least-order bit of the data into a least-order bit position of a result of doubling the current address to obtain the next address;

setting the current address equal to the next address; and

iterating said accessing, said generating and said setting.

7. The storage medium of claim 6, wherein a portion of the data stored within the storage 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 the storage array, wherein the ordered list of numbers is generated by beginning with an initial value and successively choosing a power of two times the initial value plus an increment, modulo the size of the storage array, as a next number, wherein the increment is the largest number less than the power of two such that the next number has not already been chosen, and wherein the initial value is any non-negative number less than the power of two, and wherein the next number replaces the initial value to generate another next number.

8. The storage medium of claim 6, wherein said iterating is performed until all data locations in the storage array have been accessed.

9. A method of serial data access, the method comprising:

beginning with a current address of a location in a contiguous linear storage array of size 2^N for some integer N, accessing data stored at the location in the array corresponding to the current address;

generating a next address of a location within the array, said generating comprising;

setting the next address equal to the current address multiplied by 2^M, where M is a positive integer, and

inserting M bits of the data into M least-order bit positions of the next address; and

iterating said accessing and said generating to serially access data stored in the array.

10. The method of claim 9, 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.