[数学]信息论与编码原理_第9章_循环码

智能信息技术导论 - 循环码一、概述循环码是一种在通信领域中广泛使用的编码方式。

它通过在数据中添加冗余位来实现错误检测和纠正的功能。

循环码在数字通信系统、计算机网络、存储系统等领域都有着重要的应用，是保障数据传输可靠性的重要技术手段之一。

二、循环码的原理循环码是一种线性块码，通过在数据位后面添加一系列的冗余位（也称为校验位）来构成编码后的数据。

冗余位的计算方式使循环码的编码、译码实现起来非常高效。

2.1 循环码的生成多项式循环码最重要的参数是生成多项式，它决定了编码和译码的方式。

生成多项式是一个不可分解的多项式，用于生成校验位。

在循环码中，校验位是通过数据位和生成多项式的模2乘法来计算得到的。

2.2 循环码的编码循环码的编码过程实际上就是将数据位和生成多项式进行一系列模2乘法的计算，并将结果作为校验位添加到数据位后面。

编码过程可以通过移位寄存器的方式实现，其中移位寄存器的初始状态为全0。

2.3 循环码的译码循环码的译码过程主要是通过计算接收到的编码数据位和生成多项式的模2除法来还原数据位。

译码过程中，接收到的编码数据位会与寄存器中的状态进行模2除法的计算，得到的结果会作为冗余位进行错误检测。

三、循环码的性质循环码具有许多重要性质，这些性质使得循环码在实际应用中具有较好的性能。

3.1 线性性质循环码满足线性性质，即两个编码字的异或结果仍然是一个有效的编码字。

这种性质使得循环码可以方便地进行编码和译码操作。

3.2 最小距离性质循环码的最小距离决定了它所能检测和纠正的错误的能力。

最小距离越大，循环码的纠错能力越强。

在设计循环码时，需要考虑到数据传输过程中可能出现的各种错误类型，以便选择合适的生成多项式和编码长度。

3.3 循环码的循环性循环码具有循环性，即将一个编码字进行循环移位后所得到的码字仍然是一个有效的编码字。

该性质使得循环码在传输过程中可以通过循环移位将错误传播到多个位上，从而提高错误的检测和纠正的能力。

Shannon理论讨论了信息的度量，以及对于信息表 示和传输的基本限制。Shannon的信道编码定理表 明只要信息传输速率小于信道容量，则信息传输可 以以任何小的错误概率进行。但是Shannon并没有 告诉人们如何去实现这一点。Hamming提出的纠错 编码理论却正是为了试图解决这个问题。
7
在通信中信源编码、信道编码与数据转换编码常常是同时使用的。
任何一位错误。
接收到序 列
译出序列
显然表中的译码方法不能同时 检测出二位错误。因为如果发生 二位错误，则译码器会错误的
000
0
001
0
把它作为一位错误而“纠正”了 所以r=2的重复码可以发现 二位错误或者纠正一位错误，
0
0
但二者不能兼得。
011
1
100
0
101
1
110
1
30
例2。如果用r=3的重复编码。该编码器实现 “0” “0000” ， “1” “1111”
12
13
其中分组码又可分循环码和非循环码： 循环码——该码书的特点是，若将其全部码字分成 若干组，则每组中任一码字中码元循环移位后仍是这 组的码字。 非循环码——任一码字中码元的循环移位后不一定 再是该码书中的码字 。 按照纠正错误类型可分为纠正随机错误码、纠正突发 错误码、纠正随机与突发错误码以及纠正同步错误码 等。
26
汉明重量
27
检错与纠错：
信道编码提供了对于信息传输发生差错的 控制能力。这种控制能力由编码器的纠错 能力与检错能力来表征。检错是指当信息 在信道上传输发生错误时，译码器能发现 传输有误，并及时的告诉接受者；而纠错 则是译码器能自动纠正这个错误的能力。 下面以重复码为例说明编码的纠错和检错 能力。

28
9.5 循环码 9.5.1 循环码原理
• 循环码是一种重要的线性分组码,易于实 现,性能较好.
• 循环码除具有线性码的一般性质外,还具 有循环性,即循环码中任一码组循环一位 以后,仍为该码中的一个码组.
• 一长为n的码组可表示成码多项式
T (x) a xn1 a xn2 a x a
n1
（2）改写为：
a6
a2
a 1
a0
=
1 1 1
1 1 0
1 0 1
0 1
a5
a4
1 a3
21
或
1 1 1
a 2
a 1
a 0
a 6
a 5
a 4
a 1
3 1
1 0
0 1
0 1 1
a6 a5 a4 a3 Q
Q PT k r阶 G IkQ 生成矩阵
a 6
a 5
a 4
a 3
11
1P 0
01
0 1 1
1 0 0
0
1Ir
0
0
a 4
0
a 3
a 2
1
a 1
=
0 0
20
a 0
简记为 HAT 0T 或 AH T 0
• H称为监督矩阵，H确定，则编码时监督 位和信息位的关系就完全确定了。
P为r × k 阶 Ir为 r × r 阶单位方阵
具有[ P Ir ]形式的H矩阵称为典型阵。
nk
nk 1
0
在循环码中，除全0码外，再没有连续k 位均为“0”的码组，即连“0”的长度 最多只能k-1位。因此g（x）必须是一个 常数项不为“0”的n-k次多项式
32

