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

de Bruijn序列是一类最长的非线性伪随机序列。本文给出了2元de Bruijn序列的一种新的生成算法,该算法能产生2~(δ·N(n,s))个n级de Bruijn序列,其中,0≤s≤2 (n-7)/2;当2~(l-1)相似文献   

扩展de Bruijn图的生成树和广播

扩展de Bruijn图EB(d,m;h1,h2,…,hk)是de Bruijn图的一种推广,它是一种再要的网络互连结构.本文主要研究扩展de Bruijn图中的有根生成树,证明了对任何顶点u和任意整数r:2≤r≤d,扩展de Bruijn图都有以u为根且深度为[log(?),d]·max{hi:1≤i≤k}的rk-叉生成树,并由此获得了扩展de Bruijn图的广播时间的上界.     

有限域上与仿射多项式有关的一些多项式的可约性

在这篇文章中,研究了有限域上一些与仿射多项式有关的多项式的可约性.对于有限域Fp上不是xppt-x-1的仿射三项式,得到了这些三项式的一个明确的因式.完全确定了多项式g(xps-ax-b)在Fp[x]中的分解,这里g(x)是Fp[x]中一个不可约多项式.证明了Fp上次数相同的不可约多项式的全体可以构成一个正则图.同时给出了多项式g(xqs-x-b)在Fp[x]不可约因式的个数公式,这里g(x)是Fp上一个不可约多项式.     

一种生成k元de Bruijn序列的算法

目前,已有很多生成全长的移位寄存器序列(又称de Bruijn序列)的方法,他们的共同思想是先通过某种简单的移位寄存器生成所有不同的圈,然后再把它们联接为一个全长圈。在这篇文章中,我们先定义一个项链的周期约化,进而提出一种新的生成任意k元de Bruijn序列的方法。这种方法把这类算法从域推广到整数模上,而且在n≥3和k≥4时,这种算法能生成一大批de Bruijn序列。     

产生 M 序列的一个递推算法

§1.引言M 序列又称 de Bruijn 序列,是一类具有最长周期的非线性移位寄存器序列。本文研究产生 M 序列的算法。早在70年代万哲先等对构造 M 序列的方法已有系统的研究。此后有一系列的文章研究 M 序列的构造问题。最近 Fredricksen 对这方面的工作给出了一个很好的综述。产生 M 序列的一个常用方法是先由一个较简单的移位寄存器产生许多短圈,再用并圈法将这些短圈合并起来构成 M 序列。如在[1,6]中就已给出过一些将 n 级纯轮换移位寄存器(简记为 PCK_n)和 n 级补轮换移位寄存器(简记为 CCR_n)产生的圈合并为 M 序列的方法。与[1—7]不同,Fredricksen 给出一个将 PCR_n 产生的圈合并为 M 序列的递推算法。最近 Etzion 和 Lempe 在 Fredricksen 算法的基础     

二元de Bruijn网络的可靠性分析

证明了二元de Bruijn网络是极大限制边连通的,并且它们的最小限制边割只能分离一条孤立边或者一个三角形. 利用此结果分析了二元de Bruijn网络的可靠性,确定了它们的可靠多项式的前四项系数.     

F_q[x]上的素数定理和Dirichlet定理及最小范数不可约多项式

讨论了F_q[x]上的zeta函数和L函数的解析性质,并在不假定黎曼猜想的情况下,导出了F_q[x]上的多项式环及其算术级数中不可约多项式的分布.然后,通过一系列的技术性处理,给出了算术级数中不可约多项式的最小范数的估计.成功地把素数定理及Dirichlet定理推广到了F_q[x]中,最重要的是,对应于最小素数问题,得到的最小范数的估计值本质上要比有理整数环上假定黎曼猜想情况下所推得的结果还好.     

Fq[x]上的素数定理和Dirichlet定理及最小范数不可约多项式

讨论了Fq[x]上的zeta函数和L函数的解析性质,并在不假定黎曼猜想的情况下,导出了Fq[x]上的多项式环及其算术级数中不可约多项式的分布.然后,通过一系列的技术性处理,给出了算术级数中不可约多项式的最小范数的估计.成功地把素数定理及Dirichlet定理推广到了Fq[x]中,最重要的是,对应于最小素数问题,得到的最小范数的估计值本质上要比有理整数环上假定黎曼猜想情况下所推得的结果还好.     

M 序列反馈函数的构造方法Ⅲ

