< previous page	page_440	next page >
Page 440 Then the module address is: [(d4 d5) + (d2 d3) + (d0 d1)] mod 17. Suppose we have (in hex): d5 = F d4 = 3 d3 = 7 d2 = A d1 = 9 d0 = 0, so that 3 - F = -12(-C), A - 7 = 3, 0 9 = -9. For all negative results, we map the result to the resource (i.e., the least positive number that satisfies the congruence). Now consider interleave factors of the form 2k-1. Here, the residue is even easier to compute, since 2nk mod (2k - 1) = 1. So, we merely need to sum up the digits of a number, i.e., EXAMPLE 7.2 In decimal, the procedure for finding the mod residue is called "casting out nines." We find 732089 mod 9 by: 7 + 3 + 2 + 0 + 8 + 0. Note that the 9 is replaced ("cast out") by 0, since 9 mod 9 = 0. Thus, 20 = 2 + 0 = 2. In finding the address of a word in a module, note that 2k ± 1 is always relatively prime to 2n. Now we also know that residues of relatively prime modules are unique up to the product of the moduli (this is the Chinese Remainder theorem). So that an address, represented by the pair (a1, a2) a1 = A mod (2k + 1) and a2 = A mod 2m (2m the size of a memory module) is unique up to (2k + 1)2m, which is simply the size of memory. So all that has to be done is to find A mod (2k + 1) and use it as the module address, then use the low order m bits of A as a word address in a module and we have a unique address pair (a1, a2) that spans the address space of 2k + 1 modules, each containing 2m words.
< previous page	page_440	next page >