Let's say the goal is to find out if an error occurred during transmission, and if it did, correct it. Let us look at our codes
A quick and to-the-point intro to algebra of polynomials and the extensions of its coefficients from GF(2) to GF(2^k), based on what is defined as an irreducible polynomial in GF(2), (and we look for irredicible polynomials that are also "primitive polynomials" and construct a GF(2^k) using a symbol that would be the root of this primitive polynomial etc.)
http://www.uotechnology.edu.iq/dep-eee/lectures/4th/communication/information%20theory/8.pdf
The point is, with GF(2), 0 and 1 symbols are interpreted as the values that the polynomial's variables can take, but with GF(2^k), k bits become the symbols and based on properties of the GF(2^k) certain error correction can be done. An example is a BCH code where the input symbols are first multiplied by the degree of the generator polynomial (of the field), (See this, page 13-14 for an example). I will revisit this soon.
- If the code is a binary code, i.e. the symbols are 0 and 1, then a 0 may in error come as 1 and 1 as 0. How will the decoder know ? It cannot ! there is no way to know
- If instead we say that the symbols are from 2^2 i.e. 2 bits, then we can say that we have only 2 symbols (00 and 11) if we get a 01 or 10, we say that we have "detected an error"
- Further, if we wan't to transmit say codes that are say 8 bits (2^3 e.g. ascii), how should we transmit it ? It turns out that if we wan't to add, subtract, divide, multiply elements together, we are essentially talking about a mathematical structure called a field. Why do we want to add, subtract, multiply, divide elements together ? The hope is that we can find some clever way to detect or correct errors. Let us investigate where this field related stuff can take us
- One issue with a Finite field is that it can be constructed only with elements that are a power of $$p^m$$, where $$p$$ is a prime. (See this). Therefore one thing to try is to look at a field with $$Z_{2^m}$$ elements and see what addition, multiplication, etc leads us to. We need to find the $$m$$ here of course.
- The trouble it turns out is that elements in $$Z_{2^m}$$ do not all have inverses, so instead we move to polynomial arithmetic (See this for more clarification. I will also touch this again soon)
A quick and to-the-point intro to algebra of polynomials and the extensions of its coefficients from GF(2) to GF(2^k), based on what is defined as an irreducible polynomial in GF(2), (and we look for irredicible polynomials that are also "primitive polynomials" and construct a GF(2^k) using a symbol that would be the root of this primitive polynomial etc.)
http://www.uotechnology.edu.iq/dep-eee/lectures/4th/communication/information%20theory/8.pdf
The point is, with GF(2), 0 and 1 symbols are interpreted as the values that the polynomial's variables can take, but with GF(2^k), k bits become the symbols and based on properties of the GF(2^k) certain error correction can be done. An example is a BCH code where the input symbols are first multiplied by the degree of the generator polynomial (of the field), (See this, page 13-14 for an example). I will revisit this soon.
No comments:
Post a Comment