This paper investigates CKKS-encrypted Support Vector Machine (SVM) inference utilizing Radial Basis Function (RBF) kernels. Unlike prior research focusing on encrypted queries, we address the challenge of model-side encryption, where the classifier remains confidential while processing user data. Encrypted inference with nonlinear models typically requires replacing them with polynomial approximations. We investigate the effect of these approximations for CKKS-based RBF SVM inference, where kernel evaluation depends on exp (x). Using OpenFHE, we evaluate degree-1 through degree-8 Taylor and Chebyshev approximations of exp (x), with Chebyshev polynomials constructed on a preselected interval. We use the binary Iris task and the Wisconsin Diagnostic Breast Cancer (WBC) dataset in our experiments. Models are trained in the clear, and during inference, model-side quantities are encrypted while test vectors remain in plaintext. Accuracy is measured together with root-mean-square percent error in the decision value relative to plaintext RBF inference. The optimal approximation depends on both the polynomial degree and the input distribution. On Iris, Chebyshev uniformly achieves 100% accuracy, whereas on WDBC, Taylor is superior at low degrees, though both reach plaintext accuracy by degree 4. These findings demonstrate that approximation selection must be guided by empirical data distributions, achieving model-side encryption parity with query-side baselines without accuracy degradation.

This paper revisits the design and optimization of parallel fast finite impulse response (FIR) filters using polyphase decomposition and iterated fast FIR algorithms (FFAs). Parallel FIR filtering enhances computational efficiency and throughput in digital signal processing (DSP) applications by enabling the simultaneous processing of multiple input samples. We revisit a prior approach to design of fast parallel filter architectures by using the iterated FFA approach where the same primitive filter, such as 2-parallel, is iterated to design the fast parallel filter. In this paper, we present yet another novel iterated fast parallel FIR filter, referred to as the fast hybrid filter. The hybrid filter iterates a transposed 2-parallel fast FIR filter in all the inner layers and a direct-form 2-parallel fast FIR filter in the outermost layer, resulting in reduced hardware complexity. Such an iterated hybrid approach has not been presented before. We show that the hybrid fast parallel filters require less number of additions compared to prior approaches.

This paper presents a novel accelerator architecture for real-time image filtering applications that require high throughput and low latency. The proposed architecture consists of two systolic arrays: a Row Convolution (RConv) Array and a Column Convolution (CConv) Array. The RConv Array processes one row of the input image and computes one row of an intermediate image per clock cycle which is then input to CConv Array. The CConv Array computes one row of the output image per clock cycle. A novel aspect of the architecture is that the line delays within the convolution architecture are used efficiently due to the parallelism. This leads to a significant reduction in the memory requirement and latency of the architecture. While the row convolution in the RConv Array is implemented using a direct-form FIR filter, the column convolution in the CConv Array is implemented using the transpose-form FIR filter. Thus, the processing elements in the CConv array are implicitly pipelined and do not require additional pipelining delays. The parallelized row-by-row processing significantly reduces the memory overhead per output pixel. The proposed architecture is then generalized where multiple rows of the image can be processed in a clock cycle, leading to further proportional reduction in latency and memory requirements. The proposed architecture is fully feed-forward and can be pipelined further as needed. We show that using a Xilinx Virtex-7 2000T FPGA clocked at 100 MHz, the architecture achieves$16.0\times$,$86.3\times$, and$943\times$improvements in the LUT-time$^2$, FF-time$^2$, and DSP-time$^2$products over a baseline serial architecture for the non-separable case with Image size$128\times 128$and filter size$11\times 11$. The proposed architecture can operate at a throughput of 12.8 Gpixels/s whereas the baseline can only operate at 100 Mpixels/s.

Cognitive control dysregulation is nearly universal across disorders, including major depressive disorder (MDD). Achieving comparable response rates to medication, the transcranial magnetic stimulation (TMS) mechanism and its effect on cognitive control have not been well understood yet. This paper investigates the predictive capability of the clinical response to TMS treatment using 34 cognitive variables measured from TMS treatment of 22 MDD subjects over an eight-week period. We employ a novel brain-inspired computing paradigm, hyperdimensional computing (HDC), to classify the effectiveness of TMS using leave-one-subject-out cross-validation (LOSOCV). Four performance metrics-accuracy, sensitivity, specificity and AUC-are used, with AUC being the primary metric. Experimental results reveal that: i). Although SVM outperforms HDC in terms of accuracy, HDC achieves an AUC of 0.82, surpassing SVM by 0.07. ii). The optimal performance for both classifiers is obtained with feature selection using SelectKBest. iii) Among the top features selected by SelectKBest for the two classifiers, ws_MedRT (median rate for the Websurf task) shows a more distinguishable distribution between clinical responses ("1") and no clinical responses ("0"). In conclusion, these results highlight the potential of HDC for predicting clinical responses to TMS and underscore the importance of feature selection in improving classification performance.

Quantum computers pose a significant threat to modern cryptographic systems by efficiently solving problems such as integer factorization through Shor’s algorithm. Homomorphic encryption (HE) schemes based on ring learning with errors (Ring-LWE) offer a quantum-resistant framework for secure computations on encrypted data. Many of these schemes rely on polynomial multiplication, which can be efficiently accelerated using the number theoretic transform (NTT) in leveled HE, ensuring practical performance for privacy-preserving applications. This article presents a novel NTT-based serial pipelined multiplier that achieves full-hardware utilization through interleaved folding, and overcomes the 50% under-utilization limitation of the conventional serial R2MDC architecture. In addition, it explores tradeoffs in pipelined parallel designs, including serial, 2-parallel, and 4-parallel architectures. Our designs leverage increased parallelism, efficient folding techniques, and optimizations for a selected constant modulus to achieve superior throughput (TP) compared with state-of-the-art implementations. While the serial fold design minimizes area consumption, the 4-parallel design maximizes TP. Experimental results on the Virtex-7 platform demonstrate that our architectures achieve at least 2.22 times higher TP/area for a polynomial length of 1024 and 1.84 times for a polynomial length of 4096 in the serial fold design, while the 4-parallel design achieves at least 2.78 times and 2.79 times, respectively. The efficiency gain is even more pronounced in TP squared over area, where the serial fold and 4-parallel designs outperform prior works by at least 4.98 times and 26.43 times for a polynomial length of 1024 and 6.7 times and 43.77 times for a polynomial length of 4096, respectively. These results highlight the effectiveness of our architectures in balancing performance, area efficiency, and flexibility, making them well-suited for high-speed cryptographic applications.

This paper addresses the design of a partly-parallel cascaded FFT-IFFT architecture that does not require any intermediate buffer. Folding can be used to design partly-parallel architectures for FFT and IFFT. While many cascaded FFT-IFFT architectures can be designed using various folding sets for the FFT and the IFFT, for a specified folded FFT architecture, there exists a unique folding set to design the IFFT architecture that does not require an intermediate buffer. Such a folding set is designed by processing the output of the FFT as soon as possible (ASAP) in the folded IFFT. Elimination of the intermediate buffer reduces latency and saves area. The proposed approach is also extended to interleaved processing of multi-channel time-series. The proposed FFT-IFFT cascade architecture saves about N/2 memory elements and N/4 clock cycles of latency compared to a design with identical folding sets. For the 2-interleaved FFT-IFFT cascade, the memory and latency savings are, respectively, N/2 units and N/2 clock cycles, compared to a design with identical folding sets.

Homomorphic encryption enables computations on the ciphertext to preserve data privacy. However, its practical deployment has been hindered by the significant computational overhead compared to the plaintext computations. In response to this challenge, we present HERMES, a novel hardware acceleration system designed to explore the computation flow of the CKKS homomorphic encryption bootstrapping process. Among the major contributions of our proposed architecture, we first analyze the properties of the CKKS computation data flow and propose a new scheduling strategy by partitioning the computation modules into general-purpose and special-purpose modular computation modules to allow smaller resource consumption and flexible scheduling. The computation modules are also reconfigurable to reduce the memory access overhead during the intermediate computation. We also optimize the CKKS computation dataflow to improve the regularity with reduced control overhead.

The ML-KEM post-quantum cryptography (PQC) scheme requires matrix-vector polynomial multiplication and polynomial arithmetic operations in the number theoretic transform (NTT) domain. Prior optimization approach KyberMat leverages the transposed-form fast filtering structure and sub-structure sharing technique, reducing the computational complexity. In this paper, a novel and area-efficient design builds upon the KyberMat framework, using the hierarchical interleaved folding algorithm to reduce hardware resources. Two design strategies are utilized in the proposed design. The proposed design initially scales down the NTT/inverse NTT processors via folding transformation, while utilizing a fixed number of DSPs and LUTs across different security levels of ML-KEM. This work further introduces a recursive summing unit along with the interleaving method to ensure continuous data processing and ultimately improve hardware utilization and throughput. The experimental result shows that our proposed area-efficient design achieves an average reduction of 71.55% in DSPs and 63.89% in LUTs among three different security levels, compared to the KyberMat framework.

Quantum computing is an emerging technology that has the potential to achieve exponential speedups over their classical counterparts. To achieve quantum advantage, quantum principles are being applied to fields such as communications, information processing, and artificial intelligence. However, quantum computers face a fundamental issue since quantum bits are extremely noisy and prone to decoherence. Keeping qubits error free is one of the most important steps towards reliable quantum computing. Different stabilizer codes for quantum error correction have been proposed in past decades and several methods have been proposed to import classical error correcting codes to the quantum domain. Design of encoding and decoding circuits for the stabilizer codes have also been proposed. Optimization of these circuits in terms of the number of gates is critical for reliability of these circuits. In this paper, we propose a procedure for optimization of encoder circuits for stabilizer codes. Using the proposed method, we optimize the encoder circuit in terms of the number of 2-qubit gates used. The proposed optimized eight-qubit encoder uses 18 CNOT gates and 4 Hadamard gates, as compared to 14 single qubit gates, 33 2-qubit gates, and 6 CCNOT gates in a prior work. The encoder and decoder circuits are verified using IBM Qiskit. We also present encoder circuits for the Steane code and a 13-qubit code, that are optimized with respect to the number of gates used, leading to a reduction in number of CNOT gates by 1 and 8, respectively.

High-speed long polynomial multiplication is important for applications in homomorphic encryption (HE) and lattice-based cryptosystems. This paper addresses low-latency hardware architectures for long polynomial modular multiplication using the number-theoretic transform (NTT) and inverse NTT (iNTT). Parallel NTT and iNTT architectures are proposed to reduce the number of clock cycles to process the polynomials. Chinese remainder theorem (CRT) is used to decompose the modulus into multiple smaller moduli. Our proposed architecture, namely PaReNTT, makes three novel contributions. First, cascaded parallel NTT and iNTT architectures are proposed such that any buffer requirement for permuting the product of the NTTs before it is input to the iNTT is eliminated. This is achieved by using different folding sets for the NTTs and iNTT. Second, a novel approach to expand the set of feasible special moduli is presented where the moduli can be expressed in terms of a few signed power-of-two terms. Third, novel architectures for pre-processing for computing residual polynomials using the CRT and post-processing for combining the residual polynomials are proposed. These architectures significantly reduce the area consumption of the pre-processing and post-processing steps. The proposed long modular polynomial multiplications are ideal for applications that require low latency and high sample rate such as in the cloud, as these feed-forward architectures can be pipelined at arbitrary levels. Pipelining and latency tradeoffs are also investigated. Compared to a prior design, the proposed architecture reduces latency by a factor of 49.2, and the area-time products (ATP) for the lookup table and DSP, ATP(LUT) and ATP(DSP), respectively, by 89.2% and 92.5%. Specifically, we show that for$n=4096$and a 180-bit coefficient, the proposed 2-parallel architecture requires 6.3 Watts of power while operating at 240 MHz, with 6 moduli, each of length 30 bits, using Xilinx Virtex Ultrascale+ FPGA.

CRYSTAL-Kyber (Kyber) is one of the post-quantum cryptography (PQC) key-encapsulation mechanism (KEM) schemes selected during the standardization process. This paper addresses optimization for Kyber architecture with respect to latency and throughput constraints. Specifically, matrix-vector multiplication and number theoretic transform (NTT)-based polynomial multiplication are critical operations and bottle-necks that require optimization. To address this challenge, we propose an algorithm and hardware co-design approach to systematically optimize matrix-vector multiplication and NTT-based polynomial multiplication by employing a novel sub-structure sharing technique in order to reduce computational complexity, i.e., the number of modular multiplications and modular additions/subtractions consumed. The sub-structure sharing approach is inspired by prior fast parallel approaches based on polyphase decomposition. The proposed efficient feed-forward architecture achieves high speed, low latency, and full utilization of all hardware components, which can significantly enhance the overall efficiency of the Kyber scheme. The FPGA implementation results show that our proposed design, using the fast two-parallel structure, leads to an approximate reduction of 90% in execution time$(\mu s)$, along with a$66\times$improvement in throughput performance.

Spiking Neural Networks (SNNs) are closely related to the dynamics of the human brain and use spatiotemporal encoding of information to generate spikes. Implementing various neuronal models in hardware is a popular field of research aiming to mimic biological behavior. The leaky integrate-and-fire model of the neuron is generally chosen for hardware implementation owing to its simplicity and accuracy in modeling the neuron. This paper proposes an infinite impulse response (IIR) filter-based neuron model and describes a backpropagation-based training algorithm for an SNN built using the proposed neurons. The trained network is implemented on an Ultra96-V2 FPGA to validate the design and demonstrate the power and resource efficiency. The implemented design achieves an accuracy of 98.91% on the MNIST dataset and classifies images at 13,021 frames-per-second (FPS) with a 200 MHz clock while consuming$\approx 7.5\times$higher resource efficiency than previous publications.

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

Graph neural networks (GNNs) have emerged as a powerful tool to process graph-based data in fields like communication networks, molecular interactions, chemistry, social networks, and neuroscience. GNNs are characterized by the ultrasparse nature of their adjacency matrix that necessitates the development of dedicated hardware beyond general-purpose sparse matrix multipliers. While there has been extensive research on designing dedicated hardware accelerators for GNNs, few have extensively explored the impact of the sparse storage format on the efficiency of the GNN accelerators. This article proposes SCV-GNN with the novel sparse compressed vectors (SCVs) format optimized for the aggregation operation. We use$Z$-Morton ordering to derive a data-locality-based computation ordering and partitioning scheme. This article also presents how the proposed SCV-GNN is scalable on a vector processing system. Experimental results over various datasets show that the proposed method achieves a geometric mean speedup of$7.96\times $and$7.04\times $over compressed sparse column (CSC) and compressed sparse row (CSR) aggregation operations, respectively. The proposed method also reduces the memory traffic by a factor of$3.29\times $and$4.37\times $over CSC and CSR, respectively. Thus, the proposed novel aggregation format reduces the latency and memory access for GNN inference.

This paper addresses the design of accelerators using systolic architectures to train convolutional neural networks using a novel gradient interleaving approach. Training the neural network involves computation and backpropagation of gradients of error with respect to the activation functions and weights. It is shown that the gradient with respect to the activation function can be computed using a weight-stationary systolic array, while the gradient with respect to the weights can be computed using an output-stationary systolic array. The novelty of the proposed approach lies in interleaving the computations of these two gradients on the same configurable systolic array. This results in the reuse of the variables from one computation to the other and eliminates unnecessary memory accesses and energy consumption associated with these memory accesses. The proposed approach leads to$1.4 - 2.2 \times $savings in terms of the number of cycles and$1.9 \times $savings in terms of memory accesses in the fully-connected layer. Furthermore, the proposed method uses up to 25% fewer cycles and memory accesses, and 16% less energy than baseline implementations for state-of-the-art CNNs. Under iso-area comparisons, for Inception-v4, compared to weight-stationary (WS), Intergrad achieves 12% savings in energy, 17% savings in memory, and 4% savings in cycles. Savings for Densenet-264 are 18%, 26%, and 27% with respect to energy, memory, and cycles, respectively. Thus, the proposed novel accelerator architecture reduces the latency and energy consumption for training deep neural networks.

Computing the FFT of a single channel is well understood in the literature. However, computing the FFT of multiple channels in a systematic manner has not been fully addressed. This paper presents a framework to design a family of multi-channel FFT architectures using folding and interleaving. Three distinct multi-channel FFT architectures are presented in this paper. These architectures differ in the input and output preprocessing steps and are based on different folding sets, i.e., different orders of execution.

Hyperdimensional (HD) computing holds promise for classifying two groups of data. This paper explores seizure detection from electroencephalogram (EEG) from subjects with epilepsy using HD computing based on power spectral density (PSD) features. Publicly available intra-cranial EEG (iEEG) data collected from 4 dogs and 8 human patients in the Kaggle seizure detection contest are used in this paper. This paper explores two methods for classification. First, few ranked PSD features from small number of channels from a prior classification are used in the context of HD classification. Second, all PSD features extracted from all channels are used as features for HD classification. It is shown that for about half the subjects small number features outperform all features in the context of HD classification, and for the other half, all features outperform small number of features. HD classification achieves above 95% accuracy for six of the 12 subjects, and between 85-95% accuracy for 4 subjects. For two subjects, the classification accuracy using HD computing is not as good as classical approaches such as support vector machine classifiers.

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

The time required for training the neural networks increases with size, complexity, and depth. Training model parameters by backpropagation inherently creates feedback loops. These loops hinder efficient pipelining and scheduling of the tasks within the layer and between consecutive layers. Prior approaches, such as PipeDream, have exploited the use of delayed gradient to achieve inter-layer pipelining. However, these approaches treat the entire backpropagation as a single task; this leads to an increase in computation time and processor underutilization. This paper presents novel optimization approaches where the gradient computations with respect to the weights and the activation functions are considered independently; therefore, these can be computed in parallel. This is referred to as intra-layer optimization. Additionally, the gradient computation with respect to the activation function is further divided into two parts and distributed to two consecutive layers. This leads to balanced scheduling where the computation time of each layer is the same. This is referred to as inter-layer optimization. The proposed system, referred to as LayerPipe, reduces the number of clock cycles required for training while maximizing processor utilization with minimal inter-processor communication overhead. LayerPipe achieves an average speedup of 25 % and upwards of 80% with 7 to 9 processors with less communication overhead when compared to PipeDream.

Sub-graph entropy has recently been applied to functional brain network analysis for identifying important brain regions associated with different brain states and for discriminating brain networks of subjects with psychiatric disorders from healthy controls. This letter describes two pertinent properties of sub-graph entropy. It is shown that when a graph is divided into multiple smaller graphs, the summation of their sub-graph entropy is always less than a constant. Additionally, this summation is always greater than the corresponding graph entropy. We also demonstrate that node entropy, a special case of sub-graph entropy, is stable. Experiments using both synthetic data and real world brain network data are carried out to further validate these points. Overall, node entropy has better stability compared to other centrality metrics. Furthermore, our results illustrate that, for human functional brain networks with two different induced states, node entropy has relatively higher change in ranking. Altogether these findings pave the way for real-world applications of sub-graph entropy as a centrality metric in graph signals.

Spiking Neural Networks (SNNs) represent a biologically inspired computation model capable of emulating neural computation in human brain and brain-like structures. The main promise is very low energy consumption. Classic Von Neumann architecture based SNN accelerators in hardware, however, often fall short of addressing demanding computation and data transfer requirements efficiently at scale. In this article, we propose a promising alternative to overcome scalability limitations, based on a network of in-memory SNN accelerators, which can reduce the energy consumption by up to 150.25= when compared to a representative ASIC solution. The significant reduction in energy comes from two key aspects of the hardware design to minimize data communication overheads: (1) each node represents an in-memory SNN accelerator based on a spintronic Computational RAM array, and (2) a novel, De Bruijn graph based architecture establishes the SNN array connectivity.

This paper introduces an approach for classifying adolescents suffering from MDD using resting-state fMRI. Accurate diagnosis of MDD involves interviews with adolescent patients and their parents, symptom rating scales based on Diagnostic and Statistical Manual of Mental Disorders (DSM), behavioral observation as well as the experience of a clinician. Discovering predictive biomarkers for diagnosing MDD patients using functional magnetic resonance imaging (fMRI) scans can assist the clinicians in their diagnostic assessments. This paper investigates various static and dynamic connectivity measures extracted from resting-state fMRI for assisting with MDD diagnosis. First, absolute Pearson correlation matrices from 85 brain regions are computed and they are used to calculate static features for predicting MDD. A predictive sub-network extracted using sub-graph entropy classifies adolescent MDD vs. typical healthy controls with high accuracy, sensitivity and specificity. Next, approaches utilizing dynamic connectivity are employed to extract tensor based, independent component based and principal component based subject specific attributes. Finally, features from static and dynamic approaches are combined to create a feature vector for classification. A leave-one-out cross-validation method is used for the final predictor performance. Out of 49 adolescents with MDD and 33 matched healthy controls, a support vector machine (SVM) classifier using a radial basis function (RBF) kernel using differential sub-graph entropy combined with dynamic connectivity features classifies MDD vs. healthy controls with an accuracy of 0.82 for leave-one-out cross-validation. This classifier has specificity and sensitivity of 0.79 and 0.84, respectively.

This paper addresses design of accelerators using systolic architectures for training of neural networks using a novel gradient interleaving approach. Training the neural network involves backpropagation of error and computation of gradients with respect to the activation functions and weights. It is shown that the gradient with respect to the activation function can be computed using a weight-stationary systolic array while the gradient with respect to the weights can be computed using an output-stationary systolic array. The novelty of the proposed approach lies in interleaving the computations of these two gradients to the same configurable systolic array. This results in reuse of the variables from one computation to the other and eliminates unnecessary memory accesses. The proposed approach leads to 1.4-2.2× savings in terms of number of cycles and 1.9× savings in terms of memory accesses. Thus, the proposed accelerator reduces latency and energy consumption.

Physical unclonable functions (PUFs) are hardware security primitives that are used for device authentication and cryptographic key generation. Standard XOR PUFs typically contain multiple standard arbiter PUFs as components, and are more secure than standard arbiter PUFs or feed-forward (FF) arbiter PUFs (FF PUFs). This paper proposes design of feed-forward XOR PUFs (FFXOR PUFs) where each component PUF is a FF PUF. Various homogeneous and heterogeneous FFXOR PUFs are presented and evaluated in terms of four fundamental properties of PUFs: uniqueness, attack-resistance, reliability and randomness. Certain key issues pertaining to XOR PUFs such as their vulnerability to machine learning attacks and instability in responses are investigated. Other important challenges like the lack of uniqueness in FF PUFs and the asymmetry in FPGA arbiter PUFs are addressed and it is shown that FFXOR PUFs can naturally overcome these problems. It is shown that heterogeneous FFXOR PUFs (i.e., FFXOR PUFs with non-identical components) can be resilient to state-of-the-art machine learning attacks. We also present systematic reliability analysis of FFXOR PUFs and demonstrate that soft-response thresholding can be used as an effective countermeasure to overcome the degraded reliability bottleneck. Observations from simulations are further verified through hardware implementation of 64-bit FFXOR PUFs on Xilinx Artix-7 FPGA.

