Codes with a poset metric
type: Item
instance of: scholarly article
title: Codes with a poset metric
zbMATH Open document ID: 0854.94019
DOI: 10.1016/0012-365X(94)00228-B
author: Richard A. Brualdi
author: Janine Smolin Graves
author: K. Mark Lawrence
published in: Discrete Mathematics
publication date: 1996-03-24T00:00:00Z
review text: Let \(F^m_q\) be the vector space of \(m\)-tuples over the finite field \(\mathbb{F}_q\). The reviewer [Discrete Math. 96, 221-228 (1991; Zbl 0747.11063)] posed the following problem which generalizes a basic problem in algebraic coding theory. Let \(n_1, \dots, n_s\) be positive integers and let \(H= \{h_{i,j}: 1\leq j\leq n_i\), \(1\leq i\leq s\}\) be a system of \(\sum^s_{i=1} n_i\) vectors in \(F^m_q\) partitioned into \(s\) ordered sets of vectors of cardinalities \(n_1, \dots, n_s\), respectively. Define \(d(H)\) to be 1 plus the maximum integer \(t\) such that for all partitions of \(t\) into nonnegative parts \(t_1, \dots, t_s\) with \(t_i\leq n_i\) for \(1\leq i\leq s\), the vectors \(\{h_{i,j}: 1\leq j\leq t_i\), \(1\leq i\leq s\}\) are linearly independent. The problem is to determine the number \[ d_q (n_1, \dots, n_s; m)= \max d(H), \] where the maximum is taken over all systems \(H\). The authors observe that the index set here is a poset consisting of \(s\) disjoint chains of sizes \(n_1, \dots, n_s\), respectively, and they generalize the problem by considering an arbitrary poset of cardinality \(n\) and extend earlier results to this case. This approach leads also to new concepts in coding theory. For instance, if the poset is \(P= \{1, 2, \dots, n\}\) w.l.o.g., then the \(P\)-weight \(w_P (x)\) of \(x\in F^n_q\) is the cardinality of the smallest ideal of \(P\) containing the support of \(x\), and this yields the metric \(d_P (x, y)= w_P (x- y)\) on \(F^n_q\). The paper contains characterizations of perfect codes with respect to \(d_P\) in the cases where \(P\) is a chain or a union of two disjoint chains of equal size. It is also shown that there are simple posets \(P\) such that the extended binary Hamming codes and the extended Golay codes are perfect.
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 858048
zbMATH Keywords: poset
zbMATH Keywords: \(P\)-weight
zbMATH Keywords: perfect codes
zbMATH Keywords: extended binary Hamming codes
zbMATH Keywords: extended Golay codes
reviewed by: Harald Niederreiter
MaRDI profile type: Publication
cites work: Q4146667
cites work: Point sets and sequences with small discrepancy
cites work: A combinatorial problem for vector spaces over finite fields
cites work: Orthogonal arrays and other combinatorial aspects in the theory of uniform point distributions in unit cubes
cites work: Q3996427
full work available at URL: 0012-365x(94)00228-b
OpenAlex ID: W2043474783
description: scientific article; zbMATH DE number 858048