Homomorphic encryption (HE) enables arithmetic operations to be performed directly on encrypted data. It is essential for privacy-preserving applications such as machine learning, medical diagnosis, and financial data analysis. In popular HE schemes, ciphertext multiplication is only defined for two inputs. However, the multiplication of multiple inputs is needed in many HE applications. In our previous work, a three-input ciphertext multiplication method for the CKKS HE scheme was developed. This paper first reformulates the three-input ciphertext multiplication to enable the combination of computations in order to further reduce the complexity. Thesecond contribution is extending the multiplication to multiple inputs without compromising the noise overhead. Additional evaluation keys are introduced to achieve relinearization of polynomial multiplication results. To minimize the complexity of the large number of rescaling units in the multiplier, a theoretical analysis is developed to relocate the rescaling, and a multi-level rescaling approach is proposed to implement combined rescaling with complexity similar to that of a single rescaling unit. Guidelines and examples are provided on the input partition to enable the combination of more rescaling operations. Additionally, efficient hardware architectures are designed to implement our proposed multipliers. The improved three-input ciphertext multiplier reduces the logic area and latency by 15% and 50%, respectively, compared to the best prior design. For multipliers with more inputs, ranging from 4 to 12, the architectural analysis reveals 29% savings in area and 63% shorter latency, on average, compared to prior work.

Homomorphic encryption (HE) allows computations to be directly carried out on ciphertexts and is essential to privacy-preserving computing, such as neural network inference, medical diagnosis, and financial data analysis. Only addition and 2-input multiplication are defined over ciphertexts in popular HE schemes. However, many HE applications involve non-linear functions and they need to be approximated using high-order polynomials to maintain precision. To reduce the complexity of these computations, this paper proposes 3-input ciphertext multiplication. One extra evaluation key is introduced to carry out the relinearization step of ciphertext multiplication, and new formulas are proposed to combine computations and share intermediate results. Compared to using two consecutive 2-input multiplications, computing the product of three ciphertexts utilizing the proposed scheme leads to almost a half of the latency, 29% smaller silicon area, and lower noise without sacrificing the throughput.

The medium-density parity-check (MDPC) code-based Bit Flipping Key Encapsulation (BIKE) mechanism remains a candidate for post-quantum cryptography standardization. The latest version utilizes a new bit-flipping (BF) decoding algorithm, which decides the BF threshold by an affine function with high-precision coefficients. Previous BF decoder implementations can be extended to the new algorithm. However, they suffer from large memories that dominate the overall complexity. This paper proposes a column-layered decoder for the new BIKE BF decoding algorithm to substantially reduce the memory requirement, and optimizes the affine BF threshold function coefficients to reduce the code length needed for the same security level. For the first time, our work also investigates the impact of finite precision representation of the threshold coefficients on the decoding performance. For an example MDPC code considered for the standard, the proposed layered BF decoder achieves 20% complexity reduction compared to the best prior effort with a very small latency overhead.

Cyclic redundancy check (CRC) is utilized in digital communication and storage systems for error detection. CRC en/decoding is implemented using linear feedback shift registers (LFSRs). To achieve high throughput, a parallel LFSR can be implemented by registers with a feedback matrix and a pre-processing matrix multiplication. In previous designs, the feedback matrix is decided by look-ahead computations of the LFSR, and its multiplication contributes to a significant portion of the overall complexity. This paper proposes to search over a wide range of powers of the companion matrix describing the LFSR to minimize the gate count of the feedback matrix multiplication. This is enabled by an alternative interpretation of data inputs. Although the achievable data length protected by CRC is reduced by the proposed scheme, it still meets the requirement of IEEE standards. Besides, our scheme does not affect the pre-processing matrix and the input tap of the LFSR can still be shifted to reduce the complexity. For an example case that the parallelism equals the generator polynomial degree, the proposed design can reduce the gate count by 18%-53% and achieve shorter critical path for various CRCs.

If no abstract provided do not include one in the JATS XML

Reed-Solomon (RS) and BCH codes are among the most broadly used error-correcting codes in digital communication and storage systems. The Chien search step accounts for a significant part of the overall decoder complexity of these codes. The Chien search can be expressed as a Vandermonde matrix multiplication. This brief develops a novel Vandermonde matrix decomposition that significantly reduces the number of multiplications needed for the Chien search. Further reformulation on the matrix decomposition is also proposed to enable efficient parallel processing in hardware implementation. Accordingly, a low-complexity parallel Chien search architecture is designed. For example,$9$-error-correcting RS or BCH code over$\text{GF}(2^{10})$, the proposed design with$40$-,$60$-, and$80$-parallel processing achieves$11\%$,$14\%$, and$17\%$, respectively, area reduction compared to the best prior design with the same throughput and similar latency.

This paper presents a low-latency hardware accelerator for modular polynomial multiplication for lattice-based post-quantum cryptography and homomorphic encryption applications. The proposed novel modular polynomial multiplier exploits the fast finite impulse response (FIR) filter architecture to reduce the computational complexity of the schoolbook modular polynomial multiplication. We also extend this structure to fast$M$-parallel architectures while achieving low-latency, high-speed, and full hardware utilization. We comprehensively evaluate the performance of the proposed architectures under various polynomial settings as well as in the Saber scheme for post-quantum cryptography as a case study. The experimental results show that our proposed modular polynomial multiplier reduces the computation time and area-time product, respectively, compared to the state-of-the-art designs.

In order to protect intellectual properties against untrusted foundry, many logic-locking schemes have been developed. The idea of logic locking is to insert a key-controlled block into the circuit to make the circuit function incorrectly or go through redundant states without right keys. However, in the case that the algorithm implemented by the circuit is self-correcting, existing logic-locking schemes do not affect the system performance much even if a wrong key is used and hence do not effectively protect the circuit. One example is low-density parity-check (LDPC) error-correcting decoders, which are used in numerous digital communication and storage systems. This article proposes two algorithmic-level obfuscation methods for LDPC decoders. By modifying the decoding process and locking the stopping criterion, our new designs substantially degrade the decoder throughput and/or error-correcting performance, and make the decoder unusable when a wrong key is applied. For an example of the LDPC decoder, our proposed methods reduce the throughput to less than 1/3 and/or increase the decoder error rate by at least two orders of magnitude with at most 0.55% area overhead. Besides, our designs are also resistant to the SAT, AppSAT, and removal attacks.

Deep neural networks (DNNs) are utilized in numerous image processing, object detection, and video analysis tasks and need to be implemented using hardware accelerators to achieve practical speed. Logic locking is one of the most popular methods for preventing chip counterfeiting. Nevertheless, existing logic-locking schemes need to sacrifice the number of input patterns leading to wrong output under incorrect keys to resist the powerful satisfiability (SAT)-attack. Furthermore, the DNN model inference is fault tolerant. Hence, using a wrong key for those SAT-resistant logic-locking schemes may not affect the accuracy of DNNs. This makes the previous SAT-resistant logic-locking scheme ineffective on protecting DNN accelerators. Besides, to prevent DNN models from being illegally used, the models need to be obfuscated by the designers before they are provided to end-users. Previous obfuscation methods either require a long time to retrain the model or leak information about the model. This article proposes a joint protection scheme for DNN hardware accelerators and models. The DNN accelerator is modified using a hardware key (Hkey) and a model key (Mkey). Different from previous logic locking, the Hkey, which is used to protect the accelerator, does not affect the output when it is wrong. As a result, the SAT attack can be effectively resisted. On the other hand, a wrong Hkey leads to substantial increase in memory accesses, inference time, and energy consumption and makes the accelerator unusable. A correct Mkey can recover the DNN model that is obfuscated by the proposed method. Compared to previous model obfuscation schemes, our proposed method avoids model retraining and does not leak model information.

