摘要
KL变换是一种建立在图像统计特性基础上的重要的正交变换，在许多方面尤其是图像识别上得到了广泛的应用。由于其可以去掉图像相关性的特性而在图像压缩上也得到应用。
在计算机科学里，数据压缩是通过使用特定的编码方案编码信息，比解码后的表示法使用更少的比特数（或其他的信息单位）的处理过程。需要压缩的数据主要是多媒体，比如音频，视频，图像等。对数据压缩人们目前已经提出了多种多样的理论与技术。变换编码压缩是其中经常应用的一类，KL变换是其中的失真最小的一种最佳变换。对于不同的数据类型，有不同的压缩方法。而课题研究的KL变换用于数据压缩时，主要是用于图像压缩，因此论文讨论的是KL变换用于图像压缩。
本文主要介绍了KL变换的概念及应用，图像压缩的基本原理与技术，相关的国际标准，KL变换用于图像压缩的原理，研究了其算法，并做了具体的实现等。证实了其在图像压缩方面的应用的可行性。

关键词：图像压缩,变换编码,KL变换,算法

ABSTRACT

The Karhunen-Loeve transform(KLT) is a kind of important orthogonal transformation,it has been widely applied in many respects particularly image recognition. Because of its characteristic of removing the image correlation,it also been used in image compression.
In computer science，data compression is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes.The data need to be compressed mainly is multimedia,such as audio,video and image.Now people has made a wide variety of theories and techniques to Data compression. Transform Coding compression is an often used method，and the KL transform is a best transformation has smallest Distortion. Regarding the different data type, has the different compression method.The study of the subject–KL transform,is mainly used in image compression when it’s been used in data compression,so what the paper discussed is KL transform used in image compression.
This paper mainly introduced the concept and application of the KL transform, basic principle and technology of image compression, international standard relevanted,the principle of the KL transform used in image compression. Has studied its algorithm and the concrete realization,approved its feasibility in the image compression aspect.

KEY WORDS: image compression,transform coding,KL transform, algorithm

第一章绪论
1．1研究背景
1950年以来，新技术革命――信息技术的应用使人类社会生产力的发展一日千里。随之而来的巨大数据量需要处理。可以说，人类正处在信息爆炸的时代，每时每刻产生的数据需要传输、存储。然而，不经压缩的信息其所需要的数据空间是极其巨大的。尤其是在多媒体信息渗透了人类生活方方面面的今天，声音，图像，视频需要巨大的传输带宽与存储空间。例如，一幅512*512像素，每分量8bit的彩色图像占768KB，而一幅2230*2230*8bit的气象卫星云图就占4.74MB了。再如，数字电话取样率最低，按每一取样用8位压扩量化，其数码率已达到64kb/s；而一路高清晰度电视（HDTV）数码率高达1280*720*60*3*8＝1327Mb/s！可以看出，若不对这些数据进行压缩，其传输或存储很难实用化。因此，人们提出了各种各样的数据压缩理论与方法。
数据压缩就是以最少的数码表示信源所发出的信息，减少容纳给定消息集合或数据采样集合的信号空间。其中一种理论是，数据的冗余度有时与不同的表示方法有关。可以将原始数据变换到另一个更为紧凑的表示空间，从而实现数据压缩。也就是所谓变换编码压缩。其基本原理是，用映射变换把原始信号中的各个样值从一个域变换到另一个域，然后针对变换后的数据再进行量化（二次量化）与编码操作。接收端首先对收到到信号进行解码和反量化，然后再进行反变换以恢复原来信号（在一定保真度下）。映射变换的关键在于能产生一系列更加有效的系数，对这些系数进行编码的总比特数，要比对原始数据直接编码所需的总比特数少的多，使数据率得以降低[1]。其中一种重要方法就是KL变换。KL变换是在均方误差准则下，失真最小的一种变换。KLT便于失真和码率的控制。在早期的编码实践中，用KL变换压缩在13.5kb/s下得到到的语音质量，可与56kb/s的PCM相比拟；在2bit/pel编码下的图像质量，可与7bit/pel的PCM相当。由此可见，研究KL变换编码压缩是有一定的意义的。不过KL变换需要先知道信源的协方差矩阵并求出特征值。但求特征值与特征向量并非易事，维数较高时甚至求不出来。即使能借助于计算机求解，也很难满足实时处理的要求，因此KLT在工程实践中还不能广泛使用[1]。
1．2 研究意义
作为毕业设计研究内容，基于KL变换编码的数据压缩研究可以加深对变换编码压缩的理解，增强工程实践能力。并对数据压缩尤其是图像压缩有切身体会。另外，KL变换主要用于图像处理领域，这也是值得研究的一个方向。
KL变换虽然实际工程中应用较少，但KL变换常用来评价其他变换的性能，因此其具体实现也有研究的必要。KL变换目前无快速算法，能找到一个相对高效的算法也是本课题的研究意义之一。
1．3 研究内容
KL变换（Karhunen-Loeve transform），也称Hotelling变换，特征向量变换或主分量变换。一个随机向量中各元素间往往存在某些相关性，1933年霍特林（Hotelling）提出了一个可以去掉其相关性的线性变换，并把它称为“主分量分析法”，所以此变换又称Hotelling变换。此后Karhunen和Loeve提出了一种针对连续信号的类似的变换，并派生出它的离散变换方法。故这个方法就称为Karhunen-Loeve transform――KL变换。
本课题将研究KL变换的概念，KL变换的应用，比较各种变换编码的性能，研究KL变换用于图像压缩的理论基础及基本算法，利用KL变换实现一个基本的图像压缩程序。讨论其改进算法。
第一章主要介绍了课题研究的背景。第二章则讨论了图像压缩的基本理论，技术分类等。第三章介绍了变换编码技术，KL变换的理论基础与应用。第四章研究了KL变换用于图像压缩的理论与算法。第五章则讨论了基于KL变换的图像压缩的具体实现。第六章给出全文的结论与总结。

第二章图像压缩技术现状
2．1 图像压缩的理论基础
2．1．1 图像压缩的意义
图像是信息传递的重要媒介，图像的应用在不断扩大：遥感图像、数字图书馆、Internet上的大量图像、视频，如电视会议、数字电视、IPTV等等。然而，图像的数据量通常很大，对存储、处理和传输带来许多问题。比如，图象采样后，如果对之进行简单的8bit量化和PCM编码，其数据量是巨大的。以CIF（Common Intermediate Format）格式的彩色视频信号为例，若采样速率为25帧/秒，采样样点的Y、U、V分量均为8bit量化，则一秒钟的数据量为：
352×288×3×8×25＝60.83Mbit
要传输或存储这样大的数据量是非常困难的，必需对其进行压缩编码，在满足实际需要的前提下，尽量减少要传输或存储的数据量。
在这种情况下，必须对图像进行合适的压缩以满足实际使用的要求。
2．1．2 图像压缩的方法评价
1．编码效率：包括图象压缩比（CR）、每像素所用的比特数（bpp）、每秒所需的传输比特数（bps）等。
2．重建图象质量，包括客观度量和主观度量。
客观度量：即图象的逼真度，可考虑为原图像与重建图像的差值。令波形解码器的输入波形为X，解码器的输出波形为Y，则较为常用的两个参数为：
均方误差：（2.1）
峰值信噪比：（2.2）
主观度量：即通过人们的主观测试来评价系统的质量，包括二元判决（即“接受”和“不可接受”）、主观PSNR、平均判分、等偏爱度曲线、多维积分（MDS）等。
3．算法的运算量和硬件实现的复杂程度；
4．算法的适用范围；
5．算法的抗信道噪声干扰能力等。
2．1．3 图像压缩的可能性
图像存在三种基本的数据冗余：编码冗余、像素间冗余、心理视觉冗余。如果能减少或消除上述三种冗余的1种或多种冗余，就能取得数据压缩的效果。
编码冗余：如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余。
像素间冗余：1. 反映图像中像素之间的相互关系。2. 因为任何给定像素的值可以根据与这个像素相邻的像素进行预测，所以单个像素携带的信息相对较少。3. 对于一幅图像，很多单个像素对视觉的贡献是冗余的。它的值可以通过与它相邻的像素值为基础进行预测。
心理视觉冗余：1. 人眼感觉到的图像区域亮度不仅取决于该区域的反射光，例如根据马赫带效应，在灰度值为常数的区域也能感觉到灰度值的变化。2. 这是由于眼睛对所有视觉信息感受的灵敏度不同。在正常视觉处理过程中各种信息的相对重要程度不同。3. 有些信息在通常的视觉过程中与另外一些信息相比并不那么重要，这些信息被认为是心理视觉冗余的，去除这些信息并不会明显降低图像质量。4. 由于消除心理视觉冗余数据会导致一定量信息的丢失，所以这一过程通常称为量化。5. 心理视冗余压缩是不可恢复的，量化的结果导致了数据有损压缩。
2．2 图像压缩技术分类
这里主要讨论的是静态图像压缩。可以分为两类：无损压缩（Lossless Compression）与有损压缩（Lossy Compression）。
2．2．1无损压缩
无损压缩主要基于减少像素间冗余，减少编码冗余的思想。主要分类与技术如下：
一变长编码
这是一种减少编码冗余的方法。
1． Huffman编码
将需要考虑的符号概率排序，并将最低概率的符号联结为一个单一符号。对每个化简后的信源进行编码，从最小的信源开始，一直编码到原始的信源。解码通过查询表的方式完成。问题：当对大量符号进行编码，构造霍夫曼编码比较复杂；对J个信源符号，需要进行J-2次信源化简和J-2次编码分配。它是一种单义码。
2．游程编码（RLC）
若沿某一特定方向上的一串m个象素具有相同的灰度值p，则只要传输(p,m)即可。
3．算术编码（Arithmetic Coding ，AC）
从整个符号序列出发，采用递推形式连续编码；在算术编码中，源符号和码字间的一一对应关系并不存在。1个算术码字要赋给整个信源符号序列，而码字本身确定0和1之间的1个实数区间；随着符号序列中的符号数量增加，用来代表它的区间减小而表达区间的信息单位数量变大。在信源概率分布比较均匀的情况下，它的编码效率高于Huffman编码，而且没有变换编码对数据输入分块的要求。
二 LZW编码
消除像素间冗余。是由Lemple和Ziv最早提出，然后由Welch充实的有专利保护的算法；将原始数据中的重复字符串建立一个字串表，然后用该重复字串在字串表中的索引替代原始数据达到压缩的目的；使用LZW的文件格式包括TIFF，GIF和PDF等。
三位平面编码
消除像素间冗余。将一幅图像分解为一系列二值图像并通过二值图像压缩方法对每幅二值图像进行压缩；位平面分解的两种方法：二值图像位平面与灰度编码位平面。
四无损预测编码
基本思想：通过仅提取每个像素中的新信息并对它们编码来消除像素间的冗余；1个像素的新信息定义为该像素的当前值与预测值的差；正是由于像素间有相关性，所以才使预测成为可能。
2．2．2 有损压缩
这里的思想是：牺牲图像复原的准确度以换取压缩能力的增加；如果产生的失真可以容忍，则压缩能力的增加是有效的。
一有损预测编码
直接对像素在图像空间进行操作。有损预测编码系统；最优预测器；最优量化。
二变换编码
这是种基于图像变换的编码方法：用可逆的线性变换（如傅里叶变换）将图像映射成1组变换系数，然后将这些系数量化和编码；大多数图像变换得到的系数值都很小，这些系数可以较粗地量化，或忽略不计；虽然失真很小，信息仍然不能完全复原，所以还是有损压缩。
三分形（fractal）编码
基于自相似性：无论几何尺度怎样变化，物体任何组成部分的形状都以某种方式与整体相似。关键在于引入了局部与全部相关去冗余的思想。压缩效率与物体本身性质有关。
四矢量量化(vector quantization,VQ)编码
核心思想：利用码书（Code Book）进行信息的传递和存储。编码思路：码书就是一种人为制定的映射，按照一定的准则把n维空间划分为若干子空间，然后把图像各象素的输入值分配到各组中，每组用一个n维矢量来表示。这组矢量和相应的序号构成码书；工作时码书在发送端和接收端各有一本，每输入一个像素数据就根据距离最小原则确定重建矢量，查出相应的序号送出，达到压缩的目的。特点：压缩效率较高；码书的训练非常重要。
五其他
主要有小波变换编码、基于模型的编码方法（MBA）、人工神经网络方法（ANN）等等。
2．3 图像编码标准
相关的国际组织：ISO（International Standardization Organization，国际标准化组织），ITU（International Telecommunication Union,国际电信联盟），前身是CCITT（国际电话电报咨询委员会）。相关工作：覆盖了从二值到灰度（彩色）值的静止和运动图像；采用的大部分基本技术前面已经介绍，主要包括预测和变换编码技术。
2．3．1 二值图像压缩标准G3和G4
这2个标准是由CCITT的两个小组(Group 3和Group 4)负责制定的，最初是为传真应用而设计的，现也用于其它方面。G3采用了非自适应、1维行程编码技术。对每组N行（N=4或N=2）扫描线中的后N-1行也可以用2维方式编码。G4是G3的1种简化版本，其中只使用2维编码。
在制定标准期间曾选择了1组共8幅具有一定代表性的“试验”图用来评判各种压缩方法。它们既包括打印的文字，也包括用几种语言手写的文字，另外还有少量的线绘图，G3对它们的压缩率约为15:1，G4的压缩率一般比G3高1倍。
2．3．2 JPEG(Joint Picture Expert Group)标准和JPEG2000标准
ISO和CCITT于1986年底成立了“联合图片专家组”，（Joint Photographic Experts Group，简称JPEG），致力于研究静止图像压缩算法的国际标准。定义了3种编码系统：1. 基于DCT的有损编码基本系统，可用于绝大多数压缩应用场合；2. 用于高压缩比、高精确度或渐进重建应用的扩展编码系统；3. 用于无失真应用场合的无损系统。
JPEG并没有规定文件格式、图像分辨率或所用彩色空间模型，这样它就有可能使用于不同应用场合，JPEG对录像机质量的静止图像的压缩率一般可达到25:1。
2000年完成的JPEG2000标准是JPEG的更新换代，它基于小波变换。特点如下：
1. 卓越的低码率压缩效率。传统的JPEG使用DCT，需将图像分块，限制了图像的压缩倍数；而小波是基于整幅图像处理，可实现高压缩比，避免了“分块”效应；
2. 嵌入式编码：在解码端无论获得多少码流，都能在当前码率下最优地将图像重建；
3. 引入“视觉权重”概念。根据视觉特性模型，对小波系数进行调整；
4. 实现“区域”编码策略，即对图像中感兴趣的部分进行单独的编、解码，而无需将整幅图像完全重建出来；
5. 开放性结构，可随时加入新的有效的算法模块。
2．3．3 视频图像编码标准H.261和H.263
一 H.261
1984年12月，CCITT第15研究组成立了“可视电话编码专家组”，并在1988年提出了视频编码器的H.261建议。主要应用对象是视频会议的图像传输。
H.261建议的原理结构的要点是：采用运动补偿进行帧间预测，以利用图像在时域的相关性；对帧间预测误差以8*8或16*16为宏块，进行DCT变换，以利用图像在空域上的相关性；接着对DCT变换系数设置自适应量化器，以利用人们的视觉特性；再采用Huffman熵编码，获得压缩码流。
二 H.263
H.263是一种低码率的视频编码标准，码率可达H.261的一半，是对H.261标准的很好的改进。它仍然以MC/DCT为核心算法，与H.261不同的是，它采用半像素精度进行运动补偿，传送的符号采用变长编码。除了这些基本编码算法外，H.263还包括下面四个可选的编码方法。所有这些算法可以通过某种组合使用，也可以单独使用。
1.无约束运动矢量模式；2. 基于句法的算术编码模式；3. 先进预测模式；4.PB帧模式。
2．3．4 运动图像压缩标准MPEG系列
为适应有声音的运动图像压缩的需要，1988年5月，CCITT和ISO成立了“运动图像专家组”（Motion Picture Experts Group），致力于有关运动图像的编码标准。MPEG对运动图像的帧内编码技术中采用了JPEG推荐的DCT技术，此外MPEG又引入了帧间MC技术，因此可认为MPEG的工作是JPEG的延续，同时尽量与H.261标准兼容，但比H.261要复杂的多。MPEG标准包括MPEG视频、MPEG音频和MPEG系统三个部分。它采用了MC、DCT、可变长编码（VLC）等多种技术。
MPEG－1标准于1993年8月正式通过，用于对连续传送码率为1.5Mbits/s存储和传输媒体进行操作，CD、硬盘和光盘驱动器；
MPEG－2标准于1994年编译出版，其码率在3～10Mbits/s之间，应用范围更加广泛，如数字电视、数字通信、其他数字媒体等。
MPEG－4与前面提到的JPEG、MPEG－1、MPEG－2有很大的不同，它为多媒体数据压缩编码提供了更为广阔的平台，它定义的是一种格式、一种框架，而不是具体的算法。MPEG的目标为：支持多种多媒体的应用，特别是多媒体信息基于内容的检索和访问，可根据不同的应用需求，现场配置解码器。编码系统也是开放的，可随时加入新的高效的算法模块。
MPEG－7将确定各种类型的多媒体信息的标准描述方法。可应用于数字图书馆、各种多媒体目录服务、广播媒体的选择，以及多媒体编辑等领域。
2．4 本章小结
本章介绍了图像压缩的必要性，压缩的评判指标，图像压缩的可能性，基本原理与技术分类，以及相关的国际标准。
可以看出，图像的压缩有多种方法，并已经形成了一些国际标准，但发展新的技术还是必要的，因为数据增长的速度极快，现有的方法也远非完美。对于将要研究的变换编码压缩，KL变换，将在下一章详细介绍。

