The growing adoption of self-supervised learning transformers for speech (speech SSL) is constrained by their significant computational and memory demands, making deployment on resource-constrained edge devices challenging. We propose a latency-aware compression framework that integrates structured pruning and quantization to address these challenges. Guided by a latency model that considers the combined effects of pruning and quantization, our method dynamically identifies and removes less critical blocks while maintaining task performance, avoiding the inefficiencies of over-pruning and under-pruning seen in prior approaches. Unlike prior methods specialized in either post-training compression without fine-tuning data or in cases where fine-tuning data is available, our method is effective in both settings. Experimental results show that, in task-agnostic compression, our method achieves a 4.2× speedup on the Hikey970 edge development platform, outperforming previous task-agnostic pruning methods in most tasks, while requiring only 21–24 GPU hours—a 3× reduction compared to prior methods. Additionally, our method achieves a lower word error rate of 7.8% using task-specific pruning, while reducing computational overhead by approximately 19.4% in terms of GFLOPs compared to previous task-specific methods. Finally, our method consistently achieves higher accuracy than the state-of-the-art post-training compression approach across various latency speedup constraints, even without fine-tuning data.

To extend the applications of polar codes within next-generation wireless communication systems, it is essential to incorporate support for Incremental Redundancy (IR) Hybrid Automatic Repeat Request (HARQ) schemes. The baseline IRHARQ scheme's reliance on set-based operations leads to irregular memory access patterns, posing significant challenges for efficient hardware implementation. Furthermore, the introduction of new bit types increases the number of fast nodes that are decoded without traversing the sub-tree, resulting in a substantial area overhead when implemented in hardware. To address these issues and improve hardware compatibility, we propose transforming the set-based operations within the polar IR-HARQ scheme into binary vector operations. Additionally, we introduce a new fast node integration approach that avoids increasing the number of fast nodes, thereby minimizing the associated area overhead. Our proposed scheme results in a memory overhead of$25-27 \%$compared to successive cancellation list (SCL) decoding without IR-HARQ support.

Projection-aggregation decoders have been used in conjunction with a list structure to achieve near maximum-likelihood decoding for short-length and low-rate Reed-Muller (RM) codes but suffer from high computational complexity. We reduce the worst-case computational complexity of projection-aggregation (PA) decoders by more than 50% using a scheduling scheme compared to PA decoders without the scheduling scheme, and propose a redesigned syndrome check pattern to avoid repeated syndrome computations in the decoder. A latency model based on the existing hardware architecture is proposed. Input distribution aware (IDA) decoding is adopted as a pre-possessing tool, and the average list size when using IDA decoding is analytically derived under additive white Gaussian noise and uncorrelated normalized Rayleigh fading channels. Using IDA, the average list size is reduced by 30% with less than 0.1 dB loss. The proposed list decoders require a smaller computational complexity than the state-of-the-art iterative decoder, automorphism ensemble decoding with the belief propagation constituent decoder (AED-BP) for decoding RM(7, 3) and RM(8, 3) codes. Based on the developed latency models, the PA list decoder has a smaller latency than the AED-BP and the successive cancellation list decoder to reach near maximum-likelihood decoding performance.

The ultrareliable low-latency communication (URLLC) application scenario requires the adoption of short linear block codes to satisfy the low-latency requirements. Guessing random additive noise decoding (GRAND) is a prominent universal decoding solution for short linear block codes that lends itself to efficient hardware implementations. GRAND-based hardware implementations generally offer reduced average decoding latency but their high worst-case (W.C.) latency renders them unsuitable for deployment in mission-critical applications. This article presents an improved version of step-GRAND, a soft-input variant of GRAND that features a novel test error pattern (TEP) generating approach. A novel very large-scale integration (VLSI) architecture is developed for the execution of the improved step-GRAND algorithm with reduced W.C. decoding latency. Application specific integrated circuit (ASIC) implementation results, employing low-power (LP) TSMC 65-nm CMOS technology, demonstrate that the proposed improved step-GRAND can achieve an average decoding latency as low as 10 ns for decoding a$(128,105)$linear block code at a target frame error rate (FER) of$10^{-7}$, while the W.C. decoding latency can reach$300~\text {ns}\sim 1~\mu \text { s}$depending on the parametric settings. Compared with the previously proposed baseline soft-input ordered reliability bits GRAND (ORBGRAND) hardware implementation with similar decoding performance at target FER of$10^{-7}$, the improved step-GRAND hardware achieves$7 \times \sim 17\times $reduction in W.C. latency,$7\times $reduction in power consumption, and$37 \times \sim 66\times $higher area efficiency in the W.C. scenario. Furthermore, the proposed hardware can achieve an average throughput of up to 10.5 Gb/s and a W.C. throughput of$102\sim 350$Mb/s.

Polar codes encounter challenges in decoder complexity while preserving good error-correction properties. Instead of conventional decoders, a quantum annealer (QA) decoder has been proposed to explore untapped possibilities. For future QA applications, a crucial prerequisite is transforming the optimization problem into quadratic unconstrained binary optimization (QUBO) form. However, existing QUBO forms for polar decoding result in suboptimal frame error rate (FER) performance for codes exceeding 8 bits. This paper redesigns the QUBO form for polar decoding. We first introduce a novel receiver constraint modeled by the binary cross-entropy (BCE) function. Utilizing a simulated annealing (SA) solver with the proposed QUBO form with BCE (QUBO-BCE) achieves maximum-likelihood (ML) performance for a code length of 32 bits. Next, to reduce the number of variables, we remove the frozen variables and introduce a simplified QUBO-BCE form (SQUBO-BCE). Additionally, CRC polynomials are modelled into constraints in QUBO form, resulting in a CRC-aided SQUBO-BCE (CA-SQUBO-BCE) form for polar decoding to further enhance the FER. Numerical results demonstrate that SQUBO-BCE achieves ML performance and reduces up to 61.5% of variables compared to QUBO-BCE. Furthermore, the proposed CA-SQUBO-BCE achieves near CRC-aided ML performance. The proposed SQUBO-BCE requires the lowest number of SA processes to reach a specific FER.

Grouped convolution has been observed to be an effective approximation for convolution in many DNN applications. For example, SqueezeBERT, which is a light and fast BERT language processing model, utilizes 1D grouped convolutions. Though SqueezeBERT is well-optimized for inference on edge devices, it suffers from poor memory management during fine-tuning (training). This results in longer fine-tuning time on resource-limited GPUs compared to the original BERT model, BERT-base, despite being specifically designed for edge devices. We study this behavior and show that this poor memory management originates from the use of 1D grouped convolutions in SqueezeBERT. We re-implement 1D grouped convolutions using fully-connected layers, addressing the poor memory allocation and data locality of 1D grouped convolutions. We show that our method is well-suited for edge devices with limited memory; further, it has a negligible effect on inference speed. When utilizing our method, we observe a 42 % reduction in fine-tuning time for SqueezeBERT on edge devices.

There has been growing interest in improving the BERT inference throughput on resource-constrained edge devices for a satisfactory user experience. One methodology is to employ heterogeneous computing, which utilizes multiple processing elements to accelerate inference. Another methodology is to deploy Neural Architecture Search (NAS) to find optimal solutions in accuracy-throughput design space. In this paper, for the first time, we incorporate NAS with pipelining for BERT models. We show that performing NAS with pipelining achieves on average 53% higher throughput, compared to NAS with a homogeneous system.

Reducing the complexity of training convolutional neural networks results in lower energy consumption expended during training, or higher accuracy by admitting a greater number of training epochs within a training time budget. During backpropagation, a considerable amount of temporary data is offloaded from GPU memory to CPU memory, increasing training time. In this paper, we address this training time overhead by introducing an activation compression technique for frequency domain convolutional neural networks. Applying this compression technique on frequency domain AlexNet results in activation compression of 57.7%, and a reduction of training time by 23%, with a negligible effect on classification accuracy.

Guessing random additive noise decoding (GRAND) and sphere decoding (SD) are two algorithms that can achieve maximum likelihood decoding. In this paper, a hybrid GRAND-SD (HGRAND) scheme is proposed to extend GRAND to low-rate codes. An accelerated GRAND decoder, assisted by a sphere decoder running in parallel and giving hints to it to allow skipping of certain candidates allows HGRAND to achieve a latency below the minimum latency of the individual component decoders while guaranteeing error-correction performance.

Guessing Random Additive Noise Decoding (GRAND) excels at decoding high-rate codes but struggles to decode low-rate codes with reasonable complexity. Ordered Statistics Decoding (OSD) specifically excels in decoding short codes irrespective of rates; however, OSD necessitates the use of Gaussian elimination which introduces additional time, space and computational complexity. Partial Ordered Statistics Decoding (POSD) was proposed to reduce the time, space, and computational complexity of OSD; however, the current partition-based POSD has poor decoding performance since it does not generate test error patterns across partitions. In this paper, we propose to improve the decoding performance of POSD by incorporating test error patterns inspired by GRAND methods. This work offers a trade-off between performance and complexity compared to existing decoders such as GRAND and OSD. We enhance POSD by optimizing the scheduling of Test Error Patterns (TEPs) and show that our technique can be applied to any code in a standard form. At a target BER 10−4with eBCH (128,64) the enhanced error patterns achieve more than 0.6 dB gain in performance compared to the POSD with partition-based error patterns. Moreover, at a target frame error rate of 10−5, POSD uses 10× less binary operations compared to GRAND when decoding eBCH (128,64) and RLC(128,64) codes. With BCH (127,29) and RLC(128,32), at a target frame error rate of 10−2, POSD with enhanced error patterns with a maximum number of queries (MQ) of 104achieves up to a 2 dB gain to its GRAND equivalent which is using 107maximum number of queries.

