Linear spans of modified de Bruijn sequences

Order n modified de Bruijn sequences are created by removing a single zero from the longest run of zeros in period 2ⁿ 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⩽n⩽6     

一种de Bruijn序列的高效生成算法

文中提出用计算机搜索算法，利用真值表后继状态的互补对称性，快速生成任意级数的全部de Brui jn序列的通用方法，并对算法进行改进，以加快de Brui jn序列的生成时间。文中详细说明了对应的计算机程序设计方法，最后给出实验数据，验证算法的可行性与快速性。此算法方案可以作为设计序列密码的密钥发生器，亦可以用于通信领域，具有一定的实用性．     

A generalized recursive construction for de Bruijn sequences

This paper is concerned with the construction of de Bruijn sequences of spann--binary sequences of period2^{n}in which every binaryn-tuple appears as somenconsecutive 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 spannand produce one of spann+1. We give a more general recursive construction which takes two de Brnijn sequences of spannand produces a de Bruijn sequence of spann+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 spann+1with maximum complexity2^{(n+1)}-1are obtained from maximum complexity sequences of spann. Reverse-complementary de Bruijn sequences are also considered.     

A method for constructing decodable de Bruijn sequences

We present two related methods of construction for de Bruijn (1946) sequences, both based on interleaving “smaller” de Bruijn sequences. Sequences obtained using these construction methods have the advantage that they can be “decoded” very efficiently, i.e., the position within the sequence of any particular “window” can be found very simply. Sequences with simple decoding algorithms are of considerable practical importance in position location applications     

Construction of de Bruijn sequences of minimal complexity

It is well known that the linear complexity of a de Bruijn sequenceSof length2^{n}is bounded below by2^{n- 1} + nforn geq 3. It is shown that this lower bound is attainable for alln.     

修正de Bruijn序列的重量和线性复杂度研究

n级修正de Bmijn序列，就是从n级de Bmijn序列所有的2“个状态中去掉全0状态而得到的移位寄存器序列。为深入了解修正de Bmijn序列，研究了修正de Bmijn序列的重量和线性复杂度，提出了相关的定理并进行了证明，并给出了5—6级修正de Bmijn序列的线性复杂度和重量的分布统计数据。     

Linear complexity of de Bruijn sequences-old and new results

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ⁿ is bounded below by 2^n-1+n and above by 2^n-1 for n⩾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^{[log n]+1} in the above range, there exist binary de Bruijn sequences of length 2ⁿ with linear complexity in the interval     

On the distribution of de Bruijn sequences of given complexity

The distributiongamma (c, n)of de Bruijn sequences of ordernand linear complexitycis investigated. It is shown that forn geq 4, gamma (2^{n} - 1, n) equiv 0 pmod{8}, and fork geq 3, gamma (2^{2k} - 1,2k) equiv 0 pmod{l6}. It is also shown thatgamma (c, n) equiv 0 pmod{4}for allc, andn geq 3such thatcnis even.     

On the distribution of de Bruijn CR-sequences (Corresp.)

It is shown that the number of de Bruijn sequences of ordernand linear complexitycis not a multiple of four for everynandc.     

修正de Bruijn序列的自相关特性和线性复杂度

n级修正de Bruijn序列,就是从n级de Bruijn序列所有状态中去掉全0状态而得到周期为2n-1的移位寄存器序列。文章讨论了修正de Bruijn序列的伪随机特性,主要研究了修正deBruijn序列的自相关特性和线性复杂度,给出了4-6级修正de Bruijn序列旁瓣特性和线性复杂度的统计数据。     

Complexity and autocorrelation properties of a class of de Bruijn sequences

The complexity and autocorrelation properties of de Bruijn sequences generated by an algorithm of Etzion and Lempel are investigated. While the autocorrelation results deviate from the behaviour expected for truly random sequences, the complexity distributions are very encouraging. Specifically, the minimum complexities are significantly greater than those of other de Bruijn sequences.     

产生2元de Bruijn序列的一个新算法

