Improved Bounds for Quaternary Linear Codes of Dimension 6

In this paper, twenty new codes of dimension 6 are presented which give improved bounds on the maximum possible minimum distance of quaternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. A table of upper and lower bounds for d ⁴(n,6) is presented for n≤ 200. Received: 20 December 1996 / Accepted: 13 May 1997     

The number of MDS [7, 3] codes on finite fields of characteristic 2

A code of lengthn, dimensionk and minimum distanced ismaximum distance separable (MDS) ifk+d=n+1. We give the number of MDS codes of length 7 and dimension 3 on finite fields withq elements whereq=2 ^m . In order to get this number, we compute the number of configurations of seven points in the projective plane overF _q , no three of which are collinear.     

Bounds on the Weight Hierarchies of Extremal Non-chain Codes of Dimension 4

 The weight hierarchy of a linear [n, k; q] code C over GF(q) is the sequence (d ₁, d ₂, . . . , d _k ) where d _r is the smallest support of an r-dimensional subcode of C. An [n, k; q] code is external non-chain if for any r and s, where 1≦r<s≦k, there are no subspaces D and E, such that D⊂E, dim D=r, dim E=s, w _S (D)=d _r , and w _S (E)=d _s . Bounds on the weight hierarchies of such codes of dimension 4 are studied. Received: September 27, 1996     

1-Perfect Uniform and Distance Invariant Partitions

Let F ⁿ be the n-dimensional vector space over ℤ₂. A (binary) 1-perfect partition of F ⁿ is a partition of F ⁿ into (binary) perfect single error-correcting codes or 1-perfect codes. We define two metric properties for 1-perfect partitions: uniformity and distance invariance. Then we prove the equivalence between these properties and algebraic properties of the code (the class containing the zero vector). In this way, we characterize 1-perfect partitions obtained using 1-perfect translation invariant and not translation invariant propelinear codes. The search for examples of 1-perfect uniform but not distance invariant partitions enabled us to deduce a non-Abelian propelinear group structure for any Hamming code of length greater than 7. Received: March 6, 2000; revised version: November 30, 2000     

Maximum Distance Separable Convolutional Codes

A maximum distance separable (MDS) block code is a linear code whose distance is maximal among all linear block codes of rate k/n. It is well known that MDS block codes do exist if the field size is more than n. In this paper we generalize this concept to the class of convolutional codes of a fixed rate k/n and a fixed code degree δ. In order to achieve this result we will introduce a natural upper bound for the free distance generalizing the Singleton bound. The main result of the paper shows that this upper bound can be achieved in all cases if one allows sufficiently many field elements. Received: December 10, 1998; revised version: May 14, 1999     

Matrix-Product Codes over ? q

Codes C ₁ ,…,C _M of length n over ? _q and an M × N matrix A over ? _q define a matrix-product code C = [C ₁ …C _M ] ·A consisting of all matrix products [c ₁ … c _M ] ·A. This generalizes the (u|u+v)-, (u+v+w|2u+v|u)-, (a+x|b+x|a+b+x)-, (u+v|u-v)- etc. constructions. We study matrix-product codes using Linear Algebra. This provides a basis for a unified analysis of |C|, d(C), the minimum Hamming distance of C, and C ^⊥. It also reveals an interesting connection with MDS codes. We determine |C| when A is non-singular. To underbound d(C), we need A to be `non-singular by columns (NSC)'. We investigate NSC matrices. We show that Generalized Reed-Muller codes are iterative NSC matrix-product codes, generalizing the construction of Reed-Muller codes, as are the ternary `Main Sequence codes'. We obtain a simpler proof of the minimum Hamming distance of such families of codes. If A is square and NSC, C ^⊥ can be described using C ₁ ^⊥, …,C _M ^⊥ and a transformation of A. This yields d(C ^⊥). Finally we show that an NSC matrix-product code is a generalized concatenated code. Received: July 20, 1999; revised version: August 27, 2001     

Maximal AMDS codes

Complete (n, k)-arcs in PG(k − 1, q) and projective (n, k) _q -AMDS codes that admit no projective extensions are equivalent objects. We show that projective AMDS codes of reasonable length admit only linear extensions. Thus, we are able to prove the maximality of many known linear AMDS codes. At the same time our results sharply limit the possibilities for constructing long nonlinear AMDS codes. We also show that certain short linear AMDS codes are maximal. Central to our approach is the Bruen–Silverman model of linear codes first introduced in Alderson (On MDS codes and Bruen–Silverman codes. Ph.D. Thesis, University of Western Ontario, 2002) and Alderson et al. (J. Combin. Theory Ser. A 114(6), 1101–1117, 2007). The authors acknowledge support from the N.S.E.R.C. of Canada.     

