252
D. Gorodecky and T. Villa
Table 11.1 Representation
of X(mod 13) with SOPs
x 4 x 3 x 2 x 1 r 4 r 3 r 2 r 1 x 4 x 3 x 2 x 1 r 4 r 3 r 2 r 1
0 0 0 1
0 0 0 0
0 1 0 0
1 0 0 0
0 0 0 0
1 0 0 1
1 0 1 –
1 0 0 0
0 0 1 0
0 1 0 1
0 0 0 1
1 0 0 0
0 0 1 1
0 0 0 1
0 1 1 1
1 0 0 0
0 1 0 0
1 0 1 0
0 1 0 1
0 1 0 0
0 1 0 1
0 1 1 0
– 0 1 0
0 1 0 0
0 1 1 0
0 0 1 0
1 – 0 0
0 1 0 0
0 1 1 1
1 0 1 1
1 0 0 –
0 0 1 0
1 0 0 0
0 1 1 1
0 1 – –
0 0 1 0
1 0 0 1
0 0 1 1
– 0 0 1
0 0 0 1
1 0 1 0
1 1 0 0
1 0 0 –
0 0 0 1
1 0 1 1
1 0 0 0
0 – 1 1
0 0 0 1
1 1 0 0
0 1 0 0
0 0 1 –
0 0 0 1
Subtable 1
Subtable 2
inputs and 6 outputs) X 2
2 · 17(mod 47); with 8 columns (2 inputs and 6 outputs)
X 3
2 · 17(mod 47).
In the example from the last section in Listing 11.2, modular multiplication of
two 6-bit numbers by modulo 47 includes six blocks. Every block realizes Boolean
functions minimized with Espresso or ELS:
– the block mult 3x3 realizes 3 by 3 bit multiplication, with 6 inputs and 6 outputs;
– the block mult 3x38 realizes multi-operand multiplication by modulo 47: ([3 :
1] · [3 : 1] · 8)(mod 47), with 6 inputs and 6 outputs;
– the block mult 3x317 realizes multi-operand multiplication by modulo 47: ([3 :
1] · [3 : 1] · 17)(mod 47), with 6 inputs and 6 outputs;
– the block mult 38 realizes multi-operand multiplication by modulo 47: ([3 : 1] ·
8)(mod 47), with 3 inputs and 6 outputs, and the three least significant bits equal
to zero;
– the block mult 217 realizes multi-operand multiplication by modulo 47: ([2 :
1] · 17)(mod 47), with 2 inputs and 6 outputs, and the fourth bit equal to zero.
11.6 Experimental Results
We compared our procedure vs. three EDA tools: Synopsys, Mentor Graphics (for
standard cells), and Xilinx (for FPGAs). Since Mentor Graphics and Xilinx do
not synthesize general modular operations, we compared with the case of special
moduli, such as 2 s − 1, 2 s + 1. Our approach shows gains within 10%.