Low Complexity Posterior Matching for Sequential Transmission Over The Binary Symmetric Channel with Noiseless Feedback
Amaael Antonini
Abstract:
Consider sequential transmission of a k-bit message over the binary symmetric channel (BSC) with noiseless feedback. Variable-length schemes usually aim to minimize the expected block-length, constrained to maximum frame error rate (FER). A common approach, pioneered by Horstein, is to partition the possible messages into two sets, and transmit a bit based on which set contains the intended message. Horstein’s scheme and others similar ones are referred to as posterior matching (PM), introduced by Shayevitz & Feder. Recently, Yang et. al. provided a lower bound on the achievable rate for this scenario. Their proof relies on a PM scheme that enforces certain constraints by utilizing the small-enough difference (SED) encoder, by Naghshvar et. al. This work shows that the same achievable rate can be achieved by any PM algorithm that satisfies more relaxed constraints. The new constraints admits a simpler partitioning rule, the Small Enough Absolute Difference (SEAD) rule. The SEAD rule facilitates a scheme with significantly reduced computational complexity. This work presents a three-phase systematic encoding PM algorithm that features reduced complexity by implementing the SEAD rule and simplifying the posterior updates. Simulations results show that this algorithm exceeds Yang’s lower bound on achievable rate.