This paper describes a novel approach to synthesize molecular reactions to compute a radial basis function (RBF) support vector machine (SVM) kernel. The approach is based on fractional coding where a variable is represented by two molecules. The synergy between fractional coding in molecular computing and stochastic logic implementations in electronic computing is key to translating known stochastic logic circuits to molecular computing. Although inspired by prior stochastic logic implementation of the RBF-SVM kernel, the proposed molecular reactions require non-obvious modifications. This paper introduces a new explicit bipolar-to-unipolar molecular converter for intermediate format conversion. Two designs are presented; one is based on the explicit and the other is based on implicit conversion from prior stochastic logic. When 5 support vectors are used, it is shown that the DNA RBF-SVM realized using the explicit format conversion has orders of magnitude less regression error than that based on implicit conversion.

Physical unclonable functions (PUFs) can be used to generate unique signatures of integrated circuit (IC) chips. XOR arbiter PUFs (XOR PUFs), that typically contain multiple standard arbiter PUFs as their components, are more secure than standard arbiter PUFs. This paper proposes design of feed-forward XOR PUFs (FFXOR PUFs) where each component PUF is a feed-forward arbiter PUF (FF PUF). Arbiter PUFs suffer from two main drawbacks: vulnerability to modeling attacks and degraded reliability. It is shown that FFXOR PUFs cannot be accurately modeled if the number of component PUFs is more than 5 or 6. We also state that the number of machine learning runs required to learn a model using evolutionary strategies increases by a factor of N^2/2 if N-stage FF PUFs with one loop are used as components instead of standard arbiter PUFs. In general, for FF PUFs with k loops (one intermediate arbiter), it would increase by a factor of N \choose k+1. We also show that the use of a thresholding strategy can increase the reliability of FFXOR PUFs by about 30% for a 15% noise level.

Modern applications for DSP systems are increasingly constrained by tight area and power requirements. Therefore, it is imperative to analyze effective strategies that work within these requirements. This paper studies the impact of finite word-length arithmetic on the signal to quantization noise ratio (SQNR), power and area for a real-valued serial FFT implementation. An experiment is set up using a hardware description language (HDL) to empirically determine the tradeoffs associated with the following parameters: (i) the input word-length, (ii) the word-length of the rotation coefficients, and (iii) length of the FFT on performance (SQNR), power and area. The results of this paper can be used to make design decisions by careful selection of word-length to achieve a reduction in area and power for an acceptable loss in SQNR.

This paper presents a novel incremental feature selection method based on minimum uncertainty and feature sample elimination (referred as MUSE). Feature selection is an important step in machine learning. In an incremental feature selection approach, past approaches have attempted to increase class relevance while simultaneously minimizing redundancy with previously selected features. One example of such an approach is the feature selection method of minimum Redundancy Maximum Relevance (mRMR). The proposed approach differs from prior mRMR approach in how the redundancy of the current feature with previously selected features is reduced. In the proposed approach, the feature samples are divided into a pre-specified number of bins; this step is referred to as feature quantization. A novel uncertainty score for each feature is computed by summing the conditional entropies of the bins, and the feature with the lowest uncertainty score is selected. For each bin, its impurity is computed by taking the minimum of the probability of Class 1 and of Class 2. The feature samples corresponding to the bins with impurities below a threshold are discarded and are not used for selection of the subsequent features. The significance of the MUSE feature selection method is demonstrated using the two datasets: arrhythmia and hand digit recognition (Gisette), and datasets for seizure prediction from five dogs and two humans. It is shown that the proposed method outperforms the prior mRMR feature selection method for most cases. For the arrhythmia dataset, the proposed method achieves 30 percent higher sensitivity at the expense of 7 percent loss of specificity. For the Gisette dataset, the proposed method achieves 15 percent higher accuracy for Class 2, at the expense of 3 percent lower accuracy for Class 1. With respect to seizure prediction among 5 dogs and 2 humans, the proposed method achieves higher area-under-curve (AUC) for all subjects.

Retinal swelling due to the accumulation of fluid is associated with the most vision-threatening retinal diseases. Optical coherence tomography (OCT) is the current standard of care in assessing the presence and quantity of retinal fluid and image-guided treatment management. Deep learning methods have made their impact across medical imaging, and many retinal OCT analysis methods have been proposed. However, it is currently not clear how successful they are in interpreting the retinal fluid on OCT, which is due to the lack of standardized benchmarks. To address this, we organized a challenge RETOUCH in conjunction with MICCAI 2017, with eight teams participating. The challenge consisted of two tasks: fluid detection and fluid segmentation. It featured for the first time: all three retinal fluid types, with annotated images provided by two clinical centers, which were acquired with the three most common OCT device vendors from patients with two different retinal diseases. The analysis revealed that in the detection task, the performance on the automated fluid detection was within the inter-grader variability. However, in the segmentation task, fusing the automated methods produced segmentations that were superior to all individual methods, indicating the need for further improvements in the segmentation performance.

This paper presents a performance comparison of new authenticated encryption (AE) algorithms which are aimed at providing better security and resource efficiency compared to existing standards. Specifically, these algorithms improve the security of existing AE standards by providing a critical property termed nonce-misuse resistance. This paper addresses algorithm to architectural mappings of several candidates from the ongoing Competition for AE: Security, Applicability, and Robustness as well as a submission from the Crypto Forum Research Group. Implementations of the architectures on both field-programmable gate arrays and application-specific integrated circuits platforms are provided and compared with the architecture of a popular standard: Advanced Encryption Standard in Galois Counter mode (AES-GCM). Optimizations that are applicable to AE, in general, and nonce-misuse-resistant architectures, in particular, are presented. A hardware-software codesign approach to optimization is also discussed. The implementations via proposed optimizations demonstrate that new AE algorithms can provide comparable performance as standard AES-GCM while enhancing security and resource utilization for specific use-case scenarios.

This paper addresses the effect of aging on linear and non-linear MUX physical unclonable functions (PUFs). It is well known that a PUF response can be modeled in terms of the delay difference of MUX stages. In this paper, we show that the aging effects can be modeled in terms of variations in delay-difference and arbiter delay. Specifically, with aging, the percent delay-difference variation of each MUX stage can be modeled as a ratio of two correlated Gaussian random variables. This ratio distribution is shown to be approximately Gaussian with zero mean and variance increasing with time. In case of the arbiter, the ratio distribution is modeled as a Gaussian with positive mean. The paper makes three contributions: modeling the effect of aging in terms of percent variations in delay-difference of the MUX stages and arbiter delay, analysis of authentication accuracy with aging, and approaches to increase the PUF's lifetime by either recalibrating it to obtain new delay-difference parameters, or by tuning a threshold based on the total delay-difference. A general approach for selecting the threshold values is described in the paper. It is shown that the authentication accuracy of a PUF is significantly affected due to aging effects of the arbiter itself. Therefore, under the assumption that the variations in arbiter delay are considerably more than in delay-differences, the performance degradation in the case of aging alone is prominent compared to noise alone. We show that the authentication accuracy of a feed-forward PUF is more degraded compared to linear or modified feed-forward PUF. Metrics like Jenson-Shannon and Henze-Penrose divergence are also used to analyze the effect of aging.

This paper presents a novel incremental-precision classification approach that leads to a reduction in energy consumption of linear classifiers for IoT applications. Features are first input to a low-precision classifier. If the classifier successfully classifies the sample, then the process terminates. Otherwise, the classification performance is incrementally improved by using a classifier of higher precision. This process is repeated until the classification is complete. The argument is that many samples can be classified using the low-precision classifier, leading to a reduction in energy. To achieve incremental-precision, a novel data-path decomposition is proposed to design of fixed-width adders and multipliers. These components improve the precision without recalculating the outputs, thus reducing energy. Using a linear classification example, it is shown that the proposed incremental-precision based multi-level classifier approach can reduce energy by about 41% while achieving comparable accuracies as that of a full-precision system.

This paper presents a logistic regression based approach to predict the soft-response for a challenge using the total delay-difference as an input. This approach enables us to determine whether a challenge is stable or not. Soft-response is the probability of response bit corresponding to the challenge being 1. The total delay-difference is computed from the input challenge by assuming that the delay-difference of the stages are known. The approach learns a logistic function based on the total delay-difference which has just 3 parameters. Therefore, this is a simple approach which gives comparable performance against a more complex approach based on artificial neural network (ANN) models. The model demonstrates good sensitivity and precision but poor specificity. Furthermore, we use scaling parameter of the logistic function to study its relation to the arbiter's timing parameters like setup and hold time.

A Physical Unclonable Function (PUF) using capacitor mismatch in a standard successive approximation register analog-to-digital converter (SAR-ADC) as the entropy source is demonstrated in 65nm CMOS. SAR-ADCs are readily available in many system-on-chips, making the hardware overhead of the proposed PUF almost negligible. The inherent process variation of metal-oxide-metal (MOM) capacitors is harnessed through a charge redistribution operation which is sampled by the voltage comparator. To enhance the stability of the PUF output, soft response generation and dynamic thresholding techniques were adopted. Finally, we verify that performing the enrollment operation at a lower operating voltage can ensure that PUF responses are stable at the nominal supply voltage used during authentication.

Deep neural network (DNN) has emerged as the most important and popular artificial intelligent (AI) technique. The growth of model size poses a key energy efficiency challenge for the underlying computing platform. Thus, model compression becomes a crucial problem. However, the current approaches are limited by various drawbacks. Specifically, network sparsification approach suffers from irregularity, heuristic nature and large indexing overhead. On the other hand, the recent structured matrix-based approach (i.e., CirCNN) is limited by the relatively complex arithmetic computation (i.e., FFT), less flexible compression ratio, and its inability to fully utilize input sparsity. To address these drawbacks, this paper proposes PermDNN, a novel approach to generate and execute hardware-friendly structured sparse DNN models using permuted diagonal matrices. Compared with unstructured sparsification approach, PermDNN eliminates the drawbacks of indexing overhead, non-heuristic compression effects and time-consuming retraining. Compared with circulant structure-imposing approach, PermDNN enjoys the benefits of higher reduction in computational complexity, flexible compression ratio, simple arithmetic computation and full utilization of input sparsity. We propose PermDNN architecture, a multi-processing element (PE) fully-connected (FC) layer-targeted computing engine. The entire architecture is highly scalable and flexible, and hence it can support the needs of different applications with different model configurations. We implement a 32-PE design using CMOS 28nm technology. Compared with EIE, PermDNN achieves 3.3x~4.8x higher throughout, 5.9x~8.5x better area efficiency and 2.8x~4.0x better energy efficiency on different workloads. Compared with CirCNN, PermDNN achieves 11.51x higher throughput and 3.89x better energy efficiency.

This paper proposes a novel technique for hardware obfuscation termed dynamic functional obfuscation. Hardware obfuscation refers to a set of countermeasures used against IC counterfeiting and illegal overproduction. Traditionally, obfuscation encrypts semiconductor circuits using key inputs which must be set to a correct value to operate the circuit correctly. By keeping the key values secret during the manufacturing process, any attempt by unauthorized parties to overproduce chips or pirate designs is thwarted. The proposed dynamic technique differs from existing fixed obfuscation schemes as the obfuscating signals change over time. This results in inconsistent circuit behavior upon input of incorrect key, where the chip operates correctly sometimes and fails sometimes. The advantage of dynamic obfuscation is that it results in stronger obfuscation by increasing the time complexity of deciphering the correct key using brute-force attack, even with shorter keys. Moreover, the dynamic nature of these circuits also makes them resistant to reverse engineering and SAT solver-based attacks. To achieve dynamic obfuscation, ideas from hardware Trojan literature and sequentially triggered counters are utilized. A demonstration of obfuscation on sequential circuits implementing fast Fourier transform (FFT) algorithm and Ethernet IP shows low overall area and power overheads of less than 1%. Security in terms of time to attack for the FFT circuit (for a key size of 30 bits and a system operating at 100 MHz) is increased to 1021,055 years using dynamic obfuscation compared with only 5.36 s using fixed obfuscation schemes. For the Ethernet IP core, time to attack of dynamic obfuscation with a key size of 32 bits is 1046,423,135 years compared with 21.47s with fixed obfuscation. It is also shown that for a key size of K bits, the lower bound for time to attack using brute-force is proportional to K2Kand K22Kfor the proposed design using one and two random number generators, respectively.

This paper shows that performing an XOR operation between the outputs of parallel arbiter PUFs generates a more secure output at the expense of reduced stability. In this work, we evaluate the security and stability of XOR PUFs using 1,000,000 randomly chosen challenges, applied to 10 custom-designed PUF chips, tested for 100,000 cycles per challenge, under different voltage and temperature conditions. Based on extensive hardware data, we propose a practical method for selecting challenges that will produce stable responses. A linear regression approach based on soft responses collected during enrollment phase was used to build accurate models for each individual arbiter PUF. Hardware data from fabricated chips verify that the approach is highly effective.

This paper proposes a novel method, referred to as \textit{double-NAND expansion}, to implement polynomials with all positive coefficients using unipolar stochastic logic. %The inputs and outputs of these circuits lie between 0 and 1, and are encoded using unary bit streams. Prior work has addressed implementation of polynomials with alternately positive and negative coefficients and non-increasing magnitudes, using stochastic logic based on Horner's rule. However, Horner's expansion is not applicable to implementation of polynomials with all positive coefficients. The proposed double-NAND expansion leads to implementations of polynomials using no more than 2n NAND gates where n represents the degree of the polynomial. %While the Horner's rule leads to cascaded AND-NAND gates, the proposed expansion leads to cascaded double-NAND gates.The proposed implementations are compared with those based on multiplexers, Bernstein polynomial method, finite state machine method and factorization. The paper also considers implementations of several functions expressed as polynomials using truncated Mclaurin series based on the proposed approach. The experimental results show that the proposed method outperforms the prior methods in terms of accuracy, hardware complexity, and critical path.

Blind source separation (BSS) using independent component based analysis (e.g., probabilistic ICA and infomax ICA) have been studied in-depth to extract common hemodynamic sources for a group of functional magnetic resonance images (fMRI). The inherent assumption here is that the sources must be non-Gaussian. For most of the real world data, the decomposition is non-unique. Furthermore, there is no quantitative way to determine the component(s) of interest common for the group. This paper shows that using a novel constrained Parallel Factor Analysis (PARAFAC)-based tensor decomposition, one can extract the common task signals and spatial maps from a group of noisy fMRI as rank-1 tensors. The extracted hemodynamic signals have very high correlation with ideal hemodynamic response. A quantitative algorithm to extract common components for a group of subjects is also presented. The modified decomposition preserves the uniqueness under mild conditions which is the most attractive feature for any PARAFAC-based tensor decomposition approach.

Authenticated Encryption (AE) schemes are key-based cryptographic algorithms that provide both goals of confidentiality of message and authenticity of the sender, simultaneously. Traditionally, Advanced Encryption Standard (AES) in Galois Counter Mode (AES-GCM), among several other approaches, has been employed for Authenticated Encryption. However, several lightweight cryptographic applications such as those used in sensor networks or RFID security can benefit from new AE schemes which can be constructed more efficiently. In this paper we provide evaluations for Deoxys, a third round candidate from the ongoing Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR). We describe simplified flow diagrams and a detailed summary on the timing performance, area, memory and energy requirements of AES-GCM and Deoxys, using our own implementations on Altera Cyclone V FPGAs. Our analysis shows that Deoxys requires 10% less energy per bit and 25% less LUTs as compared to AES-GCM.

Hardware obfuscation has been proposed as a hardware security measure against reverse engineering, intellectual property (IP) piracy and integrated circuits (IC) overbuilding. In this paper, we present a novel method of obfuscation using a hierarchical approach. In the design flow, IP vendors obfuscate their designs using a set of keys and provide these keys to the design house. The design house then integrates all the IPs and adds its own keys to create a complete obfuscated system. This prevents both misuse of IPs and illegal use of ICs since only secure parties have access to the correct keys. The obfuscation at each level is performed using a mode-based approach in which the design can operate in meaningful and non-meaningful modes. The design is functionally correct in only one mode. An attacker needs to work through different levels of the design to correctly decipher its operation and correct working mode. Since each of the IPs can work in multiple meaningful modes, the attack becomes more difficult as the number of IPs increases. These ideas are demonstrated using a convolution architecture with fast Fourier transform (FFT) blocks. With only about 13% area and 15% power overhead over an unobfuscated design, it is shown that the proposed design has the flexibility to be obfuscated with different key sizes and overheads depending on the level of security.

This paper proposes a novel entropy test to determine whether a MUX PUF is linear or not. Three MUX PUF configurations are considered, namely linear, feed-forward and modified feed-forward. In addition to these, we also consider feed-forward structures like overlap, cascade and separate configurations. The approach is focused on computing the conditional entropy of responses to a set of predefined challenges. The challenge set consists of randomly chosen challenges and their 1-bit neighbors. The entropy is computed across the responses of two 1-bit neighboring challenges. For non-linear MUX PUFs like feed-forward, the method determines the MUX stages which are controlled by internally generated challenge bits as opposed to external challenge bits. This is based on the observation that the conditional entropy for each of these stages is zero. Also, the number of zero conditional entropy values across the MUX stages provide an upper bound on the number of internal arbiters present in the PUF. With the proposed approach, we observe 100% sensitivity and 100% specificity for identifying non-linearity. Furthermore, we show that the proposed approach requires very less number of stable random challenges (about 50) for successfully determining whether a PUF is linear or not for real chips.

Implementations of polynomials and functions using stochastic logic have been of interest due to their low-area and high fault-tolerance properties. In stochastic logic, numbers are represented using unary bit streams where each bit is of same weight. If a number is represented in the range [0,1], the representation is referred to as unipolar. The representation is referred as bipolar if the number lies in the range [-1, 1]. Typically, inputs and outputs are in same format. However, sometimes the input and output may be in different formats; these are referred as circuits using hybrid formats. While analysis of unipolar stochastic logic circuits and bipolar logic circuits containing ex-or, ex-nor and multiplexors are well understood, the analysis of general bipolar stochastic logic circuits and hybrid logic circuits are not well understood. This paper presents general approaches to compute outputs of bipolar and hybrid stochastic logic circuits. It is shown that the analysis approach presented in this paper can form a basis for synthesis of stochastic logic circuits in bipolar and hybrid formats.

The start-up value of an SRAM cell is unique, random, and unclonable as it is determined by the inherent process mismatch between transistors. These properties make SRAM an attractive circuit for generating encryption keys. The primary challenge for SRAM based key generation, however, is the poor stability when the circuit is subject to random noise, temperature and voltage changes, and device aging. Temporal majority voting (TMV) and bit masking were used in previous works to identify and store the location of unstable or marginally stable SRAM cells. However, TMV requires a long test time and significant hardware resources. In addition, the number of repetitive power-ups required to find the most stable cells is prohibitively high. To overcome the shortcomings of TMV, we propose a novel data remanence based technique to detect SRAM cells with the highest stability for reliable key generation. This approach requires only two remanence tests: writing `1' (or `0') to the entire array and momentarily shutting down the power until a few cells flip. We exploit the fact that the cells that are easily flipped are the most robust cells when written with the opposite data. The proposed method is more effective in finding the most stable cells in a large SRAM array than a TMV scheme with 1,000 power-up tests. Experimental studies show that the 256-bit key generated from a 512 kbit SRAM using the proposed data remanence method is 100% stable under different temperatures, power ramp up times, and device aging.

This article addresses subtraction and polynomial computations using unipolar stochastic logic. Stochastic computing requires simple logic gates, and stochastic logic--based circuits are inherently fault tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. It is well known that an AND gate and a multiplexer can be used to implement stochastic unipolar multiplier and adder, respectively. Although it is easy to realize multiplication and scaled addition, implementation of subtraction is nontrivial using unipolar stochastic logic. Additionally, an accurate computation of subtraction is critical for the implementation of polynomials with negative coefficients in stochastic unipolar representation. This work, for the first time, demonstrates that instead of using well-known Bernstein polynomials, stochastic computation of polynomials can be implemented by using a stochastic subtractor and factorization. Three major contributions are given in this article. First, two approaches are proposed to compute subtraction in stochastic unipolar representation. In the first approach, the subtraction operation is approximated by cascading multilevels of OR and AND gates. The accuracy of the approximation is improved with the increase in the number of stages. In the second approach, the stochastic subtraction is implemented using a multiplexer and a stochastic divider. This approach requires more hardware complexity due to the use of a linear-feedback shift register and a counter for division. Second, computation of polynomials in stochastic unipolar format is presented using scaled addition and proposed stochastic subtraction. Third, we propose stochastic computation of polynomials using factorization. Stochastic implementations of first- and second-order factors are presented for different locations of polynomial roots. From experimental results, it is shown that the proposed stochastic logic circuits require less hardware complexity than the previous stochastic polynomial implementation using Bernstein polynomials.

Neural network (NN) systems are widely used in many important applications ranging from computer vision to speech recognition. To date, most NN systems are processed by general processing units like CPUs or GPUs. However, as the sizes of dataset and network rapidly increase, the original software implementations suffer from long training time. To overcome this problem, specialized hardware accelerators are needed to design high-speed NN systems. This article presents an efficient hardware architecture of restricted Boltzmann machine (RBM) that is an important category of NN systems. Various optimization approaches at the hardware level are performed to improve the training speed. As-soon-as-possible and overlapped-scheduling approaches are used to reduce the latency. It is shown that, compared with the flat design, the proposed RBM architecture can achieve 50% reduction in training time. In addition, an on-the-fly computation scheme is also used to reduce the storage requirement of binary and stochastic states by several hundreds of times. Then, based on the proposed approach, a 784-2252 RBM design example is developed for MNIST handwritten digit recognition dataset. Analysis shows that the VLSI design of RBM achieves significant improvement in training speed and energy efficiency as compared to CPU/GPU-based solution.

Physical unclonable functions (PUFs) can extract chip-unique signatures from integrated circuits (ICs) by exploiting the uncontrollable randomness due to manufacturing process variations. These signatures can then be used for many hardware security applications including authentication, anti-counterfeiting, IC metering, signature generation, and obfuscation. However, most of these applications require error correcting methods to produce consistent PUF responses across different environmental conditions. This paper presents a novel method to enable lightweight, secure, and reliable PUF-based authentication. A two-level finite-state machine (FSM) is proposed to correct erroneous bits generated by environmental variations (e.g., temperature, voltage, and aging variations). In the proposed method, each PUF response is mapped to a key during design phase. The actual key can be determined from the PUF response only after the chip is fabricated. Because the key is not known to the foundry, the proposed approach prevents counterfeiting. The performance of the proposed method and other applications are also discussed. Our experimental results show that the cost of the proposed self-correcting two-level FSM is significantly less than that of the commonly used error correcting codes. It is shown that the proposed self-correcting FSM consumes about 2× to 10× less area and about 20× to 100× less power than the Bose-Chaudhuri-Hochquenghem codes.

