 |
Description  |
|
|
BACKGROUND OF THE INVENTION
This application is related to my copending applications Ser. No. 849,589
entitled "FDM/TDM Transmultiplexer" and Ser. No. 849,279 entitled "A
Configurable Parallel Arithmetic Structure For Recursive Digital
Filtering," both filed Nov. 7, 1977 and assigned to the same assignee as
the present invention.
In each of my above-mentioned applications, I have disclosed a
transmultiplexer capable of converting 60-channel super groups from
FDM-to-TDM and vice versa. In order to process such a large number of
channels, the transmultiplexer must be capable of very high operating
speeds. An important aspect of my novel transmultiplexer is that it is
relatively small, but it was also my purpose in designing the
transmultiplexer to decrease the cost of manufacture and simplify the
maintenance of the system and, therefore, a modular design concept was
adopted. The modular design would decrease cost by allowing mass
production of a limited number of components, and field maintenance would
be simplified by enabling the user to merely replace malfunctioning
modules and return them to the manufacture of repair. In order to reduce
the size of the transmultiplexer hardware, the computational advantage of
Fast Fourier Transform (FFT) algorithm and, therefore, FFT processors were
required for both FDM-to-TDM and TDM-to-FDM conversion which were capable
of operating at high enough speeds to accomodate a 60-channel super group.
Up to this time, FFT processors have been too slow for satisfactory
transmultiplexing of a large number of channels. Known FFT processors have
also been too large, too expensive and consume too much power to meet the
size and cost saving goals of my transmultiplexer design.
Since the inputs to the FFT processor in the FDM-to-TDM conversion are all
real, it is possible to reduce the size requirements of that FFT processor
by operating it in what is commonly known as a "two channel trick" mode.
Since a modular design concept for the transmultiplexer was adopted, it
was, therefore, preferable to utilize an FFT processor which could easily
be switched to the two channel trick mode.
A further requirement of the modular design was that the user be able to
treat the processor as a black-box component so that a malfunctioning
processor could merely be removed and replaced by a spare. Presently
available FFT processors are integral parts of larger systems and,
therefore, are incapable of such "stand-alone" operation.
The requirements of the transmultiplexer are also important in other FFT
applications. A relatively small and inexpensive FFT processor capable of
very high speed and stand-alone operation would also be of significant
advantage in a wide variety of systems employing spectral analysis.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a high-speed FFT processor.
It is a further object of this invention to provide such a processor which
is relatively small and exhibits low power consumption.
It is a further object of this invention to provide a high-speed FFT
processor capable of readily switching to its two channel trick mode.
It is a still further object of this invention to provide a high-speed FFT
processor which interfaces readily with other digital processors so that
it is capable of stand-alone operation.
These and other objects are achieved by providing an FFT processor having a
novel high-speed butterfly (HSB) for performing elemental two-point
transformation, a random access read/write memory (RAM) for storing
intermediate operating results of the HSB, a coefficient PROM for holding
FFT coefficients, and an indexing and control circuit for generating
addresses for all the memories in the system and controlling the flow of
data within the system. The algorithm used in the FFT is radix-2, fixed
geometry, decimation in frequency (DIF), with ordered inputs and outputs.
This algorithm has the advantage of simpler indexing routine at the
expense of double-the-memory capacity. The HSB operates in a pipeline
fashion by using the delay in obtaining the multiplication results to
store sum and difference results and begin computing a new sum and
difference. The overall processor operates in a pipeline fashion by
utilizing a pair of input and output buffers so that the processor may be
reading from one input buffer and storing in one output buffer while
simultaneously receiving input samples and reading out output data from
the remaining buffers. Novel address generation techniques are used in
order to greatly simplify the processor hardware.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a functional block diagram of the FDM/TDM-PCM transmultiplexer
according to the present invention.
FIG. 2 is a block diagram showing the TDM-PCM to FDM operation of the
transmultiplexer according to the present invention.
FIG. 3 is a plot of the frequency spectrum occupied by a voice channel.
FIG. 4 is an illustration of the multiple image frequency spectrum which
results from sampling a voice channel at 512 kHz.
FIG. 5 is a table which illustrates the operation of the positioning
circuit in FIG. 2.
FIG. 6 is a block diagram of the positioning circuit of FIG. 2.
FIGS. 7a and 7b illustrate the frequency spectra of even and odd channels,
respectively, at the output of the positioning circuit of FIG. 2.
FIG. 8 is a block diagram showing the FDM to TDM-PCM operation of the
transmultiplexer according to the present invention.
FIG. 9 is a block diagram illustrating the arithmetic operation of a
bi-quad section, which can be used for implementing higher order recursive
filters.
FIGS. 10a-10d represent successive stages in the design of a high-speed
multiplexed bi-quad recursive filter section according to the present
invention.
FIGS. 11a-11c are block diagrams of multiplexed bi-quad recursive filters
using the filter section shown in FIG. 10d.
FIGS. 12a and 12b are block diagrams illustrating the successive operating
steps of an FFT processor.
FIG. 13 is a block diagram of an FFT processor according to the present
invention.
FIG. 14 is a block diagram of the HSB shown in FIG. 13.
FIG. 15 is a state diagram illustrating the operation of the FFT processor
shown in FIG. 13.
FIG. 16 is a block diagram showing the memory organization of the FFT
processor shown in FIG. 13.
FIG. 17 is a block diagram of the indexing and control circuit in the FFT
processor shown in FIG. 13.
FIG. 18 is a timing diagram of the control signals generated by the control
PROM shown in FIG. 17.
FIG. 19 is a block diagram of the RAM address generation circuit shown in
FIG. 17.
FIG. 20 is a timing diagram for various pass control signals of the FFT
processor.
FIG. 21 is a table indicating the sequence of complex butterfly
coefficients.
FIG. 22 is a block diagram of the coefficient PROM address generation
circuit shown in FIG. 17.
DETAILED DESCRIPTION OF THE DRAWINGS
For ease of understanding, certain signalling frequencies, sampling
frequencies and frequency bands will be used in the description of the
present invention, but it should be understood that the present invention
is not limited to operation at these frequencies.
FIG. 1 is a block diagram illustrating the function of the present
invention. Existing analog communications equipment 1 operates in FDM,
usually transmitting signals in the form of 60-channel super groups
occupying a composite band width of 312-552 kHz. Digital equipment 2,
which is finding increasingly wide-spread use in the communications field,
typically operates in TDM-PCM, and in order to provide compatibility
between digital and analog equipment, a transmultiplexer 3 is needed which
will convert the 60-channel analog FDM super group occupying a 240 kHz
band width to a TDM-PCM signal also occupying a 240 kHz band width.
FIG. 2 is a block diagram illustrating the TDM-PCM to FDM conversion
operation of the transmultiplexer according to the present invention. The
input 4 to the transmultiplexer consists of 64 TDM-PCM channels at a
sampling rate of 8 kHz. The PCM signal originally included 60 voice
channels, but four dummy channels numbered 0, 1, 2 and 63 have been added
to the original 60 PCM channels due to the binary nature of the system.
The addition of the four extra channels makes the system simpler in design
since binary numbers are easier to work with, but it should be noted that
the transmultiplexer according to the present invention could be designed
to process any number of channels. Since voice information is being
transmitted, the frequency spectrum of each channel occupies the 0-4 kHz
band as shown in FIG. 3. It is known that sampling a signal at a sampling
rate which is an integral multiple of the highest frequency in the
occupied band will result in a "folding over" effect which produces
multiple side bands. Although the sampling rate per channel in the
64-channel PCM signal is 8 kHz, the multiplexed 64 channels will have a
composite sampling rate of 512 kHz, resulting in multiple upper and lower
side bands 16 and 18, respectively, for each channel as shown in FIG. 4.
In order to achieve a base band FDM signal, it is convenient to position
the frequency spectra of each channel so that there are 64 lower side
bands 18 occupying 64 distinct 4 kHz bands between 0 kHz and 256 kHz. The
64 PCM channels are frequency positioned by positioning means 6 so that a
lower side band of each Lth channel (L = 0, 1 . . . 63) channel is
positioned at the center frequency 4L kHz. This is accomplished by
modulating the even channels up by 2 kHz and odd channels down by 2 kHz.
The position modulation can be accomplished as follows. It can be shown
that multiplication of an incoming TDM-PCM signal by the quantity
##EQU1##
where L is the channel number and n is a running multiplex frame index,
will result in the frequency spectrum of even channels being shifted up by
2 kHz and that of odd channels being shifted down by 2 kHz. Since we know
that
##EQU2##
we can see that as long as n is an integer, equation (1) will always have
a value of either +1 or -1. This can be seen from the table of FIG. 5. One
possible embodiment of the positioning means 6 is illustrated in FIG. 6.
Since the multiplication factor is either +1 or -1, the circuit can be
very simple. L and n information is supplied to a PROM 8, the indicating
that the information contains a plurality of bits supplied in parallel.
Since it is only important whether L is even or odd, the L input signal 9
to the PROM 8 need only be the least significant bit (LSB) of each
channel. The output 10 of the PROM will correspond to the value of
equation (1) above. Multiplication by -1 can be achieved by taking the
two's complement of a binary signal and, therefore, the two's complement
circuit 12 will pass either the input signal 4 or its two's complement to
the output terminal 14, depending on state of the PROM output 10.
As a result of the positioning, the even and odd channels will occupy the
frequency spectra illustrated in FIGS. 7a and 7b, respectively.
Since the lower side band 18 and upper side band 16 of the frequency
spectrum shown in FIG. 4 both consist of the same information, all of the
information in any given channel may be preserved by preserving only the
lower side band in any one of the mirrored frequency spectra. Since the
lower side bands of even and odd channels occupy 4 kHz and are also
separated by 4 kHz, it is possible to demultiplex the 64 TDM-PCM channels
into 64 individual PCM signals, pass only the lower side band centered at
4L kHz in each of the L channels and combine the individual PCM signals to
achieve a digital FDM signal having a composite band width of 0-256 kHz,
wherein each of the 64 channels occupies a 4 kHz band. The equivalent of
this is accomplished in the 3-section recursive filter 20, dual 128-point
FFT processors 22 and 24, respectively, and weighting means 26.
The upper side bands are removed by passing the TDM-PCM signal through a
sixth-order elliptic filter 20 with a 2 kHz cut-off and 50 dB out-of-band
loss. The filter will be described in more detail hereinbelow. Briefly,
the filter is realized as a cascade combination of these bi-quad sections
and is time-shared over all 64 channels. The filter is reconfigured in
real time as a low-pass filter for even channels and as a bandpass
(centered at 4 kHz) filter for odd channels. The reconfiguration is
accomplished by altering two of the coefficients of the transfer function
of each bi-quad section for odd channels. This removes the upper side
bands 16 from the frequency spectra shown in FIGS. 7a and 7b. The signal
is next supplied to FFT processors 22 and 24 which operate as a coarse
filter removing all but a selected lower side band in each channel, and
the weighting means 26 serves as an enhancement filter to remove any
overlap between the selected frequency spectra of adjacent channels.
The above-described filtering and combining operations performed by the FFT
processor and weighting means could be achieved in a 256-tap transversal
filter having a cut-off at 2 kHz, incorporating a sampling rate increase
from 8 kHz/channel to 512 kHz/channel. Since the 64 channels in the PCM
output signal Z.sub.n.sup.L are each sampled at 8 kHz, the signal
Z.sub.n.sup.L consists of samples at a rate of 512 kHz where every 64th
sample is from the same channel. The sampling rate for each channel can
thus be effectively increased from 8 kHz to 512 kHz by merely treating as
zero-valued samples the intermediate 63 samples which contain no
information from the channel in question. The sampling rate increase can
be achieved by merely inserting zero-valued samples between two samples of
the output of filter 20. Denoting this rate-increased signal
X.sub.n.sup.L, the filtering process is described as
##EQU3##
where X.sub.m-i.sup.L is the value at each tap, and H.sub.i is the
weighting factor assigned to each tap of the transversal filter.
Interchanging the summation and keeping in view that X.sub.m-i.sup.L is
zero, except when m-i is a multiple of 64, let m = 64q + p; p = 0, 1 . . .
63 and denoting these non-zero values Z.sub.q.sup.L, Z.sub.q-1.sup.L,
Z.sub.q-2.sup.L and Z.sub.q-3.sup.L for i = P, P+64, P+128 and P+192,
respectively, let
##EQU4##
then
V.sub.m = H.sub.p W.sub.q (P) + H.sub.p+64 W.sub.q-1 (P+64) + H.sub.p+128
W.sub.q-2 (P) + H.sub.p+192 W.sub.q-3 (P+64) (4)
it will be apparent to one skilled in the art that equation (3) is
equivalent to a 128-point Discrete Fourier Transform (DFT) for which the
second half of the sequence is zero. In order to save processing time,
equation (3) may be implemented in a pair of overlapped 128-point FFT
processors so that for each 128-point data input, two 128-point FFTs are
performed. The first 64 samples are augmented by 64 zeros to form a
128-point input array for FFT 22, and the second set of 64 samples are
augmented by 64 zeros to form the input array for FFT 24. The outputs of
FFT 22 and FFT 24 represent W.sub.q-1 (P) and W.sub.q (P), respectively. A
set of three previous outputs of these FFTs are also stored. These stored
data are weighted and combined according to equation (4) in a manner well
known in the art, and the output V.sub.m is a 64-channel digital FDM
signal occupying the 0-256 kHz frequency band. The four dummy channels
occupy the 0-10 kHz and 250-256 kHz band so that all voice information is
carried in the 10-250 kHz band. The signal V.sub.m is the shifted up in
frequency by 128 kHz in a digital mixer 28 which may be similar to the
positioner 6, except that since every channel is to be shifted in the same
direction rather than opposite directions, the channel information (L
input terminal 9 in FIG. 6) is unnecessary. The output of mixer 28 is
labeled U.sub.m, and the 64 channels will occupy bands at 128-384 kHz. The
60 voice information channels will occupy bands from 138-378 kHz. The
sampling rate is increased to 1536 kHz by inserting two zero-valued
sampled between each sample of U.sub.m, thus remaining in additional voice
information image bands at 650- 890 kHz and 1162-1402 kHz, and the center
component (650-890 kHz) is kept by passing it through a bandpass filter
30. This filter is realized by a combination of a 7-tap transversal filter
32 and a 1-section recursive filter 34. The recursive filter 34 consists
of one bi-quad section similar to those used in the 3-section recursive
filter 20. The zero insertion may be accomplished by merely reading zeroes
out of a memory in the transversal filter 32. Denoting the output of the
filter 34 by T.sub.K, the sampled super group is acquired by shifting the
spectrum of T.sub.K down by 338 kHz and keeping the real part (S.sub.k) of
the shifted spectra. This is done in a digital mixer 36 of the type well
known in the art. It remains only to convert the signal S.sub.K to analog
form and insert the pilot(s). This is done in a D/A converter of the type
well known in the art having a sampling frequency F.sub.s equal to 1536
kHz. The analog signal is passed through a 6-pole elliptic low-pass analog
filter 40 in which the pilot insertion takes place. The output 42 of the
analog filter 40 is an analog FDM signal occupying the 312-552 band width.
The reverse FDM to TDM conversion is illustrated in the block diagram of
FIG. 8. The incoming signal 44 consists of an FDM super group of 60 voice
channels occupying the 312-552 kHz frequency band and pilot signals at
some known frequencies. The pilots will be removed as a natural result of
the demultiplexing. The super group is translated down by 302 kHz in a
mixer 46, and the resulting signal is band limited to 250 kHz in a
low-pass analog filter 48. The analog signal is passed through an A/D
converter having a sampling frequency of 512 kHz, thereby forming an
FDM-PCM signal having 60 voice channels and four dummy channels occupying
the 0-256 kHz frequency spectrum, with each Lth channel (L = 0, 1, 2 . . .
63) occupying the 4 kHz band centered at 4L kHz. Since the 512 kHz
sampling frequency is twice the maximum frequency in the 0-256 kHz
spectrum, the spectrum will be folded over to form an image spectrum from
256-512 kHz. Since the 60 voice channels occupy only the 10-250 kHz
spectrum, the image spectrum of the voice channels will be at 266-506 kHz.
The weighting circuit 52, FFT processor 54 and 3-section recursive filter
56 perform the reverse operation of their counterparts 22-28 in the TDM to
FDM conversion.
Each channel is separated from its neighbors and shifted to a base band
signal with an 8 kHz sampling rate. The separation can be accomplished in
a 256-tap transversal filter, and the frequency shift of 4L kHz could be
performed by modifying the tap weights H.sub.i to G.sup.Li defined by
##EQU5##
where i = 0, 1, 2, 3 . . . 255; L = 0, 1, 2 . . . 63; and
##EQU6##
The filtered signal C.sub.n (L) is expressed by
##EQU7##
which can be rewritten as
##EQU8##
It will be apparent to one skilled in the art that equation (7) represents
a 128-point DFT on a sequence X(n,i) given by
X(n,i) - H.sub.i S.sub.64n-i + H.sub.128+i S.sub.64n-128i (8)
Also note that the transform is performed on an overlapped sequence--i.e.,
a 128-point transform for every 64 input data points. This will require
two real time simultaneous transforms on X(n,i). Since all of the inputs
to the weighting means 52 are real, the processor may be operated in a
"two channel trick" mode so that only a single FFT processor is required
rather than the two processors required in the TDM to FDM conversion
illustrated in FIG. 2. This two channel trick mode will be described in
more detail below.
Adjacent channel noise is removed by passing the output of FFT processor 54
through a 3-section recursive filter 56 which is multiplexed over all 64
channels and reconfigured as a low-pass recursive filter having a cut-off
at 2 kHz for even channels and a 4 kHz bandpass filter for odd channels.
As mentioned earlier, both TDM to FDM and FDM to TDM conversion will
require a 128-point FFT for every 64 data input samples. However, for the
FDM to TDM side, the FFT input X(n,i) is real (equation (7)) and,
therefore, two transforms can be performed by utilizing a single hardware
unit performing DFT, usually referred to as "two channel trick."
Furthermore, the computational advantage of FFT algorithm can be exploited
for performing DFT. Two channel trick is applied by decomposing X(n,i)
into two sequences, E(n,i) and F(n,i), for n odd and even, respectively,
and combining these sequences to form a complex sequence K(n,i), such that
K(n,i) = E(n,i) + j F(n,k)
and DFT is given by
K.sub.n (L) = E.sub.n (L) + j F.sub.n (L)
such that the DFTs of the original sequences can be retrieved by
E.sub.n (L) = 1/2[K.sub.n (L) + K.sub.n * (128-L)]
f.sub.n (L) = 1/2 [K.sub.n (L) - K.sub.n * (128-L)]
where * denotes complex conjugate. This separation of the FFT output
K.sub.n (L) into two sequences E.sub.n (L) and F.sub.n (L) can be achieved
by merely altering the programming of the bi-quad filter structure 56 to
perform the required mathematical operations.
The output format is arranged as
E.sub.n (0), E.sub.n (1) . . . E.sub.n (63);
F.sub.n (0), F.sub.n (1) . . . F.sub.n (63) . . .
corresponding to (for n even)
C.sub.n-1 (0), C.sub.n-1 (1) . . . C.sub.n-1 (63);
C.sub.n (0), C.sub.n (1) . . . C.sub.n (63) . . .
from equation (7), which is a time multiplexed sequence for 64 PCM
channels.
For the TDM to FDM side, this assumption is not true; hence, two FFT
processors are required. Therefore, a total of three FFT processor modules
are required in the transmultiplexer. The output C.sub.n.sup.L is a PCM
signal in which the frequency spectrum of each channel contains multiple 4
kHz side bands which are spaced by 4 kHz, and the side bands occupied by
the even and odd channels are offset by 4 kHz relative to each other. The
recursive filter output is modulated up and down by 2 kHz for even and odd
channels, respectively, in a multiplier 58 which may be identical to the
positioning means 6 shown in FIG. 2. The real part of the resulting signal
E.sub.n.sup.L is selected at 60 in a manner well known in the art, and the
resulting signal is the desired TDM-PCM signal.
The two most important components in the above-described transmultiplexer
are the recursive filters and the FFT processors, which constitute
approximately 80% of the hardware needed for implementation of the
transmultiplexer. These will now be described in detail.
It was discovered by means of computer simulation that the out-of-band loss
requirements of the transmultiplexer could be achieved by cascading three
bi-quad section recursive filters, but it was necessary to design such a
cascaded arrangement of bi-quad sections which was capable of being
multiplexed over all 60 channels of the super group and which was also
capable of being reconfigured for even and odd TDM channels as a low-pass
and bandpass filter, respectively.
The transfer function of a digital filter can be expressed as a ratio of
polynomials in Z.sup.-1 given by
##EQU9##
where Z.sup.-i represents i units of delay and a.sub.i and b.sub.i are the
coefficients. This direct form can be realized by either a parallel or
cascade combination of second-order sections (two poles, two zeros), such
as that shown in FIG. 9. This second-order section is also known as
bi-quad because of its bi-quadratic nature. Different filter forms can
differ substantially in the amount of required coefficient accuracy. In
particular, a direct form suffers in this respect when compared to other
forms such as cascade or parallel combination of bi-quad sections. The
transfer function of a bi-quad section in Z-domain is given as follows:
##EQU10##
The set of difference equations describing a bi-quad section derived from
equation (10) is given below:
W.sub.K = X.sub.K + b.sub.1 W.sub.K-1 + b.sub.2 W.sub.K-2 (11)
y.sub.k = w.sub.k + a.sub.1 W.sub.K-1 + a.sub.2 W.sub.K-2 (12)
where X.sub.K is the input, Y.sub.K is the output and W.sub.K 's are the
intermediate results.
From a computational point of view, this set of equations can be
represented as
##EQU11##
where C.sub.j 's are the coefficients, .psi..sub.j are the data and
.theta..sub.j is the result.
A simple structure for computing equation (13) is shown in FIG. 10a. A PROM
62 stores the coefficients C.sub.j and supplies them to a multiplier 64
synchronously with the incoming data stream .psi..sub.j, and the products
are accumulated in the accumulator 68 and composed of an adder 66 and a
latch 67. As shown in FIG. 10b, the simple structure of FIG. 10a can be
improved by adding a scaler 70 in the feedback loop of the accumulator to
limit the magnitude of the output .theta..sub.j, and by also adding a
separate storage device 72 so that the inputs X.sub.K may be added
directly to the accumulator via tri-state parallel bus 74, thus
eliminating the unnecessary multiplication of the inputs X.sub.K by unity
coefficients. The use of a tri-state bus--i.e., a bus having only
tri-state outputs connected thereto--eliminates the need for multiplexers
to connect the various component outputs to the common bus, and results in
a significant increase in operating speed.
The overflow in two's complement number system can be detected by the
following Boolean expression:
OVFL = Z.sub.s .multidot. X.sub.s .multidot. Y.sub.s + Z.sub.s .multidot.
X.sub.s .multidot. Y.sub.s (14)
where X.sub.s and Y.sub.s are the signs of addends and Z.sub.s is the sign
of the result. The first term is true for an overflow as a result of
addition of two large positive numbers, while the second term is true for
addition of two large negative numbers. To prevent the modulo wrap around
of the adder, a maximum allowable positive number or negative number can
be loaded into the accumulator for first or second term being true
respectively. This can be achieved by using three tri-state buffers 76, 78
and 80, and an overflow detection circuit 82 as shown in FIG. 10c. Buffer
76 contains the maximum positive number, buffer 78 contains the maximum
negative number and buffer 80 contains the output of the adder. One of
these three buffers is enabled, according to equation (14). Three
registers labeled R.sub.1 through R.sub.3 provide the required storage.
R.sub.1 contains W.sub.K-1 while R.sub.3 contains W.sub.K-2 and R.sub.2 is
used as a scratch pad memory. All these registers have tri-state outputs
for interdata transfer. In FIG. 10c, the storage device 72 has been
replaced by input terminal 84 in order to provide for continuous
operation.
The speed of the structure of FIG. 10c can be increased by adding another
multiplier. Some of the commercially available parallel multipliers, such
as TRWs, MPYAJ series, have built-in registers for holding the operators
(multiplier, multiplicand and result) and provide tri-state output also. A
structure using two of these multipliers is shown in FIG. 10d. Note that
register R.sub.3 is eliminated due to the fact that W.sub.K and W.sub.K-1
have to be loaded to the internal registers of the multipliers M1 and M2
only once in the whole computation cycle. A program for this bi-quad
section operation is written as follows:
______________________________________
Operation Interpretation
______________________________________
1. 0 .fwdarw. ACC Clear accumulator
2. X.sub.K + ACC .fwdarw. ACC;
Load input and multipliers
R.sub.1 .fwdarw. M.sub.1 ; R.sub.2 .fwdarw. M.sub.2
3. M.sub.2 .times. b.sub.1 + ACC .fwdarw. ACC
Calculate feedback loop
4. M.sub.2 .times. b.sub.1 + ACC .fwdarw. ACC,
R.sub.2 .fwdarw. R.sub.2
5. ACC .fwdarw. R.sub.1
W.sub.K-1 .fwdarw. W.sub.K-2 ; W.sub.K .fwdarw.
W.sub.K-1
6. M.sub.1 .times. a.sub.1 + ACC .fwdarw. ACC
Store W.sub.K
7. M.sub.2 .times. a.sub.2 + ACC .fwdarw. ACC
Calculate feed forward loop
8. ACC .fwdarw. D/A Output Y.sub.K
9. Repeat 1 through 9
______________________________________
where M.sub.1 and M.sub.2 are the internal holding registers of the
multipliers. Some of the operations can be performed simultaneously.
The bi-quad section discussed above can be multiplexed to realize higher
order filters utilizing parallel or cascade structures. Parallel
realization would require holding the input while the structure is
multiplexed for M sections, and also retaining the contents of the
accumulator between sections. In cascade realization, the output of the
previous section becomes the input to the next section. This can be
accomplished by retaining the contents of the accumulator instead of
clearing it after the bi-quad section is done. Also, no new input X.sub.K
would be required, but different coefficients corresponding to the
transfer function of each cascaded filter would be supplied, and the
length of the program would become M times the original program described
earlier, where M is the number of cascaded filter sections.
The multiplexing requires the addition of storage to the basic bi-quad
section. A RAM may be used for this purpose. The required RAM capacity
would be N .times. 2M words, where M is the number of bi-quad sections per
filter and N is the number of channels to be multiplexed. This capacity is
dependent on computational capacity of the bi-quad which, in turn, depends
on the multiplier speed. The state of the art is about 5 MHz multiplying
speed for a parallel multiplier. Thus, with two multipliers, a throughput
of 2-2.5 MHz for this bi-quad can be achieved. For audio applications
where sampling frequency is 8 kHz, a total of 300 such bi-quad sections
can be multiplexed requiring 600 words of storage. A tri-state memory 86
may be directly attached to the bi-quad structure without any change in
the bi-quad structure itself. A different program would be required, and
the transfer of data is between memory 86 and registers R.sub.1 and
R.sub.2 instead of intertransfer between the registers as described
earlier. Registers R.sub.1 and R.sub.2 are retained for scratch-pad usage.
The bi-quad computing structure described above can be viewed as a special
purpose microprocessor which can be configured to a desired filter by
programming. The programming is performed via a control vector or
microinstruction [.PHI.]. This microinstruction has P elements which are
divided into three fields, P.sub.1, P.sub.2 and P.sub.3. P.sub.1 provides
various controls for the arithmetic unit; P.sub.2 provides the necessary
address for the RAM; and P.sub.3 provides the address for the coefficient
PROM. Thus, vector [.PHI.] can be represented as:
[.PHI.] = [P.sub.1 P.sub.2 P.sub.3 ] (15)
this vector can be the output of a PROM, which is described as a control
PROM or microsequencer. A set of such vectors constitute a program such as
described above.
If there are N filters, each having a varying number of bi-quad sections
M.sub.i, where i = 1, 2 . . . N, and each section requires the performance
of n operations, then the total length of the control PROM is given by
##EQU12##
so that the control PROM requires L .times. P capacity. FIG. 11a
represents a block diagram of a filter having this control PROM. The
double lines represent two or more lines in the bus. A divide-by-L counter
88 and a control PROM 90 will control the operation of this filter.
The length L can be reduced by looping the program over similar filters,
forming groups. A simplest looping example would be a single filter having
M sections multiplexed over N channels. In this case, the length of the
PROM will be reduced to L.sub.1 given by L = n .times. M .times. N.
A further reduction in the size of control PROM is achieved by providing an
extra counter 92 which counts the number of filters being multiplexed N.
The address for individual section storage will still be provided by
[.PHI.], but this modification will reduce the length of the vector
[.PHI.] since part of field P.sub.2 will be provided by the output of the
counter, and the length L.sub.2 of the control PROM will be given by L = n
.times. M. The modified control block diagram is shown in FIG. 11b.
A generalized example can be given by forming N.sub.j groups of the total N
filters and assuming that N.sub.1 filters contain M.sub.1 bi-quad
sections; N.sub.2 filter contains M.sub.2 bi-quad sections and so on, such
that j programs will be required to process N.sub.j groups. These j
programs can be stacked in the control PROM and they can be accessed by
decoding the N counter output in a decoder 94 and using this output as an
offset to the address provided by the sequence counter L. A change of
stack will accompany by resetting of the L counter. The final block
diagram is shown in FIG. 11c. The L counter is a variable modulo counter
to accommodate various lengths of filter programs.
As mentioned above, it was discussed by means of computer simulation that
the out-of-band loss requirements for the filters 20 and 56 in FIGS. 2 and
8, respectively, could be achieved by cascading three of the bi-quad
section recursive filters shown in FIG. 10d in order to form a single
sixth-order elliptic filter. Since the system requires 60 channels with a
sampling frequency of 8 kHz to be multiplexed over this filter, the
structure shown in FIG. 11b is used. The coefficient PROM is a 32 .times.
8 organization for storing three values of each of the non-unity
coefficients a.sub.1, a.sub.2, b.sub.1 and b.sub.2 in equations (11) and
(12) above. The control PROM 90 is a 32 .times. 16 organization for
providing a control vector [.PHI.] with 16 elements. The divide-by-L
counter 88 is a divide-by-32 counter, while the divide-by-N counter 92 is
a divide-by-64. Three LSBs for RAM address are provided by [.PHI.], while
the RAM 86 contains 256 .times. 16 words. The number system used is two's
complement, and the internal computation is rounded off to 16 bits with
saturating overflow. Multipliers M.sub.1 and M.sub.2 are 16 .times. 16
parallel multipliers, such as MPY16AJ, manufactured by TRW. In the TDM to
FDM conversion, the input to the 3-section recursive filter 20 is complex,
having both real and imaginary components due to the positioning operation
in which the incoming PCM signal was multiplied by a complex quantity.
Thus, both real and imaginary components for each channel must be filtered
in the filter 20, resulting in a requirement of two filters per channel.
Since each filter includes three sections and must be multiplexed over 64
channels, the total requirement of bi-quad sections is 64 .times. 3
.times. 2 = 384 bi-quad sections. Since, as discussed above, the capacity
of the filter structure shown in FIGS. 10d and 11b for a clock frequency
of 16 MHz is only 300 bi-quad sections, two filter structures, one for the
imaginary components and one for the real components, are used to fulfill
the requirements of filter 20 in FIG. 2. The filter 34 in FIG. 2 is only a
1-section recursive filter multiplexed over 64 channels, thus resulting in
a bi-quad section requirement of 64 .times. 2 = 128 bi-quad sections, and
a single filter structure is sufficient. In the FDM to TDM conversion, the
input signals to the 3-section recursive filter 56 is always complex, so
that two high-speed multiplexed bi-quad structures are required as in TDM
to FDM conversion.
In order to achieve the transmultiplexer of the present invention, it was
necessary to provide an FFT processor capable of performing the required
128-point FFT as quickly as the 128 samples are provided. At a sampling
rate of 512 kHz, the total time allowed to perform a 128-point FFT is 250
microseconds. It was also desirable to provide such a processor having low
power consumption and small size. Another important feature in the FFT
processor was that it should be capable of "stand-alone" operation--i.e.,
it should interface readily with other digital processors to enable the
user to treat it as a black box component in the signal processing system.
Finally, it was necessary to provide an FFT processor having the
capability of performing 128-point FFT on two real channels simultaneously
(two channel trick).
The algorithm chosen for the FFT is radix-2, fixed geometry, DIF, with
ordered inputs and outputs. This algorithm has the advantage of a simpler
indexing routine at the expense of double-the-memory capacity. Parallel
multipliers are used in the complex arithmetic unit (Butterfly). DIF
computation involves six additions and four multiplications. The additions
are done before multiplication, and the multiplier delay is used for
storage, which blends nicely with fixed geometry algorithm. The processor
also has the flexibility of performing 256-point FFT or 128-point FFT on
two real channels simultaneously (usually referred to as two channel
trick) with a small external circuitry. Two's complement fixed point
arithmetic is used, with computational word length of 16 bits and
coefficient word length of 12 bits. Automatic array scaling is utilized
between passes with multiplication results rounded off to 16 bits.
The algorithm chosen for the FFT is a radix-2, fixed geometry, DIF, ordered
inputs and outputs and is shown only for 8-point FFT in FIG. 12a. The
input data is arranged sequentially, and two complex data points, P and Q,
spaced N/2 (N being the total number of points) are processed through the
complex relations given by the following equation:
P' = 1/2 (P + Q)
q' = 1/2 (p - q) .times. w (17)
where P' and Q' are two new complex points generated by the arithmetric
process, and W is a complex coefficient. As is known in the art, complex
coefficients are generally written in the form
##EQU13##
for time domain-to-frequency domai | | |
