It has been shown that the 2-D cubic spline interpolation (CSI) proposed by Truong et al. is one of the best algorithms for image resampling or compression. Such a CSI algorithm together with the image coding standard, e.g., JPEG, can be used to obtain a modified image codec while still maintaining a good quality of the reconstructed image for higher compression ratios. In this paper, a fast direct computation algorithm is developed to improve the computational efficiency of the original FFT-based 2-D CSI methods. In fact, this algorithm computes the 2-D CSI directly without explicitly calculating the complex division usually needed in the FFT or Winograd discrete Fourier transform (WDFT) algorithm. In addition, this paper describes a novel way to derivate the 2-D CSI from the 1-D CSI by using the row-column method. This new fast 2-D CSI provides a regular and simple structure based upon linear correlations. Therefore, it can be implemented by the use of a modification of Kung’s pipeline structure and is naturally suitable for VLSI implementations. Experimental results show that the proposed new fast 2-D CSI algorithm can achieve almost the same CSI performance with much fewer arithmetic operations in comparison with existing efficient algorithms.

In this letter, it is shown that a fast, prime-factor discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2/sup m/-1 points over GF(2/sup m/), where 8/spl les/m/spl les/10. Using these transforms, together with the Berlekamp-Massey algorithm, the complexity of the transform-domain decoder for correcting both errors and erasures of the Reed-Solomon codes of block length 2/sup m/-1 over GF(2/sup m/) for 8/spl les/m/spl les/10 is reduced substantially from the previous time-domain decoder. A computer simulation verifies these new results.

In this paper, a high efficient decoding algorithm is developed here in order to correct both erasures and errors for Reed-Solomon (RS) codes based on the Euclidean algorithm together with the Berlekamp-Massey (BM) algorithm. The new decoding algorithm computes the errata locator polynomial and the errata evaluator polynomial simultaneously without performing polynomial divisions, and there is no need for the computation of the discrepancies and the field element inversions. Also, the separate computation of the Forney syndrome needed in the decoder is completely avoided. As a consequence, the complexity of this new decoding algorithm is dramatically reduced. Finally, the new algorithm has been verified through a software simulation using C/sup ++/ language. An illustrative example of (255,239) RS code using this program shows that the speed of the decoding process is approximately three times faster than that of the inverse-free Berlekamp-Massey algorithm.