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:

a_nxⁿ + a_n-1x^n-1 + ... + a₂x² + a₁x + a₀

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

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 = x⁸+x⁵+x³+x²+1
The Galois field for the QRCODE barcode and our Reed-Solomon calculator is specified in the standard ISO 18004 as
pp = 285 = x⁸+x⁴+x³+x²+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=15₁₀     = 00001111₂
and        B=6₁₀      = 00000110₂
then  A + B = A - B  = 00001001₂  = 9₁₀

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;