Although computers are beneficial to individuals and society, frequently users encounter frustrating experiences when using computers. This study represents an attempt to measure, in 111 participants, the frequency, the cause, and the level of severity of frustrating experiences. The data show that frustrating experiences happen on a frequent basis. The applications in which the frustrating experiences happened most frequently were Web browsing, e-mail, and word processing. The most-cited causes of frustrating experiences were error messages, dropped network connections, long download times, and hard-to-find features. The time lost due to frustrating experiences ranged from 47% to 53% of time spent on a computer, depending on the location and study method. After extreme cases were discarded, the time lost was still above 38%. These disturbing results should be a basis for future study.

MOTIVATION: High accuracy of data always governs the large-scale gene discovery projects. The data should not only be trustworthy but should be correctly annotated for various features it contains. Sequence errors are inherent in single-pass sequences such as ESTs obtained from automated sequencing. These errors further complicate the automated identification of EST-related sequencing. A tool is required to prepare the data prior to advanced annotation processing and submission to public databases. RESULTS: This paper describes ESTprep, a program designed to preprocess expressed sequence tag (EST) sequences. It identifies the location of features present in ESTs and allows the sequence to pass only if it meets various quality criteria. Use of ESTprep has resulted in substantial improvement in accurate EST feature identification and fidelity of results submitted to GenBank. AVAILABILITY: The program is freely available for download from http://genome.uiowa.edu/pubsoft/software.html

MOTIVATION: In gene discovery projects based on EST sequencing, effective post-sequencing identification methods are important in determining tissue sources of ESTs within pooled cDNA libraries. In the past, such identification efforts have been characterized by higher than necessary failure rates due to the presence of errors within the subsequence containing the oligo tag intended to define the tissue source for each EST. RESULTS: A large-scale EST-based gene discovery program at The University of Iowa has led to the creation of a unique software method named UITagCreator usable in the creation of large sets of synthetic tissue identification tags. The identification tags provide error detection and correction capability and, in conjunction with automated annotation software, result in a substantial improvement in the accurate identification of the tissue source in the presence of sequencing and base-calling errors. These identification rates are favorable, relative to past paradigms. AVAILABILITY: The UITagCreator source code and installation instructions, along with detection software usable in concert with created tag sets, is freely available at http://genome.uiowa.edu/pubsoft/software.html CONTACT: [email protected]

Genetic search with a decision level chromosome is used to search efficiently for Golomb (1982) arrays. A Golomb array A is a binary array with three values for its discrete autocorrelation function; M, the number of ones in A for no offset, 1 when there is partial overlap, and 0 otherwise. In one dimension, A is known as a Golomb ruler. The method yields improvement because the genetic search considers only feasible solutions in the most likely portion of the search space. Each chromosome bit represents a decision to place a one in an iterative construction. The representation includes all possible arrays. Since the chromosome bits represent binary decisions in the search space, genetic operations (such as crossover and mutation) always result in feasible descendent chromosomes. Experimental results include comparison to previously known search methods and several new arrays. These results indicate that the proposed search is significantly more efficient than prior methods.

A correspondence between two-dimensional Golomb rectangles and one-dimensional Golomb rulers is given. Results are translated from rulers to rectangles. The extension of these results to an arbitrary number of dimensions is given. A new bound is developed on the number of ones in a Golomb array of any dimension. Some new optimum Golomb squares, rectangles, and higher dimensional arrays are given.

Built-in-self-test (BIST) schemes provide on-chip circuitry to generate test vectors and to analyze output responses so that testing can be performed without using expensive external testers. The authors present a unified approach to test pattern generation and output compaction. ISCAS benchmark circuits are used to show the applicability of the proposed method.>

A new error model that considers both space and time correlation is proposed. An exact closed form expression for aliasing probability is obtained for an arbitrary test length for a large class of signature registers. The authors identify the minimum register structure that falls into this class.>