Chemical reaction networks (CRNs) provide a fundamental model in the study of molecular systems. Widely used as formalism for the analysis of chemical and biochemical systems, CRNs have received renewed attention as a model for molecular computation. This paper demonstrates that, with a new encoding, CRNs can compute any set of polynomial functions subject only to the limitation that these functions must map the unit interval to itself. These polynomials can be expressed as linear combinations of Bernstein basis polynomials with positive coefficients less than or equal to 1. In the proposed encoding approach, each variable is represented using two molecular types: a type-0 and a type-1. The value is the ratio of the concentration of type-1 molecules to the sum of the concentrations of type-0 and type-1 molecules. The proposed encoding naturally exploits the expansion of a power-form polynomial into a Bernstein polynomials. The method is illustrated first for generic CRNs; then the chemical reactions designed for two examples are mapped to DNA strand-displacement reactions.

This paper addresses computing complex functions using unipolar stochastic logic. Stochastic computing requires simple logic gates and is inherently fault-tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. Implementations of complex functions cost extremely low hardware complexity compared to traditional two's complement implementation. In this paper an approach based on polynomial factorization is proposed to compute functions in unipolar stochastic logic. In this approach, functions are expressed using polynomials, which are derived from Taylor expansion or Lagrange interpolation. Polynomials are implemented in stochastic logic by using factorization. Experimental results in terms of accuracy and hardware complexity are presented to compare the proposed designs of complex functions with previous implementations using Bernstein polynomials.

This paper presents novel architectures for machine learning based classifiers using stochastic logic. Two types of classifier architectures are presented. These include: linear support vector machine (SVM) and artificial neural network (ANN). Stochastic computing systems require fewer logic gates and are inherently fault-tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. These architectures are validated using seizure prediction from electroencephalogram (EEG) as an application example. To improve the accuracy of proposed stochastic classifiers, a novel approach based on linear transformation of input data is proposed for EEG signal classification using linear SVM classifiers. Simulation results in terms of the classification accuracy are presented for the proposed stochastic computing and the traditional binary implementations based datasets from one patient. Compared to conventional binary implementation, the accuracy of the proposed stochastic ANN is improved by 5.89%. Synthesis results are also presented for EEG signal classification. Compared to the traditional binary linear SVM, the hardware complexity, power consumption and critical path of the stochastic implementation are reduced by 78%, 74% and 53%, respectively. The hardware complexity, power consumption and critical path of the stochastic ANN classifier are reduced by 92%, 88% and 47%, respectively, compared to the conventional binary implementation.

Polar codes have become one of the most attractive topics in coding theory community because of their provable capacity-achieving property. Belief propagation (BP) algorithm, as one o f the popular approaches for decoding polar codes, has unique advantage of high parallelism but suffers from high computation complexity, which translates to very large silicon area and high power consumption. This paper, for the first time, exploits the design of polar BP decoder using stochastic computing. Several methods ranging from algorithm level to architecture level are presented to improve the error and hardware performances of the stochastic BP decoder. The approaches proposed in this work provide a potential low-cost solution for stochastic BP decoder design.

In this work, we present probability based response generation schemes for MUX based Physical Unclonable Functions (PUFs). Compared to previous implementations where temporal majority voting (TMV) based on limited samples and coarse criteria was utilized to determine final responses, our design can collect soft responses with detailed probability information using simple on-chip circuits. Thresholds with fine accuracy are applied to efficiently distinguish stable and unstable challenge response pairs (CRPs). A 32nm test chip including both linear and feed-forward MUX PUFs was implemented for concept verification. Based on a detailed analysis of the hardware data, we propose several enhanced thresholding strategies for determining stable CRPs. For instance, a stringent threshold can be imposed in enrollment phase for selecting good CRPs, while a relaxed threshold can be used during normal authentication phase. Experimental data shows a high degree of uniqueness and randomness in the PUF responses which can be attributed to the carefully optimized circuit layout. Finally, output characteristic of a feed-forward MUX PUF was compared to that of a standard linear MUX PUF from the same 32nm chip.

True random number generators (TRNGs) are crucial components for the security of cryptographic systems. In contrast to pseudo--random number generators (PRNGs), TRNGs provide higher security by extracting randomness from physical phenomena. To evaluate a TRNG, statistical properties of the circuit model and raw bitstream should be studied. In this article, a model for the beat frequency detector--based high-speed TRNG (BFD-TRNG) is proposed. The parameters of the model are extracted from the experimental data of a test chip. A statistical analysis of the proposed model is carried out to derive mean and variance of the counter values of the TRNG. Our statistical analysis results show that mean of the counter values is inversely proportional to the frequency difference of the two ring oscillators (ROSCs), whereas the dynamic range of the counter values increases linearly with standard deviation of environmental noise and decreases with increase of the frequency difference. Without the measurements from the test data, a model cannot be created; similarly, without a model, performance of a TRNG cannot be predicted. The key contribution of the proposed approach lies in fitting the model to measured data and the ability to use the model to predict performance of BFD-TRNGs that have not been fabricated. Several novel alternate BFD-TRNG architectures are also proposed; these include parallel BFD, cascade BFD, and parallel-cascade BFD. These TRNGs are analyzed using the proposed model, and it is shown that the parallel BFD structure requires less area per bit, whereas the cascade BFD structure has a larger dynamic range while maintaining the same mean of the counter values as the original BFD-TRNG. It is shown that 3.25 M and 4 M random bits can be obtained per counter value from parallel BFD and parallel-cascade BFD, respectively, where M counter values are computed in parallel. Furthermore, the statistical analysis results illustrate that BFD-TRNGs have better randomness and less cost per bit than other existing ROSC-TRNG designs. For example, it is shown that BFD-TRNGs accumulate 150% more jitter than the original two-oscillator TRNG and that parallel BFD-TRNGs require one-third power and one-half area for same number of random bits for a specified period.

This paper presents a novel classification-based optic disc (OD) segmentation algorithm that detects the OD boundary and the location of vessel origin (VO) pixel. First, the green plane of each fundus image is resized and morphologically reconstructed using a circular structuring element. Bright regions are then extracted from the morphologically reconstructed image that lie in close vicinity of the major blood vessels. Next, the bright regions are classified as bright probable OD regions and non-OD regions using six region-based features and a Gaussian mixture model classifier. The classified bright probable OD region with maximum Vessel-Sum and Solidity is detected as the best candidate region for the OD. Other bright probable OD regions within 1-disc diameter from the centroid of the best candidate OD region are then detected as remaining candidate regions for the OD. A convex hull containing all the candidate OD regions is then estimated, and a best-fit ellipse across the convex hull becomes the segmented OD boundary. Finally, the centroid of major blood vessels within the segmented OD boundary is detected as the VO pixel location. The proposed algorithm has low computation time complexity and it is robust to variations in image illumination, imaging angles, and retinal abnormalities. This algorithm achieves 98.8%-100% OD segmentation success and OD segmentation overlap score in the range of 72%-84% on images from the six public datasets of DRIVE, DIARETDB1, DIARETDB0, CHASE_DB1, MESSIDOR, and STARE in less than 2.14 s per image. Thus, the proposed algorithm can be used for automated detection of retinal pathologies, such as glaucoma, diabetic retinopathy, and maculopathy.

Polar codes, as the new generation of channel codes, have potential applications in communication and storage systems. Successive-cancellation list (SCL) algorithm is the main decoding approach for improving the error-correcting performance of polar codes. Recently low-complexity SCL decoders in the log-likelihood-ratio (LLR) form were proposed to replace the original ones in the likelihood form. However, these LLR-based SCL decoders can only decode 1 bit in one cycle, which leads to very long latency. This paper, for the first time, presents a reduced-latency LLR-based SCL decoder. With the new decoding scheme that determines 2 bits simultaneously, the proposed (n, k) decoder reduces the entire decoding latency from 3n-2 to 3n-2 clock cycles with the same critical path delay as the prior LLR-based SCL decoders. As a result, the decoding throughput and hardware efficiency are increased by a factor of 1.5. In addition, compared to a prior reduced-latency non-LLR-based SCL decoder, the proposed work reduces the area by two times as well.

The Fast Fourier transform (FFT) is an important operation in digital signal processing applications. In applications such as biomedical signal processing, the signals are real. The real-valued signals exhibit conjugate symmetry, giving rise to redundant values in the outputs. This property can be exploited to reduce arithmetic computations, area and power consumption. This paper presents hardware architectures for computing real FFT that exploits this conjugate symmetry property where the inputs are processed in a serial manner. This is facilitated by pushing the twiddle factor values across various butterfly stages. In this paper, two different serial FFT architectures are presented: one using real and the other using hybrid datapaths. These architectures process one sample per clock cycle and are well suited for low-sample-rate applications such as biomedical. These architectures are also modified so that two independent computations can be interleaved in the same datapath. The advantage of interleaving is reduction in area, and is attractive for applications where FFT computation of two independent real signals is required.

This paper presents novel architectures for linear-phase FIR digital filters using stochastic computing. Stochastic computing systems require fewer logic gates and are inherently fault-tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. Compared to direct-form linear-phase FIR filters, linear-phase lattice filters require twice the number of multipliers but the same number of adders. The hardware complexities of stochastic implementations of linear-phase FIR filters for direct-form and lattice structures are comparable. Using speech signals from ICA '99 Synthetic Benchmarks, it is shown that, for linear-phase FIR filters, the error-to-signal power ratios of stochastic direct-form and stochastic lattice filters are about the same. However, the error-to-signal power of stochastic direct-form or lattice filter is an order of magnitude higher at very low fault rates but is more than two orders of magnitude less when the fault rate is about one percent than the direct-form, where the faults represent random bit-flips at outputs of all logic gates.

Design of integrated circuits that cannot be reverse engineered is very important for protecting the intellectual property of owners. Integrated circuits can be obfuscated by introducing several modes into the control flow. Only one of the modes is the desired mode and other modes represent either meaningful modes where computations are partially correct or modes where the outputs computed are completely random. This paper presents a novel architecture and implementation of an obfuscated FFT for real input signals. The proposed design can be reconfigured to compute real FFTs of size N or N/4 with 2-parallel or 4-parallel processing, which are considered the 4 meaningful modes in the design. A 4-bit configure data is used to select one of the four meaningful modes. The remaining 12 modes output partially correct results. The meaningful mode with the most number of blocks, i.e., an N-point, 4-parallel real FFT, is designed first and that circuit is then obfuscated with the inclusion of a reconfigurator and an obfuscating FSM. A novel control flow approach is introduced for hiding the modes for obfuscation. It is shown that the proposed approach results in minimal area and power overhead compared to the base design.

Integrated circuit chips fabricated using nano-scale CMOS technologies will be prone to errors caused by fluctuations in threshold voltage, supply voltage, electromigration, random dopant fluctuations, aging, timing errors and soft errors. Design of nano-scale failure-resistant systems has drawn significant interest in past few years. One common approach to reducing errors is the use of triple modular redundancy (TMR). The hardware overhead associated with TMR is significantly high. This paper presents a novel partial triple modular redundancy (PTMR) approach that achieves the same or better fault-tolerance as that of TMR but with significantly less hardware overhead. In a weighted number system, the most significant bits carry greater weight and preserving these bits is more critical than the lower significant bits. In PTMR, only the P most significant bits of the result are computed using TMR as opposed to all the W bits, where W represents the word-length of the operands. The proposed PTMR approach is illustrated in the context of a ripple-carry adder. It is shown that the hardware overhead can be reduced by 75% to 87.5% with P = 4 as the word-length varies from 16 to 32, with average error power equal to or less than that of TMR. It is shown that P = 3 or 4 is sufficient for word-lengths varying from 16 to 32.

Polar codes have emerged as the most favorable channel codes for their unique capacity-achieving property. To date, numerous approaches for efficient decoding of polar codes have been reported. However, these prior efforts focused on design of polar decoders via deterministic computation, while the behavior of stochastic polar decoder, which can have potential advantages such as low complexity and strong error-resilience, has not been studied in existing literatures. This paper, for the first time, investigates polar decoding using stochastic logic. Specifically, the commonly-used successive cancellation (SC) algorithm is reformulated into the stochastic form. Several methods that can potentially improve decoding performance are discussed and analyzed. Simulation results show that a stochastic SC decoder can achieve similar error-correcting performance as its deterministic counterpart. This work can pave the way for future hardware design of stochastic polar codes decoders.

A novel approach using neuronal potential similarity (NPS) of two intracranial electroencephalogram (iEEG) electrodes placed over the foci is proposed for automated early seizure detection in patients with refractory partial epilepsy. The NPS measure is obtained from the spectral analysis of space-differential iEEG signals. Ratio between the NPS values obtained from two specific frequency bands is then investigated as a robust generalized measure, and reveals invaluable information about seizure initiation trends. A threshold-based classifier is subsequently applied on the proposed measure to generate alarms. The performance of the method was evaluated using cross-validation on a large clinical dataset, involving 183 seizure onsets in 1785 h of long-term continuous iEEG recordings of 11 patients. On average, the results show a high sensitivity of 86.9% (159 out of 183), a very low false detection rate of 1.4 per day, and a mean detection latency of 13.1 s from electrographic seizure onsets, while in average preceding clinical onsets by 6.3 s. These high performance results, specifically the short detection latency, coupled with the very low computational cost of the proposed method make it adequate for using in implantable closed-loop seizure suppression systems.

This paper presents a novel three-stage blood vessel segmentation algorithm using fundus photographs. In the first stage, the green plane of a fundus image is preprocessed to extract a binary image after high-pass filtering, and another binary image from the morphologically reconstructed enhanced image for the vessel regions. Next, the regions common to both the binary images are extracted as the major vessels. In the second stage, all remaining pixels in the two binary images are classified using a Gaussian mixture model (GMM) classifier using a set of eight features that are extracted based on pixel neighborhood and first and second-order gradient images. In the third postprocessing stage, the major portions of the blood vessels are combined with the classified vessel pixels. The proposed algorithm is less dependent on training data, requires less segmentation time and achieves consistent vessel segmentation accuracy on normal images as well as images with pathology when compared to existing supervised segmentation methods. The proposed algorithm achieves a vessel segmentation accuracy of 95.2%, 95.15%, and 95.3% in an average of 3.1, 6.7, and 11.7 s on three public datasets DRIVE, STARE, and CHASE_DB1, respectively.

