# Spectrally flat binary sequence

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.

• en.wikipedia.org/wiki/Maximum_length_sequence Jan 30, 2021 at 0:57
• @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. Jan 30, 2021 at 1:01
• So are you trying to do audio reconstruction of some kind? Jan 30, 2021 at 2:05
• I am building the reverb myself, so I control the reverb's coefficients and topology. Jan 30, 2021 at 2:17
• 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. Jan 30, 2021 at 4:18

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.