Error detection and correction.

In the early days of digital computers paper tape was cheap way of processing data. Using technology developed from telegraphic communications, 5 hole punched tape provided a good start. Paper tape was already established as a way of automating teletypes and telex machines. Printed output was regarded as the "safe" archive and error correction was done by eye, on paper. Punch card systems, made originally to automate weaving machines, were also attached to digital computers and provided some competition before they were both eventually replaced by magnetic media.

Checking that you have read "good data" remained the most important challenge. A "parity bit" was reserved on 8 hole paper tape. The math was very simple. Count the number of "1" bits in a 7 bit symbol and cut a parity bit hole to make the up the number of holes in the 8bit symbol to an even number. Tape readers evolved to include electronics to test the "parity" and stop if an error was detected. An improvement, but still not very safe. e.g. what happens if several holes are misread but the parity is still good.

The data parity idea was extended to make error detection safer by adding more bits. Packets of data were sent over communications networks complete with large amounts of parity data. If a packet was found to be corrupt is was easy to engage a protocol to ask the originator to send the packet again. However, if the round trip time is long (deep space communication) it was obviously desirable to repair damaged data in situ. A naive scheme to replicate the data several times would work. e.g If the same message is repeated 10 times then, provided you have a robust way of distinguishing between good and bad, bad data can be simply discarded.
However, this scheme makes heavy demands on storage space or communications bandwidth. If every packet is slightly damaged then you can devise other schemes to "vote on" the correct version of a byte provided you can recognise the start and end of each packet. It was clear to the mathematicians that ignoring an entire byte or even an entire message packet just because a few bits were wrong was wasteful. The mathematics of calculating extended parity bits (sometimes called Cyclic redundancy check) involves treating data as the coefficients of a polynomial rather than a series of numbers and, from this technology, emerged a way to repair damaged data. First look at how some extended parity schemes are actually calculated
The polynomials are of the form:

anxn + an-1xn-1 + ... + a2x2 + a1x + a0

The series of n coefficients an correspond to binary digit. (This is a trivial instance of a finite field. gf(2)note 1 consists of 0 and 1)

Incoming data is treated as a series of binary digits that are also treated as the coefficients of a polynomial. This "polynomial" is dividednote 2 by another "generator polynomial" and the remainder is used as the CRC. The division is performed by a repeated XOR of the incoming data bits with the divisor. To simplify presentation, the polynomial is written as just the series of coefficients - a string of binary digits
e.g. A generator polynomial 1x3+0x2+1x+1 or x3+x+1 is represented as binary 1011. This divisor will generate a three bit CRC error correction code.
f(x)   11010011101100   Incoming data
gp(x)  1011             XOR the significant top order bits
       --------------   with the Generator polynomial 1101
r(x)'  01100011101100   Carry the remainder forward
        1011            and repeat the operation
        -------------
        0111011101100   
         1011
         ------------
         010111101100
          1011
          -----------
          00001101100
              1011
              -------
              0110100
               1011
               ------
               011000
                1011 
                -----
                01110
                 1011
                 ----
                 0101 The CRC is thus 101
Choosing the generator polynomial defines the number of errors that can be detected from a single error parity bit (gp(x) = x + 1) ,to much more robust schemes like CRC-64-ISO (gp(x)=x64 + x4 + x3 + x + 1)

It is wrong to assume you can easily produce all types of CRC once you have obtained the generator polynomial and mastered the calculation. Many schemes spend a lot of effort obfuscating the final result. Sometimes there are legitimate reasons to re-order bits to comply with network conventions but usually they are attempts to protect intellectual property, avoid patent disputes or misguided efforts to improve the cryptographic strength. This group of papers is an attempt to shed light on bald statements like "apply the REED SOLOMON algorithm" where a few fully worked examples would be welcome.

Please contact (replace ρ rho with p) ρete@redtitan.com with comments.
note 1
    gf(2) is an example of a "finite field" discovered by Evariste Galois (c1826) to have special properties. His divergent analysis of algebraic problems gives him the reputation of one of the founders of a branch of mathematics called "number theory". His work on finite fields, that appeared to only irritate his mentors, is at the heart of digital communications today.