Probabilistic bits (p-bits) have recently been presented as a spin (basic computing element) for the simulated annealing (SA) of Ising models. In this brief, we introduce fast-converging SA based on p-bits designed using integral stochastic computing. The stochastic implementation approximates a p-bit function, which can search for a solution to a combinatorial optimization problem at lower energy than conventional p-bits. Searching around the global minimum energy can increase the probability of finding a solution. The proposed stochastic computing-based SA method is compared with conventional SA and quantum annealing (QA) with a D-Wave Two quantum annealer on the traveling salesman, maximum cut (MAX-CUT), and graph isomorphism (GI) problems. The proposed method achieves a convergence speed a few orders of magnitude faster while dealing with an order of magnitude larger number of spins than the other methods.

Guessing random additive noise decoding (GRAND) is a recently proposed universal maximum likelihood (ML) decoder for short-length and high-rate linear block codes. Soft-GRAND (SGRAND) is a prominent soft-input GRAND variant, outperforming the other GRAND variants in decoding performance; nevertheless, SGRAND is not suitable for parallel hardware implementation. Ordered Reliability Bits-GRAND (ORBGRAND) is another soft-input GRAND variant that is suitable for parallel hardware implementation; however, it has lower decoding performance than SGRAND. In this article, we propose List-GRAND (LGRAND), a technique for enhancing the decoding performance of ORBGRAND to match the ML decoding performance of SGRAND. Numerical simulation results show that LGRAND enhances ORBGRAND’s decoding performance by 0.5–0.75 dB for channel codes of various classes at a target frame error rate (FER) of 10−7. For linear block codes of length 127/128 and different code rates, LGRAND’s VLSI implementation can achieve an average information throughput of 47.27–51.36 Gb/s. In comparison to ORBGRAND’s VLSI implementation, the proposed LGRAND hardware has a 4.84% area overhead.

To meet DNN inference latency constraints on resource-constrained edge devices, we employ heterogeneous computing, utilizing multiple processing elements (e.g. CPU + GPU) accelerate inference. This leads to the challenge of efficiently mapping DNN operations to heterogeneous processing elements. For this task, we introduce a novel genetic algorithm (GA) optimizer. Through intelligent initialization and a customized mutation operation, we are able to evaluate 20x fewer generations while finding superior configurations compared with a baseline GA. Using our mapping optimizer, we find device placement configurations that achieve 15%, 24%, and 31% inference speed-up for BERT, SqueezeBERT, and InceptionV3,respectively.

We present SuperNAS, a fast multi-objective neural architecture search framework for semantic segmentation. SuperNAS subsamples the structure and pre-trained parameters of DeepLabV3+, without fine-tuning, dramatically reducing training time during search. To further reduce candidate evaluation time, we use a subset of the validation dataset during search. Only the final, Pareto-dominant, candidates are ultimately fine-tuned using the complete training set. We evaluate SuperNAS by searching for models that effectively trade accuracy and computational cost on the PASCAL VOC 2012 dataset. SuperNAS finds competitive designs quickly, e.g., taking just 0.5 GPU days to discover a DeepLabV3+ variant that reduces FLOPs and parameters by 10% and 20% respectively, for less than 3% increased error.

With the increased size and complexity of state-of-the-art language models such as BERT, deploying them on resource-constrained devices has become challenging. Latency-aware Neural Architecture Search (NAS) is an effective solution for finding an efficient implementation of complex models that satisfy hardware limitations. However, collecting on-device accuracy and latency feedback would significantly slow down the search process, making NAS impractical. To address this, we propose a low-cost method that models both accuracy and latency of BERT-based models on the target device, NVIDIA Jetson TX2, and removes the hardware-related delays from the search loop. Using a Random Forest regressor, our predictors outperform the state-of-the-art and achieve up to 57x speedup while finding a set of near-optimal models.

Knowledge distillation (KD) is an effective tool for compressing deep classification models for edge devices. However, the performance of KD is affected by the large capacity gap between the teacher and student networks. Recent methods have resorted to a multiple teacher assistant (TA) setting for KD, which sequentially decreases the size of the teacher model to relatively bridge the size gap between these models. This paper proposes a new technique called Curriculum Expert Selection for Knowledge Distillation (CES-KD) to efficiently enhance the learning of a compact student under the capacity gap problem. This technique is built upon the hypothesis that a student network should be guided gradually using stratified teaching curriculum as it learns easy (hard) data samples better and faster from a lower (higher) capacity teacher network. Specifically, our method is a gradual TA-based KD technique that selects a single teacher per input image based on a curriculum driven by the difficulty in classifying the image. In this work, we empirically verify our hypothesis and rigorously experiment with CIFAR-10, CIFAR-100, CINIC-10, and ImageNet datasets and show improved accuracy on VGG-like models, ResNets, and WideResNets architectures.

Resource-constrained devices are increasingly the deployment targets of machine learning applications. Static models, however, do not always suffice for dynamic environments. On-device training of models allows for quick adaptability to new scenarios. With the increasing size of deep neural networks, as noted with the likes of BERT and other natural language processing models, comes increased resource requirements, namely memory, computation, energy, and time. Furthermore, training is far more resource intensive than inference. Resource-constrained on-device learning is thus doubly difficult, especially with large BERT-like models. By reducing the memory usage of fine-tuning, pre-trained BERT models can become efficient enough to fine-tune on resource-constrained devices. We propose Freeze And ReconFigure (FAR), a memory-efficient training regime for BERT-like models that reduces the memory usage of activation maps during fine-tuning by avoiding unnecessary parameter updates. FAR reduces fine-tuning time on the DistilBERT model and CoLA dataset by 30 %, and time spent on memory operations by 47%. More broadly, reductions in metric performance on the GLUE and SQuAD datasets are around 1% on average.

A novel recursive list decoding (RLD) algorithm for Reed-Muller (RM) codes based on successive permutations (SP) of the codeword is presented. A low-complexity SP scheme applied to a subset of the symmetry group of RM codes is first proposed to carefully select a good codeword permutation on the fly. Then, the proposed SP technique is integrated into an improved RLD algorithm that initializes different decoding paths with random codeword permutations, which are sampled from the full symmetry group of RM codes. Finally, efficient latency and complexity reduction schemes are introduced that virtually preserve the error-correction performance of the proposed decoder. Simulation results demonstrate that at the target frame error rate of 10−3 for the RM code of length 256 with 163 information bits, the proposed decoder reduces 6% of the computational complexity and 22% of the decoding latency of the state-of-the-art semi-parallel simplified successive-cancellation decoder with fast Hadamard transform (SSC-FHT) that uses 96 permutations from the full symmetry group of RM codes, while relatively maintaining the error-correction performance and memory consumption of the semi-parallel permuted SSC-FHT decoder.

Ultrareliable low-latency communication (URLLC), a major 5G new-radio (NR) use case, is the key enabler for applications with strict reliability and latency requirements. These applications necessitate the use of short-length and high-rate channel codes. Guessing random additive noise decoding (GRAND) is a recently proposed maximum likelihood (ML) decoding technique for these short-length and high-rate codes. Rather than decoding the received vector, GRAND tries to infer the noise that corrupted the transmitted codeword during transmission through the communication channel. As a result, GRAND can decode any code, structured or unstructured. GRAND has hard-input as well as soft-input variants. Among these variants, ordered reliability bits GRAND (ORBGRAND) is a soft-input variant that outperforms hard-input GRAND and is suitable for parallel hardware implementation. This work reports the first hardware architecture for ORBGRAND, which achieves an average throughput of up to 42.5 Gb/s for a code length of 128 at a target frame error rate (FER) of 10−7. Furthermore, the proposed hardware can be used to decode any code as long as the length and rate constraints are met. In comparison to the GRAND with ABandonment (GRANDAB), a hard-input variant of GRAND, the proposed architecture enhances decoding performance by at least 2 dB. When compared to the state-of-the-art fast dynamic successive cancellation flip decoder (Fast-DSCF) using a 5G polar code (PC) (128, 105), the proposed ORBGRAND VLSI implementation has$49\times $higher average throughput,$32\times $times more energy efficiency, and$5\times $more area efficiency while maintaining similar decoding performance.

Guessing Random Additive Noise Decoding (GRAND) is a recently proposed approximate Maximum Likelihood (ML) decoding technique that can decode any linear error-correcting block code. Ordered Reliability Bits GRAND (ORBGRAND) is a powerful variant of GRAND, which outperforms the original GRAND technique by generating error patterns in a specific order. Moreover, their simplicity at the algorithm level renders GRAND family a desirable candidate for applications that demand very high throughput. This work reports the first-ever hardware architecture for ORBGRAND, which achieves an average throughput of up to 42.5 Gbps for a code length of 128 at an SNR of 10 dB. Moreover, the proposed hardware can be used to decode any code provided the length and rate constraints. Compared to the state-of-the-art fast dynamic successive cancellation flip decoder (Fast-DSCF) using a 5G polar (128,105) code, the proposed VLSI implementation has 49× more average throughput while maintaining similar decoding performance.

While in the past several decades the trend to go towards increasing error-correcting code lengths was predominant to get closer to the Shannon limit, applications that require short block length are developing. Therefore, decoding techniques that can achieve near-maximum-likelihood (near-ML) are gaining momentum. This overview paper surveys recent progress in this emerging field by reviewing the GRAND algorithm, linear programming decoding, machine-learning aided decoding and the recursive projection-aggregation decoding algorithm. For each of the decoding algorithms, both algorithmic and hardware implementations are considered, and future research directions are outlined.

