RS編碼和迴旋碼: 串接碼的軟式決定解碼法

Abstract

Reed-Solomon (RS)-迴旋串接碼是一種非常有效的錯誤更碼。由於其強大改錯能力，這種碼已經被應用在很多的通訊和儲存系統。眾所皆知，串接碼的重複解法相對於傳統的串接碼在性能上有明顯的改善。但是，除了Jiang及Narayanan（JN）兩氏在兩年前提出利用信心傳遞法推導出來的複雜度頗高的方法之外由於缺乏有效的軟式輸出演算法，幾乎所有的RS碼或RS-迴旋串接碼之解碼器都用硬式解碼法。 很多快速限定距離軟式RS解碼演算法在1990年代初期即被提出，但其解碼能力與硬式解碼法比較改善有限。1997年Sudan是第一位提出可以對低編碼率RS碼超越其硬式解碼設計距離的有效軟式解碼法的人。兩年之後他和他的學生Guruswami更進一步提出簡稱為GS演算法的改良版本。這個新演算法由兩個部分所組成: 內插和因式分解。K□tter與Vardy（KV）接著又提出另一軟式解碼演算法。他們藉由轉換通道可靠度到內差點的點數，大大減低了GS演算法的解碼複雜度。由於KV演算法的複雜度仍然高，K□tter與其他的人再藉由轉換接收的值可以改善重複的次數，使得改良後的KV演算法變得可行。 本篇論文的目的在於探討RS碼軟式輸入和軟式輸出 (SISO)解碼的可能性，希望讓RS-迴旋串接碼的重複解變為實際可能。我們評估了不同軟式RS 解碼法的效能，檢視它們對單獨RS碼及串接碼所能提供的改善幅度。我們也提出一種綜合改良式KV演算法和JN軟式演算法的遞迴式SISO RS-迴旋串接碼解碼法並透過電腦模擬估算其解碼能力。