Information theory of massively parallel probe storage channels

Oliver Hambrey, Thomas P. Parnell, Oleg V. ZaboronskiarXiv 2011 · OpenReview

TL;DR

This paper investigates the theoretical limits of information storage in massively parallel probe storage systems, like IBM's Millipede. They reveal that global positioning errors, common at the nanoscale, create strong correlations between probes, leading to an inherent "error floor" for standard error correction codes. This suggests that future probe storage systems will require sophisticated interleaving techniques to achieve reliable data retrieval.

What Problem Does This Paper Address?

The paper tackles the challenge of reliable data storage in emerging nanoscale technologies like probe storage. These systems utilize arrays of thousands of tiny probes to read and write data at extremely high densities. However, at this scale, precise positioning of the entire probe array is difficult, leading to "global jitter" – a shared error in probe positions. This global jitter introduces long-range correlations between the signals read by individual probes, making traditional error correction methods, designed for independent errors, perform poorly and exhibit an "error floor" where errors can no longer be reduced below a certain level, regardless of signal strength or code complexity. The authors aim to understand the fundamental information-theoretic limits imposed by this global jitter and explore the potential for effective error correction.

Methods

The authors develop a mathematical model for the "global jitter channel," which captures the effects of correlated positioning errors. They derive an asymptotically optimal low-complexity detector (the LLN-detector) that leverages the law of large numbers to estimate the global jitter and improve detection accuracy. They then analyze the performance of Reed-Solomon codes, a common choice for error correction, under this channel model, both through simulations and theoretical analysis using large deviation theory and Chernoff bounds. To establish fundamental limits, they calculate the Shannon capacity of the global jitter channel and the random coding bound. Finally, they prove the non-existence of effective non-interleaved error correction codes for this channel and discuss the requirements for capacity-achieving codes, emphasizing the need for interleaving.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and simulation rather than empirical data from a specific probe storage device.

Key Insights and Ideas

  • Global Jitter is the Bottleneck: The core insight is that global positioning errors, not individual probe noise, are the primary limiter for massively parallel probe storage. These correlated errors fundamentally alter the channel's properties.
  • The Inherent "Error Floor": Standard error correction codes, like Reed-Solomon, exhibit an "error floor" – a minimum bit error rate that cannot be overcome, even with stronger signals or more complex codes. This is a direct consequence of the global jitter.
  • LLN-Detector for Improved Detection: A novel LLN-detector is proposed, which uses the collective output of all probes to estimate the global jitter, leading to significantly better detection performance than treating each probe independently.
  • Capacity Approaches 1 Bit, But Slowly: While the channel capacity does approach 1 bit per probe in the limit of low noise, this convergence is polynomial, not exponential, meaning it's a slow process heavily influenced by jitter.
  • Interleaving is Crucial: The paper strongly suggests that to achieve reliable communication, error correction codes must interleave data across multiple time samples, effectively spreading the impact of rare, strong jitter events.

Key Results

  • The LLN-detector achieves near-optimal performance, virtually indistinguishable from a "Genie-assisted" detector that knows the jitter value.
  • Reed-Solomon codes applied to the global jitter channel exhibit an error floor that is independent of block size and only weakly dependent on code rate.
  • The Shannon capacity of the global jitter channel approaches 1 bit per probe as additive noise decreases, but this convergence is polynomial in the noise strength.
  • The random coding bound for non-interleaved codes also shows an error floor, suggesting this is a fundamental limitation of non-interleaved approaches.
  • The paper proves the non-existence of effective non-interleaved error correction codes for the global jitter channel with positive rates.
  • Capacity-achieving codes for this channel would require significant interleaving, potentially leading to block sizes on the order of 10^6 bits.

Limitations and Future Work

  • Weak Noise and Jitter Assumption: Some analytical results, particularly for capacity and error floor estimation, rely on assumptions of weak additive noise and weak jitter. While reasonable for some applications, this might limit their applicability in extreme conditions.
  • Theoretical Focus: The paper is primarily theoretical, focusing on information-theoretic limits. While it provides strong guidance, practical implementation challenges of achieving the proposed interleaving schemes are not fully detailed.
  • Future Work: The authors suggest further investigation into the complexity of capacity-achieving codes, particularly interleaved codes. They also mention the possibility of re-reading data following strong jitter events as a practical mitigation strategy, though this would likely reduce throughput. The paper also highlights the need for robust signal detection algorithms in the presence of strong correlations.

Summary updated

Abstract

Motivated by the concept of probe storage, we study the problem of information retrieval using a large array of N nano-mechanical probes, N ~ 4000. At the nanometer scale it is impossible to avoid errors in the positioning of the array, thus all signals retrieved by the probes of the array at a given sampling moment are affected by the same amount of random position jitter. Therefore a massively parallel probe storage device is an example of a noisy communication channel with long range correlations between channel outputs due to the global positioning errors. We find that these correlations have a profound effect on the channel's properties. For example, it turns out that the channel's information capacity does approach 1 bit per probe in the limit of high signal-to-noise ratio, but the rate of the approach is only polynomial in the channel noise strength. Moreover, any error correction code with block size N >> 1 such that codewords correspond to the instantaneous outputs of the all probes in the array exhibits an error floor independently of the code rate. We illustrate this phenomenon explicitly using Reed-Solomon codes the performance of which is easy to simulate numerically. We also discuss capacity-achieving error correction codes for the global jitter channel and their complexity.
BibTeX
@misc{hambrey2011information,
  author = {Oliver Hambrey and Thomas P. Parnell and Oleg V. Zaboronski},
  title = {{Information theory of massively parallel probe storage channels}},
  year = {2011},
  eprint = {1102.0540},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1102.0540},
}
Figure