Error detection in arithmetic coding with artificial markers

Error detection in arithmetic code is usually achieved by inserting markers in the source sequence during encoding. Transmission errors can then be detected in the decoding process if the inserted markers do not appear at the expected positions. Unlike the existing approaches in which the marker symbol is selected from the set of source symbols, we propose that the marker be created artificially so as not to affect the original distribution of the source symbols. Our scheme is proved to possess a better compression ratio than existing marker approaches at the same error misdetection probability. The relationship between codeword length expansion and error misdetection probability within a coded block is well formulated, which makes it easy to adapt to channels with different bit error rates. Simulation results show that, for adaptive arithmetic coding implemented using finite-precision computation, the distribution of error detection delay has a peak at a value slightly larger than the length of the decoding register. With a sufficiently long register, our approach can detect most error patterns in long source sequences at a high probability.     

On the complexity of simple arithmetic expressions

Let $\text{E}$ be the set of all simple arithmetic expressions of the form E(x) = xT_l…T_k where x is a nonnegative integer variable and each T_i is a multiplication or integer division by a positive integer constant. We investigate the complexity of the inequivalence and the bounded inequivalence problems for expressions in $\text{E}$. (The bounded inequivalence problem is the problem of deciding for arbitrary expressions E₁(x) and E₂(x) and a positive integer l whether or not E₁(x) ≠ E₂(x) for some nonnegative integer x<l. If l = ∞, i.e., there is no upper bound on x, the problem becomes the inequivalence problem.) We show that the inequivalence problem (or equivalently, the equivalence problem) for a large subclass of $\text{E}$ is decidable in polynomial time. Whether or not the problem is decidable in polynomial time for the full class $\text{E}$ remains open. We also show that the bounded inequivalence problem is NP-complete even if the divisors are restricted to be equal to 2. This last result can be used to sharpen some known NP-completeness results in the literature. Note that if division is rational division, all problems are trivially decidable in polynomial time.     

On parsing arithmetic expressions in a multiprocessing environment

Summary Some decomposition of the parsing of the sentences of context-free grammars into sequences of independant sub-tasks is proposed. An example of grammar is presented, for which this decomposition provides an efficient parser for a multiprocessing environment. The average speed-up resulting from the parallelization of the parser of an arithmetic infix grammar is evaluated by means of probabilistic models and real world measurements.     

Least significant bit evaluation of arithmetic expressions in single-precision

Single-precision floatingpoint computations may yield an arbitrary false result due to cancellation and rounding errors. This is true even for very simple, structured arithmetic expressions such as Horner's scheme for polynomial evaluation. A simple procedure will be presented for fast calculation of the value of an arithmetic expression to least significant bit accuracy in single precision computation. For this purpose in addition to the floating-point arithmetic only a precise scalar product (cf. [2]) is required. If the initial floatingpoint approximation is not too bad, the computing time of the new algorithm is approximately the same as for usual floating-point computation. If not, the essential progress of the presented algorithm is that the inaccurate approximation is recognized and corrected. The algorithm achieves high accuracy, i.e. between the left and the right bound of the result there is at most one more floating-point number. A rigorous estimation of all rounding errors introduced by floating-point arithmetic is given for general triangular linear systems. The theorem is applied to the evaluation of arithmetic expressions.     

The number of registers required for evaluating arithmetic expressions

We study the number of registers required for evaluating arithmetic expressions. This parameter of binary trees appears in various computer science problems as well as in numerous natural sciences applications where it is known as the Strahler number.We give several enumeration results describing the distribution of the number of registers for trees of size n. The average number of registers has the asymptotic expansion log₄n + D(log₄n) + 0(1); here, function D is periodic of period one, and its Fourier expansion can be explicitly determined in terms of Riemann's zeta function and Euler's gamma function.     

A new parallel algorithm for parsing arithmetic infix expressions

A new parallel algorithm for transforming an arithmetic infix expression into a par se tree is presented. The technique is based on a result due to Fischer (1980) which enables the construction of the parse tree, by appropriately scanning the vector of precedence values associated with the elements of the expression. The algorithm presented here is suitable for execution on a shared memory model of an SIMD machine with no read/write conflicts permitted. It uses O(n) processors and has a time complexity of O(log²n) where n is the expression length. Parallel algorithms for generating code for an SIMD machine are also presented.     

Bounds on the parallel evaluation of arithmetic expressions using associativity and commutativity

Summary We show that any arithmetic expression with n operands and parentheses nested to depth d can be evaluated in at most 1+2d+ [log₂ n] steps, assuming that only associativity and commutativity are used to transform the expression. We also show that at most [n–2d/2] processors are needed to achieve this bound.This work was supported in part by NSF Grant GJ 36936. An earlier version of this paper was presented at the Seventh Annual Princeton Conference on Information Sciences and Systems, March 1973.     

Decomposition of arithmetic expressions to improve the behavior of interval iteration for nonlinear systems

Interval iteration can be used, in conjunction with other techniques, for rigorously bounding all solutions to a nonlinear system of equations within a given region, or for verifying approximate solutions. However, because of overestimation which occurs when the interval Jacobian matrix is accumulated and applied, straightforward linearization of the original nonlinear system sometimes leads to nonconvergent iteration. In this paper, we examine interval iterations based on an expanded system obtained from the intermediate quantities in the original system. In this system, there is no overestimation in entries of the interval Jacobi matrix, and nonlinearities can be taken into account to obtain sharp bounds. We present an example in detail, algorithms, and detailed experimental results obtained from applying our algorithms to the example.     

Error detection in precedence parsers

