linear convolution toeplitz matrix vs circular convolution toeplitz matrix

Question

I have an issue in understanding the difference between building the Toeplitz matrix when the convolution is linear and when it's circular. As I know that Toeplitz matrix $H$ can be built as following

H = toeplitz(h;zeros(N-L,1),h(1), zeros(1,N-1));

where h is the channel and L is the length of the channel, and N is the total length of symbol convoluted with the channel.

My question, if the convolution with the channel is circular, will the Toeplitz matrix still be built in the same way?

Answer 1

They are in general different. For two signals of lengths $N$ and $M$, linear and circular convolution are equivalent if the output is specified to be of length $N + M - 1$ with the appropriate padding. Convolution via the DFT is inherently circular, which is why padding must be done before the inverse DFT to yield the linear convolution. So, this is a special case where they are the same.

If your goal is to always yield linear convolution, then don't worry about forming a circular Toeplitz matrix since the result will be the same when using the regular Toeplitz and is simpler to do so.

Below is some sample code and output where we form regular and circular Toeplitz matrices with a specified output of length $N + M - 1$:

%% Toeplitz Convolution

x = [1 8 3 2 5];
h = [3 4 1];

% Form the row and column vectors for the Toeplitz matrix
r = [h zeros(1, length(x) - 1)];
c = [h(1) zeros(1, length(x) - 1)];

% Toeplitz matrix
hConv = toeplitz(c,r)

% Compare the two types of convolutions
y1 = x*hConv
y2 = conv(x, h)

hConv =

 3     4     1     0     0     0     0
 0     3     4     1     0     0     0
 0     0     3     4     1     0     0
 0     0     0     3     4     1     0
 0     0     0     0     3     4     1


y1 =

 3    28    42    26    26    22     5


y2 =

 3    28    42    26    26    22     5

%% Toeplitz Circular Convolution

% Convolution length
n = length(x) + length(h) - 1;
numElementDiff = n - length(h);

% Set up the circular Toeplitz matrix
c = [h(1) fliplr([h(2:end) zeros(1, numElementDiff)])];
hConvCirc = toeplitz(c, [h zeros(1, numElementDiff)])

% Compare the two types of convolutions
y1 = [x zeros(1, length(c) - length(x))]*hConvCirc
y2 = cconv(x, h, n)

hConvCirc =

     3     4     1     0     0     0     0
     0     3     4     1     0     0     0
     0     0     3     4     1     0     0
     0     0     0     3     4     1     0
     0     0     0     0     3     4     1
     1     0     0     0     0     3     4
     4     1     0     0     0     0     3


y1 =

     3    28    42    26    26    22     5


y2 =

    3.0000   28.0000   42.0000   26.0000   26.0000   22.0000    5.0000

Here we're testing three things:

1. Linear convolution conv() is equivalent to performing the matrix multiplication with the appropriate Toeplitz matrix.
2. Circular convolution cconv() is equivalent to performing the matrix multiplication with the appropriate circular Toeplitz matrix.
3. Output length is specified as $N + M - 1$, so we see that linear and circular convolution are equivalent.

If you are going to perform circular convolution of varying sizes, then you must form the Toeplitz matrix differently. This usually involves some type of padding with the matrix entries themselves or the signal(s) being operated on. Mathworks has a good summary of Toeplitz matrices here and linear vs circular convolution here.