Signals and Systems · Discrete-time convolution

#14 Shift and add; flip and slide

Compute all seven output samples of a linear convolution by scaled shifted copies and by overlap products.

Question

Original final-video reference for linear discrete-time convolution. — Original-video reference. Both input arrays start at index zero. In the shift-and-add graph, red is minus h[n], green is h[n−2], purple is 2h[n−3], and the lower cyan row is the completed output. The flip-and-slide reference shows the final input and output after the moving row has been cleared. A dot denotes summation of aligned products, not a single pointwise multiplication.

Use real-valued sequences x[0..3]=[−1,0,1,2] and h[0..3]=[1,1,−1,1], with zero values outside those ranges. This is linear convolution, with seven output positions indexed zero through six. M and N denote the lengths of the listed arrays, including interior zeros; M+N−1 is the full output array length, not a count of nonzero samples. For finite nonzero supports with nonzero endpoints, the first and last output indices are the sums of the respective input endpoints. Fix output index n while summing over integer k. Flipping means reflection of the time index k to negative k, leaving amplitudes unchanged; then shift by n to form h[n−k]. The dot-product description here sums ordinary products of real entries; do not add complex conjugation to the convolution formula. In an LTI system interpretation, h is the impulse response and this gives the zero-state output. The worked example uses the existing revised narration with x[3]=2.

Written solution and narration transcript(shows the full solution)

Below are all the lines written in the notebook together with the full narration transcript.