二元域 F_2上周期为2~n 的 n 级 M 序列(即最大长度移位寄存器序列)具有较好的随机性.实际构造这种序列及其反馈函数(简称 M 馈)历来很受重视.近几年来,人们试图从一线性移位寄存器出发来构造 M 馈.利用一个 n 次本原多项式,J.Mykkeltveit 等人构造了2~n-2个 n+1级 M 馈,M.K.siu 与 P.Tong 构造出2~(n+1)个 n+2级 M 馈,F.Hemmati 又构造出2~(5n)个 n+2级 M 馈.B.Arozi 用两个次数分别为 m_1和 m_2的本原多项式构造出一个 m_1+m_2级 M 馈,其中(m_1,m_2)=1.我们在[1]和[2]中提供了几种直接构造 M 馈的方法,从任一非奇异移存器出发,可以直接写出一大批 M 馈.本文是[1]和[2]的继续,通过对几类线性移存器因子关联图的详细分析,构造出几类新的 M 馈.在§2中,用两个互反的 n 次本原多项式构造出2~(?)(2~(n-2)-     

多个移位寄存器级联产生的互钟控序列

本文在文[1]的基础上,提出了两种互钟控序列模型,即Ⅰ型 LSR[k,d]~l 序列和Ⅱ型 LSR[k,d]~l 序列,并对Ⅱ型 LSR[k,d]~l 序列证明了它的极小多项可以达到 h(x~(q_1…q_l)),复杂度为 n·q_1…q_l,其中 h(x)为 GF(2)上某一 n 次不可约多项式,q_1、q_2、…,q_l 分别为l 个参加 LSR[k,d]~l 运算的 LSR 序列之周期.     

A recursive construction of nonbinary de Bruijn sequences

This paper presents a method to find new de Bruijn sequences based on ones of lesser order. This is done by mapping a de Bruijn cycle to several vertex disjoint cycles in a de Bruijn digraph of higher order and then connecting these cycles into one full cycle. We present precise formulae for the locations where those cycles can be rejoined into one full cycle. We obtain an exponentially large class of distinct de Bruijn cycles. This method generalizes the Lempel construction of binary de Bruijn sequences as well as its efficient implementation by Annextein.     

Similarity to symmetric matrices over fields which are not formally real

We show that a matrix is similar to a symmetric matrix over a field of characteristic 2 if and only if the minimum polynomial of the matrix is not the product of distinct irreducible polynomials whose splitting fields are inseparable extensions. When the field is not of characteristic 2, a known theorem is generalized by considering k, the number of elementary divisors of odd degree of the n × n A: If -1 is a sum of 2^v squares and n differs from a multiple of 2^{v + 1} by at most ±k, then A is similar to a symmetric matrix.     

广义Carmichael数

设n是一个合数,Z_n表示模n的剩余类环,r(x)∈Z_n[x]是一个首一的k(>0)次不可约多项式。本文引入n是k阶摸r(x)的Carmichael数的定义,全体这样的数记为集C_(k,r)(x),由此给出k阶Carmichael数集:C_k={∪C_(k,r)(x)|r(x)过全体Z_n上的首一k次不可约多项式}。显然C_1表示通常的Carmichael数集。作者得到了n∈C_(k,r(x))的一个充要条件,进而得到n∈C_k的一个充要条件及n∈C_2的一个更易计算的充要条件,还证明了C_1(?)C_2以及|C_2|=∞。     

有关广义中心三项式系数的3个超同余式

设b,c为整数,定义广义中心三项式系数Tn(b,c)=[xn](x2+bx+c)n=「n/2」∑k=0(n2k)(2kk)bn-2kck(n∈N={0,1,…}),这里[xn]P(x)表示多项式P(x)中xn项的系数.特别地,中心Delannoy多项式Dn(x)=Tn(2x+1,x2+x)(n ∈ N),中心三项式系数...     

哈密顿图的无符号拉普拉斯谱半径条件

令A(G)=(a_(ij))_(n×n)是简单图G的邻接矩阵,其中若v_i-v_j,则a_(ij)=1,否则a_(ij)=0.设D(G)是度对角矩阵,其(i,i)位置是图G的顶点v_i的度.矩阵Q(G)=D(G)+A(G)表示无符号拉普拉斯矩阵.Q(G)的最大特征根称作图G的无符号拉普拉斯谱半径,用q(G)表示.Liu,Shiu and Xue[R.Liu,W.Shui,J.Xue,Sufficient spectral conditions on Hamiltonian and traceable graphs,Linear Algebra Appl.467(2015)254-255]指出:可以通过复杂的结构分析和排除更多的例外图,当q(G)≥2n-6+4/(n-1)时,则G是哈密顿的.作为论断的有力补充,给出了图是哈密顿图的一个稍弱的充分谱条件,并给出了详细的证明和例外图.     

On an iterated construction of irreducible polynomials over finite fields of even characteristic by Kyuregyan

We deal with the construction of sequences of irreducible polynomials with coefficients in finite fields of even characteristic. We rely upon a transformation used by Kyuregyan in 2002, which generalizes the Q-transform employed previously by Varshamov and Garakov (1969) as well as by Meyn (1990) for the synthesis of irreducible polynomials. While in the iterative procedure described by Kyuregyan the coefficients of the initial polynomial of the sequence have to satisfy certain hypotheses, in the present paper these conditions are removed. We construct infinite sequences of irreducible polynomials of nondecreasing degree starting from any irreducible polynomial.     

On five-diagonal Toeplitz matrices and orthogonal polynomials on the unit circle

This paper deals with modifications of the Lebesgue moment functional by trigonometric polynomials of degree 2 and their associated orthogonal polynomials on the unit circle. We use techniques of five-diagonal matrix factorization and matrix polynomials to study the existence of such orthogonal polynomials.Dedicated to Prof. Luigi Gatteschi on his 70th birthdayThis research was partially supported by Diputación General de Aragón under grant P CB-12/91.     

涉及导数与差分的亚纯函数唯一性

设f,g是两个非常数亚纯函数,a是一个非零有穷复数,n≥5是一个正整数.若[f(z)]~n与[g(z)]~n CM分担a,f(z)与g(z) CM分担∞,且N_(1))(r,f)=S(r,f),则或者f(z)三tg(z),其中t~n=1;或者f(z)g(z)≡t,其中t~n=a~2.由此改进了涉及导数与差分的一些亚纯函数唯一性的结果.