Patent ID: 7191203

Claim:
A method of multiplying a binary multiplier X with a binary multiplicand Y comprising the steps of: (a) creating a copy Z of multiplier X; (b) reading the least significant pair of bits of X; (c) if the most recently read pair of multiplier bits X i+1 X i is equal to 11, adding 1 to Z i+2 ; (d) if more than three bits remain unread in multiplier X, reading the next two bits of X and returning to step (c); (e) otherwise, encoding the remaining unread bits of multiplier X; (f) multiplying Z and Y, to create a product X·Y; and (g) generating an electrical signal that represents the product. wherein step (e) comprises the steps of: (i) if there are two remaining unread bits in X, performing a one bit sign extension, to produce a third unread bit; (ii) if the most significant unread bit X MSB equals 0, then performing the following: (A) reading X MSB-1 X MSB-2 ; (B) looking up an addition value, corresponding to X MSB-1 X MSB-2 , in the following table: X MSB−1 X MSB−2 Addition value 00 0 01 Y/2 10 Y 11 3Y/2 (C) looking up Z MSB Z MSB-1 Z MSB-2 corresponding to the addition value in the following table: Z MSB Z MSB−1 Z MSB−2 Addition value 000 Y 001 3Y/2 010 2Y 011 Y/2 100 −Y 101 −Y/2 110 0 111 −3Y/2 and (D) writing Z MSB Z MSB-1 Z MSB-2 to Z; (iii) otherwise, performing the following: (A) forming the two's complement of X MSB X MSB-1 X MSB-2 to form complemented X MSB X MSB-1 X MSB-2 ; (B) looking up an addition value, corresponding to the complemented X MSB X MSB-1 X MSB-2 , in the following table: X MSB−1 X MSB−2 Addition value 00 0 01 Y/2 10 Y 11 3Y/2 (C) negating the addition value; (D) if X MSB-3 X MSB-4 equals 11, increasing the negated addition value by Y/2; (E) looking up Z MSB Z MSB-1 Z MSB-2 corresponding to the negated addition value in the following table: Z MSB Z MSB−1 Z MSB−2 Negated addition value 000 Y 001 3Y/2 010 2Y 011 Y/2 100 −Y 101 −Y/2 110 0 111 −3Y/2 and (F) writing Z MSB Z MSB-1 Z MSB-2 to Z.