Root counting, the DFT and the linear complexity of nonlinear filtering (Q1265231)

The linear complexity of a binary sequence can be analysed with one of the two methods: the root counting or the method based on the Discrete Fourier Transform (DFT) and Blahut's Theorem. The main goal of the paper is to show that both approaches are equivalent: any analysis based on root counting can be converted into a DFT-type analysis and vice-versa. It also illustrates the utility of the DFT approach to linear complexity by applying it to the problem of nonlinear filtering of binary \(m\)-sequences.