Error correcting output code (ECOC) is a classic method that encodes binary classifiers to tackle the multi-class classification problem in decision trees and neural networks. Among ECOCs, the one-hot code has become the default choice in modern deep neural networks (DNNs) due to its simplicity in decision making. However, it suffers from a significant limitation in its ability to achieve high robust accuracy, particularly in the presence of weight errors. While recent studies have experimentally demonstrated that the non-one-hot ECOCs with multi-bits error correction ability, could be a better solution, there is a notable absence of theoretical foundations that can elucidate the relationship between codeword design, weight-error magnitude, and network characteristics, so as to provide robustness guarantees. This work is positioned to bridge this gap through the lens of neural tangent kernel (NTK). We have two important theoretical findings: 1) In clean models (without weight errors), utilizing one-hot code and non-one-hot ECOC is akin to altering decoding metrics from $l_2$ distance to Mahalanobis distance. 2) In non-clean models (with weight errors), if the normalized distance exceeds a threshold, then non-clean DNNs can reach the clean model's accuracy as long as the code length approaches infinity. This threshold is determined by DNN architecture (e.g. layer number, activation), weight error magnitude, and the distance between the output and the nearest codeword. Based on these findings, we further demonstrate how to practically use them to identify optimal ECOCs for simple tasks (short-code ECOCs) and complex tasks (long-code ECOCs), by balancing the code orthogonality (as per finding 1) and code distance (as per finding 2). Extensive experimental results across four datasets and four DNN models validate the superior performance of constructed codes, guided by our findings, compared to existing ECOCs. To our best knowledge, this is the first work that provides theoretical explanations for the effectiveness of ECOCS and offers associated design guidance for optimal ECOCs specifically tailored to DNNs.

Error correcting output codes (ECOCs) have been proposed to improve the robustness of deep neural networks (DNNs) against hardware defects of DNN hardware accelerators. Unfortunately, existing efforts suffer from drawbacks that would greatly impact their practicality: 1) robust accuracy (with defects) improvement at the cost of degraded clean accuracy (without defects); 2) no guarantee on better robust or clean accuracy using stronger ECOCs. In this paper, we first shed light on the connection between these drawbacks and error correlation, and then propose a novel comprehensive error decorrelation framework, namely COLA. Specifically, we propose to reduce inner layer feature error correlation by 1) adopting a separated architecture, where the last portions of the paths to all output nodes are separated, and 2) orthogonalizing weights in common DNN layers so that the intermediate features are orthogonal with each other. We also propose a regularization technique based on total correlation to mitigate overall error correlation at the outputs. The effectiveness of COLA is first analyzed theoretically, and then evaluated experimentally, e.g. up to 6.7% clean accuracy improvement compared with the original DNNs and up to 40% robust accuracy improvement compared to the state-of-the-art ECOC-enhanced DNNs.

Implementing deep neural networks (DNNs) in hardware is challenging due to the requirements of huge memory and computation associated with DNNs' primary operation—matrix-vector multiplications (MVMs). Memristive crossbar shows great potential to accelerate MVMs by leveraging its capability of in-memory computation. However, one critical obstacle to such a technique is potentially significant inference accuracy degradation caused by two primary sources of errors—the variations during computation and stuck-at-faults (SAFs). To overcome this obstacle, we propose a set of dedicated schemes to significantly enhance its tolerance against these errors. First, a minimum mean square error (MMSE) based denoising scheme is proposed to diminish the impact of variations during computation in the intermediate layers. To the best of our knowledge, this is the first work considering denoising in the intermediate layers without extra crossbar resources. Furthermore, MMSE early denoising not only stabilizes the crossbar computation results but also mitigates errors caused by low resolution analog-to-digital converters. Second, we propose a weights-to-crossbar mapping scheme by inverting bits to mitigate the impact of SAFs. The effectiveness of the proposed bit inversion scheme is analyzed theoretically and demonstrated experimentally. Finally, we propose to use L1 regularization to increase the network sparsity, as a greater sparsity not only further enhances the effectiveness of the proposed bit inversion scheme, but also facilitates other early denoising mechanisms. Experimental results show that our schemes can achieve 40%-78% accuracy improvement, for the MNIST and CIFAR10 classification tasks under different networks.

Belief Propagation (BP) decoding provides soft outputs and features high-level parallelism. In this paper, we propose an optimized software BP decoder for polar codes on graphics processing units (GPUs). A full-parallel decoding architecture for codes with length n ≤ 2048 is presented to simultaneously update n/2 processing elements (PEs) within each stage and achieve high on-chip memory utilization by using 8-bit quantization. And, for codes with length n > 2048, a partial-parallel decoding architecture is proposed to partly update PEs of each stage in parallel and coalesced global memory accesses are performed. Experimental results show that, with incorporation of the G-matrix based early termination criterion, more than 1 Gbps throughput for codes n ≤ 1024 can be achieved on NVIDIA TITAN Xp at 5 dB while the decoding latency is less than 1 ms. Compared with the state-of-the-art works, the proposed decoder achieves throughput speedups from 2.59× to 131× and provides good tradeoff between error performance and throughput.

