Ghosh, S and Natarajan, Lakshmi Prasad
(2019)
Codes for Updating Linear Functions over
Small Fields.
arXiv.
pp. 1-17.
Abstract
We consider a point-to-point communication scenario where the receiver intends to maintain a specific linear
function of a message vector over a finite field. When the value of the message vector changes, which is modelled
as a sparse update, the transmitter broadcasts a coded version of the modified message while the receiver uses
this codeword and the current value of the linear function to update its contents. It is assumed that the transmitter
has access to only the modified message and is unaware of the exact difference vector between the original and
modified messages. Under the assumption that the difference vector is sparse and that its Hamming weight is at the
most a known constant, the objective is to design a linear code with as small a codelength as possible that allows
successful update of the linear function at the receiver. This problem is motivated by applications to distributed data
storage systems. Recently, Prakash and Medard derived a lower bound on the codelength, which is independent of ´
the size of the underlying finite field, and provided constructions that achieve this bound if the size of the finite field
is sufficiently large. However, this requirement on the field size can be prohibitive for even moderate values of the
system parameters. In this paper, we provide a field-size aware analysis of the function update problem, including
a tighter lower bound on the codelength, and design codes that trade-off the codelength for a smaller field size
requirement. We also show that the problem of designing codes for updating linear functions is related to functional
index coding or generalized index coding. We first characterize the family of function update problems where linear
coding can provide reduction in codelength compared to a naive transmission scheme. We then provide field-size
dependent bounds on the optimal codelength, and construct coding schemes based on error correcting codes and
subspace codes when the receiver maintains linear functions of striped message vector. These codes provide a
trade-off between the codelength and the size of the operating finite field, and whenever the achieved codelengths
equal those reported by Prakash and Medard the requirements on the size of the finite field are matched as well. ´
Finally, for any given function update problem, we construct an equivalent functional index coding or generalized
index coding problem such that any linear coding scheme is valid for the function update problem if and only if
it is valid for the constructed functional index coding problem.
Actions (login required)
 |
View Item |
Altmetric
Altmetric