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
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
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 
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
Page 81, part (d) of proof: Instead of using perturbation, use an 
        argument based on a Jordan canonical form and generalized
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
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
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),
Page 277, reference [Sai93a]: Delete the space between the forward-
        slash and "input".