Deep learning algorithms are increasingly employed at the edge. However, edge devices are resource constrained and thus require efficient deployment of deep neural networks. Pruning methods are a key tool for edge deployment as they can improve storage, compute, memory bandwidth, and energy usage. In this paper we propose a novel accurate pruning technique that allows precise control over the output network size. Our method uses an efficient optimal transportation scheme which we make end-to-end differentiable and which automatically tunes the exploration-exploitation behavior of the algorithm to find accurate sparse sub-networks. We show that our method achieves state-of-the-art performance compared to previous pruning methods on 3 different datasets, using 5 different models, across a wide range of pruning ratios, and with two types of sparsity budgets and pruning granularities.

Biological neural networks are equipped with an inherent capability to continuously adapt through online learning. This aspect remains in stark contrast to learning with error backpropagation through time (BPTT) that involves offline computation of the gradients due to the need to unroll the network through time. Here, we present an alternative online learning algorithm ic framework for deep recurrent neural networks (RNNs) and spiking neural networks (SNNs), called online spatio-temporal learning (OSTL). It is based on insights from biology and proposes the clear separation of spatial and temporal gradient components. For shallow SNNs, OSTL is gradient equivalent to BPTT enabling for the first time online training of SNNs with BPTT-equivalent gradients. In addition, the proposed formulation unveils a class of SNN architectures trainable online at low time complexity. Moreover, we extend OSTL to a generic form, applicable to a wide range of network architectures, including networks comprising long short-term memory (LSTM) and gated recurrent units (GRUs). We demonstrate the operation of our algorithm ic framework on various tasks from language modeling to speech recognition and obtain results on par with the BPTT baselines.

Automatic speech recognition systems (ASR), such as the recurrent neural network transducer (RNN-T), have reached close to human-like performance and are deployed in commercial applications. However, their core operations depart from the powerful biological counterpart, the human brain. On the other hand, the current developments in biologically-inspired ASR models lag behind in terms of accuracy and focus primarily on small-scale applications. In this work, we revisit the incorporation of biologically-plausible models into deep learning and enhance their capabilities, by taking inspiration from the brain’s diverse neural and synaptic dynamics. In particular, we propose novel deep learning units by introducing neural connectivity concepts emulating the axo-somatic and the axo-axonic synapses and integrate them into the RNN-T architecture. We demonstrate for the first time that such a model can yield performance levels competitive to the state-of-the-art. Moreover, our implementation has a significantly reduced computational cost and a lower latency.

Developing energy-saving neural network models is a topic of rapidly increasing interest in the artificial intelligence community. Spiking neural networks (SNNs) are biologically inspired models that strive to leverage the energy efficiency stemming from a long process of evolution under limited resources. In this paper we propose a SNN model where each neuron integrates piecewise linear postsynaptic potentials caused by input spikes and a positive bias, and spikes maximally once. Transformation of such a network into the ANN domain yields an approximation of a standard ReLU network, leading to a facilitated training based on backpropagation and an adaptation of the batch normalization. With backpropagation-trained weights, SNN inference offers a sparse-signal and low-latency classification, which can be readily adapted for a stream of input patterns, lending itself to an efficient hardware implementation. The supervised classification of MNIST and Fashion-MNIST datasets, using this approach, provides accuracy close to that of an ANN and surpassing other single-spike SNNs.

In-memory computing is an emerging computing paradigm enabling deep-learning inference at significantly higher energy-efficiency and reduced latency. The essential idea is mapping the synaptic weights of each layer to one or more in-memory computing (IMC) cores. During inference, these cores perform the associated matrix-vector multiplications in place with O(1) time complexity, obviating the need to move the synaptic weights to additional processing units. Moreover, this architecture enables the execution of these networks in a highly pipelined fashion. However, a key challenge is designing an efficient communication fabric for the IMC cores. In this work, we present one such communication fabric based on a graph topology that is well-suited for the widely successful convolutional neural networks (CNNs). We show that this communication fabric facilitates the pipelined execution of all state-of-the-art CNNs by proving the existence of a homomorphism between the graph representations of these networks and that corresponding to the proposed communication fabric. We then present a quantitative comparison with established communication topologies and show that our proposed topology achieves the lowest bandwidth requirements per communication channel. Finally, we present one hardware implementation and show a concrete example of mapping ResNet-32 onto an IMC core array interconnected via the proposed communication fabric.

A novel interleaved switched-capacitor and SRAM-based multibit matrix-vector multiply-accumulate engine for in-memory computing is presented. Its operation principle is based on first converting an SRAM-stored n-bit weight into a proportional voltage using a pipeline D/A converter built from n+1 equally sized stages. A switched-capacitor stage then multiplies these voltages with an m-bit digital input activation. Finally, the output voltages that correspond to the different multiplication results are accumulated along one column by means of charge-sharing. With our proposed architecture, the required circuit area, computation time, and power consumption scale linearly versus the bit resolution of both the inputs and the weights. Analytical formulas are presented for the energy consumption in both capacitors and switches. Moreover, the impact of fabrication mismatch on analog computation accuracy is examined. The full system architecture is described, and the feasibility is demonstrated, via a full macroimplementation study in 14 nm, detailing area and energy consumption, as well as the overall latency. Finally, a specific design of a 128 × 2048 6 -bit weight and 6-bit input signed matrix-vector multiplication accelerator system in 14 nm is presented, which runs at 2.43 TOP/s at an efficiency of 16.94 TOP/s/W, while using the nominal supply voltage of 0.8 V. If the operands' precision is considered in the metric, then the efficiency becomes 609.7 TOP/s/W.

