Method and apparatus for binary encoding logic circuits
AssigneeAutomatic Parallel Design Limited
InventorsSunil Talwar, Peter Meulemans
Life of this patent
Estimating the term…
Abstract
A method and apparatus for state assignment of a logic circuit comprises receiving internal state representations for the logic circuit, determining binary code for the internal state representations by successively dividing the states into disjoint sets of ever decreasing size Each disjoint set of a pair is assigned a one bit at each division step. The division can continue for all bits to be encoded, or the division can be halted and exact encoding used for the encoding of the final number of bits.
Claims61
A method of state assignment of a logic circuit, the method comprising;
- receiving state transition data for the logic circuit the state transition data including internal state representations;
- determining binary code for said internal state representations one bit at a time until the number of bits left to be encoded to provide an encoding of said internal state representations reaches a predetermined number;
- and
- exhaustively evaluating the possible encodings for the predetermined number of bits having regard to the determined binary code or codes for said internal state representations to determine the optimum state assignment for the logic circuit.
A method according to any preceding claim wherein the step of determining binary code for said internal state representations comprises:
- determining binary code for said internal state representations one bit at a time by repeatedly dividing the internal state representations into disjoint sets by reference to next states transited to from present states in response to an input to the logic circuit and assigning a binary code to each bit in dependence upon the divisions;
- where the sets of internal state representations become repeatedly smaller after each division, and the divisions of the internal state representations are determined in dependence upon the encoding of any previous divisions.
A method according to any preceding claim wherein the step of determining binary code for said internal state representations comprises;
- identifying for a first bit at least one set of internal state representations for next states to which a set of internal state representations for present state transit upon an input to the logic circuit, the or each identified set being one of a pair of disjoint sets dividing said internal state representations into two sets;
- assignment a binary code to the first bit for each internal state representation dependent upon which set of the pair of disjoint sets the internal state representations belongs to;
- for any subsequent bits, subsequently identifying for each previously identified disjoint set for a previous bit, at least one set of internal state representations for next states to which a set of internal state representations for present states contained within the previously identified disjoint set of internal state representations transit upon an input to the logic circuit and using the assigned binary code of a previous bit as an input, the or each subsequently identified set being one of a pair of disjoint sets dividing the previously identified disjoint set of internal state representations into two sets;
- and
- assignment a binary code to any subsequent bit for each said internal state representation dependent upon which set of the or each pair of disjoint sets the internal state representation belongs.
A method according to any preceding claim wherein each determined binary encoding represents a set of said internal state representations, each set of said internal state representations having said predetermined number of bits left to be encoded, and the exhaustive evaluation step comprising:
- (a) determining the set of said internal state representations which has the smallest number of internal state representations for next states transited to upon an input which are not in the set and which require encoding of said predetermined number of bits;
- (b) defining default encodings for the predetermined number of bits of any said internal state representations for next states not in the set;
- (c) exhaustively evaluating the possible encodings for the predetermined number of bits for said set of internal state representations to determine optimum encodings;
- (d) combining said set with each logically adjacent partially encoded set to form a new set;
- and
- (e) repeat steps (a) to (d) until said predetermined number of bits for all of said internal state representations have been encoded.
Apparatus for the state assignment of a logic circuit, the apparatus comprising:
- receiving means for receiving state transition data for the logic circuit, the state transition data including internal state representations,
- determining means for determining binary code for said internal state representations one bit at a time until the number of bits left to be encoded to provide an encoding of said internal state representations reaches a predetermined number;
- and
- evaluation means for exhaustively evaluating all the possible encodings for the predetermined number of bits having regard to the determined binary code or codes for said internal state representations to determine the optimum state assignment for the logic circuit.
A method of state assignment for a logic circuit, the method comprising:
- receiving state transition data for the logic circuit, the state transition data including internal state representations;
- determining binary code for said internal state representations one bit at a time by repeatedly dividing the internal state representations into disjoint sets by reference to next states transited to from present states in response to an input to the logic circuit and assigning a one bit code to each of the states of the disjoint sets in dependence upon the divisions;
- where the sets of internal state representations become repeatedly smaller after each division, and the divisions of the internal state representations are determined in dependence upon the encoding of any previous divisions.
Apparatus for the state assignment of a logic circuit, the apparatus comprising:
- receiving means for receiving state transition data for the logic circuit, the state transition data including internal state representations;
- determining means for determining binary code for said internal state representations one bit at a time by repeatedly dividing the internal state representations into disjoint sets by reference to next states transited to from present states in response to an input to the logic circuit, and for assigning a one bit code to each state of the disjoint sets in dependence upon the divisions;
- said determining means being adapted to make the sets of internal state representations become repeatedly smaller after each division, and to determine the divisions of the internal state representations in dependence upon the encoding of any previous divisions.
A method of optimising state assignments of a logic circuit, the method comprising;
- receiving state data for the logic circuit, the state data including internal state representations each being encoded with a plurality of binary bits;
- encoding a plurality of binary encoded bits of each internal state representation as at least one symbolic representation;
- and
- determining optimum binary codes for the symbolic representations of the or each set having regard to any binary codes for each representation.
Apparatus for optimising state assignments of a logic circuit, the apparatus comprising;
- receiving means for receiving state data for the logic circuit, the state data including internal state representations each being encoded with a plurality of binary bits;
- symbolic means for encoding a plurality of binary encoded bits of each internal state representation as at least one set of symbolic representations;
- and
- determining means for determining optimum binary codes for the symbolic representations of the or each set having regard to any binary codes for each representation.
Apparatus according to any one of claims 47 to 57, wherein said determining means is adapted to repeatedly divide the internal state representations into disjoint sets by reference to next states transited to from present states in response to an input to the logic circuit, and to assign a binary code to each bit in dependence upon the divisions, wherein said determining means is adapted to make the sets of internal state representations repeatedly smaller after each division and to determine the divisions of the internal state representations in dependence upon the encoding of any previous divisions.
Dependencies are inferred from the claim text.