第三章变换编码与KL变换
3．1 变换编码与图像压缩
3．1．1正交变换与消除相关性
用统计学方法描述图像，各分量之间的相关性将会大大增加图像生成和图像处理过程中的误差，有效消除这些相关性是一个基本的任务。也就是说，我们应该设法将协方差矩阵的非对称元素化为零元素，就是设法将协方差矩阵对角化[2]。
线性代数证明，对于一个实对称矩阵Σ（Σ＝ΣT），必存在一个正交矩阵Q，使得
(3.1）
其中对角矩阵Λ中的λ1,λ2,…λN是实对角矩阵Σ的N个特征根。这给我们一个重要启示：
通过正交变换能够将协方差矩阵（实对称矩阵）Σ对角化，从而消除图像的相关性。
通过正交矩阵T对向量X 作正交变换Y ＝TX
证： Y的协方差矩阵定义为：
，
那么Y的协方差矩阵ΣY为：
（3.2）
其中T为正交矩阵；ΣX为实对称矩阵。表明：
向量X通过正交变换后的向量Y的协方差矩阵为λ的对角矩阵，说明向量X的分量间的相关性已被消除，即正交变换能消除存在相关性的冗余度，这是采用正交变换消除图像相关性的一个数学依据[3]。
3．1．2 图像数据压缩和变换编码
这里的变换编码主要指正交变换。基本思想：将空间域里表述的图像经过某种正交函数变换，转换为能量比较集中的变换域中，然后对变换系数进行编码，从而达到缩减比特率的目的。
变换编码之所以能够压缩信息的比特数，是因为经过正交变换得到的系数矩阵中，数值较大的方差总是集中在少数系数中。多数图像的统计特性表明，大幅度的系数往往集中在低频率区内，这样，可以给那些较小的系数分配很少的比特数，甚至可以不予传送，从而压缩了传送数据的比特数。因此，正交变换本身只是把分布在变换域中的信息变得集中起来，为合理少分配给某些数据比特数提供了可能[4]。
变换编码工作流程：

图3.1 变换编码工作流程
变换编码过程主要有两个阶段：变换和量化。经过变换处理，将原始数据从一个空间变换到另一个空间，使图像中相邻像素、相邻扫描行间的数据的相关性变小，同时使图像数据在变换域中相对较为集中，以有利于进行下一步的量化在进行量化之后，便进一步达到了数据压缩的目的。
3．1．3 变换编码的数理概念
假如变换矩阵是归一化正交变换矩阵，经过变换之后，空间域中的总能量在变换域中得到保持，即满足：
（3.3）
式中f2（m，n）为空间域矩阵中元素，F2（i，j）为变换域矩阵中元素。上式是离散正交变换中的Parseval能量保持定理。其意义在于：空间域中能量全部转移到变换域中，而在反变换中，变换中的能量又能全部转换到空间域中。但是，在变换过程中，保持不变的能量会重新分布。在空间域中，能量的分布有一定的随机性，对于相关图像来说，在大多数情况下，变换域中能量集中于零空间频率或低空间频率对应的变换系数上。
这样，经过变换之后，使图像的相关性减少，在新的变换域中，经过选择适当的量化方法，便可以达到压缩数据的目的。
3．2 KL变换基础
KL变换是一种基于特征向量(Eigenvectors)的离散正交变换[2]。
3．2．1 KL变换的概念
一特征值（Eigenvalues）
对N*N的矩阵A，有N个标量，＝1，2，…，N，能使
，（3.4）
则称为矩阵A的特征值；
：单位矩阵
特征值：当矩阵的每个对角元素都减去它时，将变成奇异阵（不存在逆的矩阵）。如果给定矩阵是奇异的，那么N个特征值中至少有一个是0。
二特征向量（Eigenvectors）
设每个是N*1维的，通过满足
（3.5）
对应一个特征值，则称其为A的特征向量。N个这样的特征向量构成一个正交基集。
如果A是实对称矩阵，那么也是实数。
三一维KL变换
定义一个线性变换A，它可由任何X向量产生一个新向量Y：
，（3.6）
这里为由L个样本向量估计的均值向量。这就是KL变换的变换式。理解：变换后的图像是由中心化向量与变换矩阵A相乘。
A的构成法：由的特征向量，＝1，2，…N构成A的行向量，按相应特征值幅值大小的顺序排列各行：即取A的第一行为对应最大特征值的特征向量，A的最后一行为对应最小特征值的特向量。
3．2．2 KL变换的性质
1.Y的均值。即变换后的图像向量是期望值为零的随机向量。
2.Y向量的协方差矩阵为。
3. 协方差矩阵是对角型矩阵。
，（3.7）
为对角矩阵，特征值即沿着特征向量方向上Y的第i个元素的方差。
上式主对角线上以外的元素为0，即y向量的各元素是不相关的，也就是说，随机向量Y是由互不相关的随机变量组成的。因此，线性变换A起到了消除变量间相关性的作用。即每个都是变换后第i个变量的方差。
4. 能量集中特性
这里所指的能量集中特性是对n 维矢量信号进行K-L 变换后，最大的方差将集中在前m个分量之中的这样一种特性(m < n)。
3．2．3 KL变换的应用
自KL变换提出以来，学者们对其应用做了一些有益的探索。清华大学的研究人员提出了Karhunen—Loeve变换在语音识别中的应用。特征提取与选择是语音识别中一个非常重要的环节。好的特征，既可以具有很高的模式区分能力，又可以节省大量的存储空间，起到很好的数据压缩作用。目前在语音识别中主要采用基于线性预测分析 (LPC)技术得到的倒谱系数或基于 Mel-Scale的 MFcc系数 (Mel频率刻度倒谱系数)，然后辅之以能量和过零率等其它特征参数。而他们提出在特征提取阶段利用帧间相关性的一种方法．对每一帧考虑其前后各n帧，加上自身帧共 2n+l帧的特征矢量串起来组合成—个大的特征矢量串。对这个大的特征矢量串用Karhunen-Loeve变换进行降维处理．将变换后的数据作为本帧的特征矢量用于后续的训练和识别。在基于 CDCPM的语音识别系统中采用这种方法进行了音节的训练和识别。实验结果表明Karhunen-Loeve变换在考虑帧间相关性的特征提取阶段上表现了良好的效果，有着很广阔的应用前景[5]。中国科学院长春光学精密机械研究所的学者则提出了一种基于KL变换的三维谱象数据压缩方法。该方法将原始谱象分成若干子块，对每一子块使用去相关性效果最佳的KL变换，去除谱象数据空间相关性。实验结果表明, 经KL变换后，若不编码, 可获得3～5倍的准无损压缩。经JPEG编码后, 压缩比可达100倍以上。且峰值信噪比大于34.0dB[6]。美国的Gabriel Fernandez，Craig M.Wittenbrink也把基于幅度的KL变换用于多光谱图像压缩，他们在更好的压缩率下得到了比典型KL变换更小的失真[7]。
中南林学院的陈爱斌提出了一种基于KL变换的汽车车型的识别方法。先对车辆图像进行预处理，然后通过KL变换构造特征车，将样本投影到特征车子空间，得到的投影系数即为待识别车型的代数特征。最后利用 K近邻法进行车型识别。实验结果表明了文中提出的车辆识别方法是简便、快捷、有效的[8]。
KL(Karhunen—Loeve)变换是一种二维酉变换。理论上，二维酉变换在图像处理中有3种主要功能：第一，从图像中提取特征；第二，图像变换编码；第三，减少计算维数。这些功能在数字图像处理和遥感多图像变换组合分析中得到了成功的应用。KL变换是遥感图像增强和信息提取中用得最多的线性变换，是对原波段图像进行波谱信息的线性投影变换，在尽可能不减少信息量的前提下，将原图像的高维多光谱空间的像元亮度值投影到新的低维空间，减少特征空间维数，达到数据压缩、提高信噪比、提取相关信息、降维处理和提取原图像特征信息的目的，并能有效地提取影像信息。它可使原来多波段图像经变换后提供出一组不相关的图像变量，最前面的主分量具有较大的方差，包含了原始影像的主要信息，所以要集中表达信息，突出图像的某些细部特征，可采用主分量变换来完成。KL变换的最大优点是去相关性好,可用于数据压缩和图像旋转[9]。KL变换最复杂，时间，空间开销大，变换域中能力最集中，集中到少数几个变换系数上，编码效率最高，误差最小。 K-L 不具有二维分离特性，离散余弦变换性能与其相似。KL变换的缺点是计算过程复杂，变换速度慢。无快速算法而难以实现。但其具有最佳性能。因此，KL变换常常作为其他变换性能的评价标准。
目前，KL变换主要还是用于图像特征处理，比如指纹的识别，遥感图像的提取等。尽管本课题研究的是其用于数据压缩，但实际工程中通常不采用该方法。
3．3 各种变换编码的性能比较
对各种变换编码技术已有了初步的比较[4]：
1. 离散傅立叶变换（DFT）
离散傅立叶变换不对图像本身编码，只对变换系数进行编码和传输，具有蝶型快速算法，但其运算量大，实际使用有问题。
2. 沃尔什－哈达玛变换（WHT）
可取代DFT，使运算量明显降低，这是因为WHT具有DFT的快速算法结构，且只有加减法运算而无乘法。但实践证明经WHT变换后，能量集中程度不如DFT。
3．哈尔变换（HRT）
具有比WHT更快的运算速度，但其能量集中程度WHT更差。
4. 离散余弦变换（DCT）
运算速度较快（有快速算法），而且经DCT后能量集中性仅次于KLT，对于大多数相关性很强的图像数据，DCT是KLT目前最好的替代。
5. KL变换
能量集中性最好。
6. 斜变换（ＳＬＴ）
奇异值分解最佳坐标展开变换（SVD）。

按变换后数据的可压缩性，在变换域中信源能量集中程度排序（从优至劣）：
KLT－DCT－SLT－DFT－WHT－HRT
按算法的简单复杂程度排序（由简至繁）：
HRT－WHT－SLT－DCT－DFT－KLT
按变换运算量大小排序（由小至大）：
HRT－WHT－SLT－DCT－DFT－KLT
3．4 本章小结
本章介绍了变换编码用于图像压缩的基本原理，工作流程，KL变换的概念，性质与应用。最后还对各种变换编码技术做了简单的比较。这样，为下面引入基于KL变换的图像压缩做了技术上的铺垫。
可以看出，变换编码技术是相当有效的图像压缩方法，其中KL变换实现图像压缩较为困难，往往用于图像识别等其他领域，但为了利用其对其他变换作出评判，研究其用于图像压缩也有一定意义。

第四章基于KL变换的图像压缩算法研究
4．1 基于KL变换的图像压缩基本思想
4．1．1图像的KL变换
假定一幅图像N*N的数字图像通过某一信号通道传输了 M 次，由于受随机噪声干扰和环境条件影响，接受到的图像实际上是一个受噪声干扰的数字图像集合
，
对第i次获得的图像，可用一个含N2个元素的向量Xi表示，即
，（4.1）
该向量的第一组分量（N个元素）由图像的第一行像素（N个）组成，接下来是第二行像素组成向量的第二组分量，余类推。亦可按列的方式形成这种向量。
同样，对于M幅数字图像，平均值和协方差矩阵可由下面方法求得：
，（4.2）
是个元素的向量
，（4.3）
的方阵。
假定是按递减顺序排列的特征值，即，对应特征向量为
，（4.4）
定义KL变换矩阵A为
，（4.5）
可得KL变换的变换表达式
，（4.6）
理解为：由中心化图像向量与变换矩阵A相乘，可得变换后的图像Y。由于协方差矩阵ΣX是实对称矩阵，由线性代数理论知，，故由KL变换式可得KL反变换式
（4.7）
4．1．2 KL变换用于图像数据压缩
如前所述，KL变换矩阵A是由特征向量组成的变换矩阵，而且这些特征向量的排列是按特征值递减顺序排列的。由于能量集中在特征值λ大的系数中，因此我们丢掉特征值小的Y系数，不应影响图像质量。
设我们取λ最大的前K个特征向量组成的变换核矩阵，记做Ak，有
（4.8）
这相当于原Y的K维投影，记做Y’。在反变换重建图像向量X时，可采用补零方法。仍补成N*N维向量
，（4.9）
这显然会带来误差。所重建的图像只能叫原X的估计值：
（4.10）
总之，由于我们只丢掉较小的Y系数，故引入较小的误差。可以证明[10]，引入的误差为：
（4.11）
其中λi为协方差ΣX的特征值。因为λi是按大小顺序排列的，因而k+1至N2的λi是非常小的。而且，λi之间数值差异非常之大。这样丢掉特征值小的基向量做变换，引起误差的百分数小。另外，因为对于实际图像集合而言，做KL变换必须求得这个集合的N2*N2的协方差矩阵的特征值与特征向量，计算量非常之大。但由于KL 变换矩阵是不可分离的，所以至今还没有找到一种成熟的快速算法，这就限制了使用。
4．2 基于KL变换的图像压缩基本算法
由上面的基本思想，我们可以得出基于KL变换的图像压缩基本算法如下：
一图像分块
这里一般是把图像分成一系列不重叠的特定尺寸的如8*8的子图像块，然后对每个块，一排排地级联成64×1向量。
二构建协方差矩阵，求出特征值与特征向量
收集所有这些级联向量构建所需要的协方差矩阵，求出其特征值和相应的特征向量。
三进行KL变换
对每个子图像块，已经求出了特征值与特征向量。按特征值递减的顺序排列特征向量构建变换矩阵。能量已经集中在特征值大的向量中，此时丢弃特征值小的特征向量，取特征值最大的前K个向量组成的变换核矩阵，进行KL变换。
四量化编码
这里若需要传输，则需要量化编码。对KL变换后得到的数据量化编码。在KL变换时，丢弃了特征值小的特征向量，因此实现了数据压缩。
五解码
接收方需要对接收到的数据进行解码。
六进行KL反变换重构图像
反变换重建图像时，对丢弃的数据补零，仍构成64×1向量。这样可以恢复出近似原图像的图像，实现了压缩。
补充：对于四、五两个步骤，若不需要传输图像可以省略。实际上，四、五两步还可以实现进一步的压缩。比如采取特殊的编码如游程编码，Huffman编码等。
4．3 基于KL变换的图像压缩的改进算法
传统的算法里，Karhunen-Loeve变换（KLT）很难被使用在图像压缩中，原因是由于它们求解从给定的训练数据中构建的协方差矩阵变换很慢[11]。协方差矩阵的规模或维数越大，计算特征向量的速度就越慢，因此变换越慢。然后表现为压缩编码或变换就越慢。为了缓和这个问题，通常采取两种方法。第一种是用离散余弦变换（DCT）代替KL变换就像JPEG标准中那样[12]。尽管能得到比KLT更快的压缩速度，DCT导致了与KLT比起来在相同压缩比率下相对更大的压缩质量降低。第二种方法是使用相似的技术[13][14]比如神经网络包括关联记忆[15]和自适应主要成分提取（APEX）。尽管是一种强大的相似方法，神经网络也必须在压缩速度和质量之间权衡。
而这里的改进算法由南京航空航天大学的Daoqiang Zhang, Songcan Chen两人提出，对传统的KL变换提出以一种新型的矩阵KL变换扩展，对18幅广泛采用的基准图像的实验结果表明，矩阵KL变换在相似的压缩质量下，可以比传统KL变换压缩速度提高数十至上百倍[11]。
主要思想在于减少原始KLT的协方差矩阵规模。直接用一个矩阵型而不是向量型表示法来构建协方差矩阵，称之为推广协方差矩阵（GCM）。因此它的规模要小于那些由级联向量构建的协方差矩阵。拿一个级联成n维向量的图像块为例，KLT的协方差矩阵规模是n*n,而推广协方差矩阵的规模只有m*m，此时它由m*p维矩阵构建，是n维向量的重新排列，这里m*p=n。显然每个规模的降低率达到了p2，当p很大时会是一个令人印象深刻的结果。
矩阵KL变换由两个主要步骤。第一步是“重新装配或重新排列”，该步把一个子图像块向量组件重新排列成一个新的m*p维的矩阵，它直接用子图像块矩阵作为一种特殊情况从而变得更灵活。第二步是把第一步中得到的矩阵表示为矩阵KLT。
最后重建图像。Daoqiang Zhang和Songcan Chen证明了矩阵KL变换同样可以去掉图像的相关性来达到压缩的目的。而且实现的速度较传统KL变换大为提高。
4．4 本章小结
在这一章里讨论了基于KL变换的图像压缩的基本算法。显然，由于KL变换没有快速算法，求特征值、特征向量困难，用其实现图像压缩较为困难，实际中压缩图像也基本不采用KL变换算法。但实现它的现实意义在于其是失真最小的变换，经常需要用它对其他变换做为评判标准。上面提到的改进算法实际上是对KL变换做了改进，但其还不不成熟，尚未得到广泛认可。

第五章基于KL变换的图像压缩的软件实现
本设计要实现的目标是完成一个基本的基于KL变换的图像压缩程序，这里采用KL变换的基本算法实现。
5．1 开发程序与环境
在本课题中，实现的程序运行于windows系统下(windows 2000/XP等)，使用Visual C++开发。Visual C++是Microsft公司推出的一种高度综合性能的开发Win32环境程序，面向对象的可视化集成编程系统。用它开发的程序有着运行速度快、可移植能力强等特点。由于Visual C++本身就是一个图形的开发界面，它提供了丰富的关于位图操作的函数，对开发图像处理系统提供了极大的方便。因此，它现在已经成为开发win32程序，包括图像处理程序的主要开发工具。
5．2 功能描述
在前面已经提到KL变换无快速算法。因此这里设计的功能将比较基础。比如，简单的压缩设置：仅有固定压缩比，固定的图像类型等。
具体功能如下：
一可以对256*256的灰度bmp图像进行基于KL变换的压缩；
二可以选择固定的几个压缩比（1：2，1：4，1：8，1：16，1：32，1：64，1：128，1：256）；
三可以在界面中对比显示压缩前与压缩后的图像；
四自动在被压缩图像所在的文件夹中生成compic压缩文件和重建的bmp图像文件；
五若打开的图像不是256*256的bmp图像，则会弹出对话框提示。
5．3 模块设计
本程序主要由主界面模块（由Visual C＋＋自动生成），读取图像模块，KL变换模块，量化编码模块，KL反变换模块，图像重建模块，显示模块构成。
图像依次经过各个模块处理，完成压缩过程。

图5.1 程序模块
主界面模块：
由Visual C++系统自动生成。建立程序时，选择MFC AppWizard [exe],名称为KLT，在菜单中添加“选择压缩比”栏，系统即可自动生成主界面如下图：

图5.2 程序界面
建立的这个界面只是一个框架，其本身无任何处理功能。
读取图像模块：
此模块作用仅为实现256*256位图的读取。这里要注意的是，由于简化设计的考虑，设置的是仅对256*256的灰度位图读取。若不符合要求，自动提示。

KL变换模块：
这是比较核心的模块。这里对读入的图像进行主要的运算－KL变换。
具体步骤：对读入图像分块，求协方差矩阵，求特征值、特征向量，用特征向量矩阵与原始图像数据相乘，得到的结果即为变换后数据。
各个函数如下：
Vec = (double*)malloc(PICSIZE*sizeof(double));
buffer = (double**)malloc(PICSIZE*sizeof(double*));
temp = (double**)malloc(PICSIZE*sizeof(double*));
sort(a, v); //将特征值与特征向量按照由大到小的顺序排序
//特征值与特征向量排序
void CKLTDoc::sort(double* a, double* v)
transpose(v); //特征向量矩阵转置
//矩阵转置
void CKLTDoc::transpose(double* array)
Multiply(v, array); //特征向量矩阵与原始图像数据相乘，得到的结果即为变换後数据，保存在array中
函数及部分参数说明：
//求实对称矩阵的特征值及特征向量的雅格比法
//利用雅格比(Jacobi)方法求实对称矩阵的全部特征值及特征向量
//返回值小于0表示超过迭代jt次仍未达到精度要求
//返回值大于0表示正常返回
//a-长度为n*n的数组，存放实对称矩阵，返回时对角线存放n个特征值
//n-矩阵的阶数
//u-长度为n*n的数组，返回特征向量(按列存储)
//eps-控制精度要求
//jt-整型变量，控制最大迭代次数

量化编码模块：
这是实现压缩的部分。在这里按压缩比把KL变换后数据中由特征值小的部分生成的数据丢弃，并把剩余数据写成compic文件，即生成的压缩文件。
代码如下：
//数据压缩
void CKLTDoc::compress(double** array)
{
int tmp = PICSIZE/comRate;

int i, j;

for(i = tmp + 1; i < PICSIZE; i++)
{
for(j = 0; j < PICSIZE; j++)
{
array[i][j]=0;
}
}

//将压缩後的数据写文件
FILE* fp;
fp = fopen(“compic”, “wb”);
for(i = 0; i < tmp + 1; i++)
{
for(j = 0; j < PICSIZE; j++)
{
unsigned char tempdata = (Byte)array[i][j];
fwrite(&tempdata,sizeof(tempdata),1,fp);
}
}
fclose(fp);
}

KL反变换模块：
把丢弃的数据补零，然后把与前面KL变换后生成的数据一起做KL反变换。反变换是重建的基础。
代码如下：
void CKLTDoc::IKLT(double* a, double* v, double** buffer)
{
transpose(v);
Multiply(v, buffer);
}

图像重建模块：
重建bmp图像。因为这里补的是零，所以肯定带来了误差。所以重建图像是不可能与原图一致的。这也就是有损压缩。
实现代码：
//将KLT反变换后的数据写成一个bmp文件
FILE* fp = fopen(“stuff.bmp”, “wb”);
fwrite(&MyBmp,sizeof(MyBmp),sizeof(unsigned char),fp);
fclose(fp);

for(i=0;i {
for(j=0;j {
MyBmp.Pix[i][j]=ppbImage[i][j];

}
}

显示模块：
把原图像和重建图像显示在界面中，效果如下（这里压缩率为1：16）：

图5.3 显示效果
5．4 程序流程图
一主程序流程图

图5.5 主程序流程图

二 KL变换模块实现过程图
这里是该模块的实现过程图，并没有对其中每个函数写出具体的流程。比如，图像分块、求协方差矩阵、求特征值与特征向量都是比较复杂的运算过程。这里仅指出该步骤。

图5.6 KL模块实现过程
5．5 实验结果
5．5．1 实际实验
实验环境为Windows XP 系统，Athlon 3000＋的处理器，512M的内存。
这里将展示基于KL变换的图像数据压缩程序的实际效果。所用测试图片为“lena”，它是18幅广泛使用的基准测试图像之一。
首先，打开程序后选择压缩比（这里压缩比例的含义代表压缩后图像大小与原图像大小之比），若不设置，则默认为1：8。选择“操作”，在“压缩比例”中选择压缩比，如下图所示：

图5.7 设置压缩比
确定后打开图像，这里的图像必须是256*256的灰度bmp图像，否则，弹出警告对话框如下：

图 5.8 提示对话框
下面是实际效果。
一压缩比为1：2。此时原图与压缩后的图片效果如下：

图5.9 1：2压缩对比
原图大小为65.0KB，形成的压缩文件compic为32.2KB。
可以看出质量很好，重建图像仅有少量失真。但必须提到的是，执行速度较慢。
二压缩比为1：4
此时压缩比提高了一倍，下面是结果。

图5.10 1：4压缩对比
此时形成的压缩文件compic为16.2KB。
可以看出，重建图像失真明显比压缩比为1：2时大。
三设置压缩比为1：16
再次提高了两倍压缩比，结果如下：

图5.11 1：16压缩对比
此时形成的压缩文件compic为4.25KB。
此时的重建图像已经基本不能接受。
其他压缩比不需再一一列举，总之，compic文件的大小体现了压缩程度，而且压缩比越大恢复图像效果越差也是在意料之中。
实际压缩时，由于KL变换无快速算法，程序运行时间较长。这也是KL变换在实际压缩中得不到采用的原因。
5．5．2 实验结果分析
程序基本实现了预计的功能：可以对符合要求的图像进行指定压缩比的压缩，形成压缩文件，可以重建图像。
不足：由于KL变换实现较为复杂，故这里为了简化设计起见设计为只能对256*256的灰度bmp图像进行压缩。压缩进度不能实时显示。不能设置任意压缩比，只有固定的压缩比。若要改进程序，可以在以上几个方面着手。
方法评价：图像在1：2压缩比时，重建质量比较令人满意，在主观度量上，可以达到“良好”，1：4时则只能说“可用”，更高压缩比时只能达到“刚可看”及以下了。编码效率方面，在1：4的压缩比时，重建图像还可以达到“可用”，可以看出效率比较高。算法运算量方面，KL变换无快速算法，运算量很大，程序运行时，要等待的时间较长。
因此，基于KL变换的压缩往往不能用于实际工程实践中，但其效果在变换编码中属于最佳，可以用于对其他变换方法的评价。
第六章总结与展望
随着信息社会的发展，图像压缩技术越来越重要。包括变换编码压缩在内的各种技术也在不断发展。下面给出本研究课题的结论。
6．1 工作总结
在本文中，探讨了图像压缩的基本技术，评价方法，相关的国际标准，研究了变换编码技术，对其中的基于KL变换的图像压缩做了深入的算法研究与实际实现。通过具体的编程，检验了压缩的效果。可以看出，KL变换在比较高的压缩比下还有相对较好的重建效果。但是，正因为其算法复杂，实现的速度还是很慢的。当选择较大的压缩比时，要等待很长时间。这是其最大的不足，造成了它的不能实用。
尽管在文中提到了其改进算法，但事实上这个算法尚未得到广泛认可，因此还需要进一步的检验。
总之，基于KL变换的图像压缩目前还只能作为其他压缩算法的评判，若想实际应用，必须提出新的高效率改进算法。
6．2 未来研究方向
对于KL变换技术来说，由于其复杂性与实现的困难性，只能找到其他的变换来代替它，这个变换目前是DCT，但未来可以找到更好的变换，这是一个研究方向。但从KL变换本身着手，改进其算法也是一条可行之路，只不过目前看来也相当困难。文中也提到采用相似的技术比如神经网络包括关联记忆和自适应主要成分提取（APEX），从这方面也可以继续研究。
图像压缩技术是不断发展的，相信基于KL变换的压缩技术或有与其效果相似乃至更好的技术一定会出现。

参考文献
[1] 吴乐南.数据压缩[M].北京:电子工业出版社,2000.94,99.
[2] 黄贤武等. 数字图像处理与压缩编码技术[M].成都: 电子科技大学出版社,2000.30-66.
[3] 章毓晋. 图像工程(上) [M].北京:清华大学出版社,1999.43-70.
[4] 刘榴娣,刘明奇,党长民. 实用数字图像处理[M].北京：北京理工大学出版社，2001.62－86.
[5] 郭庆,吴文虎,方棣棠.Karhunen-Loeve变换在语音识别中的应用[J].模式识别与人工智能,1998,11(4),396-402.
[6] 孙辉. 采用KL变换的三维谱象数据压缩方法[N]. 长春邮电学院学报,1999,17(1),5-8,12.
[7] Gabriel Fernandez，Craig M.Wittenbrink. REGION BASED KLT FOR MULTISPECTRAL IMAGE COMPRESSION[Z].
[8] 陈爱斌. 基于KL变换的汽车车型的识别方法[N]. 中南林学院学报,2004,24(2),111-113.
[9] 高守传,姚领田等 Visual C++实践与提高－数字图像处理与工程应用篇[M].北京:中国铁道出版社,2006.202-205.
[10] 容观澳. 计算机图像处理[M]. 北京:清华大学出版社,2000.101-102.
[11] Daoqiang Zhang, Songcan Chen. Fast image compression using matrix KL transform [Z].
[12] R.C.Gonzalez,R.E.Woods,Digital Image Processing,2nd Edition,Prentice Hall,Jan.2002
[13] S.Bhama,H.Singh,N.D.Phadte,”Parallelism for the faster implemention of the K-L transform for image compression”,Pattern Recognition Letters,vol.14,pp.651-659,Aug,1993.
[14] S.Costa,S.Fiori,”Image compression using principal component neural networks”,Image and Vision Computing,Vol.19,pp.649-668,Aug.2001.
[15] C.C.Wang,C.R.Tsai,”Data compression by the recursive algorithm of exponential bidirectional associative memory”,IEEE Trans.Syst.Man.Cybern.
,vol.28,no.4,pp.125-134,Apr.1998.

Turbo码的性能研究及仿真实现

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 18-08-2009

标签：Log－MAP, SOVA, Turbo码, 信道, 算法, 纠错编码

0

1.毕业论文（设计）内容要求：
Turbo 码是一种非常复杂的信道编码方案，又称并行级联卷积码( PCCC) ，它巧妙地将卷积码和交织器结合在一起，在实现随机编码思想的同时，通过交织器实现了由短码构造长码的方法，并采用软输出迭代译码来逼近最大似然译码。目前对Turbo 码的理论分析十分困难，因此, 就需要使用计算机对系统进行仿真分析。
本次设计要求先对Turbo 码进行性能分析，并利用仿真工具（如Matlab）对Turbo 码进行系统仿真。仿真要求实现对信源、编码器、信道、译码器、信宿五大子系统的仿真，并完成整个系统的仿真，要求得到不同交织器大小、不同信道下、不同译码算法时系统性能的仿真曲线图。

[1]题目类型：(1)理论研究(2)实验研究(3)工程设计(4)工程技术研究(5)软件开发
[2]题目来源：(1)教师科研题(2)生产实际题(3)其它

2.主要参考资料
（1）黄智伟.无线发射与接收电路设计 .北京: 北京航空航天大学出版社，2004
（2）袁东风等.宽带移动通信中的先进信道编码技术.北京: 北京邮电大学出版社，2004
（3）徐明远, 邵玉斌. MATLAB仿真在通信与电子工程中的应用. 西安: 西安电子科技大学出版社，2005
（4）邓华.MATLAB通信仿真及应用实例详解. 北京: 人民邮电出版社，2003
（5）周金萍等.MATLAB6实践与提高.北京：中国电力出版社，2002

摘　要 V
Abstract VI
第一章绪论 1
1.1 研究的目的和意义 1
1.2 国内外研究现状及发展 1
1.3 Turbo码的研究展望 2
1.4 要求及内容安排 3
第二章 Turbo码的编译码原理 4
2.1 Turbo码的编码器 4
2.2　Turbo码子码和交织器 5
2.2.1 子码的选择 6
2.2.2 交织器 6
2.3 Turbo码的译码组成 7
2.4 Turbo码的基本算法 8
2.4.1 译码算法分析 8
2.4.2 译码算法比较 9
2. 迭代次数对译码性能的影响。 9
3. 帧长对译码性能的影响。仿真环境参数为: 9
第三章 Turbo码的设计及模块方案 10
3.1 Turbo码的设计 10
3.1.1.RSC编码器生成元的设计 10
3.1.2.迭代次数 10
3.1.3.交织长度的选择 10
3.1.4.交织算法 10
3.2 模块方案 10
3.2.1 设计总流程 10
3.2.2 模块说明 11
3.2.3 简要说明 13
第四章 Turbo码的仿真实现及分析 14
4.1 Turbo码的仿真环境及设置 14
4.1.1 仿真环境 14
4.1.2 仿真设置 14
4.2 Turbo码仿真系统结构 15
4.3 Turbo_system主程序流程图 16
4.3.1 信源的产生: 17
4.3.2 交织器的生成: 17
4.3.3 调用编码模块 : 17
4.3.4 模拟信道: 17
4.3.5 调用相应译码模块: 17
4.3.6 输出结果: 17
4.4 LOG-MAP分量译码器Singlewindow 19
4.5 LOG-MAP分量译码器doublewindows 20
4.6 SOVA分量译码器的程序模块 21
4.7 仿真结果分析 22
4.7.1 几种主要译码算法的性能比较 22
4.7.2 不同的交织器大小对性能的影响 22
第五章结论和展望 24
致谢 25
参考文献 26
附录 27

摘　要

纠错编码技术作为改善数字通信可靠性的一种有效手段,在数字通信的各个领域中获得极为广泛的应用,其主要分为卷积码、分组码。Turbo码是并行级联递归系统卷积码，是在过去20年中信道编码方面最令人激动的事情之一。他在接近Shannon 限的低信噪比下能获得较低的误码率。
因为其优越的性能,现在已经被许多通信系统所采用。就近年来的研究热点纠错编码Turbo码进行分析,旨在阐明Turbo码的基本原理和各参数对Turbo码纠错性能的影响。
本文首先回顾了信道编码学科发展历史，介绍了Turbo码的研究现状及基本特点，分析了Turbo码编译码结构和基本原理，比较了常用Turbo译码算法的性能和复杂度。指出Turbo码在信号很弱或在干扰信号较强时,能够准确地还原信号,已成为以大容量、高数据率和承载多媒体业务为目的的第3 代移动通信的信道编码方案之一。
接着，讨论了Turbo码的设计，并使用MATLAB进行了编程仿真，通过Turbo码在不同交织器大小、不同信道下、不同译码算法等情况下，来分析这些参数对Turbo码性能的影响，以便选择更为合理的参数以提高Turbo码的性能。仿真结果表明,在低信噪比的无线衰落信道中, Turbo码不仅可以获得更大的编码增益,有效地改善系统的性能，而且具有很强的抗衰弱、抗干扰能力，有很大的应用潜力。

关键词: 纠错编码,Turbo码,Log－MAP,算法,SOVA, 算法,信道

Abstract

The technology of error correcting code is an efficient way for improving the reliability of the digital communication systems. It obtains the extremely widespread application in each domain of the digital communication, and it is classified into convolutional code and block code. Turbo code is the parallel concatenated convolutional code. They can gain lower Bit Error Rate (BER) in the low Signal Noise Rate (SNR) which is near Shannon limit. Because of the predominant performance, they have been adopted in the many communication systems. This paper analyzes the technology of error correcting code (Turbo code), which is becoming more and more popular in recent years. Its aim is to clarify the basic principle of Turbo code and influence of various parameters on its performance.
A novel channel coding scheme called Turbo codes, is one of the most exciting channel coding schemes introduced in the last two decades.
Firstly, this paper reviews the history of channel code and presents the status ofTurbo Codes, recommends the code-decode structure and basic principle of Turbo
Codes. Some decoding algorithm of Turbo codes in common use are compared in their capability and complexity. It is pointed that Turbo code can accurately decode and recover the signal under weak signal or strong noise. The Turbo code has become the criterion one of the channel codes in 3Gwith advantages such as large capacity, high data ratio and multimedia task.
Secondly, this paper discusses some design issue of Turbo Codes. By programming emulator, transmission of Turbo Codes is simulated with different parameters, such as interweave length, different algorithms, different fading channels etc, which can help us to analyze and choose the right parameters to improve its capability. the simulation result that shows turbo code can achieve more and more coding gain, turbo code has better performance in fading channel and more extensive application.

Keywords: turbo codes, log-map algorithm, sova algorithm, iterative decoding, fading channel

第一章绪论

1.1 研究的目的和意义

纠错编码是数字通信系统和计算机系统的重要组成部分。1948年,现代信息论的奠基人C. E. Shannon在他的开创性论文《通信的数学理论》 (A Mathematical Theory of Communication)中首次阐明了在有噪信道中实现可靠通信的方法, 提出了著名的有噪信道编码定理，奠定了差错控制码的基石。
如今,纠错码已经成为现代通信领域中不可或缺的一项标准技术。现代通信系统的复杂化以及通信业务的多样化,要求通信系统能够对话音、数据以及图像等大数据量信息实现高速实时传输,而且用户对通信质量的要求也日趋提高；移动通信的快速发展以及个人通信的全球化,使得对高数据率数字移动通信等领域所采用的纠错编码技术要求也越来越高。
人们为了在有噪情况下进行有效的差错控制,对纠错编码译码进行了大量的研究。但是他们所实现的系统性能始终和Shannon极限有一定的差距。因此,编码理论和方法研究人员一直认为信道截止速率是差错控制码性能的实际极限,Shannon极限是不可能达到的。在1993年的国际通信会议上C. Berrou, A.Glavieux提出的Turbo码方案很好地应用了Shannon信道编码定理中的随机性编译码条件而获得了几乎接近Shannon理论极限的译码性能。Turbo码的出现在编码理论界引起了轰动,成为自信息论提出以来最重大的研究进展。同Shannon极限仅仅相差0.17dB 。由于Turbo码接近Shannon极限的性能, 所以研究它的特性有很大的实用价值和经济效益。

1.2 国内外研究现状及发展

Turbo码提出两年之内就被首次硬件芯片实现，并一直受到理论研究者和实验科学家的重视。从1997年开始，Turbo码和相关主题的国际会议每隔三年举行一次。
第一次会议（1997年）主要议题集中在编码器串并设计、交织器设计、解码器算法上，当时已经有人提出用DSP进行实时Turbo解码。在这个会议前后已经有了最早采用Turbo码的商用通信系统。
第二次会议（2000年）的主要内容在分析和提高Turbo码的性能上，并且出现了关于Turbo码在衰落信道等非高斯信道上的研究。也有不少的研究在为实现Turbo码的DSP解码而需要做的简化解码复杂度的问题。对于Turbo码在传送不同信源的研究也在逐步进行中。
第三次会议（2003年）时，Turbo码和其他相关通信技术的结合与应用被更多的关注，多用户检测、与BLAST的结合、多天线信道解码等具体的应用问题也被更多的提到。关于硬件电路和软件实现也是热点之一。有关“类Turbo”码技术，如低密度校验（LDPC）码技术又重新被提出。在Turbo码提出十年左右的时候，它已经发展的比较完善，并且进入应用服务领域。
由于Turbo码的优越性能，研究者在将它用于应用系统上作出了很多努力。例如移动卫星通信系统、数字音频广播、数字视频广播、深空通信、深空网、UMTS/3GPP、CDMA等系统。
除此之外，Turbo码技术也被应用到信息隐藏领域，例如视频和图象的加密和数字水印技术上。Turbo码的思想也被用于分布式信源编码的研究和信源信道联合编码技术中。

1.3 Turbo码的研究展望

从2003年以来，对于Turbo码的研究越来越倾向于具体应用。2006年的Turbo码会议将在德国慕尼黑与第六届信源信道编码会议一起举行。Turbo码会议的主要议题有：纠错码、Turbo码和LDPC码、编码和Turbo编码调制、检测和Turbo检测、均衡和Turbo均衡、同步和Turbo同步、多用户检测、界限、性能和收敛性、算法和成员码、交织和座标图、Fountain码以及网络编码。而信源信道编码会议的主要议题是：信息理论、线性编码、MIMO和CDMA系统、信源编码和数据压缩、语音、音频、图象和视频编码、信源信道联合编码、差错隐藏及加密和数字水印。由于Turbo码已经称为当前信道编码最重要的组成部分，因此这两个会议联合举行也可以看作是Turbo码应用范围的扩大。我们也可以从中看到Turbo码今后的发展方向。除了对编/解码器和交织器的新设计和改进之外，更多研究将会投入到Turbo码与其他技术的联合应用中去。
Turbo码作为信道编码，与所要保护传输的信源本身特点相结合，会对Turbo码的设计提出不同的要求，例如语音、音频、图象、视频和超文本数据对于传输信道的延迟、抖动和可靠性都有着不同的要求。而视频编码技术中的各种分层编码所产生的不同的码流对传输的要求也不尽相同。各种数据对安全性的要求也不相同。因而Turbo码与信源联合编码及不平等保护等技术的结合在实现上还有很多问题有待解决。
虽然Turbo码最早提出来的时候是为了深空和卫星通信，但其价值远远超出了这个范围，因此Turbo码在各种不同通信环境中的性能一直是研究的一个重点。早期的研究主要针对AWGN信道。而无线通信的发展使得对衰落信道中的Turbo码研究称为热点。为了适应无线和移动信道的衰落特点，Turbo码也被结合到其他编码系统中，如BLAST、VBLAST系统等。对于Turbo码在光通信信道中的研究也一直在进行。
面对越来越强大的通信，需要不停的创新，更需要非传统的概念。Turbo码得益于莫尔定律和世界范围内研究者为达到香农极限所作出的努力，来得正是时候。由于Turbo码正在其蓬勃发展的时期，它还不能解决流量、延迟、复杂度等所有的需求，在此领域内还有许多研究要做。此外，在这个为求简化而产生的的纠错技术之外，“Turbo”的概念，也就是在接收器处理数据时不浪费任何信息的方式为建立通信算法提供了一种新的思考方式。

1.4 要求及内容安排

先对Turbo码进行性能分析，并利用仿真工具（如MATLAB）对Turbo码进行系统仿真。仿真要求实现对信源、编码器、信道、译码器、信宿五大子系统的仿真，并完成整个系统的仿真，要求得到不同交织器大小、不同信道下、不同译码算法时系统性能的仿真曲线图。
本文的结构安排如下：
第一章：介绍了及其现状以及器未来展望。
第二章：介绍了Turbo码的编译码原理、结构及其思想。
第三章：介绍了Turbo码设计中需要考虑的问题及其程序流程图。
第四章：对Turbo码进行了系统的计算机仿真。仿真的内容包括对影响Turbo码性能的各种参数进行仿真。
第五章：对全文内容进行总结，指出了以后的主要研究工作和方向。

第二章Turbo码的编译码原理

Turbo码的提出是为了在一般译码复杂度下获得较高的编码增益。在发送端,编码器采用并行级联编码技术,用简单的码构造长码;在接收端,译码器把长码化成短码,利用软输入/软输出迭代译码算法进行译码。从一些模拟结果来看,Turbo码的性能距离Shannon极限已相当接近。

2.1 Turbo码的编码器

Turbo码由2个递归系统卷积码（RSC码）并行级联而成。最早提出的Turbo码的编码器结构如图1.1所示，主要由2个并行的系统反馈卷积编码器（RSC）和1个置于第2个RSC之前的交织器构成在Turbo码的编码器中，并行结构并不是必需的，也可以采用串联结构，或是串并联混合结构。级联的RSC也不一定是2个，更多得RSC和交织器构造起来的Turbo码，其编码性能一般会更好。

图2.1 Turbo码编码器基本原理框图

从图2.1可以看到，第1个RSC对信息比特直接经行编码, 第2个RSC责被交织器改变顺序后的信息比特进行编码。信息比特总是在信道中传输，而校验比特责根据编码的速率进行相应的删除后再传输。编码器的主要特点是级联编码。

2.2　Turbo码子码和交织器

Turbo码有一个重要技术手段:“分集”,就是通过交织器帮助实现的。交织器打乱了输入编码器2的信息流,输入编码器1和2的信息流一般来说相关性很小。这样,当一个子码对于相应的信息流在某段时间内产生了一个在编码格图中与其它路径距离较近的符号流,而另外一个子码在同时段内产生类似的不佳符号流的可能性较小,因此两者在性能上可以互补,也就在这个意义上实现了分集。相应地,选择交织器的一个准则就是使编码器1和编码器2产生的码字尽量不同,或者说,交织器的作用是当一个编码输出不太好时,尽量使另一个编码输出好些。
交织器一般可分为两种,一种是规则的,或叫块交织器,数据被按行(列)写入一个矩阵,然后被按列(行) 读出;另一种是不规则的,数据或被类似随机地写入或被类似随机地读出。不规则交织器的选择还没有一个好方法,但一般能产生较好的效果。在传统的级联编码中也采用交织器,作用是使内码纠正不了的错误随机化以便外码纠正,而Turbo码中的交织器和整个码是一体的,它在Turbo码中的作用是不能替代的。虽然最佳交织器的选择是个很复杂的问题,但研究表明即使采用简单的块交织,Turbo码的性能也是可观的。
Turbo码编码设计的指导原则是“分集”,分集效果的好坏决定了Turbo码的性能,当子码不带反馈时,没有交织器的增益,所谓交织器的增益指的是: Turbo码的性能随交织器尺寸的增大而产生的提高。只有使用带反馈的子码才会有交织器增益。一个简单的例子可以说明这一点:当一个只含有一个“1”的比特流进入Turbo码编码器后,编码器1产生了一个不理想的码字流,而经交织后,信息流仍只含一个“1”,若编码器2编码不带反馈,会产生一个同样的不理想码字流。但若子码带有反馈,因为进入编码器2的信息流中“1”的位置已改变,这样编码器2的编码输出和编码器1的不一样。因此,可以说交织增益是交织器本身对信息流的随机化和子码具有反馈两者的综合效果,只有交织器,没有子码的反馈,不会实现交织增益。子码和交织器一体是Turbo码设计的一个重要原则。

2.2.1 子码的选择

图2.1中RSC编码器部分是成员码编码器,一般采用迭代反馈的系统卷积码(RSC) 的编码结构,它是一种针对定长的比特序列的编码方法。采用这种编码结构是因为在较大信噪比(BER)情况下,非系统卷积码(NSC)比具有同样长度编码存储的非递归系统卷积码的误比特率(BER)要小,而带反馈系统卷积码组合了非系统卷积码和非递归系统卷积码两者的优点。对于任意大小的信噪比,当码率大于2/3时,带反馈系统卷积码的性能比具有同样参数的非系统卷积码性能要好。因此,Turbo码通常选用带反馈系统卷积码作为成员码。
后来的研究表明,即使是非常简单的子码也可以得到异常好的Turbo码。子码的自由距离以及Turbo码的自由距离的提高对性能没有明显的改善,特别是好的子码不一定造成好的Turbo码。进一步的研究表明,子码选择的关键在于是否具有反馈结构。子码的反馈性是Turbo码性能提高的前提条件。

2.2.2交织器

Turbo码之所以具有如此诱人的性能,主要是由于:(1) 采用递归系统码(RSC) 作为分量码;(2) 使用了随机交织器;(3)译码采用了软输出迭代译码算法。
Turbo码的强纠错能力是源于它在译码过程中巧妙的利用了附加信息在子译码器中进行多次迭代译码的结果,而这些由各级子译码器产生并反映相应信息位译码判决可信度的附加信息之所以能被相互利用,归功于插在他们之间的交织与去交织器,即它们的“置乱”作用使在同一时刻送入各子编译码器的信息序列码元几乎不相关。可见,交织器在Turbo码的设计中起着十分重要的作用,它很大程度上地影响着Turbo码的性能。
在以往的信道编码中,使用交织器的目的主要是抗信道突发错误,而在Turbo码中,交织器除了抗信道突发错误外,主要是改变码的重量分布,控制编码序列的距离特性,使重量谱窄带化,从而使Turbo码的整体纠错性能得以提高。采用随机交织器, Turbo码的编码就类似于随机的编译码方式,其性能接近于Shannon随机码的性能,即Shannon极。限因此,交织器性能的好坏将直接影响到Turbo码的纠错能力。而且,交织类型和交织深度的不同也会在译码时延、抗突发错能力等性能指标中反映出来。
为提高编码效率,Turbo码通常以“删余截短”码的形式送入信道,收端通过插入“模拟零”的方式加以恢复,这本身对码元的纠错能力将打折扣。以1/2码率的截短Turbo码为例,如果采取不甚恰当的交织方式,还需考虑更坏的情况,即有可能是信息序列中的某些比特位在水平和垂直方向有重复的对应校验位送往信道,而另外一些比特位却在两个方向均无对应的校验位送往信道,即造成对信息位保护不均的现象,这也势必影响码元的纠错性能。为此,提出一种“保奇偶”的随机交织方案解决这一问题。“保奇偶”随机交织就是在保持信息比特位置奇偶性不变的前提下,随机产生位置地址表的读表式随机交织方式。在生成截短Turbo码时,如果水平和垂直方向每次分别将输入奇数和偶数位信息比特时编码器产生的监督位交替送往信道,即可保证信息序列中的每一位均有对应的监督位通过信道送抵解码器。

2.3Turbo码的译码组成

与编码不同的是，译码得关键是尽量降低算法的复杂性和减少译码时延。降低算法的复杂性可以通过采用一些次优算法来实现。译码时延主要取决于交织器的大小和迭代的收敛性，而处理时延一般可以采用高速DSP和简单的次优算法来减小。
译码器的基本结构框图如图2.2所示，主要组成部分是2个软输入、软输出的译码器和与编码器相关的交织器、去交织器。

图2.2 Turbo码译码器基本原理框图

在接收机解调器输出软判决信息之后，Turbo码译码器的基本工作过程是：对应于第1个分量器（RSC1）得系统信息比特和校验比特的软判决信息，首先被送到第1个译码单元（DEC1）进行译码，译码输出的信息可以分解为内信息和外信息，其中外信息经过去交织后，再传送给第2个译码单元（DEC2）作为器译码的先验信息，第2个译码单元同时得到相应系统比特及校验比特的软判决信息，进行第2次译码，得到的外信息接着反馈到第1个译码单元，进行下一轮的译码。各轮译码之间的信息连接就是通过外信息实现的。译码过程可以多次反复进行，最后的判决输出是在完成要求的迭代次数后进行的。从上述过程可以看出，Turbo码译码是软输入、软输出的反馈迭代译码。

2.4 Turbo码的基本算法
Turbo码可在译码复杂性和码率之间达到较好的平衡。由于2个译码器交换APP信息可以得到很高的编码收益，而用不同码率的成员码通过不同的互通方案可以得到不同码率的Turbo码,所以用2个码率各为1/2的卷积码级联后可得到码率为1/3的Turbo码。有时相对简单的成员码级联可组成接近Shannon理论信息容量的Turbo码。Turbo码纠突发错和成串错的能力较强。
Turbo码在中高噪声的应用环境中的性能必以往其他的信道编码好，这是它的一大优点。下面介绍Turbo码的基本算法思想。
2.4.1 译码算法分析
主要的译码算法有3种: MAP 算法、Log-MAP 算法、Max-Log-MAP算法、SOVA算法 :
1. MAP算法。
MAP算法是Turbo码中最常用的译码算法之一,它是在C.Berro等人提出的一种优化译码算法的基础上修正而来的。其特点是算出每个信息位的最大似然值,在译码时确保比特差错率最小。通过对该算法的修正,利用它计算出每个判决符号的对数似然比,即判决符号的可靠性信息,这就是MAP算法。
其主要特点有:
1)不同于最大似然译码(Maximum Likelihood Algorithm)算法仅能给出最可能传输的信息序列，MAP算法能在已知接收序列的条修下给出最可能传输的信息比特;
2)MAP算法本身是一种SISO算法，迭代方便，易于实现软判决译码;
3)MAP算法能在较低误码率条件下仍能获得较高的编码增益;
4)通过MAP算法所得出的对数似然比(Log-Likelihood Ratios，LLRs)本来就是软判决译码中最为常用的一种软信息。这也是MAP算法性能优异的原因之一。
2. Log-MAP算法
在MAP算法中将似然值运算全部用对数似然值表示,通过一定的简化,可将乘法运算变成加法运算,利用不同简化方法,可得到基于Log -MAP算法的其他算法。
3. Max-Log-MAP算法
这种含修正函数的算法叫Log-MAP算法。在具体实现的时候，由于修正函数是x1和x2的差的绝对值的函数，可以使用一维查找表实现。Robertson等人指出:只需要对修正函数进行8阶量化便可获得很好的性能。
可以发现,Max-Log-MAP算法比Log-MAP算法简单了许多。
4. SOVA算法
SOVA算法就是软输出Viterbi算法(Soft-Output Viterbi Algorithm),是Viterbi算法一种改进型。SOVA算法在删除低似然路径时保留必要的信息,以给每个输出比特提供一个可信度,其基本思想是利用最优路径和被删路径的度量差,差值越小意味着这次选取的可靠性越低。SOVA算法也是一种在对数域对卷积码进行软输出译码的算法。如果采用硬判决译码，SOVA算法与Max-Log-MAP算法相比具有相近的译码性能。采用软判决译码方式时，Max-Log-MAP算法的性能优于SOVA算法。但SOVA算法的硬件实现复杂度比Max-Log-MAP算法要小。

