If H has the minimum A-depth, the overall graph has the minimum A-depth because the CM subgraph has also the minimum A-depth.
Additionally, a new lower bound has been revealed, namely, the theoretical minimum number of A-operations required to preserve the minimum A-depth, denoted as L EA.
This means that three A-operations are actually not sufficient to preserve the minimum A-depth and at least five A-operations are required.
This new lower bound is essential because preserving the minimum A-depth has been currently an important objective to design systems with high speed and low power.
Figure 9 Graph to implement the multiplier by 11,467 with five A -operations and the minimum A -depth equal to 3. Since we have L A,c = L d,c = 3, with the current lower bounds one can assume that the three A-operations necessary to meet the minimum A-depth might be sufficient to implement the constant multiplier by 11,467.
The theoretical lower bound for the A-cost required when the minimum A-depth is preserved, as well as the lower bound for the A-depth necessary to obtain the minimum A-cost, can be revealed.
Thus, the solution with A-cost equal to 5 and A-depth equal to 3, whose graph is presented in Figure 9, is in fact optimal in terms of the A-cost subject to the minimum A-depth.
Additionally, the formulation of optimal and a suboptimal SCM and MCM algorithms to minimize the A-cost subject to the minimum A-depth can be developed, taking as a basis the theorems developed in this work, where the prime factors of the involved constants can be used as input information.
Theorem 6 A constant c whose MNSD is S(c) > 3 × 2p − 2+ 2Ω c) + q − 2with q = {1, 2,…, (p − Ω(c) − 1)} only can be obtained by using a graph with A-depth at least equal to p + 1 if up to p + q A-operations are used, or with at least p + q + 1 A-operations if the minimum A-depth equal to p is preserved.
Since for current and future semiconductor technologies leakage power consumption is closely related to chip area and it has a significant impact, the value L EA might provide valuable information to decide in an early stage of design if it is better to pursue a minimization of the A-cost subject to the minimum A-depth or minimize the A-cost subject to a given A-depth greater than the minimum.
On the other hand, recall from [12] that it is always possible to find a solution with the lower bound L d,c given in (2), which in this case is L d,c = ⌈ log2S c)⌉ = ⌈ log2 8)⌉ = 3. Figure 9 shows a graph that implements the multiplier by 11,467 with the minimum A-depth equal to 3 and five A-operations, based on the 'Leapfrog' Cost-5 Graph No. 14 of Appendix A of [13].
