Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A bound for block codes with delayed feedback related to the sphere-packing bound

Harikrishna R Palaiyanur and Anant Sahai

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-61
May 12, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-61.pdf

This note attacks the open problem of the error-exponent with feedback for asymmetric discrete-memoryless channels. A partial result is obtained: the error exponent for rate-R codes used with perfect feedback delayed by T symbols is upper bounded by (for T large enough) E_{sp}(R - O(log T / T) ) + O(log T / T), where E_{sp} is the sphere-packing exponent and the constants depend on the channel transition matrix. This partially resolves the longstanding conjecture that the sphere-packing bound continues to govern block-codes with feedback by showing that it does so at least in the limit of long feedback delays. So either it must hold without such delays or something truly shocking is going on.


BibTeX citation:

@techreport{Palaiyanur:EECS-2009-61,
    Author = {Palaiyanur, Harikrishna R and Sahai, Anant},
    Title = {A bound for block codes with delayed feedback related to the sphere-packing bound},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {May},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-61.html},
    Number = {UCB/EECS-2009-61},
    Abstract = {This note attacks the open problem of the error-exponent with feedback for asymmetric discrete-memoryless channels. A partial result is obtained: the error exponent for rate-R codes used with perfect feedback delayed by T symbols is upper bounded by (for T large enough) E_{sp}(R - O(log T / T) ) + O(log T / T),
where E_{sp} is the sphere-packing exponent and the constants depend on the channel transition matrix.

This partially resolves the longstanding conjecture that the sphere-packing bound continues to govern block-codes with feedback by showing that it does so at least in the limit of long feedback delays. So either it must hold without such delays or something truly shocking is going on.}
}

EndNote citation:

%0 Report
%A Palaiyanur, Harikrishna R
%A Sahai, Anant
%T A bound for block codes with delayed feedback related to the sphere-packing bound
%I EECS Department, University of California, Berkeley
%D 2009
%8 May 12
%@ UCB/EECS-2009-61
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-61.html
%F Palaiyanur:EECS-2009-61