Research on Design of VLSI Oriented Hardware Algorithms Using Redundant Representation

在一个复杂的超大规模集成电路的设计和开发中，为了实现高性能的电路，首先设计其硬件算法是非常重要的。从这一点出发，我们进行了研究的VLSI面向硬件算法的设计使用冗余表示。主要研究结果如下：1.用冗余表示法设计硬件算法我们提出了用冗余二进制表示法实现初等函数的高速硬件算法。冗余二进制表示法使实现等深度加法器和减法器成为可能。利用这些加法器和减法器，我们设计了各种基本功能的高速电路.利用复杂的数据表示和数据结构设计面向VLSI的硬件算法我们提出了一种<OMICRON>基于剩余数表示的（log n）深度n位二进制除法算法，并在此基础上设计了一个除法器，此外，我们还提出了一种基于项图的高速硬件合一算法.高速硬件算法的冗余编码我们提出了冗余编码的方法，使得对剩余类和有限阿贝尔群进行运算的恒时硬件算法的实现成为可能.一种适合于逐步求精的硬件设计语言我们提出了一种硬件设计语言，它可以用硬件算法描述硬件的层次逻辑设计。

In a design and development of complex VLSI, it is very important to design its hardware algorithm first so that we can realize high performance circuit. From this point of view, we have performed researches on design of VLSI oriented hardware algorithms using redundant representation. The main results are listed below:1. Desing of Hardware Algorithms Using Redundant RepresentationWe proposed high speed hardware algorithms for elementary functions using a redundant binary representation. The redundant binary representation makes it possible to realize adder and subtracter of constant depth. By using these adder and subtracter, we have designed high speed circuits for various elementary functions.2. Design of VLSI Oriented Hardware Algorithms by Means of Sophisticated Data Expressions and Data StructuresWe have proposed an <OMICRON> (log n) depth n-bit binary division algorithm using residue number representation and designed a divider based on it. Furthermore, we proposed a high speed hardware algorithm for unification based on a new data structure named term graph.3. Redundant Coding for High Speed Hardware AlgorithmsWe have proposed redundant coding methods which makes it possible to realize constant time hardware algorithms for operations on residue class and finite Abelian group.4. Hardware Design Language Suitable for Step by Step RefinementWe have proposed a hardware design language which can describe hierarchical logic design of hardware with its hardware algorithms.