WO1992018944A1 - Verfahren zur verifikation datenverarbeitender systeme - Google Patents

Verfahren zur verifikation datenverarbeitender systeme Download PDF

Info

Publication number
WO1992018944A1
WO1992018944A1 PCT/EP1992/000789 EP9200789W WO9218944A1 WO 1992018944 A1 WO1992018944 A1 WO 1992018944A1 EP 9200789 W EP9200789 W EP 9200789W WO 9218944 A1 WO9218944 A1 WO 9218944A1
Authority
WO
WIPO (PCT)
Prior art keywords
states
mealy
binary decision
processing systems
automatons
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/EP1992/000789
Other languages
English (en)
French (fr)
Inventor
Thomas Filkorn
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Siemens AG
Siemens Corp
Original Assignee
Siemens AG
Siemens Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Siemens AG, Siemens Corp filed Critical Siemens AG
Priority to EP92908193A priority Critical patent/EP0580663B1/de
Priority to US08/133,208 priority patent/US5491639A/en
Priority to DE59201155T priority patent/DE59201155D1/de
Publication of WO1992018944A1 publication Critical patent/WO1992018944A1/de
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F30/00—Computer-aided design [CAD]
    • G06F30/30—Circuit design
    • G06F30/32—Circuit design at the digital level
    • G06F30/33—Design verification, e.g. functional simulation or model checking
    • G06F30/3323—Design verification, e.g. functional simulation or model checking using formal methods, e.g. equivalence checking or property checking

Definitions

  • combinatorial or synchronous sequential circuits are often formulated in the form of so-called hardware description languages (HOL).
  • the formal verification means the comparison of a digital circuit, as is given, for example, in the form of a network list with its specification in the form of a description using the methods of a hardware description language.
  • Formal circuit verification tools are known from the literature (Erik Tid ⁇ n, Richard Schmid, "Verifying ASICs at symbolic Simulation", in EURO ASIC 90, 1990), but their applicability is limited to combinatorial circuits.
  • the formal verification of sequential digital circuits is much more difficult, and only a few approaches to solving the problem of verifying digital circuits with a large number of states are known.
  • the invention relates to a method for verifying data processing systems, in particular digital circuits, which is based on the symbolic representation of Boolean functions with the aid of binary decision diagrams.
  • the invention is based on the object of specifying a method for verifying data-processing systems, in particular digital circuits, which is capable of verifying not only combinatorial but also sequential systems of great complexity and thus the problems of the prior art known methods to overcome. This object is achieved with the aid of a method for verifying data processing systems, in particular digital circuits, with features according to claim 1.
  • this method is also based on the comparison of two independently created formal descriptions of a system to be verified, for example the system specification formulated with the aid of a hardware description language and the circuit implementation currently available in the form of a network list .
  • the method according to the invention uses a special representation of Boolean functions with the aid of binary decision diagrams or means equivalent to this.
  • This special and advantageous representation of Boolean functions enables a comparison of the two system descriptions to be carried out with the aid of a fixed point iteration, with the aid of which non-equivalent states of the two system descriptions are found.
  • the two system descriptions to be compared with one another are modeled as Mealy automatons.
  • the set of non-equivalent states of the two Mealy automatons is represented in the form of binary decision diagrams or means equivalent to them.
  • the output and transition functions of the two Mealy automatons are also represented by binary decision diagrams or by means equivalent to them.
  • Decision diagrams results in an extremely efficient storage of the data structures of the method and enables the operations required to carry out the method to be restricted to simple substitutions and Boolean operations on binary decision diagrams. As a result, the process becomes technically applicable for systems of technical interest in the first place.
  • the method according to the invention can be applied to data processing systems of various types, e.g. applied to digital circuits, communication protocols, computer programs and micro programs for their verification. Every technical system that can be modeled as a Mealy automat can be verified using the method.
  • Figure 1 shows a flow chart of the method.
  • a finite deterministic Mealy automaton is by specifying an alphabet of input variables, a finite set of states, a alphabet of output variables, an output function which assigns a value of the output variables to each value of the input variable 1 " 1 and the states, give a transition function, which assigns a state to each input value and state, and an initial state.
  • a deterministic Mealy automaton defines a partial mapping, which assigns a word made up of elements of the alphabet of output sizes to each word made up of elements of the alphabet of input sizes. If the machine is given a sequence of input variables, this sequence becomes a sequence of
  • Output variables are assigned, firstly new state variables are calculated from the input variables with the aid of the transition function and then the new output variables are calculated from the state variables and the input variables with the aid of the output function. If one looks at the machine from the outside, these assignments are the only thing that can be observed about its behavior and it is therefore natural to consider two deterministic Mealy machines as equivalent if they have a matching input and output alphabet and if their assignments described above are equivalent.
  • the mapping is referred to here as partial, because in general the transition function and the output function are only partially defined functions. By completing these functions, e.g. in Z.Kohavi, 1978, the problem of comparing two incompletely described machines can be attributed to a comparison of two fully described machines. In the following, it is therefore assumed that the output and transition functions are completely defined functions, and therefore only the problem of comparing two completely deterministic Mealy automatons is considered.
  • Two states of two deterministic Mealy automatons with matching input and output alphabets are called equivalent if and only if a) the values of their output functions for these two states match with the same input signals and b) for all values of the input signals which are equivalent from their states resulting from these transition states with the same input signals in each case.
  • Mealy automatons are described in the article by Z.Kohavi 1978:
  • the product automaton is defined for two Mealy automatons with identical input and output alphabets, by using as the input alphabet of the product automaton the underlying underlying the two original Mealy automatons ⁇ uses the same input alphabet, selects the set of states of the automatic product equal to the map product of the state set of the output automats, the output alphabet of the automatic product allows the two Boolean values "true” or "false” to exist, the output function of the automatic product Assigns the value "true” if the output functions of the original machines match, assigns the output function of the product machine the value "false” if the output functions of the original machines do not match, and the transition function of the product machine which results from the values of the transition functions of the original l assigns two-tuple to automatons.
  • the equivalence relation between states of two deterministic Mealy automatons is the largest relation on the Cartesian product of the two state spaces of two Mealy automatons with the following property:
  • An element of the product state space belongs to the relation and only if the following applies to all input values:
  • the output function of the product automat takes the value "true" for this element of the product status space and the image of the transition function also belongs to the relation.
  • Two deterministic mealy automata are then called equivalent only if all states of the product state space formed from the initial states of these two automata belong to this equivalence relation.
  • Devadas, et al, 1988 can be compared with the aid of this strategy.
  • the second possible strategy can be called breadth-first strategy (O.Coudert, et al, 1989).
  • This strategy several states are treated in one step instead of just one, as in the depth-first strategy, so that this strategy can benefit from an efficient representation of sets using binary decision diagrams (REBryant, "graph-based") algorithm for boolean function manipulation ", IEEE Transaction ⁇ Computer, C-35 (12): 1035-1044, 1966).
  • REBryant, "graph-based" algorithm for boolean function manipulation ", IEEE Transaction ⁇ Computer, C-35 (12): 1035-1044, 1966).
  • the total relation of the non-equivalent states ie the complement of the set of equivalent states, is determined calculated the product space of the states. The calculation is performed using a fixed point iteration, in which only simple operations on binary decision diagrams are required.
  • the starting point is considered to be the set of all state pairs, ie the set of all states of the product automat of the Mealy automat to be checked, which have different output values for at least one input pattern.
  • This output quantity is now gradually expanded to include those state pairs for which it applies that the state pairs of the original quantity can be reached in a finite number of steps, assuming suitable input patterns, using the transition functions of the Mealy automats to be verified or the transition function of the product automat can.
  • This iteration ends if the set of state pairs generated thereby no longer changes, ie if a fixed point is reached. It is clear from the definition of equivalence of Mealy automatons that this set of fixed points is the set of all non-equivalent states.
  • the states and input or output signals of the Mealy automatons modeling these circuits are Boolean vectors and the output and transition functions are defined as vector-valued Boolean functions, the arguments of which are Boolean vectors.
  • the binary decision diagrams (BODS) were introduced by Bryant (R.E.Bryant 1986) to represent such Boolean functions and the operations on them.
  • Binary decision diagrams have advantageous properties only for certain classes of Boolean functions, since the size of a binary decision diagram, which represents a Boolean function, is in the worst case an exponentially growing function of the number of arguments of this Boolean function.
  • Boolean functions which are implemented by combinatorial or sequential digital circuits, have compact representations by means of binary decision diagrams and that? binary decision diagrams can advantageously be used to represent sequential digital circuits.
  • the characteristic function corresponds to an average set of two sets of the AND operation of both characteristic functions of these sets, the characteristic function of a union set of the OR operation and the characteristic function of a difference formation of the AND Linking the characteristic functions of the initial set with the characteristic function of the complement of the subtracted set.
  • the corresponding transition relation is used to model a synchronous sequential digital circuit instead of the transition function.
  • This transition relation is represented with the aid of a binary decision diagram of the characteristic function of this transition relation.
  • Empirical studies have shown that the representation of synchronous sequential digital circuits and combinatorial digital circuits with the aid of functional vectors of binary decision diagrams has advantages over a representation in the form of characteristic functions, since it is apparently able to represent circuits of higher complexity.
  • the first step in preparing the fixed point iteration is the calculation of the output relation MO, to which all pairs of states, which are formed from two states of the two automatic mealyers, belong, for which it applies that at least one input signal exists for which the output functions of the two Mealy machines assume different values for the two states. If the output functions of the two automatic mealyers are given as vectors of binary decision diagrams, the characteristic function of the output relation can easily be calculated.
  • the associated binary decision diagrams "EXOR” are linked from the vectors of binary decision diagrams for the output functions for each individual output.
  • a binary decision diagram is therefore calculated for each output, which delivers the value "true” for exactly the state pairs and input signals, for which this output supplies a different value in the two automatic machines.
  • An existence operator with respect to the inputs is then applied to each of these binary decision diagrams.
  • a binary decision diagram calculated in this way gives the value "true” precisely for the pairs of states for which at least one input signal exists, so that the original binary decision diagram supplies the value "true", that is to say the output has a lower value delivers different value.
  • the existence operator on a binary decision diagram for a set of inputs can be successively calculated by the existence operator for a single input.
  • the existence operator with respect to the first is added to the original binary decision diagram. Initially calculated.
  • the existence operator with respect to the second input is calculated on the resulting binary decision diagram. This process continues until the last input.
  • To calculate an existence operator with respect to an input the input is substituted in the binary decision diagram by "true” or "false” and the two standing binary decision diagrams are linked "OR". The existence operator can thus be traced back to simple substitution and an "OR" combination.
  • the binary decision diagrams which have arisen for the individual outputs are still all ORed and the result is a binary decision diagram which represents the characteristic function for MO.
  • An explicit calculation of the intermediate results is not absolutely necessary, but the entire calculation of MO described above from the vectors of binary decision diagrams for the output functions can also be merged into a single step.
  • the starting relation MO is the starting point of the fixed point iteration, which calculates further relations from the starting relation.
  • the iteration process stops if an iteration step does not change the relation.
  • a simple comparison of two successive binary decision diagrams, which represent the characteristic functions of the relations, is necessary.
  • the Mealy automatons to be compared are equivalent if their initial states do not belong to the relation M of the non-equivalent states.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Evolutionary Computation (AREA)
  • Geometry (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)
  • Complex Calculations (AREA)
  • Design And Manufacture Of Integrated Circuits (AREA)

