In this paper, we propose an efficient solution for the Multiple Constant Multiplication (MCM) problem. The method uses hierarchical clustering to exploit common subexpressions among constants and reduces the number of shifts, additions, and subtractions. The algorithm defines appropriate weights, which indicate operation priority, and selects common subexpressions, resulting in a minimum number of local operations. It can also be extended to various high-level synthesis tasks such as arbitrary linear transforms. Experimental results for several error-correcting codes, digital filters and Discrete Cosine Transforms (DCTs) have shown the effectiveness of our method.

The technique of common-multiplicand multiplication, CMM, is modified and the similar approach is utilized to enhance the performance of a recently proposed fast exponentiation algorithm by exponent decomposition. On average, the improved exponentiation, its original version, and the traditional right to left binary exponentiation algorithm take 1.292m+11,1.375m+3, and 1.5m multiplications, respectively where m is the bit length of the exponent. Finally, it is shown how to improve the overall performance of an exponentiation by employing the improved exponentiation algorithm, the improved CMM algorithm , and any general purpose fast multiplication algorithm.

The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log2 N) time, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.

A programmable clock generator, based on a phase-locked loop (PLL) circuit, has been developed with 0.5 µm CMOS triple-layer Al interconnection technology for use as an on-chip clock generator in a 300-MHz video signal processor. The PLL-based clock generator generates a clock signal whose frequency ranges from 50 to 350 MHz which is an integral multiple, from 2 to 16, of an external clock frequency. In order to achieve stable operation within this wide range, a voltage controlled oscillator (VCO) with selectable low VCO gain characteristics has been developed. Experimental results show that the clock generator generates a 297-MHz clock with a 27-MHz external clock, with jitter of 180 ps and power dissipation of 120 mW at 3.3-V power supply, and it can also oscillate up to 348 MHz with a 31.7-MHz external clock.

High speed multiplication of two n-bit numbers plays an important role in many digital signal processing applications. Traditional array and Wallace multipliers are the most widely used multipliers implemented in VLSI. The area and time (=latency) of these two multipliers depend on operand bit-size, n. For a particular bit-size, they occupy fixed positions in some graph which has area and time along the x and y-axes respectively. However, many applications require a multiplier which has an 'intermediate' area-time characteristics with the above two traditional multipliers occupying two extreme ends of above mentioned area-time curve. In this paper, we propose such an intermediate multiplier which trades off area for time. It has higher speed (i.e., less latendy) but more area than a traditional array multiplier. Whereas when compared with a traditional Wallace multiplier, it has lower speed and area. The attractive point of our multiplier is that, it resembles an array multiplier in terms of regularity in placement and inter-connection of unit computation cells. And its interesting feature is that, in contrast to a traditional array multiplier, it computes by introducing multiple computation wave fronts among its computation cells. In this paper, we investigate on the area-time complexity of our proposed multiplier and discuss on its characteristics while comparing with some contemporary multiplers in terms of latency, area and wiring complexity.

This paper presents an efficient multi-precision modular-multiplication algorithm which minimizes the calculation RAM space required when implementing public-key schemes with software on general-purpose computers including smart cards and personal computers. Many modular-multiplication algorithms cannot be efficiently realized on small systems due to their high RAM consumption. The Montgomery algorithm, which can rapidly perform modular multiplication, has received a lot of attention. Unfortunately, the Montgomery algorithm is difficult to implement, especially in smart cards which have extremely limited RAM space. Furthermore, when the modulus of modular multiplication is frequently changed, or when the number of permissible repeated modular multiplications is small, pre- and post-processing operations such as conversion from/to the Montgomery space become wasteful. The proposed algorithm avoids these problems because it requires only half the RAM space and no pre- and post-processing operations. The algorithm is a radical extension to the approximation methods that use the most significant bits and our newly proposed lookahead determination method. This paper gives a proof of the completeness of this method, describes implementation results using a smart card, introduces a theory supported by the results, and considers the optimal technique to enhance the speed of this method.