Code Tree

Code Tree

Coding and decoding is considerably facilitated by what is known as the code tree, which shows the coded output for any possible sequence of data digits. The code tree for the coder in Fig. with k = 5 is shown in fig

 

When the first digit is 0, the coder output is 00, and when it is 1, the output is 11. This is shown by the two tree branches that start at the initial node. The upper branch represents 0, and the lower branch represents 1. This convention will be followed throughout. At the terminal node of each of the two branches, we follow a similar procedure, corresponding to the second data digit. Hence, two branches initiate from each node, the upper one for 0 and the lower one for 1. This continues until the kth data digit. From there on, all the input digits are 0 (augmented digit), and we have only one branch until the end. Hence, in all there are 32 (or 2^k) outputs corresponding to 2^k possible data vectors. The coded output for input 11010 can be easily read from this tree (the path shown dashed in Fig. ).

Figure  shows that the code tree becomes repetitive after the third branch. This can be seen from the fact that the two blocks enclosed inside the dashed lines are identical. It means that the output from the fourth input digit is the same whether the first digit was 1 or 0. This is not surprising in view of the fact that when the fourth input digit enters the shift register, the first input digit is shifted out of the register, and it ceases to influence the output digits. In other words, the data vector 1x₁x₂x₃x₄… and the data vector 0 x₁x₂x₃x₄… generate the same output after the third group of output digits. It is convenient to label the four third-level nodes (the nodes appearing at the beginning of the third branch) as nodes a, b, c, and d (Fig. ). The repetitive structure begins at the fourth-level nodes and continues at the fifth-level nodes, whose behavior is similar to that of nodes a, b, c, and d at the third level. Hence, we label the fourth- and fifth-level nodes also as either a, b, c, or d. What this means is that at the fifth-level nodes, the first two data digits have become irrelevant; that is, any of the four combinations (11,10, 01, or 00) for the first two data digits will give the same output after the fifth node.