This paper presents a novel approach to design obfuscated circuits for digital signal processing (DSP) applications using high-level transformations, a key-based obfuscating finite-state machine (FSM), and a reconfigurator. The goal is to design DSP circuits that are harder to reverse engineer. High-level transformations of iterative data-flow graphs have been exploited for area-speed-power tradeoffs. This is the first attempt to develop a design flow to apply high-level transformations that not only meet these tradeoffs but also simultaneously obfuscate the architectures both structurally and functionally. Several modes of operations are introduced for obfuscation where the outputs are meaningful from a signal processing point of view, but are functionally incorrect. Examples of such modes include a third-order digital filter that can also implement a sixth-order or ninth-order filter in a time-multiplexed manner. The latter two modes are meaningful but represent functionally incorrect modes. Multiple meaningful modes can be exploited to reconfigure the filter order for different applications. Other modes may correspond to nonmeaningful modes. A correct key input to an FSM activates a reconfigurator. The configure data controls various modes of the circuit operation. Functional obfuscation is accomplished by requiring use of the correct initialization key, and configure data. Wrong initialization key fails to enable the reconfigurator, and a wrong configure data activates either a meaningful but nonfunctional or nonmeaningful mode. Probability of activating the correct mode is significantly reduced leading to an obfuscated DSP circuit. Structural obfuscation is also achieved by the proposed methodology via high-level transformations. Experimental results show that the overhead of the proposed methodology is small, while a strong obfuscation is attained. For example, the area overhead for a (31)th-order IIR filter benchmark is only 17.7% with a 128-bit configuration key, where 1 ≤ l ≤ 8, i.e., the order of this filter should be a multiple of 3, and can vary from 3 to 24.

Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from (3n-2) to (2n-2) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2Kbits simultaneously. This general approach, referred as 2K-bit reformulated SCL (2Kb-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2K-2-2 cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively.

Ubiquitous access to computers, cell phones, internet, personal digital devices, cameras and TV can be attributed to advances in the very large scale integration (VLSI) technology and the advances in circuit design to operate circuits at Gigahertz rates. One of the mysteries that we have not been able to unravel is the understanding of how the brain works from different perspectives. Reverse engineering the brain has been identified as one of the grand challenge problems by the National Academies. Advances in sensor technologies and imaging modalities such as electroencephalogram (EEG), intra-cranial electroencephalogram (iEEG), magnetoencephalogram (MEG), and magnetic resonance imaging (MRI) allow us to collect data from hundreds of electrodes from the brain at sample rates ranging from 256 Hz to 15kHz. These data can be key to not only understanding brain functioning and brain connectivity at macro and micro levels in healthy subjects but also in identifying patients with neurological and mental disorder. Extracting the appropriate biomarkers using spectral-temporal-spatial signal processing approaches and classifying states using machine learning approaches can assist clinicians in predicting and detecting seizures in epileptic patients, and in identifying patients with mental disorder such as schizophrenia, depression and personality disorder. The biomarkers can be tracked to design personalized therapy and effectiveness of therapy by closed loop drug delivery or closed loop neuromodulation, i.e., brain stimulation either by invasive or non-invasive means using electrical or magnetic stimulation. High-performance VLSI system design is critical to not-only increasing battery life of VLSI chips for neuromodulation but also for reducing computation time by orders of magnitude in analyzing MRI signals. Another grand challenge problem identified by the National Academies is Advanced Health Informatics. Analysis of health data is key to monitoring biomarkers and delivering drugs as needed. VLSI system design of biomarkers and disease state classification is again critical in improving the health and quality of life of human beings.

This paper presents a novel approach to protect digital signal processing (DSP) circuits through obfuscation by using high-level transformations. The goal is to design DSP circuits that are harder to reverse engineer. High-level transformations of iterative data-flow graphs have been exploited for area-speed-power tradeoffs. This is the first attempt to develop a design flow to apply high-level transformations that not only meet these tradeoffs but also simultaneously obfuscate the architectures both structurally and functionally. Several modes of operations are introduced for obfuscation where the outputs are either meaningful from a signal processing point of view, but functionally incorrect, or non-meaningful. Experimental results show that the proposed methodology only introduces relatively small overhead, while a high level of obfuscation is achieved. For instance, the area overhead for a (3l)th-order IIR filter benchmark is only 17.7% with a 128-bit configuration key.

This paper addresses implementation of IIR digital filters using stochastic computing. Stochastic computing requires fewer logic gates and is inherently fault-tolerant. Thus, these structures are well suited for deep sub-micron technologies. While it is easy to realize FIR digital filters using stochastic computing, implementation of IIR digital filters is non-trivial. Stochastic logic assumes independence of input signals; however, the feedback in IIR digital filters leads to correlation of input signals and the independence assumption is violated. The novelty of this paper lies in demonstrating that, despite the feedback in IIR filters, these filters can be implemented using stochastic logic. The key to stochastic implementation is selection of an IIR filter structure where the states are orthogonal and are, therefore, uncorrelated. Two architectures are presented for stochastic IIR digital filter. Both architectures are based on the lattice filter representation where the states are orthogonal. The first is based on a state-space description of the IIR filter derived from the lattice filter structure. The second is based on transforming the lattice IIR digital filter into an equivalent form that can exploit the novel scaling approach developed in our prior work for inner product computations. Our experimental results show that the two proposed architectures for stochastic IIR digital filters can lead to one to two orders of magnitude reduction in the output error-to-signal power ratio, compared to stochastic implementations using direct-form IIR filters. Furthermore, for higher-order filters, while stochastic direct-form structures fail to function correctly, the state-space and lattice based stochastic IIR digital filters always filter the input signals in a functionally correct manner.

Capacity-achieving polar codes have received significant attention in past few years. These codes can be decoded using either the successive-cancellation (SC) approach or the belief propagation (BP) approach. Several VLSI architectures of SC polar decoders have been reported in the literature. However, SC decoders suffer from long latency and low throughput due to their sequential decoding nature. On the other hand, although the BP decoders can be operated in an inherently parallel manner with high throughput, the functional units in these decoders are underutilized. In this paper, we exploit various architecture transformation techniques to further improve hardware performance of polar BP decoders. First, we propose an overlapped-scheduling approach at iteration level to reduce the overall decoding latency. Second, we propose codeword-level overlap to further improve hardware utilization efficiency. Third, we show that the above two overlapping approaches can be unified into a general framework into a joint overlapping approach. Fourth, we exploit the folding technique to design low-complexity polar BP decoders, and present two types of folded architectures. Synthesis results show that the proposed two (1024, 512) polar BP decoder designs can achieve 1.50 and 2.43 times reduction in hardware complexity, respectively. In addition, the proposed two designs can also achieve 7.4 and 2.5 times improvement in hardware efficiency, respectively.

Polar codes are among the most promising error correction codes due to their ability to achieve the symmetric capacities of the binary-input discrete memoryless channels (B-DMCs). However, how to design successive cancellation (SC) decoders which can maximize the hardware utilization efficiency is still challenging due to the inherent serial nature of SC decoding algorithm. To this end, in this paper, formal design approaches for designing both the time-constrained and resource-constrained interleaved SC decoders are proposed. Compared with the state-of-the-art design, the proposed interleaved decoders can achieve more than 50% reduction in term of area-time product.

Physical unclonable functions (PUFs) can store secret keys in integrated circuits (ICs) by exploiting the uncontrollable randomness due to manufacturing process variations. These PUFs can be used for authentication of devices and for key generation in security applications. This paper presents a rigorous statistical analysis of various types of multiplexer-based (MUX-based) PUFs including the original MUX PUF, the feed-forward MUX PUFs, the modified feed-forward MUX PUFs, and multiplexer-demultiplexer (MUX/DeMUX) PUF. The modified feed-forward MUX PUF structure is a new structure that is introduced in this paper. Three types of feed-forward PUFs are analyzed in this paper. These include feed-forward overlap, feed-forward cascade and feed-forward separate. The performance analysis quantifies interchip and intrachip variations as a function of the number of stages, the process variation variance, the environmental noise variance, and the arbiter skew for different PUFs. Three other metrics of performance are also introduced and analyzed in this paper, which include reliability, uniqueness, and randomness. A PUF is more reliable if it has less intrachip variation. A PUF is more unique if the interchip variation is closer to 50%. A PUF is more random if its response bit is 0 or 1 with equal probability. Our statistical analysis shows that the intrachip variation is less dependent on the number of stages, N, if N is greater than ten. However, the interchip variation is dependent on N if N is less than 100. It is shown that the feed-forward PUFs have higher intrachip variation than MUX PUFs; however, the modified feed-forward PUFs have significantly lower intrachip variation than the feed-forward PUFs. It is shown that the modified feed-forward cascade MUX PUF has the best uniqueness and randomness, while the original MUX PUF has the best reliability. The analysis presented in this paper can be used by the designer to choose an appropriate PUF based on the application's requirement. This eliminates the need for fabrication and testing of many PUFs for selecting an appropriate PUF.

This paper presents a computer-aided screening system (DREAM) that analyzes fundus images with varying illumination and fields of view, and generates a severity grade for diabetic retinopathy (DR) using machine learning. Classifiers such as the Gaussian Mixture model (GMM), k-nearest neighbor (kNN), support vector machine (SVM), and AdaBoost are analyzed for classifying retinopathy lesions from nonlesions. GMM and kNN classifiers are found to be the best classifiers for bright and red lesion classification, respectively. A main contribution of this paper is the reduction in the number of features used for lesion classification by feature ranking using Adaboost where 30 top features are selected out of 78. A novel two-step hierarchical classification approach is proposed where the nonlesions or false positives are rejected in the first step. In the second step, the bright lesions are classified as hard exudates and cotton wool spots, and the red lesions are classified as hemorrhages and micro-aneurysms. This lesion classification problem deals with unbalanced datasets and SVM or combination classifiers derived from SVM using the Dempster-Shafer theory are found to incur more classification error than the GMM and kNN classifiers due to the data imbalance. The DR severity grading system is tested on 1200 images from the publicly available MESSIDOR dataset. The DREAM system achieves 100% sensitivity, 53.16% specificity, and 0.904 AUC, compared to the best reported 96% sensitivity, 51% specificity, and 0.875 AUC, for classifying images as with or without DR. The feature reduction further reduces the average computation time for DR severity per image from 59.54 to 3.46 s.

Stochastic computing has recently gained attention due to its fault-tolerance property. In stochastic computing, numbers are represented by probabilities of sequences. This paper addresses implementation of inner products and digital filters using stochastic logic. Straightforward implementations of stochastic inner products and digital filters lead to significantly large output error. To overcome this, this paper proposes a novel scaling method for efficient stochastic logic implementations of inner products and digital filters. By incorporating the filter coefficients into the probability of the selection signals of the multiplexors, the proposed weighted summation circuit can achieve better signal scaling with lower cost than the one derived from a traditional structure. This paper also presents how to vary the seeds in stochastic filters in order to reduce the correlation. Implementing IIR filters using stochastic logic limits possible pole locations. To overcome this, a new stochastic IIR filter structure is presented that includes a binary multiplier and stochastic-to-binary and binary-to-stochastic converters. Our experimental results show that the proposed architecture for the inner-product unit can lead to more than 12 times reduction in the error-to-power ratio. The stochastic FIR filters can perform the desired filtering function, but their accuracy degrades with the increase of filter order. The direct-form stochastic IIR filters may fail for large filter orders, but their performance can be improved by using cascade-form filter architecture.

Polar codes have emerged as important channel codes because of their capacity-achieving property. For low-complexity polar decoding, hardware architectures for successive cancellation (SC) algorithm have been investigated in prior works. However, belief propagation (BP)-based architectures have not been explored in detail. This paper begins with a review of min-sum (MS) approximated BP algorithm, and then proposes a scaled MS (SMS) algorithm with improved decoding performance. Then, in order to solve long critical path problem in the SMS algorithm, we propose an efficient critical path reduction approach. Due to its generality, this optimization method can be applied to both of SMS and MS algorithms. Compared with the state-of-the-art MS decoder, the proposed (1024, 512) SMS design can lead to 0.5dB extra decoding gain with the same hardware performance. Besides, the proposed optimized MS architecture can also achieve more than 30% and 80% increase in throughput and hardware efficiency, respectively.

This paper presents a methodology for implementing digital logic with molecular reactions based on a bistable mechanism for representing bits. The value of a bit is not determined by the concentration of a single molecular type; rather, it is the comparison of the concentrations of two complementary types that determines if the bit is “0” or “1”. This mechanism is robust: any small perturbation or leakage in the concentrations quickly gets cleared out and the signal value is not affected. Based on this representation for bits, a constituent set of logical components are implemented. These include combinational components - AND, OR, NOR, and XOR - as well as sequential components - D latches and D flip-flops. Using these components, three full-fledged design examples are given: a square-root unit, a binary adder and a linear feedback shift register. DNA-based computation via strand displacement is the target experimental chassis. The designs are validated through simulations of the chemical kinetics. The simulations show that the molecular systems compute digital functions accurately and robustly.

The author has presented a multiplexer-based carry-select modified tree (CSMT) adder design. It was correctly pointed out in Section VI that these multiplexer-based adders are not just limited to redundant-to-binary-conversion-based adders, but can also be used in the context of carry-save binary adders.

This paper presents a novel approach to design four and eight parallel pipelined fast Fourier transform (FFT) architectures using folding transformation. The approach is based on use of decimation in time algorithms which reduce the number of delay elements by 33% compared to the decimation in frequency based designs. The number of delay elements required for an N-point FFT architecture is N - 4 which is comparable to that of delay feedback schemes. The number of complex adders required is only 50% of those in the delay feedback designs. The proposed approach can be extended to any radix-2n based FFT algorithms. The proposed architectures are feed-forward designs and can be pipelined by more stages to increase the throughput. Further, a novel four parallel 128-point FFT architecture is derived using the proposed approach. It is shown that a radix-24 4-parallel 128-point design requires 124 delay elements, 28 complex adders, and four full complex multipliers.

In this paper we propose two efficient low-area, low-power folded VLSI architectures for linear prediction error filter. One of them is based on the split-Levinson-Durbin and requires half computational complexity of an architecture based on the Levinson-Durbin algorithm. The other one is based on the Schur algorithm. Using folding method, the number of multipliers and adders is minimized. In addition, by modifications in data scheduling, the number of required multiplexers are also decreased. Comparison with previous architectures demonstrates the efficiency of the proposed architectures with respect to hardware and computational complexity.

Polar codes have become one of the most favorable capacity achieving error correction codes (ECC) along with their simple encoding method. However, among the very few prior successive cancellation (SC) polar decoder designs, the required long code length makes the decoding latency high. In this paper, conventional decoding algorithm is transformed with look-ahead techniques. This reduces the decoding latency by 50%. With pipelining and parallel processing schemes, a parallel SC polar decoder is proposed. Sub-structure sharing approach is employed to design the merged processing element (PE). Moreover, inspired by the real FFT architecture, this paper presents a novel input generating circuit (ICG) block that can generate additional input signals for merged PEs on-the-fly. Gate-level analysis has demonstrated that the proposed design shows advantages of 50% decoding latency and twice throughput over the conventional one with similar hardware cost.

This paper presents a novel approach to develop parallel pipelined architectures for the fast Fourier transform (FFT). A formal procedure for designing FFT architectures using folding transformation and register minimization techniques is proposed. Novel parallel-pipelined architectures for the computation of complex and real valued fast Fourier transform are derived. For complex valued Fourier transform (CFFT), the proposed architecture takes advantage of under utilized hardware in the serial architecture to derive$L$-parallel architectures without increasing the hardware complexity by a factor of$L$. The operating frequency of the proposed architecture can be decreased which in turn reduces the power consumption. Further, this paper presents new parallel-pipelined architectures for the computation of real-valued fast Fourier transform (RFFT). The proposed architectures exploit redundancy in the computation of FFT samples to reduce the hardware complexity. A comparison is drawn between the proposed designs and the previous architectures. The power consumption can be reduced up to 37% and 50% in 2-parallel CFFT and RFFT architectures, respectively. The output samples are obtained in a scrambled order in the proposed architectures. Circuits to reorder these scrambled output sequences to a desired order are presented.

Just as electronic systems implement computation in terms of voltage (energy per unit charge), molecular systems compute in terms of chemical concentrations (molecules per unit volume). Prior work has established mechanisms for implementing logical and arithmetic functions including addition, multiplication, exponentiation, and logarithms with molecular reactions. In this paper, we present a general methodology for implementing synchronous sequential computation. We generate a four-phase clock signal through robust, sustained chemical oscillations. We implement memory elements by transferring concentrations between molecular types in alternating phases of the clock. We illustrate our design methodology with examples: a binary counter as well as a four-point, two-parallel FFT. We validate our designs through ODE simulations of mass-action chemical kinetics. We are exploring DNA-based computation via strand displacement as a possible experimental chassis.

A patient-specific seizure prediction algorithm is proposed using a classifier to differentiate preictal from interictal ECoG signals. Spectral power of ECoG processed in four different fashions are used as features: raw, time-differential, space-differential, and time/space-differential ECoG. The features are classified using cost-sensitive support vector machines by the double cross-validation methodology. The proposed algorithm has been applied to ECoG recordings of 18 patients in the Freiburg EEG database, totaling 80 seizures and 437-hour-long interictal recordings. Classification with the feature obtained from time/space-differential ECoG demonstrates performance of 86.25% sensitivity and 0.1281 false positives per hour in out-of-sample testing.

Most of the state-of-the-art voice biometrics systems use the natural speech signal (either read speech or spontaneous or contextual speech) from the subjects. In this paper, an attempt is made to identify speakers from their hum. A new feature set, viz., Variable length Teager Energy Based Mel Frequency Cepstral Coefficients (VTMFCC) is proposed for this problem. Experiments have been carried out for person identification and verification task using Linear Prediction Cepstral Coefficients (LPCC) and Mel Frequency Cepstral Coefficients (MFCC) with polynomial classifier of 2ndorder approximation. It is shown that the speaker identification rate for proposed feature set outperforms LPCC by 13.6% and is competitive over baseline MFCC. For speaker verification, a reduction in equal error rate (EER) by 1.73% is achieved when a score-level fusion system is employed by combining evidence from MFCC and VTMFCC.

In this paper, a novel method is developed to solve the problem of underdetermined blind source separation, where the number of mixtures is smaller than that of sources. Generalized Gaussian Distributions (GGDs) are used to model the source signals and generative Continuous Density Hidden Markov Models (CDHMMs) are derived to track the nonstationarity inside the source signals. Each source signal can switch between several states such that the separation performance can be significantly improved. The model parameters are trained through the Expectation Maximization (EM) algorithm and the source signals are estimated via the Maximum a Posteriori (MAP) approach. Compared with the results of L1-norm solution, our proposed algorithm has obtained much better output signal-to-noise ratio (SNR) and the separation results are more realistic.

We present a methodology for implementing digital signal processing (DSP) operations such as filtering with biomolecular reactions. From a DSP specification, we demonstrate how to synthesize biomolecular reactions that produce time-varying output quantities of molecules as a function of time-varying input quantities. Unlike all previous schemes for biomolecular computation, ours produces designs that are dependent only on coarse rate categories for the reactions (“fast” and “slow”). Given such categories, the computation is exact and independent of the specific reaction rates. We implement DSP operations through a self-timed “handshaking” protocol that transfers quantities between molecular types based on the absence of other types. We illustrate our methodology with the design of a simple moving-average filter as well as a more complex biquad filter. We validate our designs through transient stochastic simulations of the chemical kinetics. Although conceptual for the time being, the proposed methodology has potential applications in domains of synthetic biology such as biochemical sensing and drug delivery. We are exploring DNA-based computation via strand displacement as a possible experimental chassis.

It has been recently demonstrated that digital signal processing systems may possibly leverage unconventional voltage overscaling (VOS) to reduce energy consumption while maintaining satisfactory signal processing performance. Due to the computation-intensive nature of most signal processing algorithms, the energy saving potential largely depends on the behavior of computer arithmetic units in response to overscaled supply voltage. This paper shows that different hardware implementations of the same computer arithmetic function may respond to VOS very differently and result in different energy saving potentials. Therefore, the selection of appropriate computer arithmetic architecture is an important issue in voltage-overscaled signal processing system design. This paper presents an analytical method to estimate the statistics of computer arithmetic computation errors due to supply voltage overscaling. Compared with computation-intensive circuit simulations, this analytical approach can be several orders of magnitude faster and can achieve a reasonable accuracy. This approach can be used to choose the appropriate computer arithmetic architecture in voltage-overscaled signal processing systems. Finally, we carry out case studies on a coordinate rotation digital computer processor and a finite-impulse-response filter to further demonstrate the importance of choosing proper computer arithmetic implementations.

In this paper, we propose an efficient low-complexity switch network design for reconfigurable low-density parity-check (LDPC) decoders. The proposed architecture leads to significant reductions in hardware complexity. Since the structured quasi-cyclic (QC) LDPC codes for most modern wireless communication systems include multiple code rates, various block lengths, and different sizes of submatrices, a reconfigurable LDPC decoder is desirable and the barrel shifter needs to be programmable. The Benes network cannot be optimized as the barrel shifter for a reconfigurable LDPC decoder when the input size of barrel shifter is not a power of 2. Also, it is not trivial to generate all the control signals on-the-fly for numerous 2 × 2 switches in the switch network. In this paper, a novel low-complexity switch network design is proposed, which can be used efficiently when the input size of barrel shifters is not a power of 2. Furthermore, we propose a novel algorithm to generate all the control signals, which can be implemented with a small size of lookup table (LUT) or a simple combination logic on-the-fly, using the properties that both the full-size switch network can be broken into two half-size switch networks and the barrel shifters for the structured QC LDPC decoders require only cyclic shifts. Compared with conventional Benes networks using a dedicated LUT or a complicated signal generating algorithm, the proposed architectures achieve significant hardware reductions in implementing the barrel shifters for reconfigurable LDPC decoders. In synthesis result using the TSMC 0.18-¿m standard cell CMOS technology, the proposed switch network for a reconfigurable LDPC decoder of IEEE 802.16e and IEEE 802.11n can be implemented with an area of 0.772 mm2, which leads to a significant area reduction.

Supply voltage overscaling has been studied recently for the design of low power finite impulse response (FIR) filters, where the supply voltage is deliberately scaled beyond the critical voltage so as to lower the power consumption quadratically. The violation of timing constraint leads to computational errors/noise, which is then reduced via prediction-based algorithms. In this paper, we first propose an estimation-based algorithm aiming at accuracy maximization. Then, practical design issues are addressed and the major problem that causes performance drop is identified, which leads to a novel flexible two-phase bilateral estimation-based noise reduction architecture with the use of error-delay detection mechanism that enables the flexible size estimator. Compared to conventional designs, simulation results show that the estimation-based algorithm and the two-phase bilateral estimation algorithm improve the noise reduction performance by 10-20 dB and 17-22 dB while achieving the same power saving ratio, respectively. Alternatively, the proposed algorithms can achieve lower power while a certain performance requirement is satisfied.

Supply voltage overscaling (VOS) has been studied recently for the design of low power finite impulse response (FIR) filters, where estimation-based noise reduction schemes are used for reducing the computational noise. When broadband filters are concerned, which are widely used in the scenario of high speed communication such as frequency-division multiplexed (FDM) systems, existing noise reduction schemes fail due to the relatively low dependency among broadband filter output samples. In this paper, a novel noise reduction scheme is proposed for broadband filters, which is the first implementation-independent scheme that can effectively reduce the noise due to both voltage overscaling and environmental fluctuations. Simulation results show that the proposed scheme achieves 7-27 dB performance gain while achieving 10.33%-51.74% power saving.

Byte substitution (S-Box), which is essentially a combination of inversion and affine operations over a finite field GF(28), limits the throughput of the Advanced Encryption Standard (AES) algorithm. Among existing S-Box architectures, the composite field S-Box algorithm is very attractive for its extremely low area cost, which is only 12%-20% of other implementation approaches [1]. However, the composite field S-Box suffers from extremely low throughput rate. In this paper, we propose a novel fast composite field S-Box architecture. By applying pre-computation techniques, some computation on the critical data path can be eliminated so as to reduce the critical path delay. The complexity of the precomputation units is minimized via sharing common structures. The proposed design is implemented using a 0.18-um CMOS technology library. The results show that the throughput rate is increased by 28.22% at the expense of a fairly modest increase in area. Based on the proposed design, we then present an approach to further reduce critical path delay. The gate-level analysis shows that the second proposed approach can increase the throughput rate by 56.25%. In addition, the proposed designs can reduce the pipelining latency by 40%-60% compared with the conventional design while keeping the same throughput rate.

In this paper, we propose a novel min-sum (MS) decoder architecture using nonuniform quantization schemes for low-density parity-check (LDPC) codes. The finite word-length analysis in implementing an LDPC decoder is a very important factor since it directly impacts the size of memory to store the intrinsic and extrinsic messages and the overall hardware area in the partially parallel LDPC decoder. The proposed nonuniform quantization scheme can reduce the finite word-length while achieving similar performances compared to a conventional quantization scheme. From simulation results, it is shown that the proposed 4-bits nonuniform quantization scheme achieves an acceptable decoding performance unlike a conventional 4-bits uniform quantization scheme. In addition, the hardware implementation for the proposed nonuniform quantization scheme requires smaller area.

In this paper, we propose an efficient controller design of barrel shifter for reconfigurable low-density parity-check (LDPC) decoders, which leads to significant reduction in hardware complexity. Since the structured LDPC codes for the most modern wireless communication systems include multiple code rates, various block lengths, and different sizes of submatrices, a reconfigurable LDPC decoder is desirable and the barrel shifter needs to be programmable. Even though the Benes network can be optimized for the barrel shifting networks of reconfigurable LDPC decoder, it is not trivial to generate all the control signals for numerous 2times2 switches on-the-fly. A novel simplified algorithm capable of generating all the control signals is proposed using the properties that both the full-size Benes network can be broken into two half-size Benes networks and the barrel shifters needed in the structured LDPC decoders require only cyclic shifts. The proposed algorithm can be easily implemented with a small numbers of gates. Compared with the direct implementation using a dedicated look-up table, the proposed algorithm achieves a significant hardware reduction in implementing a reconfigurable LDPC decoder.

This paper presents an efficient method for computing the optimal tap coefficients of the MIMO equalizers and cancellers from the channel impulse responses (CIR). The proposed method provides an insight of the minimum mean-square error (MMSE) solution in a general MIMO system and shows that the MSE optimization problem in a M-input N-output system can be decomposed into N independent minimization problems each with smaller size. Solving each separate problem in MMSE sense is computationally efficient, thus leading to substantial savings in overall computational complexity. Compared with a prior method, this new method is exact and much faster.

In this paper, the authors propose an efficient highly-parallel decoder architecture using partially overlapped decoding scheme for quasi-cyclic (QC) low-density parity-check (LDPC) codes, which leads to reduction in hardware complexity and power consumption. Generally, due to the regularly structured parity-check matrix H of QC LDPC codes, the message updating computations in the check node unit (CNU) and the variable node unit (VNU) can be efficiently overlapped, which increases the decoding throughput by maximizing the hardware utilization efficiency (HUE). However, the partially overlapped decoding scheme cannot be used to design a highly-parallel decoding architecture for high-throughput applications. For (3, 5)-regular QC LDPC codes, our proposed method could reduce the hardware complexity by approximately 33% for the CNU and 20% for the VNU in the highly-parallel decoder architecture without any performance degradation. In addition, the power consumption can be minimized by reducing the total number of memory accesses for updated messages.

This paper analyzes the performance of quantized min-sum decoding algorithms for irregular low-density parity-check (LDPC) codes. For regular LDPC codes, it is known that the normalized or offset min-sum decoding algorithm with quantization bits less than 6 bits achieves good performances over wide range of signal-to-noise ratios (SNR). However, finite precision effects in decoding irregular LDPC codes are different from that in decoding regular LDPC codes which is caused by the difference of convergence speeds between low degree nodes and high degree nodes. This paper proposes a novel method to improve the performance of the conventional normalized or offset min-sum decoding algorithm when it is approximated with finite precision for hardware implementations. The proposed method applies down-scaling factors to intrinsic information which has effects on increasing the reliability of extrinsic information at variable nodes and compensating the quantization errors caused by finite precision. Computer simulation results for irregular LDPC codes show that the proposed normalized and offset min-sum decoding algorithms achieve better performances at high SNR compared to the conventional normalized and offset min-sum algorithms under (6:2) quantization scheme.

Sphere decoding has been used for maximum likelihood (ML) detection of multiple-input-multiple-output (MIMO) communication systems. In order to combine the sphere decoder with the outer channel code decoder, researchers have proposed to include a candidate list in the sphere decoder to provide soft information to the channel code decoder. This algorithm is called list sphere decoder (LSD). With LSD, it takes many cycles to decode a vector. In this paper, the architecture of applying parallel processing technique in LSD is presented, with detailed discussions on the individual building blocks.

This paper proposes a novel parallel approach for pipelining of nested multiplexer loops to design high speed decision feedback equalizers (DFEs) based on look-ahead techniques. It is well known that the DFE is an efficient scheme to suppress intersymbol interference (ISI) in various communication and magnetic recording systems. However, the feedback loop within a DFE limits an upper bound of the achievable high speed in hardware implementation. A straightforward parallel implementation requires more hardware complexity. The novel proposed technique offers significant reduction of hardware complexity of 56% and 80% over the conventional parallel six-tap DFE architectures for 10 Gbps and 20 Gbps throughput, respectively.

Traditionally equalization is performed individually for 10GBASE-T, and FEXT is treated as noise to be cancelled at the receiver. However, FEXT contains information about the symbols transmitted from remote transmitters and it can be viewed as a signal rather than noise to facilitate signal recovery. This paper proposes to use MIMO (multi-input multi output) equalization technique to deal with FEXT in 10GBASE-T. In the proposed MIMO technique, FEXT is treated as signal, which improves SNR. Instead of using long FEXT cancellers, MIMO-DFE with short length is used to remove post-cursor ISI. Our simulation results show that, by using the proposed MIMO equalization, we are able to achieve SNR (signal to noise ratio) improvement around 0.5-9 dB with 13% less complexity than the traditional equalization technique in twisted-pair channel environment

Since finding the nearest point in a lattice for multi-input multi-output (MIMO) channels is NP-hard, simplified algorithms such as sphere decoder (SD) have been proposed. List sphere decoder (LSD), which is a modified version of SD, allows soft information to be extracted for channel decoding and iterative detection/decoding. In this paper, recently proposed efficient methods for reducing the computational complexity of SD and LSD with depth-first tree searching are summarized. Numerous simulations have been carried out and comparison has been made based on the average number of processing cycles. We also present two efficient schemes which can decrease hardware complexity without significant performance degradation, restricted list updating in LSD and restricted node storing at each tree level.

A probabilistic list sphere decoding (LSD) is proposed for LDPC-coded MIMO-OFDM systems. By confining the search to channel-adaptively chosen promising candidate groups, our proposed probabilistic LSD evaluates the more promising candidates earlier in the search, while retaining efficient implementation of the depth-first LSD. Simulation results show that, the proposed LSD significantly improves the error performance for constrained throughput, or increases the throughput for a fixed bit error rate. The proposed LSD can be implemented by simply adding special hardware blocks that perform preprocessing and control the tree traversal. The K-best search algorithm enables efficient implementation of the preprocessing.

This paper presents a systematic study of early stopping criteria for Turbo decoding. First, statistical analysis is carried out on numerous hard/ soft variables that may be used in an early stopping criterion. Desirable variables are suggested based on their statistical properties. Simulation results show that any stopping criteria based on a single variable will have BER/FER performance loss. Two criteria, each of which uses two variables, are recommended in this paper and neither of them will result in any performance loss. It is also shown in this paper that the thresholds for these variables should be set to be proportional to the logarithm of the block size instead of being proportional to the block size.

In this paper a novel pre-computation technique for scalar point multiplication on elliptic curves is proposed. Compared to standard affine coordinates without pre-computation this method achieves a performance increase of 23% while requiring an additional increase in control and logic for the pre-computation step. This method achieves a (2m bits times numpoints) reduction in storage overhead compared with other pre-computation techniques

Although current turbo equalization/decoding algorithms provide superior performance, their implementation complexity is significantly high. Iterative methods make the decoding process even slower. No simple turbo equalization method exists which can work with block turbo decoding. Therefore, this paper proposes a new block turbo equalization algorithm and its corresponding VLSI architecture which requires a very low complexity

The paper focuses on the design of a new dual field divider that can achieve performance of 1/m throughput. This dual field division unit can operate at 118 MHz with a latency of 7m-2 cycles and has an area requirement 15 XOR2, 40 AND2, 29 MUX2, and 7 INV gates per processing element with a total of 2m processing elements. It is intended to be used in an elliptic curve crypto-accelerator for GF(2/sup m/) and GF(p). The actual performance for scalar point multiplication in GF(2/sup 571/) running at 100 MHz would be 20.4 kP/s. The actual performance for scalar point multiplication in GF(p) with |p| = 521 running at 100 MHz would be 24.4 kP/s.

One of the powerful, yet simple, algorithms to decode trellis codes as well as to combat intersymbol interference (ISI) is the parallel decision feedback decoding algorithm. However, for high-speed applications, such as gigabit Ethernet over copper, the implementation and design of a parallel decision feedback decoder (PDFD) is challenging due to the long critical path in the decoder structure. Straightforward pipelined designs usually introduce significant hardware overhead. To solve these problems, first, based on an optimized scheduling of the computations in the parallel decision feedback decoding algorithm, a low complexity pipelined PDFD is proposed. Next, we present a retiming and reformulation technique for the decision feedback unit (DFU) in the PDFD which can remove the DFU from the critical path of the PDFD with negligible hardware overhead. Compared with similar designs in the literature, the proposed design can reduce hardware overhead by 60% while achieving similar speedup for gigabit Ethernet systems.

Ultra-wideband (UWB) communication systems have attracted both academic research and commercial interests due to their potential high throughput and precise ranging capability. Convolutional codes are widely used in different proposals for high-speed UWB communication systems. In this paper, a novel Viterbi decoder architecture is studied for the multiband orthogonal frequency division multiplexing (MB-OFDM) UWB system. In the Viterbi decoder, sliding block, 2-step lookahead and 2 parallel techniques are combined to achieve the highest desired data rate. For lower data rates, it is possible to disable some parts of the decoder for power saving by proper analysis of the effects of puncturing on word length and trace back length. At the same time, in the add-compare-select (ACS) unit, a pipelined most-significant bit (MSB) first ACS unit is also utilized to shorten the length of the critical path.

This paper presents novel approaches for pipelining of parallel nested multiplexer loops and decision feedback equalizers (DFEs) based on look-ahead techniques. Look-ahead techniques can be applied to pipeline a nested multiplexer loop in many possible ways. It is shown that not all the look-ahead approaches necessarily result in improved performance. A novel look-ahead approach is identified, which can guarantee improvement in performance either in the form of pipelining or parallelism. The proposed technique is demonstrated and applied to design multiplexer-loop-based DFEs with throughput in the range of 3.125-10 Gb/s.

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

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

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

Long BCH codes achieve additional coding gain of around 0.6 dB compared to Reed-Solomon codes with similar code rate used for long-haul optical communication systems. For our considered parallel decoder architecture, a novel group matching scheme is proposed to reduce the overall hardware complexity of both Chien search and syndrome generator units by 46% for BCH(2047, 1926, 23) code as opposed to only 22% if directly applying the iterative matching algorithm. The proposed scheme exploits the substructure sharing within a finite field multiplier (FFM) and among groups of FFMs.

It is highly likely that 10 Gigabit Ethernet over copper (10GBASE-T) transceivers will use a 10-level pulse amplitude modulation (PAM 10) as well as a 4D trellis code as in 1000BASE-T. The traditional trellis coded modulation scheme, as in 1000BASE-T, leads to a design where the corresponding decoder with a long critical path needs to operate at 833 MHz. It is difficult to meet the critical path requirements of such a decoder. To solve the problem, two interleaved trellis coded modulation schemes are proposed. The inherent decoding speed requirements are relaxed by factors of 4 and 2, respectively. Parallel decoding of the interleaved codes requires multiple decoders. To reduce the hardware overhead, time-multiplexed or folded decoder structures are proposed where only one decoder is needed and each delay in the decoder is replaced with four delays for scheme 1 and two delays for scheme 2, respectively. These delays can be used to reduce the critical path. Compared with the conventional decoder, the folded decoders for the two proposed schemes can achieve speedups of 4 and 2, respectively. Simulation results show that the error-rate performances of the two schemes are quite close to that of the conventional scheme.

The high speed implementation of a DFE (decision feedback equalizer) requires reformulation of the DFE into an array of comparators and a multiplexer loop. The throughput of the DFE is limited by the speed of the multiplexer loop. This paper proposes a novel look-ahead computation approach to pipeline multiplexer loops. The proposed technique is demonstrated and applied to design multiplexer loop based DFEs with throughput in the range of 3.125-10 Gbps.

This paper exploits the similarity between the two stages of belief propagation decoding algorithm for low density parity check codes to derive an area efficient design that re-maps the check node functional units and variable node functional units into the same hardware. Consequently, the novel approach could reduce the logic core size by approximately 21% without any performance degradation. In addition, the proposed approach improves the hardware utilization efficiency as well.

Long BCH codes can achieve about 0.6 dB additional coding gain over Reed-Solomon codes with a similar code rate in long-haul optical communication systems. BCH encoders are conventionally implemented by a linear feedback shift register architecture. Encoders of long BCH codes may suffer from the effect of large fanout, which may reduce the achievable clock speed. The data rate requirement of optical applications require parallel implementations of the BCH encoders. In this paper, a novel scheme based on look-ahead computation and retiming is proposed to eliminate the effect of large fanout in parallel long BCH encoders. For a (2047, 1926) code, compared to the original parallel BCH encoder architecture, the modified architecture can achieve a speedup of 132%.

We study the theory and implementation of pulsed orthogonal frequency division multiplexing (pulsed-OFDM) modulation. Pulsed-OFDM is an enhancement to the leading proposal to the IEEE 802.15.3a wireless personal area networks standardization effort, known as multi-band OFDM. In particular, we show in this paper that the pulsed-OFDM system has better performance than the non-pulsed system in indoor multipath channels and considerably lower complexity and power consumption. We begin by studying the, spectral characteristics of pulsed OFDM and the added degrees of diversity that it provides. Next, we discuss the design of receivers for such a system. We show that the diversity branches can be captured and demodulated by one or more fast Fourier transform (FFT). We then focus on a system for the IEEE 802.15.3a standard and derive a particularly low complexity implementation for that system. The implementation is based on carefully designed punctured convolutional codes. It also exploits the normal inefficiencies in an FFT architecture to implement the parallel FFT operations required to demodulate a full diversity pulsed OFDM with lower complexity and smaller area than the single FFT used by the non-pulsed system. We conclude by presenting realistic simulation results for the measured indoor propagation channels provided by the IEEE 802.15.3a standard.

The sphere decoding (SD) algorithm has been widely recognized as an important algorithm to solve the maximum likelihood detection (MLD) problem, given that symbols can only be selected from a set with a finite alphabet. The complexity of the sphere decoding algorithm is much lower than the directly implemented MLD method, which needs to search through all possible candidates before making a decision. However, in high-dimensional and low signal-to-noise ratio (SNR) cases, the complexity of sphere decoding is still prohibitively high for practical applications. In this paper, a simplified SD algorithm, which combines the K-best algorithm and SD algorithm, is proposed. With carefully selected parameters, the new SD algorithm, called SD-KB algorithm, can achieve very low complexity with acceptable performance degradation compared with the traditional SD algorithm. The low complexity of the new SD-KB algorithm makes it applicable to the simultaneously operating piconets (SOP) problem of the multi-band orthogonal frequency division multiplex (MB-OFDM) scheme for the high- speed wireless personal area network (WPAN). We show in particular that the proposed algorithm provides over 4 dB gain in bit error rate (BER) performance over the baseline MB-OFDM scheme when several piconets interfere with each other. The SD-KB algorithm can provide pseudo-MLD solutions, which have significant performance gain over the baseline method, especially when the signal-to-interference ratio (SIR) is low. The cost of performance improvement is higher complexity. However, the new SD algorithm has predictable computation complexity even in the worst scenario.

In this letter, tradeoffs between very large scale integration implementation complexity and performance of block turbo decoders are explored. We address low-complexity design strategies on choosing the scaling factor of the log extrinsic information and on reducing the number of hard-decision decodings during a Chase search.

Protecting short data frames by turbo coding is a challenging task because of the small interleaver size and the need for transmission efficiency. In this letter, turbo-decoding-metrics aided short cyclic redundancy check codes are applied to novel tailbiting encoded trellis codes with a twofold purpose: to stop the iterative decoding processes to achieve low-power design and to reduce fractional coding-rate loss. Significant coding gains can be achieved by actually increasing the transmission rate with a negligible increase in power consumption. Performance improvement is demonstrated over additive white Gaussian noise channels. The savings is up to 21.4% for the transmission throughput and 21.5% for the energy consumption of the turbo decoder when frame size 49 is used.

This article describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. Given a circuit G and a target clock period c , our algorithm either outputs a retimed version of G satisfying setup and hold constraints or reports that such a solution is not possible, in O (∣V∣ 3 log ∣ V ∣ log (∣ V ∣ C )) steps, where ∣ V ∣ corresponds to number of gates in the circuit and C is equal to the number of registers in the circuit. This is the first polynomial-time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues into consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of long path only retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that problem statement are also demonstrated in simulation for the approach presented here. Finally, a basis is provided for deriving efficient heuristics for addressing both long-path and short-path requirements by combining the techniques of retiming and min-delay padding.

To implement parallel BCH (Bose-Chaudhuri-Hochquenghem) decoders in an area-efficient manner, this paper presents a novel group matching scheme to reduce the Chien search hardware complexity by 60% for BCH(2047, 1926, 23) code as opposed to only 26% if directly applying the iterative matching algorithm. The proposed scheme exploits the substructure sharing within a finite field multiplier (FFM) and among groups of FFMs.

This paper presents an error compensation method for a modified Booth fixed-width multiplier that receives a W-bit input and produces a W-bit product. To efficiently compensate for the quantization error, Booth encoder outputs (not multiplier coefficients) are used for the generation of error compensation bias. The truncated bits are divided into two groups depending upon their effects on the quantization error. Then, different error compensation methods are applied to each group. By simulations, it is shown that quantization error can be reduced up to 50% by the proposed error compensation method compared with the existing method with approximately the same hardware overhead in the bias generation circuit. It is also shown that the proposed method leads to up to 35% reduction in area and power consumption of a multiplier compared with the ideal multiplier.

In this paper, a novel K-nested layered look-ahead method and its corresponding architecture, which combine K-trellis steps into one trellis step (where K is the encoder constraint length), are proposed for implementing low-latency high-throughput rate Viterbi decoders. The proposed method guarantees parallel paths between any two-trellis states in the look-ahead trellises and distributes the add-compare-select (ACS) computations to all trellis layers. It leads to regular and simple architecture for the Viterbi decoding algorithm. The look-ahead ACS computation latency of the proposed method increases logarithmically with respect to the look-ahead step (M) divided by the encoder constraint length (K) as opposed to linearly as in prior work. For a 4-state (i.e., K=3) convolutional code, the decoding latency of the Viterbi decoder using proposed method is reduced by 84%, at the expense of about 22% increase in hardware complexity, compared with conventional M-step look-ahead method with M=48 (where M is also the level of parallelism). The main advantage of our proposed design is that it has the least latency among all known look-ahead Viterbi decoders for a given level of parallelism.

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

In this paper, a systematic approach is proposed to develop high throughput decoder for structured (quasi-cyclic) low density parity check (LDPC) block codes. Based on the properties of quasi-cyclic LDPC codes, the two stages of belief propagation decoding algorithm could be overlapped and thus the overall decoding latency is reduced. To avoid the memory access conflict, the maximum concurrency of the two stages is explored by a novel scheduling algorithm. Consequently, the decoding throughput could be increased by almost twice assuming dual-port memory is available.

When the input and the output clocks are asynchronous, the nearest interpolated value can be used to approximate the desired output sample. The design for asynchronous sample rate conversion (ASRC) from 44.1 kHz compact disk (CD) to 48 kHz digital audio tape (DAT) is presented. Using a wave digital filter and a fractional delay filter, the ASRC is implemented in all-digital form. To this end, the paper proposes a novel IIR fractional delay filter. Compared with other methods, the proposed method requires less hardware complexity and obtains signal-quality compatible with digital audio.

A practical turbo decoder is usually implemented with a serial decoding architecture for low complexity, where the extrinsic information symbols are stored in the so-called interleaver memory for the next decoding. Either a dual-port (or two ping-pong memories) or a single-port memory can be employed for this memory. The first approach achieves twice the throughput as the second one while spending approximately twice the hardware on the interleaver memory. In this work, two novel architectures are proposed for the interleaver memory design. Both proposed architectures work for any type of random interleavers. Compared with the traditional single-port approach, twice the throughput can be obtained with less than 1% area overhead when applied in third generation CDMA systems. On the other hand, more than 25% area of an entire turbo decoder can be saved compared with the traditional dual-port solution.

Two efficient approaches are proposed to improve the performance of soft-output Viterbi (1998) algorithm (SOVA)-based turbo decoders. In the first approach, an easily obtainable variable and a simple mapping function are used to compute a target scaling factor to normalize the extrinsic information output from turbo decoders. An extra coding gain of 0.5 dB can be obtained with additive white Gaussian noise channels. This approach does not introduce extra latency and the hardware overhead is negligible. In the second approach, an adaptive upper bound based on the channel reliability is set for computing the metric difference between competing paths. By combining the two approaches, we show that the new SOVA-based turbo decoders can approach maximum a posteriori probability (MAP)-based turbo decoders within 0.1 dB when the target bit-error rate (BER) is moderately low (e.g., BER<10/sup -4/ for 1/2 rate codes). Following this, practical implementation issues are discussed and finite precision simulation results are provided. An area-efficient parallel decoding architecture is presented in this paper as an effective approach to design high-throughput turbo/SOVA decoders. With the efficient parallel architecture, multiple times throughput of a conventional serial decoder can be obtained by increasing the overall hardware by a small percentage. To resolve the problem of multiple memory accesses per cycle for the efficient parallel architecture, a novel two-level hierarchical interleaver architecture is proposed. Simulation results show that the proposed interleaver architecture performs as well as random interleavers, while requiring much less storage of random patterns.

Recently a novel algorithm transformation was proposed to reduce the critical path of Berlekamp-Massey algorithm implementation for errors-alone Reed-Solomon decoding. In this paper, we apply the same methodology to transform the Berlekamp-Massey algorithm for errors-and-erasures RS decoding. We present a regular hardware architecture to implement the reformulated Berlekamp-Massey algorithm, which can achieve high throughput. Moreover, an operation scheduling scheme is proposed to further reduce the hardware complexity without loss of throughput.

This paper presents a computationally efficient algorithm for the soft decoding of space-time block codes. Compared to the original maximum likelihood algorithm, the proposed algorithm saves up to 80% hardware operations. The simulation results using space-time block turbo coded modulation scheme show that the proposed algorithm achieves the same decoding performance as the maximum likelihood decoding with much lower complexity.

In this paper, a sub-optimal algorithm for decoding BCH (t ≥ 2) turbo codes is presented. High speed VLSI decoder architecture is proposed for codes constructed over extended GF(25). While the algorithm applies to higher order BCH product codes, it is shown that this particular block turbo codes, when decoded using the proposed algorithm, gives the best performance (achieving 10−6bit error rate at a signal to noise ratio of 2.4 dB) among all two dimensional turbo product codes. Following an analysis of the impact of finite word-length effect on the performance of the SISO decoder, full parallel decoding architecture at the top level and a number of lower level high speed implementation strategies such as applying lookahead technique to reduce the critical path of the merge sort circuit and fast finite field operations are presented. Area and timing estimates obtained by logic synthesis (0.18 µm, 1.5V CMOS technology) from VHDL descriptions are given to show how the design strategies translate into the area consumption and decoding throughput (> 32M bits/s) of the VLSI implementation.

This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation-based tool that has two alternating phases. For a circuit with |V| transistors and |E| wires, the first phase (D-phase) is based on minimum cost network flow, which in our application, has a worst case complexity of O(|V/spl par/E| log(log(|V|))). The second phase (W-phase) has a worst case complexity of O(|V/spl par/E|). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets, MINFLOTRANSIT shows up to 16.5% area savings (in relatively large circuits) over a circuit sized using a TILOS-like algorithm. In our opinion, the primary contribution of this paper is to take advantage of the structure of the transistor sizing problem and devise an iterative relaxation based gradient descent approach (D-phase) that has excellent convergence properties.

Turbo decoders inherently have large decoding latency and low throughput due to iterative decoding. To increase the throughput and reduce the latency, high-speed decoding schemes have to be employed. In this paper, following a discussion on basic parallel decoding architectures, the segmented sliding window approach and two other types of area-efficient parallel decoding schemes are proposed. Detailed comparison on storage requirement, number of computation units, and the overall decoding latency is provided for various decoding schemes with different levels of parallelism. Hybrid parallel decoding schemes are proposed as an attractive solution for very high level parallelism implementations. To reduce the storage bottleneck for each subdecoder, a modified version of the partial storage of state metrics approach is presented. The new approach achieves a better tradeoff between storage part and recomputation part in general. The application of the pipeline-interleaving technique to parallel turbo decoding architectures is also presented. Simulation results demonstrate that the proposed area-efficient parallel decoding schemes do not cause performance degradation.

A class of pseudo-random compound error-correcting codes, called generalized low-density (GLD) parity-check codes, has been proposed recently. As a generalization of Gallager's low-density parity-check (LDPC) codes, GLD codes are also asymptotically good in the sense of minimum distance criterion and can be effectively decoded based on iterative soft-input soft-output (SISO) decoding of individual constituent codes. The code performance and decoding complexity of GLD codes are heavily dependent on the employed SISO decoding algorithm. In this paper, we show that Max-Log-MAP is an attractive SISO decoding algorithm for GLD coding scheme, considering the trade-off between performance and complexity in the practical implementations. A normalized Max-Log-MAP is presented to improve the GLD code performance significantly compared with using conventional Max-Log-MAP. Moreover, we propose two techniques, decoding task scheduling and reduced search Max-Log-MAP, to effectively reduce the decoding complexity without any performance degradation.

This paper presents a very low complexity block turbo decoder composed of extended Hamming codes. New efficient complexity reduction algorithms are proposed including simplifying the extrinsic information computation and soft inputs updating algorithm. For performance evaluation, [eHamming (32,26,4)]/sup 2/ and [eHamming (64,57,4)]/sup 2/ block turbo code transmitted over an AWGN channel using BPSK modulation are considered. Extra 0.3 dB to 0.4 dB coding gain is obtained if compared with the scheme proposed in Pyndiah et al., (1996), and the hardware overhead is negligible. The complexity of our new block turbo decoder is about ten times less than that of the near-optimum block turbo decoder with a performance degradation of only 0.5 dB. Other schemes such as reduction of test patterns in the Chase algorithm and memory saving techniques are also presented.

Article Share on Models for power consumption and power grid noise due to datapath transition activity Authors: Lijun Gao Department of Electrical and Computer Engineering, University of Minnesota, 200 Union Street S.E., Minneapolis, MN Department of Electrical and Computer Engineering, University of Minnesota, 200 Union Street S.E., Minneapolis, MNView Profile , Keshab K. Parhi Department of Electrical and Computer Engineering, University of Minnesota, 200 Union Street S.E., Minneapolis, MN Department of Electrical and Computer Engineering, University of Minnesota, 200 Union Street S.E., Minneapolis, MNView Profile Authors Info & Claims GLSVLSI '01: Proceedings of the 11th Great Lakes symposium on VLSIMarch 2001Pages 121–126https://doi.org/10.1145/368122.368891Published:01 March 2001Publication History 1citation207DownloadsMetricsTotal Citations1Total Downloads207Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we investigate an efficient encoding approach for generalized low-density (GLD) parity check codes, a generalization of Gallager's (1962, 1963) low-density parity check (LDPC) codes. We propose a systematic approach to construct an approximate upper triangular GLD parity check matrix which defines a class of efficient-encoding GLD codes. It is shown that such GLD codes have equally good performance. By effectively exploiting structure sharing in the encoding process, we also present a hardware/software codesign for practical encoder implementation of these efficient-encoding GLD codes.

Protecting short frames using turbo coding is a challenging task because of the small interleave size and the need for transmission efficiency. We explore possible trade-off between power consumption (estimated by the average number of iterations) and performance of turbo decoders when short frame turbo codes are used. Three encoding/decoding schemes are proposed to improve performance of turbo decoder in terms of frame/bit error rate, and to increase the data transmission efficiency whether ARQ protocols are performed or not. Specifically, turbo decoding metrics aided short CRC codes are applied to terminated trellis codes, tail-biting encoded trellis codes and CRC embedded trellis codes with a two-fold purpose: to stop the iterative decoding processes and to detect decoding errors at the last iteration. We show that significant coding gains can be achieved by actually increasing the coding rate with negligible increase in power consumption. Performance improvement is demonstrated over both AWGN and Rayleigh flat fading channels.

Turbo decoders inherently have a large latency and low throughput due to iterative decoding. To increase the throughput and reduce the latency, high speed decoding schemes have to be employed. In this paper, following a discussion on basic parallel decoding architectures, two types of area-efficient parallel decoding schemes are proposed. Detailed comparison on storage requirement, number of computation units and the overall decoding latency is provided for various decoding schemes with different levels of parallelism. Hybrid parallel decoding schemes are proposed as an attractive solution for very high level parallelism implementations. Simulation results demonstrate that the proposed area-efficient parallel decoding schemes introduce no performance degradation in general. The application of the pipeline-interleaving technique to parallel turbo decoding architectures is also presented.

This paper considers the design of bit-parallel dedicated finite field multipliers using standard basis. An explicit algorithm is proposed for efficient construction of Mastrovito product matrix, based on which we present a systematic design of Mastrovito multiplier applicable to GF(2/sup m/) generated by an arbitrary irreducible polynomial. This design effectively exploits the spatial correlation of elements in Mastrovito product matrix to reduce the complexity. Using a similar methodology, we propose a systematic design of modified Mastrovito multiplier, which is suitable for GF(2/sup m/) generated by high-Hamming weight irreducible polynomials. For both original and modified Mastrovito multipliers, the developed multiplier architectures are highly modular, which is desirable for VLSI hardware implementation. Applying the proposed algorithm and design approach, we study the Mastrovito multipliers for several special irreducible polynomials, such as trinomial and equally-spaced-polynomial, and the obtained complexity results match the best known results. Moreover, we have discovered several new special irreducible polynomials which also lead to low-complexity Mastrovito multipliers.

Modular multiplication is a fundamental operation in numerous public-key cryptosystems including the RSA method. The increasing popularity of Internet e-commerce and other security applications translate into a demand for a scalable performance hardware design framework. Previous scalable hardware methodologies either were not systolic and thus involved performance-degrading, full-word-length broadcasts or were not scalable beyond linear array size. In this paper these limitations are overcome with the introduction of three scalable-performance modular multiplication architectures based on systolic arrays. Very high clock rates are feasible, since the cells composing the architectures are of bit-level complexity. Architectural methods based on both binary and high-radix modular multiplication are derived. All techniques are constructed to allow additional flexibility for the impact of interconnect delay within the design environment.

In this paper, a block-update parallel processing algorithm is proposed for increasing the throughput of the CORDIC-based QRD-RLS filtering with low power consumption. The proposed algorithm employs single-state-update parallel processing, and with this algorithm, the throughput of a block-by-block weight-update QRD-RLS filter can be increased at the cost of linear increase in hardware resource. However, the proposed algorithm does not change the iteration bounds and clock frequency of the QRD-RLS filters. As a result, the functional units need not be pipelined and the power consumption only increases linearly instead of quadratically. Due to non-pipelining and less power consumption, a higher folding factor can be used for a folding transformation and a great reduction in hardware resource can be achieved without exceeding the physical limitation on pipelining level and power density. Therefore, the proposed algorithm can serve as an important stage in designing and mapping a QRD-RLS filter onto physical hardware or computing resources, and thus is better for both ASIC chip design and parallel computing when block-by-block weight-update is applicable.

Transitions on high capacitance busses in VLSI systems result in considerable power dissipation. Various coding schemes have been proposed in literature to encode the input signal in order to reduce the number of transitions. Reducing number of transitions comes in exchange for redundancy in data transferred over the busses. For a given amount of redundancy there exists a lower bound on the average number of transitions. In recent times noise and reliability problems have brought the peak/instantaneous power consumed in VLSI systems in to prominence. There has been limited study done on reducing the number of instantaneous transitions and hence the peak power consumed in busses. In this paper we model a bus with a limit on the maximum instantaneous transition activity as a constrained channel and derive an upper bound on the data-rate obtainable using the capacity of the underlying channel. We then demonstrate that some existing bus encoding schemes are near-optimal with respect to the derived bounds thus, perhaps, obviating the need to search for newer more complicated coding schemes. Also considered is a bus with a constraint on number of transitions in a fixed number of (k) bus transmissions. The capacity of such a bus is derived in the same manner as a bus with a constraint on maximum instantaneous transition activity. 1.

This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation based tool that has two alternating phases. For a circuit with |V| transistors and |E| wires, the first phase (D-phase)) is based on minimum cost network flow, which in our application, has a worst-case complexity of O(|V||E|log(log(|V|))). The second phase W-phase has a worst case complexity of O(|V||E|). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets MINFLOTRANSIT shows up to 16.5% area savings over a circuit sized using a TILOS-like algorithm.