Deep neural networks (DNNs) have surpassed human-level accuracy in a variety of cognitive tasks but at the cost of significant memory/time requirements in DNN training. This limits their deployment in energy and memory limited applications that require real-time learning. Matrix-vector multiplications (MVM) and vector-vector outer product (VVOP) are the two most expensive operations associated with training of DNNs. Strategies to improve the efficiency of MVM computation in hardware have been demonstrated with minimal impact on training accuracy. However, the VVOP computation remains a relatively less explored bottleneck even with the aforementioned strategies. Stochastic computing (SC) has been proposed to improve the efficiency of VVOP computation but on relatively shallow networks with bounded activation functions and floatingpoint (FP) scaling of activation gradients. In this paper, we propose ESSOP, an efficient and scalable stochastic outer product architecture based on the SC paradigm. We introduce efficient techniques to generalize SC for weight update computation in DNNs with the unbounded activation functions (e.g., ReLU), required by many state-of-the-art networks. Our architecture reduces the computational cost by re-using random numbers and replacing certain FP multiplication operations by bit shift scaling. We show that the ResNet-32 network with 33 convolution layers and a fully-connected layer can be trained with ESSOP on the CIFAR-10 dataset to achieve baseline comparable accuracy. Hardware design of ESSOP at 14nm technology node shows that, compared to a highly pipelined FP16 multiplier design, ESSOP is 82.2% and 93.7% better in energy and area efficiency respectively for outer product computation.

In-memory computing is an emerging non-von Neumann computing paradigm where certain computational tasks are performed in memory by exploiting the physical attributes of the memory devices. Memristive devices such as phase-change memory (PCM), where information is stored in terms of their conductance levels, are especially well suited for in-memory computing. In particular, memristive devices, when organized in a crossbar configuration can be used to perform matrix-vector multiply operations by exploiting Kirchhoff's circuit laws. To explore the feasibility of such in-memory computing cores in applications such as deep learning as well as for system-level architectural exploration, it is highly desirable to develop an accurate hardware emulator that captures the key physical attributes of the memristive devices. Here, we present one such emulator for PCM and experimentally validate it using measurements from a PCM prototype chip. Moreover, we present an application of the emulator for neural network inference where our emulator can capture the conductance evolution of approximately 400,000 PCM devices remarkably well.

Metal-oxide-based resistive memory devices (ReRAM) are being actively researched as synaptic elements of neuromorphic co-processors for training deep neural networks (DNNs). However, device-level non-idealities are posing significant challenges. In this work we present a multi-ReRAM-based synaptic architecture with a counter-based arbitration scheme that shows significant promise. We present a 32×2 crossbar array comprising Pt/HfO2/Ti/TiN-based ReRAM devices with multi-level storage capability and bidirectional conductance response. We study the device characteristics in detail and model the conductance response. We show through simulations that an in-situ trained DNN with a multi-ReRAM synaptic architecture can perform handwritten digit classification task with high accuracies, only 2% lower than software simulations using floating point precision, despite the stochasticity, nonlinearity and large conductance change granularity associated with the devices. Moreover, we show that a network can achieve accuracies > 80% even with just binary ReRAM devices with this architecture.

The capabilities of artificial neural networks (ANNs) are limited by the operations possible at their individual neurons and synapses. For instance, each neuron's activation only represents a single scalar variable. In addition, because neuronal activations may be dominated by a single timescale in the synaptic input, unsupervised learning from data with multiple timescales has not been generally possible. Here we address these by exploiting the continuous-time and asynchronous operation of spiking neural networks (SNNs), i.e. a biologically-inspired type of ANNs. First, we demonstrate how input neurons can be two-dimensional (2D), i.e. each represent two variables. Second, we show unsupervised learning from multiple timescales simultaneously. 2D neurons operate by allocating each variable to a different timescale in their activation, i.e. one variable corresponds to the timing of individual spikes, and another to the spike rate. We show how these can be modulated separately but simultaneously, and we apply this mixed coding technique to encoding images with two modalities, namely, colour and brightness. Unsupervised multi-timescale learning is achieved by synapses with spike-timing-dependent plasticity, combined with varying degrees of short-term plasticity. We demonstrate the successful application of this learning scheme on the unsupervised classification of bimodal pictures encoded by our 2D neurons. Taken together, our results show that SNNs are capable of increasing both the information content of each neuron and the exploitable data in the input. We suggest that through these unique features, SNNs may increase the performance and broaden the applicability of ANNs.

Neuromorphic computing takes inspiration from how the brain works to design power- and area-efficient hardware architectures for learning systems. Recently, unsupervised feature learning neuromorphic architectures have been presented, including a concept of synaptic competition that promotes the engagement of the synapses in the learning beyond weight storage. However, it is common to train these neuromorphic systems following the classic machine learning assumption of i.i.d. dataset sampling, which may not hold for real world inputs. In this paper, we propose a more realistic dataset sampling technique and apply it for online learning in a neuromorphic system using phase-change memristors as synapses and implementing synaptic competition. Furthermore, we propose a novel formulation of synaptic competition that captures orthogonal features, alternatively to independent components. We experimentally demonstrate the operation of the system for a non-i.i.d. stream and compare the performance to the models of lateral inhibition and dendritic inhibition. The obtained results demonstrate online feature learning capabilities of the proposed system and robustness to non-i.i.d. inputs.

