Last edited by Shakazshura

Thursday, May 14, 2020 | History

1 edition of **On the distribution of complexity for de Bruijn sequences** found in the catalog.

On the distribution of complexity for de Bruijn sequences

Robert LaVern Holdahl

- 205 Want to read
- 10 Currently reading

Published
**1983**
by Naval Postgraduate School in Monterey, California
.

Written in English

- Mathematics

ID Numbers | |
---|---|

Open Library | OL25480389M |

methods for constructing De Bruijn sequences are suggested. Keywords: symmetric boolean function, feedback shift register, De Bruijn sequence, cycle joining method. 1 Introduction De Bruijn sequences, i.e., periodic sequences in which each n-tuple appears exactly once in one period, have been studied for many years, see, for example, [1,4].Author: Ming Li, Mingxing Wang, Dongdai Lin. Abstract: This paper is concerned with the construction of de Bruijn sequences of span n--binary sequences of period 2^{n} in which every binary n-tuple appears as some n consecutive terms in one period of the sequence. Constructions in the literature are based on maximum length linear sequences, algorithms which start from scratch, and recursive methods which start with a single de Bruijn Cited by:

Completely uniformly distributed sequences based on de Bruijn sequences. 09/24/ ∙ by Emilio Almansi, et al. ∙ University of Buenos Aires ∙ 0 ∙ share. We study a construction published by Donald Knuth in yielding a completely uniformly distributed sequence of real numbers. Why use de Bruijn Graphs for Genome Assembly? 2. De Bruijn Graph of a Genome overlap-consensus-layout programs mask repetitive and low-complexity regions and assemble the remaining genome into many contigs and scaffolds. Unlike overlap-consensus-layout methods belaboring to merge Sanger reads into longer sequences based on mutual.

sequence. In particular, an n-stage nonlinear feedback shift register (NLFSR) generating a de Bruijn sequence is considered as a source of generating t-tuples with 1 t n, and then it is converted into another sequence (called ltering sequence) by applying a ltering function. Note that any ltering. computational complexity of constructing these half de Bruijn sequences (oth-erwise known as complement-free de Bruijn sequences), see [15]. For quotient de Bruijn strings over larger alphabets, we provide the following result. Theorem Let Gbe a group of order d with operation ‘+’. Let A= a 0a a dn 1 1 be a d-ary de Bruijn sequence.

You might also like

Topley and Wilsons Principles ofbacteriology, virology, and immunity

Topley and Wilsons Principles ofbacteriology, virology, and immunity

churches and race relations in South Africa.

churches and race relations in South Africa.

Accounting and food control for home economics students

Accounting and food control for home economics students

preliminary report on the bauxite deposits of Georgia

preliminary report on the bauxite deposits of Georgia

Pen portraits

Pen portraits

Colorful mineral identifier

Colorful mineral identifier

The Chemistry of Acid Derivatives (Chemistry of Functional Groups S.)

The Chemistry of Acid Derivatives (Chemistry of Functional Groups S.)

The history of New-Hampshire.

The history of New-Hampshire.

Indian paleography from about B.C. 350 to about A.D. 1300

Indian paleography from about B.C. 350 to about A.D. 1300

How can digital photography enhance digital media products.

How can digital photography enhance digital media products.

Business investment in the arts

Business investment in the arts

Great Garden Fix-Its

Great Garden Fix-Its

texts All Books All Texts latest This Just In Smithsonian Libraries FEDLINK On the distribution of complexity for de Bruijn sequences. Item Preview remove-circle On the distribution of complexity for de Bruijn sequences.

by Holdahl, Robert LaVern. Publication date Topics MathematicsPages: For n = 1, the only de Bruijn sequence (0, 1) has complexity 2.

For n = 2, the only de Bruijn sequence (0, 0, 1, 1) has complexity 3. The remark at the end of the previous section shows that the two de Bruijn sequences of span 3 have complexity by: It will be shown that the complexity of a de Bruijn sequence (S) is the same as the complexity of its reverse (r S), complement (5~), and Sequences (S) for which r S = S~ are termed RC sequences.

