# US 2006/0136541 A1 · Binary digit multiplications and applications

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0136541 A1
- Document ID: US20060136541A1
- Status: Published application
- Kind: A1
- Application number: 11/016,544
- Filed: 2004-12-17
- Published: 2006-06-22
- Earliest claimed: 2004-12-17
- Assignees: The Regents of the University of California
- Inventors: Te Hu
- Web page: https://patentgrep.com/patent/US20060136541A1

## CPC

- G06F 7/5332: {by skipping over strings of zeroes or ones, e.g. using the Booth Algorithm}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A multiplying system for binary digits. The digits are multiplied in a rectangular memory array, where the digits are placed along the edges, and intersections between 1's form blocks of 1's in the memory array. The blocks of 1's are evaluated based on a weighting assigned to positions within the memory, either directly, or by reducing each block to a reduced block representation. The system can be used for multiplications, partial multiplications, and divisions, as well as applications thereof.

## Claims

### Claim 1

A method comprising:
multiplying a first binary value by a second binary value and accumulating information indicative of areas of intersections between 1's in said first binary value and 1's in said second binary value; and
evaluating said information indicative of said areas of intersections to determine a value related to said multiplying.

### Claim 2 (depends on 1)

A method as in claim 1, wherein said accumulating information comprises forming a table having areas, said areas being weighted in a way such that areas of intersection between the 1's in said table represent a partial value associated with said intersections between the 1's.

### Claim 3 (depends on 2)

A method as in claim 2, wherein said table is formed in a memory associated with a processor.

### Claim 4 (depends on 2)

A method as in claim 2, further comprising identifying blocks of 1's in said table, and wherein said evaluating comprises evaluating values of the blocks of 1's.

### Claim 5 (depends on 4)

A method as in claim 4, wherein said evaluating comprises reducing the blocks of 1's to a reduced representation indicative of the blocks of 1's.

### Claim 6 (depends on 5)

A method as in claim 5, wherein said reducing comprises reducing the blocks of 1's to a representation where any block of 1's of any size can be represented by four symbols or less.

### Claim 7 (depends on 6)

A method as in claim 6 wherein said reducing comprises reducing a block of 1's with m rows and n columns to a corresponding reduced value proportional to
2m+n−2m−2n+20.

### Claim 8 (depends on 6)

A method as in claim 6, wherein said reducing comprises determining a block of 1's, maintaining a northeast bit of the block of 1's in a same position as a first bit, positionally encoding a southeast bit one bit south of its bit position as a (−1) value as a second bit, positionally encoding a southwest bit into a corresponding 1 bit shifted diagonally one bit south and west as a third bit, and positionally encoding a Northwest bit as a (−1) bit, one bit to the west of its position as a fourth bit, and removing all other bits from said block of 1's, other than said first bit, said second bit, said third bit, and said fourth bit.

### Claim 9 (depends on 1)

A method as in claim 1, further comprising dividing said first value and said second value into multiple separated portions, and carrying out said accumulating and said evaluating of each of said separate portions, separately.

### Claim 10 (depends on 9)

A method as in claim 9, further comprising carrying out said evaluating for each of said multiple separated portions on each of a plurality of separated processing implementers.

### Claim 11 (depends on 9)

A method as in claim 9, wherein said carrying out said evaluating on each of said separate portions comprises evaluating intersections between each of the separate portions, and subsequently weighting values related to the intersections according to values of said separate portions.

### Claim 12 (depends on 9)

A method as in claim 9, further comprising evaluating each of a plurality of separated portions on each of a plurality of separate processing implementers.

### Claim 13 (depends on 12)

A method as in claim 12, wherein said evaluating each of the plurality of separated portions comprises forming a table which is weighted in a way such that intersections between the 1's represent a partial value associated with said intersections between the 1's, and accumulating partial values, to form a partial value related to said separated portions.

### Claim 14 (depends on 13)

A method as in claim 13, wherein said accumulating said partial values comprises reducing said partial values to a representation where at least a plurality of two-dimensional blocks of same value bits are reduced to a reduced representation of four symbols or less.

### Claim 15 (depends on 13)