Deep neural networks (DNN) have revolutionized the field of machine learning by providing unprecedented human-like performance in solving many real-world problems such as image or speech recognition. Training of large DNNs, however, is a computationally intensive task, and this necessitates the development of novel computing architectures targeting this application. A computational memory unit where resistive memory devices are organized in crossbar arrays can be used to store the synaptic weights in their conductance states. The expensive multiply accumulate operations can be performed in place using Kirchhoff's circuit laws in a non-von Neumann manner. However, a key challenge remains the inability to alter the conductance states of the devices in a reliable manner during the weight update process. We propose a mixed-precision architecture that combines a computational memory unit storing the synaptic weights with a digital processing unit and an additional memory unit that stores the accumulated weight updates in high precision. The new architecture delivers classification accuracies comparable to those of floating-point implementations without being constrained by challenges associated with the non-ideal weight update characteristics of emerging resistive memories. The computational memory unit in a two layer neural network realized using nonlinear stochastic models of phase-change memory achieves a test accuracy of 97.40% in the MNIST digit classification problem.

Spiking neural networks (SNNs) could play a key role in unsupervised machine learning applications, by virtue of strengths related to learning from the fine temporal structure of event-based signals. However, some spike-timing-related strengths of SNNs are hindered by the sensitivity of spike-timing-dependent plasticity (STDP) rules to input spike rates, as fine temporal correlations may be obstructed by coarser correlations between firing rates. In this article, we propose a spike-timing-dependent learning rule that allows a neuron to learn from the temporally-coded information despite the presence of rate codes. Our long-term plasticity rule makes use of short-term synaptic fatigue dynamics. We show analytically that, in contrast to conventional STDP rules, our fatiguing STDP (FSTDP) helps learn the temporal code, and we derive the necessary conditions to optimize the learning process. We showcase the effectiveness of FSTDP in learning spike-timing correlations among processes of different rates in synthetic data. Finally, we use FSTDP to detect correlations in real-world weather data from the United States in an experimental realization of the algorithm that uses a neuro-morphic hardware platform comprising phase-change memristive devices. Taken together, our analyses and demonstrations suggest that FSTDP paves the way for the exploitation of the spike-based strengths of SNNs in real-world applications.

Neuromorphic systems provide biologically inspired methods of computing, alternative to the classical von Neumann approach. In these systems, computation is performed by a network of spiking neurons controlled by the values of their synaptic weights, which are updated in the process of learning. Providing efficient synaptic learning rules, such as spike-timing-dependent plasticity (STDP), is a challenging task. These rules need to primarily use local information, but simultaneously develop a knowledge representation that is useful in the global context. From the implementation viewpoint, they also need to be suited for particular hardware technology. In this work, we propose a system with spiking neurons and synapses realized using phase-change devices. We design in a bottom-up manner an architecture for pattern learning and feature extraction. Experimental results from a prototype hardware platform demonstrate the capabilities of the proposed neuromorphic system.

Novel forms of nonvolatile memory, such as phase-change memory (PCM), promise low latency and small granularity of read and write access at high storage density. They also feature very high endurance. These characteristics make them highly desirable for emerging high-capacity (hybrid) memory applications such as in-memory databases and in-memory processing. In this work, we present the architecture, implementation and experimental performance results of an FPGA-based PCM memory controller for OpenPOWER servers. The memory controller leverages the Coherent Accelerator Processor Interface (CAPI) of the POWER processor in order to offer low-latency access to the CPU memory space. In addition, the memory controller implements an efficient management protocol that supports a dynamic size of pending read and write requests in order to offer high bandwidth under mixed-type workloads. We describe the architecture and implementation details of the memory controller and we demonstrate its performance using a prototype platform based on different types of OpenPOWER servers equipped with CAPI-enabled FPGA cards. The developed PCM controller is evaluated in terms of sustained data rates (MBps) and access latency (us). Experimental results are based on legacy commercial 90nm PCM chips as well as on accurate HW emulation of next generation PCM chips.

Neuromorphic systems increasingly attract research interest owing to their ability to provide biologically inspired methods of computing, alternative to the classic von Neumann architecture. In these systems, computing relies on spike-based communication between neurons, and memory is represented by evolving states of the synaptic interconnections. In this work, we first demonstrate how spike-timing-dependent plasticity (STDP) based synapses can be realized using the crystal-growth dynamics of phase-change memristors. Then, we present a novel learning architecture comprising an integrate-and-fire neuron and an array of phase-change synapses that is capable of detecting temporal correlations in parallel input streams. We demonstrate a continuous re-learning operation on a sequence of binary 20×20 pixel images in the presence of significant background noise. Experimental results using an array of phase-change cells as synaptic elements confirm the functionality and performance of the proposed learning architecture.

