Title of Invention	DIGITAL FILTER WITH STATE STORAGE
Abstract	The present invention relates to a system for digital filtering comprising a set of logic gates, a state storage, and a multiplexer. The state storage has two or more storage banks and may also include combinatorial logic and/or at least one lookup table. In one application, a filtering operation according to a finite-impulse-response filter coefficient vector is performed without runtime multiplications. Applications to symmetric and antisymmetric filter coefficient vectors are described, as well as applications to filter coefficient vectors of arbitrary odd or even length.

Title of Invention

DIGITAL FILTER WITH STATE STORAGE

Abstract

The present invention relates to a system for digital filtering comprising a set of logic gates, a state storage, and a multiplexer. The state storage has two or more storage banks and may also include combinatorial logic and/or at least one lookup table. In one application, a filtering operation according to a finite-impulse-response filter coefficient vector is performed without runtime multiplications. Applications to symmetric and antisymmetric filter coefficient vectors are described, as well as applications to filter coefficient vectors of arbitrary odd or even length.

Full Text	r This invention relates to digital signal processing. Digital signal processing techniques may be used to process signals at baseband, intermediate, and radio frequencies. In addition to their use in new applications, such techniques are also replacing analog processing techniques in existing applications such as signal filtering. The numerous advantages that a digital filter may possess over an analog counterpart include a lack of impedance matching problems, guaranteed stability and/or phase linearity, freedom from a change in response due to aging, and programmability and ease of alteration. [0003] Digital filters are implemented primarly as linear constant coefficient filters. Such filters may be broadly divided into two classes: infinite-impulse-response (IIR) filters and finite-impulse-response (FIR) filters. By incorporating feedback, IIR filters require fewer taps to achieve the same performance. Such filters cause less delay and can be implemented with less hardware than FIR filters with similar characteristics. However, IIR filters are harder to design than FER filters, generally have nonlinear phase characteristics, and may have stability problems as well. In contrast to IIR filters, FIR filters are guaranteed to produce a bounded output in response to a bounded input Moreover, if the coefficients of a FIR filter are symmetric (or antisymmetric), then the filter will have a linear phase response. One basic FIR filter system is illustrated in FIGURE 1. Shift register 20 receives an input signal (e.g. a series of digital values) and outputs an N-element input vector SIC to filter 40. In this example, a new input value is shifted into register 20 upon a predetermined transition of a clock signal from clock 30. Filter 40 contains a filter coefficient vector of length N, N multipliers, and an N-input adder. For each instance of input vector S10 (expressed as a series of values x0, X1, X2,..., XN), filter 40 outputs a value y according to the expression Further information on the theory and design of digital filters may be found in such documents as Electronic Filter Design Handbook 2" ed., by A. B, Williams and F. J. Taylor, McGraw-Hill, New York, 1988; Digital Filtering: an introduction, E. P. Cunningham, Houghton Mifflin, Boston, 1992; and section XVI of The Circuits and Filters Handbook ed. by W.-K. Chen, CRC Press, Boca Raton, FL, 1995. Lookup tables (LUTs) are used in various computing contexts to hold decision information that cannot easily be expressed mathematically. Two examples of information that may be stored in a LUT are (1) the mapping of IP addresses to aliases or to physical network locations, and (2) colormaps. Lookup tables have also been used in waveform generation applications to hold values that are frequently used but may be cumbersome to calculate, such as a mapping from a time index (x) into a trigonometric value (such as sin x or cos x). A digital filter as shown in FIGURE I is a calculation-intensive circuit. Because the set of possible input values to a digital filter is finite, the response of such a filter is completely deterministic and may be specified before runtime. However, it has not generally been feasible to use LUTs in digital filtering applications. In order to directly represent every possible output of an N-tap FIR filter which receives an input data stream M bits wide, a lookup table of size 2MxN would be required. For an 8-bit-wide input and a relatively short 16-tap filter, such a table would have to contam 2123 (or on the order of 1038) symbol storage spaces. If the input data stream for the filter is only I bit wide (i.e. binary-valued), then the size of the lookup table reduces to 2N symbol storage spaces. Even m this case, however, the size of the filter is severely limited by the resulting storage requirements: for example, a 16-tap filter would require 216 symbol storage spaces (i.e. one megabit of storage area for every bit of the width of the output symbols). Where the performance of a longer filter is required or the application imposes severe circuit area and/or power constraints (e.g. as in a portable device for wireless communications), FIR implementation using lookup tables may not be feasible. SUMMARY A system for digital filtering according to one embodiment of the invention includes a digital filter that has a set of logic gates, a state storage, and a multiplexer. The set of logic gates is configured and arranged to receive an input vector and a phase count signal The phase count signal may count at a rate that is a multiple of the rate of a clock associated with the input vector. The set of logic gates is configured and arranged to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector. For example, the set of logic gates may map the input vector to the state select vector according to a sequence select signal based on at least a portion of the phase count signal. The state storage has two or more storage banks, each configured and arranged to receive the state select vector and to produce a state signal indicated by that vector. For example, the state storage (or each of the storage banks) may include one or more lookup tables having values based on components of a finite-impulse-response filter coefficient vector (such as a symmetric or antisymmetric filter coefficient vector). The state storage may also include combinatorial logic configured and arranged to produce a signal (such as a zero select signal) based on at least part of the state select vector. The multiplexer is configured and arranged to receive the two or more state signals and to pass a selected state signal corresponding to a bank select signal. The bank select signal is based on the phase count signal and may also be based on at least a part of the input vector. The digital filter may also include an inverter configured and arranged to produce an output signal based on the selected state signal and an invert signal. The invert signal is based on at least part of the input vector and may also be based on the phase count signal. Additionally, components of at least a portion of the state select vector may be based on the invert signal Such a system may include a shift register configured and arranged to produce the input vector and a phase counter configured and arranged to produce the phase count signal. The system may also include additional digital filters, with one or more adders configured and arranged to produce a sum based on the selected state signals. A method of digital filtering according to an embodiment of the invention includes receiving an input vector and a phase count signal and mapping the input vector to a state select vector according to the phase count signal. The method also includes inputting the state select vector to a state storage that includes two or more storage banks. From each of the storage banks, a state signal corresponding to the state select vector is received, and one from among the state signals is selected according to a bank select signal. As noted above, the bank select signal is based on the phase count signal and may also be based on at least a part of the input vector. Additional embodiments of the invention and applications thereof are described and/or illustrated herein. For example, a system or method according to an embodiment of the invention may be applied to filter a binary data stream according to the 48-tap FIR filter shown in TABLE 1. BRIEF DESCRIPTION OF THE DRAWINGS FIGURE 1 is a block diagram of a basic FIR filter system, FIGURE 2 shows an example of a data path for a pulse-shaping filter system. FIGURES 3A, 3B, and 3C illustrate signals a,x,y of FIGURE 2, respectively. FIGURE 4 shows a phase decomposition of a FIR filter. FIGURE 4A shows a phase decomposition of a FIR filter. FIGURES 5A, 5B, and 5C illustrate an approach to reducing storage according to an embodiment of the invention. FIGURES 6A shows a block diagram of a digital filter 100 according to an embodiment of the invention. FIGURE 6B shows a block diagram of a system for digital filtering according to an embodiment of the invention. FIGURE 7 shows a block diagram of an exemplary implementation of set of logic gates 110. FIGURE 8 shows a block diagram of an exemplary implementation 112 of set of logic gates 110. FIGURE 9A shows a phase decomposition of a type 2 FIR filter. FIGURE 9B illustrates a reduction of the decomposition of FIGURE 9A. FIGURE 10 shows a block diagram of an implementation 104 of a filter 100 according to an embodiment of the invention. FIGURE llA shows a block diagram of an implementation 114-1 of set of logic gates 110. FIGURE IIB shows a block diagram of an implementation 124cl of storage bank 124c. FIGURE 12 shows a block diagram of multiplexer 134. FIGURE 13A shows a phase decomposition of a type 2 FIR filter. FIGURE 13B illustrates a reduction of the decomposition of FIGURE 13A. FIGURE 14 shows a block diagram of an implementation 114-2 of set of logic gates 110. FIGURE 15 shows a block diagram of an implementation 124c2 of storage bank 124c. FIGURE 16A shows a phase decomposition of a type 2 FIR filter. FIGURE 16B illustrates a reduction of the decomposition of FIGURE 16A. FIGURE 17 shows a block diagram of an implementation 116-1 of set of logic gates 110. FIGURE 18 shows a block diagram of an implementation 116-2 of set of logic gates 110. FIGURE i9A shows a phase decomposition of a type 1 FIR filter. FIGURE 19B illustrates a reduction of the decomposition of FIGURE 19A FIGURE 20 shows a block diagram of an implementation 118 of set of logic gates 110. FIGURE 21 shows a block diagram of an implementation 200 of a digital filter according to another embodiment of the invention. FIGURE 22 shows a block diagram of an exemplary implementation of set oflogic gates 210. FIGURE 23 shows a block diagram of an exemplary implementation 212 of set of logic gates 210. FIGURE 24 shows a block diagram of one binary-input implemeatation 202 ofa filter 200. FIGURE 25 shows a block diagram of one implementation 204 of a filter 200. FIGURE 26 shows a block diagram of a set of logic gates 214. FIGURE 27 shows an exemplary implementation of multiplexer 234. FIGURE 28 shows a block diagram of a filter 250 according to an embodiment of the invention. FIGURE 29A shows a phase decomposition of a 24-tap FIR filter. FIGURE 29B shows a reduction of the decomposition of FIGURE 29A. FIGURE 30A shows a division of the reduction of FIGURE 29B. FIGURE 30A shows another division of the reduction of FIGURE 29B. FIGURE 30B shows another division of the reduction of FIGURE 29B. FIGURE 3 IB shows a division of the decomposition of FIGURE 29A. FIGURE 32 shows a block diagram of an implementation 260 of filter 250. FIGURE 31C shows another division of the decomposition of FIGURE 29A. DETAILED DESCRIPTION Digital filters are frequently used to modify the frequency characteristics of an input signal. One such application is to control the bandwidth of a baseband signal before transmission (e.g. over a radio frequency (RF) channel). FIGURE 2 shows one example of a data path for a pulse-shaping filter system that includes a zero-padding operation 10 and a FIR filter 45. FIGURES 3A, B, and C provide illustrations of signals -a = [K, a0, a1, a2, as, K],-x, and-y, respectively. In this non-limiting example, input signal is binary-valued (±1), while output signal-y is more than one bit wide. Zero-padding operation 10 produces upsampled signal x = K ,a,0,9,a,a1,0,0,a2,0,0a,0,0,K] by inserting (L -1) zero samples for each sample of signal a (in this example, upsampling factor L = 3, and the zero samples are inserted after each data value). Filter 45 filters signal K to produce pulse-shaped signal y. Coefficients for one particular example of a pulse-shaping filter are shown in TABLE 1 below; this 48-tap symmetric filter is specified in Table 6.1.3.LlO-1 of TIA/EIA Interim Standard IS-95-A (May 1995, Telecommunications Industry Association, Arlington, VA) for a binary data stream upsampled by L = 4. In an application where the N-element filter coefficient vector is specified for a zero-padded input stream, the number of nonzero terms that contribute to each output value is limited by N/L rather than N (where L is the upsampling factor and N is the length of the filter coefficient vector). Expressions for each of the L output values Y1 that are produced for one instance of input vector [ao, a1, 0.2, a3] follow, each expression including N/L possibly nonzero terms (in this non-limiting example, L = 4 andN = 16): These expressions are illustrated in FIGURE 4A, which demonstrates that the operations of such a filter may be modeled as separate applications of the input vector to L nonoverlapping cosets (or phases) of the filter coefficients. The zero-padding and filtering operations shown in FIGURE 2 may also be combined into a single filtering operation. In one possible implementation of these prmciples, the values of the N terms of expressions (I)-(4) sre precalculated and stored for each possible input vector. These values are then retrieved at runtime (according to the phase number and the particular instance of the input vector) as output values of the filter. In such case, the total number of states to be stored may be reduced fiom PN (2N for binary input) to L _ P"^ (L _ 2N/L for binary input), where P is the number of possible states for each component of the input vector, and the filter is clocked at a rate at least L times greater than the clock associated with the input vector (e.g. clock 30 in FIGURE 1). In the example of FIGURE 4A, the total number of states to be stored may be reduced firom 216 to 26 for binary input (with the filter output values being arbitrarily wide). In a case where the filter coefficient vector is symmetric (hi == h(N+1)), the maximum required storage capacity may be reduced further (i.e. by a factor of 2). FIGURE 4B illustrates how two values may be retrieved from the reduced storage at runtime (e.g. in successive filter clock periods), each according to the phase number and a respective half of the input vector. These two values are then added together to produce a filter output value. In this case, the filter is clocked at a rate at least 2L times greater than the clock associated with the input vector. Additionally, the two retrieved values to be added may be many bits wide, and an adder having considerable complexity (and possibly a considerable delay) may be required to perform the summing operation. FIGURES 5A, 5B, and 5C illustrate an alternative approach to reducing the required storage capacity in a case where the filter coefficient vector is symmetric. FIGURE 5A shows how the symmetry of the coefficients can be exploited to allow the entire input vector to be applied as an index to the reduced storage for each phase. In FIGURE 5B, the L phases axe reduced to L/2 banks indexed by a sequence vector having two states. In the first state, the input vector is mapped to the sequence {a0, as, a1, aa}. In the second state, the input vector is mapped to the sequence {as, a0, a2, ai}. FIGURE 5C demonstrates how each desired filter output may be retrieved m a single indexing operation according to a bank select signal and a mapping of the input vector to a selected sequence. FIGURE 6A shows a block diagram of a digital filter 100 according to an embodiment of the invention. A set of logic gates 110 receives the input vector S10 and a phase count signal S20. In an exemplary implementation, phase count signal S20 is clocked at a rate L times that of the clock associated with input vector S10, such that phase count signal S20 counts from 0 to (L -1) for each instance of the input vector. Based on at least a portion of phase count signal S20, set 110 selects a sequence and maps the input vector to a state select vector S30 according to die selected sequence. Set 110 also produces a bank select signal S40 based on phase count signal S20 (or a portion thereof). State storage 120 includes two or more storage banks 1201, each receiving state select vector S30. Each storage bank 120i may include combinatorial logic and/or a lookup table having stored values. In some implementations, two or more of storage banks 120i may mclude different portions of a single lookup table. Each storage bank 120i outputs a state signal S60i. Multiplexer 130 receives the state signals S60i and passes one among them as selected state signal 350 according to bank select signal 840. In one binary-input implementation of the example illustrated in FIGURE 5C, state storage 120 has two storage banks 120a (bank 0) and 120b (bank I). In this implementation, bank 0 stores the sixteen values represented by the expresS10n (± ho ± h3 ± h4 ± h2), while bank 1 stores the sixteen values represented by the expresS10n (± h1±h2±h5±h6). FIGURE 6B shows a block diagram of a system for digital filtering according to an embodiment of the invention. Shift register 20 receives an input signal S5 and a clock signal from clock 30 and produces an N/L-component input vector S10. Filter 100 receives input vector S10 and phase select signal S20 (from phase counter 300) and produces selected state signal S50. As noted above, filter 100 produces L output values for each instance of input vector S10. [00070] FIGURE 7 shows a block diagram of an exemplary implementation of set of logic gates 110 for a type 2 FIR filter (i.e. having a symmetric filter coefficient vector of even length). In this implementation, multiplexer pairs M10 and M20 map input vector S10 to state select signal S30, switching between the two sequences according to sequence select signal S50 (here, the high bit of phase count signal S20) and inverter 110. XOR gate X40 receives phase count signal S20 and produces bank select signal S40, which controls multiplexer 130 to select between the state signals S60 produced by storage banks 120a, 120b (banks 0,1) of state storage 120 as discussed above. FIGURE 8 shows a block diagram of an exemplary implementation 112 of set of logic gates 110 for a type 4 FIR filter (i.e. having an antisymmetric filter coefficient vector of even length). In this implementation, inverters 120 and 130 invert the components in the latter half of input vector S10 (here, aa and aa). A filter according to an embodiment of the invention as shown in FIGURE 6 is not limited to implementations in which input vector S10 has binary-valued components. For example, implementations of sets of logic gates 110 and 112 as shown in FIGURES 7 and 8 may also be used in applications where components of input vector S10 have more than one bit In such cases, multiplexer pairs MIO, M20 may be configured to select between multi-bit input values (in response to a binary control signal), and inverters 120,130 may be configured to invert mnlti-bit data values. SetvS 110 (and } 12) as shown in FIGURES 7 and 8 may be used in implementing filter coefficient vectors of arbitrary even length N by adding additional multiplexer pairs (and one or more corresponding inverters) as appropriate. As noted above, such filters may be decomposed into (and state storage 120 may be implemented to include) L/2 banks. FIGURE 9 A illustrates an example of a phase decomposition of a Type 2 FIR filter in which L is odd and N/L is even (here, L == 5, N = 10, and N/L = 2). As shown in FIGUKE 98, such a case (having L phases) may be condensed to ceil(L/2) banks (ceil(x) denoting the smallest integer not less than x), where the highest numbered bank has only one sequence (sequence number X indicating 'don't care*). FIGURE 10 shows a block diagram of an implementation 104 of a filter 100 according to an embodiment of the invention for a case where L is odd and N/L is even (e.g. as shown in FIGURE 9B). In this implementation, state storage 120 include ceil(L/2) banks, each receiving state select vector S34, and multiplexer 134 selects from among the ceil(L/2) state signals S60i according to bank select signal S44. FIGURE llA shows a block diagram of an implementation 114-1 of set of logic gates 110 suitable for the particular case illustrated in FIGURE 9B. In this implementation, XOR gate X60 receives the two high bits of phase count signal S24 (which counts from 0 to (L-1) - 4) and produces sequence select signal S54, and the two low bits of phase count signal S24 serve as bank select signal S44. As noted in FIGURE 9B, the sequence in which a0 and ai are mapped to state select signal S34 is irrelevant to bank 2, as both input values correspond to the same filter coefficient value. Another consequence of this correspondence is that if the value of ao is the inverse of the value of ai, the filter output is zero. In fact, by including logic to produce zero and inverted values at runtime, bank 2 may be implemented in tiiis case with only one stored value. FIGURE 1 IB shows a block diagram of an implementation 124cl of storage bank 124c for the binary input case. XOR gate X70 receives state select vector S34. Via zero select signal S70-1, XOR gate S70 causes multiplexer M40 to output a zero value if the two components of state select vector differ. Value storage 4 210-1 stores only one value, which is received by XOR gate X80. If invert signal S80-1 (either component of state select vector S34) is high, the stored value is inverted. XOR gate X80 may be implemented to receive one multi-bit value (the stored value) and one binary value (invert signal S80-1). Depending upon the mapping between input and output values in the particular implementation, invert signal S80-1 may be inverted before being inputted to XOR gate X80. FIGURE 12 shows a block diagram of multiplexer 134 suitable for use in the implementation 104 of filter 100 shown in FIGURE 10. Multiplexer i34a selects between the state signals S64 of bank 0 and bank 2 according to the high bit of bank select signal S44, and multiplexer 134b selects between the state signal S64 of bank 1 and the output of multiplexer 134a according to the low bit of bank select signal S44. FIGURE 13A illustrates another example of a phase decomposition of a Type 2 FIR filter in which L is odd and N/L is even (here, L = 5, N = 20, and N/L = 4). FIGURE 13B shows how the L phases may be condensed to ceil(L/2) banks. FIGURE 14 shows a block diagram of an implementation 114-2 of set of logic gates 110 suitable for the case illustrated in FIGURE 13B. Multiplexer pairs M10 and M20 map input vector S14 to state select vector S34 according to sequence select signal S54 and its inverse. Set 114-2 may be used in implementing filter coefficient vectors of arbitrary even length N by adding additional multiplexer pairs (and one or more corresponding inverters) as appropriate. FIGURE 15 shows a block diagram of an implementation I24c2 of storage bank 124c suitable for the case illustrated in FIGURE 13B. In this case, value storage 210-2 stores only four values. Via a collection of logic gates (XOR gates XI10, X120. X130; AND gates A10, A20, A30; 0R gate 010; and inverter 140) and multiplexer M50, state select vector S34 is processed to select the appropriate value from value storage 210-2 and to produce zero select signal S70-2 and invert signal S80-2. Other collections of logic gates may be used, and Boolean expresS10n minimization techniques (such as Karnaugh maps) may be used to produce such other collections and/or to extend implementatioii 124c2 to state select vectors having more components while minimizing the size of value storage 210. As with XOR gate X80 described above, XOR gate X90 may be implemented to receive one multi-bit value (the selected stored value) and one binary value (invert signal S80-2). As discussed with reference to FIGURE 8, sets of logic gates 114-1 and 114-2 may be extended to apply to the antisymmetric case by inverting fte components in the latter half of input vector S10. FIGURE 16A illustrates an example of a phase decomposition of a type 2 FIR filter in which L is even and N/L is odd (here, L = 4, N = 20, and N/L - 5). FIGURE 16B shows how the L phases may be condensed to L/2 banks. FIGURE 17 shows a block diagram of an implementation 116-1 of set of logic gates 110 suitable for the case illustrated in FIGURE 16B. As the middle component of input vector S16 (here, aa) shares filter coefficients with no other component, this value may pass through to the same component of state select vector S36 for all sequences. . FIGURE 18 shows a block diagram of an implementation 116-2 of set of logic gates 110 suitable for a case as illustrated in FIGURE 16B in which the filter coefficient is antisymmetric. Multiplexer M70 selects between the middle component of input vector SI 6 and its inverse (as produced by inverter 150) according to sequence select signal S50. In applications where components of input vector S16 have more than one bit, multiplexer M70 may be configured to select between multi-bit input values (in response to a binary control signal), and inverter 150 may be configured to invert a multi-bit data value. Sets of logic gates 116-1 and 116-2 may be used in implementing filter coefficient vectors of arbitrary even length N by adding additional multiplexer pairs (and one or more corresponding inverters) as appropriate. As noted above, such filters may be decomposed into (and state storage may be implemented to include) ceil(L/2) banks. FIGURE 19A illustrates an example of a phase decomposition of a type 1 FIR filter (i.e. having a symmetric filter coefficient of odd length). In such case, both L and N/L are odd (here, L - 5, N = 15, and N/L - 3). FIGURE 19B shows how the L phases may be condensed to ceil(L/2) banks. FIGURE 20 shows a block diagram of an implementation 118 of set of logic gates 110 suitable for a case as illustrated in FIGURE 19B. Implementation 118 may be applied to cases of an antisymmetric filter coefficient vector (type 3) and/or components of input vector S18 having more than one bit by extenS10n as described herein. Additionally, set of logic gates 118 may be used in implementing filter coefficient vectors of arbitrary odd length N by adding additional multiplexer pairs (and one or more corresponding inverters) as appropriate. FIGURES I IB and 15 above demonstrate how the number of stored values in a storage bank may be reduced by applying an invert signal decoded from the input vector. This principle of exploiting symmetry among the set of output states may also applied more generally to reduce the size of the state storage by a factor of 2. FIGURE 21 shows a block diagram of an implementation 200 of a digital filter according to another embodiment of the invention. In this implementation, set of logic gates 210 produces an invert signal S52, and an inverter (here, XOR gate X50) produces an output signal S70 based on selected state signal S50 (selected firom outputs of state storage 220) and invert signal S52, FIGURE 22 shows a block diagram of an exemplary implementation of set of logic gates 210 to a type 2 FIR filter bank decomposition as shown in FIGURE 5C. In this implementation, the output of a multiplexer of one of the multiplexer pairs M10, M20 serves as invert signal S50. XOR gates X10, X20, and X30 receive invert signal S50 and the signals from the other multiplexers and produce the components of state select vector S230, As state storage 220 is only half as large as state storage 120, state select vector S230 is one bit narrower than state select vector S30 as shown in FIGURE 7. in a case where components of input vector S10 have more than one bit, one bit of the output of a multiplexer of one of the multiplexer pairs M10, M20 serves as invert signal S50. In such case, the other bits of the output of that multiplexer are inputted to an XOR gate that receives invert signal S50. Like XOR gates X10, X20, and X30 described above, this XOR gate also produces components of state select vector S230. FIGURE 23 shows a block diagram of an exemplary implementation 212 of set of logic gates 210 for a type 4 FIR filter. In this implementation, XOR gate X50 receives sequence select signal S50 and one bit of the output of a multiplexer of one of the multiplexer pairs M10, M20 and produces invert signal S52. Implementations of filter 200 and set of logic gates 210 may be extended to cases of filter coefficient vectors of arbitrary length, and/or to various odd/even relationships of L and N/L, as described above with respect to implementations of filter 100 and set of logic gates 110. FIGURE 24 shows a block diagram of one binary-input implementation 202 of a filter 200 that is suitable for application to the example illustrated in FIGURE 5C, In this implementation, state storage 222 has two storage banks 222a {bank 0) and 222b (bank 1), with bank 0 storing the eight values represented by the expresS10n (ho ± ha ± ha+hr) and bank 1 storing the eight values represented by the expresS10n (h1+ h2+ hs ± he). In some applications, it may be desirable to divide one or more of the storage banks into subbanks. For example, it may be desired to modify a state storage 222 as described above by dividing each bank into two subbanks, each subbank receiving the state select vector and producing a state signal. FIGURE 25 shows a block diagram of one such implementation 204 in which subbanks 224a0 and 224al each store the four values represented by the expresS10n (so + Si ± S2 ± S3) [(ho + hs ± h4 ± by) and (hi + ha ± hs ± hg), respectively], while subbanks 224b0 and 224b 1 each store the four values represented by the expresS10n (so - s1 ± sa ± S3) [(ho - ha =fc h4 ± h7) and (h1 - hz ± hs ± he), respectively]. FIGURE 26 shows a block diagram of a set of logic gates 214 suitable for use in filter 204. Although the total number of stored states in state storage 224 is the same as the total number of stored states in state storage 222, the number of banks receiving the state select vector and producing a state signal is greater in filter 204 (here, by a factor of two). Consequently, multiplexer 134 selects from among a greater number of inputs. At the same time, the number of states stored in each bank 224 is less (here, also by a factor of two) such that state select vector S234 may be more narrow than state select vector S230. In this particular example, set 214 is derived from set 210 by moving one of the state select vector components (here, the component corresponding to state so in set 210) to bank select signal S44. In other applications, a different number of banks may be implemented, with a corresponding exchange of components between the state select vector and the bank select signal. FIGURE 27 shows a block diagram of an exemplary Implementation of multiplexer 234. FIGURE 28 shows a block diagram of a filter 250 according to an embodiment of the invention. In this embodiment, input vector S10 is split into two separate input vectors S10a and S10b, each being inputted to a filter 100 (constructed e.g, as shown in FIGURE 6A), The output signals S70 produced by filters 100 are added by adder 400 to obtain filter output signal S80. In one implementation, filters 200a,b receive the same phase count signal; in another implementation, filters 200a,b receive the same sequence select and bank select signals (generated e.g. as described herein). FIGURE 29 A shows a phase decomposition of a 24-tap FIR filter (here, L - 4), and FIGURE 29B shows a reduction of this symmetric (or anti-symmetric) filter into ceil(L/2) banks. Assuming a binary input, the total number of stored states in an application of filter 200 to this example may reach (L _ 2(N/L)) or 128. FIGURE 30A shows a diviS10n of the reduction of FIGURE 29B into two sections. In an exemplary application of filter 250 to this filter coefficient vector, input vector S 10a includes the coraponents of the first section (ho-hs) and input vector S10b includes the components of the second section (h4-h11). The total number of stored states in each filter 100i may reach L times 2 to the power (length of input vector S10i minus 1). Assuming a binary input in this example, this limit may be calculated as (4 „ 22-1) or 8 for filter 200a, plus (4 _ 22-1) or 32 for filter 200b, for a total of 40. An even further reduction in the total number of stored states may be achieved by using the three-part diviS10n shown in FIGURE 30B. In this example, filter 250 is implemented with three filters 100, each receiving a four-component input vector S10i, and a three-input adder to receive the three output signal S70 and to produce the filter output signal S80. In this example, the total number of stored states may reach only 24 (or 3 _ 8). In another example, FIGURE 31A shows a phase decomposition of a 48-tap four-times-oversampled symmetric FIR filter as shown in TABLE 1. Each of the four phase expresS10ns may then be divided into three four-term blocks as shown in FIGURE 31B, each block having 16 possible values (for binary input) and serving as an input vector to one of the filters in a three-filter implementation as described above. Note that the particular grouping of input values shown in FIGURE 3 IB is only one of many possible groupings. For example, FIGURE 31C shows another such grouping, which differs from that of FIGURE 3 IB in the placement of coefficients h4-h7 and hg-h1, A particular grouping may also be chosen on the basis of the magnitude of the corresponding filter coefficients, such that blocks having filter coefficients of low magnitude may be formed for processing using a more narrow logical bus width, storage area, etc, than blocks having filter coefficients of higher magnitude. In a further example, the stored state values may be normalized. In one implementation, a normalization of the filter coefficient vector is calculated according to a factor determined by dividing the maximum possible output value of the filter (e.g. as determined by the unnormalized filter coefficient vector) by the maximum value that may be represented in the number of bits provided for the filter output. In an exemplary application, normalization is used to support an integer implementation of a filter coefficient vector having floating-point components. FIGURE 32 shows a block diagram of an implementation 260 of filter 250 asapplied to the48-tapfilter ofTABLEl dividedasshowninFIGURE3lB. Inthis example, output signals S70a, S70b, and S70c are eight, nine, and eleven bits wide, respectively, and the outputs of adders 402a and 402b are nine and eleven bits wide, respectively. Filters 200a and 200b are configured to output signed integer values in offset two's complement representation, while filter 200c and adder 402b are configured to output signed integer values in two's complement representation. This particular configuration eliminates the need for an additional adder to process the carry bits from the three filters. Depending on the numeric representation or representations used in a particular application, it may be desirable to perform additional logic operations when an invert signal is invoked in an implementation as shown, for example, in FIGURE 21. For example, negation of a value encoded in two's complement representation includes both complementation and addition of one. One approach in such case is to include a two-input adder having one input tied to zero, receiving as the other input output signal S70, and having invert signal S50 as the carry-in signal. FIGURE 32 demonstrates how inverS10n may be handled without additional logic. Numbers encoded in offset two's complement representation differ from numbers encoded in two's complement representation by including a bias of 0,5. For example, the numbers 00101 and 11010 in offset two's complement representation signify the decimal values 5.5 and-5.5, respectively. One feature of offset two's complement representation is that complementing such a number is equivalent to negating it. As each of the two values inputted to adder 402a has a bias of 0-5, the carry__in input to this adder is set to one, and the axider outputs a value in two's complement representation. Adder 402b receives two inputs in two's complement representation. As negation of a value encoded in two's complement representation includes both complementation and addition of one, invert signal S50 is inputted to the carry _in input of adder 402b to provide the value of one in case of negation. The foregoing presentation of the described embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments are possible, and the generic principles presented herein may be applied to other embodiments as well For example, the invention may be implemented in part or in whole as a hard-wired circuit, as a circuit configguration fabricated into an application-specific integrated circuit, or as a firmware program loaded into non-volatile storage or a software program loaded from or into a data storage medium as machine-readable code, such code being instructions executable by an array of logic elements such as a microprocessor or other digital signal processing unit. In other implementations of filters as described herein, the actual number of stored states may be lower than the limits indicated above. For example, if it is known that certain forms of the input vector will not be encountered in a particular application, states corresponding to those forms need not be stored. [000112] Reduction of the number of stored states by producing and applying an invert signal is described herein. A similar reduction may be performed with respect to other linear relations that may exist among the possible filter states. For example, states in a first portion of the set of possible fdter states may be expressible as a multiple of corresponding states in a second portion of the set of possible filter states. In such case, it may be more efficient in a particular application to store only the second portion of states and to derive states of the first portion as needed at runtime. A filter according to an embodiment of the invention may also be used in conjunction with a circuit configuration as described in copending United States ProviS10nal Patent Application No. 60/245,232, entitled "CIRCUIT FOR DIGITAL DATA TRANSMISS10N," attorney docket no. 010086P, filed on November 3,2000. Thus, the present invention is not intended to be limited to the embodiments shown above but rather is to be accorded the widest scope consistent with the principles and novel features disclosed in any fashion herein. WE CLAIM: 1. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector, characterized in that the state storage comprising at least one lookup table having values based on components of an antisymmetric finite-impulse-response filter coefficient vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal. 2. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector, characterized in that the state storage comprising combinatorial logic configured and arranged to produce a zero select signal based on at least a portion of the state select vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count and to pass a selected state signal, said selected state signal corresponding to the bank select signal. 3. The system for digital filtering as claimed in claim 2, wherein each among the plurality of storage banks has at least one lookup table having values based on components of a fmite-impulse-response filter coefficient vector. 4. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector, characterized in that the set of logic gates is configured and arranged to map the input vector to the state select vector according to a sequence select signal based on at least a portion of the phase count signal; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector, and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal. 5. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal, characterized in that the digital filter comprises an inverter configured and arranged to receive the selected state signal and an invert signal and to produce an output signal. 6. The system for digital filtering as claimed in claim 5, wherein the invert signal is based on the phase count signal. 7. The system for digital filtering as claimed in claim 5, wherein the components of at least a portion of the state select vector are based on the invert signal. 8. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector; a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal; and a shift register configured and arranged to receive an input signal according to a clock signal and to produce the input vector; characterized in that the digital filter comprises a phase counter configured and arranged to produce the phase count signal, wherein a counting rate of the phase count signal is a multiple of the rate of the clock signal. 9. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal; characterized in that the system for digital filtering comprises a second filter configured and arranged to receive a second input vector and to produce a signal based on a second selected state signal; and an adder configured and arranged to add a signal based on the selected state signal and the signal based on a second selected state signal. 10. The system for digital filtering as claimed in claim 9, wherein said system is configured and arranged to receive values of an input signal over time, and wherein the components of the input vector correspond to values of the input signal received over a first time period, and wherein the components of the second input vector corresponds to values of the input signal received over a second time period different than the first time period. 11. A system for digital filtering, said system comprising: a shift register configured and arranged to receive the input signal and to produce a plurality of input vectors; a plurality of digital filters configured and arranged to receive a phase count signal, each digital filter comprising: a set of logic gates, said set being configured and arranged to receive a corresponding input vector and the phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal; and at least one adder configured and arranged to produce a sum based on the plurality of selected state signals, wherein the components of each of the plurality of input vectors correspond to values of the input signal received over a corresponding time period, each input vector corresponding to a different time period. 12. The system for digital filtering as claimed in claim 11, wherein the state storage of at least one of the digital filters has at least one lookup table. 13. The system for digital filtering as claimed in claim 12, wherein the at least one lookup table has values based on components of a finite-impulse-response filter coefficient vector. 14. The system for digital filtering as claimed in claim 11, wherein the set of logic gates of at least one digital filter is configured and arranged to map the corresponding input vector to the corresponding state select vector according to a sequence select signal based on at least a portion of the phase count signal. 15. The system for digital filtering as claimed in claim 11, wherein at least one of the digital filters comprises an inverter configured and arranged to receive the corresponding selected state signal and an invert signal and to produce an output signal. 16. The system for digital filtering as claimed in claim 15, wherein the invert signal is based on the phase count signal. 17. The system for digital filtering as claimed in claim 15, wherein the components of at least a portion of the corresponding state select vector are based on the invert signal. 18. A method of digital filtering, said method comprising: receiving an input vector and a phase count signal; mapping the input vector to a state select vector according to at least a portion of the phase count signal; inputting the state select vector to a state storage, said state storage comprising a plurality of storage banks; receiving a state signal corresponding to the state select vector from each of the plurality of storage banks; and selecting a state signal from among the plurality of state signals according to a bank select signal. 19. The method of digital filtering as claimed in claim 18, wherein the state storage has a plurality of stored values, and wherein each of at least a subset of the state signals is based on a corresponding one of the stored values. 20. The method of digital filtering as claimed in claim 19, wherein the stored values are based on components of finite-impulse-response filter coefficient vector. 21. The method of digital filtering as claimed in claim 19, wherein the stored values are normalized with respect to a predetermined maximum filter output value. 22. The method of digital filtering as claimed in claim 18, wherein the bank select signal is based on at least a portion of the input vector. Dated this 2 day of May 2003

