Sequences and the De Bruijn graph : properties, constructions, and applications /
The de Bruijn graph was defined in 1949 to enumerate the number of closed sequences where each n-tuple appears exactly once as a window in a sequence. Through the years, the graph and its sequences have found numerous applications - in space technology, wireless communication, cryptography, parallel...
| Main Author: | |
|---|---|
| Corporate Author: | |
| Format: | eBook |
| Language: | English |
| Published: |
London :
Academic Press,
2024.
|
| Subjects: | |
| Online Access: | Connect to the full text of this electronic book |
Table of Contents:
- Front Cover
- Sequences and the de Bruijn Graph
- Copyright
- Contents
- Preface
- 1 Introduction
- 1.1 Some concepts in finite fields and number theory
- 1.2 Codes, graphs, and sequences
- 1.3 The de Bruijn graph and feedback shift registers
- 1.4 Overview of the chapters
- 1.5 Notes
- References
- 2 LFSR sequences
- 2.1 Sequence length and polynomial representation
- 2.2 Maximum length linear shift-register sequences
- 2.3 Powers of irreducible polynomials
- 2.4 Patterns with distinct differences
- 2.5 Notes
- References
- 3 Cycles and the nonlinear theory
- 3.1 Cycles from feedback shift registers
- 3.2 Enumeration methods for polynomials and cycles
- 3.3 Maximum number of cycles in a state diagram
- 3.4 Notes
- References
- 4 Constructions of full cycles
- 4.1 Enumeration of all Eulerian cycles
- 4.2 The D-morphism and recursive constructions
- 4.3 Merging cycles of large factors
- 4.4 Notes
- References
- 5 Linear complexity of sequences
- 5.1 Binary sequences whose length is 2n
- 5.2 Complexity of binary de Bruijn sequences
- 5.3 Sequences over pm whose length is pn, p prime
- 5.4 Complexity of non-binary de Bruijn sequences
- 5.5 Notes
- References
- 6 Classification of sequences
- 6.1 Classification of sequences with length 2n−1
- 6.2 Classification of de Bruijn sequences
- 6.3 Classification of balanced sequences
- 6.4 The depth of a word
- 6.5 Notes
- References
- 7 One-dimensional applications
- 7.1 Stream ciphers
- 7.2 VLSI testing
- 7.3 Single-track Gray codes
- 7.4 Rotating-table games
- 7.5 Notes
- References
- 8 DNA sequences and DNA codes
- 8.1 The genome assembly
- 8.2 DNA storage codes
- 8.3 Constant-weight de Bruijn sequences
- 8.4 Reconstruction of a sequence from subsequences
- 8.5 Synchronization codes
- 8.6 Notes
- References
- 9 Two-dimensional arrays
- 9.1 Graph representations of perfect maps
- 9.2 Constructions by merging cycles
- 9.3 Pseudo-random arrays
- 9.4 Recursive constructions for perfect maps
- 9.5 Two-dimensional arrays with distinct differences
- 9.6 Notes
- References
- 10 Two-dimensional applications
- 10.1 Robust self-location two-dimensional patterns
- 10.2 Key predistribution for sensor networks
- 10.3 Folding of one-dimensional sequences
- 10.4 Notes
- References
- 11 Unique path property graphs
- 11.1 Basic properties of UPP graphs
- 11.2 Constructions for UPP graphs
- 11.3 Cycles and factors in UPP graphs
- 11.4 Notes
- References
- 12 Interconnection networks
- 12.1 The shuffle-exchange network
- 12.2 Multistage interconnection networks
- 12.3 Multistage permutation networks
- 12.4 Layouts
- 12.5 Notes
- References
- Index
- Back Cover