Let the Generator Polynomials of a 1/3 binary Convolutional Encoder be given by $$ \begin{aligned} & g_1(D)=D^3+D^2+1 \\ & g_2(D)=D^3+D \\ & g_3(D)=D^2+1 \end{aligned} $$ The encoder starts with the all zero state. i) Encode the bit stream: 00111010 . (5 points) ii) Decode the received bit stream: 010101110000000000001000 . Correct the error(s) while necessary with the procedure. (5 points)

i) To encode the bit stream 00111010 using the given convolutional encoder, we need to follow the steps below:

1. Initialize the encoder with the all-zero state, which is represented as 00.

2. For each input bit, feed it into the encoder and generate the corresponding output bits based on the generator polynomials.

a. For the first input bit 0, we apply the generator polynomials on the current state 00 to get the output bits 000.

b. For the second input bit 0, we apply the generator polynomials on the current state 00 to get the output bits 000.

c. For the third input bit 1, we apply the generator polynomials on the current state 00 to get the output bits 101.

d. For the fourth input bit 1, we apply the generator polynomials on the current state 10 to get the output bits 011.

e. For the fifth input bit 1, we apply the generator polynomials on the current state 11 to get the output bits 101.

f. For the sixth input bit 0, we apply the generator polynomials on the current state 11 to get the output bits 110.

g. For the seventh input bit 1, we apply the generator polynomials on the current state 11 to get the output bits 011.

h. For the eighth input bit 0, we apply the generator polynomials on the current state 10 to get the output bits 100.

Thus, the encoded bit stream is 000 000 101 011 101 110 011 100.

ii) To decode the received bit stream 010101110000000000001000, we need to follow the Viterbi decoding algorithm. The steps are as follows:

1. Initialize the trellis with the all-zero state and set the path metric to zero.

2. For each received bit, calculate the branch metrics and update the path metrics and survivor paths.

a. For the first received bit 0, we calculate the branch metrics from state 00 to states 00 and 10, and update the path metrics and survivor paths accordingly. The updated trellis is shown below:

            00(0) - 00(0)
                  \ 10(1)
                   10(1)

b. For the second received bit 1, we calculate the branch metrics from state 00 to states 10 and 00, and update the path metrics and survivor paths accordingly. The updated trellis is shown below:

            00(0) - 00(0) - 10(1)
                  \ 10(1) \ 00(2)
                   10(1) - 00(2)

c. For the third received bit 0, we calculate the branch metrics from state 10 to states 11 and 01, and update the path metrics and survivor paths accordingly. The updated trellis is shown below:

            00(0) - 00(0) - 10(1) - 11(2)
                  \ 10(1) \ 00(2) \ 01(3)
                   10(1) - 00(2) - 01(3)

d. For the fourth received bit 1, we calculate the branch metrics from state 11 to states 10 and 00, and update the path metrics and survivor paths accordingly. The updated trellis is shown below:

            00(0) - 00(0) - 10(1) - 11(2) - 10(3)
                  \ 10(1) \ 00(2) \ 01(3) \ 00(4)
                   10(1) - 00(2) - 01(3) - 10(4)

e. For the fifth received bit 1, we calculate the branch metrics from state 10 to states 01 and 11, and update the path metrics and survivor paths accordingly. The updated trellis is shown below:

            00(0) - 00(0) - 10(1) - 11(2) - 10(3) - 01(4)
                  \ 10(1) \ 00(2) \ 01(3) \ 00(4) \ 11(5)
                   10(1) - 00(2) - 01(3) - 10(4) - 01(5)

f. For the sixth received bit 1, we calculate the branch metrics from state 01 to states 10 and 00, and update the path metrics and survivor paths accordingly. The updated trellis is shown below:

            00(0) - 00(0) - 10(1) - 11(2) - 10(3) - 01(4) - 10(5)
                  \ 10(1) \ 00(2) \ 01(3) \ 00(4) \ 11(5) \ 00(6)
                   10(1) - 00(2) - 01(3) - 10(4) - 01(5) - 10(6)

g. For the seventh received bit 0, we calculate the branch metrics from state 10 to states 01 and 11, and update the path metrics and survivor paths accordingly. The updated trellis is shown below:

            00(0) - 00(0) - 10(1) - 11(2) - 10(3) - 01(4) - 10(5) - 01(6)
                  \ 10(1) \ 00(2) \ 01(3) \ 00(4) \ 11(5) \ 00(6) \ 11(7)
                   10(1) - 00(2) - 01(3) - 10(4) - 01(5) - 10(6) - 01(7)

h. For the eighth received bit 0, we calculate the branch metrics from state 01 to states 10 and 00, and update the path metrics and survivor paths accordingly. The updated trellis is shown below:

            00(0) - 00(0) - 10(1) - 11(2) - 10(3) - 01(4) - 10(5) - 01(6) - 10(7)
                  \ 10(1) \ 00(2) \ 01(3) \ 00(4) \ 11(5) \ 00(6) \ 11(7) \ 00(8)
                   10(1) - 00(2) - 01(3) - 10(4) - 01(5) - 10(6) - 01(7) - 10(8)

3. Trace back the survivor paths to get the most likely transmitted bit sequence. The decoded bit stream is 00111010.

Since there is no error in the received bit stream, no error correction is necessary.