Neural networks have shown great potential in many applications like speech recognition, drug discovery, image classification, and object detection. Neural network models are inspired by biological neural networks, but they are optimized to perform machine learning tasks on digital computers. The proposed work explores the possibility of using living neural networks in vitro as the basic computational elements for machine learning applications. A new supervised STDP-based learning algorithm is proposed in this work, which considers neuron engineering constraints. A 74.7% accuracy is achieved on the MNIST benchmark for handwritten digit recognition.

As solid state drives (SSDs) are gradually replacing hard disk drives, error correction is critical to SSDs since NAND flash has deteriorating reliability over their life span. Existing error correction codes suffer from limited error correction capability or error floor issues. Polar codes are promising for SSDs since they are theoretically proven optimal codes and have good error floor behavior. In this paper, we first design multi-rate polar codes for SSDs, and then implement encoder and decoder that simultaneously support multiple rates in FPGA. Multi-rate polar codes provide a good tradeoff between reliability and efficiency. Finally, we use an FPGA emulation platform to evaluate the error performance of our polar codes, and examine their error floor behavior.

The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.

Polar codes are the first provably capacity-achieving forward error correction codes. To improve decoder throughput, the symbol-decision SC algorithm makes hard-decision for multiple bits at a time. In this paper, we prove that for polar codes, the symbol-decision SC algorithm is better than the bit-decision SC algorithm in terms of the frame error rate (FER) performance because the symbol-decision SC algorithm performs a local maximum likelihood decoding within a symbol. Moreover, the bigger the symbol size, the better the FER performance. Finally, simulation results over both the additive white Gaussian noise channel and the binary erasure channel confirm our theoretical analysis.

The belief propagation (BP) decoding algorithm not only is an alternative to the successive cancelation (SC) decoders of polar codes, but also provides soft outputs that are necessary for joint detection and decoding. The BP decoders with the flooding schedule achieve high throughput with excessive hardware cost especially when the block length is large. The soft-cancelation (SCAN) decoders for polar codes have reduced memory complexity compared to the BP decoders based on the flooding schedule. The simplified SC aided reduced complexity soft-cancelation (S-RCSC) decoders further reduce the computational and memory complexity of the SCAN decoders at the cost of negligible error performance degradation. Both the SCAN and S-RCSC decoders have limited throughput due to their serial decoding schedules. In this paper, we first propose an improved S-RCSC (IS-RCSC) decoding algorithm and then present a high throughput decoder architecture based on our IS-RCSC algorithm. Our IS-RCSC decoding algorithm performs the message passing on a binary tree representation of a polar code. Compared to the S-RCSC decoding algorithm, our IS-RCSC decoding algorithm accelerates the computing of the returned soft messages when certain types of nodes are activated. The corresponding hardware architecture of our IS-RCSC decoder is also proposed. In terms of area efficiency, the hardware implementation results demonstrate that our IS-RCSC decoders are 19% to 43% better than decoders in the literature.

While long polar codes can achieve the capacity of arbitrary binary-input discrete memoryless channels when decoded by a low complexity successive-cancellation (SC) algorithm, the error performance of the SC algorithm is inferior for polar codes with finite block lengths. The cyclic redundancy check (CRC)-aided SC list (SCL) decoding algorithm has better error performance than the SC algorithm. However, current CRC-aided SCL decoders still suffer from long decoding latency and limited throughput. In this paper, a reduced latency list decoding (RLLD) algorithm for polar codes is proposed. Our RLLD algorithm performs the list decoding on a binary tree, whose leaves correspond to the bits of a polar code. In existing SCL decoding algorithms, all the nodes in the tree are traversed, and all possibilities of the information bits are considered. Instead, our RLLD algorithm visits much fewer nodes in the tree and considers fewer possibilities of the information bits. When configured properly, our RLLD algorithm significantly reduces the decoding latency and, hence, improves throughput, while introducing little performance degradation. Based on our RLLD algorithm, we also propose a high throughput list decoder architecture, which is suitable for larger block lengths due to its scalable partial sum computation unit. Our decoder architecture has been implemented for different block lengths and list sizes using the TSMC 90-nm CMOS technology. The implementation results demonstrate that our decoders achieve significant latency reduction and area efficiency improvement compared with the other list polar decoders in the literature.

