3 years ago

Codes for Updating Linear Functions over Small Fields.

Suman Ghosh, Lakshmi Natarajan

We consider a point-to-point communication scenario where the receiver maintains a specific linear function of a message vector over a finite field. When the value of the message vector undergoes 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 the modified message but 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 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 when the receiver maintains linear functions of striped message vector. Finally, we show that every function update problem is equivalent to a generalized index coding problem.

Publisher URL: http://arxiv.org/abs/1901.02816

DOI: arXiv:1901.02816v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.