Below is a cache of http://www.comsoc.org/comm/private/2000/mar/pdf/48comm03-roth.pdf. It's a snapshot of the page taken as our search engine crawled the Web.
The web site itself may have changed. You can check the current page or check for previous versions at the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
PubTeX output 2000.03.09:1157
IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 48, NO. 3, MARCH 2000
351
On Runlength-Limited Coding with DC Control
Ron M. Roth, Senior Member, IEEE
AbstractConstructions are presented of finite-state encoders
for certain
(d; k) runlength-limited (RLL) constraints with direct
current control. In particular, an example is provided for a rate
8:16 encoder for the (2,10)-RLL constraint that requires no look-
ahead in decoding, thus, performing favorably compared to the
EFMPlus code used in the DVD standard.
Index TermsDC control, EFM code, EFMPlus code, optical
recording, runlength-limited coding.
I. I
NTRODUCTION
I
N OPTICAL and magnetic recording systems, the bit stream
that is written into the device must satisfy certain constraints.
The most common family of such constraints appears to be that
of the
runlength-limited (RLL) constraints, where the run
of zeros between consecutive ones in the bit stream must have
length at least
and no more than
for prescribed parameters
and
For example, bit streams recorded in the compact disk
and the DVD satisfy the (2,10)-RLL constraint [4][6]. The set
of all sequences satisfying a given
-RLL constraint can
be described by reading the labels off of paths in the labeled
directed graph as shown in Fig. 1.
Given a binary sequence
that satisfies a given
-RLL constraint, the respective NRZI sequence over
the bipolar alphabet
is given by
where
In addition to satisfying RLL constraints,
recording applications typically require also the suppression
of the direct current (dc) component of the recorded NRZI
signal; namely, the spectrum (i.e., power spectral density) of the
ensemble of NRZI sequences should take small values in the
neighborhood of zero frequency [4, Ch. 2], [8][10]. Another
parameter that measures the dc suppression is the running sum
variation (RSV), which is defined as the expected value of
when
Clearly, a smaller RSV indicates
a better suppression of the dc component.
In order to satisfy a given constraint, a user-provided uncon-
strained data stream should be encoded; namely, it needs to un-
dergo a uniquely decodable (or lossless) mapping into a con-
strained sequence. Encoders for constrained data usually take
the form of a finite-state machine. A rate
finite-state en-
coder accepts an input block of bits and generates a -bit code-
word depending on the input block and the current state of the
encoder. The sequences obtained by concatenating the gener-
ated -bit codewords satisfy the constraint.
Paper approved by W. E. Ryan, the Editor for Modulation, Coding, and Equal-
ization of the IEEE Communications Society. Manuscript received September
9 1998; revised February 8, 1999 and August 18, 1999.
The author was with Hewlett-Packard Laboratories, Paolo Alto, CA 93404
USA and Hewlett-Packard Laboratories, Israel, Haifa, Israel. He is now with
the Computer Science Department, Technion, Haifa 32000, Israel (e-mail:
ronny@cs.technion.ac.il).
Publisher Item Identifier S 0090-6778(00)02266-2.
Each encoder must have a decoder that recovers the input
stream from the constrained sequence generated by the encoder.
The class of sliding-block decoders has the advantage of lim-
iting error propagation. An
m, a
-sliding-block decoder recon-
structs an input -bit block that corresponds to a given received
-bit codeword on the basis of the local context of that codeword
in the received sequencethe codeword itself, as well as
m
pre-
ceding codewords and
a
upcoming codewords. The parameter
m
is called the encoder memory, and
a
is referred to as the an-
ticipation. Thus, a single error at the input to a sliding-block
decoder can only affect the decoding of at most
m
a
con-
secutive codewords.
In addition to having sliding-block decoders, it is desirable
that the code have the highest rate possible. The rate of any
encoder for a given constraint is bounded from above by the
Shannon capacity of that constraint. The Shannon capacities of
several
-RLL constraints are listed in [4, p. 91, Table 5.4].
This work presents constructions of finite-state encoders for
certain
-RLL constraints with dc control. Two examples
are provided. The first example, presented in Section II, is a rate
8:16 encoder for the (2,10)-RLL constraint, and the second ex-
ample, presented in Section III, is a rate 8:15 encoder for the
(2,12)-RLL constraint. Both encoders are sliding-block decod-
able with zero memory, and the (2,10)-RLL encoder has zero
anticipation. dc control is achieved by letting as many input
blocks as possible be encoded into two possible codewords; the
parity of number of ones is different in these two codewords,
and so the respective NRZI sequences end with a different po-
larity, thus reversing the polarity of subsequent codewords. Fur-
thermore, both codewords lead to the same state, thus allowing
local replacement of a codeword by its alternate without af-
fecting subsequent codewords. The spectral properties of the
new (2,10)-RLL encoder are compared in Section II with two
existing encoders for the same constraint at the same rate; one
of these encoders is the EFMPlus code which is part of the DVD
standard. Design considerations are summarized in Section IV.
One architectural feature of the design approach here is
having a single compact encoder table that contains the code-
word tables of all states in an overlapping manner. Recognizing
that sets of codewords that correspond to different states can
intersect, the overlapping encoding table uses the very same
entry in the table for each intersecting codeword, regardless of
the state from which this codeword is generated. Furthermore,
the specific ordering of the codewords in the table provides an
easy mechanism of dc control.
II. (2,10)-RLL E
NCODER WITH
DC C
ONTROL
The Shannon capacity of the (2,10)-RLL constraint is approx-
imately 0.5418 [4, p. 91]. We describe here a four-state encoder
for this constraint at rate 8:16.
00906778/00$10.00 © 2000 IEEE 352
IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 48, NO. 3, MARCH 2000
Fig. 1.
Graph presentation of a
(d; k)-RLL constraint.
TABLE I
T
ABLE OF THE
(2,10)-RLL E
NCODER
Our encoder consists of a table of 556 codewords, each 16 bits
long. Table I lists the codewords in hexadecimal form. At each
encoding step, the encoder can be in one of the following states:
S0, S1, S2-5, or S6-8. Each state is associated with a range of
runlengths which is reflected in the state name. For example,
state S6-8 is associated with runlengths 6, 7, and 8. Encoding is
carried out as follows: given an input byte
a ten-bit address is
formed by prefixing with two bits. This two-bit prefix depends
on how the value of
(as an integer) compares with two thresh-
olds, T1 and T2. These thresholds, in turn, depend on the current
state of the encoder. The table of threshold values and the table
of prefixes are presented in Table II (the notation
stands here
for the dont care sign).
For example, if the current state is S6-8 and the input byte is
049 (decimal), then the address will be 256 + 049 = 305.
The output codeword is the entry in Table I at the computed
address, and the next encoder state is determined by the last
runlength of the generated codeword.
In the example, the output codeword is 0000001001000010
(0242 in hexadecimal notation) and the next encoder state is S1.
There are cases where more than one prefix is possible, re-
sulting in two different codeword candidates. To allow dc con-
trol, the encoder table is designed so thatto the largest extent
possiblethose codeword candidates will have different parity
(odd/even) of number of ones, thereby inducing different parity
of sign changes (see [7] for using a similar idea in an uncon- IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 48, NO. 3, MARCH 2000
353
TABLE II
T
HRESHOLDS AND
P
REFIXES FOR THE
(2,10)-RLL E
NCODER
Fig. 2.
Schematic diagram of the (2,10)-RLL encoder.
strained setting). Furthermore, both codeword candidates lead
the encoder to the same state, and therefore replacement of a
codeword with its alternate can be done within an output stream
without affecting preceding or following codewords. The de-
coder can recover the input byte regardless of the specific code-
word candidate that was chosen.
For example, if the current state is S1 and the input
is 70 (decimal), then the output codeword can be either
0000100000010001 or 0100000010010001. Both codewords
lead to state S0.
A schematic diagram of the encoder is shown in Fig. 2. As-
suming independent and uniformly distributed input, the ex-
pected percentage of input bytes within an input sequence for
which two codeword candidates exist is 49.7% (this number is
computed by first finding the stationary probability of being at
each encoder state; see the discussion toward the end of Sec-
tion IV).
Decoding is carried out as follow