⎧
监督矩阵H
c = (c6 , c5 , c4 , c3, c2 , c1,
c3 = u2 ⊕ u0 = c6 ⊕ c4
c0
)
u =
= (u2 , (c6 , c5
u1, u0 , c4 )
)
⎪⎪ ⎨
c
2
⎪ c1
= =
u2 u2
⊕ u1 ⊕ u1
⊕ u0 = c6 = c6 ⊕ c5
⊕
c5
⊕
c4
⎪⎩ c0 = u1 ⊕ u 0 = c5 ⊕ c4
,n
⎥ ⎦
H和G的关系：
G的每一行及其线性组合均是(n,k)码的码组（字），可得：
监督矩阵H的重要特性：
1、由H可以建立线性分组码的线性方程组。共有n-k 行，每行代表一个线性方程的系数，表示一个监督位 的线性方程。 2、H的每行与它的分组码中的每一码字的内积为0。 3、任何一个(n,k)线性分组码的H矩阵有(n-k)行，且 每行线性无关。H=(P:I)，I的各行线性无关，可得H 的各行线性无关。 4、一个(n,k,d)线性分组码，若要纠正<=t个错误， 则其充分必要条件：H中的任何2t列线性无关，由于 最小距离d=2t+1,所以也相当于要求H矩阵中任意(d-1) 列线性无关。
奇数时称为奇校验码 偶数时称为偶校验码
偶校验码:a0⊕ a1 ⊕… ⊕ an-1=0
许用码组为000，011，101，110B
奇校验码: a0⊕ a1 ⊕… ⊕ an-1=1
许用码组为001，010，100，111B
不满足校验关系，传输一定错误！ 奇偶校验只能发现奇数个(单个)错误，不能
s=yHT=eHT –不为0时即存在错误.

111 1110100
根据定理4.3，应有 xn-1=g(x) h(x) (3-7)
如果g(x)是循环码的生成多项式，那么h(x)一定 就是循环码的校验多项式。这是因为对于任意 一个码多项式C(x)，必有
C(x)h(x)=0 mod (xn-1)
∵ C(x)h(x) = m(x)g(x) h(x) = m(x) (xn-1)是(xn-1) 的倍式，一定能被(xn-1)整除 ∴ mod (xn-1) 运算后必定为零。
mk 1 x g( x ) m1 xg( x ) m0 g( x )
x k 1 g( x ) =[mk-1 mk-2…m0] xg( x ) =[mk-1 mk-2…m0] g( x )
其中，g(x)=gn-k xn-k+…+ g1 x + g0
第四讲
三、循环码
主要内容
1、循环码的定义 2、循环码的多项式描述 3、循环码编码方法 4、循环码的译码
1957年美国人E.Prange提出循环码概念； 1961年J.E.Meggitt提出了一种译码器，主要用于检
错；
1960年前后提出了两类重要的循环码：BCH码和 RS码。 1965年E.R.Berlekamp和G.D.Forney提出了有效的
生成矩阵G的每一行是n重空间的一个基底，也是k 维n重码空间的一个基底。在一般线性分组码的生 成矩阵中，这些基底除线性无关外没有什么特殊关 系。然而从式(4-10)看到，循环码生成矩阵的k个基 底，是一个基底(gn-k … g1 g0 0 … 0)的循环移位得 出的。因此只要知道一个基底，其它(k-1)个基底可 通过循环移位得到。
循环码的(n-k)n阶的校验矩阵可写为：

29
9.2 线性分组码— 校验矩阵与生成矩阵
(3) 校验矩阵和生成矩阵的关系
由于生成矩阵G的每一行都是一个码字，所以G 的每
行都满足 HGi T 0 T，则有 HG T 0
对于标准形式的校验矩阵和监督矩阵，有
HGT Q I I P T Q +P T 0
Q PT
30
9.2 线性分组码— 校验矩阵与生成矩阵
1 0 0 1 1 1 0
c3
0c1
0c2
c3
c4 c1 0c2 c3
c5
c1
c2
c3
c6 c7
c1 c2 0c3 0c1 c2 c3
G 0 1 0 0 1 1 1 I P
0 0 1 1 1 0 1
(7,3)分组码编码表
信息组
对应码字
000
0000000
C mG
001 010
第九章：纠错编码
石东新 中国传媒大学 信息工程学院
1
一：基本概念 二：线性分组码 三：汉明码 四：循环码
2
9.1 纠错编码的基本概念—概述
香农第二定理证明，当 R C 时 PE 0 的码存在。 证明过程采用的是随机编码的方法：
随机编码所得的码集很大，通过搜索得到好码的方法在实 际上很难实现； 即使找到了好码，这种码的码字也没有规律，不便于译 码。
附加 r n k个校验码元，每个校验码元是该信
息码组的某些信息码元模2和； 这2k 个码字的集合称为 (n,k) 分组码； 编码信息率R=k/n
15
9.2 线性分组码— 概述
对二进制(n, k)线性分组码，合法码字数为2k，可用编 码空间的序列数为2n个。
任一种2k信息集合到二进制序列集合(2n)的映射都是