Toric Codes over Finite Fields

In this note, a class of error-correcting codes is associated to a toric variety defined over a finite field _q, analogous to the class of AG codes associated to a curve. For small q, many of these codes have parameters beating the Gilbert-Varshamov bound. In fact, using toric codes, we construct a (n,k,d)=(49,11,28) code over ₈, which is better than any other known code listed in Brouwers tables for that n, k and q. We give upper and lower bounds on the minimum distance. We conclude with a discussion of some decoding methods. Many examples are given throughout.     

Bounds for traces in complete intersections and degrees in the Nullstellensatz

In this paper we obtain an effective Nullstellensatz using quantitative considerations of the classical duality theory in complete intersections. Letk be an infinite perfect field and let f₁,...,f n–rk[X₁,...,X_n] be a regular sequence with d:=max_j deg f_j. Denote byA the polynomial ringk [X₁,..., X_r] and byB the factor ring k[X₁,...,X_n]/(f₁,...,f_n r); assume that the canonical morphism AB is injective and integral and that the Jacobian determinant with respect to the variables X_r+1,...,X_n is not a zero divisor inB. Let finally B^*:=Hom_A(B, A) be the generator of B^* associated to the regular sequence.We show that for each polynomialf the inequality deg (¯f) dⁿ r(+1) holds (¯fdenotes the class off inB and is an upper bound for (n–r)d and degf). For the usual trace associated to the (free) extensionA B we obtain a somewhat more precise bound: deg Tr(¯f) dⁿ r degf. From these bounds and Bertini's theorem we deduce an elementary proof of the following effective Nullstellensatz: let f₁,..., f_s be polynomials in k[X₁,...,X_n] with degrees bounded by a constant d2; then 1 (f₁,..., f_s) if and only if there exist polynomials p₁,..., p_sk[X₁,..., X_n] with degrees bounded by 4n(d+ 1)ⁿ such that 1=_ip_if_i. in the particular cases when the characteristic of the base fieldk is zero ord=2 the sharper bound 4ndⁿ is obtained.Partially supported by UBACYT and CONICET (Argentina)     

A Problem of Ranking and Estimation With Poisson Processes

There are given k Poisson processes with parameters (rates of occurrence) λ₁, …, λ _k . Let λ₍₁₎ ≤ λ₍₂₎ ≤ … ≤ λ_(k) denote the ordered set of values of the parameters. A procedure is given for selecting the process corresponding to λ_(k) and estimating its parameter (λ_(k)). The given procedure controls the joint risk of improper selection and of large error in the estimate. Let θ > 1 and 0 < α, β < 1 be given numbers, and let δ denote the estimate of λ_(k). The joint probability that a correct selection is made and that |(δ/λ_(k)) ? 1| ≤ α is at least as large as β, for (λ_(k)/λ_(k?1)) ≥ θ. Two cases are considered, that is, when the processes are observed continuously in time, and when they are observed at successive intervals of time. Both the cases lead to the same theoretical results.     

Two “Dual” Families of Nearly-Linear Codes over ℤ p , p odd

Since the paper by Hammons e.a. [1], various authors have shown an enormous interest in linear codes over the ring ℤ₄. A special weight function on ℤ₄ was introduced and by means of the so called Gray map ϕ : ℤ₄→ℤ₂ ² a relation was established between linear codes over ℤ₄ and certain interesting non-linear binary codes of even length. Here, we shall generalize these notions to codes over ℤ _p2 where p is an arbitrary prime. To this end, a new weight function will be proposed for ℤ _p2 . Further, properties of linear codes over ℤ _p2 will be discussed and the mapping ϕ will be generalized to an isometry between ℤ _p2 and ℤ _p ^p , resp. between ℤ _p2 ⁿ and ℤ _p ^pn . Some properties of Galois rings over ℤ _q will be described and two dual families of linear codes of length n = p ^m − 1, gcd(m, p) = 1, over ℤ _q will be constructed. Taking q = p ², their images under the new mapping can be viewed as a generalization of the binary Kerdock and the Preparata code, although they miss some of their nice combinatorial properties. Received: June 19, 2000; revised version: November 6, 2000     

On a signal processing algorithms based class of linear codes

In this work, the correspondence between linear (n,k,d) codes and aperiodic convolution algorithms for computing a system ofk bilinear forms over GF(p^m) is explored. A number of properties are established for the linear codes that can be obtained from a computational procedure of this type. A particular bilinear form is considered and a class of linear codes over GF(2^m) is derived with varyingk andd parameters. The code lengthn is equal to the multiplicative complexity of the computation of an aperiodic convolution and an efficient computation thereof leads to the shortest codes possible using this approach, many of which are optimal or near-optimal. A new decoding procedure for this class of linear codes is presented which exploits the block structure of the generator matrix of the codes. Several interesting observations are made on the nature of the codes obtained as a result of such computations. Such a computation of bilinear forms can be generalized to include other bilinear forms and the related classes of codes.     