In this paper, we introduce a novel bit-flipping algorithm for fast successive cancellation (FSC) decoding of polar codes. In particular, we first propose a new bit-flipping strategy tailored to single parity-check (SPC) constituent codes of polar codes. A parameterized bit-flipping model is then developed and reinforcement learning (RL) is used to optimize the parameters. Our experimental results show that for a polar code of length 512 with 256 information bits, the proposed decoder has a better or similar error-correction performance compared to the state-of-the-art fast DSCF (FDSCF) decoding algorithm when the same number of maximum decoding attempts is considered.

Invertible logic using a probabilistic magnetoresistive device model has been recently presented that can compute functions in bidirectional ways and solve several problems quickly, such as factorization and combinational optimization. In this article, we present a design framework for invertible logic circuits. Our approach makes use of linear programming to create a Hamiltonian library with the minimum number of nodes for small invertible-logic functions. In addition, as the device model is approximated based on stochastic computing in synthesizable SystemVerilog, a faster simulation using the compiled SystemC binary is realized than a conventional SPICE-level simulation and is verified using field-programmable gate array (FPGA) as prototyping. Using our design framework, several invertible-logic circuits are designed and emulated (verified) in SystemC, exhibiting five order-of-magnitude faster simulation than conventional work.

With the advent of deeper, larger and more complex convolutional neural networks (CNN), manual design has become a daunting task, especially when hardware performance must be optimized. Sequential model-based optimization (SMBO) is an efficient method for hyperparameter optimization on highly parameterized machine learning (ML) algorithms, able to find good configurations with a limited number of evaluations by predicting the performance of candidates before evaluation. A case study on MNIST shows that SMBO regression model prediction error significantly impedes search performance in multi-objective optimization. To address this issue, we propose probabilistic SMBO, which selects candidates based on probabilistic estimation of their Pareto efficiency. With a formulation that incorporates error in accuracy prediction and uncertainty in latency measurement, probabilistic Pareto efficiency quantifies a candidate's quality in two ways: its likelihood of being Pareto optimal, and the expected number of current Pareto optimal solutions that it will dominate. We evaluate our proposed method on four image classification problems. Compared to a deterministic approach, probabilistic SMBO consistently generates Pareto optimal solutions that perform better, and that are competitive with state-of-the-art efficient CNN models, offering tremendous speedup in inference latency while maintaining comparable accuracy.

In this paper we address the problem of selecting factor-graph permutations of polar codes under belief propagation (BP) decoding to significantly improve the error-correction performance of the code. In particular, we formalize the factor-graph permutation selection as the multi-armed bandit problem in reinforcement learning and propose a decoder that acts like an online-learning agent that learns to select the good factor-graph permutations during the course of decoding. We use state-of-the-art algorithms for the multi-armed bandit problem and show that for a 5G polar codes of length 128 with 64 information bits, the proposed decoder has an error-correction performance gain of around 0.125 dB at the target frame error rate of 10-4, when compared to the approach that randomly selects the factor-graph permutations.

SC-Flip (SCF) decoding is a low-complexity polar code decoding algorithm alternative to SC-List (SCL) algorithm with small list sizes. To achieve the performance of the SCL algorithm with large list sizes, the Dynamic SC-Flip (DSCF) algorithm was proposed. However, DSCF involves logarithmic and exponential computations that are not suitable for practical hardware implementations. In this work, we propose a simple approximation that replaces the transcendental computations of DSCF decoding. Moreover, we show how to incorporate fast decoding techniques with the DSCF algorithm. With proposed approaches, the computational complexity of DSCF decoding is remarkably reduced while maintaining equivalent decoding performance.

SC-Flip (SCF) decoding algorithm shares the attention with the common polar code decoding approaches due to its low-complexity and improved error-correction performance. However, the inefficient criterion for locating the correct bit-flipping position in SCF decoding limits its improvements. Due to its improved bit-flipping criterion, Thresholded SCF (TSCF) decoding algorithm exhibits a superior error-correction performance and lower computational complexity than SCF decoding. However, the parameters of TSCF decoding depend on multiple channel and code parameters, and are obtained via Monte-Carlo simulations. Our main goal is to realize TSCF decoding as a practical polar decoder implementation. To this end, we first realize an approximated threshold value that is independent of the code parameters and precomputations. The proposed approximation has negligible error-correction performance degradation on the TSCF decoding. Then, we validate an alternative approach for forming a critical set that does not require precomputations, which also paves the way to the implementation of the Fast-TSCF decoder. Compared to the existing fast SCF implementations, the proposed Fast-TSCF decoder has 0.24 to 0.41 dB performance gain at frame error rate of 10-3, without any extra cost. Compared to the TSCF decoding, Fast-TSCF does not depend on precomputations and requires 87% fewer decoding steps. Finally, implementation results in TSMC 65nm CMOS technology show that the Fast-TSCF decoder is 20% and 82% more area-efficient than the state-of-the-art fast SCF and fast SC-List decoder architectures, respectively.

In stochastic computing, values are represented as sequences of random bits and arithmetic computations are computed on the bit streams. Since bit-wise operations are performed on random bit streams, stochastic computing offers low-cost error-tolerant architectures for its hardware implementations. In stochastic computing, complex arithmetic operations can be computed using linear finite state machines (FSMs). However, the synthesis of a linear FSM for a given target function is nontrivial. In this paper, we exploit linear regression and demonstrate a general approach to synthesize linear FSMs for stochastic computations. We show that our approach outperforms traditional numerical synthesis methods in terms of mean-squared error. We also demonstrate that fault-tolerance of FSMs synthesized using linear regression can be improved by injecting noise during the synthesis phase, allowing the synthesized functions to tolerate up to 35% of random bit flips.

With the growing research and application of deep learning, there are increasing demands in the ability to re-train or improve models with new data in the field. The popular backpropagation algorithm are very effective when training large models offline, however, it requires considerable computational resources. Equilibrium Propagation is an energy based learning algorithm for neural networks proposed as an alternative to the traditional back propagation algorithm. With the forward and backward phase using almost the same computation, the algorithm is an interesting candidate for implementing on-chip learning. As a first step towards building the hardware, we apply quantization on the algorithm to study the feasibility of a digital implementation. We then introduce a hardware oriented network pruning method to reduce the number of computations and the memory usage by a factor of 2.7. This paper lays the foundation for the implementation of Equilibrium Propagation on digital hardware, and an provides alternative angle to the problem of on-chip learning.

A finite-state machine (FSM) is a computation model to process binary strings in sequential circuits. Hence, a single-input linear FSM is conventionally used to implement complex single-input functions , such as tanh and exponentiation functions, in stochastic computing (SC) domain where continuous values are represented by sequences of random bits. In this paper, we introduce a method that can train a multi-layer FSM-based network where FSMs are connected to every FSM in the previous and the next layer. We show that the proposed FSM-based network can synthesize multi-input complex functions such as 2D Gabor filters and can perform non-sequential tasks such as image classifications on stochastic streams with no multiplication since FSMs are implemented by look-up tables only. Inspired by the capability of FSMs in processing binary streams, we then propose an FSM-based model that can process time series data when performing temporal tasks such as character-level language modeling. Unlike long short-term memories (LSTMs) that unroll the network for each input time step and perform back-propagation on the unrolled network, our FSM-based model requires to backpropagate gradients only for the current input time step while it is still capable of learning long-term dependencies. Therefore, our FSM-based model can learn extremely long-term dependencies as it requires 1/l memory storage during training compared to LSTMs, where l is the number of time steps. Moreover, our FSM-based model reduces the power consumption of training on a GPU by 33% compared to an LSTM model of the same size.

Convolutional neural networks (CNNs) are a vital approach in machine learning. However, their high complexity and energy consumption make them challenging to embed in mobile applications at the edge requiring real-time processes such as smart phones. In order to meet the real-time constraint of edge devices, recently proposed custom hardware CNN accelerators have exploited parallel processing elements (PEs) to increase throughput. However, this straightforward parallelization of PEs and high memory bandwidth require high data movement, leading to large energy consumption. As a result, only a certain number of PEs can be instantiated when designing bandwidth-limited custom accelerators targeting edge devices. While most bandwidth-limited designs claim a peak performance of a few hundred giga operations per second, their average runtime performance is substantially lower than their roofline when applied to state-of-the-art CNNs such as AlexNet, VGGNet and ResNet, as a result of low resource utilization and arithmetic intensity. In this work, we propose a zero-activation-skipping convolutional accelerator (ZASCA) that avoids noncontributory multiplications with zero-valued activations. ZASCA employs a dataflow that minimizes the gap between its average and peak performances while maximizing its arithmetic intensity for both sparse and dense representations of activations, targeting the bandwidth-limited edge computing scenario. More precisely, ZASCA achieves a performance efficiency of up to 94 percent over a set of state-of-the-art CNNs for image classification with dense representation where the performance efficiency is the ratio between the average runtime performance and the peak performance. Using its zero-skipping feature, ZASCA can further improve the performance efficiency of the state-of-the-art CNNs by up to 1.9× depending on the sparsity degree of activations. The implementation results in 65-nm TSMC CMOS technology show that, compared to the most energy-efficient accelerator, ZASCA can process convolutions from 5.5× to 17.5× faster, and is between 2.1× and 4.5× more energy efficient while occupying 2.1× less silicon area.