note 2
    This is clearly not a divide operation in the usual sense. The special nature of Galois aritmetic is discussed later in the text.

Galois Field Arithmetic

The operators in conventional arithmetic (divide, multiply, add, subtract etc) deal with infinite or unbounded numbers. Computer hardware uses binary arithmetic where integer results are stored in registers, bytes or words of a finite size. Dealing with the overflows caused by very large calculations is a considerable problem if the result is to be used in bit by bit error detection.

Reed Solomon codes are created by the manipulation of finite group of numbers called a Galois Field. GF(256) is a field consisting of the every integer in the range 0 to 255 arranged in a particular order. If you could devise an arithmetic where the result of each operation produces another number in the field the overflow issues could be avoided. The generation (ordering) of the field is key. e.g. a simple monotonic series from 0 to 255 is a finite field BUT modulo 255 arithmetic fails commutative tests i.e. certain operations will not reverse.

A Galois field gf(p) is the element 0 followed by the (p-1) succeeding powers of α : 1, α, α1, α2, ..., αp-1

Extending the gf(2) field used in binary arithmetic (and CRC calculation) to 256 elements that fit nicely in a computer byte: gf(28) = gf(256). Substituting the primitive element α=2 in the galois field it becomes 0, 1, 2, 4, 8, 16, and so on. This series is straightforward until elements greater than 127 are created. Doubling element values 128, 129, ..., 254 will violate the range by producing a result greater than 255. Some way must be devised to "fold" the results back into the finite field range without duplicating existing elements (this lets modulo 255 aritmetic out). This requires an irreducible primitive polynomial. "Irreducible" means it cannot be factored into smaller polynomials over the field.
Without this mathematical insight it is possible to search for suitable numbers using empirical methods. There has to be some way of turning off bit 8 so an XOR operation on results greater than 255 with a number in the range 256 to 256+255 will find "irreducible primitive polynomial" if they exist. A "brute force" scanning program [source] checks each candidate and rejects potential polynomials if they duplicate existing elements in the field.

