有限链环上循环码的研究

设R为有限链环,定义从Rn到 的Gray映射 ,给出Gray映射 的一个性质。利用Gray映射的性质研究有限链环R上任意长循环码的Gray象。证明有限链环R上长为n的码C是循环码当且仅当它的Gray象 是有限域Fp上指标为pe-1长为npe-1的准循环码。     

环上Fpk+uFpk的循环码*

利用Gray映射Φ的性质,研究了交换环R=Fpk+uFpk上任意长的循环码。其中p是素数,k是一给定的正整数。证明了环R上长为n的码C是循环码当且仅当Φ(C)是Fpk上指标为pk长为npk的准循环码。特别地,环R上长为n的线性循环码的Gray像是有限域Fpk上指标为pk长为npk的线性准循环码。     

环Fp+uFp+vFp上的(1+u+v)-循环码

常循环码是一类重要的线性码,由于其纠错性能易于分析,因而广泛应用于实践中,同时,利用有限环上常循环码还可以直接构造最优线性码。定义了有限非链环[Fp+uFp+vFp]上[(1+u+v)]-循环码的相关概念,讨论了其生成多项式;引入了一种新的Gray映射[?],证明了该环上[(1+u+v)]-循环码在此Gray映射[?]下的[p]元象是一个长为[2pn]的2-准循环码,并由此构造出了两个最优二元准循环码。     

环[F2+uF2+vF2]上的[(1+v)-]常循环码

研究了环[R=F2+uF2+vF2] 上的[(1+v)-]常循环码。利用环[R]上奇长循环码的生成元来刻画环[R]上奇长的[(1+v)-]常循环码,进而给出了[Rn]到[(F2+uF2)2n]的一个广义Gray映射[φ],证明了环[R]上的[(1+v)-]常循环码[C]在[φ]下的广义Gray像[φ(C)]是环[F2+uF2]上的循环码。     

