This article proposes two types of unscented particle filters (UPFs) that leverage unscented transformation (UT) from a geometric perspective to compute the proposal distribution. An UPF on Lie groups is first developed. Specifically, both the propagation of the sigma points and the computation of the mean and covariance are performed on the Lie groups, while the weight update and resampling are conducted on the Lie algebra. Second, we introduce the log-linear property of group elements to streamline particle propagation by reducing redundant operations, thereby optimizing the proposed UPF framework. In the update process, intermittent measurements that are caused by factors such as packet dropouts and stochastic sensor scheduling are considered. While lowering computational demands, these measurements pose challenges to filter stability. To this end, the introduced property is used to prove that the estimation error remains bounded under certain assumptions. We further establish a critical threshold for the arrival rate of intermittent measurements and derive an upper bound for the expected state error covariance. Moreover, a detailed computational complexity analysis is conducted to evaluate the efficiency of the proposed method. Finally, with the original method serving as a benchmark, simulation and real-world GNSS/INS integrated navigation experiments confirm that the redesigned approach delivers comparable performance and significantly improved computational efficiency.

Event-based visual odometry has recently gained attention for its high accuracy and real-time performance in fast-motion systems. Unlike traditional synchronous estimators that rely on constant-frequency (zero-order) triggers, event-based visual odometry can actively accumulate information to generate temporally high-order estimation triggers. However, existing methods primarily focus on adaptive event representation after estimation triggers, neglecting the decision-making process for efficient temporal triggering itself. This oversight leads to the computational redundancy and noise accumulation. In this paper, we introduce a temporally high-order event-based visual odometry with spiking event accumulation networks (THE-SEAN). To the best of our knowledge, it is the first event-based visual odometry capable of dynamically adjusting its estimation trigger decision in response to motion and environmental changes. Inspired by biological systems that regulate hormone secretion to modulate heart rate, a self-supervised spiking neural network is designed to generate estimation triggers. This spiking network extracts temporal features to produce triggers, with rewards based on block matching points and Fisher information matrix (FIM) trace acquired from the estimator itself. Finally, THE-SEAN is evaluated across several open datasets, thereby demonstrating average improvements of 13% in estimation accuracy, 9% in smoothness, and 38% in triggering efficiency compared to the state-of-the-art methods.

Indoor positioning technologies are pivotal for achieving high-precision localization in GPS-denied environments. Wireless positioning methods based on angle of arrival (AOA) models leverage spatial diversity to mitigate indoor multipath challenges. Recent approaches combine the extended sparse reconstruction framework with direct positioning (DP) techniques to jointly extract location parameters at the raw signal level. However, the disadvantage is that they have limited utilization for structure information inherent in a sparse solution and overlook the low-rankness in array manifolds induced by redundant grid points. To overcome these problems, a novel structure-aware direct localization method namely SaDPD is proposed that incorporates comprehensive structural constraints of joint row plus element sparsity and low-rankness in the designed sparse framework. A new sparse reconstruction problem is formulated by decomposing the position weight matrix into two distinct feature matrices, in which they are optimized for correlated line-of-sight (LOS) and inconsistent non-line-of-sight (NLOS) components, respectively. In particular, it employs the Alternating Direction Method of Multipliers (ADMM) to effectively address the extended high-dimensional optimization and utilizes grid refinement to avoid quantization constraints. Finally, extensive simulations verify that SaDPD tremendously improves sparse reconstruction accuracy and localization performance. Experimental result further demonstrates its effectiveness and practical applicability against real-world interference. These advancements establish SaDPD as a robust solution for asset positioning and target tracking where localization accuracy beyond half-meter level under multipath interference is critical.

The state estimation on$SE_{2}(3)$Lie Group has been proven to have the ability to improve the consistency of the estimated results. They are called invariant state estimation approaches, including filter-based ones and optimization-based ones. Precise Point Positioning (PPP) is a Global Navigation Satellite System (GNSS) positioning technology which can achieve high-precision positioning without commercial base stations. Visual-Inertial Odometry (VIO) combines Visual-SLAM and IMU, realizing a more robust local pose estimation than either of the two. In this paper, the invariant optimization approach has been applied to fuse PPP/INS/Visual-SLAM. The proposed positioning system in our paper is called In-P3VINS. All raw data of the In-P3VINS is modeled and optimized under an invariant factor graph framework. In particular, the carrier phase measurement is utilized by adding the phase ambiguity into the estimated states. Finally, In-P3VINS is evaluated in both simulation experiments and real-world experiments. In the simulation experiments, the accuracy and consistency of In-P3VINS are superior to the other compared methods. In the real-world experiments, In-P3VINS has the most accurate results.

This paper aims to estimate the two dimensional (2D) direction-of-arrival (DOA) using a polarized uniform rectangular array (URA) under multipath propagation. To leverage the tensorial nature, a parallel factor (PARAFAC) model is established, in which it comprises two spatial response matrices, the polarization response matrix, and the source matrix. Unfortunately, the source matrix exhibits rank-deficiency, hindering effectively PARAFAC decomposition. Our analysis reveals that the rank-deficiency can be easily resolved by taking the KhatriRao product with a full column rank factor matrix. Consequently, three rearranged PARAFAC tensors are obtained that are free of the source matrix's rank-deficiency. The estimation of 2D-DOA is then performed using the vector cross product-auxiliary rotational invariance technique (VCPARIT). The proposed algorithms are insensitive to inter-sensor distance and are suitable for a one-snapshot scenario. Furthermore, they outperform existing smoothing methods from the perspective of estimation accuracy. Theoretical advantages of the proposed algorithms are corroborated by the simulations.

Convolution on 3D point clouds has been extensively explored in geometric deep learning, but it is far from perfect. Convolution operations on point clouds with the fixed kernel indistinguishably capture correspondences between feature pairs, thereby raising an inherent drawback of limited distinctive feature learning. This paper proposes a novel approach to Sampling Adaptive Kernels from Subspace (SAKS) for graph convolution. It adaptively constructs convolution kernels for different feature correspondences according to the unique coordinate representations under the learned subspace. Associating the subspace design with the deep network is a novel concept, providing different viewpoints on feature learning. Specifically, incomplete orthogonal bases are learned at each convolution layer to span a linear subspace in an elaborately designed manner. Subsequently, adaptive kernels are sampled from the learned subspace via unique coordinates parameterized by feature pairs. Unlike existing adaptive convolution methods in a bruteforce manner, the low-rank property of the subspace reduces the computational complexity of this method. Moreover, we theoretically prove that the proposed SAKS derives the principal components of the kernel distribution, which is similar to principal component analysis under some prior assumptions. Extensive experimental results on point cloud classification and segmentation tasks show that SAKS outperforms state-of-the-arts on various benchmark datasets.

The front-wall clutter removal in the case of the through-the-wall radar (TWR) system is studied in this work. To remove the wall clutter, its low-rank property is utilized, and at the same time, the sparse property of the target returns is exploited to perform target reconstruction. To account for the unparalleled setting of the antenna and the wall, a weighted nuclear norm minimization (WNNM) is employed, and the resulting problem is solved in an alternating manner. In addition, different transmitted waveform signals, including monofrequency and stepped-frequency waveforms, are used to demonstrate their effects on the clutter suppression performances. The experimental results show that the proposed WNNM with stepped-frequency waveform outperforms other approaches.

This paper is aiming at addressing an azimuth-elevation direction-finding algorithm using a pair of identically oriented acoustic vector sensors located near a reflecting boundary. Two fourth-order cumulant matrices related in terms of a translationally invariant structure are formed for recovering the acoustic vector sensor steering vectors in the particle-velocity coarray domain. Afterward, source azimuth-elevation directions are extracted in closed-form from the estimates of the coarray steering vectors. The identifiability study shows that the algorithm proposed herein can uniquely resolve up to 13 sources, thereby being applicable to underdetermined scenarios, where the number of sources exceeds that of the sensors. This capability constitutes the primary advantage over the many seminal works Hawkes and Nehorai (2000); Wu et al. (2016); Ahmadi-Shokouh and Keshavarz (20007); Tao et al. (2007); Xu and Liu (2007) that pioneered AVS array processing involving reflecting boundaries. Finally, numerical examples are provided to verify the theoretical analysis and demonstrate the efficacy of the proposed algorithm.

A novel spatial singularity-exponent-domain multiresolution imaging (SSMRI) method is proposed in this article. It is aimed at improving the image processing ability for the single-channel synthetic aperture radar (SAR), thereby acquiring the robust image feature for SAR target detection at the very low SNR. Combining the 2-D singularity power spectrum (SPS) and the 2-D pseudo-Wigner–Ville distribution (PWVD), the SSMRI method is derived. Consequently, the single-channel SAR images are transformed to obtain spatial multiresolution SAR images with respect to the singularity exponent. Furthermore, the separability of the SAR image target in the space of the singularity exponent is analyzed, and the separability theorem in the sense of SSMRI is proved. In particular, under the background of GWN and fractal noise, the separability of SAR image targets based on SSMRI processing is studied. In addition, the stability and robustness of SSMRI-SAR feature extraction are demonstrated. On this basis, a maritime SAR ship target detection method based on SSMRI is put forward in the extremely low SNR condition. The experiment results on the SAR-Ship-Dataset indicate that the proposed method is superior in performance to the traditional CFAR or 2-D-SPS method. Especially when SNR = −30 dB, the detection performance with more than 99.4% can be achieved.

