Search

In this work, we propose cumulative residual Fisher information and relative cumulative residual Fisher information measures and establish some of their properties. We first show that these cumulative Fisher measures can be expressed based on the hazard function. We then define extended versions of cumulative residual entropy and cumulative residual Fisher information measures based on the Jensen inequality. We also discuss connections between these information measures based on a new version of de Bruijn’s identity for survival functions.

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.

Depth sensing with single-shot structured light is widely employed for depth measurement of dynamic scenes. For conventional single-shot structured light techniques, the projected pattern is coded with regards to color, shape, and intensity, aiming at assigning each pixel a unique label. However, the features of the projected pattern are extremely susceptible to the surface texture of the measured object, resulting in errors during performing decoding. In this study, a robust and simple binary pattern is proposed for high-accuracy depth sensing. Only two gray values are utilized in the designed pattern, which is insensitive to environmental noise. The pseudo two-dimensional De Bruijn sequence coding method is employed to reduce the size of the decoding window for robust matching. Short slashes are adopted as features of the pattern that greatly simplifies the feature extraction and pattern decoding. Compared with the Kinect and time-of-flight (TOF) depth cameras, our proposed method can acquire high-precision depth in quantitative and qualitative experiments.

The De-Bruijn sequences could provide appropriate circular arrangements to achieve a single-track absolute rotary optical encoder in the servo motor application. One example used popularly is the maximum length sequences. High-resolution single-track encoders need a sensor array to obtain the position signal simultaneously. Nevertheless, the individual photocurrents would interference by other adjacent photocurrents, like the photocurrent blooming. The circumstances would increase the bias noise for the digital binarization. The concept in this article would try to find the optimal De-Bruijn sequences to reduce the photocurrent blooming interference intrinsically without signal process remodification. Three different types of the 9-bits codes, the adjacent De-Bruijn code, the quarter De-Bruijn codes, and the optimal De-Bruijn codes, are analyzed, manufactured, and experimented in the actual encoders. Based on the open-factor of the eye-diagram, the adjacent De-Bruijn code has 0.328 and would be the worse signal quality in De-Bruijn sequences. The quarter De-Bruijn codes have 0.386 of the open-factor with 17.7% improvement to adjacent De-Bruijn code. Finally, the optimal De-Bruijn codes have 0.436 of the open-factor with 32.9% improvement to the traditional M-code. The fact would mean the possible ability of 3-bits progress from 9-bits of adjacent De-Bruijn code to 12-bits of the optimal De-Bruijn codes under the same signal-to-noise ratio.

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.

In this paper, we study a class of binary nonlinear feedback shift register sequences generated by cascaded feedback registers, one is an LFSR and the other one generates a de Bruijn sequence. The cycle structure (in particular, the initial state of each cycle) is determined by solving a system of linear equations. As an application, we can generate de Bruijn sequences of large period algorithmically.

We present a simple framework for constructing $k$ -ary de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes several previously known de Bruijn sequence constructions based on the pure cycling register and is applied to derive a new construction that is perhaps the simplest of all successors. Furthermore, it generalizes an algorithm to construct binary de Bruijn sequences based on any arbitrary nonsingular feedback function. The framework is applied to derive and prove the correctness of successors to efficiently construct 1) universal cycles for $k$ -ary strings of length $n$ whose weight is bounded by some $w$ and 2) universal cycles for permutations. It has also been subsequently applied to find the first universal cycle constructions for weak orders.

Nonlinear feedback shift registers (NFSRs) are widely used in communication and cryptography. How to construct more NFSRs with maximal periods, which can generate sequences with maximal periods, i.e., de Brujin sequences, is an attractive problem. Recently many results on constructing de Bruijn sequences from adjacency graphs of Linear feedback shift registers (LFSRs) by means of the cycle joining method have been obtained. In this paper we discuss a class of LFSRs with characteristic polynomial p 2(x), where p(x) is a primitive polynomial of degree n ≥ 2 over the finite field F 2. As results, we determine their cycle structures and adjacency graphs, and further construct a class of new de Bruijn sequences from these LFSRs.

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.

