タイトル：On Prefixed Varshamov-Tenengolts Codes for Segmented Edit Channels 著者名：Xiaopeng Jiao; Haiyang Liu; Jianjun Mu; Hui Han; Yu-Cheng He 雑誌名：IEEE Transactions on Communications 号数：Volume 70, Issue 3 DOI:10.1109/TCOMM.2022.3146285 Abstract：The prefixed Varshamov-Tenengolts (VT) codes, which are subsets of VT codes with predetermined prefixes, can be used for error correction over segmented edit channels. In this paper, we investigate the construction and analysis of this class of codes. First, we derive upper bounds on the size of zero-error codes for segmented edit channels with segment-by-segment decoding. Second, we establish a one-to-one correspondence between prefixed VT codes and Levenshtein codes. Based on this relation, we can obtain explicit formulas on the size of prefixed VT codes via the existing results on the size of Levenshtein codes. Third, we construct a new zero-error prefixed VT code and show that the size of the constructed code is strictly larger than that of the existing prefixed VT code for the segmented deletion channel. Finally, an efficient systematic encoding method of prefixed VT codes is proposed for the segmented edit channels.
タイトル : A Single-Round File Synchronization Scheme from Insertions and Deletions with Low Redundancy 著者名 : Guochen Ma; Xiaopeng Jiao; Jianjun Mu; Hui Han; Yu-Cheng He 雑誌名 : IEEE Communications Letters 号数 : - DOI: 10.1109/LCOMM.2022.3193809 Abstract : Consider a file synchronization problem at two remote nodes A and B connected by a noiseless link. The node A has a binary file X, and node B has a binary file Y which is an edited version of X with random insertions and deletions (indels). The goal is to reconstruct X at node B from Y with minimal exchange of information between A and B. In this letter, we design a single-round, thus low latency, file synchronization scheme with low redundancy. In particular, a series of redundancy bits, including markers, check symbols of Reed-Solomon (RS) codes for hashes and Varshamov-Tenengolts (VT) syndromes, are constructed from X at node A and send to node B. According to the received redundancy and Y, we develop a recovery algorithm at node B to reconstruct X. The amount of exchanged information of the proposed scheme is significantly reduced when compared with the existing single-round synchronization scheme under random indels.
