2

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

Matt L.
  • 89,963
  • 9
  • 79
  • 179
Leon
  • 21
  • 1
  • 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. ā€“ robert bristow-johnson Jan 23 '17 at 06:01

2 Answers2

2

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

Fat32
  • 28,152
  • 3
  • 24
  • 50
0

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

Husrev
  • 67
  • 5