Full Text

r

This invention relates to digital signal processing.
Digital signal processing techniques may be used to process signals at baseband, intermediate, and radio frequencies. In addition to their use in new applications, such techniques are also replacing analog processing techniques in existing applications such as signal filtering. The numerous advantages that a digital filter may possess over an analog counterpart include a lack of impedance matching problems, guaranteed stability and/or phase linearity, freedom from a change in response due to aging, and programmability and ease of alteration.
[0003] Digital filters are implemented primarly as linear constant coefficient filters. Such filters may be broadly divided into two classes: infinite-impulse-response (IIR) filters and finite-impulse-response (FIR) filters. By incorporating feedback, IIR filters require fewer taps to achieve the same performance. Such filters cause less delay and can be implemented with less hardware than FIR filters with similar characteristics. However, IIR filters are harder to design than FER filters, generally have nonlinear phase characteristics, and may have stability problems as well.
In contrast to IIR filters, FIR filters are guaranteed to produce a bounded output in response to a bounded input Moreover, if the coefficients of a FIR filter are symmetric (or antisymmetric), then the filter will have a linear phase response. One basic FIR filter system is illustrated in FIGURE 1. Shift register 20 receives an input signal (e.g. a series of digital values) and outputs an N-element input vector SIC to filter 40. In this example, a new input value is shifted into register 20 upon a predetermined transition of a clock signal from clock 30. Filter 40 contains a filter

