one of the most recent is detroit underground du-rdt, the one i have is instead The Harvestman\IME Zorlon Cannon mk2.Īs you can see the concept might be used for a wide range of applications, from pseudo random cv sequences to pseudo random gates to pitched noise and tonal sound generation. perhaps the most well known is the turing machine. The net result is that you can combine two efficient but insecure generators to create a new generator that is efficient and secure.There are modules that already implement this technique in the eurorack realm. The two generators can both be LFSRs, but the combined generator is nonlinear because the sampling mechanism is nonlinear. The idea of shrinking generators is use one random number generator to sample another generator. LFSRs make very efficient random number generators, but they’re not appropriate for cryptography because their linear structure makes them vulnerable to attack. If you associate the linear coefficients with polynomial coefficient (with a sign change, as noted in the previous post) then the LFSR sequence is a De Bruijn sequence if and only if the polynomial is a primitive polynomial of degree n.Ī few months ago I wrote about LFSRs in the context of random number generation. For some choices of linear coefficients the output is a De Bruijn sequence, but not for others. So technically a LFSR is an “nearly always linear feedback shift register.” It’s linear for 2 n – 2 inputs and nonlinear for 2 special inputs.Ī LFSR is more general than a binary De Bruijn sequence. The algorithm couldn’t be entirely linear because it would get stuck It would produce nothing but zeros forevermore once it encountered an input sequence of all zeros. Note that the LFSR algorithm is a linear operator over the field GF(2), except for the special cases in steps 1 and 2. Hence the name “linear feedback shift register” sequence. We then shift the register content over by one and add the new output on the end. We take the feedback from the previous outputs and compute a linear combination. That is, we operate on the latest n symbols, saving them to registers. Note that the last line says to return a linear combination of the previous symbols. Otherwise return c 1 x 1 + c 2 x 2 + … c n x n mod k.Here’s the algorithm from the previous post: If we set k = 2, the generating algorithm is an example of a linear feedback shift register (LFSR) sequence. As noted near the end of the post, the case k = 2 is especially important in application, i.e.
These are optimal sequences that contain every possible consecutive sequence of n symbols from an alphabet of size k. The previous post looked at an algorithm for generating De Bruijn sequences B( k, n) where k is a prime number.
0 kommentar(er)
