The Fast Fourier Transform (FFT) is a foundational algorithm widely used in fields like digital signal processing and machine learning. While High-Level Synthesis (HLS) tools have boosted the development of customized hardware accelerators in these fields, existing FFT HLS IP libraries often suffer from low throughput and poor usability due to inadequate exploitation of potential parallelism. In constract, many high-throughput RTL FFT designs lack portability and flexibility, limiting their practical adoption. To get rid of this predicament, we conducted an in-depth analysis of the FFT algorithm's loop structure, uncovering hierarchical parallelism to optimize performance. Based on these insights, we developed a general FFT HLS generator, HP-FFT, which supports multiple functionalities and a wide range of customizable parallelism settings to meet diverse user requirements. Experimental results demonstrate that our proposed HLS generator matches or outperforms state-of-the-art RTL/HLS IP libraries or generators, while enabling users to easily generate architectures that balance resource efficiency and high throughput to suit various application needs.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. Generalized integrated interleaved (GII) codes have an enhanced error-correction capability over an array of interleaves which are also known as component codes. With BCH component codes, the GII codes are called GII-BCH codes. The existing Chase decoding of GII-BCH codes can achieve a significant coding gain over hard-decision decoding of the codes, but at the cost of complexity. On the other aspect, the existing theoretical characterization of the codes' Chase decoding performance remains complex, and even partially numerical. This paper introduces a new theoretical characterization for Chase decoding performance of the codes, offering a simpler and computationally friendly closed form expression. Based on it, this paper further proposes a new Chase decoding method for GII-BCH codes, namely the enhanced Chase decoding (ECD). The ECD can identify the decoding rounds which are more likely to declare a decoding failure and prioritize allocating the flipped positions to them. Our simulation results show that with a similar maximum number of test-vectors, the ECD can achieve an improved performance over the existing Chase decoding.

Generalized integrated interleaved (GII) codes enable an enhanced error-correction over an array of interleaves (component codes) within a single block. Error-correction performance of GII codes can be further improved by utilizing the soft received information. The existing Chase decoding of GII-BCH codes can achieve a significant coding gain over the hard-decision decoding, but at the cost of complexity. Meanwhile, the existing theoretical characterization of its Chase decoding performance remains complex and partially empirical. This paper introduces a new theoretical characterization for Chase decoding performance of GII-BCH codes. With this characterization, it further proposes two new soft-decision decoding methods for GII-BCH codes, including the enhanced Chase decoding (ECD) and the enhanced concatenated Chase decoding (ECCD). They both identify the decoding rounds that are more likely to declare a decoding failure and prioritize allocating the flipped positions to those rounds. In particular, the latter utilizes codewords of a linear block code to cover the least reliable or the second least reliable positions, further improving the error-correction performance over the ECD. With a similar number of test-vectors, both the ECD and ECCD can outperform the existing Chase decoding for GII-BCH codes.

The state-of-the-art LZ77 compression replaces repeated occurrences of a string with references to a single copy of that string existing earlier in the uncompressed string stream. A match is encoded by a pair of numbers called a length-distance pair. To spot matches, the compressor must keep track of some amount of the most recent string, such as the last 4KB, 8KB, or 32KB. The structure in which this string is held is called a sliding window. In practice, searching for the longest string match is expedited by a hash table and a hash chain (it simply uses a hash table when only the first match is considered). In this paper, we present a novel technique to effectively improve the LZ77 compression. Specifically, it applies different sliding windows for each match length, each possibly equipped with different hashing functions. It effectively thwarts the dilemma of the original single-window, wherein a large window size renders short strings incompressible (e.g., a 2-byte match in a 16-bit window) whereas a small window size renders long strings (lying outside of window) incompressible.

Generalized integrated interleaved codes refer to two-level Reed-Solomon codes, such that each code of the nested layer belongs to different subcode of the first-layer code. In this paper, we first devise an efficient decoding algorithm by ignoring first-layer miscorrection and by intelligently reusing preceding results during each iteration of a decoding attempt. Neglecting first-layer miscorrection also enables to explicitly and neatly formulate the decoding failure probability. We next derive an erasure correcting algorithm for redundant arrays of independent disks systems. We further construct an algebraic systematic encoding algorithm, which had been open. Analogously, we propose a novel generalized integrated interleaving scheme over binary Bose-Chaudhuri-Hocquenghem codes, reveal a lower bound on the minimum distance, and derive a similar encoding and decoding algorithm as those of Reed-Solomon codes.

