2011/08/22 by Graham H. Norton, Norton, Graham H.
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1108.4224
19 pages, 3 tables
arxiv created 2011/08/23 · arxiv updated 2011/08/24
We derive Bézout identities for the minimal polynomials of a finite sequence and use them to prove a theorem of Wang and Massey on binary sequences with a perfect linear complexity profile. We give a new proof of Rueppel's conjecture and simplify Dai's original proof. We obtain short proofs of results of Niederreiter relating the linear complexity of a sequence s and K(s), which was defined using continued fractions. We give an upper bound for the sum of the linear complexities of any sequence. This bound is tight for sequences with a perfect linear complexity profile and we apply it to characterise these sequences in two new ways.