Weighted Hamming metric structures

It is known that the binary generalized Goppa codes are perfect codes for the weighted Hamming metrics. In this paper, we present the existence of a weighted Hamming metric that admits a binary Hamming code (resp. an extended binary Hamming code) to be perfect code. For a special weighted Hamming metric, we also give some structures of a 2-perfect code, show how to construct a 2-perfect linear code and obtain the weight distribution of a 2-perfect code from the partial information of the code.     

Concatenation of convolutional codes and rank metric codes for multi-shot network coding

In this paper we present a novel coding approach to deal with the transmission of information over a network. In particular we make use of the network several times (multi-shot) and impose correlation in the information symbols over time. We propose to encode the information via an inner and an outer code, namely, a Hamming metric convolutional code as an outer code and a rank metric code as an inner code. We show how this simple concatenation scheme can exploit the potential of both codes to produce a code that can correct a large number of error patterns.     

A group ring construction of the [48,24,12] type II linear block code

A new construction of the self-dual, doubly-even and extremal [48, 24, 12] binary linear block code is given. The construction is much like that of a cyclic code from a polynomial. A zero divisor in a group ring with an underlying dihedral group generates the code. A proof that the code is of minimum distance twelve, without need to resort to computation by computer, is outlined. We also prove the code is self-dual, doubly even and that the code is an ideal in the group ring. The underlying group ring structure is used, which offers a number of useful generator matrices for the code. Interestingly, the construction involves unipotent elements within the group ring, and these lead to the creation of weighing matrices.     

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

极大前缀码的一些性质

设X+(X~*)是由字母表X生成的自由(幺)半群且A是X~*的非空子集,如果A∩AX+=φ,则称A是前缀码.如果前缀码A满足:对任意ω∈X+\A,有A∪{ω}不是前缀码,则称A是极大前缀码.给出了极大前缀码的一些性质,并推广了相关文献的结果.     

Linear error-block codes

A linear error-block code is a natural generalization of the classical error-correcting code and has applications in experimental design, high-dimensional numerical integration and cryptography. This article formulates the concept of a linear error-block code and derives basic results for this kind of code by direct analogy to the classical case. Some problems for further research are raised.     

一种求循环码对偶码的新方法

本文应用离散傅里叶变换来分析有限域上时域多项式环和它的频域多项式环之间的同构,从另一角度提出了一种由循环码单位元生成它的对偶码的新方法。本文还建立了循环码单位元与它的频域单位元之间的联系,由此可以很方便地生成它的对偶码,理论和实例表明这种方法是行之有效的。     

Experiments with a variable-order type 1 DIMSIM code

The issues related to the development of a new code for nonstiff ordinary differential equations are discussed. This code is based on the Nordsieck representation of type 1 DIMSIMs, implemented in a variable-step size variable-order mode. Numerical results demonstrate that the error estimation employed in the code is very reliable and that the step and order changing strategies are very robust. This code outperforms the Matlab ode45 code for moderate and stringent tolerances. This revised version was published online in August 2006 with corrections to the Cover Date.     

An optimal ternary [69, 5, 45] code and related codes

A ternary [69, 5, 45] code is constructed, thus solving the problem of finding the minimum length of a ternary code of dimension 5 and minimum distance 45. Furthermore, this code is shown to be a unique two-weight code with weight enumerator 1+210Z⁴⁵+32Z⁵⁴. It is also shown that a ternary [70, 6, 45] code, which would have been a projective two-weight code giving rise to a new strongly regular graph, does not exist. In order to prove the main results, the uniqueness of some other optimal ternary codes with specified weight enumerators is also established.     

An implementation of linear and nonlinear multicommodity network flows

This work presents a new code for solving the multicommodity network flow problem with a linear or nonlinear objective function considering additional linear side constraints that link arcs of the same or different commodities. For the multicommodity network flow problem through primal partitioning the code implements a specialization of Murtagh and Saunders' strategy of dividing the set of variables into basic, nonbasic and superbasic. Several tests are reported, using random problems obtained from different network generators and real problems arising from the fields of long and short-term hydrothermal scheduling of electricity generation and traffic assignment, with sizes of up to 150000 variables and 45 000 constraints The performance of the code developed is compared to that of alternative methodologies for solving the same problems: a general purpose linear and nonlinear constrained optimization code, a specialised linear multicommodity network flow code and a primal-dual interior point code.     

