广义Gray码及其在数字图像置乱中的应用

以图像信息安全问题为背景，讨论了广义Gray码及其在数字图像中的置乱作用，推广了丁玮等人（1999年）的相关结果。给出了图像置乱变换的周期，得到了周期性的一个充分必要条件。     

A construction of Gray codes inducing complete graphs

A binary Gray code G(n) of length n, is a list of all 2ⁿn-bit codewords such that successive codewords differ in only one bit position. The sequence of bit positions where the single change occurs when going to the next codeword in G(n), denoted by S(n)?s₁,s₂,…,s_2ⁿ-1, is called the transition sequence of the Gray code G(n). The graph G_G(n) induced by a Gray code G(n) has vertex set {1,2,…,n} and edge set {{s_i,s_i+1}:1?i?2ⁿ-2}. If the first and the last codeword differ only in position s_2ⁿ, the code is cyclic and we extend the graph by two more edges {s_2ⁿ-1,s_2ⁿ} and {s_2ⁿ,s₁}. We solve a problem of Wilmer and Ernst [Graphs induced by Gray codes, Discrete Math. 257 (2002) 585-598] about a construction of an n-bit Gray code inducing the complete graph K_n. The technique used to solve this problem is based on a Gray code construction due to Bakos [A. Ádám, Truth Functions and the Problem of their Realization by Two-Terminal Graphs, Akadémiai Kiadó, Budapest, 1968], and which is presented in D.E. Knuth [The Art of Computer Programming, vol. 4, Addison-Wesley as part of “fascicle” 2, USA, 2005].     

Combinatorial families enumerated by quasi-polynomials

We say that the sequence (an) is quasi-polynomial in n if there exist polynomials P₀,…,Ps−1 and an integer n₀ such that, for all n?n₀, an=Pi(n) where . We present several families of combinatorial objects with the following properties: Each family of objects depends on two or more parameters, and the number of isomorphism types of objects is quasi-polynomial in one of the parameters whenever the values of the remaining parameters are fixed to arbitrary constants. For each family we are able to translate the problem of counting isomorphism types of objects into the problem of counting integer points in a union of parametrized rational polytopes. The families of objects to which this approach is applicable include combinatorial designs, linear and unrestricted codes, and dissections of regular polygons.     

Gray code for permutations with a fixed number of cycles

We give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.     

环F_2+uF_2上长为2~e循环码的Gray象

利用环F2+uF2上长为2e的循环码结构,证明了这样的循环码的一类码在Gray映射下的象是循环码,并给出了环F2+uF2上长为2e的循环码的Gray象仍是循环码的一个充要条件.     

Gray codes for column-convex polyominoes and a new class of distributive lattices

We introduce the problem of polyomino Gray codes, which is the listing of all members of certain classes of polyominoes such that successive polyominoes differ by some well-defined closeness condition (e.g., the movement of one cell). We discuss various closeness conditions and provide several Gray codes for the class of column-convex polyominoes with a fixed number of cells in each column. For one of our closeness conditions, a natural new class of distributive lattice arises: the partial order is defined on the set of m-tuples [S₁]×[S₂]××[S_m], where each S_i>1 and [S_i]={0,1,…,S_i−1}, and the cover relations are (p₁,p₂,…,p_m)(p₁+1,p₂,…,p_m) and (p₁,p₂,…,p_j,p_j+1,…,p_m)(p₁,p₂,…,p_j−1,p_j+1+1,…,p_m). We also discuss some properties of this lattice.     

Gray codes for non-crossing partitions and dissections of a convex polygon

In this paper we develop Gray codes for two families of geometric objects: non-crossing partitions and dissections of a convex polygon by means of non-crossing diagonals.     

环F_2+uF_2+u~2F_2上线性码的广义Gray像

摘要:引入了环F_2+uF_2+u~2F_2与F_2之间的广义Gray映射,利用环F_2+uF_2+u~2F_2上线性码的生成矩阵得出了广义Gray像φ(C)的生成矩阵,证明了F_2+uF2+u2F2上线性码自正交码的广义Gray像仍为自正交码和F_2+uF_2+u~2F_2上循环码的广义Gray像是F_2上的准循环码.     

A p-adic model of DNA sequence and genetic code

Using basic properties of p-adic numbers, we consider a simple new approach to describe main aspects of DNA sequence and the genetic code. In our investigation central role plays an ultrametric p-adic information space whose basic elements are nucleotides, codons and genes. We show that a 5-adicmodel is appropriate for DNA sequence. This 5-adicmodel, combined with 2-adic distance, is also suitable for the genetic code and for amore advanced employment in genomics. We find that genetic code degeneracy is related to the p-adic distance between codons. The text was submitted by the authors in English. This paper is a slight modification of an article available in the electronic archive form arXiv:qbio. GN/0607018v1 (July 2006). Since that time some other papers on this subject have appeared, e.g. [1], [2].     

