We present a new class of linear error-correcting codes taking numerical data into codewords with numerical symbols. These codes can correct large random numerical errors added to codewords. The goal is for numerical data to be protected directly as numbers whether in storage or transmission. The coding structures are based on discrete Fourier transform (DFT) codes, defined by parity-check matrices where rows are consecutively indexed DFT vectors. The new tensor codes use the Kronecker product of two parity-check DFT matrices of shorter length codes. We construct all necessary processing matrices. Error correction methods involve two levels of syndromes and use several stochastic Berlekamp-Massey Algorithms (sBMA) to find big syndromes, locate and evaluate large errors. Decoding is done in two stages with stage one producing corrected syndromes. Stage two determines errors within a welldefined segment for the codewords. Tensor codes have simpler and more efficient decoding operations. The characteristics of the tensor codes are compared to standard DFT codes of equal length. The processing operations are significantly less for the tensor codes but the standard DFT codes sometimes have better correcting performance. Nevertheless, tensor product codes can have acceptable levels of correction, more efficiently.

Parity computations, checksums, over the input and output data of fast unitary transforms are compared, down to roundoff noise levels, to detect the effects from a single error on any one line between stages of the fast algorithm. Error spaces and their dual spaces guide the design process.

A class of complex-valued convolutional codes, wavelet codes, that encode numbers into numbers, is constructed by assigning consecutively indexed discrete Fourier transform (DFT) vectors to the parity-checking requirements. For a rate k/n code with constraint length m, the parameters must satisfy (m + 1)(n-k)<;n. The algebraic structures are very similar to the finite field convolutional codes but the decoding procedures operate over the complex numbers. These wavelet codes are effective against the impulse errors even when round off noise due to computational operations is allowed too. When the groups of impulsive errors are separated by the constraint length m, the errors can be corrected by extracting from the convolutional code's syndromes, new syndromes associated with a DFT block code inherent in the code's algebraic structure. A modified Berlekamp-Massey algorithm computes the error locations and the correcting values are determined by an inverse DFT operation. Systematic forms of these codes are developed by manipulating the original generating transfer function. Each systematic form is a subcode of the original wavelet code from which it was determined. Moreover, this form may be decoded by DFT code methods too. Extensive simulation results verify the power and viability of both forms of the codes and their decoding techniques.

Real number block codes derived from the discrete Fourier transform (DFT) are corrected by coupling a very modified Berlekamp-Massey (BM) algorithm with a syndrome extension process. The modified BM algorithm determines recursively the locations of any large errors whose number is within the capability of the DFT code. It evolves a connection polynomial which is changed when a discrepancy is above a threshold which is adjusted during each iteration. The large error locations are repositioned to exact location indices to combat low-level noise effects. The syndromes are extended using the refined connection polynomial taps. Alternately, enhanced extension recursions based on Kalman syndrome extensions are developed and simulated.

Real number block codes derived from the discrete Fourier transform (DFT) are corrected by coupling a very modified Berlekamp-Massey algorithm with a syndrome extension process. Enhanced extension recursions based on Kalman syndrome extensions are examined.

Real number data processing failures are detected by comparing parity values associated with a wavelet code which is most efficient in systematic form. Any rate k/n wavelet code, a form of real number convolutional code, is manipulated into a systematic wavelet subcode, with slightly reduced rate (k-1)/n, staying within the original algebraic structure.

Algorithm-based fault tolerance (ABFT) methods, which use real number parity values computed in two separate comparable ways to detect computer-induced errors in numerical processing operations, can employ wavelet codes for establishing the necessary redundancy. Wavelet codes, one form of real number convolutional codes, determine the required parity values in a continuous fashion and can be intertwined naturally with normal data processing. Such codes are the transform coefficients associated with an analysis uniform filter bank which employs downsampling, while parity-checking operations are performed by a syndrome synthesis filter bank that includes upsampling. The data processing operations are merged effectively with the parity generating function to provide one set of parity values. Good wavelet codes can be designed starting from standard convolutional codes over finite fields by relating the field elements with the integers in the real number space. ABFT techniques are most efficient when employing a systematic form and methods for developing systematic codes are detailed. Bounds on the ABFT overhead computations are given and ABFT protection methods for processing that contains feedback are outlined. Analyzing syndromes' variances guide the selection of thresholds for syndrome comparisons. Simulations demonstrate the detection and miss probabilities for some high-rate wavelet codes.

