Codes for Identification in the King Lattice

Let G=(V, E) be an undirected graph and C a subset of vertices. If the sets B _r (F)C are distinct for all subsets FV with at most k elements, then C is called an (r,k)-identifying code in G. Here B _r (F) denotes the set of all vertices that are within distance r from at least one vertex in F. We consider the two-dimensional square lattice with diagonals (the king lattice). We show that the optimal density of an (r,2)-identifying code is 1/4 for all r3. For r=1,2, we give constructions with densities 3/7 and 3/10, and we prove the lower bounds 9/22 and 31/120, respectively. The research of the authors was supported by the Academy of Finland under grants 44002 and 46186     

Higher Power Residue Codes and the Leech Lattice

We shall consider higher power residue codes over the ring Z₄. We will briefly introduce these codes over Z₄ and then we will find a new construction for the Leech lattice. A similar construction is used to construct some of the other lattices of rank 24.     

On Optimal Lattice Decompositions

A lattice decomposition lemma by H. Rosenthal is given an optimal refinement, both in the real and in the complex valued setting.     

Optimal Identifying Codes in Cycles and Paths

The concept of identifying codes in a graph was introduced by Karpovsky et?al. (in IEEE Trans Inf Theory 44(2):599–611, 1998). These codes have been studied in several types of graphs such as hypercubes, trees, the square grid, the triangular grid, cycles and paths. In this paper, we determine the optimal cardinalities of identifying codes in cycles and paths in the remaining open cases.     

An Optimal Edge-Robust Identifying Code in the Triangular Lattice

A subset C of vertices in an undirected graph G = (V, E) is called a 1-identifying code if the sets I(v)={u C: d(u,v) 1 }, v V, are non-empty and no two of them are the same set. A 1-identifying code C is called 1-edge-robust 1-identifying if it is 1-identifying in every graph G¹ obtained from G by deleting or adding one edge. It is shown that the optimal density of a 1-edge-robust 1-identifying code in the infinite triangular lattice is 3/7.     

Some New Optimal Ternary Linear Codes

Let d₃(n,k) be the maximum possible minimum Hamming distance of a ternary [ n,k,d;3]-code for given values of n and k. It is proved that d₃(44,6)=27, d₃(76,6)=48,d₃(94,6)=60 , d₃(124,6)=81,d₃(130,6)=84 , d₃(134,6)=87,d₃(138,6)=90 , d₃(148,6)=96,d₃(152,6)=99 , d₃(156,6)=102,d₃(164,6)=108 , d₃(170,6)=111,d₃(179,6)=117 , d₃(188,6)=123,d₃(206,6)=135 , d₃(211,6)=138,d₃(224,6)=147 , d₃(228,6)=150,d₃(236,6)=156 , d₃(31,7)=17 and d₃(33,7)=18 . These results are obtained by a descent method for designing good linear codes.     

Binary Optimal Odd Formally Self-Dual Codes

In this paper, we study binary optimal odd formallyself-dual codes. All optimal odd formally self-dual codes areclassified for length up to 16. The highest minimum weight ofany odd formally self-dual codes of length up to 24 is determined. We also show that there is a unique linearcode for parameters [16, 8, 5] and [22, 11, 7], up to equivalence.     

On Balanced Optimal Optical Orthogonal Codes

Variable‐weight optical orthogonal codes (OOCs) were introduced by G.‐C. Yang for multimedia optical CDMA systems with multiple quality of service (QoS) requirement. In this paper, by using incomplete difference matrices and perfect relative difference families, a balanced ‐OOC is obtained for every positive integer .     

Lattices of Optimal Finite Lattice Packings

We consider finite lattice ball packings with respect to parametric density and show that densest packings are attained in critical lattices if the number of translates and the density parameter are sufficiently large. A corresponding result is not valid for general centrally symmetric convex bodies.The second author was partially supported by a DAAD Postdoc fellowship and the hospitality of Peking University during his work.     

Lattices of Optimal Finite Lattice Packings

We consider finite lattice ball packings with respect to parametric density and show that densest packings are attained in critical lattices if the number of translates and the density parameter are sufficiently large. A corresponding result is not valid for general centrally symmetric convex bodies.     

On Optimal Codes Over the Field with Five Elements

