Arbitrary Group Permutations on Hypercube and Nonblocability of Cube-connected Cycles

For packet switching of arbitrary group permutations on the hypercube and arbitrary permutations on the cube-connected cycles with small number of node channels, methods of conflictless realization were proposed, and their speed was considered.     

正形置换的一种启发式构造策略

正形置换是对称密码体制中一类重要的基础置换.论文提出了一种利用演化算法来优化正形置换的方案,并基于该方案得到了一些密码学性质优良的正形置换.该方法同时使得正形置换的构造实现了自动化,为构造正形置换提供了一种新方法.     

Rearrangeable Circuit-Switched Hypercube Architectures for Routing Permutations

Rearrangeable hypercube architectures and routing algorithms are developed to realize arbitrary permutations in circuit switching. We prove that if each connection between two neighboring nodes consists of two pairs of links (two full-duplex communication lines), the hypercube can handle two arbitrary permutations simultaneously. We also prove that a hypercube is rearrangeable if one additional pair of links is provided in any one dimension of connections.     

General Algorithms for Permutations in Equational Inference

Mechanized systems for equational inference often produce many terms that are permutations of one another. We propose to gain efficiency by dealing with such sets of terms in a uniform manner, by the use of efficient general algorithms on permutation groups. We show how permutation groups arise naturally in equational inference problems, and study some of their properties. We also study some general algorithms for processing permutations and permutation groups, and consider their application to equational reasoning and term-rewriting systems. Finally, we show how these techniques can be incorproated into resolution theorem-proving strategies.     

uBlock类结构最优向量置换的高效搜索

整体结构是分组密码的重要特征,也是首要的研究对象,对于分组密码的轮数选取、软硬件实现性能都有非常大的影响.对于类AES算法的设计,当选用非最优分支数的矩阵作为列混淆操作时,向量置换(即字换位操作)的选择可有效提高整体结构的安全性.uBlock类结构是一种类AES结构,通过研究uBlock类结构的特点及其扩散性,给出了其全扩散轮数的下界及等价类划分准则,提出了一种uBlock类结构最优向量置换的搜索策略.依据全扩散轮数最优、超级扩散层的分支数最优及uBlock类结构扩散层的特殊性质,证明了左右向量置换都不能是恒等变换,给出了uBlock类结构的一系列最优向量置换.该搜索策略大幅度减少了需要测试的置换对,为后续uBlock类算法的设计提供技术支持.     

布尔置换与Costas阵列

研究了通信系统中重要的Castas阵列。给出一种简洁的证明一般布尔代数上的布尔置换的充要条件的方法,并依此给出了一类Costas阵列。     

Common Intervals of Multiple Permutations

Given k permutations of n elements, a k-tuple of intervals of these permutations consisting of the same set of elements is called a common interval. We present an algorithm that finds in a family of k permutations of n elements all z common intervals in optimal O(kn+z) time and O(n) additional space. Additionally, we show how to adapt this algorithm to multichromosomal and circular permutations.     

联机手写中文速记符的自动识别

手写中文速记符的自动识别是文字类识别中的一个比较特殊的课题.实现了一个联机手写中 文速记符识别系统HCSRS(handwritten Chinese shorthand recognition system),并给出了 对速记符中的基本音符、独立略符、连笔符的识别实验结果.该识别系统采用了以声符、韵 符为基元的结构识别策略.为了实现基元的有效切分,提出了一种基于切分-分析-交互结构 及其相应知识库的自调整切分算法STSA(self-tuning segmentation algorithm),从而大大 改     

Approaches Based on Permutations for Partitioning Sparse Matrices on Multiprocessors

This paper introduces new approaches to the data distribution-partition problem for sparse matrices in a multiprocessor environment. In this work, the data partition problem of a sparse matrix is modeled as a Min-Max Problem subject to the uniformity constrain when the goal is to balance the load for both sparse and dense operations. This problem is NP-Complete and two heuristic solutions (ABO and GPB) are proposed. The key of ABO and GPB is to determine the permutation of rows/columns of the input sparse matrix to obtain a sorted matrix with a homogeneous density of nonzero elements. Due to the heuristic nature of the proposed methods their validation is carried out by a comparative study of the parallel efficiency of two types of problems (sparse and mixed) when ABO, GPB, Block, Cyclic and MRD data distributions are applied.This work has been partially supported by the Spanish CICYT through grant TIC2002-00228.     

