In this paper we discuss a novel storage scheme for simultaneous memory access in parallel turbo decoder. The new scheme employs vertex coloring in graph theory. Compared to a similar method that also uses unnatural o...In this paper we discuss a novel storage scheme for simultaneous memory access in parallel turbo decoder. The new scheme employs vertex coloring in graph theory. Compared to a similar method that also uses unnatural order in storage, our scheme requires 25 more memory blocks but allows a simpler configuration for variable sizes of code lengths that can be implemented on-chip. Experiment shows that for a moderate to high decoding throughput （40-100 Mbps）, the hardware cost is still affordable for 3GPP＇s （3rd generation partnership project） interleaver.展开更多
We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically.Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider...We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically.Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider the dynamically arrival model of disk requests to obtain an algorithm, shortest path first-fit first （SPFF）. This algorithm is based on the shortest path of disk head motion constructed by all the pendent requests. From view of the head moving distance, it has the stronger glohality than SSTF. From view of the head-moving direction, it has the better flexibility than SCAN. Therefore, SPFF keeps the advantage of SCAN and, at the same time, absorbs the strength of SSTF. The algorithm SPFF not only shows the more superiority than other scheduling polices, but also have higher adjustability to meet the computer system＇s different demands.展开更多
多约束尺寸可变的装箱问题作为经典装箱问题的扩展,具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中,运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别,并据此给出了一种新的...多约束尺寸可变的装箱问题作为经典装箱问题的扩展,具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中,运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别,并据此给出了一种新的尺寸可变装箱问题的定义。除了经典装箱问题中物品体积这一参数,还引入了物品类型、箱子类型等参数,建立了数学模型,将经典的FFD(First Fit Decreasing)算法进行了推广,提出了新的算法MFFD,并分析了相关的算法复杂性。最后对FF、FFD以及MFFD算法进行了模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,MFFD算法效果较好。展开更多
作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景。分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题。除了经典装箱问题中物品体积和箱子容量这两个参数,还引...作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景。分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题。除了经典装箱问题中物品体积和箱子容量这两个参数,还引入了物品类型和箱子脆度等参数,给出了相关的数学模型。在经典的FFD(First Fit Decreasing)算法的基础上进行了推广,提出了新的启发式算法NFFD,它对箱子的特性进行了预处理,再进行装箱。分析了该算法的复杂性。对NFD、FFD和NFFD算法进行了数值模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,NFFD算法的效果是最好的。展开更多
基金supported by the National High-Technology Research and Development Program of China （Grant No.2003AA123310）, and the National Natural Science Foundation of China （Grant Nos.60332030, 60572157）
文摘In this paper we discuss a novel storage scheme for simultaneous memory access in parallel turbo decoder. The new scheme employs vertex coloring in graph theory. Compared to a similar method that also uses unnatural order in storage, our scheme requires 25 more memory blocks but allows a simpler configuration for variable sizes of code lengths that can be implemented on-chip. Experiment shows that for a moderate to high decoding throughput （40-100 Mbps）, the hardware cost is still affordable for 3GPP＇s （3rd generation partnership project） interleaver.
基金Supported by the National Natural Science Founda-tion of China (60373088)
文摘We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically.Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider the dynamically arrival model of disk requests to obtain an algorithm, shortest path first-fit first （SPFF）. This algorithm is based on the shortest path of disk head motion constructed by all the pendent requests. From view of the head moving distance, it has the stronger glohality than SSTF. From view of the head-moving direction, it has the better flexibility than SCAN. Therefore, SPFF keeps the advantage of SCAN and, at the same time, absorbs the strength of SSTF. The algorithm SPFF not only shows the more superiority than other scheduling polices, but also have higher adjustability to meet the computer system＇s different demands.
文摘多约束尺寸可变的装箱问题作为经典装箱问题的扩展,具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中,运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别,并据此给出了一种新的尺寸可变装箱问题的定义。除了经典装箱问题中物品体积这一参数,还引入了物品类型、箱子类型等参数,建立了数学模型,将经典的FFD(First Fit Decreasing)算法进行了推广,提出了新的算法MFFD,并分析了相关的算法复杂性。最后对FF、FFD以及MFFD算法进行了模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,MFFD算法效果较好。
文摘作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景。分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题。除了经典装箱问题中物品体积和箱子容量这两个参数,还引入了物品类型和箱子脆度等参数,给出了相关的数学模型。在经典的FFD(First Fit Decreasing)算法的基础上进行了推广,提出了新的启发式算法NFFD,它对箱子的特性进行了预处理,再进行装箱。分析了该算法的复杂性。对NFD、FFD和NFFD算法进行了数值模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,NFFD算法的效果是最好的。