Optimal Formally Self-Dual Codes over ?5 and ?7

In this paper, we study optimal formally self-dual codes over ?₅ and ?₇. We determine the highest possible minimum weight for such codes up to length 24. We also construct formally self-dual codes with highest minimum weight, some of which have the highest minimum weight among all known linear codes of corresponding length and dimension. In particular, the first known [14, 7, 7] code over ?₇ is presented. We show that there exist formally self-dual codes which have higher minimum weights than any comparable self-dual codes. Received: May 18, 1998; revised version: September 4, 1999     

On liouvillian solutions of linear differential equations

This paper deals with the problem of finding liouvillian solutions of a homogeneous linear differential equationL(y)=0 of ordern with coefficients in a differential fieldk. For second order linear differential equations with coefficients ink _o(x), wherek _o is a finite algebraic extension ofQ, such an algorithm has been given by J. Kovacic and implemented. A general decision procedure for finding liouvillian solutions of a differential equation of ordern has been given by M.F. Singer, but the resulting algorithm, although constructive, is not in implementable form even for second order equations. Both algorithms use the fact that, ifL(y)=0 has a liouvillian solution, then,L(y)=0 has a solutionz such thatu=z/z is algebraic overk. Using the action of the differential galois group onu and the theory of projective representation we get sharp bounds (n) for the algebraic degree ofu for differential equations of arbitrary ordern. For second order differential equations we get the bound (2)=12 used in the algorithm of J. Kovacic and for third order differential equation we improve the bound given by M.F. Singer from 360 to (3)36. We also show that not all values less than or equal to (n) are possible values for the algebraic degree ofu. For second order differential equations we rediscover the values 2, 4, 6, and 12 used in the Kovacic Algorithm and for third order differential equations we get the possibilities 3,4, 6, 7, 9, 12, 21, and 36. We prove that if the differential Galois group ofL(y)=0 is a primitive unimodular linear group, then all liouvillian solutions are algebraic. From this it follows that, if a third order differential equationL(y)=0 is not of Fuchsian type, then the logarithmic derivative of some liouvillian solution ofL(y)=0 is algebraic of degree 3. We also derive an upper bound for the minimal numberN(n) of possible degreesm of the minimal polynomial of an algebraic solution of the riccati equation associated withL(y)=0.Supported by Deutsche Forschungsgemeinschaft while visiting North Carolina State University     

On the Lattice Structure of Pseudorandom Numbers Generated over Arbitrary Finite Fields

Marsaglia's lattice test for congruential pseudorandom number generators modulo a prime is extended to a test for generators over arbitrary finite fields. A congruential generator η₀,η₁,…, generated by η _n =g(n), n = 0, 1,…, passes Marsaglia's s-dimensional lattice test if and only if s≤ deg(g). It is investigated how far this conditin holds true for polynomials over arbitrary finite fields F _q , particularly for polynomials of the form g _d (x)=α(x+β) ^d +γ, α, β, γ∈F _q , α≠ 0, 1 ≤d≤q− 1. Received: December 13, 1999; revised version: November 17, 2000     

Sample size required to estimate a parameter in the power function distribution

The purpose of this paper is to establish a two step sampling procedure for estimating the parameter θ of the power function distribution to within givend units of its true value with a given probability 1—α;(0<α<1). The density of the power function distribution is a function of two parameters, the second of whichk is assumed known. Given a preliminary sample sizem, tables and formulas are presented by which one may establish the sizen of the second sample such thatP(|y _n —θ|<d)>1—α is true, wherey _n is the largest observation in the second sample. The method used is deriving the results of this paper is similar to that given by Graybill and Connell (1964) and since the power function density reduces to the uniform density whenk=0, their results can be derived from the formulas given here. Also a table of comparisons between the expected second sample size in this paper and two other solutions is given.

---

