Rank Modulation Codes for Translocation Errors

University of Illinois in Urban-Champaign

Abstract:

We consider a generalization of rank modulation coding for flash memories that allows for handling arbitrary charge drop errors. Unlike rank modulation codes that may be used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed translocation rank codes account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transposition and as such may be analyzed using related concepts in combinatorics and rank modulation coding. 

Our results include tight bounds on the capacity of translocation rank codes, construction techniques for asymptotically good codes, as well as simple decoding methods for the proposed structured code families.

Biography:

Farzad Farnoud (Hassanzadeh) received his BS degree in Electrical Engineering from Sharif University of Technology, Iran, on August 2006. He received his MSc degree in Electrical and Computer Engineering from University of Toronto, Canada. He is currently a PhD candidate in Electrical and Computer Engineering at UIUC. His research interests include distribution estimation in the presence of errors, rank modulation for flash memories and rank aggregation algorithm.

For inquiry, contact Prof. Lara Dolecek (dolecek@ee.ucla.edu)