Ulam-Rényi容错搜索问题与最优纠错编码  

Ulam-Rényi problem on searching with errors and optimal error-correcting codes

作　　者：刘文安[1] 聂赞坎[1] 

机构地区：[1]西安交通大学理学院

出　　处：《河南师范大学学报（自然科学版）》2004年第1期1-6,共6页Journal of Henan Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(69874010)

摘　　要：带反馈对称信道的最优e-纠错编码等价于Ulam-Rényi容错搜索问题中的最小提问次数q(n;e).情形e∈{1,2,3}时确定q(n;e)的精确值问题己经解决.本文将针对e=2所建立的著名的Guzicki算法推广到一般情形.我们的主要结果提供了用来判定搜索过程中出现的任意状态是否能够达到其信息论下界的一个精确的算法.Optimal e-error-correcting codes for symmetric channels with feedback is equivalent to the minimum number q(n;e) of questions of the Ulam-Rényi problem. The problem of determining the exact values of q(n;e) have been solved for the cases e∈｛1,2,3｝ and all n1. The well-known Guzichi′s algorithm is generalized to arbitrary e. Our main results provide an accurate algorithm which can be used to judge whether the information-theoretic bound is achieved for any possible state.

关 键 词：最优e-纠错编码 容错搜索 对称差错模式 Ulam-Rényi问题 反馈对称信道 

分 类 号：TN911.22[电子电信—通信与信息系统]