实例介绍
【实例简介】
RS纠错编码原理及其实现方法。
Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 前言 随着越来越多的系统采用数字技术来实现,纠错编码技术也得到了越来越广 泛的应用。RS码既可以纠正随机错误,又可以纠正突发错误,具有很强的纠错 能力,在通信系统中应用广泛。近些年来,随着软件无线电技术的发展,RS编 码、译码一般都在通用的硬件平台上实现。通常采用基于FPGA的ⅦHDL编码 硬件实现,或者在DSP、单片机上用C和汇编编程软件实现。 RS纠错编码涉及的领域很广,特别是设计到很多数学知识。这对那些对数 学不太感冒的工程技术人员来书是个不小的挑战。尽管讲RS编码的书籍很多 但是那些书都是采用循序渐进,逐步引人的方式从汉明码到循环码,从循环码 到BCH码,BCH码再引入悶S码。对亍工程技术人员他们需要的是简明扼要的讲 解,和详细的实现方法。 本人写这篇文章的宗旨就是尽量最简单的语言最简短的篇幅来讲RS纠 错编码原理,把重点来放在实现方法上。 为了便于读者仿真,本文采样MLAB程序实现,程序尽量符合硬件C语言 写法,读者经过简单修改即可应用到工程中去。 本文读者对象 本文是为那些初识瑙编码的学生、工程技术人员而写,并不适合做理论研 究,如果你是纠错编码方面的学者、专家,那么本文并不适合你。 由于作者水平有限,错误在所难免,恳请读者批评指正。 不得更改 陈文礼 2008-01于郑州 Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 必备的一些代数知识 1、在纠错编码代数中,把以二进制数字表示的一个数据系列看成一个多项式。例如二进制 数字序列1010111,可以表示成: M(x)=ax+a5x0+a5不 5+a+4 TasK +ax+a,x+ank 式中的x表示代码的位置,或某个二进制数位的位置,X前面的系数表示码的 值。若a;是一位二进制代码,则取值是0或1。dM()称为信息代码多项式 多项式次数 称系数不为0的x的最高次数为多项式/(x)的次数,记为Of(x) 2、域 域在R编码理论中起着至关重要的作用。 简单点说域GF(2)有2设2个符号[0,n,a2…22 且具有以下性质 域中的每个元素都可以用a",a,a2,om的和来表示。a←l a为本原多项式p(x)的根。 运算规则有: 在纠错编码运算过程中,加减、乘和除的运算是在伽罗华域中进行。现以 GF(2)域中运算为例: 加法例:a+a=0010+0110101(模2加法相当于0005与011或 减法运算与加法相同 乘法例:a·a0=a (8+10)modl5 除法例:cs/a0=a-2=a-2+5=a 不理解没关系,下面的例子也许对你有帮助。 例:mF=4,p(x)=x4+x+1求GF(2")的所有元素 因为a为p(x)的根得到a4+a+1=0或a4=a+1(根据运算规则) Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 由此可以得到域的所有元素 元素 二进制对应十进制对应 码 值 0000 0010 1000 a+1 00l⊥ 0110 a(a+1)=a+a(mod p(a)) 12 a(a+a=a+a(mod p(a) 1011 a( a+l(modula)) +a+1) 10 C (a+1=a+a(mod p(a ) a(a23+a) a+I(mod p(a) 1110 a(a+a+D=aa+a(modp(a) tatI(mod p(a)) 11 a(a3+a2+a+1)=a34a2+1(modp(a) 1001 a(a+a+1=a+l(mod p(a) a(a+1=l(mod(a)) 由此可以看岀本原多项式是求解域的全部元素的关键。读者也许会有这样的疑问 我们如何得到p(x)呢?本原多城式p(x)的特性是2+ 得到的余式等于0 O(X 由于作者也是工程技术人员,具体怎么得到p(x),也没有深究过。 Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 作者在设计RS编码时候都是根据 MATLAB指令rsgeηpoly来得到p(x)。 其格式为 rsgenpoly(n,k) 参数n为码长一般n=2"-1,k为信息码元个数。 例如m4,码长n=15,信息码元长度为9 GF(2)的本原多项式可以根据指令 >>rsgenpoly(15, 9) 得到 ans= GF(2 4)array. Primitive polynomial =D 4+D+1 (19 decimal) 有读者来信问:我要做一个(158的RS编码,在 MATLAB中输入 命令 rsgenpoly(158,128),结果MAB报错 Error using =- rsgenpoly N must equal 2m-1 for some integer m 这里做一下解释我们S编码时普先要根据码长选取mλ选择原则是 2 若码长为6那么我们可以选择n=8, rsgenpey命令的第少个参数必须为 2"-1,第二个参数司以随便选择只要小于2”-1就形了 在此给出m∈(2,16)的所有本原多项式 (m=2) P[m+1]={1,1,1} /米1+x+x3*/ P[m+1]-{1,1,0,1} /米1+x+x4*/ P[m11]={1,1,0,0,1} /米1+x2+x5*/ P|m+1={1,0,1,0,0,1}; Zhengzhou Oriole Xinda Electronic Information Cc., Ltd (m=6) /米1+x+x6*/ P[m+1]={1,1,0,0,0,0,1} 7) /来1+x3+x7* P[m+1]={1,0,0,1,0,0,0,1} (m=8) /米14x2+x31x4+x8*/ P[m+1]-{1,0,1,1,1,0,0,0,1 /*1+x4+x9半 P[m1]={1,0,0,0,1,0,0,0, (m=10) /1+x3+x10*/ P|m+1={1,0,0,1,0,0,0,0, /*1+x2+x11 P[m+1]={1, 0,0,0,0, 0,0,1} (m=12) /*1+x+x4+x6+x12 P[m+1]-{1,1,0,0,、1,0,0, (m=13) /*1+x+x^3+x4+x^13*/ P[m+1]={1,1,0,1,1,0,0, 00,0,1}; (m=14) /*1+x+x6+x10+x14来 P[m+1]={1,1,0,0,0,0,1,0,0,0,1,0,0,0,1} (m=15) /米14x+x15*/ P[m+1]={1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1}; (m=16) /*1+x+x3+x12+x16*/ P[m+1]={1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1}; Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 二、线性分组码的一些基本概念 1、线性分组码一般用(n,)或(n,k,d)表示n为码长,k为信息码元的数目,n-k为监督 码元的数目。d表示码元距离。 定义:两个码组上对应位置上数字不同的个数称为码组的距离。 发送的码字C=(1,C2C3,…C 接收的矢量r=(,2, 信道错误图样:e=c+r 例如c=(1,1,0,0,0) (1,0,001) e=(1+1,1+0,0+0,0+0,0+1)(0,1,0,0,1) 从而可以看出从左端起第2位和第5位是错误的 2、校验矩阵概念 码长为n,信息数为k,监督数为r。 这样的一组码形式为:m:m2,P,P2P m表示第个信息码,P表示第j个校验码 各个校验码可从下列线性方程组求得 hm+h2m2+…+n+1B1+012+0 h2m1+2m2+…+h2m+0p1p2 0 hmn+h,2m2+…+hm+O+0+…+1p,=0 式中h;是常数 校验方程组可写成校验矩阵 100 h21h2…,h2k010 h000 该矩阵具有r行和n列 故式(1-1)可以写成 c=0或c=0 8 Zhengzhou Oriole Xinda Electronic Information Cc., Ltd H矩阵称为[n,k,r码的校验矩阵。 发送矢量为C接收矢量为F若rH≠0 则说明接收到的码有错误。 设错误图样为e 则可写成以下关系式r=c+e 为了纠错必须知道那些位上存在错误。这可由校正子(又称伴随式)s来确定 s=rH=cH +eh=eh 译码器的主要任务就是如何从中得到最像e的错误图样e 从而译出c=r-e 设第讠个是错误的 因此e=(00..0 第个有错误 s=rH=(00…0、100 0 0 0) 00 计算出的矢量示出i是出错误的位置。 3、生成矩阵概念 生成矩阵G,它是一个k行,n列的矩阵 若已知信息组m,通过生存矩阵可求得相应的码字。 c=mxG (m是k个信息元组成的信息组) 这个应该比较容易理解,在此就不做过多解释。 、RS码的一些重要性质 1、RS码生成多项式: 码长n=2”-1,监督元数目r=n-k=2t,能纠正t个错误。 Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 定义:在(n,k,d)的RS码中,存在唯一的n-k次多项式g(x),使得每一个码多项式c(x) 都是g(x)的倍式。g(x)称为n,k,d]RS码的生成多项式 一般情况下g(x)=(x-a)(x-a2)…(x-a2) 2、定理: 在GF(2m)中,每个非0元素(1,a,a2…a22)均满足x2=1,反之x21-1=0的根必 在GF(2")中。 所以 x-1=(x-a)(x-a)x 3、RS码的校验多项式 由于生成多项式g(x)是x-1的因式 g(rh( g(x)为n-k次多项式,则h(x)为k次多项式, k 3x+g)hx+…+x+4) 由右式可以看出x"1,x2,x的系数均等于0 即gg 00 1 0h1+g1bo=0 g0h+g1h11+…+8nkh2(2k)=0 ∴.+ n-kk-1 0 n-kk 式中g0+81h1+…+8nkh1(n=k)(表示X的系数 10 【实例截图】
【核心代码】
RS纠错编码原理及其实现方法。
Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 前言 随着越来越多的系统采用数字技术来实现,纠错编码技术也得到了越来越广 泛的应用。RS码既可以纠正随机错误,又可以纠正突发错误,具有很强的纠错 能力,在通信系统中应用广泛。近些年来,随着软件无线电技术的发展,RS编 码、译码一般都在通用的硬件平台上实现。通常采用基于FPGA的ⅦHDL编码 硬件实现,或者在DSP、单片机上用C和汇编编程软件实现。 RS纠错编码涉及的领域很广,特别是设计到很多数学知识。这对那些对数 学不太感冒的工程技术人员来书是个不小的挑战。尽管讲RS编码的书籍很多 但是那些书都是采用循序渐进,逐步引人的方式从汉明码到循环码,从循环码 到BCH码,BCH码再引入悶S码。对亍工程技术人员他们需要的是简明扼要的讲 解,和详细的实现方法。 本人写这篇文章的宗旨就是尽量最简单的语言最简短的篇幅来讲RS纠 错编码原理,把重点来放在实现方法上。 为了便于读者仿真,本文采样MLAB程序实现,程序尽量符合硬件C语言 写法,读者经过简单修改即可应用到工程中去。 本文读者对象 本文是为那些初识瑙编码的学生、工程技术人员而写,并不适合做理论研 究,如果你是纠错编码方面的学者、专家,那么本文并不适合你。 由于作者水平有限,错误在所难免,恳请读者批评指正。 不得更改 陈文礼 2008-01于郑州 Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 必备的一些代数知识 1、在纠错编码代数中,把以二进制数字表示的一个数据系列看成一个多项式。例如二进制 数字序列1010111,可以表示成: M(x)=ax+a5x0+a5不 5+a+4 TasK +ax+a,x+ank 式中的x表示代码的位置,或某个二进制数位的位置,X前面的系数表示码的 值。若a;是一位二进制代码,则取值是0或1。dM()称为信息代码多项式 多项式次数 称系数不为0的x的最高次数为多项式/(x)的次数,记为Of(x) 2、域 域在R编码理论中起着至关重要的作用。 简单点说域GF(2)有2设2个符号[0,n,a2…22 且具有以下性质 域中的每个元素都可以用a",a,a2,om的和来表示。a←l a为本原多项式p(x)的根。 运算规则有: 在纠错编码运算过程中,加减、乘和除的运算是在伽罗华域中进行。现以 GF(2)域中运算为例: 加法例:a+a=0010+0110101(模2加法相当于0005与011或 减法运算与加法相同 乘法例:a·a0=a (8+10)modl5 除法例:cs/a0=a-2=a-2+5=a 不理解没关系,下面的例子也许对你有帮助。 例:mF=4,p(x)=x4+x+1求GF(2")的所有元素 因为a为p(x)的根得到a4+a+1=0或a4=a+1(根据运算规则) Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 由此可以得到域的所有元素 元素 二进制对应十进制对应 码 值 0000 0010 1000 a+1 00l⊥ 0110 a(a+1)=a+a(mod p(a)) 12 a(a+a=a+a(mod p(a) 1011 a( a+l(modula)) +a+1) 10 C (a+1=a+a(mod p(a ) a(a23+a) a+I(mod p(a) 1110 a(a+a+D=aa+a(modp(a) tatI(mod p(a)) 11 a(a3+a2+a+1)=a34a2+1(modp(a) 1001 a(a+a+1=a+l(mod p(a) a(a+1=l(mod(a)) 由此可以看岀本原多项式是求解域的全部元素的关键。读者也许会有这样的疑问 我们如何得到p(x)呢?本原多城式p(x)的特性是2+ 得到的余式等于0 O(X 由于作者也是工程技术人员,具体怎么得到p(x),也没有深究过。 Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 作者在设计RS编码时候都是根据 MATLAB指令rsgeηpoly来得到p(x)。 其格式为 rsgenpoly(n,k) 参数n为码长一般n=2"-1,k为信息码元个数。 例如m4,码长n=15,信息码元长度为9 GF(2)的本原多项式可以根据指令 >>rsgenpoly(15, 9) 得到 ans= GF(2 4)array. Primitive polynomial =D 4+D+1 (19 decimal) 有读者来信问:我要做一个(158的RS编码,在 MATLAB中输入 命令 rsgenpoly(158,128),结果MAB报错 Error using =- rsgenpoly N must equal 2m-1 for some integer m 这里做一下解释我们S编码时普先要根据码长选取mλ选择原则是 2 若码长为6那么我们可以选择n=8, rsgenpey命令的第少个参数必须为 2"-1,第二个参数司以随便选择只要小于2”-1就形了 在此给出m∈(2,16)的所有本原多项式 (m=2) P[m+1]={1,1,1} /米1+x+x3*/ P[m+1]-{1,1,0,1} /米1+x+x4*/ P[m11]={1,1,0,0,1} /米1+x2+x5*/ P|m+1={1,0,1,0,0,1}; Zhengzhou Oriole Xinda Electronic Information Cc., Ltd (m=6) /米1+x+x6*/ P[m+1]={1,1,0,0,0,0,1} 7) /来1+x3+x7* P[m+1]={1,0,0,1,0,0,0,1} (m=8) /米14x2+x31x4+x8*/ P[m+1]-{1,0,1,1,1,0,0,0,1 /*1+x4+x9半 P[m1]={1,0,0,0,1,0,0,0, (m=10) /1+x3+x10*/ P|m+1={1,0,0,1,0,0,0,0, /*1+x2+x11 P[m+1]={1, 0,0,0,0, 0,0,1} (m=12) /*1+x+x4+x6+x12 P[m+1]-{1,1,0,0,、1,0,0, (m=13) /*1+x+x^3+x4+x^13*/ P[m+1]={1,1,0,1,1,0,0, 00,0,1}; (m=14) /*1+x+x6+x10+x14来 P[m+1]={1,1,0,0,0,0,1,0,0,0,1,0,0,0,1} (m=15) /米14x+x15*/ P[m+1]={1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1}; (m=16) /*1+x+x3+x12+x16*/ P[m+1]={1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1}; Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 二、线性分组码的一些基本概念 1、线性分组码一般用(n,)或(n,k,d)表示n为码长,k为信息码元的数目,n-k为监督 码元的数目。d表示码元距离。 定义:两个码组上对应位置上数字不同的个数称为码组的距离。 发送的码字C=(1,C2C3,…C 接收的矢量r=(,2, 信道错误图样:e=c+r 例如c=(1,1,0,0,0) (1,0,001) e=(1+1,1+0,0+0,0+0,0+1)(0,1,0,0,1) 从而可以看出从左端起第2位和第5位是错误的 2、校验矩阵概念 码长为n,信息数为k,监督数为r。 这样的一组码形式为:m:m2,P,P2P m表示第个信息码,P表示第j个校验码 各个校验码可从下列线性方程组求得 hm+h2m2+…+n+1B1+012+0 h2m1+2m2+…+h2m+0p1p2 0 hmn+h,2m2+…+hm+O+0+…+1p,=0 式中h;是常数 校验方程组可写成校验矩阵 100 h21h2…,h2k010 h000 该矩阵具有r行和n列 故式(1-1)可以写成 c=0或c=0 8 Zhengzhou Oriole Xinda Electronic Information Cc., Ltd H矩阵称为[n,k,r码的校验矩阵。 发送矢量为C接收矢量为F若rH≠0 则说明接收到的码有错误。 设错误图样为e 则可写成以下关系式r=c+e 为了纠错必须知道那些位上存在错误。这可由校正子(又称伴随式)s来确定 s=rH=cH +eh=eh 译码器的主要任务就是如何从中得到最像e的错误图样e 从而译出c=r-e 设第讠个是错误的 因此e=(00..0 第个有错误 s=rH=(00…0、100 0 0 0) 00 计算出的矢量示出i是出错误的位置。 3、生成矩阵概念 生成矩阵G,它是一个k行,n列的矩阵 若已知信息组m,通过生存矩阵可求得相应的码字。 c=mxG (m是k个信息元组成的信息组) 这个应该比较容易理解,在此就不做过多解释。 、RS码的一些重要性质 1、RS码生成多项式: 码长n=2”-1,监督元数目r=n-k=2t,能纠正t个错误。 Zhengzhou Oriole Xinda Electronic Information Cc., Ltd 定义:在(n,k,d)的RS码中,存在唯一的n-k次多项式g(x),使得每一个码多项式c(x) 都是g(x)的倍式。g(x)称为n,k,d]RS码的生成多项式 一般情况下g(x)=(x-a)(x-a2)…(x-a2) 2、定理: 在GF(2m)中,每个非0元素(1,a,a2…a22)均满足x2=1,反之x21-1=0的根必 在GF(2")中。 所以 x-1=(x-a)(x-a)x 3、RS码的校验多项式 由于生成多项式g(x)是x-1的因式 g(rh( g(x)为n-k次多项式,则h(x)为k次多项式, k 3x+g)hx+…+x+4) 由右式可以看出x"1,x2,x的系数均等于0 即gg 00 1 0h1+g1bo=0 g0h+g1h11+…+8nkh2(2k)=0 ∴.+ n-kk-1 0 n-kk 式中g0+81h1+…+8nkh1(n=k)(表示X的系数 10 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论