Error correcting codes for rank modulation
US8225180B2 · kind B2 · utility
Assignees
Inventors
Key dates
| Filing date | Nov 20, 2008 |
| Grant date | Jul 17, 2012 |
| Priority date | — |
| Expiry date | Apr 17, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG11C2211/5634
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
We investigate error-correcting codes for a novel storage technology, which we call the rank-modulation scheme. In this scheme, a set of n cells stores information in the permutation induced by the different levels of the individual cells. The resulting scheme eliminates the need for discrete cell levels, and overshoot errors when programming cells (a serious problem that reduces the writing speed), as well as mitigates the problem of asymmetric errors. In this discussion, the properties of error correction in rank modulation codes are studied. We show that the adjacency graph of permutations is a subgraph of a multi-dimensional array of a special size, a property that enables code designs based on Lee-metric codes and L1-metric codes. We present a one-error-correcting code whose size is at least half of the optimal size. We also present additional error-correcting codes and some related bounds.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.