An Optimal Systolic Algorithm for Generating Permutations in Lexicographic Order

A systolic algorithm is described for generating all permutations of n elements in lexicographic order. The algorithm is designed to be executed on a linear array of n processors, each having constant size memory, and each being responsible for producing one element of a given permutation. There is a constant delay per permutation, leading to an O(n!) time solution. This is an improvement over the best previously known techniques in two respects: the algorithm runs on the (arguably) weakest model of parallel computation, and is cost optimal (assuming the time to output the permutations is counted). The algorithm is extended to run adaptively, i.e., when the number of available processors is other than n.     

三元组布尔置换的构造

布尔置换和bent函数在密码学中起着非常重要的作用。在Coulter和Mesnager所提出的三元组布尔置换广义构造方法（该三元组布尔置换可以用来构造bent函数）的基础上，给出了一个等价的构造三元组布尔置换的具体方法。利用此具体方法，提供了一个构造三元组布尔置换的算法。对三个置换之间的依赖关系做了进一步研究，提出了一个三元组置换成立的充要条件，并给出了一个构造三元组布尔置换的新算法。分析了利用三元组布尔置换所得bent函数的性质。     

Single-Cycle Bit Permutations with MOMR Execution

Secure computing paradigms impose new architectural challenges for general-purpose processors. Cryptographic processing is needed for secure communications, storage, and computations. We identify two categories of operations in symmetric-key and public-key cryptographic algorithms that are not common in previous general-purpose workloads： advanced bit operations within a word and multi-word operations. We define MOMR （Multiple Operands Multiple Results） execution or datarich execution as a unified solution to both challenges. It allows arbitrary n-bit permutations to be achieved in one or two cycles, rather than O（n） cycles as in existing RISC processors. It also enables significant acceleration of multiword multiplications needed by public-key ciphers. We propose two implementations of MOMR： one employs only hardware changes while the other uses Instruction Set Architecture （ISA） support. We show that MOMR execution leverages available resources in typical multi-issue processors with minimal additional cost. Multi-issue processors enhanced with MOMR units provide additional speedup over standard multi-issue processors with the same datapath. MOMR is a general architectural solution for word-oriented processor architectures to incorporate datarich operations.     

Routing Permutations on Graphs via Factors

We deal with the permutation routing problem on graphs modeling interconnection networks. In our model, calledrouting via factors, at each routing step, the communication pattern is a directed 1-factor in a symmetric digraph. This adds a new feature, that of continuous packet movement, to preciously studied routing types, where the routing of a permutation is reduced to a sequence of permutations from a given class. We especially focus on bipartite graphs and we give sufficient conditions for a graph to be rearrangeable in our model. We propose a general technic for routing via factors that we apply to the 2D mesh and the hypercube.     

正形置换的枚举与计数

正形置换在密码算法的设计中占有很重要的地位．研究正形置换的特性、枚举、计数对于密码设计和密码分析均具有重要的意义．正形置换的理论研究已成为国内外密码学编码理论的热点问题．对正形置换的计数和枚举问题进行讨论,利用和阵给出了正形置换的一个枚举方法,利用该方法可以列出所有的”阶正形置换．国内外相关文献中还未见到正形置换的枚举方法．由该枚举法得出了n阶正形置换个数Nn的上界和下界,这个结果比迄今为止给出的结果都要好,是目前给出的最优上下界．     

从美国速记员资格认证看速记的重要性

美国速记员资格认证分为各个地方州认证和联邦政府认证,要求严格,规定详细,突出了速记工作的重要性和速记员职责的特别性。美国速记的历史源远流长,对中国的影响也很深远。了解和学习美国的速记工作有助于中国速记的发展,更好为现代化建设服务。     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).