On q-ary Antipodal Matchings and Applications

Ordentlich, Erik ; Roth, Ron M. ; Seroussi, Gadiel

HP Development Company

关键词: resistive memories;    crossbar memories;    Boolean threshold functions;    weight-constrained codes;    two- dimensional coding;   

RP-ID  :  HPL-2012-113

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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.