For the recently developed quasi-reversible BCH codes with long lengths and high error-correcting capability, this paper is aimed at proposing a new and faster decoding procedure. It consists of four steps: 1) compute the consecutive syndromes; 2) calculate the syndrome functions by the forward and backward recursions; 3) solve a linear subsystem together with one matrix multiplication in order to find an error-locator polynomial; 4) determine the errors from the obtained polynomial by using the root-finding algorithm. This procedure, especially in Steps 2 and 3, differs greatly from the conventional procedures, which determine an error-locator polynomial directly from solving a linear system with the aid of the consecutive syndromes. The key idea behind this decoding technique is that the computational complexity of such a small subsystem instead of an originally large linear system can be significantly reduced, although there are additional forward and backward syndrome calculations with low complexity increasing. Finally, the illustrative examples and numerical simulations can be helpful to demonstrate the accuracy and efficacy of the presented decoding technique at different error-correcting capabilities.

A new signal processing algorithm proposed here is aimed at estimating five-dimensional (5-D) polarization-space-time (polarization, angle, delay) channel parameters for a tri-polarized system that works in a multipath environment. Unlike most channel estimation algorithms, where spatially spread antenna arrays are deployed, our algorithm is designed for a spatial col-located tripole antenna. A third-order tensor model is firstly established for the multipath polarization-space-time channel. This tensor is subsequently solved by exploiting low-rank decomposition techniques. After that, a closed-form solution of 2-D angles, 2-D polarizations, and multipath delay estimates for each multipath ray are derived. The proposed algorithm requires no computation for iterative searching and parameter pairing, thus offering an advantage in time-sensitive applications. In addition, it is applicable to either narrowband or wideband systems of arbitrary bandwidth and center-frequency.

Blind image deblurring is a long standing challenging problem in image processing and low-level vision. Recently, sophisticated priors such as dark channel prior, extreme channel prior, and local maximum gradient prior, have shown promising effectiveness. However, these methods are computationally expensive. Meanwhile, since these priors involved subproblems cannot be solved explicitly, approximate solution is commonly used, which limits the best exploitation of their capability. To address these problems, this work firstly proposes a simplified sparsity prior of local minimal pixels, namely patch-wise minimal pixels (PMP). The PMP of clear images is much more sparse than that of blurred ones, and hence is very effective in discriminating between clear and blurred images. Then, a novel algorithm is designed to efficiently exploit the sparsity of PMP in deblurring. The new algorithm flexibly imposes sparsity inducing on the PMP under the maximum a posterior (MAP) framework rather than directly uses the half quadratic splitting algorithm. By this, it avoids non-rigorous approximation solution in existing algorithms, while being much more computationally efficient. Extensive experiments demonstrate that the proposed algorithm can achieve better practical stability compared with state-of-the-arts. In terms of deblurring quality, robustness and computational efficiency, the new algorithm is superior to state-of-the-arts. Code for reproducing the results of the new method is available at https://github.com/FWen/deblur-pmp.git.

Combining the generalized fractal theory and the time-frequency distribution, the image feature decomposition in the singularity exponent domain is studied in this paper. With the theoretical derivation and quantitative analysis, the singularity-exponent-domain image feature transform (SIFT) method is proposed to analyze and process images from new feature dimensions. If one derives from the generalized fractal characteristics of the image, the two-dimensional frequency variables of the 2D time-frequency transform of the image can be used to estimate the two-dimensional singularity power spectrum (SPS) in the space dimension. As a consequence, it leads to the SPS distribution of the original image in the spatial domain, i.e., SIFT images. Based on the SIFT, the feature transform images with different singularity exponent and feature curves of singularity power spectrum with respect to different physical regions can thus be obtained. The SIFT is rigorously derived from the 2D-SPS and the Pseudo Wigner-Ville distribution (PWVD). In addition, the feature images based on the SIFT is proved to be the SNR independence in the GWN background. In order to validate the effectiveness of feature extraction, the proposed methodology is tested on the breast ultrasound images, the visual images, and the synthetic aperture radar (SAR) images. Furthermore, the SAR target detection method based on the SIFT images is proposed, and the experiment results indicate that the proposed algorithm is superior in performance to the traditional CFAR or 2D-SPS method. In fact, this new SIFT is promising to provide a technical approach for image feature extraction, target detection, and recognition.

It has been demonstrated that the cubic convolution spline interpolation (CCSI) scheme is one of the best algorithms for image resampling or compression. In this paper, a new simple direct computation of CCSI is proposed, where the sampled data are directly calculated by the use of the original data. Moreover, the proposed algorithm provides a regular and simple structure based on linear correlation and thus is naturally suitable for VLSI implementation. Computer simulations on several standard images indicate that the proposed simple direct computation of CCSI scheme can achieve almost the same objective and subjective performance with lower complexity.

We propose a novel direction-of-arrival (DOA) estimation method for hybrid millimeter-wave massive MIMO systems at low SNR. Unlike the existing hierarchical-search-based methods that directly estimate the DOA from the angular power, we investigate the angular power gradient based on beamforming with incremental gains. Then, we leverage the difference of beamforming gain among codebook levels and adopt a cumulative positive angular power gradient for estimation. Specifically, codewords for analog precoders are selected from different levels of a codebook that cover the same direction during every spatial sweep. Moreover, the power difference is proved to be a weak detector of source existence according to its sign, enabling the angular distribution estimation of the signal strength. Finally, the DOAs are estimated from peaks of the cumulative product of the previously measured signal strength. Simulation results show considerably enhancements of DOA performance at low SNR.

Generally, high-resolution imaging for highly squinted synthetic aperture radar (SAR) data is a difficult problem due to large range migration. Thus, when trying to solve this nontrivial problem, an azimuth-variant Doppler will arise, thereby leading to phase errors containing the azimuth spatial-variant (ASV) component. In this article, we analyze the characteristics of highly squinted SAR data and propose a new full-aperture ASV phase error autofocus algorithm. In this new algorithm, the accurate and suitable phase error signal model for highly squinted SAR data is derived. Moreover, the closed-form solution of the relationship between a distorted image and a focused image is also explicitly revealed. Furthermore, in this newly proposed algorithm, an accurate estimation of nonlinear ASV phase error is established based on the maximum contrast of the SAR imagery. In addition, an iterative gradient-based solver is introduced. The advantage of this new method provides a simple yet effective approach while being able to eliminate the ASV phase errors. More importantly, the accuracy of this new method using the full-aperture data is independent of SAR imaging algorithms. As a result, the proposed new method can be easily embedded in many existing imaging algorithms to produce focused imagery. Finally, two real highly squinted SAR data sets are provided to validate the advantages of our algorithm.

This article addresses the problem of tracking targets behind the wall using through-the-wall radar. To that end, the wall reflection, i.e., clutter, must be eliminated first because it interferes with the subsequent image formation operation. The low-rank of the clutter and sparseness of the useful signal are utilized to devise a joint low-rank and sparse framework to simultaneously suppress the clutter and recover the target returns, where alternating direction method of multipliers (ADMM) approach is developed to solve the corresponding optimization. Since then, an effective observation window scheme is proposed to locate the target and further to facilitate the tracking process. The tracking is finally provided by Kalman filter and particle filter. The numerical studies are provided to demonstrate that the performance of the proposed framework is superior to that of other methods in terms of clutter removal and tracking accuracy.

It is well-known that the decoding of algebraic codes with error locators have been extensively conceived in the literature over a half century. The radical locator, which is an ω th root of error locator, has recently been discovered. This paper focuses on the two classes of radical locators. The first is complete radical locators, where all the locators are assigned to radical locators. The second is partial radical locators in that there are only a few locators being radical locators. In the former case based on complete radical locators, a new square matrix whose determinant is a univariate radical-locator polynomial is proposed. In particular, this matrix is modified to allow a large square matrix. It can be transformed by Gaussian elimination to the matrix in a row-echelon form in which zeros appearing in the diagonal entries of the current matrix are able to determine errors implicitly. Furthermore, this work further extends the previous results from the univariate case to multivariate cases. The matrix methods found herein enable one to decode a large class of cyclic codes efficiently. In the latter case, the cyclotomic cosets are a practical approach to select a small subset of positive integers. They are employed to develop partial radical locators. Finally, in contrast with the complete radical locators, the algebraic decoding methods make a natural use of partial radical locators more widely and flexibly to arbitrary cyclic codes.