The McEliece cryptosystem based on medium-density parity-check (MDPC) codes remains a candidate in the fourth round submission of post-quantum cryptography standard. The low-density parity-check (LDPC) decoders used in digital communications have been extensively studied. However, the MDPC codes for the McEliece cryptosystem have much higher column weight and different structure in their parity-check matrices. As a result, simplification techniques for LDPC decoders are not applicable to MDPC decoders. Besides, existing MDPC decoder designs have been focusing on the simplest bit-flipping algorithm, whose performance is inferior compared to that of the Min-sum algorithm. This paper first optimizes the scaled Min-sum algorithm for codes with high column weight to improve the performance with simple scalar multiplications. The overall decoder architecture is re-designed to take into account the sparsity of the parity-check matrix and nontrivial min-sum check node processing. Besides, a flexible message storage scheme is proposed to reduce the worst-case decoding latency of the randomly constructed codes utilized in the McEliece cryptosystem. Then a 2-stage scaling scheme is developed to reduce the long critical path caused by the high column weight and a group size re-balancing scheme is introduced to mitigate the precision loss caused by the 2-stage scaling in parallel decoders. For an example MDPC decoder, the proposed optimized 2-stage scaled Min-sum algorithm leads to orders of magnitude error-correcting performance improvement and 16% higher clock frequency with negligible silicon area overhead compared to unoptimized Min-sum decoders.

The generalized integrated interleaved (GII) codes can nest BCH sub-codewords to form more powerful BCH codewords. GII codes enable hyper-speed decoding and achieve excellent error-correction capability. They are among the best candidates for the new storage class memories (SCMs). However, SCMs require high code rate and short codeword length. In this case, the GII sub-codewords have small correction capability, and miscorrections on the sub-words lead to severe performance degradation. In previous work, higher-order nested syndromes are computed to detect and mitigate miscorrections in GII decoding. These computations cause long decoding latency, even though they can be implemented by sharing the hardware architecture for other decoding steps. This paper proposes three methods to optimize the miscorrection detection by investigating dominant error patterns leading to miscorrections. The first scheme is to skip the nested syndrome checking for cases that are less likely miscorrected. To make up for the performance loss caused by the first scheme, our second approach exploits 2-bit extended BCH codes to protect each sub-codeword. In addition, the third scheme is developed to protect all sub-codewords using extra parity bits while keeping the code rate loss negligible. Formulas are also derived to estimate the achievable performance. Applying the proposed optimizations, the average nested decoding latency is reduced by 43% for an example GII code with 3-error-correcting sub-codewords at input bit error rate 10−3, while the performance loss and complexity overheads are negligible.

Generalized integrated interleaved (GII) codes can nest BCH sub-codewords to form stronger BCH codewords. They are among the best candidates for error correction in the new storage class memories (SCMs). However, SCMs require short codeword length and low redundancy. In this case, the nested key equation solver (KES), which is a key step in GII decoding, has a small number of iterations. The initialization and/or scalar pre-computation in previous nested KES designs have large area and may take even longer time than the iterations themselves. This paper proposes an efficient nested KES design for short GII-BCH codes. The polynomial updating is decomposed into two steps to reduce the critical path without requiring scalar pre-computation. Besides, the KES is reformulated to reduce the number of clock cycles without incurring any area overhead. For an example code over $GF(2^{10})$ that protects 2560 bits with 10% redundancy, the proposed design achieves at least 25% area reduction and 37% reduction on the area-time product averaged over the nested decoding rounds compared to prior efforts.

Low-density parity-check (LDPC) codes defined over non-binary (NB) finite field GF(2q)(q >1) achieve better error-correcting performance than binary LDPC codes when the codeword length is moderate. The decoder complexity increases very fast with the order of the field, 2q, although the error-correcting performance also improves. To reduce the complexity for practical applications, NB-LDPC codes over lower-order finite fields are of great interest. Previous designs have been focusing on decoders over either the smallest NB field GF (4) or much larger fields, such as GF (32) or higher. Prior optimization techniques are either not applicable or do not lead to efficient designs for codes over GF (8) or other lower-order fields. In this paper, an efficient architecture is developed for the check node processing, which is the most complicated step in NB-LDPC decoding, for the Min-max algorithm over lower-order fields. By utilizing the properties of finite field elements, the max/min comparison results are shared and the number of comparators needed is reduced significantly. Compared to the best prior design, the proposed check node processing has 18.5% smaller area and shorter critical path for an example code over GF (8).

The advanced encryption standard (AES) is the current standard for symmetric-key cipher. To protect AES implementations from correlation power analysis (CPA) side-channel attacks (SCAs), many countermeasures have been proposed. However, existing approaches have large area overheads. This paper proposes two low-complexity techniques for AES to resist CPA attacks. By exploiting generalized dual ciphers, alternative conversions are utilized to substantially simplify all the involved constant matrix multiplications. Additionally, a multiplicative masking scheme utilizing simple constant multipliers is developed for AES designs used in resource-constraint applications. FPGA implementation results on a Xilinx XC7a200t device show that the proposed design with four Sboxes achieves 11.1% area reduction and 89.2% clock frequency increase compared to the best prior architecture without sacrificing CPA-attack resistance. In addition, the proposed multiplicative masking scheme not only keeps the resistance to CPA attacks, but also reduces the area by 52.6% and increases the clock frequency by 29.7% in a single-Sbox design compared to the previous scheme.

Reed-Solomon (RS) codes are used in many storage systems for failure recovery. In popular software implementations, RS codes are defined by using a parity check matrix that is either a Cauchy matrix padded with an identity or a Vandermonde matrix. The encoding complexity can be reduced by searching for a Cauchy matrix that has a smaller number of ‘1's in its bit matrices or exploiting Reed-Muller (RM) transform in the Vandermonde matrix multiplication. This article proposes two new approaches that improve upon the previous schemes. In our first approach, different constructions of finite fields are explored to further reduce the number of ‘1's in the bit matrices of the Cauchy matrix and a new searching method is developed to find the matrices with minimum number of ‘1's. Our second approach defines RS codes using a parity check matrix in the format of a Vandermonde matrix concatenated with an identity matrix so that the multiplication with the inverse erasure columns in the encoding is eliminated and the decoding can be carried out using simplified formulas. The Vandermonde matrix in such an unconventional RS code definition needs to be constructed using finite field elements in non-consecutive order. A modification is also developed in this article to enable the application of the RM transform in this case to reduce the matrix multiplication complexity. For 4-erasure-correcting RS codes over$GF(2^8)$, the two proposed approaches increase the encoding throughput by 40 and 15 percent on average over the prior works based on Cauchy matrix and Vandermonde matrix with RM transform, respectively, for a range of codeword length. Moreover, the decoding throughput is also significantly improved.