In this paper, we propose generalizations of the de Bruijn identity based on extensions of the Shannon entropy, Fisher information and their associated divergences or relative measures. The foundations of these generalizations are the $\phi $ -entropies and divergences of the Csiszar (or Salicru) class considered within a multidimensional context, including the one-dimensional case, and for several types of noisy channels characterized by a more general probability distribution beyond the well-known Gaussian noise. We found that the gradient and/or the Hessian of these entropies or divergences with respect to the noise parameter naturally give rise to generalized versions of the Fisher information or divergence, which are named the $\phi $ -Fisher information (divergence). The obtained identities can be viewed as further extensions of the classical de Bruijn identity. Analogously, it is shown that a similar relation holds between the $\phi $ -divergence and an extended mean-square error, named $\phi $ -mean square error, for the Gaussian channel.

We study the problem of constructing De Bruijn sequences by joining cycles of linear feedback shift registers (LFSRs) with reducible characteristic polynomials. The main difficulty for joining cycles is to find the location of conjugate pairs between cycles, and the distribution of conjugate pairs in cycles is defined to be adjacency graphs. Let $l(x)$ be a characteristic polynomial, and $l(x)=l_{1}(x)l_{2}(x)\cdots l_{r}(x)$ be a decomposition of $l(x)$ into pairwise co-prime factors. First, we show a connection between the adjacency graph of $\mathrm {FSR}(l(x))$ and the association graphs of $\mathrm {FSR}(l_{i}(x))$ , $1\leq i\leq r$ . By this connection, the problem of determining the adjacency graph of $\mathrm {FSR}(l(x))$ is decomposed to the problem of determining the association graphs of $\mathrm {FSR}(l_{i}(x))$ , $1\leq i\leq r$ , which is much easier to handle. Then, we study the association graphs of LFSRs with irreducible characteristic polynomials and give a relationship between these association graphs and the cyclotomic numbers over finite fields. At last, as an application of these results, we explicitly determine the adjacency graphs of some LFSRs and show that our results cover the previous ones.

Feedback shift registers can be applied to the fields of communications, stream ciphers, computers, and design theory. The linear feedback shift registers are often used in the construction of De Bruijn sequences. For any given linear shift register, its cycle structure and adjacency graphs are features that must be investigated in the construction of the De Bruijn sequences by using the cycle-joining method. A class of linear feedback shift registers is discussed in this paper. The cycle structure of some linear feedback shift registers is derived. And the adjacency graphs are divided into two categories to analyze their structure in detail. Based on this kind of linear feedback shift registers combined with the cycle-joining method, a novel family of De Bruijn cycles is obtained. The number of the corresponding De Bruijn cycles produced is also proposed exactly.

A binary de Bruijn sequence with period $2^n$ is a sequence in which every tuple of $n$ bits occurs exactly once. De Bruijn sequence generators have randomness properties that make them attractive for pseudorandom number generators and as building blocks for stream ciphers. Unfortunately, it is very difficult to find de Bruijn sequence generators with long periods (e.g., $2^{128}$ ) and most known de Bruijn sequence generators are computationally quite expensive. In this article, we present “OcDeb- $k$ - $n$ ” and the first hardware implementation of de Bruijn sequence generators. OcDeb- $k$ - $n$ efficiently computes a composited de Bruijn sequence where $k$ levels of composition are added to a de Bruijn sequence of period $2^n$ . Numerically, OcDeb reduces the bit operations used for computing the feedback function significantly from ${\Theta}(k^2+nk)$ to ${\Theta}(k\;\log {k} + \log {n})$ . Furthermore, it enables efficient parallelization and hardware retiming. Comprehensive result analysis is conducted for 65 nm ASIC technology. For example, OcDeb-32-32 has an area of 643 GE with 1.45 Gbps performance, and with parallelization it generates up to 25.4 Gbps at the cost of 4,787 GE. The area of OcDeb-512-32 generating a de Bruijn sequence of period $2^{544}$ is 7,304 GE and the performance is 1.25 Gbps.

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 the cyclotomic numbers over finite fields. By using this connection, we give a unified method to determine their adjacency graphs. As an application of the method, we explicitly calculate the adjacency graphs of LFSRs with the characteristic polynomials of the form $(1+x+x^{3}+x^{4})p(x)$ , and construct a large class of De Bruijn sequences from them.