G k n
~
第2节 线性分组码

举例 已知(7,4)线性系统码的监督矩阵为
1 1 1 0 1 0 0 H (7,4) 0 1 1 1 0 1 0 1 1 0 1 0 0 1 可直接写出它的生成矩阵 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1
(7，4)线性码
各列都不相同，任意2列之和不等于0，2 列线性无关；某3列线性相关。所以该码的最 小距离为3，小于n-k +1＝4。
生成矩阵和校验矩阵

（n,k）线性码最小距离dmin的上边界是 n-k +1。如果我们设计的（n,k）线性码 的 d min 达到了 n-k +1 ，就是达到了设计 性能的极点。因此，dmin＝ n-k +1的码 称为极大最小距离码 (MDC – Maximized minimum Distance Code)。
G (7,4)

定理 (n,k) 线性分组码最小距离等于dmin的 充要条件是：校验矩阵H的列矢量中至少要 有dmin个才能线性相关,而任意（dmin-1)列线 性无关。 定理 (n,k) 线性分组码的最小距离必定小于 等于 (n-k+1)

dmin (n-k+1)
例：
H＝
1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1

9.1 差错控制的基本方式

混合纠错(HEC)：是FEC与ARQ方式的结合。 发端发送同时具有自动纠错和检测能力的码 组，收端收到码组后，检查差错情况，如果 差错在码的纠错能力以内，则自动进行纠正。 如果信道干扰很严重，错误很多，超过了码 的纠错能力，但能检测出来，则经反馈信道 请求发端重发这组数据。

