✦ LIBER ✦

Permutation Polynomials, de Bruijn Sequences, and Linear Complexity

✍ Scribed by Simon R. Blackburn; Tuvi Etzion; Kenneth G. Paterson

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 837 KB
Volume: 76
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1996.0088

No coin nor oath required. For personal study only.

✦ Synopsis

The paper establishes a connection between the theory of permutation polynomials and the question of whether a de Bruijn sequence over a general finite field of a given linear complexity exists. The connection is used both to construct span 1 de Bruijn sequences (permutations) of a range of linear complexities and to prove non-existence results for arbitrary spans. Upper and lower bounds for the linear complexity of a de Bruijn sequence of span n over a finite field are established. Constructions are given to show that the upper bound is always tight, and that the lower bound is also tight in many cases.

1996 Academic Press, Inc.

1. Introduction

A periodic sequence s over F p m , the finite field with p m elements, is called a span n de Bruijn sequence if each n-tuple of elements of F p m appears article no.

📜 SIMILAR VOLUMES

Characterising the Linear Complexity of

Characterising the Linear Complexity of Span 1 de Bruijn Sequences over Finite Fields

✍ Peter A. Hines 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 307 KB

We give a complete resolution to a conjecture regarding the characterisation of linear complexities of span 1 de Bruijn sequences over nonprime finite fields. This contrasts with results for prime fields, where the characterisation is equivalent to an open question concerning permutation polynomials

On the Minimum Linear Complexity of de B

On the Minimum Linear Complexity of de Bruijn Sequences over Non-prime Finite Fields

✍ Peter A. Hines 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 126 KB

It has been conjectured that over any non-prime finite field F p m and for any positive integer n, there exists a span n de Bruijn sequence over F p m which has the minimum possible linear complexity p nm&1 +n. We give a proof by construction that this conjecture is true.

On the distribution of de bruijn sequenc

On the distribution of de bruijn sequences of low complexity

✍ Tuvi Etzion 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 614 KB

On the complexities of de Bruijn sequenc

On the complexities of de Bruijn sequences

✍ Agnes Hui Chan; Richard A Games; Edwin L Key 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 576 KB

De Bruijn sequences, irreducible codes a

De Bruijn sequences, irreducible codes and cyclotomy

✍ Erik R. Hauge; Tor Helleseth 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 456 KB

There are no de bruijn sequences of span

There are no de bruijn sequences of span n with complexity 2n − 1 + n + 1

✍ Richard A Games 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 184 KB