Successive-Cancellation Decoding of Linear Source Code

This paper investigates the error probability of several decoding methods for a source code with decoder side information, where the decoding methods are: 1) symbol-wise maximum a posteriori decoding, 2) successive-cancellation decoding, and 3) stochastic successive-cancellation decoding. The proof of the effectiveness of a decoding method is reduced to that for an arbitrary decoding method, where ‘effective’ means that the error probability goes to zero as the block length goes to infinity. Furthermore, we revisit the polar source code showing that stochastic successive-cancellation decoding, as well as successive-cancellation decoding, is effective for this code.