TY - GEN

T1 - Linear universal decoding for compound channels

T2 - 2008 IEEE International Symposium on Information Theory, ISIT 2008

AU - Abbe, Emmanuel

AU - Zheng, Lizhong

PY - 2008

Y1 - 2008

N2 - On a discrete memoryless channel (DMC), the maximum likelihood (ML) decoding rule is not only optimal (for equiprobable messages and average error probability), but it is also linear (the metric that it maximizes is additive over the block length), which in particular, makes ML practically conceivable. On a compound DMC, the use of ML is ruled out by the channel's law ignorance. In order to account for this, the universal decoders proposed in[7],[10],[3],[9] can be employed. However, none of these decoders is linear. Hence, we consider the problem of finding good linear decoders for compound DMC's. We show that on most compound sets, when universality requires to be capacity achieving, there exists a universal decoding rule which is generalized linear, in the sense that it maximizes only a finite number of additive metrics. A local to global geometric method is developed to solve this problem. By considering very noisy channels, the global problem is reduced, in the limit, to an inner product space problem, for which insightful solutions can be found. We describe an heuristic method used, in this problem, to "lift" local results to global results.

AB - On a discrete memoryless channel (DMC), the maximum likelihood (ML) decoding rule is not only optimal (for equiprobable messages and average error probability), but it is also linear (the metric that it maximizes is additive over the block length), which in particular, makes ML practically conceivable. On a compound DMC, the use of ML is ruled out by the channel's law ignorance. In order to account for this, the universal decoders proposed in[7],[10],[3],[9] can be employed. However, none of these decoders is linear. Hence, we consider the problem of finding good linear decoders for compound DMC's. We show that on most compound sets, when universality requires to be capacity achieving, there exists a universal decoding rule which is generalized linear, in the sense that it maximizes only a finite number of additive metrics. A local to global geometric method is developed to solve this problem. By considering very noisy channels, the global problem is reduced, in the limit, to an inner product space problem, for which insightful solutions can be found. We describe an heuristic method used, in this problem, to "lift" local results to global results.

UR - http://www.scopus.com/inward/record.url?scp=52349096600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=52349096600&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2008.4595157

DO - 10.1109/ISIT.2008.4595157

M3 - Conference contribution

AN - SCOPUS:52349096600

SN - 9781424422579

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1098

EP - 1102

BT - Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008

Y2 - 6 July 2008 through 11 July 2008

ER -