Span(Graph) II: Circuits with feedback
Previous Span(Graph) post; next Span(Graph) post.
As an introduction to ${\bf Span(Graph)}$ I will describe how to extend the category of straight-line circuits to allow circuits with state and feedback. But before doing that I would like to point out a couple of things about straight-line circuits.
Firstly, I introduced the operation of twisting two wires $twist:B^2\to B^2$. It is easy to see that using $twist$, $1_B$, product and composition we can write an expression which gives the twisting of two wires against two wires, or $m$ wires against $n$ wires, or in fact any permutation of wires. Let's just look at twisting two across two.
We can read off the expression:
$(1_B\times twist\times 1_B)(twist\times twist)(1_B\times twist \times 1_B)$.
Another operation on wires was the duplication of a wire $\Delta:B\to B^2$. But we can also duplicate two, or $n$ wires. Let's see two:
We will call this operation $\Delta_2$, defined by $\Delta_2=(\Delta\times \Delta)(1_B\times twist\times 1_B)$. Its input/output behaviour is $(x,y)\mapsto (x,y,x,y)$.
A final example before passing to circuits with feedback, namely an equation true for straight-line circuits but false for the circuits with feedback we are about to define. I will draw a picture of the equation: given any arrow $f:B\to B$ (but a similar equation is also true for and $f:B^m\to B^n$):
That is, $f\Delta=(\Delta)(f\times f)$. If you look at the input/output behaviour of these circuits you can see they are the same namely $x\mapsto (f(x),f(x))$, however the second uses more components.
${\bf Boolean\; circuits\; with\; state\; and\; feedback}$.
The aim is to define a category, denoted ${\bf Circ}$, again with objects being $B^n$ but with more general arrows, with operations similar to the ones we have defined for straight-line circuits, but with also an operation of feedback.
Today I will just describe the arrows, which often I shall call components.
An arrow of ${\bf Circ}$ from $B^m$ to $B^n$ consists of a finite graph $G$ whose edges are labelled by pairs of elements $(x,y)$ where $x=(x_1,x_2,\cdots ,x_m)\in B^m$, and $y=(y_1,y_2,\cdots ,y_n)\in B^n$. The vertices of the graph $G$ are called the ${\it states}$ of the component and the edges are called the ${\it transitions}$ of the component. The labels tell you what happens on the left and right hand wires of the component when a transition occurs. A ${\it behaviour}$ of the component is a path in the graph $G$ which yields also a sequence of left and right labels.
Let's look at a simple example. Notice that we separate the left and right labels by a slash.
This is a two state component with four transitions but what should we call it? Let's see what kind of behaviour it has. Remember a behaviour is a path in the graph. The sequence of left-labels on a path may be thought of as a signal occuring on the left as the transitions occur; similarly the sequence of right-labels is the signal on the right.
So here is a behaviour starting in state $0$:
$0\xrightarrow{0/0}0\xrightarrow{1/0}1\xrightarrow{0/1}0\xrightarrow{0/0}0\xrightarrow{1/0}1\xrightarrow{0/1}0\xrightarrow{0/0}0$.
The signal on the left for this behaviour is $0,1,0,0,1,0,0$ whereas the signal on the right is $0,0,1,0,0,1,0 $. You may notice that the signal on the right is the left signal ${\it delayed}$ by one step. In fact this component is a ${\it unit\; delay\; element}$.
Why does it act that way? The reason is that the next state is determined by the left signal (the signal is remembered as state) and the next right signal is determined by the current state (which was the last left signal).
You may wonder why I speak of left signal, right signal instead of input and output signals. It is crucial for what we do next that left and right do not necessarily correspond to input or output respectively.
As an introduction to ${\bf Span(Graph)}$ I will describe how to extend the category of straight-line circuits to allow circuits with state and feedback. But before doing that I would like to point out a couple of things about straight-line circuits.
Firstly, I introduced the operation of twisting two wires $twist:B^2\to B^2$. It is easy to see that using $twist$, $1_B$, product and composition we can write an expression which gives the twisting of two wires against two wires, or $m$ wires against $n$ wires, or in fact any permutation of wires. Let's just look at twisting two across two.
We can read off the expression:
$(1_B\times twist\times 1_B)(twist\times twist)(1_B\times twist \times 1_B)$.
Another operation on wires was the duplication of a wire $\Delta:B\to B^2$. But we can also duplicate two, or $n$ wires. Let's see two:
We will call this operation $\Delta_2$, defined by $\Delta_2=(\Delta\times \Delta)(1_B\times twist\times 1_B)$. Its input/output behaviour is $(x,y)\mapsto (x,y,x,y)$.
A final example before passing to circuits with feedback, namely an equation true for straight-line circuits but false for the circuits with feedback we are about to define. I will draw a picture of the equation: given any arrow $f:B\to B$ (but a similar equation is also true for and $f:B^m\to B^n$):
That is, $f\Delta=(\Delta)(f\times f)$. If you look at the input/output behaviour of these circuits you can see they are the same namely $x\mapsto (f(x),f(x))$, however the second uses more components.
${\bf Boolean\; circuits\; with\; state\; and\; feedback}$.
The aim is to define a category, denoted ${\bf Circ}$, again with objects being $B^n$ but with more general arrows, with operations similar to the ones we have defined for straight-line circuits, but with also an operation of feedback.
Today I will just describe the arrows, which often I shall call components.
An arrow of ${\bf Circ}$ from $B^m$ to $B^n$ consists of a finite graph $G$ whose edges are labelled by pairs of elements $(x,y)$ where $x=(x_1,x_2,\cdots ,x_m)\in B^m$, and $y=(y_1,y_2,\cdots ,y_n)\in B^n$. The vertices of the graph $G$ are called the ${\it states}$ of the component and the edges are called the ${\it transitions}$ of the component. The labels tell you what happens on the left and right hand wires of the component when a transition occurs. A ${\it behaviour}$ of the component is a path in the graph $G$ which yields also a sequence of left and right labels.
Let's look at a simple example. Notice that we separate the left and right labels by a slash.
This is a two state component with four transitions but what should we call it? Let's see what kind of behaviour it has. Remember a behaviour is a path in the graph. The sequence of left-labels on a path may be thought of as a signal occuring on the left as the transitions occur; similarly the sequence of right-labels is the signal on the right.
So here is a behaviour starting in state $0$:
$0\xrightarrow{0/0}0\xrightarrow{1/0}1\xrightarrow{0/1}0\xrightarrow{0/0}0\xrightarrow{1/0}1\xrightarrow{0/1}0\xrightarrow{0/0}0$.
The signal on the left for this behaviour is $0,1,0,0,1,0,0$ whereas the signal on the right is $0,0,1,0,0,1,0 $. You may notice that the signal on the right is the left signal ${\it delayed}$ by one step. In fact this component is a ${\it unit\; delay\; element}$.
Why does it act that way? The reason is that the next state is determined by the left signal (the signal is remembered as state) and the next right signal is determined by the current state (which was the last left signal).
You may wonder why I speak of left signal, right signal instead of input and output signals. It is crucial for what we do next that left and right do not necessarily correspond to input or output respectively.
Labels: computing
posted by Unknown at 10:27 AM
4 Comments:
"The reason is that the next state is determined by the left signal (the signal is remembered as state) and the next right signal is determined by the current state (which was the last left signal)."
Is it a property of arrow in Circ?
I am not quite sure what you are asking.
I hope it is clear that the arrows in the category may also be regarded as components with ports, so I usually call them components rather than arrows.
The particular component I described with two states 0 and 1 has the property that in any state a signal 0 one the left drives it into state 0, and a signal 1 on the left drives it into state 1, so the left signal is recorded a state (in fact, that is the reason I gave the names 0 and 1 to the states). But further the right signal is determined by the state: in state 0 the next right signal is always 0, in state 1 the right signal is always 1. So the next right signal is the recorded last left signal. The component delays the signals on the left by one step.
I will be writing a new post about the operations in the category in the next day or two.
Thank for explanation. I'm sorry for not well formulated question. I think that I understand this particular example, but It seems to me that only some specific arrows are satisfy this property (that next state is determined by left signal)
cheers
You are absolutely right. It is important in general not too think of the ports as being input/output, or that the left signal drives the component. See my comment in the third post. I started with the delay element because it is particularly simple, but it has very special properties.
Post a Comment
<< Home