Construction of a (64, 2 37, 12) Code via Galois Rings

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock and Preparata codes, which exist for all lengths 4^m 16. At length 16 they coincide to give the Nordstrom-Robinson code. This paper constructs a nonlinear (64, 2₃₇, 12) code as the binary image, under the Gray map, of an extended cyclic code defined over the integers modulo 4 using Galois rings. The Nordstrom-Robinson code is defined in this same way, and like the Nordstrom-Robinson code, the new code is better than any linear code that is presently known.     

New uniqueness proofs for the (5, 8, 24), (5, 6, 12) and related Steiner systems

New elementary proofs of the uniqueness of certain Steiner systems using coding theory are presented. In the process some of the codes involved are shown to be unique.The uniqueness proof for the (5, 8, 24) Steiner system is due to John Conway. The blocks of the system are used to generate a length 24 binary code. Any two such codes are then shown to be equivalent up to a permutation of the coordinates. This code turns out to be the extended Golay code.In the uniqueness proof for the (4, 7, 23) system, the blocks generate a length 23 code which is extended to a length 24 code. The minimum weight vectors of this larger code hold a (5, 8, 24) Steiner system. This result together with the previous one completes the proof. At this point it is also possible to conclude that the codes involved are unique and hence equivalent to the binary perfect Golay code and its extension.Continuing with the uniqueness result for the (3, 6, 22) Steiner system, the blocks generate a length 22 code which is extended to the same length 24 code by the addition of two coordinates and one additional vector. This extension ultimately requires the computation of the coset weight distribution of the length 22 code, a result heretofore unknown. The complete coset weight distribution for a specific (22, 11, 6) self-dual code is computed using the CAMAC computer system.The (5, 6, 12) and (4, 5, 11) Steiner systems are treated differently. It is shown that each system is completely determined by the choice of six blocks which may be assumed to lie in any such design. These six blocks in fact form a basis for length 12 (and 11) ternary codes corresponding to the two systems and may be generated by an algorithm independent of the designs. This algorithm is presented and the minimum weight vectors of the resulting codes, the perfect ternary Golay code and its extension, are calculated by the CAMAC system.     

第二类窃密信道中的组合数学方法

当信息在第二类窃密信道中传输时,线性码的广义汉明重量谱完全描述的它在该信道中的密码学特征.计算一个线性码的广义汉明重量谱是一个基本问题,首先提出了线性码的“最简基”的概念.在此基础上给出了一般线性码子码的几种计数公式,并给出了它们之间等价性的证明.     

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.     

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

环$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.     

Data compression and histograms

Summary In this paper, the relationship between code length and the selection of the number of bins for a histogram density is considered for a sequence of iid observations on [0,1]. First, we use a shortest code length criterion to select the number of bins for a histogram. A uniform almost sure asymptotic expansion for the code length is given and it is used to prove the asymptotic optimality of the selection rule. In addition, the selection rule is consistent if the true density is uniform [0,1]. Secondly, we deal with the problem: what is the best achievable average code length with underlying density functionf? Minimax lower bounds are derived for the average code length over certain smooth classes of underlying densitiesf. For the smooth class with bounded first derivatives, the rate in the lower bound is shown to be achieved by a code based on a sequence of histograms whose number of bins is changed predictively. Moreover, this best code can be modified to ensure that the almost sure version of the code length has asymptotically the same behavior as its expected value, i.e., the average code length.Research supported in part by NSF grant DMS-8701426Research supported in part by NSF grant DMS-8802378     

Perfect codes from the dual point of view I

The two concepts dual code and parity check matrix for a linear perfect 1-error correcting binary code are generalized to the case of non-linear perfect codes. We show how this generalization can be used to enumerate some particular classes of perfect 1-error correcting binary codes. We also use it to give an answer to a problem of Avgustinovich: whether or not the kernel of every perfect 1-error correcting binary code is always contained in some Hamming code.     

Fuzzy codes and distance properties

A fuzzy code is defined as a fuzzy subset of n-tuples over a set F. An analysis of the Hamming distance between two fuzzy codewords and the error-correcting capability of a regular code in terms of its corresponding fuzzy code is presented.