• Call for Nomination of 2011 Best Paper Awards in the area of Data Storage (Coming soon!)

• 2010 Best Paper Award on Data Storage Area

  Awardees:  A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright and K. Ramchandran ,"Network Coding for Distributed Storage Systems," IEEE Transactions on Information Theory, Vol. 56, Issue 9, Sept. 2010.

   

  Abstract: Distributed storage systems provide reliable access to data through redundancy spread over individually unreliable nodes. Application scenarios include data centers, peer-to-peer storage systems, and storage in wireless networks. Storing data using an erasure code, in fragments spread across nodes, requires less redundancy than simple replication for the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate encoded fragments in a distributed way while transferring as little data as possible across the network. For an erasure coded system, a common practice to repair from a single node failure is for a new node to reconstruct the whole encoded data object to generate just one encoded block. We show that this procedure is sub-optimal. We introduce the notion of regenerating codes, which allow a new node to communicate functions of the stored data from the surviving nodes. We show that regenerating codes can significantly reduce the repair bandwidth. Further, we show that there is a fundamental tradeoff between storage and repair bandwidth which we theoretically characterize using flow arguments on an appropriately constructed graph. By invoking constructive results in network coding, we introduce regenerating codes that can achieve any point in this optimal tradeoff.

• 2010 Best Student Paper Award on Data Storage Area

  Awardee:  Y. Cassuto, M. Schwartz, V. Bohossian, and J. Bruck, "Codes for Asymmetric Limited-Magnitude Errors With Application to Multilevel Flash Memories", IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 56, NO. 4, APRIL 2010.

   

  Abstract: Several physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This paper studies block codes for asymmetric limited-magnitude errors over q-ary channels. We propose code constructions and bounds for such channels when the number of errors is bounded by t and the error magnitudes are bounded by l. The constructions utilize known codes for symmetric errors, over small alphabets, to protect large-alphabet symbols from asymmetric limited-magnitude errors. The encoding and decoding of these codes are performed over the small alphabet whose size depends only on the maximum error magnitude and is independent of the alphabet size of the outer code. Moreover, the size of the codes is shown to exceed the sizes of known codes (for related error models), and asymptotic rate-optimality results are proved. Extensions of the construction are proposed to accommodate variations on the error model and to include systematic codes as a benefit to practical implementation.

• 2009 Best Paper Award on Data Storage Area

  Awardees:  Anxiao (Andrew) Jiang, Robert Mateescu, Moshe Schwartz, Jehoshua Bruck

  Paper:  "Rank Modulation for Flash Memories," IEEE Transactions on Information Theory, vol. 55, pp. 2659-2673, June 2009.

   

  Abstract: We explore a novel data representation scheme for multilevel flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. The only allowed charge-placement mechanism is a “push-to-the-top” operation, which takes a single cell of the set and makes it the top-charged cell. The resulting scheme eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. We present unrestricted Gray codes spanning all possible n-cell states and using only “push-to-the-top” operations, and also construct balanced Gray codes. One important application of the Gray codes is the realization of logic multilevel cells, which is useful in conventional storage solutions. We also investigate rewriting schemes for random data modification. We present both an optimal scheme for the worst case rewrite performance and an approximation scheme for the average-case rewrite performance.

• 2009 Best Student Paper Award on Data Storage Area

  Awardee:  Anantha Raman Krishnan, Rathnakumar Radhakrishnan, Bane Vasic, Aleksander Kavcic, William Ryan, Fatih Erden

  Paper:  "2-D Magnetic Recording: Read Channel Modeling," IEEE Transactions on Magnetics, vol. 45, pp. 3830-3836, October 2009.

   

  Abstract: Two-dimensional magnetic recording (TDMR) is a novel storage architecture that, in theory, can achieve a density of up to 10 Tb/in^2. It uniquely differs from other proposed next-generation architectures because of its reliance on sophisticated 2-D signal-processing algorithms. Recently, a number of contributions have been made in the development of read-channel models and detectors for TDMR systems. In this paper, we provide a detailed review on all important read-channel models under consideration. Our discussion focuses on the purpose of each model, placing a special emphasis on the suitability of the Voronoi model for the purpose of designing detectors. We also propose several detection schemes for TDMR based on the Voronoi model and present some numerical results.

