Necessary and sufficient conditions for collision-free hashing

This paper determines an exact relationship between collision-free hash functions and other cryptographic primitives. Namely, it introduces a new concept, the pseudopermutation, and shows that the existence of collision-free hash functions is equivalent to the existence of claw-free pairs of pseudopermutations. We also give a simple construction of collision-free hash functions from everywhere-defined claw-free (pseudo-) permutations.Supported by an NSF Graduate Fellowship, NSF Grant 92-12184, AFOSR F49620-92-J-0125, and DARPA N00014-92-J-1799.     

Necessary and sufficient conditions for system similarity

New conditions for the system similarity of two system matrices in state-space form are presented. It is shown that these conditions can be expressed very simply in terms of the mode-controllability and mode-observability matrices of the systems concerned.     

Necessary conditions for absolute stability of nonlinear regulators

Simple necessary conditions involving the fundamental frequency-domain concept of transmission zeros are established for the absolute stability of nonlinear regulators. These results significantly complement the sufficient conditions provided by the Popov criterion in the analysis and synthesis of nonlinear control systems.     

Even-weighted codes for error detection

For a binary symmetric channel, a code V with only evenweighted words performs better than a corresponding code V? with both odd- and even-weighted words, from the point of the probability of undetected errors. We derive an estimate of the improvement in the performance.     

Efficient codes for single error detection and partial single error correction

Coding schemes are proposed for error control in systems where individual blocks of information are organised as two sub-blocks each requiring a different degree of error control. The codes described guarantee single error correction in one sub-block and provide single error detection and partial single error correction in the other. The main advantages are savings in redundancy and ability to use standard encoding/decoding procedures.     

Necessary conditions for optimum distributed sensor detectors underthe Neyman-Pearson criterion

Distributed signal detection schemes that are optimum under the Neyman-Pearson criterion continue to be of interest. The functional forms of these schemes can be difficult to specify, especially for cases with dependent observations from sensor to sensor. For cases with dependent observations from sensor to sensor, the optimum sensor test statistics are generally not the likelihood ratios of the sensor observations. Equations expressing the forms of the optimum sensor test statistics in terms of the other optimum test statistics and the optimum fusion rule are given. Detailed proofs of these results are given in this correspondence and have not been given previously. In some communication, radar, and sonar system problems the amplitude of the received signal may be unknown, but the signal may be known to be weak. Equations expressing the forms of the optimum sensor test statistics for such cases are given. These expressions have already been shown to be useful for interpreting and finding optimum distributed detection schemes, but detailed proofs of the type given here have not yet been given     

Necessary conditions for stabilisation and pole placement with output feedback

For linear multivariable systems, simple necessary conditions are given for the existence of constant stabilising and arbitrary pole-placing output feedback matrices. These conditions can easily be tested by evaluating an indexed output controllability matrix.     

Compaction-based concurrent error detection for digital circuits

We present a non-intrusive concurrent error detection (CED) method for combinational and sequential digital circuits. We analyze the optimal solution model and point out the limitations that prevent logic synthesis from yielding a minimal-cost monolithic CED implementation. We then propose a compaction-based alternative approach for restricted error models. The proposed method alleviates these limitations by decomposing the CED functionality into: compaction of the circuit outputs, prediction of the compacted responses, and comparison. We model the fault-free and erroneous responses as connected vertices in a graph and perform graph coloring in order to derive the compacted responses. The proposed method is first discussed within the context of combinational circuits, with zero detection latency, and subsequently extended to Finite State Machines (FSMs), with a constant detection latency of one clock cycle. Experimental results demonstrate that the proposed method achieves significant hardware reduction over duplication-based CED, while detecting all possible errors.     

On testing for improper error detection codes

A family of tests for improper codes is given. These tests can be used in cases where the complete weight distribution of the code is unknown. It was found that knowledge of the number of minimum weight codewords can be used to greatly increase the effectiveness of the asymptotic Varshamov-Gilbert test. Further improvement is possible as more is known about the number of other weight codewords     

Necessary conditions for stability and a simple stabilisationscheme for two-dimensional digital filters

The letter describes a set of necessary stability conditions which form the basis of a new fast testing procedure, followed by a simple stabilisation scheme. An example is given     

Optimal codes for minimax criterion on error detection

Nonlinear quadratic codes that are optimal for the minimax error detection are presented. Characteristic functions for these codes are asymptotically bent. For a given block size n and the number of codewords |C|, these codes minimize max Q(e), e≠0, where Q(e) is the conditional error-masking probability, given the error pattern e. The codewords are blocks of n symbols from GF(q). Encoding and decoding procedures for the codes are described     

