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 Bose-Chaudhuri-Hocquenghem (BCH) is called quasi-reversible if there are consecutive elements a1,⋯,a2in the defining set, where a1is a negative integer and a2is a positive integer. A matrix in band form presented in this article involves the use of the Newton identities and symmetric polynomial identities. This matrix is the coefficient matrix of a linear system. The solution to such a linear system is the coefficients of an error-locator polynomial for quasi-reversible BCH codes. Its computational complexity is significantly lower than BCH decoding using the linear system with coefficient matrix in column echelon form. This article also proposes a new partial syndrome matrix with radical locators and a lot of zeros. Such a matrix is still in band form. The expansion of its matrix determinant is exactly a radical-locator polynomial. Compared to the former radical-locator polynomials in the literature, the newly discovered radical-locator polynomial not only requires less storage memory but also results in computational benefits. Surprisingly, the resulting polynomials are much sparser than those for the narrow-sense BCH codes. Finally, a complete algebraic decoding algorithm for quasi-reversible BCH codes is provided. The error-locator and radical-locator polynomials of degree less than or equal to 5 are listed.

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.

Partial syndrome matrices and weak-locator polynomials have received considerable attention in recent years due to their applications in decoding cyclic codes. The technical contribution of this paper is threefold: (1) cyclic codes can be decoded by the newly proposed partial syndrome matrices, which generalize the previously known results on the determination of error positions; (2) a new type of polynomial associated with error locations, called radical-locator polynomial, is defined, which includes the weak-locator polynomial as a special case; and (3) a novel class of matrices with many zero entries, called row-echelon partial syndrome matrices, is presented, based on the Newton identities, for efficiently decoding cyclic codes. It is also shown that the radical-locator polynomials can be obtained from the determinants of the above-mentioned (row-echelon) partial syndrome matrices.

Cyclic codes, which are an important class of error-correcting codes, have wide applications in communication systems and data storage systems. This paper defines a new type of locator polynomial, called radical-locator polynomials, for the algebraic decoding of cyclic codes. These polynomials can be obtained by expanding the determinant of a newly proposed partial syndrome matrix. The sparse representation for the resulting polynomials is theoretically demonstrated. A complete decoding algorithm for cyclic codes is also provided.

Cyclic codes have been widely used in many applications of communication systems and data storage systems. This paper proposes a new procedure for decoding cyclic codes up to actual minimum distance. The decoding procedure consists of two steps: 1) computation of known syndromes and 2) computation of error positions and error values simultaneously. To do so, a matrix whose all entries are syndromes is called syndrome matrix. A matrix whose entries are either syndromes or the elements of a finite field is said to be partial syndrome matrix. In this paper, two novel methods are presented to determine error positions and error values simultaneously and directly. The first method uses a new partial syndrome matrix along with Gaussian elimination. The partial syndrome matrices for binary (respectively, ternary) cyclic codes of lengths from 69 to 99 (respectively, 16 to 37) are tabulated. For some cyclic codes, the partial syndrome matrices contain unknown syndromes; the second method constructs a matrix from a system of equations, which is generated by the determinants of different partial syndrome matrices and makes use of Gaussian elimination to determine its row rank. Many more cyclic codes beyond the Bose-Chaudhuri-Hocquenghem bound can be decoded with these methods.

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.

Recently, the perfect Gaussian integer sequences have been widely used in modern wireless communication systems, such as code division multiple access and orthogonal frequency-division multiplexing systems. This letter presents two different methods to generate the long perfect Gaussian integer sequences with ideal periodic auto-correlation functions. The key idea of the proposed methods is to use a short perfect Gaussian integer sequence together with the polynomial or trace computation over an extension field to construct a family of the long perfect Gaussian integer sequences. The period of the resulting long sequences is not a multiple of that of the short sequence, which has not been investigated so far. Compared with the already existing methods, the proposed methods have three significant advantages that a single short perfect Gaussian integer sequence is employed, the long sequences consist of two distinct Gaussian integers, and their energy efficiency is monotone increasing.

This study extends the authors’ earlier work to show that the Gaussian integer sequences of period p m − 1 with p − 2 non‐zero out‐of‐phase autocorrelation values can be constructed from the known families of two‐tuple‐balanced p ‐ary sequences over the finite field , where p is an odd prime and m ≥ 2. The proposed Gaussian integer sequences have high energy efficiency and are superior to the perfect Gaussian integer sequences (introduced by Hu et al. in 2012) for the peak‐to‐average power ratio reduction in orthogonal frequency‐division multiplexing systems.

