RS纠错编码原理及其实现方法.pdf
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←la为本原多项式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由此可以得到域的所有元素元素二进制对应十进制对应码值000000101000a+100l⊥0110a(a+1)=a+a(mod p(a))12a(a+a=a+a(mod p(a)1011a(a+l(modula))+a+1)10C(a+1=a+a(mod p(a )a(a23+a)a+I(mod p(a)1110a(a+a+D=aa+a(modp(a)tatI(mod p(a))11a(a3+a2+a+1)=a34a2+1(modp(a)1001a(a+a+1=a+l(mod p(a)a(a+1=l(mod(a))由此可以看岀本原多项式是求解域的全部元素的关键。读者也许会有这样的疑问我们如何得到p(x)呢?本原多城式p(x)的特性是2+得到的余式等于0O(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,信息码元长度为9GF(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 =- rsgenpolyN 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+x11P[m+1]={1,0,0,0,0,0,0,1}(m=12)/*1+x+x4+x6+x12P[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,P2Pm表示第个信息码,P表示第j个校验码各个校验码可从下列线性方程组求得hm+h2m2+…+n+1B1+012+0h2m1+2m2+…+h2m+0p1p20hmn+h,2m2+…+hm+O+0+…+1p,=0式中h;是常数校验方程组可写成校验矩阵100h21h2…,h2k010h000该矩阵具有r行和n列故式(1-1)可以写成c=0或c=08Zhengzhou Oriole Xinda Electronic Information Cc., LtdH矩阵称为[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、100000)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)x3、RS码的校验多项式由于生成多项式g(x)是x-1的因式g(rh(g(x)为n-k次多项式,则h(x)为k次多项式,k3x+g)hx+…+x+4)由右式可以看出x"1,x2,x的系数均等于0即gg0010h1+g1bo=0g0h+g1h11+…+8nkh2(2k)=0∴.+n-kk-10n-kk式中g0+81h1+…+8nkh1(n=k)(表示X的系数10
- 2020-12-08下载
- 积分：1
高能物理分析软件ROOT的入门使用方法
root是cern开发的数据分析软件，根据cern官网的A ROOT Guide For Beginners英文版翻译的中文文档，适合初学者了解root软件的使用723存储任意类型的 N-tuples…724处理跨文件的 n-tuple7.2.5对进阶用户:使用送择器即本处理树…547.2.6对干进阶价用户:使用 PROOF lite进行多核处理72.7关于 N-tuples的优化8 ROOT in python:::::::::::t·::::··:598. 1 PYROOT598.1. 1 More Python-less C++8.2自定义代码:从C+到 Python9结束语…64References64摘要ROOT是一个用于数据分析和I/O的软件框架:一个强大的工只,可以应对最先进的科学数据分析的典型任务。它的突出特点包括高级图形用户界面,非常适合交互式分析,C++编程语言的解释器,快速高效的原型设计和C艹+对象的持久性杋制,还用于写入大型强了对撞机实验记录的每年PB级数据(1PB=1024TB译者注)。本入门指南说明了ROOT的主要特征,这些特征与数据分析的典型问题相关:输入和绘制测量数据和分析功能的拟合。原创作者-D. Piparo-G. Quast-M,cisc译者注:本文均是 Google翻译结果,仅对代码和板式作调整,欢迎修改分享软件背景与简介欢迎来到数据分析ROOT!测量与理论模型的比较是实验物理学中的标准仟务之一。在最简单的情况下,“模型”只是提供测量数据预测的函数。通常,模垩取决于参数。这种模型可以简单地表示“电流I与电压U成比例”,并且实验者的任务包括从一组测量中确定电阻R作为第一步,需要数据的可视化。接下来,通常必须应用一些操作,例如,校正或参数转换。通常,这些操作是复杂的,并且应该提供强大的数学函数和程序库-例如,考虑应用于输入光谱的积分或峰值搜索或傅立叶变换以获得模型描述的实际测量偵。实验物理学的一个特点是影响每个测量的不可避免的不确定性,可视化工具必须包括这些。在随后的分析中,必须正确处理错误的统计性质作为最后一步,将测量值与模型进行比较,并且需要在此过程中确定自由模型参数。有关适合数据点的函数(模型)的示例,请参见图1.1。有儿种标准方法可供使用,数据分析工具应能方便地访问其中一种以上。还必须提供量化测量和模型之间一致性水平的方法。通常,要分析的数据量很大-考虑借助计算机累积的细粒度测量。因此,可用工具必须包含易于使用且有效的方法来存储和处理数据在量子力学中,模型通常仅根据许多参数预测测量的概率密度函数(“pdf),并且实验分析的目的是从观察到的频率分布中提取参数,其中观察测量。这种测量需要生成和可视化频率分布的装置,所谓的直方图和严格的统计处理,以从纯粹的统计分布中提取模型参数。预期数据的模拟是数据分析的另一个重要方面。通过重复生成“伪数据”,其以与用于真实数据的预期相同的方式进行分析,可以验证或比较分析过程。在许多情况卜,测量误差的分布并不是精确已知的,并且模拟提供了测试不同假设的景响的可能性。满足上述所有要求的强大软件框架是ROOT,这是个由日内瓦欧洲核了研究中心欧洲核研究组织协调的开源项目ROOT非常灵活,既可以在自己的应用程序中使用编程接口,也可以提供用于交互式数据分析的图腦用户界面。木文档的目的是作为初学者指南,并根据学生实验室中解决的典型问题为您自己的用例提供可扩展的示例。本指南有望为您未来科学工作中更复杂的应用奠定基础,建立在现代,最先进的数据分析上具之上本指南以教程的形式向您介绍ROOT包。根据“边做边学”的原则,这个目标将通过具体的例子来完成。也正因为这个原因,本指南无法涵盖ROOT包的所有复杂性。然而,一日您对以卜章节中介绍的概念有信心,您将能够欣赏ROOT用户指南( The Root Users guide2015)并浏览类参考(根参考指南2013)以査找所有详细信息您可能会感兴。您甚至可以查看代码本身,因为ROOT是一个免费的开源广品。与本教程并行使用这些文档!ROOT数据分析框架本身是编写的,并且在很大程度上依赖于C++编程语言:需要些关于C++的知识。如果您不了解这种语言的含义,Js可以利用有关C++的大量文献。ROOT可用于许多平台( Linux, Mac osx, Windows….),但在本指南中我们将隐含地假设您使用的是 Linux。你需要做的第一件事就是安装ROOT,不是吗?获取最新的ROOT版本非常简单。只需在此网页htp:/ root, cern.ch/ downloading-root上寻找“专业版”。您将找到针对不同体系结构的预编译版木,或者您自凵编译的ROOT源代码。只需拿起您需要的味道并按照安装说明操作即可。让我们深入了解ROOT!ROOT基础既然你凵经安装了ROOT,那么你止在运行的这个交互式 shell是什么?就像这样:ROOT带来了双重功能。它有一个宏的解释器(Cing( What is Cling”2015)),您可以从命令行运行或像应用程序一样运行。但它也是一个可以评估任意语句和表达式的交互式 shell这对于调试,快速黑客攻击和测试非常有用。我们先来看一些非常简单的例子2.1ROOT作为计算器您甚至可以使用ROOT交互式she代替计算器!使用该命令启动ROOT交互式shelroot在你的Liux机器上。提示应该很快出现:root「8让我们来看看这里显示的步骤root [0] 1+1(int)2root[1]2*(4+2)/12(doub1e)1.0000root [2] sqrt(3.( double)1.732051root[3]1>2(bool) falseroot [4] TMath: Pi()( double)3.141593root [5] TMath: Erf( 2)( double).222703不错。您可以看到,ROOT不仅可以输入C++语句,还可以输入存在于 MAth命名空间中的高级数学函数。现在让我们做一些更详尽的事情。一个众所周知的几何系列的数字小例root [6 double X=5(double)0.500000root [7] int N=30(int)30root [8] double geom series=0(doub1e)8.099root [9] for (int i=0; i
- 2020-06-28下载
- 积分：1
