Antiblocking systems and PD-sets (Q2468024): Difference between revisions

Permutation decoding is a decoding technique developed by F. J. MacWilliams which uses a subset of the automorphism group of the linear code. A \textit{PD}-set for a \(t\)-error-correcting linear code \(C\) is a set \(S\) of automorphisms of the code which is such that every possible error vector of weight \(t\) or less can be moved by some member of \(S\) out of the information positions. The permutation decoding algorithm is more efficient the smaller the size of the PD-set. A lower bound on this size is given in \textit{D. M. Gordon} [IEEE Trans. Inf. Theory 28, 541--543 (1982; Zbl 0479.94021)]. The question is whether there is a PD-set \(S\) in the corresponding symmetric group such that the size \(| S| \) is the Gordon bound? The authors introduce the notion of an \textit{anti-blocking system} to find and discuss PD-sets. An \textit{anti-blocking system} \(U\) for a finite set \(P\) is a set of subsets of \(P\) such that for every subset \(B\) of \(P\) of size \(t\), there exists an element \(A\) in \(U\) such that \(A\cap B=\emptyset\). Using this notion of anti-blocking systems, the authors give examples where the Gordon bound is not sharp.