2
$\begingroup$

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]$?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 23, 2017 at 6:01

2 Answers 2

2
$\begingroup$

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 <N>} 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.

enter image description here

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...

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.