Digitized by the Internet Archive 
 in 2013 
 
 http://archive.org/details/quarterlytechnic917info 
 
UIUCDCS-R-78 -917 
 
 ■9'J 
 
 TKt^tt 
 
 V 
 
 UILU-ENG 78 1711 
 
 QUARTERLY TECHNICAL PROGRESS REPORT 
 
 of the 
 INFORMATION ENGINEERING LABORATORY 
 for the period 
 November 1977-January 1978 
 
 February 1978 
 
 
 
 ^ 
 
 DEPARTMENT OF COMPUTER SCIENCE 
 UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 
 
 The Library of the 
 
 JUN 1 5 1978 
 
 diversity 01 Illinois 
 ^na-Chf 
 
 URBANA, ILLINOI 
 
Quarterly Technical Progress Report 
 of the 
 Information Engineering Laboratory 
 for the period 
 November 1977-January 1978 
 
 February 1978 
 
 Department of Computer Science 
 University of Illinois at Urbana-Champaign 
 Urbana, Illinois 61801 
 

 1. 
 
 1. Introduction 
 
 This report is intended to keep interested persons informed about 
 the progress on various research projects being carried out by the Information 
 Engineering Laboratory of the Department of Computer Science. Each report 
 lists those projects which have been completed, summarizes progress on those 
 which are currently active, and provides introductory remarks on new projects. 
 For each project, the source of funding is identified in brackets: [ ]. 
 
 The research is carried out by half-time graduate research assistants 
 (graduate students) under the direction of one or more faculty members. The 
 final documentation on a given project is usually in the form of the students 
 thesis (MS or Ph.D.). These theses are often published as technical reports 
 and are listed, along with an abstract in the "projects completed" section 
 of this report. In some cases technical reports are issued which are not 
 theses and these are also listed. It is also possible that a thesis is 
 produced which is not issued as a technical report. 
 
 Some of the research is the result of a research proposal and in 
 such cases a more detailed account of the proposed research can be found 
 by consulting the relevant proposal. In other cases the research is a result 
 of ideas originating with a student or staff member. In either case, an 
 introductory description of the proposed research appears when a new project 
 is introduced into the report. Thereafter only a brief synopsis is included. 
 
 Section two summarizes the projects completed during the quarter, 
 section three presents progress reports on current projects, and section 
 four introduces new projects. Projects are listed by name and a correspond- 
 ing project number is given in parentheses. 
 
