TNETX3150A datasheet(40/78 Pages) TI

40 / 78 page

TNETX15AE

ADDRESS-LOOKUP DEVICE

SPWS041A – AUGUST 1997 – REVISED OCTOBER 1997

POST OFFICE BOX 655303

• DALLAS, TEXAS 75265

PRINCIPLES OF OPERATION

lookup algorithm (continued)

Each pointer points to a table in the next level. The TNETX15AE uses N bits in the address as an offset to this

table and, if a valid pointer is found, decode proceeds to the next level. A null pointer indicates that the entry

was not found (in this case the search fails). The width of the memory word (W) must increase as the memory

gets deeper, such that 2N+W – 1

≥ memory size; the memory address of the next pointer is (contents of current

table entry):(next N bits to decode).

a graphical example of the lookup algorithm

This example uses the following method to look up the number 0xB2 (10.11.00.10b), two bits at a time (N = 2).

Graphically, this number is represented in Figure 6.

Figure 6. Example of Lookup-Number Algorithm (Matching 0xB2)

The first table at offset 0x10b points to the second level (see Figure 6). The pointer at the second level (offset

by the second set of bits (0x11b)) points to the third table. This process continues until the last two bits are

matched. Matching 0xB2, two bits at a time, uses four tables, with each containing four possible pointers. Not

all locations in the tables are used, which potentially can lead to unused memory. Now, add 0xB0 (10.11.00.00b)

to the table. Figure 7 illustrates the results.

Figure 7. Example of Lookup-Number Algorithm (Adding 0xB0)

0xB0 follows exactly the same thread as 0xB2 and the only difference between the two is in the last table. 0xB0

matches offset 00b while 0xB2 matches offset 10b. There are now two numbers being represented, but there

are still four tables allocated.

TNETX3150A Datasheet(PDF) 40 Page - Texas Instruments