This paper shows that de Bruijn identity, which relates entropy with Fisher information, can be obtained as a particular case of an immediate generalization of Price’s theorem, which is a tool used in the analysis of nonlinear memoryless systems with Gaussian inputs. It is shown that, while the general Price’s theorem follows since the density of the perturbation satisfies the heat equation, the particular case of de Bruijn identity follows since the score function is zero-mean, which is thewell-knownconditionthatprovidestheinsightfulCrame ´r- Rao bound expression based on the negative second derivative of the log-likelihood function. The unified framework uses the characteristic function as a main tool and becomes a more intuitive alternative to the classical technical proof obtained by integrating by parts. Second-order Tsallis entropy is also briefly explored under this general framework.

A binary de Bruijn sequence of order $n$ is a sequence of zeros and ones of period $2^n$ that contains every binary $n$ -tuple exactly once in a period of the sequence. A composited construction of a de Bruijn sequence is a construction of a nonlinear feedback shift register (NLFSR) that generates a de Bruijn sequence where the composited feedback function of the NLFSR is the sum of a feedback function with $k$ th order composition and a sum of $(k+1)$ product-of-sum terms. The goals of this article are to perform a profound analysis of composited de Bruijn sequences for use in cryptography and find an efficient implementation of the composited feedback function. We first determine the lower bound of the linear complexity of a composited de Bruijn sequence and then conduct a profound analysis on the composited construction by introducing the notion of the higher order $D$ -morphic preimages of a binary sequence. Our analysis aims at the reconstruction of a composited de Bruijn sequence from a segment known as $k$ th order $D$ -morphic order $n$ de Bruijn preimages ( $(n,k)$ -DMDPs) of length $(2^n+k)$ and $k$ th order $D$ -morphic order $n$ $m$ -sequence preimages ( $(n,k)$ -DMMPs) of length $(2n+k)$ for a nonlinearly and linearly generated composited de Bruijn sequence, respectively. We also provide the success probability of finding an $(n,k)$ -DMMP/DMDP from a composited de Bruijn sequence for the reconstruction. Furthermore, we develop a new iterative technique with its parallel extension for computing the feedback function and the new technique is faster than other known techniques for producing de Bruijn sequences of long period. In addition, we present three instances of composited de Bruijn sequences of period $2^{64}$ together with their software implementations and performances.

We consider the problem of storing and retrieving information from synthetic DNA media. The mathematical basis of the problem is the construction and design of sequences that may be discriminated based on their collection of substrings observed through a noisy channel. This problem of reconstructing sequences from traces was first investigated in the noiseless setting under the name of "Markov type" analysis. Here, we explain the connection between the reconstruction problem and the problem of DNA synthesis and sequencing, and introduce the notion of a DNA storage channel. We analyze the number of sequence equivalence classes under the channel mapping and propose new asymmetric coding techniques to combat the effects of synthesis and sequencing noise. In our analysis, we make use of restricted de Bruijn graphs and Ehrhart theory for rational polytopes., 27 pages, 5 figures. Journal version of arXiv:1410.8837

In 1982, H. Fredricksen presented the up- per and lower bounds of the number of ones in the truth table of characteristic functions of de Bruijn sequences. In this paper, the distribution of ones in the truth table of characteristic functions of de Bruijn sequences is further studied. We provide the upper and lower bounds of the number of ones in the partial truth table of characteris- tic functions of de Bruijn sequences. Furthermore, the two bounds are tight.

In this paper, a class of linear feedback shift registers (LFSRs) with characteristic polynomial (1 + x 3 )p(x) is discussed, where p(x) is a primitive polynomial of degree n > 2. The cycle structure and adjacency graphs of the LFSRs are determined. A new class of de Bruijn sequences is constructed from these LFSRs, and the number of de Bruijn sequences in the class is also considered. To illustrate the efficiency of constructing de Bruijn sequences from these LFSRs, an algorithm for producing some corresponding maximum-length nonlinear feedback shift registers with time and memory complexity O(n) is also proposed.