Tang and Koetter proposed generalized integrated interleaved Reed-Solomon codes in which each code of the second layer belongs to different subcode of the first layer code. However, the original scheme is inapplicable to binary BCH codes since its integrating coefficients are general finite field elements. In this work we propose a novel generalized integrated interleaving scheme over binary BCH codes, derive a lower bound on the minimum distance, and further present an algebraic encoding and decoding algorithm.

In this paper, we devise new scalable decoder architectures for Reed-Solomon (RS) codes, comprising three parts: error-only decoding, error-erasure decoding, and their decoding for singly extended RS codes. New error-only decoders are devised through algorithmic transformations of the inversionless Berlekamp-Massey algorithm (IBMA). We first generalize the Horiguchi-Koetter formula to evaluate error magnitudes using the error locator polynomial Λ(x) and the auxiliary polynomial B(x) produced by IBMA, which effectively eliminates the computation of error evaluator polynomial. We next devise an enhanced parallel inversionless Berlekamp-Massey algorithm (ePIBMA) that effectively takes advantage of the generalized Horiguchi-Koetter formula. The derivative ePIBMA architecture requires only 2t + 1 (t denotes the error correction capability) systolic cells, in contrast with 3t or more cells of the existing regular architectures based on IBMA or the Euclidean algorithm. Moreover, it may literally function as a linear-feedback-shift-register encoder. New error-erasure decoders are devised through algorithmic transformations of the inversionless Blahut algorithm (IBA). The proposed split parallel inversionless Blahut algorithm (SPIBA) yields merely 2t + 1 systolic cells, which is the same number as the error-only decoder ePIBMA. The task is partitioned into two separate steps, computing the complementary errorerasure evaluator polynomial followed by computing error-erasure locator polynomial, both utilizing SPIBA. Surprisingly, it has exactly the same number of cells and literally the same complexity and throughput as the proposed error-only decoder architecture ePIBMA; it employs 33% less hardware and at the same time achieves more than twice faster throughput, than the serial architecture IBA. we further propose a unified parallel inversionless Blahut algorithm (UPIBA) by incorporating the key virtues of the error-only decoder ePIBMA into SPIBA. The complexity and throughput of the rderivative UPIBA architecture are literally the same as ePIBMA and SPIBA, while performing almost equally efficiently as ePIBMA on error-only decoding and as SPIBA on error-erasure decoding. UPIBA also inherits the dynamic power saving feature of ePIBMA and SPIBA. Indeed, UPIBA renders highly attractive for on-the-fly implementation of error-erasure decoding. We finally demonstrate that the proposed decoders, i.e., ePIBMA, SPIBA, and UPIBA, can be magically migrated to decode singly extended RS codes, with negligible add-ons, except that an extra multiplexer is added to their critical paths. To the author's best knowledge, this is the first time that a high-throughput decoder for singly extended RS codes is explored.

We derive the Wu list-decoding algorithm for generalized Reed-Solomon (GRS) codes by using Gröbner bases over modules and the Euclidean algorithm as the initial algorithm instead of the Berlekamp-Massey algorithm. We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami-Sudan algorithm, immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes.

