CROSS REFERENCE TO RELATED APPLICATION
This application is being filed concurrently with an application
entitled Code Division Multiple Access (CDMA) System and Method which is herein
incorporated by reference as if fully set forth.
BACKGROUND OF THE INVENTION
Field Of The Invention
The present invention relates generally to digital filtering
techniques for code division multiple access telecommunication. More specifically,
the invention relates to a highspeed, multichannel, finite impulse response filter
architecture which obviates multipliers throughout the filter structure.
Description Of The Related Art
Communications technology today includes the use of spread
spectrum modulation or CDMA (code division multiple access) for pointtomultipoint
telecommunications. CDMA has long been used in military applications due to the
difficulty to detect and jam the transmission. This attribute is due to a wireless
communication technique that uses a transmission bandwidth much greater than the
information bandwidth of a given user. All users communicate with each other or
a common receiver over the same bandwidth and are identified by a particular code.
Multiple access is provided through the sharing of a large common bandwidth thereby
increasing overall system performance.
High tolerance to intentional or unintentional interference
and the ability to communicate with a large population of users in a common geographical
area make CDMA communication techniques attractive for commercial applications.
Since each user in a CDMA communication system transmits and receives data or communication
signals over the same frequency bandwidth, guard band requirements are lessened
and the capacity of the communication system increases.
Each communication channel within the communication system
typically uses DSP (digital signal processing) hardware and software to filter,
weight, and combine each signal prior to transmission. The weighting, filtering
and combining of multiple signal channels is performed in the transmit circuitry
of a CDMA communication system base station.
Prior art CDMA modems require many multipliers and binary
adders for channel weighting and combining. The filter operation used is equivalent
to that of a FIR (finite impulse response or transversal) structure. Each individual
FIR filter used also requires many multipliers and adders.
A multiplier implemented in digital form is inefficient
and expensive. The expense is directly related to logic gate count. Binary adders
are less costly than binary multipliers, however, their use should be minimized.
To implement a design using binary multiplication and addition into an ASIC (application
specific integrated circuit) would be expensive to manufacture and would result
in a more inefficient and slower signal throughput.
One disadvantage of FIR filters is the computational complexity
required for each output sample. For example, for each output sample, N multiplyaccumulate
(MAC) operations need to be performed. To those knowledgeable in the state of the
art, disclosed in
U.S. Patent No. 4,811,262 (White
) and
U.S. Patent No. 4,862,402 (Shaw et al.
) are digital filter structures obviating multipliers. Both referenced
patents disclose a reduction or elimination of multipliers in digital FIR filters
by storing the weighting coefficients in memory. However, neither referenced filter
structure, or the prior art has been optimized for multichannel operation.
The disadvantage with prior art CDMA modems is the ability
to weight, filter, and combine a plurality of single bit valued signal channels
efficiently and accurately. When a multiplicity of signal processing channels are
involved, the consistency between channels becomes important and the cost of hardware
per channel escalates.
In a CDMA communication system, it is necessary to use
the minimum amount of power to achieve the minimum required BER (bit error rate)
for maximum user capacity. Since CDMA communication systems allocate the same transmission
bandwidth to all users, controlling the transmitted power of each user to the minimum
required to maintain a given signaltonoise ratio is paramount. Since each user
employs a wide band signal occupying the entire frequency bandwidth for a finite
duration, each user contributes to the overall background noise that effects all
users. Therefore, the lack of power control will increase usertouser interference.
Each channel must have appropriate individual weights applied
so that the same relative amplitudes are transmitted. After the weighting operation,
each data stream is represented by multibit values. These are typically summed together
in a large digital summing circuit that consists of a tree of numerous two input
adders.
The weighted and summed digital values are then filtered
in a conventional FIR filter. The multipliers in the FIR process the multibit data
and weighting coefficients to the desired precision.
A multichannel filter for a CDMA modem constructed according
to the teachings of the prior art would require separate FIR integrated circuits
rather than total integration onto an economical ASIC (application specific integrated
circuit).
Accordingly, there exists a need for a multichannel CDMA
modem FIR filter architecture which uses weighting coefficients, either fixed or
variable through adaptation, operating with the accuracy and speed of multiplierless
filters.
SUMMARY OF THE INVENTION
The efficient, multichannel filter for CDMA modems of the
present invention allows multiple channels consisting of serial, digital bit streams
to be filtered by digital signal processing techniques performing sample weighting
and summing functions. Each individual channel may have custom weighting coefficients
or weighting coefficients common for all channels. If the weighting coefficients
are by adaption, the same approach may be taken.
The multichannel FIR filter presented is implemented with
no multipliers and a reduction in the number of adders. To increase the speed of
operation, the filter structure utilizes LUTs (lookup tables) storing the weighting
coefficients. The invention can be constructed either as a FPGA (field programmable
gate array) or an ASIC (application specific integrated circuit). The use of LUTs
save significant chip resources and manufacturing costs.
Accordingly, it is an object of the present invention to
provide an efficient CDMA FIR filter structure for multichannel applications.
It is a further object of the invention to provide a multichannel
FIR filter structure of reduced complexity and increased performance.
If is a further object of the invention to provide a multiplierless,
multichannel FIR filter.
Other objects and advantages of the system and method will
become apparent to those skilled in the art after reading the detailed description
of the preferred embodiment.
BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 is a block diagram of a typical, prior art, single input FIR filter.

