Geometric computations by broadcasting automata

In this paper we introduce and apply a novel approach for self-organisation, partitioning and pattern formation on the non-oriented grid environment. The method is based on the generation of nodal patterns in the environment via sequences of discrete waves. The power of the primitives is illustrated by giving solutions to two geometric problems using the broadcast automata model arranged in an integer grid (a square lattice) formation. In this model automata cannot directly observe their neighbours?? state and can only communicate with neighbouring automata through the non-oriented broadcast of messages from a finite alphabet. In particular we show linear time algorithms for the problem of finding the centre of a digital disk starting from any point on the border of the disc and the problem of electing a set of automata that form the inscribed square of such a digital disk. Possible generalizations and applications of techniques based on nodal patterns and the construction of different discrete wave interference pictures are discussed in the conclusion.     

Large neighbourhood search algorithms for the founder sequence reconstruction problem

The reconstruction of founder genetic sequences of a population is a relevant issue in evolutionary biology research. The problem consists in finding a biologically plausible set of genetic sequences (founders), which can be recombined to obtain the genetic sequences of the individuals of a given population. The reconstruction of these sequences can be modelled as a combinatorial optimisation problem in which one has to find a set of genetic sequences such that the individuals of the population under study can be obtained by recombining founder sequences minimising the number of recombinations. This problem is called the founder sequence reconstruction problem. Solving this problem can contribute to research in understanding the origins of specific genotypic traits. In this paper, we present large neighbourhood search algorithms to tackle this problem. The proposed algorithms combine a stochastic local search with a branch-and-bound algorithm devoted to neighbourhood exploration. The developed algorithms are thoroughly evaluated on three different benchmark sets and they establish the new state of the art for realistic problem instances.     

Characterization of best Chebychev approximation using the frequency response of IIR digital filters with convex stability

This paper deals with the application of Chebychevʼs approximation theory to IIR digital filter frequency response (FR) approximation. It explores the properties of the frequency response of IIR digital filters as a nonlinear complex approximating function; IIR digital filter frequency response is used to approximate a prescribed magnitude and phase responses. The approximation problem is closely related to optimization. If the set of approximating functions is non-convex, the optimization problem is difficult and may converge to a local minimum. The main results presented in the paper are proposing a convex stability domain by introducing a condition termed “sign condition” and characterization of the best approximation by the Global Kolmogorovʼs Criterion (GKC). The Global Kolmogorovʼs Criteria is shown to be also a necessary condition for the approximation problem. Finally, it is proved that the best approximation is a global minimum. The sign condition can be incorporated as a constraint in an optimization algorithm.     

Reconstruction of a digital circle

Since digitization always causes some loss of information, reconstruction of the original figure from a given digitization is a challenging task. Reconstruction of digital circles has already been addressed in the literature. However, an in-depth analysis of an OBQ image of a continuous circle as well as a solution to its domain construction problem is still lacking. In this paper a detailed analysis of digital circles has been carried out. A modified I_R method is formulated to numerically compute the domain of each digital quarter circle for a given radius. Several properties of the OBQ image of a circle reveal that in many cases it is possible to split a digital circle into four digital quarter circles, such that the domains of the individual quarter circles can be combined to obtain the domain of the full circle. Moreover, the domain of a quarter circle is geometrically characterized.     

基于数字签名的DNA篡改提示方法研究

为有效发现DNA数据是否被恶意篡改,保证研究者所使用的DNA数据是真实可靠的,即未经过篡改的,本文提出一种基于数字签名的DNA数据篡改提示方法,用向原有信息中加入数字签名的方法来解决该问题.设计了一整套加入、检测以及滤除签名的方法.该方法将数字签名嵌入DNA序列,在使用前通过校验数字签名来发现DNA是否篡改,以便给出篡改提示.实验表明,该方法可以有效发现篡改者对序列的恶意篡改,而且经添加签名后的序列与原始序列有一定的相似性,不易引起篡改者的注意.     

Constructing suffix tree for gigabyte sequences with megabyte memory