2.4.2 译码算法比较
1. Log-MAP算法和SOVA算法的比较。
Log-MAP 算法比SOVA算法用时较长,但其误码率较低,这说明Log-MAP算法比SOVA 算法性能更好,而SOVA 算法延时小,更容易实现。
2. 迭代次数对译码性能的影响。
无论是Log-MAP算法,还是SOVA 算法,在不同迭代次数下,迭代次数越大,纠错性能越好,只是迭代次数的增加,用时也会增加。
3. 帧长对译码性能的影响。仿真环境参数为:
在Log-MAP算法中, 随着帧长的增加,译码器的性能越优越。无论是采用Log-MAP 算法,还是采用SOVA算法,帧长对译码性能的影响相同。

第三章 Turbo码的设计及模块方案

Turbo码的设计包括分量RSC生成元的确定、码速调整器的设计已及内部交织器的设计。

3.1 Turbo码的设计
3.1.1.RSC编码器生成元的设计
译码的计算量与卷积码的约束长度有关，如果要减少运算量，约束长度就不能太大，因此方案中的约束长度一般为3、4或5。如果不考虑交织器对生成元的影响，从仿真结果看，译码时，在一定的范围内，较长的约束长度具有较大地编码增益。而且，约束长度越大，信息关联程度越大这对译码性能的提高优好处。
3.1.2.迭代次数
无论是Log-MAP算法,还是SOVA算法,在不同迭代次数下,迭代次数越大,纠错性
能越好,只是迭代次数的增加,用时也会增加。在一般的系统中，5次迭代究足够了。
3.1.3.交织长度的选择
交织器的主要作用就是去相关。交织长度越长,对码字中各个比特的交织距离就越大,去相关的效果就越好。不过,交织长度的增加给译码带来了时延,在实际应用中要根据系统对实时性的要求进行折衷考虑。
3.1.4.交织算法
Turbo码的交织算法时影响其性能的一个重要因素。目前的交织算法还处于研究阶段，到底采用什么方法作为标准还没有定论。在4种译码算法的仿真比较中，拟合MAP算法在性能上与MAP算法相近，而计算的复杂性比MAP算法低，在工程上有一定的意义，SOVA的性能比MAP算法差，但SOVA算法的复杂性时最低的；

3.2 模块方案
3.2.1 设计总流程
设计总流程如图3.1

图3.1 设计总流程

3.2.2 模块说明
Turbo编码模块如图3.2。Turbo译码模块如图3.3。

图3.2 Turbo码编码模块

图3.3 Turbo码译码模块
3.2.3 简要说明
1. 信道传输
程序模拟的是具有标准方差的AWGN信道,由于采用BPSK调制, 故在进入信道传输前要进行信号的+1/-1电平转换。
2. 译码算法
译码算法是采用基于后验概率的软输出译码算法LOG－MAP算法。
3. 迭代停止准则
采用的程序是用Turbo译码的误帧数目为迭代停止准则。
4. 判决
采用完整似然信息进行硬判决, 即A(uk)≥0判原始序列估计值^uk为1;A( uk ) < 0判原始序列估计^uk 为0。
5. 调制方式
程序模拟采用的是BPSK调制。

第四章 Turbo码的仿真实现及分析

4.1 Turbo码的仿真环境及设置

4.1.1 仿真环境
由于Turbo码系统十分复杂，使用软件对其进行仿真时，编码和译码的过程中要处理的数据量相当大，因此仿真时软件的数值计算能力和计算机的性能将对仿真结果产生比较大的影响，尤其是对软件系统运行时间长短的影响。
本文的仿真过程中，使用MATLAB来编写Turbo码的编码和译码系统。MATLAB是一个基于矩阵代数数值求解的科技应用软件，在数值计算、数据处理、信号处理等领域应用十分广泛。软件Turbo码系统中，利用生成矩阵对信息序列进行编码，以及在译码时的前向和后向迭代中都要设计到大里的数组或者是矩阵的运算。因此，MATLAB非常适用于Turbo码的系统仿真。
仿真的硬件环境为一台个人计算机。

4.1.2 仿真设置
整个Turbo码仿真系统按照Turbo码的基本结构进行，采用如图3.1的系统框图。仿真的设置分为三大部分，分别是编码器、信道和译码器。
使用MATLAB提供的函数产生{0,1}序列，作为翰人信息序列。
编码器采用常用的结构:二个相同的RSC并行级联，RSC的具体结构根据仿真的目的进行适当的选择。第二个分量码编码器使用交织器。由于计算机仿真中随机交织器比较容易实现，所以大部分仿真中都采用性能优异的随机交织器。对每帧信息序列进行编码时，适时生成新的随机交织器进行交织，以获得RSC2的输人序列。随机交织器将每帧数据中比特的位置进行随机置换。这种置换的格式将被保存下来，以保证在译码器端据此进行正确的解交织。
除了专门对归零处理的仿真外，分量RSC编码器的归零处理方式都采取常用的方式:将第一个编码器进行结尾处理(terminated )，第二个仍处于开放状态(open)。如图4.1所示。采用这种终止方式后，每一个编码的信息块之后将附加m(RSC中存储器个数)个比特，用于将RSC1的存储器状态恢复为全零状态。当我们采用的RSC存储级数为3时，如果我们设定每帧的大小为1024比特，那么每帧中被编码的信息比特数为1024-3=1021个比特。亦即帧的大小等于信息比特数加终止结尾比特数。

图4.1 仿真中RSC的主要终止方式

由于交织器的存在，同样的结尾比特能将RSCI成功置零，但不能保证RSC2同时归零。所以译码开始时，两个成员译码器的初始状态不同。
我们知道，使用两个RSC分量编码器时，对长为L的序列编码，两个RSC将分别得到长为L的编码序列。将信息序列和两个编码序列组合为长为3L、码率为1/3的编码输出。为了提高码率常常采用截余技术。很多关于Turbo码的文献中，提到的计算机仿真都使用码率1/2。为了得到1/2的码率，使用截余矩阵P=[10,01]对RSC1编码输出的序列丢掉偶比特保留奇比特，对RSC2编码输出的序列丢掉奇比特保留偶比特，再跟信息序列一起组合成长2L的序列输出。

4.2 Turbo码仿真系统结构

根据Turbo码系统的结构特点和上节中提出的仿真设置，本文将整个系统合理地划分成多个模块，使用MATLAB，通过模块化设计实现了可以用于计算机模拟的Turbo码系统。前文所得出的结果将证明所实现的模拟系统是合理的、有效的。
系统所包涵的模块具体划分为:主程序、信道模型及复用调制子程序、交织子程序、RSC编码子程序、网格图生成子程序、对一帧编码的子程序、对一位信息比特编码子程序、译码前解复用子程序、使用不同的算法进行译码的译码子程序。
Turbo码仿真系统结构可以分成主程序体Turbo_system( 产生信源，交织器)编码模块和译码模块组成。
1.主程序体Turbo_system用于设置具体的参数:
产生信源;
交织器的实现;
调用编码模块;
模拟高斯白噪声信道;
逆复用;
调用相应的译码模块;
输出出错帧的概率和误码率。
2.编码模块encodem:
3.译码模块有三个子模块:
单滑动窗口技术的LOG-MAP译码模块
双滑动窗口技术的LOG-MAP译码模块

4.3 Turbo_system主程序流程图

设置参数包括:
(1):设置译码算法:可以设置成为LOG-MAP译码算法或者SOVA算法。如果是LOG
-MAP算法还需要设置是单滑动窗口技术或双滑动窗口技术.
(2):设置滑动窗口的大小:滑动窗口的大小要合适。大小为交织长度的1/4左右。
(3):设置每帧长度:每帧长度也就是交织长度，一般在10′的量级。
(4):设置编码产生多项式:
(5)设置是否删余:参量为puncture其目的是得到1/2或1/3的码率。
(6):设置译码迭代次数:根据具体的误码率要求进行设置，缺省值为3次。
(7):设置AWGN信道的信噪比:一般进行低信噪比设置，可以是0.5dB,1.0dB,1.5dB
等。

4.3.1信源的产生:

用随机数函数产生0-1之间的随机数，然后用舍入函数生成二进制信源

x=round(rand(1,L_total-m))

4.3.2 交织器的生成:

本文采用的是伪随机交织器。可以是用随机函数产生0-1的随机数，然后用排序函数求出其每个随机数排序后对应的位置。因为随机数的大小是随机的。所以它们排序后对应的位置也是随机的。这样就可以得到伪随机交织器。
[temp,alpha]=sort(rand(1,L_total))

4.3.3 调用编码模块 :
调用编码模块encodermo:
en_output=encoderm(x,g,alpha,puncture)

4.3.4 模拟信道:

相关程序语句:
en=10^(EbN0db(nEN)/10);
sigma=1/sqrt()*en)
r=en_output+sigma*randa(1,L_total*(2+puncture));

4.3.5 调用相应译码模块:

根据设置的参数，选择SOVA算法就调用SOVAO模块，选择LOG-MAP算法以及选择的单滑动窗口技术或双滑动窗口技术调用singlewindow模块或者doublewindow模块。

4.3.6 输出结果:

每译码完3帧就输出误帧率和误码率。编码器各程序模块Encoder程序模块的流程图如图所示。具体可以分块实现。
调用RSC_encode:RSC_encode要根据是否截尾，进行相应的编码处理。因为在编码完一帧之后，编码器的状态移位寄存器最后要清零，这样才能进行下一帧的编码，所以没有截尾处理，也就是信息位结尾是交织长度m位。，那么，显然最后编码器的状态移位寄存器会清零。如果截尾了，那么就要进行相应的处理，使编码器状态移位寄存器清零。具休的做法就是把寄存器的反馈信息作为输入信息，那么，在编码的时候，反馈信息要和输入信息模2相加，这样就会变成使得存储到移位寄存器中的输入信息为零。经过m次相应的操作最后，使得移位寄存器清零。

调用交织器:因为RSC_encode2的输入信息是交织之后的信源序列，所以要调用伪随机交织器。交织器是采用随机函数产生随机数，然后再用排序函数处理得到的。
调用RSCencode:这相当于Turbo编码器中的RSCencode2，其输入信息为交织之后的信源序列。
删余和串并转换:为了提高码率，通常是采用删余处理，把码率从1/3，高到1/20
串并转换是把并行的两路或多路信息转换成串行信息。
调制:是采用二相调制。

4.4 LOG-MAP分量译码器Singlewindow

Singlewindow模块对应LOG-MAP译码算法的单滑动窗口技术。其对应的程序流程图如图所示。以下采用单滑动窗口技术的LOG-MAP译码模块。根据每帧的大小和滑动窗口的大小将一帧分划成几个窗口。每次根据一个窗口内的前向递推，后向递推计算窗口内信息位的对数似然比，然后再对下一个窗口进行译码。这样看起来就像一个窗口在沿着信息帧在滑动，这也就是滑动窗口技术的由来。因为我们只是采用一个滑动窗口，所以称之为单滑动窗口技术。单滑动窗口技术可以有效地提高译码速度，以及减少对于前向递推和后向递推的存储。

划分窗口: 根据帧的大小和滑动窗口的大小进行划分。
初始化Alpha和Beta: Alpha和Beta的存储空间的大小只要滑动窗口的大小即可，但是考虑到滑动窗口的长度可以变化，所以在软件仿真的时候，使得Alpha的存储数组的大小和交织长度相同。
调用Betaf进行预处理: 预处理的目的是减少后向递推的初始值的盲目性。

4.5LOG-MAP分量译码器doublewindows

Doublewindow模块对应LOG-MAP译码算法的双滑动窗口技术。其对应的程序流程图如图所示。其与单滑动窗口技术的差别在于“两驾马车”同时跑，把接收的信息序列分割成为两个大小相当数据模块，前一块由前向后逐位计算对数似然比，对后向递推采用预处理技术;后一块数据由后向前计算对数似然比，对前向递推采用预处理技术。Doublewindow程序模块的流程图:

4.6 SOVA分量译码器的程序模块

sova分量译码器的程序流程图如图所示。

SOVA分量译码器的过程是通过找出幸存路径和竞争路径。其中寻找竞争路径的过程比较复杂，计算量比较大，耗费硬件资源，而且对译码的速度起着决定的作用。Turbo码SOVA算法为了降低系统的复杂度，竞争路径的求取不需要在整个数据块的范围内求取，只需要在一个滑动窗口的范围内搜索，在竞争路径的搜索过程中，通常竞争路径的尾部和幸存路径的尾部重合，这样另一方面也减少了存储空间。

4.7仿真结果分析

目前Turbo码的大部分研究致力于在获得次优性能的情况下公小译码复杂度和时延，从而得到可实现的Turbo码系统。
对于本文中的仿真需要说明一点，这种荃于软件的仿真葬幼技得教件仿真运行在时间上跟具体的硬件编译码处理所藉的时延不同，也不成比例;另外，原本在硬件运行中产生很明显的时延差的情况，在软件仿真中并不能明显地体现出来(比如第四章中为了减小时延所提出的近似方案)。所以并不适于使用软件系统运行处理的时间对Turbo码系统性能进行评价。但是，对于软件仿真和硬件运行的时间会可预期地受参数影响向相同的方向变化的情况，软件运行时间可以作为时延分析的一种参考。基于此，本文没有专门把咐间作为仿真结果之一。信道编码的根本目的是降低数字信息在有扰信道传抽过程中的误比特率，本文的仿真结果也以误比特率（BER）的形式给出。

4.7.1 几种主要译码算法的性能比较

首先对MAP算法、Log-MAP算法、Max-Log-MAP算法和SOVA算法在加性高斯白噪声信道（AWGN）环境下进行仿真比较，四种算法使用相同的生成多项式G=(15.17)，码率R=1/3（未进行截余），帧大小为4×1024比特，译码时迭代5次。仿真结果表明，四种算法中，MAP算法性能最好，Log-MAP算法的性能跟MAP算法在较低的SNR时比较接近，高信噪比时差别则较大。理论上，Log-MAP算法跟MAP算法有相同的性能，仿真结果中二者性能的差异可能是由计算机系统的性能造成的，较大的帧给计算机系统带来了较大的计算量，从而对不同的算法进行仿真时可能引入不确定因素。Max -Log-MAP算法和SOVA算法的性能十分接近，一般，Max-Log-MAP算法的性能稍微优于SOVA算法。他们跟MAP算法和Log-MAP算法相比较，性能下降明显。从算法复杂度而言， MAP算法最复杂， Log-MAP算法其次，Max-Log-MAP算法再次，SOVA算法最简单。因此可知，性能好的Turbo码译码算法十分的复杂，如果要使的译码容易实现，往往是以性能的下降为代价的。

4.7.2不同的交织器大小对性能的影响

交织器通过对进入RSC2的信息序列进行位置置换，从而使得整个Turbo码编码器得到近似长码的编码输出。
在Turbo码生成中,交织器起着重要作用,在很大程度上影响着Turbo性能。它在成员码编码器RSC2之前将输入信息比特的位置进行随机置换,使得长码的构造具有了伪随机性。我们知道,随机化是贯穿Shannon理论的核心思想之一。可以说,Turbo码之所以具有如此令人惊异的优异性能,其根本原因就在于Turbo码实现方案中由于交织器的引入而实现的伪随机性。在发送端,伪随机性是通过编码器中的交织器及成员码的并行级联方式实现的;在接收端,则是通过带有交织器的具有软输入、软输出特性的反馈递推迭代译码来实现的。,由于交织器的引入,整个Turbo码编码器可以看成是一个伪随机编码器。1995年,Svirid考虑了成员码是分组码的情形。设码字C=(m|mP|m’P),其中,m是k维信息矢量,P是k×r矩阵,m’是m通过随机置换得来的。
Svirid指出交织器的目的在于使Turbo码的最小重量尽可能大,即交织器直接影响m’P的重量,起到随机化作用。当mP的汉明重量小时,m’P的汉明重量应该大;反之亦然。在Turbo码的编码中,交织器起着”窄谱化”的作用,使得Turbo码中重量小的码字数目减少,而这正是影响Turbo码性能的主要因素之一。1996年S.Benedetto和G.Montorsi引入均匀交织器的概念,指出好的交织器是存在的。这些都说明了Turbo码优异性能在发送端主要是由编码交织器的伪随机化带来的。由图2所示的译码器结构可以看出,这是一类具有反馈结构的伪随机译码器。这是由于2个码可以交替互不影响地译码,并可以通过关于系统码信息位的软判决输出相互传递信息,进行递推式迭代译码。通过若干次迭代,使每个码元都可以得到来自序列中几乎所有码元的信息。它具体是通过迭代中反复交织反馈及去交织来实现的,这实际上就实现了译码的伪随机化。长码的构造及对Turbo码性能的影响Shannon有噪信道编码定理指出,随着编码长度L→∞,译码错误概率趋于0。因此为了使码有效就必须使用长码。但随着码长的增加,译码器的复杂度和计算量也相应增加以致难以实现。为解决这个问题,人们提出了级联码概念,把编制长码的过程分几级完成(通常分2级),即以现有短码为基础构成等效长码。如分别采用确知的短码作为内码和外码,希望通过2次纠错串行级联方式,即外码可以继续纠正内码未能纠正的错误,其总的纠错能力取决于内、外码的纠错能力。
但传统级联码并没有摆脱短码性能的束缚,当其接近信道容量的渐近状态时,一般传统短码的译码过程不但不能纠正错误,反而有可能使错误增大。然而,Berrou等人提出的Turbo码,其编码器由递归系统卷积码(RSC)并行级联而成,并采用了反馈迭代译码,真正挖掘了级联码潜力,以其类似于随机的编译码方式,使其更加逼近了Shannon随机码的性能。
交织器长度越大,即Turbo码的伪随机性越好,则Turbo码的性能也就越好。

