Hash-based translation method and apparatus with multiple level collision resolution
US5920900A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Dec 30, 1996 |
| Grant date | Jul 6, 1999 |
| Priority date | — |
| Expiry date | Dec 30, 2016 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L12/46
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A translation is performed by using a programmable hashing technique on an input number to generate a hashed number. A subset of the hashed number bits are used to index a first hash table. In first hash table locations where a hash collision does not occur, the first hash table entry contains an index into an output table which contains the desired translated output number. In first hash table locations where a hash collision occurs, the first hash table entry contains a pointer to a first resolution table area in a second hash table. The first resolution table area contains entries which are indexed by additional bits selected from the hashed number in accordance with a mask field in the first hash table location. If collisions occur in the resolution table a new resolution table is created and the process is repeated. The resolution process thus proceeds in stages until all input numbers have been translated.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.