基于矢量量化编码的数据压缩算法的研究与实现

文章摘要：BSA算法的主要思想是通过不断交换码字的位置，使得信道噪声失真的目标函数场获得局部最优值.随着交换的进行 不断下降，而且索引映射函数 也跟着不断变化。在每次迭代中，码字的交换对是按一定的顺序选择的。所有的码字y，都对应一个函数 ，用来描述当该码字的索引(在当前码书中)在噪声信道中传输时可能产生的失真，其定义为公式（3.21）：（3.21）BSA算法每次按 从大到小的顺序对码字进行排序。拥有最大函数值 的码字被选为首先交换的候选对象。首先进行试验性的交换， 与其他每一个码字分别进行交换，并计算每次交换后 的下降值。选择能使 出现最大下降的那一个码字与 进行真正地交换，然后进入下一次迭代。如果不存

基于矢量量化编码的数据压缩算法的研究与实现,标签：单片机开发,单片机原理,单片机教程,http://www.88dzw.com
BSA算法的主要思想是通过不断交换码字的位置，使得信道噪声失真的目标函数场获得局部最优值.随着交换的进行 不断下降，而且索引映射函数 也跟着不断变化。在每次迭代中，码字的交换对是按一定的顺序选择的。所有的码字y，都对应一个函数 ，用来描述当该码字的索引(在当前码书中)在噪声信道中传输时可能产生的失真，其定义为公式（3.21）：
（3.21）
BSA算法每次按 从大到小的顺序对码字进行排序。拥有最大函数值 的码字被选为首先交换的候选对象。首先进行试验性的交换， 与其他每一个码字分别进行交换，并计算每次交换后 的下降值。选择能使 出现最大下降的那一个码字与 进行真正地交换，然后进入下一次迭代。如果不存在这样的码字，则对yi作相同的交换试验。如果每一个码字按这种方法与其他码字进行交换后。不再下降，则终止算法，从而获得一个局部最优的码字索引分配方案。算法的具体步骤如下：
Step 1：初始化。随机打乱码字的排序；
Step 2：整理排序。根据 从大到小的顺序对码字yi进行排序。令n=－1；
Step 3：试验性交换。令n＝n＋1从j＝n＋1到N一1，分别计算索引n和索弓!j交换后所能引起的失真减少量，比较这些失真减少量，获得最大的失真下降量 ；
Step 4：如果 >0，则交换索引n和引起最大失真下降的索引j，并转Step 2；
Step 5：终止算法。如果n=N一1，则终止算法，否则，转Step 3。
可以看出，BSA算法根据函数值 将码字进行排列而选择出哪一个码字最先进行交换，从而在运算上给出了一个方向性引导。如果由于程序运行时间的限制而使算法的迭代次数有限，则这种方向性引导将显得尤为重要。每一次成功交换的完成，代表一次迭代的结束。若一次迭代中的所有试验性交换产生的失真下降都不大于O，则说明算法已经达到一个局部最优解.应该指出的是:从不同的初始码字排序出发，可获得不同的局部最优解，从而保证BSA算法对于码字交换的限制不会影响它获得全局最优码字索引分配方案的可能性。实验证明，该算法获得的码字索引分配方案的失真比随机码字索引分配方案的失真有较大改进。
3．3．2 禁止搜索码字索引算法
禁止搜索的基本思想是通过一系列移动来搜寻所有可行解的搜索空间，并且在当前迭代中禁止某些搜索方向以避免死循环和跳入局部极小。由当前解到其邻域解的移动被部分地或完全地记录在禁止表中，目的是为了禁止以后迭代中的重复操作。
令 为测试解的集合，其中元素si可以被表示为式【8】（3.22）：
（3.22）
其中，N为码书的尺寸，Si(j)表示在解si中分配给码字Yj的索引， 令 和 分别表示当前解和最优解。中码字Yj的索引，Sb(j)仍表示分配给解Sb中码字Yi的索引。
令 ， 和 分别代表测试解组的目标函数值集合，当前解的目标函数值和最优解的目标函数值，其中 是测试解 的目标函数值，0<i<Ns-1。初始的当前解是随机产生的，通过随机交换当前解中的两个索引来产生测试解。禁止表中只存储交换的索引。如果从当前解中产生测试解的交换索引与禁止表中任何记录相同，则称该测试解为禁止解。该算法的具体步骤如下:
Step 1：设置禁止表大小Ts测试解个数N，以及迭代次数Im。令迭代计数器i=1，禁止表插入点t=1。随机产生当前解 ，计算其相应的目标函数值V}。令Sb=Sc以及Vb=Vc
Step 2：把当前解Sc拷贝给每一个测试解si, 0<i<Ns-1。对每一个测试解si，0<i< Ns-1，产生两个随机整数r1和r2， ， ， 。N为码字个数，然后通过交换索引 和 产生新测试解组。计算测试解的函数值 。
Step 3：如果最优测试解的目标函数值比最优解的目标函数值Vb还小，则把它作为新的当前解，并令其目标函数值作为当前解的目标函数值Vc，转Step 3。否则，选出测试解中最好的非禁止解。如果能选到，则把它作为新的当前解Sc并令其目标函数值作为当前解的目标函数值Vc，转Step 3；否则，转Step 1。
Step 4： 如果vb>vc，令Sb=Sc，Vb＝Vc，把从旧当前解到新当前解所交换过的索引插入禁止表中。禁止表的插入点设为ti=ti+1;如果ti>Ts，令ti＝l，如果i<Im，令i=i+1转Step 1；否则，算法结束。

第四章 矢量量化算法的实现
4．1 需求分析与整体设计
4．1．1需求分析

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]  下一页