Two-user tree codes are considered for use on an arbitrary two-user discrete memoryless multiple-access channel (MAC). A two-user tree Is employed to achieve true maximum likelihood (ML) decoding of two-user tree codes on MAC's. Each decoding error event has associated with it a configuration indicating the specific time slots in which a decoding error has occurred for the first user alone, for the second user alone, or for both users simultaneously. Even though there are many possible configurations, it is shown that there are five fundamental configuration types. An upper bound on decoding error probability, similar to Liao's result for two-user block codes, is derived for sets of error events having a particular configuration. The total ML decoding error probability is bounded using a union bound first over all configurations of a given type and then over the five configuration types. A two-user tree coding error exponent is defined and compared with the corresponding block coding result for a specific MAC. It is seen that the tree coding error exponent is larger than the block coding error exponent at all rate pairs within the two-user capacity region. Finally, a new lower bound on free distance for two-user codes is derived using the same general technique used to bound the error probability.

Binary convolutional (linear) code pairs are investigated for use on the two-user adder channel. Maximum likelihood decoding is discussed, and a two-user decoding trellis is defined. The L-free distance of a convolutional code pair is defined and shown to be equal to the free distance of the mod-2 sum of the two single-user codes. It follows that the code pair is uniquely decodable if and only if the mod-2 sum code has an inverse, and that the code pair is subject to catastrophic error propagation if and only if the mod-2 sum code is catastrophic. These results also imply that no uniquely decodable binary convolutional (linear) code pairs exist with a rate sum above time sharing.