Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Erasure”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 91 records · Page 5

Stable Symmetry-Protected Topological Phases in Systems with Heralded Noise

Here, we present a family of local quantum channels whose steady-states exhibit stable mixed-state symmetry-protected topological (SPT) order. Motivated by recent experimental progress on "erasure conversion" techniques that allow one to identify ($\textit{herald}$) decoherence processes, we consider open systems with biased erasure noise, which leads to strongly symmetric heralded errors. We utilize this heralding to construct a local correction protocol that effectively confines errors into short-ranged pairs in the steady-state. Using a combination of numerical simulations and mean-field analysis, we show that our protocol stabilizes SPT order against a sufficiently low rate of decoherence. As the rate of heralded noise increases, SPT order is eventually lost through a directed percolation transition. We further find that while introducing unheralded errors destroys SPT order in the limit of long length- and time-scales, the correction protocol is sufficient for ensuring that local SPT order persists, with a correlation length that diverges as $\xi \sim (1-f_e)^{-1/2}$, where $f_e$ is the fraction of errors that are heralded.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

RAPIDS: Reconciling Availability, Accuracy, and Performance in Managing Geo-Distributed Scientific Data

In modern science, big data plays an increasingly important role. Many scientific applications, such as running simulations on supercomputers or conducting experiments on advanced instruments, produce huge amount of data at unprecedented speed. Analyzing and understanding such big data is the key for scientists to make scientific breakthroughs. However, data might become unavailable for scientists to access when outages or maintenance of the storage system occur, which severely hinders scientific discovery. To improve the data availability, data duplication and erasure coding (EC) are often used. But as the scientific data gets larger, using these two methods can cause considerable storage and network overhead.In this paper, we propose RAPIDS, a hybrid approach that combines the multigrid-based error-bounded lossy compression with erasure coding, to significantly reduce the storage and network overhead required for maintaining high data availability. Our experiments show that RAPIDS reduces the storage overhead by up to 7.5x and network overhead by up to 3x to achieve the same level of availability compared to the regular EC method. We improve RAPIDS by building two models to optimize the fault tolerance configurations and data gathering strategy. We demonstrate that RAPIDS significantly improves performance when running on many CPU cores in parallel or on GPUs.

Wan, Lipeng↗

Capacity, cutoff rate, and coding for a direct-detection optical channel

It is shown that Pierce's pulse position modulation scheme with 2 to the L pulse positions used on a self-noise-limited direct detection optical communication channel results in a 2 to the L-ary erasure channel that is equivalent to the parallel combination of L completely correlated binary erasure channels. The capacity of the full channel is the sum of the capacities of the component channels, but the cutoff rate of the full channel is shown to be much smaller than the sum of the cutoff rates. An interpretation of the cutoff rate is given that suggests a complexity advantage in coding separately on the component channels. It is shown that if short-constraint-length convolutional codes with Viterbi decoders are used on the component channels, then the performance and complexity compare favorably with the Reed-Solomon coding system proposed by McEliece for the full channel. The reasons for this unexpectedly fine performance by the convolutional code system are explored in detail, as are various facets of the channel structure.

Massey, J. L.↗

Maximizing throughput over an average-power-limited and band-limited optical pulse position modulation channel

Given an optical pulse position modulation (PPM) channel, with an average power constraint and a bandwidth constraint, the word length needed to maximize the information throughput achievable by the channel is determined. It is shown that, to achieve the maximal capacity, the channel must be operated with a high erasure probability. This implies that coding schemes capable of compensating for a high percentage of erasures are needed for the PPM channel.

Zwillinger, D.↗

A decoding failure test for the transform decoder of Reed-Solomon code

Using a finite field transform, a transform decoding algorithm is able to correct erasures as well as errors of any (n,k,d) Reed-Solomon code over the finite field GF(q). A pitfall of transform decoding and how to avoid it are discussed. A simple test is given so that the decoder fails to decode instead of introducing additional errors, whenever the received word contains too many errors and erasures.

Miller, R. L.↗

A PPM modulator and demodulator for the 2.5 bit/detected photon demonstration

In addition to performing the basic pulse position modulation and demodulation, the hardware described also indicates the occurrence of erasures and errors of various types. The analyzer portion of the circuit counts the number of pulses received in a word, demodulates a second input pulse (if one is received), indicates the occurrence of erasures, and detects PPM word errors. Word errors are detected by comparing the modulator input word to the corresponding demodulator output. These functions are provided mainly for testing and diagnosis of the system during the feasibility demonstration period.

Marshall, W. K.↗

Capacity, cutoff rate, and coding for a direct-detection optical channel

It is shown that when Pierce's pulse-position modulation scheme with 2 to the L power positions (where L is some positive integer) is used on a self-noise-limited direct-detection optical communication channel, there results a (2 to the L power)-ary erasure channel that is equivalent to the parallel combination of L completely correlated binary erasure channels. The capacity of the full channel is the sum of the capacities of the component channels, but the cutoff rate of the full channel is shown to be much smaller than the sum of the cutoff rates. An interpretation of the cutoff rate is given that suggests a complexity advantage in coding separately on the component channels. It is shown that if short-constraint length convolutional codes with Viterbi decoders are used on the component channels, then the performance and complexity compare favorably with the Reed-Solomon coding system proposed by McEliece (1979) for the full channel. The reasons for this unexpectedly fine performance by the convolutional code system are explored in detail, as are various facets of the channel structure.