Table 1. The following 16 candidate primitive polynomials are found. α=2
element->
of gf(256)
0 α0α1α2α3α4α5α6α7α8α9α10α11α12α13α14α15α16α17α18α19α20α21α22α23α24α25α26α27α28α29α30α31α32α33α34α35α36α37α38α39α40α41α42α43α44α45α46α47α48α49α50α51α52α53α54α55α56α57α58α59α60α61α62α63α64α65α66α67α68α69α70α71α72α73α74α75α76α77α78α79α80α81α82α83α84α85α86α87α88α89α90α91α92α93α94α95α96α97α98α99α100α101α102α103α104α105α106α107α108α109α110α111α112α113α114α115α116α117α118α119α120α121α122α123α124α125α126α127α128α129α130α131α132α133α134α135α136α137α138α139α140α141α142α143α144α145α146α147α148α149α150α151α152α153α154α155α156α157α158α159α160α161α162α163α164α165α166α167α168α169α170α171α172α173α174α175α176α177α178α179α180α181α182α183α184α185α186α187α188α189α190α191α192α193α194α195α196α197α198α199α200α201α202α203α204α205α206α207α208α209α210α211α212α213α214α215α216α217α218α219α220α221α222α223α224α225α226α227α228α229α230α231α232α233α234α235α236α237α238α239α240α241α242α243α244α245α246α247α248α249α250α251α252α253α254
pp = 285    0124816326412829581162322051351938761524590180117234201143361224489619215739781563774148531062121811192381931593570140510204080160931861052101851112221619519097194153479418810120213715306012024025323121118710721417712725422522316391182113226217175671341734681361326521042081891032061293162124248237199147591182361971515110220413323469218410921816979158336613221428416877154418216485170731465711422821318311523020919199198145631262522292151791232462412552272191717515049981961495511022016587174651302550100200141714285611222422116783166811628917812124224923919515543861726913891836721446112224424524724325123520313911224488176125250233207131275410821617371142
pp = 299    0124816326412843861721152302312292252332492171532550100200187931869519087174119238247197161105210143531062121314590180671343978156193876152275410821615529581162322512211459183672144112244881767515071428561122242352532091375711422822723724120118589178791582346921849118271142551102201471326521042081396112224419517311322623924519316912124220718165130479418883166103206183691386312625221114149981961631092181592142841681232461991659719417511723425521312941821649919816710120219185170127254215133336613235701405110220417977154316212424821915717346813659118236243205177731461530601202402031898116211122215151020408016010721413537741483612244896192171125250223149
pp = 301    0124816326412845901806913857114228229231227235251219155275410821615723469218493186891787314691836721441326521042081415511022014971428561122242372471951711232461931751152302252392432031879118265130418216410120218595190811621052101376312625221313535701405310621213339781562142841681252502171591938761522958116232253215131438617211723424922314711224488176771542550100200189871741132262332552111395911823624519916310721412947941888517012124220119183166971941691272542091435110220418171142499819616510320617779158173468136611222441971679919816111122214515306012024020518367134336613237741485102040801601092181533162124248221151361224489619217311923824120717975150
pp = 333    0124816326412877154121242169316212424818955110220245167361224489619220521522713991182336613269138891784182164510204080160132652104208237151991981932072112351551232461611530601202401732346921846112224416571428561122241418717417346813693186571142281337114281162918367214410921824919151102204213231131751509719420122324317127541082162531833570140851702550100200221247163112244881764590180377414810120221725517943861722142841682958116232157119238145111222241175193876152125250185631262521813978156117234153127254177479418853106212229135671346513073146105210233159115230129791581132261379519049981961971991952032192511875911823614910320620923914710721422514383166
pp = 351    0124816326412895190357014071142671348316619387615211122222715310921823513777154107214243185459018055110220231145125250171918367214412725416325501002002071932212291491172341397314612324617957114228151113226155105210251169132652104208255161295811623214365130911825110220419920925316521428416815306012024019133661328717436122448961922232251571012022032012051972132451815310621224717761122244183499819621524118937741481192381318917859118236135811622754108216239129931864386172714285611222415997194219233141691387515011523014712124218741821642346921844794188397815610320619521723713385170112244881766312625216717346813679158991982112491735102040801603162124248175
pp = 355    0124816326412899198239189255010020024313310521019923718517346813611523017561122244139117234183132652104208195229169499819623518191836721446713411122222322121720919322516133661321072142072531538116239781569118215306012024013110120224714112124213510921821520524914565130103206255157891787142856112224163377414875150791589519031621242481476913811923819129581162321795102040801603570140123246143125250151771548717463126252155851705511022021921320124112997194231173571142281715310621220324513711322616745901801122448817636122448961922271654182164438617259118236187214284168511022042511497314671142127254159931862346921841938761528316647941882754108216211197233177
pp = 357    0124816326412810120224113510721420124713911523016955110220221223219211195227163357014012525014571142121242129103206249151751507314665130971942251674386172611222441411272541538717457114228173631262521579519025501002002451431232461371192381852346921842142841685310621220525515583166418216445901801326521042081972391871938761528517049981962371912754108216213207251147671341052101932311715110220425315991182918367214469138113226161397815693186173468136117234177714285611222416547941882958116232181153060120240133111222217215203243131991982331831122448817651020408016037741487715481162336613210921820919923517936122448961922291755911823618931621242481497915889178
pp = 361    0124816326412810521020524314311923818136122448961922331873162124248153911825102040801604182164336613297194237179153060120240137123246133991982291634794188173468136121242141115230165357014011322617351102204241139127254149671341012022531477915885170611222441291072141972271755511022020920325515171142117234189193876152891781326521042082012511598717453106212193235191234692184255010020024915595190214284168571142281614386172499819622517163126252145751506913812525015783166377414865130109218221211207247135103206245131111222213195239183714285611222416959118236177112244881769183672144731467715493186295811623218527541082162172192232151992311673978156811624590180
pp = 369    0124816326412811322618127541082161932431519519013265210420820921121522320723917547941889183672144811625310621221719524715979158771546913810120222918771428561122241771938761526513011723416559118236169357014010521021321919925514311122220523516763126252137991982531391032062371713978156731468517037741488917821428416833661321212421499118229581162321615110220423316355110220201227183316212424812911523018911224488176173468136971942451557114210921819725113512725414110721422120323119115306012024014583166611222441536713412525013312324615775150931865102040801604998196249131119238173438617241821645711422818536122448961922411478717445901802550100200225179234692184
pp = 391    0124816326412813513714917322161122244111222591182369519025111322667134139145165205295811623287174219499819615306012024010320627541082165511022063126252127254123246107214438617222357114228791581872411012021938761521832338517021133661321431531812379318624397194361224489619271428561122247114215517722977154179225691381471611971326521042083978156191249117234831662031734681361511692134590180239891782276513013112913314115718925312525011523075150171209377414817521753106212479418825512124299198112244881762317314616319351020408016019991836721441672012142841682154182164207255010020023469218424710521035701401591852451092185110220431621242481192389118223581162195
pp = 397    0124816326412814115116320327541082166112224410120225501002002958116232931862491272541132267314616922351102204214284168221551102205310621237741481651993612244896192132652104208459018022971142145175211438617221339781561812316713412914314717121959118236851702176312625211723489178233951902411112224998196510204080160205234692184253119238811622013162124248125250121242105210418216419771428561122247715418525511523065130137159179235911822257915817723983166193153060120240109218571142286913815319124310721433661321331351311391551872511232469719491836721441732153570140149167195112244881762378717420947941882451032061734681361571832277515016120719387615218924799198
pp = 425    0124816326412816925195190213361224489619241821642251072145102040801602331232466913818921115306012024073146141179207551102201734681361852193162124248891782055110220449981963366132161235127254851702538316622999198377414812917125587174245671341652271112222142841682499118219735701401772036312625281162237115230101202611222446513017324379158149131175247711421811954794188209112244881762015911823611322610921829581162321212427715415714714318319939781561451391912157142856112224105210132652104208918367214413718722323469218421727541082162550100200571142289719445901801934386172241751501331632391192381172341252509318622119387615215315515915113516723110320653106212
pp = 451    0124816326412819569138215109218119238316212424851102204911821751572494998196751502392958116232193876152243377414823521428416814722991836721442275102040801601311977314623113265210420899198791582556112224443861721552454182164139213105210103206951901911891851771611291936513019977154247459018017114923317346813621110120287174159253571142281122448817616313320181162135205891781671412171132267142856112224361224489619267134207931861831731532413366132203851701512372550100200831661432211212423978156251531062121072141112221272546312625259118236275410821611523015306012024035701402191172342346921841791651372099719471142223125250551102201232464794188187181169145225
pp = 463    0124816326412820781162139217125250591182362346921841911771731492295102040801601432091092181232463570140215971947515022791836721442391734681362231132261122448817617514523721428416815924145901801671292058517015524961122244397815624733661321996513020389178171153253531062121032068316613120193186187185189181165133197691382191212424386172151225132652104208111222115230361224489619279158243418216413519377154251571142287142856112224153060120240479418818316114121310120291182163137221117234275410821612725451102204871741472332958116232316212424863126252551102201192381938761522554998196711422111052101072149919867134195731462352550100200951901791691572453774148231
pp = 487    0124816326412823141821641751851492051252501938761522157314619597194991981072147515020311322635701402552550100200119238591182366312625231621242482346921841512011172345110220412725427541082168717418714519710921883166171177133237611222441530601202407142856112224397815622389178131225377414820712124236122448961921032061232461122448817613523353106212791582198116216316116517318915722193186147193101202115230438617219115321377154211651302273366132239571142284794188159217851701791292294590180143249214284168183137245132652104208711422511734681362479183672144199105210671342354998196111222911821392415102040801601671691811412532958116232551102209519015520969138243
pp = 501    0124816326412824531621242485102040801601811592039919812124217346813622963126252132652104208851701611831551951152305711422861122244295811623237741482217915820110320610521081162177151219671342497142856112224531062129318612924727541082166913822555110220771541931192384182164189143235357014023747941881412394386172173175171163179147211831661851352513612244896192117234336613225315306012024021428416816519113922751102204109218651302412346921841332551122448817614922375150217711422333978156205111222731462098717416916718713124319387615219712725491836721442139519013723159118236459018015720710721489178145215911821531991232462550100200101202971941132264998196125250

