CaltechAUTHORS
  A Caltech Library Service

Asymmetric Error Correction and Flash-Memory Rewriting using Polar Codes

En Gad, Eyal and Li, Yue and Kliewer, Joerg and Langberg, Michael and Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2014) Asymmetric Error Correction and Flash-Memory Rewriting using Polar Codes. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20150206-113520153

[img] PDF - Submitted Version
See Usage Policy.

309Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150206-113520153

Abstract

We propose efficient coding schemes for two communication settings: 1. asymmetric channels, and 2. channels with an informed encoder. These settings are important in non-volatile memories, as well as optical and broadcast communication. The schemes are based on non-linear polar codes, and they build on and improve recent work on these settings. In asymmetric channels, we tackle the exponential storage requirement of previously known schemes, that resulted from the use of large Boolean functions. We propose an improved scheme, that achieves the capacity of asymmetric channels with polynomial computational complexity and storage requirement. The proposed non-linear scheme is then generalized to the setting of channel coding with an informed encoder, using a multicoding technique. We consider specific instances of the scheme for flash memories, that incorporate error-correction capabilities together with rewriting. Since the considered codes are non-linear, they eliminate the requirement of previously known schemes (called polar write-once-memory codes) for shared randomness between the encoder and the decoder. Finally, we mention that the multicoding scheme is also useful for broadcast communication in Marton’s region, improving upon previous schemes for this setting.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr124.pdfAuthorTechnical Report
http://arxiv.org/abs/1410.3542arXivDiscussion Paper
http://dx.doi.org/10.1109/TIT.2016.2539967Related ItemArticle
Additional Information:The material in this paper was presented in part at the IEEE Int. Symp. on Inform. Theory (ISIT), Honolulu, HI, USA, July 2014 [8]. This work was supported in part by Intellectual Ventures, NSF grants CIF-1218005, CCF-1439465, CCF-1440001 and CCF-1320785, NSF CAREER Award CCF-0747415 and the US-Israel Binational Science Foundation (BSF) under Grant No. 2010075.
Group:Parallel and Distributed Systems Group
Funders:
Funding AgencyGrant Number
Intellectual VenturesUNSPECIFIED
NSFCIF-1218005
NSFCCF-1439465
NSFCCF-1320785
NSFCCF-0747415
Binational Science Foundation (USA-Israel)2010075
Record Number:CaltechAUTHORS:20150206-113520153
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150206-113520153
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54481
Collection:CaltechPARADISE
Deposited By: Kristin Buxton
Deposited On:06 Feb 2015 19:46
Last Modified:22 Jun 2016 20:10

Repository Staff Only: item control page