Algebraic soft decoding of Reed-Solomon codes with improved progressive interpolation

详细信息    查看全文

• 作者：Yi Lyu ^{lvyi3@mail2.sysu.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Li Chen ; ^{chenli55@mail.sysu.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae
• 关键词：Algebraic soft decoding ; Complexity reduction ; Koetter&ndash ; Vardy algorithm ; Re-encoding transform ; Reed&ndash ; Solomon codes
• 刊名：Physical Communication
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：20
• 期：Complete
• 页码：48-60
• 全文大小：795 K

文摘

The algebraic soft decoding (ASD) algorithm for Reed–Solomon (RS) codes can correct errors beyond the half distance bound with a polynomial time complexity. However, the decoding complexity remains high due to the computationally expensive interpolation that is an iterative polynomial construction process. By performing the interpolation progressively, the progressive ASD (PASD) algorithm can adapt the decoding computation to the need, leveraging the average complexity of multiple decoding events. But the complexity reduction is realised at the expense of system memory, since the intermediate interpolation information needs to be memorised. Addressing this challenge, this paper proposes an improved PASD (I-PASD) algorithm that can alleviate the memory requirement and further reduce the decoding complexity. A condition on expanding the set of interpolated polynomials will be introduced, which excepts the need of performing iterative updates for the newly introduced polynomial. Further incorporating the re-encoding transform, the I-PASD algorithm can reduce the decoding complexity over the PASD algorithm by a factor of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1874490716300404&_mathId=si69.gif&_user=111111111&_pii=S1874490716300404&_rdoc=1&_issn=18744907&md5=c9021c455236239a7736af3be59617e4" title="Click to view the MathML source">1/3class="mathContainer hidden">class="mathCode">$1/3$ and its memory requirement is at most half of the PASD algorithm. The complexity and memory requirement will be theoretically analysed and validated by numerical results. Finally, we will confirm that the complexity and memory reductions are realised with preserving the error-correction capability of the ASD algorithm.