Span(Graph) III: Circuits with feedback
Previous post in this series; next post in the series.
The two main operations in $\bf Circ$ are composition and parallel as for straight-line circuits, and there are a variety of constants.
Today we describe the operation of composition of circuits with feedback in $\bf Circ$.
$\bf Composition$ If $G$ is a component with left interface $B^m$ and right interface $B^n$ (an arrow in $\bf Circ$ from $B^m$ to $B^n$) and $H$ is a component from $B^n$ to $B^p$ then the composition denoted $G\bullet H$ has left interface $B^m$ and right $B^p$. The graph of $G\bullet H$ has states being all pairs $(x,y)$ of states, one $x$ of $G$ and one $y$ of $H$. A transition in $G\bullet H$ is a pair of transitions $(\alpha,\beta)$, one of $G$ and one of $H$, which however must satisfy the following requirement: the $n$-tuple of right labels of $\alpha$ must equal the $n$-tuple of left labels of $\beta$.
This is just the obvious requirement that for both components to change state the signals on the connected ports must be equal.
It remains to say what are the left and right labellings of transitions of the composite. The left labelling of a transition $(\alpha,\beta)$ is the left labelling of $\alpha$, and the right labelling of $(\alpha,\beta)$ is the right labelling of $\beta$.
The picture of the composite will be the two components joined side-by-side with the right ports of $G$ joined to the left ports of $H$.
To make sure that the definition is clear we will calculate the composite of two delay elements.
(I notice that I did not say that the delay component is an arrow in $\bf Circ$ from $B$ to $B$ - I hope that was obvious.)
The states of this composite are the four pairs of states, namely $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ which I will write more briefly as $00$, $01$, $10$, $11$ to reduce clutter.
There are $16$ candidates for transitions, namely all pairs of transitions but not all satisfy the condition that the labels on the common ports are equal.
One transition of the composite comes from the pair $(0\xrightarrow{1/0}1, 1\xrightarrow{0/1}0)$ since these two transitions have the common signal $0$ on the middle wire.
This transition of the composite is then $01\xrightarrow{1/1}10$; that is it goes from state $01$ to state $10$, with the labelling being the labels of the free ports.
A pair which does not give rise to a transition of the composite is $(0\xrightarrow{1/0}1, 1\xrightarrow{1/1}1)$ since the labels on the middle wire do not agree.
I will list all the transitions which do occur in the composite:
$00\xrightarrow{0/0}00$, $00\xrightarrow{1/0}10$, $01\xrightarrow{0/1}00$, $01\xrightarrow{1/1}10$, $10\xrightarrow{0/0}01$, $10\xrightarrow{1/0}11$, $11\xrightarrow{0/1}01$, $11\xrightarrow{1/1}11$.
Here is the resulting component:
You may think of a state as the state of a 2-bit register. On a transition the first bit moves to the second place, the second bit exits as a right signal, and the left signal is inserted in the first bit of the register. The result is a step 2 delay. It is easy to generalize this to the composite of $n$ delay elements: states are the states of a $n$ bit register; on a transition all the bits are moved to the right by one place, the last bit exits as a right signal, and the left signal is recorded in the first place. All this occurs in one transition of the composed $n$ delays.
$\bf A\; very\; important\; remark!$ The delay element is a very particular component in which the left signal drives the component into a new state, and the state determines the right signal. We will be soon dealing with components which are quite different, in which the left hand ports are nothing like input ports and in which the the signals on the ports do not determine the transitions.
You should not think (in general) of components having input and output ports. Instead you should think that the component has its own transitions, and that the left and right signals are a reflection of the transitions of the component on the interfaces.
The two main operations in $\bf Circ$ are composition and parallel as for straight-line circuits, and there are a variety of constants.
Today we describe the operation of composition of circuits with feedback in $\bf Circ$.
$\bf Composition$ If $G$ is a component with left interface $B^m$ and right interface $B^n$ (an arrow in $\bf Circ$ from $B^m$ to $B^n$) and $H$ is a component from $B^n$ to $B^p$ then the composition denoted $G\bullet H$ has left interface $B^m$ and right $B^p$. The graph of $G\bullet H$ has states being all pairs $(x,y)$ of states, one $x$ of $G$ and one $y$ of $H$. A transition in $G\bullet H$ is a pair of transitions $(\alpha,\beta)$, one of $G$ and one of $H$, which however must satisfy the following requirement: the $n$-tuple of right labels of $\alpha$ must equal the $n$-tuple of left labels of $\beta$.
This is just the obvious requirement that for both components to change state the signals on the connected ports must be equal.
It remains to say what are the left and right labellings of transitions of the composite. The left labelling of a transition $(\alpha,\beta)$ is the left labelling of $\alpha$, and the right labelling of $(\alpha,\beta)$ is the right labelling of $\beta$.
The picture of the composite will be the two components joined side-by-side with the right ports of $G$ joined to the left ports of $H$.
To make sure that the definition is clear we will calculate the composite of two delay elements.
(I notice that I did not say that the delay component is an arrow in $\bf Circ$ from $B$ to $B$ - I hope that was obvious.)
The states of this composite are the four pairs of states, namely $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ which I will write more briefly as $00$, $01$, $10$, $11$ to reduce clutter.
There are $16$ candidates for transitions, namely all pairs of transitions but not all satisfy the condition that the labels on the common ports are equal.
One transition of the composite comes from the pair $(0\xrightarrow{1/0}1, 1\xrightarrow{0/1}0)$ since these two transitions have the common signal $0$ on the middle wire.
This transition of the composite is then $01\xrightarrow{1/1}10$; that is it goes from state $01$ to state $10$, with the labelling being the labels of the free ports.
A pair which does not give rise to a transition of the composite is $(0\xrightarrow{1/0}1, 1\xrightarrow{1/1}1)$ since the labels on the middle wire do not agree.
I will list all the transitions which do occur in the composite:
$00\xrightarrow{0/0}00$, $00\xrightarrow{1/0}10$, $01\xrightarrow{0/1}00$, $01\xrightarrow{1/1}10$, $10\xrightarrow{0/0}01$, $10\xrightarrow{1/0}11$, $11\xrightarrow{0/1}01$, $11\xrightarrow{1/1}11$.
Here is the resulting component:
You may think of a state as the state of a 2-bit register. On a transition the first bit moves to the second place, the second bit exits as a right signal, and the left signal is inserted in the first bit of the register. The result is a step 2 delay. It is easy to generalize this to the composite of $n$ delay elements: states are the states of a $n$ bit register; on a transition all the bits are moved to the right by one place, the last bit exits as a right signal, and the left signal is recorded in the first place. All this occurs in one transition of the composed $n$ delays.
$\bf A\; very\; important\; remark!$ The delay element is a very particular component in which the left signal drives the component into a new state, and the state determines the right signal. We will be soon dealing with components which are quite different, in which the left hand ports are nothing like input ports and in which the the signals on the ports do not determine the transitions.
You should not think (in general) of components having input and output ports. Instead you should think that the component has its own transitions, and that the left and right signals are a reflection of the transitions of the component on the interfaces.
Labels: computing
posted by Unknown at 1:31 AM
0 Comments:
Post a Comment
<< Home