The JPEG image compression standard is very sensitive to errors. Even though it contains error resilience features, it cannot easily cope with induced errors from computer soft faults prevalent in remote-sensing applications. Hence, new fault tolerance detection methods are developed to sense the soft errors in major parts of the system while also protecting data across the boundaries where data flow from one subsystem to the other. The design goal is to guarantee no compressed or decompressed data contain computer-induced errors without detection. Detection methods are expressed at the algorithm level so that a wide range of hardware and software implementation techniques can be covered by the fault tolerance procedures while still maintaining the JPEG output format. The major subsystems to be addressed are the discrete cosine transform, quantizer, entropy coding, and packet assembly. Each error detection method is determined by the data representations within the subsystem or across the boundaries. They vary from real number parities in the DCT to bit-level residue codes in the quantizer, cyclic redundancy check parities for entropy coding, and packet assembly. The simulation results verify detection performances even across boundaries while also examining roundoff noise effects in detecting computer-induced errors in processing steps.

The JPEG 2000 image compression standard is designed for a broad range of data compression applications. The new standard is based on wavelet technology and layered coding in order to provide a rich feature compressed image stream. The implementations of the JPEG 2000 codec are susceptible to computer-induced soft errors. One situation requiring fault tolerance is remote-sensing satellites, where high energy particles and radiation produce single event upsets corrupting the highly susceptible data compression operations. This paper develops fault tolerance error-detecting capabilities for the major subsystems that constitute a JPEG 2000 standard. The nature of the subsystem dictates the realistic fault model where some parts have numerical error impacts whereas others are properly modeled using bit-level variables. The critical operations of subunits such as discrete wavelet transform (DWT) and quantization are protected against numerical errors. Concurrent error detection techniques are applied to accommodate the data type and numerical operations in each processing unit. On the other hand, the embedded block coding with optimal truncation (EBCOT) system and the bitstream formation unit are protected against soft-error effects using binary decision variables and cyclic redundancy check (CRC) parity values, respectively. The techniques achieve excellent error-detecting capability at only a slight increase in complexity. The design strategies have been tested using Matlab programs and simulation results are presented.

Wavelet transforms are the central to many applications in image processing and data compression. They have banks of multirate filters that are difficult to protect from computer-induced numerical errors. An efficient algorithm-based fault tolerance approach is proposed for detecting arithmetic errors in the output data. Concurrent weighted parity values are designed to detect the effects of a single numerical error within the transform structure. The parity calculations use weighted sums of data, where the input parity weighting is related to the weighting used on the output data. Each parity computation is properly viewed as an inner product between weighting values and the data motivating the use of dual space functionals related to the error gain matrices that describe error propagations to the output. The parity weighting values are defined by a combination of dual space functionals. An iterative procedure for evaluating the design of the parity weights has been incorporated in Matlab code.

Wavelet transforms, central to multiresolution signal analysis and important in the JPEG2000 image compression standard, are quite susceptible to computer-induced errors because of their pipelined structure and multirate processing requirements. Such errors emanate from computer hardware, software bugs, or radiation effects from the surrounding environment. Implementations use lifting schemes, which employ update and prediction estimation stages, and can spread a single numerical error caused by failures to many output transform coefficients without any features to warn data users. We propose an efficient method to detect the arithmetic errors using weighted sums of the wavelet coefficients at the output compared with an equivalent parity value derived from the input data. Two parity values may straddle a complete multistage transform or several values may be used, each pair covering a single stage. There is greater error-detecting capability at only a slight increase in complexity when parity pairs are interspersed between stages. With the parity weighting design scheme, a single error introduced at a lifting section can be detected. The parity computation operation is properly viewed as an inner product between weighting values and the data, motivating the use of dual space functionals related to the error gain matrices. The parity weighting values are generated by a combination of dual space functionals. An iterative procedure for evaluating the design of the parity weights has been incorporated in Matlab code and simulation results are presented.

Convolutional codes defined over the integers modulo a power of two, an arithmetic structure used for fixed-point arithmetic computations, employ well-known binary convolutional codes as their underlying generators. A recursive decoding technique that exploits binary expansion components of the code symbols uses any binary decoding algorithm valid for the underlying code.

Errors due to failures in data processing algorithms may be detected and even corrected by employing systematic convolutional codes defined over the fixed-point arithmetic structures supporting the computations. A new class of arithmetic convolutional codes using symbols from the finite ring associated with normal signed arithmetic is based on binary burst-correcting codes and a code's performance in the larger context exceeds that of an underlying basis code. When failures satisfy the usual guard band requirements for the binary code, error correction is possible using an iterative feedback decoder processing syndromes that are defined over the integers modulo a power of two. A class of high rate burst-correcting codes is discussed in more detail and their properties guarantee the detection of the onset of errors. The corrector also contains failure error-detecting capabilities.