Abstract

Implementierung und Spezifikation synchroner, sequentieller Schaltungen und anderer datenverarbeitender Systeme können durch endliche Automaten modelliert werden. Die Verifikation, d.h. der Vergleich der Implementierung und der Spezifikation solcher Systeme kann dann auf den Vergleich zweier endlicher Automaten zurückgeführt werden. Basierend auf einer symbolischen Darstellung endlicher Automaten mit Hilfe binärer Entscheidungsdiagramme wurde eine Methode für den Vergleich endlicher Automaten entwickelt, welche auf Rechenanlagen automatisch ablauffähig ist und somit die automatische Verifikation solcher Schaltungen ohne Simulation ermöglicht.

Description

Verfahren zur Verifikation datenverarbeitender Systeme
Fehler in der Entwurfsphase digitaler Schaltungen sind ein Hauptgrund für unerwartete Verzögerungen und zusätzliche Kosten. Um.diese zu vermeiden, werden momentan verschiedene Simulationsverfahren zur Verifikation eines logischen Schal¬ tungsentwurfs eingesetzt. Unglücklicherweise wächst die Zahl der zur Verifikation einer Schaltung oder eines datenver¬ arbeitenden Systems nötigen Simulationen exponentiell mit der Zahl der Eingänge kombinatorischer Schaltkreise und sogar schneller für sequentielle Schaltkreise, da bei diesen alle möglichen Eingangssequenzen zu simulieren sind. Obwohl solche Methoden zur Simulation digitaler Schaltungen weit verbreitet sind und einen wichtigen Platz im Entwurfsprozeß solcher Schaltungen einnehmen, sind sie weit davon entfernt zur voll- ständigen Überprüfung und Verifikation von Schaltungen geeig¬ net zu sein, weshalb die Richtigkeit einer Schaltung, d.h. die Übereinstimmung zwischen ihrer tatsächlichen Implementie¬ rung und ihrer Entwurfsspezifikation nicht garantiert werden kann. Aus diesem Grunde sind formale Verifikationsmethoden jeder Art von Simulation vorzuziehen, da diese im Prinzip die vollständige Richtigkeit einer Schaltung beweisen können.
Spezifikationen von kombinatorischen oder synchronen sequen¬ tiellen Schaltungen werden häufig in Form sog. Hardware-Be- Schreibungssprachen (hardware description languages, HOL) for¬ muliert. In solchen Fällen bedeutet die formale Verifikation den Vergleich einer digitalen Schaltung, wie sie z.B. in Form einer Netzliste gegeben ist mit ihrer Spezifikation in Form einer Beschreibung mit den Methoden einer Hardware-Beschrei- bungssprache. Aus der Literatur (Erik Tidέn, Richard Schmid, "Verifying ASICs bei symbolic Simulation", in EURO ASIC 90, 1990) sind formale Schaltkreisverifikationswerkzeuge bekannt, deren Anwendbarkeit aber auf kombinatorische Schaltkreise beschränkt ist. Die formale Verifikation sequentieller Digi¬ talschaltungen ist wesentlich schwieriger, und es sind nur wenige Ansätze zu einer Lösung des Problems der Verifikation digitaler Schaltungen mit einer großen Zahl von Zuständen bekannt.
Die Erfindung betrifft ein Verfahren zur Verifikation datenver- arbeitender Systeme, insbesondere digitaler Schaltungen, welche auf der symbolischen Darstellung boolescher Funktionen mit Hilfe binärer Entscheidungsdiagramme basiert. Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren zur Verifikation datenverarbeitender Systeme, insbesondere digitaler Schaltungen anzugeben, welches in der Lage ist, nicht nur kombinatorische, sondern auch sequentielle Systeme großer Komplexität zu veri¬ fizieren und damit die Probleme der zum Stand der Technik be¬ kannten Verfahren zu überwinden. Diese Aufgabe wird mit Hilfe eines Verfahrens zur Verifikation datenverarbeitender Systeme, insbesondere digitaler Schaltungen, mit Merkmalen nach Anspruch 1 gelöst.
Dieses Verfahren basiert ebenfalls wie das aus de Stand der Technik bekannte Verfahren auf dem Vergleich zweier unabhängig voneinander erstellter formaler Beschreibungen eines zu veri¬ fizierenden Systems, z.B. der mit Hilfe einer Hardware-Beschrei¬ bungssprache formulierten Systemspezifikation und der z.E. in Form einer Netzliste vorliegenden Schaltungsimplementierung. Das erfindungsgemäße Verfahren bedient sich einer speziel- len Darstellung boolescher Funktionen mit Hilfe binärer Entschei dungsdiagram e oder hierzu gleichwertiger Mittel. Diese spezielle und vorteilhafte Darstellung boolescher Funktionen ermöglicht die Durchführung des Vergleichs beider Systembeschreibungen mit Hilfe einer Fixpunktiteration, mit deren Hilfe nicht äquivalente Zustände der beiden Systembeschreibungen aufgefunden werden. Dazu werden die beiden miteinander zu vergleichenden Systembe¬ schreibungen als Mealy-Automaten modelliert. Mit Hilfe einer Fixpunkt-Iteration wird die Menge der nicht-äquivalenten Zustände der beiden Mealy-Automaten in Form binärer Entschei¬ dungsdiagramme oder hierzu äquivalenter Mittel dargestellt. Zur Durchführung der Fixpunktiteration werden die Ausgangs¬ und Übergangsfunktionen der beiden Mealy-Automaten ebenfalls durch binäre Entscheidungsdiagramme oder hierzu äquivalente Mittel dargestellt.
Die erfindungsgemäße Form der Darstellung durch binäre
Entscheidungsdiagramme bewirkt eine äußerst effiziente Speiche¬ rung der Datenstrukturen des Verfahrens und ermöglicht eine Be¬ schränkung der zur Durchführung des Verfahrens notwendigen Ope¬ rationen auf einfache Substitutionen und Boolesche Operationen auf binären Entscheidungsdiagrammen. Hierdurch wird das Verfah¬ ren für technisch interessierende Systeme überhaupt erst prak¬ tisch anwendbar.
Das erfindungsgemäße Verfahren kann auf datenverarbeitende Systeme verschiedener Art, wie z.B. auf digitale Schaltungen, Kommunikationsprotokolle, Computerprogramme und Mikroprogramme zu deren Verifikation angewendet werden. Jedes technische System, welches als Mealy-Automat modelliert werden kann, kann mit Hilfe des Verfahrens verifiziert werden.
Vorteilhafte Weiterbildungen der Erfindung ergeben sich aus den Unteransprüchen.
Figur 1 zeigt ein Ablaufdiagramm des Verfahrens.
Im folgenden wird die Erfindung anhand eines speziellen Ausführungsbeispiels näher beschrieben. Aus Gründen der besse¬ ren Verständlichkeit werden die wichtigsten grundlegenden hier¬ zu benötigten Begriffe am Anfang erläutert. Im übrigen sind die hier verwendeten Begriffe und Bezeichnungsweisen dem Fach¬ mann auf diesem Gebiet geläufig und können z.B. in den Ver¬ öffentlichungen von K. Brauer, "Automatentheorie", E.G. Teub- ner, 1964 oder Z. Kohavi, "Switching and Finite Automata Theory", McGraw-Hill Book Edition, 1978, entnommen werden. -A-
Bei synchronen sequentiellen Digitalschaltungen werden alle Elemente mit internen Zuständen, wie z.B. Flip-Flops, Latches, Register und speichernde Elemente mit Hilfe eines globalen Clocksignals getriggert, sodaß alle Elemente ihren Zustand simultan bei einem Clocksignal-Übergang ändern. Der neue Zu¬ stand einer synchronen sequentiellen Digitalschaltung hängt dabei ausschließlich von ihrem momentanen Zustand und den Wer¬ ten der Eingangssignale ab. Damit hängen auch die Ausgangs- Signale der Digitalschaltung nur von den Eingangssignalen und dem internen Zustand dieser Schaltung ab. Aus diesem Grunde kann das Verhalten einer synchronen sequentiellen Digitalschal¬ tung durch das Modell des endlichen Automaten (finite State machine), genauer als Mealy-Automat modelliert werden (Z.Koha- vi, 1978, K.Brauer, 1984). Sowohl die Spezifikation einer syn¬ chronen sequentiellen Digitalschaltung als auch ihre Implemen¬ tierung kann daher als Mealy-Automat aufgefaßt werden. Dabei wird die Implementierung einer solchen Digitalschaltung häufig in Form einer sog. Netzliste vorliegen. Die Spezifikation kann vorteilhaft mit Hilfe einer Übergangstabelle oder einer geeig¬ neten Hardware-Beschreibungssprache geschehen. Eine synchrone seαuentielle Digitalschaltung zu verifizieren bedeutet, eine Implementierung dieser Schaltung mit ihrer Spezifikation zu vergleichen. Wegen der Modellierbarkeit beider Beschreibungen durch Mealy-Automaten läßt sich dieses Problem auf den Vergleich zweier unterschiedlich beschriebener Mealy-Automaten reduzie¬ ren. Die folgenden Definitionen endlicher deterministischer Mealy-Automaten und der Äquivalenz zwischen zwei Mealy-Automε- ten sind in der Automatentheorie (Z.Kohavi, 1978; W.Brauer, 1984) üblich. Der besseren Verständlichkeit halber werden diese Definitionen hier kurz zusammengestellt.
Ein endlicher deterministischer Mealy-Automat ist durch die Angabe eines Alphabetes von Eingangsgrößen, einer endlichen Menge von Zuständen, eines Alphabetes von Ausgangsgrößen, einer Ausgangsfunktion, welche jedem Wert der Eingangsgröße1"1 und der Zustände einen Wert der Ausgangsgrößen zuordnet, einer Übergangsfunktion, welche jedem Eingangswert und Zustand einen Zustand zuordnet, sowie eines anfänglichen Zustandes ge¬ geben.
Ein deterministischer Mealy-Automat definiert eine partielle Abbildung, welche jedem Wort aus Elementen des Alphabets von Eingangsgrößen ein Wort aus Elementen des Alphabets der Aus¬ gangsgrößen zuordnet. Wird dem Automaten eine Folge von Ein- gangsgrδßen eingegeben, so wird dieser Folge eine Folge von
Ausgangsgrößen zugeordnet, wobei zunächst aus den Eingangsgrös- sen mit Hilfe der Übergangsfunktion neue Zustandsgrößen und dar¬ aufhin aus den Zustandsgrößen und den Eingangsgrößen mit Hilfe der Ausgangsfunktion die neuen Ausgangsgrößen berechnet werden. Betrachtet man den Automaten von außen, so sind diese Zuord¬ nungen das einzige was über sein Verhalten beobachtet werden kann und es ist deshalb natürlich, zwei deterministische Mealy Automaten als äquivalent anzusehen, wenn sie ein übereinstim¬ mendes Eingangs- und Ausgangsalphabet haben und wenn ihre oben beschriebenen Zuordnungen äquivalent sind. Die Abbildunc wird dabei als partiell bezeichnet, weil im allgemeinen die Über¬ gangsfunktion und die Ausgangsfunktion nur partiell definierte Funktionen sind. Indem diese Funktionen vervollständigt werden, was z.B. in Z.Kohavi, 1978 beschrieben ist, kann das Problem des Vergleichs zweier unvollständig beschriebener Automaten auf einen Vergleich zweier vollständig beschriebener Automaten zurückgeführt werden. Im folgenden wird deshalb angnommen, daß die Ausgangs- und Übergangsfunktion vollständig definierte Funktionen sind, und es wird deshalb lediglich das Problem des Vergleichs zweier vollständiger deterministischer Mealy-Auto¬ maten betrachtet.
Zwei Zustände zweier deterministischer Mealy-Automaten mit übereinstimmenden Eingangs- und Ausgangsalphabeten heißen äquivalent genau dann, falls a) die Werte ihrer Ausgangsfunktionen für diese beiden Zustände bei jeweils gleichen Eingangssignalen übereinstim¬ men und b) für alle Werte der Eingangssignale, die sich aus ihren Übergangsfunktionen aus diesen Zuständen ergebenden Zustände bei jeweils gleichen Eingangssignalen äquivalent sind.
Zwei deterministische Mealy-Automaten mit gleichen Eingangs¬ und Ausgangsalphabeten heißen äquivalent dann und nur dann, wenn ihre Anfangszustände äquivalent sind.
Ein Standardverfahren zur Überprüfung der 'Äquivalenz zweier
Mealy-Automaten wird in dem Aufsatz von Z.Kohavi 1978 beschrie¬ ben: Hierzu definiert man zu zwei Mealy-Automaten mit identi¬ schen Eingangs- und Ausgangsalphabeten den Produktautomaten, indem man als Eingangsalphabet des Produktautomaten das den beiden ursprünglichen Mealy-Automaten zugrundeliegende gemein¬ same Eingangsalphabet verwendet, die Menge der Zustände des Produktautomaten gleich dem karteεischen Produkt der Zustands- menge der Ausgangsautomaten wählt, das Ausgangsalphabet des Produktautomaten aus den beiden booleschen Werten "wahr" bzw. "falsch" bestehen läßt, der Ausgangsfunktion des Produktauto¬ maten den Wert "wahr" zuweist, falls die Ausgangsfunktionen der ursprünglichen Automaten übereinstimmen, der Ausgangs¬ funktion des Produktautomaten den Wert "falsch" zuweist, falls die Ausgangsfunktionen der ursprünglichen Automaten nicht übereinstimmen, und der Übergangsfunktion des Produktauto¬ maten die aus den Werten der Übergangsfunktionen der ursprüng¬ lichen Automaten gebildeten Zweitupel zuweist. Mit Hilfe die¬ ser Definition können die beiden Definitionen über die Äqui¬ valenz zweier Zustände zweier deterministischer Mealy-Auto- maten sowie die Definition über die Äquivalenz von Mealy- Automaten wie folgt formuliert werden:
Die Äquivalenzrelation zwischen Zuständen zweier determini¬ stischer Mealy-Automaten ist die größte Relation auf dem kar- tesischen Produkt der beiden Zustandsräume zweier Mealy-Auto- maten mit der folgenden Eigenschaft:
Ein Element des Produkt-Zustandεraums gehört zur Relation dann und nur dann, falls für alle Eingangswerte gilt: Die Ausgangsfunktion des Produktautomaten nimmt für dieses Element des Produktzustandsraums den Wert "wahr" an und das Bild der Übergangsfunktion gehört ebenfalls zur Relation. Zwei deterministische mealy-Automaten heißen dann äquivalent dann und nur dann, falls sämtliche aus den Anfangszuständen dieser beiden Automaten gebildeten Zustände des Produktzustandsraums zu dieser Äquivalenzrelation gehören.
Die bekannten Verfahren (O.Coudert, Ch. Berthet, J.Ch. Madre, "Verification of sequential achines using boolean functional vectors", in IMEC-IFIP International Workshop on Applied Formal Methods For Correct VLSI Design, 1989; S.Devadas, Hi-Keung Tony Ma, R. Newton, "On the verification of sequential machines at differing levels of abstraction", IEEE-Transactions on
Computer-Aided Design, 7(6): 713-722, 1988; K.J.Supovit, S.J. Friedman, "A new method for verifying sequential circuits, in 23rd ACM/IEEE Design Automation Conference, 1986) zur Überprüfung der Äquivalenz zweier synchroner sequentieller Schaltkreise (Mealy-Automaten) gehen von einem Anfangszu¬ stand des Produktautomaten aus, und suchen nach einem Über¬ gang bei dem die Ausgangsfunktion des Produktautomateπ den Wert falsch annimmt, wodurch ein Unterschied im Ausganos- verhalten der beiden ursprünglichen Maschinen signalisiert wird. Falls kein solcher Übergang gefunden wird, nachdem der gesamte erreichbare Zustandsraum der Produktmaschine abge¬ arbeitet worden ist, ist die Äquivalenz der ursprünglchen Mealy-Automaten und damit der zu vergleichenden synchronen sequentiellen Schaltungen bewiesen.
Die explizite Konstruktion des Zustandsdiagra s (K.H.Supovit, S.J.Friedman 1986) des Produktautomaten ist ein sehr speicher¬ verzehrender Vorgang und kommt daher nur zur Verifikation mit Automaten mit nur sehr wenigen Zuständen, wie sie z.B. zu Kontrollschaltungen gehören, in Betracht. Andere Verfahren
(O.Coudert, et at, 1989) untersuchen den Produktautomaten ohne sein Zustandsdiagram explizit zu konstruieren. Die Untersu- chung des Produktautomaten beginnt mit einem Anfangszusta d des Produktautomaten und bei jedem neuen Zustand wird überprüft, ob kein Übergang den Ausgang falsch erzeugt, wodurch ein unter- schiedliches Verhalten der ursprünglichen Automaten angezeigt würde. Bei einer derartigen Untersuchung des Produktautomaten bieten sich grundsätzlich zwei verschiedene Stratetgien zur Buchführung über alle erzeugten Zustände an: Die erste Strategie kann als depth-first Strategie bezeichnet werden (S.Devadas, et, 1988). Diese Strategie hat den Nachteil, daß ihre Komplexität linear mit der Zahl der erreichbaren Zu¬ stände wächst. Aus diesem Grunde können mit Hilfe dieser Strate¬ gie nur Automaten mit einer sehr kleinen Zahl von Zuständen (z.B. 2764 in dem Beispiel in dem Aufsatz von S.Devadas, et al, 1988) verglichen werden. Die zweite mögliche Strategie kann als breadth-first Strategie bezeichnet werden (O.Coudert, et al, 1989). Bei dieser Strategie werden in einem Schritt mehrere Zustände anstelle nur eines Zustandes, wie bie der depth-first Strategie behandelt, so daß diese Strategie von einer effi- zienten Darstellung von Mengen mit Hilfe binärer Entscheidungs¬ diagramme profitieren kann (R.E.Bryant, "Graph-based algorith- mus for boolean function manipulation", IEEE Transactionε Com¬ puter, C-35 (12): 1035-1044, 1966). Die Vorzüge dieses Ver¬ fahrens sind mit Hilfe von Beispielen demonstriert worden, bei denen Automaten mit bis zu 22 Mill. Zuständen verifiziert worden sind. Trotzdem wächst die Komplizität einer breadth- first Untersuchung linear mit der Länge des längsten Zyklus im erreichbaren Teil der Produktmaschine, und deshalb kann eine recht große Klasse interessanter Automaten, wie z.B. Zähler, nicht mit Hilfe eines solchen Verfahrens verglichen werden. Ein anderes Problem des Verfahrens von Coudert et al besteht darin, daß zu der Durchführung dieses Verfahrens zwischen ver¬ schiedenen Darstellungen gewechselt werden muß und daß der Wechsel zwischen diesen Darstellungen Operationen mit exponen- tieller Komplexität erfordert. Um die Probleme, welche mit der Abarbeitung des erreichbaren Zustandsraumes eines Produktautomaten und der adäquaten Darstel¬ lung von Mealyautomaten einhergehen, zu überwinden, wird ein anderes Verfahren verwendet. Aus der Definition der Äquivalenz zweier Zustände bzw. der Äquivalenz zweier Mealyautomaten geht hervor, daß für den Fall, daß zwei nicht äquivalente Zustände existieren es eine endliche Eingangssequenz geben muß, für welche sich die zugehörigen Ausgangssequenzen der beiden Mea- lyautomaten unterscheiden. Es wird daher angenommen, daß in den meisten praktisch interessierenden Fällen eine recht kurze Eingangssequenz existiert, welche diese Eigenschaft hat, da, wenn zwei Zustände nicht äquivalent sind, dies nach einer kur¬ zen Zeit bei Verwendung einer geeigneten Eingangssequenz am Ausgang beobachtbar sein sollte. Anstelle also den gesamten erreichbaren Zustandsraum zu erzeugen und die Äquivalenz aller Zustände zu überprüfen, wie dies bei den Verfahren aus der Li¬ teratur geschieht, wird bei dem erfindungsgemäßen Verfahren die gesamte Relation der nicht äquivalenten Zustände, d.h. das Komplement der Menge der äquivalenten Zustände auf dem Produkt¬ raum der Zustände berechnet. Die Berechnung wird mittels einer Fixpunkt-Iteration durchgeführt, in der nur einfache Operationen auf binären Entscheidungsdiagrammen benötigt werden.
Zur Durchführung dieser Iteration betrachtet man als Ausgangs¬ punkt die Menge aller Zustandspaare, d.h. die Menge aller Zu¬ stände des Produktautomaten der zu überprüfenden Mealy-Auto¬ maten, welche unterschiedliche Ausgangswerte für mindestens ein Eingangsmuster haben. Diese Ausgangsmenge wird nun schritt- weise um diejenigen Zustandspaare erweitert, für welche gilt, daß von ihnen aus unter Anwendung der Übergangsfunktionen der zu verifizierenden Mealyautomaten bzw. der Übergangsfunktion des Produktautomaten die Zustandspaare der Ursprungsmenge in endlich vielen Schritten unter Annahme geeigneter Eingangs- muster erreicht werden könnnen. Diese Iteration endet, falls die dabei erzeugte Menge von Zustandspaaren sich nicht mehr ändert, falls also ein Fixpunkt erreicht wird. Es ist klar aus der Definition der Äquivalenz von Mealyautomaten, daß diese Fixpunktmenge die Menge aller nicht äojivalenten Zustände ist. Es handelt sich also um alle nicht äquivalenten Zustandspaare der zu vergleichenden Mealyautomaten. Diese sind nun äquiva¬ lent, falls ihre Anfangszustände äquivalent sind. Es bleibt also lediglich zu prüfen, ob die Anfangszustände der zu ver¬ gleichenden Mealyautomaten bzw. die aus diesen Zuständen ge¬ bildeten Zustandspaare Elemente der erzeugten Fixpunktmenge sind oder nicht. Dieses Verfahren hat den Vorteil, daß in allen praktisch untersuchten Fällen die Fixpunktmenge bereits nach sehr wenigen Schritten konstruiert ist. Daneben hat dieses Verfahren den Vorteil, daß alle zur Konstruktion der Fixpunkt¬ menge nötigen Operationen sehr effizient mit Hilfe binärer Ent¬ scheidungsdiagramme realisiert werden können. Diese werden in dem Aufsatz von Bryant 1986 detailliert beschrieben (R.E. Bryant, "Graph based algorithmus for boolean function manipu- lation", IEEE Trans. Computer, C-35 (12): 1035-1044, 1986).
Bei synchronen sequentiellen Digitalschaltungen sind die Zu¬ stände und Eingangs- bzw. Ausgangssignale der diese Schalt- kreise modellierenden Mealyautomaten boolesche Vektoren und die Ausgangs- und Übergangsfunktionen sind als vektorwertige boolesche Funktionen definiert, deren Argumente boolesche Vektoren sind. Zur Darstellung solcher booleschen Funktionen und der Operationen auf ihnen wurden von Bryant (R.E.Bryant 1986) die binären Entscheidungsdiagramme (BODS) eingeführt.
Binäre Entscheidungsdiagramme haben vorteilhafte Eigenschaften nur für bestimmte Klassen boolescher Funktionen, da die Größe eines binären Entscheidungsdiagramms, welches eine boolesche Funktion darstellt, schlimmstenfalls eine expondentiell wach- sende Funktion der Zahl der Argumente dieser booleschen Funk¬ tion ist. Andererseits haben empirische Untersuchungen ergeben, daß boolesche Funktionen, welche durch kombinatorische oder sequentielle Digitalschaltungen realisiert werden, kompakte Darstellungen durch binäre Entscheidungsdiagramme haben und dal? binäre Entscheidungsdiagramme vorteilhaft zur Darstellung sequentieller Digitalschaltungen eingesetzt werden können.
In dem oben beschriebenen Fixpunktiterationsverfahren zur Erzeugung der Relation der nicht äquivalenten Zustände zweier Mealyautomaten wird eine Methode zur Darstellung der Mengen, welche im Laufe des Fixpunktiterationsverfahrens erzeugt wer¬ den benötigt. Diese Mengen sind Relationen über dem kartesi- sehen Produkt der Zustandsräume beider Mealyautomaten, d.h. Teilmengen eines binären Einheitswürfels entsprechender Dimen¬ sionen. Jede Teilmenge U eines k-dimensionalen binären Würfels kann durch ihre charakteristische Funktion beschrieben werden, welche jedem Punkt des binären Würfels, welcher zugleich Ele- ent der Menge U ist, den Wert 1 zuordnet und allen anderen
Elementen des Würfels den Wert 0. Dabei entspricht die charak¬ teristische Funktion einer Durchschnittsmenge zweier Mengen der UND-Verknüpfung beider charakteristischen Funktionen die¬ ser Mengen, die charakteristische Funktion einer Vereinigungs- menge der ODER-Verknüpfung und die charakteristische Funktion einer Diferenzbildung der UND-Verknüpfung der charakteristi¬ schen Funktionen der Ausgangsmenge mit der charakteristi¬ schen Funktion des Komplements der subtrahierten Menge. In dem Aufsatz von J.R.Burch, et al, "Sequential cireuit verification using symbolic model checking", in ACM/IEEE Desgin Automation Conference, 1990, wird anstelle der Übergangsfunktion die entsprechende Übergangsrelation zur Modellierung einer syn¬ chronen sequentiellen Digitalschaltung verwendet. Diese Über¬ gangsrelation wird mit Hilfe eines binären Entscheidungsdia- gramms der charakteristischen Funktion dieser Übergangsrelation dargestellt. Empirische Untersuchungen haben gezeigt, daß die Darstellung synchroner sequentieller Digitalschaltungen und kombinatorischer Digitalschaltungen mit Hilfe funktionaler Vektoren binärer Entscheidungsdiagramme Vorteile gegenüber einer Darstellung in Form von charakteristischen Funktionen hat, da sie offenbar in der Lage ist, Schaltkreise höherer Komplexität darzustellen.
Auf der Basis der Darstellung von Mealyautomaten und Relationen mit Hilfe von booleschen Funktionen und damit durch binäre
Entscheidungsdiagramme wird nun die Realisierung des Fixpunkt¬ verfahrens zur Berechnung der Relation der nicht äαuivalenten Zustände zweier Mealyautomaten beschrieben. Der erste Schritt zur Vorbereitung der Fixpunktiteration besteht in der Berech¬ nung der Ausgangsrelation MO, zu welcher alle Zustandspaare, welche aus zwei Zuständen der beiden Mealyautomaten gebildet sind, gehören, für welche gilt, daß mindestens ein Eingangs¬ signal existiert, für welches die Ausgangsfunktionen der beiden Mealyautomaten für die beiden Zustände verschiedene Werte annehmen. Sind die Ausgangsfunktionen der beiden Mealyautomaten als Vektoren binärer Entscheidungsdiagramme gegeben, kann die charakteristische Funktion der Ausgangsrelation einfach berech¬ net werden.
Dazu werden aus den Vektoren von binären Entscheidungsdiagra - men für die Ausgangsfunktionen für jeden einzelnen Ausgang die zugehörigen binären Entscheidungsdiagramme "EXOR" verknüpft. Für jeden Ausgang wird also ein binäres Entscheidungsdiagramm berechnet, welches für genau die Zustandspaare und Eingangssignεl den Wert "wahr" liefert für die dieser Ausgang in beiden Mealy- automaten einen unterschiedlichen Wert liefert. Auf jedes die¬ ser binären Entscheidungsdiagramme wird anschließend ein Exi¬ stenzoperator bezüglich der Eingänge angewandt. Ein so berech¬ netes binäres Entscheidungsdiagramm gibt genau für die Paare von Zuständen den Wert "wahr", für welche mindestens ein Eingabe- signal existiert, so daß das ursprüngliche binäre Entscheidungs¬ diagramm den Wert "wahr" liefert, also der Ausgang einen unter¬ schiedlichen Wert liefert. Der Existenzoperator auf einem binären Entscheidungsdiagramm bezüglich einer Menge von Eingängen kann sukzessive durch den Existenzoperator bezüglich eines einzelnen Eingangs berechnet werden. Dazu wird auf das ursprüngliche binäre Entscheidungsdiagramm der Existenzoperator bezüglich des erster. Eingangs berechnet. Auf das entstandene binäre Entscheidungsdiε- gram wird der Existenzoperator bezüglich des zweiten Eingangs berechnet. Dieses Verfahren wird bis zum letzten Eingang fort- gesetzt. Zur Berechnung eines Existenzoperators bezüglich eines Eingangs wird in dem binären Entscheidungsdiagramm der Eingang durch "wahr" bzw. "falsch" substituiert und die beiden ent- stehenden binären Entscheidungsdiagramme werden "ODER" ver¬ knüpft. Der Existenzoperator ist also auf einfache Substitution und "ODER"-Verknüpfung zurückführbar. Nach Anwendung des Exi- stenzoperators werden die für die einzelnen Ausgänge entstande¬ nen binären Entscheidungsdiagramme noch alle "ODER" verknüpft und das Ergebnis ist ein binäres Entscheidungsdiagramm, welches die charakteristische Funktion für MO darstellt. Eine explizite Berechnung der Zwischenergebnisse ist nicht unbedingt erforder- lieh, sondern die gesamte oben beschriebene Berechnung von MO aus den Vektoren von binären Entscheidungsdiagrammen für die Ausgangsfunktionen kann auch zu einem einzigen Schritt ver¬ schmolzen werden.
Die Ausgangsrelation MO ist der Ausgangspunkt der Fixpunktite¬ ration, welche aus der Ausgangsrelation weitere Relationen be¬ rechnet.
Während des Ablaufs des Iterationsverfahrens wird die cha- rakteristische Funktion der zwischendurch auftretenden Re¬ lationen M(i) aus den vorhergehenden charakteristischen Funk¬ tionen durch folgende Schritte berechnet:
In dem binären Entscheidungsdiagramm der charakteristischen Funktion für M(i) werden die Zustände durch die binären Ent¬ scheidungsdiagramme ihrer Zustandsübergangsfunktionen ersetzt. Dies entspricht der Substitution von Variablen in binären Ent¬ scheidungsdiagrammen durch binäre Entscheidugnsdiagramme. Das berechnete binäre Entscheidungsdiagramm gibt für jedes Paar von Zuständen und jedes Eingabesignal genau dann den Wert
"wahr", wenn die Nachfolgezustände der betrachteten Zustände unter der Wirkung der Übergangsfunktion der Mealy-Automaten die Eigenschaft haben, daß die charakteristische Funktion der Rela¬ tion M(i) dieses Iterationsschrittes den Wert "wahr" besitzt. Auf das berechnete binäre Entscheidungsdiagramm wird der Exi¬ stenzoperator bezüglich der Eingangssignale angewandt und das Ergebnis mit dem binären Entscheidungsdiagramm der charakteri- stischen Funktion der Relation M(i) "ODER" verknüpft, die Relation M(i) wird also um genau die Paare von Zuständen erweitert, für welche mindestens ein Eingabesignal existiert, so daß die Nachfolgezustände in der Relation M(i) enthalten sind. Zur Durchführung des Iterationsschrittes sind also lediglich Einsetzung, d.h. Substitution undf."ODER"-Verknü- pfung auf binären Entscheidungsdiagrammen erforderlich, da der Existenzoperator wie vorherbeschrieben auf Substition und nODER"-Verknüpfung zurückgeführt werden kann. Eine expli¬ zite Berechnung der Zwischenergebnisse ist nicht unbedingt erforderlich, sondern die gesamte oben beschriebene Berech¬ nung kann zu einer einzigen Operation verschmolzen werden.
Im Effekt sind diese Operationen gleichwertig zu einer Vereini¬ gung von Teilmengen des Produktzustandsraumes, bei der die Menge M(i), welche die Relation dieses Iterationsschrittes repräsentiert, mit der Menge der Vorgänger-Zustandspaare unter der Wirkung der Übergangsfunktionen der zu vergleichenden Mea- ly Automaten vereinigt wird, um die Menge M(i+1) zu erhalten, welche die Relation des nachfolgenden Iterationsschrittes repräsentiert.
Das Iterationsverfahren bricht ab, wenn ein Iterationsschritt zu keiner Veränderung der Relation führt. Um dies festzustel¬ len, ist ein einfacher Vergleich zweier aufeinander folgender binärer Entscheidungsdiagramme, welche die charakteristischen Funktionen der Relationen darstellen, erforderlich.
Die zu vergleichenden Mealy-Automaten sind dann äquivalent, wenn ihre Anfangszustände nicht zur Relation M der nichtäquiva¬ lenten Zustände gehören.
Die Kombination der Darstellung von Mealyautomaten mit Hilfe von Vektoren von Funktionen, d.h. binärer Entscheidungs¬ diagramme, und der Darstellung von Mengen durch ihre charak¬ teristischen Funktionen kann mit Hilfe der obigen Substitionen einfach und elegant ausgeführt werden. Das Verfahren von Coudert et al (O.Coudert 1989) benötigt eine explizite Über¬ führung der beiden Darstellungen ineinander, obwohl damit Opera- tionen von exponentieller Komplexität verbunden sind. Das Ite¬ rationsverfahren kommt zum Stillstand, falls die erzeugten Mengen bzw. Relationen zwischen zwei Iterationschritten identisch sind. Diese Identität wird durch Auswertung der binären Entscheidungsdiagramme der charakteristischen Funk- tionen, welche diese Mengen repräsentieren durchgeführt.
Damit ist die Realisierung des gesamten Fixpunktverfahrens auf der Grundlage binärer Entscheidungsdiagramme beschrieben. Die einzigen Operationen auf binären Entscheidungsdiagrammen, welche innerhalb der Fixpunktiteration benötigt werden, sind die booleschen Funktionen "ODER" bzw. "ungleich" und die Er¬ setzung (Substitution) von Variablen boolescher Funktionen bzw. von Entscheidungsdiagrammen.

Claims

Patentansprüche
1. Verfahren zur Verifikation datenverarbeitender Systeme, bei dem a) zwei unabhängig voneinander erstellte Beschreibungen eines zu verifizierenden Systems als Mealy-Automaten oder dazu gleichwertig repräsentiert und miteinander verglichen werden; b) der Vergleich mit Hilfe eines Fixpunktiterationsverfahrens durchgeführt wird, welches die Menge M aller nicht äquivalenten
Zustandspaare aus Zuständen der beiden Mealy-Automaten erzeugt; c) Äquivalenzrelationen zwischen Zuständen, Ausgangs- und Über¬ gangsfunktionen von Mealy-Autoamten durch binäre Entscheidungs¬ diagramme oder hierzu äquivalente Mittel dargestellt werden; d) in jedem Schritt der Fixpunktiteration lediglich boolesche Operationen und Substitionen auf binäre Entscheidungsdiagramme angewendet werden.
2. Verfahren nach Anspruch 1, bei dem die datenverarbeitenden Systeme digitale Schaltungen sind.
3. Verfahren nach Anspruch 2, bei dem die zu verifizierende Digitalschaltung in Form zweier Netzlisten beschrieben ist.
4. Verfahren nach Anspruch 2, bei dem die zu verifizierende Digitalschaltung in Form einer Netzliste und mit Hilfe einer Hardware-Beschreibungssprache beschrieben ist.
5. Verfahren nach Anspruch 1, bei dem die datenverarbeitenden Systeme Kommunikationsprotokolle sind.
6. Verfahren nach Anspruch 1, bei dem die datenverarbeitenden Systeme Computerprogramme sind.
7. Verfahren nach Anspruch 1, bei dem die datenverarbeitenden Systeme Mikroprogramme sind.
8. Verfahren nach einem der vorhergehenden Ansprüche, bei dem
- zunächst die Menge MO aller Zustandspaare erzeugt wird, welche für mindestens einen Satz von Eingangswerten minde¬ stens einen verschiedenen Ausgangswert erzeugen;
- die Menge MO erweitert wird um die Menge aller Zustands¬ paare, welche in endlich vielen Schritten der beiden Mealy- Automaten auf ein Zustandspaar führen, das der Menge MO ange- hört.
PCT/EP1992/000789 1991-04-17 1992-04-07 Verfahren zur verifikation datenverarbeitender systeme Ceased WO1992018944A1 (de)

