Huffman algebras for independent random variables

Based on a rearrangement inequality by Hardy, Littlewood, and Polya, we define two-operator algebras for independent random variables. These algebras are called Huffman algebras since the Huffman algorithm on these algebras produces an optimal binary tree that minimizes the weighted lengths of leaves. Many examples of such algebras are given. For the case with random weights of the leaves, we prove the optimality of the tree constructed by the power-of-2 rule, i.e., the Huffman algorithm assuming identical weights, when the weights of the leaves are independent and identically distributed.     

Locality-preserving hash functions for general purpose parallel computation

Consider the problem of efficiently simulating the shared-memory parallel random access machine (PRAM) model on massively parallel architectures with physically distributed memory. To prevent network congestion and memory bank contention, it may be advantageous to hash the shared memory address space. The decision on whether or not to use hashing depends on (1) the communication latency in the network and (2) the locality of memory accesses in the algorithm.We relate this decision directly to algorithmic issues by studying the complexity of hashing in the Block PRAM model of Aggarwal, Chandra, and Snir, a shared-memory model of parallel computation which accounts for communication locality. For this model, we exhibit a universal family of hash functions having optimal locality. The complexity of applying these hash functions to the shared address space of the Block PRAM (i.e., by permuting data elements) is asymptotically equivalent to the complexity of performing a square matrix transpose, and this result is best possible for all pairwise independent universal hash families. These complexity bounds provide theoretical evidence that hashing and randomized routing need not destroy communication locality, addressing an open question of Valiant.This work was started when the author was a student at Oxford University, supported by a National Science Foundation Graduate Fellowship and a Rhodes Scholarship. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author and do not necessarily reflect the views of the National Science Foundation or the Rhodes Trust.     

广义de Bruijn多计算机互连网络

（ｄ，ｍ）ｄｅ Ｂｒｕｉｊｎ多计算机系统互连网络限制网络的规模必须为ｄ＾ｍ。本文把（ｄ，ｍ）ｄｅ Ｂｒｕｉｊｎ网络推广到了任意顶点情形，提出了广义ｄｅ Ｂｒｕｉｊｎ网络，研究了广义ｄｅ Ｂｒｕｉｊｎ网络的自路由性质，设计了路由算法，研究了广义ｄｅ Ｂｒｕｉｊｎ网络顶点度的性质和容错特性。     

A design and analysis of objective function-based unsupervised neural networks for fuzzy clustering

Fuzzy clustering has played an important role in solving many problems. In this paper, we design an unsupervised neural network model based on a fuzzy objective function, called OFUNN. The learning rule for the OFUNN model is a result of the formal derivation by the gradient descent method of a fuzzy objective function. The performance of the cluster analysis algorithm is often evaluated by counting the number of crisp clustering errors. However, the number of clustering errors alone is not a reliable and consistent measure for the performance of clustering, especially in the case of input data with fuzzy boundaries. We introduce two measures to evaluate the performance of the fuzzy clustering algorithm. The clustering results on three data sets, Iris data and two artificial data sets, are analyzed using the proposed measures. They show that OFUNN is very competitive in terms of speed and accuracy compared to the fuzzy c-means algorithm.     

Error handling in a parallel LR substring parser

Parallel parsing is currently receiving attention but there is little discussion about the adaptation of sequential error handling techniques to these parallel algorithms. We describe a noncorrecting error handler implemented with a parallel LR substring parser. The parser used is a parallel version of Cormack's LR substring parser. The applicability of noncorrecting error handling for parallel parsing is discussed. The error information provided for a standard set of 118 erroneous Pascal programs is analysed. The programs are run on the sequential LR substring parser.     

Steady-state weights solution to affine projection algorithm

A new expression of the weights update equation for the affine projection algorithm (APA) is proposed that improves the convergence rate of an adaptive filter,particularly for highly colored input sign...     

基于Matlab的线性规划问题求解

线性规划是运筹学中研究较早、发展较快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种重要的数学方法.文章首先介绍了线性规划的基本概念及标准形式,着重讨论了线性规划问题的三种常用解法:单纯形法、直接搜索法以及遗传算法,最后在Matlab R2009a环境下进行了仿真.通过结果可以看出,用Matlab求解线性规划问题,可以避免手工的烦琐计算,大大地提高工作效率和结果的准确性.     

一种降低电离层梯度影响的Hatch滤波算法

目前,地基增强系统（Ground-Based Augment System,GBAS）中的主要问题是：尽管使用载波平滑降低了伪距噪,利用差分技术消除了用户和基准站间的大部分共同误差,从而减少了差分改正值中的误差。但是电离层时间梯度和空间梯度于这两个过程中产生了额外的误差,阻碍了差分改正值质量的进一步提高。基于对电离层时间和空间梯度引起的额外误差的分析,并考虑平滑伪距噪声,文章提出了一种新的Hatch滤波方法,该滤波器的时间常数是随卫星仰角、电离层时间和空间梯度以及用户与参考站之间的距离而实时变化的。该方法降低了差分改正值误差,提高了定位精度。并且通过差分定位仿真并对比传统的单频Hatch滤波方法,发现使用该方法后,减小了差分校正值的误差。     

VxWorks下PCI9054显卡图形开发库的实现

介绍了一种基于VxWorks操作系统的PCI9054显卡的图形开发库,实现了基本绘图功能,汉字和字符的显示功能,以及贴图存图的功能,满足综合显示的需求。     

磁场信号检测误差分析及补偿算法

针对载体自身磁场特性及三轴磁传感器误差特性建立了地磁导航干扰误差补偿模型,通过对模型进行简化变形,利用系统辨识的最小二乘估计算法(LS)求取误差特性参数.数据分析表明:该方法简单易实现,简化了复杂的求解过程,基本达到了误差补偿的要求.