基于遗传进化的元胞级并行无失真数据压缩方法

利用一阶和二阶细胞自动机,进行元胞级并行无失真数据压缩,细胞自动机中的数据压缩规则由遗传进化算法得到,构造相应的全局置的置换映射,分别证明了一阶和二阶细胞自动机文本压缩规则的正确性。讨论阴关的时间复杂性及符号动力学特性。     

细胞自动机语言Cellang的扩展与应用

并行执行与并行描述是并行计算的两个方面,后者是并行软件技术的一个日益重要的问题,目前主流的并行语言都是针对特定的需求设计的。细胞自动机对许多问题具有自然而贴切的描述并行性,作为动力学系统仿真工具与并行离散计算模型近来受到广泛关注。通过对某些细胞自动机语言进行扩展,可以使其成为并行数值计算的良好工具,方便地描述与求解一大类并行数值计算问题。本文介绍我们对细胞自动机语言Cellang的扩展及在并行数值计算上的应用。     

散列高阶字典编码及其实现*

该文引入了散列高阶字典的概念,提出了一个使用散列高阶字典实现数据压缩的模型.实验数据表明,该模型比传统的数据压缩字典方法具有更高的数据压缩能力.     

对称耦合式触发细胞自动机在加密中的应用

提出一种基于一维触发细胞自动机的数据加密算法.待加密的数据块被分成两个等长的子块在两个触发细胞自动机上并行加密.细胞自动机之间采用对称耦合结构,每个细胞自动机迭代时采用的反转规则不仅依赖于其自身的状态,也依赖于与其耦合的细胞自动机以及密钥流的状态.这种结构降低了硬件的实现代价并实现了密钥分存,确保只有在同时获得一对密文时才能正确解密,而且两个子数据块并行加密提高了加密效率.触发细胞自动机的反转规则由子密钥流和数据本身共同决定.密钥空间,即反转规则表,随着细胞自动机邻居半径增大呈指数增长,所以可以根据不同的安全性要求,通过增加细胞自动机的邻居半径来实现.     

CUDA并行数据压缩技术研究

在信息爆炸的今天,提高海量数据压缩比和压缩速度已成为一种迫切需求。该文主要通过介绍数据压缩的背景知识、数据压缩的现状,详细分析了基于bzip2的并行数据压缩技术及其并行实现高速数据压缩的算法,提出在CUDA架构上利用GPU实现并行数据压缩的方法。结果表明,该文提出的方法相对于在CPU上并行压缩,虽然压缩速度降低但压缩比却提高了,这体现了CUDA的优势和局限性。     

新型细胞自动机规则空间的参数化

细胞自动机在复杂性科学研究中占有重要地位,规则空间的规律性是细胞自动机理论研究的核心问题。本文首次引入沃尔什正交变换,结合计算机实验,提出了刻画细胞自动机规则空间规律性的δ参数。通过对所有初等细胞自动机的分析,并与朗顿λ参数的对比研究,结果表明该参数能更好地刻画细胞自动机规则空间中从有序到混沌的相变,不存在关于相变临界值的争论。     

基于并行状态自动机的工作流建模

为了实现工作流管理功能，首先要把业务过程从现实世界抽象出来，并用一种形式化方法对其进行描述，其结果就是工作流模型。该文讨论利用并行自动机对工作流的形式化问题。基于对工作流和并行自动机的分析，提出了将工作流的概念映射到并行自动机概念上的方法，该方法可以把工作流联盟提出的工作流的4种结构映射到并行自动机的结构上。给出了并行自动机的结点转化图，即给出了工作流引擎的框架。并行自动机是一种图形的、数学化的计算模型，当工作流的模型——并行自动机建立起来后，为工作流的静态特性和动态特性的分析打下不坚实的基础，为进一步的研究作好了准备。     

基于并行状态自动机的工作流建模

为了实现工作流管理功能，首先要把业务过程从观实世界抽象出来，并用一种形式化疗法对其进行描述，其结果就是工作流模型。该文讨论利用并行自动机对工作流的形式化问题。基于对工作流和并行自动机的分析，提出了将工作流的概念映射到并行自动机概念上的方法，该方法可以把工作流联盟提出的工作流的4种结构映射到并行自动机的结构上。给出了并行自动机的结点转化图，即给出了工作流引擎的框架。并行自动机是一种图形的、数学化的计算模型，当工作流的模型一并行自动机建立起来后，为工作流的静态特性和动态特性的分析打下不坚实的基础，为进一步的研究作好了准备。     

基于耦合混沌系统和细胞自动机的图像加密算法

提出一种基于耦合混沌系统和细胞自动机的加密方法。耦合混沌系统比单一混沌系统具有更复杂的动力学特性,可以增大密钥空间,提高加密系统的安全性;利用耦合触发细胞自动机实现明文分块的并行加密,提高加/解密速度,改进置乱效果。加密时首先经过混沌加密,然后利用混沌序列产生反转规则,由细胞自动机再次加密;解密过程正好相反。实验表明,这种混合加密方法具有更大的密钥空间和更好的置乱效果,能够有效抵抗蛮力攻击和差分分析攻击。     