Polar codes are of great interest, since they are the first provably capacity-achieving forward error correction codes. To improve throughput and to reduce decoding latency of polar decoders, maximum likelihood (ML) decoding units are used by successive cancellation list (SCL) decoders as well as SC decoders. This paper proposes an approximate ML (AML) decoding unit for SCL decoders first. In particular, we investigate the distribution of frozen bits of polar codes designed for both the binary erasure and additive white Gaussian noise channels, and take advantage of the distribution to reduce the complexity of the AML decoding unit, improving the throughput-area efficiency of the SCL decoders. Furthermore, a multimode (MM) SCL decoder with variable list sizes and parallelism is proposed. If high throughput or small latency is required, the decoder decodes multiple received words in parallel with a small list size. However, if error performance is of higher priority, the MM-SCL decoder switches to a serial mode with a bigger list size. Therefore, the MM-SCL decoder provides a flexible tradeoff between latency, throughput, and error performance at the expense of small overhead. Hardware implementation and synthesis results show that our polar decoders not only have a better throughput-area efficiency but also easily adapt to different communication channels and applications.

Although the successive cancelation (SC) algorithm works well for very long polar codes, its error performance for shorter polar codes is much worse. Several SC based list decoding algorithms have been proposed to improve the error performances of both long and short polar codes. A significant step of SC based list decoding algorithms is the updating of partial sums for all decoding paths. In this paper, we first proposed a lazy copy partial sum computation algorithm for SC based list decoding algorithms. Instead of copying partial sums directly, our lazy copy algorithm copies indices of partial sums. Based on our lazy copy algorithm, we propose a hybrid partial sum computation unit architecture, which employs both registers and memories so that the overall area efficiency is improved. Compared with a recent partial sum computation unit for list decoders, when the list size L = 4, our partial sum computation unit achieves an area saving of 23% and 63% for block length 213and 215, respectively.

Long polar codes can achieve the symmetric capacity of arbitrary binary-input discrete memoryless channels under a low-complexity successive cancelation (SC) decoding algorithm. However, for polar codes with short and moderate code lengths, the decoding performance of the SC algorithm is inferior. The cyclic-redundancy-check (CRC)-aided SC-list (SCL)-decoding algorithm has better error performance than the SC algorithm for short or moderate polar codes. In this paper, we propose an efficient list decoder architecture for the CRC-aided SCL algorithm, based on both algorithmic reformulations and architectural techniques. In particular, an area efficient message memory architecture is proposed to reduce the area of the proposed decoder architecture. An efficient path pruning unit suitable for large list size is also proposed. For a polar code of length 1024 and rate 1/2, when list size L=2 and 4, the proposed list decoder architecture is implemented under a Taiwan Semiconductor Manufacturing Company (TSMC) 90-nm CMOS technology. Compared with the list decoders in the literature, our decoder achieves 1.24-1.83 times the area efficiency.

In this paper, we propose locally repairable codes (LRCs) with optimal minimum distance for distributed storage systems (DSS). A two-layer encoding structure is employed to ensure data reconstruction and the designated repair locality. The data is first encoded in the first layer by any existing maximum distance separable (MDS) codes, and then the encoded symbols are divided into non-overlapping groups and encoded by an MDS array code in the second layer. The encoding in the second layer provides enough redundancy for local repair, while the overall code performs recovery of the data based on redundancy from both layers. Our codes can be constructed over a finite field with size growing linearly with the total number of nodes in the DSS, and facilitate efficient degraded reads.

Long polar codes achieve the capacity of binary-input discrete memoryless channels when decoded with a successive cancelation (SC) algorithm. For polar codes with short or moderate length, the decoding performance of the SC algorithm is inferior, and the cyclic redundancy check (CRC) aided successive cancelation list (SCL) algorithm achieves significantly improved performance. In this paper, we propose an efficient list decoder architecture for the CRC aided SCL algorithm. Three list decoders with list size L = 2, 4 and 8, respectively, are implemented with a 90nm CMOS technology. Compared to list decoders with L = 2 and 4 in the literature, the proposed list decoders achieve 1.42 and 2.84 times, respectively, higher hardware efficiency. The implementation with list size L = 8 demonstrates that our decoder architecture works for large list sizes.

Nonbinary low-density parity-check (NB-LDPC) codes outperform their binary counterparts in some cases, but their high decoding complexity is a significant hurdle to their applications. In this paper, we propose a decoding algorithm with reduced computational complexities and smaller memory requirements for NB-LDPC codes. First, a simplified algorithm is proposed to reduce the computational complexity of variable node processing. To reduce the memory requirements, existing NB-LDPC decoders often truncate the message vectors to a limited number nmof values. However, the memory requirements of these decoders remain high when the field size is large. In this paper, an improved trellis-based check node processing algorithm is proposed to significantly reduce the memory requirement. The number of elements in a variable-to-check message is reduced to nv(nvm). The sorted log likelihood ratio (LLR) vector of a check-to-variable (c-to-v) message is approximated using a piecewise linear function. For each a priori message, most of the LLRs are approximated with a linear function. Two low complexity LLR generation units (LGUs) are proposed to compute LLR vectors for c-to-v messages. A fully parallel NB-LDPC decoder over GF(256) is implemented with 28-nm CMOS technology. The decoder over GF(256) achieves a throughput of 546 Mb/s and an energy efficiency of 0.178 nJ/b/iter.

