A new combinatorial approach to the construction of constant composition codes

Constant composition codes(CCCs)are a new generalization of binary constant weight codes and have attracted recent interest due to their numerous applications. In this paper, a new combinatorial approach to the construction of CCCs is proposed, and used to establish new optimal CCCs.     

Constructions of optimal GDRP’s of type

Generalized doubly resolvable packings (GDRPs) represent a combinatorial characterization of constant composition codes (CCCs). In this paper, we develop a number of general constructions of GDRPs of type λ¹μ^m−1. As a consequence, a new series of optimal CCCs is obtained.     

常重复合码的构造和界

摘要给出了一种Chebyshev距离下的常重复合码的构造,并在其基础上讨论了它的译码算法和优化处理.考虑了Chebyshev距离下的界及其改进.研究了具有Chebyshev距离和Hamming距离的常重复合码的构造,给出了Hamming距离为4的常重复合码的一个结论.     

A combination of testability and decodability by tensor products

Ben‐Sasson and Sudan (RSA 2006) showed that taking the repeated tensor product of linear codes with very large distance results in codes that are locally testable. Due to the large distance requirement the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result to present a combinatorial construction of locally testable codes with largest known rate. As a consequence, this construction was obtained over sufficiently large fields. In this paper we improve the result of Ben‐Sasson and Sudan and show that for any linear codes the associated tensor products are locally testable. Consequently, the construction of Meir can be taken over any field, including the binary field. Moreover, a combination of our result with the result of Spielman (IEEE IT, 1996) implies a construction of linear codes (over any field) that combine the following properties:

• have constant rate and constant relative distance;
• have blocklength n and are testable with n^? queries, for any constant ? > 0;
• linear time encodable and linear‐time decodable from a constant fraction of errors.

Furthermore, a combination of our result with the result of Guruswami et al. (STOC 2009) implies a similar corollary for list‐decodable codes. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 572–598, 2015     

On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability

Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability [6] in the classical setting. This interest also translates to other metric setting, including the insertion and deletion (insdel for short) setting which is used to model synchronization errors caused by positional information loss in communication systems. Such interest is supported by the construction of a deletion correcting algorithm of insdel Reed-Solomon code in [22] which is based on the Guruswami-Sudan decoding algorithm [6]. Nevertheless, there have been few studies [3] on the insdel error-correcting capability of Reed-Solomon codes.In this paper, we discuss a criterion for a 2-dimensional insdel Reed-Solomon codes to have optimal asymptotic error-correcting capabilities, which are up to their respective lengths. Then we provide explicit constructions of 2-dimensional insdel Reed-Solomon codes that satisfy the established criteria. The family of such constructed codes can then be shown to extend the family of codes with asymptotic error-correcting capability reaching their respective lengths provided in [3, Theorem 2] which provide larger error-correcting capability compared to those defined in [25].     

Symmetric LDPC codes and local testing

Coding theoretic and complexity theoretic considerations naturally lead to the question of generating symmetric, sparse, redundant linear systems. This paper provides a new way of construction with better parameters and new lower bounds.Low Density Parity Check (LDPC) codes are linear codes defined by short constraints (a property essential for local testing of a code). Some of the best (theoretically and practically) used codes are LDPC. Symmetric codes are those in which all coordinates “look the same,” namely there is some transitive group acting on the coordinates which preserves the code. Some of the most commonly used locally testable codes (especially in PCPs and other proof systems), including all “low-degree” codes, are symmetric. Requiring that a symmetric binary code of length n has large (linear or near-linear) distance seems to suggest a “con ict” between 1/rate and density (constraint length). In known constructions, if one is constant, then the other is almost the worst possible - n/poly(logn).Our main positive result simultaneously achieves symmetric low density, constant rate codes generated by a single constraint. We present an explicit construction of a symmetric and transitive binary code of length n, near-linear distance n/(log logn)², of constant rate and with constraints of length (logn)⁴. The construction is in the spirit of Tanner codes, namely the codewords are indexed by the edges of a sparse regular expander graph. The main novelty is in our construction of a transitive (non Abelian!) group acting on these edges which preserves the code. Our construction is one instantiation of a framework we call Cayley Codes developed here, that may be viewed as extending zig-zag product to symmetric codes.Our main negative result is that the parameters obtained above cannot be significantly improved, as long as the acting group is solvable (like the one we use). More specifically, we show that in constant rate and linear distance codes (aka “good” codes) invariant under solvable groups, the density (length of generating constraints) cannot go down to a constant, and is bounded below by (log^(Ω(?)) n)(an Ω(?) iterated logarithm) if the group has a derived series of length ?. This negative result precludes natural local tests with constantly many queries for such solvable “good” codes.     

