用C语言实现线性分组码的编译码.doc
- 文档编号:4911452
- 上传时间:2023-05-07
- 格式:DOC
- 页数:37
- 大小:1.07MB
用C语言实现线性分组码的编译码.doc
《用C语言实现线性分组码的编译码.doc》由会员分享,可在线阅读,更多相关《用C语言实现线性分组码的编译码.doc(37页珍藏版)》请在冰点文库上搜索。
*******************
实践教学
*******************
2011年春季学期
《计算机通信》课程设计
题目:
线性分组码的编译码软件设计
专业班级:
姓名:
学号:
指导教师:
成绩:
34
摘要
本次课程设计是线性分组码的编译码软件设计,该软件可以对输入的多个四位信息码进行Hamming编码,对于接收的多个七位信息码可以进行译码,从而译出四位信息位。
当接收的信息码中有一位错误时,可以纠正这一位错码,进而译出正确的信息码组,整个程序是用C语言编写的。
关键词:
线性分组码;编码;译码;纠错;检错
目录
前言 1
一、C语言简介 2
1.1什么是C语言 2
1.2C语言的特点 2
1.3运行C程序的步骤与方法 3
二、设计目标 5
三、线性分组码的基本原理 6
3.1线性分组码的编码 6
3.1.1监督矩阵 6
3.1.2生成矩阵 8
3.2线性分组码的译码 9
3.2.1码的距离及纠检错能力 9
3.2.2伴随式与译码 10
四、推导过程 11
4.1编码过程 11
4.2译码过程 11
五、程序设计及仿真分析 13
5.1程序流程图 13
5.1.1主程序流程图 13
5.1.2编码程序流程图 14
5.1.3译码程序流程图 15
5.2程序运行分析 16
5.2.1主程序运行分析 16
5.2.2编码运行分析 19
5.2.3译码运行分析 20
5.3软件分析 21
设计总结 23
致谢 23
参考文献 24
附录 25
前言
数字通信系统是以数字信号的形式来传递信息的一种通信系统。
它所包括的范围很广,从现在的市话通信系统、数字蜂窝系统、计算机通信系统到雷达系统、遥控测控系统、计算机运算和存储系统等都是数字通信系统。
所有数字通信系统都可归结为如图1所示的模型。
信道编码器
信源编码器
信源
调制器
(读出单元)
调制器
(存储媒质)
调制器
(写入单元)
噪声源
信道译码器
信源译码器
信宿
图1数字通信系统模型
图1中,信源编码器把信源发出的消息如语言、图像、文字等转换成为二进制(也可以转换成为多进制)形式的信息序列,并且为了传输有效,还去掉一些与传输信息无关的冗余。
有时为了保密,信源编码器后还可以接上加密器。
为了抗击传输过程中的各种干扰,往往要认为地增加一些冗余,使系统具有自动检错和纠错能力,这种功能由图中的信道编码器即纠错编码器完成。
调制器的功能是把纠错编码器送出的信息序列通过调制器变换成适合于信道传输的信号。
数字信号在信道传输过程中,总会遇到各种干扰而使信号失真,这种失真信号传输到接收端的解调器进行解调,变成二进制信息(多进制)序列。
由于信道干扰的影响,该信息序列中可能有错误,经过信道译码器即纠错码译码器,对其中的错误进行纠正,再通过信源译码器(及解密器)恢复成原来的消息送给用户。
从上可知,信道编码是用来控制有扰信道对信息序列所产生的差错,故也称为差错控制编码。
这种方法是提高数字通信可靠性的有效方法,也是目前较为流行的差错控制编码技术。
分组码是一组固定长度的码组,可表示为(n,k),通常它用于前向纠错。
在分组码中,监督位被加到信息位之后,形成新的码。
在编码时,k个信息位被编为n位码组长度,而n-k个监督位的作用就是实现检错与纠错。
这种码的编码效率比较高,因此得到了广泛的应用。
一、C语言简介
1.1什么是C语言
C语言是一种计算机程序设计语言。
它既具有高级语言的特点,又具有汇编语言的特点。
它由美国贝尔研究所的D.M.Ritchie于1972年推出。
1978后,C语言已先后被移植到大、中、小及微型机上。
它可以作为工作系统设计语言,编写系统应用程序,也可以作为应用程序设计语言,编写不依赖计算机硬件的应用程序。
它的应用范围广泛,具备很强的数据处理能力,不仅仅是在软件开发上,而且各类科研都需要用到C语言,适于编写系统软件,三维,二维图形和动画。
具体应用比如单片机以及嵌入式系统开发。
1.2C语言的特点
一种语言之所以能存在和发展,并具有较强的生命力,总是有不同于其他语言的特点。
主要的优缺点介绍如下。
优点
l简洁紧凑、灵活方便。
C语言一共只有32个关键字,9种控制语句,程序书写形式自由,区分大小写。
把高级语言的基本结构和语句与低级语言的实用性结合起来。
C语言可以像汇编语言一样对位、字节和地址进行操作,而这三者是计算机最基本的工作单元。
l运算符丰富。
C语言的运算符包含的范围很广泛,共有34种运算符。
C语言把括号、赋值。
强制类型转换等都作为运算符处理。
从而使C语言的运算类型极其丰富,表达式类型多样化。
灵活使用各种运算符可以实现在其它高级语言中难以实现的运算。
l数据类型丰富。
C语言的数据类型有:
整型、实型、字符型、数组类型、指针类型、结构体类型、共用体类型等。
能用来实现各种复杂的数据结构运算。
并引入了指针概念,使程序效率更高。
另外C语言具有强大的图形功能,支持多种显示器和驱动器。
且计算功能、逻辑判断功能强大。
lC是结构式语言。
结构式语言的显著特点是代码及数据的分隔化,即程序的各个部分除了必要的信息交流外彼此独立。
这种结构化方式可使程序层次清晰,便于使用、维护以及调试。
C语言是以函数形式提供给用户的,这些函数可方便的调用,并具有多种循环、条件语句控制程序流向,从而使程序完全结构化。
l语法限制不太严格,程序设计自由度大。
虽然C语言也是强类型语言,但它的语法比较灵活,允许程序编写者有较大的自由度。
l允许直接访问物理地址,对硬件进行操作。
由于C语言允许直接访问物理地址,可以直接对硬件进行操作,因此它既具有高级语言的功能,又具有低级语言的许多功能,能够像汇编语言一样对位、字节和地址进行操作,而这三者是计算机最基本的工作单元,可用来写系统软件。
l生成目标代码质量高,程序执行效率高。
一般只比汇编程序生成的目标代码效率低10へ20%。
l适用范围大,可移植性好。
C语言有一个突出的优点就是适合于多种操作系统,如DOS、UNIX、windows98.windowsNT;也适用于多种机型。
C语言具有强大的绘图能力,可移植性好,并具备很强的数据处理能力,因此适于编写系统软件,三维,二维图形和动画,它也是数值计算的高级语言。
缺点
lC语言的缺点主要表现在数据的封装性上,这一点使得C在数据的安全性上有很大缺陷,这也是C和C++的一大区别。
lC语言的语法限制不太严格,对变量的类型约束不严格,影响程序的安全性,对数组下标越界不作检查等。
从应用的角度,C语言比其他高级语言较难掌握。
1.3运行C程序的步骤与方法
为了使计算机能按照人的意志进行工作,必须根据问题的要求,编写出相应的程序。
为了使计算机能执行高级语言源程序,必须先用一种称为“编译程序”的软件,把源程序翻译成二进制形式的“目标程序”,然后再将该目标程序与系统的函数库以及其他目标程序连接起来,形成可执行的目标程序。
在编好一个C源程序后如何上机运行呢?
在纸上写好一个程序后,要经过这样几个步骤:
上机输入与编辑源程序对源程序进行编译与库函数连接运行目标程序。
以上过程如图2所示。
图中实线表示操作流程,虚线表示文件的输入输出。
例如,编辑后得到源程序文件f.c,然后在进行编译时再将源程序文件f.c输入,经过编译得到目标程序文件f.obj,再将目标程序f.obj输入内存,与系统提供的库函数等连接,得到可执行的目标程序f.exe,最后把f.exe调入内存再使之运行。
不正确
有
无
正确
编辑
编译
有错?
连接
执行
结果
正确?
结束
开始
源程序
f.c
目标程序
f.obj
库函数和其他目标程序
可执行目标程序f.exe
图2运行C程序的流程图
二、设计目标
本次课程设计主要是用语言编写一个(7,4)线性分组码的编译程序,最基本的是要具备对输入的信息码进行编码,让它具有抗干扰的能力。
同时,还要让它具有对接收到的整个码组中提取信息码组的功能。
但是,在实际的通信系统中,由于信道传输特性不理想以及加性噪声的影响,接收到的信息中不可避免地会发生错误,影响通信系统的传输可靠性,因而,本设计要让该程序具有纠正错误的能力,当接收到的码组中有一位码,发生错误时可以检测到这一位错码,并且可以纠正这一位错码,最终系统可以从纠正后的码组中提取正确的信息码组;对于接收码组中出现的两位错误,能检测到错误,但是不能正确的纠正错误。
该编译器针对具体的生成矩阵
完成如下工作:
1.完成对任意信息序列的编码。
2.根据生成矩阵,形成监督矩阵;
3.根据得到的监督矩阵,得到伴随式,并根据它进行译码;
4.验证工作的正确性。
三、线性分组码的基本原理
3.1线性分组码的编码
3.1.1监督矩阵
线性分组码中许用码组为个。
定义线性分组码的加法为模二加法,乘法为二进制乘法。
即、、、;、、、。
且码组与码组的运算在各个相应比特位上符合上述二进制加法运算规则。
线性分组码具有如下性质的性质:
1.封闭性。
任意两个码组的和还是许用的码组。
2.码的最小距离等于非零码的最小码重。
对于码组长度为、信息码元为位、监督码元为位的分组码,常记作码,如果满足,则有可能构造出纠正一位或一位以上错误的线性码。
下面我们通过(7,4)分组码的例子来说明如何具体构造这种线性码。
设分组码中,,为能纠正一位误码,要求。
取,则。
该例子中,信息组为,码字为。
用,,的值与错码位置的对应关系可以规定为如表1所列。
由表中规定可知,当已知信息组时,按以下规则得到三个校验元,即:
(式3.1)
表1错码位置示意表。
错码位置
错码位置
001
101
010
110
100
111
011
000
无错
在发送端编码时,信息位,,和的值决定于输入信号,因此它们是随机的。
监督位,和应根据信息位的取值按监督关系来确定,即监督位应使上三式中,和的值为零(表示编成的码组中应无错码)。
由上式经移项运算,解出监督位:
(式3.2)
给出信息位后,可直接按上式算出监督位,其结果见表2。
接收端收到每个码组后先按式(3.1)计算出,和,再按表1判断错码情况。
表2(7,4)线性分组码(海明码)
信息组
码组
信息组
码组
0000
0000000
1000
1000111
0001
0001011
1001
1001100
0010
0010101
1010
1010010
0011
0011110
1011
1011001
0100
0100110
1100
1100001
0101
0101101
1101
1101110
0110
0110011
1110
1110100
0111
0111000
1111
1111111
给出(7,4)线性分组码有即16个许用码字或合法码字,另有个禁用码字。
发送方发送的是许用码字,若接收方收到的是禁用码字,则说明传输中发生了错误。
按上述方法构造的码称为海明码。
表2所列的(7,4)海明码的最小码距,因此,这种码能纠正一个错码或检测两个错码。
海明码的编码效率等于
(式3.3)
当n很大时,则编码效率接近1。
可见,海明码是一种高效码。
现在再来讨论线性分组码的一般原理。
上面已经提到,线性码是指信息位和监督位满足一组线性方程的码,式(3.1)就是这样一组线性方程的例子。
现在将它改写成:
(式3.4)
式(3.4)可以表示成如下矩阵形式:
(模2) (式3.5)
上式还可以简记为:
或 (式3.6)
其中
右上标“T”表示将矩阵转置。
将称为监督矩阵,编码时只要监督矩阵给定,编码时监督位和信息位的关系就完全确定。
由式(3.4)、式(3.5)都可看出,的行数就是监督关系式的数目,它等于监督位的数目。
的每行中的“1”的位置表示相应码元之间存在的监督关系。
式(3.5)中的矩阵可以分为两部分:
(式3.7)
式中,为阶矩阵,为阶单位方阵,将具有形式的矩阵称为典型监督矩阵。
由代数理论可知,矩阵的各行应该是线性无关的,否则将得不到个线性无关的监督关系式,从而也得不到个独立的监督位。
若一行矩阵能写成典型的矩阵形式,则其各行一定是线性无关的。
因为容易验证的各行是线性无关的,故也是线性无关的。
3.1.2生成矩阵
类似于式(3.4)改变成式(3.5)中矩阵形式那样,式(3.5)也可以改写成:
(式3.8)
或者
(式3.9)
式中,为一个阶矩阵,即它为的转置,即
(式3.10)
式(3.9)表明,信息位给定后,用信息位的行距乘矩阵就产生出监督位。
将的左边加上一阶单位方阵就构成一矩阵,即
(式3.11)
称为生成矩阵,因为由它可以产生整个码组,即有
(式3.12)
或者
(式3.13)
因此,如果找到了码的生成矩阵,则编码的方法就完全确定。
具有形式的生成矩阵称为典型生成矩阵。
由典型生成矩阵得出的码组中,信息位不变,监督位附加于其后,这种码称为系统码。
与矩阵相似,也要求矩阵的各行是线性无关的。
因为由式(3.13)可以看出,任一码组都是的各行的线性组合。
共有行,若它们线性无关,则可组合出种不同的码组,它恰是有为信息位的全部码组;若的各行有线性相关的,则不可能由生成种不同码组了。
实际上,的各行本身就是一个码组。
因此,如果已有个线性无关的码组,则可以用其作为生成矩阵,并由它生成其余的码组。
3.2线性分组码的译码
3.2.1码的距离及纠检错能力
1.码的距离
两个码字之间,对应位取之不同的个数,称为汉明距离,用表示。
一个码的最小距离定义为,两个码字之间的距离表示了它们之间差别的大小。
距离越大,两个码字的差别越大,则传送时从一个码字错成另一码字的可能性越小。
码的最小距离愈大,其抗干扰能力愈强。
2.线性分组码的纠检错能力
对于任一个线性分组码,
(1)若要在一个码字内检测出e个错误,则要求码的最小距离;
(2)纠正个错误,则要求码的最小距离;
(3)纠正个错误同时检测个错误,则要求。
3.2.2伴随式与译码
一般说来,式(3.13)中为一列的行矩阵。
此矩阵的个元素就是码组中的个码元,所以发送的码组就是。
此码组在传输中可能由于干扰引入差错,故接收码组一般说来与不一定相同。
若设接收码组为一列的行矩阵,即
(式3.14)
则发送码组和接收码组之差为:
(模2) (式3.15)
它就是传输中产生的错码行矩阵,其中
(式3.16)
其中
因此,若,表示该位接收码元无错;若,则表示该位接收码元有错。
式(3.15)也可以改写成:
(式3.17)
接收端译码时,可将接收码组代入式(3.6)中计算。
若接收码组中无错码,即,则,把它代入式(3.6)后,该式仍成立,则有
(式3.18)
当接收码组有错时,,将代入式(3.15)后,该式不一定成立。
在错码较多,已超过这种编码的检错能力时,变为另一许用码组则式(3.18)仍能成立。
这样的错码错码是不可检测的。
在未超过检错能力时,上式不成立,即其右端不等于零。
假设这时式(3.18)的右端为,即
(式3.19)
将代入式(3.19)中可得
由式(3.6)知,,所以
(式3.20)
式中,称为伴随式或校正子。
它与式(3.1)中的相似,有可能利用它来指示错码位置,这一点可以直接从式(3.20)中看出,式中只与有关,而与无关,这就意味着与错码之间有确定的线性变换关系。
若和之间一一对应,则将能代表错码的位置。
四、推导过程
4.1编码过程
由与的分块表示的矩阵形式
(式4.1)
(式4.2)
(式4.3)
(式4.4)
则有
或 (式4.5)
已知生成矩阵
根据以上几式可求出监督矩阵
最后可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵。
即
(式4.6)
所有的编码情况如表1所示。
4.2译码过程
对于译码过程来说,同样由上知道监督矩阵:
根据监督矩阵,将矩阵的行和列调换,可求出监督矩阵的转置矩阵
再根据式(3.20)即求出伴随式,由伴随式式可以知道错码的位置及及纠正错码,具体的错码位置如表1所示。
纠正了接收码后可以提取出其中的四位信息位。
五、程序设计及仿真分析
5.1程序流程图
5.1.1主程序流程图
主程序一开始就有欢迎界面,并对该编译器做了简单的介绍,同时为方便用户使用,对用户的操作也进行了补充说明,接着给用户显示出了选择提示语句,可以选择编码器、译码器、退出。
当用户做出选择后便会进入各自的子程序,执行相应的功能,如果用户输入错误,还会给出错误提示。
主程序的流程图如图3所示。
输入3
输入3
输入2
输入1
输入2
输入1
开始
欢迎界面
1.编码器2.译码器3.退出
译码程序
退出提示
持续操作
1.编码器2.译码器3.退出
退出
编码程序
图3主程序流程图
5.1.2编码程序流程图
在程序进入编码子程序时,它首先提示用户输入需要编码的码组个数,根据用户选择的个数接着要求用户输入编码的信息码组,信息码组与生成矩阵相乘便会得到相应的编码,其流程图如图4所示。
错误
正确
开始
提示输入要编码的信息码组的个数
提示输入信息码组M
输入正确?
将码组赋给二维数组,码组的个数作为行数,码组的位数作为数组的列数
返回
提示输入错误
并重新输入
信息组的数组与生成矩阵数组相乘
编码输出c
把生成矩阵赋给一个二维数组G
图4编码程序流程图
5.1.3译码程序流程图
对于译码程序,因为信息在传输过程中会遇到噪声干扰,所以接收码组会出现错码、丢码或多码现象。
又因为很难判断丢码或多码的具体位置,所以这两种情况处理起来比较复杂,在这暂不进行译码,只做出判断。
对于错码,可以纠正一位错误,发现两位错误。
在译码的过程中,要用到监督矩阵的转置矩阵,所以先求生成矩阵对应的监督矩阵,再进行转置,然后提示输入接收码组,输入的接收码组中有可能丢失码位,故而先判断,再进行纠检错,输出正确的码组,最后提取出正确的信息组。
其流程图如图5所示。
无
有
开始
根据生成矩阵求监督矩阵H
输出监督矩阵H
求监督矩阵对应的转置矩阵HT
提示输入接收码组B
输入的接收码组是否有丢码?
把接收码组每七位分成一个码组,并输出
丢码提示
接上页
求接收码组与转置矩阵的乘积
输出伴随式
根据伴随式译码
输出纠正后的码组,
并提取信息码输出。
返回
图5译码程序流程图
5.2程序运行分析
5.2.1主程序运行分析
图6主界面运行图
从程序一开始就运行主界面,主界面有对该软件的简单介绍,接着就给出了选择功能。
用户输入不同的序号可以执行不同的功能,主界面仿真结果如图6所示。
输入“1”后按回车键执行编码功能,如图7所示;输入“2”后按回车键执行译码功能,如图8所示;输入“3”后按回车键执行退出如图9所示;输入其它系统会显示错误提示信息,如图10所示。
图7选择编码功能
图8选择译码功能
图9执行退出功能
图10输入错误时错误提示
5.2.2编码运行分析
执行编码程序时,为了满足用户的不同需求,可以先输入用户需要的编码的信息组数,再根据用户输入的信息组数决定输入信息码的多少,输入完按回车键就完成了一次编码。
例如用户一次需要对连续的四个四位信息组进行编码,信息组为(1011010100011001),根据表2可知,编码后的结果为(1011001010100100010111001100),仿真过程如图11和图12所示。
图11输入信息组数后系统界面
图12编码后的系统界面
由运行的界面可知,软件还可以持续操作,当用户再做出选择,可以执行相应的功能,整个体系就是按照这个思想联系在一起的。
5.2.3译码运行分析
对于信道编码程序而言,由于信道干扰,接收码组的长度不一,当接收码组中出现丢码时,系统会给出提示,对这种情况系统无法译码只给出提示要求重新输入,例如输入(01100011101112),2作为输入的结束标志,因为信息码组只有十三位,传输过程丢了一位,系统会给出提示,如图13所示;如果接收码组没有丢码,系统可以纠正一位错码,发现两位错码,例如输入上面编码后的4个接收码组,并故意输错第二个码组的位和第四个码组的位和位,即输入(10110010101111000101110011112)(2为结束标志),以验证系统运行的正确性。
运行界面如图14所示。
为了体现软件的持续操作,我们从编码结束后再选择译码。
图13输入有丢码的接收码组时系统运行界面
图14译码运行界面
5.3软件分析
根据软件运行情况分析来看,该软件最终实现的功能有:
ü对数量不等的信息组编码;
ü对数量不等的接收码组纠正一位错误,发现两位错误;
ü对输入的接收码组判断是否有丢码;
ü循环使用编码器和译码器;
ü对操作失误做出提示。
与最初的设计目标相比,该软件的不足方面有:
Ø使用编码器的时候,如果输入有误,系统没有给出明确提示;
Ø当接收码组中有丢失位时,不能译码;
Ø显示界面不够人性化。
总之,软件在可靠性方面已做出验证,达到了要求。
C语言比起其它语言要难学,更稳定,C程序的稳定性就证明了该软件具有很好的稳定性。
实用性方面,由于该软件只对四位信息组编码,编码后有七位;对七位接收码组译码,提取信息位后是四位。
其它码并不适应该软件,所以它的适用范围受到了限制。
设计总结
三周的课程设计已经结束,这些天对于一天都在学习理论知识的我来说十分珍贵。
因为这是一个理论联系实际,实践检验理论的相互过程。
在这一过程中,真切感觉到自己知识能力的匮乏,虽然我考过了C语言二级,但是好多东西都只是知道一些皮毛,真正学透的东西很少,更不用说把学到的知识运用到实际生活中了。
而且很多东西在实际中与理想相去甚远,而应用就是要减小这种差距。
每一点差距的缩小都得付出艰辛的努力,但这种付出是非常值得的。
这次课设刚开始时,由于好长时间没有接触C语言,编写程序遇到的问题非常多,比如写输入语句和输出语句的格式,还有每个语句后面的分号必须是英文的,在这个上最容易犯错,幸好最后经过我的仔细检查最终完成了整个程序。
在程序的功能上,刚开始我想的比较简单,只对简单的一个码组编译码,后来经过老师的提醒,我又做了很多改动,最终完成整个程序。
但是在使用编码器的时候,对输入时的操作失误没有给出提示,由于时间的关系,也没有修改
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 实现 线性 分组码 译码