一类弹性布尔函数的谱值分布

Sarka等人在文献[1]中给出了弹性布尔函数的一种构造方法,利用该方法可以构造出非线性度、弹性阶和代数次数等密码学性质均较理想的奇数元弹性布尔函数。对其构造得到的弹性布尔函数的谱值分布进行了研究,分析了由该方法所构造得到的5元1阶和7元1阶弹性布尔函数的谱值,给出了这两类弹性布尔函数的谱值分布情形,并给出了相应谱值点的计数结果。     

Linear time Euclidean distance transform algorithms

Two linear time (and hence asymptotically optimal) algorithms for computing the Euclidean distance transform of a two-dimensional binary image are presented. The algorithms are based on the construction and regular sampling of the Voronoi diagram whose sites consist of the unit (feature) pixels in the image. The first algorithm, which is of primarily theoretical interest, constructs the complete Voronoi diagram. The second, more practical, algorithm constructs the Voronoi diagram where it intersects the horizontal lines passing through the image pixel centers. Extensions to higher dimensional images and to other distance functions are also discussed     

基于Census变换的自适应权值Hamming距离立体匹配算法

传统的Census+Hamming距离立体匹配算法往往由于将邻域像素等同对待,从而缺少足够的匹配信息,造成较高的误匹配率。对此提出了一种自适用加权的Hamming距离算法,通过引入邻域像素空间距离,使在距离测算时将邻域像素分等级计算,丰富了匹配图像的信息。并且使用梯度图像像素之间的距离作为聚合代价计算的权值,实验证明其对于噪声有一定的抗干扰性,并且能够很好地反映纹理等信息,同时引入稀疏聚合窗口来减少算法的复杂度。最后进行亚像素插值增大匹配的正确性。通过对比试验证明,此算法不仅能够提高匹配的准确性和抗干扰性,还能减少算法的复杂度,适用于实时的立体匹配。     

面向密码算法的非线性布尔函数实现技术研究

为了提升密码算法中非线性布尔函数实现效率,设计了串行与电路和以查找表为基础的并行化低次布尔函数实现架构,分别实现高次与项和低次与项。分析了不同并行化查找表实现密码算法中低次布尔函数的效率。结果表明,结合香农分解定理提出的并行化查找表架构处理性能可以达到1.02 GHz,不仅能够灵活适配密码算法中的非线性布尔函数,而且能够节省资源占用。     

Generation of sign Walsh spectra from disjoint cubes of Boolean functions

A new algorithm is given that converts a reduced representation of Boolean functions in the form of disjoint cubes to sign Walsh spectra. Since the known algorithms that generate sign Walsh spectra always start from the truth table of Boolean functions, the method presented computes faster with a smaller computer memory. The method is especially efficient for such Boolean functions that are described by only few disjoint cubes.     

Scalable and efficient parallel algorithms for Euclidean distance transform on the LARPBS model

A parallel algorithm for Euclidean distance transform (EDT) on linear array with reconfigurable pipeline bus system (LARPBS) is presented. For an image with n/spl times/n pixels, the algorithm can complete EDT transform in O(n log n/c(n) log d(n)) time using n/spl middot/d(n)/spl middot/c(n) processors, where c(n) and d(n) are parameters satisfying 1/spl les/c(n)/spl les/n, and 1相似文献   

New algorithms for fixed-length approximate string matching and approximate circular string matching under the Hamming distance

This paper proposes new algorithms for fixed-length approximate string matching and approximate circular string matching under the Hamming distance. Fixed-length approximate string matching and approximate circular string matching are special cases of approximate string matching and have numerous direct applications in bioinformatics and text searching. Firstly, a counter-vector-mismatches (CVM) algorithm is proposed to solve fixed-length approximate string matching with k-mismatches. The development of CVM algorithm is based on the parallel summation of counters located in the same machine word. Secondly, a parallel counter-vector-mismatches (PCVM) algorithm is proposed to accelerate CVM algorithm in parallel. The PCVM algorithm is integrated into two-level parallelisms that exploit not only word-level parallelism but also data parallelism via parallel environments such as multi-core processors and graphics processing units (GPUs). In the particular case of adopting GPUs, a shared-mem parallel counter-vector-mismatches (PCVMsmem) scheme can be implemented from PCVM algorithm. The PCVMsmem scheme can exploit the memory model of GPUs to optimize performance of PCVM algorithm. Finally, this paper shows several methods to adopt CVM and PCVM algorithms in case the input pattern is in circular structure. In the experiments with real DNA packages, our proposed algorithms and scheme work greatly faster than previous bit-vector-mismatches and parallel bit-vector-mismatches algorithms.     

Parallel algorithms for evaluation of directional Boolean derivatives of multivalued logic functions

