Correlation properties of a general binary combiner with memory (Q1916030)

In this paper correlation properties of a general binary combiner with memory are studied. There are two functions that play important roles: the next state function that computes a next state based on the current state and a time dependent input vector, and the output function that computes an output based upon the current state and the input vector. The inputs are assumed to be mutually independent, balanced uniformly distributed binary random variables. The state space is associated with the memory size. It is proved that a pair of certain mutually correlated functions of at most \(M+1\) successive outputs and inputs exists. The minimum value of the sum of the squares of the correlation coefficients between all nonzero linear functions of \(m\) successive output bits and all linear functions of the corresponding \(m\) successive inputs is minimal if and only if any \(M\) successive output bits are balanced and statistically independent of the corresponding \(M\) successive inputs. The output function must then be balanced for each memory state. For large \(M\) the author developed a method (Linear Sequential Circuit Approximation) that can be used for finding linear functions on outputs and inputs with comperatively large correlation coefficients.