Codes for Updating Linear Functions over Small Fields

Ghosh, S and Natarajan, Lakshmi Prasad (2019) Codes for Updating Linear Functions over Small Fields. arXiv. pp. 1-17.

Text (arXiv copy)
1901.02816.pdf - Accepted Version

Download (401kB) | Preview


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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Natarajan, Lakshmi Prasad
Item Type: Article
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: Team Library
Date Deposited: 16 Jan 2019 04:40
Last Modified: 16 Jan 2019 04:41
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4719 Statistics for this ePrint Item