Correlator/convolver using a second shift register to rotate sample values

Circular correlator/convolver for discrete sample signals having a first shift register to receive the sample signals in series and a second shift register to receive the sample signals, in parallel, from the first register to circulate these signals in the second register, and once each shfit period, to apply the n signals it is storing to a group of n multipliers, Each multiplier receives also a second signal which serves as a second operand and is multiplied with the signal received from the second shift register. The correlated/convolved values are produced in response to the product signals generated by the multipliers during the time a following group of sample signals is being read into the first shift register. The design is suitable for implementing with charge-coupled devices on a single substrate.

This invention relates to convolvers and correlators for processing 
discrete signals and especially to circular convolvers or correlators. 
For continuous signal values, convolution is performed by solving the 
convolution integral: 
##EQU1## 
These formulas are especially useful for predicting a system output signal 
when x(t) is the input signal function and h(t) is the impulse response 
function. 
Correlation is closely allied to convolution in form, i.e., 
##EQU2## 
WHERE R.sub.XY (.tau.)= cross correlation function, 
T.sub.p = period of interest, 
X(t)= a first signal, and 
Y(t)= a second signal. 
If y(t) is replaced with x(t), the function R.sub.xx (.tau.), is called the 
autocorrelation function. Correlation is useful in detection of signals 
over noise and in decision theory. If the signals are periodic with period 
T, then 
##EQU3## 
Much practical signal processing uses sampling techniques because several 
signals can be multiplexed over a single channel or message path. Sampling 
is also used when the processing is to be performed digitally. An example 
of the latter is digital filtering. Sampling results in discrete signals 
to be processed whether the sampled signal is continuous or not. Discrete 
signals can be processed in either analog or digital form. The remainder 
of this description makes no distinction between the analog or digital 
forms; the remarks are applicable to both. 
The convolution integral of continuous signals is converted to a summation 
for discrete signals. For example, 
##EQU4## 
where x(n).ident. x(n.tau.)= discrete value of x(t) at sample time n.tau., 
h(n).ident. h(n).tau. )= discrete value of h(t) at sample time n.tau., 
.tau. = time interval between samples, and 
N= number of sample points 
Similarly, the correlation function for the discrete case is given by 
##EQU5## 
As an example of the calculation involved, let x(t) be represented by 
A.sub.i in the discrete case and h(t) or y(t) be represented by B.sub.i. 
Assume that the signals are periodic and four samples per period are used 
(N=4). Thus for convolving, 
##EQU6## 
Similarly, for correlating, 
##EQU7## 
In both summations, n and k will have the values 0, 1, 2 and 3. Changing 
the zero indexing to one indexing, using subscript indexing, and noting 
that the indices are modulo-N because the signals are assumed periodic, 
the summations can be written for 
__________________________________________________________________________ 
Convolution Correlation 
__________________________________________________________________________ 
n=0 : A.sub.1 B.sub.1 + A.sub.2 B.sub.4 + A.sub.3 B.sub.3 +A.sub.4 
B.sub.2 ; k=0 : A.sub.1 B.sub.1 + A.sub.2 B.sub.2 + A.sub.3 
B.sub.3 + A.sub.4 B.sub.4 ; 
n=1 : A.sub.1 B.sub.2 + A.sub.2 B.sub.1 + A.sub.3 B.sub.4 + A.sub.4 
B.sub.3 ; k=1 : A.sub.1 B.sub.4 + A.sub.2 B.sub.1 + A.sub.3 
B.sub.2 + A.sub.4 B.sub.3 ; 
n=2 : A.sub.1 B.sub.3 + A.sub.2 B.sub.2 + A.sub.3 B.sub.1 + A.sub.4 
B.sub.4 ; k=2 A.sub.1 B.sub.3 + A.sub.2 B.sub.4 + A.sub.3 
B.sub.1 + A.sub.4 B.sub.2 ; 
n=3 : A.sub.1 B.sub.4 + A.sub.2 B.sub.3 + A.sub.3 B.sub.2 + A.sub.4 
B.sub.1 ; k=3 A.sub.1 B.sub.2 + A.sub.2 B.sub.3 + A.sub.3 
B.sub.4 + A.sub.4 B.sub.1 ; 
__________________________________________________________________________ 
From the above tabulations, it can be seen that both processes involve 
shifting one set of values past the other set and forming the sum of 
products for each shift. The difference between the two processes is that 
one set of values (B.sub.i in the example) is reversed in order before the 
process is started in the case of convolution. This comports with the 
representation of convolution as "mirror and slide". Therefore, a device 
that can perform correlation can be assumed to perform convolution if one 
set of values is reversed before being applied to the device. Conversely, 
a convolver can be used as a correlator by reversing one set of input 
values. 
Based on a generalization of the above tabulations, a type of processor has 
been developed called a circular convolver or circular correlator. In such 
a device, one set of values is usually coupled to one set of multipliers' 
input terminals in a fixed configuration and the other set of values is 
applied to the other input terminals of successive multipliers in a cyclic 
manner. The product values from the multipliers are summed to produce the 
successive values of correlation or convolution. The order of the values 
determines whether the circuit is a convolver or a correlator. 
Early circular correlators/convolvers used 2N multipliers and 2N-1 delay 
stages to produce N-point sampled signals. Later improvements reduced the 
number of delay stages and multipliers, but increased the complexity of 
the multipliers because two second input terminals were required. 
Recirculating the second set of values through a reduced number of delay 
stages also reduced the number of delay stages and multipliers without 
adding to the multiplier complexity, but required complex timing circuitry 
to control the data routing in the system. 
A convolver or correlator embodying the invention has an input means for 
supplying first input signals at a predetermined rate r and shift signal 
source means for supplying shift signals at the predetermind rate r. A 
first shift register means capable of serial input and parallel output has 
a plurality of at least n stages and receives the first input signals in 
serial manner, shifting them from stage to stage in response to the shift 
signals. A second shift register means capable of both serial and parallel 
input and parallel output has a plurality of n stages which receives, in 
parallel manner, the contents of the n stages of the first shift register 
means each time the first register means receives a successive group of n 
input signals. The parallel transfer of the contents of the first shift 
register to the second shift register is effected by transfer means such 
as transmission gates which are enabled each time the first shift register 
receives a group of n input signals. There is further supplied a rotate 
signal means coupled to the second shift register for rotating the input 
signals from stage to stage at approximately the predetermined rate, a 
plurality of multipliers coupled to receive as input operands the first 
input signal from a correspondig one of the stages of the second shift 
register and second input signals for producing product signals 
representative of the value of the corresponding first input signal times 
the value of the corresponding second input signal, and summing means 
responsive to the product signals from the plurality of multiplier means 
for producing output signals.

