solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看445次
Bounds on Codes Correcting Tandem and Palindromic Duplications. (arXiv:1707.00052v1 [cs.IT])
来源于:arXiv
In this work, we derive upper bounds on the cardinality of tandem and
palindromic duplication correcting codes by deriving the generalized sphere
packing bound for these error types. We first prove that an upper bound for
tandem or palindromic deletions is also an upper bound for inserting the
respective type of duplications. Therefore, we derive the bounds based on these
special deletions as this results in tighter bounds. We determine the spheres
for tandem and palindromic duplications/deletions and the number of words with
a specific sphere size. Our upper bounds on the cardinality directly imply
lower bounds on the redundancy which we compare with the redundancy of the best
known construction correcting arbitrary burst errors. Our results indicate that
the correction of palindromic duplications requires more redundancy than the
correction of tandem duplications. Further, there is a significant gap between
the minimum redundancy of duplication correcting codes and burst insertion
co 查看全文>>