Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

To make it simple assume you have only AND and OR gates. Each has two inputs and one output. The output of two inputs can be used as an input for the next gate For example:

A AND B -> E

C AND D -> F

E OR F -> G

Assuming an arbitrary number of gates, we want to check if the circuit ever connects back into itself at an earlier state? For example:

E AND F -> A

This should be illegal since it creates an endless cycle. What design pattern would best be able to check for these cycles?

share|improve this question
10  
The first time you model a flip-flop, you're going to discover why cycles in logic circuits are not only legal but important. –  Blrfl Nov 2 '12 at 14:56

2 Answers 2

up vote 3 down vote accepted

Looks like you are talking about building a directed graph and checking for cycles. This can be done in many ways. The most basic is a topological sort.

http://stackoverflow.com/questions/583876/how-do-i-check-if-a-directed-graph-is-acyclic
or
http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph

share|improve this answer

As @Blrfl pointed out, feedback in logic circuits is extremely useful. The way to deal with it in a model is to add a time component, essentially representing the propagation delay through the gate. For example:

A AND B -> B

The way you deal with this is to consider B at time 0 and B at time 1 as two completely different signals, like:

A[0] AND B[0] -> B[1]

This lets you do your calculations without entering an endless loop. Note that in this case you only have to do one iteration to determine the steady state (what it eventually settles down to). If A is 1, B won't change from its initial value. If A is 0, then B will also change to 0 and stay there.

share|improve this answer
2  
Even on simple combinatorial circuits and using the propagation delay as your time increment, you have to iterate once for every gate between the inputs and the outputs before you come up with something "right." In the OP's case, line G won't be valid for two iterations. Some circuits never reach a stable state: loop the output of a NOR gate back into one input (or both inputs of a NAND) and the output will change state continuously. More complex circuits are clocked to regulate that behavior. –  Blrfl Nov 2 '12 at 21:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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