























The problem of correcting transpositions (or swaps) of consecutive symbols in $ q $-ary strings is studied. Lower bounds on asymptotically achievable rates of codes correcting $ t = τn $ transpositions are derived. The first bound is obtained by analyzing the average cardinality of ``transposition balls'' and evaluating the appropriate version of the generalized Gilbert--Varshamov bound, while the second bound follows from a construction of codes correcting an arbitrary number of transpositions (i.e., zero-error codes). Asymptotic bounds on the cardinality of optimal codes correcting $ t = \textrm{const} $ transpositions are also derived.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。