2009-7-19
现代通信原理第十一章 差错控制编码第十一章 差错控制编码
§ 11.4 BCH码
§ 11.5 纠正和检测突发错误的分组码
§ 11.5 纠错码的误码性能
§ 11.4 BCH码
即约多项式
– 一个 m 次多项式不能被二元域上任何二次数小于的，但大于 0的多项式除尽，如 是即约的。
本原多项式
– 若 m次多项式 P(x)除尽的 的最小正整数 n 满足,就称为本原的。
– 如 能除尽,但除不尽 的
。
– 如,是即约的，但不是本原的，因它能除尽 。
125 DD
1?nx
12 mn
1)( 4 xxxp 115?x 151 n
1?nx
1234 xxxx
15?x
§ 11.4.1 本原循环码
由本原多项式构成的码称为本原码。
特点
– 码长为
– 它的生成多项式是由若干 m阶或以 m的因子为最高阶的多项式相乘而构成。
要判定 (n,k) 的循环码是否存在，只需要判断 n-k
阶的生成多项式是否能由 Dn+1的因式构成。
为正整数mm,12?
循环码例子
生成多项式的阶次为 r,该生成多项式是否是的因此。
一个 m阶即约多项式一定能除尽
如,m＝ 5，共有 6个 5阶即约多项式。
再加上 因子,是以上 7个多项式的乘积。
kknrnkn mm 12,12),,(
1?nD
11 12mDD n
111
111
345123535
245234525
DDDDDDDDDD
DDDDDDDDDD
)1(?D 131?D
§ 11.4.2 BCH 码的生成多项式
如果循环码形式的形式为
为纠错个数,为最小多项式，
为最小公倍数最小码距码长为 的 BCH码称为 本 BCH码（侠义）
码长为 则称为非本原 BCH码
),(),(),(L C M)( 1231 DmDmDmDg t
)(Dmi
LCM
t
12 mn
12 mn
12 td
BCH 码
由于 g(D)有 t个因式，且每个因式的最高次为 m，
因此监督码元最多有 mt位。
对于纠 t 个错误的本原 BCH码，其生成多项式
纠单个错误的本原 BCH码字为汉明码。
– 表 11－ 13给出了 n<5的本原 BCH码。
11－ 14给出了部分非本原 BCH码。
)()()()( 1231 DmDmDmDg t
BCH 码例子
纠正 3 个错误，码长为 15的 BCH码解,n=15,m=5 查表 11-12得，
23 37 07
这是 (15,5)码。
1
)1)(1)(1(
)()()()(
245810
22344
531
DDDDDD
DDDDDDDD
DmDmDmDg
重要的 BCH码 (23,12)
表 11－ 14中最重要的 BCH码是 (23,12)
称为格雷码，码间为 7，能纠正 3个错误。
生成多项式
在实际通信系统中，所要求的 n,k并不是码表中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。
1)( 567911 DDDDDDDg
BCH码
如 BCH码的码长为奇数，而有时需要偶数码长，这时可以在原 BCH码生成多项式中乘以（ D+1)因子，从而得到（ n+1,k）扩展 BCH码，这时相当于在原 BCH码上加一个全校验位，从而将码距增加 1，这时的码字不具有循环性。
如果 BCH码不是 2m-1或它的因式，这时可以采用缩短的方式，去掉 s位信息,(n-s,k-s)
RS码 Reed-Solomon
非二进制 BCH码，输入以符号来考虑
假定每组有 K 个符号，每个符号用 m比特，输入信息将是 K× m 比特。
RS码
RS码适合于纠正突发错误，纠正的错误图样有
对于一个长度为 符号的 RS码，每个符号都可以看成是有限域 中的一个元素，如
RS码的最小码距为 d符号，则生成多项式个突发比特的总长度为个突发比特的总长度为比特的单个突发总长度为
iimitb
mtb
mtb
12)12(
31)3(
1)1(
1
1
1
12?m
)2( mGR
)())()(()( 132 dDDDDDg
中的一个元素是 )( mi GR
§ 11.5 纠正和检测突发错误的分组码
－交织码 interleaved
在水平垂直监督码中将信息码排列成方阵，然后对行和列分别进行检验，可以达到检测突发错误的目的。
如果方阵中行码是能纠 t 个随机错误，交织后能纠 t个长度为 i的突发错误。 i称为交织深度。
i
t
循环码构成交织码
采用循环码构成交织码时，可以不采用方阵就能实现编码。
假设交织码每行为 循环码，其生成多项式为,可以除尽,如交织深度为 其交织码为,其生成多项式为可以除尽,所以也是循环码。
1?nD
),( ii kn
)()( ii DgDg?
11)( nini DD
i
),( kn
)(Dg )(Dg
)( iDg ),( ii kn
循环码构成交织码 (续 )
如，循环码 (7,4),其生成多项式为构成交织深度为 3 的 (21,12)交织码。
交织码的生成多项式为它也是循环码，可以用循环码的方式构成。在发送端可以不排成方阵，但是在译码时，必须将码字排列成 阵列，然后分别独立的对每行码字进行译码。
1)()()()( 690323333 DDDDDDg
in?
1)( 23 DDDg
交织码 之小结
为了进一步提高纠错能力，可以在交织阵列中不仅对每行进行纠错编码，而且也对每列进行纠错编码，这种形式的交织码称为乘积码。
若乘积码的行码和列码 分别能纠长度超过 的突发错误，则乘积码能纠正长度为 的突发错误。
交织一般都带固有延时，在语音中交织的延时不要超过 40ms。
),( 21 nn长为
21 bb和
),m a x ( 2211 nbnbb?
法尔码 Fire
也是循环码，能纠单个突发错误。
法尔码的纠错能力
CRC 码
循环冗余检验码，简称 CRC，也是循环码。
能检测出以下错误常用 CRC 码
常用的四种，已经成为国际标准。
§ 11.6 纠错码的误码特性
任何纠错码的能力都是有限的，超出纠错码能力的错误不可能纠正，甚至会出现乱纠的现象。
采用纠错后，误码性能的改善？
由于纠错码种类很多，纠错能力各不相同，译码方法也不同，因此其性能必须根据具体分析和计算。
BSC & AWGN
BSC
– 如果纠正 t 个随机错误，则
AWGN
– BPSK
现代通信原理第十一章 差错控制编码第十一章 差错控制编码
§ 11.4 BCH码
§ 11.5 纠正和检测突发错误的分组码
§ 11.5 纠错码的误码性能
§ 11.4 BCH码
即约多项式
– 一个 m 次多项式不能被二元域上任何二次数小于的，但大于 0的多项式除尽，如 是即约的。
本原多项式
– 若 m次多项式 P(x)除尽的 的最小正整数 n 满足,就称为本原的。
– 如 能除尽,但除不尽 的
。
– 如,是即约的，但不是本原的，因它能除尽 。
125 DD
1?nx
12 mn
1)( 4 xxxp 115?x 151 n
1?nx
1234 xxxx
15?x
§ 11.4.1 本原循环码
由本原多项式构成的码称为本原码。
特点
– 码长为
– 它的生成多项式是由若干 m阶或以 m的因子为最高阶的多项式相乘而构成。
要判定 (n,k) 的循环码是否存在，只需要判断 n-k
阶的生成多项式是否能由 Dn+1的因式构成。
为正整数mm,12?
循环码例子
生成多项式的阶次为 r,该生成多项式是否是的因此。
一个 m阶即约多项式一定能除尽
如,m＝ 5，共有 6个 5阶即约多项式。
再加上 因子,是以上 7个多项式的乘积。
kknrnkn mm 12,12),,(
1?nD
11 12mDD n
111
111
345123535
245234525
DDDDDDDDDD
DDDDDDDDDD
)1(?D 131?D
§ 11.4.2 BCH 码的生成多项式
如果循环码形式的形式为
为纠错个数,为最小多项式，
为最小公倍数最小码距码长为 的 BCH码称为 本 BCH码（侠义）
码长为 则称为非本原 BCH码
),(),(),(L C M)( 1231 DmDmDmDg t
)(Dmi
LCM
t
12 mn
12 mn
12 td
BCH 码
由于 g(D)有 t个因式，且每个因式的最高次为 m，
因此监督码元最多有 mt位。
对于纠 t 个错误的本原 BCH码，其生成多项式
纠单个错误的本原 BCH码字为汉明码。
– 表 11－ 13给出了 n<5的本原 BCH码。
11－ 14给出了部分非本原 BCH码。
)()()()( 1231 DmDmDmDg t
BCH 码例子
纠正 3 个错误，码长为 15的 BCH码解,n=15,m=5 查表 11-12得，
23 37 07
这是 (15,5)码。
1
)1)(1)(1(
)()()()(
245810
22344
531
DDDDDD
DDDDDDDD
DmDmDmDg
重要的 BCH码 (23,12)
表 11－ 14中最重要的 BCH码是 (23,12)
称为格雷码，码间为 7，能纠正 3个错误。
生成多项式
在实际通信系统中，所要求的 n,k并不是码表中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。
1)( 567911 DDDDDDDg
BCH码
如 BCH码的码长为奇数，而有时需要偶数码长，这时可以在原 BCH码生成多项式中乘以（ D+1)因子，从而得到（ n+1,k）扩展 BCH码，这时相当于在原 BCH码上加一个全校验位，从而将码距增加 1，这时的码字不具有循环性。
如果 BCH码不是 2m-1或它的因式，这时可以采用缩短的方式，去掉 s位信息,(n-s,k-s)
RS码 Reed-Solomon
非二进制 BCH码，输入以符号来考虑
假定每组有 K 个符号，每个符号用 m比特，输入信息将是 K× m 比特。
RS码
RS码适合于纠正突发错误，纠正的错误图样有
对于一个长度为 符号的 RS码，每个符号都可以看成是有限域 中的一个元素，如
RS码的最小码距为 d符号，则生成多项式个突发比特的总长度为个突发比特的总长度为比特的单个突发总长度为
iimitb
mtb
mtb
12)12(
31)3(
1)1(
1
1
1
12?m
)2( mGR
)())()(()( 132 dDDDDDg
中的一个元素是 )( mi GR
§ 11.5 纠正和检测突发错误的分组码
－交织码 interleaved
在水平垂直监督码中将信息码排列成方阵，然后对行和列分别进行检验，可以达到检测突发错误的目的。
如果方阵中行码是能纠 t 个随机错误，交织后能纠 t个长度为 i的突发错误。 i称为交织深度。
i
t
循环码构成交织码
采用循环码构成交织码时，可以不采用方阵就能实现编码。
假设交织码每行为 循环码，其生成多项式为,可以除尽,如交织深度为 其交织码为,其生成多项式为可以除尽,所以也是循环码。
1?nD
),( ii kn
)()( ii DgDg?
11)( nini DD
i
),( kn
)(Dg )(Dg
)( iDg ),( ii kn
循环码构成交织码 (续 )
如，循环码 (7,4),其生成多项式为构成交织深度为 3 的 (21,12)交织码。
交织码的生成多项式为它也是循环码，可以用循环码的方式构成。在发送端可以不排成方阵，但是在译码时，必须将码字排列成 阵列，然后分别独立的对每行码字进行译码。
1)()()()( 690323333 DDDDDDg
in?
1)( 23 DDDg
交织码 之小结
为了进一步提高纠错能力，可以在交织阵列中不仅对每行进行纠错编码，而且也对每列进行纠错编码，这种形式的交织码称为乘积码。
若乘积码的行码和列码 分别能纠长度超过 的突发错误，则乘积码能纠正长度为 的突发错误。
交织一般都带固有延时，在语音中交织的延时不要超过 40ms。
),( 21 nn长为
21 bb和
),m a x ( 2211 nbnbb?
法尔码 Fire
也是循环码，能纠单个突发错误。
法尔码的纠错能力
CRC 码
循环冗余检验码，简称 CRC，也是循环码。
能检测出以下错误常用 CRC 码
常用的四种，已经成为国际标准。
§ 11.6 纠错码的误码特性
任何纠错码的能力都是有限的，超出纠错码能力的错误不可能纠正，甚至会出现乱纠的现象。
采用纠错后，误码性能的改善？
由于纠错码种类很多，纠错能力各不相同，译码方法也不同，因此其性能必须根据具体分析和计算。
BSC & AWGN
BSC
– 如果纠正 t 个随机错误，则
AWGN
– BPSK
