Dimension of a Subset of Residue Classes

This paper introduces a problem in additive number theory which is motivated by optimization of hardware implementation of QC-LDPC codes. For a fixed subset S, S ⊂ℤq, of residue classes modulo q the object of interest is a basis set G, G ⊂ℤq, of minimal size, such that every element of S is representable as a sum of several elements from G. For a fixed number k, k ≤⌈log2q⌉, the object of interest is a function ζ(q,k) defined as a maximum number such that, for every set of cardinality <; ζ(q,k), there exists a basis set of cardinality <; k.