【毕业学位论文】（Word原稿）应用快速RS编码法于MPEG-4容错编码之研究-義守大學资讯管理研究所

义 守 大 学 资 讯 管 理 研 究 所 硕 士 论 文 应用快速 之研究 A S 究 生：李俊明 指导教授：陈孟峰 博士 共同指导教授：王隆仁 博士 中华民国 九十二 年 六 月 - 1 - 应用快速 研究生：李俊明 指导教授：王隆仁 义守大学资讯管理所 摘要 本论文 提出运用 然 处理工具，例如：重新同步 (资料分割 (资料恢复 (可逆式变长度码 (盖错 (及档头延伸码 (技术，但是这些方法在检测到错误资料后，都只在处理如何减少错误资料的移除量，避免将整个资料移除，但是对于错误的资料并无法进一步做资料更正。 而 对于多重的错误具有相当高的侦测及更正能力，目前已被应用在许多的系统上，包括： (1)资料储存设备 (例如：磁带 ( 条码 ( (2)无线或移动通讯 (，例如：数位细胞式行动电话 (微波通讯 (3)卫星通讯 ( (4)数位电视 (以及 (5)高速数据机 (例如：非对称式数位回路系统 (由此可见，如果能将 ，应用到 低位元率影音编码的资料传输上，势必大幅提高 因此，本论文研究发现以质因数计算的 算法可以用于 计算 )2( )12( m 点转换 (其中 104 m )，而且这种 且，若将此快速 2 - 法，运用在 容错技术上， 可以改善传统 容错技术，且非常适用于 极低位元率影音编码的资料传输。 关键词： 容错度 ( 3 - A S i a to be as of of as in to in 1) as 2) or as 3) 4) ) as if be it a In it is be to 2( 04 m . is - 4 - It is by a - 5 - 目录索引 中文摘要 1 英文摘要 3 目录 5 第一章 绪言 6 1 7 1 9 1 10 第二章 10 2 10 2 12 2 12 第三章 14 3 14 3 16 3 18 第四章 算法 22 4散傅立叶转换 22 - 6 - 4速傅立叶转换 23 4 28 第五章 43 5 43 5 44 第六章 实验结果 46 第七章 结论与未来研究 59 参考文献 60 - 7 - 第一章 绪言 1究背景 由于传统的影音媒体被数位化成数位资料后，其资料量将极为庞大，相对地也需要相当大容量的记忆体空间来储存，然而目前一般电脑的储存记忆体都不能满足这种需求。而且在现有的通讯网路上传递这些影音数位资料，也会造成网路塞车、传输太慢等的问题。因此，如何在可接受的程度下，减少这些影音数位资料量，在现在及未来的影音媒体之播映、通讯及存录上，其重要程度日益升高，于是数位影音压缩技术便愈见其重要性 1。根据估算解析度为 1280 720 60的高画质电视 (2，若不经数位影音压缩编码技术的 处理，所需的储存容量将高达 9492钟，但是在 200 倍压缩率的数位影音压缩编码技术下，只需要 47钟的储存空间，所需的储存空间只需原来的 200分之 1，由此可见数位影音压缩编码技术的重要性。 数位影音压缩编码技术，早在 1984年就开始讨论，目前并以 准 3-17最被广泛采用。 下，所制定用来压缩影音的编码标准，由数位储存媒体(18专用的 直发展到用于高画质电视系统 (数位影音光碟 (19，与高品质通讯网路影音服务专用的 转往处理多媒体方面发展，并提出 刚开始进行制定标准时，被命名为”极低位元率下的影音编码”(后来才改名为”影音物件编码” (成为多媒体物件的编码标准 。也就是说，数位电视和电影的视讯与音讯资料、互动式多媒体和无线通讯网路，都是 应用极低位元率影音编码的行动多媒体，是 最初目的，此技术可以提供笔记型电脑、个人数位助理 (行动电话，可以透过移动体无线通讯网路技术，接收多媒体的影音数位资料。但是由于移动 - 8 - 体无线通讯网路技术，需要提高数位资料编码效率，而很容易在数位资料传送时发生错误，所以对于传送资料的容错度 (是一个必须慎重考虑的重要问题。 因此，如何解决数位资料在传送及接收时，因杂讯所造成的错误，将是一个极为重要的课题 17。 为了对付无线通讯网路中恶劣的传输环境以及移动体可能的高速移动，常常会使用上错误更正码 (技术，才不至于通讯品质低落或是断讯连连。换句话说，为了保证数位资料的正确性，通常数位化的资料还要再加入错误更正码，在原本的资料以外，再加入一些额外的资料以提高传送的正确性。而为了提高通讯的正确性，最简单的方法，就是将每笔资料传送两次，或是在资料发生错误时，将该笔资料一直重复传送，直到接收 端接收正确为止。但是将资料重复传送，不仅需要更多的传送时间，亦浪费了比较多的频宽。为了更有效率的处理通讯所造成的错误，就是利用错误更正码的技术，此技术是利用复杂的数学来产生一些额外的编码资料，并置放在资料的适当位置，当资料发生错误时，就可以利用此解码技术，将错误资料找出并予以更正。何况这种技术对于压缩过的资料更是重要，因为压缩后的资料若发生错误，可能会造成整笔资料的不同。这就像有些卫星电视台，因为利用数位资料传送，在天候不佳时，时常会发现电视萤幕上的影像变成一个个的方块。 通常错误更正码大致可以分为两类：一 类是区块码 (其使用的方法是一次编码许多资料，但是编码过程不影响以后的资料，也就是不具有时间相关性；另一类是回旋码 (其编码的过程是具有时间相关性的。这两种编码方式各有其长处，区块码中最常用的循环码 ( 及 而 (为一种回旋码。这些错误更正码中，著名的S)码已是数位通讯与资料储存系统上广泛被采用的一种错误更正码，它对于多重的错误具有相当高的侦测及更正能力 20。如再配合其他编码技巧，例如串接或交错，其能力更可进一步提升，以便应用在 低位 - 9 - 元率影音编码的资料传输上，提高数位资料通讯的容错度 ( 1究动机与目的 笔记型电脑、个人数位助理和行动电话等移动体的无线通讯，在这个应用领域，大量的影音数位资料利用 极低位元率编码后，经由无线通讯传送给 接收端的移动体，这个过程很容易发生资料传送的错误，所以对于数位资料的容错度 (要特别重视。虽然 提出了一些针对低位元率容错度的处理工具，例如：重新同步(资料分割 (资料恢复 (可逆式变长度码 (盖错 (及档头延伸码 (技术 17，但是这些方法技术在检测到错误资料后，都只是在如何减少错误资料的移除量，对于错误的资料并无法更正。 而 (被证实是一种功能强大的错误更正码，它对于多重的错误具有相当高的侦测及更正能力，目前已被应用在许多的系统上，包括： (1)资料储存设备 (例如：磁带 ( 条码 ( (2)无线或移动通讯 (，例如：数位细胞式行动电话 (微波通讯( (3)卫星通讯 ( (4)数位电视 (以及 (5)高速数据机 (例如：非对称式数位回路系统 (由此可见，如果能将 及更正能力，应用到 低位元率影音编码的资料传输上，势必大幅提高 能。因此，为了满足 应用 功能，以适用于极低位元率影音编 - 10 - 码的资料传输，并期望以加入少许冗余资料量而大幅提升 论文所采用的 55, 223)编码式依据美国太空总署 (码标准所修改而成，此标准为应用于卫星与太空通讯 33。 1文架构 本论文架构为第一章绪论说明研究的背景、动机与目的；第二章探讨目前用三小节描述 重新同步 (资料恢复 (盖错 (三种方法； 第三章介绍 333四章介绍 五章说明本论文所使用的55六章利用电脑模拟观察实验结果，第七章为结论及未来研究方向。 - 11 - 第二章 目前 面的处理，大致可以分成重新同步 (资料恢复 (盖错 (三种方法 17,21-24，兹说明如下： 2新同步 (以压缩的视讯为例，当传送压缩视讯经过有杂讯的通讯频道时，错误 (会被置入数位资料流 (。视讯解码器 (对损坏的资料流进行解码，因为不能精确定义出目前资料是属于视讯的哪一部分，而与编码器(去同步 (因此如果没有使用矫正的方法，则经解码后的视讯品质会迅速降低，而且很快地全部的视讯资料都不正确。有一个解决方法就是编码器在资料流的几个地方置入重新同步的记号 (如图 2示。当解码器在检查出有错误后，它可以随后取得重新同步记号而恢复其同步。 图 2码器没有限制重新同步记号只能置放在每一列巨集区块(开端。编码器可以有选择的将影像分割到视讯封包内。每一个视讯封包是由数个连续的巨集区块所组成。这些巨集区块可以在视讯中延展成多列的形式也可以只是部分被包含。一种 码器的建议操作模式，就是每隔 k 位元 (期性地将重新同步 记号置入。当视讯的一个部分包含了重要的资料，则巨集区块相对应于这个区域就会产生比视讯中的其他区域更多的位元。现在，如果 码器将重新同步记号以同样的位元间隔置入 (可以为 512位元 )，则在重要区域的重新同步记号之间的巨集间隔会比较小，而在不重要区 - 12 - 域的间隔则会比较大。因此，当短暂的突现错误产生，解码器可以迅速地将视讯中重要的区域内包含错误的巨集区块集中，并且维护重要区域的视讯品质。 另外，资料分割 (于一种比较进阶的方法，在资料流中发现错误并且以下一个重新同步记号再 同步之后，解码器会将两个重新同步记号之间含有错误资料的巨集区块隔离。如图 2是一种资料分割的方法，其将移动及巨集区块标头 ( 资料与画质资料 (开，并且在其间插入一个第二同步记号，即移动记号 (如果画质资料遗失，则利用移动资料来隐藏这些错误。也就是说，由于错误的画质资料被抛弃，就使用前一画面作移动补偿 ( 图 2料恢复 (根据前述 ， 传送压缩影音经过有错误可能的频道会有一个问题 ， 就是使用可逆式变长度码 (在解码处理的过程中，如果当解码器在解读变长度码 (据资料时发现错误就会失去同步，并且依照惯例地将下一个重新同步点之前的资料移除。使用可逆式变长度码 (以缓和这个问题，并且使解码器可以更有效率的隔离错误区域。也就 是说，这种可逆式变长度码 (一种特殊的变长度码 (其字首代表可以正向与反向的意思，它可以从正、反两个方向进行解码。其优点是当解码器从正向进行解码而发现错误时，它会跳到下一个重新同步记号并进行反向解码，直到又发现错误为止，如图 2时解码器会尝试将两个错误位置之间的资料进行恢复，如果失败就只要将两个错误之间的资料移除，而不是将两个重新同步记号的资料移除。因此，善加利用可逆式变长度码 (术， - 13 - 可以提高资料复原的比例。 图 2错 (盖错是极为重要的技术，在采取资料恢复方法之后，还需要对那些无法恢复的错误资料做一些处理，也就是如何把错误的资料隐藏起来，让那些错误不会太明显。目前 低位元率下，对错误资料的处理方式是使用盖错的方法，此方法十分简单，就是直接复制前一个画面来取代有错误的画面，亦如前面资料分割 (述，这样因为前后两个画面基本上的差距不会太大，所以方法虽简单但效果也不错。 另外，因为档头资料所包含的资讯是有关于影音资料的规格大小，以及 解码与影音有关的 有影音物件所使用的编码方式。如果这些资讯因为频道的杂讯而受到干扰，解码器将因为没有其他的参考依据，只好将属于这些资讯的影音全部移除。为了减低这方面错误所造成的损失， 构引入，亦如图 1所示。在每个影音封包中会使用一个 1位元的栏位来当作 果这个位元被设定，则描述影音视讯的重要档头资讯会在影音封包中一直被重复。如果影音资料的档头受到干扰，解码器仍然可以使用影音封包中的档头资 讯对影音资料的其余资料进行解码。在 可以发现，使用 且可以帮助获得更高的整体影音解码品质。 - 14 - 第三章 是由 I. S. . 960年首先提出来的。它在计算机纠错系统，特别是储存系统如：光碟 (磁碟、磁带中用的很普遍，并 已广泛使用在多媒体通讯上 33。RS 用不同的解码演算法除错，例如 可除两个未知错或四个已知错； 下为其应用的范围： 储存装置 ( 无线电、行动电话及微波 (or 卫星通讯 ( 数 位电视 ( 高速电话线传输 (RS 如 后将如同元件般直接叫入使用，这意味着解码器 (编码器复杂且慢，所以如何提升解码器的速度，就变成非常重要的主题 25,34。 3S 学定义 在实现 RS 35，须先决定 抗未知错数 t (抗 t 个 因而需要 2此外，假设每笔资料 (位元数为 m，则构成一个，因此一组 包括冗余资料 )最多为12 根据以上所述，一组 为 k=此可定义 n, k)， t，其代表 为了抗最多 附加 2共 此计 - 15 - 算资料比率 (此可知， 为了具备较好的抗错能力而选择较大的 而造成 一组 会降低传输率 (造成不良之影响。 然而在某些应用情况下，位元数为 m，但 不如上述定义之 12 大。此时需以 较大的 用较短的 例说明：当决定的抗错力是解两个 知错 )或是一个 此设计为运用两笔冗余资料的 RS 是为了配合电脑资料表示及传递规格，所采用的位元数为 m=8 (8 位元 )，故一组 个 时，如果 55的话，就必须利用 大小。 RS 要先了解其乘法 25及加法的意义及动作原理，则可开始了解 RS 上述定义位元数 根据 便产生 的主要元素 (作为日后编码或解码用。关于 子 。因此令 m=8，使用的 1)( 2348 式中 ”+” 号为 代表 上式代入值使得 p( )=0，可找出所有 82 )的元素，并建立一个元素表，此表为以后编码或解码时所使用的元素值，如表 3 - 16 - 表 3初始元素表 3依据上一节的 RS F( 82 )之后，便可根据定义及所产生的元素表，进行 加及乘的运算，进行资料编码。 首先，计算 tj 1 )()( 其中 式最高项为 2t (g(x)=2t)。将原始资料以多项式系数 (式表示，并标示为I(x)=(1,I 编码动作可表示为求取余数： )()( g(x) 此式中由于 g(x)的最高项为 2t，故 d(x)的最高项必小于 2t。 上 式所得之结果 d(x)便是编码所产生之冗余资料，将其与原始资料一同储存，故编码结果可表示为： )()()()()( 2 t - 17 - 由此式可知，编码结果 C(x)必可被 g(x)整除，如此据以抗错及解错。编码器示意图如图 3 图 3图中可看出 S (n, k)编码器编码后，输出为 n=k+2t。若编码后的资料在传送过程中出错，其错误模型可表示为 e(x)，则接收端所收到的资料 (表示为： r(x)=C(x)+e(x) m(x)g(x) 若错误的数量在解错的范围内，仍可根据 C(x)所含之资讯解错。 图 3编码器示意图 图 3为两笔冗余资料的编码器。右边为原始资料输 - 18 - 入，左边为编码后资料输出。图中 待 果存放于两个 由控制器 (制，先将原始资料输出，再将编码所产生之冗余资料尾随原始资料之后输出，形成一组连续的资料序列。 3编码器如上一节所述，理论的主要部分为取余数运算，较简单且容易实现 ，但解码器与编码器相反，其解码步骤较多，硬体也复杂些。本节所述之解码器的输入资料必须为上一节编码器编码过的资料，若使用不同解码器，则必须用不同的编码器编码。解码示意图如下图 3 图 3解码示意图 解码器的输入资料用 r(x)表示，其可能是已经出错的资料。输入为 过解码器计算后，输出亦为 出资料则用 C(x)表示，与编码过的资料表示法相同。这代表原始资料经编码后储存，尔后再读出时却可能已经出错，但经解码器运算后，错误的部份将会被更正。只需将冗余资料去除掉，便为正确之原始资 料。 然而若要解已知错 (则必须外界提供错误位于何处之额外资讯。用 - 19 - j，则已知错误位置的资讯可表示为： ti j 1 )1()( 此式为 表已知错位置， 0j码器所接收到的资料是否出错，可经由下式计算而判别出其症状 (这些症状值包含所有错误大小及位置： )()()()( ， k=1, 2, , 2t 式中计算结果只剩下 e( k )，因为 k 为 3g(x)的根，而 g(x)可整除C(x)，故代入后 C( k )将被消掉。经过 有 2, 全为 0则代表资料正确无误；若不全为 0则表示有错误存在，导致 e(x)残留不为 0的值，必须进行解错运算。其中每个 位元宽度与 3若 3此时 。 症状值算完后便可得知资料是 否出错，若有错则必须继续找出错误位置及错误大小之步骤，如下所述： 先以皮德森演算法 (将上述计算出之症状值解出错误位置多项式 ( tt tt )( ，其中 10 ， 011 / 并将所有症状值以多项式形式表示 ( tk kk 1 1)( 此刻解码器已解算出错误 症状值、未知错误位置多项式，并由外界提供而计算出已知错误位置多项式，接下来必须计算错误的大小。然而本例设计之 RS 解一个未知错或二个已知错，故在此造成一个分支，视不同状况而以不同方式计算错误的大小 ( )()()( ， er a s u r er r o ( )()( 若有已知错则以已知错误多项式 (解错；若无已知错则使用上 - 20 - 述解算出之错误位置多项式 (进行解错运算。 现已获得错误位置与错误大小之个别多项式，只需将所有根代入并计算，便可得该错误位置及错误大小： )( )()( 最后便是针对错误位置，将解算出的错误大小以 e(x)表示，并将 e(x)加回 r(x)，便可将错误消掉而达到修正之结果， C(x)便为解码后正确的资料： C(x) = r(x) + e(x) 综合以上所述，总结解码器之运作流程如图 3 图 3解码器之流程图 - 21 - 依据上述之流程，其方块图如下图 3 图 3解码器方块图 图 3错误解算出之后，将输入资料修改。最下面的 后可见此方块图中的唯一分支点，判别是否有已知错，若有则后部将接收并处理 不再处理 后有二个 最主要作用在于个别将所有根依序代入错误位置及错误大 小二个多项式，其输出结果供后部之 备 - 22 - 第四章 4散傅立叶转换 (离散讯号 )(一维离散傅立叶转换 (下所示 36： 10 )/2()()( Nk , 1,.,1,0 (也可以写成 10 )()( Nn (其中 2。 而 )( 反离散傅立叶转换(如下所示： 10 )/2()(1)( Nk , 1,.,1,0 (因此，形成下面的转换对： )()( (一维离散傅立叶转换有下列特质： 1. 线性 ()()()()()()( 213213 (其中 a和 2. 对称性 (若 )(实数，则 )()( (3. 与回旋积的关系 对于两个长度分别为 1N 及 2N 的离散讯号 )(1 )(2 执行回旋积定义)()()( 213 后， )(3 长度可达 121 现在将 )(1 )(2 别添补 12 N 及 11N 个零后，将其视为长度为 (,1 与 )(,2 ， - 23 - 且其 (1 )(2 则 )()()( 213 (换言之，这是透过 合下一节所讨论的快速傅立叶转换，当所考虑讯号的长度大到一个程度以后，以上式执行回旋积会比用定义直接计算快，而且讯号长度越长，所节省的时间越多。二维离散傅立叶转换具备一维情况完全相同的性质。 4速傅立叶转换 (快速傅立叶转换 (一种用来计算离散傅立叶转换及反离散傅立叶转换的高效率演算法。快速傅利叶转换的价值在于它使用更快的计算方式来节省计算机的时间，降低了数位讯号处理中乘法的运算量，使得更多更复杂的讯号得以快速的处理，改善了数位讯号不能即时处理的问题，为数位讯号的即时处理带来了希望，因此，快速傅立叶转换是数位讯号处理发展史上的一个重要里程碑。 快速傅立叶转换的演算法，可分为时间端分组 (频率端分组 (种 36。 兹以 N=16的离散函数 )(例说明之。因为 N=16，所以 15 0 )()( n 15,.,1,0k (依照偶数位置和奇数位置，将序列 )(成两个序列，可得 1501501616 )()()(e v e 因为 8/2)2(16/2)2(16 (所以 - 24 - 7 0 87 0 168 )12()2()( n (若令 )2()(10 ()12()(11 (则 7 0 8117 0 16810 )()()( n (令 7 0 81010 )()( n ( 7 0 81111 )()( n (7,.,1,0r ，即分别为 )(10 )(11 8点 写 得 )()()( 111610 r (另外，由 (8 也可轻松证得 )()()8( 111610 r (7,.,1,0r 。可见 所谓的蝶形 (算单元。在图 4图形来代表一个蝶形运算单元，其中 变动因子 ( 前三级可依此类推。亦即一个 16点的 个 8点 8点的 个 4点 4点的个 2点 个 - 25 - 图 4 运算单元。 (a)蝶形运算单元； (b)为 (a)之简图。 图 4整个 算法的流程图 - 26 - 图中输出入序列的序号间恰有位元倒置的关系。所谓位元倒置就是将一序列之序号的二进位码反序后作为新的序号。 前面的 在 其他过程则相同。 我们再度以 N=16的离散函数 )(例说明之。因为 N=16，所以 15 0 )()( n 15,.,1,0k (将上式依 )(成两部份，即 15 0 15 8 1616 )()()( n n (其中第二个和可写成 15 8 7 0 7 0 16)8(1616 )8()1()8()(n n n (将此结果代回