Errata
An Introduction to Coding for Constrained Systems
May 24, 2006
Page 5, line 7 from bottom: The Blake-Mullin reference is mistyped.
Page 12, example 1.5, line 4: Both words are defined as "w_0". The
second one should be "w_1".
Page 18, section 1.5.6, line 1: "Within the last decade" should
probably be changed to "Within the last decade and a half" or,
in a more absolute time reference, "Beginning in the early
1990's"...
Page 18, section 1.5.6, paragraph 1, last line: "PRML" should be
replaced by "PRML and its extensions".
Page 18, second paragraph, line 2 from bottom: "section 1.6.2" should
be "Section 1.6.2"
Page 25, section 1.7, line 4: "For much more detailed information"
Page 25, section 1.7.1, line 6: "the pits appear as bumps" sounds
better.
Page 26, paragraph before section 1.7.2: Change "have missed" to "miss"
Page 28, paragraph 2, line 1: Change "allows to reduce" to "makes it
possible to reduce"
Page 28, example 1.11, line 3: "(refer to the precoding rule in Section
1.5.5, and also ..."
Page 28, paragraph 2 from bottom, line 1: "As explained earlier,
recording in"
Page 30, line 3 after Table 1.3: "recorded signal in the"
Page 30, line 7 after Table 1.3: "power spectral density in the"
Page 44, section 2.2.7: The claim that S(G) = S(H) for the Moore form
(resp. co-form) H of G is wrong if there are source (resp. sink)
states. Therefore, when producing those graphs, one needs to
assume that each source (resp. sink) state has one dummy
incoming(resp. outgoing) edge. Alternatively, just assume that
the graph is essential.
Page 46, proof of Lemma 2.4: The graph H might not generate words of S
that are not extendible to words of length M+1. This can be
fixed by endowing each state u_w in H with an incoming path that
generates the word w. Alternatively, assume that the graph is
essential.
Page 63, Problem 2.2: In part (3), we need to assume that G has n
source states. In part (4), we will always have equality if
there are no sink states.
Page 78, last paragraph: First show that the elements in each C_r
are congruent. Then deduce that the C_r's form distinct
congruence classes, as the lengths of paths between distinct
C_r's are not divisible by the period.
Page 78, line 5 from bottom: Change "path" into "paths".
Page 78, line 3 from bottom: The word "class" is missing after
"equivalence".
Page 81, part (d) of proof: Instead of using perturbation, use an
argument based on a Jordan canonical form and generalized
eigenvectors.
Page 83, last line: "x" is missing at the end of Equation (3.5).
Page 88, line 3 from bottom: If there is a state u \in V for which
P(e) = 0 for all edges e \in E_u, then the matrix Q will contain
an all-zero row and, therefore, will not be stochastic.
Page 94, Proposition 3.24: The proof assumes that S is generated by
a graph G that has no source states (i.e., each state is assumed
to have an incoming edge).
Page 94, first displayed equation: Change u_{w_3...z_m z_1 z_2} into u_{w_3...w_m z_1 z_2}.
Page 95, Problems 3.1 and 3.2: The order of the questions should be
switched.
Page 97, Problem 3.12: A should be irreducible.
Page 101, Problem 3.20, part 6: A factor 2 is missing in the argument
of the cosine. This problem also implicitly requires to show
that for 1 \le i < (B+1)/2, the multiplicity of the
eigenvalue \lambda_i is 2. Maybe a hint is in place. E.g.,
observe that if x is an eigenvector, then so is the vector
obtained by shifting its entries cyclically, or by reversing
their order. Hence, the geometric multiplicity can be 1 only if
the entries of x are all equal (i.e., are all 1) or alternate
between 1 and -1. The first case corresponds to the Perron
eigenvalue 2, while the second for the eigenvalue which exists
only if B is odd.
Page 102, Problem 3.25: In the hint, change "=" into "\le".
Page 102, Problem 3.27: In the last line, the rightmost "<="
can be changed into "<".
Page 103, Problem 3.32(2): Change H_m into H_3.
Page 111, Theorem 4.2: Maybe state first the theorem for (S,n)-
encoders, namely, show that \log n \le \capacity(S).
Page 112, line 3: Make reference to Proposition 3.14 to claim that
in every irreducible n-regular graph G, n = \lambda(A_G).
(Since this holds also in the reducible case, the assumption
of irreducibility at the beginning of the proof of Theorem 4.2
can be omitted.)
Page 112, Theorem 4.3: Maybe do the following: state first that for
every \log n < \capacity(S) there exists a block (S^t,n^t)-
encoder for some t. Then, by shifting to the Moore co-form,
state that there exists an (S,n)-encoder with anticipation \le
2t-1. Finally, state Theorem 4.3 as a corollary.
Page 113, proof of Theorem 4.3: Make the shift to the primitive
case explicitly in the proof.
Page 115, last two lines: The (1,7)-RLL encoder that is exhibited
in Example 4.9 in Section 4.3 has only four states. Also,
the sliding-block decoder of that encoder is not included
in that example (instead, a reference is provided); therefore,
change the first "with" in the last line into "that has".
Page 120, last line: The problem number is incorrect.
Page 137, Proposition 4.1. part 4: This holds if none of the partition
elements E_u^{(i)} is allowed to be empty.
Page 140, last paragraph: add transposition to the left eigenvector z.
Page 141, Proposition 5.5(a): Backslash missing before "Bigl".
Page 150, line following the proof: Change "a" into "an" and
delete "is".
Page 155, third paragraph in Section 5.5: If the graph H is lossless
yet with infinite anticipation, then state merging may result
in a lossy graph. (This problem does not occur if H has finite
anticipation, even for the more general concept of (u,u')-merger
presented on page 157.)
Page 156, Figure 5.14: The self-loop at state 0 should be labeled "01".
Page 157, Figure 5.15: State 0 corresponds to state 1 in Figure 5.14,
and state 1 corresponds to state 0 therein. Therefore, the
figure should be mirrored, with the new left (resp., right)
state labeled "0" (resp., "1-2"). This change will produce a
conflict with the notation in Figure 4.1, so a remark to this
effect needs to be added at the end of Example 5.5 (line 4 from
bottom of page 156). Alternatively, Figure 4.1 can be changed so
that it looks like the new Figure 5.15 (see also Figures 5.19
and 5.20 on page 163).
Page 158, Proposition 5.8: We can weaken (b) to x_u \ge x_{u'}.
Page 158, last two lines: This definition of weight-minimal states
is useful only when there are no two states that have the same
follower set. So either make this assumption explicit, or change
the condition "u = v" in the last line into "u \simeq v" (i.e.,
"u is follower-set equivalent to v").
Page 158, last line: We can change the condition "x_v = x_u" into
"x_v \ge x_u".
Page 161, last line: The text does not read well if the second
parenthesized phrase, "rounds of", is dropped. Therefore, do not
enclose these two words in parentheses.
Page 162, line 6: The text, again, does not read well if the second
parenthesized phrase, "rounds of", is dropped.
Page 169, Problem 5.9: "e" is missing from the set of labels
(mentioning of this set can be deleted altogether).
Page 172, Problem 5.16, line 2: Backslash is missing before "bldx".
Page 268, reference [Fra68]: The pages should read 143--157.
Page 277, Second paragraph that follows Example 8.13: The condition
that \lambda(A) \le n is sufficient, but not necessary.
To make the condition also necessary, it needs to be
changed to \min_i \lambda(A_i) \le n, where A_i ranges
over all irreducible sources of A (i.e., all irreducible
components with no incoming edges from other irreducible
components).
Page 277, paragraph that precedes Proposition 8.8: The assumption
on the irreducibility of A is more than just a convenience:
entries in \bldx may have zero components otherwise.
Page 231, Proposition 8.9: The restriction to the irreducible case
is required, and it should be justified differently than what is
done in the ordinary state-splitting algorithm. Specifically,
the constraint is typically an image of an encoder of a
constraint S(G). By shifting to an irreducible sink of the
encoder, we get an irreducible encoder of an irreducible
constraint S(G'), where G' is an irreducible subgraph of G
(Lemma 2.9 in Chapter 2).
Page 266, reference [Dav93]: The title should read "Codes correcting
errors in the modulus metric,..." The word "Informatsiy" is
misspelled, and it is better to give instead a reference to
the Engligh translation, "Problems Inform.\ Transm., 29 (1993),
208-216."
Page 277, reference [Sai93a]: Delete the space between the forward-
slash and "input".