This paper gives the theory and design of efficient codes capable of correcting errors caused by the insertion and deletion of a repeated symbol in the information sequence. Two efficient methods are described. For an...
详细信息
ISBN:
(纸本)9781424469604
This paper gives the theory and design of efficient codes capable of correcting errors caused by the insertion and deletion of a repeated symbol in the information sequence. Two efficient methods are described. For any fixed t(+), t(-) is an element of IN, one method gives a fixed length scheme to encode k information bits into a systematic code of length n = k + r, with r = (t(+) + t(-)) log(2) k + O(log log k), capable of correcting the insertion of t(+) repeated symbols and, simultaneously, correcting the deletion of t(-) repeated symbols in every codeword. The second method is a systematic variable length scheme which on average doubles the number of information bits k compared to the first method. The time complexity of the entire coding process for both schemes is T = O (k + (1 + min{t(-), t(+)})t) multiplication operations over a finite field containing k elements. The space complexity is S = O(k + t) field memory elements. The generalization to the m-ary case, m >= 2, is also given.
暂无评论