• 2008 Best Paper Award on Data Storage Area

  Awardees: K. Cai and K. Immink

  Paper:  "A general construction of constrained parity-check codes for optical recording," IEEE Transactions on Communications, vol. 56, pp. 1070-1079, July 2008.

   

  Abstract: This paper proposes a general and systematic code design method to efficiently combine constrained codes with parity-check (PC) codes for optical recording. The proposed constrained PC code includes two component codes: the normal constrained (NC) code and the parity-related constrained (PRC) code. They are designed based on the same finite state machine (FSM). The rates of the designed codes are only a few tenths below the theoretical maximum. The PC constraint is defined by the generator matrix (or generator polynomial) of a linear binary PC code, which can detect any type of dominant error events or error event combinations of the system. Error propagation due to parity bits is avoided, since both component codes are protected by PCs. Two approaches are proposed to design the code in the non-return-to-zero-inverse (NRZI) format and the non-return-to-zero (NRZ) format, respectively. Designing the codes in NRZ format may reduce the number of parity bits required for error detection and simplify post-processing for error correction. Examples of several newly designed codes are illustrated. Simulation results with the Blu-Ray disc (BD) systems show that the new d = 1 constrained 4-bit PC code significantly outperforms the rate 2/3 code without parity, at both nominal density and high density.

• 2008 Best Student Paper Award on Data Storage Area

  Awardee: O. Shental, N. Shental, S. Shamai, I. Kanter, A. J. Weiss and Y. Weiss

  Paper:  "Discrete-input two dimensional Gaussian channels with memory: estimation and information rates via graphical models and statistical mechanics," IEEE Trans. Information Theory, pp. 1500-1513, Apr. 2008.

   

  Abstract: Discrete-input two-dimensional (2D) Gaussian channels with memory represent an important class of systems, which appears extensively in communications and storage. In spite of their widespread use, the workings of 2D channels are still very much unknown. In this work, we try to explore their properties from the perspective of estimation theory and information theory. At the heart of our approach is a mapping of a 2D channel to an undirected graphical model, and inferring its a posteriori probabilities (APPs) using generalized belief propagation (GBP). The derived probabilities are shown to be practically accurate, thus enabling optimal maximum a posteriori (MAP) estimation of the transmitted symbols. Also, the Shannon-theoretic information rates are deduced either via the vector-wise Shannon-McMillan-Breiman (SMB) theorem, or via the recently derived symbol-wise Guo-Shamai-Verdu (GSV) theorem. Our approach is also described from the perspective of statistical mechanics, as the graphical model and inference algorithm have their analogues in physics. Our experimental study, based on common channel settings taken from cellular networks and magnetic recording devices, demonstrates that under nontrivial memory conditions, the performance of this fully tractable GBP estimator is almost identical to the performance of the optimal MAP estimator. It also enables a practically accurate simulation-based estimate of the information rate. Rationalization of this excellent performance of GBP in the 2-D Gaussian channel setting is addressed.

• 2007 Best Paper Award on Data Storage Area

  Awardees: J.B. Soriaga, H. D. Pfister and P. H. Siegel

  Paper:  "Determing and approaching achievable rates of binary intersymbol interference channels using mulitstage decoding," IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 53, No. 4, pp. 1416- 1429, April 2007.

   

  Abstract: By examining the achievable rates of a multistage decoding system on stationary ergodic channels, we derive lower bounds on the mutual information rate corresponding to independent and uniformly distributed (i.u.d.) inputs, also referred to as the i.u.d. information rate. For binary intersymbol interference (ISI) channels, we show that these bounds become tight as the number of decoding stages increases. Our analysis, which focuses on the marginal conditional output densities at each stage of decoding, provides an information rate corresponding to each stage. These rates underlie the design of multilevel coding schemes, based upon low-density parity-check (LDPC) codes and message passing, that in combination with multistage decoding approach the i.u.d. information rate for binary ISI channels. We give example constructions for channel models that have been commonly used in magnetic recording. These examples demonstrate that the technique is very effective even for a small number of decoding stages.

