UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN The person charging this material is re- sponsible for its return to the library from which it was withdrawn on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. To renew call Telephone Center, 333-8400 UNIVERSITY OF ILLINOIS LIBRARY AT URBANACHAMPAIGN MAR 2 1981 FEB 2 6 RECB L161— 0-10% Digitized by the Internet Archive in 2013 http://archive.org/details/burstprocessing957popp riCJLls.: uIUCDCS-R-79-957 UILU-ENG 79 1702 Final Report for the Navy for Contract N000014-75-C-0982 BURST PROCESSING by February 1979 W. J. Poppelbaum Principal Investigator i he Library of the m t Urbana-Ch?' Final Report to the Navy for Contract N000014-75-C-0982 BURST PROCESSING by W. J. Poppelbaum Principal Investigator 0. ABSTRACT To multiply two numbers with 7 bit (i.e. 1%) accuracy a 2000 transistor microprocessor needs about 10 clock-periods. A stochastic 4 computer gives the same accuracy (within one standard deviation) in 10 clock periods — but it only uses a 2 transistor AND for the operation. For the last 4 years the Information Engineering Laboratory in the Department of Computer Science at the University of Illinois has examined a "compromise" called BURST PROCESSING, which uses deterministic methods (like a microprocessor), but averages (like a stochastic machine). The fundamental idea is to perform 1-decimal digit arithmetic and to obtain accuracy by averaging over various inputs. For example 3.4 would be treated as 4444333333 and 6.2 as 7766666666. Using the insight that the average of a sum is the sum of the averages, we can use a simple adder which forms (4 + 7), etc., the average being 9.6 = 3.4 + 6.2! The actual representation uses a unary PCM frame, e.g. 7 corresponds to a "burst" consisting of the (first) seven slots of a 10- slot frame being filled. This has the advantage that, as long as the number represented does not change, it is immaterial which 10 adjacent slots ("window") we look at : A window contains always the same informa- tion. Should the information change (e.g. from 2 to 8 occupied slots), the contents of the window will increase steadily from the initial to the final value. In practice it is useful to introduce so called block- sum registers (BSR's) which look at 10 adjacent slots and put out a voltage proportional to the number of "ones" in the BSR. Besides it's simplicity, burst processing has some additional advantages: There are no correlation difficulties as in stochastics, nor do we usually have to staticize the information as in a microprocessor. Also the burst format is only 2 — times less efficient in bandwidth requirements than weighted binary: It can be used directly for audio and video transmissions. The lost bandwidth is compensated for by good noise- immunity under very high noise conditions (i.e. as much as 10% error rate!). Lastly the accuracy of burst processing increases linearly with the number of slots , as contrasted with the square-root law of stochastics . This report describes both a quasi-analog and a purely digital fashion of performing arithmetic using bursts. On the way the use of non- compacted bursts and the corresponding encoders is brought up. Then the general area of digital filters, realized in burst technology, is discussed and practical examples from the area of convolution, adaptive filtering and RF tuning and demodulation are given. Finally applications to picture processing and "spatial" versions of burst processing are mentioned and suggestions made for future areas of study. 1. INTRODUCTION The field of computation and communication — initially purely analog — has been almost entirely taken over by weighted binary (WB) digital techniques, simply because the circuit parameter tolerances are so much greater when one makes a binary decision on each pulse; also the binary representation is relatively efficient. The advent of micro- computers and packet switching only reinforced our belief in these binary digital implementations and it may seem preposterous to even suggest alternate, albeit digital, technologies. What we mean by "alternate" is "non weighted binary" (NWB) . Historically NWB systems have played an important role: The earliest digital computers were digital differential analyzers (DDA' s) in which one simply counted the number of pulses (in a given time or in a given number of time slots) . A DDA uses therefore a unary number representations : Each pulse is a marker and one counts markers. Sometimes, of course, the count will have to be displayed — one then uses a binary, octal, decimal or hexadecimal representation. When the pulses are used in a control system (actuators for rudders, antennas etc.) it is usually not necessary to specifically refer to a number syste m. More recently considerable success has been obtained by stochastic or probabilistic unary encoding (-6) (~5) (-4) (-3) (-2) (-1) (0)^ Here a number is represented by the probability of appearance of a pulse in a given time slot. The ultra-simplicity of the computational circuits in this stochastic method is well know, as is the failsoft behavior: A pulse more or less does not matter; Figure 1 shows a common way of multiplying by an AND and adding by two AND's and an OR. The crux of the method is to assess the probabilities by measuring the average frequency (the probability being the limit for an (3) infinite number of time-slot) . Unfortunately the number of time-slots (a) lltl & LOO l.L OOOO^ 1 . *...[.— _L (b) 1" SEOWNtl : Mi!B/°~ iJHU lilll ©- Figure 1 Stochastic Multiplication and Addition 2 to obtain 10% midrange-precision (with 68% likelihood) is 10 , for 1% we need 4 6 10 , for 0.1%, 10 , i.e. the precision increases only as the square root of the number of time slots. Furthermore one must make quite sure that the random pulse sequences (RPS's) which represent 2 variables (to be processed) are uncorrelated . In practice there are many applications (e.g., stochastic feed- back controls) in which 1% accuracy is quite sufficient. With a 10MHz clock -3 this means a computation time of 10 s, an often acceptable value. Note also that negative numbers can be represented by mapping the interval -1,+1 onto the probabilities from to +1. Lately transducers have been built which furnish directly RPS's . The method described in this paper, known as BURST PROCESSING (3) (BP) is the result of attempting to extend averaging techniques to a deterministic unary number representation , making sure that the complexity of the circuitry would be quite a bit lower than in WB representation, yet perhaps not as low as in stochastic methods. Two versions are discussed. In one use is made of "quantized analog" circuits, better known as "multistate (2) (23) logic" v . Perhaps the time has come to take such implementations more seriously: The recent success of linear integrated circuits lets one hope that 8- or 10-state devices will become common. But burst processing is by no means predicated on multistate devices; one can very successfully use binary logic (in NWB form!) for all computational cirucits — this second approach is also treated in detail. Before going over to a description of the fundamental principles of burst processing, it should be clearly stated that this method is not a panacea. As a matter of fact it is somewhat wasteful of bandwidth: In the 10-slot version we could represent the integers though 10 by 4 WB digits! But the advantages of BP may well make this sacrifice acceptable. Among the advantages are: 1. Precision increases linearly with the number of time-slots. No correlation difficulties. 2. Simple computational circuitry (typically less than 10% of WB systems) . 3. Possibility of on-line processing without staticizing the information: No synchronization is necessary. 4. Great error tolerance because of averaging. 5. Availability of a first appoximation at all times. 6. Novel techniques for comparing, sorting, maximum-operations etc., leading to low cost equipment. 7. Novel techniques for digital filters. 8. RC-element emulation without capacitors, an important point for integrated versions. It should be said that BP is only efficient if we can use crude approximations for our averaging process. Happily enough (see Section 4) such crude approximations are perfectly acceptable in the transmission of audio and video signals, in control-system computers (in which the output is averaged), in ranging and windowing equipment (sonar, radar) and, most importantly of all, in sampling devices for purely digital radios. As shown below, very encouraging results have been obtained in hardware realizations in all of these areas. 2. THE FUNDAMENTAL PRINCIPLES OF BURST PROCESSING AND ENCODING The idea of burst processing (see Figure 2) is to perform very low precision arithmetic (typically on single decimal digits) and to use (2) (3) appropriate averaging procedures to obtain higher accuracy Figure 2 shows for instance how one can add 3.4 and 4.2 by decomposing 3.4 into a sequence of four 4's and six 3's, while 4.2 is decomposed into a sequence of two 5's and eight 4's. A one (decimal-) digit adder then gives — as successive sums — two 9's, two 8's and six 7's. The average of the latter is clearly 7.6, i.e. the sum of 3.4 and 4.2! The fundamental problem is obviously to produce automatically, in some circuit, the required integer sequences; we shall show below how this can be done. THE AVERAGES OF LOW PRECISION ARITHMETIC OPERATIONS CAN BE MADE EXTREMELY PRECISE. EXAMPLE; 3.4 IS THE AVERAGE OF 4444333333 4.2 IS THE AVERAGE OF 5544444444 -»> 9988777777 4 4 5 4 4 4 4 3 4 3 4 3 4 3 4 3 4 3 »» A to 1- DIGIT ADDER 5 THEREFORE 3.4 + 4.2 = 7.6 AVERAGE 7.6 Figure 2 Fundamental Idea of Burst Processing A possible format for representing the integers from to 10 is a 10-slot frame (called a "block") with the integer n corresponding to n adjacent pulses at the beginning of the frame: This will be called a " compacted burst" . Instead of using 10 slots one can, of course, also use m-slots per block; systems have been built with 4 <_ m <_ 16. If we do not mention the value of m explicitly, it will be assumed that m=10. One of the interesting properties of this representation is that a "window" of length m always contains the same number of pulses , (namely (3) n) as long as we continue to represent n — quite independently of whether the beginning of the window coincides with the beginning of a block or not! The so called Block Sum Register (BSR) shown in Figure 3a exploits the above "windowing property" in that the (quantized analog or m-state, here 10-state) output is proportional to the number of CURRENT SUMMING BUS (MSDI V/ l Z2S -H-N-i" T%m% V (SOURCE STRENGTH CONTROL ) symbol: IN- BSR -¥ CURRENT OUT • NUMBER OF ONES X — R • OUT Tl ^-« C CL (CLOCK)! CLEAR) Figure 3a Block Sum Register 8 "ones'* in the shift register. Note that by adjusting V we can actually multiply this number of "ones" by a predetermined coefficient; this possibility is exploited in building digital filters (see below) using BSR's. If burst processing were to be adopted on a large scale, it would be trivial to implement a BSR according to Fig. 3a through a semiconductor house, instead of building it from a shift register and current sources. If an accuracy of 2% per step is sufficient, Ma has shown that we can use a sensing resistor (e.g. lOfi) in the ground return (23) of certain shift registers . The best performance was obtained from a Signetics 8273 as shown in Fig. 3b: Although the variation from chip to chip was from .0085V to .010V per step, for a given chip the linearity was astonishingly good, namely less than 2% variation from step to step! OUTPUTS •UA8T INPUT RESET 16 15 14 13 12 11 10 9 SIGNETICS 8273 12 3 4 5 6 7 8 OUTPUTS CLOCK CLOCK f- 1 2 — V„ SIGNETICS 8273 - 10 BIT SERIAL IN PARALLEL OUT SHIFT REGISTER MINIMUM FREQUENCY - 25 MHj NUMBER OF SAMPLE OUTPUT VOLTAGES ONES (±0002 VOLTS) 10 .144 .150 9 .153 .159 8 .162 .168 7 .171 .177 6 .180 .186 5 .189 .195 4 .198 .204 3 .207 .213 2 .216 .222 1 .223 .231 .234 .240 Figure 3b Signetics 8273 used as BSR CLOCK CLEAR 1 Y — •• BSR IS. INPUT o— ~>w_ COMPACTED + ^* BURSTS (d) CLOCK MODE ' ",., SR- 1 1 BIDIRECTIONAL BSR 4 — 'o' I s s ^ UNCOMPACTED INPUT r o s BURSTS \y CLOCK . CLEA — r~ 1'-* BSR "GATE SAMPLE ANO HOLO M>- COMPACTED BURSTS CLOCK •-♦ BSR INPUT •- ^>^ .UNCOMPACTED BURSTS (e) SL CLOCK SR I! !| II BIDIRECTIONAL BSR -J STEP INPUTc *>* ^ =t> 5$^ !=D- 3 LEVEL OUTPUT H - SR CND- HOLt L - SL Figure 4 Burst Encoders 10 It must be mentioned that the compacted burst format, although usually easier to handle, is by no means a necessity. Figure 4 shows a variety of encoders studied by Wolff . The first one (Fig. 4a) is the original ramp encoder which consists of a BSR connected as a stair- step generator and a comparator. It does actually furnish compacted bursts. Because the stairstep generated by the BSR samples the input at a time dependent on the input voltage, the input must change by less than one level of quantization during one stairstep. This obviously limits the maximum input frequency. With the addition of a sample-and- hold circuit (Fig. 4b) the bandwidth can be increased to the Nyquist limit. A different encoder using essentially the same components is the delta block encoder (Figure 4c). Here the BSR tracks the input signal by clocking in "ones" or "zeros" depending on whether it is below or above the input. Unfortunately the BSR only changes its output if the input bit is the opposite of the final bit: The tracking depends on the history of the input signal! Figure 4d shows a way out: We use a bidirectional BSR with a "one"-feed on the left and a "zero"-feed on the right. Fig. 2e shows a not uncommon 3-level version called "bibursts" which has synchronization and bandwidth advantages. Here we transmit a positive or negative pulse when the input differs from the BSR value by more than half a step. The receiver therefore does not need a clock: It derives it's clock from the edge of the input pulses and simply freezes its value if none are coming in! 11 MICROPHONE BURST ENCODER SPEAKER 10 ! TRANSMISSION BLOCK SUM REGISTER ADDITIONAL HARDWARE OVER PURE ANALOG: ENCODER : 1 BSR + 1 COMPARATOR DECODER: 1 BSR } Figure 5 Burst Encoding and Decoding In Figure 5 we show the action of a ramp-encoder when the input varies and the reconstituted signal is taken from a BSR. It should be noted that a window of length 10, sliding along the transmitted sequences gives, at any moment, the most recent approximation and that it interpolates in so doing. Voice transmission has been shown to be feasible with only 3 slots and a clock-rate of lOKHz. 12 . 5, it can be proved that the two averages differ by less than 5 percent in the 10-slot system. BURST A BURST B -INOT IN BURST FORMAT) A B J_i PA A*B 2 NOTE 1 : TNE PERVERTEO ADDER IS SIMPLY » FULL ADDER IN WHICH THE 'NORMAL CARRY OUTPUT" IS THE OVERALL OUTPUT. WHILE THE "NORMAL SUM" IS FED BACK TO "NORMAL CARRY IN" BY A MASTER/ SLAVE STORAGE DEVICE HOTE 2 *yfi IS NOT IN BURST FORMAT AND HAS TO BE COMPACTED BY AN ASSEMBLY REGISTER Figure 10 PoriforhoH AH^or 17 It was noted by Taylor and Tietz that it is possible to modify a serial full-adder in such a fashion that it furnishes an uncompacted sum of two (uncompacted) bursts with a normalizing factor of 1/2. Figure 10 shows why we call the arrangement a perverted adder (PA) : What is normally the carry output of a serial adder gives the (normalized) sum while the sum output in normal operation becomes the input to the carry-delay circuit. The carry delay is in effect a master/ slave D-f lipf lop pair (symbolized by two RS f lipf lops and appropriate gates) , which delays the carry by one clock cycle and then re-inserts it in the next cycle of the adder. Note that contrary to the selector adder, we have several collector delays and that the carry feedback limits the speed. But there are also very attractive features, in particular the fact that we can cascade many PA's if necessary! SHIFT REGISTER PA =D- CLOCK PA PA PA PA T PA PA o AB Figure 11 PA Multiplier 18 The ease with which PA's can be cascaded is used in the PA- Multiplier of Figure 11. Here we use a tree of PA's to (dynamically) add all digits in A whenever B has a "one". It is not hard to see that when we use all "ones" in B, we obtain AB/8 at the output. The figure shows the arrangements for an 8-slot burst format, because this is more efficient than the standard 10-slot format for a tree-structure, but it is, of course, possible to design a 10-slot version! We have not commented on the complexity of AU's for burst processing: By optimizing the design (LOCOBURST Project) we have been able to imitate an 8-bit microprocessor (10MHz clock) with about 10% of the gate count. In these times of ultra-cheap hardware this may not be so impressive, but the critics often forget that a simplification by a factor 10 means also 10 times less power consumption, 10 times less space, and 10 times more reliability! A. BURST DIGITAL FILTERS, CONVOLUTION, PREDICTOR THEORY and RADIOS . Like stochastics, burst processing was initially a method in search of an application. For stochastics the solution of systems of differential equations (and therefore modelling of large systems) seems to be most attractive. For burst processing one of the more promising fields is that of digital filtering. Fig. 12 shows — somewhat whimsically — why such an application is desirable: When averages of many (more or less random) numbers are calculated, each number can be a crude approximation, in particular a 8- or 10- slot burst approximation! 19 FOR RANDOMLY DISTRIBUTED NUMBERS THE AVERAGE CAN BE CALCULATED AS THE AVERAQE OF APPROXIMATIONS AVERAGE 5 •< 27 \£l/ w 1 1 ... AVERAGE OF APPROXIMATIONS 5 Figure 12 Why Burst Processing Works • We have concentrated mostly on realizing FIR (Finite Impulse Response) filters, i.e. filters in which delayed versions of the signal are multiplied by certain constants and then added : No feedback from output to input is allowed as in IIR (Infinite Impulse Response) filters. The reason for this limitation is that the noise problems in IIR filters are much more severe and the (crude) burst approximations are therefore less attractive. Nonetheless IIR filters have been shown to be viable, for instance in Pitt's PREDICTORBURST project discussed below. The theory of designing FIR digital filters from an analog version is well known and leads to a layout as shown in Fig. 13a. To implement such a filter, we simply replace the circuit delays z "" by n-bit shift registers (typically n=8, 10 or 16) and multiply their burst contents (i.e. the number of "ones") by appropriate constants c , c , etc. as shown in Fig. 13b 20 (a) Kilt I ! r . i >--♦— z'^l f~ I T I I I i 1 0) \ a D • • • Q / ' / '; ' (b) J - / CD © I© Figure 13 General FIR Filter (a) and Burst Version (b) As in our arithmetic units there is again a quasi-analog and a purely digital way of realizing Fig. 13b. In the former case c ,c etc. are simply the return voltages on BSR's and we use analog summation. Fig. 14 shows such an application (developed by Xydes) for an on-line Fourier Trans- form Unit used in a rather sophisticated frequency analyzer for speech (BURFT) . Fig. 15 shows an adaptive system (PREDICTORBURST) to calculate the predictor coefficients a. (only stage i=2 is shown explicitly) in view of bandwidth compression of human speech — as is well-known the a.'s vary quite slowly. MDAC is a multiplying digital-to-analog converter 21 which sends a 2 • s n _ 2 [+ a^l + a 3 s n _ 3 + • • . ] to a summing amplifier. The latter forms the error signal. Note the feedback from the error- output to the counters storing the a^s. s(t) Figure 14 BURFT Fourier Transform Unit 22 0/ ONE STAGE SHOWN BINARY 0" COUNTER "" 0* S„- 2 T7~T MDAC INPUT BURST ENCODER COEFFICIENT SIGN FH2 BSR OUTPUT L__ L__ p P P A u = v - I v, « s„ - I a,s n -i = e„ 1=1 1=1 EZ> sqn(e„) Figure 15 PREDICTORBURST Unit In order to obtain a purely digital version of a FIR burst filter, we can again revert to a perverted adder (PA) design: Here the coefficients c ,c~... etc. are supposed to be small integers and their (18) influence is realized by appropriate fan-outs inside the PA tree ' . Fig. 16 shows the practical layout of a Hamming Weighted Filter studied by Wells. Two clock lines (CKS and CKF) are used because the filter is actually multiplexed! In conjunction with some additional burst filters to suppress the periodic peaks due to sampling at 125 KHz, the response is down 39 db at 8 KHz from the center (null-) frequency, and down by better than 70db at 125 KHz. This is comparable to what one obtains in good communication equipment. 23 o : :n. ■ -• 1 i r * ■ - * T * D — f •> # 41S3 J 0»0 - 144 6-t>- 0*1 i --t>-o- - T L ( . 74-9 5 «■ — 0, h ._ » C «F Figure 16 Hamming Weighted Burst Filter From the outset we became very interested in digital radios and used comb-filters for tuning . The principle is shown (for AM) in Fig. 17. The idea is that if we sample at the frequency of the desired station, we shall obtain constructive interference of the samples for that station, while other stations will be subject to destructive interference. Here it must, of course, be assumed that during the integration over about 24 100 cycles the amplitude remains essentially constant: This is the case for speech and a carrier above 1 MHz, a condition always met in real life. UNDESIRED STATION AVERAGED SIGNAL (SYNCHRONOUS SAMPLING) SAMPLING WINDOWS s = (s, + s 2 + s,ts 4 » ) + i €, * e 2 * €; « {, ♦ ) NOTE 1 IN BOTH AM AND FM MODULATION THE CHARACTERISTIC AMPLITUDE AND FREQUENCY CAN BE ASSUMED CONSTANT OVER n ■ 10 - 100 CYCLES NOTE 2: TO TUNE A STATION ONE ARRANGES TO SAMPLE AT ITS FREOUENCY (TO EXTRACT THE AMPLITUDES ONE MUST ACTUALLY SAMPLE MORE OFTEN ' I Figure 17 Principle of Interference Tuner In practice it is awkward to operate with variable frequency clock in order to obtain tuning. Fig. 18 shows how this can be avoided by using (delaying) shift registers of variable length: Tuning then corresponds to adjusting the delays so that from BSR to BSR we have exactly one period of the desired station! To extract the AM modulation, Noble simply averaged the tuned signal, for instance by running it into a counter and watching the overflow. I »| DELAY REG i i J DELAY REG 1 1 | »4 DEL LzzzzzT r Y ;HaH °2iiZM-* ' — H 9s y ^ -* SAMPLES FROM ANTENNA un NOTE TO TUNE A STATION OF PERIOD T ONE CHANGES THE LENGTH OF ALL DELAY REGISTERS AVERAGED SIGNAL TUNED SIGNAL Figure 18 Delay Register Tuner 25 BURSTS FROM ANTENNA ZERO CROSSING DETECTOR • c, • INSTANTANEOUS COUNTER 4> =»ir^> BALANCE REGISTER SHIFT DOWN AVERAGING COUNTER © NOTE 1 IN ESSENCE THE CIRCUIT SIMPLY DETECTS WHETHER THE NEXT ZERO CROSSING OCCURS IOR NOT) BEFORE THE INSTANTANEOUS COUNTER REACHES THE PREVIOUS AVERAGE BETWEEN ZERO CROSSINGS THE BALANCE REGISTER MODIFIES THE AVER- AGE NOTE Z THE WIDTH OF THE WINDOW OF COMPARATOR C, CORRESPONDS TO ONE PULSE OF A BURST NOTE 3 COMPARATOR Cj AND (SIMPLIFIED) COMPARATOR C 2 CAN BE REPLACED BY DIGITAL DESIGNS Figure 19 PLL for FM Demodulation To demodulate FM we must determine the average frequency of the (tuned) antenna signal. This can be done by building a burst-implemented phase-locked-loop (PLL) and watching the average time between zero crossings c . (9) (18) (20) of its output The PLL-design in Figure 19 studied by Robinson and Mohan starts, on top, with a zero-crossing detector. Although we indicate a BSR and a comparator in this position, it is clear that we can use a purely digital design. The game is now to count clock-cyles between zero-crossings in an "instantaneous counter". If the count is high, we increase the averaging counter; if it is low, we decrease it. Of course, such a feedback system must have some inertia built into it. This is done by delaying the increase/ decrease decision in the "balance register", which has its 1/0 boundary 26 hop up and down, but only large and repeated hops lead to "1" slipping out on top, or "0" on the bottom. It is the "slipping out" which modifies the averaging register in the appropriate direction. Clearly the contents of the averaging counter can be used to retrieve the FM. 5. PICTURE, INDICATOR-AND SEQUENCY-PROCESSING This paper cannot cover the many designs in the burst area which have been examined at IEL during the past 3 years: The bibliography gives a complete list. But 3 projects stand out because of the insight they afforded us into the pros and cons of burst processing and also into future generalizations. (21) In Bracha's WALSHSTORE project we examined the feasibility of storing the "electronic hologram" of a binary input picture in such a way that the destruction of a large percentage of the memory would simply correspond to a lack of definitions of the reconstituted input. This objective was attained by using a two-dimensional Walsh-Transform. Burst processing was used (in conjunction with weighted binary techniques) because the input came from a CCD-type camera which essentially shifted out bursts. But the storage of the transform, (obtained by burst processing) was done in binary : The storage of a number in non-weighted unary fashion would be prohibitively expensive. In Gostin's INDIRAD project we used a spatial version of bursts : In a set of 7 wires we energize just one to indicate the numerical value of waveform-samples taken at times in quadrature, i.e. for sin t = + 1 and cos t = + 1. The advantage of such an Indicator Representation is that very fast arithmetic becomes trivial: All we have to do is to realize a table-look-up scheme (for sum, product etc.) in hardware. The averaging at the end then smoothes the results. Fig. 20 shows the block-diagram of INDIRAD. 27 SIN CX Register Sampler U E> CONVF.RT TO INDICATOR 7 x •> Indicator Ma i r i x Summar i on Block cjrry ♦ T 16 Bit Up/Down Counter Latch RF AMPLIFIER AND 3ANDLIMITER A/D Register Sampler w 6 CONVERT TO INDICATOR SUM latch SUM ^atch 7 x 5 Indicator Matrix Summa t i on Block borrow i I carry II) Bit Up/Down Counter ROM Latch I) /A Audio Ampl if Ler l or l->0 transition). Successive frames are inverted with respect to each other: The average is always one-half of the full swing — this has advantages in CW applications. Although the system updatesmore frequently than burst processing (as a matter of fact: It has a binary version which updates faster than any other sytem. . . ) , we must realize that arithmetic units are more complex, mostly because we have no exact equivalent of the "windowing property". Finally we should note that burst processing uses only a small number of standard elements (BSR's, comparators, counters, ANDs , ORs , and NOTs) and that designing with it is rather easy. In case relatively untrained personnel has to be used for design and maintenance, this "modular kit" feature could be very attractive! 29 6. BIBLIOGRAPHY -6 Petrovic, Siljak: "Multiplication by means of Coincidence", ACTES Proc. of 3rd Intern, Analog Comp . Meeting, Summer 1962. -5 Von Neumann: "Probabilistic logics and the synthesis of reliable organisms from unreliable components", Collected Works Vol. 6 Macmillan 1963. -9 Afuso: Quarterly Technical Progress Reports of the DCS at the UofI, starting in January 1964. -3 Ribeiro: "Comments on pulsed data hybrid computers", IEEE Transactions on Computers, Vol. EC-13 Oct. 1964. -2 Gaines: "Stochastic Computing" AFIPS Proc. SJCC Vol. 30, Summer 1967. -1 Poppelbaum, Afuso, Esch: "Stochastic Computing Elements and Systems" Proc. Fall JCC 1967. 0. Poppelbaum: "Computer Hardware Theory", Macmillan, New York 1972. 1. Poppelbaum: "A Practical Program in Stochastic Processing", Proposal to ONR for 73/74 June 1973. 2. Poppelbaum: Appendix I to above: "Novel PCM Transmission and Processing system called BURST PROCESSING", Proposal to ONR for 74/75 March 1974. 3. Poppelbaum: "Statistical Processors", DCS Report, May 1974. Also appeared in "Advances in Computers", Vol. 14, 1976. 4. Tse: "BURP-A Bundle Repeater and Restorer", MS-Thesis, DCS Report 689, Dec. 1974. 5. Mohan, Bracha, Liu: "Performance Evaluation of the Digital AM Receiver", DCS Report 757, April 1975. 6. Huberts: "NORMAN", MS-Thesis, DCS Report 715, April 1975. 7. Cutler: "Molecular Stochastics: A Study of Direct Production of Stochastic Sequences from Transducers", Ph.D. Thesis, DCS Report 723, April 1975. 8. Cutler, Ficke: "A Stochastic Control System", DCS Report 752, June 1975. 9. Poppelbaum: "Application of Stochastic and Burst Processing to Communication and Computing Systems", Proposal to ONR for 75/76, July 1975. 10. Bracha: "BURSTCALC", MS-Thesis, DCS Report 769, Oct. 1975. 11. Taylor: "An Analysis of Burst Encoding Methods and Transmission Properties", MS-Thesis, DCS Report 770, Dec, 1975. 30 12. Holberger: "An Addressable Ring Conveyor", MS-Thesls, DCS Report, 778 Jan., 1976. 13. Mohan: "The Application of Burst Processing to Digital FM Receivers", MS-Thesis, DCS Report 780, January 1976. 14. Pleva: "A Microprocessor - Controlled Interface for Burst Processing" MS-Thesis, DCS Report 812, July 1976. 15. Poppelbaum: "Application of Stochastic and Burst Processing to Communication and Computing Systems," Proposal to ONR for 76/77. July 1976. 16. Wolff: "Transmission of Analog Signals Using Burst Techniques", MS-Thesis, DCS Report 838, Jan. 1977. 17. Xydes : "Application of Burst Processing to the Spectral Decomposition of Speech" MS-Thesis, DCS Report 870, July 1977. 18. Wells: "Digital Filtering Using Burst Processing Techniques", MS-Thesis DCS Report 871, July 1977. 19. Poppelbaum: "Application of Stochastic and Burst Processing to Communication and Computing Systems," Proposal to ONR for 77/78, July 1977. 20. Robinson: "BURSTLOCK: A Digital Phase-Locked Loop Using Burst Techniques", MS-Thesis, DCS Report 872, May 1977. 21. Bracha: "WALSHSTORE: The Application of Burst Processing to Fail- Soft Storage Systems Using Walsh Transforms", Ph.D. -Thesis, DCS Report 878, Oct. 1977. 22. Pitt, Poppelbaum, Xydes: "OPTOBUNDLE - A Unique Fiber Optic Multiplier", DCS Report 882, June 1977. 23. Ma: "Block Sum Register and Burst Arithmetic", MS-Thesis, DCS Report 890, Aug. 1977. 24. Tietz: "BURSTLOGIC: Design and Analysis of Logic Circuitry to Perform Arithmetic on Data in Burst Format", Ph.D. -Thesis, DCS Report 895, May 1977. 25. Gostin: "INDIRAD: A Digital Receiver for Amplitude Modulated Signals Using Indicator Processing", MS-Thesis, DCS Report 923, June 1978. Additional information may be obtained from the Quarterly Progress Report of the IEL and the Annual Reports of the Department of Computer Science of the University of Illinois. BI.IOGRAPHIC DATA SKET 1. Report No. UIUCDCS-R-79-957 17 tic .inJ Subtitle inal Report for the Navy for Contract N000014-75-C-0982 URST PROCESSING 3. Recipient's Accession No. 5. Report Date February 1979 '. ithoi W. J. Poppelbaum, Principal Investigator ;:in£ Organization Name and Address epartment of Computer Science aiversity of Illinois rbana, IL 61801 ..^rmg Organization Name and Address arae as above. 6- 8. Performing Organization Rept. No " UIUCDCS-R-79-957 10. Project/Task/Work Unit No. 11. Contract/Grant No. 13. Type of Report & Period Covered Final Report 14. . mcntary Notes To multiply two numbers with 7 bit (i.e. 1%) accuracy a 2000 transistor micro- rocessor needs about 10 clock-periods. A stochastic computer gives the same accuracy within one standard deviation) in 10 4 clock periods— but it only uses a 2 transistor ND for the operation. For the last 4 years the Information Engineering Laboratory a the Department of Computer Science at the Unives-ity of Illinois has examined a compromise" called BURST PROCESSING, which uses deterministic methods (like a micro- rocessor), but averages (like a stochastic machine). The fundamental idea is to erform 1-decimal digit arithmetic and to obtain accuracy by averaging over various iputs. For example 3.4 would be treated as 4444333333 and 6.2 as 7766666666. Using le insight that the average of a sum is the sum of the averages, we can use a simple ider which forms (4 + 7), etc., the average being 9.6 = 3.4 + 6.2! >rds and Document Analysis. 17a. Descriptors :ary process irst Representative -gital radios "ansverseful filter 'edictor theory > -entifiers/Open-Ended Terms 1 Fie Id /Group ility Statement ^TIS-35 (10-701 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 30 22. Price USCOMM-DC 40329-P7 1 m - ° ' n I