The complex valued matched filter correlators consume maximum power in the DS/SS CDMA receivers. These correlators accumulate 1024 samples lying in the range -7 to +7. This accumulation needs 3 data bits, 1 sign bit and 10 extra bits for overflow. Hence, the correlator can be implemented as a cascade of 4-bit full adder and a 10-bit incrementer. As a ripple carry adder (RCA) consumes the least power among all the existing adder architectures, we have implemented the 4-bit adder as a RCA. Previous incrementers were implemented as ripple counters. In this paper we propose a novel incrementer which is faster than a ripple counter based incrementer. Hence, it can be operated at a reduced voltage resulting in considerable power reduction. The incrementer is implemented using multiplexers, AND gates and TSPC registers. The ripple-counter correlator and the proposed incrementer correlator were laid out in MAGIC using 0.5µ CMOS technology followed by power estimation using HSPICE. It is shown that the proposed architecture requires 50% less power than a ripple counter based design.

Transitions on high capacitance busses in VLSI systems result in considerable power dissipation. Various coding schemes have been proposed in literature to encode the input signal in order to reduce the number of transitions. Number of transitions can be reduced by introducing redundancy in data transferred over the busses. For a given amount of redundancy there exists a lower bound on the average number of transitions. In this paper we derive a new coding scheme which leads to extremely practical techniques for bus transmission that reduce bus transitions to within 3.96-8.42% of the lower bound depending on the redundancy employed. There is also a net reduction in power dissipation ranging from 8.53-21.88% over an uncoded bus transmission scheme. This savings in power dissipation is identical to that for bus-invert coding per word transmitted the higher efficiency brought about by codeword slimming, however, results in shorter codewords than bus-invert coding which in turn results in higher energy efficiency in word transmission. Applications suitable for this new technique include systems relying on bit-serial implementation and systems with bit-parallel implementations where the cost of extra parallel-to-serial and serial-to-parallel data-format converters is marginal compared to the power savings obtained.

