2014级通信专业《纠错码原理》考试题(开卷)
姓名: 学号: 分数:
第一题:根据以为根的本原多项式为x6+x+1
(1) 构造扩域GF(26)
(2) 分解因式x63-1和x21-1
(3) 构造可纠2个错误的二进制BCH码
(4) 构造可纠2个错误的RS码
第二题:采用计算机编程仿真比较相同码率的RS码与卷积码在AWGN下的性能。其中,RS码为(23,11)格雷码的扩展码(24,12)码,卷积码为参数(2,1,2)的卷积码,其编码电路如图所示
第一题
根据以为根的本原多项式为
1.构造扩域
已知,,即,由这个等式,可构造扩域:
得到扩域的元素表如下:
幂表示 | 6维向量表示 | 幂表示 | 6维向量表示 |
0 | 000000 | | 010010 |
1 | 100000 | | 001001 |
| 010000 | | 110100 |
| 001000 | | 011010 |
| 000100 | | 001101 |
| 000010 | | 110110 |
| 000001 | | 011011 |
| 110000 | | 111101 |
| 011000 | | 101110 |
| 001100 | | 010111 |
| 000110 | | 111011 |
| 000011 | | 101101 |
| 110001 | | 100110 |
| 101000 | | 010011 |
| 010100 | | 111001 |
| 001010 | | 101100 |
| 000101 | | 010110 |
| 110010 | | 001011 |
| 011001 | | 110101 |
| 111100 | | 101010 |
| 011110 | | 010101 |
| 001111 | | 111010 |
| 110111 | | 011101 |
| 101011 | | 111110 |
| 100101 | | 011111 |
| 100010 | | 111111 |
| 010001 | | 101111 |
| 111000 | | 100111 |
| 011100 | | 100011 |
| 001110 | | 100001 |
| 000111 | | 1 |
| 110011 | | |
| 101001 | | |
| 100100 | | |
| | | |
2.分解因式和
由共轭根系概念,将除0、1以上元素划分,同属一个根系的元素为一组:
分别求取每组共轭根系的最小多项式,化简得:
所以,因式分解结果为
(2.2) 分解因式x21-1
x21-1中n=21,且不到一个整数m使等式n=2m-1成立,因此需要寻非原元。
由于,所以令,由共轭根系概念划分:
分别求取每组共轭根系的最小多项式,化简得:
所以,因式分解结果为
3.构造可纠2个错误的二进制BCH码
定理5:码长为、纠t个错误的二进制BCH码的生成多项式
由题可知,是的本原元,且,码长
查表可知,、的最小多项式分别为:
,
由定理5,可得码长63,可纠2个错误的二进制BCH码的生成多项式:
因此,
所以,该码是一种的(63,51)本原BCH码,也叫循环码。
4.构造可纠2个错误的RS码
RS码的定义:令是的本原元。符号取自、纠t个错误的RS码,其生成多
项式以为其全部的根。
则,上本原元,本原多项式,纠2个错误的RS码生成多项 式的根为:四个连续根。
因此,,
化简得:
所以,该码是一种的(63,59)RS码。
第二题
1.卷积码原理
一个简单的数字通信系统都包括信源、信源编码、信道编码、调制、解调、信道译码、信源译码、信宿几个基本部分。如图1所示: 图1 简单数字通信系统
其中,信源产生作为通信的消息,信源编码的目的是把信源产生的消息转化为二进制形式的符号,并去除消息中的冗余,保证通信的有效性。信道编码则是增加一些冗余使得消息序列在信道中传输时,具有一定的抗干扰性及纠错能力,保证通信的可靠性。调制的作用是把纠错码送出的信息序列通过调制器变换成适合于信道传输的信号。信号经调制后会送入信道进行传输,这期间就会受到各种噪声的干扰,变成失真信号送到解调器进行解调。解调出来的二进制信息序列中可能已有错误,经过信道译码器即纠错码译码器,对其中的错误进行纠正,最后经过信源译码器恢复成原来的消息传给用户。 2.卷积码原理
卷积码是1955年由爱里斯(Hias)提出的。它的特点是编码器有记忆,且在任意给定时间单元内,编码器的输出不仅取决于该时刻的输入,也依赖于一定数量的以前的输入。一个存储级数为m的码率为的卷积码编码器,可以用输入存储为m的输入、输出线性时序电路实现;换言之,输入在进入编码器后还在其中额外驻留了 m个时间单元。通常,和是小的整数, <,信息序列被分成长度为的分组,码字被分成长为的分组。 2.1卷积码编码
卷积码是由连续输入的信息序列得到连续输出的已编码序列。以(2,1,2)卷积码编码器为例,为编码器输入数据的位数,为编码器输出数据的位数,为约束长度(或移位寄存器的级数),码率是衡量传输信息有效性的一个重要指标。
卷积码的编码器分成两种类别:前馈和反馈。本次课程设计采用前馈类型。结构图如图2所示:
图2 (2,1,2)卷积码编码器结构图
为更好表现编码器状态转移和时间的关系,引入篱笆或网格图(Trellis),如图3所示:
图3 (2,1,2)卷积码L=5网格图
如图3所示,网格图中每一个状态由两个输入和两个输出分支。在某一时间单位(节点)i,离开每一状态的虚线分支表示输入编码器中的信息子组;而实线分支表示此时刻输入至编码器的信息子组;每一分支上的2(n)个数字表示第i时刻编码器输出的子组,因而网格图中的每一条路径都对应于不同输入的信息序列。由于所有可能输入的信息序列共有个,因而网格图中可能有的路径也有条,相应于个长为的不同码序列。例如,输入至图中编码器的信息序列,则由编码器输出的码序列,它相应于网格图中用粗线表示的一条路径。
2.2 Viterbi译码
1967年,维特比(Viterbi)提出Viterbi算法。
Viterbi译码算法是一种基于序列的最大似然译码算法,得到了很广泛的应用。假设信道输出序列R,译码器输出序列C,所有可能的码字,若一个译码器的译码规则能在个码字C中选择某一个使得最大,则这种译码规则称为最大似然译码,称为似然函数。若发送每个码字相同,且由于与译码方法无关,则由贝叶斯公式:
得
由于与是单调关系,因此上两式可以写为:
称为对数似然函数或似然函数。
信息序列经编码器编码之后,编码器送出码序列C,经过DMC(离散无记忆信道)传输后,送入译码器的序列是R=C+E,其中E是信道错误序列或信道噪声。译码器根据接受序列R,按最大似然译码准则出编码器在网格图上走过的路径,这个过程就是译码器计算、寻最大似然函数的过程。
2.3 (2,1,2)卷积码Matlab仿真
%%%%%%%%%%%%%%%%%%%
% (2,1,2)卷积码编码
trel = poly2trellis(3,[7,5]);
vertcode = convenc(msg,trel);
%%%%%%%%%%%%%%%%%%%
% 维特比译码程序:
function Decoder = Viterbi(ConCode,Length)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%该函数实现维特比译码
%%%%ConCode为待译的卷积码
%%%%Length为原始序列的长度
%%%%Decoder为译码后所得码字
%%%%S0->00,S1->10,S2->01,S3->11
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
RecSeq = ConCode;
Decoder = zeros(1,Length); %存储维特比译码后的码字
D = zeros(1,4); %记录到达某一状态时的累计汉明距离
DTemp = D;
RouteS0 = zeros(1,2*Length); %记录到达S0状态所经过的路径
RouteS1 = zeros(1,2*Length); %记录到达S1状态所经过的路径
RouteS2 = zeros(1,2*Length); %记录到达S2状态所经过的路径
RouteS3 = zeros(1,2*Length); %记录到达S3状态所经过的路径 = zeros(1,2*Length);