Search

In 1972, Mykkeltveit confirmed Golomb's conjecture on the de Bruijn graphs: he proved that the pure cycling register rule yields the maximum number of vertex-disjoint cycles in de Bruijn graphs. We show that this result encompasses the tensor product of the de Bruijn graph for strings of length n with a simple cycle of size k , when n divides k or vice versa. Furthermore, we give counting formulas for an array of cycling register rules, which includes Golomb's well-studied linear register rules. [ABSTRACT FROM AUTHOR]

We study the sequences generated by prefer-one rule with different initial vectors. Firstly, we give upper bounds of their periods and for initial vectors with Hamming weight one, we prove that the generated sequences are modified de Bruijn sequences. Moreover, for two of them, we give the truth tables of their feedback functions. We also investigate the feedback functions of prefer-one de Bruijn sequences. For order n prefer-one de Bruijn sequence, we give linear and quadratic terms in its feedback function and prove that the number of degree n - 2 terms has the same parity as n. The statistical result for small n shows that about half of all terms occur in the feedback functions. [ABSTRACT FROM AUTHOR]

De Bruijn sequence is an important kind of nonlinear shift register sequence, which has a very wide range of applications in the fields of communication and cryptography. From the perspective of the relationship between linear terms, quadratic terms and cubic terms in the feedback functions of de Bruijn sequences, some new necessary conditions for feedback functions of de Bruijn sequences are obtained. Some examples show that the known necessary conditions cannot deduce the proposed necessary conditions.

This note introduces a code snippet in R aiming to generate necklaces as well as bracelets. Among various uses, necklaces are useful tools to manage traces of products of random matrices. Functionality for necklaces and bracelets is provided with some examples of applications such as Lyndon words and de Bruijn sequences. The routines are collected in the Necklaces package available from the Comprehensive R Archive Network. [ABSTRACT FROM AUTHOR]

We explicitly construct the first universal cycles for strings with fixed-content—also known as strings with the same Parikh vector, or multiset permutations—using their shorthand encoding, which omits the final symbol as it is redundant. For example, 112312131132 is a universal cycle for content S = { 1 , 1 , 2 , 3 } . Its first three windows—112, 123, and 231—are the shorthand representatives of 1123, 1231, and 2311, respectively. Our first construction V (S) applies the classic cycle-joining approach on the first-inversion tree of necklace cycles with content S. For example, when S = { 1 , 1 , 2 , 3 } the root is the necklace cycle 1123 and its children are 1 21 ̲ 3 and 11 32 ̲ by swapping their first (i.e., leftmost) inversions. From this construction, we derive a successor rule to generate successive symbols of V (S) in O(n)-time, where n = | S | is the cardinality of S. Our second construction U (S) concatenates fixed-content necklaces together in a cool-lex order using the necklace-prefix algorithm. For example, U (S) = 1123 · 1213 · 1132 for S = { 1 , 1 , 2 , 3 } . Central to this construction is the first shift Gray code for fixed-content necklaces, and a new efficient algorithm for generating these strings. From this construction, we can generate successive symbols of U (S) in O(1)-amortized time while using O(n)-space. We complete our investigation with a pleasant surprise: V (S) = U (S) . Our new results simultaneously generalize universal cycle constructions of shorthand permutations by Ruskey et al. (Algorithmica 64, 2012) and shorthand fixed-weight binary strings by Ruskey et al. (SIAM J Disc Math 26(2):605–617, 2012). They also provide a prefix-shift Gray code for multiset permutations in which the first symbol moves into the last or second-last position, which tightens the previous prefix-shift Gray code by Williams (Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009). Finally, we draw parallels between our constructions and the well-known granddaddy de Bruijn sequence for binary strings. [ABSTRACT FROM AUTHOR]

Years ago Zeev Rudnick defined the \lambda-Poisson generic sequences as the infinite sequences of symbols in a finite alphabet where the number of occurrences of long words in the initial segments follow the Poisson distribution with parameter \lambda. Although almost all sequences, with respect to the uniform measure, are Poisson generic, no explicit instance has yet been given. In this note we give a construction of an explicit \lambda-Poisson generic sequence over any alphabet and any positive \lambda, except for the case of the two-symbol alphabet, in which it is required that \lambda be less than or equal to the natural logarithm of 2. Since \lambda-Poisson genericity implies Borel normality, the constructed sequences are Borel normal. The same construction provides explicit instances of Borel normal sequences that are not \lambda-Poisson generic. [ABSTRACT FROM AUTHOR]

