An inequality on guessing and its application to sequential decoding
An inequality on guessing and its application to sequential decoding
复制标题
DOI：
10.1109/18.481781
复制
发表时间：
1996-01-01
影响因子：
2.5
通讯作者：
Arikan, E
中科院分区：
文献类型：
--
作者：
Arikan, E
设(X，Y)是一对离散随机变量，X取M个可能值中的一个。假设在给定Y的值的情况下，要确定X的值，则可以通过以下形式的问题来确定X的值：X是否等于x？直到答案是肯定的。设G(x/y)表示当X=x，Y=y时猜想的次数，我们证明了对任意大于等于0的Rho，[G(X\Y)(Rho)]大于或等于(1+ln M)(-Rho)Sigma(Y)[Sigma(X)P-X，P-Y(x，y)(1/1+Rho)](1+Rho).这提供了人意熵的一个可操作的特征。接下来，我们将该不等式应用于序列译码的计算复杂度的估计。为此，我们将X视为通信通道的输入，Y视为通信通道的输出。在给定Y的情况下，顺序解码算法基本上是通过一次猜测一个值来猜测X，直到猜测是正确的。因此，作为随机变量的顺序译码的计算复杂性由猜测函数G(X\Y)给出，该猜测函数由解码器假设树码中的节点的顺序来定义。这一观察结果与上述G(X\Y)矩的下界相结合，给出了序列译码计算矩的下界。本方法能够以简单的方式确定顺序解码的(先前已知的)截止速率；它还产生多址信道的顺序解码的(先前未知的)截止速率区域。这些结果适用于输入字母表有限的无记忆通道。
Let (X,Y) be a pair of discrete random variables with X taking one of M possible values. Suppose the value of X is to be determined, given the value of Y, by asking questions of the form ''Is X equal to x?'' until the answer ''Yes.'' Let G(x / y) denote the number of guesses in any such guessing scheme when X = x, Y = y. We prove thatE[G(X \ Y)(rho)] greater than or equal to (1 + ln M)(-rho)Sigma(y)[Sigma(x) P-X,P-Y(x,y)(1/1+rho)](1+rho)for any rho greater than or equal to 0. This provides an operational characterization of Renyi's entropy. Next we apply this inequality to the estimation of the computational complexity of sequential decoding. For this, we regard X as the input, Y as the output of a communication channel. Given Y, the sequential decoding algorithm works essentially by guessing X, one value at a time, until the guess is correct. Thus the computational complexity of sequential decoding, which is a random variable, is given by a guessing function G(X \ Y) that is defined by the order in which nodes in the tree code are hypothesized by the decoder. This observation, combined with the above lower bound on moments of G(X \ Y), yields lower bounds on moments of computation in sequential decoding. The present approach enables the determination of the (previously known) cutoff rate of sequential decoding in a simple manner; it also yields the (previously unknown) cutoff rate region of sequential decoding for multiaccess channels. These results hold for memoryless channels with finite input alphabets.