Coding And Decoding For Cascaded VT Codes With High Probability To Correct Three Insertion/Deletion Errors

Insertion/Deletion Error,inserting or deleting some additional code elements in the encoded data stream,often occurs under out-of-syn communication conditions.Although Varshamov-Tenengolts（VT）codes can correct single insertion/deletion errors with optimal asymptotic code rates,no general insertion/deletion error correction codes have been presented so far,so the research on insertion/deletion error correction codes and the extension of the error correction capability of VT codes is still a challenging topic.In this thesis,the design of cascade construction of CRC codes,DED codes and VT codes and the design of list decoding algorithm can achieve high probability of correcting no more than three insertion/deletion errors.The main research work as follows.First,the systematic coding method of VT code is studied,and the VT code list decoding algorithm that can correct up to three insertion/deletion errors is designed based on the unique decoding algorithm.The core idea of the VT list decoding algorithm is to apply the unique decoding algorithm of VT code by traversing the super-sequence or sub-sequence of the received sequence one by one,and if the returned sequence is a codeword of VT code,then add this codeword into the decoding list,and finally output the codeword of the smallest dictionary sequence in the list.Second,a CRC-VT cascade code compilation code scheme is designed based on the error detection capability of CRC codes.The scheme performs CRC systematic coding of message sequences followed by VT code systematic coding.The improved idea of CRC-VT list decoding algorithm is that when the returned sequence is a codeword of VT code and its information sequence must pass CRC checksum before it can be added to the decoding list.The CRC-VT simulations for CRC check bits of 24 and message sequence lengths of 16/32/64/128 show that the codeword error rate of list decoding can be as low as10^-4 order of magnitude when three insertion/deletion errors occur.Third,a segmented CRC-VT cascaded compiled code scheme is designed.The scheme first divides the message sequence into two segments and codifies the CRC system separately,then unites them in sequential steps and uses them as the input of the VT code system coding,and adopts two segmented CRC checks in the list decoding.Simulation experiments show that the decoding performance of segmented CRC-VT cascade codes is inferior to unsegmented CRC-VT cascade codes at the same code rate.Fourth,a DED-CRC-VT cascade code compilation scheme is designed based on the error detection capability of the DED code.This scheme first encode the message sequence with DED system,then with CRC code system,and finally with VT code system.The experimental results show that DED-CRC-VT cascade codes are more suitable for shorter message sequences than CRC-VT cascade codes under the same code rate.