第五章结论和展望

Turbo码是一类新的纠错码，是一种新颖的信道编码方案，它具有目前任何其它信道编码技术无法比拟的误比特性能。编码时它使用并行级联卷积码的递归编码器结构，引人交织器对进人分量编码器的信息序列进行随机交织，从而获得了近似长码的编码输出;译码时使用软输人软输出译码器进行递归迭代译码。Turbo码是一种极为复杂的信道编码技术，性能优异的译码算法往往由于硬件实现的复杂度太高或者译码时延太大而难以实现。目前Turbo码领域面临的主要问题是:如何在复杂度和时延都可以接受的前提下获得最佳的系统性能。
通过理论分析与计算机仿真，本文得出的结论有:
1、对于信道编码，Turbo码具有得天独厚的优点，它相对其它编码方法，具有更近香农限的性能；
2、影响Turbo码的因素很多，如译码算法、信道、交织器设计、迭代次数等等。在减小码率，增加交织长度、迭代次数等众多措施可以使Turbo码的性能得到改善；
3、Turbo码的几种译码算法各有各的优缺点，在降低一定计算复杂度的前提下，Log-MAP算法比较有前途。
4、 Rayleigh信道下的Turbo码比AWGN信道下的Turbo码性能要差，对于Rayleigh信道下的Turbo码擂要考虑更多的因素:比如信道交织、多径衰落、多普勒效应等。
随着研究的不断深入，其性能也不断提高，虽然理论上还并不十分完善，但是仿真分析及部分应用足可显示出的广阔前景。Turbo码的译码比较复杂，延时也比较大，这是它的重大弱点。但是我们相信随着微电子技术的发展，通过电路计算速度的提高，以及对交织器和译码算法的改进，一定能解决Turbo码的实时性问题。Turbo码在不久的将来一定会在通信和数字电子技术领域得到广泛应用。

致谢

本文的研究工作是在彭春华教授的精心指导和悉心关怀下完成的，在整个研究过程中，得到了彭老师的全力支持和帮助。导师渊博的学术理论知识、精益求精的科研态度不但使我受益匪浅，也深深感染着我。从彭老师身上，我不仅学到了扎实、宽广的专业知识，也学到了积极乐观的生活态度，和脚踏实地做事、老老实实做人的作风，这些都会令我终生受益!
几个月的科研和学习中，学院的老师和同学们在学习和生活上都给予了我许多帮助，在此，向所有关心和帮助过我的老师、同学和朋友表示由衷的谢意!
另外，我也很高兴在一个学风浓厚，关系融洽的环境中度过我在学校的最后时光。在日常学习和生活中，实验室的兄弟姐妹们相互帮助、共同进步。在此我对你们的一如既往支持表示真诚的感谢!
衷心感谢在百忙之中评阅论文和参加答辩的各位专家、教授!

参考文献

[1] 王新梅,肖国镇1 纠错码———原理与方法[M]1 西安:西安电子科技大学出版社,2001.1.
[2] 周世东，姚彦.Turbo-code,一种接近理论极限的信息编码[J].1997,13(3):19~22.
[3] Berrou C, Glavieux A. Near Op timum Error Correcting Coding and Decoding: Turbo-codes [ J ]. IEEE Transactions on Communication, 1996, 44: 1261～1271.
[4] A. GOALIC, R. PYNDIAH, “Real-time Turbo- decoding of product codes on a digital signal processor”,GLOBECOM ‘97 Phoenix pp. 624-628 V.2.
[5] C. Berrou, “The ten-year-old turbo codes are entering into service”, IEEE Commun. Mag.,. pp. 110-116, Aug. 2003.
[6] 彭林等. 第三代移动通信技术[M].北京:电子工业出版社，2003.105~116.

[7] Viterbi A. An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes [J ] . IEEEJournal on Selected Areas in Communications , 1998 , 16 (2) : 260 —264.
[8] Hagenauer J , Robertson P. Iterative (Turbo) Decoding of Systemic Convolution Codes with the MAP and SOVA Algorithm [A] .In : Proceeding of ITG2Conf on Source and Channel Coding [C] . Munich : Germany , 1994 : 21—29.
[9] Robertson P , Villebrun E , Hoeher P. A Comparision of Optimal and Sub2Optimal MAP Decoding Algorithms Operating in the Log Domain [A] . Proceeding of IEEE International Conference on Communications [C] . Seattle : WA , 1995 : 1009—1013.
[10] 　Hagenauer J , Offer E , Papke L. Iterative Decoding of Binary Block and Convolution Codes [J ] . IEEE Transactions on Information Theory , 1996 , 42 (2) : 429 —445.
[11] 刘东华，唐朝京.用于Turbo迭代译码的log-MAP算法的简化[J].电子与信息学报,2001,23(12):1340~1347.
[12] 李建新,刘乃安,刘继平. 现代通信系统分析与仿真—–Matlab 工具箱[M] . 西安:西安电子科技大学出版社,2001.
[13] 邓华,张振中,张海洋,等.MATLAB 通信仿真与应用实例详解[M].北京:人民邮电出版社,2003.

附录

Turbo码仿真系统Matlab源代码

Turbo_ system主程序休

DSP+FPGA体系结构实现最小二乘递推算法

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 17-08-2009

标签：DSP, FPGA, least-squares, recursive algorithm, VHDL, 最小二乘, 算法, 递推

0

摘要 V
ABSTRACT VI
第一章绪论 1
嵌入式系统概述[1] 1
1.1.1 嵌入式软件的分类、特点以及发展趋势 1
嵌入式软件与嵌入式系统是密不可分的，嵌入式系统是“控制、监视或者辅助设备、机器和车间运行的装置”，就是以应用为中心，以计算机技术为基础，并且软硬件可裁剪，适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系统。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序等四个部分组成，用于实现对其它设备的控制、监视或管理等功能。而嵌入式软件就是基于嵌入式系统设计的软件，它也是计算机软件的一种，同样由程序及其文档组成，可细分成系统软件、支撑软件、应用软件三类，是嵌入式系统的重要组成部分。
1.嵌入式软件的分类：
1、嵌入式操作系统：嵌入式操作系统EOS（Embedded Operating System）是一种用途广泛的系统软件，过去它主要应用于工业控制和国防系统领域。EOS负责嵌入系统的全部软、硬件资源的分配、调度工作，控制、协调并发活动；它必须体现其所在系统的特征，能够通过装卸某些模块来达到系统所要求的功能。嵌入式操作系统通常以商业运作为主，从上世纪80年代起，商业化的嵌入式操作系统开始得到蓬勃发展。现在国际上有名的嵌入式操作系统有Windows CE 、Palm OS 、Linux 、VxWorks 、pSOS、 QNX、OS-9 、LynxOS等，已进入我国市场的国外产品有WindRiver、Microsoft、QNX和Nuclear等。我国嵌入式操作系统的起步较晚，国内此类产品主要是基于自主版权的Linux操作系统，其中以中软Linux、红旗Linux、东方Linux为代表。
2、嵌入式支撑软件：支撑软件是用于帮助和支持软件开发的软件，通常包括数据库和开发工具，其中以数据库最为重要。嵌入式数据库技术已得到广泛的应用，随着移动通信技术的进步，人们对移动数据处理提出了更高的要求，嵌入式数据库技术已经得到了学术、工业、军事、民用部门等各方面的重视。嵌入式移动数据库或简称为移动数据库（EMDBS）是支持移动计算或某种特定计算模式的数据库管理系统，数据库系统与操作系统、具体应用集成在一起，运行在各种智能型嵌入设备或移动设备上。其中，嵌入在移动设备上的数据库系统由于涉及数据库技术、分布式计算技术，以及移动通讯技术等多个学科领域，目前已经成为一个十分活跃的研究和应用领域。国际上主要的嵌入式移动数据库系统有Sybase、Oracle等。我国嵌入式移动数据库系统以东软集团研究开发出了嵌入式数据库系统OpenBASE Mini为代表。
3、嵌入式应用软件：嵌入式应用软件是针对特定应用领域，基于某一固定的硬件平台，用来达到用户预期目标的计算机软件。由于用户任务可能有时间和精度上的要求，因此有些嵌入式应用软件需要特定嵌入式操作系统的支持。嵌入式应用软件和普通应用软件有一定的区别，它不仅要求其准确性、安全性和稳定性等方面能够满足实际应用的需要，而且还要尽可能地进行优化，以减少对系统资源的消耗，降低硬件成本。目前我国市场上已经出现了各式各样的嵌入式应用软件，包括浏览器、Email软件、文字处理软件、通讯软件、多媒体软件、个人信息处理软件、智能人机交互软件、各种行业应用软件等。嵌入式系统中的应用软件是最活跃的力量,每种应用软件均有特定的应用背景,尽管规模较少,但专业性较强，所以嵌入式应用软件不像操作系统和支撑软件那样受制于国外产品垄断，是我国嵌入式软件的优势领域。
2.嵌入式软件的特点：
    1、嵌入式软件具有独特的实用性。嵌入式软件是为嵌入式系统服务的，这就要求它与外部硬件和设备联系紧密。嵌入式系统以应用为中心，嵌入式软件是应用系统，根据应用需求定向开发，面向产业、面向市场，需要特定的行业经验。每种嵌入式软件都有自己独特的应用环境和实用价值。
    2、嵌入式软件应有灵活的适用性。嵌入式软件通常可以认为是一种模块化软件，它应该能非常方便灵活的运用到各种嵌入式系统中，而不能破坏或更改原有的系统特性和功能。首先它要小巧，不能占用大量资源；其次要使用灵活，应尽量优化配置，减小对系统的整体继承性，升级更换灵活方便。
3.嵌入式软件发展趋势：
随着信息技术以及互联网飞速发展普及，3C（计算机、通讯、消费电子）合一的加速，嵌入式设计已经成为工业现代化、智能化的必经之路，嵌入式产品已经深入到各行各业。嵌入式接入设备是数字化时代的一大主流产品，嵌入式软件已经成为数字化产品的核心。嵌入式软件大量应用于家用市场、工业市场、商业市场、通讯市场和国防市场。近几年来，信息电器迅速发展，也为嵌入式软件的发展起到推波助澜的作用。彩电、DCD、手机、MP3/MP4、掌上电脑、汽车等都是潜在的信息电器。信息电器平台与通用操作系统、数据库不同，不存在国外软件厂商垄断市场的现象，这一领域已成为中国软件业的突破口。
    嵌入式系统面向特定应用领域，根据应用需求定制开发，并随着智能化产品的普遍需求渗透到各行各业。随着硬件技术的不断革新、微电子技术的快速发展，使芯片功能更加强大，硬件平台的处理能力不断增强，硬件成本不断下降，产品体积越来越小，同时嵌入式软件的可靠性、实时性、可维护性进一步提高。嵌入式软件已成为产品的数字化改造、智能化增值的关键性、带动性技术。移动通讯、掌上电脑、数字电视是嵌入式操作系统的重要应用领域，随着掌上电脑等手持设备性能的提高，嵌入式操作系统将成为必须的配置。随着行业的推广，行业应用软件市场将迅速扩大。掌上电脑功能的不断扩展，专项功能软件面临新的发展机会。 1

1.2 DSP＋FPGA实时信号处理系统[2] 3
1.2.1信号处理系统的类型与常用处理机结构 3
1.2.2 DSP+ASIC结构 4
1.2.3 线性流水阵列结构 4
1.3 DSP+FPGA系统的特点和优点 5
1.4 VHDL硬件描述语言简介[3] 6
第二章最小二乘递推算法及原理概述 8
2.1 最小二乘算法 8
2.1.1 最小二乘算法原理[4] 8
2.1.2 最小二乘算法的应用 9
1. 最小二乘法在足底矫形器交流伺服数控平台CAM中的应用 9
2. 基于加权最小二乘法的机车车辆零部件可靠性分析 9
3. 镜像映射法及递推最小二乘法在GPS 伪距导航定位解算中的应用 9
2.2 最小二乘递推算法 10
2.2.1 最小二乘递推算法及其原理概述 10
2.2.2 最小二乘递推算法的优点 12
第三章 DSP及FPGA芯片原理和开发应用 13
3.1 DSP系统[6] 13
3.1.1 DSP系统构成 13
3.1.2 DSP系统的特点 14
3.1.3 DSP系统的设计过程 14
3.2 可编程DSP芯片 17
3.2.1 什么是DSP芯片 17
3.2.2 DSP芯片的分类 18
1．按基础特性分 18
2．按数据格式分 18
3．按用途分 18
3.2.3 DSP芯片的应用 18
3.3 PLD发展概况[8] 19
3.4 FPGA的基本结构 20
3.5 可编程逻辑器件的设计 20
3.5.1 设计输入 21
3.5.2 设计处理 21
3.5.3 模拟仿真 21
第四章设计中基本逻辑电路模块的设计 23
4.1加法器模块的设计 23
4.1.1 加法器原理 23
4.1.2 加法器电路结构 23
24
4.1.3 加法器程序 24
4.1.4 加法器仿真结果 25
4.2 乘法器模块的设计[11] 26
4.2.1 乘法器原理 26
4.2.2 乘法器结构 27
4.2.3 乘法器仿真结果 28
4.2.4 乘法器位数不同的比较 29
4.3 除法器模块的设计 30
4.3.1 除法器原理结构及流程图 30
4.3.2 除法器仿真结果 31
第五章算法实现步骤及方法 33
5.1 算法流程图 33
5.2 DSP部分的设计 36
5.3 FPGA部分的设计 36
5.4 DSP与FPGA接口部分的设计 39
第六章结论 41
参考文献 43
附录 45

摘要

最小二乘递推算法在模型参数辨识、最优化决策、动态实时跟踪预测等多方面得到了广泛的应用。而DSP+FPGA结构具有灵活、有较强的通用性，适合于模块化设计，能够提高算法的效率，这种结构在信号处理系统体现了较强的优越性。
对最小二乘递推算法进行分析和研究，在设计中应注意模块化的设计，因为算法流程过程当中，需要大量使用乘法运算和加法运算等，这些模块的设计也是算法能够最终实现的基础。通过设计模块，可以使算法实现起来更加方便、快捷。
根据算法的复杂程度和重复频率并结合DSP和FPGA各自的特点，将算法分解为适合DSP实现的部分和FPGA实现的部分，再根据算法在各部分实现过程中遇到的实际问题进行适当的调整和改进，完成DSP和FPGA的接口通信，保证两者能够协调工作。通过采用VHDL硬件描述语言，完成算法在FPGA实现，并通过仿真且在FPGA中实际下载验证设计的正确性。

关键词：最小二乘,递推,算法,DSP,FPGA,VHDL；

ABSTRACT

Recursive least squares algorithm for the model parameter identification, optimization decision Real-time dynamic tracking, and other aspects forecast to be widely used. DSP and FPGA architecture are flexible, and have strong generic and suitable for modular design, algorithm to improve the efficiency of this structure in signal processing system reflects the strong advantage.
Recursive least squares algorithm to analyze and study, the design should pay attention to the modular design, Algorithms process because the process requires extensive use multiplication and addition operations. These modules are also designed algorithm can eventually achieve foundation. Through the design module will enable algorithm can be more convenient and faster.
According to the algorithm complexity and repetition frequency and with each DSP and FPGA features decomposition algorithm suitable for the DSP and FPGA part of the question, According algorithm in the process of achieving some of the practical problems encountered make an appropriate adjustment and improvement, complete DSP and FPGA interface communication, both to ensure coordination. Through the use of VHDL hardware description language, complete algorithm in FPGA, Through simulation and the actual download FPGA design verification correctness.

KEY WORDS least-squares, recursive algorithm, DSP, FPGA, VHDL

第一章绪论

嵌入式系统概述[1]

在计算机、互联网和通信技术高速发展的同时，嵌入式系统开发技术也取得迅速发展。这不仅表现在从事嵌入式系统开发研究的人员队伍日益壮大，嵌入式处理器和实时操作系统的性能增强和产品升级换代，更重要的体现在嵌入式技术应用范围的急剧扩大。
嵌入式系统拥有巨大的市场空间，我国应该抓住机遇，与时俱进，奋起直追，在嵌入式系统领域赶超世界先进水平。要达到这个目标，具有一定的现实可行性，这是因为同PC机系统相比，嵌入式系统更有自身的特征。在PC领域，虽有AMD系列处理器和Linux操作系统的市场冲击，但是Win_Tel（Windows+Intel）体系架构仍占主导地位；可是，嵌入式系统本身是一个相当分散的工业，典型特征是面向用户、面向产品、面向应用的，市场应用才是嵌入式系统开发的导向和前提，在当前的嵌入式市场中不存在垄断的局面。
嵌入式系统包含硬件和软件两部分：硬件架构上以嵌入式处理器为中心，配置存储器、I/O设备、通信模块等必要的外设；软件部分以软件开发平台为核心，向上提供应用编程接口（API），向下屏蔽具体硬件特性的板级支持包BSP。嵌入式系统中，软件和硬件紧密配合，协调工作，共同完成系统预定的功能。
　　对于不同的市场应用类型，嵌入式系统开发中的嵌入式处理器、实时操作系统、仿真器、调试器以及开发队伍的技术水平和结构比例等要素的选择是至关重要的。

1.1.1 嵌入式软件的分类、特点以及发展趋势

嵌入式软件与嵌入式系统是密不可分的，嵌入式系统是“控制、监视或者辅助设备、机器和车间运行的装置”，就是以应用为中心，以计算机技术为基础，并且软硬件可裁剪，适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系统。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序等四个部分组成，用于实现对其它设备的控制、监视或管理等功能。而嵌入式软件就是基于嵌入式系统设计的软件，它也是计算机软件的一种，同样由程序及其文档组成，可细分成系统软件、支撑软件、应用软件三类，是嵌入式系统的重要组成部分。
1.嵌入式软件的分类：
1、嵌入式操作系统：嵌入式操作系统EOS（Embedded Operating System）是一种用途广泛的系统软件，过去它主要应用于工业控制和国防系统领域。EOS负责嵌入系统的全部软、硬件资源的分配、调度工作，控制、协调并发活动；它必须体现其所在系统的特征，能够通过装卸某些模块来达到系统所要求的功能。嵌入式操作系统通常以商业运作为主，从上世纪80年代起，商业化的嵌入式操作系统开始得到蓬勃发展。现在国际上有名的嵌入式操作系统有Windows CE 、Palm OS 、Linux 、VxWorks 、pSOS、 QNX、OS-9 、LynxOS等，已进入我国市场的国外产品有WindRiver、Microsoft、QNX和Nuclear等。我国嵌入式操作系统的起步较晚，国内此类产品主要是基于自主版权的Linux操作系统，其中以中软Linux、红旗Linux、东方Linux为代表。
2、嵌入式支撑软件：支撑软件是用于帮助和支持软件开发的软件，通常包括数据库和开发工具，其中以数据库最为重要。嵌入式数据库技术已得到广泛的应用，随着移动通信技术的进步，人们对移动数据处理提出了更高的要求，嵌入式数据库技术已经得到了学术、工业、军事、民用部门等各方面的重视。嵌入式移动数据库或简称为移动数据库（EMDBS）是支持移动计算或某种特定计算模式的数据库管理系统，数据库系统与操作系统、具体应用集成在一起，运行在各种智能型嵌入设备或移动设备上。其中，嵌入在移动设备上的数据库系统由于涉及数据库技术、分布式计算技术，以及移动通讯技术等多个学科领域，目前已经成为一个十分活跃的研究和应用领域。国际上主要的嵌入式移动数据库系统有Sybase、Oracle等。我国嵌入式移动数据库系统以东软集团研究开发出了嵌入式数据库系统OpenBASE Mini为代表。
3、嵌入式应用软件：嵌入式应用软件是针对特定应用领域，基于某一固定的硬件平台，用来达到用户预期目标的计算机软件。由于用户任务可能有时间和精度上的要求，因此有些嵌入式应用软件需要特定嵌入式操作系统的支持。嵌入式应用软件和普通应用软件有一定的区别，它不仅要求其准确性、安全性和稳定性等方面能够满足实际应用的需要，而且还要尽可能地进行优化，以减少对系统资源的消耗，降低硬件成本。目前我国市场上已经出现了各式各样的嵌入式应用软件，包括浏览器、Email软件、文字处理软件、通讯软件、多媒体软件、个人信息处理软件、智能人机交互软件、各种行业应用软件等。嵌入式系统中的应用软件是最活跃的力量,每种应用软件均有特定的应用背景,尽管规模较少,但专业性较强，所以嵌入式应用软件不像操作系统和支撑软件那样受制于国外产品垄断，是我国嵌入式软件的优势领域。
2.嵌入式软件的特点：
    1、嵌入式软件具有独特的实用性。嵌入式软件是为嵌入式系统服务的，这就要求它与外部硬件和设备联系紧密。嵌入式系统以应用为中心，嵌入式软件是应用系统，根据应用需求定向开发，面向产业、面向市场，需要特定的行业经验。每种嵌入式软件都有自己独特的应用环境和实用价值。
    2、嵌入式软件应有灵活的适用性。嵌入式软件通常可以认为是一种模块化软件，它应该能非常方便灵活的运用到各种嵌入式系统中，而不能破坏或更改原有的系统特性和功能。首先它要小巧，不能占用大量资源；其次要使用灵活，应尽量优化配置，减小对系统的整体继承性，升级更换灵活方便。
3.嵌入式软件发展趋势：
随着信息技术以及互联网飞速发展普及，3C（计算机、通讯、消费电子）合一的加速，嵌入式设计已经成为工业现代化、智能化的必经之路，嵌入式产品已经深入到各行各业。嵌入式接入设备是数字化时代的一大主流产品，嵌入式软件已经成为数字化产品的核心。嵌入式软件大量应用于家用市场、工业市场、商业市场、通讯市场和国防市场。近几年来，信息电器迅速发展，也为嵌入式软件的发展起到推波助澜的作用。彩电、DCD、手机、MP3/MP4、掌上电脑、汽车等都是潜在的信息电器。信息电器平台与通用操作系统、数据库不同，不存在国外软件厂商垄断市场的现象，这一领域已成为中国软件业的突破口。
    嵌入式系统面向特定应用领域，根据应用需求定制开发，并随着智能化产品的普遍需求渗透到各行各业。随着硬件技术的不断革新、微电子技术的快速发展，使芯片功能更加强大，硬件平台的处理能力不断增强，硬件成本不断下降，产品体积越来越小，同时嵌入式软件的可靠性、实时性、可维护性进一步提高。嵌入式软件已成为产品的数字化改造、智能化增值的关键性、带动性技术。移动通讯、掌上电脑、数字电视是嵌入式操作系统的重要应用领域，随着掌上电脑等手持设备性能的提高，嵌入式操作系统将成为必须的配置。随着行业的推广，行业应用软件市场将迅速扩大。掌上电脑功能的不断扩展，专项功能软件面临新的发展机会。

1.2 DSP＋FPGA实时信号处理系统[2]

实时信号处理系统要求必须具有处理大数据量的能力，以保证系统的实时性；其次对系统的体积、功耗、稳定性等也有较严格的要求。实时信号处理算法中经常用到对图像的求和、求差运算，二维梯度运算，图象分割及区域特征提取等不同层次、不同种类的处理。其中有的运算本身结构比较简单，但是数据量大，计算速度要求高；有些处理对速度并没有特殊的要求，但计算方式和控制结构比较复杂，难以用纯硬件实现。因此，实时信号处理系统是对运算速度要求高、运算种类多的综合性信息处理系统。

1.2.1信号处理系统的类型与常用处理机结构

根据信号处理系统在构成、处理能力以及计算问题到硬件结构映像方法的不同，将现代信号处理系统分为三大类：
    ·指令集结构（ISA）系统。在由各种微处理器、DSP处理器或专用指令集处理器等组成的信号处理系统中，都需要通过系统中的处理器所提供的指令系统（或微代码）来描述各种算法，并在指令部件的控制下完成对各种可计算问题的求解。
    ·硬连线结构系统。主要是指由专用集成电路（ASIC）构成的系统，其基本特征是功能固定、通常用于完成特定的算法，这种系统适合于实现功能固定和数据结构明确的计算问题。不足之处主要在于：设计周期长、成本高，且没有可编程性，可扩展性差。
    ·可重构系统。基本特征是系统中有一个或多个可重构器件（如FPGA），可重构处理器之间或可重构处理器与ISA结构处理器之间通过互连结构构成一个完整的计算系统。
    从系统信号处理系统的构成方式来看，常用的处理机结构有下面几种：单指令流单数据流（SISD）、单指令流多数据流（SIMD）、多指令流多数据流（MIMD）。
    ·SISD结构通常由一个处理器和一个存贮器组成，它通过执行单一的指令流对单一的数据流进行操作，指令按顺序读取，数据在每一时刻也只能读取一个。弱点是单片处理器处理能力有限，同时，这种结构也没有发挥数据处理中的并行性潜力，所以在实时系统或高速系统中，很少采用SISD结构。
    ·SIMD结构系统由一个控制器、多个处理器、多个存贮模块和一个互连网络组成。所有“活动的”处理器在同一时刻执行同一条指令，但每个处理器执行这条指令时所用的数据是从它本身的存储模块中读取的。对操作种类多的算法，当要求存取全局数据或对于不同的数据要求做不同的处理时，它是无法独立胜任的。另外，SIMD 一般都要求有较多的处理单元和极高的Ｉ／Ｏ吞吐率，如果系统中没有足够多的适合SIMD 处理的任务，采用SIMD 是不合算的。
     ·MIMD结构就是通常所指的多处理机，典型的MIMD系统由多台处理机、多个存储模块和一个互连网络组成，每台处理机执行自己的指令，操作数也是各取各的。MIMD结构中每个处理器都可以单独编程，因而这种结构的可编程能力是最强的。但由于要用大量的硬件资源解决可编程问题，硬件利用率不高。

1.2.2 DSP+ASIC结构

随着大规模可编程器件的发展，采用DSP+ASIC结构的信号处理系统显示出了其优越性，正逐步得到重视。与通用集成电路相比, ASIC芯片具有体积小、重量轻、功耗低、可靠性高等几个方面的优势，而且在大批量应用时，可降低成本。
    现场可编程门阵列（FPGA）是在专用ASIC的基础上发展出来的，它克服了专用ASIC不够灵活的缺点。与其它中小规模集成电路相比，其优点主要在于它有很强的灵活性，即其内部的具体逻辑功能可以根据需要配置，对电路的修改和维护很方便。目前，FPGA的容量已经跨过了百万门级，使得FPGA成为解决系统级设计的重要选择方案之一。
   DSP+FPGA结构最大的特点是结构灵活，有较强的通用性，适于模块化设计，从而能够提高算法效率；同时其开发周期较短，系统易于维护和扩展，适合于实时信号处理。
    实时信号处理系统中，低层的信号预处理算法处理的数据量大，对处理速度的要求高，但运算结构相对比较简单，适于用FPGA进行硬件实现，这样能同时兼顾速度及灵活性。高层处理算法的特点是所处理的数据量较低层算法少，但算法的控制结构复杂，适于用运算速度高、寻址方式灵活、通信机制强大的DSP芯片来实现。

1.2.3 线性流水阵列结构

在我们的工作中，设计并实现了一种实时信号处理结构。它采用模块化设计和线性流水阵列结构(图1.1)。

……………

图1.1 线性流水列阵

这种线性流水阵列结构具有如下特点：
    ·接口简单。各处理单元（PU）之间采用统一的外部接口。
    ·易于扩充和维护。各个PU的内部结构完全相同，而且外部接口统一，所以系统很容易根据需要进行硬件的配置和扩充。当某个模块出现故障时，也易于更换。
    ·处理模块的规范结构能够支持多种处理模式，可以适应不同的处理算法。
    每个PU的核心由DSP芯片和可重构器件FPGA组成，另外还包括一些外围的辅助电路，如存储器、先进先出（FIFO）器件及FLASH ROM等。可重构器件电路与DSP处理器相连，利用DSP处理器强大的I/O功能实现单元电路内部和各个单元之间的通信。从DSP的角度来看，可重构器件FPGA相当于它的宏功能协处理器（Co-processer）。