Long Short-Term Memory (LSTM) is a special class of recurrent neural network, which has shown remarkable successes in processing sequential data. The typical architecture of an LSTM involves a set of states and gates: the states retain information over arbitrary time intervals and the gates regulate the flow of information. Due to the recursive nature of LSTMs, they are computationally intensive to deploy on edge devices with limited hardware resources. To reduce the computational complexity of LSTMs, we first introduce a method that learns to retain only the important information in the states by pruning redundant information. We then show that our method can prune over 90% of information in the states without incurring any accuracy degradation over a set of temporal tasks. This observation suggests that a large fraction of the recurrent computations are ineffectual and can be avoided to speed up the process during the inference as they involve noncontributory multiplications/accumulations with zero-valued states. Finally, we introduce a custom hardware accelerator that can perform the recurrent computations using both sparse and dense states. Experimental measurements show that performing the computations using the sparse states speeds up the process and improves energy efficiency by up to 5.2× when compared to implementation results of the accelerator performing the computations using dense states.

Visible light communication (VLC) provides a short- range optical wireless communication through light- emitting diode (LED) lighting. Light beam flickering and dimming are among the challenges to be addressed in VLC. Conventional methods for generating flicker-free codes in VLC are based on run-length limited codes that have poor error correction performance, use lookup tables which are memory consuming, and have low transmission rates. In this paper, we propose an efficient construction of flicker-free forward error correction codes to tackle the issue of flickering in VLC. Our simulation results show that by using polar codes and at a dimming ratio of 50%, the proposed system generates flicker-free codes without using lookup tables, while having lower complexity and higher transmission rates than the standard VLC methods. For an information block length of 256, the error correction performance of the proposed scheme is 1.8 dB and 0.9 dB better than that of the regular schemes at the bit error rate of 10^{-6} for a rate of 0.44 and 0.23, respectively.

Polar codes are a class of capacity-achieving error correcting codes that have been selected for use in enhanced mobile broadband in the 3GPP 5thgeneration (5G) wireless standard. Most polar code research examines the original Arkan polar coding scheme, which is limited in block length to powers of two. This constraint presents a considerable obstacle since practical applications call for all code lengths to be readily available. Puncturing and shortening techniques allow for flexible polar codes, while multi-kernel polar codes produce native code lengths that are powers of two and or three. In this work, we propose a new low complexity coding scheme called asymmetric polar coding that allows for any arbitrary block length. We present details on the generator matrix, frozen set design, and decoding schedule. Our scheme offers flexible polar code lengths with decoding complexity lower than equivalent state-of-the-art length-compatible approaches under successive cancellation decoding. Further, asymmetric decoding complexity is directly dependent on the codeword length rather than the nearest valid polar code length. We compare our scheme with other length matching techniques, and simulations are presented. Results show that asymmetric polar codes present similar error correction performance to the competing schemes, while dividing the number of SC decoding operations by up to a factor of 2 using the same codeword length.

Polar codes are the first class of error correcting codes that provably achieve the channel capacity at infinite code length. They were selected for use in the fifth generation of cellular mobile communications (5G). In practical scenarios such as 5G, a cyclic redundancy check (CRC) is concatenated with polar codes to improve their finite length performance. This is mostly beneficial for sequential successive-cancellation list decoders. However, for parallel iterative belief propagation (BP) decoders, CRC is only used as an early stopping criterion with incremental error-correction performance improvement. In this paper, we first propose a CRC-polar BP (CPBP) decoder by exchanging the extrinsic information between the factor graph of the polar code and that of the CRC. We then propose a neural CPBP (NCPBP) algorithm which improves the CPBP decoder by introducing trainable normalizing weights on the concatenated factor graph. Our results on a 5G polar code of length 128 show that at the frame error rate of 10-5and with a maximum of 30 iterations, the error-correction performance of CPBP and NCPBP are approximately 0.25 dB and 0.5 dB better than that of the conventional CRC-aided BP decoder, respectively, while introducing almost no latency overhead.

Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported.

The emergence of XNOR networks seek to reduce the model size and computational cost of neural networks for their deployment on specialized hardware requiring real-time processes with limited hardware resources. In XNOR networks, both weights and activations are binary, bringing great benefits to specialized hardware by replacing expensive multiplications with simple XNOR operations. Although XNOR convolutional and fully-connected neural networks have been successfully developed during the past few years, there is no XNOR network implementing commonly-used variants of recurrent neural networks such as long short-term memories (LSTMs). The main computational core of LSTMs involves vector-matrix multiplications followed by a set of non-linear functions and element-wise multiplications to obtain the gate activations and state vectors, respectively. Several previous attempts on quantization of LSTMs only focused on quantization of the vector-matrix multiplications in LSTMs while retaining the element-wise multiplications in full precision. In this paper, we propose a method that converts all the multiplications in LSTMs to XNOR operations using stochastic computing. To this end, we introduce a weighted finite-state machine and its synthesis method to approximate the non-linear functions used in LSTMs on stochastic bit streams. Experimental results show that the proposed XNOR LSTMs reduce the computational complexity of their quantized counterparts by a factor of 86x without any sacrifice on latency while achieving a better accuracy across various temporal tasks.

Polar codes are a class of linear error correction codes which provably attain channel capacity with infinite codeword lengths. Finite length polar codes have been adopted into the 5th Generation 3GPP standard for New Radio, though their native length is limited to powers of 2. Utilizing multiple polarizing matrices increases the length flexibility of polar codes at the expense of a more complicated decoding process. Successive cancellation (SC) is the standard polar decoder and has time complexity O(N log N) due to its sequential nature. However, some patterns in the frozen set mirror simple linear codes with low latency decoders, which allows for a significant reduction in SC latency by pruning the decoding schedule. Such fast decoding techniques have only previously been used for traditional Arikan polar codes, causing multi-kernel polar codes to be an impractical length-compatibility technique with no fast decoders available. We propose fast simplified successive cancellation decoding node patterns, which are compatible with polar codes constructed with both the Arikan and ternary kernels, and generalization techniques. We outline efficient implementations, made possible by imposing constraints on ternary node parameters. We show that fast decoding of multi-kernel polar codes has at least 72% reduced latency compared with an SC decoder in all cases considered where codeword lengths are (96, 432, 768, 2304).

The interest in polar codes has been increasing significantly since their adoption for use in the 5thgeneration wireless systems standard. Successive cancellation (SC) decoding algorithm has low implementation complexity, but yields mediocre error-correction performance at the code lengths of interest. SC-Flip algorithm improves the error-correction performance of SC by identifying possibly erroneous decisions made by SC and re-iterates after flipping one bit. It was recently shown that only a portion of bit-channels are most likely to be in error. In this paper, we investigate the average log-likelihood ratio (LLR) values and their distribution related to the erroneous bit-channels, and develop the Thresholded SC-Flip (TSCF) decoding algorithm. We also replace the LLR selection and sorting of SC-Flip with a comparator to reduce the implementation complexity. Simulation results demonstrate that for practical code lengths and a wide range of rates, TSCF shows negligible loss compared with the error-correction performance obtained when all single-errors are corrected. At matching maximum iterations, TSCF has an error-correction performance gain of up to 0.45 dB compared with SC-Flip decoding. At matching error-correction performance, the computational complexity of TSCF is reduced by up to 40% on average and requires up to 5× lower maximum number of iterations.

Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10-4.

Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency and soft output with a high hardware cost. A form of approximate computing called stochastic computing provides a low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. Multiple methods at the algorithm and architecture levels are presented to further speed up convergence and hardware efficiency.

Polar codes are a class of channel capacity achieving codes that has been selected for the next generation of wireless communication standards. Successive-cancellation (SC) is the first proposed decoding algorithm, suffering from mediocre errorcorrection performance at moderate code lengths. In order to improve the error-correction performance of SC, two approaches are available: (i) SC-List decoding which keeps a list of candidates by running a number of SC decoders in parallel, thus increasing the implementation complexity, and (ii) SC-Flip decoding that relies on a single SC module, and keeps the computational complexity close to SC. In this work, we propose the partitioned SC-Flip (PSCF) decoding algorithm, which outperforms SCFlip in terms of error-correction performance and average computational complexity, leading to higher throughput and reduced energy consumption per codeword. We also introduce a partitioning scheme that best suits our PSCF decoder. Simulation results show that at equivalent frame error rate, PSCF has up to 4.1× less computational complexity than the SC-Flip decoder. At equivalent average number of iterations, the error-correction performance of PSCF outperforms SC-Flip by up to 0.26 dB at frame error rate of 10-3.

Parallel processors and GP-GPUs have been routinely used in the past to perform the computations of convolutional neural networks (CNNs). However, their large power consumption has pushed researchers towards application-specific integrated circuits and on-chip accelerators implement neural networks. Nevertheless, within the Internet of Things (IoT) scenario, even these accelerators fail to meet the power and latency constraints. To address this issue, binary-weight networks were introduced, where weights are constrained to -1 and 1. Therefore, these networks facilitate hardware implementation of neural networks by replacing multiply-and-accumulate units with simple accumulators, as well as reducing the weight storage. In this paper, we introduce a convolutional accelerator for binary-weight neural networks. The proposed architecture only consumes 128 mW at a frequency of 200 MHz and occupies 1.2 mm2when synthesized in TSMC 65 nm CMOS technology. Moreover, it achieves a high area-efficiency of 176 Gops/MGC and performance efficiency of 89%, outperforming the state-of-the-art architecture for binary-weight networks by 1.8× and 3.2×, respectively.

Polar codes are a recent class of linear error-correcting codes that asymptotically achieve the channel capacity at infinite code length. The Successive Cancellation List (SCL) algorithm yields very good error-correction performance, at the cost of high implementation complexity. The Stack (SCS) decoding algorithm provides similar error-correction performance at a lower complexity. In this work, we propose an efficient software implementation of the SCS decoding algorithm, along with techniques to further reduce its computational complexity. In particular, we reduce the SCS memory requirements through efficient path switching, replace the stack sorting with a linear search, and explore the use of a partial CRC along with an early termination criterion. Using the proposed methods, we are able to reduce the computational complexity of the SCS decoder, reducing the number of estimated bits up to 97% with respect to SCL, while maintaining similar error-correction performance as SCL.

Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption. In this paper, we consider the paradigm of PSCL decoding from a practical standpoint, and we provide several improvements. First, by changing the target signal-to-noise ratio and consequently modifying the construction of the code, we are able to improve the performance at no additional computational, latency, or memory cost. Second, we bridge the performance gap between SCL and PSCL decoding by introducing a generalized PSCL decoder and a layered PSCL decoder. In this way, we obtain almost the same performance of the SCL decoder with a significantly lower memory requirement, as testified by hardware implementation results. Third, we present an optimal scheme to allocate cyclic redundancy checks. Finally, we provide a lower bound on the list size that guarantees optimal maximum a posteriori performance for the binary erasure channel.

This paper proposes a “quasi-synchronous” design approach for signal processing circuits, in which timing violations are permitted, but without the need for a hardware compensation mechanism. The case of a low-density parity-check (LDPC) decoder is studied, and a method for accurately modeling the effect of timing violations at a high level of abstraction is presented. The error-correction performance of code ensembles is then evaluated using density evolution, while taking into account the effect of timing faults. Following this, several quasi-synchronous LDPC decoder circuits based on the offset min-sum algorithm are optimized, providing a 23%-40% reduction in energy consumption or energy-delay product, while achieving the same performance and occupying the same area as conventional synchronous circuits.

Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption [1]. In this paper, we examine the paradigm of PSCL decoding from both theoretical and practical standpoints: (i) by changing the construction of the code, we are able to improve the performance at no additional computational, latency or memory cost, (ii) we present an optimal scheme to allocate cyclic redundancy checks (CRCs), and (iii) we provide an upper bound on the list size that allows MAP performance.

Despite the importance of distributed learning, few fully distributed support vector machines exist. In this paper, not only do we provide a fully distributed nonlinear SVM; we propose the first distributed constrained-form SVM. In the fully distributed context, a dataset is distributed among networked agents that cannot divulge their data, let alone centralize the data, and can only communicate with their neighbors in the network. Our strategy is based on two algorithms: the Douglas-Rachford algorithm and the projection-gradient method. We validate our approach by demonstrating through simulations that it can train a classifier that agrees closely with the centralized solution.

Recently, it was shown that if multiplicative weights are assigned to the edges of a Tanner graph used in belief propagation decoding, it is possible to use deep learning techniques to find values for the weights which improve the error-correction performance of the decoder. Unfortunately, this approach requires many multiplications, which are generally expensive operations. In this paper, we suggest a more hardware-friendly approach in which offset min-sum decoding is augmented with learnable offset parameters. Our method uses no multiplications and has a parameter count less than half that of the multiplicative algorithm. This both speeds up training and provides a feasible path to hardware architectures. After describing our method, we compare the performance of the two neural decoding algorithms and show that our method achieves error-correction performance within 0.1 dB of the multiplicative approach and as much as 1 dB better than traditional belief propagation for the codes under consideration.

The hardware implementation of deep neural networks (DNNs) has recently received tremendous attention: many applications in fact require high-speed operations that suit a hardware implementation. However, numerous elements and complex interconnections are usually required, leading to a large area occupation and copious power consumption. Stochastic computing (SC) has shown promising results for low-power area-efficient hardware implementations, even though existing stochastic algorithms require long streams that cause long latencies. In this paper, we propose an integer form of stochastic computation and introduce some elementary circuits. We then propose an efficient implementation of a DNN based on integral SC. The proposed architecture has been implemented on a Virtex7 field-programmable gate array, resulting in 45% and 62% average reductions in area and latency compared with the best reported architecture in the literature. We also synthesize the circuits in a 65-nm CMOS technology, and we show that the proposed integral stochastic architecture results in up to 21% reduction in energy consumption compared with the binary radix implementation at the same misclassification rate. Due to fault-tolerant nature of stochastic architectures, we also consider a quasi-synchronous implementation that yields 33% reduction in energy consumption with respect to the binary radix implementation without any compromise on performance.

Stochastic computing (SC) has received much recent attention due to its inherent fault-tolerance and low implementation cost compared to binary radix representations. SC has been proposed for various signal processing applications such as digital filters. The prior art in stochastic FIR filters can accurately implement the desired filtering function for low-order filters, however, their accuracy degrades as the filter order increases. Moreover, stochastic IIR filters demonstrate high hardware complexity and degraded accuracy. In this paper, we propose an architecture for high-order FIR filters with negligible accuracy loss compared to fixed-point implementation. The proposed architecture requires fewer random number generators. We also describe a novel cascaded second-order direct-form II structure for IIR filters. The implementation results of the proposed design show an improvement in latency and hardware complexity compared to the stochastic architectures reported to date.

Successive-cancellation list (SCL) decoding is an algorithm that provides very good error-correction performance for polar codes. However, its hardware implementation requires a large amount of memory, mainly to store intermediate results. In this paper, a partitioned SCL algorithm is proposed to reduce the large memory requirements of the conventional SCL algorithm. The decoder tree is broken into partitions that are decoded separately. We show that with careful selection of list sizes and number of partitions, the proposed algorithm can outperform conventional SCL while requiring less memory.

Artificial neural networks have gone through a recent rise in popularity, achieving state-of-the-art results in various fields, including image classification, speech recognition, and automated control. Both the performance and computational complexity of such models are heavily dependant on the design of characteristic hyper-parameters (e.g., number of hidden layers, nodes per layer, or choice of activation functions), which have traditionally been optimized manually. With machine learning penetrating low-power mobile and embedded areas, the need to optimize not only for performance (accuracy), but also for implementation complexity, becomes paramount. In this work, we present a multi-objective design space exploration method that reduces the number of solution networks trained and evaluated through response surface modelling. Given spaces which can easily exceed 1020 solutions, manually designing a near-optimal architecture is unlikely as opportunities to reduce network complexity, while maintaining performance, may be overlooked. This problem is exacerbated by the fact that hyper-parameters which perform well on specific datasets may yield sub-par results on others, and must therefore be designed on a per-application basis. In our work, machine learning is leveraged by training an artificial neural network to predict the performance of future candidate networks. The method is evaluated on the MNIST and CIFAR-10 image datasets, optimizing for both recognition accuracy and computational complexity. Experimental results demonstrate that the proposed method can closely approximate the Pareto-optimal front, while only exploring a small fraction of the design space.

Polar codes are an exciting new class of error correcting codes that achieve the symmetric capacity of memoryless channels. Many decoding algorithms were developed and implemented, addressing various application requirements: from error-correction performance rivaling that of LDPC codes to very high throughput or low-complexity decoders. In this work, we review the state of the art in polar decoders implementing the successive-cancellation, belief propagation, and list decoding algorithms, illustrating their advantages.

The Successive-Cancellation List (SCL) algorithm is one of the best polar code decoding algorithms in terms of trade-offs between complexity and error correction performance. The List-Sphere Decoding (List-SD) algorithm has been recently proposed: it yields a better complexity/performance trade-off than SCL in the decoding of short polar codes, that can be used as component codes for larger polar codes. We exploit the structure of the generator matrix of polar codes to propose a matrix reordering technique which allows to significantly reduce the List-SD complexity without degrading its error correction performance, further improving the aforementioned trade-off. The proposed technique is implemented on hardware and it is shown that at the same Frame Error Rate (FER) and Bit Error Rate (BER), the matrix reordering can reduce the resource requirements of List-SD of up to 73%. Furthermore, FER and BER curves are plotted for case studies, showing that at the same complexity cost, matrix reordering improves the performance of List-SD of up to 0.75 dB at FER=10-2.

The Successive-Cancellation List (SCL) decoding algorithm is one of the most promising approaches towards practical polar code decoding. It is able to provide a good trade-off between error-correction performance and complexity, tunable through the size of the list. In this paper, we show that in the conventional formulation of SCL, there are redundant calculations which do not need to be performed in the course of the algorithm. We simplify SCL by removing these redundant calculations and prove that the proposed simplified SCL and the conventional SCL algorithms are equivalent. The simplified SCL algorithm is valid for any code and can reduce the time-complexity of SCL without affecting the space complexity.

Polar codes asymptotically achieve the symmetric capacity of memoryless channels, yet their error-correcting performance under successive-cancellation (SC) decoding for short and moderate length codes is worse than that of other modern codes such as low-density parity-check (LDPC) codes. Of the many methods to improve the error-correction performance of polar codes, list decoding yields the best results, especially when the polar code is concatenated with a cyclic redundancy check (CRC). List decoding involves exploring several decoding paths with SC decoding, and therefore tends to be slower than SC decoding itself, by an order of magnitude in practical implementations. In this paper, we present a new algorithm based on unrolling the decoding tree of the code that improves the speed of list decoding by an order of magnitude when implemented in software. Furthermore, we show that for software-defined radio applications, our proposed algorithm is faster than the fastest software implementations of LDPC decoders in the literature while offering comparable error-correction performance at similar or shorter code lengths.

