• Login
    View Item 
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Electrical Communication Engineering (ECE)
    • View Item
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Electrical Communication Engineering (ECE)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    On Streaming Codes, Regenerating Codes and Locality-Aided Decoding

    View/Open
    Thesis full text (9.855Mb)
    Author
    Nikhil Krishnan, M
    Metadata
    Show full item record
    Abstract
    This thesis presents results relating to the application of error-correcting codes with different aims and in different settings; to achieve low-latency communication, to improve decoding performance and to enable the efficient and reliable distributed storage of large volumes of data. Low-Latency Communication The work in this direction employs packet-level Forward Error Correction (FEC) and was motivated initially by multimedia streaming applications. For this reason, we refer in this thesis to the low-latency codes developed here as streaming codes or codes for streaming. The work is also however, relevant to the development of future cellular standards such as 5G, which place an emphasis on the need for low-latency communication Locality-Aided Decoding for Improved Performance Locally recoverable codes (LRCs) also known as codes with locality, are developed by Gopalan et al. with the aim of reducing the number of helper nodes contacted (termed as repair degree) for repair of a failed node, in the setting of distributed storage. Contribution (b): In this thesis, we explore a novel application of LRCs, namely, that of using LRCs in conjunction with traditional decoding methods such as ordered statistics decoding (OSD) or trellis decoding, to carry out improved decoding of cyclic codes. The locality-aware OSD scheme that we propose for binary cyclic codes, in which locality is either already present or introduced, is shown to have reduced error probabilities for a given signal-to-noise ratio, in comparison to the conventional OSD scheme. With respect to trellis decoding, we demonstrate how locality can be carefully introduced to obtain cyclic codes having low trellis complexity. We also present a quick-look decoding method that can be employed in either the OSD or trellis decoding setting, to reduce the average decoding complexity. Regenerating Codes In a regenerating code (RGC), a data le is regarded as a collection of B data symbols over a fi nite fi eld Fq of size q. These symbols are stored in redundant fashion, across n nodes. Each node stores symbols over Fq and thus an RGC may be regarded as a code having the vector symbol alphabet F q . A data collector should be able to reconstruct the data le from the k symbols present in any set of k nodes. Node repair should be accomplished by contacting any d nodes and downloading at most symbols from each of the d nodes. There are two modes of repair termed respectively, as functional repair (FR) and exact repair (ER). In the ER setting, the contents of the replacement node are identical to that of the failed node. In the FR setting, this is not necessary and it is only required that, following node repair, the resultant arrangement of data continues to constitute an RGC. For a given parameter set fn; k; d;Bg, it is known that there exists a trade-o between the amount of per-node storage, represented by , and the repair bandwidth d . This trade-o , referred to as the storage-repair bandwidth (S-RB) trade-o , is completely characterized in the case of an FR RGC, whereas in the case of an ER RGC, it remains mostly open. The RGCs that appear at the two ends of the S-RB trade-o , termed as the minimum storage regenerating (MSR) and minimum bandwidth regenerating (MBR) codes, minimize the amount of data storage and the repair bandwidth, respectively. Contribution (c) Constructions of MBR Codes With Replication: In the thesis, we present two new families of MBR codes for d (n 􀀀 2). These code families offer inherent double replication of all systematic symbols (i.e., the raw data symbols) and optimal access during the repair of a set of d nodes that collectively contain all the systematic symbols. We also show that it is not possible to replicate even a single scalar symbol more than twice in an MBR code. We fully identify the parameter range ((n; k; d); ( ; = 1)) for which there exist MBR codes with all symbols replicated twice and present a node transformation to convert any MBR code lying within this parameter range to one in which all symbols are replicated twice. Contribution (d) Optimal Constructions of Locally Regenerating Codes (LRGCs): LRGCs combine the benefi ts of LRCs and RGCs by offering both low repair degree and low repair bandwidth. Existing LRGC constructions require in general a eld-size exponential in block length. In the thesis, we present the first families of LRGCs that require a fi eld-size only linear in block length. Contribution (e) S-RB Trade-o of Linear ER RGCs: In the fi nal contribution reported here, an upper bound on the le-size of linear RGCs for parameters (n; k; d = k) is derived. In conjuction with an achievability result due to Tian et al., this results in the characterization of the S-RB trade-o of linear RGCs for the parameter set (n; k = n 􀀀 1; d = n 􀀀 1).
    URI
    https://etd.iisc.ac.in/handle/2005/5045
    Collections
    • Electrical Communication Engineering (ECE) [402]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV