在BCH解碼中錯誤定位多項式計算方法之探討、比較及矩陣描述

Abstract

本論文針對BCH碼在文獻中所提出之解碼方法所用之各種重要演算法，如：Berlekamp-Massey演算法(BMA)、Euclid演算法、Welch-Berlekamp演算法及各種無倒數運算方法等，予以歸納探討整理。這些演算法主要是用來解錯誤位置關鍵式或解錯誤位置多項式。我們並以應用在DVD規格中之RS(208,192)碼為例，比較各種演算法之乘法運算量、倒數運算量及記憶體需求量，以了解各種方法之優缺點。 本文並針對性能最佳且最常被使用來解錯誤位置多項式之Berlekamp-Massey演算法，以一個簡單且容易了解的矩陣方式來描述BMA的疊代步驟；本文最後說明此矩陣方式所描述之BMA，經簡單修改後，即可推導出無倒數運算之BMA。

In this thesis we survey the important algorithms in literature for decoding the BCH code; these algorithms includes the Berlekamp-Massey algorithm (BMA), the Euclid algorithm, the Welch-Berlekamp algorithm, and the corresponding inverse-free algorithms, used mainly to obtain the key equation of the error locator or the error-locator polynomial. We also investigate the performance of each decoding method using one Reed-Solomon code RS(208,192), adopted in the DVD specification, as an example by the number of multiplications, inverses, and memories required for realizing the algorithms. This thesis further focuses on the BMA, the most efficient decoding algorithm to obtain the error-locator polynomial from the syndromes, and presents a new description by using the matrix representation. This approach makes the derivation of BMA simpler and easier to understand, especially for the beginner. The matrix representation further enables us to derive easily the inverse-free BMA by simple coefficient modification.