Reduced-Redundancy Product Codes for Burst Error Correction

Roth, Ron M. ; Seroussi, Gadiel

HP Development Company

关键词: error-correcting codes;    Reed-Solomon codes;    array codes;    generalized concatenatedcodes;    product codes;    superimposed codes;   

RP-ID  :  HPL-97-25

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

美国|英语

来源: HP Labs

【 摘 要 】

In a typical burst-error correction application of a product code of n(sub v) X n(sub h) arrays, one uses an [n(sub h), n(sub h) - r(sub h) code C(sub h) that detects corrupted rows, and an [n(sub v), n(sub v) - r(sub v)] code C(sub v) that is applied to the columns while regarding the detected corrupted rows as erasures. Although this conventional product code scheme offers very good error protection, it contains excessive redundancy, due to the fact that the code C(sub h) provides the code C(sub v) with information on many error patterns that exceed the correction capability of C(sub v). In this work, a coding scheme is proposed in which this excess redundancy is eliminated, resulting in significant savings in the overall redundancy compared to the conventional case, while offering the same error protection. The redundancy of the proposed scheme is n(sub h) r(sub v) + r(sub h)(lnr(sub v) + O (1)) + r(sub v), where the parameters r(sub h) and r(sub v) are close in value to their counterparts in the conventional case, which has redundancy n(sub h) r(sub v) + n(sub v) r(sub h) - r(sub h) r(sub v). In particular, when the codes C(sub h) and C(sub v) have the same rate and r(sub h) << n(sub h), the redundancy of the proposed scheme is close to one half of that of the conventional product code counterpart. Variants of the scheme are presented for channels that are mostly bursty, and for channels with a combination of random errors and burst errors.