In this paper, we present hardware and software implementations of flexible polar systematic encoders and decoders. The proposed implementations operate on polar codes of any length less than a maximum and of any rate. We describe the low-complexity, highly parallel, and flexible systematic-encoding algorithm that we use and prove its correctness. Our hardware implementation results show that the overhead of adding code rate and length flexibility is little, and the impact on operation latency minor compared with code-specific versions. Finally, the flexible software encoder and decoder implementations are also shown to be able to maintain high throughput and low latency.

This paper presents the mixed-signal circuit implementation of reduced complexity algorithms for decoding low-density parity check (LDPC) codes. Based on modified differential decoding using binary message passing (MDD-BMP), binary addition using discrete-time digital circuits is replaced by continuous-time analog-current summation. Potential degradation due to the mismatch between current sources, P/N strength mismatch and inverter-threshold mismatch is considered in behavioural simulation and shown to be tolerable. Area estimates suggest a reduction from 0.27 mm2to 0.11 mm2for the FG(273, 191) code. Finally, transistor level simulation of the FG(273, 191) code using TSMC 65 nm technology shows an efficiency of 0.56 pJ/bit.

High-speed and low-area decoders for low-density parity-check (LDPC) codes with very long block lengths are challenging to implement due to the large amount of nodes and edges required. In this paper we implement a decoder for a (32643, 30592) LDPC code that has variable nodes of degree 7, check nodes degrees of 111 and 112, and 228501 edges, making fully-parallel hardware implementation unfeasible. We analyze the structure of this code and describe a method of replacing the complex interconnect with a local, area-efficient version. We develop an modular architecture resulting in a low-complexity partially-parallel decoder architecture based on the offset min-sum algorithm. The proposed decoder is shown to achieve a minimum gain of 92% in area utilization, compared to an extremely optimistic area estimation of the fully-parallel decoder that neglects the interconnection overhead. Synthesis in 65 nm CMOS is performed resulting in a clock frequency of 370 MHz and a throughput of 24 Gbps with an area of 7.99 mm2.

Associative memories are an alternative to classical indexed memories that are capable of retrieving a message previously stored when an incomplete version of this message is presented. Recently a new model of associative memory based on binary neurons and binary links has been proposed. This model named Clustered Neural Network (CNN) offers large storage diversity (number of messages stored) and fast message retrieval when implemented in hardware. The performance of this model drops when the stored message distribution is non-uniform. In this paper, we enhance the CNN model to support non-uniform message distribution by adding features of Restricted Boltzmann Machines. In addition, we present a fully parallel hardware design of the model. The proposed implementation multiplies the performance (diversity) of Clustered Neural Networks by a factor of 3 with an increase of complexity of 40%.

This paper presents a quasi-synchronous design approach for signal processing circuits, in which timing violations are permitted, but without the need for a hardware compensation mechanism. A quasi-synchronous low-density parity-check decoder processing circuit based on the offset min-sum algorithm is designed, achieving the same performance and occupying the same area as a conventional synchronous circuit, but using up to 28% less energy.

Associative memories are capable of retrieving previously stored patterns given parts of them. This feature makes them good candidates for pattern detection in images. Clustered Neural Networks is a recently-introduced family of associative memories that allows a fast pattern retrieval when implemented in hardware. In this paper, we propose a new pattern retrieval algorithm that results in a dramatically lower error rate compared to that of the conventional approach when used in oriented edge detection process. This function plays an important role in image processing. Furthermore, we present the corresponding hardware architecture and implementation of the new approach in comparison with a conventional architecture in literature, and show that the proposed architecture does not significantly affect hardware complexity.

This letter introduces a design and proof-of-concept implementation of Gabor filters based on stochastic computation for area-efficient hardware. The Gabor filter exhibits a powerful image feature extraction capability, but it requires significant computational power. Using stochastic computation, a sine function used in the Gabor filter is approximated by exploiting several stochastic tanh functions designed based on a state machine. A stochastic Gabor filter realized using the stochastic sine shaper and a stochastic exponential function is simulated and compared with the original Gabor filter that shows almost equivalent behaviour at various frequencies and variance. A root-mean-square error of 0.043 at most is observed. In order to reduce long latency due to stochastic computation, 68 parallel stochastic Gabor filters are implemented in Silterra 0.13 μm CMOS technology. As a result, the proposed Gabor filters achieve a 78% area reduction compared with a conventional Gabor filter while maintaining the comparable speed.

In recent years, on-chip trace generation has been recognized as a solution to the debugging of increasingly complex software. An execution trace can be seen as the most fundamentally useful type of trace, allowing the execution path of software to be determined post hoc. However, the bandwidth required to output such a trace can be excessive. Our architecture-aware trace compression (AATC) scheme adds an on-chip branch predictor and branch target buffer to reduce the volume of execution trace data in real time through on-chip compression. Novel redundancy reduction strategies are employed, most notably in exploiting the widespread use of linked branches and the compiler-driven movement of return addresses between link register, stack, and program counter. In doing so, the volume of branch target addresses is reduced by 52%, whereas other algorithmic improvements further decrease trace volume. An analysis of spatial and temporal redundancy in the trace stream allows a comparison of encoding strategies to be made for systematically increasing compression performance. A combination of differential, Fibonacci, VarLen, and Move-to-Front encodings are chosen to produce two compressor variants: a performance-focused xAATC that encodes 56.5 instructions/bit using 24,133 gates and an area-efficient fAATC that encodes 48.1 instructions/bit using only 9,854 gates.

We propose a low-power content-addressable memory (CAM) employing a new algorithm for associativity between the input tag and the corresponding address of the output data. The proposed architecture is based on a recently developed sparse clustered network using binary connections that on-average eliminates most of the parallel comparisons performed during a search. Therefore, the dynamic energy consumption of the proposed design is significantly lower compared with that of a conventional low-power CAM design. Given an input tag, the proposed architecture computes a few possibilities for the location of the matched tag and performs the comparisons on them to locate a single valid match. TSMC 65-nm CMOS technology was used for simulation purposes. Following a selection of design parameters, such as the number of CAM entries, the energy consumption and the search delay of the proposed design are 8%, and 26% of that of the conventional NAND architecture, respectively, with a 10% area overhead. A design methodology based on the silicon area and power budgets, and performance requirements is discussed.

In this paper, we present LDPC decoder designs based on gear-shift algorithms, which can use multiple decoding algorithms or update rules over the course of decoding a single frame. By first attempting to decode using low-complexity algorithms, followed by high-complexity algorithms, we increase energy efficiency without sacrificing error correction performance. We present the GSP and IGSP algorithms, and ASIC designs of these algorithms for the 10 Gbps Ethernet (2048,1723) LDPC code. In 65nm CMOS, our pipelined GSP decoder achieves a core area of 5.29mm2, throughput of 88.1 Gbps, and energy efficiency of 39.3 pJ/bit, while our IGSP decoder achieves a core area of 6.00mm2, throughput of 100.3 Gbps, and energy efficiency of 14.6 pJ/bit. Both algorithms achieve error correction performance equivalent to the offset min-sum algorithm. The throughput per unit area and energy efficiency of these decoders improve upon state-of-the-art decoders with comparable error correction performance.

Among error-correcting codes, polar codes are the first to provably achieve channel capacity with an explicit construction. In this work, we present software implementations of a polar decoder that leverage the capabilities of modern general-purpose processors to achieve an information throughput in excess of 200 Mbps, a throughput well suited for software-defined-radio applications. We also show that, for a similar error-correction performance, the throughput of polar decoders both surpasses that of LDPC decoders targeting general-purpose processors and is competitive with that of state-of-the-art software LDPC decoders running on graphic processing units.

We consider associative memories based on clustered graphs that were recently introduced. These memories are almost optimal in terms of the amount of storage they require (efficiency), and allow retrieving messages with low complexity. We study an unreliable implementation of the memory and compare its error rate and storage efficiency with that of a reliable implementation. We present analytical and simulation results that indicate that the proposed memory structure can tolerate a large number of faults at a reasonable cost, thereby making it a good candidate for achieving highly efficient circuit implementations of associative memories.

Polar codes provably achieve the symmetric capacity of a memoryless channel while having an explicit construction. The adoption of polar codes however, has been hampered by the low throughput of their decoding algorithm. This work aims to increase the throughput of polar decoding hardware by an order of magnitude relative to successive-cancellation decoders and is more than 8 times faster than the current fastest polar decoder. We present an algorithm, architecture, and FPGA implementation of a flexible, gigabit-per-second polar decoder.

In software debugging, trace generation techniques are used to resolve highly complex bugs. However, the emulators increasingly used for embedded software development do not yet offer the types of trace generation infrastructure available in hardware. In this article, we make changes to the ARM ISA emulation of the QEMU emulator to allow for continuous instruction-level trace generation. Using a standard GDB client, tracepoints can be inserted to dynamically log registers and memory addresses without altering executing code. The ability to run trace experiments in five different modes allows the scope of trace generation to be narrowed as needed, down to the level of a single Linux process. Our scheme collects the execution traces of a Linux process on average between 9.6x--0.7x the speed of existing QEMU trace capabilities, with 96.7% less trace data volume. Compared to a software-instrumented tracing scheme, our method is both unobtrusive and performs on average between 3--4 orders of magnitude faster.

A low-power Content-Addressable Memory (CAM) is introduced employing a new mechanism for associativity between the input tags and the corresponding address of the output data. The proposed architecture is based on a recently developed clustered-sparse network using binary-weighted connections that on-average will eliminate most of the parallel comparisons performed during a search. Therefore, the dynamic energy consumption of the proposed design is significantly lower compared to that of a conventional low-power CAM design. Given an input tag, the proposed architecture computes a few possibilities for the location of the matched tag and performs the comparisons on them to locate a single valid match. A 0.13μm CMOS technology was used for simulation purposes. The energy consumption and the search delay of the proposed design are 9.5%, and 30.4% of that of the conventional NAND architecture respectively with a 3.4% higher number of transistors.

