Maximum-likelihood binary shift-register synthesis from noisy observations

We consider the problem of estimating the feedback coefficients of a linear feedback shift register based on noisy observations. The problem of determining feedback coefficients in the absence of noise is now classical (Massey´s (1969) algorithm). In the current approach to the problem of estimation with noisy observations, the coefficients are endowed with a probabilistic model. Gradient ascent updates to coefficient probabilities are computed using recursions developed by means of the expectation-maximization (EM) algorithm. Reduced-complexity approximations are also developed by reducing the number forward probability terms propagated at each stage. While suffering from a local-maximum problem typical of many maximum-likelihood (ML) procedures, the method does exhibit convergence