Eitan Yaakobi

Eitan Yaakobi

Auto-generated profile, based on publicly available information

Eitan Yaakobi

Department of Computer Science, Technion—Israel Institute of Technology, Haifa, Israel

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
20 December 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
ALAndreas Lenz
Andreas Lenz
PSPaul H. Siegel
Paul H. Siegel
AWAntonia Wachter-Zeh
Antonia Wachter-Zeh
EYEitan Yaakobi
Eitan Yaakobi
In this paper we study error-correcting codes for the storage of data in synthetic deoxyribonucleic acid (DNA). We investigate a storage model where a data set is represented by an unordered set of $M$ sequences, each of length $L$ . Errors within that model are a loss of whole sequences and point errors inside the sequences, such as insertions, deletions and substitutions. We derive Gilbert-Varshamov lower bounds and sphere packing upper bounds on achievable cardinalities of error-correcting codes within this storage model. We further propose explicit code constructions than can correct errors in such a storage system that can be encoded and decoded efficiently. Comparing the sizes of these codes to the upper bounds, we show that many of the constructions are close to optimal.

19 February 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
YCYeow Meng Chee
Yeow Meng Chee
HKHan Mao Kiah
Han Mao Kiah
AVAlexander Vardy
Alexander Vardy
VVVan Khu Vu
Van Khu Vu
EYEitan Yaakobi
Eitan Yaakobi
Racetrack memory is a new technology, which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory is structured like a tape, which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this paper, we design codes, which combat shift errors in racetrack memory, called position errors, namely, shifting the domains is not an error-free operation and the domains may be over shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. This setup is a special case of the reconstruction problem studied by Levenshtein, however, in our case, the position errors from different heads are correlated. We will show how to take advantage of this special feature of racetrack memories in order to construct codes correcting deletions and sticky insertions. In particular, under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, d deletions with d+1 heads if the heads are well separated. Similar results are provided for burst of deletions, sticky insertions, and combinations of both deletions and sticky insertions.

28 November 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
RGRyan Gabrys
Ryan Gabrys
EYEitan Yaakobi
Eitan Yaakobi
OMOlgica Milenkovic
Olgica Milenkovic
Motivated by applications in DNA-based storage, we introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which, in addition to deletions, insertions and substitution errors also accounts for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. We conclude with constructions for joint block deletion and adjacent block transposition error-correcting codes.

1 March 2016 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
MBMario Blaum
Mario Blaum
JPJames Plank
James Plank
MSMoshe Schwartz
Moshe Schwartz
EYEitan Yaakobi
Eitan Yaakobi
Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while sector-disk (SD) codes are erasure codes that address the mixed failure mode of current redundant arrays of independent disk (RAID) systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6.

31 January 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
RGRyan Gabrys
Ryan Gabrys
EYEitan Yaakobi
Eitan Yaakobi
The sequence reconstruction problem, first proposed by Levenshtein, models the setup in which a sequence from some set is transmitted over several channels, and the decoder receives the outputs from every channel. The channels are almost independent as it is only required that all outputs are different from each other. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius t, where the distance between their centers is at least d. The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendalltau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted sequence can be arbitrary, we study the setup, where the transmitted sequence belongs to a single-deletion-correcting code and there are t deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder.

1 October 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
MLMaya Levy
Maya Levy
EYEitan Yaakobi
Eitan Yaakobi
Mutually uncorrelated (MU) codes are a class of codes in which no proper prefix of one codeword is a suffix of another codeword. These codes were originally studied for synchronization purposes and recently, Yazdi et al. showed their applicability to enable random access in DNA storage. In this paper,we follow the research of Yazdi et al. and study MU codes along with their extensions to correct errors and balanced codes. We first review a well-known construction of MU codes and study the asymptotic behavior of its cardinality. This task is accomplished by studying a special class of run-length limited codes that impose the longest run of zeros to be at most some function of the codewords length. We also present an efficient algorithm for this class of constrained codes and show how to use this analysis for MU codes. Next, we extend the results on the run-length limited codes in order to study (d h , d m )-MU codes that impose a minimum Hamming distance of dh between different codewords and d m between prefixes and suffixes. In particular, we show an efficient construction of these codes with nearly optimal redundancy. We also provide similar results for the edit distance and balanced MU codes. Last, we draw connections to the problems of comma-free and prefix synchronized codes.