Here, I am going to share how multiplication is done inside processor. Due to evolution of human mind, There may be better and different way to do.
Each and every method have some pros and cons, If we choose first it is quite complicated to implement the same in processor as everything in processor is Logic High and Logic Low. For the second one, it take O(multiplier) times and you need to take care in choosing lower value as multiplier. Third method shows multiplication done using Logic High(1’s) and Logic Low(0’s). If you look into third one, every times 1’s and 0’s are multiplied with the multiplicand and shifted left (2 power n) times. Where n is the position of bit used by multiplier.
Below figure, explains how Multiplication is done for two unsigned numbers.
Lets understand the concept first, for example, take 6(0b0110) as multiplicand and 2(0b0010)as multiplier and Initial value of Accumulator and Carry bit are zero.
Step 1:
Check the Last bit of multiplier(i.e. 2) if it is 0 proceed else jump to step 2. Right shift Accumulator, Multiplier and carry in such a way that last bit(LSB) of Accumulator jump to first position(MSB) of Multiplier, Carry bit jump to first position(MSB) of Accumulator and Last bit of Multiplier is left alone. We can also do the same thing using left shift which use additional memory compare to this method.
Count = Count + 1
Accumulator = 0b0000
Multiplier = 0b0001
Step 2:
Now check again the last bit of multiplier if it 1. Add multiplicand with Accumulator and store the result in Accumulator.
Accumulator = 0b0110
After that do the Right shift Accumulator, Multiplier and carry in such a way that last bit(LSB) of Accumulator jump to first position(MSB) of Multiplier, Carry bit jump to first position(MSB) of Accumulator and Last bit of Multiplier is left alone.
Count = Count + 1
Accumulator = 0b0011
Multiplier = 0b0000
Step 3:
Do the Above steps until count reach the size of multiplier.
Count == 4
Accumulator = 0b0000
Multiplier = 0b1100
And the Result will be,
Result = Accumulator(4bit MSB) | Multiplier (4bit LSB).
Result = (0b0000 << 4) | 0b1100 = 0b00001100 = 12.
The above method will not be applicable to solve multiplication of negative number. What we can do is convert both multiplier and multiplicand to positive numbers, perform the multiplication then take 2’s complement of the result.
The above figure is the advance method used for multiplication of two signed or unsigned numbers.
Here, is how the above method multiply two signed/unsigned numbers.
Here is the C source code, for the above algorithm
#define BYTE 8
#define SET_MSB_BIT(x) ((x) << (BYTE -1))
#define TWOS_COMPLEMENT(x) ((~x) + 1)
short multiply(unsigned char multiplicand, unsigned char multiplier) {
unsigned short result = 0;
/*Accumulator, intial value is assigned as zero*/
unsigned char ACC = 0;
unsigned char M = multiplicand;
unsigned char Q = multiplier;
/*Number of bits in a byte*/
unsigned char count = BYTE;
/*Q-1, intial value assigned as zero*/
bool Q_prev = 0;
/*Q 0*/
bool Q_0 = 0;
/*Accumulator MSB bit*/
bool ACC_msb = 0;
do {
Q_0 = Q & 1;
if (Q_0 ^ Q_prev) {
/*Check xor truth table*/
ACC = ACC + (Q_0 ? TWOS_COMPLEMENT(M): M);
}
/*Right shift Q by one*/
Q = Q >> 1;
/*store Q_0 value as Q_prev*/
Q_prev = Q_0;
/*Store MSB bit of ACC*/
ACC_msb = ACC & SET_MSB_BIT(1);
/*Set MSB bit of Q, if ACC LSB bit is set*/
Q |= SET_MSB_BIT(ACC & 1);
/*right shift Accumulator*/
ACC = ACC >> 1;
ACC |= SET_MSB_BIT(ACC_msb);
count--;
} while(count > 0);
result = Q | (ACC << BYTE);
return result;
}
/*example code for division for unsigned number*/
#define SIZE_HWORD (16) /*bits*/
struct division {
unsigned short quotient;
unsigned short reminder;
};
struct division divide(unsigned short divisor, unsigned short dividend) {
struct division result;
unsigned short ACC = 0;
unsigned short M = divisor;
unsigned short Q = dividend;
short count = SIZE_HWORD;
bool Q_0 = 0;
bool Q_msb = 0;
do {
/*Assign Q_0 ,i.e. LSB bit as 1*/
Q_0 = 1;
/*store MSB bit of Q as Q_msb*/
Q_msb = (Q & (1 << (SIZE_HWORD -1)));
/*left shift Acc by 1*/
ACC = ACC << 1;
/*ADD Q_msb to the LSB of ACC*/
ACC |= Q_msb;
/*left shift Q by 1*/
Q = Q << 1;
/*subtract ACC with M*/
ACC -= M;
/*check ACC is negative,
if so revert the value back. ADD zero to Q_0*/
if ((short)ACC < 0) {
ACC += M;
Q_0 = 0;
}
Q |= Q_0;
/*decrement count*/
count--;
} while (count > 0);
result.reminder = ACC;
result.quotient = Q;
return result;
}
Thanks for viewing my blog, please post your comment.
No comments:
Post a Comment