Johnson type bounds on constant dimension codes

Very recently, an operator channel was defined by Koetter and Kschischang when they studied random network coding. They also introduced constant dimension codes and demonstrated that these codes can be employed to correct errors and/or erasures over the operator channel. Constant dimension codes are equivalent to the so-called linear authentication codes introduced by Wang, Xing and Safavi-Naini when constructing distributed authentication systems in 2003. In this paper, we study constant dimension codes. It is shown that Steiner structures are optimal constant dimension codes achieving the Wang-Xing-Safavi-Naini bound. Furthermore, we show that constant dimension codes achieve the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures. Then, we derive two Johnson type upper bounds, say I and II, on constant dimension codes. The Johnson type bound II slightly improves on the Wang-Xing-Safavi-Naini bound. Finally, we point out that a family of known Steiner structures is actually a family of optimal constant dimension codes achieving both the Johnson type bounds I and II.      

$$\mathbb {Z}_{4}$$-codes and their Gray map images as orthogonal arrays

A classic result of Delsarte connects the strength (as orthogonal array) of a linear code with the minimum weight of its dual: the former is one less than the latter. Since the paper of Hammons et al., there is a lot of interest in codes over rings, especially in codes over \(\mathbb {Z}_{4}\) and their (usually non-linear) binary Gray map images. We show that Delsarte’s observation extends to codes over arbitrary finite commutative rings with identity. Also, we show that the strength of the Gray map image of a \(\mathbb {Z}_{4}\) code is one less than the minimum Lee weight of its Gray map image.     

On constant composition codes

A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword is the same for each codeword. These specialize to constant weight codes in the binary case, and permutation codes in the case that each symbol occurs exactly once. Constant composition codes arise in powerline communication and balanced scheduling, and are used in the construction of permutation codes. In this paper, direct and recursive methods are developed for the construction of constant composition codes.     

Codes over Hurwitz integers

In this study, we obtain new classes of linear codes over Hurwitz integers equipped with a new metric. We refer to the metric as the Hurwitz metric. Also, we define decoding algorithms for these codes when up to two coordinates of a transmitted code vector are affected by the error of arbitrary Hurwitz weight. The interest in the codes with respect to the Hurwitz metric is their use in coded modulation schemes based on quadrature amplitude modulation (QAM)-type constellations where the Hamming metric and the Lee metric are not appropriate.     

Message encoding and retrieval for spread and cyclic orbit codes

Spread codes and cyclic orbit codes are special families of constant dimension subspace codes. These codes have been well-studied for their error correction capability, transmission rate and decoding methods, but the question of how to encode and retrieve messages has not been investigated. In this work we show how a message set of consecutive integers can be encoded and retrieved for these two code families.     

The characterization of binary constant weight codes meeting the bound of Fu and Shen

Fu and Shen gave an upper bound on binary constant weight codes. In this paper, we present a new proof for the bound of Fu and Shen and characterize binary constant weight codes meeting this bound. It is shown that binary constant weight codes meet the bound of Fu and Shen if and only if they are generated from certain symmetric designs and quasi-symmetric designs in combinatorial design theory. In particular, it turns out that the existence of binary codes with even length meeting the Grey–Rankin bound is equivalent to the existence of certain binary constant weight codes meeting the bound of Fu and Shen. Furthermore, some examples are listed to illustrate these results. Finally, we obtain a new upper bound on binary constant weight codes which improves on the bound of Fu and Shen in certain case. This research is supported in part by the DSTA research grant R-394-000-025-422 and the National Natural Science Foundation of China under the Grant 60402031, and the NSFC-GDSF joint fund under the Grant U0675001     

