2
$\begingroup$

I was asked to model the following sequential circuits C1, C2 as transition systems (i.e. identify the output y function and register functions r1, r2, r3)

enter image description here

For C2 there appears to be not input x and only output y with a register R3. I assumed that there would be two possible states R3 = 0, R3 = 1 and then Y2 = !R3. But then what is the register function for R3?

For C1 I really had no idea how approach the problem as it was just an intimidating maze and while I thought it may be possible to break the circuit up and try find the functions that way, I wasn't sure. I would like to know how I can find the output and register functions of these circuits

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Welcome to CS.SE! Please ask only one question per post. I recommend you ask about only one of these two circuits (probably C2); the answer to one might enable you to solve the other. Also, can you define what you mean by "register function"? What is your definition of transition system? The standard definition of transition system doesn't have any notion of an output function or register function: en.wikipedia.org/wiki/Transition_system, en.wikipedia.org/wiki/Kripke_structure_(model_checking). $\endgroup$
    – D.W. ♦
    Commented Sep 16, 2016 at 14:20
  • $\begingroup$ I agree with @D.W. -- it's a valid point and question should be formulated more carefully. Nevertheless, my answer assumes the traditional approach of modelling sequential circuits as transition systems, usually covered in materials on model checking. $\endgroup$
    – ivcha
    Commented Sep 26, 2016 at 5:35

1 Answer 1

Reset to default
2
$\begingroup$

To build a transition system from a sequential circuit, in general, one needs to define three components:

  1. the states of the transition system, which are all possible combinations of values of your inputs and registers in the circuit

  2. transitions between states in the transition system, which result from the functions that determine the output and the registers (according to used logical circuits and wire connections)

  3. labels for states in the transition system, which consist of all variables and registers that are evaluated true given the valuations in the circuit

As per the (contrived) circuit in C2, the states reflect only the possible values of the single register. In turn, the function of the output equals to the register (Y2=R3), while the current value of the register is the negation of its previous value. This should give you enough insights to build the transition system.

The circuit given in C1 is indeed more convoluted, but it can be decomposed into functions on how values (for the registers and the output Y1) change, which then can be used to derive possible transitions in the system. (This is done with respect to possible changes of the input X.) For example, Y1 = R1 && R2 and the form for the value of R1 is R1 = (X AND ...) OR (... AND ...), while the missing values ... can be traced down according to the wire connections of the circuit.

More details on modelling sequential circuits as transition systems can be found in [1].

[1] Baier, Christel, Joost-Pieter Katoen, and Kim Guldstrand Larsen. Principles of model checking. MIT press, 2008.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.