Chase decoding is a prevalent soft-decision decoding method for algebraic codes where an efficient bounded-distance decoder is available. Essentially, it repeatedly applies bounded-distance decoding upon combinatorially flipping certain least reliable bits (or patterns for nonbinary case). In this paper, we devise a one-pass Chase decoding algorithm of Reed-Solomon codes such that the desired error locator polynomial by flipping an error pattern is obtained in one pass (when operated in parallel) through utilizing the preceding results. This is effectively achieved through cumulative interpolation and linear-feedback-shift-register (LFSR) synthesis techniques. Furthermore, through converting the algorithm into the transform domain, exhaustive root search for each error locator polynomial is circumvented. Computationally, the new algorithm exhibits linear complexity , in attempting to determine a candidate codeword associated with each additionally flipped symbol/pattern; it compares favorably to quadratic complexity by straightforwardly utilizing hard-decision decoding, where and denote the code length and minimum distance, respectively. We also reveal a corrected algorithm for one-pass generalized minimum distance (GMD) decoding for Reed-Solomon codes from Koetter's original work. In addition, we devise a highly efficient one-pass Chase decoding algorithm for binary Bose-Chaudhuri-Hocquenghem (BCH) codes by taking advantage of a key characteristic of the Berlekamp algorithm. Finally, we present a systolic very large-scale integration (VLSI) decoder architecture through slightly compromising the proposed one-pass Chase decoding algorithm. It takes clock cycles to complete one iteration by flipping one error pattern. Both circuit and memory complexities are dictated by the dimension of flipping patterns; in particular, they are independent of the code length or the minimum distance , rendering it highly attractive for various applications.

In this paper, we present three novel burst error correcting algorithms for an (n,k) Reed-Solomon code. The algorithmic complexities are of the same order as error-and-erasure decoding,O(rn), wherer=n-k. In particular, their hardware implementation shares elements of Blahut error-and-erasure decoding. In contrast, all existing single-burst error correcting algorithms, which are equivalent to the proposed first algorithm, have complexityO(r2n). The first algorithm corrects the shortest single-burst with lengthfup tor-1. The algorithm follows the key characterization that the ending locations of all candidate bursts can be purely determined by the roots of a polynomial which is a linear function of syndromes, and moreover, the shortest burst is associated with the longest sequence of consecutive roots. The algorithmic miscorrection probability is bounded byq-(r-1-f), whereqdenotes the field size. The second algorithm extends the first one to correct the shortest burst with lengthf≤r-3 and additionally a random symbol error. The algorithmic miscorrection probability is bounded byq-(r-3-f). The third algorithm probabilistically corrects the shortest burst with lengthf≤r-1-2δ and additionally δ (a small constant) random symbol errors. The algorithmic miscorrection and failure probabilities are both bounded byq-(r-1-2δ-f). Our simulation results for (60, 40) and (30, 16) shortened Reed-Solomon codes verify that the miscorrection probability for three algorithms and the failure probability for the third algorithm all decay exponentially (at the rate ofq-1) with respect to the length of burst.

Algebraic soft-decision decoding (ASD) of Reed-Solomon (RS) codes can achieve substantial coding gain with polynomial complexity. Particularly, the low-complexity Chase (LCC) ASD decoding has better performance-complexity tradeoff. In the LCC decoding, 2ηtest vectors need to be interpolated over, and a polynomial selection scheme needs to be employed to select one interpolation output to send to the rest decoding steps. The interpolation and polynomial selection can account for a significant part of the LCC decoder area, especially in the case of long RS codes and large η . In this paper, simplifications are first proposed for a low-complexity polynomial selection scheme. Then a novel interpolation scheme is developed by making use of the simplified polynomial selection. Instead of interpolating over each vector, our scheme first generates information necessary for the polynomial selection. Then only the selected vectors are interpolated over. The proposed interpolation and polynomial selection schemes can lead to 162% higher efficiency in terms of throughput-over-area ratio for an example LCC decoder with η = 8 for a (458, 410) RS code overGF(210).

Algebraic soft-decision decoding (ASD) of Reed-Solomon (RS) codes can achieve substantial coding gain with polynomial complexity. Particularly, the low-complexity Chase (LCC) ASD decoding has better performance-complexity tradeoff. In the LCC decoding, 2ηtest vectors need to be interpolated over, and a polynomial selection scheme needs to be employed to select one interpolation output to send to the rest decoding steps. The polynomial selection can account for a significant proportion of the overall LCC decoder area, especially in the case of long RS codes and large η. In this paper, a novel low-complexity polynomial selection scheme is proposed and efficiently incorporated into the LCC decoder. By sacrificing one single message symbol and modifying the encoder slightly, the polynomial selection is done using simple computations. For a (458, 410) RS code over GF(210), the encoder and LCC decoder with η = 8 employing the proposed scheme requires 34% less area without changing the encoding or decoding throughput.

