On the random generation and counting of weak order extensions of a poset with given class cardinalities

In previous work, we have proposed a simple algorithm to generate random linear extensions of a partially ordered set (poset). A closely related problem is the random generation of so-called weak order extensions of a poset. Such an extension can be informally characterized as a linear order on the equivalence classes of a partition of the poset, not contradicting the underlying poset order. The generation of linear extensions can then be seen as a special case of the generation of weak order extensions where each equivalence class degenerates into a singleton. If no a priori knowledge about the underlying partition is available, time complexity increases tremendously. In first instance, we therefore restrict to the generation of weak order extensions with given class cardinalities, a problem encountered in the context of ranking algorithms. It will be shown that a first random weak order extension can be generated in O(w²(P)·|I(P)|) time, while every subsequent extension with the same class cardinalities can be obtained in O(w(P)·|P|) time, where |I(P)| denotes the number of ideals of the poset P, and w(P) the width of the poset P. Additionally, the number of weak order extensions obeying the specified class cardinalities can also be obtained in the stated O(w²(P)·|I(P)|) time.     

位平面与Gray码相结合的图像置乱方法

针对数字图像的传输安全问题,提出一种将位平面分解与Gray码相结合的图像置乱方法。该方法首先将图像分解成8个位平面,通过位异或操作改变携带图像有用信息的高4位位平面的值,然后对得到的初步置乱图像的灰度值进行Gray码变换,进一步置乱图像,从而得到加密图像。初步实验结果显示,该方法置乱效果明显优于Arnold法、Hilbert法等现有置乱方法,且实现简单。     

Parallel binary reflected Gray code sequence generation on multicore architectures

We propose a novel parallel algorithm for generating all the sequences of binary reflected Gray code for a given number of bits as input, targeting machines with multicore architectures. A theoretical analysis of work and span, as well as parallelism of this algorithm, is carried out following a multithreaded implementation using Cilk++ on a multicore machine. Theoretical analysis of this algorithm shows a parallelism of Θ(2ⁿ/log n) and achieves a linear speedup on 12 cores for input data of sufficiently large size.     

Constant time generation of derangements

This paper presents the first constant time generation algorithm for derangements—permutations with no fixed points. Each derangement is obtained from its predecessor by making either one transposition or one rotation of three elements. It also generalizes this to permutations with a bounded number of fixed points.     

双混沌和广义Gray码相融合的图像加密算法

针对部分现有图像加密算法加密效率与安全性的不足,提出了一种新的图像加密算法。算法利用Kent映射对图像进行分块重排列,然后再重新进行全局位置置乱。接下来利用Logistic映射构造下标序列,利用下标序列对置乱图像的像素点进行异或。最后将异或后的像素值进行广义Gray码变换。实验表明,该算法加密后的图像满足如下特点：足够大的密钥空间、均匀分布的灰度直方图、弱相关性等。该算法具有良好的安全性和加密效果。     

Finding cycles in hierarchical hypercube networks

The hierarchical hypercube network, which was proposed as an alternative to the hypercube, is suitable for building a large-scale multiprocessor system. A bipartite graph G=(V,E) is bipancyclic if it contains cycles of all even lengths ranging from 4 to |V|. In this paper, we show that the hierarchical hypercube network is bipancyclic.     

Efficient embedded code generation with multiple load/store instructions

In a recent study, we discovered that many single load/store operations in embedded applications can be parallelized and thus encoded simultaneously in a single‐instruction multiple‐data instruction, called the multiple load/store (MLS) instruction. In this work, we investigate the problem of utilizing MLS instructions to produce optimized machine code, and propose an effective approach to the problem. Specifically, we formalize the MLS problem, that is, the problem of maximizing the use of MLS instructions with an unlimited register file size. Based on this analysis, we show that we can solve the problem efficiently by translating it into a variant of the problem finding a maximum weighted path cover in a dynamic weighted graph. To handle a more realistic case of the finite size of the register file, our solution is then extended to take into account the constraints of register sequencing in MLS instructions and the limited register resource available in the target processor. We demonstrate the effectiveness of our approach experimentally by using a set of benchmark programs. In summary, our approach can reduce the number of loads/stores by 13.3% on average, compared with the code generated from existing compilers. The total code size reduction is 3.6%. This code size reduction comes at almost no cost because the overall increase in compilation time as a result of our technique remains quite minimal. Copyright © 2007 John Wiley & Sons, Ltd.     

F2+uF2和Z4上循环码的Gray象

利用Gray映射Φ的性质,研究了环F₂+uF₂和Z₄上的任意长循环码。证明了环F₂+uF₂上任意长码是循环码当且仅当它的Gray象是域F2上的准循环码,得到了Z₄上任意长码是循环码的一个充分必要条件。特别的,环F₂+uF₂上长为n的线性循环码的Gray象是域F₂上指标为2长为2n的线性准循环码,环Z₄上长为n的线性循环码的Gray象是域F₂上指标为2长为2n的准循环码。     

More restrictive Gray codes for some classes of pattern avoiding permutations

In a recent article [W.M.B. Dukes, M.F. Flanagan, T. Mansour, V. Vajnovszki, Combinatorial Gray codes for classes of pattern avoiding permutations, Theoret. Comput. Sci. 396 (2008) 35-49], Dukes, Flanagan, Mansour and Vajnovszki present Gray codes for several families of pattern avoiding permutations. In their Gray codes two consecutive objects differ in at most four or five positions, which is not optimal. In this paper, we present a unified construction in order to refine their results (or to find other Gray codes). In particular, we obtain more restrictive Gray codes for the two Wilf classes of Catalan permutations of length n; two consecutive objects differ in at most two or three positions which is optimal for n odd. Other refinements have been found for permutation sets enumerated by the numbers of Schröder, Pell, even index Fibonacci numbers and the central binomial coefficients. A general efficient generating algorithm is also given.     