基于AVS视频解码的错误检测方法

针对AVS视频传输过程中出现的码流错误,提出了一种基于健康度记录与双阈值判别的错误检测方法。在解码过程中,对每一个宏块都用邻域相关性来计算其健康度,并记录健康度较差的宏块号,健康度判别中使用双阈值,出现首个大于较大的阈值一的宏块后则改为使用较小的阈值二进行判别;若出现语法/语义错误,则再利用宏块内部相关性对出错宏块号进行微调,最后把所有被记录下的宏块都标记为出错。实验结果表明,该错误检测方法能较准确定位出错宏块位置,特别是对于出错宏块不连续和相关性增幅不够大的错误类型,与传统的逐个向前检测的方法相比,能有更好的检测效果。     

An IDDQ sensor for concurrent timing error detection

Error control is a major concern in many computer systems, particularly those deployed in critical applications. Experience shows that most malfunctions during system operation are caused by transient faults, which often manifest themselves as abnormal signal delays that may result in violations of circuit element timing constraints. We present a novel complementary metal-oxide-semiconductor-based concurrent error-detection circuit that allows a flip-flop (or other timing-sensitive circuit element) to sense and signal when its data has been potentially corrupted by a setup or hold timing violation. Our circuit employs on-chip quiescent supply current evaluation to determine when the input changes in relation to a clock edge. Current through the detection circuit should be negligible while the input is stable. If the input changes too close to the clock time, the resulting switching transient current in the detection circuit exceeds a reference threshold at the time of the clock transition, and an error is flagged. We have designed, fabricated, and evaluated a test chip that shows that such an approach can be used to detect setup and hold time violations effectively in clocked circuit elements     

The MMD codes are proper for error detection

The undetected error probability of a linear code used to detect errors on a symmetric channel is a function of the symbol error probability /spl epsi/ of the channel and involves the weight distribution of the code. The code is proper, if the undetected error probability increases monotonously in /spl epsi/. Proper codes are generally considered to perform well in error detection. We show in this correspondence that maximum minimum distance (MMD) codes are proper.     

Necessary and sufficient conditions for controllability of multivariable systems incorporating integral feedback

Necessary and sufficient conditions are derived for controllability of linear multivariable time-invariant systems incorporating feedback of the integrals of some or all of the state variables. The results extend recent work by Porter and Power on establishing necessary conditions for controllability of such systems.     

A strategy for designing error detection schemes for general datanetworks

The author presents a five-step methodology that provides insight into the order in which errors should be considered when designing an error detection scheme, which types of error detection mechanisms are most effective, and which layer should be responsible for detecting a given type of error     

Linear block codes for error detection (Corresp.)

The probability of undetected error of linear block codes for use on a binary symmetric channel is investigated. Upper hounds are derived. Several classes of linear block codes are proved to have good error-detecting capability.     

Arithmetic coding-based continuous error detection for efficientARQ-based image transmission

Block cyclic redundancy check (CRC) codes are typically used to perform error detection in automatic repeat request (ARQ) protocols for data communications. Although efficient, CRCs can detect errors only after an entire block of data has been received and processed. We propose a new “continuous” error detection scheme using arithmetic coding that provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. This method of error detection, first introduced by Bell, Witten, and Cleary (1990), is achieved through the use of an arithmetic codec, and has the attractive feature that it can be combined physically with arithmetic source coding, which is widely used in state of-the-art image coders. We analytically optimize the tradeoff between added redundancy and error-detection time, achieving significant gains in bit rate throughput over conventional ARQ schemes for binary symmetric channel models for all probabilities of error     

Continuous error detection (CED) for reliable communication

Block cyclic redundancy check (CRC) codes represent a popular and powerful class of error detection techniques used almost exclusively in modern data communication systems. Though efficient, CRCs can detect errors only after an entire block of data has been received and processed. In this work, we exploit the “continuous” nature of error detection that results from using arithmetic codes for error detection, which provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. We demonstrate how this continuous error detection framework improves the overall performance of communication systems, and show how considerable performance gains can be attained. We focus on several important scenarios: 1) automatic repeat request (ARQ) based transmission; 2) forward error correction (FEC frameworks based on (serially) concatenated coding systems involving an inner error-correction code and an outer error-detection code; and 3) reduced state sequence estimation (RSSE) for channels with memory. We demonstrate that the proposed CED framework improves the throughput of ARQ systems by up to 15% and reduces the computational/storage complexity of FEC and RSSE by a factor of two in the comparisons that we make against state-of-the-art systems