Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When I am reading some algorithm related to error correction. To generate some polynomial it uses finite-field which is Galois field. I am not from mathematical background. Can anybody explain me in simple form to understand this ?

share|improve this question
3  
Others have given you good answers. For an example involving an error-correcting code (Reed-Solomon code) see this question, where a code over $GF(8)$ is used. That is a toy example only. As prof. Sarwate explains, in real life applications the most common Galois field is $GF(256)$. Reed-Solomon error-correcting codes with that alphabet have the property that a single byte can be viewed as an element of the field and vice versa. Such codes are used to correct the scratches on CDs. They are also part of the current European digital-TV standard. –  Jyrki Lahtonen Oct 19 '11 at 19:47
1  
To a person without strong math background I would recommend Richard Blahut's book (don't remember the title, sry). It concentrates on the algorithms related to using RS-codes, and does so with the minimum amount of algebra, so it gives the necessary background on finite fields also, and gives a very nice account of the Berlekamp-Massey algorithm (both on the time and frequency domains) as well as the extension to erasure correction. For error detection I would recommend searching stuff on CRC-polynomials for starters. –  Jyrki Lahtonen Oct 20 '11 at 7:07
2  
@JyrkiLahtonen The title of Blahut's book is Algebraic Codes for Data Transmission but I would not recommend it to a neophyte with a computer science background. An alternative might be Benjamin Arazi's A Commonsense Approach to the Theory of Error-Correcting Codes, or at an even more practical level for programmers, C. R. Rorabaugh's Error Coding Cookbook: Practical C/C++ Routines and Recipes for Error Detection and Correction –  Dilip Sarwate Oct 20 '11 at 12:01
1  
@Dilip I do not question your recommendations at all. On the contrary. I mentioned Blahut's book, because it does use the Galois fields heavily. Also my former students with a weaker (in comparison to yours truly) algebra background benefited from Blahut's book. Admittedly the said students were math majors as opposed to EE/CS majors. Undoubtedly you have more mileage teaching these topics to those people, so I'm not gonna fight the issue. Would those books still adequately cover RS-codes (judging from the original post that is on the wish list)? –  Jyrki Lahtonen Oct 20 '11 at 13:22
2  
@Jyrki EE/CS majors (at the graduate level) as well as math students (even those with weak backgrounds in algebra) can and do benefit from reading Blahut's book. But Sunny says elsewhere on Math.SE that "I am software programmer" and his other postings on Math.SE seem to indicate that he does not want or need such an extensive exposure to RS codes as Blahut's book provides. This is why I suggested other books that may well provide Sunny with what he needs. For the general readership of Math.SE, Blahut's book is indeed an excellent recommendation for algorithms relating to RS codes. –  Dilip Sarwate Oct 20 '11 at 13:41

2 Answers 2

up vote 6 down vote accepted

Galois field is the name that engineers (and especially those studying error correcting codes) use for what mathematicians call finite field. In applications, the most commonly used Galois field is GF$(256)$, also called GF$(2^8)$. Its elements can be thought of as polynomials of degree $7$ or less with binary coefficients ($0$ or $1$). Addition of two field elements is addition of the two polynomials with coefficients being added modulo $2$. Multiplication is polynomial multiplication modulo a polynomial $m(x)$ of degree $8$, that is, multiply the two given polynomials (which may result in a polynomial of degree as much as $14$) and then divide by $m(x)$, throwing away the quotient and keeping only the remainder.

share|improve this answer
    
in my computer parlance it is used to convert set of characters to again a character. Because AsCII is having 255 chars is it correct ? –  dungeon Hunter Oct 19 '11 at 19:22
    
@Sunny: Calculations in $GF(256)$ can be used to convert bytes to bytes, but usually there's no guarantee that the byte you get out of it will be the number of a printable characters. "ASCII" is a 7-bit code defining 95 characters (and some non-character control-codes). Typically one uses one byte to represent an ASCII character, but that doesn't make all bytes ASCII. –  Henning Makholm Oct 20 '11 at 1:18
    
ASCII calls the control codes "control characters". For instance, see the opening sentence in A7.1. Scans are here: wps.com/projects/codes/X3.4-1963/index.html –  Kaz Feb 16 '13 at 1:24

A Galois field is a finite field (from the Wikipedia article):

In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains a finite number of elements.

share|improve this answer
3  
@Sunny: Make sure that you visit this page linked to from the Wikipedia page that Jack refers you to. There are detailed examples worked out there. Also some C-code for implementing the field $GF(256)$. There it is for the purposes of Rijndael cryptosystem, but the same field is very commonly used in Reed-Solomon codes. –  Jyrki Lahtonen Oct 19 '11 at 19:53
3  
... and Rijndael is better known as AES these days, essentially the standard choice of block cipher everywhere. –  Henning Makholm Oct 20 '11 at 1:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.