Coding Methods for String Reconstruction From Erroneous Prefix-Suffix Compositions
Zitan Chen · IEEE Journal on Selected Areas in Information Theory · 2025
The number of zeros and the number of ones in a binary string are referred to as the composition of the string, and the prefix-suffix compositions of a string are a multiset formed by the compositions of the prefixes and suffixes of all possible lengths of the string. In this work, we present binary codes of lengthnin which every codeword can be efficiently reconstructed from its erroneous prefix-suffix compositions with at mosttcomposition errors. All our constructions have decoding complexity polynomial innand the best of our constructions has constant rate and can correctt= Θ(n) errors. As a comparison, no prior constructions can afford to efficiently correctt= Θ(n) arbitrary composition errors. Additionally, we propose a method of encodingharbitrary strings of the same length so that they can be reconstructed from the multiset union of their error-free prefix-suffix compositions, at the expense ofh-fold coding overhead. In contrast, existing methods can only recoverhdistinct strings, albeit with code rate asymptotically equal to 1/h. Building on the top of the proposed method, we also present a coding scheme that enables efficient recovery ofhstrings from their erroneous prefix-suffix compositions witht= Θ(n) errors.