The recovery problem of synthetic aperture radar (SAR) signal in the presence of radio frequency interference (RFI) is studied. To perform RFI suppression, in this paper, the RFI is modeled as the combination of multiple complex sinusoids such that the RFI suppression problem becomes a frequency estimation one. To accurately estimate model parameters, by exploiting sparse representation of the RFI, a gridless approach based on atomic norm minimization is proposed, which completely removes the off-grid issue. Finally, to recover the SAR signal, a joint scheme is devised to simultaneously perform the RFI suppression and the SAR signal recovery under an optimization framework. The resultant optimization is efficiently solved by a two-step process based on the coordinate descent approach. Simulation results and real-world experiments are provided to show the superior performance of the proposed approach.

In this paper, two new decoding algorithms to decode Reed-Solomon codes during transmission over burst Rayleigh fading channels with additive white Gaussian noise (AWGN) are proposed. They only conduct error correction for coded symbols located in the pure AWGN region and conduct error and erasure correction for those symbols located in the burst fading region by treating those coded symbols that are very likely erroneous as erasures. The first algorithm does not need to know the fading locations in advance, while the second algorithm assumes that the fading locations are known. In addition, the performance of such two algorithms is studied when a pre-computed threshold is used to determine the erasures of the code. Simulation results show that our proposed algorithms not only significantly perform better than the classic Berlekamp-Messay algorithm with a comparable computational complexity but also achieve a better tradeoff between the performance and the computational complexity when compared with other existing algorithms. In particular, our algorithms exhibit excellent robustness for tested various code parameters and fading configurations. Furthermore, a more detailed mathematical analysis is also developed in this paper in order to estimate the performance of the new algorithms in the burst Rayleigh fading channels. We observe that the performance of the first algorithm can only be estimated relatively accurately when encountering burst deep-fading, whereas the performance prediction for the second algorithm is always in agreement with the simulation results for various fading cases.

Multiple-input multiple-output (MIMO) array synthetic aperture radar (SAR) with array antennas distributed along the cross-track direction can obtain 3-D scene information of the surveillance region. However, the cross-track resolution is unacceptable due to the length limitation of the MIMO antenna array. The superresolution algorithms within the framework of compressive sensing (CS) have been introduced to recover the cross-track signal because of its inherent spatial sparsity. The existing sparse recovery algorithms for 3-D SAR are attempted to find the sparse solution in the complex domain directly, which requires a very high computational complexity. To overcome this problem, a new fast 3-D imaging algorithm based on real-valued sparse representation is proposed in this paper. In this new algorithm, unitary transformation can be employed to transform the sparse signal recovery model of uniform/nonuniform MIMO array SAR from the complex domain to the real domain. Thus, a real-valued reweighted 12,1-norm minimization model is established. In addition, a modification of the fast iterative shrinkage-thresholding algorithm (FISTA) is used to reconstruct the 3-D image for further improving the computational efficiency. Moreover, the theoretical analysis of computational complexity of the proposed algorithm is derived when compared with an existing complex domain algorithm. Finally, numerical simulations and MIMO array SAR real experimental results are illustrated to validate that the proposed algorithm can reduce the computational complexity significantly in terms of CPU time while still maintaining the inherent advantages of superresolution and robustness against the noise.

Cubic-spline interpolation (CSI) scheme is known to resample the discrete image data based on the least-square method with the cubic convolution interpolation (CCI) function. It is superior in performance to other interpolation functions for digital image processing. In this paper, an improved approach to the CSI scheme is proposed for the decimation and interpolation of image data. The proposed CSI scheme combines the least-square method with six-point CCI function to improve performance. Moreover, a novel low-complexity implementation algorithm is proposed to simplify the decimation and achieve improvement of the computational efficiency. Computer simulations indicate that the proposed CSI scheme can achieve better performance without increasing the computational complexity compared with the four-point CSI scheme.

This paper addresses the problem of recovering a synthetic aperture radar (SAR) signal that is corrupted by both radio frequency interference (RFI) and wideband interference (WBI). The time–frequency domain is utilized for both the SAR signal and interference in the form of sparse representations. By doing so, a unified framework that allows one to suppress both the RFI and WBI while recovering the SAR signal can be developed. The resulting framework is an optimization problem that is efficiently solved using a customized alternating direction method of multipliers approach. Finally, simulation results are provided to demonstrate that the performance of the joint estimation algorithm is superior to the performances of other methods in terms of both subjective and objective evaluation standards.

The problem of blind image recovery using multiple blurry images of the same scene is addressed in this paper. To perform blind deconvolution, which is also called blind image recovery, the blur kernel and image are represented by groups of sparse domains to exploit the local and nonlocal information such that a novel joint deblurring approach is conceived. In the proposed approach, the group sparse regularization on both the blur kernel and image is provided, where the sparse solution is promoted by -norm. In addition, the reweighted data fidelity is developed to further improve the recovery performance, where the weight is determined by the estimation error. Moreover, to reduce the undesirable noise effects in group sparse representation, distance measures are studied in the block matching process to find similar patches. In such a joint deblurring approach, a more sophisticated two-step interactive process is needed in which each step is solved by means of the well-known split Bregman iteration algorithm, which is generally used to efficiently solve the proposed joint deblurring problem. Finally, numerical studies, including synthetic and real images, demonstrate that the performance of this joint estimation algorithm is superior to the previous state-of-the-art algorithms in terms of both objective and subjective evaluation standards. The recovery results of real captured images using unmanned aerial vehicles are also provided to further validate the effectiveness of the proposed method.

In this paper, an efficient decoding algorithm is developed to facilitate faster decoding of the binary systematic quadratic residue (QR) codes. It is based on the difference of syndromes (DS), and hence, is called the DS algorithm hereinafter. This new method combines the advantages of the syndrome-weight algorithm and properties of the cyclic codes. Actually, it is a natural generalization of the cyclic weight (CW) algorithm for the (47, 24, 11) QR code developed by Lin et al., and its validity of decoding any binary systematic QR code is also proved. The complexity analysis and simulation results show that the DS algorithm dramatically reduces the decoding complexity without performance loss and considerably requires less memory when compared with previous ones. Utilizing the (47, 24, 11), the (71, 36, 11), the (73, 37, 13), and the (89, 45, 17) QR codes as examples, the DS algorithm not only significantly improves the decoding efficiency, but also saves the memory evidently. When the (23, 12, 7) QR code is considered, the DS algorithm performs almost as well as the currently known best algorithm in terms of decoding efficiency and memory requirements. Thus, all QR codes of lengths less than 100 can be decoded efficiently by using the proposed algorithm. Especially, when the proposed algorithm is applied to decode the (89, 45, 17) QR code, the best one among all the QR codes of lengths less than 100, the decoding speed is raised 26 times and the memory is saved up to 76.6% in comparison with the existing fastest decoding algorithm.

A class of cyclic codes has recently been decoded by using the weak-locator polynomials instead of the conventional error-locator polynomials. In this paper, a generalization of weak-locator polynomials to the multivariate cases, called the multivariate weak-locator polynomials, is defined, and a new matrix whose determinant can be expressed as a multivariate weak-locator polynomial is developed for cyclic codes. Moreover, a modified matrix along with Gaussian elimination found herein enables one to determine error positions precisely. The presented matrices result in a reduction of the number of syndromes when compared with the previously known matrices. The simulation shows that, for example, with the capability of correcting more errors, a considerably sophistical scheme of decoding the (97, 49, 15) binary cyclic code based on the proposed matrices is around 115 times faster than other existing decoders. Therefore, in general, it is developed to facilitate faster decoding of a large class of cyclic codes and is naturally suitable for the software implementation.

This work addresses image recovery problem in the presence of salt-and-pepper noise and image blur. The salt-and-pepper noise reviewed as the impulsive noise, in this paper, is modeled as a sparse signal because of its impulsiveness. To accurately reconstruct the clean image and the blur kernel, the framelet domains are exploited to sparsely represent the image and the blur kernel. From the reformulations conducted, a joint estimation is devised to simultaneously perform the image recovery, the salt-and-pepper noise suppression and the blur kernel estimation under a optimization framework. To solve the optimization problem, an efficient solver based on accelerated proximal gradient (APG) is developed to obtain the joint estimation solution. Numerical studies demonstrate the superior performance of the joint estimation algorithm compared with the state-of-the-art approaches in terms of both objective and subjective evaluation standards.

The cubic‐spline interpolation (CSI) scheme is known to be designed to resample the discrete image data based on the least‐square method in conjunction with the cubic convolution interpolation (CCI) function. In this CSI scheme, the improved quality of resampling can be achieved as the interpolation kernel size increases. However, the improvement of the performance gets less and less. This means that the performance of the CSI scheme has not been significantly improved and converges toward a constant value when the interpolation kernel size exceeds a certain value. A proof of this result is given in this study and has never been seen in the literature to the authors' knowledge. Moreover, this study analyses the relationship between the performance and computational complexity of the CSI schemes with different interpolation kernel sizes and compares them from a structural point of view. Simulation results indicate that it is in agreement with the theoretic derivations. Since the arithmetic operations required are increasing linearly with the increment of the interpolation kernel size, selecting an interpolation kernel size gives the best trade‐off between the performance and computational complexity in practical applications. However, the optimum choice of the interpolation kernel size depends crucially on effective demand.