Conclusion Processing of logical data always requires special software and hardware tools. This is attributable to the specific features of the mathematical apparatus of the algebra of logical functions. Organization of parallel logical computation on the basis of the symbolic mathematical apparatus leads to complex logic programs. A different approach is proposed in this article. It is based on the matrix apparatus. Its use enables us to synthesize parallel and structurally homogeneous algorithms for the evaluation of directional logical derivatives of multivalued logic functions and implement their evaluation using standard matrixalgebra software or homogeneous computing systems. Homogeneous computing systems substantially accelerate the processing speed and can be built using VLSI technology. The operation graphs of the proposed algorithms have the same configuration as the graphs of fast algorithms used in digital signal processing. This result makes it possible to use well-tried standard procedures of digital signal processing, which involve mapping of algorithms into homogeneous computing structures and hardware-software architectures. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 41–59, November–December, 1996.     

New sequential exact Euclidean distance transform algorithms based on convex analysis

We present several sequential exact Euclidean distance transform algorithms. The algorithms are based on fundamental transforms of convex analysis: The Legendre Conjugate or Legendre–Fenchel transform, and the Moreau envelope or Moreau-Yosida approximate. They combine the separability of the Euclidean distance with convex properties to achieve an optimal linear-time complexity.We compare them with a Parabolic Envelope distance transform, and provide several extensions. All the algorithms presented perform equally well in higher dimensions. They can naturally handle grayscale images, and their principles are generic enough to apply to other transforms.     

Polynomial transformation of Boolean functions: Analysis of computational algorithms

This paper considers some realization features of polynomial factoring algorithms for n-argument Boolean functions, as well as analyzes their computational complexity and necessary hardware resources.     

基于Walsh变换的数字水印算法*

经对目前数字水印变换域算法的研究,发现常用的变换大多都是正交变换（如DCT和DWT等）。通过对Walsh正交函数系的研究,获得了与之对应的性能优良的正交变换,提出一种新颖的、鲁棒的Walsh域盲水印算法。实验表明,该算法计算简单,且具有良好的不可见性,并且在抵抗噪声和JPEG压缩攻击等方面具有较强的鲁棒性。     

DNA-based algorithms for learning Boolean formulae

We apply a DNA-based massively parallel exhaustive search to solving the computational learning problems of DNF (disjunctive normal form) Boolean formulae. Learning DNF formulae from examples is one of the most important open problems in computational learning theory and the problem of learning 3-term DNF formulae is known as intractable if RP NP. We propose new methods to encode any k-term DNF formula to a DNA strand, evaluate the encoded DNF formula for a truth-value assignment by using hybridization and primer extension with DNA polymerase, and find a consistent DNF formula with the given examples. By employing these methods, we show that the class of k-term DNF formulae (for any constant k) and the class of general DNF formulae are efficiently learnable on DNA computer.Second, in order for the DNA-based learning algorithm to be robust for errors in the data, we implement the weighted majority algorithm on DNA computers, called DNA-based majority algorithm via amplification (DNAMA), which take a strategy of ``amplifying' the consistent (correct) DNA strands. We show a theoretical analysis for the mistake bound of the DNA-based majority algorithm via amplification, and imply that the amplification to ``double the volumes' of the correct DNA strands in the test tube works well.     

基于汉明距离的无线传感器网络密钥预分配方案*

无线传感器网络自身的特征,如网络规模庞大,动态的拓扑结构,有限的计算、通信和存储能力等,使得传统的密钥分配和管理机制无法直接应用。基于汉明距离提出了一种新的适用于无线传感器网络的密钥预分配方案。该方案将对称密钥系统和非对称密钥系统结合起来,并借助汉明距离的概念在无线传感器网络中实现了密钥的分配和管理。与随机密钥预分配方案相比,本方案在健壮性和安全性方面具有一定的优势,其计算和存储开销也不大,具有一定的实用性。     

Partitioning 1-variable Boolean functions for various classification of n-variable Boolean functions

This paper addresses all possible equivalence classes of 1-variable Boolean functions and from these classes using recursion and Cartesian product of sets, 15 different ways of classifications of n-variable Boolean functions are obtained. The properties with regard to the size and the number of classes for these 15 different ways are also elaborated.     

Complexity hierarchies for Boolean functions

Summary Circuit size and depth are two important complexity measures for a Boolean function. Uniform hierarchies are shown to exist with respect to each of these measures.     

基于汉明距离的DNA编码约束研究

DNA计算是将现实问题进行编码映射到DNA分子上,通过生物实验产生出代表问题的解的DNA分子,最后通过检测技术提取出该DNA分子。高质量的DNA编码可以尽可能避免或减少计算过程中出现的错误,并使检测阶段易于提取出代表问题的解的DNA分子。对DNA编码约束进行了研究,分析了基于汉明距离的编码约束可以有效降低DNA分子间相似程度,减少DNA计算过程中DNA分子间的相互干扰,从而提高DNA计算的有效性和可靠性。还证明了基于汉明距离的编码约束存在等价的序列组合,降低了编码计算的复杂度。     

小汉明重量的布尔函数代数厚度上界研究

根据布尔函数代数厚度的定义,总结变量不交布尔函数的组合函数代数厚度与各布尔函数代数厚度的联系,指出代数厚度上界证明的局限性,得到布尔函数与其补布尔函数代数厚度的限制关系式。利用该关系式得到汉明重量为2和3的布尔函数及其补布尔函数的代数厚度上界,计算满足一定代数厚度的布尔函数的概率值。