Figure 2 is a block diagram of a typical, prior art, single input FIR filter
structure.

Figure 3 is a block diagram of an alternative implementation of a prior art,
single input FIR filter structure.

Figure 4A is a block diagram of a single channel of a multichannel FIR filter.

Figure 4B is a detailed block diagram of a multichannel FIR filter.

Figure 5 is a block diagram showing a first refinement.

Figure 6 is a block diagram showing a second refinement.

Figure 7 is a block diagram of the multichannel processing element.

Figure 8A is a global block diagram of a LUT table.

Figure 8B is a detailed block diagram showing the multichannel LUT input
of the present invention.

Figure 9 is a detailed block diagram of the preferred embodiment.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
A multichannel FIR filter for CDMA modems is described
with reference to the drawing figures where like numerals represent like elements
throughout. Such modems are used in multichannel wireless communication stations
in conjunction with the transmission and reception of communication signals.
By way of background, many systems have the property of
having their outputs at a given instant of time depend not only on the input at
the time, but on the entire, or immediate history of the input. Such systems are
said to have memory, averaging past and present samples in arriving at an output.
It is necessary to separate systems with memory into the classes of discrete and
continuous systems. A discrete system is one whose inputs and outputs are sequences
of numerical values rather than continuous functions of time.
A sequence of discrete values can be represented as
x_{k}, where the value x is a quantity such as voltage. The
subscript k represents the sequence number. Very often in digital signal
processing, x_{k}
represents a sampled waveform or signal where the subscript specifies the point
in time at which the sample was taken. However, the subscript can represent an alternative
meaning such as distance in a spatially sampled application. For a system to be
physically realizable, the output must depend only on the present and past history
of the input. No real system can have an output that depends on the future of the
input. The dependence of the output of any physically realizable system on the input
is indicated by
$${y}_{k}=f\left({x}_{k},,,{x}_{k1},,,{x}_{k2},,,\dots ,,,{x}_{kn}\right),$$
where the input variables are x_{k}, the output variable is
y_{k}, and f(*) is any arbitrary function of n+1 variables.
Although this function is too broadly defined to be analyzed in general, the subset
of linear operations becomes very useful for a plurality of signal processing applications.
These functions also prove to be much more tractable in analysis.
If the output depends on the previous n samples of the
input (a system having a finite memory) in a linear fashion, Equation (1) can be
written as
$${y}_{k}={\displaystyle \sum _{j=0}^{N}{a}_{j}{x}_{kj}}+b.$$
Such a linear system is characterized by the
N+1 weighting variables a_{j}, and by the bias b. An unbiased,
discrete linear system is characterized by the weighting variables (a_{0},
a_{1}, ..., a_{n}
). If the input x_{k}
is a delta function (unity for one sample and zero for all others), it can
be seen that the output of Equation (2) is the sequence of weighting variables
a_{0}, a_{1}, ..., a_{n}. Therefore, the response
to the input completely characterizes an unbiased, linear system.
There are certain types of linear systems with memory that
can be analyzed using linear techniques. Even though digital signal processing is
discrete by nature, if the input is samples of a continuous input and is sampled
sufficiently fast, it is possible to simulate a continuous system using the samples
as the input variables. The output then appears as a linear system with a long memory.
One such system is a FIR filter 20. A fixed coefficient FIR filter is characterized
by the input/output equation
$${y}_{k}={\displaystyle \sum _{j=0}^{N1}{c}_{j}{x}_{kj}},$$
as shown in Figure 1, or expanded as
$${y}_{k}={c}_{0}{x}_{k}+{c}_{1}{x}_{k1}+\dots +{c}_{k1}{x}_{k\left(N,,1\right)},$$
where the FIR filter has an impulse response c_{0}, c_{1},
..., x_{k}
represents the discrete input signal samples at time k, c_{i}
are the filter coefficient weights, N are the number of taps, and
y_{k}
represents the output at time k. As shown in Figure 1, the block
diagram forms a tapped delay line with the coefficients being known as tap weights.
Digital filters are presently a common requirement for
digital signal processing systems. In the field of discrete systems, the most popular
type of digital filter using convolution is the FIR. FIR filters have two advantages.
The first is that FIR filters are inherently stable. The finite length of the impulse
response guarantees that the output will go to zero within N samples. The second
advantage is that FIR filters can be designed and implemented. The FIR filter
20 can be physically realized by using digital shift registers
22, multipliers 24 and summers 26 as shown in Figure 2.
The discrete signals 28 are shifted into registers 22 by a sampling
clock pulse 30. The registers 22 hold past values 32 of the sampled
signal 28 as well as present values 34 required for mathematical convolution.
The past 32 and present 34 values are multiplied 24 by filter
weighting coefficients 36, summed 26 and then output 38.
Another way of representing a FIR filter structure 20 is
shown in Figure 3. The operation described can be shown to be the equivalent
of Figure 2 since
$$A={c}_{3}{x}_{k1},$$
$$B={c}_{3}{x}_{k1}+{c}_{2}{x}_{k},$$
$$C={c}_{3}{x}_{k2}+{c}_{2}{x}_{k1},$$
resulting in
$$D={y}_{k}={c}_{3}{x}_{k3}+{c}_{2}{x}_{k2}+{c}_{1}{x}_{k1}+{c}_{0}{x}_{k}={\displaystyle \sum _{j=0}^{3}{c}_{j}{x}_{kj}}={c}_{k}\ast {x}_{k}.$$
As can be seen in Figures 2 and 3 the weighting
36 of the discrete input samples 28 relies upon many multipliers
24.
A single channel of a multichannel FIR filter
40 for CDMA modems is shown in simplified form in Figure 4A. The multichannel
FIR filter 40 is shown as a single element with a multichannel input sequence
x_{(i)k}
entering the filter 40 and the filtered result y_{(i)k}
exiting. The subscript "i" identifies which channel from a plurality
channels is being filtered.
The multiple single bit data/signal streams represent serial
data streams that have been modulated with a pseudo noise (PN) code sequence. Each
channel could represent user traffic channels at various data rates. Various types
of signaling data might comprise other channels.
A typical example of an ISDN (integrated service digital
network) CDMA modem would require five channels. Two channels would be 64 Kbps traffic
channels (B1 and B2), a 16 Kbps auxiliary signaling and packet channel (D), an order
wire channel (OW), and a reverse automatic power control channel (APC).
For maximum user capacity in a CDMA system it is necessary
to use the minimum amount of power to achieve the required BER. Each channel must
have the appropriate individual weight applied so that the correct relative amplitudes
are transmitted. After the weighting operation the individual data streams become
multibit values. The data streams are summed together in a large digital summing
circuit that consists of a tree of numerous two input adders.
The weighted and summed digital values are then filtered
in a conventional FIR filter. The FIR filter is required to pulse shape the input
waveforms while suppressing outofband emissions. The multipliers in the FIR must
handle the multibit data and coefficients to the desired precision.
In Figure 4B, four signal channels are input individually
into separate FIR filters 20 (the clock signal has been omitted for clarity).
The individually filtered signals are then weighted using multipliers
24 with a channel specific weighting coefficient 37 w_{(i)}
for power control (equalizing the power or gain between individual channels)
before being input to a multichannel summer 46. Since all users occupy the
same frequency spectrum and time allocation in spread spectrum communication systems,
it is desired that each user is received with the same power level. The result,
y_{(i)k}
44, is a weighted sum of the individually FIR filtered multiple signal
channels.
A CDMA transmitter combines many channels of varying types
of digital signals (serial digital voice, power control, ISDN data). Typically,
each channel is modulated with a different spreading code. The spreading code allows
a CDMA receiver to recover the combined signals by use of the proper code during
demodulation. Alternatively, any set of orthogonal functions could be combined with
the preferred embodiment and later separated by correlation. The output
44 of the multichannel FIR filter 40 is a weighted and filtered average.
Although each channel has been described as a single bit valued serial data stream,
multibit values or levels may be processed with the identical multichannel filter
structure.
Referencing Figure 5, the multichannel FIR filter
40 is shown using four tap FIR filters 48. The weighting of the discrete
samples is performed by conventional multipliers 24. Each FIR structure is
comprised of shift registers 22 and summers 26 for past
32 and present 34 sampled signals. Each tap weight coefficient
36 is multiplied by the respective channel power control weighting factor
37. The result is the same as shown in Figure 4B, but with the external
multipliers inside the FIR 48 structures.
Hardware reduction is accomplished by sharing FIR registers
and adders as shown in Figure 6. Each multichannel processing element
52 performs part of the channel weighting 37, the FIR tap coefficient
36 multiply 24, and the summing 26 of the multiple channels
for that tap. The partitioning of the discrete functions reveals the preferred embodiment.
Figure 7 shows the multichannel processing element 52 as a processing block
with "N" single bit input signals X_{(o)k}, X_{(1)k},
..., X_{(N)k}. The computed output z_{k}
54 contains "W" bits of resolution. The discrete input signals
28 form a vector. This vector can be assigned an overall value by weighting each
bit with an increasing power of two. In the alternative, the multichannel signal
bits are treated as a binary valued word. The output of the processing block is
a "W" bit wide function of the N bit binary input argument. The block performs
the equivalent logical function of a memory device where the input signal bits form
an address and the computed values are contents of the selected memory word. A memory
based LookUpTable (LUT) 56 can perform an arbitrary function quickly and
efficiently as shown in Figure 8A.
A mathematical function f of an argument
x with a result of y is expressed as y=f(x). The function performs
a mapping of all values of x into another space of y values. A LUT
performs this mapping for the values of interest in the preferred embodiment. The
LUT memory device is presented with an address of a location within the memory circuit.
The value previously stored at that location is delivered to the memory output data
bus. The values of interest of x, which are discrete, are mapped into a binary
number. Since the multichannel signals are represented by zero or one logic levels,
they are used as bits to form a binary number. Every possible combination of channel
values is therefore assigned a state number. This operation is represented as
$$A={\displaystyle \sum _{j=0}^{M1}{x}_{j}{2}^{j}}={x}_{M1}{2}^{M1}+\dots {x}_{3}{2}^{3}+{x}_{2}{2}^{2}+{x}_{1}{2}^{1}+{x}_{0}{2}^{0}={x}_{M1}{2}^{M1}+\dots {x}_{3}8+{x}_{2}4+{x}_{1}2+{x}_{0}.$$
Each state is a binary number that references an address
in the LUT. The output value from the LUT is the precomputed value of the function
resultant that would occur given the argument corresponding to that address. This
is illustrated as a tabular representation of the LUT contents. The function to
be performed is the weighted sum of the multiple channels for a given single tap
of the FIR structure.
For example, in an application using 4 channels (M=4),
the LUT contents located at the 2nd tap of the multichannel FIR (j=2) would
be as shown in Table 1.
Table 1
Values of x x_{3}, x_{2}, x_{1}, x_{0}
Address Computation of A
LUT Value Stored At Location A
0 0 0 0
0
0
0 0 0 1
1=1
W_{0}C_{2}
0 0 1 0
2=2
W_{1}C_{2}
0 0 1 1
2+1=3
W_{1}C_{2}
+ W_{0}C_{2}
0 1 0 0
4=4
W_{2}C_{2}
0 1 0 1
4+1=5
W_{2}C_{2}
+ W_{0}C_{2}
···
···
···
···
···
···
···
···
···
···
···
···
···
···
···
1 1 0 1
8+4+1=13
W_{3}C_{2} + W_{2}C_{2} + W_{0}C_{2}
1 1 1 0
8+4+2=14
W_{3}C_{2} +W_{2}C_{2} + W_{1}C_{2}
1 1 1 1
8+4+2+1=15
W_{3}C_{2} + W_{2}C_{2} + W_{1}C_{2}
+ W_{0}C_{2}
The LUT 56 memory words contain precomputed values corresponding
to the current input address value as shown in Figure 8B. The memory can
be implemented in either ROM or RAM, depending upon the application.
In the preferred embodiment, ROM (read only memory) is
used to store permanent LUT values. This is implemented efficiently as an integrated
circuit. ROM is appropriate for time invariantsystems where the required channel
weights and filter coefficients are known a priori. RAM (random access memory)
allows new values to be written over old. LUT values can be computed and loaded
to achieve adaptivity. RAM is not as space efficient as ROM but is still efficient
considering the increased flexibility.
The preferred embodiment of the multichannel FIR filter
40 for CDMA modems according to the present invention is shown in
Figure 9. The filter structure uses LUTs 56 rather than the inefficient
multichannel processing elements 52 which require a plurality of multipliers
24 and summers 26.
The signal bits form the address word which is applied
to the LUT 56. There is a LUT 56 for each filter tap required. The contents
of each LUT 56 is computed
$${L}_{j}\left({D}_{N},,,{D}_{N1},\dots ,,,{D}_{2},,,{D}_{1}\right)={C}_{j}{\displaystyle \sum _{i=1}^{N}{D}_{i}{W}_{i}}.$$
As shown, any combination of signal values has its weighted
sum precomputed. The multiplication of each tap coefficient of the FIR function
is included in the precomputed table.
The weighted and filtered single channel operation of
Figure 4A with and N tap FIR can be expressed as
$${y}_{\left(i\right)k}={w}_{i}{\displaystyle \sum _{j=0}^{N1}{c}_{\left(i\right)j}{x}_{\left(i\right)kj}}={w}_{i}\left[{c}_{\left(i\right)j},\ast ,{x}_{\left(i\right)j}\right].$$
An M channel multichannel version of this is shown in Figure 4B and can
be expressed as
$${y}_{\left(i\right)k}={\displaystyle \sum _{j=0}^{M1}{y}_{\left(i\right)k}}={\displaystyle \sum _{i=0}^{M1}\left({w}_{i},{\displaystyle \sum _{i=0}^{M1}{c}_{\left(i\right)j}{x}_{\left(i\right)kj}}\right)},$$
$${y}_{\left(i\right)k}={\displaystyle \sum _{i=0}^{M1}{w}_{i}\left[{c}_{\left(i\right)j},\ast ,{x}_{\left(i\right)j}\right]}.$$
This is the desired weighted sum of convolutions or FIR
filtering operations.' The convolution is performed in FIR filters 20, the
weighting in multipliers 24 and the summation in adders 46. The convolution
achieved is identical to that originally presented in Equation 3. The summation
and weights are a result of the extension to a multichannel process.
The preferred embodiment shows an improved filter for multichannel
CDMA FIR filtering modem applications. It has been shown that the signal processing
operation over multiple channels, as shown in Figure 4, can be implemented
using no multipliers and a reduced number of adders.
While specific embodiments of the present invention have
been shown and described, many modifications and variations could be made by one
skilled in the art without departing from the spirit and scope of the invention.
The above description serves to illustrate and not limit the particular form in
any way.