Abstract:

Aiming at the problems of Reed-Solomon algorithm（RS）, such as the encoding process involving finite field operations, high complexity, low efficiency, high computational cost that is difficult to accept by large-scale distributed storage systems, a new improved algorithm of RS Cauchy code is proposed. Firstly, the algorithm uses the greedy algorithm to select the local optimal Cauchy matrix, which reduces the computational complexity of the Cauchy code. At the same time, the binary matrix is replaced by the finite field elements in the Cauchy matrix to be arrayed. The finite field operation is converted into the XOR operation. And the array is optimized, which further reduces the calculation amount and increases the encoding efficiency of the Cauchy code. The results of simulation experiments indicate that the improved RS Cauchy code algorithm has less computation than the Cauchy code of the optimal Cauchy matrix. The array code is known for its high encoding efficiency. The improved algorithm has higher encoding efficiency than the EVENODD code and the STAR code in the array code. And it can choose a simpler and more efficient decoding method, which has the similar array code property. To a certain extent, the decoding efficiency can be improved.

Key words: RS Cauchy code, Maximum Distance Separable（MDS） code, binary matrix, array, encoding efficiency

摘要：

针对RS（Reed-Solomon）算法编码过程涉及有限域运算，复杂度高，效率低，运算代价难以被大规模分布式存储系统所接受等问题，提出了一种RS柯西码编码改进算法。该算法用贪心算法选取局部最优柯西矩阵，减少柯西码的计算量。同时，引入二进制矩阵替换柯西矩阵中的有限域元素进行阵列化，将有限域运算转换为异或运算，并对阵列进行运算优化，进一步减少计算量，增加柯西码的编码效率。根据仿真实验表明，改进后RS柯西码与通过遍历得到的最优柯西矩阵的柯西码相比，计算量更小，与编码效率著称的阵列码中的EVENODD码和STAR码相比，编码效率更高。并且具有类似阵列码性质，能够选择更简单高效的译码方法，在一定程度上提高解码效率。

关键词: RS柯西码, 极大距离可分码, 二进制矩阵, 阵列化, 编码效率