一类循环码的极小距离

循环码的极小距离大于或等于BCH界。本文考虑的是极小距离等于BCH界的特殊情形。利用一类自反循环码的事实。证明了使循环码的极小距离等于其BCH界的两个充分条件；并指出极小距离等于任意给定值，维数任意大的循环码可以构造。     

Toward the Determination of the Minimum Distance of Two-Point Codes on a Hermitian Curve

This is a first step toward the determination of the parameters of two-point codes on a Hermitian curve. We describe the dimension of such codes and determine the minimum distance of some two-point codes.AMS Classification: 94B27, 14H50, 11T71, 11G20Masaaki Homma - Partially supported by Grant-in-Aid for Scientific Research (15500017), JSPS.Seon Jeong Kim - Partially supported by Korea Research Foundation Grant (KRF-2002-041-C00010).     

On Upper Bounds for Minimum Distance and Covering Radius of Non-binary Codes

We consider upper bounds on two fundamental parameters of a code; minimum distance and covering radius. New upper bounds on the covering radius of non-binary linear codes are derived by generalizing a method due to S. Litsyn and A. Tietäväinen lt:newu and combining it with a new upper bound on the asymptotic information rate of non-binary codes. The upper bound on the information rate is an application of a shortening method of a code and is an analogue of the Shannon-Gallager-Berlekamp straight line bound on error probability. These results improve on the best presently known asymptotic upper bounds on minimum distance and covering radius of non-binary codes in certain intervals.     

On the Minimum Distances of Non-Binary Cyclic Codes

We deal with the minimum distances of q-ary cyclic codes of length q ^m - 1 generated by products of two distinct minimal polynomials, give a necessary and sufficient condition for the case that the minimum distance is two, show that the minimum distance is at most three if q > 3, and consider also the case q = 3.     

AMDS symbol-pair codes from repeated-root cyclic codes

Symbol-pair codes are proposed to guard against pair-errors in symbol-pair read channels. The minimum symbol-pair distance is of significance in determining the error-correcting capability of a symbol-pair code. One of the central themes in symbol-pair coding theory is the constructions of symbol-pair codes with the largest possible minimum symbol-pair distance. Maximum distance separable (MDS) and almost maximum distance separable (AMDS) symbol-pair codes are optimal and sub-optimal regarding the Singleton bound, respectively. In this paper, six new classes of AMDS symbol-pair codes are explicitly constructed through repeated-root cyclic codes. Remarkably, one class of such codes has unbounded lengths and the minimum symbol-pair distance of another class can reach 13.     

二元码的平均Hamming距离和方差

通过对二元ｎ长码Ｃ的对偶距离分布的研究,在码字数为奇数的情况下,改进了Ａｌ－ｔｈｏｆｅｒ－Ｓｉｌｌｋｅ［１］和［２］文关于Ｃ的码字间平均Ｈａｍｍｉｎｇ距离及其均方差的不等式,并在码字数为２ｎ－１或２ｎ－１－１时,确定了码Ｃ的最小平均距离及其均方差的精确值．     

Distance Matrix Completion by Numerical Optimization

Consider the problem of determining whether or not a partial dissimilarity matrix can be completed to a Euclidean distance matrix. The dimension of the distance matrix may be restricted and the known dissimilarities may be permitted to vary subject to bound constraints. This problem can be formulated as an optimization problem for which the global minimum is zero if and only if completion is possible. The optimization problem is derived in a very natural way from an embedding theorem in classical distance geometry and from the classical approach to multidimensional scaling. It belongs to a general family of problems studied by Trosset (Technical Report 97-3, Department of Computational & Applied Mathematics—MS 134, Rice University, Houston, TX 77005-1892, 1997) and can be formulated as a nonlinear programming problem with simple bound constraints. Thus, this approach provides a constructive technique for obtaining approximate solutions to a general class of distance matrix completion problems.     

A new learning strategy for stereo matching derived from a fuzzy clustering method

This paper presents an approach to the local stereo correspondence problem. The primitives or features used are groups of collinear connected edge points called segments. Each segment has several associated attributes or properties. We have verified that the differences of the attributes for the true matches cluster in a cloud around a center. Then for each current pair of primitives we compute a distance between the difference of its attributes and the cluster center. The correspondence is established in the basis of the minimum distance criterion (similarity constraint). We have designed an image understanding system to learn the best representative cluster center. For such purpose a new learning method is derived from the Fuzzy c-Means (FcM) algorithm where the dispersion of the true samples in the cluster is taken into account through the Mahalanobis distance. This is the main contribution of this paper. A better performance of the proposed local stereo-matching learning method is illustrated with a comparative analysis between classical local methods without learning.     

Minimum Distance Estimation in AR(1)-processes

In this paper a new minimum distance estimator is defined in case that the residuals of an AR(1)-process are contaminated normally distributed. This estimator is asymtotically normally distributed and in most cases less biased than the least square estimator. Furthermore, a method is presented to numerically calculate the minimum distance estimator as a root of an implicit function.     

考虑拥堵路况下碳排放的选址-配送集成优化问题

