循环码编码.docx - 冰点文库

资源描述

循环码编码.docx

《循环码编码.docx》由会员分享，可在线阅读，更多相关《循环码编码.docx（28页珍藏版）》请在冰点文库上搜索。

循环码编码.docx

循环码编码

摘要

本报告详细给出了循环码的定义以及由生成多项式求解生成矩阵和系统生成矩阵的过程，并在Matlab环境下写出了循环码的编码器和解码器代码，实现了编码和译码功能。

在计算机通信信息码中循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码。

它有许多特殊的代数性质，它使计算机通信以一种以数据通信形式出现，实现了在计算机与计算机之间或计算机与终端设备之间进行有效的与正确地信息传递，它使得现代通信的可靠性与有效性实现了质的飞跃循环码还有易于实现的特点，很容易用带反馈的移位寄存器实现其硬件。

关键字：

循环码；编码；译码；Matlab。

前言

在通信软件中大多数采用循环码进行数据差错控制。

了解循环码的数学原理,掌握硬件实现电路,运用简单快速的软件方法,对于各种通信软件编程员（包括单片机、系统机）有很高的实用价值。

在计算机通信信息码中循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码。

它有许多特殊的代数性质，它使计算机通信以一种以数据通信形式出现，实现了在计算机与计算机之间或计算机与终端设备之间进行有效的与正确地信息传递，它使得现代通信的可靠性与有效性实现了质的飞跃。

一循环码概念及其编译码原理介绍

1.1线性生成码

1.1.1线性生成码的原理

线性分组码的构成方式是把信息序列分成每k个码元一段，并由这k个码元按一定规则产生r个校验位，组成长度为n=k+r的码字，用（n,k）表示信息码元与校验位之间为线性关系。

一个[n,k]线性分组码，是把从信源输出的以k个码元为一组的信息组m，通过信道编码器后，变成长度为n≥k的码组（码字）c作为[n,k]线性分组码的一个码字。

设GF（q）是一个含有q个元素的有限数域，若每位码元的取值有q种（取自GF（q）），则信息组m共有

种不同的状态，因此，需要

个码字c。

而长为n的数组共有

个，二进制时（q=2）共有

个。

显然，

个n维向量组成有限域GF（q）上的一个n维线性空间V，编码就是要在这个n维线性空间中选出

个向量作为合法码字，其余的

个向量为禁用码字。

如果选出的

个作为合法码字的向量的集合构成了V的一个k维线性子空间，则称它是一个q进制[n,k]线性分组码。

如果值取自GF（q）上的[n,k]分组码的

个码字的集合C，便构成了有限域GF（q）上的n维线性空间V的一个k维线性子空间，则称C是一个q进制[n,k]线性分组码。

1.1.2生成矩阵和校验矩阵

生成矩阵：

G称为生成矩阵，因为可以用它产生整个码组A，即有

生成矩阵的性质：

具有[IkQ]形式的生成矩阵称为典型生成矩阵。

由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。

这种形式的码组称为系统码。

矩阵G的各行也必须是线性无关的。

如果已有k个线性无关的码组，则可以将其用来作为生成矩阵G，并由它生成其余码组。

监督矩阵：

监督矩阵可用来校验和纠错。

1.2（n,k）循环码

1.2.1（n,k）循环码概念

在实际应用中，数据传输一般采用系统码的编码方式，即在发送的信息序列之后附加上特定位数序列的冗余位，该冗余位称为所发送的信息序列的监督位。

监督位一般是由所发送的信息序列经过恰当的变化而产生。

若监督位由信息序列经过线性组合得到，则称得到的系统码为线性分组码。

循环码是线性分组码的一个重要子类，具有严密的代数学理论。

循环码“线性”是指任意两个循环码模2相加所得的新码仍为循环码。

循环码具有线性码的一般性质（即封闭性．指一种线性分组码的任意两个码组之和仍是该分组码的另一个码组）外，还具有循环性，即循环码中任一码组循环一位（将最右端码元移至左端，或反之）以后，仍为该码组中的一个码组。

（n，k）循环码表示其中信息位为k，监督位为n-k位。

若一个循环码的所有码字多项式都是一个次数最低的非零首一多项式g（x）的倍式，则g（x）生成该码，并称g（x）为该码的生成元或生成多项式。

