page_439

< previous page

page_439

Page 439



		relatively straightforward to determine:



		(Address mod 2ⁿ) mod (2^k + 1).



		This allows distribution of addresses across an odd number of modules (and in the case of k = 2 and 4, a prime number, 5 and 17).



		This translation consists of initially decomposing the mod 2ⁿ address into p digits, each of k bits. Thus,



		X_n_-1 X₀ mod 2ⁿ = Y_p_-12^(p-1)k + + Y₂2^2k + Y₁2^k + Y₀,



		where each Y_i is a k-bit grouping of binary bits X.



		Now observe that Y₀ = X_k_-1 X₀, and



		2^k mod (2^k + 1) = -1 mod (2^k + 1)



		and



		2^2k mod (2^k + 1) = +1 mos (2^k + 1),



		since 2^2k = 2^k..2^k, or 2^2k mod (2^k+1) = 2^k mod (2^k+1)..2^k mod (2^k+1) = (-1)(-1) = +1.



		Finally,



		Y_i2^ik mod (2^k = Y_i(±1) (-1 if i is odd, +1 if i is zero or even).



		Thus,



		X_n_-1 X₀ mod (2^k + 1)



		=



		Y_p_-1 Y₀ mod (2^k + 1)



		=



		( + Y₄ - Y₃ + Y₂ - Y₁ + Y₀) mod (2^k + 1).



		The pairwise differences can be computed using mod 2^k arithmetic with sign extension. The results are summed mod 2^k with end-around borrow, since if (X_i + Y_j) < 2^k + 1:



		(X_i mod 2^k + Y_j mod 2^k + 1) = (X_i + Y_j) mod (2^k + 1).



		If X_i + Y_j = 2^k, then X_i + Y_j = -1 mod (2^k + 1), since 10000 with end-around borrow is 0000 - 1 = -1.



		If X_i + Y_j = 2^k +1, then X_i + Y_j = 0, since 10001 with end-around borrow becomes 0001 - 1 = 0.



		EXAMPLE 7.1



		k = 4, 2^k + 1 = 17.



		Consider a 24-bit mod 2²⁴ address:

d₅

d₄

d₃

d₂

d₁

d₀

6 hex digits

< previous page

page_439