• 2007 Best Student Paper Award on Data Storage Area

  Awardee: X. Hu, B. V. K. Kumar, Z. Li and R. Barndt

  Paper:  "Error floor estimation of long LDPC codes on partial response channels," in Proc. Globecom2007, pp. 259-264, Nov. 2007.

   

  Abstract: The presence of error floor in low density parity check (LDPC) codes is of great concern for potential applications of LDPC codes to data storage channels, which require the error correcting code (ECC) to maintain the near-capacity error correcting performance at frame error rate as low as 10^-12. In order to investigate the error floor of LDPC codes under partial response channels used in data storage systems, we propose a new estimation method combining analytical tools and simulation, based on the concept of trapping sets. The definition of trapping sets is based on the dominant error patterns observed in the decoding process. The goal is to accurately estimate the error rate in the error floor region for certain types of LDPC codes under the partial response channel and further extend the frame error rate down to 10^-14 or lower. Towards this goal, we first use field programmable gate array (FPGA) hardware simulation to find the trapping sets that cause the decoding failure in the error floor region. For each trapping set, we extract the parameters which are key to the decoding failure rate caused by this trapping set. Then we use a much simpler in situ hardware simulation with these parameters to obtain the conditional decoding failure rate. By considering all the trapping sets we find, we obtain the overall frame error rate in the error floor region. The estimation results for a length -4623 QC-LDPC code under the EPR4 channel are within 0.3 dB of the direct simulation results. In addition, this method allows us to estimate the frame error rate of a LDPC code down to 10^-14 or lower.

• 2006 Best Paper Award on Data Storage Area

  Awardees: Jing Jiang and Krishna R. Narayanan

  Paper:  "Iterative Soft-Input Soft-Output Decoding of Reed--Solomon Codes by Adapting the Parity-Check Matrix," IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 52, No. 8, pp. 3746- 3756, August 2006.

   

  Abstract: An iterative algorithm is presented for soft-input soft-output (SISO) decoding of Reed-Solomon (RS) codes. The proposed iterative algorithm uses the sum-product algorithm (SPA) in conjunction with a binary parity-check matrix of the RS code. The novelty is in reducing a submatrix of the binary parity-check matrix that corresponds to less reliable bits to a sparse nature before the SPA is applied at each iteration. The proposed algorithm can be geometrically interpreted as a two-stage gradient descent with an adaptive potential function. This adaptive procedure is crucial to the convergence behavior of the gradient descent algorithm and, therefore, significantly improves the performance. Simulation results show that the proposed decoding algorithm and its variations provide significant gain over hard-decision decoding (HDD) and compare favorably with other popular soft-decision decoding methods.

• 2006 Best Student Paper Award on Data Storage Area

  Awardee: Riccardo Pighi, Riccardo Raheli and Umberto Amadei

  Paper:  "Multidimensional Signal Processing and Detection for Storage Systems with Data-Dependent Transition Noise," IEEE TRANSACTIONS ON MAGNETICS, vol. 42, No. 7, pp. 1905-1916, July 2006.

   

  Abstract: In the last decade, significant research on detection algorithms capable of mitigating the effects of colored Gaussian thermal noise and transition noise in storage systems, has been performed. In this paper, we present a new detection scheme based on a multidimensional detector front end and multidimensional linear prediction, applied to maximum a posteriori probability (MAP) sequence detection. This method improves the bit-error-rate (BER) performance with respect to previous approaches and makes the detector quite insensitive to transition noise. We show that the gain in terms of BER versus signal-to-noise ratio with our detector increases with the user density. The results obtained for a magnetic storage channel are extendable to optical storage systems as well.

   

• IEEE ICC2007 Best Paper Award in Signal Processing and Coding for Storage

Awardees: Richard Todd , J. R. Cruz

Paper: R. Todd and J. R. Cruz, "Computing Maximum-Likelihood Bounds for Reed-Solomon Codes over Partial Response Channels," University of Oklahoma

• Signal Processing for Storage 2005 Best Paper Award

Awardees: Aleksandar Kavcic, Xiao Ma, Nedeljko Varnica

Paper: A. Kavcic, X. Ma, N. Varnica, "Matched Information Rate Codes for Partial Response Channels," IEEE Transactions on Information Theory, vol. 51, pp. 973-989, March 2005

 