The explosion of data volumes in enterprise environments and limited budgets have triggered the need for multi-tiered storage systems. With the bulk of the data being extremely infrequently accessed, tape is a natural fit for storing such data. In this paper we present our approach to a file storage system that seamlessly integrates disk and tape, enabling a bottomless and cost-effective storage architecture that can scale to accommodate Big Data requirements. The proposed system offers access to data through a POSIX filesystem interface under a single global namespace, optimizing the placement of data across disk and tape tiers. Using a self-contained, standardized and open filesystem format on the removable tape media, the proposed system avoids dependence on proprietary software and external metadata servers to access the data stored on tape. By internally managing the tape tier resources, such as tape drives and cartridges, the system relieves the user from the burden of dealing with the complexities of tape storage. Our implementation, which is based on the GPFS and LTFS filesystems, demonstrates the applicability of the proposed architecture in real-world environments. Our experimental evaluation has shown that this is a very promising approach in terms scalability, performance and manageability. The proposed system has been productized by IBM as LTFS Enterprise Edition.

NAND flash memory is not only the ubiquitous storage medium in consumer applications but has also started to appear in enterprise storage systems as well. MLC and TLC flash technology made it possible to store multiple bits in the same silicon area as SLC, thus reducing the cost per amount of data stored. However, at current sub-20nm technology nodes, MLC flash devices fail to provide the levels of raw reliability, mainly cycling endurance, that are required by typical enterprise applications. Advanced signal processing and coding schemes are needed to improve the flash bit error rate and thus elevate the device reliability to the desired level. In this article, we report on the use of adaptive voltage thresholds and cell-to-cell interference cancellation in the read operation of NAND flash devices. We discuss how the optimal read voltage thresholds can be determined and assess the benefit of cancelling cell-to-cell interference in terms of cycling endurance, data retention, and resilience to read disturb.

NAND Flash memory is not only the ubiquitous storage medium in consumer applications, but has also started to appear in enterprise storage systems as well. MLC and TLC Flash technology made it possible to store multiple bits in the same silicon area as SLC, thus reducing the cost per amount of data stored. However, at current sub-20nm technology nodes, MLC Flash devices fail to provide the levels of raw reliability, mainly cycling endurance, that are required by typical enterprise applications. Advanced signal-processing and coding schemes are needed to improve the Flash bit error rate and thus elevate the device reliability to the desired level. In this paper, we report on the use of adaptive voltage thresholds in the read operation of NAND Flash devices. We discuss how the optimal read voltage thresholds can be determined, and assess the benefit of adapting the read voltage thresholds in terms of cycling endurance, data retention and resilience to read disturb.

Phase-change memory (PCM) has emerged as one among the most promising technologies for next-generation non-volatile solid-state memory. Multilevel storage, namely storage of non-binary information in a memory cell, is a key factor for reducing the total cost-per-bit and thus increasing the competiveness of PCM technology in the nonvolatile memory market. In this paper, we present a family of advanced programming schemes for multilevel storage in PCM. The proposed schemes are based on iterative write-and-verify algorithms that exploit the unique programming characteristics of PCM in order to achieve significant improvements in resistance-level packing density, robustness to cell variability, programming latency, energy- per-bit and cell storage capacity. Experimental results from PCM test-arrays are presented to validate the proposed programming schemes. In addition, the reliability issues of multilevel PCM in terms of resistance drift and read noise are discussed.

This paper presents a data-placement scheme for log-structured flash translation layers (FTLs), with the dual aims of reducing write amplification due to garbage collection and flash wear-out due to block erasing and programming. The central idea is to identify and place data that is expected to change frequently together in young flash blocks that are far from wearing out, and infrequently changing data in old blocks where it can be expected to stay longer. In previous work, garbage collection and wear levelling were treated separately, and the importance of data placement was largely ignored. We propose a new scheme, called container marking, to combine data placement, garbage collection, and wear levelling in a single mechanism, thus improving both the random write performance and the endurance. Each flash block is a data container that is assigned an activeness marker indicating how frequently the data it stores is updated. A simple solution for dynamically tracking data's activeness that adapts to utilizations is presented. The system is implemented in a Java1-based flash simulator, and is shown to reduce write amplification and wear-out in synthetic and trace-driven workloads.

Two schemes proposed to cope with unrecoverable or latent media errors and enhance the reliability of RAID systems are examined. The first scheme is the established, widely used, disk scrubbing scheme, which operates by periodically accessing disk drives to detect media-related unrecoverable errors. These errors are subsequently corrected by rebuilding the sectors affected. The second scheme is the recently proposed intradisk redundancy scheme, which uses a further level of redundancy inside each disk, in addition to the RAID redundancy across multiple disks. A new model is developed to evaluate the extent to which disk scrubbing reduces the unrecoverable sector errors. The probability of encountering unrecoverable sector errors is derived analytically under very general conditions regarding the characteristics of the read/write process of uniformly distributed random workloads and for a broad spectrum of disk scrubbing schemes, which includes the deterministic and random scrubbing schemes. We show that the deterministic scrubbing scheme is the most efficient one. We also derive closed-form expressions for the percentage of unrecoverable sector errors that the scrubbing scheme detects and corrects, the throughput performance, and the minimum scrubbing period achievable under operation with random, uniformly distributed I/O requests. Our results demonstrate that the reliability improvement due to disk scrubbing depends on the scrubbing frequency and the load of the system, and, for heavy-write workloads, may not reach the reliability level achieved by a simple interleaved parity-check (IPC)-based intradisk redundancy scheme, which is insensitive to the load. In fact, for small unrecoverable sector error probabilities, the IPC-based intradisk redundancy scheme achieves essentially the same reliability as that of a system operating without unrecoverable sector errors. For heavy loads, the reliability achieved by the scrubbing scheme can be orders of magnitude less than that of the intradisk redundancy scheme. Finally, the I/O and throughput performances are evaluated by means of analysis and event-driven simulation.