PU中的其它电路辅助核心电路进行工作。DSP和FPGA各自带有RAM，用于存放处理过程所需要的数据及中间结果。FLASH ROM中存储了DSP的执行程序和FPGA的配置数据。先进先出（FIFO）器件则用于实现信号处理中常用到的一些操作，如延时线、顺序存储等。
每个PU单独做成一块PCB，各级PU之间通过插座与底板相连。底板的结构很简单，主要由几个串连的插座构成，其作用是向各个PU提供通信通道和电源供应。可以根据需要安排底板上插座的个数，组成多级线性阵列结构。这种模块化设计的突出优点在于，它使得对系统的功能扩充和维护变得非常简单。需要时，只要插上或更换PU电路板，就可以实现系统的扩展和故障的排除。每一级PU中的DSP都有通信端口与前级和后级PU电路板相连，可以很方便地控制和协调它们之间的工作。

1.3 DSP+FPGA系统的特点和优点

通用DSP的优点是通过编程可以广泛应用到产品中，并且主流制造商生产的DSP已能满足算法控制结构复杂、运算速度高、寻址方式灵活和通信性能强大等需求，但是传统的DSP采用冯.诺依曼（von Neumann）结构或某种类型扩展，本质上是串行的，因此在数据量大、对处理速度要求高的场合，其运算结构相对比较简单的底层信号处理算法显示不出其优点。这时，如果将FPGA作为协处理器，发挥FPGA的并行性，将算法中简单却大量重复的部分采用FPGA进行硬件实现，DSP就可以适时地从繁重的运算中解脱出来，进行其它更重要的工作，如控制采样、与FPGA之间的通信、控制数据流动等。这种做法不但效率更高，而且可以节省大量的时间。采用DSP+FPGA的数字硬件系统可以把二者优点结合在一起，兼顾速度和灵活性，既满足底层信号处理要求，又满足高层信号处理要求，提高了算法效率，适用于实时信号处理。
DSP+FPGA系统的核心由DSP芯片和现场可编程器件FPGA组成。另外还包括一些外围的辅助电路，如存贮器、先进先出（FIFO）器件及存储器等。FPGA电路与DSP相连，利用DSP处理器强大的I/O功能实现系统内部的通信。从DSP角度看，FPGA相当于它的宏功能协处理器，外围电路辅助核心进行工作。DSP和FPGA各自带有RAM，用于存放处理过程所需要的数据及中间结果，FLASH ROM中存储了DSP执行程序和FPGA的配置数据，先进先出（FIFO）器件则用于实现信号处理中常用到的一些操作。

1.4 VHDL硬件描述语言简介[3]

VHDL是Very High Speed Integrated Circuit Hardware Description Language 的英文缩写。是一种快速的电路设计工具，功能涵盖了电路描述、电路合成、电路仿真等三大电路设计工作。
VHDL原来是由美国国防部于70年代开始研究发展的电路设计工具，并于1987年成为IEEE的一种标准语言。原先发展的目的是为了将电子电路的设计和其内部的含意，用文件的方式储存起来，以便其它人能够轻易地了解电路的设计意义。这至少意味着两种重大的改变：
● 设计电路可以透过文字描述的方式，完成设计工作。
● 电子电路也可以当作文件一样来储存。
从VHDL每年能够以超过30%的速度快速成长便可以知道VHDL电路设计语言不但功能强大，而且能够满足各个设计阶层的设计工作，从ASIC设计到PCB系统设计，都能够轻易地达成设计工作者的需求。在产品更换快速的今天，VHDL可以说是符合市场需求，VHDL有以下之优点：
● 功能强大。
● 设计灵活。
● 有各种不同的描述风格。
● 可流通性与可移植性。

第二章最小二乘递推算法及原理概述

2.1 最小二乘算法

2.1.1 最小二乘算法原理[4]
最小二乘法可以用来处理一组数据, 可以从一组测定的数据中寻求变量之间的依赖关系, 这种函数关系称为经验公式.假定实验测得变量之间的个数据,，…，，则在平面上, 可以得到个点, 这种图形称为“散点图”, 从图中可以粗略看出这些点大致散落在某直线旁, 我们认为与之间近似为一线性函数, 下面介绍求解步骤.
考虑函数, 其中和是待定常数. 如果在一条直线上, 可以认为变量之间的关系为. 但一般说来, 这些点不可能在同一直线上. 记, 它反映了用直线来描述,时, 计算值与实际值产生的偏差. 当然要求偏差越小越好, 但由于可正可负, 因此不能认为总偏差时, 函数就很好地反映了变量之间的关系, 因为此时每个偏差的绝对值可能很大. 为了改进这一缺陷, 就考虑用来代替. 但是由于绝对值不易作解析运算, 因此, 进一步用来度量总偏差. 因偏差的平方和最小可以保证每个偏差都不会很大. 于是问题归结为确定中的常数和 , 使为最小. 用这种方法确定系数 , 的方法称为最小二乘法.
2.1.2 最小二乘算法的应用

1. 最小二乘法在足底矫形器交流伺服数控平台CAM中的应用
足底矫形器作为一种以减轻足底骨骼肌肉系统的功能障碍为目的的支撑装置（常人称之为：鞋内托、为缓解局部应力或增加足部穴位按摩功能的称之为舒适性鞋垫），用于矫治足部各种疾患。在国内，它的生产已经步入数控机床的高技术生产空间，涉及到硬件的合理设计与选取、CAD/CAM系统的进一步优化和机床本体的高精度运行。
对足底矫形器特征进行分类，分为行起始点、中间点、结束点、行转折点。在中间点加工过程中，为提高加工速度，在软件编程控制算法中引入最小二乘法，即在固定的每个值对应的Y轴上，平均每5个点进行一次走刀加工。对行转折做了“抬刀保护”当转折的X轴距离相差较大时可能会出现因三轴联动铣刀球面对矫形器表面造成的“连带铣削”。为加快生产速度，编成中将最小二乘法应用于面向制造的加工方法。
在行加工的过程中，改掉原来点对点的加工方式，即不再是为了减少原来步进电机的低速震荡每走过一点都需要电机的停止、启动；而是采用最小二乘法，即在符合产品的质量标准和舒适性保证、满足矫形器的表面光滑性要求的前提下，充分利用松下交流伺服电机低速运转平稳的优越性，每五个加工点进行一次性走刀，极大地缩短了加工时间、提高了生产效率。
2. 基于加权最小二乘法的机车车辆零部件可靠性分析
针对机车车辆零部件的现场数据特点并结合航空部门的实践经验,总结了机车车辆零部件现场数据的收集方法,并提出以平均故障率大小为加权依据,采用加权最小二乘法对现场数据进行三参数威布尔分布拟合计算,该方法可更加准确地描述机车车辆零部件的可靠性和故障情况。
根据目前我国机车车辆的使用-维修特点,在机务段和修理工厂所收集到的现场数据都属于随机截尾数据,且具有以下两个突出特点：
（1）数据类型复杂。
（2）删除比大、短寿命数据多。
机车车辆零部件现场数据删除比大，中、长期寿命数据少的特点，提出以平均故障率大小为加权依据，采用相关系数优化法和加权最小二乘法对三参数威布尔分布进行拟合计算，该方法可更加准确地描述零部件在高故障率时段的可靠性和故障情况。利用该方法可开发出操作简单、界面友好的可靠性分析软件，从而为机务段或修造工厂评估零部件寿命和制定检修周期提供比较科学的依据。
3. 镜像映射法及递推最小二乘法在GPS 伪距导航定位解算中的应用
全球定位系统GPS ( Global Positioning System) 是美国第二代卫星导航系统,该系统由24 颗卫星组成,分布在6 条轨道上。地球表面的任何地区在任何时间都可至少同步接收4 颗以上的卫星信号,从而实现了全球实时导航定位。从GPS 伪距导航定位原理可知,用户通过接收机对不少于四颗卫星进行伪距测量,然后利用导航电文提供的卫星位置和伪距观测值,即可以解算出接收机的位置。伪距测量受卫星时钟和星历、选择可用性(SA) 、电离层延迟、多径延迟和热噪声等误差因素的影响,使导航定位精度下降。同时为满足社会各领域不断扩大的应用需求, GPS 导航和定位要求时间越来越短,精度越来越高。特别是高动态目标要求定位设备精度高、实时性强、体积小、重量轻,这些条件难以满足,即使满足其造价也非常高。针对以上的各项要求,有必要提出一种有效方法,既可以保证GPS 导航定位精度又可以解决实时动态快速性跟踪问题。本文提出了将镜像映射法和递推最小二乘法相结合的方法来解决以上的问题。其基本思想如图1 所示,首先用镜像映射法算出导航定位的初始参数,作为递推的初值,再根据实时所选取的最佳卫星所给出的信息不断地进行最小二乘递推,从而可以实时、快速给出导航定位参数- 接收机三维位置参数和时钟误差参数。

图2.1 镜像映射法及递推最小二乘法在GPS伪距导航定位解算中的应用示意图

由上面的几个例子可以很明显的看出，最小二乘算法的应用是十分的广泛的，在诸多的科学与技术中，都充分发挥了最小二乘算法的计算精度高，误差小，计算量小等特点。在许多要求计算精度高的领域当中，其都发挥了不可替代的作用。

2.2 最小二乘递推算法

2.2.1 最小二乘递推算法及其原理概述

设m次独立实验，得到m个观测值：。t表示时间或其它物理量，为便于计算采用多项式
公式（2.1）
表示z与t之间的函数关系。其中为已知的确定性函数，为n个待定的未知数。所谓的最小二乘法即是要选择的参数使得观测值与对应的函数的偏差平方和最小，将方程写成矩阵形式为
公式（2.2）
根据偏差平方和最小条件求得待定估计(矩阵形式)：
公式（2.3）
如果对不同的误差项加不同的权，假定,，得到为最优的加权矩阵。当权为1时，R为单位阵I。
由于最小二乘算法需要同时用到所有的测量数据，当测量数据很多时，要求计算机有很大的存储量。在实际处理过程中，可先处理已经得到的一批数据，得到X的近似估值，来了新的数据后，再对原估值进行修改，这样可以减少计算机的存储量。假定已经进行了k次观测，得到了k个观测值，用和表示相应的向量和矩阵。
观测方程：
公式（2.4）
先用加权最小二乘法处理这k个观测值可以得到X的估计值
公式（2.5）
令，则
现在又得到了第k+1个观测值，合并可得到
公式（2.6）
通过处理第k+1个观测值，求得估值
公式（2.7）
利用矩阵求逆原理和几步简单推算得到递推关系：
公式（2.8）
公式（2.9）

2.2.2 最小二乘递推算法的优点

最小二乘法在计算时需要大量的测量数据，以保证仿真程度最大化的接近理论值，而在普通的最小二乘法中，大量的数据导致计算机存储空间被过多的占用，计算时，多为重复而且复杂的操作，使得计算机的效率大为降低。而采用递推算法，则可以解决上面的诸多问题，只使用少量的存储空间，提高了计算机的效率。所以在一些要求性比较高的系统中，比如实时系统等，采用最小二乘递推算法更为优秀，得到的结果也更加接近理论值，使得实验更为准确。

第三章 DSP及FPGA芯片原理和开发应用

3.1 DSP系统[6]

3.1.1 DSP系统构成

图3.1 所示为一个典型的DSP 系统。图中的输入信号可以有各种各样的形式。例如，它可以是麦克风输出的语音信号或是电话线来的已调数据信号，可以是编码后在数字链路上传输或存储在计算机里的摄像机图像信号等。

输入输出

图3.1 典型的DSP系统

输入信号首先进行带限滤波和抽样，然后进行A/D（Analog to Digital）变换将信号变换成数字比特流。根据奈奎斯特抽样定理，为保证信息不丢失，抽样频率至少必须是输入带限信号最高频率的2 倍。
DSP 芯片的输入是A/D 变换后得到的以抽样形式表示的数字信号，DSP 芯片对输入的数字信号进行某种形式的处理，如进行一系列的乘累加操作（MAC）。数字处理是DSP的关键，这与其它系统（如电话交换系统）有很大的不同，在交换系统中，处理器的作用是进行路由选择，它并不对输入数据进行修改。因此虽然两者都是实时系统，但两者的实时约束条件却有很大的不同。最后，经过处理后的数字样值再经D/A（Digital to Analog）变换转换为模拟样值，之后再进行内插和平滑滤波就可得到连续的模拟波形。
必须指出的是，上面给出的DSP 系统模型是一个典型模型，但并不是所有的DSP 系统都必须具有模型中的所有部件。如语音识别系统在输出端并不是连续的波形，而是识别结果，如数字、文字等；有些输入信号本身就是数字信号（如CD：Compact Disk），因此就不必进行模数变换了。

3.1.2 DSP系统的特点

数字信号处理系统是以数字信号处理为基础，因此具有数字处理的全部优点：
(1) 接口方便。DSP 系统与其它以现代数字技术为基础的系统或设备都是相互兼容的，与这样的系统接口以实现某种功能要比模拟系统与这些系统接口要容易得多；
(2) 编程方便。DSP 系统中的可编程DSP 芯片可使设计人员在开发过程中灵活方便地对软件进行修改和升级；
(3) 稳定性好。DSP 系统以数字处理为基础，受环境温度以及噪声的影响较小，可靠性高；
(4) 精度高。16 位数字系统可以达到10−5 的精度；
(5) 可重复性好。模拟系统的性能受元器件参数性能变化比较大，而数字系统基本不受影响，因此数字系统便于测试、调试和大规模生产；
(6) 集成方便。DSP 系统中的数字部件有高度的规范性，便于大规模集成。
当然，数字信号处理也存在一定的缺点。例如，对于简单的信号处理任务，如与模拟交换线的电话接口，若采用DSP 则使成本增加。DSP 系统中的高速时钟可能带来高频干扰和电磁泄漏等问题，而且DSP 系统消耗的功率也较大。此外，DSP 技术更新的速度快，数学知识要求多，开发和调试工具还不尽完善。
虽然DSP 系统存在着一些缺点，但其突出的优点已经使之在通信、语音、图像、雷达、生物医学、工业控制、仪器仪表等许多领域得到越来越广泛的应用。

3.1.3 DSP系统的设计过程

总的来说，DSP 系统的设计还没有非常好的正规设计方法。图3.2 所示是DSP 系统设计的一般过程。

图3.2 DSP系统的设计流程

在设计 DSP 系统之前，首先必须根据应用系统的目标确定系统的性能指标、信号处理的要求，通常可用数据流程图、数学运算序列、正式的符号或自然语言来描述。第二步是根据系统的要求进行高级语言的模拟。一般来说，为了实现系统的最终目标，需要对输入的信号进行适当的处理，而处理方法的不同会导致不同的系统性能，要得到最佳的系统性能，就必须在这一步确定最佳的处理方法，即数字信号处理的算法（Algorithm），因此这一步也称算法模拟阶段。例如，语音压缩编码算法就是要在确定的压缩比条件下，获得最佳的合成语音。算法模拟所用的输入数据是实际信号经采集而获得的，通常以计算机文件的形式存储为数据文件。如语音压缩编码算法模拟时所用的语音信号就是实际采集而获得并存储为计算机文件形式的语音数据文件。有些算法模拟时所用的输入数据并不一定要是实际采集的信号数据，只要能够验证算法的可行性，输入假设的数据也是可以的。
在完成第二步之后，接下来就可以设计实时DSP 系统，实时DSP 系统的设计包括硬件设计和软件设计两个方面。硬件设计首先要根据系统运算量的大小、对运算精度的要求、系统成本限制以及体积、功耗等要求选择合适的DSP 芯片。然后设计DSP 芯片的外围电路及其它电路。软件设计和编程主要根据系统要求和所选的DSP 芯片编写相应的DSP 汇编程序，若系统运算量不大且有高级语言编译器支持，也可用高级语言（如C 语言）编程。由于现有的高级语言编译器的效率还比不上手工编写汇编语言的效率，因此在实际应用系统中常常采用高级语言和汇编语言的混合编程方法，即在算法运算量大的地方，用手工编写的方法编写汇编语言，而运算量不大的地方则采用高级语言。采用这种方法，既可缩短软件开发的周期，提高程序的可读性和可移植性，又能满足系统实时运算的要求。
DSP 硬件和软件设计完成后，就需要进行硬件和软件的调试。软件的调试一般借助于DSP 开发工具，如软件模拟器、DSP 开发系统或仿真器等。调试DSP 算法时一般采用比较实时结果与模拟结果的方法，如果实时程序和模拟程序的输入相同，则两者的输出应该一致。应用系统的其它软件可以根据实际情况进行调试。硬件调试一般采用硬件仿真器进行调试，如果没有相应的硬件仿真器，且硬件系统不是十分复杂，也可以借助于一般的工具进行调试。
系统的软件和硬件分别调试完成后，就可以将软件脱离开发系统而直接在应用系统上运行。当然，DSP 系统的开发，特别是软件开发是一个需要反复进行的过程，虽然通过算法模拟基本上可以知道实时系统的性能，但实际上模拟环境不可能做到与实时系统环境完全一致，而且将模拟算法移植到实时系统时必须考虑算法是否能够实时运行的问题。如果算法运算量太大不能在硬件上实时运行，则必须重新修改或简化算法。

3.2 可编程DSP芯片

3.2.1 什么是DSP芯片

DSP 芯片，也称数字信号处理器，是一种特别适合于进行数字信号处理运算的微处理器，其主要应用是实时快速地实现各种数字信号处理算法。根据数字信号处理的要求，DSP 芯片一般具有如下主要特点：
(1) 在一个指令周期内可完成一次乘法和一次加法；
(2) 程序和数据空间分开，可以同时访问指令和数据；
(3) 片内具有快速 RAM，通常可通过独立的数据总线在两块中同时访问；
(4) 具有低开销或无开销循环及跳转的硬件支持；
(5) 快速的中断处理和硬件I/O 支持；
(6) 具有在单周期内操作的多个硬件地址产生器；
(7) 可以并行执行多个操作；
(8) 支持流水线操作，使取址、译码和执行等操作可以重叠执行。
当然，与通用微处理器相比，DSP 芯片的其它通用功能相对较弱些。

3.2.2 DSP芯片的分类

DSP 芯片可以按照下列三种方式进行分类。
1．按基础特性分
这是根据DSP 芯片的工作时钟和指令类型来分类的。如果在某时钟频率范围内的任何时钟频率上，DSP 芯片都能正常工作，除计算速度有变化外，没有性能的下降，这类DSP芯片一般称为静态DSP 芯片。例如，日本OKI 电气公司的DSP 芯片、TI 公司的 TMS320C2XX 系列芯片属于这一类。
如果有两种或两种以上的DSP 芯片，它们的指令集和相应的机器代码及管脚结构相互兼容，则这类DSP 芯片称为一致性DSP 芯片。例如，美国TI 公司的TMS320C54X 就属于这一类。
2．按数据格式分
这是根据DSP 芯片工作的数据格式来分类的。数据以定点格式工作的DSP 芯片称为定点DSP 芯片，如TI 公司的TMS320C1X/C2X、TMS320C2XX/C5X、TMS320C54X/C62XX系列，AD 公司的ADSP21XX 系列，AT&T 公司的DSP16/16A，Motolora 公司的MC56000 等。以浮点格式工作的称为浮点DSP 芯片，如TI 公司的TMS320C3X/C4X/C8X，AD 公司的ADSP21XXX 系列，AT&T 公司的DSP32/32C，Motolora 公司的MC96002 等。不同浮点DSP 芯片所采用的浮点格式不完全一样，有的DSP 芯片采用自定义的浮点格式，如TMS320C3X，而有的DSP 芯片则采用IEEE 的标准浮点格式，如Motorola 公司的MC96002、FUJITSU 公司的MB86232 和ZORAN 公司的ZR35325 等。
3．按用途分
按照DSP 的用途来分，可分为通用型DSP 芯片和专用型DSP 芯片。通用型DSP 芯片适合普通的DSP 应用，如TI 公司的一系列DSP 芯片属于通用型DSP 芯片。专用DSP 芯片是为特定的DSP 运算而设计的，更适合特殊的运算，如数字滤波、卷积和FFT，如Motorola 公司的DSP56200，Zoran 公司的ZR34881，Inmos 公司的IMSA100 等就属于专用型DSP 芯片。

3.2.3 DSP芯片的应用

自从20 世纪70 年代末80 年代初DSP 芯片诞生以来，DSP 芯片得到了飞速的发展。DSP 芯片的高速发展，一方面得益于集成电路技术的发展，另一方面也得益于巨大的市场。在近20 年时间里，DSP 芯片已经在信号处理、通信、雷达等许多领域得到广泛的应用。目前，DSP 芯片的价格越来越低，性能价格比日益提高，具有巨大的应用潜力。DSP芯片的应用主要有：
(1) 信号处理——如数字滤波、自适应滤波、快速傅立叶变换、相关运算、谱分析、卷积、模式匹配、加窗、波形产生等；
(2) 通信——如调制解调器、自适应均衡、数据加密、数据压缩、回波抵消、多路复用、传真、扩频通信、纠错编码、可视电话等；
(3) 语音——如语音编码、语音合成、语音识别、语音增强、说话人辨认、说话人确认、语音邮件、语音存储等；
(4) 图形/图像——如二维和三维图形处理、图像压缩与传输、图像增强、动画、机器人视觉等；
(5) 军事——如保密通信、雷达处理、声纳处理、导航、导弹制导等；
(6) 仪器仪表——如频谱分析、函数发生、锁相环、地震处理等；
(7) 自动控制——如引擎控制、声控、自动驾驶、机器人控制、磁盘控制等；
(8) 医疗——如助听、超声设备、诊断工具、病人监护等；
(9) 家用电器——如高保真音响、音乐合成、音调控制、玩具与游戏、数字电话/电视等。
随着DSP 芯片性能价格比的不断提高，可以预见DSP 芯片将会在更多的领域内得到更为广泛的应用。

3.3 PLD发展概况[8]

PLD出现的背景
（1）.电路集成度不断提高
SSIMSILSIVLSI
（2）.计算机技术的发展使EDA技术得到广泛应用
（3）.设计方法的发展
自下而上自上而下
（4）.用户需要设计自己需要的专用电路
专用集成电路（ASIC－Application Specific Integrated Circuits）开发周期长，投入大，风险大
可编程器件PLD：开发周期短，投入小，风险小
PLD器件的优点
（1）.集成度高，可以替代多至几千块通用IC芯片
极大减小电路的面积，降低功耗，提高可靠性
（2）.具有完善先进的开发工具
提供语言、图形等设计方法，十分灵活
通过仿真工具来验证设计的正确性
（3）.可以反复地擦除、编程，方便设计的修改和升级
（4）.灵活地定义管脚功能，减轻设计工作量，缩短系统开发时间
（5）.保密性好
PLD的发展趋势
（1）.向高集成度、高速度方向进一步发展
最高集成度已达到400万门
（2）.向低电压和低功耗方向发展，5V3.3V2.5V1.8V 更低
（3）.内嵌多种功能模块
RAM ，ROM ，FIFO ，DSP ，CPU
（4）.向数、模混合可编程方向发展

3.4 FPGA的基本结构

FPGA结构原理图
内部结构称为LCA（Logic Cell Array）由三个部分组成：
（1）．可编程逻辑块（CLB）
（2）．可编程输入输出模块（IOB）
（3）．可编程内部连线（PIC）

图3.3 FPGA结构原理图

FPGA与CPLD的区别
(1). FPGA器件含有丰富的触发器资源，易于实现时序逻辑，如果要求实现较复杂的组合电路则需要几个CLB结合起来实现。CPLD的与或阵列结构，使其适于实现大规模的组合功能，但触发器资源相对较少。
(2)．FPGA为细粒度结构，CPLD为粗粒度结构。FPGA内部有丰富连线资源，CLB分块较小，芯片的利用率较高。CPLD的宏单元的与或阵列较大，通常不能完全被应用，且宏单元之间主要通过高速数据信道连接，其容量有限，限制了器件的灵活布线，因此CPLD利用率较FPGA器件低。
(3). FPGA为非连续式布线，CPLD为连续式布线。FPGA器件在每次编程时实现的逻辑功能一样，但走的路线不同，因此延时不易控制，要求开发软件允许工程师对关键的路线给予限制。CPLD每次布线路径一样，CPLD的连续式互连结构利用具有同样长度的一些金属线实现逻辑单元之间的互连。连续式互连结构消除了分段式互连结构在定时上的差异，并在逻辑单元之间提供快速且具有固定延时的通路。CPLD的延时较小。

3.5 可编程逻辑器件的设计

PLD的设计步骤如图3.4所示

图3.4 PLD的设计步骤

3.5.1 设计输入

(1).原理图输入
使用组件符号和连线等描述
比较直观，但设计大规模的数字系统时则显得繁琐
(2).VHDL语言输入
逻辑描述功能强
成为国际标准，便于移植
(3).原理图与VHDL的联系与高级语言与汇编语言类似

3.5.2 设计处理

(1).综合和优化
优化：将逻辑化简，去除冗余项，减少设计所耗用的资源
综合：将模块化层次化设计的多个文件合并为一个网表，使设计层次平面化
(2).映射
把设计分为多个适合特定器件内部逻辑资源实现的逻辑小块的形式
(3).布局与布线
将已分割的逻辑小块放到器件内部逻辑资源的具体位置并利用布线资源完成各功能块之间的连接
(4).生成编程文件
生成可供器件编程使用的数据文件

3.5.3 模拟仿真

(1).功能仿真:不考虑信号传输和器件的延时
(2).时序仿真:不同器件的内部延时不一样，不同的布局、布线延时也会有比较大的不同。
(3).在线验证:利用实现手段测试器件最终功能和性能指标

第四章设计中基本逻辑电路模块的设计

4.1加法器模块的设计

4.1.1 加法器原理

从最小二乘递推算法的公式中可以看出，加法运算是被大量使用的，所以在设计中应当设计加法器模块，使得加法运算都可以由此模块进行，节省了主电路的复杂程度。学过VHDL的人都知道，VHDL是提供了操作符“＋”，而且在很多情况下，我们是可以直接用这个加操作符的。但是，VHDL提供的加法操作只能给出“和”，却无法给出“进位”。例如我们在设计计数器的时候经常用到的加1操作，对于一个8位的计数器，当计数器的结果为0xff时，如果在加1就为0×00。实际上，结果应该时0×100，而最高位的1就是进位，我们无法利用。而我们的实际设计中，不仅要用“和”，有时还要用到两个数相加的进位。所以有必要用VHDL来描述一个带进位的加法器。加法器实际上完全可以由组合逻辑实现，但在频率较高的场合下工作时，容易产生毛刺。所以整个加法器设计成时序电路的形式，所有的加操作都是时钟的上升沿触发的。
首先应写出全加器的真值表，如表4.1所示：

表4.1 全加器真值表
输入
输出
A
B
CI
S
CO
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1

4.1.2 加法器电路结构

根据真值表写出电路输出端的逻辑表达式是：
公式（4.1）
公式（4.2）
因此，全加器可由两个异或门和3个与非门组成，其电路结构如图4.1所示：

A
B S
CI

图4.1 全加器电路结构

4.1.3 加法器程序

由此可得全加器电路的VHDL描述为
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
entity fulladder is
port(
  reset : in std_logic;
  clk : in std_logic;
  operand1: in std_logic_vector(7 downto 0);
  operand2: in std_logic_vector(7 downto 0);
  carry : out std_logic;
  sum : out std_logic_vector(7 downto 0)
  );
end fulladder;
architecture Behavioral of fulladder is
begin
     process(reset,clk)
     variable sum_t : std_logic_vector(7 downto 0);
variable carry_t: std_logic;
begin
       if(reset = ‘0′) then
   carry < = '0';
   sum <= (others => ‘0′);
  elsif(rising_edge(clk)) then
   carry_t := ‘0′;
   for i in 0 to 7 loop
    sum_t(i) := operand1(i) xor operand2(i) xor carry_t;
    carry_t := (operand1(i) and operand2(i)) or (carry_t and (operand1(i) or operand2(i)));
   end loop;
  carry <= carry_t;
  sum <= sum_t;
  end if;
     end process;
end Behavioral;
通过对上述代码的综合（XST)，布局布线和后仿真，可以发现整个加法器是可以正常工作的。也没有毛刺的现象，避免了逻辑电路设计中最忌讳的一点。仿真时钟是100mhz。

4.1.4 加法器仿真结果

仿真结果如下图4.2所示：

图4.2 全加器仿真结果图

当reset开始工作时，加法器开始工作，上图为二进制加法显示。转换为十进制以后，结果更加明显，结果如下图：

图4.3 全加器仿真结果图

4.2 乘法器模块的设计[11]

4.2.1 乘法器原理