De Bruijn graph based genome assembly has gained popularity as short read sequencers become ubiquitous. A core assembly operation is the generation of unitigs, which are sequences corresponding to chains in the graph. Unitigs are used as building blocks for generating longer sequences in many assemblers, and can facilitate graph compression. Chain compaction, by which unitigs are generated, remains a critical computational task. In this paper, we present a distributed memory parallel algorithm for simultaneous compaction of all chains in bi-directed de Bruijn graphs. The key advantages of our algorithm include bounding the chain compaction run-time to logarithmic number of iterations in the length of the longest chain, and ability to differentiate cycles from chains within logarithmic number of iterations in the length of the longest cycle. Our algorithm scales to thousands of computational cores, and can compact a whole genome de Bruijn graph from a human sequence read set in 7.3 seconds using 7680 distributed memory cores, and in 12.9 minutes using 64 shared memory cores. It is $3.7\times$ 3 . 7 × and $2.0\times$ 2 . 0 × faster than equivalent steps in the state-of-the-art tools for distributed and shared memory environments, respectively. An implementation of the algorithm is available at https://github.com/ParBLiSS/bruno .

A method for constructing n-stage Galois NLFSRs with period 2n-1 from n-stage maximum length LFSRs is presented. Nonlinearity is introduced into state cycles by adding a nonlinear Boolean function to the feedback polynomial of the LFSR. Each assignment of variables for which this function evaluates to 1 acts as a crossing point for the LFSR state cycle. The effect of nonlinearity is cancelled and state cycles are joined back by adding a copy of the same function to a later stage of the register. The presented method requires no extra time steps and it has a smaller area overhead compared to the previous approaches based on cross-join pairs. It is feasible for large n.

Most proposed DHTs engage certain topology maintenance mechanisms specific to the static graphs on which they are based. The designs of these mechanisms are complicated and repeated with graph-relevant concerns. In this paper, we propose the “distributed line graphs” (DLG), a universal technique for designing DHTs based on arbitrary regular graphs. Using DLG, the main features of the initial graphs are preserved, and thus people can design a new DHT by simply choosing the graph with desirable features and applying DLG to it. We demonstrate the power of DLG by illustrating four DLG-enabled DHTs based on different graphs, namely, Kautz, de Bruijn, butterfly, and hypertree graphs. The effectiveness of our proposals is demonstrated through analysis, simulation, and implementation.

Employing thousands of cores in a single chip is the natural trend to handle the ever increasing performance requirements of complex applications such as those used in graphics and multimedia processing. System-on-chips (SoCs) platforms based on network-on-chips (NoCs) could be a viable option for the deployment of large multicore designs with thousands of cores. This paper proposes the generalized binary de Bruijn (GBDB) graph as a reliable and efficient network topology for a large NoC. We propose a reliable routing algorithm to detour a faulty channel between two adjacent switches. In addition, using integer linear programming, we propose an optimal tile-based implementation for a GBDB-based NoC in which the number of channels is less than that of Torus which has the same number of links. Our experimental results show that the latency and energy consumption of the generalized de Bruijn graph are much less than those of Mesh and Torus. The low energy consumption of a de Bruijn graph-based NoC makes it suitable for portable devices which have to operate on limited batteries. Also, the gate level implementation of the proposed reliable routing shows small area, power, and timing overheads due to the proposed reliable routing algorithm.

The topological properties of peer-to-peer overlay networks are critical factors that dominate the performance of these systems. Several nonconstant and constant degree interconnection networks have been used as topologies of many peer-to-peer networks. The Kautz digraph is one of these topologies that have many desirable properties. Unlike interconnection networks, peer-to-peer networks need a topology with an arbitrary order and degree, but the Kautz digraph does not possess these properties. In this paper, we propose MOORE: the first effective and practical peer-to-peer network based on the quasi-Kautz digraph with O(logd n) diameter and constant degree under a dynamic environment. The diameter and average routing path length, respectively, are shorter than that of CAN, butterfly, and cube-connected cycle, and are close to that of the de Bruijn and Kautz digraphs. The message cost of node joining and departing operations are at most 2.5d\logd n and (2.5d+1)\logd n, and only d and 2d nodes need to update their routing tables. MOORE can achieve optimal diameter, high performance, good connectivity, and low congestion, evaluated by formal proofs and simulations.

Balancing of structured peer-to-peer graphs, including their zone sizes, has recently become an important topic of distributed hash table (DHT) research. To bring analytical understanding into the various peer-join mechanisms based on consistent hashing, we study how zone-balancing decisions made during the initial sampling of the peer space affect the resulting zone sizes and derive several asymptotic bounds for the maximum and minimum zone sizes that hold with high probability. Several of our results contradict those of prior work and shed new light on the theoretical performance limitations of consistent hashing. We use simulations to verify our models and compare the performance of the various methods using the example of recently proposed de Bruijn DHTs.