Discrete fast unitary transform algorithms, of which the fast Fourier transform (FFT) and fast discrete Cosine transform (DCT) are practical examples, are highly susceptible to temporary calculation failures because of their interconnected computational flows. Many error detection techniques for FFT algorithms have been reported, but fault tolerance issues for other important transforms have not been addressed as vigorously. A general design and analysis approach for all fast unitary transforms is presented. It relies on fundamental linear algebra methods coupled with associated dual space representations that are natural descriptions of real parity values. Basic output error patterns from single computational errors are used to define an equal-sized group of dual space basis vectors on which practical parity weighting functions may be evaluated. An iterative design approach leads to complete single error detection capabilities. FFT and fast DCT examples are given.

Remote-sensing applications often calculate the discrete Fourier transform of sampled data and then compress and encode it for transmission to a destination. However, all these operations are executed on computing resources potentially affected by failures. Methods are presented for integrating various fault detection capabilities throughout the data flow path so that the momentary failure of any subsystem will not allow contaminated data to go undetected. New techniques for protecting complete source coding schemes are exemplified by examining a lossy compression system that truncates fast Fourier transform (FFT) coefficients to zero, then compresses the data further by using lossless arithmetic coding. Novel methods protect arithmetic coding computations by internal algorithm checks. The arithmetic encoding and decoding operations and the transmission path are further protected by inserting sparse parity symbols dictated by a high-rate convolutional symbol-based code. This powerful approach introduces limited redundancy at the beginning of the system but performs detection at later stages. While the parity symbols degrade efficiency slightly, the overall compression gain is significant because of the run-length coding. Well-known fault tolerance measures for FFT algorithms are extended to detect errors in the lossy truncation operations, maintaining end-to-end protection. Simulations verify that all single subsystem errors are detected and the overhead costs are reasonable.

Transform coefficients carry important data characteristics but can also be compressed significantly in many remote sensing applications. Failures in the several computing facilities that execute lossy compression algorithms and support the transmission of Fourier transform data can corrupt the values beyond recovery at the final destination. Various methods for including fault tolerance at the data processing level are exemplified by describing a protected system that computes the FFT, truncates small coefficients and compresses the remaining nonzero coefficients using lossless arithmetic coding. Algorithmic checks within the FFT and arithmetic encoding and decoding operations are augmented with additional features between and across several subsystems involved in compressing and transmitting the FFT data. End-to-end error detection is achieved in this manner.

New decoding procedures for real-number block codes which are constructed by imposing constraints in the discrete Fourier transform (DFT) domain are examined. The codewords are corrupted by small levels of roundoff noise and possibly occasionally by a few large excursions of random disturbances. The error-correcting procedure is separated into two parts, large activity detection followed by error value estimation, particularly the larger errors. The first part determines if large excursions are present, roughly identifying their locations, while the second part is a Wiener minimum mean-squared error estimation technique providing a stochastic correction to the corrupted components. The activity-detecting part determines locations for large increases in the Wiener estimator's gain. A computationally intensive Bayes hypothesis testing approach is shown to be very effective at locating large activity positions, but a more efficient modified Berlekamp-Massey (1969) algorithm is developed which leads to excellent mean-squared error performance. Extensive simulations demonstrate individual codeword corrective actions and compare the average mean-squared error performance between coded and unprotected data. The error level improvement ranges from three to four orders of magnitude.

New fault tolerance techniques are presented for protecting a lossless compression algorithm, arithmetic coding, whose recursive nature makes it vulnerable to temporary hardware failures. The fundamental arithmetic operations are protected by low-cost residue codes, employing fault tolerance in multiplications and additions. Additional fault-tolerant design techniques are developed to protect other critical steps such as normalization and rounding, bit stuffing and index selection. For example, the decoding step that selects the next symbol is checked by comparing local values with estimates already calculated in other parts of the decoding structure. Bit stuffing, a procedure for limiting very long carry propagations, is checked through modified residue values, whereas normalization and rounding after multiplication are protected by efficiently modifying the multiplier to produce residue segments.

A comparison-based decoder detects the arrival of a code word by comparing the received checkbits with the checkbits computed using the received data. Implementation issues underlying comparison-based decoders for systematic delay-insensitive (DI) or unordered codes is the subject of this paper. We show that if the decoder is to be implemented using asynchronous logic, i.e., if the gate and wire delays are arbitrary (unbounded but finite), then it is impossible to design a comparison-based decoder for any code that is more efficient than a dual-rail code. In other words, the encoded word must contain at least twice as many bits as the data. In addition, the codes should satisfy two other properties, called the initial condition and the all-zero lower triangle (AZLT) property, for the realization of a delay-insensitive comparison-based decoder. The paper shows that comparison-based decoders for codes that have the requisite level of redundancy and that satisfy the two properties can be implemented using asynchronous logic.

