7 August 2019 in IEEE Transactions on Information Theory
Permutation codes and multipermutation codes are widely studied due to various applications in information theory. Designing codes correcting deletion errors has been the main subject of works in the literature and to the best of our knowledge, there exist only optimal codes capable of correcting a single deletion in a permutation. In this paper, we construct several classes of permutation and multipermutation codes that are capable of correcting a burst deletion of length s ≥ 2, for both stable and unstable models. Efficient error decoders are provided to show the correctness of our constructions.
8 January 2021 in IEEE Communications Letters
This letter proposes novel methods for designing two-dimensional (2-D) weight-constrained codes for reducing the parasitic currents in the crossbar resistive memory array. In particular, we present efficient encoding/decoding algorithms for capacity-approaching 2-D weight-constrained codes of size m ×n, where each row has a weight pn with p <; 1/2; and each column has a weight qm with q ≤ 1/2. We show that the designed codes provide higher code rates compared to the prior art codes for p ≤ 1/2 and q ≤ 1/2.
30 November 2018 in IEEE Transactions on Information Theory
1 January 2023 in IEEE Journal on Selected Areas in Information Theory
Transverse-read is a novel technique to detect the number of ‘1’s stored in a domain wall memory, also known as racetrack memory, without shifting any domains. Motivated by the technique, we propose a novel scheme to combine transverse-read and shift-operation such that we can reduce the number of shift-operations while still achieving high capacity. We also show that this scheme is helpful to correct errors in domain wall memory. A set of valid-words in this transverse-read channel is called a transverse-read code. Our goal in this work is to study transverse-read codes with respect to their properties, capacity, and applications. We first present several properties of transverse-read codes and show that they are equivalent to a family of constrained codes. Then, we compute the maximal asymptotic rate of transverse-read codes for certain parameters. Furthermore, we also present several constructions of transverse-read codes with high rate. Finally, we design several transverse-read codes that can correct limited-shift-errors and limited-magnitude errors in domain wall memory.
27 November 2024 in IEEE Transactions on Communications
Codes in the Damerau–Levenshtein metric have received some attention by the research community recently owing to their applications in DNA-based data storage. In particular, Gabrys, Yaakobi, and Milenkovic (2017) designed a length-n code correcting a single deletion and s adjacent transpositions with at most (1+2 s ) log n bits of redundancy. In this work, we consider a new setting where both deletions and asymmetric adjacent transpositions may occur. For asymmetric transpositions, at most s + 0-right shifts (i.e., 01 → 10) and at most s − 0-left shifts (i.e., 10 → 01) may occur. We present several constructions of the binary codes correcting these errors in various cases. In particular, we design a code correcting a single deletion, s + right-shift, and s − left-shift errors with at most (1 + s ) log( n + s + 1) + 1 bits of redundancy where s = s + + s − . In addition, we investigate uniquely-decodable codes correcting t 0-deletions and s adjacent transpositions with at most ( t + 2 s ) log n + o (log n ) bits of redundancy. Then, we study the code for correcting t 0-deletions, s + right-shift, and s − left-shift errors with list-decoding algorithms. Our main contribution here is the construction of a list-decodable code with list size O ( ns ) and with at most (max{ t, s + 1}) log n + O (1) bits of redundancy, where s = s + + s − . We construct non-systematic codes for correcting t b blocks of 0-deletions with l -limited magnitude and s adjacent transpositions with redundancy at most (2( t b +2 s )+1) log( n +1)+ O (1) bits and systematic codes with at most ((2( t b + 2 s ) + 1)(1 + 1/(log( t b l + 4))) log( N + 1) + O (log log N ) redundant bits in an N -length codeword.
4 July 2025 in IEEE Transactions on Information Theory
Permutation codes in the Ulam metric, which can correct multiple deletions, have been investigated extensively recently. In this work, we are interested in the maximum size of permutation codes in the Ulam metric and aim to design permutation codes that can correct multiple deletions with efficient decoding algorithms. We first present an improvement on the Gilbert-Varshamov bound of the maximum size of these permutation codes by analyzing the independence number of the auxiliary graph. The idea is widely used in various cases and our contribution in this section is to enumerate the number of triangles in the auxiliary graph and show that it is small enough. Next, we design permutation codes correcting multiple deletions with a decoding algorithm. In particular, the constructed permutation codes can correct t deletions with at most $(3t-1) \log (n+1)+o(\log n)$ bits of redundancy where n is the length of the code. Our construction is based on a new mapping that yields a new connection between permutation codes in the Hamming metric and permutation codes in various metrics. Furthermore, we construct permutation codes that correct multiple bursts of deletions using this new mapping. Finally, we extend the new mapping for multi-permutations and construct the best-known multi-permutation codes in the Ulam metric.