We study the sequences whose one period contains all the n-binary vectors of Hamming weight ≤ k exactly once. It is well known that such sequences exist for any n and 0 ≤ k ≤ n . However, their many basic properties and even their numbers are still unknown. A classical method for constructing such sequences is by joining the cycles generated by pure circulating registers, pure summing registers or complementing summing registers. In this paper, we show that, when k = 2 such sequences can all be constructed by joining cycles of pure circulating registers, but for n ≥ 4 and k ≥ 3 this is not the case any more. We also show that for n ≥ 7 and k ≥ 3 , the sequences constructed by joining cycles of pure circulating registers are different from those constructed by joining cycles of pure summing registers or complementing summing registers. Besides, we do some experiments and determine the numbers of such sequences for some small n and k. [ABSTRACT FROM AUTHOR]

We propose a general greedy algorithm for binary de Bruijn sequences, called Generalized Prefer-Opposite Algorithm, and its modifications. By identifying specific feedback functions and initial states, we demonstrate that most previously-known greedy algorithms that generate binary de Bruijn sequences are particular cases of our algorithm. [ABSTRACT FROM AUTHOR]

A preference function provides a method to build periodic sequences by specifying a set of rules that determine which symbols are to be attempted before others, when the sequence is constructed one symbol at a time. The well-known prefer-one, prefer-opposite, and prefer-same binary de Bruijn sequences are all constructed using appropriate preference functions. In this article we provide some fairly general results that give conditions for a pair of an initial word and a preference function on a q-ary alphabet to produce sequences that include every pattern of given size n ≥ 1 –except possibly some specified set of patterns. We provide several old and new constructions that showcase the flexibility of the results. Specifically, we give a construction for square-free and general separative de Bruijn sequences. The existence of these sequences was established more than a decade ago but nonconstructively. An important special case of these separative sequences produces universal cycles for permutations. We also build a preference function for binary de Bruijn sequences of patterns with a maximum density of ones. As for full de Bruijn sequences, the main result helps furnish a recursive construction from arbitrary cyclic permutations of q symbols. Finally, we build a preference function that extends a full de Bruijn sequence of order n into one of order n + 1 . [ABSTRACT FROM AUTHOR]

Fuzzing is one of the most successful software testing techniques used to discover vulnerabilities in programs. Without seeds that fit the input format, existing runtime dependency recognition strategies are limited by incompleteness and high overhead. In this paper, for structured input applications, we propose a fast format-aware fuzzing approach to recognize dependencies from the specified input to the corresponding comparison instruction. We divided the dependencies into Input-to-State (I2S) and indirect dependencies. Our approach has the following advantages compared to existing works: (1) recognizing I2S dependencies more completely and swiftly using the input based on the de Bruijn sequence and its mapping structure; (2) obtaining indirect dependencies with a light dependency existence analysis on the input fragments. We implemented a fast format-aware fuzzing prototype, FFAFuzz, based on our method and evaluated FFAFuzz in real-world structured input applications. The evaluation results showed that FFAFuzz reduced the average time overhead by 76.49% while identifying more completely compared with Redqueen and by 89.10% compared with WEIZZ. FFAFuzz also achieved higher code coverage by 14.53% on average compared to WEIZZ. [ABSTRACT FROM AUTHOR]

A cut-down de Bruijn sequence is a cyclic string of length L , where 1 ≤ L ≤ k n , such that every substring of length n appears at most once. Etzion [ Theor. Comp. Sci 44 (1986)] introduced an algorithm to construct binary cut-down de Bruijn sequences requiring o (n) simple n -bit operations per symbol generated. In this paper, we simplify the algorithm and improve the running time to O (n) time per symbol generated using O (n) space. Additionally, we develop the first successor-rule approach for constructing a binary cut-down de Bruijn sequence by leveraging recent ranking/unranking algorithms for fixed-density Lyndon words. Finally, we develop an algorithm to generate cut-down de Bruijn sequences for k > 2 that runs in O (n) time per symbol using O (n) space after some initialization. [ABSTRACT FROM AUTHOR]

