The Relationship Between LBRMS Algorithm And GBMS Algorithm

Sequence linear feedback shift-register synthesis problem, which aims at finding the shortest linear feedback shift-register that can generate a given sequence or the given multiple sequences simultaneously, plays an important role in many fields such as cryptography, coding theory, mathematics, signal processing and control theory. Researchers from many different fields has shown a great deal of interest in the problem and developed many algorithms to this problem. Therefore the research to find new algorithms and study the interrelationship among those algorithms are still hot topics in these fields , which are of great theoretical and practical significance.In this dissertation, our research is founded on the algorithm proposed by Wang Liping, which is called Lattice Basis Reduction Multi-sequence Synthesis algorithm (LBRMS). Introducing onr work in details as follows:(1) On the basis of the existed LBRSS algorithm, it is shown that if we modify the LBRSS algorithm through a simple refinement that makes the degree of the polynomials generated at each reduction step increase strictly, a refined LBRSS algorithm is deduced, which is equivalent to the GBSS algorithm.(2) We first made a reasonable transmutation with the polynomial expression of the GBMS algorithm, and got a new iterative vector-expression GBMS algorithm which is proved to be a particular form of the LBRMS algorithm. We got the conclusion that the LBRSS algorithm is equivalent to the GBSS algorithm when the single-sequence problem is concered.