The problem of synthetic aperture radar image recovery in the presence of wideband interference (WBI) is investigated. Delayed versions of a transmitted signal are utilized to construct a dictionary in which a signal of interest (SOI) has a sparse representation. In this letter, WBI is sparsely represented by the time-frequency domain. By utilizing the transform domains, a joint estimation approach is devised to simultaneously perform WBI suppression and SOI recovery within an optimization framework. Based on the separability property in the optimization, an alternating direction method of multipliers-based approach is developed to efficiently obtain a solution. Finally, simulation results are presented to demonstrate the superior performance of the joint estimation algorithm.

In this study, a new approach is developed to facilitate faster decoding of a binary systematic (71, 36, 11) quadratic residue (QR) code. In this decoder, it simplifies the step of calculating the condition and avoids calculating the unknown syndrome, thereby yielding a fast algebraic decoder for correcting four possible errors. Moreover, while using the proposed algorithm, if uses the channel measurement information proposed by Chase to sequentially invert the bits of the received word until one of the errors is cancelled for the five‐error case and apply the new algebraic decoding algorithm mentioned above to correct the remaining four errors, the algorithm has been verified through a software simulation in C‐language. The simulation shows that the decoding scheme developed here is more efficient than the previous decoding algorithm developed for the (71, 36, 11) QR code and it is naturally suitable for software implementation.

The algebraic decoding of a p-ary cyclic code consists of four steps: 1) computation of the known syndromes using the received word; 2) computation of the unknown syndromes from the known syndromes; 3) computation of the error positions by a use of the Berlekamp-Massey (BM) algorithm and Chien's search; and 4) computation of the error values by solving a linear system. This paper addresses two problems of determining the error positions and computing the unknown syndromes. To solve the first problem, a new matrix, together with Gaussian elimination instead of the BM algorithm and Chien's search, is proposed. In this new simplified decoder, finding an error-locator polynomial is completely avoided. A main advantage of the presented decoding method is when the Bose-Chaudhuri-Hocquenghem bound is unequal to the minimum distance of the code. Some cyclic codes, which do not have 2t consecutive known syndromes, can be decoded up to their actual minimum distance by using the presented matrix once. To solve the second problem, two algorithms for different square matrices reported recently by Lee et al. are also provided to calculate the value of an unknown syndrome. Finally, an algebraic decoding of the (47,23,15) ternary cyclic code is given.

In this paper, a new algebraic method to decode the (71, 36, 11) QR code up to five errors is proposed. It completely avoids computing the unknown syndromes, and uses the previous scheme of decoding this QR code up to three errors, but corrects four and five errors with a new different method. In the four-error case, the new algorithm directly determines the coefficients of the error-locator polynomial by eliminating unknown syndromes in Newton identities. Subsequently, the shift-search algorithm can be utilized to decode the fifth error and the concept of bit reliability is also introduced to accelerate the decoding process. In other words, a weight-five-error pattern can be decoded in terms of the four-error case by inverting an incorrect bit of the received word in ascending order of reliability. Particularly, a threshold parameter γ can be preset to limit the number of inverting bits one by one, and a corresponding upper bound of the probability that decoding fails is derived. Finally, simulation and analysis show that the proposed new decoding algorithm for the abovementioned QR code not only significantly reduces the decoding complexity in terms of CPU time but also saves a lot of memory while maintaining the same error-rate performance. Additionally, the introduction of γ achieves a better tradeoff between the decoding performance and the computational complexity.

Presents comments on the paper, "On decoding of the quadratic residue code,” (Wang, L., et al) IEEE Trans. Commun., vol. 61, no. 3, pp. 832–841, Mar. 2013.

In this paper, an explicit expression of the weak-locator polynomial for p-ary quadratic residue codes is presented by a modification of the Feng-Tzeng matrix method. The differences between the modified version and the original Feng-Tzeng matrix are that in the new matrix, not every entry is a syndrome, and every syndrome entry is a known syndrome. By utilizing this technique, an algebraic decoding of the ternary (61, 30, 12) quadratic residue code is proposed. This new result has never been seen in the literature to our knowledge. An advantage of the proposed decoding algorithm is that in general the obtained weak-locator polynomials can decode efficiently not only all the error patterns of weights four and five, but also some error patterns of weight six.

In this paper1, a method to search the subsets I and J needed in computing the unknown syndromes for the (73, 37, 13) quadratic residue (QR) code is proposed. According to the resulting I and J, one computes the unknown syndromes, and thus finds the corresponding error-locator polynomial by using an inverse-free BM algorithm. Based on the modified Chase-II algorithm, the performance of soft-decision decoding for the (73, 37, 13) QR code is given. This result is never seen in the literature, to our knowledge. Moreover, the error-rate performance of linear programming (LP) decoding for the (73, 37, 13) QR code is also investigated, and LP-based decoding is shown to be significantly superior in performance to the algebraic soft-decision decoding while requiring almost the same computational complexity.

It is still an open challenge in coding theory how to design a systematic linear ( n , k ) − code C over GF(2) with maximal minimum distance d . In this study, based on matroid theory (MT), a limited class of good systematic binary linear codes ( n , k , d ) is constructed, where n = 2 k − 1 + · · · + 2 k − δ and d = 2 k − 2 + · · · + 2 k − δ − 1 for k ≥ 4, 1 ≤ δ < k . These codes are well known as special cases of codes constructed by Solomon and Stiffler (SS) back in 1960s. Furthermore, a new shortening method is presented. By shortening the optimal codes, we can design new kinds of good systematic binary linear codes with parameters n = 2 k − 1 + · · · + 2 k − δ − 3 u and d = 2 k − 2 + · · · + 2 k − δ − 1 − 2 u for 2 ≤ u ≤ 4, 2 ≤ δ < k . The advantage of MT over the original SS construction is that it has an advantage in yielding generator matrix on systematic form. In addition, the dual code C ⊥ with relative high rate and optimal minimum distance can be obtained easily in this study.

In this paper, a method to search the set of syndromes' indices needed in computing the unknown syndromes for the (73, 37, 13) quadratic residue (QR) code is proposed. According to the resulting index sets, one computes the unknown syndromes and thus finds the corresponding error-locator polynomial by using an inverse-free Berlekamp-Massey (BM) algorithm. Based on the modified Chase-II algorithm, the performance of soft-decision decoding for the (73, 37, 13) QR code is given. This result is new. Moreover, the error-rate performance of linear programming (LP) decoding for the (73, 37, 13) QR code is also investigated, and LP-based decoding is shown to be significantly superior in performance to the algebraic soft-decision decoding while requiring almost the same computational complexity. In fact, the algebraic hard-decision and soft-decision decoding of the (89, 45, 17) QR code outperforms that of the (73, 37, 13) QR code because the former has a larger minimal distance. However, experimental results indicate that the (73, 37, 13) QR code outperforms the (89, 45, 17) QR code with much fewer arithmetic operations when using the LP-based decoding algorithms. The pseudocodewords analysis partially explains this seemingly strange phenomenon.

In this paper, Three decoding methods of the (89, 45, 17) binary quadratic residue (QR) code to be presented are hard, soft and linear programming decoding algorithms. Firstly, a new hybrid algebraic decoding algorithm for the (89, 45, 17) QR code is proposed. It uses the Laplace formula to obtain the primary unknown syndromes, as done in Lin et al.'s algorithm when the number of errors v is less than or equal to 5, whereas Gaussian elimination is adopted to compute the unknown syndromes when v ≥ 6. Secondly, an appropriate modification to the algorithm developed by Chase is also given in this paper. Therefore, combining the proposed algebraic decoding algorithm with the modified Chase-II algorithm, called a new soft-decision decoding algorithm, becomes a complete soft decoding of QR codes. Thirdly, in order to further improve the error-correcting performance of the code, linear programming (LP) is utilized to decode the (89, 45, 17) QR code. Simulation results show that the proposed algebraic decoding algorithm reduces the decoding time when compared with Lin et al.'s hard decoding algorithm, and thus significantly reduces the decoding complexity of soft decoding while maintaining the same bit error rate (BER) performance. Moreover, the LP-based decoding improves the error-rate performance almost without increasing the decoding complexity, when compared with the new soft-decision decoding algorithm. It provides a coding gain of 0.2 dB at BER = 2 × 10-6.

The cubic-spline interpolation (CSI) scheme can be utilized to obtain a better quality reconstructed image. It is based on the least-squares method with cubic convolution interpolation (CCI) function. Within the parametric CSI scheme, it is difficult to determine the optimal parameter for various target images. In this paper, a novel method involving the concept of opportunity costs is proposed to identify the most suitable parameter for the CCI function needed in the CSI scheme. It is shown that such an optimal four-point CCI function in conjunction with the least-squares method can achieve a better performance with the same arithmetic operations in comparison with the existing CSI algorithm. In addition, experimental results show that the optimal six-point CSI scheme together with cross-zonal filter is superior in performance to the optimal four-point CSI scheme without increasing the computational complexity.

