Codes on Permutations: Rank ModulationAryaMazumdarJoint work with Alexander Barg, University of Maryland-College ParkFlash memory• Array of Floating Gate Memory Cells.• In abundant use for short-term storage and limited number of writes.• Can they be used as caches? • What is the best model for the errors in Flash memory?• How to increase the longevity of the flash devices?• What will be the architecture of a high-performance error-resilient Flash controller?A USB Flash Drive. The chip on the left is the flash memory. The controller is on the right (Wikipedia).Reliability of data in Flash memory and rank modulation schemeDrift of charge from cells: Reliability of data stored.qq-1......3211 2 3 4 . . nInformation is written in blocks of n cells with q charge levels in each cells.Memory Cellsqq-1......3211 2 3 4 . . n• Conventional q-ary codes can be used for protection of data.• The error process is non-conventional!Error caused by drift of charge qq-1......3211 2 3 4 . . n• Due to charge leakage, after some time (aging of device) all cells will contain erroneous values.• Moreover the rate of leakage in different cells may vary.• Error correction schemes designed for q-ary writing will FAIL.Storing data in Flash memory1 2 3 4 5 6 74 6 7 1 5 3 2•Rank Modulation Scheme (ISIT’08 Jiang/Schwartz/Bruck).• Store information as the relative values of the charge levels.• σ = (4, 7, 6, 1, 5, 2, 3) • Levels can take continuous values.Storing data in Flash memory1 2 3 4 5 6 74 6 7 5 312Storing data in Flash memory1 2 3 4 5 6 74 6 7 2 5 3 1Codes in permutations• Sn= Group of permutations on n symbols • Vector representation: = ((1), (2), … (n),)• Identity: (1, 2, 3, … ,n)• Multiplication: Composition (1, 3, 2, 4)(2, 4, 1, 3)=(2, 1, 4, 3)• Inverse: (3, 4, 2, 1)(4, 3, 1, 2) = (1, 2, 3, 4) • Transposition: (1,3, 5, 4, 6, 2) (1, 3, 5, 2, 6, 4)Codes in permutationsCodes in permutations with Kendall metricRank modulation codesCoding for the Kendall distanceCoding for the Kendall distanceBounds on the size of codesCapacity of rank modulation SchemeTo prove: basic argumentsTo prove: basics of permutation1 0 1 20 0 2 0 1xσ 2 1 6 4 3 7 5 9 8Direct attempt to find the volume of the sphereDirect attempt to find the volume of the sphereDirect attempt to find the volume of the sphereIsometric embeddingsIsometric embeddingsCodes that correct t-errorsExistence of good codes: proof ideaExistence of good codes: proof ideaExistence of good codes: main toolExistence of good codes: final stepExplicit constructionsPermutation Polynomials: Polynomials that give bijective maps from a finite field to itself.Main Idea: Evaluations of permutation polynomials of bounded degree forms a subset of Reed-Solomon code.Problem 1: Identifying permutation polynomials calls for extensive search.Consider special classes, such as, Linearized polynomials, Dickson polynomials, monomials. Problem 2: Connecting Kendall Distance with Hamming distance is difficult. We use certain accumulator-type transformation that does the job for small distances. Construction from good codes of the Hamming space: We find a distance preserving Gray Map (and its variations) for the space of inversion vectors and the Hamming space of comparable size.Remember we seek an additive error correcting code in the space of inversion vectors.We obtain family of ‘good’ codes, efficiently encodable and decodable, that corrects up to O(n 1+ε) number of errors, for 0≤ε≤1.To
View Full Document
Unlocking...