%% $Id: FRS-exam.tex,v 1.6 1995/10/03 15:42:28 kris Exp $ %% Exam for FRS course. \documentclass[a4paper,oneside,12pt]{article} \usepackage{amsmath} \usepackage[all]{xy} \usepackage{qsymbols} \def\MYNAME{Kristoffer H. Rose} \title{Fundamental Reduction Systems\\Examination} \author{Teacher: \MYNAME} \date{Tuesday, December 13, 1994, 14$^{\textup{00}}$--16$^{\textup{00}}$} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Q&A... \newtheorem{Q}{\llap{$\blacktriangleright$\quad}Question} \newtheorem{Def}{Definition} \makeatletter \begingroup \catcode`\|=0 \catcode`\<=1 \catcode`\>=2 |catcode`|\=12 |gdef|otherescape<\> |catcode`|%=12 |gdef|othercomment<%>|endgroup \count@=\time \divide\count@ by 60\relax \count@@=\count@ \multiply\count@@ by -60 \advance\count@@ by \time \edef\now{\number\count@:\ifnum 10>\count@@ 0\fi \number\count@@} \newwrite\answ@ \immediate\openout\answ@=\jobname.ans \def\IW@#1{\immediate\write\answ@{#1}} \IW@{\othercomment\space\jobname.ans: \today, \now.} \def\A#1{% \IW@{\otherescape paragraph*{\string\llap{$`(:-)$\quad}Answer to Question \@currentlabel:}}% \IW@{\othercomment} {\DN@{#1}\DNii@##1:->##2<:{{\IW@{##2}}}\expandafter\nextii@\meaning\next@<:}% \IW@{}} \def\Answers{\clearpage \immediate\closeout\answ@ {\footnotesize \input\jobname.ans }} \makeatother %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Logic circuits! \newcommand{\circuit}[2][]{\vcenter{\def\next{#1}% \if\notempty{#1}\def\next{\xycompileto{#1}}\else\def\next{\xycompile}\fi \expandafter\xy\next{\xygraph{~{<2pc,0pc>:}#2}}\endxy}} \newgraphescape{n}#1#2{[]!{+0="#2"*=<10pt>{};p!#1**{},"#2" -/4pt/*!E\cir<2pt>{} .{-/12pt/*=<24pt>{}*\frm{}="X@@" !E+/^7pt/="#2a", "X@@"!E+/_7pt/="#2b", "X@@"*\cirhalf{#1}, "X@@"-/^12pt/;p-/12pt/**\dir{-};p+/_24pt/**\dir{-};p+/_12pt/**\dir{-}, "X@@"}}} \newgraphescape{i}#1#2{[]!{+0="#2"*=<10pt>{};p!#1**{},"#2" -/4pt/*!E\cir<2pt>{} +0;p-/:a(-30)24pt/**\dir{-}="X2" ;p-/:a(-60)24pt/="X1"**\dir{-};?(.5),="#2a",p-/:a(-60)24pt/**\dir{-}, "#2"."#2a"."X1"."X2"}} \newgraphescape{a}#1#2{[]!{+0="#2"*=<10pt>{};p!#1**{},"#2" .{-/12pt/*=<24pt>{}*\frm{}="X@@" !E+/^7pt/="#2a", "X@@"!E+/_7pt/="#2b", "X@@"*\cirhalf{#1}, "X@@"-/^12pt/;p-/12pt/**\dir{-};p+/_24pt/**\dir{-};p+/_12pt/**\dir{-}, "X@@"}}} \newgraphescape{b}#1{[]!{*[o]{\notingraph`(#1)}}="#1"} \makeatletter \let\notingraph=\ingraph@false \def\cirhalf#1{\csname cirhalf@#1\endcsname} \def\cirhalf@R{\cir{r_l}} \makeatother %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Misc. \newqsymbol{`*}{\mathbin{\pmb\bindnasrepma}} \newqsymbol{`+}{\mathop{\bullet}} \mathcode`\*="2202 \newcommand\bl{\dir{*}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle \noindent The questions of this exam investigate the properties of some actual term rewrite systems meant to be useful in electronics. There are~\ref{lastQ} questions (marked with a~$\blacktriangleright$ in the left margin) on~\pageref{end} pages. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bigskip\noindent% It is possible to model ´{electronic circuits} with reduction systems. In such a circuit, a number of logic-valued inputs are passed into a number of interconnected logic `gates' that combine them in various ways to form some logic-valued outputs. We will denote logic values as $1$ and $0$ (for `true' and `false'), and will only consider one kind of logic gate, namely $`*$ (for `inverted and'), usually called `nand' and depicted \begin{equation} \circuit[nand]{ []!nR1("1a"([l]x-?), "1b"([l]y-?)) - [r]z } \qquad \textup{with truth table} \qquad{\small \begin{array}[c]{|cc|c|} \hline x & y & z \\ \hline 0 & 0 & 1 \\[-2pt] 0 & 1 & 1 \\[-2pt] 1 & 0 & 1 \\[-2pt] 1 & 1 & 0 \\ \hline \end{array}}\quad\hbox{(nand)}\label{nand} \end{equation} implementing the logic function $z = {x`*y} \stackrel{\textup{def}}{=} {`!(x`^y)}$. \begin{Def}\label{Nand}% The term rewrite system ´{Nand} is intended to model the function of all possible nand-gate circuits with a single ouput. The terms are \begin{equation} t ~::=~ t`*t ~\mid~ 1 ~\mid~ 0 \label{nand-t} \end{equation} and the rules \begin{align} 1`*1 &"->" 0 \label{nand-11}\\ 0`*x &"->" 1 \label{nand-0x}\\ x`*0 &"->" 1 \label{nand-x0} \end{align} \end{Def} \begin{Q}\label{nand-nf} What are the normal forms? \A{$0$ and $1$.} \end{Q} \begin{Q}\label{nand-inverter}\label{nand-and} Nand-gates can be used to model several other gates. Verify by reduction in the ´{Nand} system that each of the circuits given below in the left column behaves as the gate pictured in the middle with truth table to the right: \begin{alignat}2 \circuit[inv]{ !nR1 ( "1a"([ll]x-?) , "1b"([l]1-?) ) - [r]z } &`= \circuit[nand-inv]{ []!iR1("1a"([l]x-?)) - [r]z } &\quad&\hbox{\small$ \begin{array}[c]{|c|c|} \hline x & z \\ \hline 0 & 1 \\[-2pt] 1 & 0 \\ \hline \end{array}$}\quad\hbox{(inverter)} \label{inverter} \\ \notag\\ \circuit[and]{ !iR2("2a"([l]!nR1 ("1a"([l]x-?), "1b"([l]y-?)) - ?)) - [r]z} &`= \circuit[nand-and]{ !aR1("1a"([l]x-?), "1b"([l]y-?)) - [r]z} &&\hbox{\small$ \begin{array}[c]{|cc|c|} \hline x & y & z \\ \hline 0 & 0 & 0 \\[-2pt] 0 & 1 & 0 \\[-2pt] 1 & 0 & 0 \\[-2pt] 1 & 1 & 1 \\ \hline \end{array}$}\quad\hbox{(and)}\label{and} \end{alignat} \A{This one is the easy one: The inverter circuit~\eqref{nand-inverter} corresponds to the term $x`*1$ which clearly reduces to $`!x$ in a single step. The and circuit~\eqref{nand-and} corresponds to the term $(x`*y)`*1$ which reduces to $x`^y$ in two reductions for each possible $x$ and $y$.} \end{Q} \begin{Q}\label{nand-bounded} Show that ´{Nand} is bounded. \A{The easiest method is based on the insight that each reduction eliminates a gate, and that all gates where the inputs are $0$ or $1$ can be reduced by one of the rules. Thus in the worst case the number of reductions is equal to the number of gates, \textit{i.e.}, $`L(x) = \#\textup{gates}(x)$.} \end{Q} \begin{Q}\label{nand-complete} Show that ´{Nand} is complete (\textit{i.e.}, noetherian (SN) and confluent (CR)). \A{´{Nand} is obviously SN since it is bounded. It is easy to show it LC by observing that the only critical pair reduces as ${0`*0} "->" 1$ with both \eqref{nand-0x} and \eqref{nand-x0}.} \end{Q} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% When building real circuits it is possible to connect a wire to more than one input and this is not captured by ´{Nand}. We will repair this by adding `branching wire' components like \begin{displaymath} \circuit{~{(0,.5)::} []-[r]!bA -[r]*=0{`+} ( -[uu]-[r], -[u]*=0{`+}-[r], -[d]*=0{`+}-[r], -[dd]-[r]) [r]*!/d3pt/{\vdots} } \end{displaymath} where crossing wires are connected when marked with $`+$. We will only consider combinatoric circuits (without feed-back, \textit{i.e.}, loops). Note that any such circuit corresponds to a ´{Nand}-circuit (without branching) by making a copy of the subcircuit generating the branched signal for each wire it is connected to. \begin{Def}\label{NandC}% The term rewrite system ´{NandC} is intended to model all combinatoric nand-gate circuits with a single ouput. The terms are as ´{Nand} with the addition of \begin{equation} t ~::=~ `(a)(t,t) ~\mid~ a\label{nandc-t} \end{equation} where $a,b$ range over special `branch constants' $A,B,\dots$ of which we use as many as needed for each circuit, with the new rules \begin{align} `(a)(u,x`*y) &"->" `(a)(u,x)~`*~`(a)(u,y) \label{nandc-*}\\ `(a)(x,a) &"->" x \label{nandc-aa}\\ `(a)(x,b) &"->" b \qquad \textup{if}~a\not=b \label{nandc-ab}\\ `(a)(x,0) &"->" 0 \label{nandc-a0}\\ `(a)(x,1) &"->" 1 \label{nandc-a1} \end{align} The new term $`(a)(x,y)$ should be read `the output of $x$ is available as input $a$ in~$y$'. \end{Def} \begin{Q}\label{nandc-nf} What are the normal forms and what do they mean in circuit concepts? \A{$0$ and $1$, as before. All the possible branch letters $A,B,\dots$ corresponding to undefined branches. $1`*x$ and $x`*1$ when $x$ is a normal form different from $0$ and $1$ corresponding to a gate that is not stable because it depends on an undefined branch.} \end{Q} \begin{Q}\label{nandc-xor} Write the ´{NandC}-term corresponding to the following circuit below to the left and verify that it implements the `exclusive or' function with truth table to the right: \begin{equation} \circuit[xor]{ []x - [rr]!bA "x"[d]y - [r]!bB "x"[d(2)r(6)]!nR1 ( "1a"[l!{"A";p+D}]*=0{`+} ([rr]!iR{1I}-"1a",?-"1Ia") "1b"[l!{"B";p+D}]*=0{`+} - "1b" ) "x"[d(4)r(6)]!nR2 ( "A"-[d!{"2a";p+/r/}] - "2a" , "B"-[d!{"2b";p+/r/}] ([rrr]!iR{2I}-"2b", ?-"2Ia") ) "x"[d(3)r(8)]!nR3 ( "1"-[r"1$, ${`*}"|->"2$, and ${`(A),`(B),\dots}"|->"3$.} \end{Q} \begin{Q}\label{nandc-critical} Show that ´{NandC} is complete. \A{First we find the overlaps; in each case $a$ can be any branch point $A,B,\dots$: \begin{gather*} 0`*0 \quad\textup{by \eqref{nand-0x}, \eqref{nand-x0} (as before)}\\ `(a)(u,\b{1`*1})\quad\textup{by \eqref{nandc-*}, \b{\eqref{nand-11}}}\\ `(a)(u,\b{0`*x})\quad\textup{by \eqref{nandc-*}, \b{\eqref{nand-0x}}}\\ `(a)(u,\b{x`*0})\quad\textup{by \eqref{nandc-*}, \b{\eqref{nand-x0}}} \end{gather*}} \end{Q} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% One application is to find a way to measure the ´{speed} of circuits in the form of the ´{delay} from the inputs are stable until the output is stable. We'll assume that all gates use one time unit to stabilise their output after their inputs are stable and that wires have no delay, so the three circuits we have investigated so far have delay 1 (inverter), 2 (and), and 3 (xor). \begin{Q}\label{delay} Design a reduction strategy for one of the systems such that the number of strategy steps that it uses corresponds to the delay of `real' circuits. Verify your system by checking for the three circuits above. ´{Hints}: Think about what properties of a circuit this depends on and that `many step strategies' use fewer steps than ordinary reduction. \A{It is sufficient to use ´{Nand} because the delay only depends on the number of gates from the inputs to the output. Furthermore, we should reduce `as fast as possible' from the inputs to the output thus some kind of parallel reduction is needed. It should be outermost because `disjoint' gates stabilise independently which means that there may be longer paths than the delay when there is redundant circuitry, \textit{i.e.}, the circuit $x`*(1`*y)$ stabilises in a single unit for $x=0$.} \end{Q} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Another application is to measure the ´{power consumption} of circuits. We will simplify the problem by asuming that only gates that ´{change state} use any power. \begin{Q}\label{power} Devise a method to measure the power consumption of circuits. ´{Hint}: It is alright to change the rewrite system to represent additional information. \A{The easiest way is to measure the `cost of the output' by annotating all terms with a cost number and then look at the final output to see the total cost. The critical point to get right is the branching rule: the cost of generating the signal that is branced should only be counted once.} \end{Q} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{Q}[difficult]\label{feedback} Discuss how one might define a rewrite system that describes feed-back in circuits, and how such circuits correspond to simple ´{Nand}-circuits? \A{Several techniques can be used here and it is still open what is best. One method is to have `pervasive branches', \textit{i.e.}, replace rule~\eqref{nandc-aa} with \begin{equation}\tag{$\ref{nandc-aa}'$} `(a)(x,a) "->" `(a)(x,x) \end{equation} Such circuits correspond to infinite (though regular) ´{Nand}-circuits.} \label{lastQ}\end{Q} \paragraph*{End of the exercises.} \copyright\ 1994 \MYNAME\ (solutions available).\label{end} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Answers %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document} $Log: FRS-exam.tex,v $ Revision 1.6 1995/10/03 15:42:28 kris Modified to not use t.sty as an Xy-pic sample... Revision 1.5 1995/02/07 23:12:46 kris Second round. Revision 1.4 1994/12/23 14:19:51 kris Løsninger sendt til studenterbedømmerne. Revision 1.3 1994/12/13 16:07:57 kris Includes the two announced corrections. Revision 1.2 1994/12/13 11:44:16 kris This is what they get. Revision 1.1 1994/12/12 09:15:43 kris Initial revision