Generalized integrated interleaved (GII) codes nest a set of linear block codewords to generate codewords belonging to stronger codes. They are among the best error-correcting codes for next-generation hyper-speed digital communications and storage. Serial encoders for GII codes based on BCH codes have been previous investigated. They consist of BCH encoders whose inputs and outputs are multiplied by vectors decided by the nesting scheme. However, parallel GII encoders for high-speed systems cannot be designed by directly extending serial encoders due to the unique feature that BCH codes of different error-correcting capabilities are involved. Moreover, GII decoder complexity and latency can be greatly reduced by sharing the encoder to compute short remainders for syndrome computation. Although previous resource-shareable BCH encoders can be utilized to implement resource-shareable GII encoders, they are all serial. This paper first proposes a low-complexity scheme to handle the different error-correcting capabilities of the involved codes and align the input and parity symbols for parallel processing. Then two efficient parallel resource-shareable BCH encoder architectures to be used as GII encoder components are developed. The first design is achieved by deriving parallel register state update formulas for concatenated linear-feedback shift registers (LFSRs). Through reformulating the remainder polynomial divisions, the second design allows the inputs to be added to different LFSR taps, and accordingly reduces the complexity by a significant portion. For an example 160-parallel GII-BCH encoder considered for Flash memory applications, the second proposed design requires 14% smaller area compared to the first one. Besides both of them lead to around 50% latency reduction in the nested syndrome computation with small area overheads compared to the best possible alternative design.

Generalized integrated interleaved (GII) codes nest short BCH sub-codewords to form more powerful BCH codewords. They can potentially achieve hyper-speed decoding with excellent error-correction capability. In particular, short GII-BCH codes are among the best candidates for the new fast storage class memories (SCMs). Miscorrections severely degrade the performance of short GII-BCH codes. Although they were effectively mitigated in previous designs, the involved repeated Chien search and higher-order syndrome computation cause long latency. This brief proposes efficient and low-latency nested decoding schemes for short GII-BCH codes. A strategy is developed to select sub-words for further nested decoding to mitigate miscorrections by keeping track of the error locator polynomials, instead of waiting for the lengthy Chien search. Formulas are also derived to estimate the effects on the error-correcting performance. Besides, a low-complexity linear feedback shift register (LFSR) architecture is developed to accelerate the higher-order nested syndrome computation. For an example GII-BCH code targeting at SCMs, the proposed design reduces the worst-case nested decoding latency by 26% with 8.5% area overhead and negligible performance loss compared to prior methods.

The generalized integrated interleaved BCH (GII-BCH) codes are among the best error-correcting codes for next-generation terabit/s memories. The key equation solver (KES) in the nested decoding of GII codes limits the achievable clock frequency. Recently, by polynomial scalar pre-computation, the critical path of the nested KES for Reed-Solomon (RS)-based GII codes has been reduced to one multiplier. However, for GII-BCH codes, the nested KES has more complicated formulas in order to skip the odd iterations and hence prior techniques do not directly extend. This paper proposes novel reformulations of the nested BCH KES to enable scalar pre-computation. Additionally, polynomial scaling is incorporated to enable complexity reduction. As a result, the critical path of the nested BCH KES with odd iterations skipped is reduced to one multiplier. For an example GII-BCH code over GF (212), the proposed design reduces the average nested BCH KES latency to around a half with similar silicon area compared to the best prior design.

The ring-learning with errors (R-LWR) problem is utilized to build many ciphers resisting quantum-computing attacks and fully homomorphic encryption that allows computations to be carried out on encrypted data. Modular multiplication of long polynomials with large coefficients is the most critical operation in these schemes. The polynomial multiplication complexity can be reduced by the Karatsuba formula. In this paper, a new method is proposed to integrate the modular reduction into the Karatsuba polynomial multiplication. Modular reduction is applied to intermediate segment products instead of the final product. As a result, additional sub-structure sharing is enabled and the number of coefficient additions needed for assembling the segment products to get the final result is substantially reduced. For polynomial multiplications with decomposition factors 2, 3, and 4, the proposed scheme reduces the number of additions by 13-17%.

Cyclic redundancy check (CRC) is adopted in many digital communication and storage systems to ensure data integrity. CRC en/decoding is carried out using linear feedback shift registers (LFSRs) and a parallel LFSR can be implemented by registers with a feedback matrix multiplication and an input pre-processing matrix multiplication. A large parallelism is needed to achieve the high throughput required by modern applications. In prior designs, the complexity of parallel LF- SRs has been reduced by applying state transformation and/or modifying the input tap. In this paper, we first show that the input tap modification can be actually described by a category of state transformation. Using this type of transformation, the pre-processing matrix in a highly-parallel LFSR can be simplified without changing the feedback matrix. Additionally, we show that the post-processing matrix multiplication in state-transformed designs can be eliminated without affecting the error detection capability of the CRC. Utilizing these two techniques, the area requirement of highly-parallel CRC can be reduced by 7-16% without increasing the critical path for various parallelisms and most generator polynomials compared to the best previous design.

Generalized integrated interleaved (GII) codes nest Reed-Solomon (RS) or BCH sub-codewords to generate codewords belonging to stronger RS or BCH codes. Their hyper-speed decoding and good error-correction capability make them one of the best candidates for next-generation terabit/s digital storage and communications. The key equation solver (KES) in the nested decoding stage causes clock frequency bottleneck and takes a large portion of the GII decoder area. Recent architectures reduce the critical path to two multipliers and rely on the application of the slow-down technique to further reduce it to one. The slow-down technique requires two sub-codewords to be interleaved in the nested KES. However, most of the time, the nested decoding only needs to be carried out on one sub-codeword and half of the clock cycles are wasted. This paper proposes two fast nested KES algorithms, both of which have one multiplier in the critical path without applying slow-down and accordingly reduce the latency of the nested KES to almost a half. The short critical path is achieved by algorithmic reformulations that enable the pre-computation of the scalars in parallel with polynomial updating. Our second design adopts scaled versions of the polynomials to enable product term sharing so that the number of multipliers in each pair of processing elements is reduced from 8 as in the first design to 4. Novel scaling and combined scalar computations are developed to keep the critical path one multiplier. For an example GII code over$GF(2^{8})$that has 3 nested codewords, our designs achieve 49.9% reduction on the number of clock cycles needed in the nested KES compared to prior designs. Besides, our second design requires 22% less area than the first one under the same timing constraint.

Logic locking is used to protect integrated circuits (ICs) from piracy and counterfeiting. An encrypted IC implements the correct function only when the right key is input. Many existing logic-locking methods are subject to the powerful satisfiability (SAT)-based attack. Recently, an Anti-SAT scheme has been developed. By adopting two complementary logic blocks that consist of AND/NAND trees, it makes the number of iterations needed by the SAT attack exponential to the number of input bits. Nevertheless, the Anti-SAT scheme is vulnerable to the later AppSAT and removal attacks. This article proposes a generalized (G-)Anti-SAT scheme. Different from the Anti-SAT scheme, a variety of complementary or non-complementary functions can be adopted for the two blocks in our G-Anti-SAT scheme. The Anti-SAT scheme is just a special case of our proposed design. Our design can achieve higher output corruptibility, which is also tunable, so that better resistance to the AppSAT and removal attacks is achieved. Meanwhile, unlike existing AppSAT-resilient designs, our design does not sacrifice the resistance to the SAT attack.

Long BCH codes are broadly used in communications and storage. BCH encoders can be implemented by linear feedback shift registers (LFSRs), and modern systems demand parallel encoders to achieve high speed. LFSRs are also used for implementing cyclic redundancy check (CRC). It was shown previously that adding the input to the least significant tap of the CRC LFSR leads to the lowest complexity in the corresponding parallel architecture derived using state transition. However, the analyses for CRC LFSRs do not hold for long BCH encoders, since the parallelism needed is much smaller than the length of the LFSR for long BCH encoders. Besides, additional clock cycles are required to pad zeros to the input in order to derive the same final state for the parities. This paper first proposes a new parallel design that allows the input to be added to any tap without sacrificing the throughput. Then the matrices involved in parallel long BCH encoders are analyzed to identify the input tap leading to minimum complexity. Besides, hardware unit sharing for matrix multiplications is enabled through analyzing the timing of the encoder. For a 32-parallel (8191, 7684) BCH encoder, our design achieves 57% higher efficiency in terms of throughput/area ratio compared to the best prior design.

