フィボナッチ多項式とその応用

概要

論文の詳細を見る
We introduce a sequence of Fibonacci polynomials {F_n(x)} over GF(2) as an analogue of well-known sequence of Fibonacci numbers. It is chraraterized by the property that all the patial quotients of the regular continued fraction expansion of F_n(x)/F_<n+1>(x) are of degree one. Two applications of Fibonacci polynomials are discussed. One is the fast generation of low-discrepancy point set, which is useful as a set of sampling points for multiple integration. Our point set is optimal with respect to a figure of merit for the two dimensional discrepancy. Another application is the built-in self-test for VLSI. Considerable interest has recently developed in the cellular automata as a generator of random test patterns as well as a compressor of the outputs of VLSFs under test. Methods proposed so far for designing the cellular automata for this purpose are rather time-consuming because they need trial and error. We propose a direct method for design using a purely theoretical result of Mesirov and Sweet on continued fraction expansions of rational expressions over GF(2).
1994-03-15