循环码是线性分组码中一个重要的子类,具有检错纠错能力强,实现方便等特点.它具有严密的代数学理论，封闭性与循环性.（n,k）循环码表示信息位为k位，监督位为(n-k）位.本次设计实验首先分析了(7,4)循环码的编码与译码原理，然后，用C语言实现其编码与译码功能。

通过C语言平台运行所编写的程序,观察了在输入信息码情况下输出对应的编码结果以及相反的译码功能。

通过多组的对比验证了该（7，4）循环码的编译码程序的正确性。

最后,在程序运行的过程中进一步分析循环码的编译码原理，并通过比较仿真模型与理论计算的性能，证明了仿真模型的可行性。

关键词：循环码，编码与译码，C程序。

现代通信的发展趋势为数字化，随着现代通信技术的不断开发，差错控制技术已日趋成熟,在各个领域都得到了广泛的应用和认同。

本文就（7，4）循环码的编码与译码原理进行C语言的编程及运行仿真。

现代社会发展要求通信系统功能越来越强，可靠性越来越高，构成也越来越复杂；这就要借助于功能强大的计算机辅助分析设计技术和工具才能实现。

现代计算机科学技术快速发展，已经研发出了新一代的可视化的仿真软件。

这些功能强大的仿真软件，使得通信系统仿真的设计和分析过程变得相对直观和便捷，由此也使得通信系统仿真技术得到了更快的发展。

本文使用的是功能强大的C语言软件。

C语言是一种使用简便的、特别适用于科学研究和工程计算的高级语言,与其他计算机语言相比，它的特点是简洁和智能化，具有极高的编程和调试效率.通过使用C工具箱函数对数字调制进行仿真，更能直观彻底的掌握循环码的编码与译码原理。

有助于我们的学习和研究，加深对知识的理解和运用. C的便利性还体现在它的仿真结果还可以存放到的工作空间里做事后处理。

方便我们修改参数对不同情况下的输出结果进行对比。

目录第1章概述 (1)第2章计算机通信与纠错码 (2)2。

1 计算机通信技术 (2)2.1.1 通信的概念 (2)2。

1。

2 通信的发展史简介 (2)2。

性质：r(1)(X)的校正子s(1)(X)是s(X)的一次循环 移动。
也就是说码字循环位移得到新码字的校验子是 原校验子循环位移后除以生成多项式的余式，
即： s(i)(X) =Xis(X)-b(X)g(X)=ri(X)-c(X)g(X)，
s(i)(X) 的次数低于g(X)
18
译码
串行译码 每次只译一个接收比特,然后循环移位，继续译
其对偶码的生成多项式为Xkh(X-1)，也是一个
循环码 一个循环码被其校验矩阵唯一确定
13
例子
（7,4）循环码C，生成多项式g(X)=1+X+X3 其校验多项式为h(X)=Xn+1/g(X)=1+X+X2+X4 码C的对偶码的生成多项式为
X4h(X-1)=1+X2+X3+X4
14
循环码的编码
循环码和BCH码
1
简述
1957年开始研究 循环码的优点：
编码和校正子的计算容易实现 具有固定的代数结构，能找到很多实用的方法来译
码
2
循环码定义
对循右价一环做于i个移向次n位左移维，移位码得位，字到n得向-iv次到(量1)=vv((=iv)(=nv-1(0,v,vvn01-,i,…,…vn,-,viv+nn1--,21…))，做,v类一n-i似-次1)，，向等向右 循环码：一个(n,k)线性码C，若每个码字的循
从接受向量r(X)可以计算校正子s(X)，错误模 式e是未知的，故需要从s(X)去求e(X)。若e(X) 是标准阵的陪集首，则可用查表译码，由校正 子获得错误模式。
若e(X)是0，则s(X)=0；若e(X)是码多项式，则 e(X)是漏检错误模式。

信息论与编码教学课件(全)
目录
• 课程介绍与背景 • 信息论基础 • 编码理论基础 • 信道编码技术 • 数据压缩技术 • 多媒体信息编码技术 • 课程总结与展望
01
课程介绍与背景
Chapter
信息论与编码概述
信息论的基本概念
01
信息、信息量、信息熵等
编码的基本概念
02
信源编码、信道编码、加密编码等
02
极化码（Polar Codes）
一种新型信道编码方式，通过信道极化现象实现高效可靠的信息传输。
03
深度学习在信道编码中的应用
利用深度学习技术优化传统信道编码算法，提高编码性能和效率。
05
数据压缩技术
Chapter
数据压缩概述与分类
数据压缩定义
通过去除冗余信息或使用更高效的编码方式，减小数据表示所需存储空间的过 程。
线性分组码原理：线性分组码是一 种将信息序列划分为等长的组，然 后对每组信息进行线性变换得到相 应监督位的编码方式。
具有严谨的代数结构，易于分析和 设计；
具有一定的检错和纠错能力，适用 于各种通信和存储系统。
循环码原理及特点
循环码原理：循环码是一种特殊的线 性分组码，其任意两个码字循环移位
后仍为该码的码字。
03
编码理论基础
Chapter
编码的基本概念与分类
编码的基本概念
编码是将信息从一种形式或格式转换为另一种形式的过程，以 满足传输、存储或处理的需要。
编码的分类
根据编码的目的和原理，可分为信源编码、信道编码、加密编 码等。
线性分组码原理及特点
线性分组码特点
监督位与信息位之间呈线性关系， 编码和解码电路简单；

汕头大学工学院三级项目报告课程名称：信息论与编码课程题目:循环码的编码和译码程序设计指导教师：唐雅娟系别：电子工程系专业：电子信息工程学生姓名：曾煌冠学号： 09141014完成时间： 2012 年 5月4日至 5月14日成绩：评阅人：唐雅娟循环码的编码和译码程序设计一. 循环码编码和译码原理简介： 1. RS 循环码编码原理与特点：首先令22112211()...t t n t t n m x c x c x c x ----=+++和210121()...t t r x c c x c x --=+++分别表示信息多项式与校验多项式，则一个RS 码的多项式表达式为：()()()c x m x r x =+如果()c x 为一个码字，则它必须为生成多项式()g x 的位数，即：()()()c x q x g x =编码的过程就是从()m x 和()g x 中寻找()p x ，它可通过除法算法来完成。

即用()m x 除以()g x 得到：()()()()m x q x g x p x =+（1式）同时令()r x =-()p x ，则有()()()()()q x g x m x r x C x =+=。

2. RS 循环码译码原理与特点：（1） 能纠正t 个符号差错的（n ，k ）RS 码，数据段中包含k 个信息符号和2t个校验符号。

设存贮器系统数据输出的多项式（妈接收字多项式）可以表达为11()n n i n i i R x r x ---==∑，差错图样多项式为11()n n i n i i E x e x ---==∑，纠错后的码多项式为11()n n i n i i C x c x ---==∑，伴随式多项式为()S x ，差错定位多项式为()x σ。

3.RS循环码的基本步骤及实现循环码的程序流程图：Array4.主要源程序：/*输入的信息元:m(x)*/void information_element(unsigned char mx[K]) {unsigned char tem;srand((unsigned)time(0));for (unsigned int i=0;i<K;i++) {tem = rand()%6+1;if (tem == 1) mx[i] = 'a';else mx[i] = tem + 48;}}/*确定被除数：x^(n-k)m(x)*/void count_dividend(unsigned char dividend[],unsigned char mx[]) { for (int i=0;i<N;i++) {if (i>=K) { dividend[i] = '0';continue; }dividend[i] = mx[i];}}/*gx各项乘以被除数的第一项系数;注意：符号'0'的ASCII码为48*/ void for_mod2(unsigned char tem[],unsigned char c){ unsigned int i;switch (c){ case '1':for (i=0;i<5;i++) tem[i] = gx[i];break;case 'a':for(i=0;i<5;i++){if (gx[i] == '1') tem[i] = 'a';else if (gx[i] == 'a') tem[i] = '2';else tem[i] = gx[i] + 1;}break;default:for(i=0;i<5;i++){ if (gx[i] == '1') tem[i] = c;else if (gx[i] == 'a') tem[i] = (int)c + 1;else tem[i] = (int)gx[i] + (int)c - 48;}break;}/*应用课本第153页的表6-7的关系式转换*/for (i=0;i<5;i++){ if (tem[i] == '8') tem[i] = 'a';if (tem[i]>'8'&& tem[i]!='a') tem[i] -= 7;if (tem[i]=='7') tem[i] = '1';}}/*与GF（2^3）扩域(课本153页)匹配*/unsigned char math(unsigned char ctem[]){unsigned char c = '0';//当两系数相同时（即a^i+a^i=0）为0if (ctem[0]=='0'&&ctem[1]=='0'&&ctem[2]=='1') c = '1';if (ctem[0]=='0'&&ctem[1]=='1'&&ctem[2]=='0') c = 'a';if (ctem[0]=='1'&&ctem[1]=='0'&&ctem[2]=='0') c = '2';if (ctem[0]=='0'&&ctem[1]=='1'&&ctem[2]=='1') c = '3';if (ctem[0]=='1'&&ctem[1]=='1'&&ctem[2]=='0') c = '4';if (ctem[0]=='1'&&ctem[1]=='1'&&ctem[2]=='1') c = '5';if (ctem[0]=='1'&&ctem[1]=='0'&&ctem[2]=='1') c = '6';return c;}/*mod2加*/void mod2(unsigned char dividend[],unsigned char tem[],unsigned char remainder[]){ unsigned int k;for (unsigned int j=1;j<5;j++){ unsigned char tem1[3]; unsigned char tem2[3];/*被除数对应到GF（2^3）扩域，增加三位都是'0'的情况*/switch (dividend[j]){case '1':for (k=0;k<3;k++) tem1[k] = GF[0][k];break;case 'a':for (k=0;k<3;k++) tem1[k] = GF[1][k];break;case '0':for (k=0;k<3;k++) tem1[k] = '0';break;default:unsigned int n = dividend[j] - 48;for (k=0;k<3;k++) tem1[k] = GF[n][k];}/*gx各项乘以被除数的第一项系数后对应到GF（2^3）扩域，增加三位都是'0'的情况*/switch (tem[j]){case '1':for (k=0;k<3;k++) tem2[k] = GF[0][k];break;case 'a':for (k=0;k<3;k++) tem2[k] = GF[1][k];break;case '0':for (k=0;k<3;k++) tem1[k] = '0';break;default:unsigned int m = tem[j] - 48;for (k=0;k<3;k++) tem2[k] = GF[m][k];}/*异或运算*/unsigned char ctem[3];for (k=0;k<K;k++){ if (tem1[k] == tem2[k]) ctem[k] = '0';else ctem[k] = '1';}remainder[j-1] = math(ctem);/*匹配*/}}/*多项式相除*/void polynomial_division(unsigned char dividend[],unsigned char remainder[],int flag){unsigned char tem[5];unsigned int i,n=5;for (i=0;i<flag;i++){for_mod2(tem,dividend[0]);mod2(dividend,tem,remainder);/*准备下次除法的被除数，如果被除数的第一项为0则被除数数组左移一位，第一，二项都为0则停止*/for (unsigned int j=0;j<R;j++)dividend[j] = remainder[j];dividend[4] = dividend[n++];if (dividend[0] == '0'){if (dividend[1] == '0')break;for (unsigned int k=0;k<K;k++)dividend[k] = dividend[k+1];i ++;n ++;dividend[3] = '0'; }}}/*求余式*/void count_remainder(unsigned char remainder[R]){information_element(mx);unsigned char dividend[N];count_dividend(dividend,mx);polynomial_division(dividend,remainder,K);}/*RS码映射成7个二进制3bit组，对应GF表*/void create_rsc(unsigned char rsc[],unsigned char remainder[],unsigned char rsc_GF[N][K]){unsigned int i,k;for (i=0;i<3;i++){rsc[i] = mx[i]; }for (i=3;i<N;i++){rsc[i] = remainder[i-3]; }for (i=0;i<N;i++){ switch (rsc[i]){ case '1':for (k=0;k<3;k++)rsc_GF[i][k] = GF[0][k];break;case 'a':for (k=0;k<3;k++)rsc_GF[i][k] = GF[1][k];break;case '0':for (k=0;k<3;k++)rsc_GF[i][k] = '0';break;default:unsigned int m = rsc[i] - 48;for (k=0;k<3;k++)rsc_GF[i][k] = GF[m][k];}}}/*BPSK映射:符号‘1’映射成‘1’，符号‘0’映射成‘-’；注意：符号‘-’输出为‘-1’*/void BPSK_mapping(unsigned char rsc_GF[N][K],unsigned char rsc_BPSK[N][K]){ unsigned int i,j;for (i=0;i<N;i++){for (j=0;j<K;j++){if (rsc_GF[i][j] == '1')rsc_BPSK[i][j] = '1';else rsc_BPSK[i][j] = '-';if (rsc_BPSK[i][j] == '-') }}}/*加噪声干扰*/void add_noise(unsigned char rsc_BPSK[N][K]){ srand(unsigned(time(0)));unsigned int n1=1,n2=2;unsigned int m1=1,m2=1;while (1){n1 = rand()%7;n2 = rand()%7;m1 = rand()%3;m2 = rand()%3;if (n1!=n2)break;}//*//*对应的位置取反*/if (rsc_BPSK[n1][m1] == '-') rsc_BPSK[n1][m1] = '1';else rsc_BPSK[n1][m1] = '-';if (rsc_BPSK[n2][m2] == '-') rsc_BPSK[n2][m2] = '1';else rsc_BPSK[n2][m2] = '-';}/*解映射*/void de_mapping(unsigned char rsc_BPSK[N][K],unsigned char de_rsc[N]) { unsigned int i,j;for (i=0;i<N;i++){ for (j=0;j<K;j++){if (rsc_BPSK[i][j] == '-')rsc_BPSK[i][j] = '0';} de_rsc[i] = math(rsc_BPSK[i]); }}/*匹配GF扩域*/void math_GF(unsigned char c,unsigned char c_tem[K]){ unsigned int k;while(1){if (c == '8')c = 'a';if (c>'8'&& c!='a')c -= 7;if (c=='7')c = '1';if (c < '7'|| c=='a')break;}switch (c){ case '1':for (k=0;k<3;k++)c_tem[k] = GF[0][k];break;case 'a':for (k=0;k<3;k++)c_tem[k] = GF[1][k];break;case '0':for (k=0;k<3;k++)c_tem[k] = '0';break;default:unsigned int m = c - 48;for (k=0;k<3;k++)c_tem[k] = GF[m][k];}}/*求伴随多项式*/unsigned char count_sx(unsigned char de_rsc[N],unsigned int f){ unsigned char tem = '0' ,result = '0';unsigned char c_tem1[K];unsigned char c_tem2[K];unsigned char c_tem[K];for (unsigned int i=0;i<N;i++){if (de_rsc[i] == '0')continue;else if (de_rsc[i] == 'a')tem = '1' + (6 - i)*f;else if (de_rsc[i] == '1'){if ((6-i)!=0)tem = '0' + (6 - i)*f;else tem = '1';}elsetem = de_rsc[i] + (6 - i)*f;math_GF(tem,c_tem1);math_GF(result,c_tem2);for (unsigned int k=0;k<K;k++){if (c_tem1[k] == c_tem2[k])c_tem[k] = '0';else c_tem[k] = '1';}result = math(c_tem);}return result;}/*求错误多项式count_ex（）的子程序，实现异或运算*/void nor(unsigned char temp1[K],unsigned char temp2[K],unsigned char result[K]){for (unsigned int i=0;i<K;i++){if (temp1[i] == temp2[i])result[i] = '0';else result[i] = '1';}}/*求错误多项式count_ex（）的子程序，返回两个行列式相减的结果*/int fun(unsigned char c1,unsigned char c2){ unsigned char temp1[K],temp2[K],result[K];if (c1 == '0')c1 = '1';else if (c1 == '1') c1 = 'a';if (c2 == '0') c2 = '1';else if (c2 == '1') c2 = 'a';math_GF(c1,temp1);math_GF(c2,temp2);nor(temp1,temp2,result);unsigned char c = math(result);if (c == '1') return 0;else if (c == 'a') return 1;else return c-48;}/*求错误多项式*/void count_ex(unsigned char s[R],unsigned char qx[K-1],int n) { unsigned char tem1,tem2; u nsigned char sx[R]; int tem;for (unsigned int i=0;i<n;i++) {if (s[i] == '1') sx[i] = '0';else if (s[i] == 'a') sx[i] = '1';else sx[i] = s[i]; }/*采用行列式法*/if (s[0]!='0'&&s[2]!='0') tem1 = sx[0]+sx[2]-48;else tem1 = '0';if (s[1]!='0') tem2 = sx[1]+sx[1]-48;else tem2 = '0';tem = fun(tem1,tem2);/*Q2=(s3s3-s2s4)/(s1s3-s2s2)*/if (s[2]!='0') tem1 = sx[2]+sx[2]-48;else tem1 = '0';if (s[1]!='0'&&s[3]!='0') tem2 = sx[1]+sx[3]-48;else tem2 = '0';int a = fun(tem1,tem2);qx[0] = a-tem+48;if (qx[0] < '0') qx[0] = qx[0] + 7;/*Q1=(s1s4-s2s3)/(s1s3-s2s2)*/if (s[0]!='0'&&s[3]!='0') tem1 = sx[0]+sx[3]-48;else tem1 = '0';if (s[1]!='0'&&s[2]!='0') tem2 = sx[1]+sx[2]-48;else tem2 = '0';int b = fun(tem1,tem2);qx[1] = b-tem+48;if (qx[1] < '0') qx[1] = qx[1] + 7;}/*搜索错误位置*/void wrong_position(unsigned char tem[2]){ unsigned char qx[K]; unsigned int i,j; unsigned char tem1[K],tem2[K],tem3[K]; unsignedchar temp='0',result;for (i=0;i<N;i++){for (unsigned int j=0;j<K-1;j++) qx[j] = tem[j];/*确保下次循环时错误位置不变*/int n=2; result = '0';for (j=0;j<K;j++){ if (qx[j]=='1') qx[j] = '0';else if (qx[j]=='a') qx[j] = '1';qx[K-1] = '1';/*错误多项式的最后一位是‘1’*/temp = qx[j]+i*n;/*实现x^i*a^i*/n -= 1;math_GF(temp,tem1);math_GF(result,tem2);for (unsigned int k=0;k<K;k++)/*异或运算*/{ if (tem1[k] == tem2[k]) tem3[k] = '0';else tem3[k] = '1';}result = math(tem3); }}}/*译码与纠错*/void decode_rsc(unsigned char de_rsc[N],unsigned char sx[R]){ for (unsigned int i=0;i<R;i++) { sx[i] = count_sx(de_rsc,i+1);}unsigned char qx[K-1];count_ex(sx,qx,R);for (unsigned int j=0;j<K-1;j++){ if (qx[j] == '8') qx[j] = 'a';else if (qx[j]>'8'&& qx[j]!='a') qx[j] -= 7;else if (qx[j]=='7') qx[j] = '1';else if (qx[j] < '0') qx[j] = qx[j] + 7;}wrong_position(qx);}void main(){char GX[R+1];void count_gx(char GX[R+1]);count_gx(GX);unsigned char rsc[N];unsigned char rsc_GF[N][K];unsigned char remainder[R];count_remainder(remainder);create_rsc(rsc,remainder,rsc_GF);unsigned char rsc_BPSK[N][K];BPSK_mapping(rsc_GF,rsc_BPSK);add_noise(rsc_BPSK);unsigned char de_rsc[N];de_mapping(rsc_BPSK,de_rsc);unsigned char sx[R];decode_rsc(de_rsc,sx);cout << endl;system("pause");}5.实验测试结果：二.心得体会：通过这次的实验，让我对循环码有了更深刻的理解。

信息论与编码基础
线性分组码
1、汉明码的结构
码长 信息位数
n 2m 1
k 2m m 1
监督码位 最小码距 纠错能力
r nk m
d 3
t 1
信息论与编码基础
线性分组码
2、扩展汉明码
C [mk1mk2...m1m0cr1...c1c0 ]
(8,4(7)扩,4)展汉汉明明码码
C [C c0 ]
1 2
1 1
H
2 2
1 2
1 0
0 1
利用伴随式译码对(1122),(2110),(2222)码字进行译码。
E 0000 1000 0100 00010010 0011 1001 1010 0200 S 00 22 12 01 10 11 20 02 21
信息论与编码基础
线性分组码
思考题2：
考虑码率为1/2的（n,n/2）的线性分组码C，其生 成矩阵为G。 证明：如果
其定充理要条件(n是,k)H线矩性阵分中组任码何最2小t列距线离性等H无于关d。111min的110 充110要条100 件100是H100
0 0 0
矩阵中任何 dmin 1 列线性无关。
0 1 1 0 0 0 1
结论：
1、上述定理是构造距离为d的任何类型线性分组码的基础
2、H矩阵列排序不同，码集不同，但纠错能力不变
线性分组码
伴随式译码
定理 每个陪集全部 2k个矢量都有相同的伴随式 而不同陪集有不同的伴随式。
C C C C （0）
（1）
（2）
（3）
S
0000 0111 1010 1101 00
1000 1111 0010 0101 10

第7章 分组码 169可以看到，()q x 正是许用码组()A x 向左循环移位i 次的结果，即它也是循环码中的一许用码组[]()121i n i n i n i n i A a a a a −−−−−+−=L 。

7.5.2 循环码生成矩阵、生成多项式和监督矩阵循环码是分组码的主要分支，因此循环码就符合分组码的描述形式，也可以用生成矩阵、校验矩阵来进行描述。

1．循环码的生成矩阵由前述式（7-31）可知，有了生成矩阵G ，就可由k 个信息位得出整个码组，而且生成矩阵G 中的每一行都是一个许用码组。

我们还知道，如果可以找到k 个线性无关的许用码组，则可以用它们作为生成矩阵G ，并由它生成其余的码组。

在循环码中，一个(,)n k 循环码有2k 个许用码组。

若用()g x 表示其中前(1)k −位皆为“0”的码组，用()x g x 、2()x g x 、L 、1()k x g x − 分别表示其向左移1、2、L 、1k −位的码组（实际上是()i x g x 除以1n x +的余式）。

根据循环性可知：()g x 、()x g x 、2()x g x 、L 、1()k x g x − 都是许用码组，而且这k 个码组将是线性无关的。

因此可用它们构成循环码的生成矩阵。

其中()g x 又被称为循环码的生成多项式。

因此，循环码的生成矩阵k n ×G 可以写成12()()()()()k k k n x g x x g x x x g x g x −−×⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦M G （7-45） 若用()M x 表示信息多项式，其定义为1110()k k M x m x m x m −−=+++L （7-46）式中，[]110k m m m −L 表示k 个信息比特。

由此得到的码组为[]11101110()()()()()()()()k k k k A x M x G x x g x m m m x g x g x m x m x m g x −−−−=⎡⎤⎢⎥⎢⎥=⋅⎢⎥⎢⎥⎢⎥⎣⎦=+++ M L L （7-47）式（7-47）表明，所有的许用码组多项式都可被()g x 整除，而且任一次数不大于(1)k − 的多项式乘()g x 都是循环码的许用码多项式。

通信传输课程设计题目循环码的原理及应用英文题目 Principle and Application of Cyclic Codes专业通信工程摘要循环码是线性分组码中最重要的一种子类，是目前研究得比较成熟的一类码。

它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠正随机错误，也能纠正突发错误。

循环码还有易于实现的特点，很容易用带反馈的移位寄存器实现其硬件。

循环码具有许多特殊的代数性质，这些性质有助于按照要求的纠错能力系统地构造这类码，并且简化译码算法，目前发现的大部分线性码与循环码有密切关系正是由于循环码具有码的代数结构清晰、性能较好、编译码简单和易于实现的特点，因此在目前的计算机纠错系统中所使用的线性分组码几乎都是循环码。

关键字：循环码；编码；解码；检错；纠错；MatlabIPrinciple and Application of Cyclic CodesAbstractCyclic code is a linear block code of a sub-class of the most important, is the more mature studied a class of codes. Its review, error correction ability, coding and decoding equipment is not complicated, and the performance is better, not only can correct random errors, burst errors can be corrected. Cyclic code also features easy to implement, it is easy to use feedback shift registers with the hardware. Cyclic code has many special algebraic properties, these properties contribute to the error correction ability of the system as required to construct such codes, and simplify the decoding algorithm, currently found in most of the closely related linear codes and cyclic codes precisely because cyclic codes have a clear code of algebraic structure, better performance, encoding and decoding features simple and easy to implement, so in the present computer system used by the error-correcting linear block codes are almost always cyclic codes.This report details the definition of cyclic codes generated by a generator polynomial matrix and the process of system-generated matrix, and write in the Matlab environment, the cycle code encoder and decoder to achieve the encoding and decoding function. Analysis and discussion of this code error is found, the ability to correct errors.Keywords:Cyclic codes; encoding; decoding; error detection; correction; MatlabII目录摘要 (I)Abstract (II)第一章绪论 (1)第二章算法原理 (2)2.1循环码定义 (2)2.2循环码的多项式描述 (2)2.3生成多项式及生成矩阵G (2)2.4 系统循环码 (3)2.5循环码的编码： (4)2.6循环码的解码 (6)2.7循环码检错与纠错能力 (7)第三章循环码的应用 (8)3.1循环码在微机网络系统中的应用 (8)3.2循环码在CDMA中的应用 (8)3.3循环码在数字通信中的应用 (8)3.4在前向纠错中的应用 (8)3.5循环码在铁路通讯安全中的应用 (9)参考文献 (11)附录A Matlab代码直接实现 (12)附录B 拓展：以（7.3）码为例 (14)Principle and Application of Cyclic Codes第一章绪论数字信号在传输过程中，由于受到干扰的影响，码元波形将变坏。

D k 1 g ( D ) k 2 D g ( D ) G ( D) 1 g ( D)
循环码
• (7,3) 循环码
g ( D) D4 D3 D2 1
D 2 ( D 4 D 3 D 2 1) D 6 D 5 D 4 D 2 5 4 3 2 4 3 G ( D) D ( D D D 1) D D D D 1 ( D 4 D3 D 2 1) D 4 D 3 D 2 1
A (1011100)
• 左移一位
• 左移 位
A( D) D6 D4 D3 D2
A (an1an2 a1a0 )
A(1) (D) (an2 Dn1 an3 Dn2
a0 D an1 )
i
A (an2
a1a0 an1 )
an1i D ani )
(l t )
9.1.3. 差错控制编码分类
• 按功能分
• • •
检错码 纠错码 纠删码（发现不可纠正的错误时，可发出指示或删除） 线性码 非线性码 分组码 卷积码
• 按信息码元和监督码元之间的校验关系分
• •
• 按信息码元和监督码元之间的约束方式分
• •
香农理 纠错码的理论基础
• 香农定理
存在噪声干扰的信道，若信道容量为C，只要发送端以低 于C的速率R发送信息（R为输入道编码器的二进制码元 速率），则一定存在一种编码方式，使编码的错误概 率随着码长n的增加将按指数下降道任一的值，即
0 0 0
1 1 1 0 1 0 0 1 1 0 1 0 1 0 a 6 1 0 1 1 0 0 1