1. DT convolution
Original-video reference. Both input arrays start at index zero. In the shift-and-add graph, red is minus h[n], green is h[n−2], purple is 2h[n−3], and the lower cyan row is the completed output. The flip-and-slide reference shows the final input and output after the moving row has been cleared. A dot denotes summation of aligned products, not a single pointwise multiplication.
Discrete-time convolution describes the zero-state action of an LTI system.
Linear convolution:
$\displaystyle y\left[n\right]=\sum _{k=-\infty }^{\infty } x\left[k\right] h\left[n-k\right]$
Full output array length:
$\displaystyle L=M+N-1$
Compute a finite example with both input arrays starting at zero.
Narration transcript
Today we learn discrete-time convolution — the fundamental operation that describes how LTI systems process signals. Given two discrete-time signals x of n and h of n, their convolution y of n is defined as the sum from k equals negative infinity to infinity of x of k times h of n minus k. For finite-length signals, if x has M samples and h has N samples, the output y will have M plus N minus one samples. Let's see how to compute this with a concrete example.
2. Shift and add
Original-video reference. Both input arrays start at index zero. In the shift-and-add graph, red is minus h[n], green is h[n−2], purple is 2h[n−3], and the lower cyan row is the completed output. The flip-and-slide reference shows the final input and output after the moving row has been cleared. A dot denotes summation of aligned products, not a single pointwise multiplication.
Method one: shift and add.
For this input starting at zero:
$\displaystyle y\left[n\right]=x\left[0\right]h\left[n\right]+x\left[1\right]h\left[n-1\right]+x\left[2\right]h\left[n-2\right]+x\left[3\right]h\left[n-3\right]$
Each term is a scaled and shifted copy of the impulse response.
Scale by an input sample, shift by its index, and add the copies.
This construction follows directly from the convolution sum.
Narration transcript
Method one is called shift-and-add. The idea is to express y of n as x of zero times h of n, plus x of one times h of n minus one, plus x of two times h of n minus two, and so on. Each term is a scaled, shifted copy of h. You scale h by each input sample x of k, shift it to position k, and add all the copies together. This method directly follows from the convolution formula.
3. Build the convolution
Original-video reference. Both input arrays start at index zero. In the shift-and-add graph, red is minus h[n], green is h[n−2], purple is 2h[n−3], and the lower cyan row is the completed output. The flip-and-slide reference shows the final input and output after the moving row has been cleared. A dot denotes summation of aligned products, not a single pointwise multiplication.
Build the output one component at a time.
Arrays indexed zero through three:
$\displaystyle x=\left[-1,0,1,2\right], h=\left[1,1,-1,1\right]$
First input sample:
$\displaystyle x\left[0\right]=-1$
First component, indices zero through three:
$\displaystyle -h=\left[-1,-1,1,-1\right]$
The first component is red in the original graph.
Next input sample:
$\displaystyle x\left[1\right]=0$
A zero sample contributes a zero sequence.
Skip the zero contribution.
Third input sample:
$\displaystyle x\left[2\right]=1$
Shift right by two: h[n−2]
The green component has values one, one, negative one, one at indices two through five.
Last input sample:
$\displaystyle x\left[3\right]=2$
Shift right by three and scale by two: 2h[n−3]
The purple component has values two, two, negative two, two at indices three through six.
Add the three nonzero components at each output index.
At the first index:
$\displaystyle y\left[0\right]=-1$
At the next index:
$\displaystyle y\left[1\right]=-1$
At the third index:
$\displaystyle y\left[2\right]=2$
Complete output, indices zero through six:
$\displaystyle y=\left[-1,-1,2,2,1,-1,2\right]$
Narration transcript
Let's apply shift-and-add step by step. Our signals are x of n equals minus one, zero, one, two, and h of n equals one, one, minus one, one. Starting with x of zero equals minus one. We scale h by minus one to get minus h of n: the values minus one, minus one, one, minus one at positions zero through three. This first component is shown in red. Next, x of one equals zero. Zero times anything is zero, so this sample contributes nothing to the output. We skip it entirely. Now x of two equals one. We shift h right by two positions to get h of n minus two: one, one, minus one, one at positions two through five. This component is shown in green. Finally, x of three equals two. We shift h right by three and scale by two to get two h of n minus three: two, two, minus two, two at positions three through six. This component is shown in purple. Now we add all components at each output index. At n equals zero, only the red contributes: minus one. At n equals one, minus one. At n equals two, we get two. Continuing through n equals six, the complete output is y of n equals minus one, minus one, two, two, one, minus one, two — seven values, exactly M plus N minus one.
4. Flip and slide
Original-video reference. Both input arrays start at index zero. In the shift-and-add graph, red is minus h[n], green is h[n−2], purple is 2h[n−3], and the lower cyan row is the completed output. The flip-and-slide reference shows the final input and output after the moving row has been cleared. A dot denotes summation of aligned products, not a single pointwise multiplication.
Method two: flip and slide, then sum aligned products.
Reverse the time index without negating amplitudes: h[−k]
At fixed output index n, shift the reversed sequence: h[n−k]
Multiply overlapping entries and sum:
$\displaystyle y\left[n\right]=\sum _{k=-\infty }^{\infty } x\left[k\right]h\left[n-k\right]$
For real arrays, this sum is the dot product of the aligned vectors.
Move one output position at a time and recompute the sum.
Narration transcript
Method two is called flip-and-slide, also known as the dot product method. First, flip h of k to get h of negative k — this reverses the signal around the origin. Then for each output index n, shift the flipped signal to get h of n minus k. Multiply x of k and h of n minus k element by element where they overlap, and sum the products. This sum is the dot product of x and the shifted, flipped h. Slide h one position at a time across x, computing the dot product at each step.
5. Check each output sample
Original-video reference. Both input arrays start at index zero. In the shift-and-add graph, red is minus h[n], green is h[n−2], purple is 2h[n−3], and the lower cyan row is the completed output. The flip-and-slide reference shows the final input and output after the moving row has been cleared. A dot denotes summation of aligned products, not a single pointwise multiplication.
Verify every output sample using overlap products.
Fixed input, indices zero through three:
$\displaystyle x=\left[-1,0,1,2\right]$
At output index zero, the reversed response occupies indices negative three through zero.
Only the input sample at index zero overlaps.
First output:
$\displaystyle y\left[0\right]=\left(-1\right)\left(1\right)=-1$
Advance the reversed response one position to the right.
At output index one, input indices zero and one overlap.
Two products:
$\displaystyle \left(-1\right)\left(1\right)+\left(0\right)\left(1\right)=-1$
Second output:
$\displaystyle y\left[1\right]=-1$
At output index two, three positions overlap.
Three products:
$\displaystyle \left(-1\right)\left(-1\right)+\left(0\right)\left(1\right)+\left(1\right)\left(1\right)=2$
Third output:
$\displaystyle y\left[2\right]=2$
At output index three, all four positions overlap.
Four products:
$\displaystyle \left(-1\right)\left(1\right)+\left(0\right)\left(-1\right)+\left(1\right)\left(1\right)+\left(2\right)\left(1\right)=2$
Sum of those products:
$\displaystyle -1+0+1+2=2$
Fourth output:
$\displaystyle y\left[3\right]=2$
At output index four, the first input sample has left the overlap.
Remaining products:
$\displaystyle \left(0\right)\left(1\right)+\left(1\right)\left(-1\right)+\left(2\right)\left(1\right)=1$
Sum of those products:
$\displaystyle 0-1+2=1$
Fifth output:
$\displaystyle y\left[4\right]=1$
At output index five:
$\displaystyle \left(1\right)\left(1\right)+\left(2\right)\left(-1\right)=-1$
Sum of those products:
$\displaystyle 1-2=-1$
Sixth output:
$\displaystyle y\left[5\right]=-1$
At output index six, only input index three overlaps:
$\displaystyle \left(2\right)\left(1\right)=2$
Last output:
$\displaystyle y\left[6\right]=2$
Both methods give the array:
$\displaystyle y=\left[-1,-1,2,2,1,-1,2\right]$
Narration transcript
Now let's verify using flip-and-slide. x of k stays fixed on the top row: minus one at k equals zero, zero at one, one at two, and two at three. For n equals zero, h of negative k sits at k equals zero, minus one, minus two, minus three. Only k equals zero overlaps. Minus one times one gives y of zero equals minus one. For n equals one, h slides right by one. Positions k equals zero and one overlap. Minus one times one plus zero times one. y of one equals minus one. For n equals two, three positions overlap. Minus one times minus one is plus one, zero times one is zero, one times one is one. Adding up: y of two equals two. For n equals three, all four positions overlap. The products are minus one times one, zero times minus one, one times one, and two times one. The sum is minus one plus zero plus one plus two. y of three equals two. For n equals four, x of zero leaves the window. The remaining products are zero times one, one times minus one, and two times one. That's zero minus one plus two. y of four equals one. For n equals five, only two positions overlap: one times one and two times minus one. That's one minus two. y of five equals minus one. For n equals six, only k equals three overlaps: two times one. y of six equals two. Same result as method one: y of n equals minus one, minus one, two, two, one, minus one, two.
6. Compare methods
Original-video reference. Both input arrays start at index zero. In the shift-and-add graph, red is minus h[n], green is h[n−2], purple is 2h[n−3], and the lower cyan row is the completed output. The flip-and-slide reference shows the final input and output after the moving row has been cleared. A dot denotes summation of aligned products, not a single pointwise multiplication.
Compare the two constructions of the same convolution.
Shift and add creates one scaled shifted response for each input sample.
This shows how each input sample contributes to the full output.
Flip and slide calculates one output value at a time.
The overlap calculation is systematic for hand computation.
Full length and starting index:
$\displaystyle L=M+N-1, n_{y}=n_{x}+n_{h}$
Narration transcript
Let's compare the two methods. Shift-and-add works signal by signal: take each sample of x, create a scaled shifted copy of h, and add them all up. It's intuitive for understanding what convolution means physically. Flip-and-slide works sample by sample: for each output position n, compute one dot product. It's more systematic and often preferred for hand calculations. The key properties to remember: the output length is always M plus N minus one, and the starting index of y equals the sum of the starting indices of x and h.
7. Summary
Original-video reference. Both input arrays start at index zero. In the shift-and-add graph, red is minus h[n], green is h[n−2], purple is 2h[n−3], and the lower cyan row is the completed output. The flip-and-slide reference shows the final input and output after the moving row has been cleared. A dot denotes summation of aligned products, not a single pointwise multiplication.
Convolution sum:
$\displaystyle y\left[n\right]=\sum _{k=-\infty }^{\infty } x\left[k\right]h\left[n-k\right]$
The same finite example was computed in two ways.
Shift and add scales and shifts the response for each input sample.
Flip and slide sums products as the reversed response moves across the input.
Both methods produce identical output.
For this full linear convolution:
$\displaystyle L=4+4-1=7$
Next: convolution properties and continuous-time convolution.
Narration transcript
Today we defined discrete-time convolution: y of n equals the sum of x of k times h of n minus k. We computed the same example two ways. Shift-and-add scales and shifts h for each input sample. Flip-and-slide flips h and computes dot products as it slides across x. Both yield the same result. The output has M plus N minus one samples. In the next lesson, we'll explore convolution properties like commutativity and distributivity, and introduce continuous-time convolution.