In this paper, an improved music genre classification method is presented. The proposed method makes use of the wavelet package transform (WPT) and the best basis algorithm (BBA) to accurately classify and increase classification performance. It is well known that WPT can generate a wavelet decomposition that offers a richer signal analysis. In this paper, the music signal is first decomposed into approximation and detail coefficients using WPT with the best basis algorithm to minimize the Shannon entropy and maximize the representation of music signal. This paper uses the Top-Down search strategy with cost function to select the best basis. Then the proposed method could apply support vector machine (SVM) to build a music genre classifier using the mel-frequency cepstral coefficients (MFCC) and log energies extracted from the decomposition coefficients of WPT with the best basis algorithm. Finally one can perform music genre classification with the built music genre classifier. Experiments conducted on three different music datasets have shown that the proposed method can achieve higher classification accuracy than other music genre classification methods with the same experimental setup.

In this study, an efficient and fast algebraic decoding algorithm (ADA) for the binary systematic quadratic residue (QR) code of length 73 with the reducible generator polynomial to correct up to six errors is proposed. The S(I, J) matrix method given by He et al. (2001) is utilised to compute the unknown syndromes S5. A technique called swap base is proposed to correct the weight-4 error patterns. To correct the weight-5 error patterns, the new error-locator polynomials for decoding the five errors are derived. Finally, the modified shift-search algorithm (SSA) developed by Lin et al. (2010) is applied to correct the weight-6 error patterns. Moreover, the computations of all syndromes are achieved in a small finite field. Simulation results show that the proposed ADA is practical.

A general algorithm for decoding the binary systematic quadratic residue (QR) codes with lookup tables is presented in this study. The algorithm can be applied in decoding the QR codes with either reducible or irreducible generator polynomials. If the generator polynomial of the QR codes is reducible, the number of elements in the Galois field is less than the sum of all correctable error patterns. In other words, the mapping between elements of syndrome set and all correctable error patterns is not one to one. The key idea of decoding based on the mapping between the ordered q-tuples of the primary known syndrome and error patterns is one to one. In addition, the algorithm directly determines the error locations by lookup tables without the operations of multiplication over a finite field. According to the simulation result, the new lookup table decoding algorithm for the (31, 16, 7) QR code and the (73, 37, 13) QR code dramatically reduces the memory required by approximately 90 and 92%, respectively. Moreover, the high speed of decoding procedure could be utilised in modern communication system.

A new decoder is proposed to decode the (23, 12, 7) binary Golay-code up to five errors. It is based on the algorithm that can correct up to four errors for the (24, 12, 8) extended Golay-code proposed by Lin et al., thereby achieving the soft decoding in the real sense for the Golay-code. For a weight-2 or weight-3 error pattern decoded by the hard decoder for correcting up to three errors, one can find the corresponding 21 weight-4 or weight-5 error patterns and choose the one with the maximum emblematic probability value, which is defined as the product of individual bit-error probabilities corresponding to the non-zero locations of the error pattern as the ultimate choice. Finally, simulation results of this decoder over additive white Gaussian noise (AWGN) channels show that the proposed method provides 0.9 dB coding gain than that of Lin et al.'s algorithm at bit-error rate of 10−5.

It is well-known that the Euclidean algorithm can be used o find the systematic errata-locator polynomial and the errata-evaluator polynomial simultaneously in Berlekamp's key equation that is needed to decode a Reed-Solomon (RS) codes. In this paper, a simplified decoding algorithm to correct both errors and erasures is used in conjunction with the Euclidean algorithm for efficiently decoding nonsystematic RS codes. In fact, this decoding algorithm is an appropriate modification to the algorithm developed by Shiozaki and Gao. Based on the ideas presented above, a fast algorithm described from Blahut's classic book is derivated and proved in this paper to correct erasures as well as errors by replacing the Euclidean algorithm by the Berlekamp-Massey (BM) algorithm. These facts lead to significantly reduce the decoding complexity of the proposed RS decoder. In addition, computer simulations show that this simple and fast decoding technique reduces the decoding time when compared with existing efficient algorithms including the new Euclidean-algorithm-based decoding approach proposed in this paper.

Recently, the general error locator polynomials have been widely used in the algebraic decoding of binary cyclic codes. This paper utilizes the proposed general error locator polynomial to develop an algebraic decoding algorithm for a class of the binary cyclic codes. This general error locator polynomial differs greatly from the previous general error locator polynomial. Each coefficient of the proposed general error locator polynomial is expressed as a binary polynomial in the single syndrome and the degrees of nonzero terms in the binary polynomial satisfy at least one congruence relation.

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 paper, a new soft-decision decoder of the (24, 12, 8) binary extended Golay code up to six errors is proposed. First, by using the error pattern obtained from hard decoder, the method of determining possible error patterns is developed. The emblematic probability value of each error pattern is then defined as the product of the individual bit-error probabilities corresponding to the locations of the possible error patterns. The most likely one among these error patterns is obtained by choosing the maximum of the emblematic probability values of possible error patterns. Finally, simulation results in additive white Gaussian noise (AWGN) show that this decoder reduce the decoding complexity although it performs a slight loss of coding gain than the modified Chase's II algorithm proposed by Hackett.

Binary quadratic residue (QR) codes, which have code rates greater than or equal to 1/2 and generally have large minimum distances, are among the best known codes. This paper considers a modified algebraic decoding algorithm for the (89,45,17) binary QR code that utilizes the Berlekamp-Massey algorithm. It identifies the primary unknown syndromes and provides methods to determine these on a case-by-case basis for any number of correctable errors. Numerical evaluation shows that the proposed algorithm significantly reduces at least 52% of decoding time for two or more errors.

A new decoder is proposed to decode the (24, 12, 8) binary extended Golay code up to four errors. It consists of the conventional hard decoder for correcting up to three errors, the detection algorithm for four errors and the soft decoding for four errors. For a weight-4 error in a received 24-bit word, Method 1 or 2 is developed to determine all six possible error patterns. The emblematic probability value of each error pattern is then defined as the product of four individual bit-error probabilities corresponding to the locations of the four errors. The most likely one among these six error patterns is obtained by choosing the maximum of the emblematic probability values of all possible error patterns. Finally, simulation results of this decoder in additive white Gaussian noise show that at least 93% and 99% of weight-4 error patterns that occur are corrected if the two Eb/N0 ratios are greater than 2 and 5 dB, respectively. Consequently, the proposed method can achieve a better percentage of successful decoding for four errors at variable signal-to-noise ratios than Lu et al.'s algorithm in software. However, the speed of the method is slower than Lu et al.'s algorithm.

A new algorithm is developed to facilitate faster decoding of the (47,24,11) quadratic residue (QR) code. This decoder, based on the idea first developed by Reed in a 1959 MIT Lincoln Laboratory Report, uses real channel data to estimate the individual bit-error probabilities in a received word. The algorithm then sequentially inverts the bits with the highest probability of error until one of the errors is canceled. The remaining errors are then corrected by the use of algebraic decoding techniques. This new algorithm, called the reliability-search algorithm, is a complete decoder that significantly reduces the decoding complexity in terms of CPU time while maintaining the same bit-error rate (BER) performance. In fact, this algorithm is an appropriate modification to the algorithm developed by Chase.

Gao's algorithm similar to Shiozaki's algorithm for decoding nonsystematic Reed-Solomon (RS) codes which is a subclass of the redundant residue polynomial codes is considered here. This algorithm computes the message polynomial directly without explicitly finding the error-locator polynomial and errorevaluator polynomial. In this letter, a simplified decoding algorithm to correct both errors and erasures is used in conjunction with Gao's algorithm for efficiently decoding RS codes. In addition, we show that the extended Gao algorithm similar to the Shiozaki-Truong-Cheung-Reed algorithm significantly reduces the decoding complexity.

This letter proposes a novel scheme which consists of a weight-counting algorithm, the combinatorial designs of the Assmus-Mattson theorem, and the weight polynomial of Gleason's theorem to determine the weight distributions of binary extended quadratic residue codes. As a consequence, the weight distributions of binary (138, 69, 22) and (168, 84, 24) extended quadratic residue codes are given.

This paper proposes a novel scheme which consists of a weight-counting algorithm, the combinatorial designs of the Assmus-Mattson theorem, and the weight polynomial of Gleason’s theorem to determine the weight distributions of binary extended quadratic residue codes. As a consequence, the weight distribution of binary (168, 84, 24) extended quadratic residue code is given.

Recently, an algebraic decoding algorithm suggested by Truong (2005) for some quadratic residue codes with irreducible generating polynomials has been designed that uses the inverse-free Berlekamp-Massey (BM) algorithm to determine the error-locator polynomial. In this paper, based on the ideas of the algorithm mentioned above, an algebraic decoder for the (89, 45, 17) binary quadratic residue code, the last one not decoded yet of length less than 100 , is proposed. It was also verified theoretically for all error patterns within the error-correcting capacity of the code. Moreover, the verification method developed in this paper can be extended for all cyclic codes without checking all error patterns by computer simulations.

