Zigzag Decodable codes : Linear-time erasure codes with applications to data storage

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

9 Scopus Citations
View graph of relations

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)190-208
Journal / PublicationJournal of Computer and System Sciences
Volume89
Online published24 May 2017
Publication statusPublished - Nov 2017

Abstract

An erasure code is said to be k-reliable if it maps k source packets into n coded packets, and any k out of the n coded packets allow recovery of the original k source packets. Codes of k-reliability achieve the best reliability-storage tradeoff, which are useful for fault tolerance in data storage systems. Zigzag Decodable (ZD) codes are k-reliable erasure codes. Its encoding and decoding (per information bit) can be done in linear time, involving only XOR and bit-shift operations. Two classes of ZD codes are constructed, and compared with Cacuhy-RS codes, the state-of-the-art general-purpose MDS codes. Numerical results show that ZD codes outperform Cauchy-RS codes over a wide range of coding parameters.

Research Area(s)

  • Data storage, Erasure codes, Implementation, k-Reliability, Linear time, Zigzag Decodable codes

Bibliographic Note

Full text of this publication does not contain sufficient affiliation information. Research Unit(s) information for this record is supplemented by the author(s) concerned.