论文部分内容阅读
【摘 要】动态规划属算法设计方案，多用在寻找问问题最优解方面。若把动态规划的所有子问题皆看作有向图的节点，则动态规划便可被考虑成对应的有向无圈图。针对某些具有特殊结构的有向无圈图，其往往可以为动态规划提供更大的便捷度。移动通信通常采用优化通信编码方案，已达到控制宿主能耗的目的。本文就移动通信内降低能耗的前缀码的动态规划加速问题展开讨论。
【关键词】移动通信 前缀码 动态规划 时间复杂度
一、前缀码
所谓前缀码，其一直被定性为计算机科学和信息论领域的经典问题。如果要对n个符号予以二进制编码，则Huffman编码仅需依托贪婪算法和O（nlgn）的时间复杂度便可获取该组符号的最优编码。Huffman编码亦可用来推到r个码元的最优编码。如果单词以排序状态出现频率，Huffman编码算法可把时间复杂度控制到O（m）阶段。针对前缀码问题，诸多学者皆做了大量的研究。研究证实，编码后字符串内码元的分布位置对对应码元的长度起决定性的作用。基于此，本文引入了一种构造前缀码的动态规划改进法，即把动态规划的状态集合以若干批次呈现出来，而状态结合间呈相互依赖关系。通过对各状态值予以成批量计算后，便可把计算各状态的平摊时间复杂度控制到O（1）。
二、预备知识
（一）问题定义
为了实现对问题的形式化定义，本文引入如下参数量：N为待编码的符号集合；n为符号集合的取值；pi为各符号的分布概率。本文认为概率的排序问题对算法时间复杂度的影响并不大。基于此，本文假定概率已排序（p1≥p2≥p3……≥pn），编码后的字符串集合记做W=﹛w1，w2，w3……，wn?﹜， w1的长度记做，wi内1的个数记做wt（wi）。那么，该编码的期望长度可表示为：
本文讨论的问题为：移动任一可行编码的宿主，由此发出的任一单词wi的耗能皆存有上界U，其中。此时，本文需要从整个编码W内挑选出一个满足最小的。
（二）最优树性质
若编码为二进制，则一个前缀码通常可映射到一棵二叉树，其中二叉树的叶节点与前缀码的待编码符号呈一一对应关系。针对二叉树的边，本文把向左的边记做1，向右的边记做0，此时可把叶节点与根节点间分布的01字符串假定为叶节点对应符号的编码。就节点v而言，如果节点与根节点间的距离长约i，则该节点便被看作分布在第i层。如果仅对二叉树第i层及以上部分作出考虑，则此情况可被称作i层数或i层部分树。本文把i层树的节点深度表述为d（v），而通常把节点与根节点间分布的1的个数表述为wt（v），即节点的权重。如果编码后的符号wi与叶节点vi间呈一一对应关系，其中该节点的概率被记做pi，。那么，此二叉树的代价可被表述为：
（为叶节点）
针对与最优编码呈对应关系的二叉树，其主要性质如下所示，其中本文假定最优编码已排序（p1≥p2≥p3……≥pn），叶节点与编码后字符串wi间呈对应关系，为叶节点对应符号的分布概率。
性质①，如果，那么，；
性质②，针对一棵满二叉树，其代价等效于最优二叉树，且其叶节点个数满足：（如果叶节点个数>n，则pt=0，i>n）。
性质③，就一棵最优树任何层i而言，任一分支节点及任一叶节点v皆满足：。
三、批处理加速
由最优树的递归构造（此部分省略）可知，签名总数共O（nU），则其对应的动态规划时间复杂度记做O（nU+1），下文欲就签名总数为O（nU）的集合予以分批加速动态规划。基于此，本文定义了如下集合：
式中，
d满足1≤d≤n+1；囊括了全部签名。
就d而言，上述两类集合皆囊括了指数个签名。就签名而言，由指数个可扩展成签名，则就任一而言，其可能存在的个数很多，而其中必然包含了一个最有选择。基于此，本文引入了“转换”计算方向法，即对I’（d）内经签名扩展后的代价予以批处理计算，并就I（d）签名的最优代价与I’（d）签名的代价予以对比分析。
就“转换”计算方向法而言，首先应考虑各变量在递推关系中的相互联系，并由此得出如下结论：就任一而言，所有可扩展到对应签名的皆属I’（d），其最有代价间的相互关系可描述为：
其次应选择I’（d）内O（n）个的签名，即设定一个多元组（长度约U-2）：
现把上述多元组与I（d）的某个子集对应，此子集如下：
就O（nU）的时间复杂度而言，1个d通常对应O（nU-2）个多元组，而任一多元组皆需O（n）时间查找出最小值。那么，单个d所需时间可记做O（nU-1），由此可知计算最优代价总时间复杂度应记做O（nU）。
四、结束语
综上所述，本文的研究对象为编码方面的动态规划加速问题。若符号的个数和通信内符号分布的概率既定，且各符号经编码后1分布的个数≤U，本文由此引入了一种计算编码最优期望长度的方法。计算结果显示，其时间复杂度为O（nU），则O（n2）的时间复杂度远小于由传统计算方法所获取的时间复杂度。
参考文献：
[1] 构造移动通信中降低能耗的前缀码的动态规划加速[J].计算机工程与科学，2009，31（12）：134-137.
[2] 张丙杰，胡捍英，王大鸣等.一种增强的GEO卫星CDMA通信系统随机接入方式[J].电路与系统学报，2010，15（5）：122-126.
[3] 肖尚辉，张忠培，史治平等.多基站协作下行系统中异步空时码构造与分析[J].电子科技大学学报，2010，39（3）：335-339.
[4] 孔繁庭.循环前缀在OFDM系统中的作用及应用研究[D].兰州大学，2008.
作者简介：
刘磊，1983年1月出生，现就职于河北张家口移动公司。
【关键词】移动通信 前缀码 动态规划 时间复杂度
一、前缀码
所谓前缀码，其一直被定性为计算机科学和信息论领域的经典问题。如果要对n个符号予以二进制编码，则Huffman编码仅需依托贪婪算法和O（nlgn）的时间复杂度便可获取该组符号的最优编码。Huffman编码亦可用来推到r个码元的最优编码。如果单词以排序状态出现频率，Huffman编码算法可把时间复杂度控制到O（m）阶段。针对前缀码问题，诸多学者皆做了大量的研究。研究证实，编码后字符串内码元的分布位置对对应码元的长度起决定性的作用。基于此，本文引入了一种构造前缀码的动态规划改进法，即把动态规划的状态集合以若干批次呈现出来，而状态结合间呈相互依赖关系。通过对各状态值予以成批量计算后，便可把计算各状态的平摊时间复杂度控制到O（1）。
二、预备知识
（一）问题定义
为了实现对问题的形式化定义，本文引入如下参数量：N为待编码的符号集合；n为符号集合的取值；pi为各符号的分布概率。本文认为概率的排序问题对算法时间复杂度的影响并不大。基于此，本文假定概率已排序（p1≥p2≥p3……≥pn），编码后的字符串集合记做W=﹛w1，w2，w3……，wn?﹜， w1的长度记做，wi内1的个数记做wt（wi）。那么，该编码的期望长度可表示为：
本文讨论的问题为：移动任一可行编码的宿主，由此发出的任一单词wi的耗能皆存有上界U，其中。此时，本文需要从整个编码W内挑选出一个满足最小的。
（二）最优树性质
若编码为二进制，则一个前缀码通常可映射到一棵二叉树，其中二叉树的叶节点与前缀码的待编码符号呈一一对应关系。针对二叉树的边，本文把向左的边记做1，向右的边记做0，此时可把叶节点与根节点间分布的01字符串假定为叶节点对应符号的编码。就节点v而言，如果节点与根节点间的距离长约i，则该节点便被看作分布在第i层。如果仅对二叉树第i层及以上部分作出考虑，则此情况可被称作i层数或i层部分树。本文把i层树的节点深度表述为d（v），而通常把节点与根节点间分布的1的个数表述为wt（v），即节点的权重。如果编码后的符号wi与叶节点vi间呈一一对应关系，其中该节点的概率被记做pi，。那么，此二叉树的代价可被表述为：
（为叶节点）
针对与最优编码呈对应关系的二叉树，其主要性质如下所示，其中本文假定最优编码已排序（p1≥p2≥p3……≥pn），叶节点与编码后字符串wi间呈对应关系，为叶节点对应符号的分布概率。
性质①，如果，那么，；
性质②，针对一棵满二叉树，其代价等效于最优二叉树，且其叶节点个数满足：（如果叶节点个数>n，则pt=0，i>n）。
性质③，就一棵最优树任何层i而言，任一分支节点及任一叶节点v皆满足：。
三、批处理加速
由最优树的递归构造（此部分省略）可知，签名总数共O（nU），则其对应的动态规划时间复杂度记做O（nU+1），下文欲就签名总数为O（nU）的集合予以分批加速动态规划。基于此，本文定义了如下集合：
式中，
d满足1≤d≤n+1；囊括了全部签名。
就d而言，上述两类集合皆囊括了指数个签名。就签名而言，由指数个可扩展成签名，则就任一而言，其可能存在的个数很多，而其中必然包含了一个最有选择。基于此，本文引入了“转换”计算方向法，即对I’（d）内经签名扩展后的代价予以批处理计算，并就I（d）签名的最优代价与I’（d）签名的代价予以对比分析。
就“转换”计算方向法而言，首先应考虑各变量在递推关系中的相互联系，并由此得出如下结论：就任一而言，所有可扩展到对应签名的皆属I’（d），其最有代价间的相互关系可描述为：
其次应选择I’（d）内O（n）个的签名，即设定一个多元组（长度约U-2）：
现把上述多元组与I（d）的某个子集对应，此子集如下：
就O（nU）的时间复杂度而言，1个d通常对应O（nU-2）个多元组，而任一多元组皆需O（n）时间查找出最小值。那么，单个d所需时间可记做O（nU-1），由此可知计算最优代价总时间复杂度应记做O（nU）。
四、结束语
综上所述，本文的研究对象为编码方面的动态规划加速问题。若符号的个数和通信内符号分布的概率既定，且各符号经编码后1分布的个数≤U，本文由此引入了一种计算编码最优期望长度的方法。计算结果显示，其时间复杂度为O（nU），则O（n2）的时间复杂度远小于由传统计算方法所获取的时间复杂度。
参考文献：
[1] 构造移动通信中降低能耗的前缀码的动态规划加速[J].计算机工程与科学，2009，31（12）：134-137.
[2] 张丙杰，胡捍英，王大鸣等.一种增强的GEO卫星CDMA通信系统随机接入方式[J].电路与系统学报，2010，15（5）：122-126.
[3] 肖尚辉，张忠培，史治平等.多基站协作下行系统中异步空时码构造与分析[J].电子科技大学学报，2010，39（3）：335-339.
[4] 孔繁庭.循环前缀在OFDM系统中的作用及应用研究[D].兰州大学，2008.
作者简介：
刘磊，1983年1月出生，现就职于河北张家口移动公司。