首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
3.
We consider words over a finite alphabet with certain uniqueness properties (a subsequence of length k does not occur more than once) and distance properties (at least j other symbols separate the occurrence of the same symbol). The maximal length of these words is realised by linear de Bruijn sequences with certain forbidden subsequences. We prove the existence of these maximal sequences.  相似文献   

4.
5.
Define the directed genus, Γ(G), of an Eulerian digraph G to be the minimum value of p for which G has a 2-cell embedding in the orientable surface of genus p so that every face of the embedding is bounded by a directed circuit in G. The directed genus of the de Bruijn graph Dn is shown to be
  相似文献   

6.
广义de Bruijn和Kautz有向图的距离控制数   总被引:1,自引:0,他引:1  
对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?).图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者.本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件.从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= .在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .  相似文献   

7.
The shortest linear recursion which generates a de Bruijn sequence is defined to be the complexity of the sequence. It is shown that the complexity of a binary de Bruijn sequence of span n is bounded by 2n ? 1 from above and 2n ? 1 + n from below. Results on the distribution of the complexities are also presented.  相似文献   

8.
We determine exact values for the k-error linear complexity L k over the finite field of the Legendre sequence of period p and the Sidelnikov sequence of period p m  − 1. The results are
for 1 ≤ k ≤ (p m  − 3)/2 and for k≥ (p m  − 1)/2. In particular, we prove
  相似文献   

9.
We analyse a binary cyclotomic sequence constructed via generalized cyclotomic classes by Bai et al. (IEEE Trans Inforem Theory 51: 1849–1853, 2005). First we determine the linear complexity of a natural generalization of this binary sequence to arbitrary prime fields. Secondly we consider k-error linear complexity and autocorrelation of these sequences and point out certain drawbacks of this construction. The results show that the parameters for the sequence construction must be carefully chosen in view of the respective application.   相似文献   

10.
Klapper (1994) showed that there exists a class of geometric sequences with the maximal possible linear complexity when considered as sequences over $GF(2)$, but these sequences have very low linear complexities when considered as sequences over $GF(p)(p$ is an odd prime). This linear complexity of a binary sequence when considered as a sequence over $GF(p)$ is called $GF(p)$ complexity. This indicates that the binary sequences with high $GF(2)$ linear complexities are inadequate for security in the practical application, while, their $GF(p)$ linear complexities are also equally important, even when the only concern is with attacks using the Berlekamp-Massey algorithm [Massey, J. L., Shift-register synthesis and bch decoding, {\it IEEE Transactions on Information Theory}, {\bf 15}(1), 1969, 122--127]. From this perspective, in this paper the authors study the $GF(p)$ linear complexity of Hall''s sextic residue sequences and some known cyclotomic-set-based sequences.  相似文献   

11.
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.  相似文献   

12.
In this article, we determine when the large generalized de Bruijn cycles are Hamiltonian. These digraphs have been introduced by Gómez, Padró and Pérennes as large interconnection networks with small diameter and they are a family of generalized cycles. They are Kronecker products of generalized de Bruijn digraphs and dicycles.  相似文献   

13.
二元de Bruijn网络的可靠性分析   总被引:1,自引:0,他引:1  
欧见平 《数学研究》2004,37(2):182-187
证明了二元de Bruijn网络是极大限制边连通的,并且它们的最小限制边割只能分离一条孤立边或者一个三角形. 利用此结果分析了二元de Bruijn网络的可靠性,确定了它们的可靠多项式的前四项系数.  相似文献   

14.
N.G. de Bruijn carried out fundamental work on integers having only small prime factors and the Dickman–de Bruijn function that arises on computing the density of those integers. In this he used his earlier work on linear functionals and differential–difference equations. We review his relevant work and also some later improvements by others.  相似文献   

15.
We prove the logical independence of a complexity-theoretic and a statistical randomness property of sequences over a finite field. The two properties relate to the linear complexity profile and to the ∞-distribution of sequences, respectively. The proofs are given by constructing counterexamples to the presumed logical implications between these two properties.  相似文献   

16.
A result by Van de Ven characterizes linear subspaces as the only closed submanifolds X ? ? N for which the normal bundle exact sequence splits. We show that X is linear assuming only the splitting of the same exact sequence when restricted to some curve contained in X .  相似文献   

17.
p元扩展序列的线性复杂度   总被引:1,自引:0,他引:1  
给出了由周期为p~m-1的p元序列导出的周期为p~(em)-1的p元扩展序列的线性复杂度.作为一个实例,计算了扩展Legendre序列的线性复杂度.  相似文献   

18.
Let Bn be the binary de Bruijn digraph of order n and W the quotient set of the set of vertices of Bn with respect to the equivalence relation of rotation. Let G be the graph which has W as the set of vertices and in which two elements C and H are adjacent when there exist a vertex v of C and a vertex u of H such that (v,u) is an arc of Bn. Recently the problem of establishing whether the graph G has a perfect matching was posed. In this paper we answer in the positive to this problem in the case of n odd.  相似文献   

19.
Engin Özkan  İpek Altun 《代数通讯》2013,41(10):4020-4030
In this article, we find elements of the Lucas polynomials by using two matrices. We extend the study to the n-step Lucas polynomials. Then the Lucas polynomials and their relationship are generalized in the paper. Furthermore, we give relationships between the Fibonacci polynomials and the Lucas polynomials.  相似文献   

20.
Let x be an m-sequence, a maximal length sequence produced by a linear feedback shift register. We show that x has maximal subword complexity function in the sense of Allouche and Shallit. We show that this implies that the nondeterministic automatic complexity AN(x) is close to maximal: n2?AN(x)=O(log2n), where n is the length of x. In contrast, Hyde has shown AN(y)n2+1 for all sequences y of length n.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号