2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for your reply.. but regarding the matrix hConvCirc, I think it can also be of size (length(x), length(x)). Is that right? What's the benefits of inserting zeros at the end of x when multiplying with hConvCirc; we can create hConvCirc to be same size of x. Am I right? $\endgroup$ – New_student Oct 8 '20 at 7:32
  • $\begingroup$ @New_student In order to yield the linear convolution from a circular Toeplitz matrix, it must be padded to accommodate the length of the output, which is 7. Because of this, the vector x must also be padded so that the matrix multiplication is valid. You make a good point about it being smaller, and that's exactly why using a circular Toeplitz matrix is wasteful if you just want plain old convolution. $\endgroup$ – Envidia Oct 8 '20 at 17:57

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.