Efficient generation of plane trees

A rooted plane tree is a rooted tree with a left-to-right ordering specified for the children of each vertex. In this paper we give a simple algorithm to generate all rooted plane trees with at most n vertices. The algorithm uses O(n) space and generates such trees in O(1) time per tree without duplications. The algorithm does not output entire trees but the difference from the previous tree. By modifying the algorithm we can generate without duplications all rooted plane trees having exactly n vertices in O(1) time per tree, all rooted plane trees having at most n vertices with maximum degree at most D in O(1) time per tree, and all rooted plane trees having exactly n vertices including exactly c leaves in O(n−c) time per tree. Also we can generate without duplications all (non-rooted) plane trees having exactly n vertices in O(n³) time per tree.     

Gray编码对族群进化算法性能的改进

族群进化算法（EGEA）利用族群机制进行群体结构调控。在基于二进制编码的群体中,个体间编码的差异性被作为族群聚类的标准。由于自然二进制编码所存在的Hamming悬崖问题易影响族群聚类的准确性,从而降低EGEA的搜索效率,因此提出利用Gray编码连续个体间编码只有一位不同的特点来改进族群聚类的精度。针对典型多维函数的仿真实验表明,基于Gray编码的族群聚类过程可显著提高EGEA的收敛速度和解的精度。     

Mediator模型的SystemC代码自动生成

Mediator是一种基于组件的建模语言,该语言主要通过自动机和系统对模型进行描述。将Mediator语言描述的模型自动生成为可执行代码,可以避免编码过程中由于人为疏忽而造成的错误,从而提高编码的可靠性,同时缩短模型开发周期。介绍一种从Mediator模型到SystemC代码的自动生成工具,该工具旨在将基于特定平台的模型转换为能直接仿真运行的代码。首先对Mediator语言的语法语义进行分析,选择合适的SystemC代码组织形式,然后针对Mediator模型的每一个组成部分 设计生成规则,其中重点对类型生成、状态转移语句生成、同步语句的生成进行分析。最后,通过一个机器掉电检测系统说明该工具运行结果的正确性。     

基于Gray码的异步FIFO接口技术及其应用

本文介绍了利用异步FIFO在跨时钟域的逻辑设计中进行异步接口的技术,介绍了利用Gray码作异步FIFO指针的方法。这些技术和方法对于异步逻辑的设计具有广泛的参考意义。     

MPI通信代码自动生成算法

对于高性能并行计算机而言，如何由给出的计算、数据划分信息及精确数组数据流分析信息自动生成并行化代码是实现串行程序并行化的一个重要问题。根据Saman P.Amarasinghe和Lam的定理，实现了一种并行化识别工具中MPI（Message Passing Interface）并行化代码自动生成技术的算法，并对该算法的性能进行分析。     

基于格雷码的无人机图像传输自适应译码算法

传统的无人机与地面接收机之间的信道编码采用Turbo码、LDPC码等.Turbo码和LDPC码译码复杂、实时性不足、硬件成本高,其中LDPC码在高信噪比时候易导致错误地板.格雷码运算复杂度低,运算时间少,硬件实现简单且功耗也相对更低.针对这一现状,本文提出了基于格雷码的无人机图像传输自适应译码算法.在格雷码软硬判决译码算法的基础上设计了依据奇偶校验位的译码判决机制.仿真结果表明,该算法复杂度低、运行速度快、可靠性好,硬件成本低,可在满足图像精度需求下自适应地选择合适的解码方法,提高解码速度.     

基于AutoSAR规范的驱动代码生成工具箱设计与实现

针对汽车控制器中驱动代码生成存在对硬件依赖性强、代码格式不规范、可重用性不强等问题,提出利用仿真建模工具Simulink/RTW、结合AutoSAR规范、基于代码生成技术的汽车控制器驱动工具箱的设计方法。通过对驱动配置模块的不同芯片配置及对相关参数的设置满足多处理器需求,依据AutoSAR规范对驱动函数接口的封装实现代码的可重用性。最后将设计的驱动工具箱结合代码生成模板应用于BCM车窗控制系统,实验证明了该方法的高效性和可行性。     

Disjoint Hamilton cycles in the star graph

In 1987, Akers, Harel and Krishnamurthy proposed the star graph Σ(n) as a new topology for interconnection networks. Hamiltonian properties of these graphs have been investigated by several authors. In this paper, we prove that Σ(n) contains ⌊n/8⌋ pairwise edge-disjoint Hamilton cycles when n is prime, and Ω(n/loglogn) such cycles for arbitrary n.     

Realization of distributed system models using code generation extensions

Development of distributed software systems is complex due to the distribution of resources, which complicates validation of system-wide functionality. Such systems include various facets like functionality and distribution, each of which must be validated and integrated in the final software solution. Model-based techniques advocate various abstraction approaches to cope with such challenges. To enhance model-based development, this paper proposes (1) guidelines for development of distributed systems, where the different facets are introduced gradually through systematic modeling extensions, (2) code generation capabilities supporting technology specific realizations, and (3) demonstration of the applicability of our approach using an industrial case study involving the development of a harvest planning system, where the communication infrastructure paradigm changed late in the project. When developing this system, we spent most time validating system-wide functionality. The model extensions allowed an easier change of the underlying communication paradigm and code generation supported realization of the different system representations.