As process technologies scale into deep submicrometer region, crosstalk delay is becoming increasingly severe, especially for global on-chip buses. To cope with this problem, accurate delay models of coupled interconnects are needed. In particular, delay models based on analytical approaches are desirable, because they are not only largely transparent to technology, but also explicitly establish the connections between delays of coupled interconnects and transition patterns, thereby enabling crosstalk alleviating techniques such as crosstalk avoidance codes. Unfortunately, existing analytical delay models, such as the widely cited model in [1], have limited accuracy and do not account for loading capacitance. In this brief, we propose analytical delay models for coupled interconnects that address these disadvantages.

Since all packets in linear network coding are subject to linear combinations, in all existing network coding schemes, a full rank of received packets is required to start decoding. This requirement unfortunately results in long delays and low throughputs. In this work we propose two classes of rank deficient decoders that work for rank deficient received packets. Within either class, different decoding strategies have been proposed for tradeoffs between delay/throughput and data accuracy. The decoders of the first class take advantage of the sparsity inherent in data and produce the data vectors with the smallest Hamming weight. Since these decoders have high complexities, we propose a class of decoders with polynomial complexities based on linear programming. Both classes of decoders can recover data from fewer received packets and hence achieve higher throughputs and shorter delays than the full rank decoder.

Non-binary low-density parity-check (NB-LDPC) codes outperform their binary counterparts in some cases, but their high decoding complexity is a significant hurdle to their applications. In this paper, we propose a decoding algorithm with reduced computational complexities and smaller memory requirements for NB-LDPC codes over large fields. First, a simplified algorithm is proposed to reduce the computational complexity of variable node processing. To reduce memory requirements, existing NB-LDPC decoders often truncate the message vectors to a limited number nmof values. However, the memory requirements of these decoders remain high when the field size is large, since nmneeds to be large enough to alleviate error performance degradation. In this paper, an improved trellised based check node processing algorithm is proposed to significantly reduce the memory requirement. The number of elements in a variable-to-check message is reduced to nv(nvm). The sorted log likelihood ratio (LLR) vector of a check-to-variable message is approximated using a piece-wise linear function. Thus, only few LLRs are stored and other LLRs are computed on-the-fly when needed. For each a priori message, most LLRs are approximated with a linear function. Our numerical results demonstrate that the proposed decoding algorithm outperforms existing algorithms. Two LLR generation units (LGUs) are proposed to compute LLR vectors for check-to-variable messages, and the two LGUs require only a fraction of the area needed to store nmLLRs.

Non-binary low-density parity-check (NB-LDPC) codes have some advantages as opposed to their binary counterparts, but unfortunately their decoding complexity is a significant challenge. Hence, iterative hard-reliability-based majority-logic decoding (IHRB-MLGD) algorithms are attractive for NB-LDPC codes due to their low complexities. In this paper, we propose a layered improved iterative hard-reliability-based majority-logic decoding algorithm and design a partly parallel architecture for the proposed algorithm. Our improved algorithm achieves better error performance and faster convergence than existing IHRB-MLGD algorithms, while maintaining low complexities. The proposed partly parallel architecture achieves a throughput of 779 Mbps with SMIC 0.13um CMOS technology.

In this brief, a shuffled schedule (SS) of the min-max decoding algorithm is proposed for nonbinary low-density parity-check (LDPC) codes. To increase the throughput and reduce the memory requirement, a modified SS (MSS) with much simpler check node processing is also proposed, based on a new shuffled merge algorithm. Numerical simulations for three LDPC codes with different lengths and rates over GF(32) show: 1) both SS and MSS converge faster and have slightly better error performance than the flooding schedule, and 2) the degradation of the MSS in error performance as well as convergence rate is negligible. Finally, an efficient decoder architecture based on the MSS is proposed for quasi-cyclic LDPC codes. The proposed decoder architecture further enhances the decoding throughput with improved check and variable node processing units. The implementation results of an (837, 726) LDPC decoder over GF(32) demonstrate that the proposed architecture outperforms those in previous works.

The crosstalk delay associated with global on-chip interconnects becomes more severe in deep submicrometer technology, and hence can greatly affect the overall system performance. Based on a delay model proposed by Sotiriadis , transition patterns over a bus can be classified according to their delays. Using this classification, crosstalk avoidance codes (CACs) have been proposed to alleviate the crosstalk delays by restricting the transition patterns on a bus. In this paper, we first propose a new classification of transition patterns, and then devise a new family of CACs based on this classification. In comparison to the previous classification, our classification has more classes and the delays of its classes do not overlap, both leading to more accurate control of delays. Our new family of CACs includes some previously proposed codes as well as new codes with reduced delays and improved throughput. Thus, this new family of CACs provides a wider variety of tradeoffs between bus delay and efficiency. Finally, since our analytical approach to the classification and CACs treats the technology-dependent parameters as variables, our approach can be easily adapted to a wide variety of technologies.

