Optimal Learning Rate of Sending One Bit Over Arbitrary Acyclic BISO-Channel Networks
Chih-Chun Wang, David J. Love · 2023
This work considers the problem of sending a 1-bit message over an acyclic network, where the “edge” connecting any two nodes is a memoryless binary-input/symmetric-output (BISO) channel. For any arbitrary acyclic network topology and constituent channel models, a min-cut-based converse of the learning rate, denoted by r*, is derived. It is then shown that for any r*, one can design a scheme with learning rate r. Capable of approaching the optimal r*, the proposed scheme is thus the asymptotically fastest for sending one bit over any acyclic BISO-channel network. The construction is based on a new concept of Lossless Amplify-&-Forward, a sharp departure from existing multi-hop communication scheme designs.