In this paper, we first investigate erasure-only list decoding of Reed-Solomon and BCH codes. We consider the scenario in which some locations of a received word are pre-corrected. Accordingly, the rational curve fitting algorithm does not interpolate the known locations, and thus effectively increases the list error correction capability (LECC). For a Reed-Solomon code C(n, k, d), let n* be the effective code length by neglecting known locations, then the resulting LECC is n* - √(n*(n* - d)), independent of the actual code length n. When n* moves toward d, the LECC approaches to d. For a BCH code C(n, k, d), let n* be the effective code length by neglecting known locations, then the resulting LECC is 1 over 2 (n* - √(n*(n* - 2d))), independent of the actual code length n. When n* reduces toward 2d, the LECC approaches to d. In particular, it lists all (up to 2d2+ 2) codewords among any 2d erasure bits by applying twice the list decoding algorithm (one with the given 2d bits, the other with all flipped 2d bits). We then apply the proposed algorithms to the iterative decoding of product Reed-Solomon/BCH codes [C1Θ C2](n1n2, k1k2, d1d2), where some locations of a row (column) word are pre-corrected by preceding column (row) decoding (by neglecting miscorrection). We show that by iterating three rounds, the proposed iterative list decoding algorithm guarantees to correct up to 27/32 d1d2errors for a product Reed-Solomon code, and 27/16 d1d2errors for a product BCH codes (with the underlying assumption that each component word does not correct beyond minimum distance).

This paper offers new insights into expanded cyclic and Reed-Solomon codes. First, we present a new description of general expanded codes defined over GF(qm). The proposed explicit description of the expanded generator matrix and the expanded parity check matrix reserves the symbol-wise algebraic structure. We reveal that the dual of an expanded code is the symbol-wise dual code expanded by the dual basis. Second, we characterize expanded cyclic codes utilizing the proposed expanded generator matrix (a similar analysis may be carried out over the proposed expanded parity check matrix). We focus on exploring the properties of component words of a codeword as well as their reciprocal relations. We reveal that the existence of subspace subcodes is dictated by conjugate roots of its dual generator polynomial, but not by its nonconjugate roots. We further show that each generator (parity check) matrix can be divided into block-bidiagonal submatrices associated with conjugate roots of the dual generator (generator) polynomial. Third, we shed light on binary expanded Reed-Solomon codes, which are of particular mathematical and practical interest. We first show an explicit way of constructing superior subspace subcodes utilizing the product basis which exhibit a higher dimension than the counterpart subfield subcodes. We next demonstrate that the effective dimension of the expanded parity check (generator) matrix, which governs the complexity of maximum-likelihood soft-decision decoding, can be noticeably reduced by employing block-bidiagonal structures of submatrices associated with conjugate roots of the generator (dual generator) polynomial. We finally conclude that the fixed-rate binary expanded Reed-Solomon codes are asymptotically “bad,” regardless of basis realization, in the sense that the ratio of minimum distance over code length diminishes with code length going to infinity. We assert “badness” in three scenarios, namely, (1) (conventional) fixed starting spectral null for all rates; (2) centered spectral null for rates above1/3; and (3) dynamic spectral null for rates above11/21. Our conclusions overturn the prevailing conjecture that binary expanded Reed-Solomon codes, particularly high-rate ones, are asymptotically “good” codes, while deviating from the ensemble of generalized Reed-Solomon codes which asymptotically achieve the Gilbert-Varshamov bound.

The integrated-interleaved coding scheme can be used to compensate the format inefficiency due to small block length or to save hardware cost in designing codes of very long block length. In this paper, we derive a new systematic encoding method for the integrated-interleaved coding scheme for both the special case where the second level has a single component codeword, and the general case where the second level may have multiple component codewords. The proposed method enjoys the great advantage of performing logical sum (possibly a weighted) once, whereas the state-of-the-art method in literature requires performing twice.

In the paper, we identify a class of constant-weight cyclic codes. Specifically, we show that a well-known class of q-ary BCH codes excluding the all-zero codeword are constant-weight cyclic codes. Moreover, we show this class of codes achieve the Plotkin bound.

In this paper, the idea of diversification is applied to box-and-match technique and a multi-basis-multi-box decoding algorithm is developed for soft-decision decoding of binary linear block codes. New preprocessing techniques are also employed to improve computational efficiency. These new techniques allow to achieve near maximum likelihood decoding of the (256,131) extended BCH code, which has not been reported so far.

