"Soft-decision" decoding of Chinese remainder codes
"Soft-decision" decoding of Chinese remainder codes
复制标题
DOI：
10.1109/sfcs.2000.892076
复制
发表时间：
2000-11
期刊：
影响因子：
--
通讯作者：
V. Guruswami;A. Sahai;M. Sudan
中科院分区：
文献类型：
--
作者：
V. Guruswami;A. Sahai;M. Sudan
给定n个相对素数p/sub1/，其中m/subi=m(modp/subi/)。中国余数码的软判决译码问题被给出作为输入的剩余向量r/sp1/=(r/sub1/，...，r/subn/)、权重向量和协议参数t。目标是找到所有消息m/sp1/M使得m的编码和r/sp1/oarr/之间的加权协议(即，/SPL Sigma//subi/w/subi/求和使得r/subi/=m(Mod Pi))至少为t。这里，我们给出了一个新的算法来解决CRT码的软判决问题，只要协议参数t足够大。我们通过更深入地挖掘纠错算法背后的代数并揭示译码的“理想”理论观点来推导我们的算法。当所有的权重都等于1时，我们得到了更常被研究的“列表解码”问题。中国剩余码的列表译码算法是由O.Goldreich等人最近提出的。(1999)，并由D.Boneh改进。它们的算法分别适用于t/SPL GES//SPL RADIC/(2nulogp/subn//logp1)和t/SPL GES//SPL Radic/(Knlogp/subn//logp/sub1/)。通过使用具有非平凡选择权值的软判决译码算法，我们改进了上述算法，解决了任意小的/SPL EPSi//SPL GES/0，给定t/SPL GES//SPL Radic/(k(n+/SPL EPSi/))的列表译码问题。
Given n relatively prime integers p/sub 1/, where m/sub i/=m(mod p/sub i/). The soft-decision decoding problem for the Chinese remainder code is given as input a vector of residues r/spl I.oarr/=(r/sub 1/,...,r/sub n/), a vector of weights , and an agreement parameter t. The goal is to find all messages m /spl isin/ M such that the weighted agreement between the encoding of m and r/spl I.oarr/(i.e., /spl Sigma//sub i/ w/sub i/ summed over all i such that r/sub i/=m(mod pi)) is at least t. Here we give a new algorithm for solving the soft-decision problem for the CRT code that works provided the agreement parameter t is sufficiently large. We derive our algorithm by digging deeper into the algebra underlying the error-correcting algorithms and unveiling an "ideal"-theoretic view of decoding. When all weights are equal to 1, we obtain the more commonly studied "list decoding" problem. List decoding algorithms for the Chinese Remainder Code were given recently by O. Goldreich et al. (1999), and improved by D. Boneh. Their algorithms work for t/spl ges//spl radic/(2knlogp/sub n//logp1) and t/spl ges//spl radic/(knlogp/sub n//logp/sub 1/), respectively. We improve upon the algorithms above by using our soft-decision decoding algorithm with a non-trivial choice of weights, solve the list decoding problem provided t/spl ges//spl radic/(k(n+/spl epsi/)), for arbitrarily small /spl epsi//spl ges/0.