Smart electronic devices are playing a fundamental role in modern home and industrial applications. The increased reliance on such devices, especially in time critical and secure applications, intensifies the need for time synchronization among multiple devices. This work presents a novel audio-based, cheap, offline synchronization method, whereby multiple slaves synchronize simultaneously to a master within a single room. Synchronization is carried out under the proposed protocol in a way that is independent of the physical location of the target devices, which in turn are not required to have any sort of network connectivity. The proposed method relies on the transmission of a De Bruijn sequence that holds the information required for the slaves to synchronize. The effectiveness of the proposed synchronization protocol is validated through an in-house experimental setup. Synchronization at distances of up to 250 cm between the master and a slave was achieved. [ABSTRACT FROM AUTHOR]

We study the adjacency graphs of feedback shift registers (FSRs) with affine characteristic functions. We first show that, similar to the linear case, the output sequences of FSRs with affine characteristic functions also have the direct sum decompositions. The only difference from the linear case is that one component of the decomposition is a family of affine sequences, rather than linear sequences. Then, based on this fact, we give a relationship between the adjacency graphs of FSRs with affine characteristic functions and the generalized adjacency graphs of FSRs whose characteristic functions correspond to the components of the decomposition. This relationship establishes the algebraic structure of adjacency graphs and greatly simplifies the calculation of them. At last, we especially study the adjacency graph of the FSR whose characteristic function is $q_{k}(x)+1$ where $q_{k}(x)$ is the linear function corresponding to the polynomial $(1+x)^{k}$. We prove that for any two cycles of this FSR, the number of conjugate pairs shared by them is no more than 4 if $k$ is a power of 2, and no more than 2 if $k$ is not a power of 2. [ABSTRACT FROM AUTHOR]