同加法器一样，在算法的运算过程当中，乘法更加被频繁的使用，且使用次数更高于加法，尤其在矩阵的乘法计算中，更是如此。因此，乘法器模块的设计更加是设计的重点之一。
乘法器基本原理：两个二进制数之相乘如十进制数相乘一样。于图4.4为四位做徒手乘法运算图。首先由右至左逐次检查乘数位是否为1，如为1，将被乘数做适当地移位至适当的位置；如为0，将0放置适当位置。其次将所有移位之被乘数求其和即为所得之积，此积应为八位。图4.5为乘法中硬件的运算情形，利用多重加法器来完成。即每一步中一个四位加法器可用来计算其新的部分乘积。于计算进行时最不重要位在连续加法中，并不受到影响；因此他们可直接放到最后之乘积中。

图4.4 徒手乘法

图4.5 乘法运算架构

乘法器制作概念：现在我们可以运用最简单且直观的方式来完成所需要的硬件电路描述，所以在往后的程序中我们使用AND GATE来做部分乘积的运算，使用全加器来计算部分乘积的最后结果。
下面为全加器的布尔代数式：
公式（4.3）
公式（4.4）
其中，A、B分别代表两个输入操作数；为前一个位所作的加法进位，S为相加后的结果；为相加后的进位，也就是连接至下一个全加器的。这两个代数式是全加器中的内部运作，透过全加器的运算能将所有的部分乘积相加，以得到我们所要的乘积。

4.2.2 乘法器结构

经过上述乘法器原理之解说，我们可以将电路架构用较直观的方式表现出来，如图4.6所示。我们将部分乘积分别放到PPXY中，例如PP00，即代表乘数中第0个位，和被乘数第0个位作运算，其结果放置PP00，其它都依此类推。一个全加器有两个输出，一个为Sum，另一个为Cout。所以我们用PSXY来表示第X列的全加器运算出来的Sum；用PCXY来表示第X列的全加器运算出来的Cout。必须注意的是上面三列的全加器是用来做部分乘积相加的，而最底下的一组全加器是用来让上一列之PS和PC的输出，做完最后运算之后，再将结果传送给P0至P7的Product，这就是最后的结果。于是我们就可以直接用这架构图和一些运算的方式，利用VHDL来写出乘法器的程序。

图4.6 乘法器电路架构图

4.2.3 乘法器仿真结果

VHDL程序在附录中，其仿真结果如图4.7所示：

图4.7 乘法器仿真结果图

十进制显示：

图4.8 乘法器仿真结果图

从图4.8中可以看出，因为乘法器为4×4的，所以当数据输入超过4位时候，乘法器就会出错，得出的结果不是正确的数值。所以在输入数据时候，以及程序的设计当中，要很注意数据的位数和乘法器所允许的位数应当相同。
当数据位数很大时候，比如需要16×16位的乘法器，则可以通过两个4×4的乘法器得到所需要的乘法器。这一点在设计中也应当注意。

4.2.4 乘法器位数不同的比较

在上面的仿真中可以看出，乘法器的位数决定了结果的正确性，不同位数的乘法器所能接受的数值也是不同的。如上面的仿真结果可以看出，4位乘法器的数值不能大于15，超过15的部分表示为负值了，计算结果也是错误的。而4×4的乘法器输出数据值是8位的，同理，8×8的乘法器输出为16位数值，这一点在设计中也应注意到。下图为16×16位乘法器的仿真图，其所能接受的位数及数值大小明显要高于4×4位的乘法器。

图4.9 16×16位乘法器仿真结果

4.3 除法器模块的设计

4.3.1 除法器原理结构及流程图

如同加法器和乘法器一样，除法器也同样是设计中的基本逻辑电路，在算法的流程中，因为涉及到了矩阵的逆运算，所以除法程序是必不可少的模块，在矩阵求逆运算当中要大量使用除法运算。
除法器原理流程示意图：

图4.10 除法器流程图

4.3.2 除法器仿真结果

由此可写出除法器的程序见附录，经过仿真可得到实验结果如图：
二进制显示：

图4.11 除法器仿真结果图

十进制显示：

图4.12 除法器仿真结果图

由结果可以看出，因为是4位的除法器，所以当数据的输入超过4位时候，结果是错误的，这一点和乘法器的原理是相同的，在数据的输入时候一定要注意数据位数与除法器的位数相同。这样才可以保证实验的结果是正确的。
当以上的基本逻辑单元设计完成以后，就可以进行算法的整体结构设计了，因为对于加法器、乘法器和除法器来说，已经设计好了程序模块，所以在整体的设计当中，需要应用这些模块时候，只需要调用出来使用即可，大大的降低了程序的复杂程度，提高了程序算法的速度与效率。为更好的设计程序算法打下了良好的基础。
第五章算法实现步骤及方法

5.1 算法流程图

图5.1 算法流程图
由算法的原理可得流程图如上，在算法的流程中，可以很明显的看出递推的步骤，在流程中，首先进行的是数据的输入，先把实验所需要的数据全部输入进去，这样可以得到结果的第一步初值，并由这个初值经过递推，就可以得到任意次数的递推值，即实验结果数据。

5.2 DSP部分的设计

在算法实现的过程中，DSP主要负责的工作是协调与FPGA的数据传递、递推初值得计算以及矩阵求逆的运算。在设计中使用TMS320C3X系列DSP，同时为了满足实时信号处理的精度要求，计算过程都采用32位的单精度浮点数。DSP中单精度浮点数表示的格式如图5.2所示。其高8位为以2为底的指数部分，采用二进制补码形式表示；第23位为符号位，表示的是整个数据的符号，为0时表示正数，为1时则表示负数；0-22位表示尾数部分，即小数点后面的部分。需要说明的是，这只是32位的规格化表示方法，通用的计算浮点数实际上是33位的：。其中，是符号位的值取反，f是尾数部分，e是指数部分的十进制形式。

31 24 23 22 0
Exponent
Sign
Fraction
Mantissa
图5.2 DSP中单精度浮点数的格式

5.3 FPGA部分的设计

因为在设计过程中的难点是两个递推关系公式的计算，在这两个公式中大量重复性的计算都是为了完成矩阵的乘和加，所以这部分的设计重点是编制DSP浮点格式数据的乘法器、加法器，以及进行矩阵的运算。在设计过程中，用FPGA来完成DSP格式浮点数的加法及乘法运算需要消耗一定的资源，如使用stratix芯片完成单精度浮点乘法需要300多个逻辑单元，完成单精度浮点加法需要800多个逻辑单元。在资源允许的情况下调用多个乘法器和加法器，不但可以充分发挥FPGA并行性的优点，减轻DSP的负担，运算效率也要比本身软件计算高。具体设计时，令观测值与t之间的关系如下：

则递推过程中涉及3*3的矩阵乘法，因此就设计由乘法器和加法器构成的运算单元，示意图如图5.3所示。

a1
b1 r1
r2
ss1
a2 ss2 ss3
b2

a3
b3
r3
r4=32’H80000000

图5.3 运算单元示意图

图中mux_1、mux_2、mux_3为调用的3个浮点乘法器，add_1、add_2、add_3为调用的3个浮点加法器，用VHDL语言编写的调用程序如下：
ENTITY module IS
PORT(clk,sel,a1,a2,a3,b1,b2,b3: IN STD_LOGIC;
r1,r2,r3,ss1,ss2:BUFFER STD_LOGIC;
ss3:OUT STD_LOGIC);
ARCHITECTURE module OF module IS
COMPONENT mux
PORT( a,b,clk,sel:IN STD_LOGIC;
r:OUT STD_LOGIC);
END COMPONENT;
COMPONENT add
PORT(a,b,clk,sel:IN STD_LOGIC;
r:OUT STD_LOGIC);
END COMPONENT
BEGIN
mux_1：mux PORT MAP(.clk(clk),.a(a1),.b(b1),.r(r1));
mux_2: mux PORT MAP(.clk(clk),.a(a2),.b(b2),.r(r2));
mux_3: mux PORT MAP(.clk(clk),.a(a3),.b(b3),.r(r3));
add_1: add PORT MAP(.clk(clk),.sel(sel),.m(r1),.n(r2),.ss(ss1));
add_2: add PORT MAP(.clk(clk),.sel(sel),.m(r3),.n(r4),.ss(ss2));
add_3: add PORT MAP(.clk(clk),.sel(sel),.m(ss1),.n(ss2),.ss(ss3));
END module
仿真结果如图5.4所示。

图5.4 仿真结果图

在图中可见，时序仿真延时两个时钟周期，而且第一个结果是“01400000”（32位十六进制换算成十进即为3）而不是应得的“80000000”（换算成十进制数即为0）。这是因为整个模块是分级进行运算的，在初始状态下，第二级运算（调用两个加法器的运算）的输入值默认为“00000000”（换算成十进制数即为1），所以才会得到“3” 的结果；另外“sel”信号是在编写加（减）法器模块时定义的，因为加法和减法的浮点运算有很多相通的地方，所以合并在一个模块中，以节省资源。当“sel”为“1”时，进行加法操作；为“0”时，进行减法操作。在流水线结构建立以后，每60ns就可以用这个运算单元计算出所求矩阵中的一个元素。
除了运算单元以外，FPGA部分的设计还要考虑到对存储单元所进行的操作，并最后通过状态机来发出控制信号的使能，控制各个模块间的协调工作（注意存、取数时一个周期的延时及运算单元在流水线建立前的延时）。在FPGA中的数据流向大致如图5.5所示。

送地址送乘数

图5.5 FPGA中数据流向示意图

5.4 DSP与FPGA接口部分的设计

DSP的外围电路主要是FLASH、ROM、SRAM，需要连接地址线、数据线和控制线。它需要连接主要包括模式连接、外部时钟、JTAG接口和电源等。FPGA外围电路主要是FLASH ROM和先进先出（FIFO）器件等，它需要连接的连线主要包括FPGA模式选择、外部时钟、JTAG接口、输出/输入接口、测试口和电源等。外围电路辅助核心电路进行工作。DSP和FPGA各自带有RAM，用于存放处理过程所需要的数据及中间结果。FLASH ROM中存储了DSP执行程序和FPGA的配置数据。因为利用FPGA进行重复性强的矩阵乘法及加、减法运算时操作数的表示方法都与DSP中浮点数的表示方法相同，所以不需要再进行格式的转换。

第六章结论

本文谈论了在DSP+FPGA体系结构下如何实现最小二乘递推算法，它属于嵌入式技术的设计及应用。最小二乘算法是一种被广泛使用的算法结构，在许多的系统中都有其应用的地方，因为它具有精度高、计算方便等特点。而最小二乘递推算法则是在最小二乘法之上的改进算法，它解决了最小二乘法里的一些弊端，比如存储量大，运算量大等，使得最小二乘递推算法的使用更为精准，比如在模型参数辨识、最优化决策、动态实时跟踪预测等多方面都得到了广泛的应用。
程序的设计使用的编程语言是硬件描述语言VHDL，这是一种专门为电子设计自动化（EDA）设计使用的语言，它可以很形式化的来描述数字系统的硬件电路。在程序的设计当中，主要解决了两个主要问题：
1.矩阵乘法的计算：在最小二乘递推算法的设计当中，涉及了大量的矩阵承法计算，这些计算多为模式相同，只是数值上有所改变而已，所以在设计当中，加入一个矩阵乘法模块，使得重复的计算只需要简单的代入乘法模块当中。
2.矩阵求逆的计算：在程序的运算中，最难解决的问题就是矩阵的求逆运算，因为求逆过程涉及大量的行列式等计算，这些计算是必不可少又相当繁琐复杂的。
在设计好上面两个模块之后，程序的设计就大为简化了。
本论文使用的是DSP+FPGA体系结构，这种结构具有灵活、有较强的通用性，适合于模块化设计，能够提高算法的效率，这种结构在信号处理系统体现了较强的优越性。在试验中，DSP负责算法的整体框架结构，不进行复杂的矩阵相乘等运算，这些复杂的重复的运算由FPGA部分解决，充分提高了算法的效率。

参考文献

[1]桑楠. 嵌入式系统原理及应用开发技术[M], 北京：北京航天航空大学出版社，2002.1～246.
[2]戴逸民. DSP+FPGA数字硬件系统设计与实现[J].世界电子元器件，2002（4）
[3]侯伯亨. VHDL硬件描述语言与数字逻辑电路设计[M]. 西安：西安电子科技大学出版社，2004. 1～246.
[4]施吉林. 计算机数值方法[M]. 北京：高等教育出版社，1999.62～125.
[5]刘碧玉. 高等数学教程[M]，长沙：中南大学出版社，2003.374～510.
[6]王念旭. DSP基础与应用系统设计[M]. 北京：北京航空航天大学出版社，2002.1～168.
[7]吴冬梅. DSP技术及应用[M], 北京：北京大学出版社，2006.1～200.
[8]翁木云. FPGA设计及应用[M]. 西安：西安电子科技大学出版社，2004.1～218.
[9]陈明义. 数字电子技术基础[M]. 长沙：中南大学出版社，2004.1～130.
[10]周祖成. 电子设计硬件描述语言VHDL[M]. 北京：北京学苑出版社，1994.1～120.
[11]许地申. 利用VHDL设计乘法器[EB/OL]. http://www.chit.edu.tw/pub/journal/29/29-2.pdf , 2007-5.
[12]Douglasl L.Perry. VHDL[M],New York: McGraw-Hill,1991.1～226.

附录

1.加法器程序：
2.乘法器程序：

3.除法器程序：

基于H.263编码的数据压缩算法的研究与实现

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 09-08-2009

标签：arithmetic, coding, decoding, H.263, video, 算法, 编码, 视频, 解码

0

目录
摘要…………………………………………………………Ⅰ
ABSTRACT…………………………………………………….Ⅱ
第一章绪论……………………………………………………1
1.1视频图像压缩的必要性和可行性………………………………….1
1.2视频图像压缩的历史、现状及趋势………………………………..2
1.3视频编码标准的发展背景与历程………………………………….3
1.4视频图像压缩编码的方法……………………………………….4
1.4.1基本编码方法简介…………………………………………4
1.4.2其他编码方法简介…………………………………………9
第二章H. 263压缩编码标准……………………………………….10
2.1 H.263标准概述…………………………………………….10
2.2 H.263编码标准的基本原理……………………………………11
2.3 H.263可选模式……………………………………………..21
2.4 H.263的码流格式……………………………………………23
第三章 H.263视频编码、解码模块的设计与实现………………………..28
3.1 TMNcodec32软件简介…………………………………………28
3.2 编码模块的实现…………………………………………….33
3.3 解码模块的实现…………………………………………….35
3.4 软件界面及结果…………………………………………….37
第四章结论…………………………………………………..43
参考文献……………………………………………………..44
致谢…………………………………………………………45

摘要

随着信息技术事业迅猛发展，传统的表达方式和信息传输方式早己经不能满足人们的社会需求。网络视频会议和可视电话等一系列新的多媒体技术应运而生，通过无线和互联网来传输视频信息是视频通信发展的趋势。但是由于有限的带宽和恶劣的通信环境，对极低码率视频编码技术的研究变得尤为重要。
H.263是ITU-T组织制定的一种视频编码标准，它主要用于极低速率的视频传输。目前的网络视频会议、可视电话等新技术无不依赖于先进的视频和音频技术。
在实现视频会议等系统的过程中，国内外对H.263技术所做的开发硬件方面实现的较多，但因价格昂贵使得难以普及，因此，有必要使用纯软件的方法来实现对H.263技术的开发研究。其特点是灵活、低成本和便于维护。
本论文重点研究了基于H.263视频编解码软件开发的方法。在此基础上，论文研究了基于H.263视频编解码软件算法编码和解码两个功能模块的具体实现方法。

关键词： H.263，视频，编码，解码，算法

ABSTRACT

With the rapid development in the information technology cause, traditional expression manner and information transmission manner are no more content to the people and social needs. The Internet video conference and Video Phone technology emerges as the times require, transmit video information through wireless and Internet is the trend of the development in video communication. Due to the limited bandwidth and abominable communication environment, researching in the low bit rate video compression encoding is special important.
H.263 is a video coding by ITU-T, which is mainly used to transmit visual signals in a low rate. At present, such new technology as web tele-meeting, visual telephone relies on advanced visual and audio techniques without exception.
In the process of realizing the systems like tele-meeting，the development is made by H.263 mainly in hard wares, which, however, difficult to widespread. Therefore, it’s necessary to conduct the research and development of H.263 in soft wares, whose qualities are flexible, cheep and easy to maintain.
The paper aims at the methods of development visual decoding soft wares by H.263, then discusses the specific methods to realize the two function of coding and decoding in software calculation.

Key Words: H.263，video，coding，decoding，arithmetic

第一章绪论

1.1 视频图像压缩的必要性和可行性
信息时代的重要特征是信息的数字化，数字化了的信息带来的“信息爆炸”。多媒体计算机系统技术是面向三维图形、立体声和彩色全屏幕运动画面的处理技术。数字计算机面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的存储和传输问题。数字化了的视频和音频信号的数据量是大得惊人的，下面列举几个未经压缩的数字化信息的例子:
（1）数字电视图像
SIF ( Source Input Format)格式，NTSC制、彩色、4: 4: 4采样，每帧数据量为352×240×3=253KB，每秒数据量(位率)为253×30=7.603 MB/s，一片CD-ROM可存帧数约650÷0.253=1.226K帧，一片CD-ROM节目时间为(650÷7.603 ) /60=1.42分钟。
CCIR ( International consultative Committee for Radio)格式，PAL制、彩色、4: 4: 4采样，每帧数据量为720×576×3=1.24 MB，每秒数据量(位率)为1.24×25=31.3 MB/s，一片CD-ROM可存帧数约650÷1.24=0.524K帧，一片CD-ROM可存节目时间约为(650÷31.1) =20.9s。
（2）数字音频磁带(DAT: Digital Audio Tape )，采样频率48KHz，采样精度16bit/样本，1秒钟时间内采样位数为48×103×16=768KB，一个650MB的CD-ROM可存储约2小时的音乐。
（3）双通道立体声激光唱盘(CD-A )，采样频率为44.1KHz，采样精度16bit/样本，其一秒钟时间内的采样位数为44.1×103×16×2=1.41Mbps。一个650MB的CD-ROM可存储约1小时的音乐。
（4）一页印在B5(约180mm×255mm)纸上的文字，若以中等分辨率(300dip约12dpi/m )的扫描仪进行采样，其数据量约6.61 MB/页。一片650MB的CD-ROM，可存98页。
由此可见，数字化信息的数字量如此之大!这么大的数据量，仅仅依靠扩大存储器的容量、增加通信干线的传输率的办法是不现实的。但是可以通过数据压缩技术来使之实现。通过数据压缩手段把信息的数据量压下来，以压缩的形式来传输和存储，不仅紧缩节约了存储空间，而且提高了通信干线的传输效率;同时也使计算机能实时处理音频、视频信息;使得保证播放出高质量的视频、音频节目成为可能。多媒体数据压缩不仅是必要的而且也是可能的;原因是，多媒体文本、声音、静态图像、视频图像等信源数据有极强的相关性，多媒体视频信号可以压缩的主要根据为:
(一)视频信号上存在大量的冗余度并且这种冗余度在编解码后可以无失真地恢复;
(二)可以利用人的视觉特性，在图像变化不被觉察的条件下减少量化信号的灰度级之种类，以一定的客观失真来换取数据压缩。
也就是说，存在着大量的冗余信息。数据压缩就是将庞大的数据中的冗余信息去掉(去除数据之间的相关性)，保留相互独立的信息分量。以静态图像画面为例，数字图像的灰度信号和色差信号在空域(x、y坐标系)虽然属于一个随机场分布，但是它可以看成为一个平稳的马尔可夫场。通俗的理解，图像像素点在空域中的灰度值和色差信号值，除了边界轮廓外，都是缓慢变化，比如一幅头肩人像图，背景、人脸、头发等处的灰度、颜色都是平缓改变。相邻像素的灰度和色差值比较接近，具有强的相关性，直接用采样数据(PCM码)表示灰度和色差，信息有较多的冗余。因此要先排除冗余信息，再进行编码，使表示每个像素所需的平均比特数下降，这就是通常所说的电视图像的帧内编码，即以减少空域冗余进行数据压缩。电视图像是沿时间轴方向的一个帧序列，其帧间图像的相关性也很强，通常用减少帧间传送帧的数目即降低帧率，以减少时域的冗余信息，采用运动估计和运动补偿的方法以满足解码图像质量要求。
1.2 视频图像压缩的历史、现状及趋势
数据压缩编码己经有了很长的历史。视频图像压缩所解决的问题是尽量减少表示数字图像时需要的数据量;减少数据量的基本原理是去除其中多余的数据。以数学的观点来看，这一过程实际上就是将二维像素阵列变换为一个在统计上无关联的数据集合。这种变换在图像存储或传输之前进行。在以后的某个时候，再对压缩图像进行解压缩来重构原图像或原图像的近似图像。
人们对视频图像压缩开始感兴趣可以追溯到60多年前。最初在这一领域研究的焦点集中在建立一种模拟的方法以便减少视频传输所需的带宽，这一过程称为带宽压缩。数字式计算机的出现和后来先进的集成电路的发展，导致这方面研究重点从模拟方式转移到数字压缩方法上来。1969年在美国召开的第一届“图像编码会议” 标志着图像作为一门独立的学科诞生了。70年代和80年代中，视频图像的压缩编码主要集中在变换编码的技术上，同时在矢量编码技术上也有了很大的发展，80年代中后期，人们结合模式识别、计算机图像学、计算机视觉、神经网络、小波分析和分形几何等理论，开始寻找新的压缩视频图像的方法，并相继提出了各种方法，如:M.Kunt在1985年提出利用人眼视觉特性的第二代图像编码技术 ; M.Barnsley在1988年提出的基于迭代函数系统的分形图像编码技术， 1989年S.Mallat、I.Daubeche将小波分析理论应用与图像编码，以及90年代才发展起来的基于模型的图像编码方法等。
近十年来，视频图像编码技术得到了迅速的发展和广泛的应用，并且日益成熟，其标志是几个关于图像编码的国际标准的指定，即ISO/IEC关于静止图像的编码标准JPEG ，CCITT关于电视电话/会议电视的视频编码标准H.261， H.263，H.264等和ISO/IEC关于活动图像的编码标准MPEG-1，MPEG-2，MPEG-4。这些标准图像编码算法融合了各种性能优良的传统图像编码方法，是对传统编码技术的总结，代表了目前图像编码的发展水平。
1.3 视频编码标准的发展背景与历程
(1)H.261视频压缩标准:H.261是ITU-T为在综合业务数字网(ISDN)上开展双向声像业务(可视电话、视频会议)而制定的，速率为64kb/s的整数倍。H.261只支持CIF和QCIF两种图像格式，每帧图像分成图像层、宏块组(GOB)层、宏块(MB)层、块(Block)层来处理。H.261是最早的运动图像压缩标准，它详细制定了视频编码的各个部分，包括运动补偿的帧间预测、DCT变换、量化、嫡编码，及与固定速率的信道相适配的速率控制等部分，以后的视频编码标准都以此为基础。
(2) H.263视频压缩标准:H.263是ITU-T为低于64kb/s的窄带通信信道制定的视频编码标准。它是在H.261基础上发展起来的，其输入图像格式可以是SUB-QCIF, QCIF,CIF, 4CIF, 16CIF的5种彩色4:2:0亚采样图像。H.263与H.261相比采用了半像素的运动补偿，并增加了4种有效的压缩编码模式。H.263以后的修订版本，H.263+和H.263++，是在保证原H.263标准核心句法和语义不变的基础上，增加了若干选项以提高压缩效率或改善某方面的功能。
(3) MPEG-x视频压缩标准:MPEG-1标准的码率为1.2Mbit/s左右，可提供30帧/秒CIF(352×288)质量的图像，是为CD-ROM光盘的视频存储和播放所制定的。MPEG-1标准视频编码部分的基本算法与H.261 /H.263相似，也采用运动补偿的帧间预测、二维DCT, VLC游程编码等措施。此外还引入了帧内帧(I)、预测帧(P)、双向预测帧(B)和直流帧(D)等概念，进一步提高了编码效率。在MPEG-1的基础上，MPEG-2标准在提高图像分辨率、兼容数字电视等方面做了一些改进，比如，它的运动矢量的精度为半像素;在编码运算中(如运动估计和DCT)区分“帧”和“场”;引入了编码的可分级性技术，如空间可分级性、时间可分级性和信噪比可分级性等。1999年推出的MPEG-4标准引入了基于视听对象(AVO:Audio-Visual Object)的编码，大大提高了视频通信的交互能力和编码效率。MPEG-4中还采用了一些新的技术，如形状编码、自适应DCT、任意形状视频对象编码等。但是，MPEG-4的基本视频编码器还是属于和H.263相似的一种混合编码器。
(4)H.264/AVC视频压缩标准:H.264/AVC是由ISO/IEC与ITU-T组成的联合视频组(JVT)制定的新一代视频压缩编码标准。在1996年制定H.263标准后，ITU-T的视频编码专家组(VCEG)开始了两个方面的研究:一个是短期研究计划，在H.263基础上增加选项(H.263+和H.263++);另一个是长期研究计划，制定一种新标准以支持低码率的视频通信。长期研究计划产生了H.26L标准草案，在压缩效率方面与先期的ITU-T视频压缩标准相比，具有明显的优越性。2001年，ISO的MPEG组织认识到H.26L潜在的优势，随后ISO与ITU开始组建包括来自ISO/IEC MPEG与ITU-T VCEG的联合视频组(JVT), JVT的主要任务就是将H.26L草案发展为一个国际性标准。于是，在ISO/IEC中该标准命名为AVC ( Advanced Video Coding )，作为MPEG-4标准的第10个选项，在ITU-T中正式命名为H.264标准。
(5) AVS音/视频编码技术标准:是由我国自主制定的，主要面向高清晰度电视、高密度光存储媒体等应用。AVS标准借鉴当前国际上最先进的MPEG-4, H.264/AVC的框架为基础，强调自主知识产权，同时充分考虑了实现的复杂度。相对于H.264, AVS的主要特点有:
●8×8的整数变换与64级量化;
●亮度和色度帧内预测都是以8×8块为单位，亮度块采用5种预测模式，色度块采用4种预测模式；
●采用16×16, 16×8, 8×16和8×8四种块模式进行运动补偿;
●在1/4像素运动估计方面，采用不同的四抽头滤波器进行半像素插值和1/4像素插值;
●P帧可以利用最多两个前向参考帧，而B帧采用前后各一个参考帧。 H.264是目前性能最优异视频编码标准，它引入了CABAC(基于上下文的自
适应二进制算术编码算法)，帧内预测、多参考帧、多块分割等最新的视频编码技术，达到了出色的视频压缩效果，但同时它优异的性能是以高复杂的运算和高要求的资源所换取的。H.263是性能优异的国际标准，针对于低码率视频压缩，其多种高级编码选项，有助于用户根据不同的应用需求选取最佳的编码方案。对比起H.264和MPEG-4两个标准，H.263在压缩性能和计算复杂度上都有比较出色的表现，目前被广泛的应用在低码率嵌入式视频领域。
1.4视频图像压缩编码的方法
1.4.1基本编码方法简介
1.嫡编码嫡编码，即信息保持编码，又称无失真编码，它是一种纯粹基于信源统计特性的编码方法。根据Shannon的无干扰嫡编码理论，在无干扰的条件下，存在一种无失真的编码方法，使得编码的平均长度与信源的墒任意接近。
根据信息论，视频图像是一种有一定信息量的载体，信息载体的信息量的大小可以用嫡( Entropy)来表示，嫡指的是具体数据的平均信息量。定义为:在不丢失信息的前提下，描述该信息内容所需的最小比特数。视频图像的嫡的表达式为(1.1):
(1.1)
式中的H(X)的单位为比特/字符，图像像素灰度集合X={ ，，，… }，起始对应的概率分别为，，，… ，图像嫡表示为图像灰度集合的比特平均数，单位为比特/像素( bits per pixel )，也描述了图像信源的平均信息量。在信息论中无干抚的编码定理这基础上，定义了某种编码方法的效率和容余度分别为(1.2 ), ( 1.3)两式:
（1.2）
（1.3）
其中为编码的平均码字长，为编码效率。从式中可以看出，信息量的大小与图像信源的概率分布有直接的关系，当N= 时，即图像信源各个像素灰度出现的概率相等，均为1/ ，此时的嫡最大，等于比特。此时用普通等长自然二进制编码就可以达到编码效率为1。在不等概率分布时，嫡H(X)小于L，如采用和概率分布相适应的不等长编码可以使平均码长小于1，即可实现数据压缩。也说明了图像信源数据中包含着冗余，采用不等长编码后的信源嫡尽可能接近最大值，只要信源不是等概率分布的，就存在数据压缩的可能。
常用的嫡编码有游程编码(RLC，run-length coding)、霍夫曼编码(Huffman
coding )、算术编码(arithmetic coding)三类。
1)游程编码(RLC，run-length coding )
当己被采样的图像/视频流数据拥有相同字节序列时，可以采用更紧密的序列来代替这些相同字节序列，从而实现数据的压缩，这就是游程编码(RLC，run-length coding )。这一方法充分利用了符号自身的相关性来达到压缩数据的目的。它是一种相对简单的编码方法，游程指的是由字符(或信号采样值)构成的数据流中各个字符重复出现而形成字符串的长度，如果给出了形成串的字符，串的长度及串的位置，就能恢复出原来的数据流。游程编码就是用二进制码字给出上述信息的一种方法，游程编码的压缩效果取决于整个数据流中重复字符出现的次数，平均游程长度及编码结构。基本的游程编码就是在数据流中直接用三个字符来给出上述三种信息，其数据结构如图1.1所示。Sc表示有一个字符串在此位置，X代表构成串的字符，Cc代表串的长度。