In this paper, Fedorenko and Trifonov's procedure is applied to evaluate the syndrome of the received word in time-domain Reed-Solomon decoders. This application leads to a substantial reduction of the computational complexity of the syndrome polynomial for correcting both errors and erasures. Moreover, simulation results for this new syndrome method are given.

In this paper, there are 17 types of wavelet coefficients obtained from the Matlab software and an Aurora-2 database used to evaluate which wavelet type has a better accuracy in speaker recognition. We first determine the frequency cepstral coefficient (FCC) level to form a 114-dimentional feature vector by the use of Daubechies-4 wavelet and support vector machines (SVMs) with pre-selected exponential radial basis kernel function (ERBF) and under some additional conditions. Then, average, for each wavelet, the accuracy of 42 possible combinations about the gender of speakers considered in seven kinds of experiments corresponding to two to eight speakers. The experimental results show that the best accuracy in average will be achieved by using the reverse biorthogonal-3.5 or reverse biorthogonal-3.7 wavelet. The reverse biorthogonal-3.5 wavelet is then chosen to be the proposed wavelet function for speaker recognition in terms of shorter filter length

This paper proposes an improved DCT-based image codec embedded cubic spline interpolation (CSI) with optimal quantization. It is shown in literature that CSI is superior in performance to the other interpolation functions. One of main applications of the CSI is to cooperate with standard DCT-based JPEG to obtain the modified JPEG codec and still obtain a better quality of the reconstructed image for higher compression ratios. This paper shows that the compression performance of such a modified JPEG codec can be further improved by the use of optimal quantization. The optimal quantization makes use of the rate distortion optimization algorithm to measure DCT coefficient statistic for an image generated from the CSI scheme and then construct a DCT quantization table for the given rate/distortion specification. Experimental results show that the proposed optimal quantization can achieve a better PSNR than that of the modified JPEG codec with a default quantization table

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, an improved audio classification and categorization technique is presented. This technique makes use of wavelets and support vector machines (SVMs) to accurately classify and categorize audio data. When a query audio is given, wavelets are first applied to extract acoustical features such as subband power and pitch information. Then, the proposed method uses a bottom-up SVM over these acoustical features and additional parameters, such as frequency cepstral coefficients, to accomplish audio classification and categorization. A public audio database (Muscle Fish), which consists of 410 sounds in 16 classes, is used to evaluate the performances of the proposed method against other similar schemes. Experimental results show that the classification errors are reduced from 16 (8.1%) to six (3.0%), and the categorization accuracy of a given audio sound can achieve 100% in the Top 2 matches.

In this paper, two algebraic decoders for the (103, 52, 19) and (113, 57, 15) quadratic residue codes, which have lengths greater than 100, are presented. The results have been verified by software simulation that programs in C++ language have been executed to check possible error patterns of both quadratic residue codes.

The weight distributions of binary quadratic residue codes C can be computed from the weight distribution of a subset of C containing one-fourth (resp., one-eighth) of the codewords in C when the length of the code is congruent to 1 (resp., -1) modulo 8. An algorithm to determine the weight distributions of binary cyclic codes is given. As a consequence, the weight distributions of (73,37,13), (89,45,17), and (97,49,15) quadratic residue codes are determined precisely.

Based on a cross-zonal filter in the two-dimensional (2-D) cubic-spline interpolation (CSI) and a symmetric extension method, an efficient algorithm is proposed for image coding. Experimental results show that the proposed method is superior in performance and yields a better quality of reconstructed image than other interpolation methods.

An algebraic decoding method is proposed for the quadratic residue codes that utilize the Berlekamp-Massey (BM) algorithm. By applying a technique developed by R. He et al. (see IEEE Trans. Inf. Theory, vol.47, p.1181-6, 2001), one can express unknown syndromes as functions of known syndromes. An efficient algorithm is also developed to determine the unknown syndromes. With the appearance of unknown syndromes, one obtains the consecutive syndromes that are needed for the application of the inverse-free BM algorithm. The new decoding scheme can be used to implement the (79,40,15) quadratic residue (QR) code which has not been treated so far. It is verified by a computer program that uses the C++ language.

Recently, a new algebraic decoding algorithm for quadratic residue (QR) codes was proposed by Truong et al. Using that decoding scheme, we now develop three decoders for the QR codes with parameters (71, 36, 11), (79, 40, 15), and (97, 49, 15), which have not been decoded before. To confirm our results, an exhaustive computer simulation has been executed successfully.

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.

In digital system development, the CPLD/FPGA is usually used to implement basic function blocks for the purposes of testing, integration and IP proof. The advantages of CPLD/FPGA are high efficiency, flexibility and easy reconfiguration. Taking AES as an example, this application needs more flexible transformations to design for diversity. In order to meet such requirements without declining the performance, a modified architecture of FPGA is proposed to increase the overall efficiency and keep high throughput. A finite field multiplier is provided for the explanation of the newly developed core. The parallel and pipelined design in FPGA can replace high-speed VLSI chip with dynamic reconfigurability.

In the applications of AES, the long-term robustness/reliability during the period of operation should be taken into serious considerations. From such considerations, one may initiate the requirements of the design for diversity against break through from outside. In system design, the use of reconfigurable FPGA can provide higher level of flexibility. In this paper, the proposed system uses different generators, various transforms, modules and algorithms to enhance the randomization of the ciphertext. It is also a challenge to improve the system flexibility and to get a more secure design in the AES system. Several reconfigurable modules are developed on our integrated test-bench.

A recursive linear detection algorithm is proposed for the detection of signals from an asynchronous direct-sequence code-division multiple-access (DS-CDMA) communication system. This algorithm works for short as well as long codes. Under some reasonable conditions, this algorithm is proved to be stable and converges to the ideal decorrelating detector (IDD) with a sufficiently large memory length. The performance of the algorithm is analyzed in some detail. Upper and lower bounds for the bit-error probabilities are developed. It is demonstrated that the two bounds converge to the bit-error probabilities of the IDD as the large memory length increases. Simulation results show that the recursive detector proposed outperforms the truncated decorrelating detector with less memory and less computational complexity.

The central problem in the implementation of a Reed-Solomon code is finding the roots of the error locator polynomial. In 1967, Berlekamp et al. found an algorithm for finding the roots of an affine polynomial in GF(2/sup m/) that can be used to solve this problem. In this paper, it is shown that this Berlekamp-Rumsey-Solomon (1967) algorithm, together with the Chien (1964) search method, makes possible a fast decoding algorithm in the standard-basis representation that is naturally suitable in a software implementation. Finally, simulation results for this fast algorithm are given.

The techniques needed to decode the (47,24,11) quadratic residue (QR) code differ from the schemes developed for cyclic codes. By finding certain nonlinear relations between the known and unknown syndromes for this special code, two methods are developed to decode up to the true minimum distance of the (47,24,11) QR code. These algorithms can be utilized to decode effectively the 1/2 -rate (48,24,12) QR code for correcting five errors and detecting six errors.

In this paper, a fast encoding algorithm is developed for fractal image compression. At each search entry in the domain pool, the mean square error (MSE) calculations of the given range block and the eight dihedral symmetries of the domain block are obtained simultaneously in the frequency domain, in which the redundant computations are all eliminated in the new encoding algorithm. It is shown in software simulation that the encoding time is about six times faster than that of the baseline method with almost the same PSNR for the retrieved image. The fast algorithm is performed to deal with the eight dihedral symmetries at each search entry. Therefore, it can be applied to various enhanced algorithms which are equipped with quadtree, classification, and other mechanisms.

A new cubic convolution spline interpolation (CCSI )for both one-dimensional (1-D) and two-dimensional (2-D) signals is developed in order to subsample signal and image compression data. The CCSI yields a very accurate algorithm for smoothing. It is also shown that this new and fast smoothing filter for CCSI can be used with the JPEG standard to design an improved JPEG encoder-decoder for a high compression ratio.

In a previous article by Truong et al. (see ibid., vol.46, p.973-76, 1998), it was shown that an inverse-free Berlekamp-Massey (1968, 1969) algorithm can be generalized to find the error locator polynomial in a Reed-Solomon (RS) decoder for correcting errors as well as erasures. The basic idea of this procedure is the replacement of the initial condition of an inverse-free BM algorithm by the Forney (1965) syndromes. It is shown that the errata locator polynomial can be obtained directly by initializing an inverse-free BM algorithm with the erasure locator polynomial and the syndromes. An important ingredient of this new algorithm is a modified BM algorithm for computing the errata locator polynomial. As a consequence, the separate computation of the erasure locator polynomial and the Forney syndrome, needed in the decoder developed by Truong et al., are completely avoided in this modification of the BM algorithm. This modified algorithm requires fewer finite field addition and multiplication operations than the previous algorithm. Finally, the new decoding method was implemented on a computer using C++ language. It is shown in a simulation that the speed of this new decoder is faster than the decoder developed by Truong et al. An example using this program is given for an (255, 239) RS code for correcting errors and erasures with 2/spl nu/+s/spl les/10.