有限状态自动机的并行确定化及过程分析

本文通过对并行环境下非确定有限自动机和确定有限自动机的等价性和转换进行研究，详细分析了非确定有限自动机到确定有限自动机的并行转换方法及算法，并以实例给出了其间并行转化的过程。     

A new parallel-by-cell approach to undistorted data compression based on cellular automaton and genetic algorithm

In this paper,a new parallel-by-cell approach to the undistorted data compression based on cellular automaton and genetic algorithm is presented.The local compression rules in a cellular automaton are obtained by using a gnetic evolutionary algorithm.The correctness of the hyper-parallel compression,the time complexity,and the relevant symbolic dynamic behaviour are discussed.In comparison with other traditional sequential or small-scale parallel methods for undistorted data compression,the proposed approcah shows much higher real-time performance,better suitability and feasibility for the systolic hardware implementation.     

The faster higher-order cellular automaton for hyper-parallel undistorted data compression

This paper defines second-order and third-order permutation global functions and presents the corresponding higher-order cellular automaton approach to the hyper-parallel undistorted data compression.The genetic algorithm is successfully devoted to finding out all the correct local compression rules for the higher-order cellualr automaton.The correctness of the higher-order compression rules,the time complexity,and the systolic hardware implementation issue are discussed.In comparison with the first-order automation method reported,the proposed higher-order approach has much faster compression speed with almost the same degree of cellular structure complexity for hardware implementation.     

基于改进蚁群算法的CA的应用——以土地利用模拟为例

元胞自动机转换规则的获取对模拟至关重要。对蚁群分类规则挖掘算法进行改进,并将该算法挖掘的转换规则作为元胞自动机的转换规则,提供了一种利用元胞自动机进行模拟的方法,以武清区土地利用模拟为例进行实验,表明了方法的有效性。该方法可应用到其他分类规则和转换规则挖掘中,也可应用到元胞自动机模拟的其他研究中。     

Simple method of selecting totalistic rules for pseudorandom number generator based on nonuniform cellular automaton

The Journal of Supercomputing - This paper is devoted to selecting rules for one-dimensional (1D) totalistic cellular automaton (TCA). These rules are used for the generation of pseudorandom...     

化学混沌与BZ反应的细观元胞自动机模拟

将所提出的细观元胞自动要应用于化学混沌与ＢＺ反应的计算机模拟,分别制定了８组分和５组分系统中粒子随机运动和反应碰撞的演化规则,建立了Ｗｉｌｌａｍｏｗｓｋｉ－Ｒｏｓｓｌｅｒ化学混沌与Ｂｅｌｏｕｓｏｖ－Ｚｈａｌｂｏｔｉｎｓｋｉ反应的二维元胞自动机模型,并在计算机上对它们进行了成功地动态模拟。     

NS模型的随机特性及其在LWR模型中的应用

本文改进了微观一维随机元胞自动机交通流模型(NS模型)的控制规则,将NS模型中的随机特性作为一个随机参量运用到宏观一阶连续交通流模型(LWR模型)中,重新构建了LWR模型的交通流基本图。在实测交通流数据基础上,应用NS模型和引入随机参量的LWR模型进行了计算机模拟和分析。     

基于模糊控制规则的元胞自动机模型

针对单车道道路交通流提出了一种新的基于模糊控制规则的元胞自动机模型。与NaSch模型不同,新模型中的随机慢化概率是根据模糊控制规则计算得来的。在新模型的模糊控制规则中,将当前车辆的车间距以及其与前车的速度差作为输入因素,经过模糊推理从而计算出当前车辆本时间步的随机慢化概率。经过计算机仿真发现,新模型的基本图和时空图较好地重现了现实道路交通流中的某些宏观特性,如时走时停波、回滞以及亚稳态等现象。     

Liesegang环带的形成机理及其元胞自动机模拟

提出了一种在反应沉淀过程中过饱和成核结晶加上Ostwald熟化作用的Liesegang环带形成机理 ,并按此机理建立了一种二维混合随机元胞自动机模型 ,制定了成核、结晶、溶解、分解、迁移、反应和扩散等的演化规则 ,并在计算机上对该Liesegang环带的元胞自动机模型进行了动态模拟     

基于元胞自动机的列车站前折返仿真模型

在对城市轨道交通中列车站前折返过程准确描述的基础上，建立了2种典型站前折返模式的元胞自动机模型，即站前单渡线折返仿真模型和站前双渡线折返仿真模型。为准确模拟列车的折返过程，模型设定了列车在不同轨道部分的元胞更新规则，在此基础上还添加了线路标识、方向标识和信号标识等来实现列车的换道、转向和防止进路冲突等问题。采用计算机编程，运用已建立的模型来模拟列车的运行过程，对列车运行过程的速度一位置图和时间一位置图的分析发现，模型的模拟结果与实际列车的折返过程完全相同，同时采用仿真方法计算的折返站折返能力与传统图解法计算的结果误差仅为2．4％，由此说明所建立的模型能够准确模拟实际列车的站前折返过程，可以应用于对列车的折返仿真。