Generating indecomposable permutations

An indecomposable permutation π on [n] is one such that π([m])=[m] for no m<n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to generate all indecomposable permutations of length n in transposition Gray code order, in constant amortized time (CAT). We also present a CAT generation algorithm for indecomposable permutations which is based on the Johnson-Trotter algorithm for generating all permutations of length n. The question of whether or not there exists an adjacent transposition Gray code for indecomposable permutations remains open.     

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.     

Gray codes for signed involutions

In this paper we present two cyclic Gray codes for signed involutions. The first one has a natural construction, implemented by a CAT algorithm, based in the recursive formula for the number of signed involutions. The second code, although with a higher computational cost, has the smallest possible Hamming distance for this family of objects.     

环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上的准循环码.     

环F_(p~k)+uF_(p~k)+u~2F_(p~k)上的常循环码和循环码

记环R=F_(p~k)+uF_(p~k)+u~2F_(p~k),定义了一个从R~n到F_(p~k)~(2np~k)的Gray映射.利用Gray映射的性质,研究了环R上(1-u~2)-循环码和循环码.证明了环R上码是(1-u~2)-循环码当且仅当它的Gray象是F_(p~k)上的准循环码.当(n,p)=1时,证明了环R上的长为n的线性循环码的Gray象置换等价于域F_(p~k)上的线性准循环码.     

Zpk+1环上的循环码的Gray像

定义了Znpk+1到Znpkp的Gray映射,给出该映射的一个性质,证明了Zpk+1环上码长为n的码为循环码的充要条件是它的Gray像是Zp上长度为npk指数为pk的准循环码.     

环Z_p[u]/(u~(k+1))上循环码的Gray象

记R=Z_p[u]/(u~(k+1)),定义了从R~n到Z_p~(np~k)的Gray映射.利用Gray映射的性质,研究了环R上任意长循环码.证明了环R上任意长码是循环码当且仅当它的Gray象是域Z_p上的准循环码.特别的,环R上的线性循环码的Gray象是Z_p上的线性准循环码.     

环F2+uF2+vF2上线性码广义Gray像

本文定义了环F2+uF2+vF2到域F2的广义Gray映射φ像,研究了环F2+uF2+vF2上线性码的广义Gray像.利用广义Gray映射φ的线性性,证明了环F2+uF2+vF2上线性码C的广义Gray像φ(C)满足dH(C)=dH(φ(C))且φ(C⊥)φ(C)⊥.同时,给出了F2+uF2+vF2上循环码C的广义Gray像φ(C)为F2上的4-拟循环码.     

State Spaces of Convolutional Codes

There are various definitions of convolutional codes and each definition leads to a definition of code state space. In the usual definition of a convolutional code generated by a rational encoding matrix input sequences can be any Laurent series. It is proved that restricting input sequences to be rational functions or restricting output sequences to be finite do not change the code state space, and that restricting both input and output sequences to be finite may change the code state space.     

Incremental and Decremental Maintenance of Planar Width

We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^ε) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^ε).     

A class of generalized cyclic codes

1. IntroductionPrange was considered to be first person to study cyclic codes at the end of 1950s, seeIll and [2]. Since then, cyclic codes are the mostly studied of all codes, because they are easyto encode, and include an important family of BCH codes. A code C is cyclic if it is linearand if any cyclic shift of a codeword is also a codeword, i.e., whenever (co, of,' 1 on--l ) is inC then so is (c.--1, co j', c.--2). In fact, one could define a cyclic code to be an ideal in thering of…     

On the construction of prefix-free and fix-free codes with specified codeword compositions

We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimize the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost.     

环F2＋uF2上长为2e循环码的Gray象

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

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

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

Gray code for derangements

We give a Gray code and constant average time generating algorithm for derangements, i.e., permutations with no fixed points. In our Gray code, each derangement is transformed into its successor either via one or two transpositions or a rotation of three elements. We generalize these results to permutations with number of fixed points bounded between two constants.     

一种OLS/OOC二维光正交码的构造与性能分析

利用不同的序列作为波长跳频序列和时间扩频序列可以构造出不同的二维光正交码在众多文献中已有所报道.在经过正交拉丁方(OLS)与跳频序列的相关性研究之后.做了以下主要工作:首先,将正交拉丁方(OLS)序列作为波长跳频序列,结合一维时间扩频序列(OOC),构造了一种OLS/OOC二维光正交码.然后,本文对构造的OLS/OOC进行了多种性能仿真和分析.相对于PC/OOC、OCFHC/OOC等二维光正交码而言,OLS/OOC的波长数并不局限于素数,更能充分利用MWOCDMA系统中的有效波长数.仿真和分析表明:码字具有很好的相关性能,码字容量直逼理论极限,为一种渐近最优二维光正交码.     

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].     

有限域上一类等维码的下界

等维码凭借其在随机线性网络编码中的良好的差错控制得到广泛研究,对于给定维数和最小距离的等维码所含码字的最大个数目前还没有一般性结果.Tuvi Etzion和Alexander Vardy给出了一定等维码所含码字最大个数的上界和下界,首先利用对偶空间构造等维码C(n,M,2k,k),达到了此类码所含码字的下界,然后具体构造了最优等维码C(7,41,4,2).     

环$F_2 uF_2 u^2F_2$上的循环码及自对偶码

We give the structures of a cyclic code over ring
R = F2 ＋ uF2 ＋ u^2F2 = {0, 1,u, u^2,v, v^2,uv, v^3},
where u^3 = 0, of odd length and its dual code. For the cyclic code, necessary and sufficient conditions for the existence of self-dual code are provided.