Protecting short frames using turbo coding is a challenging problem because of the short frame and the need for efficiency. In this paper, first, a scalable and easily implementable interleaver design is proposed since good random interleavers for long frame turbo codes are not guaranteed to perform well for short frames. Second, an efficient tail-biting encoding/decoding scheme is proposed, which does not sacrifice performance but significantly increases the throughput of the decoding process compared with existing methods. Finally, a novel error detection method, taking advantage a set of decoding metrics (DMs), is developed to reduce the number of cyclic redundancy check (CRC) bits used for error detection. The total savings is up to 12% for the transmission throughput and 21.5% for the energy consumption of the turbo decoder when a frame size of 49 is used.

A novel approach for hierarchically pipelining and folding the CORDIC-based systolic triangular array of a QRD-RLS filter to a small fixed size array is presented. With the annihilation-reordering look-ahead transformation, the iteration bound of a QRD-RLS filter can be reduced proportional to the look-ahead level. This paper presents, for the first time, how to pipeline and fold such a look-ahead transformed QRD-RLS array in a hierarchical way. Compared to the previously published mapping algorithms, this approach has low complexity and can result in a physical array of any size. Therefore, it is of great significance for ASIC chip designs and high-level synthesis. Besides, it is shown how a combination of look-ahead, pipelining and folding transformations can lead to an increase in throughput, a large reduction in area or a great saving in power consumption.

This paper presents a novel programmable digital signal processor (PDSP) component called the multiply multiple accumulator (MMAC). The MMAC differs from a standard multiply accumulator (MAC) in that it has k addressable accumulators rather than 1 in the case of the MAC. It is demonstrated that this feature of the MMAC can provide for low power scheduling of FIR filter operations. Typically, the number of read accesses to associated memories can come down, asymptotically, by a factor of k. The switching activity of associated multipliers also comes down by a factor of k.

The short length linear convolution, conventionally computed by the Cook-Toom algorithm, is important since it is the building block of large convolution algorithms. To compute the linear convolution of N and M points, the Cook-Toom algorithm computes the Lagrange interpolation at L=N+M-1 real numbers. However, the computation is often tedious and has only been carried out for special integers. We present an explicit general formula for linear convolutions which calculates the interpolation at L-2 general non-zero points. We further investigate the linear convolution from VLSI implementation point of view.

In this paper, a set of variables which can be easily computed in the course of iterative decoding of turbo decoders called decoding metrics (DMs) are introduced. According to the measured DMs after each iteration, a lot of information other than signal-to-noise ratio (SNR) in the received bits, such as how good/bad the current block is and how close the current iteration of decoding is to convergence, can be obtained. Detailed discussions are provided regarding why these variables are chosen. Based on the measured DMs after the first iteration, an approximate SNR-related variable L/sub c/ can be obtained for MAP-based turbo decoders. Simulation results show that there is almost no performance degradation if approximated L/sub c/ values are used instead of exact values. It is also shown that adaptive decoding using DMs is more efficient than existing methods both in terms of hardware and latency. Other applications of DMs are pointed out at last.

This paper presents a FPGA implementation of digit-serial complex number Multiplier-Accumulators (CMACs) based on Booth recoding techniques and carry save (CS) adders. The complex number Multiplier-Accumulators can be pipelined at LUT-level. An efficient mapping of the Booth recoding and the partial product generation is presented which results in a logic depth reduction. The combination of 5-3 and 4-3 converters in the CS structure and the utilization of ripple carry adder (RCA) trees lead to a minimum area requirement.

In this paper, we propose two VLSI applicable approaches to improving performance of soft-output Viterbi algorithm (SOVA)-based turbo decoders. In the first approach, a pseudo-median filter is employed to modify the soft outputs of each SOVA-based constituent decoder. Compared with conventional SOVA-based turbo decoders, an extra coding gain of 0.2 dB can be achieved for a wide range of target bit-error-rate (BER). In the second approach, an easily obtainable variable and a simple mapping function are used to avoid the complex computation of the scaling factor for extrinsic information in SOVA-based turbo decoders. An extra coding gain of 0.3 to 0.5 dB can be obtained in general. This approach does not require signal-to-noise ratio (SNR) related information while the original method does. The hardware overhead and the extra latency for both approaches are negligible.

This paper presents a novel analytical approach to compute the switching activity in digital circuits at the word level in the presence of glitching and correlation. The proposed approach makes use of signal statistics such as mean, variance, and autocorrelation. It is shown that the switching activity /spl alpha//sub f/ at the output node f of any arbitrary circuit in the presence of glitching and correlation is computed as /spl alpha//sub f/=/spl Sigma//sub i=1//sup S-1//spl alpha/(f/sub i,i+1/)=/spl Sigma//sub i=1//sup S-/ /sup 1/p(f/sub i+1/)(1-p(f/sub i/))(1-/spl rho/(f/sub i,i+1/)) (1) where /spl rho/(f/sub i,i+1/)=/spl rho/(f/sub i,i+1/)=(E[f/sub i/(Sn)f/sub i+1/(Sn)]- p(f/sub i/)p(f/sub i+1/))/(/spl radic/(p(f/sub i/)-p(f/sub i/)/sup 2/)(p(f/sub i+1/)- p(f/sub i+1//sup 2/))) (2). S number of time slots in a cycle; /spl rho/(f/sub i/,+1) time-slot autocorrelation coefficient; E[x]=expected value of x; p/sub x/=probability of the signal x being "one". The switching activity analysis of a signal at the word level is computed by summing the activities of all the individual bits constituting the signal. It is also shown that if the correlation coefficient of the higher order bits of a normally distributed signal x is /spl rho/(x/sub c/), then the bit P/sub 0/ where the correlation begins and the correlation coefficient is related hy /spl rho/(x/sub c/)=erfc{(2(P/sub 0/-1)-1)/(/spl radic/2/spl sigma//sub x/)} where erfc(x)=complementary error function; /spl sigma//sub x/=variance of x. The proposed approach can estimate the switching activity in less than a second which is orders of magnitude faster than simulation-based approaches. Simulation results show that the errors using the proposed approach are about 6.1% on an average and that the approach is well suited even for highly correlated speech and music signals.

Reed-Solomon (RS) coders are used for error-control coding in many applications such as digital audio, digital TV, software radio, CD players, and wireless and satellite communications. Traditionally, RS coders have been implemented using dedicated hardware. This paper considers software-based implementation of RS codecs. A hardware-software codesign approach is used to design the finite field datapath in a domain-specific digital signal processor (DSP) with low-energy RS codecs application in mind. These datapaths are designed to accommodate programmability with respect to the primitive polynomial as well as the field degree m. A novel heterogeneous digit-serial approach is proposed, where the heterogeneity corresponds to the use of different digit sizes in the multiply-accumulate (MAC) and degree reduction (DEGRED) subarrays. The salient feature of this digit-serial approach is that only the digit cells are implemented in hardware and the finite field multiplications are performed digit-serially in software by dynamically scheduling the internal digit-level operations. Efficient scheduling strategies for digit-serial finite field multiplications are presented and applied to the design of low-energy high-performance RS codecs in software. Significant energy and energy-latency reductions can be achieved using the digit-serial datapaths, as compared with the traditional approach where a combined MAC-DEGRED (parallel multiplier) unit is used. It is concluded that for two-error-correcting RS(n, k) codes over finite field GF(2/sup 8/), datapath containing a parallel MAC unit (of digit size eight) and a DEGRED unit with digit size two (or four) leads to RS codecs with the least energy consumption and energy-latency products; with these datapath architectures and appropriate digit-serial scheduling strategies, more than 60% energy reduction and more than one-third energy-latency reduction can be achieved compared with the parallel multiplication datapath-based approach.

Dynamic power consumed in CMOS gates goes down quadratically with the supply voltage.By maintaining a high supply voltage for gates on the critical path and by using a low supply voltage for gates off the critical path it is possible to dramatically reduce power consumption in CMOS VLSI circuits without performance degradation.Interfacing gates operating under multiple supply voltages, however, requires the use of level converters, which makes the problem modeling difficult.In this paper we develop a formal model and develop an efficient heuristic for addressing the use of two supply voltages for low power CMOS VLSI circuits without performance degradation.Power consumption savings up to 25% over and above the best known existing heuristics are demonstrated for combinational circuits in the ISCAS85 benchmark suite.

This paper presents a novel analytical approach to complete the switching activity in digital circuits at the word-level in the presence of glitching and correlation. The proposed approach makes use of signal statistics such as mean, variance, and autocorrelation. A novel expression is derived for the switching activity /spl alpha//sub f/ at the output node f of an arbitrary circuit in terms of time-slot autocorrelation coefficient, the expected value, and the signal probability. The switching activity analysis of a signal at the word-level is computed by summing the activities of all the individual bits constituting the signal. A novel relationship between the correlation coefficient of the higher order bits of a normally distributed signal and the bit where the correlation begins is also presented. The proposed approach can estimate the switching activity in less than a second which is orders of magnitude faster than simulation based approaches. Simulation results show that Me errors using the proposed approach are about 6% on an average and that the approach is well suited even for highly correlated speech and music signals.

This paper proposes a comprehensive method for overcoming the inherently serial nature of variable-length near-entropy coding to obtain unrestrictedly parallel realizations of Huffman compression. A codestream rearrangement technique together with a symbol-stream order-recovery procedure form a concurrent approach capable of exceeding all previously attainable code rate figures. Furthermore, the method is noteworthy for achieving 100% hardware utilization with no code rate overhead while maintaining data output in a traditional streamed format. To further this endeavor, bit-serial encoder and decoder designs that possess compelling speed and area advantages are developed for service as parallel processing elements. However, both are suitable in more general contexts as well. The decoder, in particular, is optimally fast. The encoder and decoder designs are programmable, thus suggesting the appropriateness of the composite approach for a general-purpose ultra-high-speed codec. The benefits for low-power and variable-rate applications are briefly discussed.

This paper presents a low-power bit-serial Viterbi decoder chip with the coding rate r=1/3 and the constraint length K=9 (256 states). This chip has been implemented using 0.5 /spl mu/m three-layer metal CMOS technology and is targeted for high speed convolutional decoding for next generation wireless applications such as wide-band CDMA mobile systems and wireless ATM LANs. The chip is expected to operate at 20 Mbps under 3.3 V and at 2 Mbps under 1.8 V. The add-compare-select (ACS) units have been designed using bit-serial arithmetic, which has made it feasible to execute 256 ACS operations in parallel. For trace-back operations, we have developed a novel power-efficient trace-back scheme and an application-specific memory, which was designed considering that 256 bits should be written simultaneously for write operations but only one bit needs to be accessed for read operations. We have estimated that the chip dissipates only 10 mW at 2 Mbps operation under 1.8 V.

In this paper, the problem of multiple access over digital subscriber loops is introduced and defined as FIR LTI filter design over linear dispersive channels. The 2-D FIR CAP/QAM based modulation line code is extended to the multi-dimensional system to accommodate multiple access topology. The concept of orthogonality division multiple access, ODMA, is used as the methodology to achieve that goal. The problem of increasing the number of dimensions is stated as a minimax optimization problem, then solved using sequential quadratic programming. 3, 4, and 6-dimensional systems are introduced to support multiple access applications. Computer simulations are carried out to evaluate the performance and functionality of the orthogonal signaling line code.

This paper describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. Given a circuit G and a target clock period c, our algorithm either outputs a retimed version of G satisfying setup and hold constraints or reports that such a solution is not possible, in O(|V/sup 3/|log|V|log(|V|C)) steps, where |V| corresponds to number of gates in the circuit and C is equal to the number of registers in the circuit. This is the first polynomial time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues in to consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of long-path only retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that technique are likely to be valid for improving the performance of the technique described in this paper.

In this paper, a unified methodology is introduced for the computation of modular multiplication and reduction operations, which are fundamental to numerous public-key cryptography systems. First, a general theory is presented which aides the construction of arbitrary most-significant-digit first and least-significant-digit first iterative modular reduction methods. Utilizing this foundation, new methods are presented which are not premised in division techniques. The resultant class of algorithmic techniques, which we dub iterative residue accumulation (IRA) methods, are robust, accommodating general radixes. Furthermore, forms supporting both most-significant-digit or least-significant-digit first evaluation are presented. Significantly, in comparison to earlier methods, IRA effectively replaces quotient-digit evaluation and quotient-modulus multiplication steps encountered in techniques such as Montgomery's method with a single-step residue evaluation, thereby permitting efficiency improvements. Forms suitable for either lookup or multiplication-based evaluation are explored. Precomputation overhead is minimal and the methods are suitable for VLSI implementation.

With the reducing distances between wires in deep sub-micron technologies, coupling capacitances are becoming significant as their magnitude becomes comparable to the area capacitance and fringing capacitance of a wire. This causes an increasing susceptibility to failure due to inadvertent noise, and leads to a requirement for accurate noise estimation. An incorrect estimation of the noise could lead either to circuit malfunction in the case of under-estimation, or to wasted design resources due to overestimation. This paper presents a new time-efficient method for the precise estimation of crosstalk noise. While existing fast noise estimation metrics may overestimate the coupling noise by several orders of magnitude, the proposed metric computes the coupling noise with a good accuracy as compared to SPICE.

The use of dual threshold voltages can significantly reduce the static power dissipated in CMOS VLSI circuits.With the supply voltage at 1V and threshold voltage as low as 0.2V the subthreshold leakage power of transistors starts dominating the dynamic power.Also, many times a large number of devices spend a long time in a standby mode where the leakage power is the only source of power consumption.We present a near-optimal approach to synthesize low static power CMOS VLSI circuits with two threshold voltages that reduces power consumption compared with a previous approach by upto 29.45%.Also, presented is a technique which finds static power optimal configurations for CMOS VLSI circuits when arbitrary number of threshold voltages are allowed.

Carrierless amplitude/phase modulation (CAP) is a viable alternative for digital subscriber loop (DSL) systems such as high-speed DSL, asymmetric DSL, and very high-speed DSL. In this paper, two novel orthogonal-based modulation schemes are introduced for the DSL environment. In the first technique, the conventional two-dimensional (2-D) CAP-16 line code is extended to a three-dimensional (3-D) scheme. The 3-D system is designed so that the new overall transfer matrix maintains perfect reconstruction (PR) of the transmitted information. The system is designed by solving a minimax optimization problem by using the sequential quadratic programming algorithm; this searches the whole space of signals under the PR condition and the DSL constraints. The 3-D CAP system leads to a 50% increase in throughput at the expense of the output signal-to-noise ratio (SNR) degradation by 3-4 dB. It should be noted that this increase in throughput can also be achieved by a CAP-64 system. Nevertheless, the dynamic range of the proposed 3-D CAP approach is 7.4 dB less than CAP-64, which leads to faster equalization. Furthermore, the equalizer performance in the 3-D case is 1-3 dB better, depending on channel and noise considerations. Another application of the multidimensional CAP approach, referred to as orthogonality division multiple access (ODMA) is presented. In this approach, the CAP system is extended to more than three dimensions by maintaining the same overall symbol rate as in the 2-D case. The ODMA system allows multiple-access operation of the DSL communication link with minimal hardware penalty. The performance of the ODMA system for the multiple-access environment is found to match the conventional 2-D CAP, allowing suitable multiple-access topology with minimal complexity overhead. The ODMA system complexity is compared with discrete multitone and is found to have 25% less complexity for the same bit rate. Theoretical analysis of the ODMA system using zero-forcing equalization shows that the equalization process yields better SNR as the number of dimensions increases, asymptotically approaching the intersymbol interference-free matched filter bound.

This paper considers two-dimensional (2-D) retiming, which is the problem of retiming circuits that operate on 2-D signals. We begin by discussing two types of parallelism available in 2-D data processing, which we call inter-iteration parallelism and inter-operation parallelism. We then present two novel techniques for 2-D retiming that can be used to extract inter-operation parallelism. These two techniques are designed to minimize the amount of memory required to implement a 2-D data-flow graph while maintaining a desired clock rate for the circuit. The first technique is based on an integer linear programming (ILP) formulation of the problem, and is called ILP 2-D retiming. This technique considers the entire 2-D retiming problem as a whole, but long central processing unit times are required if the circuit is large. The second technique, called orthogonal 2-D retiming, is a linear programming formulation which is derived by partitioning ILP 2-D retiming into two parts called s- and a-retiming. This technique finds a solution in polynomial time and is much faster than the ILP 2-D retiming technique, but the two sub problems (s- and a-retiming) can give results which are not compatible with one another. To solve this incompatibility problem, a variation of orthogonal 2-D retiming called integer orthogonal 2-D retiming is developed. This technique runs in polynomial time and the s-retiming and a-retiming steps are guaranteed to give compatible results. We show that the techniques presented in this paper can result in memory hardware savings of 50% compared to previously published 2-D retiming techniques.