Probe-storage devices employ large arrays of probes to write/read data in parallel in some storage medium, and combine ultra-high density, low access times, and low power consumption. A particular probe-storage technique utilizes thermomechanical means to store and retrieve information in thin polymer films. In this paper, a system-level channel model for the thermomechanical probe-storage channel is presented. Each of the components of the proposed model is derived by extensive characterization of experimentally obtained readback signals from probe recording tests. Moreover, detection techniques that are actually utilized in a probe-storage prototype implementation are described, followed by coding techniques for added reliability in the presence of particles or other impurities of the storage medium. In addition to low-complexity coding constructs, a concatenated coding scheme with an outer LDPC and inner modulation code is considered, in order to establish a benchmark for overall system performance. A novel methodology for joint decoding of outer LDPC and inner (d,k) modulation codes is developed. Furthermore, an optimal soft decoder for the modulation code is proposed, based on a modification of the decoder metrics to accurately account for the probe storage channel output statistics. Experimental results are used throughout the paper to validate the channel model and identify its relevant parameters, as well as to verify the system performance obtained by simulations.

Frame synchronization is studied for pulse-position modulation-encoded longitudinal position (LPOS) words that are embedded in servo patterns written on tape. After introducing soft-output detection of LPOS symbols, the problem of LPOS frame synchronization using soft outputs from the LPOS detector is considered. An efficient LPOS frame-synchronization algorithm that is robust in the presence of transition noise found in magnetic recording channels is then proposed. Finally, the performance of hard-decision LPOS frame synchronization is compared by simulations with that of the proposed soft-decision algorithm, and a hardware implementation of the overall scheme is illustrated.

This paper studies loop-delay compensation as a means to improve the robustness of timing recovery loops in tape storage systems. The delay compensation scheme is derived under fairly general assumptions and is found to match a known Kalman-filtering-based solution if a random-walk model of frequency-offset evolution is assumed. Extensions of the scheme to achieve delay compensation in multichannel tape-drive systems that employ global timing control are presented. The practical effectiveness of delay compensation is demonstrated using actual readback waveforms captured on commercial tape drives.

Write amplification is a critical factor limiting the random write performance and write endurance in storage devices based on NAND-flash memories such as solid-state drives (SSD). The impact of garbage collection on write amplification is influenced by the level of over-provisioning and the choice of reclaiming policy. In this paper, we present a novel probabilistic model of write amplification for log-structured flash-based SSDs. Specifically, we quantify the impact of over-provisioning on write amplification analytically and by simulation assuming workloads of uniformly-distributed random short writes. Moreover, we propose modified versions of the greedy garbage-collection reclaiming policy and compare their performance. Finally, we analytically evaluate the benefits of separating static and dynamic data in reducing write amplification, and how to address endurance with proper wear leveling.

Reverse concatenation (RC) architectures, which recently have been deployed in hard-disk-drive (HDD) products, offer crucial advantages in coding such as (i) avoiding error propagation through the modulation decoder, (ii) allowing the use of efficient high-rate modulation codes, and (iii) passing of soft information from the detector to the decoder, which facilitates parity-post processing and iterative coding schemes. In HDDs, error-correcting codes essentially consist of a single high-rate Reed-Solomon code, whereas in tape recording, large product codes are used that require a new RC architecture. Such a novel RC architecture for product codes is presented and illustrated by an example based on the linear tape open standard, generation 4 (LTO-4). Compared with the rate-16/17 modulation code of the LTO-4 standard, the proposed RC scheme has a modulation scheme of rate 0.9951, i.e., achieves 5.7% improvement in rate while maintaining the same interleaved I = 11 modulation constraint, but at the cost of a slight weakening of the G-constraint.

Two schemes proposed to cope with unrecoverable or latent media errors and enhance the reliability of RAID systems are examined. The first scheme is the established, widely used disk scrubbing scheme, which operates by periodically accessing disk drives to detect media-related unrecoverable errors. These errors are subsequently corrected by rebuilding the sectors affected. The second scheme is the recently proposed intradisk redundancy scheme which uses a further level of redundancy inside each disk, in addition to the RAID redundancy across multiple disks. Analytic results are obtained assuming Poisson arrivals of random I/O requests. Our results demonstrate that the reliability improvement due to disk scrubbing depends on the scrubbing frequency and the workload of the system, and may not reach the reliability level achieved by a simple IPC-based intra-disk redundancy scheme, which is insensitive to the workload. In fact, the IPC-based intra-disk redundancy scheme achieves essentially the same reliability as that of a system operating without unrecoverable sector errors. For heavy workloads, the reliability achieved by the scrubbing scheme can be orders of magnitude less than that of the intra-disk redundancy scheme.

