It was asserted in McEliece without proof, that a canonical generator matrix G(D) is trellis-canonical if and only if G(D) has the property that the span-length of the corresponding scalar matrix "G~" cannot be reduced by a row operation of the form Row[m]=Row[n]D/sup s/+Row[m], where s is an integer in the range 0/spl les/s/spl les/L and m/spl ne/n. In this paper, we prove a stronger result, viz., a basic PGM is trellis-canonical if and only if it is "row-reduced". An efficient algorithm for converting a basic PGM into a trellis-canonical PGM is presented. We also correct an error in the general algorithm given in Lin and McEliece (1995).