若在GF

（2）上的（n，k）循环码中，存在唯一的n-k次首一多项式

使得每一个码多项式c（x）都是g（x）的倍式，且每一低于或等于n-1次的g（x）的倍式，一定是码多项式。

（n，k）循环码的生成多项式g（x）一定是

的因式：

；反之，若g（x）为n-k次，且除尽

，则此g（x）一定生成一个（n，k）循环码。

对于一般的（n，k）循环码，设其生成多项式为

，由于

、

…

等k个码多项式必线性无关，故可用它们组成码的一组基底，而与这些码多项式相对应的k个线性无关的码向量就构成除生成矩阵G，即

G（x）=

若g（x）是（n，k）循环码的生成多项式，有

，h（x）是k次多项式，称为校验多项式。

令

，则

为（n-k）xn阶矩阵，称为码的校验矩阵。

可以证明，

。

1.2.2循环码编码原理

有信息码构成信息多项式

，其中最高幂次为k-1；

用

乘以信息多项式m（x），得到的

，最高幂次为n-1，该过程相当于把信息码（

，

，……，

，

）移位到了码字德前k个信息位，其后是r个全为零的监督位；

用g（x）除

得到余式r（x）,其次数必小于g（x）的次数，即小于（n-k），将此r（x）加于信息位后做监督位，即将r（x）于

相加，得到的多项式必为一码多项式。

根据上面的讨论，可得到在（7，4）循环码编码的程序框图如图1所示：

图2.2.1编码程序框图

1.2.3循环码纠错原理

纠错码的译码是该编码能否得到实际应用的关键所在。

译码器往往比编码较难实现，对于纠错能力强的纠错码更复杂。

根据不同的纠错或检错目的，循环码译码器可分为用于纠错目的和用于检错目的的循环码译码器。

　　通常，将接收到的循环码组进行除法运算，如果除尽，则说明正确传输；如果未除尽，则在寄存器中的内容就是错误图样，根据错误图样可以确定一种逻辑，来确定差错的位置，从而达到纠错的目的。

用于纠错目的的循环码的译码算法比较复杂，感兴趣的话可以参考一些参考书。

而用于检错目的循环码，一般使用ARQ通信方式。

检测过程也是将接受到的码组进行除法运算，如果除尽，则说明传输无误；如果未除尽，则表明传输出现差错，要求发送端重发。

用于这种目的的循环码经常被成为循环冗余校验码，即CRC校验码。

CRC校验码由于编码电路、检错电路简单且易于实现，因此得到广泛的应用。

在通过MODEM传输文件的协议如ZMODEM、XMODEM协议中均用到了CRC校验技术。

在磁盘、光盘介质存储技术中也使用该方法。

当码字c通过噪声信道传送时，会受到干扰而产生错误。

如果信道产生的错误图样是e，译码器收到的n重接受矢量是y,则表示为：

（1-1）

上式也可以写成多项式形式：

（1-2）

译码器的任务就是从y（x）中得到

，然后求的估值码字

（1-3）

并从中得到信息组

。

循环码译码可按以下三个步骤进行：

（1）有接收到的y（x）计算伴随式s（x）;

（2）根据伴随式s（x）找出对应的估值错误图样

；

（3）计算

，得到估计码字

。

若

则译码正确，否则，若

，则译码错误。

由于g（x）的次数为n-k次，g（x）除E（x）后得余式（即伴随式）的最高次数为n-k-1次，故S（x）共有2n-k个可能的表达式，每一个表达式对应一个错误格式。

可以知道（7,4）循环码的S（x）共有2（7-4）=8个可能的表达式，可根据错误图样表来纠正（7,4）循环码中的一位错误，其伴随式如表1所示。

BCH（7，4）循环码错误图样表：

错误图样

错误图样码字

伴随式S（x）

伴随式

E6（x）=x6

1000000

100

E5（x）=x5

0100000

x2+x

110

E4（x）=x4

0010000

x2+x+1

111

E3（x）=x3

0001000

x+1

011

E2（x）=x2

0000100

x2+1

101

E1（x）=x1

0000010

010

E0（x）=x0

0000001

001

E（x）=0

0000000

000

表1BCH（7，4）循环码错误图样表