On nested code pairs from the Hermitian curve

Nested code pairs play a crucial role in the construction of ramp secret sharing schemes [15] and in the CSS construction of quantum codes [14]. The important parameters are (1) the codimension, (2) the relative minimum distance of the codes, and (3) the relative minimum distance of the dual set of codes. Given values for two of them, one aims at finding a set of nested codes having parameters with these values and with the remaining parameter being as large as possible. In this work we study nested codes from the Hermitian curve. For not too small codimension, we present improved constructions and provide closed formula estimates on their performance. For small codimension we show how to choose pairs of one-point algebraic geometric codes in such a way that one of the relative minimum distances is larger than the corresponding non-relative minimum distance.     

Infinite families of 2-designs and 3-designs from linear codes

The interplay between coding theory and $t$-designs started many years ago. While every $t$-design yields a linear code over every finite field, the largest $t$ for which an infinite family of $t$-designs is derived directly from a linear or nonlinear code is $t=3$. Sporadic $4$-designs and $5$-designs were derived from some linear codes of certain parameters. The major objective of this paper is to construct many infinite families of $2$-designs and $3$-designs from linear codes. The parameters of some known $t$-designs are also derived. In addition, many conjectured infinite families of $2$-designs are also presented.     

Continuous families of vectors that are orbits of a unitary group

We characterize functions u from the real line into a Hilbert space that are the orbits of a unitary group {U(t)}_t∈R; that is, u(t)=U(t)u(0), for all real t. One of the characterizations is that u be the Fourier transform of a certain type of vector-valued measure Z; we then use our characterizations to construct Z from u.     

There exist Steiner triple systems of order 15 that do not occur in a perfect binary one‐error‐correcting code

The codewords at distance three from a particular codeword of a perfect binary one‐error‐correcting code (of length 2^m?1) form a Steiner triple system. It is a longstanding open problem whether every Steiner triple system of order 2^m?1 occurs in a perfect code. It turns out that this is not the case; relying on a classification of the Steiner quadruple systems of order 16 it is shown that the unique anti‐Pasch Steiner triple system of order 15 provides a counterexample. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 465–468, 2007     

利用有限域上交错矩阵构造Cartesian认证码

设Fq是q元有限域,q是素数的幂.令信源集S为Fq上所有的n×n交错矩阵的合同标准形,编码规则集E为Fq上所有的n×n非奇异矩阵,信息集M为Fq上所有的n×n交错矩阵,构造映射f:S×E→M,(K'(v,n),g)→gK'(v,n)gT.证明了该四元组(S,E,M;f)是一个Cartesian认证码,并计算了它的参数.进而,假定编码规则按照均匀的概率分布所选取,计算出了该码的成功模仿攻击概率PI和替换攻击概率Ps.     

Infinite families of 2‐designs from a class of cyclic codes

Combinatorial $t$‐designs have wide applications in coding theory, cryptography, communications, and statistics. It is well known that the supports of all codewords with a fixed weight in a code may give a $t$‐design. In this paper, we first determine the weight distributions of a class of linear codes derived from the dual of some extended cyclic codes. We then obtain infinite families of 2‐designs and explicitly compute their parameters from the supports of all the codewords with a fixed weight in the codes. By a simple counting argument, we obtain exponentially many 2‐designs.     

Braid groups in genetic code

For every genetic code with finitely many generators and at most one relation, a braid group is introduced. The construction presented includes the braid group of a plane, braid groups of closed oriented surfaces, Artin— Brieskorn braid groups of series B, and allows us to study all of these groups from a unified standpoint. We clarify how braid groups in genetic code are structured, construct words in the normal form, look at torsion, and compute width of verbal subgroups. It is also stated that the system of defining relations for a braid group in two-dimensional manifolds presented in a paper by Scott is inconsistent. Supported by RFBR grant No. 02-01-01118. __________ Translated from Algebra i Logika, Vol. 45, No. 2, pp. 131–158, March–April, 2006.     

Twofold triple systems with cyclic 2‐intersecting Gray codes

Given a combinatorial design with block set , the block‐intersection graph (BIG) of is the graph that has as its vertex set, where two vertices and are adjacent if and only if . The i‐block‐intersection graph (i‐BIG) of is the graph that has as its vertex set, where two vertices and are adjacent if and only if . In this paper, several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian 2‐BIGs and result in larger TTSs that also have Hamiltonian 2‐BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian 2‐BIGs (equivalently TTSs with cyclic 2‐intersecting Gray codes) as well as the complete spectrum for TTSs with 2‐BIGs that have Hamilton paths (i.e. for TTSs with 2‐intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel classes in arbitrary TTSs, and then construct larger TTSs with both cyclic 2‐intersecting Gray codes and parallel classes.