Nested Sparse Feedback Codes for Point-to-Point, Multiple Access, and Random Access Channels

This paper investigates variable-length feedback codes for discrete memoryless channels in point-to-point, multiple access, and random access communication. The proposed nested code employs ..L.. decoding times ..n_1, n_2, \dots, n_L.. for the point-to-point and multiple access channels and ..KL.. decoding times ..\{n_{k, \ell} \colon 1 \leq k \leq K, 1 \leq \ell \leq L\}.. for the random access channel with at most ..K.. active transmitters; in the latter case, decoding times ..n_{k, \ell}.., ..1 \leq \ell \leq L.. are reserved for decoding in the scenario where the decoder believes that the number of active transmitters is ..k... The code has a nested structure, i.e., codewords used to decode messages from ..k.. active transmitters are prefix of codewords used to decode messages from ..k + 1.. active transmitters. The code employs single-bit, scheduled feedback from the receiver to the transmitters at each potential decoding time to inform the transmitters whether or not it is able to decode. Transmitters cease transmission, thereby truncating their codewords, when no further transmissions are required by the decoder. The choice of decoding times is optimized to minimize the expected decoding time subject to an error probability constraint, and second order achievability bounds are derived.