This paper examines graph-theoretic properties of existing peer-to-peer networks and proposes a new infrastructure based on optimal-diameter de Bruijn graphs. Since generalized de Bruijn graphs exhibit very short average distances and high resilience to node failure, they are well suited for distributed hash tables (DHTs). Using the example of Chord, CAN, and de Bruijn, we study the routing performance, graph expansion, clustering properties, and bisection width of each graph. Having confirmed that de Bruijn graphs offer the best diameter and highest connectivity among the existing peer-to-peer structures, we offer a very simple incremental building process that preserves optimal properties of de Bruijn graphs under uniform user joins/departures. We call the combined peer-to-peer architecture optimal diameter routing infrastructure.

In this paper, we present two algorithms for efficiently aggregating link state information needed for quality-of-service (QoS) routing. In these algorithms, each edge node in a group is mapped onto a node of a shufflenet or a node of a de Bruijn graph. By this mapping, the number of links for which state information is maintained becomes aN (a is an integer, N is the number of edge nodes) which is significantly smaller than N2 in the full-mesh approach. Our algorithms also can support asymmetric link state parameters which are common in practice, while many previous algorithms such as the spanning tree approach can be applied only to networks with symmetric link state parameters. Experimental results show that the performance of our shufflenet algorithm is close to that of the full-mesh approach in terms of the accuracy of bandwidth and delay information, with only a much smaller amount of information. On the other hand, although it is not as good as the shufflenet approach, the de Bruijn algorithm also performs far better than the star approach which is one of the most widely accepted schemes. The de Bruijn algorithm needs smaller computational complexity than most previous algorithms for asymmetric networks, including the shufflenet algorithm.

The notion of a logically routed network was developed to overcome the bottlenecks encountered during the design of a large purely optical network. In the last few years, researchers have proposed the use of torus. Perfect shuffle, hypercube, de Bruijn graph, Kautz graph, and Cayley graph as an overlay structure on top of a purely optical network. All these networks have regular structures. Although regular structures have many virtues, it is often difficult in a realistic setting to meet these stringent structural requirements. In this paper, we propose generalized multimesh (GM), a semiregular structure, as an alternate to the proposed architectures. In terms of simplicity of interconnection and routing, this architecture is comparable to the torus network. However, the new architecture exhibits significantly superior topological properties to the torus. For example, whereas a two-dimensional (2-D) torus with N nodes has a diameter of /spl Theta/(N/sup 0.5/), a generalized multimesh network with the same number of nodes and links has a diameter of /spl Theta/(N/sup 0.25/). In this paper, we also introduce a new metric, flow number, that can be used to evaluate topologies for optical networks. For optical networks, a topology with a smaller flow number is preferable, as it is an indicator of the number of wavelengths necessary for full connectivity. We show that the flow numbers of a 2-D torus, a multimesh, and a de Bruijn network, are /spl Theta/(N/sup 1.5/), /spl Theta/(N/sup 1.25/), and /spl Theta/(N log N), respectively, where N is the number of nodes in the network. The advantage of the generalized multimesh over the de Bruijn network lies in the bet that, unlike the de Bruijn network, this network can be constructed for any number of nodes and is incrementally expandable.

We present a technique for determining the absolute x, y-location of a robot in a workspace. The floor of the workspace is tiled with black and white squares in a pattern based on a variant of a de Bruijn sequence. The black/white pattern on the floor is read by a modest number of inexpensive, discrete optical sensors, and a simple algorithm determines the position of the robot.

An efficient implementation of the D-homomorphism for generating de Bruijn (1946) sequences is presented. The number of exclusive-or operations required to generate the next bit for de Bruijn sequences of order n from a de Bruijn function of order k is shown to be approximately k(2/sup W(n-k)/-1), where W(r) is the number of one's in the binary representation of r: therefore, the number of required operations can be reduced to k if the de Bruijn function is selected appropriately. As an application, the stream cipher is indicated.

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 area. Some new results are also presented, in particular, it is shown that for each interval of length 2/sup [log n]+1/ in the above range, there exist binary de Bruijn sequences of length 2/sup n/ with linear complexity in the interval.