An extension to algorithm-based fault tolerance (ABFT) methodologies shows how parity values dictated by a real convolutional code can be employed by Kalman estimation techniques to perform real number correction for protecting linear processing systems. Intermittent failures appearing in the output samples are detected and corrected using only the syndromes normally generated in ABFT schemes. The algebraic structure of a real convolutional code provides separation needed by recursive Kalman state estimators to affect mean-square error correction. State and parity measurement equations model fault and computational noise in both the linear processing and parity generation subassemblies, and, in a departure from previous models, the noise sources are considered time-varying. The Kalman one-step estimator which makes decisions on all parity values up to the present point is determined, and it separates naturally into detection and correction operations permitting corrective action only when the detection levels exceed thresholds based on roundoff noise energy. The detector/corrector uses efficient multirate block processing techniques as determined by the real convolutional code. A smoothed fixed-lag Kalman estimator which uses parity values for a fixed amount beyond the point of interest is needed to complete the correction. It employs one-step estimator quantities and implementation simplifications are possible. Examples showing the correction behavior and mean-square error performance are presented, and the size of overhead calculations for detection and correction is estimated. A protected processing system is constructed by introducing additional subassemblies, mostly comparators, with the detection and correction parts already described. Under the usual assumptions of at most a single subassembly failure, no improperly detected or corrected data leave the overall protected configuration.

Convolutional codes which employ real-number symbols are difficult to decode because of the size of the alphabet and the numerical and roundoff noise inherent in arithmetic operations. Such codes find applications in both channel coding for communication systems and in fault-tolerance support for signal processing subsystems. A new method for error correction based on optimum mean-square recursive Kalman estimation techniques incorporates time-varying models for the system and associated disruptive noise sources. The underlying common model for communications and fault tolerance applications assumes the system operates nominally with low levels of channel or numerical and roundoff noise, occasionally experiencing temporarily larger noise statistics. A time-varying Kalman estimation structure which uses single-step and fixed-lag smoothing predictors can correct errors to within the nominal low-noise levels. Correction actions may be activated only when larger activity is detected, so methods for detecting possible error situations are developed. However, misdetection is not a serious problem because the Kalman correction methods only track significant errors in the data. Two activity detection techniques are examined; one is based on likelihood ratio tests while another uses clipped samples and binary pattern matching. Several examples showing simulated mean-square error performance and decoded waveforms from error injection experiments are presented.

Adaptive FIR filters are important in modern digital signal processing applications, and many situations require significant computational power attainable only through multi-processor configurations. Various block processing techniques have been proposed as viable alternatives to the sequential implementations to achieve the high throughput rate and reduce the effect of finite word length. While there are algorithm-based fault-tolerant techniques for protecting general digital signal processing systems against temporary/permanent failures, the specific features and requirements of the adaptive filtering systems have been largely ignored in the fault tolerance literature. By identifying common operations among different block adaptive filtering algorithms, however most operations of a particular algorithm can be protected with reasonably low-cost. We present a fine-grained approach, a highly efficient implementation of the well-known checksum encoding scheme, for protecting block adaptive filters. Through properly partitioning the input data, checksums for a parallel adaptive FIR filter can be calculated with reduced complexity. Computational and hardware overhead of the proposed scheme are analyzed, and shown to be proportional to the total number of partitioned submatrices.

High-level synthesis is becoming more important in practical design environments to meet new system requirements and, increasingly, fault tolerance is one especially because of high-speed and low power demands. This paper explores several basic aspects of low-cost fault tolerant synthesis for practical linear systems. It deals with practical design constraints that require basic operations to be only performed by a limited processing resources and do not normally assign each operation a separate processing resource. Two core issues, partitioning and allocation, for fault tolerant synthesis are examined. Results demonstrate a high-level abstraction and framework for fault tolerant synthesis which is almost totally independent of the physical hardware implementation. Issues in designing 1-fault detectable FFT system are considered in detail to illustrate the significance and effects of fault tolerant synthesis schemes. Our ultimate goal is to incorporate these techniques in future automated design tools so that fault tolerance features can be part of the design options.

A new technique for estimating a tight lower bound of the detection probabilities for single faults at any internal signal line in a combinational circuit for random testing is presented. This lower bound is calculated from the detection probabilities of all single faults at the primary input lines in a linear time. The technique relies on the relationship between the detection probabilities of dominating and dominated faults in the considered combinational circuit.>