In this paper, a shuffled schedule of the Min-Max decoding algorithm is proposed for nonbinary LDPC codes. To reduce the latency and memory requirement, a modified shuffled schedule with much simpler check node processing is also proposed, based on a new shuffle sort algorithm. Numerical simulations for three LDPC codes over GF(32) with different lengths and rates show: (1) both the shuffled and modified shuffled schedule converge faster and have slightly better error performance than the flooding schedule, and (2) the degradation of the modified shuffled schedule in error performance as well as convergence rate is negligible.

While random linear network coding is a powerful tool for disseminating information in communication networks, it is highly susceptible to errors caused by various sources. Due to error propagation, errors greatly deteriorate the throughput of network coding and seriously undermine both reliability and security of data. Hence, error control for network coding is vital. Recently, constant-dimension codes (CDCs), especially Kötter-Kschischang (KK) codes, have been proposed for error control in random linear network coding. KK codes can also be constructed from Gabidulin codes, an important class of rank metric codes. Rank metric decoders have been recently proposed for both Gabidulin and KK codes, but they have high computational complexities. Furthermore, it is not clear whether such decoders are feasible and suitable for hardware implementations. In this paper, we reduce the complexities of rank metric decoders and propose novel decoder architectures for both codes. The synthesis results of our decoder architectures for Gabidulin and KK codes with limited error-correcting capabilities over small fields show that our architectures not only are affordable, but also achieve high throughput.

Low-complexity CODECs for two classes of crosstalk avoidance codes (CACs), forbidden pattern codes (FPCs) and forbidden transition codes (FTCs), have been recently proposed based on Fibonacci-based binary numeral system. In this paper, we first generalize this idea and establish a generic framework for the CODEC design of all classes of CACs based on binary mixed-radix numeral systems. Using this framework, we then propose novel CODEC designs for three important classes of CACs, one lambda codes (OLCs), FPCs, and forbidden overlapping codes (FOCs). Our CODEC designs have area complexity and delay that increase quadratically with the size of the bus, while achieving optimal or nearly optimal code rates. Our CODECs also have simple and regular circuitry, and can easily achieve very high throughput by pipelining. Our efficient CODECs, used with such techniques as partial coding, help to make CACs a practical option in combating crosstalk delay, which is a bottleneck in deep submicrometer system-on-chip designs.

How to cope with the complexities of sophisticated multiple-input multiple-output (MIMO) techniques is critical to realizing these MIMO techniques in real-life applications. In this paper, we propose a list-based soft-decision MIMO detection algorithm based on the memory constraint tree search algorithm. Our algorithm achieves a flexible tradeoff between the memory requirement and computational complexity by tuning the number of available memory units. In comparison with the list sphere decoding detector, our algorithm has reduced computational complexity; as opposed to the list sequential detector, our algorithm achieves similar computational complexity while requiring much less memory. Hence, our algorithm is suitable for hardware implementations.

Codes in the projective space and codes in the Grassmannian over a finite field-referred to as subspace codes and constant-dimension codes (CDCs), respectively-have been proposed for error control in random linear network coding. For subspace codes and CDCs, a subspace metric was introduced to correct both errors and erasures, and an injection metric was proposed to correct adversarial errors. In this paper, we investigate the packing and covering properties of subspace codes with both metrics. We first determine some fundamental geometric properties of the projective space with both metrics. Using these properties, we then derive bounds on the cardinalities of packing and covering subspace codes, and determine the asymptotic rates of optimal packing and optimal covering subspace codes with both metrics. Our results not only provide guiding principles for the code design for error control in random linear network coding, but also illustrate the difference between the two metrics from a geometric perspective. In particular, our results show that optimal packing CDCs are optimal packing subspace codes up to a scalar for both metrics if and only if their dimension is half of their length (up to rounding). In this case, CDCs suffer from only limited rate loss as opposed to subspace codes with the same minimum distance. We also show that optimal covering CDCs can be used to construct asymptotically optimal covering subspace codes with the injection metric only.

Constant-dimension codes have recently received attention due to their significance to error control in noncoherent random linear network coding. What the maximal cardinality of any constant-dimension code with finite dimension and minimum distance is and how to construct the optimal constant-dimension code (or codes) that achieves the maximal cardinality both remain open research problems. In this paper, we introduce a new approach to solving these two problems. We first establish a connection between constant-rank codes and constant-dimension codes. Via this connection, we show that optimal constant-dimension codes correspond to optimal constant-rank codes over matrices with sufficiently many rows. As such, the two aforementioned problems are equivalent to determining the maximum cardinality of constant-rank codes and to constructing optimal constant-rank codes, respectively. To this end, we then derive bounds on the maximum cardinality of a constant-rank code with a given minimum rank distance, propose explicit constructions of optimal or asymptotically optimal constant-rank codes, and establish asymptotic bounds on the maximum rate of a constant-rank code.