Generalized integrated interleaved (GII) codes allow localized decoding of short sub-codewords. They are essential to hyper-speed data storage, communications, and continued scaling of distributed storage. Sub-codewords, which are usually Reed-Solomon (RS) or BCH codewords, are nested to generate codewords of higher correction capabilities. If the decoding of individual sub-codewords fails, the higher-order syndromes from the nested codewords are utilized to correct more errors. GII decoder design faces many challenges. The major ones include: 1) high-speed nested decoding utilizing the higher-order syndromes; 2) efficient updating of higher-order syndromes after sub-codewords are corrected; 3) computation of nested syndromes and matrix inversion for converting them to higher-order sub-codeword syndromes; and 4) efficient architectures capable of addressing the variable correction capabilities of the nested codewords. This paper proposes novel algorithmic reformulations and architectural transformations to address each bottleneck. For an example, GII code that has the same rate and length as eight un-nested (255, 223) RS codes, the proposed GII decoder achieves more than seven orders of magnitude improvement in error-correcting performance with less than 30% area overhead compared to the RS decoder. With a critical path of seven XOR gates, the proposed decoder can easily achieve more than 40 GByte/s throughput.

Logic locking is used to protect intellectual properties and prevent integrated circuit piracy. The satisfiability (SAT)-based attack is one of the most powerful attacks against logic locking. The Anti-SAT logic-locking scheme is subject to the removal and AppSAT attacks. To address these vulnerabilities, the G-Anti-SAT block has been proposed. However, in both of these schemes, the resiliency to the SAT attack is dependent on a single product term with a large number of literals in the logic-locking function. The corresponding gates can be easily identified by analyzing the signal probability skew. Once they are removed, the logic-locking block is no longer resistant to the SAT attack. This paper proposes a new logic-locking scheme whose function has check board patterns in the corresponding K-map. Due to the unique patterns, the resistance to the SAT attack is no longer dependent on a single product term. Even if some of the gates are removed, the design is still resistant to the SAT attack.

To reduce the network traffic overhead and latency associated with failure recovery in distributed storage, it is essential to adopt locally recoverable (LRC) erasure codes. Among available LRC codes, the generalized integrated interleaved (GII) codes that nest individual interleaves to generate shared parities achieve good tradeoffs on locality, redundancy, and complexity. To further improve the locality, a construction of three-layer GII codes has been developed recently. This paper proposes an efficient systematic encoding scheme for three-layer GII codes. Due to the fundamentally different structure in the nesting matrix, the design of three-layer GII encoders face new issues that do not exist in prior two-layer encoders. The parities from both layers of nesting need to be accommodated in the interleaves. The parity allocation and the procedure of the interleave encoding are jointly considered to ensure the generation of target codewords. Additionally, a reduced-complexity implementation architecture of the proposed encoding scheme is presented in this paper.

Intellectual property (IP) piracy and electronic counterfeiting have emerged as critical threats to the semiconductor industry in the current horizontal business model where the supply chain usually involves a large number of vendors. Hence, techniques that can protect integrated circuit (IC) against reverse engineering are demanded, especially for security-critical tasks. Hardware obfuscation is a broad category of techniques that could create ambiguity to the adversary by hiding the actual information from illegitimate users. This paper presents a novel hardware obfuscation design through reconfigurable finite field arithmetic units, which can be employed in various error correction and cryptographic algorithms. The effectiveness and efficiency of the proposed methods are verified by an obfuscated reformulated inversion-less Berlekamp-Massey (RiBM) Reed-Solomon decoder. Our experimental results show the hardware implementation of RiBM based Reed-Solomon decoder built using reconfigurable field multiplier designs. The proposed design provides only very low overhead.

To protect intellectual property, hardware obfuscation is necessary to conceal the implemented function. Besides logic-level approaches, hardware obfuscation can be done through algorithmic modifications. Prior algorithmic obfuscations address signal processing systems and those with variable data flow. This paper focuses on the obfuscation of systems based on finite field arithmetic, which are broadly adopted in digital communications. Netlists of hardware units with different field constructions are first analyzed to evaluate possible attacks. Taking into account the specifics of the computations in the Advanced Encryption Standard (AES) algorithm, optimized schemes are proposed to efficiently introduce obfuscation keys utilizing the variation of finite field construction. For an example pipelined fully-unrolled AES encryptor, the proposed scheme leads to 480 bits of obfuscation key with 3% area overhead without sacrificing the throughput. The proposed obfuscation method can be also extended to other algorithms involving finite field arithmetic.

BCH codes and cyclic redundancy check (CRC) are broadly used to ensure the reliability and integrity of data transmission. BCH encoders and CRC en/decoders are implemented by linear feedback shift registers (LFSRs). In prior LFSRs, the input is added to the most significant tap (MST), whose output is fed back and affects each of the other registers in the next clock cycle. The effects on the registers in a parallel design are translated to a pre-processing matrix multiplication, which may occupy the majority of the LFSR area. In this paper, we propose to add the input to the least significant tap (LST) and derive the corresponding parallel processing formula. Since the output of the LST is shifted to the MST before being fed back to the other taps, the corresponding pre-processing matrix is much simpler. Complexity reductions achievable by applying state-space transformations on LST-input LFSRs are evaluated and possible optimizations are discussed. For various CRCs considered, the proposed designs lead to 10–40% gate count reduction and significant power reduction compared to prior approaches with no or negligible penalty on the throughput.

Generalized integrated interleaved (GII) codes nest sub-codewords, also called interleaves, to generate parities shared by the interleaves. They achieve better tradeoffs compared to other locally recoverable erasure codes and are good candidates for hyper-speed data storage and communications. By nesting the interleaves in a hierarchical manner, the recent three-layer GII codes further improve the decoding locality. However, due to the fundamentally different structure and larger size of the nesting matrix, three-layer GII decoding faces many issues that do not exist previously. In this paper, constraints on the relative correction capabilities of the nested codes are defined to achieve the target correction goal. The bottleneck on syndrome conversion matrix inversion is eliminated by transforming the conversion matrices and syndrome vectors. The overall decoding process is optimized to increase correction capability and reduce complexity.

Hardware obfuscation is a technique that modifies the circuit to hide the functionality. Obfuscations through algorithmic modifications add protection in addition to circuit-level techniques, and their effects on the data paths can be analyzed and controlled at the architectural level. Many error-correcting coding and cryptography algorithms are based on finite field arithmetic. For the first time, this paper proposes a hardware obfuscation scheme achieved through varying finite field constructions and primitive element representations. Also the variations are effectively transformed to bit permuters controlled by obfuscation keys to achieve high level of security with very small complexity overheads. To illustrate the effectiveness, the proposed scheme is applied to obfuscate Reed-Solomon decoders, which are broadly used in communication and storage systems. For a (255, 239) RS decoder over finite field $GF(256)$GF(256), the proposed scheme achieves 1239 bits of independent obfuscation key with 4.4 percent area overhead, while yielding no penalty on the throughput and only one extra clock cycle of latency.

