The linear complexity (LC) of a sequence is the size in bits of the shortest linear feedback shift register (LFSR) which can produce that sequence. The measure therefore speaks to the difficulty of generating -- and perhaps analyzing -- a particular sequence.
Randomness can be seen as the size of the smallest program to produce a given sequence. But linear complexity is the size of a LFSR "processor" to produce a sequence, and there is an algorithm (Berlekamp-Massey) to measure the LC. So the resulting LC value might be used to measure one view of randomness.
Massey, J. 1969. Shift-Register Synthesis and BCH Decoding. IEEE Transactions on Information Theory. IT-15(1): 122-127.
"Abstract -- It is shown in this paper that the iterative algorithm introduced by Berlekamp for decoding BCH codes actually provides a general solution to the problem of synthesizing the shortest linear feedback shift register capable of generating the prescribed finite sequence of digits." "The equivalence of the decoding problem for BCH codes to a shift-register synthesis problem is demonstrated . . . ."
Groth, E. 1971. Generation of Binary Sequences With Controllable Complexity. IEEE Transactions on Information Theory. IT-17: 288-296.
"Abstract--Complexity of a binary sequence is measured by the amount of the sequence required to define the remainder. It is shown that, while maximum length (L = 2r - 1) sequences from r-stage linear feedback generators have minimum complexity, it is a simple matter to use such sequences as bases for deriving other more complex sequences of the same length."
"As a preliminary, it is important to recognize that any sequence can be generated by one or more linear generators." ". . . it is apparent that the adjectives, linear or nonlinear, applied frequently to sequences have no real meaning. Generators may be characterized as linear or nonlinear, but sequences may not."
Key, E. 1976. An Analysis of the Structure and Complexity of Nonlinear Binary Sequence Generators. IEEE Transactions on Information Theory. IT-22: 732-736.
"Abstract--A method of analysis is presented for the class of binary sequence generators employing linear feedback shift registers with nonlinear feed-forward operations. This class is of special interest because the generators are capable of producing very long 'unpredictable' sequences."
"This paper presents a method of analysis based on Galois field theory that enables one to predict the generator complexity resulting from nonlinear operations. Moreover the theory provides a conceptually simple basis for synthesizing devices with the desired characteristics, and is readily extendable to a larger class of more complex generators."
Gustavson, F. 1976. Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm. IBM Journal of Research and Development. 20: 204-212.
"Abstract: An analysis of the Berlekamp-Massey Linear Feedback Shift-Register (LFSR) Synthesis Algorithm . . . ." ". . . we present Massey's algorithm and indicate which steps contribute to the computation cost. We then prove what the minimum, average, and maximum computation costs are in terms of the numbers of multiplications and additions."
Welch, L. and R. Sholtz. 1979. Continued Fractions and Berlekamp's Algorithm. IEEE Transactions on Information Theory. IT-25(1): 19-27.
"Abstract -- Theorems are presented concerning the optimality of rational approximations using non-Archimedean norms. The algorithm for developing the rational approximations is based on continued fraction techniques and is virtually equivalent to an algorithm employed by Berlekamp for decoding BCH codes. Several variations of the continued fraction technique and Berlekamp's algorithm are illustrated on a common example.
Clark, G. and J. Cain. 1981. Error-Correction Coding for Digital Communications. Plenum Press.
Includes Berlekamp-Massey, and a lot more.
Ferguson, H and R. Forcade. 1982. Multidimensional Euclidean algorithms. Journal Fur Dir Reine Und Angewandte Mathematik. Walter de Gruyter & Co.
"Introduction. Given a pair (x, y) of positive real numbers, then one iteration of the Euclidean algorithm replaces the larger number by its least non-negative residue modulo the smaller number. If the two numbers are linearly dependent, the repetition of this process will eventually terminate with a pair in which one of the elements is zero. (If the original pair were integers, then the remaining non-zero element is their greatest common divisor.)"
"Another property of the Euclidean algorithm, fundamental to the study of continued fractions, is that it produces increasingly good rational approximations to the original pair of real numbers."
"We will construct an iterative algorithm for n-tuples, generalizing both the terminating and approximating features of the Euclidean algorithm. Thus, if the original n-tuple of elements are Z-linearly dependent, the algorithm will necessarily terminate and discover the Z-relation among the elements of the original n-tuple. If the original n-tuple elements are not Z-linearly dependent, then the algorithm will "absolutely approximate" by producing lattice points arbitrarily close to the line generated by the original n-tuple."
"We emphasize that a major difficulty in the problem of constructing a generalization of the Euclidean algorithm is to give an iterative algorithm."
Blahut, R. 1983. Theory and Practice of Error Control Coding. Addison-Wesley.
Covers decoding BCH codes both with Berlekamp-Massey and Euclidean algorithms, plus much more.
Mandelbaum, D. 1984. An Approach to an Arithmetic Analog of Berlekamp's Algorithm. IEEE Transactions on Information Theory. IT-30(5): 758-762.
"In 1968 Berlekamp [1] introduced an iterative procedure to determine a polynomial fraction A(x) / B(x) in which the coefficients are members of a field that, when divided, yields a given polynomial sequence S(x) in which the coefficients are, of course, members of the same field." "Massey gave another elegant proof of this procedure in terms of shift-registers [2]. Similar results were then obtained with the Euclidean algorithm and continued fractions [3]-[6]. Since continued fractions can be utilized with both polynomials and numbers from the real field, using an algorithm similar to the Berlekamp algorithm with real binary numbers was investigated."
"The class of arithmetic codes to which the proposed algorithm will apply is usually termed arithmetic residue codes and is a natural coding method for residue computers [12], which multiply and add quickly by using the Chinese remainder theorem." "These residue codes are the arithmetic analogs of the Reed-Solomon codes, which also can be decoded by the Euclidean algorithm or Berlekamp's algorithm."
Cheng, U. 1984. On the Continued Fraction and Berlekamp's Algorithm. IEEE Transactions on Information Theory. IT-30(3): 541-544.
"Abstract -- Continued fraction techniques are equivalent to Berlekamp's algorithm."
"Implementation of Berlekamp's algorithm by continued fraction technique was introduced by Reed et. al. [2]. In [3], Welch and Scholtz studied the equivalence between continued fraction and Berlekamp's algorithm. We will show that all entities in Berlekamp's algorithm [1] can be related to those in the continued fraction."
Brynielsson, L. 1985. On The Linear Complexity of Combined Shift Register Sequences. Advances in Cryptology -- EUROCRYPT '85. 156-160. Springer-Verlag.
"Many proposed keystream generators consist of a number of binary maximum length shift registers combined by a nonlinear binary function. The registers guarantee a long period and the nonlinear function destroys the linearity i.e. it gives the output sequence a large linear complexity [1] (linear equivalent [2]). In order to avoid correlation attacks the function should also be correlation immune [3] i.e. the output sequence should be statistically independent of the various inputs. There is however a trade off between the linear complexity and the order of correlation immunity . . . . The reason for this is that in the binary field GF(2) there are too few functions."
"In the field GF(2e) the situation is different. For instance, the polynomial function x+y+3xy+2(x2y+xy2)+x2y2 in GF(4) is both nonlinear and correlation immune. In order to validate such a function one must be able to calculate its linear complexity. That is the purpose of this paper."
Herlestam, T. 1985. On Functions of Linear Shift Register Sequences. Advances in Cryptology -- EUROCRYPT '85. 119-129. Springer-Verlag.
"Abstract. This paper is intended as an overview, presenting several results on the linear complexity of sequences obtained from functions applied to linear shift register sequences."
"Two well-known models for shift registers are in use. The Fibonacci model consists of cascaded memory boxes. The contents of each box is multiplied by a feedback coefficient before being taken to a common summing device to produce the feedback element."
"In the Galois model, adders are inserted between the memory boxes, the system output is multiplied by the feedback coefficients . . . and the products are taken to the adders."
"In both cases, the same shift register recurrence is obtained."
"Three different methods for handling this recurrence are in use. The linear algebraic (matrix) method is the most commonly used (e.g., Golomb (1967)) . . . ."
"Rewriting the shift register recurrence . . . we can apply the classical technique as use by Selmer (1966) and Key (1976) among others."
"Finally, the generating function method, used by Zierler (1959), can be applied to the shift register recurrence.
Siegenthaler, T. and R. Forre. 1987. Generation of Binary Sequences with Controllable Complexity and Ideal r-Tuple Distribution. Advances in Cryptology -- EUROCRYPT '87. 15-23.
"Abstract. A key stream generator is analyzed which consists of a single linear feedback shift register (LFSR) with a primitive connection polynomial and a nonlinear feedforward logic." ". . . a simple condition imposed on these logics ensures an ideal r-tuple distribution for these keystreams."
"Groth [2] proposed a layered structure for the feedforward logic to control the linear complexity of the generated keystream. This arrangement generates keystreams of large linear complexities, however, the statistics of these keystreams is hard to control. Rueppel suggested [3] [ the dissertation ] a simply realisable and therefore practically useful class of feedforward logics such that a lower bound for the keystream's linear complexity is guaranteed."
"Our analysis is based on Brynielsson's powerful Theorem 1 from which the linear complexity for every polynomial f applied to a maximum length sequence can be computed even if we use it only for a function . . . ."
Dornstetter, J. 1987. On the Equivalence Between Berlekamp's and Euclid's Algorithms. IEEE Transactions on Information Theory. IT-33(3): 428-431.
"Abstract -- It is shown that Berlekamp's iterative algorithm can be derived from a normalized version of Euclid's extended algorithm."
"The similarity between Berlekamp's iterative algorithm [1] and the extended Euclidean algorithm [7] has been previously noticed by several authors [3], [4]." "The original version of the iterative algorithm has been simplified by Massey [2]. We shall show in Section II that all partial results generated by this simplified version are in agreement (to a reciprocation and a normalization factor) with those given by Euclid's algorithm."
Rueppel, R. and O. Staffelbach. 1987. Products of Linear Recurring Sequences with Maximum Complexity. IEEE Transactions on Information Theory. IT-33(1): 124-131.
"Abstract -- Conditions are derived which guarantee that products of linear recurring sequences attain maximum linear complexity. It is shown that the product of any number of maximum-LENGTH GF(q) sequences has maximum linear complexity, provided only the degrees of the corresponding minimal polynomials are distinct and greater than two."
"A common type of running-key generator employed in stream cipher systems consists of n (mostly maximum-length) linear feedback shift registers (LFSR's) whose output sequences are combined in a nonlinear function F to produce the key stream." "One of the major objectives of F is to increase the linear complexity of the key stream such that the synthesis of a linear equivalent of the running-key generator (e.g., by using the Berlekamp-Massey LFSR synthesis algorithm [10]) becomes computationally feasible."
"We will stipulate that whenever we write of a product of two or more sequences we mean the termwise product of those sequences."
Imamura, K. and W. Yoshida. 1987. A Simple Derivation of the Berlekamp-Massey Algorithm and Some Applications. IEEE Transactions on Information Theory. IT-33(1): 146-150.
"The algorithm discovered by Berlekamp [1] for decoding BCH codes is very elegant. Massey [2] showed that Berlekamp's algorithm is best interpreted as an efficient recursive method for finding the shortest linear feedback shift register (LFSR) that generates a given sequence. Since Massey's interpretation is very useful, the algorithm is often called the Berlekamp-Massey algorithm."
"The derivation of the Berlekamp-Massey algorithm, however, seems to be rather difficult, and why it works is not so easy to understand [3], [4]." "The main purpose of this correspondence is to present a new method for deriving the Berlekamp-Massey algorithm . . . to make this important algorithm more easily understandable." "1) Find a general rule how the length of the LFSR grows with the sequence length and find a necessary and sufficient condition on the LFSR to be unique." "2) Find a recursive algorithm for updating the LFSR."
Chan, A. and R. Games. 1989. On the Quadratic Spans of Periodic Sequences. Advances in Cryptology -- CRYPTO '89. 82-89. Springer-Verlag.
"The length of a shortest FSR [feedback shift register] that generates the sequence is called the span of the sequence.
"Because of its tractability, most attention has been focused on determining the linear span of a sequence -- the length of the shortest linear FSR that generates the sequence."
"A sequence with very large linear span may be generated by a much shorter FSR if nonlinear terms are allowed in the feedback function."
Fuster-Sabater, A. and P. Caballero-Gil. 1994. On the Linear Complexity of Nonlinearly Filtered PN-sequences. Advances in Cryptology -- ASIACRYPT '94. 80-90. Springer-Verlag.
"Abstract. A method of analysis for the linear complexity of nonlinearly filtered PN-sequences is presented. The procedure provides a general lower bound for the linear complexity and an algorithm to improve it. The results obtained are valid for any nonlinear function with a unique term of maximum order and for any maximal-length LFSR. This work, which has as its starting point 'the root presence test' by Rueppel, is based on the handling of binary strings instead of determinants in a finite field."
"Groth [1] presented the linear complexity as a controllable parameter with the order of F. Nevertheless, in his work there is no explicit mention to the degeneracies which may occur in the linear complexity of the produced sequence."
"Key [2] established the relationship between the minimal polynomial roots required to represent the keystream generator and the linear complexity of the generated sequence. This result let Rueppel [7] state the so called 'root presence test' for the product of distinct phases of a PN-sequence."
". . . this paper proposes an algorithm to compute a lower bound for the complexity by using exclusively logic operations (OR, AND)."
Massey, J. and S. Serconek. 1994. A Fourier Transform Approach to the Linear Complexity of Nonlinearly Filtered Sequences. Advances in Cryptology -- CRYPTO '94. 332-340. Springer-Verlag.
"By exploiting 'Blahut's theorem,' which states that the linear complexity of an N-periodic sequence in GF(q)N and the Hamming weight of its frequency-domain associate are equal, we use Discrete Fourier Transform (DFT) techniques here to study the linear complexity of nonlinear filterings of PN(pseudo-noise)-sequences."
Fitzpatrick, P. 1994. New time domain errors and erasures decoding algorithm for BCH codes. Electronics Letters. 30(2): 110-111.
"A new algorithm is presented for solving the key equation that simultaneously computes the error locator polynomial and the errata evaluator polynomial. The algorithm is similar to the Berlekamp algorithm, but is more symmetrical in its treatment of the iterated pairs of polynomials making it particularly well suited to a highly parallel hardware implementation."
Fleischmann, M. 1995. Modified Berlekamp-Massey algorithm for two-sided shift-register synthesis. Electronics Letters. 31(8): 605-606.
"Introduction: Massey introduced in [3] an algorithm for calculating the shortest LFSR which generates a given finite sequence . . . . In [3] the synthesizing process is one-sided and a definite beginning or end of the sequence is needed. However, some applications may be imagined where prior knowledge of neither a sequence border nor the size of the sequence are available. As a result, the algorithm has to start somewhere within the sequence, and has to develop the LFSR using a two-sided synthesising process."
Last updated: 1996-08-15