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.

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.

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.

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.

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.

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.