Both area and throughput are significant for hardware implementations of the Advanced Encryption Standard (AES). Previous works mostly focused on area without providing full control on critical path delay (CPD), which ultimately determines throughput. To address this issue, we propose a delay-aware common subexpression elimination (DACSE) algorithm that is novel in two aspects: it not only takes advantage of implicit common subexpressions to further reduce area, but also minimizes area while satisfying any feasible CPD requirement. Using our DACSE algorithm, we propose high-performance designs for two major transformations of the AES, MixColumns and SubBytes. Compared with prior works, our designs achieve the same or shorter CPDs with the same or smaller gate counts.

Constant-dimension codes (CDCs) have been investigated for noncoherent error correction in random network coding. The maximum cardinality of CDCs with given minimum distance and how to construct optimal CDCs are both open problems, although CDCs obtained by lifting Gabidulin codes, referred to as KK codes, are nearly optimal. In this paper, we first construct a new class of CDCs based on KK codes, referred to as augmented KK codes, whose cardinalities are greater than previously proposed CDCs. We then propose a low-complexity decoding algorithm for our augmented KK codes using that for KK codes. Our decoding algorithm corrects more errors than a bounded subspace distance decoder by taking advantage of the structure of our augmented KK codes. In the rest of the paper we investigate the covering properties of CDCs. We first derive bounds on the minimum cardinality of a CDC with a given covering radius and then determine the asymptotic behavior of this quantity. Moreover, we show that liftings of rank metric codes have the highest possible covering radius, and hence liftings of rank metric codes are not optimal packing CDCs. Finally, we construct good covering CDCs by permuting liftings of rank metric codes.

Constant-dimension codes (CDCs) have been considered for error correction in random linear network coding, and low-complexity bounded distance decoders have been proposed. However, error performance, decoder error probability (DEP) in particular, of these bounded distance decoders has received little attention. In this paper, we first establish some fundamental geometric properties of the projective space. In particular, we show that the volume of the intersection of two spheres depends on only the two radii as well as the distance between and the dimensions of the two centers. Using these geometric properties, we then consider bounded distance decoders in both subspace and injection metrics and derive analytical expressions of their DEPs for CDCs over a symmetric operator channel, which ultimately depend on their distance distributions. Finally, we focus on CDCs obtained by lifting rank metric codes since their distance distributions are known, and obtain two important results. First, we obtain asymptotically tight upper bounds on the DEPs of bounded distance decoders in both metrics; the upper bounds decrease exponentially with the square of the minimum distance. Second, we show that the DEP for KK codes, obtained by lifting Gabidulin codes, is the highest up to a scalar among all CDCs obtained by lifting rank metric codes.

Codes in the projective space over a finite field, referred to as subspace codes, and in particular codes in the Grassmannians, referred to as constant-dimension codes (CDCs), have been proposed for error control in random network coding. In this paper, we study the packing and covering properties of subspace codes, which can be used with the subspace metric or the injection metric. We first determine some fundamental geometric properties of the projective space. Using these results, we derive bounds on the cardinalities of packing and covering subspace codes, and determine the asymptotic rate of optimal packing and optimal covering subspace codes for both metrics. We thus show that optimal packing CDCs are asymptotically optimal packing subspace codes for both metrics. However, optimal covering CDCs can be used to construct asymptotically optimal covering subspace codes only for the injection metric.

The extended Euclidean algorithm (EEA) for polynomial greatest common divisors is commonly used in solving the key equation in the decoding of Reed-Solomon (RS) codes, and more generally in BCH decoding. For this particular application, the iterations in the EEA are stopped when the degree of the remainder polynomial falls below a threshold. While determining the degree of a polynomial is a simple task for human beings, hardware implementation of this stopping rule is more complicated. This paper describes a modified version of the EEA that is specifically adapted to the RS decoding problem. This modified algorithm requires no degree computation or comparison to a threshold, and it uses a fixed number of iterations. Another advantage of this modified version is in its application to the errors-and-erasures decoding problem for RS codes where significant hardware savings can be achieved via seamless computation.

In this paper, we reduce the computational complexities of partial and dual partial cyclotomic FFTs (CFFTs), which are discrete Fourier transforms where spectral and temporal components are constrained, based on their properties as well as a common subexpression elimination algorithm. Our partial CFFTs achieve smaller computational complexities than previously proposed partial CFFTs. Utilizing our CFFTs in both transform- and time-domain Reed-Solomon decoders, we achieve significant complexity reductions.

We propose turbo-sum-product (TSP) and shuffled-sum-product (SSP) decoding algorithms for quasi-cyclic low-density parity-check codes, which not only achieve faster convergence and better error performance than the sum-product algorithm, but also require less memory in partly parallel decoder architectures. Compared with the turbo decoding algorithm, our TSP algorithm saves the same amount of memory and may achieve a higher decoding throughput. The convergence behaviors of our TSP and SSP algorithms are also compared with those of the SP, turbo, and shuffled algorithms by their extrinsic information transfer (EXIT) charts.