数据流

图1.1游程编码数据结构
2)霍夫曼编码(Huffman coding )
霍夫曼编码(Huffman coding)编码是常用的压缩方法之一，它的基本思路是:对于出现概率大的信息符号，编以短字长的码字，对出现概率小的信息符号编以长字长的码字。霍夫曼编码的具体方法:先按出现的概率大小排队，把两个最小的概率相加，作为新的概率与剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1″，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。
但是Huffman编码的效率受到信源概率分布的影响，当信源的概率相等，其编码效率最低;当信源概率是2的负幂时，Huffman码的编码效率才为100%；另外它必须通过两次操作，一次统计，一次编码，对位的增删比较敏感，而且Huffman码字参差不齐，不利于硬件实现。在实践中，往往采用固定Huffman编码表的方法来进行编解码。
3)算术编码(arithmetic coding )
算术编码（arithmetic coding）是由Rissanen提出，该方法是将被编码的信息表示成实数0和1之间的一个间隔，信息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。算术编码的受到编码模式(概率统计与范围分配)的影响。算术编码的优点是，其自适应模式可以不必预先定义概率模型，从而适用于无法进行概率统计的场合，其缺点是实现方法较Huffman编码复杂。
2.变换编码
变换编码（transform coding）是通过信号变换来消除图像数据空间相关性的一种有效方法。其基本原理是将原来通常在空间域描述的图像信号，变换到另外一些正交矢量空间(变换域)中进行描述。尽管图像变化本身不能对数据进行压缩，但由于它是对变换域中的变换系数进行量化编码，而变换后系数之间的相关性明显降低，图像的大部分能量只集中在少数几个变换系数上，而且系数的空间分布和频率特性与人眼的视觉特性和心理特性相匹配，采用适当的量化和熵编码可以有效地压缩图像的数据量，并且复原时图像信号只需要经过相应的逆变换，把图像信号由变换域转换到原来的空间域即可。卡南—洛伊夫(Karhunen-Loeve)变换虽然是均方误差准则下的最佳变换，它所给出的变换系数是互不相关的;但是在实际编码中，由于其计算的复杂性，K-L变换的实际应用较少。人们更常采用的是离散余弦变换(DCT，discrete cosine transform)。对大多数图像信源来说，DCT变换是现行变换编码方法中最接近K-L变换的方法，并且具有多种快速算法，所以DCT已被多种静态和活动图像编码的国际标准建议所采用。
对图像方块进行变换以后，得到的是其变换系数，接下来就要对这些系数进行量化和编码。选择哪些变换系数进行量化编码，略去哪些系数，即将系数设为零，对变换压缩的性能有很大影响。原则上应保留能量集中的，方差大的变换系数予以编码传输，系数选择一般采用门限编码加区域编码的形式。经过DCT数据，根据变换系数的能量分布，可以将图像划分为不同的区域，其中变换后幅值较大的图像系数大多集中在图像块的左上角。与其他系数相比，这些低频系数具有的能量最大，包括了图像的大部分内容，在变换图像中的地位最重要，应该使它们的量化误差最小。同样对于图像块的其他区域，也应该采用与不同量化编码的方法，该编码方法就称为区域编码。另一方面，变化图像中有许多系数的幅值很小，只具有原图像中很小比例的能量，对图像质量影响较小，因此一般采用设定阀值的方法，即对幅度大于某个阀值系数进行编码，如果变换系数大于阀值，则进行编码，否则忽略，让小于阀值的变换系数为零，大大提高编码效率，同时这样做不会丢失有用的高频分量，有“自适应”能力，根据系数的实际能量而不是按照统计规律保留系数。采用阀值的缺点是必须同时编码所保留的系数的位置，因为这些系数的位置是预先无法确定的。一般采取不直接对系数位置编码，而是先将二维系数按照“之”字型展开成一维序列，然后通过对连续的不编码系数进行行程编码来间接确定需保留的系数的位置。
在一般图像中，对应于边缘轮廓的位置附近含有大量高频信息，它们相对于原始图像是非常局部的，代表了图像数据的精细结构。按照人眼的视觉特性，这些边缘轮廓信息对于图像的主观质量很重要，在编码时应该与以足够重视。但由于传统正交变换时域局部性很差，变换后的系数失去了对原始图像精细结构的描述，从变换图像得不到图像边缘轮廓等局部信息，因此在量化编码时无法采用特殊的方法。而且在传统的变换图像编码方法中，大多是靠丢弃高频系数来提高压缩比，从而导致了图像的边缘轮廓模糊，严重影响重建图像的主观质量，这是传统编码方法的缺点之一。传统变换编码方法的另一缺点是提高编码压缩比是会出现块效应，这是因为为了降低变换算法的运算复杂度和提高编码效率，传统的图像变换均采用了分块变换技术。图像块越大，相关性就越高，压缩比也越大。
近几年在DCT方面的主要成果有：1)确定了DCT像素块的最佳尺寸为8×8; 2)制定了对DCT逆变换(IDCT)算法精度的要求;3)提出了对电视电话/会议电视和常规电视的DCT变换域“视觉阀值矩阵”的参考数据;4)为消除“块效应”而采用的简单的数字滤波器，与DPCM不同，DCT误码所造成的错误被限制在一个像素块中，而不会引起误码扩散。
3.预测编码预测编码是一种基于统计模型的率失真编码，预测编码又称为差分脉冲编码调制(DPCM) 。预测编码之所以能够达到压缩数据的目的，源于这样一个事实:预测信号的标准差要远小于原始图像数据的标准差。预测编码实际上也就是利用图像数据空间和时间冗余的特性，用相邻的己知像素(或图像块)来预测当前的值，然后再对预测误差进行量化和编码。因此，对误差信号进行可变长编码就可以达到压缩数据的目的。相邻像素或图像块可以是同行的，也可以是前几行或几帧的，相应的预测编码分别称为一维、二维和三维预测，其中，一、二维预测是帧内预测，三维是帧间预测。
预测编码的基本原理如图1.2所示:

图1.2预测编码原理图
是输入信号，为根据时间以前的采样值，， … 的预测值，为与的差值信号，为经过量化器量化后所产生的输出信号，量化器的量化误差为，为接收端的输出信号。在接收端复原的像素与发送端的源像素之间的误差如1. 4式所示:
（1.4）
预测编码系统除了量化器产生的量化误差外，不会再产生其它附加误差，最佳量化器的设计是DPCM编码方法的重要问题之一。例如合理选择量化器量化步长，使量化误差不超过人眼的视觉可见阀值，使接收端的图像质量满足主观保真度的要求，在实际的量化器设计中可以考虑到量化误差的统计特性以及人眼的视觉掩盖效应，如在图像平坦区稍有误差就很容易觉察，而在图像边缘或场景复杂时量化误差即使较大仍难发现的特点，在图像亮度变化较大的地方取较大的量化步长，从而在保证图像主观质量的同时进一步压缩数据。在以人眼观察的电视图像中采用预测法，例如:帧内预测编码和帧间预测编码。
对单幅图像而言，对一个样本值的预测根据前面若干像素值进行，称为帧内预测。对视频数据而言，待编码的是一个图像序列，预测时可利用前后帧之间在时间轴上的相关性进行，称为帧间预测，利用它和其它方法结合起来，如运动估计和运动补偿技术，则可进一步压缩数据。预测编码的一个缺点是抗干扰能力差，若在传输中出现误码，其影响不只局限于一个像素，而是扩散开去，造成明显的横条干扰。
4.矢量量化编码
矢量量化（VQ）是根据Shannon率失真理论提出的一种量化方法。它首先将图像数据序列分组，形成一个N维空间的矢量，然后对这一矢量整体进行量化。在理论上，它优于标量量化。
矢量量化是用k个样本值形成一个k维空间中的一个矢量，然后对此矢量进行量化，只传输或存储矢量地址，因而可以大大提高压缩效率。矢量量化总是优于标量量化，因为矢量量化是有效的利用了矢量中各个分量间的四种相关性(线性依赖性、非线性依赖性、概率密度函数的形状和矢量维数)来去除冗余度。矢量量化是标量量化的多维扩展。
矢量量化的关键是码书的构成。LBG算法为这一问题的解决提供了一条有效的途径。它利用一个能大致反映输入向量的概率分布的、足够大的训练样本集，通过一种聚类算法来生成码书。矢量量化的基本问题是要获得好的压缩编码效果，须尽可能增大矢量维数，从而导致码书设计时计算复杂度增加，相应地使编码复杂度增加。
1.4.2其他编码方法简介
子带编码(Sub band Coding)采用滤波和抽样技术将原始图像分解为若干频带信号，然后对分解后的各个频带信号采用合适的编码方法进行压缩。在解码端，解码后的各频带信号经过内插后，用综合滤波器重构输出信号。
分形(Fractal)是Mandelbrot在1977年提出的几何学新概念。分形压缩的基本原理是利用分形几何中自相似性原理来进行图像压缩。所谓自相似性就是指无论几何尺度如何变化，景物的任何一小部分的形状都与较大部分的形状极其相似。与DCT不同，分形编码利用的“自相似性”不是邻近样本的相关性，而是大范围的相似性，即图像块的相似性。对相似性的描述是通过仿射变换来确定的，而编码的对象就是仿射变换的系数。由于仿射变换的系数的数据量小于图像块的数据量，因此可以实现压缩的目的。分形压缩一般分为三步:1)图像划分，一般是划分为互不重叠的大小相等的块。2)区块与域块的匹配。一般采用比区块大一倍的域块，由于随机的搜索匹配比较费时，所以事先将域块分类，或事先做好域块库。3)确定映射参数，是重建图像与原始图像之间的范数最小。然而，分形压缩在进行块匹配仍然是现阶段一个难题。

第二章H.263压缩编码标准

2.1 H.263标准概述
H. 261标准是ITU于1990年公布的第一个视频编码标准，帧间编码时采用了基于16×16的宏块的整像素运动估计，而在帧内编码时采用了8×8数据块的DCT运算。这些算法有效地压缩了视频序列在时间和空间上的冗余度，使得H. 261具有较高的压缩比，适合于Px64Kbps(p:1-30)的视听业务，可用于ISDN、可视电话和会议电视等应用。H.261编码分成四层:图像层，块组层(GOB )，宏块层 (MB)和块层。每一块8×8，每一层都有各自头部，复合后串行传输。H.261的视频帧格式被称作公共中间格式 (CIF) 。
H. 263是ITU于1995年制定的一种码率低于64Kbit/s的甚低码率视频压缩编码标准。其修订版本有1998年的H. 263+和2000年的H.263++。 H.263标准不仅着眼于利用PSTN (Public Switched Telephone Network，公共交换电话网络)传输，而且兼顾 GSTN(Global Switched Telephone Network)移动通讯等无线业务。H.263已被多个多媒体终端标准所采纳，包括支持PSTN与无线网的 H.324，支持N-ISDN的H.320，支持B-ISDN的H.310等。H.263采用的基本编码方式是帧内编码(INTRA)和基于运动估计与补偿的帧间编码(INTER)。
为了进一步改善图像质量，提高压缩比，H.263与H.261相比增加了以下一些功能:
1.)半个像素精度的运动估计
2.)不受限的运动矢量
3.)先进预测模式
4.)PB帧模式
5.)基于语法的算术编码
H.263修订版主要是增加或修正了H.263的一些高级编码模式，不仅保持了对旧版本的兼容，而且增加了新的功能，例如，改进的标准可以采用自定义的图像格式；支持图像冻结和快照；为了避免信道误码对图像重建造成的不可恢复的损失，增加了一些新的抗误码技术等等。这些新功能进一步扩大了其应用范围，提高了压缩效率和抗误码能力，同时进一步改善了重建图楼的主观质量。
2.2 H.263编码标准的基本原理
2.2.1 H.263编码框架
H.263是以混合编码为技术核心，同H.261一样，在编码中，它也采用帧
间预测减小时间冗余度，利用DCT变换减小空间冗余度，在传输中，采用可
变长度编码技术，在解码恢复中，应用运动补偿。H.263编码器框图如图2.1所示。

图2.1 H.263信源编码器

与H.261相比，H.263的编码原理与之基本相同，但是H.263在H.261的基础上做了很多改进，以提高编码的效率。下面就做详细的介绍。
2.2.2 图像格式
在H.263标准中，支持的图像格式有5种，如表2.1所示，不同格式的图像亮度和色度采样也在表中。

表2.1 H.263支持的5种图像格式

图象格式亮度分量色度分量
列数（dx）行数（dy）列数（dx/2）行数（dy/2）
sub-OCIF 128 96 64 48
OCIF 176 144 88 72
CIF 352 288 176 144
4CIF 704 576 352 288
16CIF 1408 1152 704 576
2.2.3 图像的YCbCr采样
颜色空间是指用来表示亮度和颜色的方法。有2种典型的颜色空间:RGB、YCbCr。RGB空间是指每个采样点的颜色用3个数值表示:Red，Green，Blue。YCbCr空间是指用亮度、色度分开来表示图像信息。
研究发现，人类视觉系统对亮度(Luma，luminance)的敏感度远远大于对色度(Chroma，Chrominance)的敏感度，而在RGB空间中，亮度和色度都被同等重要地表现出来，没有考虑人类视觉系统，所以在视频编码中一般采用YCbCr空间，需要从RGB空间转化到YCbCr空间，转换公式如下:
（2.1）
H.263采用YCbCr空间的目的是根据人眼对亮度和色度的敏感程度不同，区别对待亮度值和色度值，减少对敏感度低的色度值的编码传输，所采用的方法就是YCbCr采样。
H.263中采用4:2:0的YCbCr采样方式，即每采样四个亮度信号值(Y),就同时采样2个色度信号值(Cr和Cb )，表示色度元素(Cb——U, Cr——V)在垂直方向和水平方向上均是亮度元素(Y)比例的一半，如图2.2所示:

图2.2 YCbCr4:2:0采样方式

很明显，通过YCbCr 4:2:0采样，比直接采用RGB方式节省了一半的存储空间。
2.2.4 图像分块
每帧图像都被分为许多块组(GOB)。一个块组是k行×16大小的分块。k值由图像格式决定，对sub-QCIF, QCIF和CIF格式而言k=1，对4CIF而言k=2，对16CIF而言k=4。每幅图像的GOB个数是:sub-QCIF格式6个；QCIF格式9个；CIF, 4CIF和16CIF格式18个。GOB的编号方式是将GOB块由上而下垂直扫描，最上的GOB块为0号，以下编号逐次加1。图2.3给出了CIF，Sub-QCIF，QCIF图像格式中GOB的编号方式。一个块组又由若干个16×16大小的宏块(MB)组成。每个宏块包含4个亮度块，2个色度块，如图2.4所示。每个宏块中亮度信号Y的大小为16×16，色度Cb，Cr的大小为8×8。编码器以8×8像素块(Block)为最小单位进行DCT变换。

图2.3 CIF, Sub-QCIF, QCIF格式的GOB编号方式
图2.4 宏块(MB)的组成
2.2.5 离散余弦变换（DCT）
在理论上，离散KLT (Karhunen-Loeve Transform)是消除线性相关性最好的一种正交变换，以图像的统计特性为基础，但是它的计算复杂，并且其变换核矩阵不是固定不变的，而是随原始输入图像而改变，所以不太实用。DCT变换在理论上虽然不是最优，但是它在去相关与能量集中性上仅次于KLT，而且其易分离的特点，易于采用快速算法。因此得到了广泛的使用，是国际编码中的主要环节。DCT不是对整幅图像一次进行变换编码，而是将图像分割成8×8的子块分别处理，原因是：小块图像变换的计算容易；距离较远的像素之间相关性比距离较近的像素之间的相关性小。
N点一维实数信号序列{Xi, i=0, 1,…，N-1}的DCT定义如下：
u=0，1，…，N-1 （2.2）
其中，
当u=0时；
，当u=1，2，…N-1时。
其逆变换IDCT定义为：
x=0，1，…，N-1 （2.3）
其中：
当u=0时；
，当u=1，2，…N-1时。
IDCT是DCT的逆变换，是解码时用到的关键算法。
在图像编码中，进行DCT时的输入数据是一个个的8×8像素值的矩阵，矩阵的每个元素是8bit精度。二维DCT变换就是指将此空间域的8×8像素值矩阵变换为与其相应的频域的8×8的DCT系数矩阵。
二维DCT的定义为：
设空间域像素值的取值范围为：x=0， 1，…，N-l； y=0，1，…，N-1。
频域系数的取值范围为；u=0，1，2，…，N-l； v=0，1，2，…，N-l二维DCT的变换公式如下：
（2.4）
二维DCT的逆变化公式如下：
（2.5）
（上两式中，当u,v=0时，C(u)，C(v)=1/ ；
当u，v=1，2，3…，N-1时，C(u)，C(v)=1。）在DCT系数矩阵中，（0, 0）处的系数称为低频系数，也称直流系数(DC ) ，代表水平和垂直的频率分量都为0。 DC系数与块的平均值成正比，在图像编码中，相邻两个块的像素值的平均值差别很小，所以可以通过相邻块的DC值进行DC预测编码，进一步压缩DC系数。其它的系数都成为交流系数(AC)。
当对8×8的像素值矩阵进行二维DCT变换时，上两式就变为：
8×8二维DCT的变换公式：
（2.6）
8×8二维DCT的逆变换公式：
（2.7）
二维DCT可以由一维DCT来表示，对公式2-6做如下变形：

（2.8）
，u=0 ，v=0
，u≠0 ，v≠0
可以看出，将二维DCT转化为2个一维的8×8 DCT的复合运算，相当于先对8×8矩阵的各行做一维DCT，再对求得的8×8矩阵的各列求DCT。因此只要提高一维DCT的速度，也就提高了二维DCT的速度，同样也适合于二维IDCT 。
2.2.6 一维DCT快速算法
目前进行DCT的最优算法是Loeffler的算法。直接计算一维的8×8 DCT需要做56次加法和64次乘法，速度最优的Loeffler进行DCT运算则需要11次乘法和29次加法。
Loeffler算法将8×8的一维DCT运算分为4级运算，由于各级之间的输入输出的依存关系，4级操作必须串行进行，而各级内部的运算可并行处理。下图给出Loeffler算法的流程图，图中共有三种运算因子，分别用a、b和c表示:蝶形因子、旋转因子和倍乘因子。

图2.5 loeffler算法的流程图

图中的的3种运算因子分别如图2.6所示：

图2.6 loeffler算法的3种运算因子

蝶形因子的输入输出关系为：
（2.9）
完成一个蝶形运算需要2次加法。旋转因子的输入输出关系为：（2.10）
需要3次乘法，3次加法即能完成一个旋转因子的运算。这里的及在旋转因子的运算量中。倍乘因子的输入输出关系为，只需一次乘法。
由以上3种因子的运算量，可计算出整个Loeffler流程图中的全部计算量。图中共有10个蝶形因子，3个旋转因子和2个倍乘因子，所以总的乘法次数是3×3+2=11，总的加法是10×2+3×3=29次。
2.2.7 量化与编码
在帧内编码模式下，帧内编码块的第一个系数(直流系数DC)使用统一的量化器，量化步长为8。其他各种系数(帧内编码的交流系数AC和帧间编码块的交直流系数AC/DC)可选择的量化器为[1, 31]，但是一个宏块内的量化器必须统一。H263采用了均匀量化的方式，在具体量化操作时，将系数值除以量化器步长，再对结果四舍五入取整，即得到量化系数，半整数值可以以向上舍入也可以向下舍入，不影响画面质量，但如果能近似为零，则编码尺寸最小，因而应优先考虑。例如，如果步长为8，系数值在25—30之间，则量化系数为3 。
在H. 263编码码流的图像层语法中增加了5比特的PQUANT码字，表示该
帧的量化器QUANT；在宏块层语法中，H.263标准采用DQUANT码字定义了QUANT的变化量。如同DCT变换一样，量化也有反量化过程。
量化会引起信息的丢失。量化步长基于可得的比特率来作出调整。量化后的8×8二维DCT系数数组经“之”字形排序(见表2.2, 1表示直流系数，按照序号的顺序排序)后转成一维数组。因为图像的能量大部分集中在低频分量，高频分量经量化后都为0，所以扫描后产生了长游程的零系数，须进行嫡编码。量化后得到的系数组可用可变长码表VLC(last, run, level)来表示，索引run表示一串零的数目；游程level是游程后面的非零系数的幅值；last是指示位，指示当前的非零系数是否是量化系数组的最后一个非零值。
表2-2“之”字形排
1 2 6 7 15 16 28 29
3 5 8 14 17 27 30 43
4 9 13 18 26 31 42 44
10 12 19 25 32 41 45 54
11 20 24 33 40 46 53 55
21 23 34 39 47 52 56 61
22 35 38 48 51 57 60 62
36 37 49 50 58 59 63 64

在视频编码中，常用的嫡编码方式有霍夫曼编码和算术编码两种，H. 263的可选模式中支持基于语法的算术编码。编码输出时，需要输出的内容包括：1.经过DCT变换后的DC/AC系数。2.色度和亮度块的编码模式3.运动矢量MV。2.2.8 运动估计(ME)与补偿(MC)
运动估计(ME, Motion Estimation)，在参考帧上搜寻最近似的方块，找出相距的距离和方向，也就是运动矢量(MV, Motion Vector)的过程叫做ME。
运动补偿(MC，Motion Compensation)，将目前要压缩的方块和找到的参考方块相减，纪录它们之间的误差值，以便在解码的时候能够补上这个误差值，这个过程叫做MC。
运动估计及补偿的基本原理就是利用帧间运动估计得到待编码图像块的一个参考块，然后用这个参考块进行运动补偿，将补偿后的残差进行DCT变换和可变长编码。运动估计的过程参考图2.6。对于某个特定的宏块，有可能在前一帧中找不到很匹配的区域，即使最匹配的区域，与当前宏块的差值也比原始宏块本身有很大的能量。此时，编码器应灵活决定对该宏块采用帧内编码。

图2.6运动估计

运动估计技术主要分为两大类：象素递归法和块匹配法。考虑到计算复杂
度和实时实现的要求，块匹配法己成为目前最常用的方法，在H.261，MPEG，H. 263等有关运动图像编码的国际标准中，均采用了该方法。由于运动估计在整个帧间预测编码中占用很大一部分时间，所以研究其快速算法具有重要的意义。本设计采用了改进后的菱形搜索算法。
H.263采用了半像素精度的运动搜索，是先用整像素的精度搜索得到整像素的运动矢量，根据整像素搜索的结果选择宏块的编码模式(INTRA或INTER) ,如果宏块为INTER模式，在整像素位移矢量的上下左右4点进行双线性插值，再做运动估计。双线性插值的具体过程如图2.7所示。

图2.7 半像素插值
前面已经提到，在H.263标准的默认框架下，每个宏块使用一个运动矢量作运动补偿；但在高级预测模式下，一个宏块可以使用四个运动矢量作运动补偿，如果采用PB帧编码模式，每个宏块还增加了一个偏差矢量，用来计算B宏块的运动矢量。
H.263标准中，宏块的运动矢量采用了差分编码技术。差分编码值是当前宏块的运动矢量和“预测值”之差。在H.261标准中，预测值只取与当前宏块左相邻的MV1，而H.263标准中预测值取三个相邻运动矢量的中值。三个相邻宏块的运动矢量位置如图2.8所示。

图2.8运动矢量预测模式图2.8 a.)中，当前运动矢量MV预测值为MVl、MV2、MV3的中值，这是一般的情况。当宏块位置在b.)时，MV1=(0, 0)，MV为MV2、MV3中值。其它情况类似。
运动矢量的水平和垂直位置分量都是整数值或者半整数值。H.263默认模式下，这些分量的取值范围 [-16，15. 5]；在高级模式不受限的运动矢量的情况下，扩大到[-31. 5，31. 5]。运动矢量的水平分量和垂直分量取正值时，表示参考块在目标块(被预测图像块)的右侧和下侧。在默认模式下，运动矢量不能超出整个图像的边界。
2.3 H.263可选模式
2.3.1 半个像素精度的运动估计
H.263采用半个像素精度预测，取代了H.261的全像素预测和环路滤波器，用于传输的是实际运动矢量与预测运动矢量之差。改进的运动估计算法充分利用以运动矢量的相关性来提高预测质量，减轻方块效应。图像中半像素位置的像素值采用线性插值方法计算得到，在前面的图2.7中已经介绍过了。
2.3.2 不受限的运动矢量
在不受限运动矢量模式下，将运动矢量的范围由原来的[-16, 15. 5]扩大到[-31. 5, 31. 5]，从而能够反映较快的图像运动，这对摄像机的运动和大图像格式十分有用。但是，扩大范围势必增大码长，考虑到运动的连续性，预测的运动矢量与实际运动矢量的差值范围应该不大，实际传输中只传输差值，这样就避免了扩大码本。另外，运动矢量范围扩大之后，可能会出现运动超出图像边界的情况，这时可以用与之最接近且其矢量指向图像内部的像素的矢量值代替该运动矢量，从而降低预测误差。
根据预测值P对运动矢量进行如下限制:
时，
时，
时，
2.3.3 高级预测模式
包含了两个特性。其一，运动估计是基于8×8块，而不是基于16×16的宏块，这样每个宏块可以具有四个运动矢量，运动估计更精确;其二，重叠块运动补偿(OBMC，只能用于P帧)。OBMC用邻块的运动矢量来重构块，能够消除块效应，改善解码图像质量。OBMC也允许运动矢量穿越图像边界，但大范围的运动矢量并不是自动支持的。
采用基于块的运动估计时，宏块的每个8×8亮度块都有各自的运动矢量，增加了搜索宏块匹配块的灵活性。在这种情况下，宏块的四部分都有可能各自找到真正匹配的块，当这些块合并起来后，就能得到更匹配的预测宏块。两个色度块的运动矢量由这四个亮度矢量相加除以8得到，由于亮度子块的运动矢量是半像素精度，所以除以8之后的精度为1/16像素，还要被修正到最接近的半像素精度。此外，运用四个运动矢量意味着需传送更多的运动矢量数据给解码器。
当每个宏块采用四个运动矢量的预测模式时，不再使用默认模式中的运动矢量预测差分编码方式，而是采用如下图2.9的方法：
图2.9 基于8×8块的运动矢量预测模式
2.3.4 PB帧模式
PB帧的概念源自MPEG2。使用PB帧模式可以在不大量增加数据量的前提下，增加图像的帧率。运动估计涉及三种帧结构:I帧、P帧、B帧，如图2.10。只包含帧内编码的帧成为I帧，对于I帧或P帧向前预测得到的帧成为P帧，对于I帧或P帧双向预测得到的帧成为B帧。运动估计时，P帧图像使用前面最近解码的I帧或者P帧作为参考图像，称为向前预测；而B帧图像使用两帧图像作为预测参考，称为双向预测，其中一个参考帧在显示顺序上先于编码帧，另一帧在显示顺序上晚于编码帧，所以进入编码器的帧序号要被打乱。

图2.10包含I帧、B帧、P帧的图像序列
2.3.5 基于语法的算术编码
算术编码采用序列编码，每个符号可用分数比特表示，而且对编码概率模型不太敏感，容易实现模型自适应调整，这就优越于霍夫曼编码必须使用整数比特表示，从而大大降低存放码本，使压缩比有很大提高。H. 263选用算术编码时，只对宏块层和块层的数据作算术编码，而对图像层、块组层大部分信息依然采用原有的编码方式编码，这样保证了头部信息的准确辨认和快速译码。另外，H. 263对码流信息中的不同部分分别建立了基本符合概率分布的编码模型，使之能更有效地编码。
2.4 H.263的码流格式
H.263标准按照分层的形式组织码流，码流结构分为4层，依次为图像层(Picture Layer)、块组层(GOB Layer)、宏块层(Macro Block Layer)和块层(Block Layer)。
2.4.1 图像层
每帧图像数据由图像头、宏块组数据、序列结束码和填充比特构成。如图
2.11所示，图像层的构成如下：

