Convolutional encoding of 10011 with state and trellis

Assumption: the encoder is the standard rate-1/2 encoder with a three-stage shift register (present bit and two delay flip-flops, constraint length $K=3$) and generator sequences $g^{(1)}=(1,1,1)$, $g^{(2)}=(1,0,1)$.

 Encoder: g1 = 111, g2 = 101 (K = 3, rate 1/2)

 m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ]
        |          |           |
        +---(+)----+-----------+---> c1 = mi+mi-1+mi-2
        |                      |
        +---(+)----------------+---> c2 = mi+mi-2
            output per bit: c1 c2

$$c_i^{(1)}=m_i\oplus m_{i-1}\oplus m_{i-2},\qquad c_i^{(2)}=m_i\oplus m_{i-2}$$

Encoded sequence

Message $(m_0\dots m_4)=10011$, followed by two 0s to return the register to 00.

By polynomials: $c^{(1)}(D)=(1+D^3+D^4)(1+D+D^2)=1+D+D^2+D^3+D^6$ and $c^{(2)}(D)=(1+D^3+D^4)(1+D^2)=1+D^2+D^3+D^4+D^5+D^6$, which give the same bits.

Encoded sequence: 11 10 11 11 01 01 11

State diagram

State = previous two inputs $(m_{i-1}m_{i-2})$: a = 00, b = 10, c = 01, d = 11.

            +--0/00--+
            v        |
          [ a 00 ]---+
           ^     \
      0/11 |      \ 1/11
           |       v
        [ c 01 ]<--0/10--[ b 10 ]
           |  ----1/00--->   |
           ^                 | 1/01
      0/01 |                 v
           +-------------[ d 11 ]--+
                            ^      | 1/10
                            +------+
 label = input/output bits

Trellis diagram

      t0     t1     t2     t3     t4     t5     t6     t7
a 00  *      o      o      *      o      o      o      *
        \                 /  \                        /
           \             /      \                    /
b 10  o      *      o   /  o      *      o      o   /  o
               \      /            \              /
                  \  /              \            /
c 01  o      o      *      o      o   \  o      *      o
                                       \      /
                                        \  /
d 11  o      o      o      o      o      *      o      o
in:      1      0      0      1      1      0      0
out:    11     10     11     11     01     01     11

At each stage every state has two branches (input 0 and 1) as in the table; the path for 10011 is marked with *. The output read along the path is 11 10 11 11 01 01 11.