Priority Applications (3)

Application Number Priority Date Filing Date Title
EP92908193A EP0580663B1 (de) 1991-04-17 1992-04-07 Verfahren zur verifikation datenverarbeitender systeme
US08/133,208 US5491639A (en) 1991-04-17 1992-04-07 Procedure for verifying data-processing systems
DE59201155T DE59201155D1 (de) 1991-04-17 1992-04-07 Verfahren zur verifikation datenverarbeitender systeme.

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP91106157.0 1991-04-17
EP91106157 1991-04-17

Publications (1)

Publication Number Publication Date
WO1992018944A1 true WO1992018944A1 (de) 1992-10-29

Family

ID=8206633

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP1992/000789 Ceased WO1992018944A1 (de) 1991-04-17 1992-04-07 Verfahren zur verifikation datenverarbeitender systeme

Country Status (4)

Country Link
US (1) US5491639A (de)
EP (1) EP0580663B1 (de)
DE (1) DE59201155D1 (de)
WO (1) WO1992018944A1 (de)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0653716A1 (de) * 1993-11-02 1995-05-17 Bull S.A. Verfahren zur Prüfung eines sequentiellen Endlichautomaten und resultierender Informationsträger und Prüfungwerkzeug
WO1999050766A1 (de) * 1998-03-30 1999-10-07 Siemens Aktiengesellschaft Verfahren zum vergleich elektrischer schaltungen