具有常数利率的延迟更新风险模型

考虑常数利率情形下的延迟更新风险过程．得到了该延迟更新风险模型下的Gerber-Shiu期望折现罚金函数的表达式,并得到了常数利率下的一种特殊的延迟更新风险模型的破产概率的显示表达式.     

An Algorithm for Computing the Minimum Distances of Extensions of BCH Codes Embedded in Semigroup Rings

An algorithm is given for computing the weights of extensions of BCH codes embedded in semigroup rings as ideals. The algorithm relies on a more general technical result of independent interest.     

低密度奇偶校验码的构造

低密度奇偶校验码(LDPC)最早是由Gallager于1962年提出.它们是线性分组码,其比特错误率极大地接近香农界.1995年Mackay和Neal发掘了LDPC码的新应用后,LDPC码引起了人们的广泛关注.本文利用组合结构给出一些新的LDPC码:利用可分组设计构造一类Tanner图中不含四长圈的正则LDPC码.     

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

最近,环F2+uF2上的线性码引起了编码研究者极大的兴趣.本文证明了R[x]/〈xn+1+u〉是有限链环,其中R=F2+uF2=F2[u]/〈u2〉且n=2e.从而给出了F2+uF2上的所有长为2e的(1+u)-循环码,进而给出了所有(1+u)-循环码的对偶码.证明了F2+uF2上不存在长为2e的非平凡的自对偶的(1+u)-循环码.     

Cyclic subspace codes via subspace polynomials

Subspace codes have been intensely studied in the last decade due to their application in random network coding. In particular, cyclic subspace codes are very useful subspace codes with their efficient encoding and decoding algorithms. In a recent paper, Ben-Sasson et al. gave a systematic construction of subspace codes using subspace polynomials. In this paper, we mainly generalize and improve their result so that we can obtain larger codes for fixed parameters and also we can increase the density of some possible parameters. In addition, we give some relative remarks and explicit examples.     

Undetected error probability of q-ary constant weight codes

In this paper, we introduce a new combinatorial invariant called q-binomial moment for q-ary constant weight codes. We derive a lower bound on the q-binomial moments and introduce a new combinatorial structure called generalized (s, t)-designs which could achieve the lower bounds. Moreover, we employ the q-binomial moments to study the undetected error probability of q-ary constant weight codes. A lower bound on the undetected error probability for q-ary constant weight codes is obtained. This lower bound extends and unifies the related results of Abdel-Ghaffar for q-ary codes and Xia-Fu-Ling for binary constant weight codes. Finally, some q-ary constant weight codes which achieve the lower bounds are found.      

Constructions of cyclic constant dimension codes

Subspace codes and particularly constant dimension codes have attracted much attention in recent years due to their applications in random network coding. As a particular subclass of subspace codes, cyclic subspace codes have additional properties that can be applied efficiently in encoding and decoding algorithms. It is desirable to find cyclic constant dimension codes such that both the code sizes and the minimum distances are as large as possible. In this paper, we explore the ideas of constructing cyclic constant dimension codes proposed in Ben-Sasson et al. (IEEE Trans Inf Theory 62(3):1157–1165, 2016) and Otal and Özbudak (Des Codes Cryptogr, doi: 10.1007/s10623-016-0297-1, 2016) to obtain further results. Consequently, new code constructions are provided and several previously known results in [2] and [17] are extended.     

Skew quasi-cyclic codes over Galois rings

Recently there has been a lot of interest on algebraic codes in the setting of skew polynomial rings. In this paper we have studied skew quasi-cyclic (QC) codes over Galois rings. We have given a necessary and sufficient condition for skew cyclic codes over Galois rings to be free, and determined a distance bound for free skew cyclic codes. A sufficient condition for 1-generator skew QC codes to be free is determined. Some distance bounds for free 1-generator skew QC codes are discussed. A canonical decomposition of skew QC codes is presented.