The Lee metric measures the circular distance between two elements in a cyclic group and is particularly appropriate as a measure of distance for data transmission under phase-shift-keying modulation over a white noise channel. In this paper, using newly derived properties on Newton's identities, we initially investigate the Lee distance properties of a class of BCH codes and show that (for an appropriate range of parameters) their minimum Lee distance is at least twice their designed Hamming distance. We then make use of properties of these codes to devise an efficient algebraic decoding algorithm that successfully decodes within the above lower bound of the Lee error-correction capability. Finally, we propose an attractive design for the corresponding VLSI architecture that is only mildly more complex than popular decoder architectures under the Hamming metric; since the proposed architecture can also be used for decoding under the Hamming metric without extra hardware, one can use the proposed architecture to decode under both distance metrics (Lee and Hamming).

In this paper, we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and Bose-Chaudhuri-Hocquenghen (BCH) codes. The resulting list decoding algorithms exhibit the following significant properties.

In this paper we formulate the list decoding of (generalized) Reed-Solomon codes as a rational curve-fitting problem, utilizing the polynomials constructed by the Berlekamp-Massey algorithm. We present a novel list decoding algorithm that ldr corrects up to 1-radic1-D errors for (generalized) Reed-Solomon codes, identical to that of the Guruswami-Sudan algorithm which is built upon the Berlekamp-Welch algorithm, where D denote the normalized minimum distance, ldr with appropriate modifications, corrects up to 1/2(1-radic1-2D) errors for binary BCH codes, which is the best known bound under polynomial complexity, ldr exhibits polynomial complexity in nature, in particular, requires O(n6(1-radic1-D)7) field operations for Reed-Solomon codes in achieving its maximum list error correction capability (n denotes code length), whereas the Guruswami-Sudan algorithm has complexity O(n10(1-D)4).

Order-w reprocessing is a suboptimal soft-decision decoding approach for binary linear block codes in which up to w bits are systematically flipped on the so-called most reliable (information) basis (MRB). This correspondence first incorporates two preprocessing rules into order-w reprocessing and shows that, with appropriate choice of parameters, the proposed order-w reprocessing with preprocessing requires comparable complexity to order-w reprocessing but achieves asymptotically the performance of order-(w+2) reprocessing. To complement the MRB, a second basis is employed for practical SNRs and this approach is systematically extended to a multibasis order-w reprocessing scheme for high signal-to-noise ratios (SNRs). It is shown that the proposed multibasis scheme significantly enlarges the error-correction radius, a commonly used measure of performance at high SNRs, over the original (single-basis) order-w reprocessing. As a by-product, this approach also precisely characterizes the asymptotic performance of the well-known Chase and generalized minimum distance (GMD) decoding algorithms. The proposed algorithm successfully decodes the (192,96) Reed-Solomon concatenated code and the (256,147) extended BCH code in near optimal manner (within 0.01 dB at a block-error rate of 10-5) with affordable computational cost

This correspondence investigates soft-decision decoding of binary linear block codes using ordered recodings of test error patterns on the so-called "most reliable basis." The analysis demonstrates the optimality of the most reliable basis by showing that, among all possible bases, the most reliable basis minimizes the list error probability for a very general (and well-defined) class of orderings for recoding operations. The correspondence then proposes a suboptimal algorithm which utilizes reprocessing ordering and incorporates two techniques that render it computationally very efficient: 1) an iterative reference recoding technique which simplifies the recoding operation required for each test error pattern, and 2) an adaptive skipping rule which significantly reduces the average number of recodings. Simulation results with codes of relatively large length show that the proposed algorithm is computationally very efficient in comparison to existing algorithms in the literature

In this paper, two universally applicable preprocessing rules are developed to improve iterative receding algorithms that utilize the most reliable basis (MRB), while focusing on order-w reprocessing. Simulation results show that the proposed algorithm successfully decodes the Reed-Solomon concatenated code in near optimal manner at a block-error-rate with the maximum number of candidate codewords.