We consider methods by which a precedence matrix may be modified without severely degrading the error-detecting capability of a parser utilizing the matrix. Two different definitions of the same error detection capability are considered. The first, called exact equivalence, permits only useless parts of the precedence matrix to be modified. The second, called simply equivalence, allows the modified matrix to perform some reductions, but never to shift an input symbol, after the original has detected an error.We give necessary and sufficient conditions for a modified precedence parser to be equivalent or exactly equivalent to the canonical parser. We then consider the interesting case where the modification is caused by replacing the precedence matrix by linear precedence functions. A simple algorithm to find (if they exist) exactly equivalent linear precedence functions for a given precedence matrix is presented.The work by this author was partially supported by NSF grant GJ-465.     

动态话题追踪中的误报检测

针对动态话题追踪模型高误报率的现象,提出了动态追踪中的误报检测来判断追踪到的相关报道是否误报,进而降低动态模型的误报率。考虑到新报道是否和话题相关,除了依据两者的相似度外,还涉及时间距离、差值关系、分布关系、追踪到的报道和话题核心报道的相似度四方面内容,给出了误报检测因子计算式。实验采用TDT4测试集合和DET曲线进行评测,通过反复实验获得了误报检测因子δ的阈值,与基于信念网络的动态话题追踪模型相比,使用误报检测后模型的最优(Cdet)norm降低了5.032%。     

Error rates for multivariate outlier detection

Multivariate outlier identification requires the choice of reliable cut-off points for the robust distances that measure the discrepancy from the fit provided by high-breakdown estimators of location and scatter. Multiplicity issues affect the identification of the appropriate cut-off points. It is described how a careful choice of the error rate which is controlled during the outlier detection process can yield a good compromise between high power and low swamping, when alternatives to the Family Wise Error Rate are considered. Multivariate outlier detection rules based on the False Discovery Rate and the False Discovery Exceedance criteria are proposed. The properties of these rules are evaluated through simulation. The rules are then applied to real data examples. The conclusion is that the proposed approach provides a sensible strategy in many situations of practical interest.     

Error detection based on MB types

This paper proposes a method of error detection based on macroblock （MB） types for video transmission. For decoded inter MBs, the absolute values of received residues are accumulated. At the same time, the intra textural complexity of the current MB is estimated by that of the motion compensated reference block. We compare the inter residue with the intra textural complexity. If the inter residue is larger than the intra textural complexity by a predefined threshold, the MB is considered to be erroneous and errors are concealed. For decoded intra MBs, the connective smoothness of the current MB with neighboring MBs is tested to find erroneous MBs. Simulation results show that the new method can remove those seriously-corrupted MBs efficiently. Combined with error concealment, the new method improves the recovered quality at the decoder by about 0.5--1 dB.     

基于改进否定选择算法的网络入侵检测模型

为了解决网络入侵检测中如何迅速有效地检测出未知模式的入侵的问题,通过对人类免疫系统的基本原理的研究,提出了一种基于免疫原理的网络入侵检测新模型.该模型采用了改进的否定选择算法;根据否定选择理论,若与自我模式相匹配,则该模式不成为检测者,从而去掉它;否则,该模式成为一个检测者模式,并存入检测系统.实验结果表明,该模型可以准确地识别出未知入侵模式,有效地提高了系统的自适应性.     

Concurrent detection of additive overflow and arithmetic errors in residue codes

The problems of detecting overflow and single or multiple residue digit errors in Redundant Residue Numeber Systems are considered through an unified approach. It is shown that a single intermodular procedure allows concurrent detection of additive overflow and single residue digit error, even in the case where the error affects a number in overflow. In addition, it is shown that codes of adequate redundancy may allow detection of additive overflow and single bit error, provided that the residue digits are appropriately encoded. The discussion concerns both separate residue codes (i. e., codes being referred to as RRNS, where one or more redundant residues are added) and Product Codes.     

Error detection: a study in anaesthesia

Although error has been shown as the main cause of accidents in complex systems, little attention has been paid to error detection. However, reducing the consequences of error depends largely on error detection. The goal of this paper is to synthesize the existing scientific knowledge on error detection, mostly based on studies conducted in laboratory or self reporting and to further knowledge through the analysis of a corpus of cases collected in a complex system, anaesthesia. By doing this, this paper is better able to describe how this knowledge can be used to improve understanding of error detection modes. An anaesthesia accident reporting system developed and organized at two Belgian University Hospitals was used in order to collect information about the error detection patterns. Results show that detection of errors principally occurred through the standard check (routine monitoring of the environment). Significant relationships were found between the type of error and the error detection mode, and between the type of error and the training level of the anaesthetist who committed the error.     

Pain detection from facial expressions using domain adaptation technique

Pattern Analysis and Applications - Pain management is gaining the attention of clinical practitioners to relieve patients from pain in an effective manner. Pain management is primarily dependent...     

一种基于环形协作算法的分布式入侵检测模型

文章分析了当前流行的分布式入侵检测系统的特征以及协作方式，提出了一种基于逻辑环形协作算法的分布式入侵检测系统，以解决目前分布式入侵检测系统中各系统间协作效率低、检测响应慢的缺陷。     

基于事件约束的RFID复合事件误检处理

RFID数据采集的不可靠性降低了RFID应用中数据的准确性,并进一步对复合事件的检测产生影响。目前以RFID读数为粒度的清洗方法只能在一定程度上降低原始采集错误的发生频度,而复合事件检测过程又很少对其进行处理。为解决上述问题,将RFID数据从数据层抽象到逻辑语义层作为处理的粒度,提出了复合事件相互之间的约束规则,进行误检处理。通过挖掘已知复合事件之间的相关性对后续发生的事件进行误检判断,考虑了具体应用的逻辑语义,保证了RFID数据的可靠性。