A method as in claim 13, wherein said evaluating further comprises weighting said partial value according to a position of said partial bits.

### Claim 16 (depends on 6)

A method as in claim 6, wherein said evaluating comprises reducing the blocks of one's to coordinates indicative of specified corners of the blocks.

### Claim 17 (depends on 1)

A method as in claim 1, wherein said evaluating comprises determining a partial result.

### Claim 18 (depends on 17)

A method as in claim 17, wherein said partial result comprises obtaining a more significant part of the result prior to obtaining a less significant part of the result.

### Claim 19 (depends on 1)

A method as in claim 1, wherein said multiplying comprises analyzing said first and second binary values to determine locations of transitions between 0 values and 1 values, and using said locations to form said information.

### Claim 20 (depends on 1)

A method as in claim 1, wherein said multiplying multiplies said first binary digit and said second binary digit by a third binary digit, and accumulating information indicative of interactions between 1's in all of said first, second and third binary digits.

### Claim 21 (depends on 1)

A method as in claim 1, wherein said multiplying determines said information by finding 0's in said first or second binary values, and using areas of 0's to define said areas of intersections between 1's.

### Claim 22 (depends on 1)

A method as in claim 1, further comprising, after said evaluating, using said value to bound an operation related to a division.

### Claim 23

A system comprising:
a memory, having a plurality of memory locations;
a multiplier, that receives a first binary value and a second binary value and accumulates information indicative of areas of intersections between 1's in said first binary value and 1's in said second binary value in said memory and evaluates said information indicative of said areas of intersections to determine a value related to multiplying said first binary value by said second binary value.

### Claim 24 (depends on 23)

A system as in claim 23, wherein said multiplier includes a processor, running according to a stored program.

### Claim 25 (depends on 23)

A system as in claim 23, wherein said multiplier includes hardware logic.

### Claim 26 (depends on 23)

A system as in claim 23, wherein said accumulating information comprises forming a table in said memory having areas, said areas being weighted in a way such that areas of intersection between the 1's in said table represent a partial value associated with said intersections between the 1's.

### Claim 27 (depends on 26)

A system as in claim 26, wherein said multiplier identifies blocks of 1's in said table and evaluates values attributable to the blocks of 1's.

### Claim 28 (depends on 27)

A system as in claim 27, wherein said multiplier reduces at least one of the blocks of 1's to a reduced representation indicative of the blocks of 1's but having fewer symbols that than the original block of 1's.

### Claim 29 (depends on 28)

A system as in claim 28, wherein said multiplier reduces at least a plurality of the blocks of 1's to a representation where any block of 1's of any size can be represented by four symbols or less.

### Claim 30 (depends on 29)

A system as in claim 29, wherein said multiplier reduces said blocks by maintaining a northeast bit of the block of 1's in a same position as a first bit, positionally encoding a southeast bit one bit south of its bit position as a (−1) value as a second bit, positionally encoding a southwest bit into a corresponding 1 bit shifted diagonally one bit south and west as a third bit, and positionally encoding a Northwest bit as a (−1) bit, one bit to the west of its position as a fourth bit, and removing all other bits from said block of 1's, other than said first bit, said second bit, said third bit, and said fourth bit.

### Claim 31 (depends on 23)

A system as in claim 23, wherein said multiplier comprises a plurality of separate processing implementers, each receiving only a part of data comprising said first value and said second value, and each carrying out only a portion of a total computation.

### Claim 32 (depends on 31)

A system as in claim 31, wherein each of said processing implementers evaluates values attributable to intersections between each of the separate portions, and subsequently weights said values according to positions of said separate portions.

### Claim 33 (depends on 28)

A system as in claim 28, wherein said multiplier reduces the blocks of 1's to coordinates indicative of specified corners of the blocks.

### Claim 34 (depends on 23)

A system as in claim 23, wherein said multiplier obtains a partial result attributable to a multiplication between said first binary value and said second binary value.

### Claim 35 (depends on 34)

A system as in claim 34, wherein said partial result comprises obtaining a more significant part of the result prior to obtaining a less significant part of the result.

### Claim 36 (depends on 23)