Today's data storage systems are increasingly adopting low-cost disk drives that have higher capacity but lower reliability, leading to more frequent rebuilds and to a higher risk of unrecoverable media errors. We propose an efficient intradisk redundancy scheme to enhance the reliability of RAID systems. This scheme introduces an additional level of redundancy inside each disk, on top of the RAID redundancy across multiple disks. The RAID parity provides protection against disk failures, whereas the proposed scheme aims to protect against media-related unrecoverable errors. In particular, we consider an intradisk redundancy architecture that is based on an interleaved parity-check coding scheme, which incurs only negligible I/O performance degradation. A comparison between this coding scheme and schemes based on traditional Reed--Solomon codes and single-parity-check codes is conducted by analytical means. A new model is developed to capture the effect of correlated unrecoverable sector errors. The probability of an unrecoverable failure associated with these schemes is derived for the new correlated model, as well as for the simpler independent error model. We also derive closed-form expressions for the mean time to data loss of RAID-5 and RAID-6 systems in the presence of unrecoverable errors and disk failures. We then combine these results to characterize the reliability of RAID systems that incorporate the intradisk redundancy scheme. Our results show that in the practical case of correlated errors, the interleaved parity-check scheme provides the same reliability as the optimum, albeit more complex, Reed--Solomon coding scheme. Finally, the I/O and throughput performances are evaluated by means of analysis and event-driven simulation.

A reverse concatenation scheme based on an efficient modulation encoder satisfying non-uniform constraints, a systematic Reed-Solomon encoder and a partial symbol interleaver is presented. This architecture achieves very tight modulation constraints and minimizes error propagation and rate loss. The modulation constraints considered are of the same type as the constraints that have been used in generalized partial-response maximum-likelihood (PRML) detection systems. A class of codes that is based on serial concatenation of a prefix-constrained code and two interleaved enumerative codes with non-uniform constraints is proposed. Specific rate-199/200 PRML(G, I) codes are constructed.

Scanning-probe data storage is emerging as a viable alternative to conventional data storage, offering ultra-high density, low access times, and low power consumption. One probe-storage technique utilizes a thermomechanical means to store and retrieve information in thin polymer films. We describe the readback signal path and characterize the thermomechanical-based probe-storage recording channel. It is shown that this channel exhibits a particular nonlinear behavior at high storage densities or high recording power, that is, the energy per unit time used to write a bit of information. A simple model is proposed that accurately captures the characteristics of this nonlinearity. Experimental results from single-probe recording setups are used to verify the validity of this model and identify its relevant parameters.

In this paper, we present an analytical method to compute the performance of product codes on channels with memory. A channel with memory introduces correlated error bursts, and hence, it is described as hidden Markov models. A hard-decision distance-bounded decoder for product code is assumed. Such an analysis is relevant for evaluating the performance of product-code-based error-correcting scheme employed in conventional tape drive systems. Using this analytical method, we present codeword-error rate plots for various Reed-Solomon codes based product codes

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.

We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.

Efficient combination of a modulation code with a parity-check code is studied for magnetic recording systems. A new approach to the design of combined modulation/parity codes that largely retains the properties of the original modulation code is proposed. It is based on the matrix transformation of a set of desired parity-check equations at the partial-response channel input into a set of parity-check equations at the input of the precoder. The code design methodology is illustrated by constructing a rate-96/104 dual-parity code that satisfies maximum transition run constraints. Simulation results for a Lorentzian recording channel show that this code significantly outperforms a single-parity code for channels dominated by electronics noise. Moreover, the rate-96/104 dual-parity code, which has been used extensively in commercial disk drives, performs as well as a single-parity code in stationary/nonstationary data-dependent noise conditions. Finally, the low-average-transition-density constraint is proposed to enhance error-rate performance in channels dominated by transition noise.

We derive the average symbol and Hamming weight spectrum functions of the random ensemble of regular low-density parity-check (LDPC) codes over GF(2/sup b/) when used with the binary-input noisy channel. This work confirms theoretically that the near-Shannon-limit performance of Gallager's binary LDPC codes can be significantly enhanced by moving to fields of higher order. We construct a family of error-correcting codes based on the binary representation of GF(2/sup b/) codes defined on a cycle Tanner graph that appears to be "good" for both optimum and iterative decoding over the binary-input noisy channel. In particular, we report a short-block-length (1008 bits), rate-1/2 progressive-edge-growth-based cycle Tanner-graph code over GF(2/sup b/) with a block-error rate <10/sup -4/ at E/sub b//N/sub 0/=1.89 dB, which appears to exhibit the best iterative-decoding performance at this short block length known to date.

Low-density parity-check (LDPC) codes in their broader-sense definition are linear codes whose parity-check matrices have fewer 1s than 0s. Finding their minimum distance is therefore in general an NP-hard problem. We propose a randomized algorithm called nearest nonzero codeword search (NNCS) approach to tackle this problem for iteratively decodable LDPC codes. The principle of the NNCS approach is to search codewords locally around the all-zero codeword perturbed by minimal noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum-Hamming- weight codeword whose Hamming weight is equal to the minimum distance of the linear code. This approach has its roots in Berrou et al.'s error-impulse method and a form of Fossorier's list decoding for LDPC codes.

We propose a family of randomized approximate algorithms, called nearest nonzero codewords search (NNCS), for computing the minimum distance of low-density parity-check (LDPC) codes, including Gallager-type and finite-geometry-type codes.

