The technique of error-trapping decoding for algebraic codes is studied in combinatorial terms of covering systems. Let n, k , and t be positive integers such that n \geq k \geq t > 0 . An (n, k,t) -covering system is a pair (X, \beta) , where X is a set of size n and \beta is a collection of subsets of X , each of size k , such that for all T \subseteq X of size t , there exists at least one B \in \beta with T\subseteq B . Let b(n, k, t) denote the smallest size of \beta , such that (X, \beta) is an (n, k, t) -covering system. It is shown that the complexity of an error-trapping decoding technique is bounded by b(n, k, t) from below. Two new methods for constructing small (n, k, t) -covering systems, the algorithmic method and the difference family method, are given.
['Agnes Hui Chan', 'Richard A. Games']
(n,k,t))-covering systems and error-trapping decoding (Corresp.)