Flash and other memories may adopt multi-stage low-density parity-check (LDPC) decoders to reduce the average decoding latency and power consumption. To meet the increasingly tighter latency constraints of next-generation data centers, the earlier-stage decoders need to have better error-correcting capability and lower latency. To achieve this goal, this paper first develops a column-layered scheduling scheme for the 2-bit message-passing (TBMP) LDPC decoding algorithm, which has significant coding gain over the 3-bit Min-sum algorithm. The proposed column-layered scheme is perfect in the sense that it does not cause any coding gain degradation. Also by utilizing the 2-bit property, efficient VLSI architectures are designed for the column-layered and non-layered TBMP algorithms. Complexity analysis shows that, the layered (non-layered) TBMP decoder has more than 10 (8) times shorter latency at the cost of 53% (8%) larger area compared to a row-layered 3-bit Min-sum decoder for an example (17664, 16560) LDPC code.

3-Error-correcting BCH codes enable high-speed optical transport networks and low-latency next-generation memodes. The error locator polynomial root computation is the most hardware-demanding step in BCll decoding. For degree-3 polynomials, the roots can be found using a look-up table (LVT), which takes large area to implement when the code is not short. In this paper, a new method is proposed to further compress the LVT by more than an order of magnitude compared to the best prior design through utilizing the fact that only a limited number of degree-3 polynomials are valid error locators. A novel low-complexity approach is also developed to find the cube roots, which were not addressed in previous work, and the decoder architecture is further optimized. Compared to prior efforts, the proposed decoder achieves higher throughput and reduces the area requirement by 19% for a (1023, 993) BCH code over GF(210).

Quasi-cyclic low-density parity-check (QC-LDPC) codes are adopted in many digital communication and storage systems. The encoding of these codes is traditionally done by multiplying the message vector with a generator matrix consisting of dense circulant submatrices. To reduce the encoder complexity, this paper introduces two schemes making use of finite Fourier transform. We focus on QC-LDPC codes whose circulant submatrices are of dimension$(2^{r}-1)\times (2^{r}-1)$and the entries are elements of GF$(2^{p})$, where$p$divides$r$, and hence, GF$(2^{p})$is a subfield of GF$(2^{r})$. These cover a broad range of codes, and binary LDPC codes are a special case. Making use of conjugacy constraints, low-complexity architectures are developed for finite Fourier and inverse transforms over subfields in this paper. In addition, composite field arithmetic is exploited to eliminate the computations associated with message mapping and reduce the complexity of Fourier transform. For a (2016, 1074) nonbinary QC-LDPC code whose generator matrix consists of circulants of dimension$63 \times 63$with GF$(2^{2})$entries, the proposed encoders achieve 22% area reduction compared with the conventional encoders without sacrificing the throughput.

The Chien search for the error locator polynomial root computation in BCH and Reed-Solomon decoding accounts for a significant part of the overall decoder power consumption, especially r long codes over finite fields of high order. For serial Chien search, the power consumption is substantially lowered by a polynomial degree reduction (PDR) scheme. Every time a root is found, it is factored out of the error locator polynomial. Only the hardware units associated with the reduced-degree polynomial coefficients are active. However, this PDR scheme can not be directly extended to partial-parallel Chien search, which is needed in any systems to achieve high throughput. By analyzing the formulas of the evaluation values over finite field elements and available intermediate results of the Chien search, this paper proposes a partial-parallel Chien search architecture that reduces the error locator polynomial degree on the fly whenever a root is found without using long division. For a 122-error-correcting BCH code over GF(215), an 8-parallel Chien search using the proposed architecture achieves 32% power reduction over existing partial-parallel architectures for a typical case.

Low-density parity-check (LDPC) codes are adopted in many applications due to their Shannon-limit approaching error-correcting performance. Nevertheless, belief-propagation (BP) based decoding of these codes suffers from the error-floor problem. Recently, a new type of decoders termed finite alphabet iterative decoders (FAIDs) were introduced. The FAIDs use simple Boolean maps for variable node processing. With very short word length, they can surpass the BP-based decoders in the error floor region. This paper develops a low-complexity implementation architecture for FAIDs by making use of their properties. Particularly, an innovative bit-serial check node unit is designed for FAIDs, and the symmetric Boolean maps for variable node processing lead to small silicon area. An optimized data scheduling scheme is also proposed to increase the hardware utilization efficiency. From synthesis results, the proposed FAID implementation needs only 52% area to reach the same throughput as one of the most efficient Min-sum decoders for an example (7807, 7177) LDPC code, while achieving better error-correcting performance in the error-floor region.

Phase change memory (PCM) is a promising candidate for next-generation memory. To lengthen the lifetime of PCM, both transient (soft) and stuck-at (hard) errors need to be corrected. Previous approaches either address only hard errors using error-correcting pointers (ECPs), or employ error-correcting codes capable of correcting six or more errors, which demand high decoding complexity and large storage overhead. Also the verify-after-write needed to generate the ECPs leads to high energy consumption and latency overhead. In this paper, by making use of the property that soft errors are rare and hard errors increase gradually with the number of writes, a novel scheme is proposed to correct both soft and hard errors through integrating 2-error-correcting BCH codes and ECPs. In our design, the ECPs come directly from BCH decoding results. Hence, the energy-consuming verify-after-write and complicated ECP generation process are eliminated. Efficient and low-latency hardware implementations are also developed for BCH en/decoding suitable for PCM applications. Synthesis and power analysis show that the proposed scheme leads to significant overall energy and latency reductions. Moreover, our design can achieve similar or better error protection than prior schemes.

Reed-Solomon (RS) codes are one of the most widely used block error-correcting codes in modern communication and computer systems. Multiplication is the key computation in RS encoding. Adopting the generator polynomial with symmetric coefficients, the number of multipliers in RS encoders can be reduced by half, and their power consumption may also reduce. However, in some cases, the encoder based on the generator polynomial with asymmetric coefficients have better power performance. Additionally, since more than one primitive polynomial can generate a finite field with certain order, different choices of primitive polynomial also change the complexity of multipliers. In this paper, we exploited the relationship between the power consumption of RS encoders and their different encoding parameters. A simple way to find the encoder with the lowest power consumption is also presented. Simulation results prove its effectiveness.

Algebraic soft-decision (ASD) decoding algorithm of Reed-Solomon (RS) codes can achieve better performance-complexity tradeoff than other soft-decision decoding algorithms. The interpolation is a major step of ASD algorithms. In the case that multiple test vectors are involved, the interpolation needs to be carried out for each vector and leads to very high hardware complexity. To enable the sharing of computation results in the interpolation for different vectors, a backward interpolation scheme was developed previously to eliminate points from a given interpolation result, which is a Grobner basis. However, this scheme can only eliminate all points in the same code position when their multiplicities are all one and the number of points is one less than the number of polynomials in the Grobner basis. Larger multiplicities are required to achieve better error-correcting performance. Moreover, for general ASD algorithms, the points in the same code position may have different multiplicities. In this paper, a generalized backward interpolation algorithm is proposed through constructing equivalent Grobner basis. It is capable of reducing the multiplicity of each point in the same code position by one at a time until zero, and the multiplicity of each point can be different. As an example, the proposed scheme is applied to a Chase-type decoding that has multiplicity two in the flipping points, and efficient hardware architectures are developed. For a (255, 239) RS code with eight test vectors, employing the proposed backward interpolation leads to 18% area reduction and 23% speedup compared to repeating the interpolation over the flipping points for each test vector.

