|
|
|
|
|
|
|
Actually, it is not too difficult to compute the quotient of the address divided by 2k + 1. Any number that is b + 1 (b the radix) is represented as 1 .. b + 1 (or 11, in decimal). We are trying to find: |
|
|
|
|
|
|
|
|
where R = N mod 2k + 1. Now we can write |
|
|
|
 |
|
|
|
|
(2k + 1)Q = N - R = N0. |
|
|
|
|
|
|
|
|
Since 2k + 1 = 11 (base 2k), we can write the digits Q = qn-1 q0 and N0 = dn-1 d0. So 11Q = N0 can be written as |
|
|
|
|
|
|
|
|
It is now clear that we can back-solve this for each of: |
|
|
|
|
|
|
|
|
where Ni is the most significant digit and qi-1 the least significant digit. |
|
|
|
|
|
|
|
|
A complementary technique for dispersing addresses is to "hash" the address bits (X). This "hashing" is a strict 1:1 mapping of the bits in X to form a new address X¢ based on simple manipulations of the bits in X. These manipulations usually consist of (Figure 7.16): |
|
|
|
|
|
|
|
|
1. Rearrangement of bits. |
|
|
|
|
|
|
|
|
2. Negation of bit values. |
|
|
|
|
|
|
|
|
3. Exclusive OR of certain bit combinations. |
|
|
|
|
|
