Feedback with carry shift registers synthesis with the Euclidean algorithm
Feedback with carry shift registers (FCSR) were introduced by Goresky and Mapper in [3]. They are very similar to classical linear feedback shift registers (LFSR) used in many pseudorandom generators. The main difference is the fact that the elementary additions are not additions modulo 2 but with propagation of carries. The mathematical models for LFSR are equivalently linear recurring sequences over GF (2) or rational series in the set GF (2) [[x(]]). For FCSR, the "good" model is the one of rational 2-adic numbers (cf. [5],[6]). It is well known, that the series generated by a LFSR can be synthesized by either the Berlekamp-Massey algorithm for binary linear recurring sequences or the extended Euclidean algorithm in the set GF (2) [x(]) of binary polynomials (cf. [11], [13]). In [5], Goresky and Mapper give an algorithm for the FCSR synthesis. This algorithm is similar to those of Berlekamp-Massey and is based on De Weger and Mahler's rational approximation theory (cf. [101, [141). In this correspondence, we prove that it is possible to synthesize the FCSR with the extended Euclidean algorithm in the ring Z of integers. This algorithm is clearly equivalent to the previous one, however, it is simpler to understand, to implement, and to prove. Our algorithm is still valid in the case of g-adic integers where g is a positive integer. We also give a near-adaptative version of this algorithm.
feedback shift registers pseudorandom generators rational approximation 2-adic expansion