Table lookup multiplier employing compressed data read only memory

In a digital processing system, a multiplier comprising:

• a first input means for receiving at least one multibit multiplicand digit;
• a second input means for receiving a first multibit multiplier digit;
• a third input means for receiving a second multibit multiplier digit;
• a memory means connected to said first, second and third input means including an array of memory locations disposed in a plurality of rows and a plurality of sets of columns, a row decode means connected to said first input means for selecting a row of said array corresponding to said at least one multiplicand digit, a first column decode means connected to said second input means for selecting a set of columns of said array corresponding to said first multiplier digit, a second column decode means connected to said third input means for selecting a set of columns of said array corresponding to said second multiplier digit, said array having stored at memory locations of said selected row and a selected set of columns bits corresponding to the product digits of said at least one multiplicand digit and respective first and second multiplier digits, said array having less than the total number of memory locations required to specify all bits of said product digits by deletion of any column of memory locations which would be "0" for all rows;
• a first output means connected to said memory means to output the product digits from said memory means for said at least one multiplicand digit and said first multiplier digit input;
• and
• a second output means connected to said memory means to output the product digits from said memory means for said at least one multiplicand digit and said second multiplier digit input.

In a digital processing system, a multiplier comprising:

• a first register means for storing a multiple digit multiplicand;
• a first input means connected to said first register means for receiving a predetermined digit stored in said first register means;
• a plurality of second input means each for receiving one multiplier digit;
• a memory means connected to said first input means and said plurality of second input means including a plurality of arrays of memory locations disposed in a plurality of rows and a plurality of sets of columns, a row decode means connected to said first input means for selecting a row of each of said arrays corresponding to said multiplicand digit, a plurality of column decode means each connected to a corresponding one of said second input means for selecting a set of columns of one of said arrays corresponding to said multiplier digit, each of said arrays having stored at memory locations of said selected row and said selected set of columns bits corresponding to the product digits of said multiplicand digit and said corresponding multiplier digit, said array having less than the total number of memory locations required to specify all bits of said product digits by deletion of any column of memory locations which would be "0" for all rows;
• a plurality of output means each connected to a corresponding array of said memory means to output the product digits from said memory means for said at least one multiplicand digit and said corresponding multiplier digit input;
• a second register means for storing a plurality of digits;
• and
• a control means connected to said first and second register means and said output means for sequentially shifting digits of said first and second register means, thereby sequentially shifting digits of said multiplicand into said first input means, and combining said product digits of said plurality of output means with the previous contents of said second register means.