环F2+uF2+u2F2上的(1+u+u2）—循环码*

通过定义一种从环F2+uF2+u2F2到域F2上新的Gray映射,将环F2+uF2+u2F2上的线性(1+u+u2)—循环码等距映射成域F2的线性循环码;进一步又给出了在码长n=3(mod 4)时环F2+uF2+u2F2上的线性(1+u+u2)—循环码的Gray象的生成多项式,这对构造新的好码具有重要意义。     

F2+uF2和Z4上循环码的Gray象

利用Gray映射Φ的性质,研究了环F₂+uF₂和Z₄上的任意长循环码。证明了环F₂+uF₂上任意长码是循环码当且仅当它的Gray象是域F2上的准循环码,得到了Z₄上任意长码是循环码的一个充分必要条件。特别的,环F₂+uF₂上长为n的线性循环码的Gray象是域F₂上指标为2长为2n的线性准循环码,环Z₄上长为n的线性循环码的Gray象是域F₂上指标为2长为2n的准循环码。     

重根循环码

在循环码理论中,通常要求码字的长度n与有限域Fq的特征p互素,即(n,p)=1,这样才能保证循环码的生成多项式g(x)没有重根。使用离散傅里叶变换（DFT）,得到长度为N=psn的q—元重根循环码的谱表示和重根循环码的结构,这对重根循环码的构造及译码有重要作用。     

环F2+uF2上长为2e的重根循环码与(1+u)-循环码的秩

通过对环F2 uF2上长为2e的重根循环码与(1 u)-循环码结构的讨论,具体给出了它们的秩和极小生成元集.这对确定码的距离分布以及译码均有重要的意义.     

计算机循环码校验及其实现

在各种数据信息传递中，为了确保其正确性，都要对传递的信息进行检错纠错。但在几十种检错方案中，检错能力最佳，效果最显著的要算循环码校验，本文着重介绍循环码校验的原理，以及循环码校验所能检错的范围和实现循环码校验的方法。     

一种新的循环码编译码设计

从循环的原理出发,讨论循环码编译码系统的特点。以一个（7,4）循环码为例,使用硬件描述语言VHDL对该系统进行了设计,能实现循环码以及一位错码的纠错译码。     

环F2+uF2+u2F2上的线性码及其Gray像

记R=F₂+uF₂+u²F₂,R₁=F₂+uF₂,定义了从Rⁿ到F³ⁿ₂的Gray映射Ф以及从Rⁿ₁到Rⁿ的映射f。通过对环R上线性码C的生成矩阵的研究,给出了线性码C的对偶码C^⊥和Gray像Ф（C）的生成矩阵,并且Ф（C）与Ф（C^⊥）是F₂上的对偶码。通过映射f将环R₁上的线性码与环R上的一类线性码对应起来。     

基于三个自对偶码的S-链和量子码构造

用随机搜索算法和典型群理论,研究了双循环形自对偶码D3,D4和D5的对偶距离d⊥满足3≤d⊥≤7的子码,确立了这些子码构成的自正交子码链及它们的对偶构成的S-链。利用得到的S-链,由Steane构造法构造出新的量子纠错码。     

On constructing disjoint linear codes

To produce a highly nonlinear resilient function, the disjoint linear codes were originally proposed by Johansson and Pasalic in IEEE Trans. Inform. Theory, 2003, 49(2): 494–501. In this paper, an effective method for finding a set of such disjoint linear codes is presented. When n ⩾ 2k, we can find a set of [n,k]disjoint linear codes with cardinality 2^n-k +⌊(n-k)/k⌊; When n < 2k, no set of disjoint linear codes exists with cardinality at least 2. We also describe a result on constructing a set of [n, k] disjoint linear codes with minimum distance at least some fixed positive integer.     

Some new optimal quaternary constant weight codes

Constant weight codes (CWCs) are an important class of codes in coding theory. Generalized Steiner systems GS (2, k, v, g) were first introduced by Etzion and used to construct optimal nonlinear CWCs over an alphabet of size g + 1 with minimum Hamming distance 2k − 3, in which each codeword has length v and weight k. In this paper, Weil’s theorem on character sum estimates is used to show that there exists a GS(2, 4, v, 3) for any prime v ≡ 1 (mod 4) and v > 13. From the coding theory point of view, an optimal nonlinear quaternary (v, 5, 4) CWC exists for such a prime v.     

A nondeterministic space-time tradeoff for linear codes

We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions in linear time, that is, in time at most kn for a constant k. Ajtai has proved such lower bounds for explicit functions over domains D of size about n, and Beame, Saks and Thathachar for functions over domains of size about k²². We prove an exponential lower bound ²Ω(n/ck) for an explicit function over substantially smaller domain D of size about k². Our function is a universal function of linear codes.     

Involution codes: with application to DNA coded languages

For an involution θ : Σ^* → Σ^* over a finite alphabet Σ we consider involution codes: θ-infix, θ-comma-free, θ-k -codes and θ-subword-k-codes. These codes arise from questions on DNA strand design. We investigate conditions under which both X and X⁺ are same type of involution codes. General methods for generating such involution codes are given. The information capacity of these codes show to be optimized in most cases. A specific set of these codes was chosen for experimental testing and the results of these experiments are presented.     

Self-checking circuits and decoding algorithms for binary hamming and BCH codes and Reed-Solomon codes over GF(2 m )

We consider problems of detecting errors in combinational circuits and algorithms for the decoding of linear codes. We show that a totally self-checking combinatorial circuit for the decoding of a binary Hamming [n, k] code can be constructed if and only if n = 2 ^r ? 1, r = n?k. We introduce the notion of a totally self-checking combinational circuit detecting error clusters of size at most µ; for shortened Hamming [n,k] codes, we construct totally self-checking decoding combinational circuits detecting error clusters of size at most µ, 2 ≤ µ < n?k. We describe single-error protected and self-checking algorithms: the extended Euclidean algorithm and decoding algorithms for binary BCH codes and Reed-Solomon codes over GF(2 ^m ).     

单体型组装MEC问题的参数化算法研究

单体型组装MEC问题指如何利用个体的DNA测序片断数据,翻转最少的SNP位点值以确定该个体单体型的计算问题。根据片段数据的特点提出了一个时间复杂度为 O（nk₂2^k₂+mlogm+mk₁）的参数化算法,其中m为片段数,n为单体型的SNP位点数,k1为一个片断覆盖的最大SNP位点数（通常小于10）,k₂为覆盖同一SNP位点的片段的最大数（通常不大于10）。对于实际DNA测序中的片段数据,即使m和n都相当大,该算法也可以在较短的时间得到MEC问题的精确解,具有良好的可扩展性和较高的实用价值。     

A note on the decoding complexity of error-correcting codes

A time-space tradeoff lower bound for the decoding complexity of asymptotically good error-correcting codes for oblivious write-k-times branching programs is proved. Specifically, we prove that the computation time T and space S of every oblivious write-k-times branching program that decodes an asymptotically good error-correcting code with block length n satisfy S⋅Tk=Ω((n/k)^k+1).