Method and apparatus for binary encoding logic circuits

Details Method and apparatus for binary encoding logic circuits Method and apparatus for binary encoding logic circuits

2001-01-29

2003-09-30

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from code based on probability

C341S058000, C341S059000

Reexamination Certificate

active

06628215

ABSTRACT:

The present invention generally relates to the design automation of electronic logic circuits e.g. combinational circuits, finite state machines, and cascaded circuits. More particularly, the present invention relates to the synthesis of logic from symbolic high level languages.
It is known that in high level descriptions of logic circuits the ability to represent the values of some signals at a higher level of abstraction (i.e. with mnemonics) is greatly desirable. However, to construct a physical circuit the mnemonics must be assigned unique binary codes. It is known that the choice of binary codes has a dramatic effect on the speed, silicon area, and power consumption of the final implemented circuit.
Table 1 below gives an example of the binary encoding of 7 mnemonics of a logic circuit.
TABLE 1
Mnemonic
Code
1
000
2
001
3
011
4
111
5
101
6
100
7
110
The minimum number of bits necessary to encode the mnemonics is p, where p is the smallest power of 2 such that 2
p
is greater than or equal to the number of mnemonics. Clearly in the example given in Table 1, 3 bit encoding is capable of coding for up to 8 mnemonics.
The above formula for p gives the minimal number of bits necessary for the encoding of the states of a logic circuit given by mnemonics. Thus, for 5 to 8 mnemonics at least 3 bits are needed, for 9 to 16 mnemonics at least 4 bits are needed, for 17 to 32 mnemonics at least 5 bits are needed, etc.
In the example given in Table 1, a unique binary encoding is given to each mnemonic. However, the choice of the binary encoding to be given to each mnemonic affects the speed area and power consumption of the implemented circuit. Thus, the task of choosing the binary codes is a key step in the implementation of circuits. Unfortunately, this task is very complex. Table 2 below shows the number of distinct minimal length encodings for circuits with various numbers of mnemonics.
TABLE 2
Number of Mnemonics
Distinct Encodings
2
 1
3
 3
4
 3
5
140
6
420
7
840
8
840
9
10,810,800
.
.
.
.
.
.
16
>>5.5 × 10
10
As Table 2 shows, for circuits with nine mnemonics there are at least 10,810,800 distinct minimal length encodings. An exhaustive evaluation of each encoding is thus not feasible. The solution to the problem of the assignment of encodings to the mnemonics of the circuits have been the target of a great deal of work in the prior art. However, the problem of the prior art methods is that they are wholly heuristic and yield slow, area hungry and power hungry circuits.
In one prior art method disclosed in a paper by G De Micheli et al entitled “Optimal State Assignment of Finite State Machines” (IEEE Transactions on Computer Aided Design, Vol. CAD-4, No. 3, July 1985, pages 269-285), a heuristic technique is used in which states which have the same next state and output for a given input are noted. These states are to be given adjacent assignments. Another heuristic is then used to define the complete code of each of the states so as to satisfy as many of the adjacency conditions as possible. This technique attempts to minimise the literal count. This technique is however limited since although it is known that the literal count is related to the area of the final circuit implementation in certain technologies, in other technologies such as field programmable gate arrays, literal count bears a weak relationship to the quality of the final implementation.
In another prior art method disclosed in a paper by T Villa and A Sangiovanni-Vincentelli entitled “NOVA: State Assignment of Finite State Machine for Optimal Two-level Logic Implementations” (26
th
Design Automation Conference pp 327-332) a heuristic technique is used in which states which have the same next state and output for a given input are noted. These states are to be given adjacent assignments. An exact method is then used to satisfy all the adjacency conditions without necessarily using minimal length encoding. It is shown in the paper by experimental methods that this technique rarely yields a lower literal count than minimal length encoding. Moreover, better experiment results from those of the above method (G De Michele) are reported.
In another prior art method disclosed in a paper by J. Monterio et al entitled “Bitwise Encoding of Finite State Machines” (7
th
International Conference on VLSI Design, pages 379-382, January 1994), the states of a finite state machine are encoded iteratively to define the code word based on a heuristic. In this technique all bits are encoded sequentially in an attempt to once again minimise the number of literals. A limitation of this technique is that only the state transitions i.e. the next states are taken in consideration in the heuristic and no outputs of the finite state machine are taken into consideration.
FIG. 1
is a schematic diagram of a finite state machine which receives primary inputs and outputs primary outputs. The major component of the finite state machine is the combinational logic circuit
1
which acts on the primary inputs and present state variables (feedback inputs) to generate the primary outputs and next state variables (feedback outputs). The combinational logic circuit can be described by internal state representations i.e. mnemonics. In a finite state machine the next state of the machine is dependent on the inputs and the present state of the machine. Thus, the states of the finite state machines are output as feedback outputs and are stored in a state memory
2
which comprises flip-flops
2
a
,
2
b
and
2
c
: one per bit for representing the internal states of the finite state machine.
FIG. 1
is represented as having internal states represented by 3 bit encodings with 3 bit encoded primary inputs and 3 bit encoded primary outputs.
Thus the inventors of the present invention have identified that in the approach of Monterio et al the omission of the consideration of the primary outputs and previously determined encoding bits in the heuristic reduces the effectiveness of the technique.
The approach by Monterio et al is also restricted to minimal length encoding and this does not always result in the best circuit from the viewpoint of area and/or speed.
Further, this approach uses a technique for the state assignment of finite state machines in which the finite state machine is decomposed by partitioning. This technique suffers from the disadvantage of the need to find preserved partitions in the set of mnemonic states. Such partitions are not always present.
It is thus an object of the present invention to provide a circuit design method and apparatus in which the disadvantages of the prior art methods are overcome and circuits of desired speeds, silicon area, and power consumption can be produced.
In accordance with a first aspect of the present invention, there is provided a method and apparatus for determining the binary encodings of a circuit which is in part heuristic and in part exact.
In this aspect of the present invention the inventors have realised that the assignment of binary encodings to a circuit can benefit from the use of the exact technique when the number of bits to be encoded is reduced. The number of bits to be encoded can be reduced by initially using a heuristic technique to determine the encodings of a number of bits thereby leaving only a limited number of bits left to be encoded. The exact technique can be used for the encoding of the last few bits to be determined.
The exact evaluation can be carried out using information on the preferred logic implementation e.g. Application Specific Integrated Circuits (ASIC's) or Field Programmable Gate Arrays (PPGA's). Thus this allows the preferred implementation to be taken into account during the state assignment.
In this aspect of the present invention, any conventional heuristic technique can be used for the encoding of the initial bits.
In this aspect of the present invention, the search can be successively divided into blocks by the encoding of initial bits using the heuristic technique. Each block is exhaustively evaluated in a determine

Affiliated with

Also associated with

Rating

Method and apparatus for binary encoding logic circuits does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for binary encoding logic circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for binary encoding logic circuits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3101707