# How to express linear convolution using positive frequencies from channel and symbol DFT vectors?

Sorry for the long question, but I'm struggling to implement something related to this question. Your help would be appreciated.

Background

Notation: In the sequel, the uppercase letters represent frequency domain vectors, while lowercase represent time-domain.

Suppose I have two $N$-length hermitian symmetric DFT vectors $\mathbf{X}$ and $\mathbf{H}$, one representing a symbol and the other a channel through which the symbol goes. Thus, the received symbol in the time domain could be expressed as:

\begin{align} \mathbf{y} = \mathbf{h} * \mathbf{x} \end{align} where $\mathbf{h}$ is the channel impulse response, $\mathbf{x}$ is the IDFT of $\mathbf{X}$ and "$*$" denotes the circular convolution.

This result could also be obtained by:

\begin{align} \mathbf{y} = \tilde{H} \mathbf{x} \end{align} where $\tilde{H}$ is the circulant matrix.

Now, considering only the positive frequencies from both $\mathbf{X}$ and $\mathbf{H}$, that is, $\mathbf{X_+} = \{\mathbf{X(1), X(2), \cdots, X(N/2+1)}\}$ and $\mathbf{H_+} = \{\mathbf{H(1), H(2), \cdots, H(N/2+1)}\}$, it is possible to obtain $\mathbf{y_+}$:

\begin{align} \mathbf{y_+} = \mathbf{h_+} * \mathbf{x_+} \end{align} where $\mathbf{x_+}$ is the IDFT of $\mathbf{X_+}$ and $\mathbf{h_+}$ the IDFT of $\mathbf{H_+}$, both having size $(N/2 + 1)$.

Then, $\mathbf{y}$ could be perfectly reconstruced from $\mathbf{y_+}$, since its IDFT:

\begin{align} \mathbf{Y}_+ = \mathbf{H_+}\cdot\mathbf{X_+} \end{align}

The $\mathbf{y_+}$ vector can also be obtained by making a circulant matrix with the IDFT of $\mathbf{H_+}$, which is a complex vector (because $\mathbf{H_+}$ does not have hermitian symmetry), and multiplying the new circulant matrix by the IDFT of $\mathbf{X_+}$, which is also complex.

Goal:

The ideal received symbol $\mathbf{y}$ is of my interest. However, I also need to know the intersymbol interference occurring when $\mathbf{x}$ is linearly convolved (not circularly) with the channel. I want to know this using $\mathbf{x_+}$ and $\mathbf{h_+}$, since I want to pre-equalize the symbols and using $(N/2 +1)$ vectors requires less operations.

Question

Using the IDFT of the positive frequencies from the original hermitian symmetric DFT vectors as the actual transmit symbols, how could the result of a linear convolution be recovered perfectly? The circular convolution is perfectly recovered.

I currently think it is not possible, because the interference will be different.

Sample code

The circular convolution is perfectly recovered:

N=8;

x = rand(N,1); % Time-domain random symbol
h = rand(N,1); % Time-domain random channel
X = fft(x); % Symbol FFT
H = fft(h); % Channel FFT
Y = H.*X; % Ideal Received Symbol (Ideal because of circular convolution)

% Time-domain complex vectors from positive frequencies
x_plus = ifft(X(1:(N/2 +1)));
h_plus = ifft(H(1:(N/2 +1)));
y_plus = cconv(x_plus,h_plus,(N/2 +1));
Y_plus = fft(y_plus); % FFT of the complex received yields positive freqs.

% Comparison
[Y_plus; flipud(conj(Y_plus(2:end-1)))]
% Should be equal to:
Y


It doesn't work for linear convolution:

N=8;

x = rand(N,1); % Time-domain random symbol
h = rand(N,1); % Time-domain random channel
X = fft(x); % Symbol FFT
H = fft(h); % Channel FFT

y = conv(h,x); % Linear convolution
y = y(1:N); % Remove convolution tail
Y = fft(y); % Ideal Received Symbol (Ideal because of circular convolution)

