Error-Correcting WOM Codes through Concatenation and Joint Design

Error-Correcting WOM Codes through Concatenation and Joint Design
January, 11, 2018
14:30
Room 1061 Electrical Eng. Building Technion City

Communication and Information Theory

Graduate Seminar

Speaker: Amit Solomon

Affiliation: Viterbi Faculty of Electrical Engineering, Technion

WOM (write-once memory) codes offer an effective solution for the greatest impediment of Flash-based storage: not being able to re-write data in place. They solve this problem by guaranteeing up to t writes of arbitrary information without need to move the physical cells in the downward direction that is forbidden by the Flash read/write circuitry.
While extremely promising, combining WOM codes with the error-correcting (EC) codes needed for reliability is a challenging and largely unsolved goal. In this work we propose a new scheme to combine WOM with EC codes. We use short WOM codes over the q-ary alphabet (q is the number of levels supported by the physical device), and concatenate them with outer EC codes. We present multiple code constructions for guaranteed error correction in common error models, which improve storage rates over straightforward concatenation. Our main construction method
is to jointly design the EC and WOM codes such that the same amount of WOM redundancy is exploited for stronger error correction. To evaluate and compare our constructions, we define a new rate measure that captures the residual redundancy added to a WOM code for error correction. Time permitting, we will also discuss a related EC-WOM scheme based on multi-level coding designed for random memory errors.

* MSc. student under the supervision of Prof. Yuval Cassuto.