Mammalian genomes are typically 3 Gbps (gibabase pairs) in size. The largest public database NCBI (National Center for Biotechnology Information (http://www.ncbi.nlm.nih.gov)) of DNA contains more than 20 Gbps. Suffix trees are widely acknowledged as a data structure to support exact/approximate sequence matching queries as well as repetitive structure finding efficiently when they can reside in main memory. But, it has been shown as difficult to handle long DNA sequences using suffix trees due to the so-called memory bottleneck problems. The most space efficient main-memory suffix tree construction algorithm takes nine hours and 45 GB memory space to index the human genome [S. Kurtz (1999)]. We show that suffix trees for long DNA sequences can be efficiently constructed on disk using small bounded main memory space and, therefore, all existing algorithms based on suffix trees can be used to handle long DNA sequences that cannot be held in main memory. We adopt a two-phase strategy to construct a suffix tree on disk: 1) to construct a diskbase suffix-tree without suffix links and 2) rebuild suffix links upon the suffix-tree being constructed on disk, if needed. We propose a new disk-based suffix tree construction algorithm, called DynaCluster, which shows O(nlogn) experimental behavior regarding CPU cost and linearity for I/O cost. DynaCluster needs 16 MB main memory only to construct more than 200 Mbps DNA sequences and significantly outperforms the existing disk-based suffix-tree construction algorithms using prepartitioning techniques in terms of both construction cost and query processing cost. We conducted extensive performance studies and report our findings in this paper.     

Multiple prefetch adaptive disk caching

A new disk caching algorithm is presented that uses an adaptive prefetching scheme to reduce the average service time for disk references. Unlike schemes which simply prefetch the next sector or group of sectors, this method maintains information about the order of past disk accesses which is used to accurately predict future access sequences. The range of parameters of this scheme is explored, and its performance is evaluated through trace-driven simulation, using traces obtained from three different UNIX minicomputers. Unlike disk trace data previously described in the literature, the traces used include time stamps for each reference. With this timing information-essential for evaluating any prefetching scheme-it is shown that a cache with the adaptive prefetching mechanism can reduce the average time to service a disk request by a factor of up to three, relative to an identical disk cache without prefetching     

基于OpenFlight的数字地形处理软件包设计及应用

数字地形技术的发展为雷达系统仿真领域提供了一个新的发展方向。该文基于OpenFlight格式地形数据库，分析了地形数据库的组成要素、建模方法及数据结构。详细论述了数字地形信息的提取、多叉树的遍历及地形数据坐标转换的实现方法，并针对雷达模拟器设计中对地形数据访问复杂的难题，提出将通用三角面地形数据转化为网格化数据的新思想。运用面向对象设计思想，开发了数字地形处理软件包。详细探讨了软件包在雷达模拟器中的应用，并进行了仿真试验，给出了仿真图例。实践证明数字地形处理软件开发包在雷达模拟器设计中实现了高逼真的雷达仿真图像，为雷达模拟器的设计提供了有效的工具，具有较强的工程实用价值。     

Determining Digital Circularity Using Integer Intervals

Digital circularity is a well-researched topic for its real-world practicality to circularity measure, estimation of discrete curvature, circular arc segmentation, etc. The proposed work reveals a novel technique to determine whether a digital curve segment is digitally circular using the correspondence of its constituent runs with the square numbers in integer intervals. The notion of radii nesting is used to successively analyze these runs of digital points. Two algorithms have been proposed along with their demonstrations and detailed analysis, and a simple-yet-effective solution has been provided to expedite them using infimum circle and supremum circles that bound the initial range of radii. We have also shown how the proposed technique can be used for segmentation of an arbitrary digital curve segment into a sequence of circular arcs. Experimental results have been given to demonstrate the efficiency and elegance of the proposed technique.     

Pruning with improving sequences in lazy functional programs

This paper presents a library based on improving sequences and demonstrates that they are effective for pruning unnecessary computations while retaining program clarity. An improving sequence is a monotonic sequence of approximation values of a final value that are improved gradually according to some ordering relation. A computation using improving sequences proceeds by demanding for the next approximation value. If an approximation value in the middle of the improving sequence has sufficient information to yield the result of some part of the program, the computations that produce the remaining values can be pruned. By combining suitable improving sequences and primitive functions defined for the sequences, we can write efficient programs in the same form as simple and naive programs. We give examples that show the effectiveness of improving sequences and show by program calculation that a simple minimax-like program using improving sequences implements a well-known branch-and-bound searching algorithm.     

On particle path generation based on quadrilinear interpolation andBernstein-Bezier polynomials

Particle path computation in unsteady 3D vector fields given in discrete, structured form (i.e., as a hexahedral curvilinear grid) requires the local approximation of the vector field and the path. Quadrilinear interpolation and Bernstein-Bezier polynomials are used for the local vector field and path approximation. The next point in a sequence of points on a particle path is computed using this local approximation. Bernstein-Bezier polynomials are primarily used in geometric modeling, and their properties allow direct computation of points on a particle path     

数字直扩接收机中同步环路设计与仿真

同步是扩频通信系统中的一个重要问题。该文详细介绍了直接序列扩频（DSSS）通信系统中，数字科斯塔斯（Costas）环、数字延迟锁定环（DLL）的工作原理和环路中二阶环路滤波器的设计方法，并根据该原理提出了一种新的码环实现方案。使用Matlab对数字直扩接收机进行了仿真。不同环路滤波器参数下环路捕获性能的仿真结果及系统解调误码率证明了该环路滤波器在Costas环和DLL环中的正确性和实用性。其较好地解决了直扩系统中载波和伪码精确同步的问题。该文所设计的数字直扩接收机可有效地应用于CDMA及GPS等系统之中。     

数字语音信号的非均匀采样的实现

该文主要叙述数字语音信号的基于FFT的非均匀采样的技术实现问题,涉及WAV文件格式、分段、对其进行非均匀降速重采样频率的选择原则及生成和语音信号重构,并对实际的WAV格式的数字语音文件用VC++6.0编写的程序实现了基于FFT的重采样;分析方法、实现程序不仅对WAV格式的数字语音文件有效,而且也适用于其它格式的数字语音文件和非语音信号的非均匀采样的实现。     

基于云边协同的数字电网通信信息网络安全策略研究

本研究旨在探讨基于云边协同的数字电网通信信息网络安全策略。首先,通过大量文献分析、调查问卷等方法,确定了数字电网通信信息网络面临的主要安全威胁和保障需求。其次,在此基础上提出以云边协同为核心的网络安全保障策略,包括资源共享、实时监测、数据加密等多层次的解决方案。接着,我们从安全性、可靠性和易用性三个角度对该策略进行评价,并通过仿真实验验证了其有效性和可行性。最后,结论表明,基于云边协同的数字电网通信信息网络安全策略可以有效地提高数字电网的安全性和稳定性,具有很强的实际应用价值。     

基于DNA计算的RNA序列多点“突变”与首段碱基的数字编码及其运算法则

RNA序列的高维空间二进制编码有以下优点:除可以对RNA序列的碱基结构、功能基团、碱基互补、氢键强弱等性质进行编码之外,还可方便的进行数学与逻辑运算。该文研究了RNA序列高维空间数字编码的更一般、更深刻的运算法则:(1)进一步研究RNA序列高维空间的表观维数NV,数值维数NX以及差异维数Nd,具体刻给出了当Nd=0,1,2,2n或2n+1(n=0,1,2,…)时,RNA序列的首段碱基及其数值取值范围。(2)推导出RNA序列多点“突变”(单核苷酸多态性SPN)的运算法则,将以前的结果推广到一般情形,深刻探讨了RNA序列之汉明距离、汉明值的变化及其数值变化情况。(3)利用RNA序列的定值部Xi和定位部Wi及其计算公式,从新的角度导出RNA重复序列的编码法则和运算法则,进而统一了以前的结果。     

Color Sequence Preserving Decolorization

Many visualization techniques use images containing meaningful color sequences. If such images are converted to grayscale, the sequence is often distorted, compromising the information in the image. We preserve the significance of a color sequence during decolorization by mapping the colors from a source image to a grid in the CIELAB color space. We then identify the most significant hues, and thin the corresponding cells of the grid to approximate a curve in the color space, eliminating outliers using a weighted Laplacian eigenmap. This curve is then mapped to a monotonic sequence of gray levels. The saturation values of the resulting image are combined with the original intensity channels to restore details such as text. Our approach can also be used to recolor images containing color sequences, for instance for viewers with color‐deficient vision, or to interpolate between two images that use the same geometry and color sequence to present different data.     

一种电子式互感器校验系统的研究

电子式互感器校验关系到电网安全经济运行以及电能计量、贸易结算的公平性。本文简要介绍了电子式互感器的分类以及常用校验方法,在LabView软件环境下,采用零相位数字滤波器滤除白噪声,运用汉宁卷积窗的绝对值数字校验方法对两路数字信号实现准同步基波参数分数分析,实现了一种电子式互感器虚拟仪器校验方法。试验数据表明,该方式可用于检定0.2S级互感器,具有实际的应用价值。     

光盘机的DSP数字伺服系统设计

该文研究了可重写光盘机ＤＳＰ数字伺服控制的问题，给出了数字控制系统的硬件构成。详细讨论了重要的设计问题－－几个主要器件如ＤＳＰ、Ａ／Ｄ、Ｄ／Ａ性能参数的选择，给出了具体的设计参数。讨论了数字控制器实现的一些具体问题，并给出了一个所实现的包含ＤＳＰ数字控制器的伺服回路的开环频率特性曲线。     

Combinatorial Construction of Seamless Parameter Domains

The problem of seamless parametrization of surfaces is of interest in the context of structured quadrilateral mesh generation and spline-based surface approximation. It has been tackled by a variety of approaches, commonly relying on continuous numerical optimization to ultimately obtain suitable parameter domains. We present a general combinatorial seamless parameter domain construction, free from the potential numerical issues inherent to continuous optimization techniques in practice. The domains are constructed as abstract polygonal complexes which can be embedded in a discrete planar grid space, as unions of unit squares. We ensure that the domain structure matches any prescribed parametrization singularities (cones) and satisfies seamlessness conditions. Surfaces of arbitrary genus are supported. Once a domain suitable for a given surface is constructed, a seamless and locally injective parametrization over this domain can be obtained using existing planar disk mapping techniques, making recourse to Tutte's classical embedding theorem.     

数字图书馆网格互操作框架

随着全球数字图书馆(DLs)的迅猛发展,互操作成为亟待解决的重要问题。目前DLs互操作的主要解决方案包括:分布式搜索、元数据收集、中间件技术等,在实现大规模的数字图书馆互操作方面都存在一定的局限性。文章通过对已有方案的分析和对比,指出各自的优势和不足,并在OAI-PMH框架的基础上,结合先进的网格技术,提出全新的数字图书馆互操作框架—数字图书馆网格DLGrid,为解决大规模数字图书馆的互操作提供一种新途径。