"For original paper see R. Melhem, ibid., vol.56, p.502-10, (2007)". Recently, Melhem presented a "new" class of low-diameter interconnection (LDI) networks, (IEEE Trans. computers, Vol. 56, No. 4, pp. 502-510). We note that LDI networks are the same as the previously known generalized de Bruijn graphs, point out an error in the decomposition of LDI networks into permutations, and find that the correct decomposition scheme is an instance of arc coloring for coset graphs. Hence, we pursue a number of general results on arc coloring of coset graphs that can be applied to this particular decomposition problem as well as within many other contexts, including complete arc coloring and normality of coset graphs.

We propose TDM/TWDM de Bruijn networks and ShuffleNets by utilizing small all-optical dilated slipped banyan networks, DSBs (Thompson, 1991). The proposed networks require fewer switches than DSBs, and smaller numbers of wavelengths than WDM de Bruijn networks and ShuffleNets. Furthermore, only one fixed-wavelength transmitter and one fixed-wavelength receiver are required for each node.

We present a distributed network-level algorithm that constructs a cycle in a d-ary De Bruijn multiprocessor network in the presence of an arbitrary number of node failures. When the number of faults f does not exceed d-1 a cycle of length at least d/sup n/-nf-1 can always be found in O(n) steps in a network of size d/sup n/.

We consider the problems of routing and sorting on a de Bruijn network. First, we show that any deterministic oblivious routing scheme for permutation routing on a d-ary de Bruijn network with N=d/sup n/ nodes, in the worst case, will take /spl Omega/(/spl radic/N) steps under the single-port model. This improves the existing lower bounds provided d is not a constant. We also show that the lower bound is indeed a tight one. Second, we present a deterministic nonoblivious permutation routing algorithm which runs in O(d.n/sup 2/) time on a d-ary de Bruijn network with N=d/sup n/ nodes. This algorithm is currently the fastest known nonoblivious deterministic routing algorithm for de Bruijn networks of arbitrary degree. Finally, we present an efficient general sorting algorithm for the de Bruijn networks of arbitrary degree. This algorithm is the best sorting algorithm known so far. It runs in O((log d).d.n/sup 2/) time for directed de Bruijn network with d/sup n/ nodes, degree d, and diameter n. As a corollary, we show that on a binary de Bruijn network of Nnodes, our sorting scheme requires at most 2 log/sup 2/ Nsteps.

Proposes de Bruijn graphs as logical topologies for multihop lightwave networks. After deriving bounds on the throughput and delay performance of any logical topology, the authors compute the throughput and delay performance of de Bruijn graphs for two different routing schemes and compare it with their bounds and the performance of shufflenets. For a given maximum nodal in- and out-degree and average number of hops between stations, a logical topology based on a de Bruijn graph can support a larger number of stations than a shufflenet and this number is close to the maximum that can be supported by any topology. The authors also propose de Bruijn graphs as good physical topologies for wavelength routing lightwave networks consisting of all-optical routing nodes interconnected by point-to-point fiber links. The worst-case loss experienced by a transmission is proportional to the maximum number of hops (diameter). For a given maximum nodal in- and out-degree and diameter, a physical topology based on a de Bruijn graph can support a large number of stations using a relatively small number of wavelengths. >

A graph has spread (m, k, l) if for any m+1 distinct nodes x, y/sub 1/, . . ., y/sub m/ and m positive integers r/sub 1/, . . ., r/sub m/, such that Sigma /sub i/r/sub i/=k, there exist k node-disjoint paths of length at most 1 from x to the y/sub i/, where r/sub i/ of them end at y/sub i/. This concept contains, and is related to many important concepts used in communications and graph theory. The authors prove an optimal general theorem about the spreads of digraphs generated by line digraph iterations. Useful graphs, like the de Bruijn and Kautz digraphs, can be thus generated. The theorem is applied to the de Bruijn and Kautz digraphs to derive optimal bounds on their spreads, which implies previous results and resolves open questions on their connectivity, diameter, k-diameter, vulnerability, and some other measures related to length-bound disjoint paths. >

