Main Goal. What we want to accomplish with our approach is to build a planar graph $\mathcal{G}$ that reassembles an $n$-bit multiplier. $\mathcal{G}$ should be build in a way that it has exactly one perfect matching (or some derived graph has a perfect matching) and this perfect matching reveals the factorization of the given product $pq$.
One way to realize multiplication of two $n$-bit numbers $p$ and $q$ in hardware is to build a network of cascading $n^2$ adder gadgets. Such a construction is called an $n$-bit multiplier and has $2\times n$ input nodes that are assigned with the $2\times n$ bits of the two input numbers $p$ and $q$. Consequently, it also has $2\times n$ output nodes that represent the $2\times n$ bits of the final product $pq$. Each of the involved $n^2$ adder gadgets has $4$ input and $4$ output nodes and is illustrated in Figure 1.Figure 1 - An adder gadget with 4 input and 4 output nodes. Two nodes with the same color represent a pair of input and output nodes, i.e., the green $p_i$ in the input area gets the input of the $i$-bit of the input integer $p$ and the green node in the output area simply outputs the same bit and hands it over to the next adder gadget. |
The meaning of the different colors in the figure are:
- GREEN $p_i$: The $i$-th bit of the input integer $p$
- RED $r$: The result output of an previous adder gadget
- YELLOW $q_i$: The $i$-th bit of the input integer $q$
- WHITE $c_{in}$: The carry output of an previous adder gadget.
An $n$-bit multiplier is an arrangement of the these $n^2$ adder gadget as shown in Figure 2 for the case $n=3$.
Figure 2 - $3$-bit multiplier with $9$ adder gadgets. |