A complex number whose real and imaginary parts are both integers is called a Gaussian integer . A Gaussian integer sequence is said to be perfect if it has an ideal periodic autocorrelation function (PACF) where all out‐of‐phase values are zero. Further, the degree of a Gaussian integer sequence is defined as the number of distinct non‐zero Gaussian integers within one period of the sequence. Recently, the perfect Gaussian integer sequences have been found important practical applications as signal processing tools for orthogonal frequency‐division multiplexing systems. The present article generalises the authors’ earlier paper by Lee et al. (2015) related to the Gaussian integer sequences with ideal PACFs. By the applications of two‐tuple‐balanced binary sequences and cyclic difference sets, a number of new degree‐2 perfect Gaussian integer sequences with different periods are obtained.

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.

A Gaussian integer is a complex number whose real and imaginary parts are both integers. Meanwhile, a sequence is defined as perfect if and only if it has an ideal periodic autocorrelation function. This paper proposes a method for constructing sparse perfect Gaussian integer sequences (SPGISs) in which most of the sequence elements are zero. The proposed SPGISs are obtained by linearly combining four base sequences or their cyclic-shift equivalents using nonzero Gaussian integer coefficients of equal magnitudes. Each base sequence contains four nonzero elements belonging to the set {±1, ±j}. The number of nonzero elements of the constructed SPGISs depends on the choice of complex coefficients and cyclic shifts. However, each SPGIS has at most 16 nonzero elements, irrespective of the sequence length. A systematic investigation is performed into the properties of the SPGISs and their Fourier dual equivalents. Finally, a general expression is derived for a perfect Gaussian integer sequence (PGIS) of length 4n, where n is any positive integer and most of the sequence elements are nonzero.

In this letter, some perfect Gaussian integer sequences of period 2m- 1 are proposed based on the trace representations of Legendre sequences, Hall's sextic residue sequences, m-sequences, and Gordon-Mills-Welch (GMW) sequences over the finite field \BBF2m. Moreover, the energy efficiency of these sequences is approximately 1 for sufficiently large m.

A composite number can be factored into either N=mp or N=2n, where p is an odd prime and m, n ≥ 2 are integers. This paper proposes a method for constructing degree-3 and degree-4 perfect Gaussian integer sequences (PGISs) of an arbitrary composite length utilizing an upsampling technique and the base sequence concept proposed by Hu, Wang, and Li. In constructing the PGISs, the degree of the sequence is defined as the number of distinct nonzero elements within one period of the sequence. This paper commences by constructing degree-3 PGISs of odd prime length, followed by degree-2 PGISs of odd prime length. The proposed method is then extended to the construction of degree-3 and degree-4 PGISs of composite length N=mp. Finally, degree-3 and degree-4 PGISs of length N=4 are built to facilitate the construction of degree-3 and degree-4 PGISs of length N=2n, where n ≥ 3.

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.

Recently, the unified unknown syndrome representations to decode a class of binary cyclic codes have been developed by using Lagrange interpolation formula (discussed by Chang and Lee in 2010). In this study, a new method by combining the syndrome matrix search and modified Chinese remainder theorem is proposed to express the unified unknown syndrome representation as a rational function in terms of the known syndromes. A computer simulation has been executed to determine the syndrome matrices for binary cyclic codes of lengths less than or equal to 51. Compared to the Lagrange interpolation method, the method presented here substantially reduces the computational time for binary cyclic codes generated by irreducible polynomials. Finally, a complete decoding of the (31, 16, 7) quadratic residue code with inverse-free Berlekamp–Massey algorithm is given as an illustration.

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.

In this paper, three algebraic decoding algorithms are proposed for the binary quadratic residue (QR) codes generated by irreducible polynomials. The polynomial relations among the syndromes and the coefficients of the error-locator polynomials have been computed with Lagrange interpolation formula (LIF). Unlike some previous QR decoders, which may take several iterations to decode a corrupted word, the iteration number of the first two algorithms is at most one. The processes in the first algorithm are the calculation of consecutive syndromes, inverse-free Berlekamp-Massey algorithm (IFBMA), and the Chien search. One of Orsini-Sala's results on the structure of general error-locator polynomials is generalized and applied to derive the second (respectively, third) algorithm that consists of the determination of general error-locator polynomial (respectively, classical error-locator polynomials) and the Chien search. Finally, the(17, 9, 5), (23, 12, 7), and (41, 21, 9) QR decoders are illustrated and their complexity analyses are given.

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.

A new effective lookup table for decoding the binary systematic (41, 21, 9) Quadratic Residue (QR) code up to 4 errors is presented in this paper. The key ideas behind this decoding technique are based on one to one mapping between the syndromes “S1” and the error correctable patterns. Such an algorithm determines the error locations directly by lookup tables without the operations of multiplication over a finite field. Moreover, the methods to dramatically reduce the memory requirement are given. The new algorithm has been verified through a software simulation by C language. The new approach is modular, regular and naturally suitable for SOC software implementation.

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, 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.

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.