Efficient hardware implementation of the Advanced Encryption Standard (AES) is important due to its widespread applications. Applying a novel common subexpression elimination (CSE) algorithm to the two major transformations of the AES, MixColumns and SubBytes, we propose compact designs of the transformations. The hardware costs of our implementations are either the same as or smaller than those of prior works.

We propose a low-complexity soft detector for coded MIMO systems, which generates soft information by combining the hard-decision maximum likelihood (ML) estimate with the soft information generated by the minimum mean square error (MMSE) detector. The hard-decision ML estimate is produced by a modified MMSE based sphere decoder (MMSE-SD). The MMSE-SD is desired since it has lower average and worst-case computational complexity than the zero-forcing (ZF) based SD (ZF-SD) and can be used for arbitrary MIMO configurations. The proposed modification simplifies the implementation of the MMSE-SD, and it can be efficiently implemented by previously proposed complex ZF-SD architecture with minor modification. Our soft detector offers a low-complexity alternative when list based soft detectors are not affordable.

Constant-dimension codes have recently received attention due to their significance to error control in noncoherent random network coding. In this paper, we show that constant-rank codes are closely related to constant-dimension codes and we study the properties of constant-rank codes. We first introduce a relation between vectors in GF(qm)nand subspaces of GF(q)mor GF(q)n, and use it to establish a relation between constant-rank codes and constant-dimension codes. We then derive bounds on the maximum cardinality of constant-rank codes with given rank weight and minimum rank distance. Finally, we investigate the asymptotic behavior of the maximal cardinality of constant-rank codes with given rank weight and minimum rank distance.

In this correspondence, we first introduce the concept of elementary linear subspace, which has similar properties to those of a set of coordinates. We then use elementary linear subspaces to derive properties of maximum rank distance (MRD) codes that parallel those of maximum distance separable codes. Using these properties, we show that, for MRD codes with error correction capability , the decoder error probability of bounded rank distance decoders decreases exponentially with based on the assumption that all errors with the same rank are equally likely.

This paper investigates packing and covering properties of codes with the rank metric. First, we investigate packing properties of rank metric codes. Then, we study sphere covering properties of rank metric codes, derive bounds on their parameters, and investigate their asymptotic covering properties.

Efficient hardware implementation of low-density parity-check (LDPC) codes is of great interest since LDPC codes are being considered for a wide range of applications. Recently, overlapped message passing (OMP) decoding has been proposed to improve the throughput and hardware utilization efficiency (HUE) of decoder architectures for LDPC codes. In this paper, we first study the scheduling for the OMP decoding of LDPC codes, and show that maximizing the throughput gain amounts to minimizing the intra- and inter-iteration waiting times. We then focus on the OMP decoding of quasi-cyclic (QC) LDPC codes. We propose a partly parallel OMP decoder architecture and implement it using FPGA. For any QC LDPC code, our OMP decoder achieves the maximum throughput gain and HUE due to overlapping, hence has higher throughput and HUE than previously proposed OMP decoders while maintaining the same hardware requirements. We also show that the maximum throughput gain and HUE achieved by our OMP decoder are ultimately determined by the given code. Thus, we propose a coset-based construction method, which results in QC LDPC codes that allow our optimal OMP decoder to achieve higher throughput and HUE.

In this paper, we investigate the covering properties of rank metric codes. We first study the properties of balls with rank radii, and derive several useful results. We then derive both upper and lower bounds on the minimal cardinality of a code with given length and rank covering radius. Using these bounds, we obtain some covering properties of linear rank metric codes.

This paper investigates the relationship between the rank weight distribution of a linear code and that of its dual code. The main result of this paper is that, similar to the MacWilliams identity for the Hamming metric, the rank weight distribution of any linear code can be expressed as an analytical expression of that of its dual code. Remarkably, our new identity has a similar form to the MacWilliams identity for the Hamming metric. Our identity is also closely related to Delsarte's MacWilliams identity for the q-distance. We use a linear space based approach in the proof for our new identity, and adapt this approach to provide an alternative proof of the MacWilliams identity for the Hamming metric. Finally, we determine the relationship between moments of the rank distribution of a linear code and those of its dual code, and provide an alternative derivation of the rank weight distribution of maximum rank distance codes.

In this correspondence, first-tier indirect (direct) discernible constellation expansions are defined for generalized orthogonal designs. The expanded signal constellation, leading to so-called super-orthogonal codes, allows the achievement of coding gains in addition to diversity gains enabled by orthogonal designs. Conditions that allow the shape of an expanded multidimensional constellation to be preserved at the channel output, on an instantaneous basis, are derived; this property, referred to as fading resilience, is first discussed in the context of quasi-static fading, then generalized to coordinate interleaved transmissions for rapid fading. In both cases - and despite of piecing together (in the latter case) a constellation point as a result of coordinate deinterleaving - the channel alters neither the relative distances nor the angles between signal points in a fading-resilient signal constellation. It is shown that nonorthogonal MIMO constellations having a geometric structure that is resilient to fading do exist, and their further study is warranted.