In this paper, we prove the nonexistence of Griesmer codes over the field of five elements for k = 4 and d = 33, 83, 163, 164.     

On Lower Bounds for the Redundancy of Optimal Codes

The problem of providing bounds on the redundancy of an optimal code for a discrete memoryless source in terms of the probability distribution of the source, has been extensively studied in the literature. The attention has mainly focused on binary codes for the case when the most or the least likely source letter probabilities are known. In this paper we analyze the relationships among tight lower bounds on the redundancy r. Let r _D,i(x) be the tight lower bound on r for D-ary codes in terms of the value x of the i-th most likely source letter probability. We prove that _D,i-1(x) _D,i(x) for all possible x and i. As a consequence, we can bound the redundancy when only the value of a probability (but not its rank) is known. Another consequence is a shorter and simpler proof of a known bound. We also provide some other properties of tight lower bounds. Finally, we determine an achievable lower bound on r in terms of the least likely source letter probability for D 3, generalizing the known bound for the case D = 2.     

A Construction of Optimal Constant Composition Codes

In this paper, a construction of optimal constant composition codes is developed, and used to derive some series of new optimal constant composition codes meeting the upper bound given by [13].     

几类最优避免冲突码

长度为n重量为w的避免冲突码C是群Z_n的w元子集族,满足对任意的x,y∈C,x≠y有d*(x)∩d*(y)=Φ,其中d*(x)={a-b(mod n):a,b∈x,a≠b}.避免冲突码适用于无反馈时隙同步多址冲突信道.C中的元素称为码字,C中所包含的码字的个数称为码的容量,它是系统中所支持的潜在用户的个数.利用已有的3种构造方法给出了重量在4到10之间的一些最优CAC(p,w)码类.     

最优循环局部修复码的构造

局部修复码是分布式存储编码领域的一个热门研究方向,具有局部性(r,δ)的局部修复码对丢失节点修复具有更高的效率.文章利用限域F_q上循环码构造了两类具有局部性(r,δ),最小距离为d=δ+4,码长n为q+1倍数的最优局部修复码.     

Combinatorial Classification of Optimal Authentication Codes with Arbitration

Unconditionallysecure authentication codes with arbitration ( A ²-codes)protect against deceptions from the transmitter and the receiveras well as that from the opponent. We first show that an optimalA ²-code implies an orthogonal array and an affine-resolvable design. Next we define a new design,an affine -resolvable + BIBD,and prove that optimal A ²-codes are equivalentto this new design. From this equivalence, we derive a conditionon the parameters for the existence of optimal A ²-codes.Further, we show tighter lower bounds on the size of keys thanbefore for large sizes of source states which can be consideredas an extension of the bounds on the related designs.     

Optimal Ternary Linear Rate 1/2 Codes

In this paper, we classify all optimal linear[n, n/2] codes up to length 12. We show that thereis a unique optimal [10, 5, 5] code up to equivalence.     

带反馈非对称信道的最优纠错编码

带反馈非对称信道的最优纠错编码等同于Ulam-Renyi问题的半谎搜索模型的最少提问次数qw(m).本文证明了qw(m)的取值分布具有非交叉性.借助于这一良好的分布特性,原始的确定最少提问次数精确值问题可以被简化为确定一个临界数问题并且这个临界数的存在性和唯一性得到了证明.同时本文也改进了Cicalese等人的结果,在更大的范围内明确地给出了最少提问次数qw(m)的精确值.     

A New Class of Optimal 3-splitting Authentication Codes

The necessary condition for the existence of a (ν, 3× 3,1)-splitting BIBD is ν ≡ 1 (mod 54). In this paper, we show that the necessary condition is also sufficient with one possible exception of ν = 55. As its application, we obtain a new infinite class of optimal 3-splitting authentication codes. AMS Classification: 05B05, 94A62 An erratum to this article is available at .     

两类新的最优变重量光正交码

变重量光正交码用于光码分多址通信系统以满足不同服务质量用户需求.给出当u≥5为素数时,最优(16u,{3,5},1,{2/3,1/3))交重量光正交码的具体构造.同时证明了当u≥5为素数时,存在一个最优(25u,{3,4,5},1,{1/4,2/4,1/4})变重量光正交码.这将改进变重量光正交码的存在性结果.