Sumario El propósito de este escrito es el de establecer un procedimiento de muestreo de dos pasos, para estimar el parámetro de la distribución de funciones de potencia cerca ded unidades de su valor verdadero con una probabilidad 1—α;(0<0<α<1). la densidad de la distribución de funciones de potencia es una función de dos parámetros, el segundo de los cualesk se supone es conocido. Dado un tama?o de muestra preliminarm, se presentan tabulaciones y fórmulas con las cuales se puede establecer el tama?on de la segunda muestra, de tal manera queP(|y _n —θ|<d)>1—α sea cierto, dondey _n es la observación más grande en la segunda muestra. El método usado en la derivación de los resultados de este escrito es similar al dado por Graybill y Connell (1964, Journal of the American Statistical Association) y ya que la densidad de funciones de potencia se reduce a la densidad uniforme cuandok=0, sus resultados pueden ser derivados a partir de las fórmulas dadas aquí. Además, se presenta una tabulación de comparaciones entre el segundo tama?o de muestra dado en este escrito y otras dos soluciones. Lafdp de la distribución de funciones de potencia es de la formaf(u)=(k+1)θ ^−(k+1) u ^k ,0<u<θ, θ>0 y cero en cualquiera otra parte.

---

---

Research supported under ONR contract N00014-68-A-0515.     

Summaries of New Books

Let X ₍₁₎, …, X _(k) be the first k ordered observations of a sample of size m from the distribution with p.d.f. f(x; β₁, θ) = (1/θ) exp [-(x – β₁)/θ] for x ≥ β₁ ≥ 0, θ > 0 and zero elsewhere (2 ≤ k ≤ m); let Y _(i), …, Y _(l) be the first l ordered observations of a sample of size n from the distribution with p.d.f. g(y; β₂, θ) = (1/θ) exp [—(y – β₂)/θ] for y ≥ β₂ ≥ 0, θ > 0 and zero elsewhere (2 ≤ l ≤ n). It is assumed that θ is unknown. A test based on (X ₍₁₎, …, X _(k), Y ₍₁₎, …, Y _(l)) is proposed for the null hypothesis β₁ = β₂ against the alternative β₁ ≠ β₂. The distribution of the test statistic under the null hypothesis is derived. The significance points for various values of k, I, m, n are tabulated for (α = .05 and .Ol.     

Electrical properties of V<Subscript>2</Subscript>O<Subscript>5</Subscript>-CaO-P<Subscript>2</Subscript>O<Subscript>5</Subscript> glasses exhibiting majority charge carrier reversal

The thermoelectric power and d.c electrical conductivity of x V₂O₅⋅40CaO⋅(60−x)P₂O₅ (10 ≤ x ≤ 30) glasses were measured. The Seebeck coefficient (Q) varied from +88 μ V K⁻¹ to −93 μV K⁻¹ as a function of V₂O₅ mol%. Glasses with 10 and 15 mol% V₂O₅ exhibited p-type conduction and glasses with 25 and 30 mol% V₂O₅ exhibited n-type conduction. The majority charge carrier reversal occurred at x = 20 mol% V₂O₅. The variation of Q was interpreted in terms of the variation in vanadium ion ratio (V^{5 +}/V^{4 +}). d.c electrical conduction in x V₂O₅⋅40CaO⋅(60−x)P₂O₅ (10 ≤ x ≤ 30) glasses was studied in the temperature range of 150 to 480 K. All the glass compositions exhibited a cross over from small polaron hopping (SPH) to variable range hopping (VRH) conduction mechanism. Mott parameter analysis of the low temperature data gave values for the density of states at Fermi level N (E_F) between 1.7 × 10²⁶ and 3.9 × 10²⁶ m⁻³ eV⁻¹ at 230 K and hopping distance for VRH (R_VRH) between 3.8 × 10⁻⁹m to 3.4 × 10⁻⁹ m. The disorder energy was found to vary between 0.02 and 0.03 eV. N (E_F) and R_VRH exhibit an interesting composition dependence.     

Note on the g-fold Joint Weight Enumerators of Self-Dual Codes over ℤ k

Recently there has been interest in self-dual codes over finite rings. In this note, g-fold joint weight enumerators of codes over the ring ℤ _k of integers modulo k are introduced as a generalization of the biweight enumerators. We establish the MacWilliams relations for these weight enumerators and investigate the biweight enumerators of self-dual codes over ℤ _k . We derive Gleason-type theorems for the corresponding biweight enumerators with the help of invariant theory. Received: March 13, 2000; revised version: December 11, 2000     

Limit laws for maxima of a stationary random sequence with random sample size

Let {X _n } be a stationary sequence and {k _n } be a nondecreasing sequence such that k _n+1/k _n →r≥1. Assume that the limit distribution G of M_knM_{k_{n}} with an appropriate linear normalization exists. We consider the maxima M _n =max {X _i ,i≤n} sampled at random times T _n , where T _n /k _n converges in probability to a positive random variable D, and show that the limit distribution of M_TnM_{T_{n}} exists under weak mixing conditions. The limit distribution of M_TnM_{T_{n}} is a mixture of G and the distribution of D.