% Current version: June 28, 1993 \documentstyle{lgjrnl} \begin{document} %% To be entered at Kluwers: ==>> \journame{Journal of Applied Intelligence} \volnumber{2} \issuenumber{1} \issuemonth{July} \volyear{1992} %% For this article: \received{April 29, 1991} \revised{October 11, 1991} %\editor{} \editors{S. Devadas and P. Michel} \authorrunninghead{Potter, et al.} \titlerunninghead{Heuristic Multiple Fault Diagnosis} \setcounter{page}{5} %% This command is optional. %% May set page number only for first page in %% issue, if desired. %% <<== End of commands to be entered at Kluwers %% Authors, start here ==>> \title{ Improving the Reliability of Heuristic Multiple Fault Diagnosis via the\\ EC-Based Genetic Algorithm } \author{Walter D. Potter} \affil{Artificial Intelligence Programs, Department of Computer Science, GSRC 111, University of Georgia, Athens GA 30602} \author{John A. Miller} \affil{Artificial Intelligence Programs, Department of Computer Science, University of Georgia, Athens GA 30602} \author{Bruce E. Tonn} \affil{Oak Ridge National Laboratory} \author{Ravi V. Gandham} \affil{Department of Computer Science, University of Georgia, Athens GA 30602} \author{Chito N. Lapena} \affil{Artificial Intelligence Programs, University of Georgia, Athens GA 30602} \begin{abstract} Engineered Conditioning (EC) is a Genetic Algorithm operator that works together with the typical genetic algorithm operators; mate selection, crossover, and mutation, in order to improve convergence toward an optimal multiple fault diagnosis. When incorporated within a typical genetic algorithm, the resulting {\it hybrid} scheme produces improved reliability by exploiting the global nature of the genetic algorithm as well as ``local'' improvement capabilities of the Engineered Conditioning operator. We show the significance of the Engineered Conditioning operator during Multiple Fault Diagnosis (i.e., finding the collection of simultaneously occurring disorders that best explains the observed symptoms or disorder manifestations). Within the Mulitple Fault Diagnosis domain, we show the improvement of diagnostic reliability when using the engineered conditioning operator with the genetic algorithm compared to results from the genetic algorithm without the new operator. Reliability is based on the number of diagnostic trials for which the two versions of the genetic algorithm find the optimal diagnosis. For comparison purposes, optimal diagnoses have been computed using a search method that is guaranteed to find the optimal solution. \end{abstract} \keywords{Genetic Algorithms, multiple fault diagnosis, heuristic search, diagnostic reliability} \begin{article} \section{Introduction} Diagnosis is the process of determining the correct problem from a collection of problems given a set of symptoms that indicate a problem exists. Common experiences with this process include visits to the physician in order to determine our illness (disease) and visits to our local mechanic to determine the cause (fault) of a poorly operating car. In either case, we report the symptoms of the problem to the diagnostician (physician or mechanic) who determines the most likely cause that best explains these symptoms. In terms of the complexity of determining the correct diagnosis, the diagnostician must find a diagnosis from a set of possible diagnoses. This is the situation in which we find ourselves. That is, if a total of 10 diseases or faults are being considered where only one of these is the correct one then at most 10 diagnoses will need to be evaluated. However, in the more typical case where several problems (diseases/faults) may occur simultaneously, the complexity of finding a proper diagnosis increases {\it exponentially} with the number of problems. For example, using the 10 problems considered above, the situation changes such that any of the 1024 (i.e., $2^{10}$) possible combinations of problems may turn out to be the correct diagnosis. \subsection{Preliminary definition of optimization} Our assumption has been that the goal of categorization is to predict unknown features of various objects that we encounter. \subsubsection{The structure of the environment} Our theory of the structure of the environment has been focused the structure of living things (arguably, the largest portion of the objects in the world) because of the aid biology gives in objectively specifying the organization of these objects. \section{Formatting Mathematical Expressions} Formally, this amounts to calculating: \begin{equation} g_i(y|f)=\sum_x P(x|F_n)f_i(y|x) \end{equation} where $g_i(y|F_n)$ is the function specifying the probability an object will display a value $y$ on a dimension $i$ given $F_n$ the observed feature structure of all the objects. Here is an example of a wide equation: \begin{wideequation} \begin{equation} \sum_k P(k) \sum_i \sum_y f_i(y|k)^2 \sum_k P(k) \sum_i \sum_y f_i(y|k)^2 \end{equation} \end{wideequation} In this wide equation the `splitmath' command is used to split the math into two lines, moving the top half to the left and the bottom to the right. \[ \begin{splitmath} [-(\Im(\alpha) +\Im(\delta)/2 -(\Im(\beta)-(\Im(\gamma))2 \\ (\Re(\alpha)-\Re(\delta))/2\quad(\Re(\beta)+\Re(\gamma))/2] \end{splitmath} \] Or, if you want a numbered equation: \begin{equation} \begin{splitmath} [-(\Im(\alpha) +\Im(\delta)/2 -(\Im(\beta)-(\Im(\gamma))2 \\ (\Re(\alpha)-\Re(\delta))/2\quad(\Re(\beta)+\Re(\gamma))/2] \end{splitmath} \end{equation} \section{Theorems, Proofs, Examples, etc.} \begin{proclaim}{Theorem 1}LEARN-MONOTONE-K makes at most $(n+1)^K$ mistakes on any monotone K-CNF formula. (Recall that $n$ is the size of the largest example seen.) \end{proclaim} \begin{proof} The running time of this algorithm is clearly polynomial in {\bf size}$(f_T)$ and the length of the longest example seen. If a proof ends with displayed math \verb+\inmathqed+ must be used. \[ \alpha\beta\Gamma\Delta\inmathqed \] \end{proof} \begin{proof}[Proof of Theorem A.1] This is an example of a proof of a particular theorem. The term you want to use should follow `proof' in square brackets. \end{proof} \goodbreak % added to make next column start here. In this section, we present an efficient formula for computing $P(B_X, D)$. We do so by first introducing two assumptions having to do with our database. \begin{demo}{Assumption 1} The database variables, which we denote as $Z$, are discrete. \end{demo} \begin{demo}{Assumption 2} The database constants, which we denote as $C$, are also discrete. \end{demo} \begin{example} Consider an example in which~$B_S$ is the structure. The term $P(B_X)$ is our probability---prior to observing the data in database $D$---that the data-generating process is a belief network with structure $B_{S1}$. This network can be seen to have the following qualities: monotonicity, and serial portability. \end{example} \subsection{Sample Text} Diagnosis is the process of determining the correct problem from a collection of problems given a set of symptoms that indicate a problem exists. Common experiences with this process include visits to the physician in order to determine our illness (disease) and visits to our local mechanic to determine the cause (fault) of a poorly operating car. In either case, we report the symptoms of the problem to the diagnostician (physician or mechanic) who determines the most likely cause that best explains these symptoms. \section{Figures} Figures can be positioned at the top or bottom of each column, or at the point in text where they are written. They can also be positioned across two columns at the top or bottom of the page. % Here is a figure to be positioned at the % top of the page, spanning both columns. \spanbothcolumns \begin{figure}[t] \begin{center} \leavevmode \unitlength1pt \picture(186.71,187.36) \catcode`\@=11 \put(30.98,168.00){\hbox{topic}} \put(35.8761,163.0556){\line(-6,-5){21.3000}} \put(0.00,138.00){\hbox{mann}} \put(47.9900,163.0556){\line(5,-4){18.8889}} \put(53.85,138.00){\hbox{verb-sec}} \put(67.6462,135.0000){\line(-5,-4){21.3195}} \put(29.47,108.00){\hbox{haben}} \put(74.9962,135.0000){\line(6,-5){23.6334}} \put(85.27,108.00){\hbox{vp-gap}} \put(100.1297,103.0556){\line(0,-1){15.1111}} \put(79.99,78.00){\hbox{vp-compl}} \put(94.1968,73.0556){\line(-6,-5){18.1333}} \put(63.95,48.00){\hbox{frau}} \put(106.0635,73.0556){\line(6,-5){18.1333}} \put(110.88,48.00){\hbox{vp-mod}} \put(117.6616,43.0556){\line(-2,-1){30.2222}} \put(46.27,18.00){\hbox{mit dem fernglass}} \put(137.4394,43.0556){\line(2,-1){30.2222}} \put(153.32,18.00){\hbox{gesehen}} \endpicture \leavevmode \unitlength1pt \picture(148.28,187.36) \catcode`\@=11 \put(30.98,168.00){\hbox{topic}} \put(35.8761,163.0556){\line(-6,-5){21.3000}} \put(0.00,138.00){\hbox{mann}} \put(47.9900,163.0556){\line(5,-4){18.8889}} \put(53.85,138.00){\hbox{verb-sec}} \put(67.6462,135.0000){\line(-5,-4){21.3195}} \put(29.47,108.00){\hbox{haben}} \put(74.9962,135.0000){\line(6,-5){23.6334}} \put(85.27,108.00){\hbox{vp-gap}} \put(100.1287,103.0556){\line(0,-1){15.1111}} \put(79.99,78.00){\hbox{vp-compl}} \put(93.5366,73.0556){\line(-4,-3){20.1482}} \put(51.87,48.00){\hbox{pp-mod}} \put(60.4350,43.0556){\line(-5,-3){25.1852}} \put(21.42,18.00){\hbox{frau}} \put(76.9165,43.0556){\line(5,-3){25.1852}} \put(68.35,18.00){\hbox{mit-dem-fernglass}} \put(106.7218,73.0556){\line(4,-3){20.1482}} \put(114.89,48.00){\hbox{gesehen}} \endpicture \end{center} \caption{\label{tree}Derivation trees of the simple attachment example} \end{figure} \endspanbothcolumns Here is an example of a figure with space left for the illustration: \begin{figure}[h] \hrule \vspace*{1.35in} \caption{This figure appears in the text where written. It uses \verb+[h]+.} \end{figure} There is even the possibility of a floating figure that occupies a complete page. \begin{figure}[t] \hrule \vspace*{1in} \caption{This figure caption floats to the top of the column. It uses [t].} \end{figure} \begin{figure}[b] \hrule \vspace*{1.4in} \caption{This figure floats to the bottom of the column. It uses [b].} \end{figure} \subsection{Sample Text} Diagnosis is the process of determining the correct problem from a collection of problems given a set of symptoms that indicate a problem exists. Common experiences with this process include visits to the physician in order to determine our illness (disease) and visits to our local mechanic to determine the cause (fault) of a poorly operating car. In either case, we report the symptoms of the problem to the diagnostician (physician or mechanic) who determines the most likely cause that best explains these symptoms. In terms of the complexity of determining the correct diagnosis, the diagnostician must find a diagnosis from a set of possible diagnoses. This is the situation in which we find ourselves. That is, if a total of 10 diseases or faults are being considered where only one of these is the correct one. %% Be careful to place a full page figure after the other %% figures on the page so that the captions are numbered correctly. \begin{figure}[p] For example, if the strategic component specifies the following structure SEM as input to the tactical component: \newcommand{\fs}{\left[\begin{array}{l}} \newcommand{\fsfs}{\end{array}\right]\vspace{0.5ex}} \[ \fs sem: \fs cont: \fs reln: remove'\\ agent: you'\\ patient: folder'\\ instrument: system\_tools' \fsfs\\ conx: \fs speech\_act: imperative \fsfs \fsfs \fsfs \] \noindent then a possible utterance is `Remove the folder with the system tools' with the corresponding derived grammatical structure where the PP `with the system tools' is an adjunct to the VP: \[ \fs phon: \langle \mbox{\it remove the folder with the system tools} \rangle\\ synsem: S[imp] \\ dtrs: \fs head: \fs phon: \langle remove \rangle\\ synsem: VP[fin] \fsfs \\ comp:\langle \begin{array}{l} \fs phon: \langle \mbox{\it the folder} \rangle\\ synsem: NP[acc] \fsfs \end{array} \rangle\\ adjunct: \langle\mbox{\it with the system tools}\rangle\\ \fsfs \fsfs \] >From the generator point of view this utterance is grammatical reflects exactly what the generator wants to express. For the hearer there also exists however the alternative grammatical structure where the PP `with the system tools' is a nominal adjunct: \[ \fs phon: \langle \mbox{\it remove the folder with the system tools} \rangle\\ synsem: S[imp] \\ dtrs: \fs head:\fs phon: \langle remove \rangle\\ synsem: VP[fin] \fsfs \\ comp: \langle \begin{array}{l} \fs phon: \langle \mbox{\it the folder with the system tools}% \rangle\\ synsem: PP \\ dtrs: \fs head: \langle\mbox{\it with the system tools}% \rangle\\ comp: \langle \mbox{\it the folder}\rangle \fsfs\fsfs\end{array}\rangle\\ \fsfs\fsfs \] \noindent with the semantic reading SEM$'$: If the generator is part of an intelligent help system, the choice of this reading could have tremendous effects on the system itself. \[ \fs sem: \fs cont: \fs reln: remove'\\ agent: you'\\ patient: \fs index: x\\ restr: folder'(x) \land \\ ~~~~~~~~~ with'(x,system\_tools') \fsfs \fsfs\\ conx: \fs speech\_act: imperative \fsfs \fsfs \fsfs \] \caption{This is a floating insertion that contains a full page figure. The command [p] is used to make a full page floating figure.} \end{figure} \newpage \section{Making Tables} Like figures, tables can be positioned in the columns at the top, bottom, or where written in the text, and also can be made to span both columns at the top, middle or bottom of the page. The table caption should be written above the table. Table notes can be used below the table. The method of producing table notes can be seen when looking at the code used to produce this example. When making the table, please use \verb+\hline+ at the top of the table, underneath the column headers and at the end of the table. You are discouraged from using vertical lines in tables, but it you must include vertical lines, you must also use \verb+\savehline+ instead of \verb+\hline+ or there will be a gap between the vertical and horizontal lines. (\verb+\hline+ has been redefined to add some vertical space above and below it.) \begin{table}[h] \caption{A short table caption.} \begin{tabular}{lcr} \hline $\alpha\beta\Gamma\Delta$ One&Two&Three\cr \hline one&two&three\cr one&two&three\cr \hline \end{tabular} \tablenotes \label{table1b} \end{table} \begin{table}[h] \caption{This is an example table caption. If it contains enough words it will be formatted as a paragraph. Short captions will be centered. This form of a table will extend to fill the width of the column.} \begin{tabular*}{\hsize}{@{\extracolsep{\fill}}lcr} \hline $\alpha\beta\Gamma\Delta$ One&Two&Three\cr \hline one&two&three\cr one&two&three\cr \hline \end{tabular*} \end{table} \spanbothcolumns \begin{table}[b] \caption{Summary of the experimental results.} \begin{tabular*}{\hsize}{@{\extracolsep{\fill}}rrrrrrrrrrrrr} \hline \multicolumn{3}{l}{Parameters}& \multicolumn{5}{c}{Averaged Results}& \multicolumn{5}{c}{Comparisons}\cr \hline \multicolumn1c{$n$}&\multicolumn1c{$S^*_{MAX}$}& \multicolumn1c{$t_1$}&\multicolumn1c{\ $r_1$}& \multicolumn1c{\ $m_1$}&\multicolumn1c{$t_2$}& \multicolumn1c{$r_2$}&\multicolumn1c{$m_2$} &\multicolumn1c{$t_{lb}$}&\multicolumn1c{\ \ $t_1/t_2$}& $r_1/r_2$&$m_1/m_2$& $t_1/t_{lb}$\cr \hline 10&1\quad &4&.0007&4&4&.0020&4&4&1.000&.333&1.000&1.000\cr 10&5\quad &50&.0008&8&50&.0020&12&49&.999&.417&.698&1.020\cr 100&20\quad &2840975&.0423&95&2871117&.1083&521&---& .990&.390&.182&---\ \ \cr \hline \end{tabular*} \begin{tablenotes} These terms are used in the table above: \tableterms $n$ & number of embeddings. $2^S MAX-1$: maximal size of embeddings.\\ $t_1(t_2)$ & test time (in time steps) required by our scheme (scheme in [6]).\\ $t_{lb}$ &estimated lower bound test time (in time steps).\\ $m_1(m_2)$& number of nodes generated by our scheme (scheme in [6]).\\ \endtableterms \end{tablenotes} \end{table} \endspanbothcolumns \section{Listing Environments} Here is an example of a bulleted list: \begin{itemize} \item Some text here. Some text here. Some text here. Some text here. Some text here. \item Some text here. Some text here. Some text here. \end{itemize} \subsection{Numbered List} Here is an example of a numbered list: \begin{enumerate} \item Some text here. Some text here. Some text here. Some text here. Some text here. Some text here. Some text here. Some text here. \item Some text here. Some text here. Some text here. \begin{enumerate} \item Some text here. Some text here. Some text here. Some text here. \item Some text here. Some text here. Some text here. \begin{enumerate} \item Some text here. Some text here. Some text here. Some text here. Some text here. \item Some text here. Some text here. Some text here. \end{enumerate} \end{enumerate} \end{enumerate} \subsection{Seeds of clauses} If an example satisfies the seed of a clause, then it satisfies the clause as well. In addition, seeds have the following property: \begin{itemize} \item[] If a seed of clause $c_T$, and example {\bf x} satisfies $c_T$ but not $c$, then {\bf x} has at least one attibute in $c_T$ that is not in $c$.\hfill({\tt*}) \end{itemize} The procedure below... The answer depends on two factors: \begin{enumerate} \item {\bf Certainty of inference:} The probability of the inference rules used to find or infer answers to knowledge goals, or the likelihood that the conclusions will be true. In a logic system where an inference rule represents a deduction, this probability is 1. \item {\bf Cost of inference:} The cost of making inferences or of matching and applying inference rules. The cheaper the inference, the more it is worth the system's while to make it. \end{enumerate} \paragraph{Memory goals:}Knowledge goals of a dynamic memory program, arising from memory-level tasks. A dynamic memory must be able to notice similarities, match incoming concepts to stereotypes in memory, form generalizations, and so on. \paragraph{Explanation goals:}Goals of an explainer that arise from explanation-level tasks, including the detection and resolution of anomalies,and the building of motivational and causal explanations for the events in the story in order to understand why the characters acted as they did, or why certain events occurred or did not occur. \paragraph{The READ step:}AQUA reads a piece of text, guided by the questions in memory. It tries to answer these questions using the new piece of information. \begin{itemize} \begin{description} \item[READ] some text, focussing attention on interesting input as determined below. Build minimal representations in memory. \item[Retrieve]extant knowledge goals or questions indexed in memory that might be relevant. \begin{description} \item[Answer question] by either confirming or refuting it. \item[Propagate]back to the hypothesis that the question originated from. \end{description} \item[Explain]the new input if necessary, i.e., if interesting and not already explained. \end{description} \end{itemize} \spanbothcolumns[h] \begin{codesamp} : $\Rightarrow$ (if ) (then ) (continuation ) \end{codesamp} \endspanbothcolumns \section{Material that spans both columns} The example above shows how to fit in a small bit of code that is too wide for one column. The following extended example is too wide to fit within the columns so it is good to be able to have it span both columns. We end the columns with the command \verb+\endtwocolumns+ and start the two column format again with the command \verb+\twocolumns+ This example also shows the use of commands to format computer screen interface examples. \endtwocolumns \begin{interface} \winline{1)}{Response window:} \window Enter your name: \bf John Smith Enter engine serial number: \bf 8581 Another line \endwindow (User now selects ``continue'' button to accept input) ($\Rightarrow$ current node in network: {\it root node} \winline{2)}{Response window:} \window Enter all pre-startup conditions as indicated on this form. \endwindow (All pertinent parameters are entered---engine settings, certain ambient conditions, etc.) (Upon acceptance of input, entries are checked against constraints for consistency.) ($\rightarrow$ current node in network: {\it root node}) \winline{3)}{Response Window:} \window Select from the list below the observed or reported snag(s): \hskip20pt$\bullet$ \hskip20pt$\bullet$ nozzle dance slow acceleration {\bf engine flameout} compressor stall \hskip20pt$\bullet$ \hskip20pt$\bullet$ \endwindow \winline{Help window:}{} \window The {\bf MFC} is a hydro-mechanical force balance system which will supply the correct fuel flow for the full range of operation up to {\bf military}. It establishes safe fuel limits for all operating conditions. It regulates engine speed by metering the main engine fuel supply. \endwindow (This help information allows the user to preview a node.) \winline{}{\hskip20pt Help window:} \window The {\bf military} position corresponds to the {\bf PLA} to 91.5$\pm$ 1.5 degrees (approximately 16,500 rpm) \endwindow \begin{itemize} \item[] (this is a definition for {\bf military} and is held in the glossary frame template in Figure 7. There are also glossary frames for {\bf PLA} and {\bf rpm} should the user wish to obtain furnther information.) \end{itemize} \end{interface} \vskip.5in \twocolumns \section{Steps} \steps \step Apply the backpropagation procedure (adapted for the KBCNN model) until the system error converges on an asymptotic value. \step Compute the Consistent-Shift value for each weight. \step For each weight, Do \begin{itemize} \item[--] if the Consistent-Shift value is less than a selected negative threshold and if the absolute value of the post-training weight is less than a selected positive threshold, then delete the corresponding commection. \item[--] Else, retain the connection. \end{itemize} \endsteps The Consistent-Shift algorithm refers to setp 2 and 3. The complete algorithm (the KBCNN model) for rule refinement is summarized by: \boldsteps \step Map the rule base into a neural network. \step Train the neural network by the adapted backpropagation procedure on the training data. \step Revise the trained neural network by the Consistent-Shift algorithm. \step Translate the revised neural network into rules. \endboldsteps \section{To Illustrate an Algorithm} \verb+\begin{algorithm}...\end{algorithm}+ are the commands to use when you want to illustrate an algorithm with some pseudo code. Math and font changes may be used. The command \verb+\bit+ will produce bold italics if you are using PostScript fonts, boldface in Computer Modern. \verb+\note{}+ will position the note on the right margin. A backslash followed by a space will provide a 2em space. Notice that each line is automatically numbered. \eject \spanbothcolumns \begin{figure}[t] \begin{algorithm} {\bit Evaluate-Single-FOE} ({\bf x$_f$, I$_0$, I$_1$}): \ {\bf I}+ := {\bf I}$_1$; \ ($\phi,\theta$) := (0,0); \ {\it repeat}\note{/*usually only 1 interation required*/} \ \ (s$_{opt}${\bf E}$_\eta$) := {\bit Optimal-Shift} ({\bf I$_0$,I$^+$,I$_0$,x$_f$}); \ \ ($\phi^+$, $\theta^+$) := {\bit Equivalent-Rotation} ({\bf s}$_{opt}$); \ \ ($\phi$, $\theta$) := ($\phi$, $\theta$) + ($\phi^+$, $\theta^+$); \ \ {\bf I}$^+$:= {\bit Derotate-Image} ({\bf I}$_1$, $\phi$, $\theta$); \ \ {\it until} ($|\phi^+|\leq\phi_{max}$ \& $|\theta^+|\leq\theta_{max}$); \ {\it return} ({\bf I}$^+$, $\phi$, $\theta$, E$_\eta$). End pseudo-code. \end{algorithm} \caption{Here is a sample algorithm. It is too wide to fit easily within a column so we positioned it at the top of the page using the command `spanbothcolumns'.} \end{figure} \endspanbothcolumns When you want to demonstrate some programming code, these are the commands to use. Lines will be preserved as you see them on the screen, as will spaces at the beginning of the line. % Notice that to produce printed `{' brackets, precede them with \string % \begin{codebox}...\end{codebox} can be inserted within % codesamp, and will be positioned at the same distance from right % margin as text. codebox needs an argument for the width of the box, % as in \begin{codebox}{2.5in} below. \begin{codesamp} sqrdc(a, n)(a, qraux)\string{ \underline{DARRAY float[180] a[180];} float qraux[180], col[180], nrmxl,t; int n,i,j,k,l; DO(1=0, n)\string{ \underline{ALIGN*(i=1, n) col[i]=a[l][i];} \begin{codebox}{2in} init*\string{ nrmxl=0.0;\string} DO*(i=l, n)\string{ nrmxl += col[i]*col[i];\string} combine*\string{nrmxl;\string} \end{codebox} nmxl=sqrt(nrmxl); if (nrmxl != 0.00)\string{ if (col[1]=1.0+col[1]; \begin{codebox}{1.5in} DO*(j=(l+1), p)\string{ float t; int i; t=0.0 DO(i=1, n)\string{ t=t+col[i] \string} \end{codebox} \string} \string} \end{codesamp} \section{Footnotes} Footnotes are not used in this format. You can still use notes, but they will be printed before the references instead at the bottom of the page. (An exception to this is the \verb+\thanks{}+ command which prints at the bottom of the article title page.) These sample footnote will be printed here above the references.\footnote{This is a footnote.} More text.\footnote{This is a second sample footnote. This is a second sample footnote. This is a second sample footnote. This is a second sample footnote.} \appendix This is an appendix. Appendix equations are lettered with `A' as well as numbered. \begin{equation} \sum_k P(k) \sum_i \sum_y f_i(y|k)^2 \end{equation} \acknowledgements I would like to thank Shiloh Smith for her careful implementation of the algorithms described. \endnotes \begin{references} \bibitem{francis} Francis, M., ``Out-of-band response of array antennas,'' Antenna Meas. Tech. Proc., September 28--October 2, 1987, Seattle, p.~14. \bibitem{jacobs}Jacobs, E., ``Design Method Optimizes Scanning Phased Array,'' Microwaves, April 1982, pp.\ 69--70. \bibitem{shrank6/86} Shrank, H., ``Comparison of low sidelobe distributions,'' IEEE AP Newsletter, Jun 1986, pp.~22-23. \bibitem{shrank8/86} Shrank, H., ``Gain factor vs sidelobe level for circular Taylor with optimum n-bar,'' IEEE AP Newsletter, Aug 1986. \end{references} %% Make the skip below big enough for photo. Space can be changed %% when article is in final production stage. \vspace*{1in} PHOTO ABOVE \bio{Walter D. Potter}is an assistant professor of computer science and the graduate coordinator for the Artificial Intelligence Programs at the University of Georgia in Athens, Georgia. His reseach interests include genetic algorithms, multiple fault diagnosis, expert database systems, hypersemantic data modeling, and advanced information system design. His work with genetic algorithms began while he was with the Intelligent Cognitive Systems Group at Oak Ridge National Laboratory as a DOE Faculty Research Fellow. Dr. Potter received the BS degree (1974) from The University of Tennessee in Business Administration and the MS (1981) and PhD (1987) from the University of South Carolina, both in Computer Science. \vspace*{1in} PHOTO ABOVE \bio{Bruce Tonn}is Group Leader of the Intelligent Cognitive Systems Group of Oak Ridge National Laboratory in Oak Ridge Tennessee. Dr.~Tonn conducts research in probability kinematics, automated knowledge acquisition, and realtime expert systems as well as in applications of advanced computing to social sciences. He has received degrees from Stanford, Harvard and Northwestern Universities. \end{article} %% To be entered at Kluwers: ==>> \journame{Journal of VLSI Signal Processing} \volnumber{4} \issuenumber{1} \issuemonth{February} \volyear{1992} %% For this article: \received{July 9, 1991} \revised{September 16, 1991} \editor{Antonio Smitts} %\editors{} \authorrunninghead{Valero-Garc\'\i a, Navarro, Llaber\'\i a and Lang} \titlerunninghead{A Method for Implementation of One-Dimensional Systolic Algorithms} \setcounter{page}{7} %% This command is optional. %% May set page number only for first page in %% issue, if desired. %% <<== End of commands to be entered at Kluwers %% Authors, start here ==>> \title{A Methord for Implementation of One-Dimensional Systolic Algorithms with\\ Data Contraflow Using Pipelined Functional Units} \authors{Miguel Valero-Garc\'ia, Juan J. Navarro, Jos\'e M. LLaber\'ia,\\ Mateo Valero and Tom\'as Lang\thanks{This work is supported by the Ministry of Education of Spain (CICYT TIC 299/89).}} \email{garcia@cata.spn.edu} \affil{Dept. Arquitectura de Computadores, Univ\ Polit\`ecnica de Catalunya, Gran Capit\'a s/n, M\'odul D4, 08034 Barcelona Spain} \begin{abstract} In this paper we present a method to implement one-dimensional Systolic Algorithms with data.... \end{abstract} \begin{article} \section{Introduction} During the last ten years, a lot of attention has been paid to the problem of automatic design of {\it Systolic Algorithms} (SAs) [1]-[5]. A method for automatic design takes a specification of the SA. Since the final objective is to implement the SA in hardware, aspects such as limitations in the number of PEs, fault aspects such as limitations should be taken into account in the design procedure. Within this context, this paper proposes a method to transform SAs for efficient implementation using {\it Pipelined Functional Units} (PFUs). \end{article} \end{document}