Thumbnail
Access Restriction
Subscribed

Author Tezuka, S. ♦ Fushimi, M.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword M-sequences ♦ Feedback shift registers ♦ Linear computation on gf(2) ♦ K-distribution
Abstract A necessary and sufficient condition is established for the generalized feedback shift register (GFSR) sequence introduced by Lewis and Payne to be k-distributed. Based upon the theorem, a theoretical test for k-distributivity is proposed and performed in a reasonable amount of computer time, even for k = 16 and a high degree of resolution (for which statistical tests are impossible because of the astronomical amount of computer time required). For the special class of GFSR generators considered by Arvillias and Maritsas based on the primitive trinomial Dp + Dq + 1 with q = an integral power of 2, it is shown that the sequence is k-distributed if and only if the lengths of all subregisters are at least k. The theorem also leads to a simple and efficient method of initializing the GFSR generator so that the sequence to be generated is k-distributed.
Description Affiliation: Univ. of Tokyo, Tokyo, Japan (Fushimi, M.; Tezuka, S.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 26
Issue Number 7
Page Count 8
Starting Page 516
Ending Page 523


Open content in new tab

   Open content in new tab
Source: ACM Digital Library