Real-Time Coding for Multiple Access Channels

We consider a multiple access channel shared by two sources. The channel is noiseless but there is interference between the transmissions of the sources. Because of applications to distributed control we are interested in the real-time version of this problem, in which the receiver must act immediately upon received information. Block coding is therefore not possible, and error probability cannot generally be made to tend to 0 in the interior of the multiple access capacity region. We study code design for a simple class of XOR channels. We provide several computationally efficient design methods. Under an assumption on the form of the correlation among the sources, one of these algorithms provides codes whose success probability is within 2/3 of optimal. In the absence of assumptions on the correlation, optimal code design is NP-hard.