We study the cross-join pairs in the cycles of linear feedback shift registers whose characteristic polynomials are of the form $l(x) = p_{1}(x)p_{2}(x)\cdots p_{k}(x)$ , where $p_{i}(x), 1\leq i\leq k$ are primitive polynomials of coprime degrees. Firstly, we use Coppersmith et al.’s generating function theory to derive the lower and upper bounds for the number of cross-join pairs. Then we design an algorithm to generate these cross-join pairs. The algorithm requires a preparatory phase which costs $O(2^{n'})$ time where $n'$ is the largest degree of $p_{i}(x), 1\leq i\leq k$ , and after that it costs only $O(n^{3})$ time to generate one cross-join pair where $n$ is the degree of $l(x)$. We also consider a special class of cross-join pairs, for which the preparatory phase costs only $O(2^{n''})$ time where $n''$ is the second-largest degree of $p_{i}(x), 1\leq i\leq k$. The number of these special cross-join pairs is about $\frac {1}{12}2^{2n-n'}$. We present some experimental results, which validate our analysis and demonstrate the efficiencies of the algorithms. These cross-join pairs can be used in the cross-joining method to construct de Bruijn sequences. [ABSTRACT FROM AUTHOR]

Fuzzing is one of the most successful software testing techniques used to discover vulnerabilities in programs. Without seeds that fit the input format, existing runtime dependency recognition strategies are limited by incompleteness and high overhead. In this paper, for structured input applications, we propose a fast format-aware fuzzing approach to recognize dependencies from the specified input to the corresponding comparison instruction. We divided the dependencies into Input-to-State (I2S) and indirect dependencies. Our approach has the following advantages compared to existing works: (1) recognizing I2S dependencies more completely and swiftly using the input based on the de Bruijn sequence and its mapping structure; (2) obtaining indirect dependencies with a light dependency existence analysis on the input fragments. We implemented a fast format-aware fuzzing prototype, FFAFuzz, based on our method and evaluated FFAFuzz in real-world structured input applications. The evaluation results showed that FFAFuzz reduced the average time overhead by 76.49% while identifying more completely compared with Redqueen and by 89.10% compared with WEIZZ. FFAFuzz also achieved higher code coverage by 14.53% on average compared to WEIZZ.

We present a simple greedy algorithm to construct the prefer-same de Bruijn sequence and prove that it is equivalent to the more complex algorithm first stated by Eldert et al. without proof (Eldert et al., 1958 [3]), and later by Fredricksen (Fredricksen, 1982 [5]). Then we prove that the resulting sequence has the lexicographically largest run-length representation among all de Bruijn sequences. Furthermore, we prove that the sequence resulting from a prefer-opposite greedy construction has the lexicographically smallest run-length representation among all de Bruijn sequences. [ABSTRACT FROM AUTHOR]

A binary de Bruijn sequence is a sequence of period $2^n$ 2 n in which every binary $n$ n -tuple occurs exactly once in each period. A de Bruijn sequence has good randomness properties, such as long period, ideal tuple distribution, and high linear complexity, and can be generated by a nonlinear feedback shift register (NLFSR). Finding an efficient NLFSR that can generate a de Bruijn sequence with a long period is a significant challenge. “Composited construction” is a technique for constructing a de Bruijn sequence of period $2^{n+k}$ 2 n + k by an NLFSR from a de Bruijn sequence of period $2^n$ 2 n through a composition operation repeatedly applying $k$ k times. The goal of this article is to further investigate the composited construction of de Bruijn sequences with efficient hardware implementations, and determine randomness properties such as linear complexity. Our contributions in this article are as follows. First, we present a generalized construction of composited de Bruijn sequences that is constructed by adding a combination of conjugate pairs of different lengths in the feedback function of the composited construction, which results in generating a class of de Bruijn sequences of size $2^k$ 2 k , whereas the original composited construction can generate only two sequences. Second, we investigate the linear complexity and the correlation property of the new class of de Bruijn sequences. We prove theoretically that the linear complexity of this class of de Bruijn sequences is optimal or close to optimal. Interestingly, we also prove that the linear complexities of all the sequences of this class are equal, which strengthens Etzion's conjecture (JCTA 1985, IEEE-IT 1999) about the number of de Bruijn sequences with equal linear complexity. This is the first known construction of de Bruijn sequences of an arbitrarily long period whose linear complexities are determined theoretically. Finally, we implement our construction in hardware to demonstrate its practicality. We synthesize our implementations for a 65 nm ASIC and a Xilinx Spartan FPGA and present hardware areas, and performances of de Bruijn sequences of periods in the range of $2^{160}$ 2 160 to $2^{1056}$ 2 1056 . For instance, a class of de Bruijn sequences of period $2^{160}$ 2 160 (resp. $2^{288}$ 2 288 ) can be implemented with an area of 3.43 (resp. 6.71) kGEs in 65 nm ASIC, and 83 (resp. 229) slices in Spartan6 FPGA. [ABSTRACT FROM AUTHOR]

An order n binary de Bruijn sequence is a periodic sequence of bits with period 2 n in which each n-tuple of bits occurs exactly once. We consider the longest subsequences shared by two de Bruijn sequences. First, we fix one de Bruijn sequence and prove that de Bruijn sequences sharing a longest subsequence with it must be those obtained by a single cross-join operation from it. Then determining such sequences is equivalent to finding cross-join pairs with maximum diameter. Second, we prove that for n ≥ 5 , there exist two de Bruijn sequences of order n sharing a subsequence of length 2 n - 2 , i.e., there exists sequence a 0 a 1 ⋯ a 2 n - 3 with length 2 n - 2 such that both a 0 a 1 ⋯ a 2 n - 3 01 and a 0 a 1 ⋯ a 2 n - 3 10 are periods of de Bruijn sequences. [ABSTRACT FROM AUTHOR]

Peptide arrays measure the binding intensity of a specific protein to thousands of amino acid peptides. By using peptides that cover all k-mers, a comprehensive picture of the binding spectrum is obtained. Researchers would like to measure binding to the longest k-mer possible but are constrained by the number of peptides that can fit into a single microarray. A key challenge is designing a minimum number of peptides that cover all k-mers. Here, we suggest a novel idea to reduce the length of the sequence covering all k-mers by utilizing a unique property of the peptide synthesis process. Since the synthesis can start from both ends of the peptide template, it is enough to cover each k-mer or its reverse and to use the same template twice: in forward and reverse. Then, the computational problem is to generate a minimum length sequence that for each k-mer either contains the k-mer or its reverse. In this study, we present a new algorithm, called ReverseCAKE, to generate such a sequence. ReverseCAKE runs in time linear in the output size and is guaranteed to produce a sequence that is longer by at most Θ ( n log n) characters compared with the optimum n. The obtained saving factor by ReverseCAKE approaches the theoretical lower bound as k increases. In addition, we formulated the problem as an integer linear program and empirically observed that the solutions obtained by ReverseCAKE are near-optimal. Through this work, we enable more effective design of peptide microarrays. [ABSTRACT FROM AUTHOR]

A hardware-friendly and visually meaningful image encryption strategy is introduced in which a binary measurement matrix and de Bruijn sequence are applied. First, the plain image is sparsely represented by performing a discrete wavelet transform (DWT), and the corresponding sparse coefficient matrix is obtained. Second, this sparse coefficient matrix is measured by a binary measurement matrix that is generated through an improved integer logistic chaotic map easily implemented by hardware. Next, the measurement result is scrambled by utilizing a de Bruijn state sequence that can be produced by nonlinear shift registers. By diffusing the scrambled result, a secret image is obtained. Finally, the secret image is hidden in the coefficient matrix of a carrier image by utilizing the integer wavelet transform (IWT). Simulation experimental results and comprehensive analyses indicate that the proposed encryption strategy can achieve an effective visually meaningful cipher image. • Proposing a measurement matrix structure which is easier to implement in hardware. • Avoiding the sorting operation and improving the speed of encryption strategy. • Cipher images and common images transmit together and may draw no attention. [ABSTRACT FROM AUTHOR]

Structured light techniques are widely used in the depth measurement. In this paper, we propose a colored speckle method for high-accuracy depth sensing. The projected pattern is a composite of the discrete phase information and the colored De Bruijn sequence information, which can prove the feasibility, in practice, and the robustness to the environment. A Gabor filter is used to estimate the wrapped phase. To alleviate the phase ambiguity of conventional measurement methods, the period of the phase is distributed in two channels of the colored pattern by the De Bruijn sequence decoding. A morphological closure is adopted to determine the De Bruijn code by the phase neighborhoods back and forth. The proposed method is suitable for a dynamic scene. The quantitative and qualitative experiments are conducted, in practice, to evaluate the performance of the proposed method. The results of the experiments prove that not only can our proposed method achieve high accuracy and dense depth map, but it is also suitable for color object and dynamic scenes indoors. [ABSTRACT FROM AUTHOR]

We propose a construction of de Bruijn sequences by the cycle joining method from linear feedback shift registers (LFSRs) with arbitrary characteristic polynomial f(x). We study in detail the cycle structure of the set Ω (f (x)) that contains all sequences produced by a specific LFSR on distinct inputs and provide a fast way to find a state of each cycle. This leads to an efficient algorithm to find all conjugate pairs between any two cycles, yielding the adjacency graph. The approach is practical to generate a large class of de Bruijn sequences up to order n ≈ 20 . Many previously proposed constructions of de Bruijn sequences are shown to be special cases of our construction. [ABSTRACT FROM AUTHOR]

Abstract A shift rule for the prefer-max De Bruijn sequence is formulated, for all sequence orders, and over any finite alphabet. An efficient algorithm for this shift rule is presented, which has linear (in the sequence order) time and memory complexity. [ABSTRACT FROM AUTHOR]

A universal cycle, or u-cycle, for a given set of words is a circular word that contains each word from the set exactly once as a contiguous subword. The celebrated de Bruijn sequences are a particular case of such a u-cycle, where a set in question is the set A n of all words of length n over a k-letter alphabet A. A universal word, or u-word, is a linear, i.e., non-circular, version of the notion of a u-cycle, and it is defined similarly. Removing some words in A n may, or may not, result in a set of words for which u-cycle, or u-word, exists. The goal of this paper is to study the probability of existence of the universal objects in such a situation. We give lower bounds for the probability in general cases, and also derive explicit answers for the case of removing up to two words in A n , or the case when k = 2 and n ≤ 4 .

In Multicarrier Code Division Multiple Access (MC-CDMA) system, the performance can get degraded due to a high Peak to Average Power Ratio (PAPR) which is equivalent to Peak to Mean Envelope Power Ratio (PMEPR) and Multi Access Interference (MAI). There are several methods to reduce the PAPR and MAI. Out of these, one of the methods is to use an efficient spreading code technique to reduce the PAPR and MAI. Here, the PAPR and MAI have been analysed using Walsh Hadamard sequence, Gold sequence, Gordon, Mills and Welch (GMW) sequence and de Bruijn sequence as the spreading code. Simulation results show that the de Bruijn sequence can provide lower PMEPR than that provided by the other spreading sequences. It is also found that the same de Bruijn sequence provides better MAI performance than the other sequences. So, in this paper it is proposed that the de Bruijn sequence can be used as a spreading sequence for MC-CDMA to reduce the PMEPR along with MAI in a MC-CDMA system.

Sequence libraries that cover all k-mers enable universal and unbiased measurements of nucleotide and peptide binding. The shortest sequence to cover all k-mers is a de Bruijn sequence of length \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert \Sigma { \vert ^k} + k - 1$$ \end{document}. Researchers would like to increase k to measure interactions at greater detail, but face a challenging problem: the number of k-mers grows exponentially in k, while the space on the experimental device is limited. In this study, we introduce a novel advance to shrink k-mer library sizes by using joker characters, which represent all characters in the alphabet. Theoretically, the use of joker characters can reduce the library size tremendously, but it should be limited as the introduced degeneracy lowers the statistical robustness of measurements. In this work, we consider the problem of generating a minimum-length sequence that covers a given set of k-mers using joker characters. The number and positions of the joker characters are provided as input. We first prove that the problem is NP-hard. We then present the first solution to the problem, which is based on two algorithmic innovations: (1) a greedy heuristic and (2) an integer linear programming (ILP) formulation. We first run the heuristic to find a good feasible solution, and then run an ILP solver to improve it. We ran our algorithm on DNA and amino acid alphabets to cover all k-mers for different values of k and k-mer multiplicity. Results demonstrate that it produces sequences that are very close to the theoretical lower bound. [ABSTRACT FROM AUTHOR]

We determine the cycle structure of linear feedback shift register with arbitrary monic characteristic polynomial over any finite field. For each cycle, a method to find a state and a new way to represent the state are proposed. [ABSTRACT FROM AUTHOR]

We present sufficient conditions for when an ordering of universal cycles α 1 , α 2 , … , α m for disjoint sets S 1 , S 2 , … , S m can be concatenated together to obtain a universal cycle for S = S 1 ∪ S 2 ∪ ⋯ ∪ S m . When S is the set of all k -ary strings of length n , the result of such a successful construction is a de Bruijn sequence. Our conditions are applied to generalize two previously known de Bruijn sequence constructions and then they are applied to develop three new de Bruijn sequence constructions. [ABSTRACT FROM AUTHOR]

In the past decades, the construction of de Bruijn sequences has been extensively studied. Let ϕ be the one-to-one map from F 2 [ x ] to the set of all linear Boolean functions and the symbol “⁎” denote the product of two Boolean functions f ( x 0 , x 1 , . . . , x n ) and g ( x 0 , x 1 , . . . , x m ) given by f ( g ( x 0 , x 1 , . . . , x m ) , g ( x 1 , x 2 , . . . , x m + 1 ) , . . . , g ( x n , x n + 1 , . . . , x n + m ) ) . Then in this paper, a feedback shift register (FSR) with the characteristic function ( l + 1 ) ⁎ ϕ ( p ( x ) ) is considered to construct de Bruijn sequences for the first time, where ( l + 1 ) is an affine Boolean function and p ( x ) is a primitive polynomial over F 2 of degree n > 2 with ϕ − 1 ( l ) not divisible by p ( x ) . In specific, we determine the cycle structure and the adjacency graphs of this type of FSRs. As an example, we present the adjacency graph of FSRs with characteristic functions of the form ( ( x 0 + x 1 + x 2 + x 3 + 1 ) ⁎ ϕ ( p ( x ) ) ) and calculate the total number of de Bruijn sequences constructed from these FSRs. Note that it is the first time that the FSRs with affine characteristic functions are considered to construct de Bruijn sequences, and thus a new class of de Bruijn sequences are derived. [ABSTRACT FROM AUTHOR]

We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomial f(x) = p(x)q(x) where p(x) and q(x) are distinct irreducible polynomials in 픽2[x]. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a state belonging to each cycle and a generic algorithm to find all conjugate pairs shared by any pair of cycles are given. The process explicitly determines the edges and their labels in the adjacency graph. The results are then combined with the cycle joining method to efficiently construct a new class of de Bruijn sequences. An estimate of the number of resulting sequences is given. In some cases, using cyclotomic numbers, we can determine the number exactly. [ABSTRACT FROM AUTHOR]

A balanced generalized de Bruijn sequence with parameters (n , l , k) is a cyclic sequence of n bits such that (a) the number of 0's equals the number of 1's, and (b) each substring of length l occurs at most k times. We determine necessary and sufficient conditions on n , l , and k for the existence of such a sequence. [ABSTRACT FROM AUTHOR]

Sequences generated by maximum-period nonlinear feedback shift registers are known as de Bruijn sequences. The problem of generating de Bruijn sequences has received considerable attention. In this paper, we provide a method for generating large state (such as $$n=128$$ ) de Bruijn sequences. [ABSTRACT FROM AUTHOR]

We give a one-step construction of de Bruijn sequences of general alphabet size and with order $$n+k$$ , given a de Bruijn sequence of order n and any integer $$k>1$$ . This is achieved by using an appropriate class of graph homomorphisms between de Bruijn digraphs whose orders differ by an integer k. The method starts with a lower order de Bruijn cycle, finds its inverse cycles in the higher order digraph, which are then cross-joined into one full cycle. Therefore, this generalizes the Lempel's binary construction and the Alhakim-Akinwande construction for non-binary alphabets and a wide class of homomorphisms. [ABSTRACT FROM AUTHOR]

A phase detection sequence is a length- $n$ cyclic sequence, such that the location of any length- $k$ contiguous subsequence can be determined from a noisy observation of that subsequence. In this paper, we derive bounds on the minimal possible $k$ in the limit of $n\to \infty $ , and describe some sequence constructions. We further consider multiple phase detection sequences, where the location of any length- $k$ contiguous subsequence of each sequence can be determined simultaneously from a noisy mixture of those subsequences. We study the optimal trade-offs between the lengths of the sequences, and describe some sequence constructions. We compare these phase detection problems to their natural channel coding counterparts, and show a strict separation between the fundamental limits in the multiple sequence case. Both adversarial and probabilistic noise models are addressed. [ABSTRACT FROM AUTHOR]

We present the first efficient algorithm to list necklaces, Lyndon words, or pseudo-necklaces of length n in colexicographic order. The algorithm has two interesting properties. First, it can be applied to construct a de Bruijn sequence of order n in O ( 1 ) -time per bit. Second, it can easily be modified to efficiently list necklaces, Lyndon words, or pseudo-necklaces of length n in binary reflected Gray code order. [ABSTRACT FROM AUTHOR]

For positive integers k, n, a de Bruijn sequence B( k, n) is a finite sequence of elements drawn from k characters whose subwords of length n are exactly the $$k^n$$ words of length n on k characters. This paper studies the unoriented de Bruijn sequence uB( k, n), an analog to de Bruijn sequences, but for which the sequence is read both forwards and backwards to determine the set of subwords of length n. We show that nontrivial unoriented de Bruijn sequences of optimal length exist if and only if k is two or odd and n is less than or equal to 3. Unoriented de Bruijn sequences for any k, n may be constructed from certain Eulerian trails in Eulerizations of unoriented de Bruijn graphs. [ABSTRACT FROM AUTHOR]

A k -ary de Bruijn sequence of order n is a cyclic sequence of length k n in which each k -ary string of length n appears exactly once as a substring. A shift rule for a de Bruijn sequence of order n is a function that maps each length n substring to the next length n substring in the sequence. We present the first known shift rule for k -ary de Bruijn sequences that runs in O ( 1 ) -amortized time per symbol using O ( n ) space. Our rule generalizes the authors’ recent shift rule for the binary case (A surprisingly simple de Bruijn sequence construction, Discrete Math. 339, 127–131). [ABSTRACT FROM AUTHOR]

We present practical algorithms for ranking k -ary necklaces and Lyndon words of length n . The algorithms are based on simple counting techniques. By repeatedly applying the ranking algorithms, both necklaces and Lyndon words can be efficiently unranked. Then, explicit details are given to rank and unrank the length n substrings of the lexicographically smallest de Bruijn sequence of order n . [ABSTRACT FROM AUTHOR]

This article concerns optimal experimental designs for neuroimaging studies in which the pioneering functional magnetic resonance imaging (fMRI) technology is used to investigate functions of the human brain. We develop analytical results for identifying designs that allow precise estimates of the contrasts between hemodynamic response functions (HRFs), each describing the effect of a mental stimulus over time. We also provide systematic methods for constructing optimal and very efficient designs, and show that fMRI designs obtained by relabeling the symbols of m -sequences can be very efficient in comparing the HRFs. [ABSTRACT FROM AUTHOR]

We consider the adjacency graphs of the linear feedback shift registers (LFSRs) with characteristic polynomials of the form $l(x)p(x)$ , where l(x)$ is a polynomial of small degree and p(x)$ is a primitive polynomial. It is shown that their adjacency graphs are closely related to the association graph of l(x) , and construct a large class of De Bruijn sequences from them. [ABSTRACT FROM AUTHOR]