convolutional codes: free distance

Question

It's commonly stated in the literature that the free distance of a convolutional code is the minimum Hamming distance between the all-zero path and any other (non-all-zero) path in the trellis originating in the zero state and ending in the zero state. (The free distance of a code is defined as the minimum Hamming distance between any two distinct codewords.)

My question: Is this true in general? Or is it true only conditionally (e.g. when we assume that the code is terminated in the zero state)? If it's the latter, what's the condition for it to be true?

It appears to me that a sufficient condition is that the convolutional code is a linear block code. This includes the finite length "zero-tail" codes and "direct truncation" codes. The former refers to codes which include all paths that end in the zero state; the latter means the codes allow the paths to terminate in all possible states. Am I mistaken?

Answer 1

It's defined as the smallest distance as above. No other condition needed. For example, see the notes here:

In the context of convolutional codes, the smallest Hamming distance between any two valid codewords is called the free distance. Specifically, the free distance of a convolutional code is the difference in path metrics between the all-zeroes output and the path with the smallest non-zero path metric going from the initial $00$ state to some future $00$ state.

Answer 2

Consider the path(s) that leave the zero state in the very first branch(es) of the trellis. In the modification to the definition of free distance that you wish to use, the minimum weight of these paths (equal to the Hamming distances of these paths from the all-zeroes path) will be the free distance, no? These one-branch paths are leaving the zero state and ending at some nonzero state and since Hamming weights of paths are nondecreasing functions of the depth into the trellis, any longer path that ends up at the same state will have a Hamming weight at least as large as the weight of the first branch.

That's why it is necessary to insist on the path beginning and ending at at the zero state. Note that the definition insists on consideration of all paths that leave the zero state and return to the zero state at a later time; not just the shortest path (measured in terms of the number of branches in the path). Consider, for example, the convolutional code whose state transition diagram is shown in Figure 8.3 of this Lecture Note from MIT. The shortest path (three branches) leaving the zero state and returning to the zero state has weight 5 but the minimum-weight path has 4 branches and weight 4, making the free distance of this code 4, not 5.

Answer 3

I appreciated the feedback of Dilip, kodlu & Jyrki in this question & 2 follow-up's (Part 2, Part 3), but was still confused. So I did some more work, and would like to share my findings here, in case someone else has similar confusion.

Much of the OP's confusion stemmed from the assumptions that were implicit in the literature or missed by the OP. So,

First of all, a little history:

1. The term 'free distance' was first proposed by Costello in 1969. It was indeed defined as the minimum distance between 2 distinct codewords of a convolutional code. See also Costello 1974. (Let's call this Def-1.) However, the codewords were allowed to have infinite length here.

2. Viterbi in 1971 subsequently made use of "minimum free distance" in bounding the "first-event" error probability of ML decoding. Here a first-event error was defined as the event that a path deviated from the zero state and returned to it for the first time. And the minimum free distance is simply the minimum weight of such paths. (Let's call this Def-2.) The codewords there appeared to be of finite length, although not very explicitly & evidently stated. (Correct me if I'm wrong.)

Now, back to the question: is Def-1 equivalent to Def-2? The answer is yes for most practical purposes, but no in general. To see this,

1. Consider conv codes of infinite codeword length first. Def-1 $\equiv$ Def-2 for the so-called "non-catastrophic" codes. But this may not be true when the code is catastrophic. (The latter is probably of little practical value.)

2. Most (if not all) practical conv. codes are of course of finite length. For these codes to be practical, they're generally properly terminated (so the trailing bits are well protected) and of considerable codeword length. For example, for zero-tailed codes as considered in Viterbi in 1971, it's not hard to see that Def-1 $\equiv$ Def-2. It also holds for tail-biting codes, c.f. Ma & Wolf 1986. This is, however, not true in general, and simple counter-examples can be found in Part 2, and Part 3, though none of them is of much practical significance.

Note: It's laborious to trace the literature. In case I erred somewhere above, corrections will be much appreciated.