coefficient vector of length N, N multipliers, and an N-input adder. For each instance of input vector S10 (expressed as a series of values x0, X1, X2,..., XN), filter 40 outputs a value y according to the expression

Further information on the theory and design of digital filters may be found in such documents as Electronic Filter Design Handbook 2" ed., by A. B, Williams and F. J. Taylor, McGraw-Hill, New York, 1988; Digital Filtering: an introduction, E. P. Cunningham, Houghton Mifflin, Boston, 1992; and section XVI of The Circuits and Filters Handbook ed. by W.-K. Chen, CRC Press, Boca Raton, FL, 1995.
Lookup tables (LUTs) are used in various computing contexts to hold decision information that cannot easily be expressed mathematically. Two examples of information that may be stored in a LUT are (1) the mapping of IP addresses to aliases or to physical network locations, and (2) colormaps. Lookup tables have also been used in waveform generation applications to hold values that are frequently used but may be cumbersome to calculate, such as a mapping from a time index (x) into a trigonometric value (such as sin x or cos x).
A digital filter as shown in FIGURE I is a calculation-intensive circuit. Because the set of possible input values to a digital filter is finite, the response of such a filter is completely deterministic and may be specified before runtime. However, it has not generally been feasible to use LUTs in digital filtering applications. In order to directly represent every possible output of an N-tap FIR filter which receives an input data stream M bits wide, a lookup table of size 2MxN would be required. For an 8-bit-wide input and a relatively short 16-tap filter, such a table would have to contam 2123 (or on the order of 1038) symbol storage spaces.
If the input data stream for the filter is only I bit wide (i.e. binary-valued), then the size of the lookup table reduces to 2N symbol storage spaces. Even m this case, however, the size of the filter is severely limited by the resulting storage requirements: for example, a 16-tap filter would require 216 symbol storage spaces

