Linear and circular convolution, the two-point DFT butterfly, and block filtering: 22-Elec-B1 Digital Signal Processing, May 2013, Q1

Question 1: Linear and circular convolution, the two-point DFT butterfly, and block filtering (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Two real, finite-length sequences, $u[n] = \{a, b, c\}$ supported on $n = 0,1,2$ (length $N_u = 3$) and $v[n] = \{0, 1\}$ supported on $n = 0,1$ (length $N_v = 2$). Note that $v[0] = 0$ and $v[1] = 1$, so $v[n] = \delta[n-1]$ exactly.

Find. The linear convolution, the 3-point circular convolution, the internal structure of the 2-point DFT "box" and of its inverse, a DFT-based route to the linear convolution, and the smallest DFT length that block filtering permits.

Approach. Evaluate the two convolution sums directly, then recognise that the length-2 DFT is a single radix-2 butterfly whose inverse is the same butterfly followed by a scaling of one half, and finish with the overlap-add length condition $L \ge N + L_v - 1$.

Fix the length of the linear convolution. For finite sequences of lengths $N_u$ and $N_v$ the convolution $z_l[n] = \sum_m u[m]\,v[n-m]$ is supported on $0 \le n \le N_u + N_v - 2$, so its length is $$N_z = N_u + N_v - 1 = 3 + 2 - 1 = 4 .$$ Four output samples, $z_l[0] \ldots z_l[3]$, must be reported.
Evaluate the convolution sum (part a). Writing the four sums out term by term, $$\begin{aligned} z_l[0] &= u[0]v[0] = a\cdot 0 = 0,\\ z_l[1] &= u[0]v[1] + u[1]v[0] = a\cdot 1 + b\cdot 0 = a,\\ z_l[2] &= u[1]v[1] + u[2]v[0] = b,\\ z_l[3] &= u[2]v[1] = c . \end{aligned}$$ Hence $$\boxed{\,z_l[n] = \{\,0,\; a,\; b,\; c\,\},\qquad n = 0,1,2,3\,}$$ The result is worth a sanity check: because $v[n] = \delta[n-1]$, convolution with $v$ is a pure one-sample delay, and indeed $z_l[n] = u[n-1]$.
Zero-pad $v[n]$ to three points (part b). A 3-point circular convolution treats both operands as length-3 sequences, so $v[n]$ is padded to $v[n] = \{0, 1, 0\}$ while $u[n]$ is already length 3. The circular convolution is then $$z_c[n] = \sum_{m=0}^{2} u[m]\, v[\langle n-m\rangle_3],$$ where $\langle \cdot \rangle_3$ denotes the index taken modulo 3.
Evaluate the circular sum. Substituting the three shifts, $$\begin{aligned} z_c[0] &= u[0]v[0] + u[1]v[2] + u[2]v[1] = 0 + 0 + c = c,\\ z_c[1] &= u[0]v[1] + u[1]v[0] + u[2]v[2] = a,\\ z_c[2] &= u[0]v[2] + u[1]v[1] + u[2]v[0] = b, \end{aligned}$$ so that $$\boxed{\,z_c[n] = \{\,c,\; a,\; b\,\},\qquad n = 0,1,2\,}$$ This is exactly the time-aliased version of part (a): the length-4 linear result $\{0,a,b,c\}$ wrapped modulo 3 puts $z_l[3] = c$ on top of $z_l[0] = 0$, giving $\{0+c,\,a,\,b\}$. The wrap-around term is the classic circular-convolution error, and it disappears only when the DFT length reaches $N_u + N_v - 1 = 4$.
Build the two-point DFT (part c). With $N = 2$ the twiddle factor is $W_2 = e^{-j2\pi/2} = -1$, so $$X[k] = \sum_{n=0}^{1} x[n]\,W_2^{\,nk} = x[0] + (-1)^{k}\,x[1],$$ which expands to the pair $$\boxed{\,X[0] = x[0] + x[1], \qquad X[1] = x[0] - x[1]\,}$$ No multiplication is needed: the "box" is a single radix-2 butterfly with branch gains $+1, +1, +1, -1$.

Part (c): the "box" is one radix-2 butterfly. Three branches carry gain +1 and the branch from x[1] into X[1] carries -1.

Invert the box with external scaling only (part d). The 2-point inverse DFT is $$x[n] = \frac{1}{2}\sum_{k=0}^{1} X[k]\,W_2^{-nk} = \frac{1}{2}\bigl(X[0] + (-1)^{n} X[1]\bigr),$$ that is $x[0] = \tfrac12 (X[0] + X[1])$ and $x[1] = \tfrac12 (X[0] - X[1])$. The bracketed operations are precisely what the box performs, so $$\boxed{\;\{x[n]\} = \tfrac{1}{2}\,\mathcal{B}\{X[k]\}\;}$$ where $\mathcal{B}$ denotes the box. Drive the box with $\{X[0], X[1]\}$ and multiply each of its two outputs by $\tfrac12$ outside the box, which is exactly the "scalar multiplication external to the box" the question allows.

Part (d): the same box driven by X[k], with the two one-half scalings applied outside it, realises the 2-point IDFT.

Parts (c) and (d) now supply a complete two-point transform pair, and part (e) asks for the length-4 linear convolution to be produced from them.

Choose the block length that a 2-point DFT can support (part e). A DFT of length $L = 2$ can carry an aliasing-free convolution only if the block of input and the filter together fit inside it: $$L \ge N + L_v - 1 \;\Longrightarrow\; 2 \ge N + 2 - 1 \;\Longrightarrow\; N = 1 .$$ So $u[n]$ is cut into single-sample blocks $u_0 = \{a,0\}$, $u_1 = \{b,0\}$, $u_2 = \{c,0\}$, each zero-padded to two points, and $v[n] = \{0,1\}$ is already length 2.
Transform, multiply, and invert each block. The box gives $V[k] = \{v[0]+v[1],\, v[0]-v[1]\} = \{1,\,-1\}$ and, for a block $\{u_i, 0\}$, $U_i[k] = \{u_i,\, u_i\}$. Multiplying point by point, $Y_i[k] = \{u_i,\, -u_i\}$, and the scaled box of part (d) returns $$y_i[0] = \tfrac12\bigl(u_i - u_i\bigr) = 0, \qquad y_i[1] = \tfrac12\bigl(u_i + u_i\bigr) = u_i ,$$ i.e. every block contributes $\{0,\,u_i\}$.
Overlap and add. Block $i$ starts at $n = i$, so the three 2-sample results are laid down at $n = 0..1$, $1..2$ and $2..3$ and summed in their overlap: $$\boxed{\;z_l[n] = \{\,0,\; a,\; b,\; c\,\}\;}$$ identical to the direct answer of part (a), which is the required confirmation that the DFT route is exact.

Part (e): overlap-add with one-sample blocks. Each 2-point DFT / IDFT pair is the box of parts (c) and (d).

Minimum DFT length for block filtering (part f). Both overlap-add and overlap-save realise a linear convolution through a circular one, and the circular convolution of a length-$N$ input block with the length-$L_v$ filter has $N + L_v - 1$ non-zero samples. Aliasing is avoided only when the transform is at least that long: $$L \ge N + L_v - 1 .$$ The block length $N$ can be no smaller than one new input sample, $N \ge 1$, so the smallest transform the method admits is $$\boxed{\,L_{\min} = L_v \quad (\text{attained with } N = 1)\,}$$ For the sequences of this question $L_v = 2$ and therefore $L_{\min} = 2$, which is precisely the size used in part (e).

Check: the printed wording of part (f) defines a right-hand sequence as one "non-zero for $n \le 0$". A right-hand (right-sided) sequence is by the standard definition non-zero only for $n \ge N_0$; the inequality as printed describes a left-sided sequence and is taken here as a typographical slip. The answer is unaffected either way: block filtering only requires that $u[n]$ be one-sided so that it can be segmented, and $L_{\min} = L_v$ in both readings. Note also that $L_{\min}$ is a correctness bound, not an efficiency one: practical designs take $L \gg L_v$, usually a power of two, so that the FFT cost is amortised over many output samples.

Quantity	Result
(a) Linear convolution $z_l[n]$	$\{0,\,a,\,b,\,c\}$, $n=0..3$
(b) 3-point circular convolution $z_c[n]$	$\{c,\,a,\,b\}$, $n=0..2$
(c) The "box"	$X[0]=x[0]+x[1]$, $X[1]=x[0]-x[1]$ (one butterfly, no multipliers)
(d) Inverse using the box	Same box, both outputs scaled by $\tfrac12$ externally
(e) $z_l[n]$ via 2-point DFT/IDFT	Overlap-add, $N=1$ sample per block: $\{0,\,a,\,b,\,c\}$
(f) Minimum DFT length	$L_{\min} = L_v$ (here $2$), from $L \ge N + L_v - 1$, $N \ge 1$

Topic. Linear versus circular convolution, the radix-2 butterfly, and DFT-based block filtering.

Key relations. Linear convolution $z_l[n] = \sum_m u[m] v[n-m]$ with length $N_u + N_v - 1$; $N$-point circular convolution $z_c[n] = \sum_m u[m] v[\langle n-m \rangle_N]$; the aliasing identity $z_c[n] = \sum_r z_l[n + rN]$; the DFT pair $X[k] = \sum_n x[n] W_N^{nk}$, $x[n] = \tfrac{1}{N}\sum_k X[k] W_N^{-nk}$ with $W_N = e^{-j2\pi/N}$; and the block-filtering condition $L \ge N + L_v - 1$.

Why this works. Multiplying DFTs always produces a circular convolution, never a linear one, because the DFT treats both sequences as one period of a periodic extension. The circular result equals the linear result folded back on itself with period $N$, so making $N$ at least as long as the linear result removes every fold and the two coincide. That single observation underlies the entire family of fast-convolution methods: overlap-add cuts the long input into blocks short enough that each block convolution fits inside the chosen transform, then sums the tails that spill into the next block; overlap-save instead discards the aliased head of each block. For $N = 2$ the transform degenerates so far that no twiddle factor other than $\pm 1$ survives, which is why the box is a bare butterfly and why the inverse differs from the forward transform only by the factor $1/N = 1/2$.

Common pitfall. Two errors dominate. The first is to zero-pad only one of the two sequences before a circular convolution; both must be extended to the same length $N$, and it is the value of $N$ (not of the padding) that decides whether wrap-around occurs. The second is to report the circular answer when the question asked for the linear one, or to forget the $1/N$ scaling that distinguishes the inverse DFT from the forward transform.

Source. Oppenheim & Schafer, Discrete-Time Signal Processing, 3rd ed., §8.6–8.7 (circular convolution and the aliasing relation) and §8.9 (block convolution: overlap-add and overlap-save); Proakis & Manolakis, 4th ed., §7.3.

Question 1 of 5: Linear and circular convolution, the two-point DFT butterfly, and block filtering

Question 1: Linear and circular convolution, the two-point DFT butterfly, and block filtering (25 marks)