An information-theoretic method is presented for computing information rates of magnetic recording channels with medium noise, assuming 0.5-Bernoulli as well as optimized Markov input processes. The method is based on the well-known conjectured Shamai-Laroia bound. The compound behavior of the magnetic recording channel is modelled by combining the Lorentzian read-back pulse, the microtrack channel model, and additive white Gaussian noise (AWGN). Numerical results are provided that show that from an information theoretic viewpoint in certain cases medium noise is preferable to AWGN.

The paper investigates the application of low-density parity-check (LDPC) codes to digital subscriber-line (DSL) transmission systems that employ discrete multitone modulation. A family of linear-time encodable binary LDPC codes that are well-suited for DSL transmission is introduced. Encoding and symbol mapping for multilevel modulation are described. Simulation results show that even under tight latency constraints good net coding gains can be achieved. Implementation complexity is analyzed and compared with that of trellis-coded modulation as employed in current asymmetric DSL transceivers. The incorporation of powerful LDPC coding techniques into next-generation DSL modems appears to be possible with reasonable increase in transceiver complexity.

A filter-bank modulation technique called filtered multitone (FMT) and its application to data transmission for very high-speed digital subscriber line technology are described. The proposed scheme leads to significantly lower spectral overlapping between adjacent subchannels than for known multicarrier techniques such as discrete multitone (DMT) or discrete wavelet multitone. FMT modulation mitigates interference due to echo and near-end crosstalk signals, and increases the system throughput and reach. Signal equalization in an FMT receiver is accomplished in the form of per-subchannel symbol-spaced or fractionally spaced linear or decision-feedback equalization. The problem of channel coding for this type of modulation is also addressed, and an approach that allows combined removal of intersymbol-interference via precoding and trellis coding is described. Furthermore, practical design aspects regarding filter-bank realization, initial transceiver training, adaptive equalization, and timing recovery are discussed. Finally, simulation results of the performance achieved by FMT modulation for very high-speed digital subscriber line systems, where upstream and downstream signals are separated by frequency-division duplexing, are presented and compared with DMT modulation.

We propose a general method for constructing Tanner (1981) graphs with large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms or parameters of the graphs. Encoding of LDPC codes based on the PEG principle is also investigated. We show how to exploit the PEG graph construction to obtain LDPC codes that allow linear time encoding. The advantages of PEG Tanner graphs over randomly constructed graphs are demonstrated by extensive simulation results on code performance.

Efficient implementations of the sum-product algorithm (SPA) are presented for decoding low-density parity-check (LDPC) codes using log-likelihood ratios (LLR) as messages between symbol and parity-check nodes. Various reduced-complexity derivatives of the LLR-SPA are proposed. Both serial and parallel implementations are investigated, leading to trellis and tree topologies, respectively. Furthermore, by exploiting the inherent robustness of LLRs, it is shown, via simulations, that coarse quantization tables are sufficient to implement complex core operations with negligible or no loss in performance. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency and computational complexity perspective.

The performance of high-rate tail-biting convolutional codes serially concatenated with generalized partial response channels is studied. The effect of precoders on the overall performance is investigated. Extrinsic information transfer charts are used to guide the selection of appropriate tail-biting codes and precoders. Simulation results for a magnetic recording system modeled as a serial concatenation of tail-biting codes with a generalized partial response channel are presented. In particular, rate-8/9 and -16/17 short- and long-block-length tail-biting codes are studied. In the former case, hard-decision decoded interleaved Reed-Solomon (RS) codes are used as the outer-most code, whereas in the latter case the sector-size tail-biting codes replace the RS codes traditionally used in storage systems. The results indicate that high-rate tail-biting codes deliver significant performance gains when used in conjunction with a rate-1 precoder and iterative detection/decoding. The results also show that long tail-biting codes can outperform hard-decision decoding of RS codes by 2 dB at a sector error rate of approx. 10/sup -4/.

Approximations to the union bound performance of sequence detection in the presence of colored noise and an algorithm to compute bit error and error event probabilities are presented and compared to bit-by-bit simulation results. These computations, which are very accurate at bit error probabilities /spl les/10/sup -3/, are then used to analyze the performance of standard and reverse concatenated Reed-Solomon(RS)/modulation coding schemes for generalized partial-response channels corrupted by colored noise. The analysis is used to determine the optimum RS code rate for recording systems that are of current interest.

A new twins constraint for maximum transition run (MTR) codes is introduced to eliminate quasi-catastrophic error propagation in sequence detectors for generalized partial response channels with spectral nulls both at dc and at the Nyquist frequency. Two variants of the twins constraint that depend on whether the generalized partial response detector trellis is unconstrained or j-constrained are studied. Deterministic finite-state transition diagrams that present the twins constraint are specified, and the capacity of the new class of MTR constraints is computed. The connection between (G,I) constraints and MTR(j) constraints is clarified. Code design methodologies that are based on look-ahead coding in combination with violation detection/substitution as well as on state splitting are used to obtain several specific constructions of high-rate MTR codes.