(i.e. one megabit of storage area for every bit of the width of the output symbols). Where the performance of a longer filter is required or the application imposes severe circuit area and/or power constraints (e.g. as in a portable device for wireless communications), FIR implementation using lookup tables may not be feasible.
SUMMARY
A system for digital filtering according to one embodiment of the invention includes a digital filter that has a set of logic gates, a state storage, and a multiplexer. The set of logic gates is configured and arranged to receive an input vector and a phase count signal The phase count signal may count at a rate that is a multiple of the rate of a clock associated with the input vector. The set of logic gates is configured and arranged to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector. For example, the set of logic gates may map the input vector to the state select vector according to a sequence select signal based on at least a portion of the phase count signal.
The state storage has two or more storage banks, each configured and arranged to receive the state select vector and to produce a state signal indicated by that vector. For example, the state storage (or each of the storage banks) may include one or more lookup tables having values based on components of a finite-impulse-response filter coefficient vector (such as a symmetric or antisymmetric filter coefficient vector). The state storage may also include combinatorial logic configured and arranged to produce a signal (such as a zero select signal) based on at least part of the state select vector.
The multiplexer is configured and arranged to receive the two or more state signals and to pass a selected state signal corresponding to a bank select signal. The bank select signal is based on the phase count signal and may also be based on at least a part of the input vector.
The digital filter may also include an inverter configured and arranged to produce an output signal based on the selected state signal and an invert signal. The invert signal is based on at least part of the input vector and may also be based on the