A fault-detecting, bidirectional data interface between uncoded data from one component, such as a processor, and coded data in the rest of the system is described. This interface is capable of correcting a single multibit symbol error or detecting the occurrence of two such errors. The device uses a shortened Reed-Solomon code, and two practical symbol sizes are considered; nibble (4-bit) errors are protected by a (40, 32) binary equivalent shortened code, and byte errors are covered by a (80, 64) binary-sized code. The Reed-Solomon codes have maximum protection levels, even when shortened, and allow simplifying the design options. A dual orthogonal basis used for the symbols' representations provides significant hardware savings. The interface unit achieves internal fault detection by comparing regenerated parity values in a totally self-checking equality checker. A fault-tolerant ultrareliable memory module is proposed and evaluated. An illustrative design is realized using a single desktop programmable gate array.>

A method is presented for protecting the overall realization of digital filters implemented with very dense high-speed electronic devices against both hard and soft errors at the data sample level using the error-detecting properties of real convolutional codes. The normal filter system is surrounded with parallel parity channels defined by a real systematic rate k/n convolutional code. Erroneous behavior is detected by comparing externally the calculated and regenerated parity samples. Significant complexity reductions are possible by modifying the code structure, without loss of error protection, yielding simplified parity channels with finite impulse response (FIR) structures with computational rates decimated by k. The code modification procedure is described. The code modification process has been automated in a computer algorithm. The effects of parity filter quantizations are analyzed and a bound on the mean-square error in the parity comparison is given.>

A description is given of Starloc (Sandia target Location computer) a special-purpose computer designed for automatic target recognition. It is motivated by the lock-and-tumbler (LAT) filter algorithm, a generalized matched filter that can detect targets regardless of variations in their appearance. Starloc's fault-tolerant structure of pipelined, parallel floating-point processors and memories efficiently performs two-dimensional correlation, the major computational kernel of the algorithm. The LAT filter algorithm correlates the input image with a set of ten to twenty filter kernels, each containing all of the information about the target and its variations, using a phase multiplexing scheme. Starloc implements the LAT algorithm correlations in the Fourier domain by transforming the image to the Fourier domain, performing pixel-by-pixel multiplication with a filter kernel represented in the domain, and then inverse-transforming the product. The last processing step is updating the target value for each pixel. Hot-standby processors and incorporating a comprehensive set of error checkers provide fault tolerance. A reduced-scale prototype has been constructed, and an advanced design using digital signal processors for increased speed is described.>

Modern high-speed convolvers use sophisticated arithmetic units operating over large finite integer rings or with floating point approximations to the real or complex fields. However, these units are susceptible to random internal errors termed soft fails. New systematic encoding and data manipulation techniques that make error detection with generalized cyclic codes straightforward and efficient are described. Error control is attached directly to the data, permitting protection of any form of parallel or distributed system configuration. Design methods for one class of real cyclic codes are detailed. The necessary overhead for direct parity computations have complexity proportional to the number of parity symbols squared, whereas the error-detecting capability for both random and burst errors is directly related to this parity number. When certain extension fields exist, the parity calculations become linear with the number of complex operations in the extended domain.>

Finite-field transform quantities, appearing in typical cyclic code decoders, obey conjugacy-based relationships commonly called chord properties. It is demonstrated that these relationships may be used to significantly expedite error estimation by the decoder. The resulting speed-up factor is proportional to the degree of the extension field in which the code design is specified. BCH codes and standard decoder structures, either of the frequency-domain or time-domain type, are used to motivate, develop, and illustrate the underlying principles. Approximate estimates of the complexities and benefits of the proposed techniques are given. Finally, these chord-directed speed-up methods are extended to Reed-Solomon and other cyclic codes that use symbols in an extension field.>

Fault-tolerance in dense high-speed arithmetic units that calculate convolutions between arrays of data is introduced through cyclic codes which are defined over the rings and fields commonly employed by such units. New systematic encoding and data manipulation techniques make the application of these generalized cyclic codes to error detection straightforward and efficient. The necessary overhead parity computations have complexity proportional to the number of parity symbols squared, whereas the error-detecting capability for both random and burst errors is directly related to this parity number.

