I initially asked this question in cryptography but I think it's better suited for this board.

I'm trying to create a simple code just to show that Blahut's theorem works for binary periodic sequences. (it's a theorem that relates the linear complexity of a sequence with the number of nonzero elements of its DFT). My main question is, which n-th root of unity do I have to use in the DFT?

The DFT I have defined is

$B_k=\sum_{j=0}^{n-1}b_j e^{i 2 \pi k j / n}$

Which is just the usual DFT (i is the imaginary unit). As I explain below, I'm not getting the expected result so $e^{i 2 \pi k j / n}$ are probably not the correct roots to choose.

For example:


Is the main period of the periodic sequence that I want to analyze. This sequence has linear complexity 3 by BMA, so by Blahut's theorem I would expect 3 not null elements in the frequency domain (so, 4 null elements). I'm not getting any null elements in $B^n$ so obviously I'm doing something wrong.

Thanks, any help is appreciated.

  • $\begingroup$ @DavidReed yes it needs to be a primitive root of unity, the problem is that I'm not as well versed in general math to know which is the n-th primitive root of unity in the field of binary sequences of length n (as far as I know, that's just the Galois Field of order $2^n$). I chose that form for the root of unity to try something but it's probably wrong. $\endgroup$ – Diego Dec 4 '17 at 1:14
  • $\begingroup$ @DavidReed as far as I understand, null element should be zero. If you want to check by yourself, all the math is explained in L Massey, T Schaub - Linear complexity in coding theory $\endgroup$ – Diego Dec 4 '17 at 1:18
  • $\begingroup$ @DavidReed by the way, k should range from 0 to n-1, just like j. As I said, that's what I understood from the original paper but I might be mistaken... $\endgroup$ – Diego Dec 4 '17 at 1:19
  • $\begingroup$ A root of unity in the field you are talking about is going to be a binary sequence, is that you're understanding? It wouldn't be a complex exponential. $\endgroup$ – David Reed Dec 4 '17 at 1:32
  • $\begingroup$ @DavidReed Yes I thought about a binary sequence but I don't know how to implement it. I'm reading ways to do it... $\endgroup$ – Diego Dec 4 '17 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.