Families Citing this family (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6185516B1 (en) * 1990-03-06 2001-02-06 Lucent Technologies Inc. Automata-theoretic verification of systems
WO1998040796A1 (de) * 1997-03-11 1998-09-17 Siemens Aktiengesellschaft Verfahren zur rechnergestützten fehleranalyse von sensoren und/oder aktoren in einem technischen system
US6035109A (en) * 1997-04-22 2000-03-07 Nec Usa, Inc. Method for using complete-1-distinguishability for FSM equivalence checking
US6816821B1 (en) * 1997-09-03 2004-11-09 Stmicroelectronics Limited Post image techniques
US6339837B1 (en) 1998-02-25 2002-01-15 Zhe Li Hybrid method for design verification
US6247165B1 (en) 1998-03-31 2001-06-12 Synopsys, Inc. System and process of extracting gate-level descriptions from simulation tables for formal verification
US6148436A (en) * 1998-03-31 2000-11-14 Synopsys, Inc. System and method for automatic generation of gate-level descriptions from table-based descriptions for electronic design automation
US6496955B1 (en) * 2000-06-16 2002-12-17 Sun Microsystems, Inc. Latch mapper
US20050192789A1 (en) * 2000-06-30 2005-09-01 Jin Yang Methods for formal verification on a symbolic lattice domain
US7031896B1 (en) 2000-06-30 2006-04-18 Intel Corporation Methods for performing generalized trajectory evaluation
US6725431B1 (en) 2000-06-30 2004-04-20 Intel Corporation Lazy symbolic model checking
US6591400B1 (en) 2000-09-29 2003-07-08 Intel Corporation Symbolic variable reduction
US6643827B1 (en) * 2000-09-30 2003-11-04 Intel Corporation Symbolic model checking with dynamic model pruning
US6957178B2 (en) * 2001-10-29 2005-10-18 Honeywell International Inc. Incremental automata verification
JP4033722B2 (ja) * 2002-06-20 2008-01-16 富士通株式会社 論理回路の論理的な等価検証方法及び装置
US8306802B2 (en) * 2006-11-02 2012-11-06 Synopsys, Inc. Method for modeling an HDL design using symbolic simulation
US20230244955A1 (en) * 2022-01-31 2023-08-03 Mirela Grujic Decision Diagram-Based Management of a Computer System or its Part

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3943350A (en) * 1974-10-18 1976-03-09 Sperry Rand Corporation Radix converter utilizing automata
US4876640A (en) * 1986-02-07 1989-10-24 Advanced Micro Devices, Inc. Logic controller having programmable logic "and" array using a programmable gray-code counter
US4933897A (en) * 1986-02-07 1990-06-12 Advanced Micro Devices, Inc. Method for designing a control sequencer
IL78542A0 (en) * 1986-04-18 1986-08-31 Yeda Res & Dev Electronic controller based on the use of statecharts as an abstract model
DE3804266A1 (de) * 1988-02-11 1989-09-14 Leitz Wild Gmbh Gray-code-wandler mit fehlersignal
US5243538B1 (en) * 1989-08-09 1995-11-07 Hitachi Ltd Comparison and verification system for logic circuits and method thereof
US5231590A (en) * 1989-10-13 1993-07-27 Zilog, Inc. Technique for modifying an integrated circuit layout
US5287289A (en) * 1990-04-13 1994-02-15 Hitachi, Ltd. Logic synthesis method
US5258919A (en) * 1990-06-28 1993-11-02 National Semiconductor Corporation Structured logic design method using figures of merit and a flowchart methodology
US5331568A (en) * 1991-06-18 1994-07-19 Microelectronics & Computer Technology Corporation Apparatus and method for determining sequential hardware equivalence

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
IEEE INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN 11-15 NOVEMBER 1990 SANTA CLARA US Seiten 126 - 129; COUDERT: 'A UNIFIED FRAMEWORK FOR THE FORMAL VERIFICATION OF SEQUENTIAL CIRCUITS' *
PROCEEDINGS OF THE IMEC-IFIP INTERNATIONAL WORKSHOP ON APPLIED FORMAL METHODS FOR CORRECT VLSI DESIGN 13-16 NOVEMBER 1989 HOUTHALEN BELGIUM Seiten 111 - 128; COUDERT ET AL: 'VERIFICATION OF SEQUENTIEL MACHINES USING BOOLEAN FUNCTIONAL VECTORS' in der Anmeldung erwähnt *

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0653716A1 (de) * 1993-11-02 1995-05-17 Bull S.A. Verfahren zur Prüfung eines sequentiellen Endlichautomaten und resultierender Informationsträger und Prüfungwerkzeug
WO1999050766A1 (de) * 1998-03-30 1999-10-07 Siemens Aktiengesellschaft Verfahren zum vergleich elektrischer schaltungen
US6557146B1 (en) 1998-03-30 2003-04-29 Siemens Aktiengesellschaft Method for the comparison of electrical circuits

Also Published As

Publication number Publication date
DE59201155D1 (de) 1995-02-16
US5491639A (en) 1996-02-13
EP0580663B1 (de) 1995-01-04
EP0580663A1 (de) 1994-02-02

Similar Documents

Publication Publication Date Title
EP0580663B1 (de) Verfahren zur verifikation datenverarbeitender systeme
DE69838835T2 (de) Verfahren zur Prüfung und zur Darstellung einer Hardware durch Zerlegung und Aufteilung
DE3689228T2 (de) Verfahren zur Modellierung und zur Fehlersimulation von komplementären Metalloxidhalbleiterschaltungen.
DE69212673T2 (de) Prüfmustererzeugungseinrichtung
EP1425638B1 (de) Verfahren zur validierung von simulationsergebnissen eines systems sowie darauf aufbauender äquivalenzvergleich digitaler schaltungen
DE3856079T2 (de) Verfahren für einen Blockdiagramm-Simulator
DE19860061B4 (de) System zur Prüfung der kombinatorischen Äquivalenz
DE3787431T2 (de) Verfahren zur Generierung einer Kandidatenliste von fehlerhaften Schaltungselementen und Verfahren zur Isolierung von Fehlern in einer logischen Schaltung unter Verwendung dieser Kandidatenliste.
DE69223787T2 (de) System fuer qualitative schlussfolgerung mit paralleler verarbeitung
DE69225527T2 (de) Verfahren und System zur automatischen Bestimmung der logischen Funktion einer Schaltung
EP1127323A1 (de) Verfahren und anordnung zum vergleich einer ersten eigenschaft mit vorgegebenen eigenschaften eines technischen systems
DE19717716A1 (de) Verfahren zur automatischen Diagnose technischer Systeme unter Berücksichtigung eines effizienten Wissenserwerbs und einer effizienten Bearbeitung zur Laufzeit
DE2515297A1 (de) Pruefsystem fuer logische netzwerke mit simulatororientiertem fehlerpruefgenerator
EP1764715B1 (de) Verfahren zur Bestimmung der Güte einer Menge von Eigenschaften, verwendbar zur Verifikation and zur Spezifikation von Schaltungen
DE10127337A1 (de) Verfahren und Vorrichtung zum Erzeugen von beim Testen von Halbleiter-ICs verwendeten Testmustern
DE3338333A1 (de) Logiksimulatorgeraet zur gueltigkeitspruefung einer logikstruktur
DE60005670T2 (de) Aktualisierung der platzierung während der technologieabbildung
DE69326072T2 (de) Verfahren zur Prüfung eines sequentiellen endlichen Automaten
DE102016119991A1 (de) Emulation von Taktjittern
DE10296464T5 (de) Verfahren und Gerät zur Validierung des Entwurfes einer komplexen integrierten Schaltungen
DE69127798T2 (de) Verfahren und Gerät zum Organisieren und Analysieren von Zeitsteuerungsinformationen
DE10038499A1 (de) Verfahren und System für die verbesserte Entwicklungsprüfung mittels angepasster Ablaufverfolgung
DE112018006331B4 (de) Testfallgenerierungsvorrichtung, Testfallgenerierungsverfahren und Testfallgenerierungsprogramm
DE60204535T2 (de) Optimierungsverfahren einer Prüfsequenz für digitale integrierte Schaltungen
DE69219662T2 (de) Verfahren zur On-Line-Modifizierung von komprimierten digitalen Prüfvektoren

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB GR IT LU MC NL SE

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
WWE Wipo information: entry into national phase

Ref document number: 1992908193

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 08133208

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 1992908193

Country of ref document: EP

WWG Wipo information: grant in national office

Ref document number: 1992908193

Country of ref document: EP