# the sub-range of circular and linear convolution

circular convolution $x_{_3p}[n]$ = $x_1[n]~\circledast_N ~x_2[n]$

is a period version of the linear convolution $x_{_3p}[n]=x_1[n] * x_2[n]$

The length of $x_1[n]$ and $x_2[n]$ are $L$ ($n\in[0,\ldots,L-1]$) and $P$ ($n\in[0,\ldots,P-1]$) points, respectively.

The minimum value of $N$ that makes $x_{_3p}[n] = x_{_3}[n]$ for $n \in [0,\ldots N-1]$ is when $N\geq L+P-1$, right?

My question is: If $N=L$, what is the sub-range of $[0,\ldots,N-1]$ that $x_{_3p}[n]=x_{_3}[n]$?

• if $N=L$ and $N \ge L+P-1$, that means that $$N-L = 0 \ge P-1$$ and that $P \le 1$. but $P=0$ or negative doesn't make much sense, so that means that $P=1$ for all $N$ samples of $x_{3P}[n]$ to be valid. if $P>1$ then it's the latter portion of $x_{3P}[n]$ for $n \in [P, ... N-1]$ that is valid. Jan 23, 2017 at 6:01

Given an $$L_x$$-point discrete-time sequence $$x[n]$$, nonzero for the range $$0 \leq n < L_x$$, and $$L_y$$-point sequence $$y[n]$$, nonzero for the range $$0 \leq n < L_y$$, their linear convolution $$z[n] = x[n] \star y[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k] ~~~,~~~0\ \leq n < L_z$$

will have $$L_z = L_x + L_y - 1$$ samples.

Also their $$N$$-point circular convolution is defined as: $$\newcommand{\circled}[1]{ \require{enclose} \enclose{circle}{#1} }$$

$$w[n] = x[n] \circled{N} y[n] = \sum_{k \in } x[(k)_N]y[(n-k)_N] ~~~,~~ 0 \leq n < N.$$

which uses modulo-$$N$$ arguments to effectively interpret the sequences as periodic with $$N$$.

Since, most typically, the circular convolution is used to implement a linear convolution, using the DFT property: $$x[n] \circled{N} y[n] \longleftrightarrow X[k]Y[k]$$ where $$X[k]$$ and $$Y[k]$$ are the $$N$$-point DFTs of $$x[n]$$ and $$y[n]$$, then we are interested in the relation between $$z[n]$$ and $$w[n]$$; i.e., what's the range of $$n$$ for which they are the same ?

The answer depends on $$L_z$$ and $$N$$:

• if $$~~ L_z \leq N ~~~$$ then $$w[n] = \begin{cases} { z[n] ~~~,~~~ 0 \leq n < L_z \\ ~0~ ~~~~~,~~~~ L_z \leq n < N }\end{cases}$$

$$\\\\$$

• if $$~~ N < L_z ~~~$$ then $$w[n] = \begin{cases} { \text{aliased} ~~~,~~~ 0 \leq n < L_z-N \\ z[n]~ ~~~,~~~~ L_z-N \leq n < N }\end{cases}$$

$$\\\\$$

In the second case, if $$L_z - N \geq N$$ or $$2N \leq L_z$$ there will be no matching samples between $$w[n]$$ and $$z[n]$$.

The following Matlab stem-plot shows the matching and unmatching samples (forced to zero for clarity of display) between linear and circular convolutions of sequences of length $$L_x = 32$$ and $$L_y=10$$, with modulus $$N=25$$. It also plots the full extended result of the linear convolution $$z[n]$$ of length $$L_z = 41$$ samples.

Since $$N < L_z$$, the first $$L_z-N = 16$$ samples of $$w[n]$$ in the range $$0 \leq n < 16$$ will be aliased, and only the remaining $$N-(L_z-N) = 2N-L_z = 9$$ samples in the range $$16 \leq n < 25$$ will be equal to $$z[n]$$.

Note, the circular convolution just has $$N=25$$ samples only, which is periodically extending. I've set the initial $$16$$ aliased samples of $$w[n]$$ to zero for clarity of display. Also plotted those 16 aliased sample locations on together with the last 16 sample of linear convolution which has a length of $$41$$. Hence the last plotted $$16$$ forced-zeros of the circular convolution actually belong to the first $$16$$ samples of the next period of the periodic result of the circular convolution...

The first $P−1$ points are corrupted by time aliasing, and the points from $n=P−1$ to $n = L − 1$ should be identical to the corresponding points of the linear convolution. Refer to https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-341-discrete-time-signal-processing-fall-2005/lecture-notes/lec16.pdf for details