RS类纠删码的译码方法

RS(Reed-Solomon)码可以根据应用环境构造出任意容错能力的码字,有很好的灵活性,且使用RS纠删码作为容错方法的存储系统能达到理论最优的存储效率.但是,与异或(exclusive-OR,XOR)类纠删码相比,RS类纠删码译码计算的时间开销过大,这又很大程度上阻碍了它在分布式存储系统中的使用.针对这一问题,提出了一类RS纠删码的译码方法,该方法完全抛弃了当前大多RS类纠删码译码方法中普遍使用的矩阵求逆运算,仅使用计算复杂度更小的加法和乘法,通过构造译码变换矩阵并在此矩阵上执行相应的简单的矩阵变换,能够直接得出失效码元由有效码元组成的线性组合关系,从而降低译码计算复杂度.最后,通过理论证明了该方法的正确性,并且针对每种不同大小的文件,进行3种不同大小文件块的划分,将划分得到的数据块进行实验,实验结果表明:在不同的文件分块大小情况下,该新译码方法较其他方法的译码时间开销更低.     

A modified teaching–learning-based optimisation algorithm for bi-objective re-entrant hybrid flowshop scheduling

In this paper, a modified teaching–learning-based optimisation (mTLBO) algorithm is proposed to solve the re-entrant hybrid flowshop scheduling problem (RHFSP) with the makespan and the total tardiness criteria. Based on the simple job-based representation, a novel decoding method named equivalent due date-based permutation schedule is proposed to transfer an individual to a feasible schedule. At each generation, a number of superior individuals are selected as the teachers by the Pareto-based ranking phase. To enhance the exploitation ability in the promising area, the insertion-based local search is embedded in the search framework as the training phase for the TLBO. Due to the characteristics of the permutation-based discrete optimisation, the linear order crossover operator and the swap operator are adopted to imitate the interactions among the individuals in both the teaching phase and the learning phase. To store the non-dominated solutions explored during the search process, an external archive is used and updated when necessary. The influence of the parameter setting on the mTLBO in solving the RHFSP is investigated, and numerical tests with some benchmarking instances are carried out. The comparative results show that the proposed mTLBO outperforms the existing algorithms significantly.     

A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes

We tighten a key estimate, which dictates the computational complexity of Guruswami-Sudan algorithm, on the lower bound of the degrees of freedom, and then propose a modified decoding algorithm for Reed-Solomon codes beyond half the minimum distance. The computational complexity of the modified algorithm is lower than the Guruswami-Sudan algorithm for the medium to high rate Reed-Solomon codes, and has the same asymptotic complexity as the algorithm proposed by Wu. Besides we also claim that our modified algorithm outperforms Wu's algorithm to some extent.     

High speed decoding of the binary (47, 24, 11) quadratic residue code

An efficient table lookup decoding algorithm (TLDA) is presented to decode up to five possible errors in a binary systematic (47, 24, 11) quadratic residue (QR) code. The main idea of the TLDA is based on the weight of syndrome, the syndrome decoder together with a reduced-size lookup table (RSLT), and the shift-search method given by Reed et al. Thus, the size of the lookup table and computational complexity in a finite field can be significantly reduced. The memory size of the proposed condensed lookup table (CLT) consists of only 36.6 Kbytes and is only about 0.24% of the full lookup table (FLT) and 3.2% of the lookup up table given by Chen et al., respectively. These facts lead to significant reduction of computational time and the decoding complexity. A simulation result shows that the decoding speed of the proposed TLDA is much faster than all existing decoding algorithms. Moreover, it can be extended to decode all QR codes, including the class of the cyclic codes when the code length is moderate. The CLT makes this new decoding algorithm suitable for hardware or firmware implementations.     

Embedding HMMs-based models in a Euclidean space: the topological hidden Markov models

