<s>[INST] Error Correcting Polynomial Code I apologize for the screenshot, it's quite a long passage. I've linked the textbook below, page number 428-429, example 16.4.3 http://faculty.uml.edu/klevasseur/ads2


I constructed the power table for $GF(8)$, but honestly I'm extremely confused on the two things being asked of me:
Suppose the four message bits are $1, 0, 0, 1$. What seven bits should be transmitted?
Suppose the seven received bits are $1, 0, 1, 0, 1, 0, 1$. What was the original four-bit message?
Any tips on how to go about this would be great. TIA.
 [/INST] $\newcommand{\b}{\beta}$We bear in mind $\b^3 = \b + 1$.

Given $1001$, we need to reduce $1 \cdot \b^3 + 0 \cdot \b^4 + 0 \cdot \b^5 + 1 \cdot \b^6$.
We compute $\b^6+\b^3 = \b^4+\b^3+\b^3 = \b^4 = \b^2 + \b$, so we transmit $0111001$.

We received $1010101$.
We check if $\b^0+\b^2+\b^4+\b^6 = 0$:
$\b^0+\b^2+\b^4+\b^6 = \b^0+\b^2+\b^4+\b^4+\b^3 \\ = \b^0+\b^2+\b^3 = \b^0+\b^2+\b^1+\b^0 = \color{red}{\b^2+\b^1}$
So we need to check which power of $\beta$ gives $\b^2+\b^1$: well, $\b^2+\b^1 = \b(\b+1) = \b^4$.
So our original message is $0001$ instead of $0101$ ($0101$ is the last 4 bits of the received code).
</s>