Previously, the authors proposed an inverse-free Berlekamp-Massey (1968, 1969) algorithm to simplify the Reed-Solomon (RS) codes. This modified RS decoding method is the best known technique for finding the error locator polynomial. The inverse-free method is generalized to find both errors and erasures. The basic idea of the new procedure is the replacement of the initial condition of the BM algorithm by the Forney (1965) syndromes. With this improved technique, the complexity of time-domain RS decoders for correcting both errors and erasures is reduced substantially from previous approaches.

Fractional Brownian motion (fBm) provides a useful model for processes with strong long-term dependence, such as 1/f/sup /spl beta// spectral behavior. However, fBm's are nonstationary processes so that the interpretation of such a spectrum is still a matter of speculation. To facilitate the study of this problem, another model is provided for the construction of fBm from a white-noise-like process by means of a stochastic or Ito integral in frequency of a stationary uncorrelated random process. Also a generalized power spectrum of the nonstationary fBm process is defined. This new approach to fBm can be used to compute all of the correlations, power spectra, and other properties of fBm. In this paper, a number of these fBm properties are developed from this model such as the T/sup H/ law of scaling, the power law of fractional order, the correlation of two arbitrary fBm's, and the evaluation of the fractal dimension under various transformations. This new treatment of fBm using a spectral representation is extended also, for the first time, to two or more topological dimensions in order to analyze the features of isotropic n-dimensional fBm.>

It is shown that any Reed-Solomon (RS) decoder which corrects both errors and erasures also can be used as an encoder for the RS code. This technique eliminates the need of a separate subsystem, namely the RS encoder in either two-way digital communication systems or storage devices which use RS encoding and decoding. As a consequence a single RS decoder chip which corrects both errors and erasures can be mass-manufactured for use in all two-way communication systems and storage devices such as a digital video-cassette recorder (VCR) or a write-once, read-many, (WORM) optical disk drive.>

This paper provides two theorems for decoding all types of cyclic codes. It is shown that from a polynomial ideal point of view, the decoding problems of cyclic codes are closely related to the monic generators of certain polynomial ideals. This conclusion is also generalized to the decoding problems of algebraic geometry codes.>

A general algebraic method for decoding all types of binary cyclic codes is presented. It is shown that such a method can correct t=[(d-1)/2] errors, where d is the true minimum distance of the given cyclic code. The key idea behind this decoding technique is a systematic application of the algorithmic procedures of Grobner bases to obtain the error-locator polynomial L(z). The discussion begins from a set of syndrome polynomials F and the ideal T(F) generated by F. It is proved here that the process of transforming F to the normalized reduced Grobner basis of I(F) with respect to the "purely lexicographical" ordering automatically converges to L(z). Furthermore, it is shown that L(z) can be derived from any normalized Grobner basis of I(F) with respect to any admissible total ordering. To illustrate this new approach, the procedures for decoding certain BCH codes and quadratic residue codes are demonstrated.>

The 1/2-rate binary quadratic residue (QR) codes, using binary phase-shift keyed (BPSK) modulation and hard decoding, are presented as an efficient system for reliable communication. Performance results of error correction are obtained both theoretically and by means of computer calculations for a number of binary QR codes. These results are compared with the commonly used 1/2-rate convolutional codes with constraint lengths from 3 to 7 for the hard-decision case. The binary QR codes of different lengths are shown to be equivalent in error-correction performance to some 1/2-rate convolutional codes, each of which has a constraint length K that corresponds to the error-control rate d/n and the minimum distance d of the QR codes.>

The class of binary quadratic residue (QR) codes of length n=8m-1 contains two perfect codes. These are the (7,4,3) Hamming code and the (23,12,7) Golay code. However, it is proved in the present paper that there are no quasi-perfect QR codes of length 8m-1. Finally, this result is generalized to all binary self-dual codes of length N>72.>

A systolic Viterbi decoder for convolutional codes is developed which uses the trace-back method to reduce the amount of data needed to be stored in registers. It is shown that this new algorithm requires a smaller chip size and achieves a faster decoding time than other existing methods.>

A new algebraic approach for decoding the quadratic residue (QR) codes, in particular the (41, 21, 9) QR code, is presented. The key ideas behind this decoding technique are a systematic application of the Sylvester resultant method to the Newton identities associated with the syndromes to find the error-locator polynomial, and next a method for determining error locations by solving certain quadratic, cubic, and quartic equations over GF(2/sup m/) in a new way which uses Zech's logarithms for the arithmetic. The logarithms developed for Zech's logarithms save a substantial amount of computer memory by storing only a table of Zech's logarithms. These algorithms are suitable for implementation in a programmable microprocessor or special-purpose VLSI chip. It is expected that the algebraic methods developed can apply generally to other codes such as the BCH and Reed-Solomon codes.>

The arithmetic Fourier transform (AFT) is a number-theoretic approach to Fourier analysis which has been shown to perform competitively with the classical fast Fourier transform (FFT) in terms of accuracy, complexity and speed. Theorems developed previously for the AFT algorithm are used to derive the original AFT algorithm which Bruns found in 1903. This is shown to yield an algorithm of less complexity and of improved performance over certain recent AFT algorithms. A computationally balanced AFT algorithm for Fourier analysis and signal processing is developed. This algorithm does not require complex multiplications. A VLSI architecture is suggested for this amplified AFT algorithm. This architecture uses a butterfly structure which reduces the number of additions by 25% over that used by the direct method. This efficient AFT algorithm is shown to be identical to Brun's original AFT algorithm.>

An algebraic decoding algorithm for the 1/2-rate (32, 16, 8) quadratic residue (QR) code is found. The key idea of this algorithm is to find the error locator polynomial by a systematic use of the Newton identities associated with the code syndromes. The techniques developed extend the algebraic decoding algorithm found recently for the (32, 16, 8) QR code. It is expected that the algebraic approach developed here and by M. Elia (1987) applies also to longer QR codes and other BCH-type codes that are not fully decoded by the standard BCH decoding algorithm.>

The authors describe the VLSI implementation of a general sidelobe cancellor (GSC) using powers-of-two arithmetic. The chip needed for this design carries six multiplications and seven additions. The layout of this chip is based on the standard cell and regular structure approach. To reduce the propagation delay of its carry-save addition unit, a fast ripple carry adder which has a single NAND gate delay for carry propagation is designed. This adder is designed to reduce the propagation delay of carries by a factor of two.>

Three different finite-field multipliers are presented: (1) a dual-basis multiplier due to E.R. Berlekamp (1982); the Massey-Omura normal basis multiplier; and (3) the Scott-Tavares-Peppard standard basis multiplier. These algorithms are chosen because each has its own distinct features that apply most suitably in particular areas. They are implemented on silicon chips with NMOS technology so that the multiplier most desirable for VLSI implementation can readily be ascertained.>

A conventional prime factor discrete Fourier transform (DFT) algorithm of the Winograd type is used to realize a discrete Fourier-like transform on the finite field GF(q/sup /n). A pipeline structure is used to implement this prime-factor DFT over GF(q/sup /n). This algorithm is developed to compute cyclic convolutions of complex numbers and to aid in decoding the Reed-Solomon codes. Such a pipeline fast prime-factor DFT algorithm over GF(q/sup /n) is regular, simple, expandable, and naturally suitable for most implementation technologies. An example illustrating the pipeline aspect of a 30-point transform over GF(q/sup /n) is presented.>

A quadratic-polynomial Fermat residue number system (QFNS) can be used to compute the complex multiplications needed to perform a DFT. The advantage of such a QFNS is that complex multiplication can be accomplished with only two integer multiplications. In this paper, it is shown that a new set of numbers of the form Tn = 22n + 1 can be used in place of the set of Fermat numbers. This new quadratic residue number system can be used also to compute a complex multiplication with only two integer multiplications.

A new VLSI design of a pipeline Reed-Solomon decoder is presented. The transform decoding technique used in a previous design is replaced by a simple time domain algorithm. A new architecture which realizes such algorithm permits efficient pipeline processing with a minimum of circuits. A systolic array is also developed to perform erasure corrections in the new design. A modified form of Euclid's algorithm is developed with a new architecture which maintains a real-time throughput rate with less transistors. Such improvements results in both an enhanced capability and significant reduction in silicon area, thereby making it possible to build a pipeline (255,223) RS decoder on a single VLSI chip.

