Abstract:
A programmable integrated circuit device such as a programmable logic device can be configured as a finite impulse response (FIR) filter capable of operating in decimation mode. The device includes at least one user-configurable random access memory block, and that user-configurable random access memory is configured as coefficient memories and data sample memories. The memories are large enough to hold up to all of the coefficients of the filter and a plurality of data samples at one time. Because the data samples and coefficients need not be shifted through the filter at the programmable logic device clock rate, overclocking of the filter is not necessary. The filter can run at a clock rate which is the same as the input data rate, while taking advantage of the available random access memory to mimic a shift register.

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to programmable integrated circuits, such as programmable logic devices (PLDs), and, more particularly, to the implementation of filters in specialized processing blocks which may be included in such devices. 
     As applications for which PLDs are used increase in complexity, it has become more common to design PLDs to include specialized processing blocks in addition to blocks of generic programmable logic resources. Such specialized processing blocks may include a concentration of circuitry on a PLD that has been partly or fully hardwired to perform one or more specific tasks, such as a logical or a mathematical operation. A specialized processing block may also contain one or more specialized structures, such as an array of configurable memory elements. Examples of structures that are commonly implemented in such specialized processing blocks include: multipliers, arithmetic logic units (ALUs), barrel-shifters, various memory elements (such as FIFO/LIFO/SIPO/RAM/ROM/CAM blocks and register files), AND/NAND/OR/NOR arrays, etc., or combinations thereof. 
     One particularly useful type of specialized processing block that has been provided on PLDs is a digital signal processing (DSP) block, which may be used to process, e.g., audio signals. Such blocks are frequently also referred to as multiply-accumulate (“MAC”) blocks, because they include structures to perform multiplication operations, and sums and/or accumulations of multiplication operations. 
     For example, STRATIX® II and STRATIX® III PLDs sold by Altera Corporation, of San Jose, Calif., include DSP blocks, each of which includes a plurality of multipliers. Each of those DSP blocks also includes adders and registers, as well as programmable connectors (e.g., multiplexers) that allow the various components to be configured in different ways. In each such block, the multipliers can be configured not only as individual multipliers, but also as a number of smaller multipliers, or as one larger multiplier. In addition, one complex multiplication (which decomposes into two multiplication operations for each of the real and imaginary parts) can be performed. 
     Such a DSP block may be configured as a finite impulse response (FIR) filter. Each block may be used to perform the summation of a plurality of multiplications to form a sub-block of a longer FIR filter. 
     Many types of FIR filters may be encountered. Two of those types are an interpolation FIR filter—in which the number of samples is increased by a factor of n by inserting (“interpolating”) n−1 samples between adjacent samples—and a decimation FIR filter—in which the number of samples is decreased by a factor of n by removing n−1 out of every n samples. A DSP block that may be configured as different types of filters, including an interpolation FIR filter and a decimation FIR filter, is shown in copending, commonly-assigned U.S. patent application Ser. No. 11/447,370, filed Jun. 5, 2006, which is hereby incorporated by reference herein in its entirety. 
     As described in the above-incorporated application, when a programmable logic device including a DSP block is configured as a decimation filter, portions of the DSP block must run at several times (e.g., three or four times) the input data rate, because the filter must operate several times with different coefficients on the same data before the data is clocked out of the data registers. This is referred to as “overclocking.” 
     It would be desirable to be able to provide a DSP block in a programmable logic device that could perform decimation filtering without having to overclock the DSP block, especially when processing high input data rates. 
     SUMMARY OF THE INVENTION 
     The present invention relates to specialized processing blocks for PLDs wherein a specialized processing block can be configured as a FIR filter capable of performing decimation without requiring overclocking. This is achieved by using available random access memory (RAM), commonly available on programmable logic devices, in place of shift registers which are typically implemented in logic elements (LEs) of programmable logic devices. Write and read address generation is used to generate an incremental pointer which mimics shift register behavior. Depending on the symmetry structure—i.e., no symmetry, odd symmetry or even symmetry—the address generation sequence is modified accordingly. 
     Discrete memory blocks—e.g., one for each multiplier in the filter design—can be used for data storage. This can be done for data, coefficients, or both. Because RAM is being used instead of shift registers, the data or coefficients can be kept in memory for many clock cycles, without being clocked out of the system. Therefore, all portions of the filter, including multipliers and adders/accumulators, can be run at the same rate as the input data samples, which typically is the ordinary programmable logic device clock rate. 
     The ability to keep all of the data and coefficients in RAM depends on the amount of RAM provided in the programmable logic device. However, using programmable logic devices available from Altera Corporation, of San Jose, Calif., as an example, it is typical to provide RAM in programmable logic devices in blocks of 512 bits or 4 kilobits. This is expected to be sufficient for most decimation filter applications, except possibly applications that require multiple filters on a single device. 
     Therefore, in accordance with the present invention, there is provided a FIR filter structure for operating in decimation filter mode. The FIR filter structure includes a first number of multipliers each corresponding to one or more taps of the FIR filter structure, each of the multipliers having first and second multiplicand inputs. A second number of coefficient memories is provided, each respective one of the coefficient memories being connected to the first multiplicand input of a respective one of the multipliers, and has capacity to store a third number of coefficients. A fourth number of data sample memories is provided, each respective one of the data sample memories being connected to the second multiplicand input of a respective one of the multipliers, and has capacity to store a fifth number of data samples. All of the multipliers, the coefficient memories, and the data sample memories operate at a single clock rate. 
     A programmable logic device so configured, and a method of so configuring a programmable logic device, are also provided. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The above and other objects and advantages of the invention will be apparent upon consideration of the following detailed description, taken in conjunction with the accompanying drawings, in which like reference characters refer to like parts throughout, and in which: 
         FIG. 1  is a conceptual representation of a decimation filter; 
         FIG. 2  is a schematic representation of a multi-channel semi-parallel FIR filter can function as a decimation filter, with overclocking; 
         FIG. 3  is a schematic representation of a non-symmetric decimation filter implemented in accordance with a preferred embodiment of the present invention; 
         FIG. 4  shows a preferred embodiment of a data loading schedule, and corresponding coefficients, for a generic decimation filter with twelve taps and a decimation factor of two, of which the filter in  FIG. 3  is an example; 
         FIG. 5  shows a preferred embodiment of a read/write sequence for the data and coefficient memories in the filter of  FIG. 3 ; 
         FIG. 6  is a schematic representation of an even-symmetric decimation filter implemented in accordance with a preferred embodiment of the present invention; 
         FIGS. 7A ,  7 B and  7 C (hereinafter collectively referred to as  FIG. 7 ) show a preferred embodiment of a read/write sequence for the data and coefficient memories in the filter of  FIG. 6 ; 
         FIG. 8  is a schematic representation of an odd-symmetric decimation filter implemented in accordance with a preferred embodiment of the present invention; 
         FIGS. 9A ,  9 B and  9 C (hereinafter collectively referred to as  FIG. 9 ) show a preferred embodiment of a read/write sequence for the data and coefficient memories in the filter of  FIG. 8 ; 
         FIG. 10  is a simplified block diagram of an illustrative system employing a programmable logic device incorporating the present invention; 
         FIG. 11  is a cross-sectional view of a magnetic data storage medium encoded with a set of machine-executable instructions for performing the method according to the present invention; and 
         FIG. 12  is a cross-sectional view of an optically readable data storage medium encoded with a set of machine executable instructions for performing the method according to the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A FIR filter calculates a weighted sum of a finite number of inputs, summing a number of multiplication results, where each multiplication is between a sample and a coefficient. Each such multiplication may be referred to as a “tap.” Mathematically, a FIR filter may be described as: 
     
       
         
           
             
               Y 
               k 
             
             = 
             
               
                 ∑ 
                 
                   i 
                   = 
                   0 
                 
                 
                   Taps 
                   - 
                   1 
                 
               
               ⁢ 
               
                 
                   c 
                   i 
                 
                 · 
                 
                   s 
                   
                     k 
                     - 
                     i 
                   
                 
               
             
           
         
       
     
     where Y k  is the kth output term, c i  is the ith coefficient, S k-i  is the (k-i)th input sample, and Taps is the number of taps or length of the filter. 
     Decimation filters are used when a signal is resampled at a lower rate. When a high-frequency filter is sampled at a lower rate, data is lost. The higher frequency components may fold back into the signal, so low-pass filtering is needed to prevent distortion of the signal. A generic decimation filter structure  10  is shown in  FIG. 1 . In this case, the filter preferably is like a multi-channel semi-parallel filter  100  as shown in  FIG. 2 , with all of the phases being accumulated together. The input is at LF Hz and the output is at F Hz—i.e., the overclocking is on the input side. 
     In accordance with the present invention, data samples and coefficients preferably are stored in RAM, which is relatively plentiful on programmable logic devices, so that a decimation filter can be run at the same rate as the input data samples. Preferably, this is achieved by implementing respective discrete memory blocks for storage of data and coefficients for each respective multiplier in the filter design. The order in which each new input sample data is written into its respective memory block preferably is based on the symmetry structure (i.e., no symmetry, even symmetry or odd symmetry). The read address logic preferably is a simple incremental pointer which preferably mimics shift register behavior. Similarly, the order of the read address preferably is modified according to the symmetry structure. Preferably, the read/write address generator may implemented in programmable logic of the programmable logic device. 
     Using a 12-tap decimate-by-2 filter as an example, the filter coefficients are: C 1 , C 2 , C 3 , . . . , C 11 , C 12 . With a decimation ratio of 2, every other output sample is discarded. Hence, it decreases the output sample rate by a factor of 2.  FIG. 3  is a block diagram of a non-symmetric decimation filter  30  implemented using memory buffers  31 ,  32  for both data and coefficient storage. For a decimate-by-2 filter, the output sample rate is reduced by a factor of 2, where each filter output can be calculated in 2 clock cycles. Hence, the number of multipliers  33  can be reduced using the time-domain multiplexing (TDM) technique. In this case, the number of multipliers  33  is 6=L/R, where L is the full length of the filter and R is the decimation ratio. Each data buffer  31  preferably has a depth equivalent to R. Each coefficient buffer  32  preferably stores all the coefficients—i.e., it has a depth equivalent to L. 
     The table of  FIG. 4  shows the data loading schedule into the tap delay line for a 12-tap decimate-by-2 filter, of which filter  30  is one example, and the corresponding coefficient that each data sample is being multiplied with at each clock cycle. The numbers in each cell of the table refer to the nth input data sample feeding into the filter as the data is shifted in from the right. 
     In this example, it is possible to decompose the filter into two phases, with 6 taps each, and calculate each output in 2 clock cycles. Coupled with the time-domain multiplexing (TDM) approach, only six multipliers are required. In accordance with the present invention, the filter can run at the input sample rate, storing the data in, e.g., memory blocks  31  in the example of  FIG. 3 . 
     The table in  FIG. 5  shows a preferred write and read sequence from memory buffers, such as the six data memory buffers  31 , storing data and the output from each coefficient buffer, such as coefficient buffers  32 , for a non-symmetric filter structure. The data write address generation preferably uses a round robin schedule targeting all six data memory buffers. The data read address generation (shown by the various shading patterns, which correspond to the various multipliers) preferably is identical across all the data memory buffers  31 . The coefficients preferably are rotated to accommodate the shifts in each clock cycle. In the drawing, different shading signifies a different one of multipliers  33 . 
     In a case of even symmetry, continuing to use the example of a 12-tap decimate-by-2 filter, the coefficients are centered around C 6  and C 7 : 
     C 1 =C 12 , C 2 =C 11 , C 3 =C 10 , C 4 =C 9 , C 5 =C 8 , C 6 =C 7   
       FIG. 6  is a block diagram of an even-symmetric decimation filter  60  implemented using memory buffers  61 ,  62  for both data and coefficient storage. With even filter symmetry, the input data may be pre-added at  63  prior to the multiplier stage  64 . This reduces the number of multipliers  640  by half. For a decimate-by-2 filter, the output sample rate also is reduced by a factor of 2, where each filter output can be calculated in two clock cycles. Hence, the number of multipliers  640  can be reduced further using time-domain multiplexing. The total number of multipliers  640  is L/(2R), where L is the filter length, and R is the decimation ratio. Preferably, all data buffers  61  have the same content and each data buffer  61  has a depth equivalent to L, the full length of the filter, while each coefficient buffer  62  stores R coefficients. 
     The table in  FIG. 7  shows the write and read sequence from the six memory buffers  61  storing data and the output from each coefficient buffer  62  for an even-symmetric filter structure  60 . The data write address generation preferably is shared across all the data memory buffers  61  and the content of all data buffers  61  preferably is identical as discussed above. The data read address generation (shown by the shaded blocks) preferably has two distinct sequences—ascending order (with offset) for the first half of data buffers  61 , and pseudo-descending order (with offset) for the second half of the data buffers  61 . The coefficients preferably are read in a round-robin fashion. In the drawing, different shading signifies a different one of multipliers  640 . 
     In a case of odd symmetry, continuing to use the example of a 12-tap decimate-by-2 filter, the coefficients are centered on C 6 : 
     C 1 =C 11 , C 2 =C 10 , C 3 =C 9 , C 4 =C 8 , C 5 =C 7   
       FIG. 8  is a block diagram of an odd-symmetric decimation filter  80  implemented using memory buffers  81 ,  82  for both data and coefficient storage. With odd filter symmetry, the input data is pre-added at  83  prior to the multiplier stage  84 . The exception is with the data sample associated with the center tap. The multiplexer  85  associated with data buffer  810  allows bypassing of pre-adder stage  83  for the center tap. The select line for multiplexer  85  is made active every other cycle to coincide with the middle tap corresponding to C 6 . With even filter symmetry, this reduces the number of multipliers  840  by half. For the decimate-by-2 filter, the output sample rate also is reduced by a factor of 2, where each filter output can be calculated in two clock cycles. Hence, the number of multipliers can be reduced further using TDM. The total number of multipliers  840  is L/(2R), where L is the filter length, and R is the decimation ratio. Preferably, all data buffers  81  have the same content and each data buffer  81  preferably has a depth equivalent to L, the full length of the filter. Each coefficient buffer  82  preferably stores R coefficients. 
     The table in  FIG. 9  shows the write and read sequence from the six memory buffers  81  storing data and the output from each coefficient buffer  82  for an odd-symmetric filter structure  80 . The data write address generation preferably is shared across all the data memory buffers  81  and the content of the data buffers preferably is identical as discussed above. The data read address generation (shown in the shaded blocks) preferably has two distinct sequences—ascending order (with offset) for the first half of data buffers  81 , and a pseudo-descending order (with offset) for the second half of data buffers  81 . The coefficients preferably are read in a round-robin fashion. In the drawing, different shading signifies a different one of multipliers  840 . 
     The foregoing examples of decimation filters having particular lengths, symmetry and decimation ratios are illustrative only. The present invention allows the use of memory blocks as data storage and coefficient storage for decimation filters, while maintaining the filter sample rate to be equal to the input sample rate. Filters implemented in accordance with the present invention do not require overclocking. With high input sample rates—e.g., over 200 MHz for a decimation filter used in digital down-converters in digital receivers, current technology does not allow devices to run at three times the input rate. Therefore, such filters might not be able to be implemented without the present invention. Even for filters with input sample rates below about 100 MHz, where the required overclocking may be possible, the requirement for overclocking may impose additional constraints on the overall design. The present invention overcomes these difficulties by making better utilization of abundant memory blocks provided on many programmable logic devices. 
     A PLD  280  incorporating such circuitry according to the present invention may be used in many kinds of electronic devices. One possible use is in a data processing system  900  shown in  FIG. 10 . Data processing system  900  may include one or more of the following components: a processor  281 ; memory  282 ; I/O circuitry  283 ; and peripheral devices  284 . These components are coupled together by a system bus  285  and are populated on a circuit board  286  which is contained in an end-user system  287 . 
     System  900  can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD  280  can be used to perform a variety of different logic functions. For example, PLD  280  can be configured as a processor or controller that works in cooperation with processor  281 . PLD  280  may also be used as an arbiter for arbitrating access to a shared resources in system  900 . In yet another example, PLD  280  can be configured as an interface between processor  281  and one of the other components in system  900 . It should be noted that system  900  is only exemplary, and that the true scope and spirit of the invention should be indicated by the following claims. 
     Various technologies can be used to implement PLDs  280  as described above and incorporating this invention. 
     Instructions for carrying out the method according to this invention may be encoded on a machine-readable medium, to be executed by a suitable computer or similar device to implement the method of the invention for programming PLDs. For example, a personal computer may be equipped with an interface to which a PLD can be connected, and the personal computer can be used by a user to program the PLD using a suitable software tool, such as the QUARTUS® II software available from Altera Corporation, of San Jose, Calif. 
       FIG. 11  presents a cross section of a magnetic data storage medium  600  which can be encoded with a machine executable program that can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium  600  can be a floppy diskette or hard disk, or magnetic tape, having a suitable substrate  601 , which may be conventional, and a suitable coating  602 , which may be conventional, on one or both sides, containing magnetic domains (not visible) whose polarity or orientation can be altered magnetically. Except in the case where it is magnetic tape, medium  600  may also have an opening (not shown) for receiving the spindle of a disk drive or other data storage device. 
     The magnetic domains of coating  602  of medium  600  are polarized or oriented so as to encode, in manner which may be conventional, a machine-executable program, for execution by a programming system such as a personal computer or other computer or similar system, having a socket or peripheral attachment into which the PLD to be programmed may be inserted, to configure appropriate portions of the PLD, including its specialized processing blocks, if any, in accordance with the invention. 
       FIG. 12  shows a cross section of an optically-readable data storage medium  700  which also can be encoded with such a machine-executable program, which can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium  700  can be a conventional compact disk read only memory (CD-ROM) or digital video disk read only memory (DVD-ROM) or a rewriteable medium such as a CD-R, CD-RW, DVD-R, DVD-RW, DVD+R, DVD+RW, or DVD-RAM or a magneto-optical disk which is optically readable and magneto-optically rewriteable. Medium  700  preferably has a suitable substrate  701 , which may be conventional, and a suitable coating  702 , which may be conventional, usually on one or both sides of substrate  701 . 
     In the case of a CD-based or DVD-based medium, as is well known, coating  702  is reflective and is impressed with a plurality of pits  703 , arranged on one or more layers, to encode the machine-executable program. The arrangement of pits is read by reflecting laser light off the surface of coating  702 . A protective coating  704 , which preferably is substantially transparent, is provided on top of coating  702 . 
     In the case of magneto-optical disk, as is well known, coating  702  has no pits  703 , but has a plurality of magnetic domains whose polarity or orientation can be changed magnetically when heated above a certain temperature, as by a laser (not shown). The orientation of the domains can be read by measuring the polarization of laser light reflected from coating  702 . The arrangement of the domains encodes the program as described above. 
     It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the various elements of this invention can be provided on a PLD in any desired number and/or arrangement, or on any other type of integrated circuit device with embedded memory. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims that follow.