２元ｎ级ｄｅＢｒｕｉｊｎ序列是由ｎ级移位寄存器产生的周期为２ｎ的移位寄存器序列，给出了２元ｄｅＢｒｕｉｊｎ序列的一个新的生成算法，该算法能生成２ｓ·ｇ（ｎ，ｓ）个ｎ级如ｄｅ　Ｂｒｕｉｊｉｎ序列，其中，０≤ｓ≤２（ｎ－７）／３；当 ２ｌ－１＜ｓ≤２Ｌ时，ｇ（ｎ，ｓ）＝ｎ－３Ｌ－６－［（ｎ－２Ｌ－６）／（Ｌ＋１）］。     

Constructive method for synthesis of complete classes of multilevel de Bruijn sequences

Two new presentation forms of multilevel de Bruijn sequences (BS) have been introduced as geometric and algebraic structures. The attractive and practical properties of these structures have been found. This formed the basis for proposing a constructive method for the synthesis of generating and complete classes of BS. It has been shown that the application of the found classes of quaternary BS in encryption ensures a two-fold reduction of the memory space required for storing the cryptographic substitution boxes (S-boxes).     

Ad hoc networks beyond unit disk graphs

In this paper, we study an algorithmic model for wireless ad hoc and sensor networks that aims to be sufficiently close to reality as to represent practical realworld networks while at the same time being concise enough to promote strong theoretical results. The quasi unit disk graph model contains all edges shorter than a parameter d between 0 and 1 and no edges longer than 1. We show that—in comparison to the cost known for unit disk graphs—the complexity results of geographic routing in this model contain the additional factor 1/d ². We prove that in quasi unit disk graphs flooding is an asymptotically message-optimal routing technique, we provide a geographic routing algorithm being most efficient in dense networks, and we show that classic geographic routing is possible with the same asymptotic performance guarantees as for unit disk graphs if .

LMMSE turbo equalization based on factor graphs

In this paper, a vector-form factor graph representation is derived for intersymbol interference (ISI) channels. The resultant graphs have a tree-structure that avoids the short cycle problem in existing graph approaches. Based on a joint Gaussian approximation, we establish a connection between the LLR (log-likelihood ratio) estimator for a linear system driven by binary inputs and the LMMSE (linear minimum mean-square error) estimator for a linear system driven by Gaussian inputs. This connection facilitates the application of the recently proposed Gaussian message passing technique to the cycle-free graphs for ISI channels. We also show the equivalence between the proposed approach and the Wang-Poor approach based on the LMMSE principle. An attractive advantage of the proposed approach is its intrinsic parallel structure. Simulation results are provided to demonstrate this property.     

Multiresolution permutation filter implementations based on acyclic connected graphs

Permutation filters are a broad class of nonlinear selection filters that utilize the complete spatial and rank order information of observation samples. This use of joint spatial-rank information has proven useful in numerous applications. The application of permutation filters, however, is limited by the factorial growth in the number of spatial-rank orderings. Although M-permutation filters have been developed to address the growth in orderings, their a priori uniform selection of samples is not appropriate in most cases. Permutation filter implementations based on acyclic connected graphs provide a more general approach that allows the level of ordering information utilized to automatically adjust to the problem at hand. In addition to developing and analyzing graph implementations of permutation filters this paper presents a LNE based optimization of the graph structure and filter operation. Simulation results illustrating the performance of the optimization technique and the advantages of the graph implementation are presented.     

Representations and routing for Cayley graphs [computer networks]

It is shown that all finite Cayley graphs can be represented by generalized chordal rings (GCR). An example Borel Cayley graph is used to illustrate the generation of GCR representations. A sufficient condition is given for the representation of a Cayley graph as a chordal ring (CR). With the integer labeling of GCR representations, a straightforward, progressive routing algorithm based on table look-up is summarized     

Impact of Reflection Induced Noise on AM-VSB CATV Lightwave Systems

1 Introduction The lightwave CATV systems recently can provide the extremely high-fidelity transmission required by the AM-VSB video format. These systems can also provide the satisfactory performance of CNR, CSO and CTB. Such performance has been realize…