Изображения страниц
PDF
EPUB

6. Ch. Pecher: La fluctuation d'excitabilit'e de la fibre nerveuse. Arch. intern. Physiol., 1939, XLIX.

7. W.A. Rosenblith: Electrical responses from the auditory nervous system. Proc. Symp. Information Networks, Polytechnic Institute of Brooklyn, 1954.

8. L.S. Frishkopf: A probability approach to certain neuroelectric phenomena. Massachusetts Institute of Technology Res. Lab. Electronics Techn. Rep. 307, 1956.

9. L.J. Viernstein, R.G. Grossman: Neural discharge patterns and simulation of synaptic operations in transmission of sensory information. 4th London symp. Inform. Theory, London 1960, to be published.

10. L.A.M. Verbeek: On error minimizing neuronal nets. Proc. Symp. Self Organizing Systems held at University of Illinois, June 1960, to be published.

11. J.D. Cowan: Many valued logics and reliable automata.

Proc. Symp.

Self Organizing Systems held at University of Illinois, June 1960, to
be published.

12. J.D. Cowan: Computation in the presence of noise. Proc. Symp. Bionics,

this volume.

TOWARD A PROPER LOGIC FOR PARALLEL COMPUTATION
IN THE PRESENCE OF NOISE

Jack D. Cowan*

Massachusetts Institute of Technology

INTRODUCTION

The work of J. von Neumann,1 and of W. S. McCulloch,

4

[blocks in formation]

and L. A. M. Verbeek, on the construction of reliable automata from unreliable components has demonstrated the effectiveness of introducing redundancy into the structure of such automata, by means of the "bundling" technique. That is, replacing each single-line automaton by a parallel net of single-line automata, subject to the constraint that "bundles" in the multiple-line automaton, carry the same amount of information as do individual lines in the single-line automaton. Thus if there are n lines per bundle, each line carries 1/nth of a bit, com

pared with 1 bit per line for the single-line automaton. The number of lines per bundle is a measure of the redundancy of parallel nets. informational constraint is introduced as follows:

The

[ocr errors][merged small][merged small][ocr errors][merged small][merged small][merged small]

Single-line automata are replaced by multiple-line automata (Figure 1) that possess n lines per bundle. A fiduciary level ▲ is set such that

Also Visiting Research Associate, Department of Electrical Engineering, Northeastern University, Boston, Massachusetts, and Communication Theory Group, U. S. Air Force Cambridge Research Laboratory, Bedford, Massachusetts.

If more than (1-A) n lines "fire", this is interpreted as "1".
If less than An lines "fire", this is interpreted as "0".

Any intermediate firing level is interpreted as a malfunction,
"i".

In the construction used by McCulloch et al., the same coding procedure is followed, but the multiple-line automaton has the following structure:

[merged small][ocr errors][merged small]

Thus each "neuron" receives inputs from all lines in both bundles. We shall not enter into an analysis of these particular systems (see Löfgren and Cowan) but merely state the results. For both constructions, if Є is the probability of malfunction associated with each component, and P is the probability of malfunction of a complete net, we obtain the following relation:

e

[merged small][merged small][merged small][merged small][ocr errors]

e

Thus P is a monotonically increasing function of 1/n, and in both cases lim P = 0. But 1/n is the number of bits per "line", and is

[ocr errors]

e

7

thus a measure of the information rate (see Shannon') in the multipleline automaton. So these results both have the property that the rate is zero for reliable computation in the presence of noise. When we consider Information Theory, this result is very surprising. The noisy coding theorem may be stated as follows:

7

If, for a communication system, there exists a certain maximum rate for transmission of information, the channel capacity C, then for transmission rates R less than C, it is possible to introduce redundancy, independent of rate, in such a way as to obtain an arbitrarily small error probability, P At rates higher than C, P increases with RC.

e

e

« ПредыдущаяПродолжить »