phase count signal. Additionally, components of at least a portion of the state select vector may be based on the invert signal
Such a system may include a shift register configured and arranged to produce the input vector and a phase counter configured and arranged to produce the phase count signal. The system may also include additional digital filters, with one or more adders configured and arranged to produce a sum based on the selected state signals.
A method of digital filtering according to an embodiment of the invention includes receiving an input vector and a phase count signal and mapping the input vector to a state select vector according to the phase count signal. The method also includes inputting the state select vector to a state storage that includes two or more storage banks. From each of the storage banks, a state signal corresponding to the state select vector is received, and one from among the state signals is selected according to a bank select signal. As noted above, the bank select signal is based on the phase count signal and may also be based on at least a part of the input vector.
Additional embodiments of the invention and applications thereof are described and/or illustrated herein. For example, a system or method according to an embodiment of the invention may be applied to filter a binary data stream according to the 48-tap FIR filter shown in TABLE 1.
BRIEF DESCRIPTION OF THE DRAWINGS
FIGURE 1 is a block diagram of a basic FIR filter system,
FIGURE 2 shows an example of a data path for a pulse-shaping filter
system.
FIGURES 3A, 3B, and 3C illustrate signals a,x,y of FIGURE 2, respectively.
FIGURE 4 shows a phase decomposition of a FIR filter.

FIGURE 4A shows a phase decomposition of a FIR filter.
FIGURES 5A, 5B, and 5C illustrate an approach to reducing storage according to an embodiment of the invention.
FIGURES 6A shows a block diagram of a digital filter 100 according to an embodiment of the invention.
FIGURE 6B shows a block diagram of a system for digital filtering according to an embodiment of the invention.
FIGURE 7 shows a block diagram of an exemplary implementation of set of logic gates 110.
FIGURE 8 shows a block diagram of an exemplary implementation 112 of set of logic gates 110.
FIGURE 9A shows a phase decomposition of a type 2 FIR filter.
FIGURE 9B illustrates a reduction of the decomposition of FIGURE 9A.
FIGURE 10 shows a block diagram of an implementation 104 of a filter 100 according to an embodiment of the invention.
FIGURE llA shows a block diagram of an implementation 114-1 of set of logic gates 110.
FIGURE IIB shows a block diagram of an implementation 124cl of storage bank 124c.
FIGURE 12 shows a block diagram of multiplexer 134. FIGURE 13A shows a phase decomposition of a type 2 FIR filter.
FIGURE 13B illustrates a reduction of the decomposition of FIGURE 13A.

FIGURE 14 shows a block diagram of an implementation 114-2 of set of logic gates 110.
FIGURE 15 shows a block diagram of an implementation 124c2 of storage bank 124c.
FIGURE 16A shows a phase decomposition of a type 2 FIR filter.
FIGURE 16B illustrates a reduction of the decomposition of FIGURE 16A.
FIGURE 17 shows a block diagram of an implementation 116-1 of set of logic gates 110.
FIGURE 18 shows a block diagram of an implementation 116-2 of set of logic gates 110.
FIGURE i9A shows a phase decomposition of a type 1 FIR filter.
FIGURE 19B illustrates a reduction of the decomposition of FIGURE 19A
FIGURE 20 shows a block diagram of an implementation 118 of set of logic gates 110.
FIGURE 21 shows a block diagram of an implementation 200 of a digital filter according to another embodiment of the invention.
FIGURE 22 shows a block diagram of an exemplary implementation of set oflogic gates 210.
FIGURE 23 shows a block diagram of an exemplary implementation 212 of set of logic gates 210.
FIGURE 24 shows a block diagram of one binary-input implemeatation 202 ofa filter 200.

FIGURE 25 shows a block diagram of one implementation 204 of a filter 200. FIGURE 26 shows a block diagram of a set of logic gates 214. FIGURE 27 shows an exemplary implementation of multiplexer 234. FIGURE 28 shows a block diagram of a filter 250 according to an embodiment of the invention.
FIGURE 29A shows a phase decomposition of a 24-tap FIR filter. FIGURE 29B shows a reduction of the decomposition of FIGURE 29A. FIGURE 30A shows a division of the reduction of FIGURE 29B. FIGURE 30A shows another division of the reduction of FIGURE 29B. FIGURE 30B shows another division of the reduction of FIGURE 29B. FIGURE 3 IB shows a division of the decomposition of FIGURE 29A. FIGURE 32 shows a block diagram of an implementation 260 of filter 250. FIGURE 31C shows another division of the decomposition of FIGURE 29A.
DETAILED DESCRIPTION
Digital filters are frequently used to modify the frequency characteristics of an input signal. One such application is to control the bandwidth of a baseband signal before transmission (e.g. over a radio frequency (RF) channel). FIGURE 2 shows one example of a data path for a pulse-shaping filter system that includes a zero-padding operation 10 and a FIR filter 45. FIGURES 3A, B, and C provide illustrations of signals -a = [K, a0, a1, a2, as, K],-x, and-y, respectively.
In this non-limiting example, input signal is binary-valued (±1), while output
signal-y is more than one bit wide. Zero-padding operation 10 produces

upsampled signal x = K ,a,0,9,a,a1,0,0,a2,0,0a,0,0,K] by inserting (L -1) zero samples for each sample of signal a (in this example, upsampling factor L = 3, and the zero samples are inserted after each data value). Filter 45 filters signal K to
produce pulse-shaped signal y. Coefficients for one particular example of a pulse-shaping filter are shown in TABLE 1 below; this 48-tap symmetric filter is specified in Table 6.1.3.LlO-1 of TIA/EIA Interim Standard IS-95-A (May 1995, Telecommunications Industry Association, Arlington, VA) for a binary data stream upsampled by L = 4.

In an application where the N-element filter coefficient vector is specified for a zero-padded input stream, the number of nonzero terms that contribute to each