A unified scheme for test-pattern generation and output compaction using circuit-specific information is presented. It is shown that partial control over test-pattern sequence can give zero aliasing in single-output circuits and reduced aliasing in multiple-output circuits. The exact aliasing probability is obtained for multiple-output circuits under the independent bit error model for any test length. The aliasing probability for multiple-output circuits of this scheme is independent of the feedback polynomial of the multiple-input shift register (MISR). This method reduces aliasing considerably without increasing the length of the MISR by having a simple quotient detector. The approach is applied to benchmark circuits to show the applicability of the scheme to a given combinational circuit.>

A data compression technique for ROM based built-in test generators of combinational circuits is described. Some of the test pattern bits are computed using the reduced data stored in the ROM combined with the address bits accessing the ROM. Some experimental results are presented for ISCAS benchmark circuits and random data.>

The aliasing probability in single and multiple input linear automata signature registers (LASRs: linear feedback shift registers (LFSRs) and linear cellular automata) has been widely studied under the independent bit error model. Aliasing in a class of multiple-input LASRs (MILASRs) under the q-ary symmetric error model is examined. By modeling the signature analyzer as a two state Markov process, it is shown that the closed form expression previously derived for aliasing probability for multiple-input LFSRs with primitive polynomials holds for a far more general class of linear automata signature analyzers, including all multiple-input LFSRs. An easily verifiable criterion is given to determine whether a MILASR falls into this category. It is shown that for q-ary symmetric errors, the circuit complexity and the propagation delay can be minimized by using a set of m single bit LFSRs.>

A computationally efficient Markov state space model is developed for determining the aliasing probability of a linear feedback shift register when used for test data reduction. The model studied can be used to test data errors which have a constant of probability of error, correlated or repeated use errors, or time varying error probability. Based on a number of simulations of various error models and feedback polynomials it appears that a primitive polynomial, with about half its terms nonzero, has the best dynamic performance in most cases.>

A procedure for multiple-output combinational circuits is presented that yields the optimum space compressor while using counting for time compression. The procedure is intended for the built-in selftest environment where output response data compression is appropriate. Optimum is defined as the minimum number of error patterns missed by the combination of space and time compression. The procedure uses the fast Walsh transform to determine the number of errors missed by each linear combination for all possible space-compression combinations. A illustrative example is included to show the effectiveness of the algorithm. A comparison between cases with and without space compression is included.>

A commonly used organization for built-in self-test of VLSI (very large-scale integration) circuits uses complete or pseudorandom test input generators followed by output data reduction. Two compression techniques which have been used are polynomial division (signature) and ones counting (syndrome). The simultaneous use of both of these approaches in parallel is investigated. Analytic and enumerative results indicate that the number of error patterns which are missed by both methods together is nearly the theoretical minimum. The conclusion extends to signature compression combined with any other counter-based compression method such as the use of Walsh spectral coefficients. Some suggestions for CAD (computer-aided design) implementations of test design are given based on these results.>

In the testing of logic circuits, two proposed data-compression methods use the number of ones (syndrome) and the number of sequence changes (transition count). An enumeration N(m, k, t) of the number of length-m binary sequences having syndrome value k and transition count t is developed. Examination of this result reveals that the parallel compression of these two methods has small overlap in error masking. An asymptotic expression for N(m, k, t) is developed.>

A unified treatment of the various techniques to reduce the output data from a unit under test is given. The characteristics of time compression schemes with respect to errors detected are developed. The use of two or more of these methods together is considered. Methods to design efficient test compression structures for built-in-tests are proposed. The feasibility of the proposed approach is demonstrated by simulation results.

The main advantages of space compression are the reduction in the number of pins monitored by the tester and the minimization of the memory space required for reference signatures. Compression, however, may reduce fault coverage. We investigate output data modification with the objective to improve the efficiency of syndrome testing and to reduce by a significant amount the error probability. It was found that this approach to output modification depends strongly upon the functions tested and may result in a complicated testing circuit, in some cases. A design algorithm is proposed which combines space compression and output modification. This algorithm will often minimize the disadvantages of both approaches while maintaining error coverage information.

