Ik ben me wat aan het voorbereiden op een tentamen Computer Organisation, maar heb even geen idee wat ze hier nou precies doen bij aantonen van correctness van het Booth algoritme voor negatieve multipliers:
Code:
To demonstrate the correctness of the Booth algortihm for negative multipliers,
we use the following property of negative-number representations in the
2's complement system: Let the leftmost 0 of a negative number, X,
be at bit position k, that is,
X = 11...10x(k-1)...x(0)
[B]Then the value of X is given by
V(X) = -2^(k+1) + x(k-1) * 2^(k-1) + ... + x(0) * 2^0.
The correctness of this expression for V(X) is shown by observing that if X is
formed as the sum of two numbers
11...100000...0
+ 00...00x(k-1)..x(0)
--------------------
X = 11...10x(k-1)...x(0)
then the top number is the 2's complement representation of -2^(k+1).[/B]
The recoded multiplier now consists of the part corresponding to the
second number, with -1 added in position k+1.
Waarom gebruiken ze die -2^(k+1)?
Matrix zal het vast wel kunnen uitleggen.
Edit: Volgens mij heb ik het al door. X is duidelijk met de 0 op plaats k. Je zou X dan kunnen krijgen door twee getallen op te tellen (-32 + 2 geeft bijvoorbeeld de multiplier 30). Het bovenste getal is inderdaad de negatie van 2^(k+1) in 2's complement met sign extension. En dan laten ze dus zien dat het inderdaad correct is dat deze twee getallen bij elkaar opgeteld weer de multiplier X geven. Dus nu kan je de multiplier in Booth's ook schrijven met een -1 op de plek k+1 en enen op de plekken waar het tweede getal enen heeft staan. Dit laatste klinkt wat vaag, maar degene die bekend is met Booth's zal het wel begrijpen.
Am I right or am I right?