output value is limited by N/L rather than N (where L is the upsampling factor and N is the length of the filter coefficient vector). Expressions for each of the L output values Y1 that are produced for one instance of input vector [ao, a1, 0.2, a3] follow, each expression including N/L possibly nonzero terms (in this non-limiting example, L = 4 andN = 16):
These expressions are illustrated in FIGURE 4A, which demonstrates that the operations of such a filter may be modeled as separate applications of the input vector to L nonoverlapping cosets (or phases) of the filter coefficients.
The zero-padding and filtering operations shown in FIGURE 2 may also be combined into a single filtering operation. In one possible implementation of these prmciples, the values of the N terms of expressions (I)-(4) sre precalculated and stored for each possible input vector. These values are then retrieved at runtime (according to the phase number and the particular instance of the input vector) as output values of the filter. In such case, the total number of states to be stored may be reduced fiom PN (2N for binary input) to L _ P"^ (L _ 2N/L for binary input), where P is the number of possible states for each component of the input vector, and the filter is clocked at a rate at least L times greater than the clock associated with the input vector (e.g. clock 30 in FIGURE 1). In the example of FIGURE 4A, the total number of states to be stored may be reduced firom 216 to 26 for binary input (with the filter output values being arbitrarily wide).
In a case where the filter coefficient vector is symmetric (hi == h(N+1)), the maximum required storage capacity may be reduced further (i.e. by a factor of 2). FIGURE 4B illustrates how two values may be retrieved from the reduced storage at runtime (e.g. in successive filter clock periods), each according to the phase number and a respective half of the input vector. These two values are then added together to produce a filter output value. In this case, the filter is clocked at a rate at least 2L

times greater than the clock associated with the input vector. Additionally, the two retrieved values to be added may be many bits wide, and an adder having considerable complexity (and possibly a considerable delay) may be required to perform the summing operation.
FIGURES 5A, 5B, and 5C illustrate an alternative approach to reducing the required storage capacity in a case where the filter coefficient vector is symmetric. FIGURE 5A shows how the symmetry of the coefficients can be exploited to allow the entire input vector to be applied as an index to the reduced storage for each phase. In FIGURE 5B, the L phases axe reduced to L/2 banks indexed by a sequence vector having two states. In the first state, the input vector is mapped to the sequence {a0, as, a1, aa}. In the second state, the input vector is mapped to the sequence {as, a0, a2, ai}. FIGURE 5C demonstrates how each desired filter output may be retrieved m a single indexing operation according to a bank select signal and a mapping of the input vector to a selected sequence.
FIGURE 6A shows a block diagram of a digital filter 100 according to an embodiment of the invention. A set of logic gates 110 receives the input vector S10 and a phase count signal S20. In an exemplary implementation, phase count signal S20 is clocked at a rate L times that of the clock associated with input vector S10, such that phase count signal S20 counts from 0 to (L -1) for each instance of the input vector. Based on at least a portion of phase count signal S20, set 110 selects a sequence and maps the input vector to a state select vector S30 according to die selected sequence. Set 110 also produces a bank select signal S40 based on phase count signal S20 (or a portion thereof).
State storage 120 includes two or more storage banks 1201, each receiving state select vector S30. Each storage bank 120i may include combinatorial logic and/or a lookup table having stored values. In some implementations, two or more of storage banks 120i may mclude different portions of a single lookup table.
Each storage bank 120i outputs a state signal S60i. Multiplexer 130 receives the state signals S60i and passes one among them as selected state signal 350 according to bank select signal 840.

In one binary-input implementation of the example illustrated in FIGURE 5C, state storage 120 has two storage banks 120a (bank 0) and 120b (bank I). In this implementation, bank 0 stores the sixteen values represented by the expresS10n (± ho ± h3 ± h4 ± h2), while bank 1 stores the sixteen values represented by the expresS10n (± h1±h2±h5±h6).
FIGURE 6B shows a block diagram of a system for digital filtering according to an embodiment of the invention. Shift register 20 receives an input signal S5 and a clock signal from clock 30 and produces an N/L-component input vector S10. Filter 100 receives input vector S10 and phase select signal S20 (from phase counter 300) and produces selected state signal S50. As noted above, filter 100 produces L output values for each instance of input vector S10.
[00070] FIGURE 7 shows a block diagram of an exemplary implementation of set of logic gates 110 for a type 2 FIR filter (i.e. having a symmetric filter coefficient vector of even length). In this implementation, multiplexer pairs M10 and M20 map input vector S10 to state select signal S30, switching between the two sequences according to sequence select signal S50 (here, the high bit of phase count signal S20) and inverter 110. XOR gate X40 receives phase count signal S20 and produces bank select signal S40, which controls multiplexer 130 to select between the state signals S60 produced by storage banks 120a, 120b (banks 0,1) of state storage 120 as discussed above.
FIGURE 8 shows a block diagram of an exemplary implementation 112 of set of logic gates 110 for a type 4 FIR filter (i.e. having an antisymmetric filter coefficient vector of even length). In this implementation, inverters 120 and 130 invert the components in the latter half of input vector S10 (here, aa and aa).
A filter according to an embodiment of the invention as shown in FIGURE 6 is not limited to implementations in which input vector S10 has binary-valued components. For example, implementations of sets of logic gates 110 and 112 as shown in FIGURES 7 and 8 may also be used in applications where components of input vector S10 have more than one bit In such cases, multiplexer pairs MIO, M20 may be configured to select between multi-bit input values (in response to a binary

control signal), and inverters 120,130 may be configured to invert mnlti-bit data values.
SetvS 110 (and } 12) as shown in FIGURES 7 and 8 may be used in implementing filter coefficient vectors of arbitrary even length N by adding additional multiplexer pairs (and one or more corresponding inverters) as appropriate. As noted above, such filters may be decomposed into (and state storage 120 may be implemented to include) L/2 banks.
FIGURE 9 A illustrates an example of a phase decomposition of a Type 2 FIR filter in which L is odd and N/L is even (here, L == 5, N = 10, and N/L = 2). As shown in FIGUKE 98, such a case (having L phases) may be condensed to ceil(L/2) banks (ceil(x) denoting the smallest integer not less than x), where the highest numbered bank has only one sequence (sequence number X indicating 'don't care*).
FIGURE 10 shows a block diagram of an implementation 104 of a filter 100 according to an embodiment of the invention for a case where L is odd and N/L is even (e.g. as shown in FIGURE 9B). In this implementation, state storage 120 include ceil(L/2) banks, each receiving state select vector S34, and multiplexer 134 selects from among the ceil(L/2) state signals S60i according to bank select signal S44.
FIGURE llA shows a block diagram of an implementation 114-1 of set of logic gates 110 suitable for the particular case illustrated in FIGURE 9B. In this implementation, XOR gate X60 receives the two high bits of phase count signal S24 (which counts from 0 to (L-1) - 4) and produces sequence select signal S54, and the two low bits of phase count signal S24 serve as bank select signal S44.
As noted in FIGURE 9B, the sequence in which a0 and ai are mapped to state select signal S34 is irrelevant to bank 2, as both input values correspond to the same filter coefficient value. Another consequence of this correspondence is that if the value of ao is the inverse of the value of ai, the filter output is zero. In fact, by including logic to produce zero and inverted values at runtime, bank 2 may be implemented in tiiis case with only one stored value.

FIGURE 1 IB shows a block diagram of an implementation 124cl of storage bank 124c for the binary input case. XOR gate X70 receives state select vector S34. Via zero select signal S70-1, XOR gate S70 causes multiplexer M40 to output a zero value if the two components of state select vector differ. Value storage
4
210-1 stores only one value, which is received by XOR gate X80. If invert signal S80-1 (either component of state select vector S34) is high, the stored value is inverted. XOR gate X80 may be implemented to receive one multi-bit value (the stored value) and one binary value (invert signal S80-1). Depending upon the mapping between input and output values in the particular implementation, invert signal S80-1 may be inverted before being inputted to XOR gate X80.
FIGURE 12 shows a block diagram of multiplexer 134 suitable for use in the implementation 104 of filter 100 shown in FIGURE 10. Multiplexer i34a selects between the state signals S64 of bank 0 and bank 2 according to the high bit of bank select signal S44, and multiplexer 134b selects between the state signal S64 of bank 1 and the output of multiplexer 134a according to the low bit of bank select signal S44.
FIGURE 13A illustrates another example of a phase decomposition of a Type 2 FIR filter in which L is odd and N/L is even (here, L = 5, N = 20, and N/L = 4). FIGURE 13B shows how the L phases may be condensed to ceil(L/2) banks.
FIGURE 14 shows a block diagram of an implementation 114-2 of set of logic gates 110 suitable for the case illustrated in FIGURE 13B. Multiplexer pairs M10 and M20 map input vector S14 to state select vector S34 according to sequence select signal S54 and its inverse. Set 114-2 may be used in implementing filter coefficient vectors of arbitrary even length N by adding additional multiplexer pairs (and one or more corresponding inverters) as appropriate.
FIGURE 15 shows a block diagram of an implementation I24c2 of storage bank 124c suitable for the case illustrated in FIGURE 13B. In this case, value storage 210-2 stores only four values. Via a collection of logic gates (XOR gates XI10, X120. X130; AND gates A10, A20, A30; 0R gate 010; and inverter 140) and multiplexer M50, state select vector S34 is processed to select the appropriate value from value storage 210-2 and to produce zero select signal S70-2 and invert signal

