Background of the Invention
This invention relates in general to complex signal transformations, and more particularly, to a resistive network for performing a simultaneous complex transformation of the spatial vector formed by sampling an input signal.
Complex signal transformations such as the Fourier, Laplace and convolution integrals are routinely encountered in modern signal processing. The Fourier transform, for example, is used to convert data from one dimension, typically time domain, into another dimension, frequency domain. This conversion is advantageous in that once the data is converted to the appropriate dimension, the individual components of that dimension may be easily manipulated to achieve the desired result. The fast Fourier transform (FFT) and the discrete Fourier transform (DFT) are conventional estimations of the Fourier integral typically calculated through sequential iterations of the input data. Likewise, the inverse discrete Fourier transform (IDFT), which transposes the data back to the original dimension, is also computed in a serial fashion.
The serial transformation is still desirable in some signal processing applications wherein a precise quantitative output is required. However, many input signals are real time in nature and the conventional sequential numeric processing of the DFT, or for that matter, any other complex transformation, creates a bottleneck in the signal path limiting the bandwidth of the input signal. Applications such as speech and pattern recognition and video image processing are much more concerned with data throughput than numeric precision, and as such, are ideal candidates for the inherent parallel processing techniques of neural networks.
Thus, what is needed is a parallel processing technique to improve the data throughput of a complex transform.
Summary of the Invention
Accordingly, it is an object of the present invention to provide an improved technique of complex signal transformation.
A further objective of the present invention is to provide an improved technique of complex signal transformation comprising a resistive network having a plurality of inputs and a plurality of outputs.
Another objective of the present invention is to provide an improved technique of complex signal transformation wherein the elements of a spatial vector of an input signal are transformed simultaneously.
Yet another objective of the present invention is to provide an improved technique of complex signal transformation wherein the DFT of the input signal is provided through a predetermined connection scheme of the resistive network from the coefficients of the sum of products estimation of the DFT.
Still another objective of the present invention is to provide an improved technique of performing the DFT wherein the coefficients of the sum of products estimation of the DFT are inversely proportional to the resistor values of the resistive network.
In accordance with the above and other objectives, there is provided a resistive network for providing the complex transformation of an input signal at an output thereof, comprising a first circuit responsive to the input signal and having a plurality of tap points for providing a signal vector representative of the state space of the input signal; a plurality of first and second conductors wherein the plurality of first conductors are coupled in a predetermined manner to the plurality of tap points; a second circuit coupled between the plurality of second conductors and the output; a plurality of resistors each having predetermined a value and a predetermined connection scheme between both the plurality of first conductors and the plurality of second conductors wherein the predetermined connection scheme and the predetermined value of each of the plurality of resistors are determined from a matrix representation of the sum of the products coefficients of the complex signal transformation.
Brief Description of Drawings
FIG. 1 is a schematic diagram of a resistive network useful in the explanation of the present invention; and
FIG. 2 is a diagram showing a particular implementation of the preferred embodiment of the present invention.
Detailed Description of the Invention
The present invention is applicable to any complex signal transformation which may be expressed as a sum of products, and therefore may be represented in matrix notation. This includes many complex transforms since mathematical estimations generally exist for most complex integrations in terms of the sum of products notation. These estimations are acceptable in many applications wherein a relatively small degree of error may be neglected. One such estimation of the Fourier integral is the well known DFT which may be expressed as follows: ##EQU1## where: N=integer number of samples of the complex input
j=complex coefficient (square root of -1)
k=integer sample number of the complex input
n=integer sample number of the complex output
f.sub.k =kth sample of the complex input
F.sub.n =nth sample of the transformed complex output
Equation (1) may be expanded into real and imaginary components, including the substitution of .omega..sub.nk =exp(-j2.pi.nk), as follows: ##EQU2## where: Re()=real part of the argument
Im()=imaginary part of the argument
Equations (2) and (3) are in terms of a sum of products and as such may be expanded and expressed in vector and matrix notation as shown in equation (4): ##EQU3## where: [.omega..sub.R ]=matrix of real components of .omega..sub.nk
[.omega..sub.I ]=matrix of imaginary components of .omega..sub.nk
f.sub.R =real column input vector whose components are Re(f.sub.k) for (0.ltoreq.k.ltoreq.N-1)
f.sub.I =real column input vector whose components are Im(f.sub.k) for (0.ltoreq.k.ltoreq.N-1)
F.sub.R =real column output vector whose components are Re(F.sub.n) for (0.ltoreq.n.ltoreq.N-1)
F.sub.I =real column output vector whose components are Im(F.sub.n) for (0.ltoreq.n.ltoreq.N-1)
Equation (4) provides the basis for preforming the DFT, including all complex operations, in one matrix multiplication. For example, selecting the simple case with two samples of the complex input signal (N=2), equation (4) provides the following result: ##EQU4##
The elements of the synoptic weighting matrix .omega. may then be evaluated from the original substitution of .omega..sub.nk =exp(-j2.pi.nk), or equivalently, .omega..sub.nk =cos(2.pi.nk)-j sin(2.pi.nk). For example, Re(.omega..sub.oo) reduces to cos(0) and Re(.omega..sub.11) becomes cos(2.pi.) both of which are equal to one. Hence, the transformed output column vector F.sub.n is calculated from the sum of products of the synoptic weighting matrix .omega. and the input vectors f.sub.k, for example, Re(F.sub.0) is calculated in equation (6) as:
In neural network terminology, matrix .omega. provides the synoptic weights coupled between the input and a processing neuron, or between interconnecting layers of neurons. The input vectors f.sub.R and f.sub.I are the input activity values for the neurons, while f.sub.R and F.sub.I are corresponding output decisions based upon the input vectors and the learning threshold of the individual neurons. Thus, for an Nth order DFT, the system would have 2*N neurons for the input vector and 2*N neurons for the output vector. Each neuron for the output vector would have 2*N connections, one from each of the input vector neurons through one of the synapses.
It should be readily apparent that the accuracy of the DFT estimation is, in part, determined by the number of samples, "N". A larger sample space of the input signal corresponds to greater accuracy for the output spectrum. According to the well known Shannon's sampling criteria, "N" should be selected at twice the rate of the maximum frequency component of the input signal.
The forthcoming discussion discloses a resistive network for performing the DFT which may be realized from the aforedescribed synoptic weighting matrix .omega. as produced from the coefficients of the sum of products. As an introduction, a simplified schematic of resistive network 10 is shown in FIG. 1 to illustrate that a resistive network may be represented as a sum of products.
Resistive network 10 includes "N" number of input terminals. Voltages V.sub.12, V.sub.14, V.sub.16 through V.sub.N are applied to inputs 12, 14, 16 and "N" of resistive network 10, respectively, and a voltage, V.sub.18, is developed at output 18 in response thereto. The network is configured with resistor R.sub.12' coupled between input 12 and output 18, resistor R.sub.14' coupled between input 14 and output 18 and resistor R.sub.16' coupled between input 16 and output 18. The connection continues in a like manner through resistor R.sub.N' coupled between input "N" and output 18. In the output path, resistor R.sub.18' is coupled between output 18 and a power supply conductor typically operating at ground potential. Currents I.sub.12, I.sub.14 and I.sub.16 then flow through resistors R.sub.12', R.sub.14' and R.sub.16' in response to voltages V.sub.12, V.sub.14 and V.sub.16 respectively. Voltage V.sub.18 is developed across resistor R.sub.18' at output 18 proportional to current I.sub.18, which is the summation of currents I.sub.12 through I.sub.N. It is relatively easy to demonstrate that voltage V.sub.18 may also be expressed in terms of the summation of ratios of the input voltages to the input resistors, V.sub.i /R.sub.i', where "i" steps 12, 14, 16 through N, as follows:
Equation (7) may be simplified by selecting R.sub.18' much less than input resistors R.sub.i' thereby allowing the summation of R.sub.18' /R.sub.i' to approach zero reducing equation (7) to:
Relating equation (8) to the original equation (1) of the DFT, output column vector F.sub.n may be related to V.sub.18 the latter of which is produced from a summation of signals (currents I.sub.12 through I.sub.N) expressed as products (1/R.sub.i') of the input signal (V.sub.i). Thus, equation (8) may be treated as one element of output vector F.sub.n wherein 1/R.sub.i' corresponds to one row of matrix .omega., input voltages V.sub.i are equal to the sampled input vector f.sub.k and R.sub.18' is an overall gain constant. The values of resistors R.sub.i' are inversely proportional to the row elements of matrix .omega., and as such are also inversely proportional to the coefficients of the sum of products estimation of the DFT. Hence, equation (8) provides the basis to realize the DFT using a multi-dimensional resistive network.
A 2-dimensional resistor network is shown in FIG. 2 of the present invention to illustrate a rank N=4 implementation of a DFT having four real processing channels and four imaginary processing channels. Resistor network 30 is responsive to input signal, V.sub.IN, which is assumed to be a complex function of time, i.e., having real and imaginary components the latter of which are applied to inputs 32 and 34, respectively. Delay circuits 36 and 38 then delay the real and imaginary components of input signal V.sub.IN for predetermined increments of time. Delay circuit 36 includes tap points 40, 42, 44 and 46 for providing the spatial vector representation of the real component of length N=4. Delay circuit 38 includes tap points 48, 50, 52 and 54 for providing the spatial vector of the imaginary component of input signal V.sub.IN. Assuming equal time delays, t.sub.d, between each tap point, the spatial vector at tap points 40, 42, 44 and 46 may be expressed as Re(V.sub.IN (t.sub.0)), Re(V.sub.IN (t.sub.0 -t.sub.d)), Re(V.sub.IN (T.sub.0 -2t.sub.d) and Re(V.sub.IN (T.sub.0 -3t.sub.d)), respectively, where V.sub.IN (t) is the value of input signal V.sub.IN evaluated at time t and t.sub.0 is the non-delayed time value. Likewise, the spatial vector of the imaginary component at nodes 48, 50, 52 and 54 may be expressed as Im(V.sub.IN (t.sub.0)), Im(V.sub.IN (t.sub.0 -t.sub.d)), Im(V.sub.IN (t.sub.0 -2t.sub.d)) and Im(V.sub.IN (t.sub.0 -3t.sub.d)), respectively.
Conductors 40', 42', 44', 46', 48', 50', 52' and 54' extend from tap points 40-54, respectively. The inputs of inverters 56, 58, 60, 62, 64, 66, 68 and 70 are then coupled to conductors 40'-54' respectively, and the outputs of inverters 56-70 are coupled to conductors 72, 74, 76, 78, 80, 82, 84 and 86, respectively, wherein conductors 40'-54' and 72-86 typically run parallel to one another. Conductors 90, 92, 94, 96, 98, 100, 102 and 104 are routed in a manner typically perpendicular to conductors 40'-54' and 72-86 so as to provide a meshwork of conductors in which predetermined resistors R.sub.nk are coupled. The subscripts of R.sub.nk, "n" and "k", are integers ranging from zero to seven corresponding to conductors 40'-54',72-86 and conductors 90-104, respectively. For example, resistor R.sub.oo is coupled between conductor 40' or 72 (depending on the sign) and conductor 90.
Resistive network 10 demonstrates that a resistive network may be expressed as a sum of products, and as such it is representative of only the connection between one output conductor and the plurality of input conductors. In one case, resistive network 10 corresponds to the connection of resistors R.sub.no between conductor 90 and conductors 40'-54' and 72-86. The present invention includes the recognition that a complex transformation may also be represented as a sum of products and thereby be converted to a multi-dimensional matrix, the elements of which provide the values and connection scheme of a corresponding multi-dimensional resistive network for preforming the complex transform.
The predetermined location and value of resistor R.sub.nk in resistive network 30 is then extracted from the transpose of matrix .omega. of the sum of products estimation of equation (4). The technique of solving matrix .omega. for any "N" length spatial vector follows directly from the example of equations (2) through (5). More specifically, expanding equations (2) and (3) provides an "N" by "N" matrix of elements .omega..sub.nk wherein "n" and "k" are integers ranging from 0 to N-1. The value of resistor R.sub.nk is inversely proportional to .omega..sub.nk /N as shown in equation (8). The proportionality between a resistor and an element of matrix .omega. is determined by an independent common multiplier, "M", such that the actual value for resistor R.sub.nk is equal to [(.omega..sub.nk /N).sup.-1 * M]. Hence, because of the common multiplier "M", the actual value of resistor R.sub.nk selected for network 30 is dependent only upon a ratio to the other values of resistor matrix R. For example, the following table represents resistor matrix R formed of resistors R.sub.nk for the aforedescribed N=4 complex transformation:
Notably, the symmetry of matrix .omega. requires relatively few unique values for resistor R.sub.nk.
Recallinq the previous evaluation of matrix .omega., .omega..sub.nk may be calculated from the original substitution of .omega..sub.nk =cos(2.pi.nk)-j sin(2.pi.nk). For example, Re(.omega..sub.00) reduces to cos(0)=1 and Re(.omega..sub.12) becomes cos(4.pi.)=-1. Matrix .omega. is then commonly multiplied by 1/4, and the resulting values are inverted and transposed to obtain the resistor matrix R showing the connection scheme and value of resistors R.sub.nk. This provides a one-to-one correspondence between resistor matrix R and resistive network 30. For example, resistors R.sub.00, R.sub.10, R.sub.20 and R.sub.30 are coupled between common conductor 90 and conductors 40', 42', 44' and 46', respectively. The values for resistors R.sub.00, R.sub.10, R.sub.20 and R.sub.30 are each equal to 4*M wherein the common multiplier M may be any convenient value. Resistors R.sub.40, R.sub.50, R.sub.60 and R.sub.70 remain as opencircuits due to the infinite impedance for each value, although theoretically these resistors are coupled between conductors 90 and conductor 48-54 respectively. Negative resistor values, for example, resistors R.sub.12 and R.sub.32 are coupled between common conductor 94 and conductors 74 and 78 the latter ones of which provide signals having the opposite polarity with respect to the signals applied to conductors 2' and 46'.
The currents flowing in conductors 90-104 represent the spatial vector of the transformed output signal. For example, current I.sub.90 flowing in conductor 90 is equal to the summation of the currents flowing in resistors R.sub.00, R.sub.10, R.sub.20 and R.sub.30 and, thus, equal to element F.sub.0 of the output signal vector F.sub.n. Likewise, elements F.sub.1 through F.sub.7 of the output signal vector F.sub.n are equal to currents flowing in conductors 92, 94, 96, 98, 100, 102 and 104, respectively.
Resistor R.sub.18' is coupled between node 18 and a power supply conductor typically operating at ground potential. Conductors 90-104 may be coupled to node 18 for providing a single output signal representative of the transformed output vector F.sub.n. Alternately, conductors 90-104 may be coupled to the inputs of another resistive network, corresponding to inputs 40-54 of resistive network 30, for providing yet another layer of transformation. The complex transformation of a secondary layer need not be the same as the transformation of the preceding layer. This expansion may be continued to as many layers as required to achieve the desired signal processing.
The source code of a Fortran program is provided in Appendix A for calculating resistor matrix R for a DFT of rank N.ltoreq.2048. The program resolves the sum of products estimation into a matrix notation and calculates and transposes elements from the original matrix .omega. into resistor matrix R. Higher rank transformations may be obtained with appropriate modification of the array dimensions.
Hence, what has been described is a novel technique utilizing a resistive network for performing a parallel complex transformation of the spatial vector of an input signal.