Part 9

TABLE II -------+--------+---------+------- A | B | C | D r e | r e | r e | r e -------+--------+---------+------- 7 47 | 18 192 | 8 110 | 4 48 3 40 | 7 69 | 10 98 | 6 68 4 43 | 7 82 | 4 47 | 6 46 -------+--------+---------+-------

FUTURE PROBLEMS

Aside from the previous question of deciding on network structure, there are several other questions that remain to be studied in learning networks.

There is the question of requiring more than a single output from a network. If, say, two outputs are required for a given input, one +1 and the other -1, this runs into conflict with the incrementing process. Changes that aid one output may act against the other. Apparently the searching process depicted before with a varying bias must be considerably refined to find weight changes which act on all the outputs in the required way. This is far from an academic question because there will undoubtedly be numerous cases in which the greatest part of the input-output computation will have shared features for all output variables. Only at later levels do they need to be differentiated. Hence it is necessary to envision a single network producing multiple outputs rather than a separate network for each output variable if full efficiency is to be achieved.

Another related question is that of using input variables that are either many-, or continuous-, valued rather than two-valued. No fundamental difficulties are discernible in this case, but the matter deserves some considerable study and experimentation.

Another important question involves the use of a succession of inputs for producing an output. That is, it may be useful to allow time to enter into the network’s logical action, thus giving it a “dynamic” as well as “static” capability.

Adaptive Detection of Unknown Binary Waveforms

J. J. SPILKER, JR.

Philco Western Development Laboratories Palo Alto, California

This work was supported by the Philco WDL Independent Development Program. This paper, submitted after the Symposium, represents a more detailed presentation of some of the issues raised in the discussion sessions at the Symposium and hence, constitutes a worthwhile addition to the Proceedings.

INTRODUCTION

One of the most important objectives in processing a stream of data is to determine and detect the presence of any invariant or quasi-invariant “features” in that data stream. These features are often initially unknown and must be “learned” from the observations. One of the simplest features of this form is a finite length signal which occurs repetitively, but not necessarily periodically with time, and has a waveshape that remains invariant or varies only slowly with time.

In this discussion, we assume that the data stream has been pre-processed, perhaps by a detector or discriminator, so as to exhibit this type of repetitive (but unknown) waveshape or signal structure. The observed signal, however, is perturbed by additive noise or other disturbances. It is desired to separate the quasi-invariance of the data from the truly random environment. The repetitive waveform may represent, for example, the transmission of an unknown sonar or radar, a pulse-position modulated noise-like waveform, or a repeated code word.

The problem of concern is to estimate the signal waveshape and to determine the time of each signal occurrence. We limit this discussion to the situation where only a single repetitive waveform is present and the signal sample values are binary. The observed waveform is assumed to be received at low signal-to-noise ratio so that a single observation of the signal (even if one knew precisely the arrival time) is not sufficient to provide a good estimate of the signal waveshape. The occurrence time of each signal is assumed to be random.

THE ADAPTIVE DETECTION MACHINE

The purpose of this note is to describe very briefly a machine which has been implemented to recover the noise-perturbed binary waveform. A simplified block diagram of the machine is shown in Figure 1. The experimental machine has been designed to operate on signals of 10³ samples duration.

The operation of this machine is described in substantially greater detail in J. J. Spilker, Jr., D. D. Luby, R. D. Lawhorn, “Adaptive Binary Waveform Detection,” Philco Western Development Laboratories, Communication Sciences Department, TR #75, December 1963.

Each analog input sample enters the machine at left and may either contain a signal sample plus noise or noise alone. In order to permit digital operation in the machine, the samples are quantized in a symmetrical three-level quantizer. The samples are then converted to vector form, e.g., the previous 10³ samples form the vector components. A new input vector, ⮕Y⁽ⁱ⁾, is formed at each sample instant.

Define the signal sample values as s₁, s₂, ..., sₙ. The observed vector Y⁽ⁱ⁾ is then either (a) perfectly centered signal plus noise, (b) shifted signal plus noise, or (c) noise alone.

{ (s₁, s₂, ..., sₙ) + (n₁, n₂, ..., nₙ) (a) (Y⁽ⁱ⁾)ᵗ = { (0, ..., s₁, s₂, ..., sₙ₋ⱼ) + (n₁, n₂, ..., nₙ) (b) { (0 ... 0) + (n₁, n₂, ..., nₙ) (c)

At each sample instant, two measurements are made on the input vector, an energy measurement ‖Y⁽ⁱ⁾‖² and a polarity coincidence cross-correlation with the present estimate of the signal vector stored in memory. If the weighted sum of the energy and cross-correlation measurements exceeds the present threshold value Γᵢ, the input vector is accepted as containing the signal (properly shifted in time), and the input vector is added to the memory. The adaptive memory has 2^{Q} levels, 2^{Q-1} positive levels, 1 zero level and 2^{Q-1}-1 negative levels. New contributions are made to the memory by normal vector addition except that saturation occurs when a component value is at the maximum or minimum level.

The acceptance or rejection of a given input vector is based on a hypersphere decision boundary. The input vector is accepted if the weighted sum γᵢ exceeds the threshold Γᵢ

γᵢ = Y⁽ⁱ⁾∙M⁽ⁱ⁾ + α‖Y⁽ⁱ⁾‖² ⩾ Γᵢ.

Geometrically, we see that the input vector is accepted if it falls on or outside of a hypersphere centered at ⮕C⁽ⁱ⁾ = -⮕M⁽ⁱ⁾/2α having radius squared

Γ⁽ⁱ⁾ ‖M⁽ⁱ⁾‖² [r⁽ⁱ⁾]² = ——— + —————— . α (2α)²

Both the center and radius of this hypersphere change as the machine adapts. The performance and optimality of hypersphere-type decision boundaries have been discussed in related work by Glaser and Cooper.

F. M. Glaser, “Signal Detection by Adaptive Filters,” IRE Trans. Information Theory, pp. 87-90; April 1961.

P. W. Cooper, “The Hypersphere in Pattern Recognition,” Information and Control, pp. 324-346; December 1962.