In this paper a recursive algorithm using the error-trellis decoding technique is developed to decode certain convolutional codes (CC's). An example, illustrating the VLSI architecture of such a decoder, is given for a dual-k CC. It is demonstrated that such a decoder can be realized readily on a single chip with NMOS technology.

In this correspondence, the complex integer multiplier and adder over the direct sum of two copies of finite field developed in [1] is specialized to the direct sum of the rings of integers modulo Fermat numbers. Such multiplication over the rings of integers modulo Fermat numbers can be performed by means of two integer multiplications, whereas the complex integer multiplication requires three integer multiplications. Such multiplications and additions can be used in the implementation of a discrete Fourier transform (DFT) of a sequence of complex numbers. The advantage of the present approach is that the number of multiplications needed to compute a systolic array of the DFT can be reduced substantially. The architectural designs using this approach are regular, simple, expandable and, therefore, naturally suitable for VLSI implementation.

Multiplication is central in the implementation of Fermat number transforms (FNT) and other residue number algorithms. There is need for a good multiplication algorithm which can be realized easily on a VLSI chip. In this paper, the Leibowitz multiplier [1] is modified to realize multiplication in the ring of integers modulo a Fermat number. The advantage of this new algorithm over Leibowitz's algorithm is that Leibowitz's algorithm takes modulo after the product of multiplication is obtained. Hence time is wasted. In this new algorithm, modulo is taken in every bit operation when performing multiplication. Therefore no time is wasted in this respect. Furthermore, this algorithm requires only a sequence of cyclic shifts and additions. The design for this new multiplier are regular, simple, expandable and therefore, suitable for VLSI implementation.

Multiplication is central in the implementation of Fermat Number Transforms (FNT) and other residue number algorithms. There is need for a good multiplication algorithm which can be realized easily on a VLSI chip. In this paper, the Leibowitz multiplier [1] is modified to realize multiplication in the ring of integers modulo a Fermat number. The advantage of this new algorithm over Leibowitz's algorithm is that Leibowitz's algorithm takes modulo after the product of multiplication is obtained. Hence time is wasted. In this new algorithm, modulo is taken in every bit operation when performing multiplication. Therefore no time is wasted in this respect. Furthermore, this algorithm requires only a sequence of cyclic shifts and additions. The design for this new multiplier are regular, simple, expandable and therefore, suitable for VLSI implementation.

A pipeline structure of a transform decoder similar to a systolic array is developed to decode Reed-Solomon (RS) codes. The error locator polynomial is computed by a modified Euclid's algorithm which avoids computing inverse field elements. The new decoder is regular and simple, and naturally suitable for VLSI implementation.

A pipeline structure of a transform decoder similar to a systolic array is developed to decode Reed-Solomon (RS) codes. An important ingredient of this design is a modified Euclidean algorithm for computing the error-locator polynomial. The computation of inverse field elements is completely avoided in this modification of Euclid's algorithm. The new coder is regular and simple, and naturally suitable for VLSI implementation. An example illustrating both the pipeline and systolic array aspects of this decoder structure is given for a RS code.

Finite field arithmetic logic is central in the implementation of Reed-Solomon coders and in some cryptographic algorithms. There is a need for good multiplication and inversion algorithms that can be easily realized on VLSI chips. Massey and Omura recently developed a new multiplication algorithm for Galois fields based on a normal basis representation. In this paper, a pipeline structure is developed to realize the Massey-Omura multiplier in the finite field GF(2m). With the simple squaring property of the normal basis representation used together with this multiplier, a pipeline architecture is developed for computing inverse elements in GF(2m). The designs developed for the Massey-Omura multiplier and the computation of inverse elements are regular, simple, expandable, and therefore, naturally suitable for VLSI implementation.

This paper discusses the VLSI design of a sub-band coder for speech. The focus is upon the architecture for the sub-band filters. A parallel and pipelined architecture is developed using Fermat number transforms which is regular, simple and suitable for VLSI. Considerations for the rest of the coder are also discussed.

Berlekamp has developed for the California Institute of Technology Jet Propulsion Laboratory (JPL) a bit-serial multiplication algorithm for the encoding of Reed-Solomon (RS) codes, using a dual basis over a Galois field. The conventional RS encoder for long codes often requires lookup tables to perform multiplication of two field elements. Berlekamp's algorithm requires only shifting and EXCLUSIVE OR operations. It is shown in this paper that the new dual-basis (255,223) RS encoder can be realized readily on a single VLSI chip with NMOS technology.

Two systolic architectures are developed for performing the product–sum computation AB + C in the finite field GF(2m) of 2melements, where A, B, and C are arbitrary elements of GF(2m). The first multiplier is a serial-in, serial-out one-dimensional systolic array, while the second multiplier is a parallel-in, parallel-out two-dimensional systolic array. The first multiplier requires a smaller number of basic cells than the second multiplier. The second multiplier heeds less average time per computation than the first multiplier if a number of computations are performed consecutively. To perform single computations both multipliers require the same computational time. In both cases the architectures are simple and regular and possess the properties of concurrency and modularity. As a consequence they are well suited for use in VLSI systems.

In this paper a parallel architecture is developed to realize a digital filter. First a systolic array is used to compute a 248-point complex number-theoretic transform (CNT). Next an algorithm is developed to realize a digital filter that uses 248-point CNT's and a generalization of the overlap-save method. This algorithm solves the conflict between long transform lengths and a wide dynamic range associated with the number-theoretic transform. Finally this algorithm is mapped to a parallel architecture. This architecture is simple, regular and expandable, and, hence, is suitable for VLSI implementation.

In this paper, a parallel-pipeline, radix-2 architecture is proposed to implement the fast polynomial transform (FPT). It is shown that such a structure can be used to efficiently compute a two-dimensional convolution of d1× d2complex number points, where d1 = 2m-r+1and d2= 2mfor 1 ≤ r ≤ m.

In this correspondence, a parallel architecture is developed to compute the linear convolution of two sequences of arbitrary lengths using the Fermat number transform (FNT). In particular, a pipeline structure is designed to compute a 128-point FNT. In this FNT, only additions and bit rotations are required.

Recently,1 the authors proposed a hybrid algorithm for computing the discrete Fourier transform (DFT) of certain long transform lengths. In that technique, a Winograd-type algorithm was used in conjunction with the Mersenne prime-number theoretic transform to perform a DFT. Even though this technique requires fewer multiplications than either the standard fast Fourier transform (FFT) or Winograd's more conventional algorithm, it increases the number of additions considerably. In this letter it is proposed to use Winograd's algorithm for computing the Mersenne prime-number theoretic transform in the transform portion of the hybrid algorithm. It is shown that this can reduce significantly the number of additions while still maintaining about the same number of multiplications.

In this paper for certain long transform lengths, Winograd's algorithm for computing the discrete Fourier transform (DFT) is extended considerably. This is accomplisbed by performing the cyclic convolution, required by Winograd's method, with the Mersenne prime number-theoretic transform developed originally by Rader. This new algorithm requires fewer multiplications than either the standard fast Fourier transform (FFT) or Winograd's more conventional algorithm. However, more additions are required.

It is shown that Reed-Solomon (RS) codes can be decoded by using a fast Fourier transform (FFT) algorithm over finite fieldsGF(F_{n}), whereF_{n}is a Fermat prime, and continued fractions. This new transform decoding method is simpler than the standard method for RS codes. The computing time of this new decoding algorithm in software can be faster than the standard decoding method for RS codes.

It is shown that\sqrt\[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Since\sqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, where\sqrt{2}is inGF(F_{2})=GF(17), is given.

A transform analogous to the discrete Fourier transform is defined on the Galois field GF(p), where p is a prime of the form k X 2n + 1, where k and n are integers. Such transforms offer a substantial variety of possible transform lengths and dynamic ranges. The fast Fourier transform (FFT) algorithm of this transform is faster than the conventional radix-2 FFT. A transform of this type is used to filter a two-dimensional picture (e.g., 256 X 256 samples), and the results are presented with a comparison to the standard FFT. An absence of roundoff errors is an important feature of this technique.

It is shown that a high-radix fast Fourier transform (FFT) with generator\gamma = 3over GF(F_{n}), whereF_{n} = 2^{2}^{n'} + 1is a Fermat prime, can be used for encoding and decoding of Reed-Solomon (RS) codes of length2^{2}^{n}. Such an RS decoder is considerably faster than a decoder using the usual radix 2 FFT. This technique applies most ideally to a 16-error-correcting, 256-symbol RS code of 8 bits being considered currently for space communication applications. This special code can be encoded and decoded rapidly using a high-radix FFT algorithm over GF(F_{3}).

A Fourier-like transform is defined over a ring of quadratic integers modulo a prime numberqin the quadratic fieldR(\sqrt{m}), wheremis a square-free integer. Ifqis a Fermat prime, one can utilize the fast Fourier transform (FFT) algorithm over the resulting finite fields to yield fast convolutions of quadratic integer sequences inR(\sqrt{m}). The theory is also extended to a direct sum of such finite fields. From these results, it is shown that Fourier-like transforms can also be defined over the quadratic integers inR( \sqrt{m})modulo a nonprime Fermat number.

A transform is defined in the Galois field ofq^2elementsGF(q^2), a finite field analogous to the field of complex numbers, whenqis a prime such that (--1) is not a quadratic residue. It is shown that the action of this transform overGF(q^2)is equivalent to the discrete Fourier transform of a sequence of complex integers of finite dynamic range. Ifqis a Mersenne prime, one can utilize the fast Fourier transform (FFT) algorithm to yield a fast convolution without the usual roundoff problem of complex numbers.

In this paper, the dynamic range of Fourier-like transforms over the Galois fieldGF(q^2), whereqis a Mersenne prime, is extended. It is shown that transforms over a direct sum of such Galois fields can be used to compute quite accurately discrete Fourier transforms of complex numbers without roundoff error.