# Convolution of BPSK signal in frequency domain implementation

Here is the simplified version of code which implement convolution of BPSK-signal in frequency domain:

import numpy as np
import matplotlib.pyplot as plt
import scipy.fftpack

# Signal and related data.
pulse_code              = "+++++--++-+-+"
pulse_shift             = len (pulse_code) * 1 + 2; # Feel free to move the signal.
sample_number           = len (pulse_code) * 2 + 4; # Feel free to change it.
time                    = np.linspace (0, sample_number, sample_number);
signal_i                = np.zeros (time.size);
signal_q                = np.zeros (time.size);
filter_i                = np.zeros (time.size);
filter_q                = np.zeros (time.size);

# Create signal.
for i in range (time.size):
if i >= pulse_shift and i < pulse_shift + len (pulse_code):
m = 1. if pulse_code [i - pulse_shift] == '+' else -1.
signal_i [i] = m
signal_q [i] = m

# Create filter.
for i in range (time.size):
if i < len (pulse_code):
m = 1. if pulse_code [i - 1] == '+' else -1.
filter_i [time.size - i - 1] = m
filter_q [time.size - i - 1] = m

# Prepare to next computation.
signal_complex= signal_i + 1j * signal_q
filter_complex= filter_i + 1j * filter_q

# Go to frequency domain.
spectrum_signal         = scipy.fftpack.fft (signal_complex);
spectrum_filter         = scipy.fftpack.fft (filter_complex);
# Convolution.
spectrum_compressed     = spectrum_signal * spectrum_filter
signal_compressed       = scipy.fftpack.ifft (spectrum_compressed)
# Get envelope.
magnitude_compressed    = np.zeros (time.size)
for i in range (signal_compressed.size):
magnitude_compressed [i] = np.sqrt (signal_compressed [i].real ** 2 + signal_compressed [i].imag ** 2)

# Print result.
fig = plt.figure ()

plt.subplot (2, 1, 1)
plt.plot (time,  signal_i);
plt.title ("Input signal.")
plt.xlabel ("Time")
plt.ylabel ("Amplitude")

plt.subplot (2, 1, 2)
plt.plot (time, magnitude_compressed);
plt.title ("Magnitude of compressed signal.")
plt.xlabel ("Time")
plt.ylabel ("Amplitude")

plt.show()


The implementation in my opinion is straightforward and clear, but result which I get is wrong: the maximum sidelobe level is 2 instead of 1, the main lobe is shifted to left and sidelobes aren't symmetric. Can anybody explain where is my error?

UPD

import numpy as np
import matplotlib.pyplot as plt
import scipy.fftpack

# Signal and related data.
# *_t - time domain;
# *_f - frequency domain.
pulse_code      = "+++++--++-+-+"
N               = 64
M               = len (pulse_code)
L               = N - M + 1
sample_number   = L * 1;
time            = np.linspace (0, sample_number, sample_number);
pulse_shift     = len (pulse_code) + 1;
signal_t        = np.zeros (sample_number) + 1j * np.zeros (sample_number)
filter_t        = np.zeros (N) + 1j * np.zeros (N)
chunk_t         = np.zeros (N) + 1j * np.zeros (N)
chunk_f         = np.zeros (N) + 1j * np.zeros (N)
envelope        = np.zeros (sample_number)

# Create signal.
for i in range (sample_number):
if i >= pulse_shift and i < pulse_shift + len (pulse_code):
m = 1. if pulse_code [i - pulse_shift] == '+' else -1.
signal_t [i] = m + 1j * 0

# Create filter as inverse signal with zero padding.
n = len (pulse_code) - 1
for i in range (len (pulse_code) ):
m = 1. if pulse_code [len (pulse_code) - i - 1] == '+' else -1.
filter_t [i] = m + 1j * 0
# and get it's FFT.
filter_f = scipy.fftpack.fft (filter_t)

# Performs convolution using overlap-save method.
for i in range (sample_number / L):
for j in range (M - 1):
chunk_t [j] = chunk_t [L + j]
for j in range (L):
chunk_t [M - 1 + j] = signal_t [i * L + j]
chunk_f = scipy.fftpack.fft (chunk_t)
chunk_f = scipy.fftpack.ifft (chunk_f * filter_f)
for j in range (L):
envelope [i * L + j] = np.abs (chunk_f [M - 1 + j])

# Print result.
fig = plt.figure ()

plt.subplot (2, 1, 1)
plt.plot (time,  signal_t);
plt.title ("Input signal.")
plt.xlabel ("Time")
plt.ylabel ("Amplitude")

plt.subplot (2, 1, 2)
plt.plot (time, envelope);
plt.title ("Magnitude of compressed signal.")
plt.xlabel ("Time")
plt.ylabel ("Amplitude")

plt.show()


• Albeit the constellation {(1,1), (-1,-1)} is also a bpsk constellation, it's a very untypical one, because it's neither normalized nor simply on the coordinate axes. But that's really just a matter of taste and being careful when calculating powers and implementing a detector – Marcus Müller Dec 14 '17 at 9:41
• And also considering that an experienced numpy user would have avoided all your for loops and went for vector operations instead, I'm really not convinced of the straightforwardness :) – Marcus Müller Dec 14 '17 at 9:49

You're doing a circular convolution where you want a linear convolution.

The Wikipedia article in fast convolution / save-add method has a pretty good explanation of the correct algorithm. Basically, you forgot to zero pad, extract the "valid" part and save the "tail" for the next convolution.

Other than that, your filter is questionable at best, and your method of bpsk generation is unusual in its effects on constellation rotation and power. That's no problem per se, but makes your implementation hard to compare to existing convolution and fast convolution implementations.

• Thanks, for your answer! It's very useful. I've read about fast convolution and implement save-overlap method. Now the result is looks better: sidelobes are symmetric, the maximum sidelobe level is 1 as expected, the main lobe is equal the length of the signal 13. Everything OK except one thing: result is shifted (I expect that the main lobe should be placed under left front of the signal). Do you have any idea why I get such result? – Gluttton Dec 14 '17 at 22:33
• Because shift. How should I know what is "wrong" (or whether it's wrong at all) with your new code? I don't know that code. Also, be sure that it's actually wrong. Calculate the group delay of your filter! – Marcus Müller Dec 15 '17 at 7:22