Symbol-Intersecting Codes

Abstract — We consider codes consisting of arrays over an alphabet F, in which certain intersecting subsets of n × m coordinates are required to form codewords of length n in prescribed codes over the alphabet F m. Two specific cases are studied. In the

1

Symbol-Intersecting Codes

Ron M.Roth and Gadiel Seroussi

Abstract—We consider codes consisting of arrays over an

alphabet F,in which certain intersecting subsets of n×m coor-

dinates are required to form codewords of length n in prescribed

codes over the alphabet F m.Two speci?c cases are studied.In the

?rst case,referred to as a singly-intersecting coding scheme,the

user data is mapped into n×(2m?1)arrays over an alphabet F,

such that the n×m sub-array that consists of the left(respectively,

right)m columns forms a codeword of a prescribed code of length

n over F m;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×m×m three-dimensional arrays in which parallel n×m sub-

arrays are all codewords of the same prescribed code over F m.

Bounds and constructions are presented for these codes,with the

analysis based on representing the n×m×m arrays as vectors

over certain algebras on m×m matrices.

Keywords:Achievable region,broadcast channels,codes over

rings,Kronecker sum of matrices,Reed-Solomon codes,sub?eld

sub-codes.

I.I NTRODUCTION

Let F be an alphabet and let F m×m be the alphabet that

consists of all m×m arrays A=(a j, )m j, =1over F.De?ne

the following projections from F m×m onto the alphabet F m:

?( )1:F m×m→F m,?( )1(A)=(a j, )m j=1,1≤ ≤m,

?(j)2:F m×m→F m,?(j)2(A)=(a j, )m =1,1≤j≤m.

We regard(column)wordsΓ∈(F m×m)n also as n×

m×m arrays(Γi,j, )n i=1m j, =1over F,with the i th entry

(over F m×m)ofΓbeing identi?ed as the i th cross-section

Γ(i)=(Γi,j, )m

j, =1.The projections?(j)

b

,b=1,2,extend

in a straightforward manner toΓby applying them to each cross-sectionΓ(i),thereby resulting in n×m slices over F, namely,

?( )1(Γ)=(Γi,j, )n i=1m j=1and?(j)2(Γ)=(Γi,j, )n i=1m =1. This work was supported by grant No.2002197from the United-States–Israel Binational Science Foundation(BSF),Jerusalem,Israel.Parts of this work were presented at the IEEE International Symposium on Information Theory(ISIT’2003),Yokohama,Japan(July2003),and at the IEEE Interna-tional Symposium on Information Theory(ISIT’2004),Chicago,Illinois(July 2004).

Ron M.Roth is with the Computer Science Department,Technion,Haifa 32000,Israel.Email:ronny@cs.technion.ac.il.

Gadiel Seroussi is with Hewlett-Packard Laboratories,1501Page Mill Road,Palo Alto,CA94304,USA.Email:seroussi@http://doc.guandang.net.We study the subset(code)C?(F m×m)n de?ned by C=

Γ∈(F m×m)n:

?( )1(Γ)∈C( )1for1≤ ≤m and

?(j)2(Γ)∈C(j)2for1≤j≤m

,(1)

where C( )1and C(j)2are prescribed codes of length n over F m. Notice that the symbols of the codes over F m resulting from the projections in(1)intersect in particular coordinates over the alphabet F;this is in contrast with the known construction of product codes,where codewords of the constituent codes intersect on whole(particular)entries over the code alphabet—F m in our case[2,Ch.10],[11,pp.274–277].

We are interested in constructions that make the overall redundancy of the code C in(1)as small as possible for given length n and error correction capabilities of each code C( )1and C(j)2.In addition to minimizing the overall redundancy,we will also be interested in a?ner analysis of how the redundancy is distributed among the slices,and in characterizing the region of redundancy pro?les attainable by constructions of the codes in(1).

The construction(1)is useful in applications where a certain database(represented by an n×m×m arrayΓ),is accessed by different users,each of whom addresses a certain slice of the database through a noisy channel that is independent of the channels of the other users.We wish each slice to be properly protected against errors,while minimizing the overall redundancy.At the same time,we wish to be able to control the distribution of the redundancy among users,or at least guarantee each user a minimum amount of information(rate) per slice.

The investigation in this paper will focus on two special cases of particular practical and mathematical interest,which are also simpler than the most general model and are therefore more amenable to analysis.In the case of fully-intersecting coding schemes,we take C( )1=C1,independent of ,and C(j)2=C2,independent of j,1≤j, ≤m.A typical code array in this case is shown in Figure1.

In the case of singly-intersecting coding schemes,we take C(1)1=C1,C(1)2=C2,and C( )1=C(j)2=(F m)n for 1<j, ≤m.We can effectively ignore entriesΓthat are indexed by(i,j, )where either >1or j>1,as they are unconstrained.Thus,Γin(1)can effectively be seen as an n×(2m?1)array consisting of two n×m arrays that share one column.

Although we restrict our attention to the case where the cross-section alphabet consists of square m×m arrays,the analysis of the two cases investigated extends without dif?-culty,except for a more cumbersome notation,to rectangular

Abstract …… 此处隐藏：62216字，全部文档内容请下载后查看。喜欢就下载吧 ……