PROBLEM STATEMENT
A basic operation of a DSP (Digital Signal Processor) chip is to implement a
filter. A digital filter of size N is a software program run on the DSP chip
that takes the present input and N-1 of the most recent inputs, and outputs a
number based on the filter coefficients. The inputs are stored in a buffer of
size N in memory so the previous values can be used in the next calculations.
At each time interval the entire buffer is shifted and the new input is shifted
in, this allows for the DSP operation to take the least amount of memory.
After the calculation is completed the value is outputted. This has the effect
of filtering certain frequency components from the input signal based on the
filter coefficients.
Determining the frequency components to be filtered out is done by defining a
int[] of N coefficients to use as a filter. Time starts at zero. Before the
filter begins the buffer contains all zeros. Then at t=0 the first sample is
shifted into the buffer and multiplied by the first filter coefficient and
outputted. Then at t=1 the second sample shifted into the buffer and then is
multiplied by the first filter and that is added to the second filter
coefficient value times the first sample value, which is in the second place in
the buffer. The general equation is:
The output at time t is SUM of filter(i)*sample(t - i) as i goes from 0 to N - 1.
Implement an algorithm that takes the sample and the filter and outputs the
value at time t. Note t = 0 means first filter times the first sample.
DEFINITION
Class: DigFilter
Method: feedFwd
Parameters: int[], int[], int
Returns: int
Method signature (be sure your method is public): int feedFwd(int[] samples,
int[] filter, int time);
NOTES
- Both arrays are zero-indexed, thus time starts at zero.
- If the value desired is outside of the bounds of the samples array the value
is zero.
TopCoder will ensure the validity of all inputs. Inputs are valid if:
- time is an integer between 0 and N+M-2, inclusive. (Where N is the number of
elements in filter and M is the number of elements in samples.)
- samples and filter have between 1 and 50 elements, inclusive.
- Each element of samples and filter is between -100 and 100, inclusive.
EXAMPLES
1)
samples = {1,1,1,1}
filter = {2,3,4,6}
time = 5
note: s denotes the samples array and f denotes the filter array (zero-indexed)
At time = 0: f(0)*s(0) = 2*1 = 2
At time = 1: f(0)*s(1) + f(1)*s(0) = 2*1 + 3*1 = 5
At time = 2: f(0)*s(2) + f(1)*s(1) + f(2)*s(0) = 2*1 + 3*1 + 4*1 = 9
At time = 3: f(0)*s(3) + f(1)*s(2) + f(2)*s(1) + f(3)*s(0) = 2*1 + 3*1 + 4*1 +
6*1 = 15
At time = 4: f(0)*s(4) + f(1)*s(3) + f(2)*s(2) + f(3)*s(1) = 2*0 + 3*1 + 4*1 +
6*1 = 13
At time = 5: f(0)*s(5) + f(1)*s(4) + f(2)*s(3) + f(3)*s(2) = 2*0 + 3*0 + 4*1 +
6*1 = 10
At time = 6: f(0)*s(6) + f(1)*s(5) + f(2)*s(4) + f(3)*s(3) = 2*0 + 3*0 + 4*0 +
6*1 = 6
Returns 10
2)
samples = {1,2,3,4,5,4,3,2,1}
filter = {16,8,4,2,1}
time = 3
Time 0 = 16
Time 1 = 32+8=40
Time 2 = 48+16+4=68
Time 3 = 64+24+8+2=98
At t=3 : f(0)*s(3) + f(1)*s(2) + f(2)*s(1) + f(3)*s(0) = 16*4 + 8*3 + 4*2 + 2*1
= 98
Returns 98
3)
samples = {1,2,3,4,5,4,3,2,1}
filter = {16,8,4,2,1}
time = 10
Returns 11