Coding for the blackwell channel: a survey propagation approach

Practical implementation of random binning is one of the key challenges in achieving the largest available rate regions for many multiuser channels. This paper explores the use of low-density parity-check (LDPC) like codes for a particular kind of deterministic broadcast channel called the Blackwell channel and illustrates that random linear codes can be used to construct practical binning schemes at rates close to the capacity region of the Blackwell channel. The key ingredient is an encoding algorithm known as "survey propagation" which is a generalization of the well-known belief propagation algorithm for LDPC codes. Survey propagation has been previously devised for a class of constraint satisfaction problems called K-SAT. This paper shows that the encoding problem for the Blackwell channel contains the same features as the constraint satisfaction problem and that the survey propagation algorithm, when concatenated with an outer error correcting code, works well at rates close to the Blackwell channel capacity region