Error probability and free distance bounds for two-user tree codes on multiple-access channels

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.