GB2215096A - Signal processing circuit - Google Patents

Abstract

In order to correlate or convolute two complex valued sequences x(i), h(i) of samples using correlators or convolvers for use with real valued sequences, four such correlators or convolvers have been needed because the real and imaginary parts of each complex valued sequence have been each separately correlated or convolved with the real and imaginary parts of the other complex valued sequence. According to the invention, at least one such real correlator or convolver 17 has as one of its sequences the sum hR(i) + RI(i) or difference RR(i) - hI(i) of the real and imaginary parts of one of the complex valued sequences, and the amount of processing is thereby reduced. The whole operation may now be performed with three correlators or convolvers or a single correlator or convolver used three times in sequence. <IMAGE>

Description

SIGNAL PROCESSING CIRCUIT This invention relates to signal processing circuits, and especially to processor architectures to implement convolutions and correlations of complex-valued sampled data sequences.

Complex convolutions and correlations are central to signal processing and efficient methodSof implementing these operations are very useful in many applications such as radar, sonar and communications.

According to convention, two complex sequences, say a sample data sequence x(t)and a reference sequence h(i)are correlated or convolved to produce output y(k) in the following way:

where the subscripts R and I denote the real and imaginary parts, respectively.

Using real correlators or convolvers, four are employed to calculate the four products required. A typical awhitecture for effecting this is illustrated in Figure 1.

The invention provides a circuit arrangement for correlation or convolution of two sequences of complex valued samples, comprising at least one correlator or convolver for correlating or convolving two sequences of real valued samples, the correlator or convolver in use having as one of its sequences the sum or difference of the real and imaginary parts of one of the complex valued sequences.

The arrangement reduces the amount of processing necessary for correlation or convolution of the two sequences of complex. valued samples.

The entire operation may in fact be performed using three real correlators or convolvers, or one used three times in sequence, each operation being on the sum or difference of the real and imaginary parts of one of the complex valued sequences and on the real or imaginary part of the other of the complex valued sequences.

The invention will now be further described by way of example with reference to the accompanying drawings, in which: Figure 2 is block diagram indicating the operations on the sample sequences; Figures 3 and 4 show respectively block diagrams for performing convolutions and correlations, respectively; Figure 5 is a first architecture for performing those operations; c Figure 6 is a second athitecture for performing those.

operations; Figures 7 and 8 are further respective architectures for performing those operations; and Figure 9 is an example of the architecture shown in Figure 5.

As seen from Figure 2, a Convolver or a Correlator 1 operates on two sampled data sequences, 3 and 5, to produce a single output sequence 7. The samples in these sequences may in general be complex, comprising real and imaginary components. Sequence 5, the reference sequence, may be of finite length N. The other two sequences, which may be finite or infinite in length, are referred to as the input data sequence 3 and the output data sequence 7.

The basic convolution and correlation operations are illustrated in Figure 3 and 4, respectively. It must be noted that these are functional block diagrams only, illustrat t the mathematical equations. In FigureS2 and 3, the input data sequence > is clocked into a tapped delay line, consisting of single clock cycle delay and single sample storage elements 9(1) to 9( ). In any one cycle, the data samples stored in 9(1) to 9(N) are multiplied in 11 by the reference sequence coefficients and added in 13 to give one convolved or correlated data output sample. After each cycle, the data samples in the delay line are clocked one position to the right and above operation is repeated.Referring to Figures 3 and 4 it is seen that the mathematical structures of convolution and correlation are similar, Figure 3 showing convolution and Figure 4 correlation. The only differences are that the reference coefficients are conjugated (denoted by an asterisk) and reversed in ordering for correlation (Figure 4). Hence it will be appreciated that a discrete system designed to carry out correlation can also implement convolution and vice versa. So, only correlator architectures are considered in detail hereinafter. The structure shown in Figure 4 is referred to here as an Nstage correlator.

A complex convolution operation can be transformed into a complex correlation by reversing the ordering of the samples in the reference sequence and conjugating all the reference coefficient samples. Hence only the complex correlation operation is considered here. All the results are--applicable for complex convolution.