It is shown that RC sequences exist for every odd n>: Robert LaVern Holdahl. On the Distribution of On the distribution of complexity for de Bruijn sequences book Bruijn Sequences of Given Complexity () Cached. Download Links @ARTICLE{Etzion84onthe, author = {Tuvi Etzion and Abraham Lempel}, title = {On the Distribution of de Bruijn Sequences of Given Share.

OpenURL. Abstract. Keyphrases. given complexity bruijn sequence. The distribution gamma (c, n) of de Bruijn sequences of order n and linear complexity c is investigated.

It is shown that for n geq 4, gamma (2^{n} - 1, n) equiv 0 pmod{8}, and for k geq 3, gamma. generates the de Bruijn sequence is called the complexity of the sequence. (Other authors [ 7,9, lo] have considered the complexity of finite sequences from different viewpoints.) The next section introduces concepts, including the concept of complexity of binary sequences.

Some new results are proved on the distribution of de Bruijn sequences of low complexity, i.e., their complexity is between 2"-1+n and 2"-'+2"-z. It is proved that for n>5 and 2"-1+n Cited by: 6. Abstract: The linear complexity of a de Bruijn sequence is the degree of the shortest linear recursion which generates the sequence.

It is well known that the complexity of a binary de Bruijn sequence of length 2/sup n/ is bounded below by 2/sup n-1/+n and above by 2/sup n-/1 for n/spl ges/3. We briefly survey the known knowledge in this by: Notably, we highlight the links between De Bruijn sequences and the most complex symmetric functions and new functions are exhibited in the case q = 2 and any m.

Enumeration of these functions are supplied, they are shown to be sufficiently numerous to allow many : RovettaChristelle, MouffronMarc. Abstract-It is well known that the linear complexity of a de Bruijn. sequence S of length 2” is bounded below by 2”-’ + n for n > 3. It is.

shown that this lower bound is attainable for all. For example, to construct the smallest B (2,4) de Bruijn sequence of length 2 4 = 16, repeat the alphabet (ab) 8 times yielding w =abababababababab. Sort the characters in w, yielding w '=aaaaaaaabbbbbbbb.

Position w' above w as shown, and map each element in w ' to the corresponding element in w by drawing a line. Order n de Bruijn sequences are the period 2n binary sequences from n-stage feedback shift registers. The de Bruijn sequences have good randomness and complexity properties.

The quantity of de Bruijn sequences in a weight class of the order n generating functions is an unsolved NP complete problem. Binary de Bruijn sequences of period 2 n bits have the property that all 2 n distinct n-tupies occur once per period.

To generate such a sequence with an n-stage shift-register requires the use of nonlinear feedback. These properties suggest that de Bruijn sequences may be useful in stream by: 2.

Etzion, On the distribution of de Bruijn sequences of low complexity, J. Combin. Theory Ser. A 38 (), Google Scholar Cross Ref; 8. Etzion and A. Lempel, On the distribution of de Bruijn sequences of given complexity, IEEE Trans. Inform. Theory 30 Author: R BlackburnSimon, EtzionTuvi, G PatersonKenneth.

For example, one can walk along the graph from Picture 1 by forming the cycle $1,3,6,4,(1)$ which corresponds to the sequence $$$$ and has the corresponding unique substrings $$,$$ There are of course many such cycles in a given graph. plexities and give some computational results on the distribution of the linear complexity of de Bruijn sequences.

In Section 3, we develop the con-nection between the linear complexity of sequences and the degrees of per-mutation polynomials and apply it to the study of permutations of F pm, these being equivalent to span 1 de Bruijn sequences.

In the present contribution, we determine the period, the distribution of short patterns and a lower bound for the linear complexity of the sequences generated by an ASG. The proof of the lower bound is greatly simplified by assuming that k generates a de Bruijn sequence.

Under this and other not very restrictive assumptions the period and the Cited by: The number of nodes and edges was approximately half that of the traditional graph, indicating that sequencing errors and false frame translations increased the complexity of the codon-based de Bruijn graph.

To obtain a more intuitive and comprehensive understanding of the codon-based de Bruijn graph, the gene FBgn was taken as an by: Let (xt) be an n-periodic sequence in which the first n elements are drawn i.i.d. according to some rational distribution.

We prove there exists a constant C such that whenever mlnm⩾Cn, with probability close to 1, there exists an automaton of size m that matches the sequence at almost all stages.

This paper deals with the analysis of the correlation properties, and radar-related properties, of a family of binary sequences known as De Bruijn sequences.

They are considered in the framework of Spread Spectrum applications, and compared to other solutions, such as those adopting chaos-based sequences. Due to the complexity of the generation process, the analysis of De Bruijn sequences. On the Distribution of Complexity Master's Thesis; for de Bruijn Sequences June 4.

PERFORMIG~ OR0. REPORT NUMBER 7. AUTHOR(@) S. CONTRACT OR GRANT NUMOERfO) Robert LaVern Holdahi 9. ORM ORGANIZATION NAME AND ADDRESS PROGRAM ELEMENT.

PROJECT, TASK AREA A WORIC UNIT [email protected] Naval Postgraduate School .Downloadable! Let µ be a rational distribution over a finite alphabet, and () be a n-periodic sequences which first n elements are drawn i.i.d.

according to µ. We consider automata of bounded size that input and output at stage t. We prove the existence of a constant C such that, whenever, with probability close to 1 there exists an automaton of size m such that the empirical frequency of.Dynamical systems.

Binary De Bruijn graphs can be drawn (below, left) in such a way that they resemble objects from the theory of dynamical systems, such as the Lorenz attractor (below, right).

This analogy can be made rigorous: the n-dimensional m-symbol De Bruijn graph is a model of the Bernoulli map ↦ The Bernoulli map (also called the 2x mod 1 map for m = 2) is an ergodic dynamical.