Finite impulse response filter

A system, a non-transitory computer readable media and a method for FIR filtering. The method may include obtaining a set of input samples; and concurrently applying a FIR filtering process on the set of input samples to provide a set of FIR filtered output samples. The latter may include calculating intermediate results that represent a first number of coefficient-input sample products, while calculating only some of the first number of coefficient-input sample products, wherein the calculating of the intermediate results is executed by using less than a first number of multipliers.

BACKGROUND

The finite impulse response (FIR) filter is a basic building block in modem architecture.

The FIRs are considered significant power consumers in high-speed modems—especially due to the usage of many multipliers.

Creative power efficient FIR design is a differentiator between designs.

The relationship between input samples x and FIR filtered output samples y is given by:

Where y[n] is the output, x[n] is the input, and biis the coefficient, T is the FIR length

A typical prior art FIR includes an input, a sequence of (T−1) delay units, T multipliers (that multiply the input sample and (T−1) delayed versions of the input sample) by coefficients to provide T multiplier outputs, and (T−1) adders for adding the T multiplier output to each other to provide a FIR filtered output. A stream of input sampled provides a stream of FIR filtered output samples.

This typical prior art structure represents a pipeline of a single sample, feasible only for up to ˜1 GBPs designs. In this structure the sample rate and the clock rate are identical.

In higher speeds, parallel processing architectures are used—as a received stream is serial to parallel converted to multiple input streams that are filtered in parallel to provide multiple FIR filtered output streams—that may be parallel to serial converted to provide a single FIR filtered output stream of the same rate as the received stream.

Some systems, for example systems that have parallel processing architectures may include many FIR filters. Each of the FIR filters may include multiple multipliers. Therefore—some systems may include a large number of multipliers—which contribute to the power consumption of such systems.

There is a growing need to reduce the energy consumption of FIR filters and to reduce the energy consumption of system that include FIR filters.

SUMMARY

There may be provided systems, methods, and computer readable medium as illustrated in the specification.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Any reference in the specification to a method should be applied mutatis mutandis to a device or system capable of executing the method and/or to a non-transitory computer readable medium that stores instructions for executing the method.

Any reference in the specification to a system or device should be applied mutatis mutandis to a method that may be executed by the system, and/or may be applied mutatis mutandis to non-transitory computer readable medium that stores instructions executable by the system.

Any reference in the specification to a non-transitory computer readable medium should be applied mutatis mutandis to a device or system capable of executing instructions stored in the non-transitory computer readable medium and/or may be applied mutatis mutandis to a method for executing the instructions.

Any combination of any module or unit listed in any of the figures, any part of the specification and/or any claims may be provided.

The specification and/or drawings may refer to a processor. The processor may be a processing circuitry. The processing circuitry may be implemented as a central processing unit (CPU), and/or one or more other integrated circuits such as application-specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), full-custom integrated circuits, etc., or a combination of such integrated circuits.

Any combination of any steps of any method illustrated in the specification and/or drawings may be provided.

Any combination of any subject matter of any of claims may be provided.

Any combinations of systems, units, components, processors, sensors, illustrated in the specification and/or drawings may be provided.

The term “and/or” means additionally or alternatively. Thus—A and/or B may be only A, only B or a combination of A and B.

Any reference to consisting should be applied mutatis mutandis to consisting and should be applied mutatis mutandis to consisting essentially of.

Some of the example refer to calculating a set of five or three FIR filtered output results—but the illustrated method, system and computer readable medium are applicable to set of any number of FIR filtered output results.

There may be provided a method, a system, and a computer readable medium for energy efficient FIR filtering.

It has been found that the overall number of multipliers may be reduced by replacing a calculation of some of the coefficient-input sample products by other operations. Yet another reduction of multipliers and/or adders can be obtained by utilizing, when at least some of the coefficient-input sample products calculated during a previous iteration. Each reduction may reduce the energy consumption of the circuit or device or system.

For clarity of explanation the following method will refer to the following example:
y0=c0x0+c1x−1+c2x−2
y1=c0x1+c1x0+c2x−1
y2=c0x2+c1x1+c2x0
y3=c0x3+c1x2+c2x1
y4=c0x4+c1x3+c2x2

Whereas y0till y4form a set of five FIR filtered output samples, c−2till c2are coefficients, x−2till x2are input samples, and mathematical expressions such as c0x0are coefficient-input sample products. In out example there are fifteen coefficient-input sample products—three per each FIR filtered output sample.

