Technical Reports
HPL-2012-113
Click here for full text:
On q-ary Antipodal Matchings and Applications
Ordentlich, Erik; Roth, Ron M.; Seroussi, Gadiel
HP Laboratories
HPL-2012-113
Keyword(s): resistive memories; crossbar memories; Boolean threshold functions; weight-constrained codes; two- dimensional coding
Abstract: We define a q-ary antipodal matching to be a perfect matching in the bipartite graph with vertices corresponding to words of length l over the integer alphabet Q = {0, 1, ..., q-1}, wherein the left and right vertices are those with respective component sums greater and smaller than l(q-1)/2, and wherein two vertices are connected by an edge if one of the corresponding words dominates the other. We present two different constructions of efficiently computable q-ary antipodal matchings. We then show how such matchings can be used for encoding arbitrary data into n x n arrays over the alphabet Q all of whose row and column sums are at most n(q-1)/2. Such encoders might be useful for mitigating parasitic currents in a next generation memory technology based on crossbar arrays of resistive devices.
5 Pages
External Posting Date: May 21, 2012 [Fulltext]. Approved for External Publication
Internal Posting Date: May 21, 2012 [Fulltext]