This paper presents novel hybrid carry-select modified-tree (CSMT) adder architectures for binary carry generators and adders using multiplexers only. These architectures not only require the fewest number of multiplexers, but also consume the least energy for a specified latency. These architectures are based on a carry-select configuration where each block can be a carry-select or tree or modified-tree block. The modified-tree blocks permit ripple in the carry-generation process; which leads to dramatic reduction in the number of multiplexers as well as power consumption. It is shown that, for a block length W, the carry-select block and the modified-tree block with internal ripple of (log/sub 2/ W-1) multiplexer stages require the same number of multiplexers. This is a powerful result because the longer carry-select blocks can be replaced by the modified-tree blocks without increasing the multiplexer complexity. The advantage of this approach is in reduction of power consumption since the amount of ripple in the carry-select block grows linearly with W, while that in the modified-tree block grows logarithmically with W. It is shown that for fastest adder/subtractor designs, the proposed CSMT architecture can reduce the multiplexer complexity by about 40% for word-lengths ranging from 8 to 32, when compared with known tree approaches. It is shown that, for a certain specified latency and specified number of multiplexers, a family of carry-select and CSMT adders can be designed. It is shown that, for a specified latency, the carry-select adders with larger number of blocks and smaller block lengths consume less power. Through extensive simulations, CSMT adder configurations that minimize energy consumption or power-latency product, which are approximately 5% to 10% less than those of known tree and best carry-select adders, are obtained. Finally, based on novel latency-matching and block-increment techniques introduced in this paper, a systematic design methodology for design of CSMT adders with least latency, least number of multiplexers, and least energy consumption is presented.

Cordic based QRD-MVDR adaptive beamforming algorithms possess desirable properties for VLSI implementation such as regularity and good finite-word length behavior. But this algorithm suffers from a speed limitation constraint due to the presence of recursive operations in the algorithm. In this paper, a fine-grain pipelined CORDIC based QRD-MVDR adaptive beamforming algorithm is developed using the matrix lookahead technique. The proposed architecture can operate at arbitrarily high sample rates, and consists of only Givens rotations which can be mapped onto a Jacobi specific dataflow processor. It requires a complexity of O(M(p/sup 2/+Kp)) Givens rotations per sample time, where p is the number of antenna elements, K is the number of look direction constrains, and M is the pipelining level.

Reed-Solomon (RS) codecs are used for error control coding in many applications such as digital audio, digital TV, software radio, CD players, and wireless and satellite communications. This paper considers software-based implementation of RS codecs where special instructions are assumed to be used to program finite field multiplication datapaths inside a domain-specific programmable digital-signal processor (DS-PDSP). A heterogeneous digit-serial approach is presented, where the heterogeneity corresponds to the use of different digit-sizes in the multiply-accumulate (MAC for polynomial multiplication) and degree reduction (DEGRED for polynomial module operation) subarrays. The salient feature of this digit-serial approach is that only the digit-cells are implemented in hardware, the finite field multiplications are performed digit-serially in software by dynamically scheduling the internal digit-level operations in RS encoders and decoders. It is concluded that, for 2-error-correcting RS(n,k) codec implementations over finite field GF(2/sup 8/), a parallel MAC unit (of digit-size 8) and a DEGRED unit with digit-size 2 is the best datapath, with respect to least energy consumption and energy-delay products. With this datapath architecture and appropriate digit-serial scheduling strategies, more than 60% energy reduction and more than 1/3 energy delay reduction can be achieved compared with the parallel multiplication datapath based approach.

Motivated by the need for designing efficient architectures for two-dimensional discrete wavelet transforms (DWTs), this paper presents a novel multi-dimensional (MD) folding transformation technique which can be used to synthesize control circuits for pipelined architectures for a specific class of multirate MD digital signal processing (DSP) algorithms. Although a multirate MD DSP algorithm contains decimeters and expanders which change the effective sample rate of a MD discrete time signal, MD folding time-multiplexes the algorithm to hardware in such a manner that the resulting synchronous architecture requires only a single clock signal for the clocking of the datapath. Feasibility constraints are derived for folding a 2-D data-flow graph (DFG) onto a given set of hardware functional units according to a specified schedule. Area/power efficient architectures are derived for 1-4 level 2-D discrete wavelet transforms (DWT) with 18.5-23.3% savings in storage area.

This paper presents a fast highly regular digit-serial complex-number multiplier-accumulator (CMAC) architecture which is well suited for VLSI implementations. This paper makes two contributions. First, several complex-number representation schemes are discussed. It is shown that the real-imaginary alternate (RIA) scheme is the best among all representation schemes and the prior designs of CMACs based on the radix-(2j) redundant complex number system (RCNS) are not efficient with respect to hardware complexity and processing speed. Second, digit-serial CMAC architectures which can be pipelined at fine-grain level to increase the throughput rate are designed based on carry-save configuration.

This paper presents a novel hierarchical divided bit-line approach for reducing active power in SRAMs by reducing bit-line capacitance. Two or more 6T SRAM cells are combined together to divide the bit-line into several sub bit-lines. These sub bit-lines are again combined to form two or more levels of hierarchy. This division of bit-line into hierarchical sub bit-lines results in reduction of bit-line capacitance, which reduces active power and access time. Optimum values for number of levels of hierarchy and number of blocks combined at each level have been derived. Experimental results show that the observed parameters and estimated ones follow the same trend. It is shown that the reduction in bit-line capacitance reduces active power consumption by 50-60% and the access time by about 20% at the expense of approximately 5% increase in the number of transistors. This approach is further extended by incorporating the controlled voltage swing on bit-lines. This extension reduces the power consumption by another 20-30%.

This paper addresses a fast low-power implementation of a shared division and square-root architecture. Two approaches are considered in this paper; these include the SRT (Sweeney, Robertson and Tocher) approach which does not require prescaling and the GST (generalized Svoboda and Tung) approach which requires prescaling of the operands. This paper makes two important contributions. Although SRT division and square-root approaches and GST division approach have been known for long time, square-root architectures based on the GST approach have not been proposed so far. This paper for the first time, develops a GST square-root architecture without requiring an additional division by the scaling factor after the square-root operation. Although various divider and square-root architectures have been compared with respect to speed, no tradeoffs with respect to power consumption of these architectures have been studied so far quantitative comparison of speed and power consumption of GST and SRT division/square-root units is the second main contribution of the paper. Shared divider and square-root units are designed based on the SRT and the GST approaches, in both minimally and maximally redundant radix-4 representations. Simulations demonstrate that the worst-case overall latency of the minimally-redundant GST architecture is 35% smaller compared to the SRT. Alternatively, for a fixed latency, the minimally-redundant GST architecture based division and square-root operations consume 42% and 20% less power respectively, compared to the maximally-redundant SRT approach.

The paper presents a general theory for developing new Svoboda-Tung (or simply NST) division algorithms not suffering the drawbacks of the "classical" Svoboda-Tung (or simply ST) method. NST avoids the drawbacks of ST by proper recoding of the two most significant digits of the residual before selecting the most significant digit of this recoded residual as the quotient digit. NST relies on the divisor being in the range [1, 1+/spl delta/), where /spl delta/ is a positive fraction depending upon: 1) the radix, 2) the signed digit set used to represent the residual, and 3) the recoding conditions of the two most significant digits of the residual. If the operands belong to the IEEE Std range [1, 2), they have to be conveniently prescaled. In that case, NST produces the correct quotient but the final residual is scaled by the same factor as the operands, therefore, NST is not useful in applications where the unsealed residual is necessary. An analysis of NST shows that previously published algorithms can be derived from the general theory proposed in the paper. Moreover, NST reveals a spectrum of new possibilities for the design of alternative division units. For a given radix-b, the number of different algorithms of this kind is b/sup 2//4.

In this paper we formalize a novel multirate folding transformation which is a tool used to systematically synthesize control circuits for pipelined VLSI architectures which implement multirate algorithms. Although multirate algorithms contain decimators and expanders which change the effective sample rate of a discrete-time signal, multirate folding time-multiplexes the multirate algorithm to hardware in such a manner that the resulting synchronous architecture requires only a single-clock signal. Multirate folding equations are derived and these equations are used to address two related issues. The first issue is memory requirements in folded architectures. We derive expressions for the minimum number of registers required by a folded architecture which implements a multirate algorithm. The second issue is retiming. Based on the noble identities of multirate signal processing, we derive retiming for folding constraints which indicate how a multirate data-flow graph must be retimed for a given schedule to be feasible. The techniques introduced in this paper can be used to synthesize architectures for a wide variety of digital signal processing applications which are based on multirate algorithms, such as signal analysis and coding based on subband decompositions and wavelet transforms.

In high-level synthesis, a data flow graph (DFG) description of an algorithm is mapped onto a register transfer level description of an architecture. Each node of the DFG is scheduled to a specific time and allocated to a processor. In this paper, we present new integer linear programming (ILP) models which generate a blocked schedule for a DFG with automatic retiming, pipelining, and unfolding while performing module selection and dataformat conversion. A blocked schedule is a schedule which overlaps multiple iterations of the DFG to guarantee a processor optimal schedule. During module selection an appropriate processor is chosen from a library of processors to construct a cost optimal architecture. Furthermore, we also include the cost and latency of data format conversions between processors of different implementation styles. We also present a new formulation for minimizing the unfolding factor of the blocked schedule. The approach presented in this paper is the only systematic approach proposed so far to include implicit unfolding and to perform synthesis using nonuniform processor styles and data format converters.

Finite fields have been used for numerous applications including error-control coding and cryptography. The design of efficient multipliers, dividers, and exponentiators for finite field arithmetic is of great practical concern. In this paper, we explore and classify algorithms for finite field multiplication, squaring, and exponentiation into least significant bit first (LSB-first) scheme and most significant bit first (MSB-first) scheme, and implement these algorithms using semisystolic arrays. For finite field multiplication (for programmable as well as fixed field order) and exponentiation, we conclude that LSB-first algorithms are more efficient as their basic cells have less critical path computation time. Another advantage of LSB-first scheme is its capability of achieving substructure sharing among multiple operations, which could lead to savings in hardware when these arithmetic units are used as building blocks for a large system. For finite field squaring operation, it turns out that the MSB-first algorithm is more efficient as it leads to simpler architectures. Bit-level pipelined semisystolic architectures utilize broadcast signals. As a result, these require much less number of latches and lead to much smaller latency than the corresponding systolic array, with the same cycle time (the computation time in one basic cell). Efficient VLSI implementation of semisystolic multipliers, squarers and exponentiators are designed and compared with existing architectures. A novel architecture for computing AB/sup n/+C using power representation is also presented.

Cordic based IIR digital filters possess desirable properties for VLSI implementation such as local connection, regularity, and good finite word-length behavior, but can't be pipelined to finer levels (such as bit or multi-bit levels) due to the presence of feedback loops. In this paper, a pipelining method for the cordic based IIR digital filters is proposed using the constrained filter design methods and the polyphase decomposition technique. Using this method, the filter sample rate can be increased to any desired level.

This paper presents a low-area finite field divider using dual basis representation. This divider is based on the division algorithm of solving Discrete Wiener-Hopf Equation using Gauss-Jordan elimination method. The hardware complexity of the matrix generation part has been reduced dramatically form O(m/sup 2/) to O(m). When it is used as a building block for a large system, this divider can achieve more savings in hardware by utilizing sub-structure sharing techniques.

Digit-serial architectures obtained using traditional unfolding techniques cannot be pipelined beyond a certain level because of the presence of feedback loops. In this paper, a novel design methodology is presented which permits bit-level pipelining of the digit-serial architectures. This achieves sample speeds close to corresponding bit-parallel multipliers with significantly lower area. This increased sample speed can be traded with reduction in power supply voltage resulting in significant reduction in power consumption. The results show that for transformed multipliers with smaller digit-sizes (/spl les/4), the singly-redundant multiplier consumes the least power and for larger digit sizes, the type-I multiplier consumes the least power. It is also found that the optimum digit-size for least power consumption in type-I and type-III multipliers is /spl sim//spl radic/(2 W), where W represents the word-length. The proposed digit-serial multipliers consume on an average 20% lower power than the traditional digit-serial architectures for the non-pipelined case, and about 5-15 times lower power for the bit-level pipelined case. Also, modified Booth (1951) recoding is applied to transformed multipliers and it is found that the recoded multipliers consume about 22% lower power than the transformed multipliers without recoding.

This paper presents novel architectures for fast binary addition which can be implemented using multiplexers only. Binary addition as carried out using a fast redundant-to-binary converter. It is shown that appropriate encoding of the redundant digits and recasting the binary addition as a redundant-to-binary conversion reduces the latency of addition from Wt/sub fa/, to Wt/sub mux/ where t/sub fa/ and t/sub mux/ respectively, represent binary full adder and multiplexer delays, and W is the word-length. A family of fast converter architectures is developed based on tree-type (obtained using lookahead techniques) and carry-select approaches. The carry-generation component is the critical component in redundant-to-binary conversion and binary addition. It is shown that fastest binary addition can be performed using (Wlog/sub 2/+W+1) multiplexers in time (log/sub 2/W+2)t/sub mux/. If the specified adder latency is greater than (log/sub 2/W+2)t/sub mux/, then a family of converters using fewest multiplexers can be designed based on carry-select approach. Finally a class of hybrid adders are designed by using a carry-select configuration and by substituting tree-based blocks in place of some carry-select blocks. It is shown that this approach can lead to adder designs which consume the least energy.

A wavelet domain robust denoising algorithm is presented, which efficiently removes both Gaussian as well as Gaussian mixed with impulse noise. Several wavelet domain operators are developed which help in the denoising process. The superiority of the new algorithm is firmly established by simulation over a variety of images.

In this paper we present a new radix 2 division algorithm that uses a recurrence employing simple 3-to-2 digit carry-free adders to perform carry-free addition/subtraction for computing the partial remainders in radix 2 signed-digit form. The quotient digit, during any iteration of the division recursion, is generated from the two most-significant radix 2 digits of the partial remainder and independent of the divisor in over-redundant radix 2 digit form (i.e., with digits which belong to the digit set {-2, -1, 0, +1, +2}). The over-redundant quotient digits are then converted to the conventional radix 2 digits (belonging to the set {-1, 0, +1}) by using a reduction technique. This division algorithm is well suited for IEEE 754 standard operands belonging to the range (1, 2) and is slightly faster than previously proposed radix 2 designs (such as the radix 2 SRT), which do not employ input scaling, since the quotient selection for such algorithms is a function of more than two most-significant radix 2 digits of the partial remainder. In comparison with the designs that employ input scaling, the proposed design although slightly slower saves hardware required for scaling purposes.

Arithmetic coding is a highly efficient lossless source coding technique. Multiplication-free arithmetic coding algorithms provide an excellent tradeoff between operation complexity and coding performance. A whole family of multiplication-free arithmetic codes, which achieve the best coding efficiency and can be used for arbitrary size of alphabets, is derived. The complete tradeoff between the complexity of operations and compression performance of all the algorithms is presented.

This paper presents a novel approach for implementing area-efficient parallel (block) finite impulse response (FIR) filters that require less hardware than traditional block FIR filter implementations. Parallel processing is a powerful technique because it can be used to increase the throughput of a FIR filter or reduce the power consumption of a FIR filter. However, a traditional block filter implementation causes a linear increase in the hardware cost (area) by a factor of L, the block size. In many design situations, this large hardware penalty cannot be tolerated. Therefore, it is advantageous to produce parallel FIR filter implementations that require less area than traditional block FIR filtering structures. In this paper, we propose a method to design parallel FIR filter structures that require a less-than-linear increase in the hardware cost. A novel adjacent coefficient sharing based sub-structure sharing technique is introduced and used to reduce the hardware cost of parallel FIR filters. A novel coefficient quantization technique, referred to as a maximum absolute difference (MAD) quantization process, is introduced and used to produce quantized filters with good spectrum characteristics. By using a combination of fast FIR filtering algorithms, a novel coefficient quantization process and area reduction techniques, we show that parallel FIR filtering structures with up to a 45% reduction in hardware is achieved for the given examples.

Finite field has received a lot of attention due to its widespread applications in cryptography, coding theory, etc. Design of efficient finite field arithmetic architectures is very important and of great practical concern. In this paper, a new bit-serial/parallel finite field multiplier is presented with standard basis representation. This design is regular and well suited for VLSI implementation. As compared to existing serial/parallel finite field multipliers, it has smaller critical path, lower latency and can be easily pipelined. When it is used as a building block for large systems, it can achieve more savings in hardware in the broadcast structures by utilizing sub-structure sharing technique. This paper also presents two generalized algorithms for finite field serial/parallel multiplication. They can be used to derive efficient bit-parallel, digit-serial or bit-serial multiplication architectures. The optimal primitive polynomials over GF(2/sup m/) (for 2/spl les/m/spl les/9) are provided which will generate structures with minimum hardware complexity and relatively more flexibilities for feasible digit-sizes with respect to the proposed algorithms. Finally a multiplier over GF(2/sup 8/) is given as an example showing how to derive finite field multipliers using the proposed algorithms. This multiplier has less number of transistors, smaller critical path and consumes less power compared to the existing semi-systolic architecture.

This paper presents an algorithm for the estimation of power in static CMOS digital circuits using a stochastic approach.The salient feature of this approach is that it can be used to estimate the power of reasonably large digital circuits in a very short time, due to its hierarchical nature.Here, the given circuit is rst partitioned into smaller sub-circuits.Then, the sub-circuits are modeled using state transition diagrams (stds), and the steady-state probabilities associated with the various states are computed by treating them as irreducible Markov c hains.Finally, the energy associated with each sub-circuit is computed, and the total energy of the circuit is obtained by summing up the energies of its constituent sub-circuits.In the proposed hierarchical approach, the energies associated with various edges in a subcircuit are calculated only once using SPICE and these values are used several times; this results in large savings in computation time.Another advantage of the proposed approach is that we can accommodate switching activities at the transistor level and not necessarily at gate or higher levels.Experimental results show that the estimated power is in close agreement with the actual power obtained from exhaustive SPICE simulations, but the computation time required by the proposed approach is orders of magnitude less than that of SPICE.

This paper presents a new heuristic, concurrent, iterative loop-based scheduling and allocation algorithm for high-level synthesis of digital signal processing (DSP) architectures using heterogeneous functional units. In a heterogeneous architecture, functional units could be either bit-serial or digit-serial or bit-parallel. We assume a library of heterogeneous implementation style based functional units is available. Experiments show that this new heuristic synthesis approach generates optimal and near-optimal area solutions. Although optimum synthesis of such architectures were proposed recently using an integer linear programming (ILP) model, our method can produce similar solutions in one to two orders of magnitude less time, at the expense of sacrificing the cost optimality. We compare the solutions generated by the proposed algorithm with the optimal solutions generated by the ILP approach and other recent techniques. We have incorporated this new algorithm into the Minnesota ARchitecture Synthesis (MARS-II) system.

We present a novel VLSI implementation of an order-configurable, coefficient-programmable, and power-efficient FIR filter architecture. This single-chip architecture contains 4 multiply-add functional units and each functional unit can have up to 8 multiply-add operations time-multiplexed (or folded) onto it. Thus one chip can be used to realize FIR filters with lengths ranging from 1 to 32 and multiple chips can be cascaded for higher order filters. To achieve power-efficiency, an on-chip phase locked loop (PLL) is used to automatically generate the minimum voltage level to achieve the required sample rate. Within the PLL, a novel programmable divider and a voltage level shifter are used in conjunction with the clock rate to control the internal supply voltage. Simulations show that this chip can be operated at a maximum clock rate of 100 MHz (folding factor of 1 or filter length of 4). When operated at 10 MHz, this chip only consumes 27.45 mW using an automatically set internal supply voltage of 2 V. For comparison, when the chip is operated at 10 MHz and 5 V, it consumes 109.24 mW. At 100 MHz, the chip consumes 891 mW with a 4.5 V supply that is automatically generated by the PLL. This design has been implemented using Mentor Graphics tools for an 8-bit word-length and 1.2 /spl mu/m CMOS technology.

This paper considers throughput and memory requirements in architectures which operate on two-dimensional (2D) digital signals. We present a novel technique for retiming a 2D data-flow graph to meet a given throughput constraint while keeping the memory required by the architecture low. This technique, which we call orthogonal two-dimensional retiming, is posed as two linear programming problems which can be solved in polynomial time. Our results show that, for a given throughput constraint, the orthogonal two-dimensional retiming formulation leads to architectures which require less memory than architectures designed using previously known techniques.

This paper presents an efficient Reed-Solomon encoder based on standard basis. The key operation in Reed-Solomon encoding is the multiplication of a feedback term with several (possibly) known terms. We present an efficient structure to implement this operation. The hardware complexity of this encoder is identical to the well-known Berlekamp encoder. It however, offers two advantages over the Berlekamp encoder-a critical path independent of the order of Reed-Solomon code being implemented and the ability to encode without any need for basis conversion.

This paper presents an algorithm for power estimation in digital circuits using a hierarchical approach. The salient feature of this approach is that it can be used to estimate the power of large digital circuits in a reasonably short time. Moreover, it takes into account both the spatial correlations introduced in the circuit due to reconvergent fanout, and the delays associated with the various computation units. The circuit is partitioned into sub-circuits which are modeled using state transition diagrams (STDs), and the energy, and therefore power, associated with the circuit is then computed from its constituent STDs by treating them as irreducible Markov chains. Experimental results show that the estimated power is in close agreement with the actual power obtained from exhaustive SPICE simulations. However, the computation time required by the proposed approach is orders of magnitude less than that required by SPICE.

The paper presents a systematic theoretical approach for the analysis of bounds on power consumption in Baugh-Wooley, binary tree and Wallace tree multipliers. This is achieved by first developing state transition diagrams (STDs) for the sub circuits making up the multipliers. The STD is comprised of states and edges, with the edges representing a transition (switching activity) from one state to another in the sub circuit. Then, maximum (minimum) energy values associated with the edges constituting the STDs are used to derive the zipper (lower) bound in both non pipelined and p-bit level pipelined multipliers. It is shown that as p is decreased, the upper bound approaches the lower bound. Moreover, based on the theoretical analysis we conclude that the upper bound in a Baugh-Wooley multiplier has a cubic dependence on the word length, while that in a binary tree multiplier has a quadratic dependence on the word length.

A new parallel-in-parallel-out bit-level pipelined multiplier is presented to perform multiplication in GF(2/sup m/). This new multiplier uses m/sup 2/ basic cells where each cell has 2 2-input AND, 2 2-input XOR and 3 1-bit latches. The system latency of this multiplier is m+1 compared to 3 m in previous architectures. The number of latches required per cell has also been reduced from 7 to 3. We also present a bit-level pipelined parallel-in-parallel-out squarer. This squarer has a system latency of [m/2] compared to 3m in previous designs and is 25% more hardware efficient. The critical paths in both these proposed designs are the same as in existing designs.

Previously, a new pipelinable PSTAR-RLS algorithm was developed. It was shown to be an effective alternative to the QRD-RLS algorithm when high-speeds are required. Using a folding technique, a 4-tap PSTAR-RLS algorithm was implemented on a single VLSI chip. All the operations in the chip are bit-level pipelined. With a 1.2 /spl mu/ CMOS technology this chip is expected to run at 100 MHz. Redundant number system based arithmetic operators were used for performance advantage. Apart from a wafer scale implementation, this is the first ever single chip ASIC implementation of a RLS adaptive filter.