A robust error control scheme for data transmission in CDMA-based cellular systems is proposed which employs outer Reed-Solomon codes concatenated with inner convolutional codes. The performance of this scheme is analyzed assuming nonperiodic random spreading sequences and a Rake receiver with perfect knowledge of the channel. In particular, a simple model for the memoryless inner coding channel that encompasses the effects of multiple access interference, self-noise and thermal noise is first derived. Using new tight upper bounds on bit- and symbol-error probabilities of convolutional codes over Nakagami, Rayleigh, and Rician fading multipath channels, the performance of the concatenated coding scheme is then evaluated. The Reed-Solomon/convolutional coding scheme has been adopted by the European RACE Project Code Division Testbed (CODIT) and implemented in an experimental testbed. The code design methodology, which has been used to specify the 9.6-, 64-, and 128-kbit/s data traffic channels of the CODIT testbed, is presented and the single-cell CDMA capacity is computed.

An error control scheme for data transmission in code division multiple access (CDMA) cellular systems is proposed. The forward error correction scheme employs Reed-Solomon (RS) outer codes concatenated with convolutional inner codes. New tight upper bounds on the convolutional code performance in independent Rayleigh fading multipath channels are derived. Using these bounds and invoking the Gaussian assumption for the multiple access interference, the performance of the concatenated coding scheme is evaluated. Furthermore, design examples of RS outer codes and convolutional inner codes for data transmission at 9.6 and 128 kbit/s in CDMA cellular systems are presented. Finally, the capacity of a CDMA cellular system employing the proposed concatenated coding scheme is computed.>

Multi level sequences with a spectral null of order M at frequency f, meaning that the power spectral density, and its first 2M-1 derivatives vanish at f, are characterized by finite-state transition diagrams (FSTDs) whose edge labels satisfy bounds on the variation of the Mth-order running digital sum (RDS). Necessary and sufficient conditions for FSTDs with higher order null constraints at DC and at an arbitrary submultiple of the symbol frequency are derived. Analytical results are given concerning the performance of codes satisfying an Mth-order RDS constraint on partial-response channels. Specific code designs for quaternary channel inputs are presented. The Euclidean distance properties of this new class of codes, aside from their spectral-shaping properties, are demonstrated.>

A novel receiver for data-transmission systems using trellis-coded modulation is investigated. It comprises a whitened-matched filter and a trellis decoder which combines the previously separated functions of equalization and trellis-coded modulation (TCM) decoding. TCM encoder, transmission channel, and whitened-matched filter are modeled by a single finite-state machine with combined intersymbol interference and code states. Using ISI-state truncation techniques and the set-partitioning principles inherent in TCM, a systematic method is then developed for reducing the state complexity of the corresponding ISI and code trellis. A modified branch metric is used for canceling those ISI terms which are not represented by the trellis states. The approach leads to a family of Viterbi decoders which offer a tradeoff between decoding complexity and performance. An adaptive version of the proposed receiver is discussed, and an efficient structure for reduced-state decoding is given. Simulation results are presented for channels with severe amplitude and phase distortion. It is shown that the proposed receiver achieves a significant gain in noise margin over a conventional receiver which uses separate linear equalization and TCM decoding.>

Data transmission at rates of 1.2 kbits/s or higher through voiceband ionospheric channels is subject to impairment from severe linear distortion, fast channel time variations, and severe fading. In this paper, we have focused on the performance of DFE (decision feedback equalization) receivers for communication over 3 kHz bandwidth HF channels. We describe the results of simulations for a wide range of fading rates on simulated and real recorded HF channels, using fractionally spaced DFE receivers. Both LMS (least mean square) and FRLS (fast recursive least squares) adaptation algorithms with periodic restart were evaluated, and both ideal-reference and decision-directed operation was observed. The results indicate that FRLS adaptation yields superior performance to LMS in rapid fading conditions, but that this performance advantage diminishes at low signal-to-noise ratios. Also, fade rates greater than about 1 Hz produced relatively high error rates, irrespective of which adaptation method was employed. Finally, a novel modification of the simple LMS algorithm which improves its tracking ability was evaluated. This involved preceding the LMS DFE receiver with an adaptive lattice whitening filter.

This paper treats analytically and experimentally the response of RLS {Recursive Least Squares} adaptive filters with exponential windows to stationary and nonstationary inputs. A new formula for the "estimation-noise" has been derived involving second- and fourth-order statistics of the filter input as well as the exponential windowing factor and filter length. Under general time-varying conditions it is shown that the time constant associated with "lag effects" depends solely on the exponential weighting parameter λ. In addition the calculation of the excess mean square error due to the lag for an assumed Markov channel provides the necessary information about tradeoffs between speed of adaptation and steady-state error. In the simple case of channel identification it is shown that the LMS and RLS adaptive filters have the same tracking behavior.

Data communication at rates near or above 2 kbits/s on 3 kHz-baadwidth HF radio channels is subject to impairment from severe linear dispersion, rapid channel time variation, and severe fading. In this investigation, recorded 2.4 kbit/s QPSK signals received from HF channels were processed to extract a time-varying estimate of the channel impulse response. From the estimated channel impulse responses, performance-related parameters were computed for ideal matched filter reception, maximum-likelihood sequence-estimation (MLSE), and decision feedback equalization (DFE). The results indicated that the simpler DFE receiver suffered only a small theoretical performance degradation relative to the more complex MLSE receiver. Other HF channel impulse response statistics were also obtained to shed light on equalization and filter adaptation techniques.