Bio

Sung Min is a rising sophomore studying mathematics and economics at Cornell University. He conducted some research on artificial muscle and balloon physics in high school. Some of his interests include number theory, cellular automata and machine learning. He is planning to pursue a master’s degree in related fields after he graduates. In his free time, he likes playing basketball, soccer and tennis.

Computational Essay

Approximations to the PrimePi Function »

Project: Nonlinear Feedback Shift Registers (NFSRs)

Goal of the project:

Linear feedback shift registers (LFSRs) have long been used to produce random sequences/numbers for various technologies such as USB, Wi-Fi and 3G networks. In fact, it is estimated that in applications, the algorithm for LFSRs has been run more than an octillion times. However, there have been few studies on nonlinear feedback shift registers. The main goal of my project was to find a combination of taps and nonlinear functions that produces a random sequence for a feedback shift register (i.e. the sequence passes randomness tests).

Summary of work:

Throughout the Summer School, I have formulated functions to test whether certain combinations of tap positions and nonlinear functions produce the sequence of maximal length, which is length 2ⁿ–1 (n is the length of the shift register). I tested all NFSRs with 2 taps and 3 taps for n<16, and all NFSRs with 4 taps for n<10. (Some notable nonlinear feedback functions were further tested with a bigger length.) I then ran several statistical randomness tests, such as the equidistribution test, the serial test and the poker test, to identify combinations that produce random sequences. I also made some analyses of the tap positions and nonlinear functions that produce long random sequences.

Results and future work:

For nonlinear shift registers with 3 taps and of length n smaller than 16, there were 8 cases in which the sequence passed all randomness tests. Compared to the sequences produced by LFSRs, these sequences seem to produce fairly nice random numbers. In addition, I could observe four big features for the settings of NFSRs (tap positions and nonlinear functions) that produced sequences of maximal length. First, tap₁ was always included, no matter the number of taps nor the length of shift register. Second, the cases seem to decrease as the length of the shift registers increased. Third, the feedback function seems to have the shape f(tap₂,…, tap_k) + tap₁ (e.g. f(tap₂, tap₃, tap₄) + tap₁ for 4-tap NFSRs), meaning that tap₁ was independent from the nonlinear part of the function. Fourth, for the cases of 3-tap NFSRs, the two most common nonlinear functions were x+y+z+xy and 1+xy+z, which are rule 30 and complement of rule 30 (rule 135) when translated into the rule numbering system of elementary cellular automata. We say that these two functions appear as a pair because, for a given choice of tap positions and length n, each function produces a sequence of maximal length if and only if the other function produces a sequence of maximal length.

In future work, the 4-tap NFSRs should be tested for bigger shift registers, and NFSRs with more taps should be tested to figure out whether the nonlinear feedback function’s shape f(tap₂,…, tap_k) + tap₁ can be generalized for all positive integers k bigger than 2. There should also be an analysis of pair-appearing functions for 4-tap NFSRs.