Ong and Ho developed optimal linear index codes for single uniprior index coding problems (ICPs) by finding a spanning tree for each of the strongly connected components of the corresponding information-flow graphs, following which Thomas et al. considered the same class of ICPs over Rayleigh fading channel. They developed the min-max probability of error criterion for choosing an index code which minimized the probability of error at the receivers and showed that there always exist optimal linear index codes for which any receiver takes at most two transmissions to decode a requested message. Motivated by the above works, this paper considers single uniprior ICPs over Rayleigh fading channels for which minimizing average probability of error is shown to be a criterion for further selection of index codes. The optimal index code w.r.t this criterion is shown to be one that minimizes the total number of transmissions used for decoding the message requests at all the receivers. An algorithm that generates a spanning tree which has a lower value of this metric as compared to the optimal star graph is also presented. For a given set of parameters of single uniprior ICPs, a lower bound for the total number of transmissions used by any optimal index code is derived, and a class of ICPs for which this bound is tight is identified.
翻译:Ong和Ho通过为信息流图的每个强连通分量找到一棵生成树来开发了单一先验索引编码问题(ICPs)的最优线性索引编码,此后,Thomas等人考虑了相同类别的ICPs在瑞利衰落信道上。他们开发了选择最小化接收器误差概率的索引编码的最小化最大概率误差标准,并表明始终存在最优线性索引编码,其任何接收器最多需要两次传输才能解码请求的消息。本文关注于对于单一先验ICPs在瑞利衰落信道上,最小化平均误差概率被证明是进一步选择索引编码的一个标准。据此标准,最优索引编码被证明是在解码所有接收器上的消息请求时最小化传输总数的编码。本文还介绍了一种生成比最优星形图具有更低的度量值的生成树的算法。对于给定单一先验ICPs的参数集,导出了任何最优索引编码使用的传输总数的下界,并确定了一个该下界是严密的ICP类。