SU-ENGR76 MAY232024 — Jemoka Knowledge Base

Convolutional Code A Convolutional Code, at each time j, takes bit b_{j} and output two bits p_{2j-1}, p_{2j}, by using b_{j} and the previous two its b_{j-1} and b_{j-2}. Working Example Consider that if you have k bits to communicate to the receiver:

\begin{equation} b_1, b_2, \dots, b_{k} \end{equation}

Codewords/Output sequence:

\begin{equation} p_1, p_{2}, \dots \end{equation}

Let we have some sequence of k input bits

\begin{equation} j = 1, \dots, k \end{equation}

then, for every input bit, we generate two output bits:

\begin{equation} p_{2j-1} = b_{j} \oplus b_{j-1} \oplus b_{j-2} \end{equation}

\begin{equation} p_{2j} = b_{j} \oplus b_{j-2} \end{equation}

if we are at j=1, then we assume that b_{j-1} = b_{j-2} = 0. Shift Register So you can encode this in a streaming fashion, and shift them off as you go FST The Convolutional Code, then, is essentially a finite state machine: whereby the last two bits are essentially the “state” of the machine used for the output. (b_{j-1}, b_{j-2}). The input would be b_{j}, and the output is p_{2j-1}, p_{2j}. During each action b_{j}, we essentially perform the “shift” operation. Therefore, you can draw it in terms of a finite state diagram. Trellis Now, consider rolling out finite state machine over time: make a grid of j on the x axis, and state on y axis. Then, you can trace possible lines connecting everything. We can encode any encoding process as a PATH is the rollout trellis. This could also help us perform decoding, because we can spot which edge our scheme traveled down. Viterbi Decoding bottom-up DP go through your edges, calculating Hamming Distance of each edge of your trellis’ decoding and the one you recieved; replace each edge with that distance edit distance minimize lol through the path to solve (i.e. run dijikstra on these edges)