2. 
 
 2. Summary of Projects Completed During the Quarter 
 
 The projects completed this quarter are listed below by project 
 name and number along with the technical report number and the abstract. 
 Some reports are available directly from the Department of Computer Science, 
 University of Illinois, Urbana, IL 61801. Others may be obtained from the 
 Engineering Documents Center, 208 Engineering Hall, University of Illinois, 
 Urbana, IL 61801 or from the IEEE Computer Society Repository, 5855 Naples 
 Plaza, Suite 301, Long Beach, CA 90803. 
 
 OTEMON (Project #95) [DCS] 
 
 A continuous waveform visual monitor was designed in the form 
 of a small, cheap TV controller. It is primarily intended for the display 
 of natural phenomena such as EKG signals, although other application can be 
 envisioned. The controller divides the TV screen into a number of "bands" 
 along which the signal is displayed. The number of bands is variable, and 
 the resolution changes accordingly. 
 
 The final documentation is an M.S. Thesis. No technical report 
 will be issued. 
 
3. 
 
 3. Progress Report on Continuing Projects 
 
 Source of funding is given in brackets: [Source] 
 
 Parallel Hardware Algorithms for High-Speed Function Generation (#73) 
 
 [DCS] 
 
 INTRODUCTION 
 
 This project considers the problem of high speed parallel hard- 
 ware function generation. The function f(x) is to be evaluated in the interval 
 [a,b] . The interval [a,b] is broken down into a few subintervals [x ,x _ ] 
 within which f is piecewise approximated by a polynomial. Each interval 
 uses a different degree polynomial. x, is called a joint. The coefficients 
 
 K. 
 
 of these polynomials are stored in ROMs. The argument x is logrithmically 
 
 distributed since it is assumed to be a floating point mantissa in the 
 
 interval [.5,1]. The goal is to minimize the average number of multiplications 
 
 M(X) needed to evaluate f(x) subject to a constraint on the number of ROM 
 
 words R n (X) where X is the vector of subinterval breakpoints (x.,x n ,... x ). 
 U Dim 
 
 PROJECT STATUS 
 
 During this quarter the final report was written and it should 
 appear during the next quarter. 
 
 Gilles Garcia 
 
4. 
 
 PREDICTORBURST (#81) [DCS] 
 
 INTRODUCTION 
 
 The goal of this project is the real-time extraction of predictor 
 coefficients from a human voice signal. These coefficients, used in the 
 linear prediction of speech, are employed so as to encrypt the message 
 or transmit it over narrow band digital data lines. 
 
 PROJECT STATUS 
 
 During this quarter, a software simulation program (in PL/l) was 
 developed for the circuit. Gate-level simulation reflecting the actual 
 signal flow was employed. A variety of input signals was used and the clock 
 rate was varied to allow examination of the dynamic behavior of the co- 
 efficients and the error signal. Initial results of the simulation were 
 the discovery that the fast clock (32 times the frequency of the sample bit 
 rate clock) used for updating the coefficients was not only unnecessary but 
 also detrimental to the stability of the coefficients, and the realization 
 that an increase in estimate accuracy is obtained when the sample-and-hold 
 is removed from the input stage. Further simulation is continuing both to 
 finalize the topology and to observe the circuit's behavior when presented 
 with different input waveforms. 
 
 Daniel Pitt 
 

 INDIRAD (#82) [DCS] 
 
 INTRODUCTION 
 
 INDIRAD is a digital A.M. receiver which uses indicator representa- 
 tion of data for high speed processing. 
 
 PROJECT STATUS 
 
 A major portion of the last quarter was spent awaiting receipt 
 of parts. Construction has begun on the ECL logic board, and about 25% of 
 it is now complete. 
 
 Two related sections of the radio were redesigned. The 4x4 multiplexer 
 was eliminated by right shifting the data in the counters the appropriate 
 number of bits using the load input of the counter (refer to Fig. 1 of 
 November, 1977 report). To control this loading the clock generator and 
 counter control were also redesigned. The new design permits the passband 
 width of the filter to be more finely adjusted, and should improve the 
 rejection of unwanted signals. 
 
 Gary Gostin 
 
6. 
 
 PEARL (#83) [UIUC Research Board] 
 
 INTRODUCTION 
 
 PEARL (Portable Evoked Average Response Laboratory) is a portable, 
 intelligent device for monitoring psychophysiological experiments and 
 collecting data. 
 
 PROJECT STATUS 
 
 This project is complete but, as yet, no final report has been 
 issued. 
 
 Tony Mui 
 
ILLIBOT (#86) [DCS] 
 
 INTRODUCTION 
 
 The goal of this project is to construct a robot capable of 
 surviving totally on its own in a potentially hostile environment. The 
 robot will require no human guidance or interference. 
 
 PROJECT STATUS 
 
 During the past quarter several approaches to the realization of 
 ILLIBOT have been considered. It is currently impractical to consider 
 constructing ILLIBOT in its present form. Instead, as previously stated, 
 we have decided to test small sections of ILLIBOT separately on board a 
 smaller robotic system presently designated ALPHA II. (See Figure 3.1) 
 ALPHA II will be connected to a DEC PDP-11/20 RT system as a peripheral 
 TTY. (See Figure 3.2). The on-board electronics consist of a command 
 controller, sensory center and motor controller. In addition, expansion 
 for a vision system is provided. The motors as well as the senses are 
 modular in that their existence is optional and their absence will in no 
 way degrade the hardware defined operations of the robot. A maximum of 16 
 senses and 16 motors are allowed in the design that is presently being 
 built. Motor timing circuits, of synchronous design utilizing 6 bit binary 
 rate multipliers, were developed and tested shortly after ALPHA I. These 
 are being used in ALPHA II. The general scheme of using a single main 
 sequencer to control the robot has been rejected in favor of a main status 
 register with subsequencer. In addition, differential feedback circuits 
 tested and built for ALPHA I will again be used for ALPHA II. 
 
 The 6 motors will be housed in a well-shielded area away from 
 the electronics. These motors, operating on a 12 volt system, will be 
 used for locomotion, directional control, rotation of the arm, a shoulder 
 joint, an elbow and the opening and closing of the hand. With the exception 
 
8. 
 
 of the locomotion motors, all are high speed low amperage motors that are 
 geared down to a low speed and high torque. An example of this is the 
 directional control motor which is a 12 VDC , PM field reversible motor 
 which yields 10 RPM at 40ma full load, with torque of 40 oz-in. Motor 
 energy (rotational) is transmitted via flexible shafting to a plate near 
 the arm where it is transferred to push/pull energy via bellcranks. These, 
 in turn, pull sheathed metal cables that cause the physical mechanical move- 
 ment in the arm. The hand described last quarter has been greatly simplified 
 so that it could be hand machined. It is presently a task as the 
 programmer is ingenous in programming the 11/20. In other words, all the 
 decision making that would be made on ILLIBOT by hardware has been moved 
 to software for ALPHA II. This ias been done for several reasons: 1) To 
 provide flexibility during research and testing. 2) To facilitate rapid 
 improvement and modifications. 3) To provide a more practical approach 
 toward the realization of ILLIBOT. 
 
 Jeff Glickman 
 
9. 
 
 ARM ROTATION 
 
 SHOULDER 
 
 LOCOMOTION 
 MOTOR 
 
 \& ^T 
 
 FLEXIBLE 
 SHAFTING 
 
 MAINTENANCE 
 PANEL 
 
 CONTROL 
 ELECTRONICS 
 
 STEEL 
 SHIELDING 
 
 DIRECTIONAL 
 CONTROL MOTOR 
 
 ALPHA II Figure 3.1 
 
10. 
 
 
 
 
 
 
 
 
 
 
 
 
 PDP 11/20 
 
 
 TTY PORT 
 
 
 
 
 
 
 i 1 
 
 
 
 EIA RS232C 
 
 TO 
 8 BIT TTL 
 
 
 
 
 
 TRANSMISSION 
 CENTER 
 
 
 
 
 V 
 
 
 
 
 
 ' 
 
 ' ♦ 
 
 
 6 WORD 
 FIFO STACK 
 
 
 FIFO 
 CONTROL 
 
 
 
 
 
 
 
 
 
 
 6th WORD 
 
 
 
 5th WORD 
 
 
 
 
 4 th WORD 
 
 
 
 
 
 
 
 
 
 
 
 
 3rd WORD 
 
 
 
 1 \ 
 
 
 
 
 
 
 2nd WORD 
 
 
 
 ' 1 
 
 
 
 
 OUTPUT 
 
 
 
 
 1 
 
 ' 
 
 
 
 
 
 COMMAND 
 CENTER 
 
 
 
 < 
 
 ' 
 
 
 J 
 
 
 
 
 
 MOTOR 
 CONTROLLER 
 
 
 MAIN 
 
 STATUS 
 
 REGISTER 
 
 
 SENSORY 
 CONTROLLER 
 
 
 
 
 
 
 
 
 
 < 
 
 ' 
 
 
 
 ♦ 1 
 
 i i 
 
 i 
 
 
 
 I 
 
 
 
 
 
 r -i__ a_, 
 
 * * * 1 OPTIONAL 1 
 
 
 • • • 1 
 
 MO 
 
 M 
 
 PL 
 
 Dl 
 0" 
 
 U( 
 
 jl; 
 roF 
 
 3-1 
 
 ■ VISION | 
 
 iR | CENTER 1 M0 
 t | SE 
 
 N | PL 
 
 1 1 
 
 L _J 
 
 DULAI 
 NSOR' 
 UG-II 
 
 f 
 
 si 1 
 
 J 
 
 SYSTEM BLOCK DIAGRAM Figure 3.2 
 
11. 
 
 PLANO BURST (#88) [DCS] 
 
 INTRODUCTION 
 
 PLANOBURST uses Burst unary processors to implement a class of 
 matrix processing functions characterized by two main features: First, 
 the operation performed on a particular element is solely a function of the 
 elements in a small surrounding neighborhood, and second, the operation 
 is to be repeated a number of times. 
 
 PROJECT STATUS 
 
 The scope of this project has now stabilized and will concentrate 
 on a visual pattern recognition system intended for use by a simple robot, 
 i.e. the class of input patterns is neither known nor bounded. 
 
 In use, the system would take a TV picture and produce from it a 
 characteristic vector which would be compared to the characteristic vectors 
 of previously encountered images. If no match were found, the vector 
 would be stored as a newly encountered image. Associated with each image 
 encountered would be a number of data bits which would guide the robots 
 reaction to a repeated encounter with an image. 
 
 FUTURE WORK 
 
 The first area of investigation should obviously be the means 
 by which a characteristic vector is to be drived from an image. Some 
 methods which have been suggested are the Fourier, Hadamard, Haar, Cosine, 
 Slant, Karhunen-Loeve and other transforms, the method of moments, auto- 
 correlation and contour analysis. It is necessary to find a method which 
 will give invariant results under the operations of translation, magnification 
 and rotation. During the next quarter an investigation will be made of how 
 each approach performs in the areas of invariance, hardware cost, speed and 
 computational efficiency, as well as related areas such as the means of compar- 
 ing stored patterns. 
 
 Michael Robinson 
 
12. 
 
 MICROCARDALERT (#94) [EE and School of Clinical Medicine] 
 
 INTRODUCTION 
 
 "CARDALERT" is a microprocessor-based cardiac signal analyzer. 
 It detects the presence of premature ventricular contractions [PVC] in 
 heart beats due to heart diseases. By detecting these abnormal contractions, 
 cardiac arrests can be predicted. 
 
 PROJECT STATUS 
 
 The ECG-PVC detect computer program has been completed and is 
 ready for demonstration purposes. Preliminary tests indicate that the 
 program detects almost all of the clearly discernable PVCs. The program 
 also detects and counts premature atrial beats (PABs) . However, no statistics 
 have been compiled as to the percent of PABs detected. 
 
 We are using the PDP8/e system presently, and have operated in 
 two modes; 1) using various recordings which are recorded at 15 times the 
 normal rate and 2) using real-time signals from electrodes placed on a 
 subject. We use a sampling interval of 250 microseconds for the tapes and 
 2 milliseconds for the real-time data . Changing between different tapes or 
 between tape and real-time requires approximately one half to one hour. 
 This change involves the modification of five variables which allow the 
 program to detect the characteristic waveforms of the different lead 
 positions which were used when recording, the various tapes. 
 
 Preliminary tests also indicate that the program is relatively 
 insensitive to the DC shifts and to high frequency noise which arises from the 
 normal movements of real-time subjects. However, the program is highly 
 sensitive to atrial fibrillation (an uncommon, erratic, extremely fast heart 
 beat) and the validity of PVC detections is destroyed if this occurs. 
 
13. 
 
 A version of the program which can be executed using the IM6100 
 is ready. This program differs from the one run using the PDP8/e in that 
 the interrupt system of the PDP8 is replaced with a DMA and UART interface 
 on the IM6100. 
 
 Jeff Anderson 
 
14. 
 
 MUMS II (#96) UNIVERSAL COMPILERS FOR MICROPROCESSORS [DCS] 
 
 INTRODUCTION 
 
 This project was undertaken to implement the language C on the MOS 
 Technology 6502 and the Intel 8080 microprocessors as part of the MUMS 
 system. The language C is well suited to this application because it 
 allows efficient utilization of machine features while not requiring much 
 in the way of translation facilities. The objective of the project is to 
 study the process of machine-independent compilation. One by-product of 
 the project has been the implementation of working compilers for the 8080 
 and 6502 processors. However, due to limited system resources, these 
 compilers cannot be released for public use. The compilers consist of 
 three programs. The first program is the front end processor of an exist- 
 ing C compiler. The second program serves as a linkage editor and can com- 
 bine several IL files into one. The third program is called COMP . See 
 the last quarterly report for a more extensive explanation. 
 
 PROJECT STATUS 
 
 To make these compilers available to the local student connunity a 
 version of COMP has been written to produce interpretive code. An interpretor 
 written in PASCAL has also been produced. This mechanism has been tested on 
 a small desk-calculator program. Testing is in progress of large programs, 
 including the C macro preprocessor. To support this interpreter, a new 
 version of COMP has been implemented which generates only the interpretive 
 code representing the compiled program. This interpretive code is suitable 
 for interpretation by the PASCAL program. Only a minor change to the COMP 
 was necessary. This interpretive code may be executed using the CYBER as 
 an interactive test bed by using the C interpreter. This allows greater 
 flexibility than we can presently achieve with the MUMS system. Users of 
 
 system are provided with a more stable environment and one can bootstrap 
 
15. 
 
 off of the CYBER rather than trying to use the microprocessors themselves 
 to develop software. 
 
 Future efforts will be towards implementing the entire cross-compiler 
 system on the CYBER. 
 
 At this point, the currently available cross-software on the CYBER is 
 as follows: 
 
 1) Intel MAC-80 assembler 
 
 2) Intel PLM compiler 
 
 3) Intel INTERP-80 simulator 
 
 4) MOSTEK ASSEMB assembler (6502) 
 
 5) Z-80 assembler 
 
 The first four are commercial products and are written in FORTRAN. The 
 
 Z-80 assembler (written by G. Lehman) is a PASCAL program supporting relocatable 
 
 code generation and external references. A linking loader will be completed 
 
 soon allowing the user to combine separate assemblies, searching a user-defined 
 
 library for unsatisfied references. 
 
 George Lehman 
 Lawrence Lopez 
 
