Monday, July 16, 2007

A Favorite Open Problem : Codes for a Poisson-repeat Channel

A (binary) Poisson-repeat channel works as follows: the sender sends a sequence of n bits, and the channel independently replaces each bit with a number of copies (or repeats) that has a discrete Poisson distribution with mean 1. That is, for each bit, the probability that it is replaced by k copies is e^{-1}/k!. Here k can be 0, in which case the bit is deleted. The receiver gets the resulting string after replacements. I'd like to find an efficient code for this channel that has a non-trivial constant rate. Any rate over 0.01 , for example, would be just fine. Of course, I'd like the bound on the rate to be provable, rather than just experimental, and I really would like the code to be practical, not just polynomial-time encodable/decodable.

What's the motivation? It turns out that the Poisson-repeat channel is closely tied to the deletion channel, where each bit is independently deleted with probability p. A code for the Poisson-repeat channel would immediately yield a good code for the deletion channel for values of p is close to 1; we showed the reduction in this paper.

Codes for insertion/deletion channels are hard; very little is known. Because a code for this specific channel would yield codes for a larger family of channels, I think it's an appropriate and intriguing target.


Anonymous said...

Hi Mike,

I take it no upper bound is known for the i.i.d deletion channel capacity that is better than the erasure channel capacity?

For the case of adversarial deletion channel (where arbitrary fraction d of bits are deleted), let d_max be the largest value of d for which communication with positive rate is possible. Is any upper bound better than d_max \le 1/2
(again obtained by trivial reduction to erasures) known?

Any personal conjectures on either of these bounds?

Michael Mitzenmacher said...


Until recently, as far as I know, there was no better upper bound for the iid deletion channel than the erasure channel capacity -- but at ISIT this year, Diggavi, Pfister, and I presented a paper with some new non-trivial upper bounds. The submitted version is available on my web page; I'll put the final version up when I can.

For the adversarial deletion channel, I don't know of any non-trivial upper bound, but I haven't really thought about that case.