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
计算机辅助几何造型技术_莫蓉
计算机辅助几何造型技术，莫蓉等编写，各大高校相关专业推荐书目。21世纪高等院校教材计算机辅助几何造型技术莫蓉吴英常智勇编著学实撤社北京内容简介计算机辅助几何造型技术是复杂曲面设计射基本技术,它所依赖的数学基础是微分几何。4书较全面介绍了计算机辅助几何造型玻术的基础知识,包括:曲线曲面论的基本知识烊条曲线与曲面、贝齐尔曲线与曲画、B样条曲线与曲面均匀有理B样条(NRRS曲线与曲画曲线曲面求交算法线曲光顺等本书是面向高等学校非数学类专业的本科生教材如机械T程及泊动化航空宇航设计与制造等也叮供高等学校师生及有关工程技术人员自学参考图书在版编目C)费据计算机辅助几何造犁技术莫蓉,昊英,常勇编著.一北京:科学出版社,2004.2(2世纪高等院校教材IsBN7030119266·计…Ⅱ.①奠…型吳…③常…Ⅲ.计箅机雜助设计Ⅳ.TP391.72中国版本图书馆CIP数据核字(20)第072140号责任編辋:钟谊段博原/文棄編軿:璐贾瑞娜仼校对:朱光光!贲任印制;安春生/封面设计:陈敬學桌訟出版北京乐域城恨北街6号邮哎:l0?17hitP/www.sciencep.com肀剩厂印刷科学击版社发行各地新华书经销2004乍2月第版开4:B5(720×100〕24年2月第次印印张:103印堂:12500字最20000定价:18.00元〔如有印装质量问题,我社负责调换〈新欣前&计箅机辅助几何造型技术》是计算机辅助设计与计算机辋助制造的基础课程,在机被、航空、航夭、船舶、汽车、家电制造等行业均有广泛的用途。计算机铺助几何造型技术是用数学理论描述自由曲线和出面的一种有效方法,它是计算机设计复杂曲面的算法基础,也是三维数字化技术的基础之一。目前國内、国际流行的著名大型 CAD CAM集成软件都使用了先进的几何造型曲面方法。本书主耍内容分为7章。第-章介绍曲线曲面论的基本知识,读者可以从中了解矢量代数基础,曲线曲面的基础,直纹面和可展曲面。第二章重点讲述样条龉线与ns曲面,包括三次样条函数、参数样条曲线、 rergusoll曲线和孔斯曲面,并且給出应用例子第三章讲述最常用的贝齐尔曲线与曲面,主要包括:贝齐尔曲线的定义与性质、贝齐尔曲线的儿何作图泫、贝齐尔曲线的合成、贝齐尔曲线的升阶和降阶、贝齐尔曲愿、贝齐尔曲面的合战、贝齐尔曲线曲的应用。第四章讲述B样条曲线和曲面基础,包括B样条曲线的定义与性质、三次均匀B样条曲线、三次均匀B祥条曲线的插值、双三次B样条曲面B样条曲面的应用。第五章讲述非均勻有理B样条由线与出面,介經非均匀B样条曲线与曲面的定义、性质和配套技术。笫六章介终由面求交的常用算法,包括曲面求交的分类与基本方法,分割算法、迭代法、追踪法。第七章介绍曲线面光顺,包括曲线出面光为的基本概念、曲线光顺方法和曲酉光顺方法,主要是各种算法的原理和步骤。每一章均附有习题可供读者练习时使用。作为非数学类本科生教材,本书省略了大量的数学推导和证明,考患到目前曲线和曲面技术的广泛应用,以讲解基木理论和基本概念为主,希望学生在使用本教树后,熊够对计算机辅助几何造型技术有一个较为深入地了解,对当前流行的CAD软件中曲线曲面造型的功能不仅知其然而豆知其所以然。《计算机助几何造型技术》课程学时约为5~颀0学时,其中有“*"的章节可作为选修内容本书由莫蓉三編兵中第一章、第二章、第四章由吴英编写,第三章由莫蓉编写,第五章、第六章、第十章常智男编写本书承蒙孙文焕教授主审,孙教投在审阅过程中为本节提出了许多宝贵意见;另外本教村能得以较快正式出版与科学出版社及西北工业大学教务处、数材科的大力支持是分不开的:在此一并向他们表示衷心的感谢。由于作者水平有限,书中的错误不妥之处在所难免,敬请读者不吝指正,作者将不陛慼激编者2004年1月目录前言第一章曲线曲面的基本知识…1.1矢量代数基硝1.1.1矢量b·■平q『即■甲曾即·甲曾■血中■『自■qq『·中鲁暂_普·自中·番平血·1.1,2直线的矢量方程■·冒■卜T■■p口q1.⊥3平面的矢量方程d口■■■直■■■■啁■幽1.2曲线论I2.1曲线的矢量力程和参数方41.2.2矢函数的导矢及其应用山41.3曲线的自然参数方程1.3,1自然参数方程………1.3,2出线论的基本公式………1.4率和挠率14.田率■■L晶■■142挠率…………141.5曲面………1.5,1曲面矢量方程和参数方程1.5.2曲画上的曲线及其切矢和曲面上法矢181.5.3曲面的等距面方程…中■■血■血■2016直纹面和可展曲面…………21b.1直纹面冒曾■12162可展曲网「-·F·-r4-幽4"ts.Hv:P44423习题血日t·自日q·1日甲·4日4·4A4·h由44■·鄂h·〓"=即·甲画24第二章样条曲线与Cons曲面…日血平亠·甲甲■■甲『4量晋P1■■山……·251基本概念■■■山山■252.t.1插值与通近……■中■■b■…………2522多项式基…2522三次样条函数及其力学背景……………………………262.3三次样条函数272.3.1定义……………………………………………………2723.2用型值点处的一阶导数表示插值三次样条曲线——m关系式272.3.3用型值点处的阶导数表示播值三次样条曲线M关系式23.4求解插值三次样条曲线的步骤235三次样条曲线局限性■■會會會■冒鲁鲁■個■口鲁■■…3524参数样条曲线噜■甲擊■擊甲P普甲冒241参数样条曲线24.2累加弦长参数样条解决“大挠度”的问题d“卜Bd血卜‘申372.4.3端点条件的换算■bψψ司ψ1ψ甲自■嚼■■■卡■普■■■↓4普昌b■4▲▲山▲244参数样条曲线的计算步骤…………■看hhd_4晶hd画鼻号·t甲平Pqv冒ppP冒q4ppb■自4392.5 fergus∞n曲线T"會會■會■血■會『血■『■甲m甲···日日日4·日日··日·血‘争甲甲甲日P蚤平号B蚤■425.1 Fergus参数曲线表达形式2.5.2 Ferguson曲线妄的拼接甲甲甲即日4-郾412.6Cxns曲面r會鲁■■個幽■幽『■■■4看■■■■↓卜■■■阝}画4226.1曲面表示法与记号……………432.6.2具有给定边界的 Coons曲面……4426.3真有给定边界和跨昇切矢的Cs曲面片…4864具有给定边其跨界切矢、跨界快率的Cxm曲面…50265双二次CUns曲面2.7三种定义曲面的基本方法532.7.l笛卡儿乘积法……幽血■■■■■L画晶』晶532.7.2母线法…5327.3布尔和法……………54习题甲甲q■上鲁■凸“■■■聊啁第三章贝齐尔曲縱与曲面…563.1贝齐尔曲线的定义与性质…备备+■■■■■■血幽■幽即聊聊↓着着昌昌晶……·56311贝齐尔曲线的定义暑■■1『h■D·■p血56312贝齐尔曲线的几何性质583.2贝齐尔曲线的几何作图法T冒■■■■■■623.2,1贝齐尔曲线的几何作图法322厌齐尔曲线的递归分割算法…633.3贝齐尔线的合成……··+--71.44即q443.31连线条件号拼接曲线的光滑度33.2贝齐尔曲线的合成及连续条件……65贝齐水曲线拼接的应用举例673,1贝齐尔曲线的升阶与降阶■bd幽■■号甲q■db4.贝齐尔曲线的不足…6834.2齐尔曲线的升阶与降阶……………!"683.5贝齐尔面■d■■■b■■■■國■703.5.1双三次贝齐尔曲面…·…s……"…s""!"703.5.2贝齐尔曲面的性质7236贝齐尔曲面的合成…LvP■平73361位置连续…甲日4日·即·日4···日4·日·日4··4‘P···日‘·‘·即47336.2界斜率连续………743.6.3只齐尔曲线曲应用………T6习题■甲P甲q77第四章B样条曲线和曲面■『T?冒■■冒■··『『+ TPTPTYP1■794.1B样条基函数的递推定义及其性质…794.1.1B样条基的递推定义4.1.2B样条基的推导过程804.13B样条基的性质4.2H样条曲线…■■矗画凸d………"…"…………834.2.1B样条曲线的定义…,……4.2.2B样条曲线性质………………844.2.3B样条曲线的分类p+·4-rb-T·"·"hr·血·÷4*"4t844.3均匀B样条曲线…r甲『■4■■■I·中·日+·口4日日■44卜A亠854.3.1三次均匀B样条画线表达形式…854.3,2二三次均每B样条曲线的几何性质…874.33特征顶点对曲线形状的影响4.3.4三次均匀B咩条曲线的算法…………………94.3,5二次均匀B样条曲线上qP■■kb山■■▲d“pp43.6三次参数曲线段的比较…924.4非均匀B样条曲线934.4.lB样条曲线的定义域……………934.2重节点对B样条基的影响44.3重节点对B样条由线的影响……954.5B样条曲面……T會會自■■■1_■■I■『■聊■;pp4.51双三次B样条出面片4.5.2双三次B样条曲面的方程…………………1014.53B样条曲面及其性质4.5,4三次均匀H样条曲面的算法…102习题甲■郾·■■■d■4■画甲b▲q"甲即·““4·画…………104第五章非均匀有理样条曲线与曲面·1065.1NRRS曲线的定义和性质……1075.1.]曲线方程的三种等价表示……1071.2NUR曲线三种去示方式的特点……5.1.3NJR曲线的儿何性质甲q4■4=q■唱司甲d■中即甲■■唱看■甲5.t4杈囚子对NRHS曲线形状的影响■郾■■■■dbdbd平qPFb【鲁5.1.5圆锥曲线泊表示■_曾甲晶_L■昌甲…………∷…………11252NURs曲面的定义和性质……5.2.1 NURBS曲面方程的三种表示方法■■·晶b晶郾d■山b■522NRHS曲面的性质………q;甲中}P■1175.2.3曲而权因子的几何意义冒TP口『■冒………117524常用曲面的NURB表示……鱼■中p口■■唱山■中52.5 NURES曲面的形状修收…………………………………………1205.3 NURBS曲线曲面的配套技术………………………1205.3.1 NURES曲线曲面求值、求导1甲■司司bb11205.32NRBS出线曲面拟合………125冒口』■■■……∵……132第六章曲面求交算法1336.1曲面求交的分类与基本方法国P■曾冒甲冒■■冒會■■罪■■■■■1336.1.1曲面求交的分类……………1336.12出面求交的基本力法………1336.2分割算法1356.2.1分割算法的本原理………1356.2.2分割算法的注意问题…1356.3迭代法…h■■m■■■·南Dp■d·13763,1迭代法的基本原理b甲。聊略甲4▲dL13763.2鑫数迭代法a日日·自甲『是4■普晋画■4■138633四参数迭代法4需意的间题…■■日■■■■平■『■TT曾■T■■■■……1406、4追踪法6.4.l追踪法基木过程…··日.甲·卜B山如如L当";a4-st上416.4.2 Lattice网格求交法…·"自■■■『■着■■■▲h■■■44←pp·4426.4.3迫踪法中的其他内容….…!143习题144第七章曲线曲面光顺1457.曲线曲面光顺的基本概念甲■■卩■1457.1}光顺的基木概念…■■↓■bdb|v甲甲nP■145?.1.2光顺性准划146
- 2021-05-06下载
- 积分：1