In fact, the Reed-Solomon calculation in the DATAMATRIX (and most other symbologies) barcodes are specified to use the Galois field created by using the primitive polynomial
pp = 301 = x8+x5+x3+x2+1
The Galois field for the QRCODE barcode and our Reed-Solomon calculator is specified in the standard ISO 18004 as
pp = 285 = x8+x4+x3+x2+1

Closed Field Arithmetic using numbers generated by a single primitive polynomial has ADDITION, SUBTRACTION, DIVISION, and MULTIPLICATION operations but they are not the same as normal binary arithmetic. To calculate ECC (error correction codes) a large polynomial representing incoming data is divided by another "generator" polynomial.
f(x) ÷ gp(n) --> r(x)
The message followed by the ECC produced in r(x) are sent to a decoder. If the operation can be repeated and the same ECC is produced then the message is intact and no error correction is required. If some bits are corrupted then an iterative process is engaged to locate and (if a number of equations are soluble) correct the errors. If a solution cannot be found the message is left intact (there is a chance all the errors were in the ECC bytes).
The essence of "arithmetic" in the Galois field is that the computer is never confronted with numbers that are too large to process; The result of an operation applied to two numbers in the Galois field is devised to be another number within the field. The following operations "appear" to lose information by processing results back to numbers within range but, in fact, the factors of the results a MULTIPLICATION can still be derived.

     C:=PRODUCT(A,B);
     D:=QUOTIENT(C,A); // D is numerically equal to B 