Current extensions of hidden Markov models such as structural, hierarchical, coupled, and others have the power to classify complex and highly organized patterns. However, one of their major limitations is the inability to cope with topology: When applied to a visible observation (VO) sequence, the traditional HMM-based techniques have difficulty predicting the n-dimensional shape formed by the symbols of the VO sequence. To fulfill this need, we propose a novel paradigm named “topological hidden Markov models” (THMMs) that classifies VO sequences by embedding the nodes of an HMM state transition graph in a Euclidean space. This is achieved by modeling the noise embedded in the shape generated by the VO sequence. We cover the first and second level topological HMMs. We describe five basic problems that are assigned to a second level topological hidden Markov model: (1) sequence probability evaluation, (2) statistical decoding, (3) structural decoding, (4) topological decoding, and (5) learning. To show the significance of this research, we have applied the concept of THMMs to: (i) predict the ASCII class assigned to a handwritten numeral, and (ii) map protein primary structures to their 3D folds. The results show that the second level THMMs outperform the SHMMs and the multi-class SVM classifiers significantly.     

Bandwidth-efficient cooperative MIMO relaying schemes

Coded cooperative MIMO relaying schemes in which all successfully decoded signals from multiple sources are simultaneously forwarded by a multi-antenna relay to a common multi-antenna destination to increase bandwidth efficiency are proposed in this paper. These schemes facilitate the various retransmission strategies at relay and single-user and multi-user iterative decoding techniques at destination, suitable for trade-offs between performance, latency, and complexity. When channel state information (CSI) is available, pre-coding and power allocation at the relay can be exploited to enhance the information transmission reliability over the relay-destination channel, thus improving the overall system performance. Simulation result shows their superiority to direct transmission under the same transmit power and bandwidth efficiency.     

Viterbi和DTW算法的关系分析——在非特定人手语识别中的应用

在经典的模式识别理论中,Viterbi算法代表了统计概率的模式匹配算法,而DTW算法代表了模版匹配的模式匹配算法,它们之间是否存在关系至今尚无定论.为了找到这两种算法之间的关系,在类别隶属度是广义概率的假设前提下,应用模糊数学的理论在Viterbi算法与DTW算法之间建立起联系.首先,提出了利用模糊数学的贴近度把DTW算法的距离向Viterbi算法的概率转化的通用贴近度表达式,并对通用贴近度表达式给出了理论上的证明.其次,应用DTW的通用贴近度表达式重估HMM参数,建立DTW算法与Viterbi算法之间的模糊贴近度关系,并为此提出了δ-ε算法,得到基于数据帧的类似于HMM的参数重估形式.然后,为了确保建立DTW算法与Viterbi算法之间的模糊贴近度关系的正确性,以定理的形式给出了相应的证明.再次,通过设定的DTW贴近度表达式对HMM参数重估的过程中,发现了DTW贴近度的重估参数与HMM重估参数之间存在着的模糊关系,以定理的形式对这种模糊关系加以证明.最后,依据上述定理提出了Dtw-ViterbiⅠ,Ⅱ,Ⅲ算法,以定理的形式对Dtw-ViterbiⅠ,Ⅱ,Ⅲ算法的正确性加以证明,并将对Dtw-ViterbiⅠ...     

基于信息向量机的神经活动分类和译码研究

利用信息向量机(IVM)算法对来自脑皮层的少量运动神经元激发率进行分类,识别出神经状态,用该神经状态指导神经元激发率的译码。将IVM算法与支持向量机算法、相关向量机算法进行实验比较,结果证明,IVM算法的神经活动分类和译码性能最优,运行时间最短。     

基于CUDA平台的规则LDPC码的译码实现研究

低密度奇偶校验(LDPC)码性能优越,允许全并行高速译码,已经在个人数字设备、移动无线通信等领域显示出了很大的应用价值,极可能取代Turbo码成为第四代移动通信的首选编码方案。NVIDIA公司的CUDA是一种新的用于GPU通用计算的软硬件架构。基于CUDA平台程序员可以写出C风格的代码来启动大量的GPU线程并行工作。基于CUDA平台提出和研究一种AWGN信道下的规则LDPC码的译码实现方案。仿真实验对LDPC码译码的CPU实现和CUDA实现的性能作了详细比较。研究表明CUDA能够带来明显的性能提升。     

符号M阵列面结构光多分辨解码方法研究

研究了符号M阵列面结构光图像的多分辨解码方法,结合基于形心特征的标准符号的分类和识别,着重提出了多分辨解码过程中未识别区域的提取方法,并结合实际问题提出了图像标记和符号识别的特殊处理方法,如分割符号间隔、填充十字型区域等,进而实现照度不均面结构光图像解码率最大化的目的.同时该解码方法也大大提高了照度不均模式图像解码的执行效率.