Digital filtering architectures that simultaneously offer advantages for VLSI fabrication and contain distributed error control are presented. Such structures require parallelism as well as inherent error- control capabilities because VLSI implementations are susceptible to temporary and intermittent hardware errors. The filtering convolution operation is similar to the formation of cyclicerror-correcting codes so that fault-tolerant systems employing finite field arithmetic may be designed containing such codes imbedded directly in the architecture. The interconnection of such systems produces a fault-tolerant system. In addition, the subsystems possess a common design structure which is easily customized to the particular field required, an attractive feature for yield enhancement. Straightforward realizations depending on parallel algebraic decompositions are studied, introducing the locations for fault tolerance and the role of cyclic codes.

High-speed cyclic code decoders, which are central to modern communication systems, when implemented in dense very large scale integration (VLSI), are susceptible to pernicious momentary internal soft fails presenting a demanding error-control challenge. However, special structures inherent in such decoders offer new methods for incorporating distributed error control throughout their designs. The underlying design principles and motivations are emphasized providing a variety of options to meet various requirements. Bose-Chaudhuri-Hocquenghem (BCH) codes are used to exemplify the new techniques as applied to the usual three standard subsystems present in a decoder. The first and last parts, syndrome calculations and transform inversion, both involve finite field transforms suggesting the effective application of fast transform algorithms. Error control features are based upon the chord properties of the transform coefficients including even fast algorithms. The third subsystem, the Berlekamp-Massey algorithm, can be protected through a chord recursion property affiliated with the error location connection polynomial. The propagation and spread of internal errors are studied and a special sink register compares several quantities, available in close proximity, to their easily recomputed counterparts. Most of these results are applicable to generalized to decoders for codes over higher ordered alphabets such as Reed-Solomon codes.

Digital filtering architectures that simultaneously offer advantages for wafer VLSI fabrication and contain distributed error-control are presented. Such structures require parallelism as well as inherent error-control capabilities because VLSI implementations are susceptible to temporary and intermittent hardware errors such as soft fails. Convolutions are implemented by finite field arithmetic subsections, where the operations in the various subsections are equivalent to polynomial multiplications, leading to the natural introduction of cyclic codes in the basic architecture. A polynomial expansion technique permits powerful cyclic subcodes to be introduced in each parallel subsection resulting from such a decomposition. Locations for error control within the architectures are examined, and several approaches for combatting failures are detailed.

Wafer-scale integration (WSI) compresses a large amount of microelectronics representing a complete digital system onto a single intact wafer. This approach is desirable for applications requiring extensive computational capabilities but only limited input and output connections. Its primary advantage is an improvement in total system density. However, such designs must have built-in fault tolerance. Parallel architectures are ideal for WSI. Thus, digital filtering implemented via the residue number system (RNS) is an application that naturally fits the requirements and advantages of WSI. A finite impulse response (FIR) filter readily lends itself to RNS implementation, and a system architecture employing both RNS and WSI is proposed. Means of introducing inherent fault tolerance using the RNS are briefly covered. After a tutorial introduction to the residue number system, methods of performing addition and multiplication operations in the RNS are explored on the basis of reducing area for a custom VLSI design. Modulo addition implemented with two conventional binary adders provides a compact design that may be externally programmed for the modulus that it operates in. Realization of mod multiplication via index addition is shown to be more effective than implementing the mod multiplication truth table directly. Conversions from binary to the RNS representation and vice versa are major bottlenecks in RNS design. Techniques for conversion into the RNS and out of the RNS based on a sequential division algorithm and the mixed-radix system expansion, respectively, are presented.

Schemes are developed whereby the number of arithmetic operations needed in a fast finite field transform employing factor-type algorithms are decreased by using a chord property of the intermediate variables. Noticeable improvements in both the Good and the Cooley-Tukey forms of fast algorithms are possible. A proof of the limited chord properties of the intermediate variable is included, and several numerical examples for comparison purposes are given.

The number of arithmetic operations needed for a fast finite filed transform is decreased by applying a chord property to the algorithm's intermediate variables. Such a property arises from the conjugacy requirements imposed by the input data lying in a smaller generating field. A chord is a list of conjugate roots which in turn are indexed by cyclotomic subsets of the integers, modulo n. The chords are easily determined through the manipulation of integers, avoiding finite field calculations directly. All transform coefficients falling in the same chord are related by repeatedly forming prime powers of any one of them.

Thekinput and output digits of a rate(k/n)linear convolutional code over a finite field GF(q)are related to a finite set of integers by aq-ary expansion. The mean-square error criterion is used to simultaneously select the optimum encoder and decoder rules. This optimization is performed over all one-to-one generalized encoding rules and all decoding functions that map into the real numbers. The optimal design procedure relies upon generalized Fourier transforms, and it is shown that the encoder part of the optimum pair of rules can be taken as a linear function when the input space of symbols is viewed in a natural algebraic setting. The decoder part is a conditional mean estimator coupled with a rounding operation. One method of implementing the decoder uses the nonlinear combination of filter functions defined in the generalized frequency domain.

