An official website of the United States government
Racetrack memory is a promising new non-volatile memory technology, especially because of the density of its 3D implementation. However, for 3D racetrack to reach its potential, certain reliability issues must be overcome. Prior work used per-track encoding to tolerate the shift errors that are unique to racetrack, but no solutions existed for tolerating both shift errors and bit flip errors. We introduce Foosball Coding, which combines per-track coding for shift errors with a novel across-track coding for bit flips. Moreover, our per-track coding scheme methodically explores the design of inter-codeword delimiters and introduces the novel concept of multi-purpose delimiters, in which the existence of multiple delimiter options can be used to provide additional information.
more »
« less
GreenFlag: Protecting 3D-Racetrack Memory from Shift Errors
Racetrack memory is an exciting emerging memory technology with the potential to offer far greater capacity and performance than other non-volatile memories. Racetrack memory has an unusual error model, though, which precludes the use of the typical error coding techniques used by architects. In this paper, we introduce GreenFlag, a coding scheme that combines a new construction for Varshamov-Tenegolts codes with specially crafted delimiter bits that are placed between each codeword. GreenFlag is the first coding scheme that is compatible with 3D racetrack, which has the benefit of very high density but the limitation of a single read/write port per track. Based on our implementation of encoding/decoding hardware, we analyze the trade-offs between latency, code length, and code rate; we then use this analysis to evaluate the viability of racetrack at each level of the memory hierarchy.
more »
« less
- Award ID(s):
- 1717602
- PAR ID:
- 10191408
- Date Published:
- Journal Name:
- 49th IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2019)
- Page Range / eLocation ID:
- 1 to 12
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the storage–retrieval rate trade-off in private information retrieval (PIR) systems using a Shannon-theoretic approach. Our focus is mostly on the canonical two-message two-database case, for which a coding scheme based on random codebook generation and the binning technique is proposed. This coding scheme reveals a hidden connection between PIR and the classic multiple description source coding problem. We first show that when the retrieval rate is kept optimal, the proposed non-linear scheme can achieve better performance over any linear scheme. Moreover, a non-trivial storage-retrieval rate trade-off can be achieved beyond space-sharing between this extreme point and the other optimal extreme point, achieved by the retrieve-everything strategy. We further show that with a method akin to the expurgation technique, one can extract a zero-error PIR code from the random code. Outer bounds are also studied and compared to establish the superiority of the non-linear codes over linear codes.more » « less
-
In the quantum compression scheme proposed by Schumacher, Alice compresses a message that Bob decompresses. In that approach, there is some probability of failure and, even when successful, some distortion of the state. For sufficiently large blocklengths, both of these imperfections can be made arbitrarily small while achieving a compression rate that asymp- totically approaches the source coding bound. However, direct implementation of Schumacher compression suffers from poor circuit complexity. In this paper, we consider a slightly different approach based on classical syndrome source coding. The idea is to use a linear error-correcting code and treat the state to be compressed as a superposition of error patterns. Then, Alice can use quantum gates to apply the parity-check matrix to her message state. This will convert it into a superposition of syndromes. If the original superposition was supported on correctable errors (e.g., coset leaders), then this process can be reversed by decoding. An implementation of this based on polar codes is described and simulated. As in classical source coding based on polar codes, Alice maps the information into the “frozen” qubits that constitute the syndrome. To decompress, Bob utilizes a quantum version of successive cancellation coding.more » « less
-
This project, titled Collective Argumentation Learning and Coding (CALC), aims to use the principles of collective argumentation to teach coding through appropriate reasoning. Creating and critiquing arguments as part of a coding activity promotes a more structured approach rather than the trial-and-error coding activity commonly used by novice programmers. Teaching coding via collective argumentation allows teachers to use methods that are already in use in mathematics and science instruction to teach coding, thus increasing the probability that it will be taught in conjunction with mathematics and science as regular parts of classroom instruction rather than relegated to an after-school or enrichment activity for only some students. Specific objectives of the CALC project are to - increase the attention that coding is given in the elementary classrooms taught by our participating teachers, and -direct students away from informal approaches (e.g.trial-and-error) to develop code to the more formal, structured approach recommended for novice programmers. Our research activities investigate teachers’ understanding of argumentation using the CALC concept and how the implementation of the CALC concept helps students (grades 3-5) learn how to code. The CALC approach supports the learning of coding by providing teachers with a formal, structured means to a) trace the growth of students’ understanding, and misunderstanding, of ideas (i.e., coding) as they form, b) facilitate students’ use of evidence, not opinion, to select a solution among multiple solutions (i.e., different sequencing of the code), and c) help each student realize she/he, as well as others, is a legitimate participant (i.e., a programmer) in the activity of developing, assessing and implementing an idea (e.g., coding of a robot). This paper/presentation discussed the first phase of an on-going investigation and focuses on a prototype graduate-level course designed for and taught to practicing elementary school teachers. The discussion outlines how the course impacted the participating teachers content knowledge of coding and their belief that coding can be made an integral part of everyday lessons, not as an add-on activity.more » « less
-
Streaming codes take a string of source symbols as input and output a string of coded symbols in real time, which effectively eliminate the queueing delay and are regarded as a promising scheme for low latency communications. Aiming at quantifying the fundamental latency performance of random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels, this work derives the exact error probability under, simultaneously, the finite memory length and finite decoding deadline constraints. The result is then used to examine the tradeoff among memory length (complexity), decoding deadline (delay), and error probability (reliability) of RLSCs for the first time in the literature. Two critical observations are made: (i) Too much memory can adversely impact the performance under a finite decoding deadline constraint, a surprising finding not captured by the traditional wisdom that large memory length monotonically improves the performance in the asymptotic regime; (ii) The end-to-end delay of the RLSC is roughly 50% of that of the MDS block code when under identical code rate and error probability requirements. This implies that switching from block codes to RLSCs not only eliminates the queueing delay (thus 50%) but also has little negative impact on the error probability.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/DSN.2019.00016