According to this invention a correlation of a complex-valued sample data sequence with an N-point complex-valued reference sequence can be implemented with three real correlators, each operating on a real-valued data sequence and an N-point real-valued reference sequence. It is known that complex correlation can be implemented using four real correlators. Hence this invention provides a significant saving in electronic devices or computation time, depending on the type of implementation. This is particularly true in the case of long correlations, such as those required for synthetic aperture rada processing.

This invention is described below with reference to Figures 5 through to 9. The complex-valued sampled data sequence, reference sequence and the output data sequence are denoted as [ xR (i) + jx1(i), for i=1,2 ... ] , [ hR (i) + jh1(i), for i=l,X, and [yR(i) + jyl (i)' for i=1,2...] respectively, where j is [yR the square root of -1. The subscripts R and I, above, refer to real and imaginary parts, respectively.

x1 (i), hR (i), h1 (i), YR(i) and Y1 (i) are allowed to take only real values.

The architecture for implementing a complex correlation, using three real correlators 17, can take any of the general forms shown in Figures 5 to 8. Each of the real correlators 17 has reference coefficients t hR(i), hI(i) or [# hR(i) t h1 (i) ] , as indicated in these figures. The part labelled 19 may be an adder or a subtractor. The choices of the parts 19 as adders or subtractors and the choices of plus (+) and minus (-) signs in the reference coefficients#h# (i), f. hI(i) and [ t + hI(i) ] in the real correlators 17, are inter related. For example, if in Figure 5, 19(1) and 19(2) are chosen as adders and 19(3) as a subtractor, then the complex correlation can be implemented by selecting the the reference coefficients in 17(1) , 17(2) and 17 as [ hR (i) hI(i) ] , h (i) and [ hR(i) + hI(i) ] . This is illustrated in Figure 9. This can be shown to carry out complex correlation by substituting mathematical expressions for real correlators 17. It must be noted that Figure 9 is only a specific case of the general structure shown in Figure 5.

It is important to note that Figures 5 through to 9 are functional block diagrams only. No assumptions have been regarding the technique used for implementing the real correlator 17. This may be implemented in hardware (i.e. hardwired devices) or using software (i.e.

programmable devices or systems). Furthermore, it is not required to have three real correlators operating in parallel. It is possible to have a single real correlator 17 and use it sequentially to implement the three real correlators. Similarly, the adders and subtractors can also be time multiplexed.

This architecture is useful in signal processing applications, especially in synthetic aperture radar processing using the architecture described in the Applicants accompanying patent application No. I/7556/MRC.

Claims (7)

1. A circuit arrangement for correlation or convolution of two sequences of complex valued samples, comprising at least one correlator or convolver for correlating or convolving two sequences of real valued samples, the correlator or convolver in use having as one of the sequences the sum or difference of the real and imaginary parts of one of the complex valued sequences.

2. A circuit arrangment as claimed in claim 1, in which the correlator or convolver in use has as its other sequence the real or imaginary parts of the other complex valued sequence.

3. A circuit arrangement as claimed in claim 1 or claim 2, in which at least one correlator or convolver for correlating or convolving two sequences of real valued samples in use has as one of its sequences the sum or difference of the the real and imaginary parts of the other complex valued sequence.

4. A circuit arrangment as claimed in claim 3, in which the last mentioned correlator or convolver in use has as its other sequence the real or imaginary parts of the said one complex valued sequence.

5. A circuit arrangement as claimed in any one of claims 1 to 4, in which there is provided three correlators or convolvers, each for correlating or convolving two sequences of real valued samples, each of which in use has as one of its sequences the sum or difference of the real and imaginary parts of one of the complex valued sequences and as its other sequence the real or imaginary parts of the other complex valued sequence.

6. A circuit arrangment as claimed in any one of claims 1 to 4, comprising a single correlator or convolver for correlating or convolving two sequences of real valued samples, and multiplexing means arranged so that in use the correlator or convolver performs three correlation or convolution operations sequentially, each operation taking place on the sum or difference of the real and imaginary parts of one of the complex valued sequences and the real or imaginary parts of the other complex valued sequence.

7. A circuit arrangement substantially as described with reference to the accompanying drawings.