Two distinct codeword-searching procedures based on iterative bounded-distance decoding (BDD) are combined to form an adaptive two-stage maximum-likelihood (ML) decoder for binary linear block codes. During the first stage of the algorithm, a tight upper bound on an error likelihood metric ("discrepancy") is established iteratively for the ML codeword. First-stage processing requires sorting and storage. Adaptive switching to the second stage removes the sorting and storage requirements and allows to rule out redundant BDDs efficiently. Second-stage processing accounts for all codewords with discrepancy lower bound below the upper bound of the ML codeword and guarantees ML performance. In addition, the proposed two-stage algorithm is inherently tunable for controlled suboptimum operation. Under sub-ML operation, the overall scheme can be interpreted as a generalization of the Chase (1972) algorithm. Simulation studies for the (24,12,8) extended Golay and the (64,30,14) and (128,64,22) extended Bose-Chaudhuri-Hocquenghem (BCH) codes illustrate and support these theoretical developments.

This paper proposes a sub-optimal maximum-likelihood decoding algorithm for linear block codes. Given reliability information about each bit in the received word, our approach initially finds the set of most reliable "basis" information bits; it then searches for the most likely codeword by iteratively flipping bits in this basis set, constructing the corresponding codeword and determining its likelihood. The search of "test error patterns" on the set of basis information bits is conducted so that at each iteration the new set of basis information bits differs from a previously studied (and stored) one in a single bit position. Thus, the new codeword can be obtained from a stored codeword by modifying only the redundant bits that depend on the modified bit. The space complexity of the proposed decoding scheme is polynomial in the code length. We also describe an heuristic criterion to approximate the optimal set of test error patterns subject to a limit on the maximum computational effort. Simulation results with codes of relatively large length show that the proposed approach is very efficient, especially under low SNR.

The local identical index (LII) associative memory (AM) proposed by the authors in a previous paper is a one-shot feedforward structure designed to exhibit no spurious attractors. In this paper we relax the latter design constraint in exchange for enlarged basins of attraction and we develop a family of modified LII AM networks that exhibit improved performance, particularly in memorizing highly correlated patterns. The new algorithm meets the requirement of no spurious attractors only in a local sense. Finally, we show that the modified LII family of networks can accommodate composite patterns of any size by storing (memorizing) only the basic (prime) prototype patterns. The latter property translates to low learning complexity and a simple network structure with significant memory savings. Simulation studies and comparisons illustrate and support the the optical developments.

Associative memories (AMs) can be implemented using networks with or without feedback. In this paper we utilize a two-layer feedforward neural network and propose a new learning algorithm that efficiently implements the association rule of a bipolar AM. The hidden layer of the network employs p neurons where p is the number of prototype patterns. In the first layer, the input pattern activates at most one hidden layer neuron or "winner." In the second layer, the "winner" associates the input pattern to the corresponding prototype pattern. The underlying association principle is minimum Hamming distance and the proposed scheme can be viewed also as an approximately minimum Hamming distance decoder. Theoretical analysis supported by simulations indicates that, in comparison with other suboptimum minimum Hamming distance association schemes, the proposed structure exhibits the following favorable characteristics: 1) It operates in one-shot which implies no convergence-time requirements; 2) it does not require any feedback; and 3) our case studies show that it exhibits superior performance than the popular linear system in a saturated mode (LSSM). The network also exhibits 4) exponential capacity and 5) easy performance assessment (no asymptotic analysis is necessary). Finally, since it does not require any hidden layer interconnections or tree-search operations, it exhibits low structural as well as operational complexity.

In contrast to conventional feedback bidirectional associative Memory (BAM) network models, a feedforward BAM network is developed based on a one-shot design algorithm of O(p(2)(n+m)) computational complexity, where p is the number of prototype pairs and n, m are the dimensions of the input/output bipolar vectors. The feedforward BAM is an n-p-m three-layer network of McCulloch-Pitts neurons with storage capacity 2(min{m,n}) and guaranteed perfect bidirectional recall. The overall network design procedure is fully scalable in the sense that any number p= or <2(min{m,n}) of bidirectional associations can be implemented. The prototype patterns may be arbitrarily correlated. With respect to inference performance, it is shown that the Hamming attractive radius of each prototype reaches the maximum possible value. Simulation studies and comparisons illustrate and support these theoretical developments.