A system as in claim 23, further comprising an evaluating unit which analyzes said first and second binary values to determine locations of transitions between 0 values and 1 values, and uses said locations to form said information.

### Claim 37 (depends on 23)

A system as in claim 23, wherein said multiplier multiplies said first binary digit and said second binary digit by a third binary digit.

### Claim 38 (depends on 23)

A system as in claim 23, wherein said multiplier uses said value to bound an operation related to a division.

### Claim 39

A computer-readable medium containing a set of instructions for a general purpose computing part, the set of instructions comprising:
Obtaining a first binary value and a second binary value;
accumulating information indicative of areas of intersections between 1's in said first binary value and 1's in said second binary value; and
evaluating said information indicative of said areas of intersections to determine a value related to multiplying of said first binary value by said second binary value.

### Claim 40 (depends on 39)

A medium as in claim 39, wherein said accumulating information comprises forming a table having areas, said areas being weighted in a way such that areas of intersection between the 1's in said table represent a partial value associated with said intersections between the 1's.

### Claim 41 (depends on 40)

A medium as in claim 40, wherein said forming a table, comprises using the computing part to form a table in a memory.

### Claim 42 (depends on 41)

A medium as in claim 41, further comprising identifying blocks of 1's in said table, and wherein said evaluating comprises evaluating values in a final multiplication result that are attributable to the blocks of 1's.

### Claim 43 (depends on 42)

A medium as in claim 42, wherein said evaluating comprises reducing the blocks of 1's to a reduced representation indicative of the blocks of 1's.

### Claim 44 (depends on 43)

A medium as in claim 43, wherein said reducing comprises reducing the blocks of 1's to a representation where any block of 1's of any size can be represented by four symbols or less.

### Claim 45 (depends on 44)

A medium as in claim 44, wherein said reducing comprises determining a block of 1's, maintaining a northeast bit of the block of 1's in a same position as a first bit, positionally encoding a southeast bit one bit south of its bit position as a (−1) value as a second bit, positionally encoding a southwest bit into a corresponding 1 bit shifted diagonally one bit south and west as a third bit, and positionally encoding a Northwest bit as a (−1) bit, one bit to the west of its position as a fourth bit, and removing all other bits from said block of 1's, other than said first bit, said second bit, said third bit, and said fourth bit.

### Claim 46 (depends on 39)

A medium as in claim 39, further comprising dividing said first value and said second value into multiple separated portions, and assigning said accumulating and said evaluating of each of said separate portions, to each of a separate processing implementer, respectively.

### Claim 47 (depends on 39)

A medium as in claim 39, wherein said evaluating comprises determining a partial result.

### Claim 48 (depends on 47)

A medium as in claim 47, wherein said partial result comprises obtaining a more significant part of the result prior to obtaining a less significant part of the result.

### Claim 49 (depends on 39)

A medium as in claim 39, further comprising, after said evaluating, using said value to bound an operation related to a division.

### Claim 50 (depends on 49)

A medium as in claim 49, further comprising, using said evaluating for cryptographic evalution.

### Claim 51

A method, comprising:
analyzing a first value and a second value to obtain an interim value with at least one two-dimensional block representing same value bits therein;
reducing at least one of said two-dimensional blocks to a reduced representation which includes four symbols that represent the value attributable to said one two-dimensional block; and
evaluating said reduced representation to determine a result related to a multiplying of said first value by said second value.

### Claim 52 (depends on 51)

A method as in claim 51, wherein said result relating to said multiplying comprises a multiplication result of said first value by said second value.

### Claim 53 (depends on 51)

A method as in claim 51, wherein said result related to said multiplying comprises a partial multiplication result of said first value by said second value.

### Claim 54 (depends on 51)

A method as in claim 51, wherein said result related to said multiplying comprises a partial multiplication result indicative of certain more significant bits only, of a product of said first value multiplied by said second value.

### Claim 55

A system, comprising:
a processor, receiving a first value and a second value, and processing said first and second values to obtain an interim value with at least one two-dimensional block representing same value bits therein, said processory operating to reduce at least one of said two-dimensional blocks to a reduced representation which includes four symbols that represent the value attributable to said one two-dimensional block and evaluating said reduced representation to determine a result related to a multiplying of said first value by said second value.

