Abstract:
A method of compressing an integer multiplication table including the steps of first eliminating one of the two symmetrical and identical sections in the table, eliminating the products of 0 multiplier and 0 multiplicand, moving the product of the multiplier having an index of n into the location of index (n-1) for the multiplier, using one-half of the number of the largest multiplier as the largest multiplier index for the compressed multiplication table, moving into the non-continuous memory space of the compressed multiplication table by a page-filling method the product of the largest multiplier index value that is larger than the compressed multiplication table such that the multiplication table after compression can be stored on the same page.

Description:
FIELD OF THE INVENTION 
     The present invention generally relates to a method and apparatus for the compression of an integer multiplication table and more particularly, relates to a method and apparatus for the compression of an integer multiplication table by utilizing a lookup table method to simplify the computational procedure of an integer multiplication method. 
     BACKGROUND OF THE INVENTION 
     In a conventional multiplication method executed by a microprocessor, the multiplication method is carried out by a software only method, a hardware only method, or a software/hardware simultaneous processing method. In a conventional microprocessor that does not have hardware multiplication instructions, a multiplication is performed by either a long multiplication method or by a direct table lookup method. The long multiplication method employed is similar to that normally performed manually and therefore, it has the drawback of a slow computational speed. For instance, in the example of a binary multiplication method, a long multiplication method is carried out by the following steps: ##EQU1## 
     Wherein the bits of the multiplicand are X 1  and X 0 , and the bits of the multiplier are Y 1  and Y 0 . The first step calculation is (X 1  X 0  *Y 0 ). The second step of the calculation is (X 1  X 0  *Y 1 ). The final product is the sum of the above two partial products. When both bits are 1, the product is 1. When one of the bit is 0, the product is 0. 
     The procedure can be further illustrated by the binary multiplication method of (7*2) shown below: ##EQU2## 
     Wherein the required number of the partial products equals to the number of bits of the multiplier. The values of the partial products need to be stored in a temporary memory device. 
     The advantage of a binary long multiplication method is that it can be expressed in a simple and clear manner. However, to implement the long multiplication method by a hardware, the circuit required is very complicated which leads to low operational efficiency. Moreover, when a large multiplier is used, its operational speed decreases. For instance, in the calculation of two binary numbers, four partial products are required. In the calculation of two 4-bits numbers, then 16 partial products are necessary. It is therefore obvious that the binary long multiplication method can not be efficiently executed. Other drawbacks of the binary long multiplication method are the large memory space required, the long execution cycle time used, and the high cost. Since the product of each digit in the multiplication of a multiplicand and a multiplier needs to be stored individually such that the final product can be calculated, very large memory space is required. Furthermore, since each bit of the multiplicand and the multiplier must be multiplied, the number of multiplication required is proportional to the number of bits of the multiplier. The larger the multiplier, the longer the execution cycle time. The large memory space occupied by the partial products and the complex execution procedures required also lead to the necessity of a high cost microprocessor. 
     In order to overcome the drawbacks and the shortcomings of the binary long multiplication method, others have attempted to simplify the computational procedure by using a lookup table method. A lookup table is a multiplication table by using the multipliers and the multiplicands as the indices. The multiplication table can be stored in a read only memory (ROM) to facilitate usage. The lookup table method, even though enables a quick result to be found, is only applicable for small multiplication tables. When large multiplication tables are involved, the method requires a large memory space and a long retrieval time, and frequently encounters memory page-skipping problems. It is therefore desirable, in order to increase the computational speed and to save the memory space, to perform a multiplication by a simplified and efficient method. 
     It is therefore an object of the present invention to provide a method and apparatus for the compression of an integer multiplication table that does not have the drawbacks and shortcomings of the prior art methods. 
     It is another object of the present invention to provide a method and apparatus for the compression of an integer multiplication table that is capable of saving half of the memory space that is normally required. 
     It is a further object of the present invention to provide a method and apparatus for the compression of an integer multiplication table that eliminates the memory page-skipping problems. 
     It is another further object of the present invention to provide a method and apparatus for the compression of an integer multiplication table where data can be easily retrieved from a compressed table. 
     It is yet another object of the present invention to provide a method and apparatus for the compression of an integer multiplication table that utilizes a lookup table method to simplify the computational procedure of the multiplication of integers. 
     It is still another object of the present invention to provide a method and apparatus for the compression of an integer multiplication table that is capable of improved computational speed. 
     SUMMARY OF THE INVENTION 
     In accordance with the present invention, a method and apparatus for the compression of an integer multiplication table is provided. 
     The present invention multiplication table compression method includes the steps of first eliminating one of the two symmetrical and identical sections in the multiplication table; eliminating the products of 0 multiplier and 0 multiplicand; moving the product of the multiplier having an index of n into the location of index (n-1) for the multiplier (n is a natural number); using 1/2 of the number of the largest multiplier as the largest multiplier index for the compressed multiplication table; moving into the non-continuous memory space of the compressed multiplication table by a page-filling method the product of the largest multiplier index value that is larger than the compressed multiplication table such that the multiplication table after compression can be stored on the same page. 
     The present invention is further directed to an apparatus for looking up a multiplication table to retrieve data stored in the compressed multiplication table. The apparatus includes a sequencing device for accepting multiplier and multiplicand as input values and then place them in sequence such that the multiplicand is always larger than the multiplier; an arbiter for determining whether the multiplier is 0 and setting the product to 0 when the multiplier is 0; a highest bit checking device for determining whether the highest bit of the multiplier is 1 or 0, and then outputting the result of the determination to an address converter; an address converter for calculating a new index value and then converting the multiplicand to a first index value, the multiplier into a second index value in order to retrieve from the compressed multiplication table. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Other objects, features and advantages of the present invention will become apparent upon consideration of the specification and the appended drawings, in which: 
     FIG. 1a is a prior art 4-bit*4-bit multiplication table. 
     FIG. 1b is a 4-bit*4-bit multiplication table wherein the identical and symmetrical portions are eliminated. 
     FIG. 1c is a 4-bit*4-bit multiplication table with the portions where the product is 0 and where the products are from a multiplier larger than 8 eliminated. 
     FIG. 1d is a compressed 4-bit*4-bit multiplication table wherein the products of multipliers larger than 8 are moved into the blank space shown in the table of FIG. 1c. 
     FIG. 2 is a flow chart of the method for setting up a compressed multiplication table. 
     FIG. 3 is a flow chart for the process of retrieving data from the compressed multiplication table. 
     FIG. 4 is a functional block diagram of the present invention method. 
     FIG. 5 is the circuit for the sequencing device of FIG. 4. 
     FIG. 6 is the logic circuit for the first index generating device shown in FIG. 4. 
     FIG. 7 is the logic circuit for the second index generating device shown in FIG. 4. 
     FIG. 8 is the logic circuit for the OR gate of FIG. 4. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Referring initially to FIGS. 1b through 1d where the present invention method of compressing a multiplication table is shown. FIG. 1a shows a prior art 4-bit*4-bit integer multiplication table before compression, where X represents the multiplicand index and Y represents the multiplier index. 
     FIG. 1b shows the table of FIG. 1a with its identical and symmetrical products removed. Based on the commutative property law of multiplication, i.e. A*B=B*A, the products shown in FIG. 1a are presented in a symmetrical and identical manner along the diagonal line. It is therefore possible to obtain the correct products after the elimination of half the product values in the multiplication table by exchanging the multiplier and the multiplicand whenever the multiplier is larger than the multiplicand. 
     FIG. 1c shows the multiplication table of FIG. 1b with the elimination of all the products of multipliers that are or equal to than 8. The compressed multiplication table shown in FIG. 1c has eliminated the products shown in FIG. 1b that are from multipliers larger than 8, in order to fill in the blanks in the table of FIG. 1c to achieve the effect of compression, and to eliminate the page-skipping problems. 
     A final compressed multiplication table is shown in FIG. 1d. The products of multipliers larger than 8 shown in FIG. 1b are filled into the blanks in the table of FIG. 1c according to the present invention method such that a completely compressed multiplication table is obtained since 0 times any number becomes 0,it is possible to detect whether a multiplier is 0 before looking up a table so that the products that are 0 are not stored into a multiplication table in order to save space. 
     The steps for filling in the present invention compressed multiplication table is shown in the flow chart of FIG. 2. X is designated as the multiplicand and Y is designated as the multiplier. Starting at the (1,0) position of the multiplication table shown in FIG. 1d to fill in the product values by the following steps: 
     201: Set X=1, Y=1; 
     202: Obtain the product of X*Y=T; 
     203: Test if Y is larger or equal to 8, if yes, execute 205; if no, execute 204; 
     204: Store Y-1 into Y&#39;, X value is not changed and is stored into X&#39;, execute 206; 
     205: Store the inverse value X of X into X&#39;, the inverse value Y of Y into Y&#39;; 
     206: Store the product T into the (Y&#39;, X&#39;) location in the compressed multiplication table; 
     207: Compare X and Y, if X=Y, execute 209; otherwise execute 208; 
     208: Set Y=Y+1, execute 202; 
     209: Set X=X+1, set Y=1; 
     210: Test whether X is 16, if yes, execute 211; if no, execute 202; 
     211: End page-filling. 
     A method of retrieving data from the above compressed multiplication table is shown in the flow chart of FIG. 3. Using X*Y as an example, the retrieving steps are as follows: 
     301: Set X as the first value, Y as the second value; 
     302: Determine if X is larger than or equal to Y, if yes, execute 303; if no, execute 304; 
     303: If X is larger than Y, set the index address as (X, Y), execute 305; 
     304: If X is smaller than Y, exchange X and Y, set the index address as (Y, X); 
     305: Set the index address after the comparison as (X 1 , Y 1 ); 
     306: Check if Y 1  is 0, if yes, execute 307; if no, execute 308; 
     307: Output 0, execute 311; 
     308: Check if Y 1  is larger or equal to (Z+1)/2 where Z is the largest multiplicand, if yes, execute 309; if no, execute 310; 
     309: Set the index address for looking up the table as (X 1 , Y 1 ), lookup the table with this address, execute 311; 
     310: Set the index address for looking up the table as (X 1 , Y 1  -1), use this address to lookup the table, execute 311; 
     311: Output the result from looking up the table, or 0. 
     The above table lookup method can be carried out by the present invention multiplication table lookup apparatus. The apparatus includes a sequencing device for inputting multipliers and multiplicands and arrange them in a sequence such that the multiplicand is always larger than the multiplier. The sequencing device is used to execute the above table lookup step 301 through step 305. 
     The present invention multiplication table lookup apparatus further includes an arbiter for determining whether the multiplier is 0. When the multiplier is 0, then the product must also be 0. Since the data has been processed by the sequencing device and the multiplier and the multiplicand have been resequenced, the multiplier must be smaller than the multiplicand. The arbiter, therefore, only requires to examine the multiplier and not the multiplicand. The function of the arbiter is to further save the memory space in a multiplication table. Since 0 times any number equals to 0, it only requires to determine whether the multiplier is 0 to know whether the product is 0. There is no need to store the 0 product into the multiplication table. The arbiter is used to execute the table lookup steps 306 and 307. 
     The present invention multiplication table lookup apparatus further includes a highest bit checking device. The checking device is used to determine whether the highest bit of the multiplier is 1 or 0, and then output the result of the determination to an address converter. When the multiplier is a 4-bit number, it minus one to become a 3-bit number which is the largest multiplier after compression. Since the largest number that is represented by a 3-bit number is 7, by determining whether the highest bit of the multiplier is 1 or 0, it can be decided whether its value is larger or equal to 8. The highest bit checking device is used to execute the table lookup step 308 to determine whether the multiplier is larger or equal to (Z+1)/2 where Z is the largest multiplicand. When the highest bit of the multiplier is 1, it indicates that the multiplier is larger or equal to (Z+1)/2. When the highest bit of the multiplier is 0, it indicates that the multiplier is smaller than (Z+1)/2. 
     The present invention multiplication table lookup apparatus further includes an address converter. The address converter is used to calculate a new index value and then convert the multiplicand into a first index value, the multiplier into a second index value in order to retrieve data from the compressed multiplication table. The converting device is used to execute the table lookup steps 309 through 310 as shown in FIG. 4. The address converting device 419 includes a first EXCLUSIVE OR gate 410, a second EXCLUSIVE OR gate 412, an inverter 413, and a subtractor 414. The address index X 1  and the output from the highest bit checking device 409 are inputted into the first EXCLUSIVE OR gate 410 in order to produce a first index value X 2 . The address index Y 1  and the output from the highest bit checking device 409 are inputted into the second EXCLUSIVE OR gate 412 and the inverter 413, and then through the subtractor 414 to subtract 1 in order to obtain the second index value Y 2 . 
     The relationship between (X 2 , Y 2 ) and (X 1 , Y 1 ) is shown in FIG. 3. When Y 1  ≧(Z+1)/2, or when the highest bit of Y 1  is 1 and the output from the highest bit checking device 409 is 1, X 2  =X 1 , Y 2  =Y 1 . When Y&lt;(Z+1)/2, or when the highest bit of Y 1  is 0 and the output from the highest bit checking device 409 is 0, X 2  =X 1 , Y 2  =Y 1  -1; the index of (X 2 , Y 2 ) is inputted into a read only memory 415 for looking up the table. The apparatus is used to execute the table lookup steps 308 through 310. 
     FIG. 4 shows a functional block diagram for the present invention. The first value X is inputted from input passage 401 and the second value Y is inputted from input passage 402 into a sequencing device 418. The sequencing device 418 includes a comparator 405 and an address exchanging device 417. Through passageways 403 and 404, the first value X and the second value Y are inputted into the comparator 405. The result of comparison between X and Y is then outputted from 406 to control the exchanger 417 and to determine whether the output connection for the first value X and the second value Y should be exchanged. After a comparison between X and Y is made by the comparator 405, if it is discovered that X≧Y, then select an output passage b 1 , or connecting the first value X from line 401 to line 407 and the second value Y from line 402 to line 408. If after comparison between X and Y by the comparator 405, it is discovered that X&lt;Y, then select the output passage b 2  to connect the first value X from line 401 to line 408 and the second value Y from line 402 to line 407 in order to achieve the exchange of the passage connection. The data on passage 407 is the first value X 1 , the data on passage 408 is the second value Y 1 . 
     The first value X 1 , the second value Y 1 , and the output from the highest bit checking device 409 are inputted into an address converting device 419 to calculate a new index value. The address converting device 419 includes a first index generator 410 and a second index generator 411. The second index generator 411 is constructed by a second EXCLUSIVE OR gate 412, an inverter 413, and a subtractor 414. The first value X 1  and the output from the highest bit checking device 409 are inputted into the first index generator 410 to produce the first index X 2 . The address index Y 1  and the output from the highest bit checking device 409 are inputted into a second EXCLUSIVE OR gate 412 and an inverter 413. 
     The arbiter 416 determines whether Y 1  is 0. When Y 1  is 0, then output a &#34;0&#34; bit. If Y 1  is not 0, then output a &#34;1&#34; bit. AND gate 421 is used to perform an &#34;AND&#34; logic calculation between the temporary product and the output from the arbiter 416 in order to output the product of the first value X and the second value Y. 
     FIG. 5 is a circuit for the sequencing device shown in FIG. 4. Passage 401, passage 402 and passage 407 are controlled through a switch to select an output of either b 1  or b 2 . 
     FIG. 6 shows that when the first value X and the second value Y shown in FIG. 4 are each a 4-bit number, the first EXCLUSIVE OR gate 410 executes and generates a first index value X 2  from a first value X 1 . Through the first EXCLUSIVE OR gate 410 of FIG. 6, when the highest bit of Y 1  is 1, which indicates Y 1 ≧(15+1)/2, or Y 1  ≧8 which obtains X 2  as X . 1 . When the highest bit of Y 1  is 0 which indicates Y 1  &lt;(15+1)/2, or Y 1  &lt;8 to obtain X2 which is X1. 
     When the first value X and the second value Y shown in FIG. 4 are each a 4-bit number, FIG. 7 shows that the second EXCLUSIVE OR gate 412, the inverter 413, and the subtractor 414 through the operation of minus 1 are used to obtain the second index value Y 2 . When the highest bit of Y 1  is 1, which indicates Y 1 ≧(15+1)/2 or Y 1  &lt;8 to obtain Y 2  as Y. When the highest bit of Y 1  is 0, which indicates Y 1&lt; (15+1)/2, or Y 1  &lt;8 to obtain Y 2  as Y 1  -1. When the highest bit of Y 1  is 0, through the inverter 413 to make the subtractor 414 to execute a minus 1 operation. When the highest bit of Y 1  is 1, through the inverter 413 to stop the subtractor 414 from action. 
     When the first value X and the second value Y of FIG. 4 are each a 4-bit number, FIG. 8 shows that an arbiter 416 executes to determine if Y 1  is 0. Through the arbiter 416, if Y 1  is 0, then output &#34;0&#34; to AND gate 417 to make the output of AND gate 417 0. When Y 1  is not 0, then output &#34;1&#34; to the AND gate 417 to make the AND gate to temporarily set a product output as the product of the first value X and the second value Y. 
     While the present invention has been described in an illustrative manner, it should be understood that the technology used is intended to be in a nature of words of description rather than of limitation. 
     Furthermore, while the present invention has been described in terms of a preferred embodiment thereof, it is to be appreciated that those skilled in the art will ratherly apply these teachings to other possible variations of the invention. 
     The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows: