P1A-4
A Transform-Domain Decoding Algorithm for Reed-Solomon Codes
Z. H. Cai, J. Z. Hao, S. M. Sun, P. S. Chin and Z. N. Chen
Institute for Infocomm Research, 21 Heng Mui Keng Terrace, Singapore 119613
Abstract –– This paper presents a Reed-Solomon decoding
algorithm based on the Euclidean algorithm. The algorithm is
conceptually simple and operates only in transform domain.
The spectrum of the codeword is directly computed without
the explicit knowledge of error-locator and error-evaluator
polynomials; the Chien search and the Forney algorithm are
not necessary.
Index Terms –– Block Codes, Channel Coding, Decoding,
Reed-Solomon Codes.
I. INTRODUCTION
The decoding algorithm for algebraic codes, including
Reed-Solomon codes, has been investigated for over three
decades [1]. Consider a Reed-Solomon code over GF(q)
with length n, number of information symbols k, and
designed odd distance d, (n=q-1, k, d=q-k). Assume the
number of errors 2/)1( −=≤ dte , the ‘conventional’
approaches take the following steps to decode the received
word
)(xv :
1) Computer the syndromes polynomial S(x),
2) Solve the Berlekamp’s key equation to find the error-
locator polynomial
)(
x
Λ
and error-evaluator polynomial
)(
x
Ω ,
3) Find the roots of the
)(
x
Λ
, and
4) Find the error values at error locations.
It is well known that the error-locator and error-evaluator
polynomials are related through Berlekamp’s key-equation
)(mod)()()(
2t
xxxSx Ω=Λ
. Usually this equation is solved
by the Berlekamp-Massey algorithm [2] or Euclidean
algorithm [3].
There are other methods to decode RS codes without the
computation of syndromes [4]. The key equation is changed
to a new Welch-Berlekamp key-equation, which is based on
the remainder polynomial. Recently methods that decode
RS codes beyond the error-correcting bound have been
proposed as well [5][6], where the list-decoding of Reed-
Solomon is viewed as a bivariate interpolation problem.
Based on the bivariate interpolation, a interesting RS
decoding algorithm that involves no syndrome calculation
or error value/location evaluation is suggested in [6,
Appendix C] by setting m = 1 and L = 1 in Kötter’s
bivariate interpolation algorithm.
In this paper a conventional decoding algorithm for RS
codes is presented. It is motivated by the approach
suggested by R. E. Blahut [1, Figure 9.3]. It needs the
spectrum of the received senseword to compute partial
Greatest Common Divisor (GCD) based on Euclidean
algorithm. The spectrum of the codeword can be recovered
through a polynomial division. Compared to the bivariate
interpolation approach in [6], it is conceptually simpler. The
advantage of our method is it does not require the codes to
be cyclic and it could be generalized to decode algebraic
geometry codes via Gröbner bases.
The paper is organized as follows. Section II presents the
transform-domain decoding algorithm for Reed-Solomon
codes with fixed generator polynomial offset. A method to
remove the offset constraint on the generator polynomial is
discussed in the section III and the section IV summarizes
the paper.
II. T
HE TRANSFORM-DOMAIN DECODING ALGORITHM
For the time being assume the generator polynomial of
the (n, k, d) RS code is
∏
−
−=
−=
1
2
)()(
n
tnj
j
xxg
α
, i.e. the offset
of the generator polynomial is fixed as n-2t. The offset
restriction will be removed later in Section III. Let the
spectrum polynomial of the codeword c(x) be C(x) which
has degree at most k-1. In the following deduction we
assume the error pattern, ),...,,(
110 −
=
n
eeee
G
, has weight
less than or equal to t, i.e., the number of the elements, e, in
the following indices set,
{}
0| ≠=
i
eiM , (1)
satisfies
tMe ≤= . The received word )(xv satisfies the
following equation
)()()(
x
e
x
c
x
v
+= . (2)
Let the spectrum polynomials of v(x), e(x) be V(x) and
E(x), respectively. Obviously we have
)()()(
x
E
x
C
x
V
+= . (3)
A proof of the algorithm in [1, Figure 9.3] is given as
follows:
1-4244-0102-X/06/$20.00 ©2006 IEEE
635
下载后可阅读完整内容，剩余3页未读，立即下载
Zhaohuibpps
- 粉丝: 0
- 资源: 4
我的内容管理
展开
最新资源
- C++标准程序库：权威指南
- Java解惑：奇数判断误区与改进方法
- C++编程必读：20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程：从入门到精通
- Spring3.0权威指南：JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略：从环境配置到索引创建
- 内存虚拟硬盘技术：提升电脑速度的秘密武器
- Java操作数据库：保存与显示图片到数据库及页面
- ISO14001：2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发：触发器与控制器重定向技术详解
- FPGA开发实战指南：创新设计与进阶技巧
- ShopExV4.8二次开发入门：解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
