1
Ù
∆
∆
Ù
∆
3
Ù
3
Ù
通信与信息技术
《现代电子技术》2005 年第 7 期总第 198 期
基于 RS 码与 Turbo 码的纠错码特性研究
曾素琼
(嘉应学院 电子信息工程系 广东 梅州 514015)
摘 要: 对两种重要实用的纠错码: R S 码和 T u rbo 码从其特点、纠错能力、码率、编码复杂度、译码复杂度等方面做
比较研究, 以加深对这两种纠错码特性的认识, 利于进一步研究和应用他们。指出 R S 码是最优线性分组码, 实现电路简单,
R S 码的缺点是: 延时较大, 要求精确的帧同步, 当信道条件比较差时, 性能变差; T u rbo 码一般利用递推系统卷积码, 通
过交织器并联而成, 他具有的优点是: 延时短, 译码算法能充分利用软判决, 纠突发错误性能好, 即使在信道条件较差时,
仍有较好的纠错能力, T u rbo 码具有广阔的应用前景; T u rbo 码的编译码运算比 R S 码复杂, 实现电路复杂, 码率低。
关键词: 纠错码; R S 码; T u rbo 码; 软判决
中图分类号: TN 911
23 文献标识码: A 文章编号: 1004 373X (2005) 07
039
03
Study on Performance of Error
correcting Codes w ith RS codes and Turbo
codes
(D ep artm en t of E lectron ic and Info rm ation T echno logy, J iaying U n iversity,M eizhou, 514015, Ch ina)
ZEN G Suqiong
A bs tra c t: T h is p ap er p resen ts a com p arative study of tw o vital and p ractical erro r
co rrecting codes
R S codes and T u rbo
the ab ility of the erro r
the characteristics of tw o erro r
co rrecting, codes′rate, coding com p lex ity and decoding com p lex ity
codes on their characteristics,
view po in t,
R S codes is a op tim um linear b lock codes, and its circu it is sim p le
ex tended latency, fram e synch ron ization and p erfo rm ance w ith the channel condition is w o rse
lu tional codes of the recu rrence system by the acro ss in terleaver
E sp ecially,
codes show s its p ro sp ectiveness
coding op eration of T u rbo
F rom the
co rrecting codes can be know n m o re deep ly and w ill be help fu l to be develop ed and u sed
B u t there are m any p rob lem s encoun tered in R S codes, such as
codes is ob tained u sing convo
A nd its decoding algo rithm can m ake fu ll u se of the soft decision
So the app lication of T u rbo
the coding and de
B u t a b lem ish in an o therw ise p erfect th ing is that, com p ared w ith R S codes′,
it has the p erfo rm ance of co rrecting bu rst erro r even if the channel condition gets w o rse
its circu it is larger and the rate coding is low er
codes is m o re com p lex,
T u rbo
Ke yw o rds: erro r
co rrecting codes; R S codes; T u rbo
codes; soft decision
纠错码技术是一门新的差错控制技术, 是提高信息传
输可靠性的一种重要手段。使用纠错码来解决实际技术问
题时, 首先要从很多各具特性的纠错码中选择到合适的纠
错码类型, 所以, 有必要对各种纠错码的特性有较全面的
了解, 只有这样, 才能选择合适的纠错码类型、研究寻找
到好的纠错码, 经济、有效地解决各种具体问题。
本文对 2 种重要实用的纠错码: R S 码和 T u rbo 码从
其特点、纠错能力、码率、编码复杂度、译码复杂度等应
用特性各方面做比较研究, 利于对 R S 码和 T u rbo 码的全
面认识, 利于进一步研究和应用纠错码。
1 RS 码
R S 码为线性分组码, 是一类有很强纠错能力的多进
制BCH 码, 他不仅在各种通信系统中得到普遍使用, 因为
他具有同时纠随机错和突发错的能力, 特别适合在存在突
收稿日期: 2004
11
27
发错的移动通信系统信道中使用, 而且在存储系统中, 如
CD 和V CD 中也大量使用, 还可以用 R S 码的特点构造某
些密码系统和认证码, 以及密钥共享系统等。
R S 码的最主要特点之一是码元取自 GF (q) 上, 而他
的生成多项式的根也在GF (q) 中, 所以 R S 码是码元符号
域与根域一致的BCH 码。另有其他特点总结如下:
(1) R S 码的设计距离
与实际距离 d 一致, 从这个角
度看, R S 为最佳码 (极大最小距离可分码, M D S 码)。
(2) R S 码重要的特点是具有同时纠随机错和突发错
的能力。
(3) R S 码对码长 n 和信息位长度 k 有限制, 对其应用
有一定影响。
1
1 R S 码的纠错能力
GF (2m ) 上R S 码[ n, k, d ] 的纠错能力: 码长 n = 2m
, 其中
信息位长 k = 2m
1)
b ≤ [ ( t 1)
2 = (
2 = (2m
1)
m + 1 =
1,
为设计距离, R S 码能纠 t = (d
2 个随机错, 同时纠长度为:
2 + 1 的突发错,
k 3)
k 1)
(2m
m
93
1
3
3
3
3
3
3
3
3
3
信 息 安 全
曾素琼: 基于 R S 码与 T u rbo 码的纠错码特性研究
。
1
4 R S 码的译码复杂度
其中 d 为实际最小距离, 他等于设计距离
1
R = k
2 R S 码的码率
n = (2m
)
(2m
3 R S 码的编码复杂度
= (2m
1)
2t
1
(2m
1)
1) = 1
2t
(2m
1)
k = 2t - 2) 级 2m 进制移位寄存器和 k (或 n -
设 GF (2m ) 上 R S 码的纠错能力为 t, 可生成 2 m - 1,
2m - 2t + 1 R S 码, 则 R S 码编码电路可用 k = 2m - 2t +
1 (或 n -
k)
次加法实现, 移位次数是 n 次如图 1 (a) 所示。用二进制部
件实现, 则每个 2m 进制移位寄存器需 m 个二进制移位寄
存器, GF (2m ) 上的乘法电路每个需 m 个二进制移位寄存
器 和 m 次加法实现, 如图 1 (b) 所示。所以, 如用二进制部
件实现, GF (2m ) 上的 R S 码编码电路共需:
m = (2m
2t)
m
m k + 1 = (2m 1) k + 1
= (2m 1) (2m
2t
1) + 1
1)
m
(2m
2t)
k + 1)m = (2t + 1)m
m + m = (k + 1)
(1) 非系统码
二进制移位寄存器个数:
k
门电路个数: m
每组加法运算次数:
2
k
m
(k + 1) = (2m
每组移位次数:
n
(2) 系统码
二进制移位寄存器个数:
(n
门电路个数: m
每组加法运算次数:
m (n
2
m + m = (n
k)
k)
(n
R S 的译码可用一般BCH 码译码器的复杂度评估 (设
采用迭代译码算法) :
(2m
1) + 8m t
n + 8m t = 2
移位器级数: 2
移位次数:
(1 + m )
乘法次数: 3n t + 4t2 = 3 (2m
加法次数: 2n t + 5t2
t = 2 (2m
1) t + 4t2
1) t + 5t2
n + 8m t = (1 + m ) (2m
1) + 8m t
2 Turbo 码
1993 年, C
Berrou 等人提出了一种新型的信道编码
方法
T u rbo 码, 他综合了过去几十年来人们构造乘积
码、级联码以及最大后验概率译码算法、叠代译码思想等
基础上的一种推广和创新, 是近几年来纠错编码领域的重
要突破。T u rbo 码使用相对简单的递归系统卷积码和交织
器就能得到接近 Shannon 极限的纠错性能。T u rbo 码不仅
在信噪比较低的高噪声环境下性能优越, 而且具有很强的
抗衰落、抗干扰能力, 这使得 T u rbo 码在信道条件较差的
移动通信环境中有很大的应用潜力。因而 T u rbo 码被确定
为第三代移动通信系统 IM T 2000 的核心技术之一。
T u rbo 码编码器和译码器如图 2 所示, 由 2 个或 2 个
以上的基本编码器通过交织器并联组成, 基本编码器一般
由递归系统卷积码组成。利用交织技术, 可用两个简单的
成员码构成一个好码。
k) + 1 = (2m 1) (n
k) + 1
每组移位次数:
n
(n
m
k + 1) = (2m
= 2t (2m 1) + 1
图 2 T u rbo 码编码器和译码器
1)
m
(2t + 1)
2
1 T u rbo 码的纠错能力
对于二进制 ( r, k, v) (v 为约束长度) 卷积码构成的
T urbo 码, 其有效自由距离(effective free distance, 相当于
卷积码的自由距离 d ) : d ≤ (2 + 2v- 1) r, v > 2。
一 般 二 进 制 卷 积 码 为 (2, 1, v) , 所 以 对 于 2v 状 态
T urbo 码, 其有效距离为:
d ≤ (2 + 2v- 1) 2 = (4 + 2v) v > 2
二进制移位寄存器个数: 2
加法运算次数: 4
移位次数: N
(N + v ) = 2N
N
v + N
v + N
v + N 2
2
2 T u rbo 码的编码复杂度
对于由 2 个 ( r, k, v) 卷积码通过交织度为N 的分组交
织器组成 T urbo 码编码:
(图中方框为移位寄存器, 椭圆为加法器)
图 1 R S 码编码器
04
二进制移位寄存器个数: 2
加法运算次数: 4
移位次数: N
N
v + N
v + N
(N + v ) = 2N
v + N 2
Ù
1
通信与信息技术
1
1
1
1
1
1
《现代电子技术》2005 年第 7 期总第 198 期
2
3 T u rbo 码的码率
根据收缩和复用的情况, 码率一般为 1
2 和 1
3, 如
图 3 (a)、(b) 所示。
(图中方框为移位寄存器, 椭圆为加法器)
图 3 不同码率的 T u rbo 码编码器
2
4 T u rbo 码的译码复杂度
图 2 (b) 为典型的 T u rbo 码译码器, 其L 12为译码器
1 到译码器 2 的软判决输出, L 21为译码器 2 到译码器 1 的
软判决输出, 译码结果可取自L 12或 L 21的任何一个。
可见 T u rbo 码译码器与迭代次数有关系, 对于由 2 个
( r, k, v) 卷积码通过交织度为 N 的分组交织器组成的
T urbo 码译码器,
N
s (s 为迭代次数)
寄存器个数(不包括M A P 译码器) : 3
移位次数: 为 3N
运算情况分 2 种:
(1) 如M A P 译码器使用普通M A P 算法, 则每个译码
2v 次乘法, 所以对于交织度为N ,
2v 次加法和 6
器需 6
迭代次数为 s 的 T urbo 码, 共需:
s
s
2
2
加法次数: N
乘法次数: N
(2) 如M A P 译码器使用L og M A P 算法, 则每个译码
2v 次加法和 2v+ 2 - 2 次 E 运算, 所以对于交织度为
2v = 3N
2v = 3N
2v+ 2
2v+ 2
6
6
s
s
器需 6
N , 迭代次数为 s 的 T urbo 码, 共需:
加法次数: N
E 运算次数 : N
s
2
s
2v = 3N
6
(2v+ 2 - 2)
2v+ 2
3 RS 码与 Turbo 码的比较总结
R S 码为最优线性分组码, 但 R S 码也带有线性分组
码本身的缺点, 这表现为:
(1) 分组码按帧 (组) 传送, 只有整个码字都接收后,
才开始译码, 这将给系统带来延迟, 特别是大分组码, 延
时较大;
(2) 分组码要求精确的帧同步;
(3) 分组码基于代数规则的译码器常利用解调器的硬
判决输出, 所以信道输出通常为 2 元, 而为了达到 Shannon
限, 要求信道输出为连续值。当信道条件比较好时, 分组
码有较好的性能, 但在低信噪比时, 分组码性能变差。
T u rbo 码一般利用递推系统卷积码, 通过交织器并联
而成, 他具有卷积码的优点, 表现为:
(1) 能连续编码也能连续译码, 延时短。
(2) 译码算法能充分利用软判决。
(3) 充分利用了各组信息的相关性。
(4) 每帧长度较小。
另外, 由于 T u rbo 码通过交织器把突发错误化为相对
独立的错误, 可克服卷积码纠突发错误性能差的缺点。所
以 T u rbo 码的纠错能力很强。
T u rbo 码的缺点是缺乏有效的数学工具进行性能分
析, 所以不容易找到好码。另外, T u rbo 码的编译码运算
比 R S 码复杂, 码率低。
下面举一实例, 对这两种码的主要性能做比较, 可更
直观地了解他们各自的特点。将 8 元 (255, 213, 33) R S
码与码率为 1
2、交织度为 220 b、迭代 18 次的 T u rbo 码
做比较, 如表 1 所示。
表 1 两种码的主要性能比较
码型
性能指标
码长
(交织度)
码率
8 元 (255, 233,
33)R S 码
255
233
255
纠错能力上限 t
同时纠 16 个随机
错, 46 个突发错
编码
运算
复杂
度
译码
运算
复杂
度
移位寄存器个数 99
移位运算次数 25 245
加法运算次数 161
移位寄存器个数 894
移位运算次数 1 404
乘法运算次数 13 264
加法运算次数 9 424
6
18 次 迭 代 交 织 度 220 b
T u rbo 码
220
1
2
每 6 b 纠 错 上 限 为 3, 每
220 b纠错上限 (220
3)
= 110 个随机错
224
49 280
880
660 (不包括M A P 译码器)
11 880
190 080
190 080
参 考 文 献
1 王新梅, 肖国镇
纠错码——原理与方法 [M ]
西安: 西
安电子科技大学出版社, 1991
2 李颖, 谢显中, 王新梅
空时码综述 [J ]
电子与信息学
报, 2002,
(12) : 1 973 1 978
3 焦文华, 梁庆林
时隙ALO HA D S
时隙ALO HA 系统吞吐性能的比较研究 [J ]
学报, 2002,
(6) : 751 757
CDM A 系统与多载波
电子与信息
4 甘良才, 蒋光明, 马斌
阻塞干扰下的性能分析 [J ]
(6) : 796 800
短波跳频系统中分组 T u rbo 码在
电子与信息学报, 2003,
作者简介 曾素琼 女, 1967 年出生, 广东五华人, 现为嘉应学院电子系讲师、高级实验师。1990 年毕业于电子科技大学, 现
正在攻读华南理工大学电信学院电子信息与通信工程专业在职研究生硕士学位。
14