Signature Codes for a Noisy Adder Multiple Access Channel

In this work, we consider q-ary signature codes of length k and size n for a noisy adder multiple access channel. A signature code in this model has the property that any subset of codewords can be uniquely reconstructed based on any vector that is obtained from the sum (over integers) of these codewords. We show that there exists an algorithm to construct a signature code of length k = 2n log 3/(1-2 tau)(log n+( q-1) log pi/2) + O (n/log n( q+log n)) capable of correcting tau k errors at the channel output, where 0 <= tau < q-1/2q. Furthermore, we present an explicit construction of signature codewords with polynomial complexity being able to correct up to (q-1/8q - epsilon) k errors for a codeword length k = O (n/log log n), where epsilon is a small non-negative number. Moreover, we prove several non-existence results (converse bounds) for q-ary signature codes enabling error correction.