纠单个有序删除和擦除错误码的构造方法
|
摘要
信息在传输过程中,因信道干扰或数据同步错误等影响,导致通信接收端接收到的信息与发送端发送的信息不一致,接收信息因信息元素被破坏可能发生删除和擦除错误。为了纠正删除和擦除错误,结合现有的Varshamov-Tenengolt码,提出了一种新的二进制码构造方法,可以纠正单个有序删除和擦除错误,并给出了相应的译码方法,同时通过实例验证了所提出的二进制码构造方法及其译码方法的正确性。与现有的纠错码构造方法相比较,所提出的码构造和译码方法更加直观。
In the process of information transmission,channel interference or data synchronization errors may cause the received information at the receiving end to be inconsistent with the sent information at the transmitting end.The received information may be deleted or erased due to the destruction of information elements.In order to correct the ordered deletion-and-erasure error,a novel binary code construction method is proposed in combination with the existing Varshamov-Tenengolt code,which could correct the single ordered deletion-and-erasure errors and give the corresponding decoding method.At the same time,verification on the correctness of the proposed binary code construction method and its decoding method is done via an example.Compared with the existing error correction code construction method,the proposed code construction and decoding method is more intuitive and effective.
In the process of information transmission,channel interference or data synchronization errors may cause the received information at the receiving end to be inconsistent with the sent information at the transmitting end.The received information may be deleted or erased due to the destruction of information elements.In order to correct the ordered deletion-and-erasure error,a novel binary code construction method is proposed in combination with the existing Varshamov-Tenengolt code,which could correct the single ordered deletion-and-erasure errors and give the corresponding decoding method.At the same time,verification on the correctness of the proposed binary code construction method and its decoding method is done via an example.Compared with the existing error correction code construction method,the proposed code construction and decoding method is more intuitive and effective.
引文
[1]Kovacevic M,Tan V Y F.Coding for The Permutation Channel With Insertions,Deletions,Substitutions,and Erasures[C].IEEE International Symposium on Information Theory,2017:1933-1937.
[2]Varshamov R R,Tenengolts G M.Codes Which Correct Single Asymmetric Errors[J].Automatikai Telemkhanika,1965,161(03):288-292.
[3]Levenshtein V.Binary Codes Capable of Correcting Deletions,Insertionsand Reversals[J].Doklady AkademiiNauk SSR,1965,163(04):845-848.
[4]Levenshtein V.Asymptotically Optimum Binary Code With Correction for Losses of One or Two Adjacent Bits[J].Systems Theory Research,1967(19):293-298.
[5]HELBERG A S J,FERREIRA H C.On Multiple Insertion/Deletion Correcting Codes[J].IEEE Transactions on Information Theory,2002,48(01):305-308.
[6]CHENG L,SWART T G,FERREIRA H C,et al.Codes for Correcting Three or More Adjacent Deletions or Insertions[C].IEEE International Symposium on Information Theory.Hawaii:IEEE Press,2014:1246-1250.
[7]Gabrys R,Yaakobi E,Farnoud F,et al.Singledeletion-correcting Codes Over Permutations[C].IEEE International Symposium on Information Theory.Honolulu,HI,USA:IEEE Press,2014:2764-2768.
[8]LE T A,Nguyen H D.NewMultiple Insertion/Deletion Correcting Codes for Non-binary alphabets[J].IEEETransactions on Information Theory,2016,62(05):2682-2693.
[9]张用宇.基于置换理论的等级调制纠错码新构造方法[J].通信技术,2018,318(06):55-58.ZHANG Yong-yu.New Constructions of Rank Modulation Error-correcting Codes Based on Permutation[J].Communications Technology,2018,318(06):55-58.
[10]GABRYS R,Yaakobi E,Farnoud F,et al.CodesCorrecting Erasures and Deletions for Rank Modulation[J].IEEETransactions o n I n f o r m a t i o n T h e o r y,2 0 1 5,62(01):136-150.
[2]Varshamov R R,Tenengolts G M.Codes Which Correct Single Asymmetric Errors[J].Automatikai Telemkhanika,1965,161(03):288-292.
[3]Levenshtein V.Binary Codes Capable of Correcting Deletions,Insertionsand Reversals[J].Doklady AkademiiNauk SSR,1965,163(04):845-848.
[4]Levenshtein V.Asymptotically Optimum Binary Code With Correction for Losses of One or Two Adjacent Bits[J].Systems Theory Research,1967(19):293-298.
[5]HELBERG A S J,FERREIRA H C.On Multiple Insertion/Deletion Correcting Codes[J].IEEE Transactions on Information Theory,2002,48(01):305-308.
[6]CHENG L,SWART T G,FERREIRA H C,et al.Codes for Correcting Three or More Adjacent Deletions or Insertions[C].IEEE International Symposium on Information Theory.Hawaii:IEEE Press,2014:1246-1250.
[7]Gabrys R,Yaakobi E,Farnoud F,et al.Singledeletion-correcting Codes Over Permutations[C].IEEE International Symposium on Information Theory.Honolulu,HI,USA:IEEE Press,2014:2764-2768.
[8]LE T A,Nguyen H D.NewMultiple Insertion/Deletion Correcting Codes for Non-binary alphabets[J].IEEETransactions on Information Theory,2016,62(05):2682-2693.
[9]张用宇.基于置换理论的等级调制纠错码新构造方法[J].通信技术,2018,318(06):55-58.ZHANG Yong-yu.New Constructions of Rank Modulation Error-correcting Codes Based on Permutation[J].Communications Technology,2018,318(06):55-58.
[10]GABRYS R,Yaakobi E,Farnoud F,et al.CodesCorrecting Erasures and Deletions for Rank Modulation[J].IEEETransactions o n I n f o r m a t i o n T h e o r y,2 0 1 5,62(01):136-150.