### Claim 56 (depends on 55)

A system as in claim 55, wherein said processor runs according to a stored program.

### Claim 57 (depends on 55)

A system as in claim 55, wherein said processor includes hardware logic.

### Claim 58 (depends on 55)

A system as in claim 55, wherein said result relating to said multiplying comprises a multiplication result of said first value by said second value.

### Claim 59 (depends on 55)

A system as in claim 55, wherein said result related to said multiplying comprises a partial multiplication result of said first value by said second value.

### Claim 60 (depends on 55)

A system as in claim 55, wherein said result related to said multiplying comprises a partial multiplication result indicative of certain more significant bits only, of a product of said first value multiplied by said second value.

### Claim 61

A method, comprising:
obtaining a first number and a second number to be multiplied; and
accumulating partial results from a multiplying by finding blocks of values at intersections between 1's in the first and second numbers, and accumulating results from said blocks of values, wherein each partial result from each block of values is accumulated separately without carry over from any other block of values.

### Claim 62 (depends on 61)

A method as in claim 61, further comprising reducing said blocks of values into a reduced representation, where said reduced representation includes fewer symbols than a number of symbols in said blocks of values.

### Claim 63 (depends on 61)

A method as in claim 61, wherein said establishing blocks of values comprises establishing information indicative of an intersection between the 1's in the first number and the second number in a rectangular array, establishing a 1 at intersections between said 1's in the first number and 1's in the second number and evaluating each block of 1's at said intersections.

### Claim 64 (depends on 63)

A method as in claim 63, further comprising reducing each of said blocks of 1's into a reduced block of symbols.

### Claim 65 (depends on 61)

A method as in claim 61, wherein said reduced block of symbols comprises four symbols for a two-dimensional block of 1's.

### Claim 66

A method, comprising:
using a computer to multiply a first value having a plurality of bits by a second value having a plurality of bits; and
obtaining a portion of a solution attributable to more significant bits before obtaining another portion of the solution attributable to less significant bits.

### Claim 67 (depends on 66)

A method as in claim 66, wherein said obtaining comprises finding intersections between 1's in said first value and said second value, and evaluating portions of the solution attributable to said 1's.

### Claim 68 (depends on 67)

A method as in claim 67, wherein said obtaining comprises grouping said intersections into blocks of 1's, and evaluating each of the blocks of 1's separately.

### Claim 69 (depends on 68)

A method as in claim 68, wherein said evaluating comprises reducing at least one of said blocks of 1's by maintaining a northeast bit of the block of 1's in a same position as a first bit, positionally encoding a southeast bit one bit south of its bit position as a (−1) value as a second bit, positionally encoding a southwest bit into a corresponding 1 bit shifted diagonally one bit south and west as a third bit, and positionally encoding a Northwest bit as a( −1) bit, one bit to the west of its position as a fourth bit, and removing all other bits from said block of 1's, other than said first bit, said second bit, said third bit, and said fourth bit.

### Claim 70

An apparatus, comprising:
Means for multiplying a first value having a plurality of bits by a second value having a plurality of bits; and
Means for obtaining a portion of a solution attributable to more significant bits before obtaining another portion of the solution attributable to less significant bits.

### Claim 71 (depends on 70)

An apparatus as in claim 70, wherein said obtaining means comprises grouping said intersections into blocks of 1's, and means for evaluating each of the blocks of 1's separately.

### Claim 72 (depends on 70)

An apparatus as in claim 70, wherein said evaluating means comprises reducing at least one of said blocks of 1's by maintaining a northeast bit of the block of 1's in a same position as a first bit, positionally encoding a southeast bit one bit south of its bit position as a (−1) value as a second bit, positionally encoding a southwest bit into a corresponding 1 bit shifted diagonally one bit south and west as a third bit, and positionally encoding a Northwest bit as a (−1) bit, one bit to the west of its position as a fourth bit, and removing all other bits from said block of 1's, other than said first bit, said second bit, said third bit, and said fourth bit.