S80-2. Other collections of logic gates may be used, and Boolean expresS10n minimization techniques (such as Karnaugh maps) may be used to produce such other collections and/or to extend implementatioii 124c2 to state select vectors having more components while minimizing the size of value storage 210. As with XOR gate X80 described above, XOR gate X90 may be implemented to receive one multi-bit value (the selected stored value) and one binary value (invert signal S80-2).
As discussed with reference to FIGURE 8, sets of logic gates 114-1 and 114-2 may be extended to apply to the antisymmetric case by inverting fte components in the latter half of input vector S10.
FIGURE 16A illustrates an example of a phase decomposition of a type 2 FIR filter in which L is even and N/L is odd (here, L = 4, N = 20, and N/L - 5). FIGURE 16B shows how the L phases may be condensed to L/2 banks.
FIGURE 17 shows a block diagram of an implementation 116-1 of set of logic gates 110 suitable for the case illustrated in FIGURE 16B. As the middle component of input vector S16 (here, aa) shares filter coefficients with no other component, this value may pass through to the same component of state select vector S36 for all sequences.
. FIGURE 18 shows a block diagram of an implementation 116-2 of set of logic gates 110 suitable for a case as illustrated in FIGURE 16B in which the filter coefficient is antisymmetric. Multiplexer M70 selects between the middle component of input vector SI 6 and its inverse (as produced by inverter 150) according to sequence select signal S50. In applications where components of input vector S16 have more than one bit, multiplexer M70 may be configured to select between multi-bit input values (in response to a binary control signal), and inverter 150 may be configured to invert a multi-bit data value.
Sets of logic gates 116-1 and 116-2 may be used in implementing filter coefficient vectors of arbitrary even length N by adding additional multiplexer pairs (and one or more corresponding inverters) as appropriate. As noted above, such filters may be decomposed into (and state storage may be implemented to include) ceil(L/2) banks.

FIGURE 19A illustrates an example of a phase decomposition of a type 1 FIR filter (i.e. having a symmetric filter coefficient of odd length). In such case, both L and N/L are odd (here, L - 5, N = 15, and N/L - 3). FIGURE 19B shows how the L phases may be condensed to ceil(L/2) banks.
FIGURE 20 shows a block diagram of an implementation 118 of set of logic gates 110 suitable for a case as illustrated in FIGURE 19B. Implementation 118 may be applied to cases of an antisymmetric filter coefficient vector (type 3) and/or components of input vector S18 having more than one bit by extenS10n as described herein. Additionally, set of logic gates 118 may be used in implementing filter coefficient vectors of arbitrary odd length N by adding additional multiplexer pairs (and one or more corresponding inverters) as appropriate.
FIGURES I IB and 15 above demonstrate how the number of stored values in a storage bank may be reduced by applying an invert signal decoded from the input vector. This principle of exploiting symmetry among the set of output states may also applied more generally to reduce the size of the state storage by a factor of 2. FIGURE 21 shows a block diagram of an implementation 200 of a digital filter according to another embodiment of the invention. In this implementation, set of logic gates 210 produces an invert signal S52, and an inverter (here, XOR gate X50) produces an output signal S70 based on selected state signal S50 (selected firom outputs of state storage 220) and invert signal S52,
FIGURE 22 shows a block diagram of an exemplary implementation of set of logic gates 210 to a type 2 FIR filter bank decomposition as shown in FIGURE 5C. In this implementation, the output of a multiplexer of one of the multiplexer pairs M10, M20 serves as invert signal S50. XOR gates X10, X20, and X30 receive invert signal S50 and the signals from the other multiplexers and produce the components of state select vector S230, As state storage 220 is only half as large as state storage 120, state select vector S230 is one bit narrower than state select vector S30 as shown in FIGURE 7.
in a case where components of input vector S10 have more than one bit, one bit of the output of a multiplexer of one of the multiplexer pairs M10, M20 serves

as invert signal S50. In such case, the other bits of the output of that multiplexer are inputted to an XOR gate that receives invert signal S50. Like XOR gates X10, X20, and X30 described above, this XOR gate also produces components of state select vector S230.
FIGURE 23 shows a block diagram of an exemplary implementation 212 of set of logic gates 210 for a type 4 FIR filter. In this implementation, XOR gate X50 receives sequence select signal S50 and one bit of the output of a multiplexer of one of the multiplexer pairs M10, M20 and produces invert signal S52.
Implementations of filter 200 and set of logic gates 210 may be extended to cases of filter coefficient vectors of arbitrary length, and/or to various odd/even relationships of L and N/L, as described above with respect to implementations of filter 100 and set of logic gates 110.
FIGURE 24 shows a block diagram of one binary-input implementation 202 of a filter 200 that is suitable for application to the example illustrated in FIGURE 5C, In this implementation, state storage 222 has two storage banks 222a {bank 0) and 222b (bank 1), with bank 0 storing the eight values represented by the expresS10n (ho ± ha ± ha+hr) and bank 1 storing the eight values represented by the expresS10n (h1+ h2+ hs ± he).
In some applications, it may be desirable to divide one or more of the storage banks into subbanks. For example, it may be desired to modify a state storage 222 as described above by dividing each bank into two subbanks, each subbank receiving the state select vector and producing a state signal. FIGURE 25 shows a block diagram of one such implementation 204 in which subbanks 224a0 and 224al each store the four values represented by the expresS10n (so + Si ± S2 ± S3) [(ho + hs ± h4 ± by) and (hi + ha ± hs ± hg), respectively], while subbanks 224b0 and 224b 1 each store the four values represented by the expresS10n (so - s1 ± sa ± S3) [(ho - ha =fc h4 ± h7) and (h1 - hz ± hs ± he), respectively].
FIGURE 26 shows a block diagram of a set of logic gates 214 suitable for use in filter 204. Although the total number of stored states in state storage 224 is the same as the total number of stored states in state storage 222, the number of banks

receiving the state select vector and producing a state signal is greater in filter 204 (here, by a factor of two). Consequently, multiplexer 134 selects from among a greater number of inputs. At the same time, the number of states stored in each bank 224 is less (here, also by a factor of two) such that state select vector S234 may be more narrow than state select vector S230.
In this particular example, set 214 is derived from set 210 by moving one of the state select vector components (here, the component corresponding to state so in set 210) to bank select signal S44. In other applications, a different number of banks may be implemented, with a corresponding exchange of components between the state select vector and the bank select signal. FIGURE 27 shows a block diagram of an exemplary Implementation of multiplexer 234.
FIGURE 28 shows a block diagram of a filter 250 according to an embodiment of the invention. In this embodiment, input vector S10 is split into two separate input vectors S10a and S10b, each being inputted to a filter 100 (constructed e.g, as shown in FIGURE 6A), The output signals S70 produced by filters 100 are added by adder 400 to obtain filter output signal S80. In one implementation, filters 200a,b receive the same phase count signal; in another implementation, filters 200a,b receive the same sequence select and bank select signals (generated e.g. as described herein).
FIGURE 29 A shows a phase decomposition of a 24-tap FIR filter (here, L - 4), and FIGURE 29B shows a reduction of this symmetric (or anti-symmetric) filter into ceil(L/2) banks. Assuming a binary input, the total number of stored states in an application of filter 200 to this example may reach (L _ 2(N/L)) or 128.
FIGURE 30A shows a diviS10n of the reduction of FIGURE 29B into two sections. In an exemplary application of filter 250 to this filter coefficient vector, input vector S 10a includes the coraponents of the first section (ho-hs) and input vector S10b includes the components of the second section (h4-h11). The total number of stored states in each filter 100i may reach L times 2 to the power (length of input vector S10i minus 1). Assuming a binary input in this example, this limit may be

calculated as (4 „ 22-1) or 8 for filter 200a, plus (4 _ 22-1) or 32 for filter 200b, for a total of 40.
An even further reduction in the total number of stored states may be achieved by using the three-part diviS10n shown in FIGURE 30B. In this example, filter 250 is implemented with three filters 100, each receiving a four-component input vector S10i, and a three-input adder to receive the three output signal S70 and to produce the filter output signal S80. In this example, the total number of stored states may reach only 24 (or 3 _ 8).
In another example, FIGURE 31A shows a phase decomposition of a 48-tap four-times-oversampled symmetric FIR filter as shown in TABLE 1. Each of the four phase expresS10ns may then be divided into three four-term blocks as shown in FIGURE 31B, each block having 16 possible values (for binary input) and serving as an input vector to one of the filters in a three-filter implementation as described above.
Note that the particular grouping of input values shown in FIGURE 3 IB is only one of many possible groupings. For example, FIGURE 31C shows another such grouping, which differs from that of FIGURE 3 IB in the placement of coefficients h4-h7 and hg-h1, A particular grouping may also be chosen on the basis of the magnitude of the corresponding filter coefficients, such that blocks having filter coefficients of low magnitude may be formed for processing using a more narrow logical bus width, storage area, etc, than blocks having filter coefficients of higher magnitude.
In a further example, the stored state values may be normalized. In one implementation, a normalization of the filter coefficient vector is calculated according to a factor determined by dividing the maximum possible output value of the filter (e.g. as determined by the unnormalized filter coefficient vector) by the maximum value that may be represented in the number of bits provided for the filter output. In an exemplary application, normalization is used to support an integer implementation of a filter coefficient vector having floating-point components.