Compared to binary low-density parity-check (LDPC) codes, nonbinary (NB) LDPC codes can achieve higher coding gain when the codeword length is moderate, but at the cost of higher decoding complexity. One major bottleneck of NB-LDPC decoding is the complicated check node processing. In this paper, a novel relaxed check node processing scheme is proposed for the min-max NB-LDPC decoding algorithm. Each finite field element of GF(2p) can be uniquely represented by a linear combination of p independent field elements. Making use of this property, an innovative method is developed in this paper to first find a set of the p most reliable variable-to-check messages with independent field elements, called the minimum basis. Then, the check-to-variable messages are efficiently computed from the minimum basis. With very small performance loss, the complexity of the check node processing can be substantially reduced using the proposed scheme. In addition, efficient VLSI architectures are developed to implement the proposed check node processing and the overall NB-LDPC decoder. Compared to the most efficient prior design, the proposed decoder for a (837, 726) NB-LDPC code over GF(25) can achieve 52% higher efficiency in terms of throughput-over-area ratio.

Low-density parity-check (LDPC) codes have very broad applications. Low-power LDPC decoder design is becoming increasingly important for wireless and other power-constraint systems. Compared to disabling or simplifying the decoder circuit, reducing the power supply voltage can bring more power reduction. Through predicting the number of iterations needed for convergence, this paper proposes to make full use of the time available for decoding and scale down the power supply voltage in the remaining decoding iterations. Novel iteration prediction schemes are developed. The proposed schemes require very small hardware overhead and do not lead to noticeable error-correcting performance loss. Compared to using the original supply voltage and powering off the decoder after convergence, the proposed schemes can bring 50% dynamic power reduction for an example LDPC code, and the power saving further increases with the signal-to-noise ratio.

Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than their binary counterparts at the cost of higher decoding complexity when the codeword length is moderate. The recently developed iterative reliability-based majority-logic NB-LDPC decoding has better performance-complexity tradeoffs than previous algorithms. This paper first proposes enhancement schemes to the iterative hard reliability-based majority-logic decoding (IHRB-MLGD). Compared to the IHRB algorithm, our enhanced (E-)IHRB algorithm can achieve significant coding gain with small hardware overhead. Then low-complexity partial-parallel NB-LDPC decoder architectures are developed based on these two algorithms. Many existing NB-LDPC code construction methods lead to quasi-cyclic or cyclic codes. Both types of codes are considered in our design. Moreover, novel schemes are developed to keep a small proportion of messages in order to reduce the memory requirement without causing noticeable performance loss. In addition, a shift-message structure is proposed by using memories concatenated with variable node units to enable efficient partial-parallel decoding for cyclic NB-LDPC codes. Compared to previous designs based on the Min-max decoding algorithm, our proposed decoders have at least tens of times lower complexity with moderate coding gain loss.

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

When the code is not long, non-binary low-density parity- check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes at the cost of higher decoding complexity. The recently developed iterative reliability-based majority-logic NB- LDPC decoding can achieve better performance-complexity tradeoffs than previous algorithms. Many existing NB-LDPC code construction schemes lead to quasi-cyclic or cyclic codes. In this paper, efficient low- complexity NB-LDPC decoder architectures are developed for these two types of codes based on the newly proposed iterative hard reliability-based majority-logic decoding (IHRB-MLGD). Particularly, novel schemes are designed to keep a small proportion of messages in order to reduce the memory requirement without causing noticeable performance loss. Moreover, a shift-message structure is proposed by using memories concatenated with variable node units to enable efficient partial-parallel decoding for cyclic NB-LDPC codes. Compared to previous decoders based on the Min-max algorithm, the proposed IHRB-MLGD decoder architectures can achieve tens of times higher efficiency for codes with similar length and rate with moderate coding gain loss.

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.

Layered decoding is well appreciated in low-density parity-check (LDPC) decoder implementation since it can achieve effectively high decoding throughput with low computation complexity. This work, for the first time, addresses low-complexity column-layered decoding schemes and very-large-scale integration (VLSI) architectures for multi-Gb/s applications. At first, the min-sum algorithm is incorporated into the column-layered decoding. Then algorithmic transformations and judicious approximations are explored to minimise the overall computation complexity. Compared to the original column-layered decoding, the new approach can reduce the computation complexity in check node processing for high-rate LDPC codes by up to 90% while maintaining the fast convergence speed of layered decoding. Furthermore, a relaxed pipelining scheme is presented to enable very high clock speed for VLSI implementation. Equipped with these new techniques, an efficient decoder architecture for quasi-cyclic LDPC codes is developed and implemented with 0.13 µm VLSI implementation technology. It is shown that a decoding throughput of nearly 4 Gb/s at a maximum of 10 iterations can be achieved for a (4096, 3584) LDPC code. Hence, this work has facilitated practical applications of column-layered decoding and particularly made it very attractive in high-speed, high-rate LDPC decoder implementation.

With increasing parameter variations in nanometer technologies, on-chip cache in processor is becoming highly vulnerable to runtime failures induced by “soft error,” voltage, or thermal noise and aging effects. Nondeterministic and unreliable memory operation due to these runtime failures can be addressed by: 1) designing the memory for worst-case scenarios and/or 2) runtime error detection and correction. Worst-case guard-banding can lead to overly pessimistic results for cell footprint and power. On the other hand, conventional error correcting code (ECC) used in processor cache has very limited correction capability, making it insufficient to protect memory in scaled technologies (sub-45 nm), which are vulnerable to multiple-bit failures in a word (64-bit). The requirement to tolerate multibit failures is accentuated with supply voltage scaling for low-power operation. We note that due to inter and intra-die parameter variations, different memory blocks move to different reliability corners. A uniform ECC protection for all memory blocks fails to account for the distribution of vulnerability across memory blocks. On the other hand, it can lead to overly pessimistic results if the worst-case vulnerability of a memory block is accounted for during ECC allocation. In this paper, we propose a reliability-driven ECC allocation scheme that matches the relative vulnerability of a memory block (determined using postfabrication characterization) with appropriate ECC protection. We achieve postfabrication variable ECC allocation by storing the check bits in the “ways” of an associative cache. We use shortened Bose-Chaudhuri-Hocquenghem (BCH) cyclic code with zero padding, which provides high random error correction capability with modest amount of check bits. Moreover, we propose efficient circuit/architecture-level optimizations of the ECC encoding/decoding logic to minimize the impact on area, performance, and energy. Simulation results for SPEC2000 benchmarks show that such a variable ECC scheme tolerates high failure rates with negligible performance (four percent) and area (0.2 percent) penalty.

Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes when the code length is moderate at the cost of higher decoding complexity. The high complexity is mainly caused by the complicated computations in the check node processing and the large memory requirement. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding algorithm. The proposed scheme first sorts out a limited number of the most reliable variable-to-check (v-to-c) messages, then the check-to-variable (c-to-v) messages to all connected variable nodes are derived independently from the sorted messages without noticeable performance loss. Compared to the previous iterative forward-backward check node processing, the proposed scheme not only significantly reduced the computation complexity, but eliminated the memory required for storing the intermediate messages generated from the forward and backward processes. Inspired by this novel c-to-v message computation method, we propose to store the most reliable v-to-c messages as “compressed” c-to-v messages. The c-to-v messages will be recovered from the compressed format when needed. Accordingly, the memory requirement of the overall decoder can be substantially reduced. Compared to the previous Min-max decoder architecture, the proposed design for a (837, 726) code overGF(25) can achieve the same throughput with only 46% of the area.