Abstract: In this paper, we design capacity-approaching codes for partial response channels. The codes are constructed as concatenations of inner trellis codes and outer low-density parity- check (LDPC) codes. Unlike previous constructions of trellis codes for partial response channels, we disregard any algebraic properties (e.g., the minimum distance or the run-length limit) in our design of the trellis code. Our design is purely probabilistic in that we construct the inner trellis code to mimic the transition probabilities of a Markov process that achieves a high (capacity-approaching) information rate. Hence, we name it a matched information rate (MIR) design. We provide a set of five design rules for constructions of capacity-approaching MIR inner trellis codes. We optimize the outer LDPC code using density evolution tools specially modified to fit the superchannel consisting of the inner MIR trellis code concatenated with the partial response channel. Using this strategy, we design degree sequences of irregular LDPC codes whose noise tolerance thresholds are only fractions of a decibel away from the capacity. Examples of code constructions are shown for channels both with and without spectral s.

• Signal Processing for Storage 2005 Best Student Paper Award

Awardee: Shaohua Yang

Paper: S. Yang, A. Kavcic, S. Tatikonda, "The Feedback Capacity of Finite-State Machine Channels," IEEE Transactions on Information Theory, vol. 51, pp. 799-810, March 2005.

 

Abstract: We consider a finite-state machine channel with a finite memory length (e.g., finite length intersymbol interference channels with finite input alphabets-also known as partial response channels). For such a finite-state machine channel, we show that feedback-dependent Markov sources achieve the feedback capacity, and that the required memory length of the Markov process matches the memory length of the channel. Further, we show that the whole history of feedback is summarized by the causal posterior channel state distribution, which is computed by the sum-product forward recursion of the Bahl-Cocke-Jelinek-Raviv (BCJR) (Baum-Welch, discrete-time Wonham filtering) algorithm. These results drastically reduce the space over which the optimal feedback-dependent source distribution needs to be sought. Further, the feedback capacity computation may then be formulated as an average-reward-per-stage stochastic control problem, which is solved by dynamic programming. With the knowledge of the capacity-achieving source distribution, the value of the capacity is easily estimated using Markov chain Monte Carlo methods. When the feedback is delayed, we show that the feedback capacity can be computed by similar procedures. We also show that the delayed feedback capacity is a tight upper bound on the feedforward capacity by comparing it to tight existing lower bounds. We demonstrate the applicability of the method by computing the feedback capacity of partial response channels and the feedback capacity of run-length-limited (RLL) sequences over binary symmetric channels (BSCs).

• Past Winners of Best Student Paper Award 

          Year 2004:  Zheng Zhang          

Title: "Achievable information rates and coding for MIMO systems over ISI channels and frequency-selective fading channels,"  IEEE Trans. Commun., vol. 52, pp. 1698-1710, Oct. 2004.
        

Abstract: We introduce a simulation-based method to compute the information rates of intersymbol interference (ISI) channels with additive colored Gaussian noise and/or signal-dependent Gaussian noise when the inputs are binary and independent identically distributed. The method extends the idea advanced by Arnold and Loeliger (2001), which focuses on the ISI channels with additive white Gaussian noise (AWGN). With the new method, we can compute the information rates of the Lorentzian channel with media noise that represents a suitable model for practical magnetic recording channels. We illustrate the use of the technique via several examples and show that media noise is preferable to AWGN in terms of the achievable information rates, at low signal-to-noise ratios, in particular. We also present examples of turbo codes for Lorentzian channels with media noise and compare the performance with the achievable information rates. The results demonstrate, not surprisingly, that improved detectors are necessary to achieve the channel capacity for magnetic recording channels when the media noise is dominant.

         Year 2001:  Dieter Arnold          

Title: "On the information rate of binary-input channels with memory,"  ICC 2001, Helsinki, Finland.
        

Abstract: The entropy rate of a finite-state hidden Markov model can be estimated by forward sum-product trellis processing (i.e., the forward recursion of the Baum-Welch/BCJR algorithm) of simulated model output data. This can be used to compute information rates of binary-input AWGN channels with memory.