1
$\begingroup$

I'm trying to construct a binary sequence of length $2^n$. This sequence will be converted to a square signal of $\pm 1$, where 0 produces $-1$ and 1 produces $1$. I want the resultant signal to be as spectrally flat as possible, minimizing the $L^2$ norm of the continuous Fourier transform. Is there a reason to believe that this problem is hard, such as by equivalence to a known mathematical problem like subset sum, or is there a solution I'm overlooking?

Things I've checked are Raskar's sequence, which uses exhaustive search, URA/MURA, and Levin 2007. The best method I've considered is genetic optimization, but I'd prefer an optimal solution over a searched one.

The motivation is that I have a reverb with Dirac delta spikes in pre-defined locations, and must choose a sign $\pm 1$ for each spike. Setting all signs to $-1$ produces a pitch determined by the locations, and setting signs randomly eliminates the pitch. This doesn't quite match the problem statement given above, but I think a solution for the above will lead to a solution for this.

$\endgroup$
12
  • $\begingroup$ en.wikipedia.org/wiki/Maximum_length_sequence $\endgroup$
    – datageist
    Jan 30, 2021 at 0:57
  • $\begingroup$ @datageist That seems to be no better than white noise (which is the random choices I made). In Page 8 of arxiv.org/ftp/arxiv/papers/1509/1509.01220.pdf, white noise is graphed; its performance is worse than Raskar's sequence. $\endgroup$ Jan 30, 2021 at 1:01
  • $\begingroup$ So are you trying to do audio reconstruction of some kind? $\endgroup$
    – datageist
    Jan 30, 2021 at 2:05
  • $\begingroup$ I am building the reverb myself, so I control the reverb's coefficients and topology. $\endgroup$ Jan 30, 2021 at 2:17
  • 1
    $\begingroup$ To be specially flat you would use a series of impulses; rectangular pulses with pseudo random noise pattern will have a Sinc shape in frequency. $\endgroup$ Jan 30, 2021 at 4:18

1 Answer 1

0
$\begingroup$

Golay Complementary Sequences are spectrally flat. See https://www.isg.rhul.ac.uk/~kp/golaysurvey.pdf or https://www.sfu.ca/~jed/Papers/Davis%20Jedwab.%20Golay%20Reed-Muller.%201999.pdf

The DTFT magnitude spectrums of Golay complementary sequences are flat, the maximum to mean value squared magnitude ratios are upper bounded by $2$ $\left( 3 dB \right)$, for any length $2^{n}$. The construction is easy.

Starting from two sequences $A_{1} = \left[ 1 ~ 1 \right]$, $B_{1} = \left[ 1 ~ -1 \right]$. Let $A_{2} = \left[ A_{1}, B_{1} \right] = \left[ 1 ~ 1 ~ 1 ~ -1 \right]$, $B_{2} = \left[ A_{1}, -B_{1} \right] = \left[ 1 ~ 1 ~ -1 ~ 1 \right]$. Continue to get longer length $2^{n}$ sequences:

$A_{n} = \left[ A_{n-1}, B_{n-1} \right]$, $B_{n} = \left[ A_{n-1}, -B_{n-1} \right]$. Use either $A_{n}$ or $B_{n}$.

There are ways to construct $0.5 \left( n! \right) 2^{\left( n + 1 \right)}$ different length $2^{n}$, {1, -1}-valued Golay complementary sequences (see Davis and Jedwab's paper), but the spectrally flat property is valid for all Golay complementary sequences, so they are all equally good.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.