On information transmission over a finite buffer channel
On information transmission over a finite buffer channel
复制标题
DOI：
10.1109/tit.2005.864445
复制
发表时间：
2000-06
影响因子：
2.5
通讯作者：
S. Diggavi;M. Grossglauser
中科院分区：
文献类型：
--
作者：
S. Diggavi;M. Grossglauser
我们研究通过有限缓冲区队列的信息传输。我们将信道建模为一个有限状态信道，其状态由数据包到达时的缓冲区占用情况给出；当数据包到达已满的队列时发生丢失。我们在两种情况下研究这个问题：一种是接收器知道缓冲区的状态，另一种是接收器不知道缓冲区的状态。在前一种情况下，我们表明信道的容量取决于缓冲区的长期丢失概率。因此，即使信道本身具有记忆，容量也仅取决于缓冲区的稳态丢失概率。本通信的主要焦点是后一种情况。当接收器不知道缓冲区状态时，这就导致了对删除信道的研究，在删除信道中符号被随机丢弃，并且接收到传输符号的一个子序列。在删除信道中，与擦除信道不同，没有关于哪些符号被丢弃的边信息。我们研究删除信道的可实现速率，并将注意力集中在简单（不匹配）的解码方案上。我们表明，即使使用简单的解码方案，对于独立同分布（i.i.d.）的输入码本，在删除概率\(p_d<1 - K^{-1}\)的情况下，删除信道中的可实现速率与擦除信道中的可实现速率最多相差\(H_0(p_d)-p_d\log K/(K - 1)\)比特，其中\(p_d\)是删除概率，\(K\)是字母表大小，\(H_0(\cdot)\)是二元熵函数。因此，对于合理的字母表大小，擦除信道和删除信道之间的传输速率差异不大。我们还通过对马尔可夫码本进行分析，在简单解码框架下为删除信道建立了更精确的下界。在此表明，对于马尔可夫码本，删除容量和擦除容量之间的差异甚至比独立同分布输入码本的情况更小，并且适用于更大范围的删除概率。我们还研究了噪声删除信道，其中删除信道与一个对称离散无记忆信道（DMC）级联。我们推导出了此类信道可实现速率的单字母表达式。对于二元情况，我们表明这个结果简化为\(\max(0,1 - [H_0(\theta)+\theta H_0(p_e)])\)，其中\(p_e\)是二元对称信道的交叉概率。
We study information transmission through a finite buffer queue. We model the channel as a finite-state channel whose state is given by the buffer occupancy upon packet arrival; a loss occurs when a packet arrives to a full queue. We study this problem in two contexts: one where the state of the buffer is known at the receiver, and the other where it is unknown. In the former case, we show that the capacity of the channel depends on the long-term loss probability of the buffer. Thus, even though the channel itself has memory, the capacity depends only on the stationary loss probability of the buffer. The main focus of this correspondence is on the latter case. When the receiver does not know the buffer state, this leads to the study of deletion channels, where symbols are randomly dropped and a subsequence of the transmitted symbols is received. In deletion channels, unlike erasure channels, there is no side-information about which symbols are dropped. We study the achievable rate for deletion channels, and focus our attention on simple (mismatched) decoding schemes. We show that even with simple decoding schemes, with independent and identically distributed (i.i.d.) input codebooks, the achievable rate in deletion channels differs from that of erasure channels by at most H0(pd)-pd logK/(K-1) bits, for pd<1-K-1, where p d is the deletion probability, K is the alphabet size, and H 0(middot) is the binary entropy function. Therefore, the difference in transmission rates between the erasure and deletion channels is not large for reasonable alphabet sizes. We also develop sharper lower bounds with the simple decoding framework for the deletion channel by analyzing it for Markovian codebooks. Here, it is shown that the difference between the deletion and erasure capacities is even smaller than that with i.i.d. input codebooks and for a larger range of deletion probabilities. We also examine the noisy deletion channel where a deletion channel is cascaded with a symmetric discrete memoryless channel (DMC). We derive a single letter expression for an achievable rate for such channels. For the binary case, we show that this result simplifies to max(0,1-[H0(thetas)+thetasH0(p e)]) where pe is the cross-over probability for the binary symmetric channel