MDS ARRAY CODES WITH INDEPENDENT PARITY SYMBOLS

A new family of MDS array codes is presented, The code arrays contain p information columns and r independent parity columns, each column co nsisting of p-1 bits, where p is a prime, We extend a previously known construction for the case r = 2 to three and more parity columns, It is shown that when r = 3 such extension is possible for any prime p. F or larger values of r, we give necessary and sufficient conditions for our codes to be MDS, and then prove that if p belongs to a certain cl ass of primes these conditions are satisfied up to r less than or equa l to 8, One of the advantages of the new codes is that encoding and de coding may be accomplished using simple cyclic shifts and XOR operatio ns on the columns of the code array, We develop efficient decoding pro cedures for the case of two- and three-column errors, This again exten ds the previously known results for the case of a single-column error, Another primary advantage of our codes is related to the problem of e fficient information updates, We present upper and lower bounds on the average number of parity bits which have to be updated in an MDS code over GF (2(m)), following an update in a single information bit, This average number is of importance in many storage applications which re quire frequent updates of information, We show that the upper bound ob tained from our codes is close to the lower bound and, most importantl y, does not depend on the size of the code symbols.