0
$\begingroup$

Take the following digital logic circuit for example:

Digital Logic Circuit with Infinite Loop

I'd like to represent this digital logic circuit with the following constructs:

  1. truth table
  2. Karnaugh map
  3. function

You'll notice from the image that there is an infinite loop. I'm trying to find a way to analyse/represent these algorithmically, but it's proving to be quite complicated.

I've tried combining the truth tables of each individual logic gate, but the results don't show the loop very well. Karnaugh maps are relatively simple to generate, given truth tables with no loops, but that doesn't do me much good here. Creating a function for this is also very difficult.

Any help in the right direction here would be greatly appreciated. Thanks!

$\endgroup$
1
  • $\begingroup$ @Moo - The image above is from a simple logic simulator. I understand the logic itself, I'm simply trying to figure out how to represent that logic in different ways. $\endgroup$
    – Zooce
    Commented Sep 25, 2016 at 4:57

2 Answers 2

1
$\begingroup$

enter image description here

Assume that the time delay from input to output is the same and constant for all gates (completely unrealistic for non clocked gates).

$X[n]$ is the value at time step $n$.

$$C[n+1] = A[n] \wedge E[n] \tag{1}$$ $$D[n+1] = B[n] \vee C[n] \tag{2}$$ $$E[n+1] = C[n] \oplus D[n] \tag{3}$$

We want to express $E[n+1]$ , the next $E$ in terms of $E,A,B$

Substitute $(1)$ into $(2)$ to get rid of $C$

$$ D[n+1] = B[n] \vee (A[n-1] \wedge E[n-1]) \tag{4} $$

Substitute $(1)$ and $(4)$ into $(3)$

$$E[n+1] = (A[n-1] \wedge E[n-1]) \oplus (B[n-1] \vee (A[n-2] \wedge E[n-2])) \tag{5}$$

Oscillation:

if $A = B = 1$ and $E = 0$ initially then $C = 0$, $D=1$.

Then $E$ becomes $1$.

At the next step $C=1$. $C=D=1$ which then makes $E = 0$.

At the next step $C=0$.

At the next step $E = 1$.

The conditions repeat and $E$ oscillates.

Using the equation for $E[n+1]$. $A[n] = 1$ and $B[n] = 1$.

$$E[n+1] = (1 \wedge E[n-1]) \oplus (1 \vee (1 \wedge E[n-2])) \tag{6}$$

$$E[n+1] = E[n-1] \oplus 1 \tag{7}$$

A xor with $1$ is an inversion, setting up an oscillation.

$A = 0$:

$$E[n+1] = (0 \wedge E[n-1]) \oplus (B[n-1] \vee (0 \wedge E[n-2])) \tag{8}$$

$$E[n+1] = B[n-1] \tag{9}$$

$\endgroup$
2
  • $\begingroup$ thinking of this problem in terms of time steps definitely helps with respect to the functional representation of this logical circuit. I am having a bit of trouble translating this idea into a more generic one, so I could apply these steps algorithmically to any logical circuit. $\endgroup$
    – Zooce
    Commented Sep 27, 2016 at 2:30
  • $\begingroup$ @Zooce - Its a discrete time system but the operations are not addition and multiplication they are logical operations. In general you label each node in the circuit then write the equation of each gate output[n+1] = function(inputs[n]). Each gate is given one unit of time delay. Then try to isolate the output in terms of the inputs. $\endgroup$
    – user186104
    Commented Sep 27, 2016 at 2:50
0
$\begingroup$

You can define the upper input as $A$, the lower as $B$, the output of the AND gate as $C$, the output of the OR gate as $D$, and the output of the XOR as $E$, which is the output of the circuit. When you have feedback from a later stage to an earlier stage, there is no guarantee that there is a unique output for a given input. One approach is to iterate-compute the output of each gate in turn. When the gate takes its input from a later stage, you just make it up to start. Then keep computing. You are looking for stability. In the case of this circuit, I find the output is just $B$. I made a spreadsheet showing each value and recalculated $C, D, E$ in order to convergence. For this circuit, convergence was achieved quickly.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .