Monday, April 15, 2013

Dummynet

Nothing new for the networking community i guess, but this is relatively new for me, so making a note.  Sounds very interesting. http://info.iet.unipi.it/~luigi/dummynet/

Will update soon. 

Thursday, April 4, 2013

Polynomials and Galois Field extensions

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

  1. 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
  2. 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"
  3. 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
  4. 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. 
  5. 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.