Existence of directed bibds with block size 7 and related perfect 5-deletion-correcting codes of length 7 (Q1960227): Difference between revisions
From MaRDI portal
Latest revision as of 08:31, 3 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Existence of directed bibds with block size 7 and related perfect 5-deletion-correcting codes of length 7 |
scientific article |
Statements
Existence of directed bibds with block size 7 and related perfect 5-deletion-correcting codes of length 7 (English)
0 references
13 October 2010
0 references
A directed BIBD with parameters \((v, k, \lambda)\), denoted by DBIBD\((v, k, \lambda)\), is a pair \((X, {\mathcal B})\) where \(X\) is a \(v\)-set of points and \({\mathcal B}\) is a collection of ordered \(k\)-tuples \((a_1, a_2,\ldots, a_k )\) of elements of \(X\) with the property that every ordered pair of distinct points occurs \(\lambda\) times amongst the pairs \((a_i , a_ j )\) with \(i < j\) and \((a_1, a_2,\ldots, a_k )\in{\mathcal B}\). Directed BIBDs are closely related to certain other types of combinatorial structures such as perfect deletion-correcting codes and insertion-correcting codes. The existence of a DBIBD\((v, k, \lambda)\), clearly implies the existence of a \((v, k, 2\lambda)\)-BIBD. So the necessary conditions for the existence of a \((v, k, 2\lambda)\)-BIBD namely, \(2\lambda(v-1)\equiv0\pmod{k-1}\) and \(\lambda v(v-1)\equiv0\pmod{k(k-1)/2}\), are also necessary for the existence of a DBIBD\((v, k, \lambda)\). For \(k\in\{3, 4, 5, 6\}\), these conditions are already known to be sufficient, except for the non-existence of DBIBD\((5, 1, 15)\) and DBIBD\((6, 1, 21)\). The paper under review deals with DBIBD\((v, 7, 1)\). The existence of these designs for all \(v\equiv{1, 7}\pmod{21}\) except for \(v = 22\) and possibly for 68 other cases were already stablished by \textit{J. Wang} and \textit{J. Yin} [``Constructions for perfect 5-deletion-correcting codes of length 7,'' IEEE Trans. Inform. Theory. 52, 3676--3685 (2006)]. The authors reduce the number of possible exceptions to 4, namely \(v = 274\), \(358\), \(400\), \(526\). Correspondingly, for all such \(v\), they establish the existence of a perfect 5-deletion-correcting code with words of length 7 over an alphabet of size \(v\), where all the coordinates must be different. They also reduce the possible exceptions for \((v, 7, 2)\)-BIBDs to 2 cases, \(v = 274\) and \(358\) (in addition to the non-existent \((22, 7, 2)\)-BIBD). The authors make use of (directed) group divisable designs in the constructions.
0 references
BIBD
0 references
Directed BIBD (DBIBD)
0 references
Directed GDD (DGDD)
0 references