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
Concepts in Programming Languages.pdf
Concepts in Programming Languages by John Mitchell.一本国外经典教材,看了之后对编程语言更加理解。费了很多劲才找到的。Concepts in Programming LanguagesThis textbook for undergraduate and beginning graduate students explains and examines the central concepts used in modern programminglanguages, such as functions, types, memory management, and controlThe book is unique in its comprehensive presentation and comparisonof major object-oriented programming languages. Separate chapters ex-amine the history of objects, Simula and Smalltalk, and the prominentanguages c++ and JavaThe author presents foundational topics, such as lambda calculus anddenotational semantics, in an easy-to-read, informal style, focusing on themain insights provided by these theories. Advanced topics include concurrency and concurrent object-oriented programming. A chapter on logicprogramming illustrates the importance of specialized programming meth-ods for certain kinds of problemsThis book will give the reader a better understanding of the issuesand trade-offs that arise in programming language design and a betterappreciation of the advantages and pitfalls of the programming languagesthey useJohn C. mitchell is Professor of Computer Science at Stanford University,where he has been a popular teacher for more than a decade. Many of hisformer students are successful in research and private industry. He received his ph D. from mit in 1984 and was a member of technical staff atat&T Bell Laboratories before joining the faculty at Stanford. Over thepast twenty years, Mitchell has been a featured speaker at internationalconferences; has led research projects on a variety of topics, includingprogramming language design and analysis, computer security, and applications of mathematical logic to computer science; and has written morethan 100 research articles. His previous textbook, Foundations for Pro-gramming Languages(MIT Press, 1996), covers lambda calculus, typesystems, logic for program verification, and mathematical semantics ofprogramming languages. Professor Mitchell was a member of the programming language subcommittee of the ACM/ieEE Curriculum 2001standardization effort and the 2002 Program Chair of the aCm principlesof programming languages conferenceCONCEPTS NPROGRAMMINGLANGUAGESJohn c. mitchellStanford UniversityCAMBRIDGEUNIVERSITY PRESSPUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGEThe Pitt Building, Trumpington Street, Cambridge, United KingdomCAMBRIDGE UNIVERSITY PRESSThe Edinburgh Building, Cambridge CB2 2RU, UK40 West 20th Street, New York, NY 10011-4211 USA477 Williamstown Road, Port Melbourne vic 3207, AustraliaRuiz de alarcon 13, 28014 Madrid, spainDock House, The Waterfront, Cape Town 8001, South Africahttp://www.cambridge.orgo Cambridge university press 2004First published in printed format 2002isBN 0-511-03492-X eBook(adobe readerISBN 0-521-78098-5 hardbackContentsPrefacepage IxPart 1 functions and foundations1 Introduction1.1 Programming Languages1.2 Goals1.3 Programming Language History3561.4 Organization: Concepts and Languages2 Computability2. 1 Partial Functions and computability102.2 Chapter SummaryExercises163 Lisp: Functions, Recursion, and Lists3.1 Lisp History183.2 Good Language design203. 3 Brief Language overview223.4 Innovations in the Design of Lisp253.5 Chapter Summary: Contributions of LispExercises404 Fundamentals484.1 Compilers and syntax484.2 Lambda calculus4.3 Denotational semantics4.4 Functional and Imperative Languages4.5 Chapter SummaryExercisesContentsPart 2 Procedures, Types, Memory Management, and Control5 The algol Family and ML5.1 The Algol Family of Programming Languages5.2 The Development of C5.3 The LCF System and ml5.4 The Ml Programming Language1035.5 Chapter summary121Exercises1226 Type Systems and Type Inference1296.1 Types in Programming1296.2 Type Safety and Type Checking1326.3 Type Inference1356.4 Polymorphism and Overloadin1456.5 Type Declarations and Type Equality1516.6 Chapter Summary155Exercises1567 Scope, Functions, and storage Management1627.1 Block-Structured Languages1627.2 In-Line blocks1657.3 Functions and procedures1707.4 Higher-Order functions1827.5 Chapter summary190Exercises1918 Control in Sequential Languages2048.1 Structured control2048.2 Exceptions2078.3 Continuations2188.4 Functions and evaluation order2238.5 Chapter summary227Exercises8Part 3 Modularity, Abstraction, and object-Oriented Programming9 Data Abstraction and Modularity2359.1 Structured Programming2359.2 Language Support for Abstraction2429.3 Modules9.4 Generic Abstractions2599.5 Chapter Summary269Exercises27110 Concepts in Object-Oriented Languages27710.1 Object-Oriented design27710.2 Four Basic concepts in object-Oriented languages278Contents10.3 Program Structure28810.4 Design Patterns29010.5 Chapter summary29210.6 Looking Forward: Simula, SmalltalkC++Java293Exercises29411 History of objects: Simula and smalltalk30011.1 Origin of Objects in Simula30011.2 Objects in Simula30311.3 Subclasses and Subtypes in Simula30811.4 Development of smalltalk31011.5 Smalltalk Language features31211.6 Smalltalk flexibilit31811.7 Relationship between Subtyping andInheritance2211.8 Chapter SummaryExercises32712 objects and Run-Time Efficiency: C++33712.1 Design goals and Constraints33712.2 Overview of c++34012.3 Classes. Inheritance and Virtual functions34612.4 Subtyping35512.5 Multiple inheritance12.6 Chapter summary366Exercises36713 Portability and Safety: Java38413.1 Java language overview38613.2 Java Classes and Inheritance38913.3 Java Types and Subtyping39613.4 Java System architecture40413.5 Security Features41213.6 Java summary417Exercises420Part 4 Concurrency and Logic Programming14 Concurrent and Distributed Programming43114.1 Basic Concepts in Concurrency43314.2 The actor model44114.3 Concurrent ML14.4 Java concurrency45414.5 Chapter Summary466Exercises469Contents15 The Logic Programming Paradigm and Prolog47515. 1 History of logic Programming15.2 Brief Overview of the logic Programming Paradigm4715. 3 Equations solved by Unification as Atomic Actions15.4 Clauses as Parts of procedure declarations48215.5 Prologs Approach to Programming48615.6 Arithmetic in Prolog49215.7 Control, Ambivalent Syntax, and Meta-Variables49615.8 Assessment of Prolog50515.9 Bibliographic remarks50715.10 Chapter Summary507Appendix a Additional Program Examples509A 1 Procedural and Object-Oriented organization509Glossary521Index525
- 2020-12-09下载
- 积分:1