图2.11 H.263图像层的码流结构图
PSC(图像起始码):22bit，其值为00000000 00000000 100000。所有的PSC都应字节对齐。
TR(时域参考值):8bit，取值1—256。当前发送帧的TR值是在前一发送帧的TR值加1，再加上当前帧与前一发送帧之间的非发送帧(29. 97Hz)的数目。在PB帧模式时，TR仅指P帧图像。
PTYPE(类型信息):13bit，包括整帧图像的信息。
bit1:始终为“1”，为了避免与起始码冲突。
bit2:始终为“0”，与H. 261相区别。
bit3:屏幕分割指示位，“0”关，“1”开。
bit4:文件相机指示器，“0”关，“1”开。bit5:图象冻结解除位，“0”关，“1”开。bit6-8:信源格式，”000″禁止，”001″ sub-QCIF, “010″ QCIF,”011″ CIF,”100″ 4CIF, “101″ 16CIF, “110″保留，”111″保留。
bit9:图象编码类型，”0″ INTRA/I帧，”1″ INTER/P帧。
bit10:非限制运动矢量模式，”0″关，”1″开。
bit11:基于句法的算术编码模式，”0″关，”1″开。
Bit12:高级预测模式，”0″关，”1″开。
Bit13: PB帧模式，”0″表示I帧或P帧，”1″表示PB帧。
PQUANT(量化器信息)：5bit，表示该图像使用的量化器QUANT，是QUANT值的二进制表示，范围1—31。该码字可由后续的GQUANT或DQUANT来更新。
CPM(连续多点显示模式):1bit, “0″表示关，”1″表示开。
PSBI(图像子比特流指示):2bit，只有CPM指示了连续多点显示模式时才出现。表示图象头和后续直到下一帧图象或GOB起始码的信息的子比特流数。
(B帧时域参考值):3bit, PTYPE表示PB帧编码时才出现。它指示上次P帧或I帧后、B帧前的未发送帧(速率为29. 97Hz)的帧数。该码字是未发送帧数目加1，最大数为6。
DBQUANT (B帧量化信息):2bit, PTYPE表示PB帧编码时才出现。在解码过程中，PB帧的每个宏块有一个量化参数，P宏块用参数QUANT, B宏块用不同的量化参数BQUANT。 DBQUANT指示QUANT和BQUANT之间的关系。
PEI(附加插入信息):1bit，为“1”时表示后面将出现可选的数据域。
PSPARE(备用信息):0/8/16…bit，如果PEI位为1，则其后面跟有9bit数据，前8bit为数据PSPARE，第9bit为另一个PEI，指示其后是否还跟有9bit。设定PEI和PSPARE的用途是ITU保持对未来标准向后兼容。
ESTUF（填充码字):变长码字，由少于8个“0”比特组成。编码器可在EOS码字前直接插入这个码字，以保证EOS码字按字节对齐。
EOS(序列结束):22bit，其值为00000000 00000000 111111。
PSTUF(填充码字):变长码字，由少于8个“0”比特组成。编码器使用该码字，以保证下一个PSC码字字节对齐。
2.4.2 块组层
每个块组数据由GOB头(包括GSTUF, GBSC, GN, GSBI, GFID, GQUANT)和宏块数据组成，如图2.12，构成解释如下：

图2.12 H.263块组层的码流结构图
GSTUF(填充码字):变长码字，由少于8个“0”比特组成。编码器在GBSC码字前插入该码字，以保证GBSC码字的起始字节对齐。
GBSC (GOB起始码):17bit，值是00000000 00000000 1。应按字节对齐。
GN(GOB序号):5bit，为GOB序号的二进制表示。对于0号GOB，表示GOB头为空，GN包含在PSC码字内:对于31号GOB， GN包含在EOS码字内;GOB序号为1—17，表示GN在GOB头中;GN18~31是ITU为以后的应用而保留。
GSBI (GOB子比特流标识):2bit，只有当CPM指示了连续多点显示模式时才出现。这个码字是GOB头部和直到下一个图像或GOB起始码为止的所有信息的子比特流号的二进制表示。
GFID(GOB帧ID):2bit，一帧图像中所有的GOB的GFID值应相同，相同PTYPE的图像应具有相同的GFID值。
GQUANT(量化器信息):5bit，指示了用于图象剩余部分的量化器，该码字可以被后续的GQUANT或DQUANT更新。取值1—31。2.4.3 宏块层
宏块层码流由宏块头信息和块数据组成，如图2.13所示，构成详解如下：

图2.13 H.263宏块层的码流结构图

COD(编码的宏块指示):1bit，“0”表示编码此宏块，“1”表示此宏块没有进一步的信息被发送，进入下一个宏块或块组。
MCBPC(色度块编码模式):变长码字，指示色度宏块编码方式(见表2.3)。MUDB (B块的宏块模式):变长码字，仅当PTYPE标识为PB帧，MB类型为0—4时有效，它用于标识CBPB和MVDB是否出现。
CBPB(B块的编码模式):6bit，仅在PB帧模式下，MODB指示有效时才出现。在PB帧模式下，一个宏块由12个块组成:前6个是P块，后6个是B块数据。每比特对应B块N有要传的系数，即置“1”，表示该B块有要传的系数。
CBPY(亮度块编码模式):变长码字，指示4个亮度块中是否存在非INTRADC(帧内编码块的直流系数)需要传送。
DQUANT(量化器信息):2bit，定义了QUANT的变化量。
MVD(运动矢量数据):变长码字，它由水平分量变长码字和垂直分量变长
码字组成。
(运动矢量数据):变长码字，只有PTYPE和 MCBPC指示在高级预测模式下才出现。结构同MVD。
MVDB (B宏块运动矢量):仅在PB帧模式下，且MODB有效时才出现，组成同MVD。
表2.3普通图像(非PB帧)的宏块类型和所包含的数据元素

帧图像类型 MB类型名称 COD MCBPC CBPY DQUANT MVD MVD2-4
INTER Not Coded — X
INTER 0 INTER X X X X
INTER 1 INTER+Q X X X X X
INTER 2 INTER4V X X X X X
INTER 3 INTRA X X X
INTER 4 INTRA+Q X X X X
INTER Stuffing — X X
INTRA 3 INTRA X X
INTRA 4 INTRA+Q X X X
INTRA Stuffing — X

注意：“X”表示该项在宏块中出现
2.4.4 块层
块层码流由帧内直流系数和变换系数组成，如图2.14所示，详解如下:

图2.14 H.263块层的码流结构图

INTRADC (INTRA的直流系数) 8bit，不会出现在B块中。
TCOEF(变换系数)变长码字，这些都可以查VLC表获得

第三章 H.263视频编码、解码模块的设计与实现

本H.263编解码模块是基于软件TMNcodec32的。TMNcodec32是由哥伦比亚大学(The University of British Columbia)图像研究实验室的Michael Gallant等学者创作的源代码公开的共享软件。我们把它用于H.263视频压缩算法的一个标准，并使用它来组成编解码模块的主要内容。
下面先简单介绍TMNcodec32软件的功能和使用方法，然后再具体描述编码模块和解码模块的实现方法。
3.1 TMNcodec32软件简介
TMNcodec32是一个Dos下的标准C 软件，包括tmncode(编码)和tmndec(解码)两个程序，分别实现了H.263视频格式的编码和解码功能。TMNcodec32是一个通用软件，它能在Dos的命令行操作环境下进行YUV格式文件和H.263格式数据文件之间的互相转换，并且在H.263转换成YUV时能实时显示解码出来的YUV图像。
下面介绍TMNcodec32软件(tmncode和tmndec)的使用方法。
1)编码软件tmncode的直接运行如下：

Encoding format: QCIF (176×144)
Usage: mn [options]-i [more options]
Options:
-i original sequence [required parameter]
-o reconstructed frames [./out.raw]
-B filename for bitstream [./stream.263]
-a image to start at [0]
-b image to stop at [0]
-x ( ) coding format [2]
n=1: SQCIF n=2: QCIF n=3: CIF n=4: 4CIF n=5: 16CIF n=6: Custom
128×96 176×144 352×288 704×576 1408×1152 pels x lines
-s (0..15) integer pel search window [15]
-q (1..31) quantization parameter QP [13]
-A (1..31) QP for first frame [13]
-r target bitrate in bits/s, default is variable bitrate
-C Rate control method [3]
-k frames to skip between each encoded frame [2]
-Z reference frame rate (25 or 30 fps) [30.0]
-l frames skipped in original compared to reference frame rate [0]
-e original sequence has n bytes header [0]
-g insert sync after each n GOB (slice) [0]
zero above means no extra syncs inserted
-w write difference image to file “./diff.raw” [OFF]
-m write repeated reconstructed frames to disk [OFF]
-t write trace to tracefile trace.intra/trace [OFF]
-f force an Intra frame every frames [0]
-j force an Intra MB refresh rate every macroblocks [0]
-D use unrestricted motion vector mode (annex D) [OFF]
n=1: H.263 n=2: H.263+ n=3: H.263+ unlimited range
-E use syntax-based arithmetic coding (annex E) [OFF]
-F use advanced prediction mode (annex F) [OFF]
-G use PB-frames (annex G) [OFF]
-U (0..3) BQUANT parameter [2]
-I use advanced infra coding mode (annex I) [OFF]
-J use deblocking filter (annex J) [OFF]
-M use improved PB-frames (annex M) [OFF]
-N use reference picture selection mode (annex N) [OFF]
VRC with pictures per thread [m=2, n=3]
-c frames to select number of true B pictures between P pictures (annex O) [0]
-d to set QP for true B pictures (annex O) [13]
-i enhancement layer sequence
-u to select SNR or spatial scalability mode (annex O) [OFF]
n=1: SNR n=3: SPATIAL(horiz) n=5: SPATIAL(vert) n=7: SPATIAL(both)
-v to set QP for enhancement layer (annex O) [13]
-S use alternative inter vlc mode (annex S) [OFF]
-T use modified quantization mode (annex T) [OFF]
-h Prints help
Default filenames and other options in square brackets are chosen in config.h

编码包含很多的高级选项，下面的命令行操作把原始的、未经编码压缩的YUV格式序列文件(xxx.yuv)中的第一帧到第十帧视频图像编码成H.263格式文件(xxx.263)。结果如下所示:

Encoding format: QCIF (176×144)
Encoding frame rate: variable
Reference frame rate: 30.00
Orig. seq. frame rate: 30.00

Reading image no: 0
Coding I frame… done
Average Intra QP: 13
SNR_Y: 73.25
SNR_Cb: 76.15
SNR_Cr: 80.13
————————
#infra: 99
#inter: 0
#inter4v: 0
———————-
Coeff_Y: 15171
Coeff_C: 2838
Vectors : 0
CBPY : 312
MCBPC : 223
MODB : 0
CBPB : 0
COD : 0
DQUANT : 0
header : 56
=============
Total : 18600

Finished INTRA
Reading image no: 3
Coding P frame 3… done
Results for P-frame:
Average Inter QP: 13.00
SNR_Y : 34.47
SNR_Cb : 41.20
SNR_Cr : 42.22
———————-
#infra : 3
#inter : 76
#inter4v : 0
———————-
Coeff_Y : 6299
Coeff_C : 341
Vectors: 650
CBPY : 318
MCBPC : 155
MODB : 0CBPB : 0
COD : 99
DQUANT : 0
header : 50
=============
Total:7912

(这里省略6-9帧编码输出显示)

Reading image no: 9
Coding P frame 9… done
Results for P-frame:
Average Inter QP: 13.00
SNR_Y : 34.47
SNR_Cb: 41.20
SNR_Cr: 42.22
———————
#infra : 4
#inter : 77
#inter4v : 0
——————
Coeff_Y: 5988
Coeff_C: 355
Vectors: 688
CBPY : 333
MCBPC : 170
MODB : 0
CBPB : 0
COD : 99
DQUANT :0
header : 51
=============
Total:7685

Original seq time: 0.40 (0.40) sec
Mean quantizer for inter frames:13.00
Encoded frames : I: 1 P: 3
Mean frame rate :7.50 Hz
Obtained bit rate: 104.14 (57.64) kbit/sec

2)解码软件tmndec的直接运行如下：

Usage: tmndecode { options } bitstream { outputfilename%d }
Options:
-vn verbose output (n: level)
-nn output format
n=0 : YUV
n=1 : SIF
n=2 : TGAn=3 : PPM
n=5 : YUV concatenated
n=6 : Windows 95/NT Display
You have to choose one output format!
-q disable warnings to stderr
-r use double precision reference IDCT
-t enable low level tracing
-s output reconstructed frame to filename (YUV concatenated)
-p enable tmn-8 post filter
-c enable error concealment
-fn frame rate
n=0 : as fast as possible
n=99 : read frame rate from bitstream (default)

如果把刚才编码得到的H.263格式文件(xxx.263)再解码成YUV格式的图像并显示出来，运行下面的命令行结果显示如下：
D:\>tmndec.exe -r -06 xxx.263并显示出一个子窗口，里面显示的是解码出来的YUV格式图像。经过以上的H.263编码和解码转换，视频图像的数据量得到了压缩，压缩比能达到50倍以上。虽然TMNcodec32能实现H.263格式文件和YUV格式文件的相互转换，并且效果令人满意，但是它的使用价值却并不大，并且有很多不足之处：
1）TMNcodec32界面不友好，不熟悉就难以使用。
2）TMNcodec32完成的是对文件的操作，但是图像文件的数据量是很大的，所以它的应用场合有限。更好的做法是把它改成对流的操作。
3）TMNcodec32对内存的管理很不完善，这跟Dos下和Windows下的程序的差别有关。
4）TMNcodec32使用的都是Dos下的单线程。编码和解码的数据运算量是很大的，更好的方法是改写成多线程的，由优先极别高的子线程来处理大的运算。
5）TMNcodec32的程序是用C语言写的，没有用到面向对象的思路，使用大量的全局变量，这样就影响了程序的可移植性。更好的做法是用C++语言改写它。
根据以上分析，应对TMNcodec32进行如下方面的改写，并把它加入到编解
码程序模块里:
1）C语言改写成C++语言。
2）对文件操作改写成对流操作。
3）对所有的内存访问的改写。
4）单线程改写成多线程。
下节分别具体介绍编码模块和解码模块的实现方法。
3.2 编码模块的实现
编码模块的思路基本上是对图像数据顺序执行格式的转换，即把从视频卡捕捉得到的数据送入编码子线程编码，然后编码子线程再输出标准的H.263格式数据。总体的线程结构如图3.1所示。
图3.1 编码线程

根据程序tmncode的编码方法，归纳出八个编码功能函数，通过调用这些函数就能实现YUV格式到H.263格式图像的转换。
1) h263 _init encoder_1(int_format, int add_argc, char** add_ argv)
初始化编码器，并返回编码器的状态(ENCODER_ STATE结构体的指针)，如果失败则返回NULL。
2)h263_init encoder _2 (struct ENCODER_STATE* s)
初始化函数h263_ init encoder_1返回的结构体，此函数执行以后，编码器就能开始工作了。
3) h263_encoder_init_buffer (int_format)
初始化输入的YUV格式缓冲区和输出的H.263格式缓冲区，申请足够的内存，图像数据的输入和输出都要用到这个函数申请的内存。
4) h263_encoder_set_frame (unsigned char*_yuv_buf, int_format)
用指定的YUV格式数据(unsigned char * _yuv_buf)填充YUV格式缓冲区。
5) h263_encode_one_frame (struct ENCODER_STATE* s, int i, int tr)
对YUV格式缓冲区的数据进行编码，并把编码器的状态保存到结构体s中。编码得到的H.263格式数据将会存放到H.263格式缓冲区中。
6) h263_encoder_get_bitstream(unsigned char*_263_buf)
从H.263格式缓冲区中取出编码得到的视频流。
7) h263_cleanup (struct ENCODER_STATE* s)
编码结束后清除编码器的状态。8) h263_encoder_release_buffer()
编码结束后释放输入的YUV格式缓冲区和输出的H.263格式缓冲区占用的内存。
下面的代码描述的是一个简单的编码子线程的编码过程，过程的while循环由编码结束事件(g_endCodeEvent)来控制，循环里依次执行“写YUV缓冲区”、“编码”、“读H.263缓冲区”、“发送H.263数据”的动作。
UINT TMNCodeExThreadPro (LPVOID param)
{
#ifdef WANG
CVIDEO_PRODoc* pDoc= (CVIDEO_PRODoc*) param;
unsigned char*_263_buf;
int i=0;
_263_buf=new unsigned char [_MY_ 263_BUF_];
int n_263_buf=0;while(WAIT_OBJECT_0!=::WaitForSingleObject(
g_endCodeEvent.m_hObject, WAIT_OBJECT_0))
{
CSingleLock singleLock (&g_yuvSourceBufferMutex);
singleLock.LockQ;
h263_encoder_set_frame(g_yuvSourceBuffer, pDoc->m nFormat);
singleLock.UnlockQ;

// force coder to encode one intra frame
// every N frames, N=pDoc->m_nForceEncodeIntra.
//
if( i==pDoc->m_nForceEncodeIntra)
i=0;
h263_encode_ one_frame(_ _s, i++, 0);
n_263_buf=h263_encoder_get_bitstream(_ 263_buf);
TRACE(“\nGet 263 bitstream %d bytes from encode.\n”,n_263_buf);
#if 1
if(pDoc->m bIsSaveAS)
{
FILE*file=fopen(“c:\\Stream.263″,”ab”);
fwrite (_263_buf,sizeof(unsigned char),n_263_buf,file);fclose(file);
}
#endif
//发送263数据给解码程序，字节数不一定
//
pDoc->SendData(_ 263_buf,n_263_buf);
}

delete []_263_buf;
AfxMessageBox(“编码线程已经退出。”)
pDoc->m_bCode=FALSE;
#endif
return 0;

3.3 解码模块的实现
H. 263视频流的解压过程是编码压缩的逆过程，它的解码算法的大体结构如下：

图3.2 解码算法

由一个子线程专门负责解码，其它线程(子线程或主线程)给解码线程提供待解码的H.263格式的压缩数据，解码的结果向外公布，由YUV格式的数据缓冲形式给出。总体的线程结构如图3.3所示。

图3.3 解码线程图

子线程1、2、3之间的数据通过全局变量(内存指针)来传递，子线程1、2、3之间的消息通过事件来传递，由互斥量(Mutex)来实现子线程之间对全局变量访问时的互斥。表示视频图像缓冲区的全局变量有:
1) g_263DestPrepared2048Buffer:编码得到的H.263格式视频流，2048字节。
2) g_yuvDestDestBuffer:经过解码转换(263→yuv)后得到的YUV格式图像数据。
用于各个子线程之间互相通信的“事件”有：
1）g_263DestPrepared2048BufferEvent:子线程1(接收线程)接收到了2048字节大小的H.263格式视频数据，它包含小定数目的帧数。
2）g_DestyuvUpdatedEvent:子线程2(解码线程)输出了新的YUV格式图像数据。总的来说，解码模块的实现由多线程来完成，H.263格式视频流的输入和YUV格式图像数据的输出跟解码分别由子线程1、子线程2、子线程3完成。子线程之间的数据更新由事件来通知，访问数据时由互斥量来保证数据的完整性。子线程之间的数据访问都只有一个函数(memcpy)来完成，所以基本上不用担心数据的交差更新或数据访问的不完整。
解码子线程(子线程2)的函数入口定义如下：
_main_decode (
&g_endDecodeEvent, //结束解码子线程
&g_263DestPrepared2048BufferMutex,
//编码得到的263, 2048字节
g_263DestPrepared2048Buffer,
&g_yuvDestDestBufferMutex,
//经过解码(263=>YUV)得到的YUV
g_yuvDestDestBuffer,
//输入事件:已有2048字节的263数据&g_263DestPrepared2048BufferEvent,
//输出事件:解码线程输出了新的YUV数据
&g_DestyuvUpdatedEvent）

在此，需要注意解码功能的封装问题。由于解码由一系列的函数完成，为了以后的兼容性和简洁性考虑，用静态连接库来输出三个重要功能函数_main_ecode(实现解码功能)、_init_decode(初始化解码器并申请内存空间)、_release_ecode (释放内存空间)。(此静态链接库也可以很快的改写成动态连接库的形式)

3.4软件界面及结果
软件的界面如图3.3所示，根据选择的路径可以打开要压缩的YUV格式文件。

图3.4 软件界面

图3.5 编码文件选择及属性设置

点击“确定”后会出现压缩后文件的存放目录

图3.6 压缩后文件存放设置

下图是压缩界面，根据“编码属性设置”中的参数进行压缩。压缩界面的下面是进度栏，可根据进度栏来了解压缩的进展

图3.7 压缩界面
压缩完成后跳出完成提示界面：

图3.8 压缩完成界面

下面是解码界面：

图3.9 解码界面
下面是3个图像序列编码后的播放截图，以及PSNR值(图像的峰值信噪比).

图3.10 Mother.yuv压缩后的图象

第1_I帧的psnr: PSNR_Lum=41.159, PSNR_Cb=45.058, PSNR_Cr=45.828
第2_P帧的psnr: PSNR_Lum=41.661, PSNR_Cb=45.532, PSNR_Cr=46.496
第3_P帧的psnr: PSNR_Lum=41.870, PSNR_Cb=45.562; PSNR_Cr=46.472
第4_I帧的psnr: PSNR_Lum=41.219, PSNR_Cb=45.135, PSNR_Cr=45.893
第5_P帧的psnr: PSNR_Lum=4I.749, PSNR_Cb=45.482, PSNR_Cr=46.096
第6_P帧的psnr: PSNR_Lum=41.893, PSNR_Cb=45.579, PSNR_Cr=46.358
第7_I帧的psnr: PSNR_Lum=41.197, PSNR_Cb=45.122, PSNR_Cr=45.875第8_P帧的psnr: PSNR_Lum=41.666, PSNR_Cb=45.653, PSNR_Cr=46.324第9_P帧的psnr: PSNR_Lum=41.947, PSNR_Cb=45.676, PSNK_Cr=46.225
第10_I帧的psnr: PSNR_Lum=41.186,PSNR_Cb=45.106, PSNR_Cr=45.820

图3.11 Foreman.yuv压缩后的图象

第1_I帧的psnr: PSNR_Lum=39.145, PSNR_Cb=42.964, PSNR_Cr=45.431
第2_P帧的psnr: PSNR_Lum=39.509, PSNR_Cb=43.318, PSNR_Cr=45.691
第3_P帧的psnr: PSNR_Lum=39.632, PSNR_Cb=43.348, PSNR_Cr=45.732
第4_I帧的psnr: PSNR_Lum=39.145, PSNR_Cb=42.991, PSNR_Cr=45.430
第5_P帧的psnr: PSNR_Lum=39.499, PSNR_Cb=43.322, PSNR_Cr=45.886
第6_P帧的psnr: PSNR_Lum=39.510, PSNR_Cb=43.287, PSNR_Cr=45.837
第7_I帧的psnr: PSNR_Lum=39.129, PSNR_Cb=42.921, PSNR_Cr=45.440
第8_P帧的psnr: PSNR_Lum=39.406, PSNR_Cb=43.232, PSNR_Cr=45.745
第9_P帧的psnr: PSNR_Lum=39.345, PSNR_Cb=43.214, PSNR_Cr=45.712
第10_I帧的psnr: PSNR_Lum=39.063, PSNR_Cb=42.789, PSNR_Cr=45.332

图3.12 Football.yuv压缩后的图象

第1_I帧的psnr: PSNR_Lum=39.512, PSNR_Cb=41.209, PSNR_Cr=41.950
第2_P帧的psnr: PSNR_Lum=39.418, PSNR_Cb=41.237, PSNR_Cr=41.989
第3_P帧的psnr: PSNR_Lum=39.441, PSNR_Cb=41.189, PSNR_Cr=41.913
第4_I帧的psnr: PSNR_Lum=39.476, PSNR_Cb=41.206, PSNR_Cr=41.965
第5_P帧的psnr: PSNR_Lum=39.197, PSNR_Cb=41.038, PSNR_Cr=41.829
第6_P帧的psnr: PSNR_Lum=39.056, PSNR_Cb=41.020, PSNR_Cr=41.732
第7_I帧的psnr: PSNR_Lum=38.931, PSNR_Cb=40.970, PSNR_Cr=41.701
第8_P帧的psnr: PSNR_Lum=38.997, PSNR_Cb=40.884, PSNR_Cr=41.790
第9_P帧的psnr: PSNR_Lum=39.058, PSNR_Cb=40.882, PSNR_Cr=41.829
第10_I帧的psnr: PSNR_Lum=39.231, PSNR_Cb=40.984, PSNR_Cr=41.801

表3.1列出了对三个视频的测试序列的压缩效果比较，压缩一幅I帧和P帧的平均时间、平均编码速度和平均编码一帧的大小。

表3.1 3种测试序列的压缩效果比较
CIF序列名 I帧 P帧编码速度压缩大小压缩比
Mother.yuv 15159267 28278847 25.1fps 6.3 KBpf 23.6
Foreman.yuv 17885070 29475151 23.4fps 12.3 KBpf 12.1
Football.yuv 19236019 30441794 22.5fps 21.3 KBpf 6.98

第四章结论

随着图象编码技术和数字通信技术的不断发展，极低码率视频编码技术的研究变的尤为重要。在这种背景下，本文对基于H.263协议的极低码率视频编码的关键技术展开了深入的研究，如DCT、“之”字扫描、变长编码、运动估计和补偿技术等编码技术。为了开阔视野，本文还研究了H.263的几个可选模式。H.263视频流编码、解码模块虽然实现了视频编码格式的转换，但它还有些需要改进之处。解码由于是多线程的交错事件触发，所以会出现内存的交错现象。特别是，当解码的速率跟不上H.263视频流的接收速率时，旧的H.263视频流还没有解码，新的H.263视频流把旧的覆盖了，解码部分就会得到中间少一段数据的H.263视频流，解码就会出错，出现马赛克或图像交错。究其原因，还归根于解码部分每次输入都是2048字节的H.263视频流。如果每次输入的是一帧或是两帧的263数据(大小的不定的)，那么就会出现数据交错的问题，最多是丢帧了。

参考文献
[1]Kunt M, et al. Second-generation image-coding techniques. Proc IEEE, 1985，73 (4): 549-574
[2]Barnsley M F, et al. A better way to compress images. Byte,1988 (1): 215-223
[3]丁贵广等.Visual C++ 6.0数字图像编码.机械工业出版社，2004年1月:265-281
[4]沈兰荪.视频编码与低速率传输[M]，北京:电子工业出版社，2001.12:1-2
[5]张春田.轮廓自适应预测的帧内 DPCM编码.通信学报，19834 (1): 1-7
[6]ITU-T,Draft ITU-T Recommendation H.263,Video Coding for low bit rate communication,May,1996
[7]肖芳，基于TI-DSP的H.263视频解码与显示系统，浙江大学，硕士论文，2005.03
[8]H.263协议中文版，作者lsf，下载地址:

http://www.chinavideo.ors/index.php?option=comremository&func=fileinfo&id=5

[9]黄贤武王加俊李家华编著，数字图像处理与压缩编码技术，成都:电子科技大学出版社，2002.12
[10]ISO/IEC JTC1/SC29/WG11，Overview of the MPEG-4 Standard,Mar.1999
[11]钟玉琢王琪贺文玉编著，基于对象的多媒体数据压缩编码标准——MPEG-4及其校验模型，北京:科学出版社，2000. 11
[12]刘明钢，H.263建议的研究及视频实时压缩算法的实现，南京理工大学，硕士论文，2002. 12：39
[13]马小虎张明敏严华明等编，多媒体数据压缩标准及实现，北京:清华
大学出版社，1996. 9.
[14] Rafael C. Gonzalez Richard E. Woods编著，Digital Image Processing Second Edition数字图像处理(第二版)，阮秋琦阮宇智等译，北京:电子工业出版社，2003.3
[15]朱曙，新一代数字监控系统，中国多媒体视讯，2004. 11
[16]张益贞刘滔编著，Visual C++实现MPEG/JPEG编解码技术，北京:人民邮电出版社，2002. 11

托斯卡纳

Featured Post

I’m back

基于KL变换编码的数据压缩算法的研究与实现

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 18-09-2009

标签：KL变换, 变换编码, 图像压缩, 数据压缩, 算法

0

Turbo码的性能研究及仿真实现

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 18-08-2009

标签：Log－MAP, SOVA, Turbo码, 信道, 算法, 纠错编码

0

DSP+FPGA体系结构实现最小二乘递推算法

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 17-08-2009

标签：DSP, FPGA, least-squares, recursive algorithm, VHDL, 最小二乘, 算法, 递推

0

基于H.263编码的数据压缩算法的研究与实现

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 09-08-2009

标签：arithmetic, coding, decoding, H.263, video, 算法, 编码, 视频, 解码

0

随机图片推荐

最新日志

最新留言

Category

Partner Links

托斯卡纳

订阅内容RSS | 订阅评论RSS