供应链网络的运输过程是碳排放的主要来源之一,道路拥堵、配送距离和车辆载重等因素会影响碳排放量,本文研究考虑拥堵路况下碳排放的选址-配送集成优化问题。根据车辆行驶状态定义道路拥堵情况,以不同时段下拥堵概率和预期拥堵距离作为路况决定因素,构建碳排放量和经济成本都最小的两目标模型。设计改进的非支配排序遗传算法(NSGA-II)求解模型获得Pareto解集。以环境问题较重的北京和天津为中心构建供应链网络作为算例,验证了模型和算法的有效性和可行性。实验结果给出了不同偏好下供应链网络的构建方案,并对不同时段下决定路况的拥堵概率和预期拥堵距离以及车辆载重进行灵敏度分析。实验结果表明,相对于高速公路,城市道路不同时段对碳排放量影响更敏感。     

Schubert varieties, linear codes and enumerative combinatorics

We consider linear error correcting codes associated to higher-dimensional projective varieties defined over a finite field. The problem of determining the basic parameters of such codes often leads to some interesting and difficult questions in combinatorics and algebraic geometry. This is illustrated by codes associated to Schubert varieties in Grassmannians, called Schubert codes, which have recently been studied. The basic parameters such as the length, dimension and minimum distance of these codes are known only in special cases. An upper bound for the minimum distance is known and it is conjectured that this bound is achieved. We give explicit formulae for the length and dimension of arbitrary Schubert codes and prove the minimum distance conjecture in the affirmative for codes associated to Schubert divisors.     

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.     

Codes with a Disparity Property

Kth order zero disparity codes have been considered in several recent papers. In the first part of this paper we remove the zero disparity condition and consider the larger class of codes, Kth order disparity D codes. We establish properties of disparity D codes showing that they have many of the properties of zero disparity codes. We give existence criteria for them, and discuss how new codewords may be formed from ones already known. We then discuss Kth order disparity D codes that have the same number of codewords. We discuss the minimum distance properties of these new codes and present a decoding algorithm for them. In the second part of the paper we look at how the minimum distance of disparity D codes can be improved. We consider subsets of a very specialised subclass, namely first order zero disparity codes over alphabet Aq of size q. These particular subsets have q codewords of length n and minimum Hamming distance n. We show that such a subset exists when q is even and nis a multiple of 4, and also when q is odd and n is even. These subsets have the best error correction capabilities of any subset of q first order zero disparity codewords.     

The Two-Point Codes with the Designed Distance on a Hermitian Curve in Even Characteristic

In Homma M and Kim SJ [2], the authors considered two-point codes on a Hermitian curve defined over fields of odd characteristic. In this paper, we study the geometry of a Hermitian curve over fields of even characteristic and classify the two-point codes whose minimum distances agree with the designed ones.     

Minimum distance of linear codes and the α-invariant

The simple interpretation of the minimum distance of a linear code obtained by De Boer and Pellikaan, and later refined by the second author, is further developed through the study of various finitely generated graded modules. We use the methods of commutative/homological algebra to find connections between the minimum distance and the α-invariant of such modules.     

Structural properties and tractability results for linear synteny

The syntenic distance between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted form of this model, has been shown to be close to the syntenic distance. Both models are computationally difficult to compute and have resisted efficient approximation algorithms with non-trivial performance guarantees. In this paper, we prove that many useful properties of syntenic distance carry over to linear syntenic distance. We also give a reduction from the general linear synteny problem to the question of whether a given instance can be solved using the maximum possible number of translocations. Our main contribution is an algorithm exactly computing linear syntenic distance in nested instances of the problem. This is the first polynomial time algorithm exactly solving linear synteny for a non-trivial class of instances. It is based on a novel connection between the syntenic distance and a scheduling problem that has been studied in the operations research literature.     

Nonparametric Estimation of Distributions in Random Effects Models

We propose using minimum distance to obtain nonparametric estimates of the distributions of components in random effects models. A main setting considered is equivalent to having a large number of small datasets whose locations, and perhaps scales, vary randomly, but which otherwise have a common distribution. Interest focuses on estimating the distribution that is common to all datasets, knowledge of which is crucial in multiple testing problems where a location/scale invariant test is applied to every small dataset. A detailed algorithm for computing minimum distance estimates is proposed, and the usefulness of our methodology is illustrated by a simulation study and an analysis of microarray data. Supplemental materials for the article, including R-code and a dataset, are available online.     

强定向图的k-强距离

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界.     

Constructions of Sidon spaces and cyclic subspace codes

In this paper, we firstly construct several new kinds of Sidon spaces and Sidon sets by investigating some known results. Secondly, using these Sidon spaces, we will present a construction of cyclic subspace codes with cardinality τ · $\frac{{{q^n} - 1}}{{q - 1}}$ and minimum distance 2k−2, where τ is a positive integer. We furthermore give some cyclic subspace codes with size 2τ · $\frac{{{q^n} - 1}}{{q - 1}}$ and without changing the minimum distance 2k−2.