Compressive sensing (CS) is a superior signal sampling strategy that combines sampling and compression. CS-based imaging systems include sampling and reconstruction stages. Currently, the complex task of image reconstruction has only been implemented in software, which can only achieve very limited speed. This paper proposes a high-speed hardware architecture for the reconstruction of compressively-sensed images. The reconstruction algorithm based on the split Bregman method, which solves the ℓ1minimization problem, is first simplified to reduce hardware complexity. Then an efficient partial parallel hardware architecture is developed to implement the modified algorithm. With moderate silicon area, the proposed architecture can reconstruct a 128 × 128 image in 3.82×10-2seconds, which is over 100 times faster than software implementations.

Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes when the code length is moderate. For the first time, this paper proposes a partial-parallel decoder architecture based on the Min-max algorithm for quasi-cyclic NB-LDPC codes. A novel boundary tracking based scheme and corresponding architecture are developed to implement the elementary step of the check node processing. In addition, layered decoding is applied, and the hardware units are optimized to reduce the latency and area. This paper also introduces an overlapped method for the check node processing among different layers to further speed up the decoding. From complexity analysis, the proposed decoder with 5 iterations for a (837,726) code over GF(25) can easily achieve 60 Mbps throughput on ASIC devices. It is 40% more efficient than prior designs.

Generalized minimum distance (GMD) decoding of Reed-Solomon (RS) codes can correct more errors than conventional hard-decision decoding by running error-and-erasure decoding multiple times for different erasure patterns. The latency of the GMD decoding can be reduced by the Kötter's one-pass decoding scheme. This scheme first carries out an error-only hard-decision decoding. Then all pairs of error-erasure locators and evaluators are derived iteratively in one run based on the result of the error-only decoding. In this paper, a more efficient interpolation-based one-pass GMD decoding scheme is studied. Applying the re-encoding and coordinate transformation, the result of erasure-only decoding can be directly derived. Then the locator and evaluator pairs for other erasure patterns are generated iteratively by applying interpolation. In addition, a simplified polynomial selection scheme is proposed to pass only one pair of locator and evaluator to succesive decoding steps. Efficient architectures are employed for the interpolation-based GMD decoder and detailed analysis is provided for the area requirement and decoding latency. With 15% less hardware requirement, the interpolation-based one-pass GMD decoder can reduce the decoding latency to 96% of the Kötter's decoder for a (255, 239) RS code. In terms of speed-over-area ratio, our design is 22% more efficient.

Algebraic soft-decision decoding (ASD) of Reed-Solomon (RS) codes can provide substantial coding gain with polynomial complexity. The major steps of ASD algorithms are the interpolation and factorization. To greatly reduce the complexity of these steps, the re-encoding and coordinate transformation techniques need to be applied. The implementation of these techniques requires a re-encoder and an erasure decoder. In re-encoded and transformed ASD decoders, these two blocks take a significant proportion of the overall area requirement and may limit the maximum achievable speed. A novel re-encoder design is proposed in this paper. In the proposed design, the erasure locator and evaluator polynomials are computed directly through multiplications and other involved computations are reformulated to reduce latency and area requirement. Scalable architectures for the proposed re-encoder are developed. When these architectures are applied to a (255, 239) RS code, our re-encoder can achieve 82% higher throughput than the previous design with 11% less area. With minor modifications, the proposed design can also be used to implement an efficient erasure decoder.

Algebraic soft-decision decoding (ASD) of Reed-Solomon (RS) codes can provide substantial coding gain with polynomial complexity. Among practical ASD algorithms, the Low-complexity Chase (LCC) algorithm can achieve similar or higher coding gain with lower complexity. The major steps of ASD algorithms are the interpolation and factorization. Applying the re-encoding and coordinate transformation, the complexity of these two steps can be greatly reduced at the cost of an extra hard-decision decoder. Backward interpolation has been proposed to enable the sharing of intermediate results among the multiple interpolations of the LCC decoding. However, not much work has been done on further optimizing the factorization step, which consumes a significant proportion of the area and can become a speed bottleneck of the overall decoder. In this paper, a novel scheme is proposed for the LCC decoding to eliminate the factorization step and the key equation solver in the extra hard-decision decoder. Compared to prior LCC decoders, the proposed factorization-free LCC decoder can achieve the same throughput with 19% less area for a (255, 239) RS code with η = 3.

Recently developed algebraic soft-decision (ASD) decoding of Reed-Solomon (RS) codes have attracted much interest due to the fact that they can achieve significant coding gain with polynomial complexity. One major step of ASD decoding is the interpolation. Available interpolation algorithms can only add interpolation points or increase interpolation multiplicities. However, backward interpolation, which eliminates interpolation points or reduces interpolation multiplicities, is indispensable to enable the reusing of interpolation results in the following two scenarios: 1) interpolation needs to be carried out on multiple test vectors, which share common entries and 2) iterative ASD decoding where interpolation points have decreasing multiplicities. Examples for these cases are the low-complexity chase (LCC) decoding and bit-level generalized minimum distance (BGMD) decoding. With lower complexity, these algorithms can achieve similar or higher coding gain than other practical ASD algorithms. In this paper, we propose novel backward interpolation schemes and corresponding efficient implementation architectures for LCC and BGMD decoding through constructing equivalent GrOumlbner bases. The proposed architectures share computational units with forward interpolation architectures. Hence, the area overhead for incorporating the backward interpolation is very small. Substantial area saving or speedup can be achieved by using the backward interpolation. When the proposed architecture is applied to the LCC decoding of a (255, 239) RS code with eta = 3, the area is reduced to 39% of those required by prior architectures. In terms of speed/area ratio, the proposed architecture is 48% more efficient than the best available architecture. For the BGMD decoding of the same code, the proposed architecture can achieve around 20% higher efficiency.

Reed-Solomon (RS) codes are one of the most extensively used error control codes in digital communication and storage systems. Recently, significant advancements have been made on algebraic soft-decision decoding (ASD) of RS codes. These algorithms can achieve substantial coding gain with polynomial complexity. One major step of ASD is the interpolation. Various techniques have been proposed to reduce the complexity of this step. Further speedup of this step is limited by the inherent serial nature of the interpolation algorithm. In this paper, taking the bit-level generalized minimum distance (BGMD) ASD as an example, we propose a novel technique to combine the computations from multiple interpolation iterations. Compared to the single interpolation iteration architecture for a (255, 239) RS code, the combined architecture can achieve 2.7 times throughput with only 2% area overhead in high signal-to-noise ratio scenarios.

In this paper, we present a high-speed FPGA implementation for the factorization step of algebraic soft-decision Reed-Solomon (RS) decoding algorithms. The design is based on the root-order prediction architecture. Parallel processing is exploited to speed up the polynomial updating involved in the factorization. To resolve the data dependency issue in parallel polynomial updating, we propose an efficient coefficient storage and transfer scheme, which leads to smaller memory usage and low latency. Synthesis results show that the factorization processor for a (255, 239) RS code with maximum multiplicity four can achieve an average decoding speed of 226 Mbps on a Xilinx Virtex-II FPGA device when the frame error rate is less than 10−2.

Algebraic soft-decision decoding (ASD) of Reed-Solomon (RS) codes can provide substantial coding gain with polynomial complexity. Among the ASD algorithms with practical multiplicity assignment schemes, the Low-Complexity Chase (LCC) decoding can achieve similar or higher coding gain. Interpolation is a major step in ASD. Since the maximum multiplicity of the interpolation point is only one in LCC, the interpolation over each point has low complexity. However, 2ηtest vectors are involved in the LCC, and the interpolation needs to be carried out on each of them. In order to reduce the computational complexity of the overall interpolation, intermediate results can be stored and shared. Nevertheless, the storage requires large memory, which accounts for a significant portion of the overall hardware requirement of the interpolator. In this paper, we propose a novel interpolation procedure, in which the 2ηtest vectors are mapped to the vertices of a dimension-η hypercube and the vectors mapped to adjacent vertices have only one different entry. In addition, a backward interpolation is proposed to support the traversal from one vertex to its neighbors. Traveling through the entire hypercube, the interpolation over each test vector can be done one after another and the memory requirement is reduced by a factor of 2η-1. Efficient architectures are also developed for the proposed interpolation procedure. With about the same latency and the same number of gates as in prior efforts, our architecture can reduce the memory size to 25% and the number of registers to 57% for a (255, 239) RS code with η = 3. The saving further increases with η.