A new test data reduction technique called accumulator compression testng (ACT) is proposed. ACT is an extension of syndrome testing. It is shown that the enumeration of errors missed by ACT for a unit under test is equivalent to the number of restricted partitions of a number. Asymptotic results are obtained for independent and dependent error modes. Comparison is made between signature analysis (SA) and ACT. Theoretical results indicate that with ACT a better control over fault coverage can be obtained than with SA. Experimental results are supportive of this indication. Built-in self test for processor environments may be feasible with ACT. However, for general VLSI circuits the complexity of ACT may be a problem as an adder is necessary.

When an error occurs in the encoded bit stream produced by a variable length code, the decoder may lose synchronization. A state model for synchronization recovery is developed, and a method for determining the expected span of source symbols lost is presented. The performance of various codes with respect to error recovery is discussed. Two examples are given where equivalent optimal codes have a marked difference in their error recovery characteristics. Some open problems are indicated.

There are a number of communications problems involving two-dimensional arrays with constrained correlation functions. Golomb's two classes of radar arrays and sonar arrays are examined. Improved bounds, optimal cases, and computational procedures are reported.

The optimum Golomb ruler1 with 13 marks has been found. This shortest ruler as well as another new ruler is reported.

A minimization approach is presented for a modulo-2 expansion of a switching function. This method uses mixed polarity representation for the variables A local optimization procedure is presented which requires modest computation and is easily expanded. The procedure applied to the 32 DES select functions of six variables is reported.

A Gray sequence is a counter sequence where the Hamming distance between successive states is one. A construction for any fixed odd distance between successive states is given based on error-correcting codes. Such sequences could be used in testing and fault diagnosis when sequencing through all possible input combinations. Sequences with the maximum possible difference between successive states, alternatelynandn-1, are given. A characterization of such maximal change sequences is given. The most nearly uniform even difference sequences are described. The distribution of bit changes or transition counts for individual variables for a counting sequence is considered.

A Golomb ruler has m division marks with the spacings between marks positive integers such that the set of (m2 − m)/2 measurements which can be made between the marks are distinct. A fast search procedure is outlined for determining the shortest ruler. For 12 marks the shortest ruler is 85 units.

Codes for a ternary channel having a character adjacency restriction and an asymmetric error behavior are considered. Allowable sequences and their characteristics are presented. Error-detection and error-correction codes are investigated, and a single error-correcting code is given as an example.

This correspondence considers three-level AND/OR gate realizations for T or more of N symmetric functions and gives a design procedure. The procedure can be used to design relatively large networks. The three-level realizations require substantially fewer test patterns for fault detection, gates, and gate inputs than the minimum two-level network. For example, the minimum two-level network for the 3 or more out of 12 functions requires 286 test patterns, 67 gates, and 726 gate inputs while the three-level realization presented requires 27 test patterns, 25 gates, and 96 gate inputs.

Combinational networks with no internal fan-out are considered from the point of view of testing for multiple faults. Several different approaches utilizing added inputs and observable outputs are considered and the tradeoffs are discussed.

We give a decoding algorithm for iterated codes that can correct up to the number of errors guaranteed by the product minimum distance, rather than about half that number when the iterated codes are decoded independently. This result is achieved by adapting Forney's generalized minimum distance decoding for use with iterated codes. We derive results on the simultaneous burst- and random-error-correction capability of iterated codes that improve considerably on known results.