In order to calculate the set of five FIR filtered output samples there is a need to calculate fifteen coefficient-input sample products—and a brute force calculation will require fifteen multipliers.

The suggested method calculates the five FIR filtered output samples in the following manner:Identifying a set of coefficient-input sample products that can be calculated by a reduced number of multipliers. In our example this set includes a first number (N1) of coefficient-input sample products, wherein in our example N1 equals nine—c0x0, c0x1, c1x0, c0x2, c1x1, c2x0, c1x2, c2x1, and c2x2c0x0is the only coefficient-input sample product selected from the three coefficient-input sample products used for calculating y0, c1x1, c2x0are two out of three coefficient-input sample products used for calculating y1. c1x1, c2x0, c1x2are all three coefficient-input sample products used for calculating y2. c1x2, c2x1are two out of three coefficient-input sample products used for calculating y3. c2x2is the only coefficient-input sample product selected from the three coefficient-input sample products used for calculating y4.Performing, by first multipliers, an element-wise multiplication of input samples of a first subset of the set by a first subset of coefficients to provide first preliminary results. In our case the number of first multipliers is three—and the first preliminary results include m00, m11and m22, whereas m00=c0x0, m11=c1x1, and m22=c2x2. The first preliminary results may also be used as first intermediate results.Calculating second preliminary results. This may include calculating a second number (N2) of sums of coefficient-input sample products that are sums of uncalculated coefficient-input sample products of the first number of coefficient-input sample products. In our example the sums are moon, moon and m1122, whereas m0011=(c0+c1)(x0x1), m0022=(c0+c2)(x0+x2), and m1122=(c1+c2)(x1+x2).The calculating of these sums may be executed in two phasesi. The first phase may include adding the pairs of input samples (for example—(x0+x1), (x0+x2), and (x1+x2)) to provide input sample sums, and adding the pairs of coefficients (for example—(c0+c1), (c0+c2), and (c1+c2)) to provide coefficient sums. It should be noted that the coefficient sums may be calculated once (if the coefficient maintain the same)—or once after each change of the coefficients—and may be used during the calculation of multiple sets of FIR filtered output samples.ii. The second phase may include performing, by second multiplies, an element-wise multiplication (for example—(c0+c1)(x0+x1), (c0+c2)(x0+x2), and (c1+c2)(x1+x2)) of the input samples sums by coefficients sums to provide second preliminary results.Extracting second intermediate results. This may include using adders and/or subtractor units to extract the second intermediate results based on the first intermediate results. In out example—the second intermediate results may include (i) c0x1+c1x0=m0011−m00−m11, (ii) c0x2+c1x1+c2x0=m0022−m00−m22−m11, and (iii) c1x2+c2x1=m1122−m11−m22.Obtaining additional coefficient-input sample products. In our example there is a need to calculate c0x3, c0x4and c2x2. On the other hand c1x−1, c2x−2and c2x−1can be calculated or may be obtained from a calculation of a previous set of five FIR filtered output samples. Thus x−1may be x4of the previous calculation and x−2may be x3of the previous calculation.

FIGS.1A-1Dillustrate difference circuits for calculating five FIR filtered output samples. The circuits differ from each other by the manner that coefficient sums and additional CIS products are obtained. InFIG.1Athe coefficient sums and the additional CIS products are calculated. InFIG.1Bthe coefficient sums are retrieved from memory and the additional CIS products are calculated. InFIG.1Cthe coefficient sums are calculated and the additional CIS products are retrieved from memory. InFIG.1Dthe coefficient sums and the additional CIS products are retrieved from memory.FIGS.1A-1Dillustrate different tradeoffs between memory resources and logic units.

Referring toFIG.1A—an input stream10of thirteen input samples (there are much more input samples—only some are illustrated) is provided—received by an input circuit (not shown). Seven input samples x−2till x4(stored in input12) are fetched. Three coefficients c1, c2, and c3are provided (stored in memory14—which may be a part of input12).

FIG.1Aalso illustrates a FIR filtering circuit20that is configured to concurrently apply a FIR filtering process on the set of input samples to provide a set of FIR filtered output samples; wherein the concurrently applying of the FIR filtering process comprises calculating intermediate results that represent a first number of coefficient-input sample products, while calculating only some of the first number of coefficient-input sample products, wherein the calculating of the intermediate results is executed by using less than a first number of multipliers.