上式指出了系统循环码的译码方法：

将收到的码字R（x）用g（x）去除，如果除尽则无错；否则有错。

如果有错，可由余式S（x）一一找出对应图样，然后将错误图样E（x）与R（x）模2和，即为所求码字C（x），从而实现纠错目的。

根据前面的讨论，可得（7，4）循环码译码的程序框图如图2.3.1所示：

1.2.4编码过程及实现

在编码时，首先需要根据给定循环码的参数确定生成多项式g（x），也就是从

的因子中选一个（n-k）次多项式作为g（x）；然后，利用循环码的编码特点，即所有循环码多项式A（x）都可以被g（x）整除，来定义生成多项式g（x）。

根据上述原理可以得到一个较简单的系统：

设要产生（n,k）循环码，m（x）表示信息多项式，循环码编码方法则其次数必小于k，而

·m（x）的次数必小于n，用

·m（x）除以g（x），可得余数r（x），r（x）的次数必小于（n-k），将r（x）加到信息位后作监督位，就得到了系统循环码。

下面就将以上各步处理加以解释：

（1）用

乘m（x）。

这一运算实际上是把信息码后附加上（n-k）个“0”。

例如，信息码为110，它相当于m（x）＝

+x。

当n-k＝7-3＝4时，

·m（x）＝

，它相当于1100000。

而希望的到得系统循环码多项式应当是A（x）=

·m（x）+r（x）。

（2）求r（x）。

由于循环码多项式A（x）都可以被g（x）整除，也就是：

（1-4）

因此，用

·m（x）除以g（x），就得到商Q（x）和余式r（x），即

（1-5）

这样就得到了r（x）。

（3）编码输出系统循环码多项式A（x）为：

（1-6）

1.2.5译码过程及实现

对于接收端译码的要求通常有两个：

检错与纠错。

达到检错目的的译码十分简单，可以由式

（1），通过判断接收到的码组多项式B（x）是否能被生成多项式g（x）整除作为依据。

当传输中未发生错误时，也就是接收的码组与发送的码组相同，即A（x）=B（x），则接收的码组B（x）必能被g（x）整除；若传输中发生了错误，则A（x）≠B（x），B（x）不能被g（x）整除。

因此，可以根据余项是否为零来判断码组中有无错码。

设发射的码字为C（x），而收到的码字为R（x），如果C（x）=R（x），则说明收到码字正确。

如果C（x）≠R（x），则说明收到的码字出现错误，即为：

R（x）=C（x）+E（x）。

……

（1）

公式

（1）中E（x）称为错误图样。

当E（x）=0时，则无错误。

用g（x）去除R（x），因为C（x）是由g（x）生成的，故C（x）必能为g（x）除尽，显然，R（x）与E（x）为同余式（R（x）≡E（x）modg（x）），以g（x）除E（x）所得余式称之为伴随式S（x）。

由公式

（1）可知，R（x）⋅

=（C（x）+E（x））⋅H（x）=E（x）⋅H（x）。

若E（x）=0，则E（x）⋅H（x）=0；若E（x）≠0，则H（x）≠0。

这说明，R（x）⋅

仅与错误图样有关，而与发送的码字无关，由此可以确定错误图样表。

由于g（x）的次数为n−k次，g（x）除E（x）后得余式（即伴随式）的最高次数为n−k−1次，故S（x）共有

个可能的表达式，每一个表达式对应一个错误格式。

可以知道（7，4）循环码的S（x）共有

=8个可能的表达式，可根据错误图样表来纠正（7，4）循环码中的一位错误，其伴随式如表1所示。

表1BCH（7，4）循环码错误图样表

错误图样

错误图样码字

伴随式S（x）

伴随式

1000000

100

0100000

110

0010000

111

0001000

011

0000100

101

0000010

010

0000001

001

0000000

000

上式指出了系统循环码的译码方法：

将收到的码字R（x）用g（x）去除，如果除尽则无错；否则有错。

如果有错，可由余式S（x）一一找出对应图样，然后将错误图样E（x）与R（x）模2和，即为所求码字C（x），从而实现纠错目的。

需要指出的是，有错码的接收码组也有可能被g（x）整除，这时的错码就不能检出了。

这种错误被称为不可检错误，不可检错误中的错码数必将超过这种编码的检错能力。