We propose a novel architecture for low-power area-efficient large-scale IP lookup engines. The proposed architecture greatly increases memory efficiency by storing associations between IP addresses and their output rules instead of storing these data themselves. The rules can be determined by simple hardware using a few associations read from SRAMs, eliminating a power-hungry search of input addresses in TCAMs. The proposed hardware that stores 100,000 144-bit entries is evaluated under TSMC 65nm CMOS technology. The dynamic power dissipation and the area of the proposed hardware are 4.6% and 30.6% of a traditional TCAM, respectively while maintaining comparable throughput.

Associative memories retrieve stored information given partial or erroneous input patterns. Recently, a new family of associative memories based on Clustered-Neural-Networks (CNNs) was introduced that can store many more messages than classical Hopfield-Neural Networks (HNNs). In this paper, we propose hardware architectures of such memories for partial or erroneous inputs. The proposed architectures eliminate winner-take-all modules and thus reduce the hardware complexity by consuming 65% fewer FPGA lookup tables and increase the operating frequency by approximately 1.9 times compared to that of previous work.

Low-density parity-check codes are attractive for high throughput applications because of their low decoding complexity per bit, but also because all the codeword bits can be decoded in parallel. However, achieving this in a circuit implementation is complicated by the number of wires required to exchange messages between processing nodes. Decoding algorithms that exchange binary messages are interesting for fully-parallel implementations because they can reduce the number and the length of the wires, and increase logic density. This paper introduces the Relaxed Half-Stochastic (RHS) decoding algorithm, a binary message belief propagation (BP) algorithm that achieves a coding gain comparable to the best known BP algorithms that use real-valued messages. We derive the RHS algorithm by starting from the well-known Sum-Product algorithm, and then derive a low-complexity version suitable for circuit implementation. We present extensive simulation results on two standardized codes having different rates and constructions, including low bit error rate results. These simulations show that RHS can converge faster on average than existing state-of-the-art decoding algorithms, leading to improvements in throughput and energy efficiency.

Despite the outstanding performance of non-binary low-density parity-check (LDPC) codes over many communication channels, they are not in widespread use yet. This is due to the high implementation complexity of their decoding algorithms, even those that compromise performance for the sake of simplicity. In this paper, we present three algorithms based on stochastic computation to reduce the decoding complexity. The first is a purely stochastic algorithm with error-correcting performance matching that of the sum-product algorithm (SPA) for LDPC codes over Galois fields with low order and a small variable node degree. We also present a modified version which reduces the number of decoding iterations required while remaining purely stochastic and having a low per-iteration complexity. The second algorithm, relaxed half-stochastic (RHS) decoding, combines elements of the SPA and the stochastic decoder and uses successive relaxation to match the error-correcting performance of the SPA. Furthermore, it uses fewer iterations than the purely stochastic algorithm and does not have limitations on the field order and variable node degree of the codes it can decode. The third algorithm, NoX, is a fully stochastic specialization of RHS for codes with a variable node degree 2 that offers similar performance, but at a significantly lower computational complexity. We study the performance and complexity of the algorithms; noting that all have lower per-iteration complexity than SPA and that RHS can have comparable average per-codeword computational complexity, and NoX a lower one.

Associative memories are alternatives to indexed memories that when implemented in hardware can benefit many applications such as data mining. The classical neural network based methodology is impractical to implement since in order to increase the size of the memory, the number of information bits stored per memory bit (efficiency) approaches zero. In addition, the length of a message to be stored and retrieved needs to be the same size as the number of nodes in the network causing the total number of messages the network is capable of storing (diversity) to be limited. Recently, a novel algorithm based on sparse clustered neural networks has been proposed that achieves nearly optimal efficiency and large diversity. In this paper, a proof-of-concept hardware implementation of these networks is presented. The limitations and possible future research areas are discussed.

The Gaussian Belief Propagation (GaBP) algorithm executed on Gaussian Markov Random Fields can take a large number of iterations to converge if the inverse covariance matrix of the underlying Gaussian distribution is ill-conditioned and weakly diagonally dominant. Such matrices can arise from many practical problem domains. In this study, we propose a relaxed GaBP algorithm that results in a significant reduction in the number of GaBP iterations (of up to 12.7 times). We also propose a second relaxed GaBP algorithm that avoids the need of determining the relaxation factor a priori which can also achieve comparable reductions in iterations by only setting two basic heuristic measures. We show that the new algorithms can be implemented without any significant increase, over the original GaBP, in both the computational complexity and the memory requirements. We also present detailed experimental results of the new algorithms and demonstrate their effectiveness in achieving significant reductions in the iteration count.

We consider the problem of efficient and lossless representation of a multiset of m words drawn with repetition from a set of size 2n. One expects that encoding the (unordered) multiset should lead to significant savings in rate as compared to encoding an (ordered) sequence with the same words, since information about the order of words in the sequence corresponds to a permutation. We propose and analyze a practical multiset encoder/decoder based on the trie data structure. The act of encoding requires O(m(n + log m)) operations, and decoding requires O(mn) operations. Of particular interest is the case where cardinality of the multiset scales as m = 1/c2nfor some c >; 1, as n → ∞. Under this scaling, and when the words in the multiset are drawn independently and uniformly, we show that the proposed encoding leads to an arbitrary improvement in rate over encoding an ordered sequence with the same words. Moreover, the expected length of the proposed codes in this setting is asymptotically within a constant factor of 5/3 of the lower bound.

We introduce two dithered belief propagation decoding algorithms to lower the error floor with a minimal hardware overhead. One of the algorithms can additionally improve the decoding performance in the waterfall region using a large iteration limit but with a negligible increase in the average time complexity.

The recently-discovered polar codes are widely seen as a major breakthrough in coding theory. These codes achieve the capacity of many important channels under successive cancellation decoding. Motivated by the rapid progress in the theory of polar codes, we pro pose a family of architectures for efficient hardware implementation of successive cancellation decoders. We show that such decoders can be implemented with O(n) processing elements and O(n) memory elements, while providing constant throughput. We also pro pose a technique for overlapping the decoding of several consecutive codewords, thereby achieving a significant speed-up factor. We furthermore show that successive cancellation decoding can be implemented in the logarithmic domain, thereby eliminating the multiplication and division operations and greatly reducing the complexity of each processing element.

We propose dithered belief propagation decoding algorithms to reduce the number of decoding failures of a belief propagation decoder and lower the error floor. The random nature of the algorithms enables a low hardware complexity compared to previously reported techniques. We introduce two dithering methods that target check node operations and channel input values, respectively. We present simulation results that confirm the error rate gains in the floor region, and that relate those gains with the maximum number of decoding iterations. The results show that the first algorithm can achieve good error rate gains with a low iteration limit. For the second algorithm, results show that with a large iteration limit, high FER gains are possible. Furthermore the average time complexity remains the same as that of a standard belief propagation algorithm.

This paper presents a Relaxed Half-Stochastic (RHS) low-density parity-check (LDPC) decoding algorithm that uses some elements of the sum-product algorithm (SPA) in its variable nodes, but maintains the low-complexity interleaver and check node structures characteristic of stochastic decoders. The algorithm relies on the principle of successive relaxation to convert binary stochastic streams to a log-likelihood ratio (LLR) representation. Simulations of a (2048, 1723) RS-LDPC code show that the RHS algorithm can outperform 100-iterations floating-point SPA decoding. We describe approaches for low-complexity implementation of the RHS algorithm. Furthermore, we show how the stochastic nature of the belief representation can be exploited to lower the error floor.

This paper proposes tracking forecast memories (TFMs) as a novel method for implementing re-randomization and decorrelation of stochastic bit streams in stochastic channel decoders. We show that TFMs are able to achieve decoding performance similar to that of the previous methods in the literature (i.e., edge memories or EMs), but they exhibit much lower hardware complexity. TFMs significantly reduce the area requirements of ASIC implementations of stochastic decoders.

Non-binary LDPC codes have been shown to outperform currently used codes for magnetic recording and several other channels. Currently proposed nonbinary decoder architectures have very high complexity for high-throughput implementations and sacrifice error-correction performance to maintain realizable complexity. In this paper, we present an alternative decoding algorithm based on stochastic computation that has a very simple implementation and minimal performance loss when compared to the sum-product algorithm. We demonstrate the performance of the algorithm when applied to a GF(16) code and provide details of the hardware resources required for an implementation.

The adaptive belief propagation (ABP) algorithm was recently proposed by Jiang and Narayanan for the soft decoding of Reed-Solomon (RS) codes. In this paper, simplified versions of this algorithm are investigated for the turbo decoding of product codes. The complexity of the turbo-oriented adaptive belief propagation (TAB) algorithm is significantly reduced by moving the matrix adaptation step outside of the belief propagation iteration loop. A reduced-complexity version of the TAB algorithm that offers a trade-off between performance and complexity is also proposed. Simulation results for the turbo decoding of product codes show that belief propagation based on adaptive parity check matrices is a practical alternative to the currently very popular Chase-Pyndiah algorithm.