Massey, J. L.↗

Single-Chip VLSI Reed-Solomon Decoder

Efficient utilization of computing elements reduces size while preserving throughput. VLSI architecture is pipeline Reed-Solomon decoder for correction of errors and erasures. Uses transform circuit to compute syndrome polynomial. Erasure information enters decoder as binary sequence. Applied to variety of digital communications involving error-correcting RS codes.

Shao, Howard M.↗

The design plan of a VLSI single chip (255, 223) Reed-Solomon decoder

The very large-scale integration (VLSI) architecture of a single chip (255, 223) Reed-Solomon decoder for decoding both errors and erasures is described. A decoding failure detection capability is also included in this system so that the decoder will recognize a failure to decode instead of introducing additional errors. This could happen whenever the received word contains too many errors and erasures for the code to correct. The number of transistors needed to implement this decoder is estimated at about 75,000 if the delay for received message is not included. This is in contrast to the older transform decoding algorithm which needs about 100,000 transistors. However, the transform decoder is simpler in architecture than the time decoder. It is therefore possible to implement a single chip (255, 223) Reed-Solomon decoder with today's VLSI technology. An implementation strategy for the decoder system is presented. This represents the first step in a plan to take advantage of advanced coding techniques to realize a 2.0 dB coding gain for future space missions.

Hsu, I. S.↗

The decoding of Reed-Solomon codes

Reed-Solomon (RS) codes form an important part of the high-rate downlink telemetry system for the Magellan mission, and the RS decoding function for this project will be done by DSN. Although the basic idea behind all Reed-Solomon decoding algorithms was developed by Berlekamp in 1968, there are dozens of variants of Berlekamp's algorithm in current use. An attempt to restore order is made by presenting a mathematical theory which explains the working of almost all known RS decoding algorithms. The key innovation that makes this possible is the unified approach to the solution of the key equation, which simultaneously describes the Berlekamp, Berlekamp-Massey, Euclid, and continued fractions approaches. Additionally, a detailed analysis is made of what can happen to a generic RS decoding algorithm when the number of errors and erasures exceeds the code's designed correction capability, and it is shown that while most published algorithms do not detect as many of these error-erasure patterns as possible, by making a small change in the algorithms, this problem can be overcome.

Mceliece, R. J.↗

Hold-up power supply for flash memory

A hold-up power supply for flash memory systems is provided. The hold-up power supply provides the flash memory with the power needed to temporarily operate when a power loss exists. This allows the flash memory system to complete any erasures and writes, and thus allows it to shut down gracefully. The hold-up power supply detects when a power loss on a power supply bus is occurring and supplies the power needed for the flash memory system to temporally operate. The hold-up power supply stores power in at least one capacitor. During normal operation, power from a high voltage supply bus is used to charge the storage capacitors. When a power supply loss is detected, the power supply bus is disconnected from the flash memory system. A hold-up controller controls the power flow from the storage capacitors to the flash memory system. The hold-up controller uses feedback to assure that the proper voltage is provided from the storage capacitors to the flash memory system. This power supplied by the storage capacitors allows the flash memory system to complete any erasures and writes, and thus allows the flash memory system to shut down gracefully.

Ott, William E.↗

Some Improvements in Utilization of Flash Memory Devices

Two developments improve the utilization of flash memory devices in the face of the following limitations: (1) a flash write element (page) differs in size from a flash erase element (block), (2) a block must be erased before its is rewritten, (3) lifetime of a flash memory is typically limited to about 1,000,000 erases, (4) as many as 2 percent of the blocks of a given device may fail before the expected end of its life, and (5) to ensure reliability of reading and writing, power must not be interrupted during minimum specified reading and writing times. The first development comprises interrelated software components that regulate reading, writing, and erasure operations to minimize migration of data and unevenness in wear; perform erasures during idle times; quickly make erased blocks available for writing; detect and report failed blocks; maintain the overall state of a flash memory to satisfy real-time performance requirements; and detect and initialize a new flash memory device. The second development is a combination of hardware and software that senses the failure of a main power supply and draws power from a capacitive storage circuit designed to hold enough energy to sustain operation until reading or writing is completed.

Gender, Thomas K.↗

Intelligibility and Space-based Voice with Relaxed Delay Constraints

The inherent aspects and flaws surrounding space based communication is technically described and the math surrounding encoding and decoding LT Codes is examined. Utilizing LT codes as a means of reducing packet erasures due to corrupted packets on an RF link can result in higher voice quality. PESQ-MOS measure was used to analyze voice degradation over space links tested for LT codec size and number of 10ms per packet.Extensions utilizing LT codes to improve the packet erasure performance and combining the use of ASR could provide for a solid means of identifying the benefit in terms of intelligibility of voice communications in space-based networks