在接收端为纠错而采用的译码方法自然比检错要复杂许多，因此，对纠错码的研究大都集中在译码算法上。

我们知道，校正子与错误图样之间存在某种对应关系。

如同其它线性分组码，循环编码和译码可以分三步进行：

（1）由接收到的码多项式B（x）计算校正子（伴随式）多项式S（x）；

（2）由校正子S（x）确定错误图样E（x）；

（3）将错误图样E（x）与B（x）相加，纠正错误。

上述第

（1）步运算和检错译码类似，也就是求解B（x）整除g（x）的余式，第（3）步也很简单。

因此，纠错码译码器的复杂性主要取决于译码过程的第

（2）步。

二、（15,7）循环码程序设计

本设计分为三个模块：

（15,7）循环码编码仿真模块、（15,7）循环码译码仿真模块、（15,7）循环码误码性能分析模块

2.1（15,7）循环码编码仿真模块

按照循环码的编码原理设计流程图如下

图2-1（15,7）循环码编码程序流程图

2.2（15,7）循环码译码仿真模块

可得（15，7）循环码译码的程序框图如图2.3.1所示：

否

图2-2（15,7）循环码译码程序流程图

2.3高斯信道下（15,7）循环码的误码性能

图2-3（15,7）循环码在高斯信道下的误码性能

三、设计与仿真

3.1（15,7）循环码的编码

在循环码编码模块的程序中，主要是根据一个输入的消息矢量从而产生（15，7）循环码编码后的序列。

（1）输入矢量为[1100110]时的编码输出序列如下图所示：

图3-1（15,7）循环码的编码程序仿真结果图

（1）

（2）输入矢量为[1110000]时的编码输出序列如下图所示：

图3-2（15,7）循环码的编码程序仿真结果图

（2）

由上图可看出，本程序实现了对任意输入消息进行（15,7）循环码的编码。

3.3（15,7）循环码的译码

在MATLAB环境下实现对任意码的编码

（1）将3.2中编出的码字输入译码程序中可得

图3-3（15,7）循环码的译码程序仿真结果图

由上图可以看出，用编出的码字译码，没有错误，正确译出原码。

验证了译码程序的正确性。

（2）将3.2中编出的码字改变一位作为译码程序的输入，译码程序仿真输出为中可得

图3-4（15,7）循环码的纠一位错程序仿真结果图

由上图可以看出本程序可以正确纠正一位错码。

3.4（15,7）循环码在高斯信道下的误码性能

图3-5信源产生的序列及无噪输出序列

图3-6循环码在不同信噪比下的误码率分析

总结

分析和讨论了此码发现错误、纠正错误的能力。

通过分析查阅（n，k）循环码的编码方法，在MATLAB环境下设计了对（15,7）循环码编译码方法的仿真，首先设计了对任意（15，7）循环码的编译码，然后使一个经过（15，7）循环码编码的信号序列通过高斯信道，再对译码后的序列进行误码分析。

通过本次课程设计，我掌握了（15,7）循环码的编译码方法，并求出该码的最小码距及纠检错能力，通过观察该码通过高斯信道后的仿真结果，并参考其他编码方法，可发现循环码纠检错能力较强并且比较易用。

参考文献

[1]曾凡鑫.现代编码技术.西安：

西安电子科技大学出版社,2007；33-42

[2]樊昌信.通信原理.北京市：

国防工业出版社，2009；79-83

[3]李鹏.计算机通信技术及其程序设计.西安:

西安电子科技大学出版社，1999.6；67-73

[4]徐明远，邵玉斌MATLAB仿真在通信与电子工程中的应用.西安：

西安电子科技大学学出版社，2005.6；126

[5]曹志刚等著，现代通信原理，北京：

清华大学出版社，2001.5。

：

65-78

[6]吴伟陵等著，移动通信原理，北京：

电子工业出版社，2005：

30-57

[7].李建新，现代通信系统分析与仿真-MATLAB通信工具箱，西安：

西安电子科技大学出版社，2000：

13-45

[8]唐向宏，岳恒立，郑雪峰MATLAB及在电子信息类课程中的应用（第二版）.北京：

电子工业出版社，2009.6；240-249

附录

源程序代码如下

1.（15,7）循环码的编码

