This paper presents some results on multiple error detection and correction based on the Redundant Residue Number System (RRNS). RRNS is often used in parallel processing environments because of its ability to increase the robustness of information passing between the processors. The proposed multiple error correction scheme utilizes the Chinese Remainder Theorem(CRT) together with a novel algorithm that significantly simplifies the error correcting process for integers. An extension of the scheme further reduces the computational complexity without compromising its error correcting capability. Proofs and examples are provided for the coding technique.

Block ciphers provide confidentiality by encrypting confidential messages into unintelligible form, which are irreversible without knowledge of the secret key used. During the design of a block cipher, its security against cryptanalysis must be considered. History has shown that a cipher designed without an adequate treatment of this will often lead to flaws and attacks by other researchers, sometimes devastatingly so. The problem for an aspiring cipher designer is that there are no standard texts on block cipher cryptanalysis because it is a fast changing field. The commonly available references are academic journals and conference proceedings, which may not be easy to grasp for researchers new to cryptanalysis. This paper presents the Xi framework, which is designed to compactly describe the block cipher cryptanalysis techniques regardless of their individual differences. This provides the cryptanalyst with a general framework to describe attacks on block ciphers, with the additional capabilities of allowing specification of the technical details of each different type of attack and of comparison of their respective strengths. Comparing different distinguishers in this framework also allows us to see natural generalizations and trigger nice open problems. We then show how to apply this Xi framework to the description of various attacks on popular and recent block ciphers.

The challenges specific to interpolation at low video frame rates are illustrated by choosing an algorithm that performs well at high frame rates and applying it to low frame rates. The performance is illustrated by comparing the original algorithm, the algorithm adapted to low frame rate particularities, and simple averaging. To overcome the particular challenges of low frame rates, two algorithms were developed and compared on objective and subjective bases and shown to provide elegant solutions to the specific challenges of low frame rate video interpolation.

It is shown that decoding of cyclic codes in the DFT domain is equivalent to an appropriate deconvolution problem. A two-dimensional (2-D) generalization of Blahut's (1979) one-dimensional (1-D) linear complexity theorem is obtained and utilized to determine the error-correcting capability of 2-D BCH codes, as afforded by code's defining array of zeros, with regard to correction of burst-errors. The 2-D linear complexity theorem is further utilized to present a new approach for decoding of cyclic codes, in general, and 2-D BCH codes in particular. An alternative exposition of Blahut's decoding algorithms, in the DFT domain, for random and burst error correction in 2-D BCH codes is given from a deconvolution viewpoint. Some modifications for efficient implementation of Blahut's decoding algorithms for random and burst error correction are suggested and improved decoding algorithms are presented. It is shown that the improved decoding algorithm requires at most half the number of passes through the Berlekamp-Massey algorithm compared to the Blahut's decoding algorithm. It is shown that Blahut's decoding algorithms have optimal error-correcting capability and improved decoding algorithms have less computational complexity. A comparative study of various time- and spectral-domain implementations of 2-D BCH decoding algorithms is also given.

We construct new sequences over finite rings having optimal Hamming correlation properties. These sequences are useful in frequency hopping multiple-access (FHMA) spread-spectrum communication systems. Our constructions can be classified into linear and nonlinear categories, both giving optimal Hamming correlations according to Lempel-Greenberger (1974) bound. The nonlinear sequences have large linear complexity and can be seen as a generalized version of GMW sequences over fields.

Finite gray-scale digital images are modeled as realizations of discrete random functions (DRF), and then the estimation of realizations of DRF corrupted by a supremum/infimum noise model is considered. It is proved that morphological operators such as openings, closings, supremum of openings and infimum of closings are optimal maximum a posteriori (MAP) estimators under an appropriate and minimal set of assumptions relating to the structural and statistical constraints on image DRF and noise DRF. These results are obtained for independent, identically distributed (i.i.d.) noise for single and multiframe observation scenarios. Next, the assumption of i.i.d. noise is relaxed and the MAP optimality and strong consistency of morphological filters for filtering image DRF degraded by morphologically smooth noise (i.e., colored noise) is proved. Simulations on actual image data are carried out in support of the validity of theoretical results presented.

The estimation of finite-gray-scale digital images corrupted by supremum/infimum noise is posed within the statistical framework of discrete random functions (DRF). It is shown that morphological operators such as openings, closings, supremum of openings and infimum of closings are optimal Maximum-A-Posteriori (MAP) estimators under the assumption that noise is independent and identically distributed (lid) for single and multiframe observation scenarios. Simulation results supporting the validity of theoretical results are also included.

The problem of optimal morphological filtering is posed within the statistical framework of discrete random function theory. The optimal morphological estimator of realizations of the discrete random function (DRF) (modeling finite-gray scale digital images) corrupted by supremum/infimum noise is obtained. The mean absolute error (MAE) is used as a distance measure between the original and the estimated image. The optimal filter (which yields minimum MAE) is characterized in terms of the discrete generating functional of the image DRF and the noise DRF under the assumption of statistical independence of image and noise. The MAE of estimation by the morphological filter is represented in terms of MAE incurred by each of the basis filter elements. Recursive expressions can be used to compute the MAE for an n element basis filter in terms of an (n-1) element basis filter. Simulation results on actual image data are included to corroborate the claims of the paper.

New families of biphase sequences of size 2/sup r-1/+1, r being a positive integer, are derived from families of interleaved maximal-length sequences over Z/sub 4/ of period 2(2/sup r/-1). These sequences have applications in code-division spread-spectrum multiuser communication systems. The families satisfy the Sidelnikov bound with equality on /spl theta//sub max/, which denotes the maximum magnitude of the periodic cross-correlation and out-of-phase autocorrelation values. One of the families satisfies the Welch bound on /spl theta//sub max/ with equality. The linear complexity and the period of all sequences are equal to r(r+3)/2 and 2(2/sup r/-1), respectively, with an exception of the single m-sequence which has linear complexity r and period 2/sup r/-1. Sequence imbalance and correlation distributions are also computed.

A generalized discrete Fourier transform defined over an appropriate extension ring is given that is suitable to characterize Abelian codes over residue class integer rings Z/sub m/. The characterization is in terms of generalized discrete Fourier transform components taking values from certain ideals of the extension ring. It is shown that the results known for cyclic codes over Z/sub m/, like the simple characterization of dual and self-dual codes and the nonexistence of self-dual codes for certain values of code parameters, extend to Abelian codes over Z/sub m/ as well.>

Abelian codes constitute a class of codes that includes cyclic codes as a special case. It is shown that the general class of abelian codes can be characterized in the transform domain using the discrete Fourier transform (DFT) over finite fields with the appropriate mixed radix number system as the indexing scheme for DFT coefficients. A simple transform domain description for dual codes of abelian codes is also obtained. Using this description the idempotent generator of the dual of a given abelian code can be easily obtained. Finally, it is shown that in the case of cyclic codes which can be considered as abelian codes also, one can work in smaller extension fields compared to the extension fields if they were considered as cyclic codes only.>