一类删位/插位纠错码的最佳构造

摘要

删位/捅位纠错码可以用来纠正码字传送过程中因码元的删除或插入而引起的差错.完备的删位纠错码是一类码字长度一致的删位/捅位纠错码，已有不少相关的研究成果.作为完备删位纠错码概念的推广，本文定义了一类u元字母表上码字长度取自集合K的s-删位/插位纠错码，若允许码字包含相同的码元，则将其记为T*(t，K，v)-码；若每个码字必须包含不同码元，则将其记为T(t，K，v)-码，其中s=min{k-t：k∈K).令N*(t，K，v)=max{|C*|：C*是一个T*(t，K，v)-码}，N(t，K，v)=max{|C|：C是一个T(t，K，v)-码}.若C*(或C)为一个T*(t，K，v)-码(或T(t，K，v)-码)且|C*|=N*(t，K，v)(或|C|=N(t，K，v))，则称该码为最佳的，并记为OT*(t，K，v)-码(或OT(t，K，v)-码).
　　 关于删位/捅位纠错码已经有不少研究工作，但对于其最佳性的研究却非常少.当3∈K(){3，4….，10)，K={4，5}及K={4，6}时，T(2，K，v)-码的存在性问题已经解决，但该码并不总是最佳的.
　　 本文对于上述的集合K，通过研究最大的(即包含区组个数最多的)有向成对平衡设计MDB(K，1；v)的存在性问题，构造出OT(2，K，v)-码，从而确定了N(2，K.v)的值，除了如下若干例外：(1)当K={4，5)时，u∈{26，30，32，36，38，41，44，45，47，51，53，59，66，68，74，89，119，231，233，239)∪{v：v≡3.9，12(mod15)，v>18)；(2)当K={4，6)时.u∈{27，33，39，45，51，57，63.87).
　　 此外，我们发现OT*(t，K，v)-码的构造可归结为OT*(t，k，v)-码的存在性问题，其中k=minK.因此对于上述的集合K，OT*(2，K，v)-码的构作问题也被完全解决.