Recursive Constructions of Detecting Matrices for Multiuser Coding: A Unifying Approach

Detecting matrices are a class of combinatorial objects originated from the coin weighing problem of Soderberg and Shapiro in the early 1960s. In this paper, various known recursive construction techniques for binary, bipolar, and ternary detecting matrices are reexamined in a unifying framework. New, general recursive constructions of detecting matrices, which include previous recursive constructions as special cases, are derived. Such matrices find applications in multiuser coding since they are equivalent to a certain class of uniquely decodable multiuser codes for the binary adder channel. Interestingly, it is found that among the three kinds of detecting matrices, ternary detecting matrices are of fundamental significance from the combinatorial theoretic, as well as from the multiuser coding application, point of view.

I. Introduction

An matrix is detecting if and only if

$$Ax=Ay \quad \Longrightarrow \quad x=y \eqno{\hbox{(1)}}$$ for . An equivalent definition is $$Ae=0 \quad \Longrightarrow \quad e=0 \eqno{\hbox{(2)}}$$ for . A detecting matrix is said to be binary, bipolar, or ternary if and only if all of its entries belong to the set , or , respectively. Clearly, if a detecting matrix is binary or bipolar, it is also ternary. For example, $$A=\left[\matrix{1 & 0 & 1 & 1 \cr 1 & 1 & 0 & 0 \cr 0 & 1 & 1 & 0} \right] \quad {\hbox {and}} \quad D=\left[\matrix{1 & -1 & 1 \cr 1 & 1 & 0} \right]$$ are binary and ternary detecting matrices, respectively.