The block diagram of FIG. 1 illustrates an embodiment of the invention 
which can employ conventional shift registers or shift registers employing 
charge coupled device (CCD) technology, which is well known in the art. An 
input section comprises a shift register 10, which can be a CCD type shift 
register or another suitable type shift register, a plurality of 
transmission gates 11, and a tapped CCD or other suitable type shift 
register 12. The output signals from the parallel output taps of the 
tapped shift register 12 are coupled to one input of a plurality of 
multipliers 14, having a second input operand signals B1-B3. Said operand 
signals B1-B3 are supplied from an appropriate signal source 60, in a 
manner well known in the art. A summing circuit which can be a plurality 
of adders 15 sums the output signals from the multipliers 14 to provide 
the output signals. Sample signals are shifted into the CCD shift register 
10 using a three-phase clock, .phi.1, .phi.2, and .phi.3. Such CCD shift 
registers are well known in the art and need not be described in detail. 
When the sample signals for one cycle have been loaded into the shift 
register 10-- in this example, three sample signals--the transmission 
gates 11 are activated by a signal V.sub.G to transfer the contents of the 
CCD shift register 10 into the parallel output ports of tapped CCD shift 
register 12. The shift register 12 also has its output terminal coupled to 
its input terminal so that the three-phase clock input signal shifts the 
contents of the tapped CCD shift register 12 in a rotational manner, i.e., 
the output signal cycles back to the input stage. While the contents of 
the tapped CCD shift register 12 are circulating, the next set of sample 
signals is being shifted into the CCD shift register 10. The 
interconnection of the devices 10, 11 and 12 will be described below in 
terms of discrete components. 
The advantage of the circuit of FIG. 1 is that the sample signals can be 
stored and processed continuously in real time. Rotating the input sample 
values in a separate shift register 12 allows the circular convolutions or 
correlation values to be continuously calculated and supplied at the 
output signal terminal 16 while the next group of samples is being stored 
in shift register 10. 
The logic diagram of FIG. 2 shows a suitable clocking circuit for providing 
the three-phase clock and the gating signal V.sub.G to the circuit of FIG. 
1. The operation of the circuit of FIG. 2 can be better understood with 
reference to FIG. 3. A clock source 20 supplies a basic pulse train such 
as shown in FIG. 3(a), which drives two groups of shift registers 21 and 
22. The output signals from the two shift registers in the group of shift 
registers 21 supplies input signals to a NOR gate 23 which produces an 
output signal when both shift registers are reset. When either shift 
register is set, the NOR gate 23 is inactivated. The output signal from 
the NOR gate 23 is shifted into the first of the shift registers of the 
group 21, thence to the second and, at the third shift signal, the group 
of shift registers 21 is reset to zero (by logic not specifically shown in 
FIG. 4) producing an output signal at the output of the NOR gate 23. FIGS. 
3(b), 3(c), and 3(d) represent the output signals .phi.1, .phi.2 and 
.phi.3 from the NOR gate 23, and the first and second shift registers of 
the group 21, respectively. The shift registers 22 are coupled as a 
modified Johnson counter producing an output signal every ninth output 
pulse from the clock 20. In this example, an output signal V.sub.G from an 
AND gate 25 indicates that a complete set of sample signals, that is, 
three sample signals have been stored and are to be gated to the rotating 
shift register 12 of FIG. 1. The output signal from the AND gate 25 is 
shown in FIG. 3(e). 
FIG. 4 is a logic diagram of the invention shown in discrete components. 
Two groups of shift registers 40 and 42 advance by a shift signal applied 
to each individual stage via leads 28 and 29. The input signals shifted 
into the stages of the first shift register 40, via a signal LOAD on lead 
30 are gated into the second shift register 42, the stages of which can be 
implemented with D-type flip-flops. The output signals from the shift 
register 42 are applied via the multipliers 44 to the adders 15 to produce 
the output signal. The coefficients, B1, B2 and B3, in the case of 
convolvers, or the second input signals, in the case of correlators, are 
coupled to the other input of each of the multipliers 44. 
The circuit of FIG. 5 is a timing circuit suitable for use with the circuit 
of FIG. 4. A modified scale-of-four counter using two flip-flops 51 and 52 
is driven by a clock signal from a clock source 50. The output signal from 
this source is divided by two by a triggerable flip-flop 54. The output 
signal from the flip-flop 54 is the shift signal which can drive both 
shift registers shown in FIG. 4. After three shift signals, when the 
samples of the cycle are loaded in the shift register 40 (FIG. 4), the 
output signal from an AND gate 53 produces the load signal which gates the 
contents of the shift register 40 into the shift register 42. The second 
AND gate 55 produces an output timing clock for the result signals from 
the adders 15. FIG. 6(a) shows the output from the clock circuit 50, FIG. 
6(b) shows the output signal from the divide-by-two flip-flop 54, and 
FIGS. 6(c) and 6(d) represent the set output signals from the flip-flops 
52 and 51, respectively. The load output signal from the AND gate 53 is 
shown in FIG. 6(e) and the output clock from the AND gate 55 is shown in 
FIG. 6(f). The shift signals driving the shift registers are those shown 
in FIG. 6(b). 
The circuits of FIG. 1 and FIG. 4. embodying the invention show how an 
auxiliary shift register for rotating the input samples permits continuous 
processing of the samples by rotating the one cycle of n input values 
through the multipliers while the second cycle of n input values is being 
loaded in the first shift register. Except for an initial delay of loading 
the first samples, the output signals from a convolver or correlator 
according to the invention are provided on a continuous and real time 
basis. 
In the circuit of FIG. 4, the multipliers 44 can be replaced by weighting 
resistors having a value dependent on the coefficient (B1-B3) coupled 
thereto and the adder 15 can be replaced by an operational amplifier 
summing circuit using suitable feedback impedance to provide the desired 
scaling factor. This would, of course, provide an analog output signal. 
The use of shift registers of the CCD type, however, cannot use weighting 
resistors as advantageously as the circuit of FIG. 4. Weighting the output 
signal of a CCD shift register by splitting the electrodes, however, is 
well known in the art. See, for example, U.S. Pat. No. 3,819,958.