A method of embedding a ring in a d-ary de Bruijn multiprocessor network in the event of multiple node (processor) failures is presented. In particular, the algorithm guarantees that a (2/sup n/-n-1)-node ring will be found in a binary de Bruijn network with a single faulty node, where 2/sup n/ is the total number of nodes in the network. It is also shown that a (d/sup n/-1)-node ring can always be found in the presence of d-1 link failures, when d is a prime power and the network contains d/sup n/ nodes. The latter is accomplished by constructing d-1 edge-disjoint cycles each of length d/sup n/-1. A modification of the graph that allows it to admit a Hamiltonian cycle in the event of d-1 edge failures is also discussed. >

This paper presents a concise and efficient implementation of a method of producing De Bruijn sequences. The implementation is based on a recursive method due to A. Lempel (1970). We provide code for a function that for each pair of integers n/spl ges/2 and 0/spl les/x

Order n modified de Bruijn sequences are created by removing a single zero from the longest run of zeros in period 2/sup n/ de Bruijn sequences. The M sequences are then the natural undisguised linear subset of modified de Bruijn sequences. Theorems are given on the linear spans of modified de Bruijn sequences and data are presented for 4 >

The aim of this note is to present some counterexamples to the results in the paper by Du, Lyuu, and Hsu (see ibid., vol.42, no.5, p.612-16, May 1993).

Corrections to the galley proof of the above-titled paper by the authors (see ibid., vol.38, no.4, p.567-81 (1989)) that were inadvertently omitted from the published paper are given. >

It is shown that the binary de Bruijn multiprocessor network (BDM) can solve a wide variety of classes of problems. The BDM admits an N-node linear array, an N-node ring, (N-1)-node complete binary trees, ((3N/4)-2)-node tree machines, and an N-node one-step shuffle-exchange network, where N (=2/sup k/, k an integer) is the total number of nodes. The de Bruijn multiprocessor networks are proved to be fault-tolerant as well as extensible. A tight lower bound of the VLSI layout area of the BDM is derived; a procedure for an area-optimal VLSI layout is also described. It is demonstrated that the BDM is more versatile than the shuffle-exchange and the cube-connected cycles. Recent work has classified sorting architectures into (1) sequential input/sequential output, (2) parallel input/sequential output, (3) parallel input/parallel output, (4) sequential input/parallel output, and (5) hybrid input/hybrid output. It is demonstrated that the de Bruijn multiprocessor networks can sort data items in all of the abovementioned categories. No other network which can sort data items in all the categories is known. >

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 sequence of span n and produce one of span n+1 . We give a more general recursive construction which takes two de Brnijn sequences of span n and produces a de Bruijn sequence of span n+1 . In addition, for a special case of the construction, the complexity (shortest linear recursion that generates the sequence) of the resulting sequence is determined in terms of the complexities of the ingredient sequences. In particular, de Bruijn sequences of span n+1 with maximum complexity 2^{(n+1)}-1 are obtained from maximum complexity sequences of span n . Reverse-complementary de Bruijn sequences are also considered.

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.

Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates 2^{k \cdot g(n,k) full cycles of length 2^{n} , using 3n + k \cdot g(n, k) bits of storage, where k is a free parameter in the range 1 \leq k \leq 2^{((n-4)/2)} , and g(n, k) is of the order of n - 2 \log k . The second algorithm generates about 2^{n^{2}/4} full cycles of length 2^{n} , using about n^{2}/2 bits of storage. In both algorithms, the time required to produce the next bit from the last n bits is close to n . A possible application to the construction of stream ciphers is indicated.

It is well known that the linear complexity of a de Bruijn sequence S of length 2^{n} is bounded below by 2^{n- 1} + n for n \geq 3 . It is shown that this lower bound is attainable for all n .

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 (2^{2k} - 1,2k) \equiv 0 \pmod{l6} . It is also shown that \gamma (c, n) \equiv 0 \pmod{4} for all c , and n \geq 3 such that cn is even.

A homomorphism of the de Bruijn graph that maps a graph of order n onto one of order n-1 and its applications to the design of nonsingular feedback shift registers are discussed. The properties preserved under this mapping suggest a new design technique whose main advantage is due to the fact that the problem of designing a desired n-stage shift register may be reduced to a problem of order n-1 or less. Among the results obtained is a recursive formula for a feedback function that generates a cycle of maximum length.