Berlekamp Massey and DFT

Question

I was looking into the Berlekamp Massey algortihm, for LFSR, over GF(2) wondering if there was any DFT(alternately FFT), for the above scheme. Also, is there any generalization to Fn, ie, start with GF2, and if there exists a DFT for the same, and to extend the the same for a Field over n. To be specific I may be given a sequence 0,1,1,0,1, and to find the min poly using BM, and DFT or FFT.

Answer 1

The book Theory and Practice of Error-Control Codes by R. E. Blahut (Addison-Wesley, 1983) and its second edition Algebraic Codes for Data Transmission (Cambridge University Press, 2002) have extensive discussions about finite-field Fourier transforms and their application in working with the Berlekamp-Massey algorithm. Since the Berlekamp-Massey calculations are additions of polynomials (that is, addition of vectors whose entries are the coefficients of the polynomials), and since Fourier transforms are linear transformations from $\mathbb F^n$ to $\mathbb F^n$, the additions can be carried out in either domain. Thus the books talk about implementing the Berlekamp-Massey algorithm in the time domain or in the frequency domain, etc. which seems exactly what you are looking for.

To answer the questton you ask in your comment, the computation of the syndrome for BCH codes is effectively computing, in part, the finite-field Fourier transform of the received sequence. Applying the Berlekamp-Massey algorithm to the syndrome yields the error-locator polynomial (and the error-evaluator polynomial) for the received sequence. So the calculations do indeed use DFTs (and even FFTs if convenient). As Blahut's books point out, these ideas extend to the complex field as well.