Three coefficient sums are calculated by three coefficient adders23. Three input sample sums are calculated by first adders23. Three first multipliers22calculate three CIS products. Three additional multipliers21calculate three additional CIS products. Three second multiplies25perform three element-wise multiplications of the input samples sums by coefficients sums to provide three second preliminary results. Three add-subtract units26extract second intermediate results. Two add-subtract units include one addition (+) input and two subtraction (−) inputs. A third add-subtract unit (denoted27) includes two addition (+) inputs and two subtraction (−) inputs. The third add-subtract unit28outputs a second intermediate result that equals one of the FIR filtered output samples.

Four output adders27calculate the four other FIR filtered output samples based on the outcome of the first and second add-subtract units, the additional CIS multipliers and the CIS multipliers.

In this case there are fewer multipliers and adders. The additional CIS products are c1x−1+c2x−2and c2x−1. The only coefficient sum is c1+c0. The only input samples sum is x1+x0.

Amended circuits that retrieve the coefficient sum and/or additional CIS products may be provided

Method100may start by step110of obtaining a set of input samples.

Step110may be followed by step120of concurrently applying a FIR filtering process on the set of input samples to provide a set of FIR filtered output samples.

Step130may include identifying a set of coefficient-input sample products that comprises the first number of coefficient-input sample products.

The set may include (a) two repetitions of a single coefficient-input sample (CIS) product from multiple CIS products required to calculate a FIR filtered output samples, and (b) a sum of all CIS products required to calculate a FIR filtered output sample. Depending on the number of the FIR filtered output samples per set of FIR filtered output samples—there may be additional sums of CIS products—wherein the number of CIS product per FIR filtered output sample gradually increased (for example by one).

Any other selection of such a set of CIS products may be provided.

Step140may include calculating intermediate results that represent a first number of coefficient-input sample products, while calculating only some of the first number of coefficient-input sample products. The calculating of the intermediate results is executed by using less than a first number of multipliers.

Step160may include obtaining additional CIS products.

Step160may include calculating all the additional CIS products. This may include calculating a third number of additional CIS products.

Alternatively—step160may include calculating a fourth number of additional coefficient-input sample products and retrieving a fifth number of additional coefficient-input sample products from a calculation of a previous set of FIR filtered output samples.

Step160may be followed by step170of determining the set of FIR filtered output samples based on the additional CIS products and the intermediate results.

Step170may be followed by responding to the determining of the set of FIR filtered output samples. This may include outputting the set of FIR filtered output samples, storing the set of FIR filtered output samples, storing at least some of the CIS products to be used in a next iteration.

It should be noted that steps110-170may be repeated multiple times—as the FIR filtering is applied on multiple sets of input samples. For example—one or more streams of input samples may be provided and segmented to multiple sets of input samples. An input module may receive a received stream that may be converted to multiple input streams—that may be processed in parallel to each other.

For example—a receiver may receive a received stream that may have a symbol rate that well exceeds (for example by factor of ten, fifty, one hundred, and the like) a clock rate of the received—and it is split to multiple input streams. Each input stream is virtually segmented to sets of input samples—and steps110-170illustrates the FIR filtering of a single set of input samples.

FIG.4illustrates example of step140.

Step140may include step142of performing, by first multipliers, an element-wise multiplication of input samples of a first subset of the set by a first subset of coefficients to provide first intermediate results that belong to the preliminary results.

Step140may include step144of calculating second preliminary results that are a second number of sums of certain coefficient-input sample products, wherein the second preliminary results are calculated without calculating each one of the certain coefficient-input sample products.

Step146may include of performing, by first adders, an element-wise addition of pairs of input samples of the set, to provide input samples sums.

Step148may include obtaining coefficient sums. The obtaining may include calculating (by coefficient adders) or receiving the coefficient sums.

Steps146and148may be followed by step150of performing, by second multiplies, an element-wise multiplication of the input samples sums by coefficients sums to provide second preliminary results that belong to the preliminary results.

Step150may be followed by step152of extracting, by using add-subtract units that may include adders and/or subtractors, the second intermediate results.

Any value or number referred to in the application may be a non-limiting example of such a value of number. For example—the number of demodulators per coherent receiver may differ from two, the number of RX units per pluggable modulator may differ from four.

It will be appreciated by persons skilled in the art that the embodiments of the disclosure are not limited by what has been particularly shown and described hereinabove. Rather the scope of the embodiments of the disclosure is defined by the appended claims and equivalents thereof.