Codes with a poset metric (Q1910507): Difference between revisions

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.