Symbol-Intersecting Codes

Roth, Ron M. ; Seroussi, Gadiel

HP Development Company

关键词: error-correcting codes;    broadcast channels;    codes over rings;    Reed-Solomon codes;    sub-field sub-codes;    Kronecker sum of matrices;   

RP-ID  :  HPL-2004-117

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

美国|英语

来源: HP Labs

【 摘 要 】

Please note: This abstract contains mathematical formula which cannot be represented here. We consider codes consisting of arrays over an alphabet F, in which certain intersecting subsets of n x m coordinates are required to form codewords of length n in prescribed codes over the alphabet Fm. Two specific cases are studied. In the first case, referred to as a singly-intersecting coding scheme, the user data is mapped into n x (2m-1) arrays over an alphabet F, such that the n x m sub-array that consists of the left (respectively, right) m columns forms a codeword of a prescribed code of length n over Fm; in particular, the center column is shared by the left and right sub-arrays. Bounds are obtained on the achievable redundancy region of singly-intersecting coding schemes, and constructions are presented which approach--and sometimes meet-- these bounds. It is shown that singly-intersecting coding schemes can be applied in a certain model of broadcast channels to guarantee reliable communication. The second setting, referred to as a fully-intersecting coding scheme, maps the user data into n x m x m three-dimensional arrays in which parallel n x m sub-arrays are all codewords of the same prescribed code over Fm. Bounds and constructions are presented for these codes, with the analysis based on representing the n x m x m arrays as vectors over certain algebras on m x m matrices. 35 Pages