Reed-Solomon (RS) codes have very broad applications in digital communication and storage systems. Among the decoding algorithms of RS codes, the Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain with a polynomial complexity. One of the major steps of the KV algorithm is the interpolation. Recently, a new algorithm was proposed to solve the interpolation problem. Compared to previous efforts, this algorithm is computationally simpler, and thus can potentially lead to practical high-speed hardware implementations of the KV algorithm. This paper proposes novel transformation techniques to further reduce the hardware complexity of the new interpolation algorithm. In addition, efficient VLSI architectures are provided for the new algorithm

Reed-Solomon (RS) codes are among the most widely utilized error-correcting codes in digital communication and storage systems. Among the decoding algorithms of RS codes, the recently developed Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain, while has a polynomial complexity. One of the major steps of the KV algorithm is the factorization. Each iteration of the factorization mainly consists of root computations over finite fields and polynomial updating. To speed up the factorization step, a fast factorization architecture has been proposed to circumvent the exhaustive-search-based root computation from the second iteration level by using a root-order prediction scheme. Based on this scheme, a partial parallel factorization architecture was proposed to combine the polynomial updating in adjacent iteration levels. However, in both of these architectures, the root computation in the first iteration level is still carried out by exhaustive search, which accounts for a significant part of the overall factorization latency. In this paper, a novel iterative prediction scheme is proposed for the root computation in the first iteration level. The proposed scheme can substantially reduce the latency of the factorization, while only incurs negligible area overhead. Applying this scheme to a (255, 239) RS code, speedups of 36% and 46% can be achieved over the fast factorization and partial parallel factorization architectures, respectively.

Reed-Solomon (RS) codes have very broad applications in communications and data storage systems. The recently developed Koetter-Vardy (KV) soft-decision decoding algorithm of RS codes can achieve substantial coding gain, while has a complexity polynomial with respect to the codeword length. One of the major steps of the KV algorithm is the factorization step. A prediction-based architecture is developed in prior efforts to reduce the latency and silicon area of this step. However, the speedup can be achieved by this approach is limited by the serial nature of the factorization algorithm. The computations involved in multiple iteration levels can not be carried out simultaneously. In this work, a novel partial parallel architecture is proposed for the factorization step. The partial 2-parallel architecture can achieve a speedup of 19% over prior works.

Reed-Solomon (RS) codes are among the most widely utilized error-correcting codes in modern communication and computer systems. Among the decoding algorithms of RS codes, the recently proposed Koetter-Vardy (KV) soft-decision decoding can achieve substantial coding gain, while has a polynomial complexity. One of the major steps of the KV decoding is the factorization. The root computation involved in each iteration level of the factorization is traditionally implemented by exhaustive search. A fast factorization architecture has been proposed to circumvent the exhaustive root search from the second iteration level by using a root-order prediction scheme. However, the root computation in the first iteration level is still carried out by exhaustive search, which accounts for a significant part of the overall factorization latency. In this paper, a novel iterative prediction scheme is proposed to compute the roots in the first iteration level. The proposed scheme can substantially reduce the average latency of the factorization, while only incurs negligible area overhead. Applying this scheme to a (255, 239) RS code, a speedup of 36% can be achieved.

Reed-Solomon (RS) codes are one of the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to hard-decision decoding, soft-decision decoding offers considerably higher error-correcting capability. The Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain, while maintaining a complexity polynomial with respect to the code word length. In the KV algorithm, the interpolation step dominates the decoding complexity. A reduced complexity interpolation architecture is proposed in this paper by eliminating the polynomial updating corresponding to zero discrepancy coefficients in this step. Using this architecture, an area reduction of 27% can be achieved over prior efforts for the interpolation step of a typical (255, 239) RS code, while the interpolation latency remains the same

Reed-Solomon (RS) codes are among the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to its hard-decision counterpart, soft-decision decoding offers considerably higher error-correcting capability. The recent development of soft-decision RS decoding algorithms makes their hardware implementations feasible. Among these algorithms, the Koetter-Vardy (KV) algorithm can achieve substantial coding gain for high-rate RS codes, while maintaining a polynomial complexity with respect to the code length. In the KV algorithm, the factorization step can consume a major part of the decoding latency. A novel architecture based on root-order prediction is proposed in this paper to speed up the factorization step. As a result, the time-consuming exhaustive-search-based root computation in each iteration level, except the first one, of the factorization step is circumvented with more than 99% probability. Using the proposed architecture, a speedup of 141% can be achieved over prior efforts for a (255, 239) RS code, while the area consumption is reduced to 31.4%.

Long Bose-Chaudhuri-Hocquenghen (BCH) codes are used as the outer error correcting codes in the second-generation Digital Video Broadcasting Standard from the European Telecommunications Standard Institute. These codes can achieve around 0.6-dB additional coding gain over Reed-Solomon codes with similar code rate and codeword length in long-haul optical communication systems. BCH encoders are conventionally implemented by a linear feedback shift register architecture. High-speed applications of BCH codes require parallel implementation of the encoders. In addition, long BCH encoders suffer from the effect of large fanout. In this paper, three novel architectures are proposed to reduce the achievable minimum clock period for long BCH encoders after the fanout bottleneck has been eliminated. For an (8191, 7684) BCH code, compared to the original 32-parallel BCH encoder architecture without fanout bottleneck, the proposed architectures can achieve a speedup of over 100%.

Long BCH codes are used as the outer error-correcting code in the second generation of Digital Video Broadcasting Standard from the European Telecommunications Standard Institute. These codes can achieve around 0.6dB additional coding gain over Reed-Solomon codes with similar codeword length and code rate in long-haul optical communication systems. BCH encoders are conventionally implemented by a linear feedback shift register architecture. High-speed applications of BCH codes require parallel implementations of encoders. In addition, long BCH encoders suffer from the effect of large fanout. In this paper, novel architectures are proposed to reduce the achievable minimum clock period of long BCH encoders after the fanout bottleneck has been eliminated. For an (8191, 7684) BCH code, compared to the original 32-parallel BCH encoder architecture without fanout bottleneck, the proposed architectures can achieve a speedup of over 100%.

This paper presents novel high-speed architectures for the hardware implementation of the Advanced Encryption Standard (AES) algorithm. Unlike previous works which rely on look-up tables to implement the SubBytes and InvSubBytes transformations of the AES algorithm, the proposed design employs combinational logic only. As a direct consequence, the unbreakable delay incurred by look-up tables in the conventional approaches is eliminated, and the advantage of subpipelining can be further explored. Furthermore, composite field arithmetic is employed to reduce the area requirements, and different implementations for the inversion in subfield GF(2/sup 4/) are compared. In addition, an efficient key expansion architecture suitable for the subpipelined round units is also presented. Using the proposed architecture, a fully subpipelined encryptor with 7 substages in each round unit can achieve a throughput of 21.56 Gbps on a Xilinx XCV1000 e-8 bg560 device in non-feedback modes, which is faster and is 79% more efficient in terms of equivalent throughput/slice than the fastest previous FPGA implementation known to date.