This paper presents the architecture and implementation of a full-custom 1.2 micron CMOS VLSI chip that executes a shared division/square root algorithm operating on mantissas (23-b in length) of single precision IEEE 754 std. floating point numbers. The division and square root algorithms used in this implementation are the radix 2 signed digit based digit-by-digit schemes. These two algorithms perform quotient/root digit selection using two most-significant digits of the partial remainder and are hence faster than other similar previously proposed radix 2 shared division/square root schemes. This chip runs at a clock rate of about 66 MHz at 5.0 V (from simulations) and requires 29 cycles per divide/square root operation from the time the operands are provided at its pin inputs.

Classical doubly-terminated lossless networks designed to meet maximum available power bounds are known to have good passband sensitivity. In this paper, a synthesis method for ladder WDFs (Wave Digital Filters) corresponding to the classical doubly-terminated lossless networks is developed. The synthesis procedures are carried out only in the digital domain so that no knowledge of LC filter or microwave filter theory is needed. The length of the critical path of the designed WDFs can be chosen optimally depending upon applications such that both the speed requirement and the hardware minimization are satisfied at the same time. For narrow-band sharp-transition filters, the pipelining level of the designed WDF can be increased further by applying the DIFIR (Decomposed and Interpolated FIR) method.

Arithmetic coding has become an important and efficient lossless compression technique for image coding. Multiplication free arithmetic coding algorithms provide excellent tradeoff between operation complexity and coding performance. This paper presents a whole family of multiplication free arithmetic codes which achieve the best coding efficiency and can be used for arbitrary size alphabets. This is accomplished by studying the effects of truncation and rounding in the sub-intervals for approximations. The complete tradeoff between the complexity of operations and compression performance of all the algorithms is presented. The conclusive study shows that there will be no more practical multiplication free arithmetic codes.

This paper presents two VLSI design advances for arithmetic coding which is an entropy coding technique for image coding. First, we present an algorithm which has less performance degradation in finite word-length implementation than two previously analyzed algorithms. Second, we propose the implementation of the interval width register update operation using redundant arithmetic to obtain further speed-up in the VLSI implementation of the JPEG/JBIG binary arithmetic coding algorithm known as QM-coder. The resulting hardware design achieves a faster clock rate and can be combined with previously proposed high speed techniques.

This paper presents a novel approach for low power implementations of finite impulse response (FIR) filters with less hardware overhead than traditional FIR implementations. Parallel or block processing with duplication of hardware can reduce power consumption; parallel processing by block size L requires the critical path to be charged in L times longer time as compared with the sequential implementation and the identical critical path can be charged in longer time with lower supply voltage which leads to lower power consumption. The hardware cost of this approach increases linearly with the block size L. In this paper we propose a general technique for block implementation of FIR filters which requires fewer multipliers than the straightforward block implementation. The use of this approach can lead to a further reduction in power consumption and hardware cost.

In this paper we present a fast radix-4 division algorithm for floating point numbers. This method is based on Svoboda's division algorithm and the radix-4 redundant number system. The algorithm involves a simple recurrence with carry-free addition and employs prescaling of the operands. In the proposed divider implementation, each radix-4 digit (belonging to set {-3,...,+3}) of the quotient and partial remainder is encoded using two radix-2 digits (belonging to the set {-1,0,+1}) and this leads to hardware simplicity. The quotient digits are determined by observing three most-significant radix-2 digits of the partial remainder and independent of the divisor. The architecture presented for the proposed algorithm is faster than previously proposed radix-4 dividers, which require at least four digits of the partial remainder to be observed to determine quotient digits.>

This paper addresses high-level synthesis methodologies for dedicated digital signal processing (DSP) architectures used in the iterative Loop-based Minnesota Architecture Synthesis (MARS) design system. We present a novel concurrent scheduling and resource allocation algorithm which exploits inter-iteration and intra-iteration precedence constraints. The novel algorithm implicitly performs algorithmic transformations, such as pipelining and retiming, on the data-flow graphs during the scheduling process to produce solutions which are as good as those previously published and which executes in less time. MARS is capable of producing optimal and near-optimal schedules in fractions of seconds. Previous synthesis systems have focused on DSP algorithms which have single or lumped delays in the recursive loops. In contrast, MARS is capable of generating valid architectures for algorithms which have randomly distributed delays. MARS exploits these delays to produce more efficient architectures and allows our system to be more general. We are able to synthesize architectures which meet the iteration bound of any algorithm by unfolding, retiming, and pipelining the original data-flow graph.>

This paper presents efficient single-rate architectures for the orthonormal discrete wavelet transform (DWT). Folded and digit-serial architectures are derived from an efficient lattice implementation of two-channel FIR paraunitary systems known as the quadrature mirror filter (QMF) lattice. Folded architectures are derived by applying systematic folding techniques to multirate systems. For digit-serial architectures, we show that any two-channel subband system can be implemented using digit-serial processing techniques by utilizing the polyphase decomposition. Using this result, we describe an orthonormal DWT architecture which uses the QMF lattice structure and digit-serial processing techniques. The number of multipliers and adders required for both the folded and digit-serial lattice-based architectures approaches one-half the number required to implement similar systems based on direct-form filter implementations as the order of the FIR filters becomes large. This makes folded and digit-serial QMF lattice structures attractive choices for applications of the orthonormal DWT which require low area and low power dissipation.>

The QR decomposition based recursive least-squares (RLS) adaptive filtering (referred to as QRD-RLS) algorithm is suitable for VLSI implementation since it has good numerical properties and can be mapped to a systolic array. Recently, a new fine-grain pipelinable STAR-RLS algorithm was developed based on scaled tangent rotation. The pipelined STAR-RLS algorithm, referred to as PSTAR-RLS, is useful for high-speed applications. The stability of QRD-RLS, STAR-RLS and PSTAR-RLS has been proved but the performance of these algorithms in finite-precision arithmetic has not yet been analyzed. The aim of this paper is to determine expressions for the degradation in the performance of these algorithms due to finite-precision. By exploiting the steady-state properties of these algorithms, simple closed-form expressions are obtained which depend only on known parameters. Since floating-point or fixed-point arithmetic representations may be used in practice, both representations are considered in this paper. The results show that the PSTAR-RLS and STAR-RLS algorithms perform better than the QRD-RLS especially in a floating-point representation. The theoretical expressions are found to be in good agreement with the simulation results.>

In high level synthesis each node of a synchronous dataflow graph (DFG) is scheduled to a specific time and allocated to a processor. In this paper we present new integer linear programming (ILP) models which generate a blocked schedule for a DFG with implicit retiming, pipelining, and unfolding while performing module selection and data format conversion. A blocked schedule is a schedule which overlaps multiple iterations of the DFG to guarantee a minimum number of processors. Component modules are selected from a library of processors to minimize cost. Furthermore, we include data format converters between processors of different data formats. In addition, we minimize the unfolding factor of the blocked schedule.

This paper considers architecture design of lapped block processing based discrete wavelet transforms. The emphasis is on computing the minimum number of registers required for various data format converters. Using life-time analysis, it is shown that the total number of on-chip line delays required for this architecture is approximately (N-1) where N is the order of the FIR filters used for the computation of the discrete wavelet transform.>

In this paper we present a fast radix 4 division algorithm for floating point numbers based on Svoboda's division algorithm. The algorithm involves a simple recurrence with carry-free addition and employs pre-scaling of the operands, The quotient digits are determined by observing three most-significant radix 2 digits (msds) of the partial remainder and independent of the divisor. The proposed algorithm is faster than previously proposed radix 4 and radix 2 division algorithms, which require at least four digits of the partial remainder to be observed to determine a quotient digit. The speedup is achieved at cost of increase in area.>

Presents novel sequential and parallel learning techniques for codebook design in vector quantizers using neural network approaches. These techniques are used in the training phase of the vector quantizer design. These learning techniques combine the split-and-cluster methodology of the traditional vector quantizer design with neural learning, and lead to better quantizer design (with fewer distortions). The sequential learning approach overcomes the code word underutilization problem of the competitive learning network. As a result, this network only requires partial or zero updating, as opposed to full neighbor updating as needed in the self organizing feature map. The parallel learning network, while satisfying the above characteristics, also leads to parallel learning of the codewords. The parallel learning technique can be used for faster codebook design in a multiprocessor environment. It is shown that this sequential learning scheme can sometimes outperform the traditional LBG algorithm, while the parallel learning scheme performs very close to the LGB and the sequential learning algorithms.>

In this paper, the design of a C-testable, high-performance carry-free array divider is presented. A radix-2 redundant number based carry-free divider is considered and is modified to make it C-testable, i.e., it can be exhaustively tested using a constant number of test vectors irrespective of its word-length. Previous C-testable designs considered dividers which used carry-propagate adders/subtractors. These dividers are slow because of their O(W/sup 2/) computation time (where W is the word-length of the divider). High-performance carry-free dividers use carry-free redundant arithmetic adders/subtractors. Due to this feature, they have O(W) computation time. The on-the-fly converter used by carry-free dividers to convert the redundant quotient to two's-complement form is shown to be not C-testable. It is modified to be linear-testable (in word-length) instead of exponential time required for exhaustive testing of all possible combinations at its inputs. We conclude that the number of test vectors needed is 99 for C-testing of the divider array and (3W+10) for linear testing of the converter. The hardware overhead required to make the divider C-testable and the on-the-fly converter linear testable is also shown to be nominal.>

To achieve additional speedup in rank order and stack filter architectures requires the use of parallel processing techniques such as pipelining and block processing. Pipelining is well understood but few block architectures have been developed for rank order and stack filtering. Block processing is essential when the architecture reaches the throughput limits caused by the underlying technology. A trivial block structure repeats a single input, single output structure to generate a multiple input, multiple output structure and can achieve speedups equal to the block size (or the number of multiple outputs). Unlike linear filters, the rank order and stack filter outputs are calculated using comparisons. It is possible to share these comparisons within the block structure. The authors introduce a systematic method for applying block processing to the rank order and stack filters. This method takes advantage of shared comparisons within the block structure to generate a block filter with shared substructures whose complexity is reduced. Furthermore, block processing is important for the generation of low power designs. Trivial block structures generate low power designs up to a certain limit. The authors demonstrate how block structures with shared substructures are used to generate designs with arbitrarily low power.>

The design of a C-testable, high-performance carry-free array divider is presented. A radix-2 redundant number based carry-free divider is considered and modified to make it C-testable, i.e. it can be exhaustively tested using a constant number of test vectors irrespective of its word-length. Previous C-testable designs considered dividers that used carry-propagate adders/subtractors. These dividers are slow because of their O(W/sup 2/) computation time (where W is the word-length of the divider). High-performance carry-free dividers use carry-free redundant arithmetic adders/subtractors. Due to this feature, they have O(W) computation time. The on-the-fly converter used by carry-free dividers to convert the redundant quotient to two's-complement form is shown not to be C-testable. It is modified to be linear-testable (in word-length), instead of taking the exponential time required for exhaustively testing all possible combinations at its inputs.>

The minimum unfolding factor necessary to reduce the critical path time of the data-flow graph to less than or equal to the required iteration period of the associated algorithm is determined. Minimizing the unfolding factor is important because the time complexity for scheduling and allocation increases linearly with the unfolding factor. An iterative unfolding algorithm that calculates the minimum unfolding factor necessary to achieve a given sample rate is introduced. The unfolding factor can be further reduced to achieve a given sample rate, in many cases with the use of retiming. The algorithm can be utilized to preprocess a data-flow graph prior to resource scheduling and allocation.>

A folded architecture and a digit-serial architecture are proposed for implementation of one- and two-dimensional discrete wavelet transforms. In the one-dimensional folded architecture, the computations of all wavelet levels are folded to the same low-pass and high-pass filters. The number of registers in the folded architecture is minimized by the use of a generalized life time analysis. The converter units are synthesized with a minimum number of registers using forward-backward allocation. The advantage of the folded architecture is low latency and its drawbacks are increased hardware area, less than 100% hardware utilization, and the complex routing and interconnection required by the converters used. These drawbacks are eliminated in the alternate digit-serial architecture at the expense of an increase in the system latency and some constraints on the wordlength. In latency-critical applications, the use of the folded architecture is suggested. If latency is not so critical, the digit-serial architecture should be used. The use of a combined folded and digit-serial architecture is proposed for implementation of two-dimensional discrete wavelet transforms.>

Rank order filters are nonlinear filters which choose an output based on the rank within a window of sample inputs determined by sorting the inputs. Rank order filters are a subset of the class of stack filters which are also nonlinear. A systematic method for applying block processing, which transforms single-input single-output structures to parallel-input parallel-output structures for non-recursive rank order and stack filters is presented. This method takes advantage of shared substructures within the block structure to efficiently generate a block filter whose complexity can be up to one-half the size of the original filter structure times the block size. This method can also be applied to two-dimensional non-recursive rank order filters.>

Achieving high speed in decision feedback equalizers (DFEs) is difficult because of the nonlinear decision directed adaptation. Recently, parallel DFE and extended LMS DFE algorithms were proposed for parallel implementation of DFEs. A new double-row DFE algorithm which outperforms the previous approaches is presented. Under the no error propagation assumption, this algorithm performs exactly like a serial DFE. The above three algorithms degrade drastically at high speeds and are more computationally expensive. Three additional novel parallel implementations of the DFE which lead to considerable hardware savings and avoid the coding loss of the former approaches are proposed. These new algorithms are referred to as the direct parallel, double-row DFE without weight correction, and improved block techniques. The first two algorithms give performance that is only slightly degraded as compared to the earlier methods. The improved block technique provides the best performance at higher speed.>

The implementation of video data format using a minimum number of registers is considered. A systematic lifetime analysis of the variables is carried out to determine the latency and the minimum number of registers needed for the converter. The technique of obtaining the minimum number of registers is illustrated using four classes of data format converters: line-by-line to column-by-column, line-by-line to interleaved skewed one-dimensional block format, line-by-line to interleaved two-dimensional block format, and line-by-line to zigzag format. Closed-form expressions for minimum number of registers in these converters are obtained in terms of the number of input and output pixels processed per cycle and the number of input and output bits processed per pixel in a cycle.>

The authors use life time analysis and propose systematic register allocation techniques to reuse the registers; register reuse leads to data format converter architectures with fewer registers. A simple forward-circulate allocation scheme is proposed to motivate the use of register allocation, and a more efficient forward-backward register allocation scheme is proposed. Examples of data converters presented include matrix transposer, serial-to-parallel, and parallel-to-serial converters. General m-to-n bit-parallel and bit-serial converters are also studied. It is shown that register allocation techniques can lead to up to 50% savings in hardware area, as compared with converter architectures designed in a straightforward manner.>

Methodologies are addressed for high-level synthesis of dedicated digital signal processing (DSP) architectures using the Minnesota Architecture Synthesis (MARS) design system. The MARS system is capable of exploring a wide design space because the authors' synthesis algorithms can accommodate multiple implementation styles. Algorithms are given for concurrent scheduling and resource allocation for systematic synthesis of DSP architectures. The algorithms exploit inter-iteration and intra-iteration precedence constraints, and produce as good or better results than those published. Synthesis is accommodated with multiple implementation styles to reduce overall hardware costs; systematic synthesis of such architectures has not been explored so far. To improve the quality of the final schedule, the algorithm utilizes implicit retiming and pipelining of the data flow graph.>

Many techniques for quantizing large sets of input vectors into much smaller sets of output vectors have been developed. Various neural network based techniques for generating the input vectors via system training are studied. The variations are centered around a neural net vector quantization (NNVQ) method which combines the well-known conventional Linde, Buzo and Gray (1980) (LBG) technique and the neural net based Kohonen (1984) technique. Sequential and parallel learning techniques for designing efficient NNVQs are given. The schemes presented require less computation time due to a new modified gain formula, partial/zero neighbor updating, and parallel learning of the code vectors. Using Gaussian-Markov source and speech signal benchmarks, it is shown that these new approaches lead to distortion as good as or better than that obtained using the LBG and Kohonen approaches.>

The design of high-speed architectures is addressed for fixed-point, two's-complement, bit-parallel, pipelined, multiplication, division and square-root operations. The architectures presented make use of hybrid number representations (i.e. the input and output numbers are presented using two's complement representation, and the internal numbers are represented using radix-2 redundant representation). A fast, new conversion scheme for converting radix-2 redundant numbers to two's-complement binary numbers is presented, and this is used to design a reduced latency bit-parallel multiplier. The novel sign-multiplexing scheme helps detect the sign of a redundant number very quickly and is used in combination with the remainder conditioning scheme to achieve very high speed in fixed-point division and square-root operators. These architectures require fewer pipelining latches than their conventional two's-complement counterparts. Reduction in latency without sacrificing clock speed has resulted in reduced computation time for these operations.>

Rate-optimal compile-time multiprocessor scheduling of iterative dataflow programs suitable for real-time signal processing applications is discussed. It is shown that recursions or loops in the programs lead to an inherent lower bound on the achievable iteration period, referred to as the iteration bound. A multiprocessor schedule is rate-optimal if the iteration period equals the iteration bound. Systematic unfolding of iterative dataflow programs is proposed, and properties of unfolded dataflow programs are studied. Unfolding increases the number of tasks in a program, unravels the hidden concurrently in iterative dataflow programs, and can reduce the iteration period. A special class of iterative dataflow programs, referred to as perfect-rate programs, is introduced. Each loop in these programs has a single register. Perfect-rate programs can always be scheduled rate optimally (requiring no retiming or unfolding transformation). It is also shown that unfolding any program by an optimum unfolding factor transforms any arbitrary program to an equivalent perfect-rate program, which can then be scheduled rate optimally. This optimum unfolding factor for any arbitrary program is the least common multiple of the number of registers (or delays) in all loops and is independent of the node execution times. An upper bound on the number of processors for rate-optimal scheduling is given.>

The authors present a systematic unfolding transformation technique to transform bit-serial architectures into equivalent digit-serial ones. The novel feature of the technique is the generation of functionally correct control circuits in the digit-serial architectures. Bit-serial systems process one bit of a word or sample in a clock cycle. For some applications bit-serial architectures may be too slow, and bit-parallel architectures may be faster than necessary and may require too much hardware. The desired sample rate can be achieved using the digit-serial approach, where multiple bits of a sample are processed in a single clock cycle. The number of bits processed in one clock cycle in the digit-serial systems is the digit size; the digit size can be any arbitrary integer. A digit-serial implementation of two's complement adders and multipliers is presented. Unfolding of multiple-rate operations (such as interpolators and decimators) is also presented.>

Concurrent fine-grain pipelined VLSI architectures for dynamic programming (DP) problems are presented. Look-ahead is used to obtain finer-grain pipelining, and a novel precomputation sequence is used to design DP computation architectures with square to linear add-compare-select (ACS) processor complexity (in number of states in the DP problem). Use of nonuniform pipelining and nonuniform implementation methodologies in dedicated DP architectures is introduced; this results in a saving of hardware modules with no loss in speed. A two's complement least-significant-bit-first bit-serial architecture is also presented for the compare-select operation.>

An exploration is made of roundoff and quantization errors in pipelined high-speed recursive filters, implemented using look-ahead computation and a two's complement number system. These errors are theoretically estimated for a first-order recursive filter, for both decomposed and nondecomposed implementations. The maximum total roundoff error in decomposed scattered look-ahead filters is shown to be less than that in the nondecomposed scattered look-ahead filters. Further, the quantization error in decomposed filters is less when poles are closer to origin (as compared with nondecomposed ones). Experimental results are presented for a sixth-order Butterworth and a fourth-order Chebyshev low-pass filter. High speed can also be obtained by using redundant arithmetic in standard filter structures. These filters may suffer from reduced dynamic range and degraded finite word-length effects. Experimental results for such implementations are presented.>

Novel algorithms for synthesis of control circuits in pipelined signal processing architectures are presented. The algorithms generate appropriate latching and switching of intermediate signals for a functionally correct operation. Sufficient theory of pipelining is developed to ensure iteration independence of the registers used in control circuits of the dedicated architectures. The interprocessor control circuits are being incorporated into CAD systems for dedicated designs. Algorithms for automatic generation of all control circuits for a specified sequencing and scheduling of operations, for single and multiple clock, and for single and multiple implementation styles are presented.>

A distributed algorithm is presented for obtaining an efficient and conflict-free broadcasting schedule in a multi-hop packet radio network. The inherent broadcast nature of the radio channel enables a node's transmission to be received by all other nodes within range. Multiple transmissions can be scheduled simultaneously because of the multi-hop nature of the network. It is first shown that the construction of a broadcasting schedule of minimum length is NP-complete, and then a centralized algorithm based on a sequential graph-coloring heuristic is presented to construct minimal-length schedules. A distributed implementation of this algorithm is then proposed, which is based on circulating a token through the nodes in the network.>

Progress in supercomputing technology has led to two major trends. First, many existing algorithms need to be redesigned for efficient concurrent implementation using supercomputers. Second, a continuous increase will be apparent in the number of application-specific VLSI integrated circuits, which can provide the performance of supercomputers using single chips or chipsets (at the expense of design time for algorithm and architecture development). Both of these approaches require considerable effort in the development of algorithms for specific applications. Four independent algorithm transformation methodologies-program unfolding, retiming, look-ahead algorithms, and index mapping transformations-are reviewed. These transformation techniques exploit the available parallelism in iterative data-flow programs and create additional parallelism if necessary.>

The authors explore various approaches to pipelining recursive digital filters. A past attempt to pipeline directly from recursive filters was based on clustered look-ahead computation, which leads to a linear increase in hardware with respect to the number of loop pipeline stages. However, the pipelined filters derived using this technique are not guaranteed to be stable. The authors introduce a new look-ahead approach (referred to as scattered look-ahead) to pipeline recursive filters in a way that guarantees stability. They also propose a decomposition technique to implement the nonrecursive portion (generated due to the scattered look-ahead) in a decomposed manner (for cases where the number of loop pipeline states is a power of two) to obtain pipelined realizations of logarithmic implementation complexity with respect to the number of loop pipeline stages (as opposed to linear). Based on the scattered look-ahead technique, they present fully pipelined and fully hardware efficient bidirectional linear systolic arrays and unidirectional ring arrays for implementation of high speed recursive digital filters.>

The maximum achievable sampling rate of recursive algorithms is inherently bounded due to the computational latency associated with the loop computation. This recursion or feedback in the algorithms destroys the opportunity to pipeline any recursive loop. In this paper, we introduce a technique of look-ahead computation applicable to any linear recursive algorithm (LRA) to achieve equivalent realizations with reduced iteration period and higher sampling rate. The concurrency created by the use of look-ahead computation can be used to obtain pipelined and/or block implementations. We illustrate the applicability of the look-ahead computation technique to obtain high speed VLSI realizations of linear time-invariant, and time-varying systems. A generalized look-ahead computation technique theorem for arbitrary interleaving is also presented. Finally, it is shown that the iteration period in certain synchronous data flow graphs can also be reduced by the use of look-ahead computation.