FIGURE 32 shows a block diagram of an implementation 260 of filter 250 asapplied to the48-tapfilter ofTABLEl dividedasshowninFIGURE3lB. Inthis example, output signals S70a, S70b, and S70c are eight, nine, and eleven bits wide, respectively, and the outputs of adders 402a and 402b are nine and eleven bits wide, respectively. Filters 200a and 200b are configured to output signed integer values in offset two's complement representation, while filter 200c and adder 402b are configured to output signed integer values in two's complement representation. This particular configuration eliminates the need for an additional adder to process the carry bits from the three filters.
Depending on the numeric representation or representations used in a particular application, it may be desirable to perform additional logic operations when an invert signal is invoked in an implementation as shown, for example, in FIGURE 21. For example, negation of a value encoded in two's complement representation includes both complementation and addition of one. One approach in such case is to include a two-input adder having one input tied to zero, receiving as the other input output signal S70, and having invert signal S50 as the carry-in signal.
FIGURE 32 demonstrates how inverS10n may be handled without additional logic. Numbers encoded in offset two's complement representation differ from numbers encoded in two's complement representation by including a bias of 0,5. For example, the numbers 00101 and 11010 in offset two's complement representation signify the decimal values 5.5 and-5.5, respectively. One feature of offset two's complement representation is that complementing such a number is equivalent to negating it. As each of the two values inputted to adder 402a has a bias of 0-5, the carry__in input to this adder is set to one, and the axider outputs a value in two's complement representation.
Adder 402b receives two inputs in two's complement representation. As negation of a value encoded in two's complement representation includes both complementation and addition of one, invert signal S50 is inputted to the carry _in input of adder 402b to provide the value of one in case of negation.

The foregoing presentation of the described embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments are possible, and the generic principles presented herein may be applied to other embodiments as well For example, the invention may be implemented in part or in whole as a hard-wired circuit, as a circuit configguration fabricated into an application-specific integrated circuit, or as a firmware program loaded into non-volatile storage or a software program loaded from or into a data storage medium as machine-readable code, such code being instructions executable by an array of logic elements such as a microprocessor or other digital signal processing unit.
In other implementations of filters as described herein, the actual number of stored states may be lower than the limits indicated above. For example, if it is known that certain forms of the input vector will not be encountered in a particular application, states corresponding to those forms need not be stored.
[000112] Reduction of the number of stored states by producing and applying an invert signal is described herein. A similar reduction may be performed with respect to other linear relations that may exist among the possible filter states. For example, states in a first portion of the set of possible fdter states may be expressible as a multiple of corresponding states in a second portion of the set of possible filter states. In such case, it may be more efficient in a particular application to store only the second portion of states and to derive states of the first portion as needed at runtime.
A filter according to an embodiment of the invention may also be used in conjunction with a circuit configuration as described in copending United States ProviS10nal Patent Application No. 60/245,232, entitled "CIRCUIT FOR DIGITAL DATA TRANSMISS10N," attorney docket no. 010086P, filed on November 3,2000. Thus, the present invention is not intended to be limited to the embodiments shown above but rather is to be accorded the widest scope consistent with the principles and novel features disclosed in any fashion herein.

WE CLAIM:
1. A system for digital filtering, said system having a digital filter comprising: a
set of logic gates, said set being configured and arranged to receive an input vector
and a phase count signal and to produce a state select vector based on at least a portion
of the phase count signal and at least a portion of the input vector; a state storage
having a plurality of storage banks, each storage bank configured and arranged to
receive the state select vector and to produce a state signal indicated by the state select
vector, characterized in that the state storage comprising at least one lookup table
having values based on components of an antisymmetric finite-impulse-response
filter coefficient vector; and a multiplexer configured and arranged to receive the
plurality of state signals and a bank select signal based on at least a portion of the
phase count signal and to pass a selected state signal, said selected state signal
corresponding to the bank select signal.
2. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector, characterized in that the state storage comprising combinatorial logic configured and arranged to produce a zero select signal based on at least a portion of the state select vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count and to pass a selected state signal, said selected state signal corresponding to the bank select signal.
3. The system for digital filtering as claimed in claim 2, wherein each among the plurality of storage banks has at least one lookup table having values based on components of a fmite-impulse-response filter coefficient vector.

4. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector, characterized in that the set of logic gates is configured and arranged to map the input vector to the state select vector according to a sequence select signal based on at least a portion of the phase count signal; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector, and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal.
5. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal, characterized in that the digital filter comprises an inverter configured and arranged to receive the selected state signal and an invert signal and to produce an output signal.
6. The system for digital filtering as claimed in claim 5, wherein the invert signal is based on the phase count signal.

7. The system for digital filtering as claimed in claim 5, wherein the components of at least a portion of the state select vector are based on the invert signal.
8. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector; a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal; and a shift register configured and arranged to receive an input signal according to a clock signal and to produce the input vector; characterized in that the digital filter comprises a phase counter configured and arranged to produce the phase count signal, wherein a counting rate of the phase count signal is a multiple of the rate of the clock signal.
9. A system for digital filtering, said system having a digital filter comprising: a set of logic gates, said set being configured and arranged to receive an input vector and a phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the

bank select signal; characterized in that the system for digital filtering comprises a second filter configured and arranged to receive a second input vector and to produce a signal based on a second selected state signal; and an adder configured and arranged to add a signal based on the selected state signal and the signal based on a second selected state signal.
10. The system for digital filtering as claimed in claim 9, wherein said system is configured and arranged to receive values of an input signal over time, and wherein the components of the input vector correspond to values of the input signal received over a first time period, and wherein the components of the second input vector corresponds to values of the input signal received over a second time period different than the first time period.
11. A system for digital filtering, said system comprising: a shift register configured and arranged to receive the input signal and to produce a plurality of input vectors; a plurality of digital filters configured and arranged to receive a phase count signal, each digital filter comprising: a set of logic gates, said set being configured and arranged to receive a corresponding input vector and the phase count signal and to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector; a state storage having a plurality of storage banks, each storage bank configured and arranged to receive the state select vector and to produce a state signal indicated by the state select vector; and a multiplexer configured and arranged to receive the plurality of state signals and a bank select signal based on at least a portion of the phase count signal and to pass a selected state signal, said selected state signal corresponding to the bank select signal; and at least one adder configured and arranged to produce a sum based on the plurality of selected state signals, wherein the components of each of the plurality of input vectors correspond to values of the input signal received over a corresponding time period, each input vector corresponding to a different time period.

12. The system for digital filtering as claimed in claim 11, wherein the state storage of at least one of the digital filters has at least one lookup table.
13. The system for digital filtering as claimed in claim 12, wherein the at least one lookup table has values based on components of a finite-impulse-response filter coefficient vector.
14. The system for digital filtering as claimed in claim 11, wherein the set of logic gates of at least one digital filter is configured and arranged to map the corresponding input vector to the corresponding state select vector according to a sequence select signal based on at least a portion of the phase count signal.
15. The system for digital filtering as claimed in claim 11, wherein at least one of the digital filters comprises an inverter configured and arranged to receive the corresponding selected state signal and an invert signal and to produce an output signal.
16. The system for digital filtering as claimed in claim 15, wherein the invert signal is based on the phase count signal.
17. The system for digital filtering as claimed in claim 15, wherein the components of at least a portion of the corresponding state select vector are based on the invert signal.
18. A method of digital filtering, said method comprising: receiving an input vector and a phase count signal; mapping the input vector to a state select vector according to at least a portion of the phase count signal; inputting the state select vector to a state storage, said state storage comprising a plurality of storage banks; receiving a state

signal corresponding to the state select vector from each of the plurality of storage banks; and selecting a state signal from among the plurality of state signals according to a bank select signal.
19. The method of digital filtering as claimed in claim 18, wherein the state storage
has a plurality of stored values, and wherein each of at least a subset of the state
signals is based on a corresponding one of the stored values.
20. The method of digital filtering as claimed in claim 19, wherein the stored
values are based on components of finite-impulse-response filter coefficient vector.
21. The method of digital filtering as claimed in claim 19, wherein the stored values are normalized with respect to a predetermined maximum filter output value.
22. The method of digital filtering as claimed in claim 18, wherein the bank select signal is based on at least a portion of the input vector.
Dated this 2 day of May 2003

Documents:

654-chenp-2003-abstract.pdf

654-chenp-2003-assignement.pdf

654-chenp-2003-claims duplicate.pdf

654-chenp-2003-claims original.pdf

654-chenp-2003-correspondnece-others.pdf

654-chenp-2003-correspondnece-po.pdf

654-chenp-2003-description(complete) original.pdf

654-chenp-2003-description(complete) duplicate.pdf

654-chenp-2003-drawings.pdf

654-chenp-2003-form 1.pdf

654-chenp-2003-form 18.pdf

654-chenp-2003-form 26.pdf

654-chenp-2003-form 3.pdf

654-chenp-2003-form 5.pdf

654-chenp-2003-pct.pdf

« Previous Patent

Next Patent »

Patent Number

206997

Indian Patent Application Number

654/CHENP/2003

PG Journal Number

26/2007

Publication Date

29-Jun-2007

Grant Date

16-May-2007

Date of Filing

02-May-2003

Name of Patentee

M/S. QUALCOMM INCORPORATED

Applicant Address

5775 MOREHOUSE DRIVE, SAN DIEGO, CALIFORNIA 92121-1714

Inventors:

#	Inventor's Name	Inventor's Address
1	MOHESENI,JAFAR M	10181 CAMINO RUIZ # 6,SAN DIEGO,CALIFORNIA 92126
2	BUTLER BRIAN K	2171 VIA NINA, LA JOLLA, CALIFORNIA 92037.
3	ZHANG,HAITAO	11018 CORTEMAR DE DELFINAS, SANDIEG, CALIFORNIA 92130.
4	JOHN DEEPU	7689 PAMILLA DRIVE, #1216,SAN DIEGO, CALIFORNIA 92037.

PCT International Classification Number

H 0 3 H 17/06

PCT International Application Number

PCT/US01/47366

PCT International Filing date

2001-11-03

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	60/245,229	2000-11-03	U.S.A.