Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Capacity Achieving Two-Write WOM Codes
verfasst von : Amir Shpilka
Erschienen in: LATIN 2012: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we give several new constructions of WOM codes. The novelty in our constructions is the use of the so called
Wozencraft ensemble
of linear codes. Specifically, we obtain the following results.
We give an explicit construction of a two-write Write-Once-Memory (WOM for short) code that approaches capacity, over the binary alphabet. More formally, for every
ε
> 0, 0 <
p
< 1 and
n
= (1/
ε
)
O
(1/
pε
)
we give a construction of a two-write WOM code of length
n
and capacity
H
(
p
) + 1 −
p
−
ε
. Since the capacity of a two-write WOM code is max
p
(
H
(
p
) + 1 −
p
), we get a code that is
ε
-close to capacity. Furthermore, encoding and decoding can be done in time
O
(
n
2
·poly(log
n
)) and time
O
(
n
·poly(log
n
)), respectively, and in logarithmic space.
We highlight a connection to linear seeded extractors for bit-fixing sources. In particular we show that obtaining such an extractor with seed length
O
(log
n
) can lead to improved parameters for 2-write WOM codes.