A Markov model of a finite state machine realization containing gates and memory elements each subject to internal soft errors is given and a computational method for determining the probability of state transition errors is presented. The system inputs are taken as stochasticaily driven and the long-run stationary probability distribution of the states is developed. Similar results are determined for a fault-tolerant realization using error-correcting codes to form cluster states according to a technique of Reed. The state transition error performance of the coded machine is compared to that of the original realization; a dramatic improvement is seen when normally small soft error rates are encountered. The computational aspects of the required probabilities are investigated and a simplified approximation approach is proposed and analyzed. Bounds on the approximation inaccuracies are derived.

A signal processing system employing digital arithmetic can be made equivalent to a set of interconnected subsystems each using finite field operations to alleviate effects of round-off noise, particularly in recursive structures. The realization of the subsystems involves the multiplication of polynomials over a finite field. Cyclic convolutions may be represented as polynomial multiplications, in a residue class ring modulo the polynomial (xk-1). Fast algorithms arise when the ring is decomposed into a direct product using its minimal ideals, the orthogonality relationships between the idempotents of the minimal ideals resembling the decomposition properties of the Chinese remainder theorem for real polynomials. The resulting component polynomial multiplications involve elements with smaller degrees. A transform domain, based upon an nthroot of unity in an extension field, offers an alternative domain for performing the component operations. Polynomial multiplications are equivalent to the vector inner product of the corresponding transform coefficients. The minimal ideal components, when mapped into the transform domain, have nonzero coefficients only in predetermined subsets, the cyclotomic subsets, which permits one coefficient to generate all others by successively forming its powers.

The theoretical basis for using the mean-square error criterion in channel coding systems has been established previously. Such a criterion leads to an unequal error-correcting system. This paper describes the design methods for translating that theory into practice. It also presents some new results concerning the performance of these types of systems. The relationship of the mean-square system to the one based on the minimum probability of error is examined. Except for very noisy channels the two decoders produce identical outputs for all correctable error patterns. However, the mean-square error decoder guarantees various levels of correcting capabilities for the more significant positions during overload conditions. The basic design technique relies upon generalized transforms that are closely affiliated with the Walsh functions. The fundamental parameters that are the key to the system design may be computed using a fast algorithm which is developed over a subspace in the generalized frequency domain. The decoder performs error correction with a code containingkinformation symbols by numerically combining the output from (k+ 1) finite impulse response (FIR) type of filters. The filter weights are directly related to the transforms of the system's transition probabilities. Simplification methods and precision requirements in the filter mechnizations are discussed.

Channel coding systems that employ linear block codes can be designed according to a mean-square error criterion. The optimum encoder and decoder pair is determined by selecting special elements in a generalized frequency domain based upon the values of key parameters called ratio weights. Systems may be designed that employ either hard or soft decision variables in the decoder. When cyclic codes are used, a minimal ideal decomposition of the code space shows that the ratio weights possess constant values on certain subsets in the frequency domain. This permits a drastic reduction in the number of ratio weights that need to be computed. For a cyclic code withtminimal ideals, this design procedure narrows the search for constancy subsets of the ratio weights to(2^{t}-1)subsets of the general space. Only one ratio weight needs to be computed for each constancy subset.

It is sometimes difficult to simulate on general purpose computers the performance of digital systems that use residue number systems. This paper demonstrates a new technique that makes effective use of a Fast Fourier Transform (FFT) to simulate the basic arithmetic operations required by such number systems. An algorithm for performing such operations which involves the FFT, standard programming techniques and normal arithmetic computations is presented. It is exemplified by consider operations in finite fields. The FFT size is proportional to the exponent of the size of the residue system. Thus there is a logarithmetic relationship between the number system's size and the transform length. Favarable comparisons are given between the FFT mechanization of this approach and one employing a more conventional assembly language implementation.

Several standard signal processing techniques may be effectively applied in the design and mechanization of optimum encoders and decoders in error control systems that employ block error-correcting codes. Many of the approaches rely upon generalized transforms that resemble the Walsh functions. They use a fast algorithm that is developed over a subspace in the generalized frequency domain. The decoder performs error correction with a code which containskinformation symbols by numerically combining the output from (k+1) finite impulse response (FIR) type of filters. These filters use weights that are directly related to the transforms of the system's transition probabilities. Each filter weights the transforms of the received digits over (k+1) special subsets in the frequency domain.