In this paper, we study properties of rank metric codes in general and maximum rank distance (MRD) codes in particular. For codes with the rank metric, we first establish Gilbert and sphere-packing bounds, and then obtain the asymptotic forms of these two bounds and the Singleton bound. Based on the asymptotic bounds, we observe that asymptotically Gilbert-Varsharmov bound is exceeded by MRD codes and sphere-packing bound cannot be attained. We also establish bounds on the rank covering radius of maximal codes, and show that all MRD codes are maximal codes and all the MRD codes known so far achieve the maximum rank covering radius.

In this paper, we first propose a parallel turbo-sum-product (PTSP) decoding algorithm for quasi-cyclic (QC) low-density parity-check codes, and show that our proposed algorithm achieves better error performance and faster convergence than the sum-product (SP) or overlapped SP (OSP) algorithm. Based on our PTSP algorithm, we then propose a partly parallel decoder architecture, which requires smaller memory size, less memory access and power consumption, and simpler control than decoder architectures based on the OSP algorithm.

The Gabidulin-Paramonov-Tretjakov (GPT) public-key cryptosystem and the GPT system with column scrambler, both based on Gabidulin codes, seem to have some advantages over McEliece's public-key cryptosystems using Goppa codes. Since the parameters of the GPT-type systems affect the work factors of attacks in different fashions and determine the effectiveness of these attacks in some cases, we evaluate the security and study the choice of parameters of the GPT-type cryptosystems with respect to some well-known structural and decoding attacks jointly. The performances of the GPT system with column scrambler and the GPT system are compared with that of McEliece's system

In this paper, we first present a general scheduling model for the overlapped message passing (OMP) decoding of LDPC codes, and show that maximizing the throughput amounts to minimizing the intra- and inter-iteration waiting times. Then we focus on maximizing the throughput for OMP decoders of quasi-cyclic (QC) LDPC codes using a partly parallel hardware structure, which can be modelled as a data dependency and hardware constrained optimization problem. Finally, we propose a scheduling scheme, which gives the optimal solution to the optimization problem under certain conditions. In comparison to previously proposed scheduling schemes, our new scheduling scheme leads to both higher hardware utilization efficiency (HUE) and greater throughput gain.

Many high-throughput two-dimensional architectures for finite field inversion and division are based on reformulations of the extended Euclidean algorithm (EEA). These reformulated EEAs usually keep track of two pairs of data polynomials (or registers), and the operations of the reformulated EEAs are only within each pair of polynomials. In this paper, we propose a new reformulated EEA wherein the operations within the two pairs of polynomials are identical. Hence, the two pairs of polynomials in our new reformulated EEA can be concatenated into one pair. By utilizing some inherent properties of the EEA, we further reduce the computational complexity of our reformulated EEA by 25%. Based on our reformulated EEA, we propose new two-dimensional inversion and division architectures. How much hardware saving the reduced computational complexity translates into depends on how control mechanisms are implemented. Regardless of the implementation of control signals, our new architectures require smaller numbers of gates and latches while achieving comparable or better throughput, latency, and critical path delay in comparison to the best architectures in the literature.

Universal Reed-Solomon decoders allow flexibility in some or all of the code parameters,and hence lend themselves to applications wherein adaptability and reconfigurability are important considerations. In this paper,we consider universal finite field arithmetics using either canonical polynomial basis or shifted polynomial basis, and propose a high-speed universal Reed-Solomon decoder by modifying the high-speed decoder proposed in [10 ].

Based on a new reformulation of the extended Euclidean algorithm, systolic architectures suitable for VLSI implementations are proposed for finite field inversion and division in this paper. The architectures proposed in this paper can achieve O(m2) area-time complexity, O(m) latency, and critical path delays of two logic gates. These architectures show improved performances when compared with previously proposed architectures.

The continued relevance of the Euclidean distance in (flat) fading scenarios renders meaning to distance preserving properties for codes designed for fading channels. Geometrical uniformity can shed more light on the structure of various techniques for jointly encoding across multiple transmit antennas, and can assist in the design of, or systematic search for, better coding schemes. In this correspondence, a family of space-time codes introduced by Ionescu et al. is treated as signal space codes, then proved to be generalized coset codes, and thereby geometrically uniform. It is then shown that geometrical uniformity does remain meaningful in fading channels, for an optimally designed space-time code.

We present two systolic architectures for inversion and division in GF(2/sup m/) based on a modified extended Euclidean algorithm. Our architectures are similar to those proposed by others in that they consist of two-dimensional arrays of computing cells and control cells with only local intercell connections and have O(m/sup 2/) area-time product. However, in comparison to similar architectures, both our architectures have critical path delays that are smaller, gate counts that range from being considerably smaller to only slightly larger, and latencies that are identical for inversion but somewhat larger for division. One architecture uses an adder or an (m+l)-bit ring counter inside each control cell, while the other architecture distributes the ring counters into the computing cells, thereby reducing each control cell to just two gates.