| dc.description.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). | en_US |