Many automatic algorithms have been proposed for analyzing magnetic resonance imaging (MRI) data sets. With the increasingly large data sets being used in brain mapping, there has been a significant rise in the need for accelerating these algorithms. Partial volume estimation (PVE), a brain tissue classification algorithm for MRI, was implemented on a field-programmable gate array (FPGA)-based high performance reconfigurable computer using the Mitrion-C high-level language (HLL). This work develops on prior work in which we conducted initial studies on accelerating the prior information estimation algorithm. In this paper, we extend the work to include probability density estimation and present new results and additional analysis. We used several simulated and real human brain MR images to evaluate the accuracy and performance improvement of the proposed algorithm. The FPGA-based probability density estimation and prior information estimation implementation achieved an average speedup over an Itanium 2 CPU of 2.5 x and 9.4 x , respectively. The overall performance improvement of the FPGA-based PVE algorithm was 5.1 x with four FPGAs.

We describe the implementation of a hardware-accelerated particle graphics engine on a reconfigurable computer. The engine incorporates a configurable flow model that enables the simulation of complex spatially-dependent particle graphics effects. The FPGA particle engine was designed using the Mitrion-C high-level language, and did not require detailed hardware design. The engine was implemented on a SGI Altix 350 with four Xilinx Virtex-4 LX200 FPGAs. The engine achieves speedups of 35 to 58 times over a 1.5 GHz Itanium 2 CPU when using one and four FPGAs respectively.

The Chinese remainder theorem (CRT) and mixed-radix conversion (MRC) are two classic theorems used to convert a residue number to its binary correspondence for a given moduli set {P_n, · · · , P_2, P_1}. The MRC is a weighted number system and it requires operations modulo P_i only and hence magnitude comparison is easily performed. However, the calculation of the mixed-radix coefficients in the MRC is a strictly sequential process and involves complex divisions. Thus the residue-to-binary (R/B) conversions and residue comparisons based on the MRC require large delay. In contrast, the R/B conversion and residue comparison based on the CRT are fully parallel processes. However, the CRT requires large operations modulo M = P_n · · · P_2P_1. In this paper, a new mixed-radix CRT is proposed which possesses both the advantages of the CRT and the MRC, which are parallel processing, small operations modulo P_i only, and the efficiency of making modulo comparison. Based on the proposed CRT, new residue comparators are developed for the three-moduli set {2^n − 1, 2^n, 2^n + 1}. The FPGA implementation results show that the proposed modulo comparators are about 20% faster and smaller than one of the previous best designs.

Particle graphics simulations are well suited for modeling complex phenomena such as water, cloth, explosions, fire, smoke, and clouds. They are normally realized in software as part of an interactive graphics application. The computational complexity of particle graphics simulations restricts the number of particles that can be updated in software at interactive frame rates. This article presents the design and implementation of a hardware particle graphics engine for accelerating real-time particle graphics simulations. We explore the design process, implementation issues, and limitations of using field-programmable gate arrays (FPGAs) for the acceleration of particle graphics. The FPGA particle engine processes million-particle systems at a rate from 47 to 112 million particles per second, which represents one to two orders of magnitude speedup over a 2.8 GHz CPU. Using three FPGAs, a maximum sustained performance of 112 million particles per second was achieved.

High-performance reconfigurable computers (HPRCs) consisting of CPUs with application-specific FPGA accelerators traditionally use a low-level hardware-description language such as VHDL or Verilog to program the FP-GAs. The complexity of hardware design methodologies for FPGAs requires specialist engineering knowledge and presents a significant barrier to entry for scientific users with only a software background. Recently, a number of High-Level Languages (HLLs) for programming FPGAs have emerged that aim to lower this barrier and abstract away hardware-dependent details. This paper presents the results of a study on implementing hardware accelerators using the Mitrion-C HLL. The implementation of two floating-point scientific kernels: dense matrix-vector multiplication (DMVM) and the computation of spherical boundary conditions in molecular dynamics (SB) are described. We describe optimizations that are essential for taking advantage of both the features of the HLL and the underlying HPRC hardware and libraries. Scaling of the algorithms to multiple FPGAs is also investigated. With four FPGAs, 80 times speedup over an Itanium 2 CPU was achieved for the DMVM, while a 26 times speedup was achieved for SB.

Many automatic algorithms have been proposed for analyzing magnetic resonance imaging (MRI) data sets. These algorithms allow clinical researchers to generate quantitative data analyses with consistently accurate results. With the increasingly large data sets being used in brain mapping, there has been a significant rise in the need for methods to accelerate these algorithms, as their computation time can consume many hours. This paper presents the results from a recent study on implementing such quantitative analysis algorithms on High-Performance Reconfigurable Computers (HPRCs). A brain tissue classification algorithm for MRI, the Partial Volume Estimation (PVE), is implemented on an SGI RASC RC100 system using the Mitrion-C High-Level Language (HLL). The CPU-based PVE algorithm is profiled and computationally intensive floating-point functions are implemented on FPGA-accelerators. The images resulting from the FPGA-based algorithm are compared to those generated by the CPU-based algorithm for verification. The Similarity Indexes (SI) for pure tissues are calculated to measure the accuracy of the images resulting from the FPGA-based implementation. The portion of the PVE algorithm thatwas implemented on hardware achieved a 11× performance improvement over the CPU-based implementation. The overall performance improvement of the FPGA-accelerated PVE algorithm was 3.5× with four FPGAs.

This paper introduces the Modified Adaptive Belief Propagation (m-ABP) algorithm, an innovative method for the turbo decoding of product codes based on BCH component codes. The Adaptive Belief Propagation algorithm of Jiang and Narayanan is simplified by moving the matrix adaptation step outside of the iteration loop, significantly reducing the complexity. Performance in terms of the bit- error-rate (BER) of the novel turbo decoding algorithm is given. Simulation results for the turbo decoding of product codes show that compared to the Chase-Pyndiah algorithm no significant BER deviation is observed while the highly- parallelizable graph-based structure of the algorithm enables high-throughput decoding.

Reed-Solomon codes are powerful error-correcting codes that can be found in many digital communications standards. Recently, there has been an interest in soft-decision decoding of Reed-Solomon codes, incorporating reliability information from the channel into the decoding process. The Koetter-Vardy algorithm is a soft-decision decoding algorithm for Reed-Solomon codes which can provide several dB of gain over traditional hard-decision decoders. The algorithm consists of a soft-decision front end to the interpolation-based Guruswami-Sudan list decoder. The main computational task in the algorithm is a weighted interpolation of a bivariate polynomial. We propose a parallel architecture for the hardware implementation of bivariate interpolation for soft-decision decoding. The key feature is the embedding of both a binary tree and a linear array into a 2-D array processor, enabling fast polynomial evaluation operations. An field-programmable gate array interpolation processor was implemented and demonstrated at a clock frequency of 23 MHz, corresponding to decoding rates of 10-15 Mb/s

The paper presents an architecture and an implementation of an FPGA-based sparse matrix-vector multiplier (SMVM) for use in the iterative solution of large, sparse systems of equations arising from finite element method (FEM) applications. The architecture is based on a pipelined linear array of processing elements (PEs). A hardware-oriented matrix "striping" scheme is developed which reduces the number of required processing elements. The current 8 PE prototype achieves a peak performance of 1.76 GFLOPS and a sustained performance of 1.5 GFLOPS with 8 GB/s of memory bandwidth. The SMVM-pipeline uses 30% of the logic resources and 40% of the memory resources of a Stratix S80 FPGA. By virtue of the local interconnect between the PEs, the SMVM-pipeline obtain scalability features that is only limited by FPGA resources instead of the communication overhead

Efficient soft-decision decoding of Reed–Solomon codes is made possible by the Koetter–Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami–Sudan list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate (RS 9225,239) Reed–Solomon code, 2–3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queuing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required.

Efficient soft-decision decoding of Reed-Solomon (RS) codes is made possible by the Koetter-Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami-Sudan (GS) list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate RS(255,239) code, 2-3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored, which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queueing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required

Particle graphics simulations are well suited for modeling phenomena such as water, cloth, explosions, fire, smoke, and clouds. They are normal realized in software, as pan of an interactive graphics application, such as a video game. Their use in such applications is limited by the computational burden and resource competition they create for a host application. We present the design of a hardware particle machine, for implementation in an FPGA, intended for accelerating real-time panicle graphics in applications such as video games. The particle machine is a system that completely contains, manages, and executes particle graphics simulations and rendering. The particle machine is a system comprised of particle memory, a controller, and the panicle pipe, a pipelined particle update processor. The panicle pipe has been synthesized to 130 MHz, on an Altera Stratix FPGA, resulting in a potential throughput of 2.1 million PPF (panicles per frame). This throughput is achieved with minimal load on application and main system performance.

We propose a parallel architecture for implementing the interpolation step in the Koetter-Vardy soft-decision Reed-Solomon decoding algorithm. The key feature is the embedding of both a binary tree and a linear array into a two-dimensional array processor, enabling fast polynomial evaluation operations. An FPGA interpolation processor was implemented and demonstrated at a clock frequency of 23 MHz, corresponding to decoding rates of 10-15 Mbps.

This paper presents several techniques for the very large-scale integration (VLSI) implementation of the maximum a posteriori (MAP) algorithm. In general, knowledge about the implementation of the Viterbi (1967) algorithm can be applied to the MAP algorithm. Bounds are derived for the dynamic range of the state metrics which enable the designer to optimize the word length. The computational kernel of the algorithm is the add-MAX* operation, which is the add-compare-select operation of the Viterbi algorithm with an added offset. We show that the critical path of the algorithm can be reduced if the add-MAX* operation is reordered into an offset-add-compare-select operation by adjusting the location of registers. A general scheduling for the MAP algorithm is presented which gives the tradeoffs between computational complexity, latency, and memory size. Some of these architectures eliminate the need for RAM blocks with unusual form factors or can replace the RAM with registers. These architectures are suited to VLSI implementation of turbo decoders.