% Time-domain complex vectors from positive frequencies
x_plus = ifft(X(1:(N/2 +1)));
h_plus = ifft(H(1:(N/2 +1)));
y_plus = conv(x_plus,h_plus); % Linear convolution
y_plus = y_plus(1:(N/2+1)); % Remove convolution tail
Y_plus = fft(y_plus); % FFT of the complex received yields positive freqs.

% Comparison
[Y_plus; flipud(conj(Y_plus(2:end-1)))]
% Should be equal to:
Y


According to wikipedia, the convolution theorem, where convolution is a multiplication in the Fourier domain, only holds for the DFT when using circular convolution. This is because the DFT assumes the signal is periodic, but using the normal MATLAB convolution operator is basically zero-padding the signal vector.

With the convolution tail, it is at the start and end of the output. Remove it using

conv(x,h,'same');


Also this

x_plus = ifft(X(1:(N/2 +1)));


is not the same as IDFT of positive frequencies. What you want is to set the negative frequencies to 0

X(end-2:end) = 0;
H(end-2:end) = 0;


Adjusted code: (note: I haven't figured out the exact expression so there is a lot of literal values in there)

N=8;

x = rand(N,1); % Time-domain random symbol
h = rand(N,1); % Time-domain random channel
X = fft(x); % Symbol FFT
H = fft(h); % Channel FFT

y = cconv(h,x,8); % Circle convolution
%y = y(1:N); % Remove convolution tail
Y = fft(y); % Ideal Received Symbol (Ideal because of circular convolution)

% Time-domain complex vectors from positive frequencies
X(end-2:end) = 0;
H(end-2:end) = 0;
x_plus = ifft(X);
h_plus = ifft(H);
y_plus = cconv(x_plus,h_plus,8); % Circle convolution
%y_plus = y_plus(1:(N/2+1)); % Remove convolution tail
Y_plus = fft(y_plus); % FFT of the complex received yields positive freqs.

% Comparison
[Y_plus(1:5);conj(Y_plus(4:-1:2))]
% Should be equal to:
Y

• That is correct. But your x_plus has size 8. What I ultimately want is to process shorter symbols. Basically, when using the hermitian symmetric symbols, I model exactly the interference that occurs due to the lack of samples to make the linear convolution appear as circular, which is called Intercarrier Interference (ICI). Thus, I am able to pre compensate this effect in the frequency domain. The real goal is to have the same ICI in the frequency domain, but only the positive frequencies to reduce computational complexity. – igorauad May 29 '13 at 18:07
• I think my question is not very clear, but it is hard to explain without going too deep into details. – igorauad May 29 '13 at 18:08
• @igorauad Hermitian symmetric in the spatial domain? Perhaps you can roll your own fft and ifft in MATLAB to process the shorter symbols? – geometrikal May 30 '13 at 12:26

I think already your fist equation is potentially wrong. The output of the channel is given by LINEAR convolution signal and channel impulse response, not by circular convolution. Circular convolution can be used but only if signal and impulse response of the channel are sufficiently small and enough zero padding is applied to avoid wrap-around errors.

Dumping the imaginary part of the spectrum is also problematic. This basically an "analytic" signal (at least if the negative frequencies are set to 0). This typically is a non-causal operation and it becomes very difficult to determine when you will be getting wrap around errors and when you don't. You will almost certainly end up with a non-causal impulse response of the channel.

What exactly are you trying to achieve and why?

• Thank you @Hilmar. What I am doing is a pre-equalizer for Inter carrier interference on a DMT system. I model the received symbol as: $Y_\text{actual} = Y_\text{Ideal} + Y_\text{Isi} + Y_\text{Ici}$. The Ideal part is the result of a circular convolution, which doesn't occur in practice. The intercarrier interference is due to the lack of samples to make the linear convolution appear as circular. – igorauad May 28 '13 at 16:33
• The intersymbol interference (ISI) is the result of some samples from previous symbols interfering in the current symbol due to channel dispersion. This paper is a good reference. – igorauad May 28 '13 at 16:39