16. 
 
 4. Progress Report on New Projects Begun this Quarter 
 
 This section introduces new projects begun during this quarter. 
 The source of funding is given in brackets: [ ]. 
 
 OLREC (#97) [DCS] 
 
 INTRODUCTION 
 
 The OLREC project is an attempt to develop an On-Line pattern 
 RECognition device. This device is to operate with only a "portable" amount 
 of hardware and is to recognize patterns regardless of translation in any 
 direction, rotation, or magnification. OLREC will not be backed-up by a 
 large computer, but rather will consist of equipment which could, for 
 example, be mounted in a robot. OLREC is to be able to recognize a pattern 
 within approximately the same amount of time as that required by a human, 
 that is, within approximately one second or less. 
 
 IMPLEMENTATION BEING CONSIDERED 
 
 Several different methods of implementing OLREC are being considered. 
 In each of these methods, invariance to translation is implemented by physically 
 moving the camera until the object is centered in the camera's field of view. 
 This can be done using motors controlled by a current-balancing network. The 
 invariance to magnification can be implemented by magnifying the image 
 electronically or with a zoom lens until some point of the image touches the 
 edge of the camera's field of view. This leaves the invariance to rotation 
 and the actual recognition still to be implemented. 
 
 One possible implementation is to store in memory several different 
 angular views of each pattern object. The acquisition of the different 
 angular views for storage would probably be facilitated by the use of a 
 radial scan camera as the input device. Once the different views of the 
 pattern objects are stored, the test object can be compared to each view of 
 each pattern object and the closest match determined. 
 
17. 
 
 Another method is to again use a radial scan camera for input 
 and to store one view of each pattern object in memory. Since a radial 
 scan camera is being used for input, however, other views of the objects 
 can be obtained by merely addressing the memory from different starting 
 locations. The test object can again be compared with several different 
 views of each pattern object and the closest match determined. 
 
 The third method again uses a radial scan camera for input. 
 This in effect, changes rotations into translations. Some sort of trans- 
 lation-independent transform can be taken of both the pattern images and 
 the test image. The closest match could then be determined in the trans- 
 form domain. The Fourier transform is one transform that exhibits trans- 
 lation independent properties. Consideration is being given to the possible 
 use of other transforms and simpler methods for implementing the Fourier 
 transform. 
 
 A fourth method consists of doing preprocessing and feature 
 extraction to both the pattern images and the test image. A feature vector 
 is then formed for each image. A clustering algorithm can be used to 
 pick the closest match. 
 
 PROJECT STATUS 
 
 OLREC is a new project and at this point each of the above 
 implementations is being investigated. Cost estimates and recognition 
 times are being calculated for each implementation. Transforms that 
 could be used for the third method are being considered as well as simpler 
 methods of implementing the Fourier transform. 
 
 Randy Moss 
 
0' ' 
 
ilOGRAPHIC DATA 
 
 T 
 
 1. Report No. 
 
 UIUCDCS-R-78-917 
 
 3. Recipient's Accession No. 
 
 \c and Subtitle 
 
 iarterly Technical Progress Report of 
 ie Information Engineering Laboratory 
 
 5. Report Date 
 ^"rnary 1 Q7ft 
 
 1 hor(s ) 
 ifnrmal-inn 
 
 Fnoinppring T.ahnratnry 
 
 8. Performing Organization Rept. 
 
 io UIUCDCS-78-917 
 
 forming Organization Name and Address 
 
 Apartment of Computer Science Information Engineering 
 
 iboratory 
 
 diversity of Illinois 
 
 rbana, IL 61801 
 
 10. Project/Task/Work Unit No. 
 
 11. Contract /Grant No. 
 
 iionsoring Organization Name and Address 
 
 2pt. of Computer Science & School of Clinical Medicine 
 diversity of Illinois 
 rbana, IL 61801 
 
 13. Type of Report & Period 
 Covered 
 
 Quarterly 
 
 14. 
 
 ,ppU-mentary Notes 
 
 hstracts 
 
 This report presents the abstracts for reports on recently 
 ompleted projects, summary information on the status of current projects, 
 nd explanations of new projects at the Information Engineering Laboratory 
 i the Department of Computer Science at the University of Illinois at 
 rbana-Champaign. 
 
 ey Words and Document Analysis. 17a. Descriptors 
 
 echnical Progress Report 
 omputer Research Report 
 
 dentif iers/Open-Ended Terms 
 
 70SATI Field/Group 
 
 ailability Statement 
 
 19. Security Class (This 
 Report) 
 
 UNCLASSIFIED 
 
 20. Security Class (This 
 UNCLASSIFIED 
 
 21- No. of Pages 
 
 17 
 
 22. Price 
 
 ' NTIS-35 ( 10-70) 
 
 USCOMM-DC 40329-P71 
 
J M 2 1978 
 

m