Two convolutional-code construction schemes that utilize block codes are given. In the first method the generators of a self-orthogonal convolutional code (SOCC) are expanded. The generators of a block code whose block length is longer than that of the SOCC code replace the nonzero blocks of the convolutional code. The zero blocks are extended to the longer block length. There results a convolutional code whose blocks are self-orthogonal and which has a lower transmission rate. In the second scheme the parity constraints of an SOCC are expanded. The parity constraints of a block code replace some of the individual nonzero elements of the SOCC parity-check matrix, so that the convolutional code rate is greater than the block code rate. The resulting codes retain the SOCC advantages of simple implementation and limited error propagation. Both the encoding and the decoding can be based on the underlying block code. If a block code is majority decodable, then the resulting "hybrid" codes are majority decodable. Optimum majority-decodable block codes with up to five information bits per block are given, and from these codes several majority-decodable convolutional codes that are "optimum" with respect to the proposed construction are obtained.

A bound and construction are presented for high-rate burst-error-correcting recurrent codes. The bound is an upper bound on the block length in terms of the total redundancy used in decoding, the redundancy per block, and the burst length. The construction uses a block-code parity-check matrix as the first block of the recurrent code parity-check matrix. For a block code it is typical to find that only a portion of the redundancy need be used to detect a burst. Any block code for which this is true can be used in the construction. The recurrent code is then related as follows to the block code from which it is constructed. 1) The recurrent code block length is the same as the block-code block length. 2) The total redundancy used in decoding the recurrent code is the same as the block-code redundancy per block. 3) The recurrent code redundancy per block is the same as the block-code redundancy required for burst detection only. 4) The recurrent code is of higher rate than the block code. 5) The recurrent code requires a guard space between bursts but otherwise corrects the same bursts as the block code. It is shown that, when certain well-known cyclic codes are used in the construction, the resulting recurrent codes are close to the upper bound.

This paper describes a sequential suboptimal test selection procedure for a combinational logic circuit. The goal is package level diagnosis assuming a single permanent fault and multiple outputs. The method extends to multiple permanent faults and/or a single output since the starting point is a fault table of test inputs as columns, faults as rows, and resulting output as the entry.

The structure of a uniform convolutional code, i.e., a code whose average distance is equal to its minimum distance, is examined, and results in a parity equation lattice. From this lattice, punctured uniform codes, i.e., uniform codes with parity bits deleted, are constructed, which can be threshold decoded and have limited error propagation. An "optimum" deletion sequence is provided. Some of the punctured uniform codes are optimal from a minimum-distance view point.

The error-propagation effect in decoding convolutional codes is a result of the internal feedback in the usual decoding method, feedback decoding (FD). As a measure of this effect, the propagation lengthLof a system is defined as the maximum span of decoding errors following a decoding error when all succeding parity checks are satisfied. A relationship betweenL, the parity check matrix, and the decoding algorithm is developed. A decoding method having no internal feedback, definite decoding (DD), is formalized. It is shown that a code using FD with limitedLexists if and only if that same code can be decoded using DD. When using DD a smaller class of errors is corrected. The self-orthogonal codes are shown to be decodable using FD withLsmall. The minimum possible value ofLwhen using bounded distance decoding is given for some of these codes. Codes are given which minimize the spacing between single correctable errors using DD. These values of spacing are compared with those for similar (known) codes which use FD, and with the theoretical minimum spacing.

It is shown that an improved Gilbert bound for convolutional codes can be obtained for the class of codes derivable from a good short code. Numerical results for the binary case illustrate the improvement.

A class of binary recurrent codes for correcting independent errors is given which has guaranteed error-limiting properties. These codes can be simply decoded using threshold decoding, and will recover from any decoding error caused by either an uncorrectable transmission error or a temporary malfunction of the encoder or decoder. A number of such codes are given along with a synthesis procedure. The results of a computer simulation are given which indicate that these codes perform better in some situations than other codes using threshold decoding.

An upper bound on the minimum distance of a linear convolutional code is given which reduces to the Plotkin bound for the block code case. It is shown that most linear convolutional codes have a minimum distance strictly less than their average distance. A table of the bound for several rates is given for binary codes as well as a comparison with the known optimum values for codes of block length2.