We develop algorithms for implementing finite field arithmetic on general signal processing machines. Our emphasis is on achieving practical approaches compatible with a wide range of computer systems. The techniques easily mix with normal signal processing algorithms obviating the need for appendages of special finite field hardware to information processing systems.

An(n,k)linear block code is used to conveykinformation digits, each having a numerical value attached, in such a way as to minimize the mean-square error of the individual information digits regardless of the other(k-1)positions. This criterion is used because it provides a graceful degradation in the coding performance when the channel temporarily becomes less reliable. Unambiguous encoding is employed, and the channel is assumed to obey a realistic additive property. An optimum pair of symbol encoding and decoding functions are derived, and it is shown that the optimum symbol encoding can be performed in a linear fashion. The related decoding role is the conditional mean estimator. Fourier transforms are central to the optimal design of both rules. The optimum symbol rules tire identical with the properly isolated parts of the optimum mean-square error rules when the code is used to carry the k Information digits considered as a single complete numerical entity, The same channel coding design is therefore optimum for a wide variety of Information configurations. Techniques for implementing the optimum symbol decoders are examined with special emphasis on memoryless channels where the storage requirements for the necessary weighting coefficients are drastically reduced.

We are concerned with the protection of speech parameters, produced by a linear predictor, when they are transmitted through a typical communications channel. An analysis of the complete system yields a lower bound to the overall mean-square error. These results isolate the role that channel coding plays in the total system performance. Our goal is to motivate the selection of a more sensible criterion for designing channel coding in such systems. We demonstrate that the mean-square error criterion used on a channel basis is such a choice and that there are reasonable design procedures for employing block codes in this fashion. This type of coding can be applied not only to whole individual speech coefficients but to various groups of positions. Finally the implementation of the corresponding decoder is examined from the viewpoint of generalized bandpass filtering.

A numerical procedure for determining the cyclically permutable code of any length over an arbitrary alphabet is outlined. This method is easily programmed on a digital computer. A formula for the Hamming weight distribution of the code is also given. The results for the 12 bit binary cyclically permutable code are presented along with the weight distribution of the binary codes through length 14.

We show that the optimum decoder for a linear code over a finite field can be implemented by a bank of bandpass filters that are defined in a generalized frequency domain. This decoder has a fixed signal processing structure and uses complex-valued arithmetic operations instead of the usual finite field ones, This structure closely resembles one of the usual digital filter mechanizations. The emphasis in this paper is on general additive channels. The maximum likelihood decoder configuration for a ratek/ncode is a bank ofkbandpass filters whose outputs are the decoded information digits. The parameters that define the filters are directly related to the channel statistics, and each of the band-pass filters is composed ofrbranch filters where the order of the field is therth power of a prime. The processing requirements can further be reduced by detuning each branch filter and following it by a real roundoff operation. These possibilities have not been fully exploited and remain an open question. A procedure for determining the filter weights needed in the branch filters that uses fast transform techniques is demonstrated. The probability of correct decoding can be computed using functions defined over the transform domain. Finally, we show that suboptimal decoders, which may also include detection capabilities, can be derived from this work. A hierarchy of suboptimal decoding levels is proposed so as to reduce the average computational requirements of the decoder.

By the use of abstract Fourier analysis on groups, the optimum mean-square-error decoding rule is developed for a fixed block code. The optimum one-to-one coding role to be used with this optimum decoder is derived, and a procedure for simultaneous optimization over both encoding and decoding rules is given. It is shown that there is a linear encoding rule which is optimum. A system which implements the optimum decoding rule is outlined. The major difference between this work and others involving coding for mean-square error is that the decoding rule developed here is a mapping from binaryn-tuples directly into the real numbers with the optimization being over all possible mappings into the real numbers. As such the system developed here replaces both the error-correction and digital-to-analog conversion components used in most numerical data transmission systems.

The Walsh series coefficients for the circular functions are considered. Specifically we determine the sequency content of eJπtand present bounds on the corresponding sequency-line spectrum.

We consider ann-dimensional vector space overGF(q)which has a probability distribution defined on it. The sum of the probabilities over a properk-dimensional subspace is compared to a sum over a coset of this subspace. The difference of these set probabilities is related to a sum of the Fourier transforms of the distribution over a subset of the domain of the transforms. We demonstrate the existence of a coset and both an upper and a lower bound on the difference associated with this coset. The bounds depend on the maximum and nonzero minimum of the transforms as defined on a special subset of the transform domain. Two examples from coding theory are presented. The first deals with aq-ary symmetric channel while the second is concerned with a binary compound channel.