clear;

clc;

a=input（'请输入消息矢量：

'）;

%高次项系数在前的生成多项式

Gx=[100010111];

%将数组a的高位依次放在数组Data的低位

Data=zeros（1,15）;

Data

（1）=a（7）;

Data

（2）=a（6）;

Data（3）=a（5）;

Data（4）=a（4）;

Data（5）=a（3）;

Data（6）=a

（2）;

Data（7）=a

（1）;

%Data除以Gx得到余数Rx

[Qx,Rx]=deconv（Data,Gx）;

b=Rx+Data;

%将数组b的高位放在后面

c=b

（1）;

（1）=b（15）;

b（15）=c;

c=b

（2）;

（2）=b（14）;

b（14）=c;

c=b（3）;

b（3）=b（13）;

b（13）=c;

c=b（4）;

b（4）=b（12）;

b（12）=c;

c=b（5）;

b（5）=b（11）;

b（11）=c;

c=b（6）;

b（6）=b（10）;

b（10）=c;

c=b（7）;

b（7）=b（9）;

b（9）=c;

%将数组b校正

fori=1:

ifrem（abs（b（i））,2）==0

b（i）=0;end

end

fori=1:

ifrem（abs（b（i））,2）==1

b（i）=1;end

end

disp（'输入序列：

'）;

disp（'编码输出序列：

'）;

2．（15,7）循环码的编码

clear;

clc;

r=[101001001110000];

h=[1,0,0,0,0,0,0,0;1,1,0,0,0,0,0,0;0,1,1,0,0,0,0,0;1,0,1,1,0,0,0,0;0,1,0,1,1,0,0,0;0,0,1,0,1,1,0,0;0,0,0,1,0,1,1,0;1,0,0,0,1,0,1,1;0,1,0,0,0,1,0,1;0,0,1,0,0,0,1,0;0,0,0,1,0,0,0,1;0,0,0,0,1,0,0,0;0,0,0,0,0,1,0,0;0,0,0,0,0,0,1,0;0,0,0,0,0,0,0,1];

b=flipud（h）;

s=r*b;

fori=1:

ifrem（abs（s（i））,2）==0

s（i）=0;end

end

fori=1:

ifrem（abs（s（i））,2）==1

s（i）=1;end

end

ifs==[00000000]

e=[000000000000000];

elseifs==[10000000]

e=[000000000000001];

elseifs==[1,1,0,0,0,0,0,0]

e=[000000000000010];

elseifs==[0,1,1,0,0,0,0,0]

e=[000000000000100];

elseifs==[1,0,1,1,0,0,0,0]

e=[000000000001000];

elseifs==[0,1,0,1,1,0,0,0]

e=[000000000010000];

elseifs==[0,0,1,0,1,1,0,0]

e=[000000000100000];

elseifs==[0,0,0,1,0,1,1,0]

e=[000000001000000];

elseifs==[1,0,0,0,1,0,1,1]

e=[000000010000000];

elseifs==[0,1,0,0,0,1,0,1]

e=[000000100000000];

elseifs==[0,0,1,0,0,0,1,0]

e=[000001000000000];

elseifs==[0,0,0,1,0,0,0,1]

e=[000010000000000];

elseifs==[0,0,0,0,1,0,0,0]

e=[000100000000000];

elseifs==[0,0,0,0,0,1,0,0]

e=[001000000000000];

elseifs==[0,0,0,0,0,0,1,0]

e=[010000000000000];

elses==[0,0,0,0,0,0,0,1]

e=[100000000000000];

end

u=r+e;

fori=1:

ifrem（abs（u（i））,2）==0

u（i）=0;end

end

fori=1:

ifrem（abs（u（i））,2）==1

u（i）=1;end

end

Data=zeros（1,7）;

Data

（1）=u（9）;

Data

（2）=u（10）;

Data（3）=u（11）;

Data（4）=u（12）;

Data（5）=u（13）;

Data（6）=u（14）;

Data（7）=u（15）;

ife==[000000000000000]

disp（'没有错误：

'）

k=0,else

disp（'第几位错误：

'）

k=find（e）

;end

disp（'接收码字'）

disp（'译码输出序列：

'）

Data

3．循环码编码与解码Matlab源程序

展开阅读全文