space communications↗

Prioritized LT Codes

The original Luby Transform (LT) coding scheme is extended to account for data transmissions where some information symbols in a message block are more important than others. Prioritized LT codes provide unequal error protection (UEP) of data on an erasure channel by modifying the original LT encoder. The prioritized algorithm improves high-priority data protection without penalizing low-priority data recovery. Moreover, low-latency decoding is also obtained for high-priority data due to fast encoding. Prioritized LT codes only require a slight change in the original encoding algorithm, and no changes at all at the decoder. Hence, with a small complexity increase in the LT encoder, an improved UEP and low-decoding latency performance for high-priority data can be achieved. LT encoding partitions a data stream into fixed-sized message blocks each with a constant number of information symbols. To generate a code symbol from the information symbols in a message, the Robust-Soliton probability distribution is first applied in order to determine the number of information symbols to be used to compute the code symbol. Then, the specific information symbols are chosen uniform randomly from the message block. Finally, the selected information symbols are XORed to form the code symbol. The Prioritized LT code construction includes an additional restriction that code symbols formed by a relatively small number of XORed information symbols select some of these information symbols from the pool of high-priority data. Once high-priority data are fully covered, encoding continues with the conventional LT approach where code symbols are generated by selecting information symbols from the entire message block including all different priorities. Therefore, if code symbols derived from high-priority data experience an unusual high number of erasures, Prioritized LT codes can still reliably recover both high- and low-priority data. This hybrid approach decides not only "how to encode" but also "what to encode" to achieve UEP. Another advantage of the priority encoding process is that the majority of high-priority data can be decoded sooner since only a small number of code symbols are required to reconstruct high-priority data. This approach increases the likelihood that high-priority data is decoded first over low-priority data. The Prioritized LT code scheme achieves an improvement in high-priority data decoding performance as well as overall information recovery without penalizing the decoding of low-priority data, assuming high-priority data is no more than half of a message block. The cost is in the additional complexity required in the encoder. If extra computation resource is available at the transmitter, image, voice, and video transmission quality in terrestrial and space communications can benefit from accurate use of redundancy in protecting data with varying priorities.

Woo, Simon S.↗

Gradient Coding With Iterative Block Leverage Score Sampling

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. Randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this study, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized ℓ 2 -subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid ℓ 2 -subspace embedding, and that our resulting approximation converges to the optimal solution.

97 MATHEMATICS AND COMPUTING↗

Prioritized LT Codes

It is common in data transmissions that some information is more important than others. This is especially true in space communications where mission critical information or science data are high priority. In this work, we propose a simple yet constructive scheme to send high priority data reliably and efficiently using Luby Transform (LT) codes. The new proposed scheme modifies the conventional LT encoder to send high priority data as a degree 1 and 2 so that high priority data can be quickly resolved and very likely recovered before a decoder stops. Preliminary results show that a carefully designed degree distribution of high priority data increases the likelihood of receiving high priority information while having negligible performance impact on data with lower priority. The performance of the proposed scheme is evaluated and compared with the conventional LT approach with the same parameters under a range of erasure error rates.

priority coding↗

Quantum error correction in the black hole interior

We study the quantum error correction properties of the black hole interior in a toy model for an evaporating black hole: Jackiw-Teitelboim gravity entangled with a non-gravitational bath. After the Page time, the black hole interior degrees of freedom in this system are encoded in the bath Hilbert space. We use the gravitational path integral to show that the interior density matrix is correctable against the action of quantum operations on the bath which (i) do not have prior access to details of the black hole microstates, and (ii) do not have a large, negative coherent information with respect to the maximally mixed state on the bath, with the lower bound controlled by the black hole entropy and code subspace dimension. Thus, the encoding of the black hole interior in the radiation is robust against generic, low-rank quantum operations. For erasure errors, gravity comes within an O (1) distance of saturating the Singleton bound on the tolerance of error correcting codes. For typical errors in the bath to corrupt the interior, they must have a rank that is a large multiple of the bath Hilbert space dimension, with the precise coefficient set by the black hole entropy and code subspace dimension.

2D gravity↗

Eigenstate thermalization hypothesis and approximate quantum error correction

The eigenstate thermalization hypothesis (ETH) is a powerful conjecture for understanding how statistical mechanics emerges in a large class of many-body quantum systems. It has also been interpreted in a CFT context, and, in particular, holographic CFTs are expected to satisfy ETH. Recently, it was observed that the ETH condition corresponds to a necessary and sufficient condition for an approximate quantum error correcting code (AQECC), implying the presence of AQECCs in systems satisfying ETH. In this paper, we explore the properties of ETH as an error correcting code and show that there exists an explicit universal recovery channel for the code. Based on the analysis, we discuss a generalization that all chaotic theories contain error correcting codes. We then specialize to AdS/CFT to demonstrate the possibility of total bulk reconstruction in black holes with a well-defined macroscopic geometry. When combined with the existing AdS/CFT error correction story, this shows that black holes are enormously robust against erasure errors.

97 MATHEMATICS AND COMPUTING↗