The Galois arithmetic operations for GF(256) must be implemented as follows:

The ADDITION and SUBTRACTION of two numbers are both implemented by the bitwise exclusive-or of the two numbers.
N.B. In Galois arithmetic A - B is the same as A + B.
e.g.
Given that A=1510     = 000011112
and        B=610      = 000001102
then  A + B = A - B   = 000010012  = 910 
     function addition(a,b:byte):byte;
     begin
       result:=a xor b;
     end;
     function subtraction(a,b:byte):byte;
     begin
       result:=a xor b;
     end;
The PRODUCT of A and B is the ANTILOG of the MODULUS 255 sum of their LOGS. The LOG and ANTILOG functions can be pre-calculated as tables. We have already computed the ANTILOG for a given primitive polynomial (pp=285) in TABLE 1.
i.e. An array of 255 bytes = 1, 2, 4, 8, 16, 32, 64, 128, 29, ..., 142

A LOGARITHM is the of a number to a given base is the power or exponent the base must be raised to produce that number. The LOG array is thus indexed from 1 to 255 = 0, 1, 25, ..., 175 e.g. LOG[255]=175 , ANTILOG[175]=255
     function product(a,b:byte):byte;
     begin
       result:=ANTILOG[(LOG[a]+LOG[b]) mod 255];
     end;
The QUOTIENT of two values is the ANTILOG of the MODULO 255 difference between the LOG of the two values.
     function quotient(a,b:byte):byte;
     begin // i.e a divided by b
       if (b=0) then result:=255 {an error}
       else if (a=0) then result:=0 else
       result:=ANTILOG[(LOG[a]-LOG[b]) MOD 255];
     end;