Description

The following is a list of primitive irreducible polynomials for generating elements of a binary extension field GF(2^m) from a base finite field. The list contains polynomials of degree 2 to 32.

Downloads

primitive_polynomials_GF2.txt
primitive_polynomials_GF2_extended.zip

Degree 2

x^2 + x^1 + 1
                       

Degree 3

x^3 + x^1 + 1
                       

Degree 4

x^4 + x^1 + 1
                       

Degree 5

x^5 + x^2 + 1
x^5 + x^4 + x^2 + x^1 + 1
x^5 + x^4 + x^3 + x^2 + 1
                       

Degree 6

x^6 + x^1 + 1
x^6 + x^5 + x^2 + x^1 + 1
x^6 + x^5 + x^3 + x^2 + 1
                       

Degree 7

x^7 + x^1 + 1
x^7 + x^3 + 1
x^7 + x^3 + x^2 + x^1 + 1
x^7 + x^4 + x^3 + x^2 + 1
x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^7 + x^6 + x^3 + x^1 + 1
x^7 + x^6 + x^4 + x^2 + 1
x^7 + x^6 + x^5 + x^2 + 1
x^7 + x^6 + x^5 + x^4 + x^2 + x^1 + 1
                       

Degree 8

x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x^1 + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x^1 + 1
x^8 + x^6 + x^5 + x^1 + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^7 + x^6 + x^1 + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x^1 + 1
                       

Degree 9

x^9 + x^4 + 1
x^9 + x^5 + x^3 + x^2 + 1
x^9 + x^6 + x^4 + x^3 + 1
x^9 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
x^9 + x^6 + x^5 + x^4 + x^2 + x^1 + 1
x^9 + x^7 + x^6 + x^4 + x^3 + x^1 + 1
x^9 + x^8 + x^4 + x^1 + 1
x^9 + x^8 + x^5 + x^4 + 1
x^9 + x^8 + x^6 + x^5 + 1
x^9 + x^8 + x^6 + x^5 + x^3 + x^1 + 1
x^9 + x^8 + x^7 + x^2 + 1
x^9 + x^8 + x^7 + x^3 + x^2 + x^1 + 1
x^9 + x^8 + x^7 + x^6 + x^5 + x^1 + 1
x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + 1
                       

Degree 10

x^10 + x^3 + 1
x^10 + x^4 + x^3 + x^1 + 1
x^10 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
x^10 + x^8 + x^3 + x^2 + 1
x^10 + x^8 + x^4 + x^3 + 1
x^10 + x^8 + x^5 + x^1 + 1
x^10 + x^8 + x^5 + x^4 + 1
x^10 + x^8 + x^7 + x^6 + x^5 + x^2 + 1
x^10 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^1 + 1
x^10 + x^9 + x^4 + x^1 + 1
x^10 + x^9 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^10 + x^9 + x^8 + x^6 + x^3 + x^2 + 1
x^10 + x^9 + x^8 + x^6 + x^5 + x^1 + 1
x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
                       

Degree 11

x^11 + x^2 + 1
x^11 + x^5 + x^3 + x^1 + 1
x^11 + x^5 + x^3 + x^2 + 1
x^11 + x^6 + x^5 + x^1 + 1
x^11 + x^7 + x^3 + x^2 + 1
x^11 + x^8 + x^5 + x^2 + 1
x^11 + x^8 + x^6 + x^5 + x^4 + x^1 + 1
x^11 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^11 + x^9 + x^4 + x^1 + 1
x^11 + x^9 + x^8 + x^7 + x^4 + x^1 + 1
x^11 + x^10 + x^3 + x^2 + 1
x^11 + x^10 + x^7 + x^4 + x^3 + x^1 + 1
x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + 1
x^11 + x^10 + x^9 + x^8 + x^3 + x^1 + 1
                       

Degree 12

x^12 + x^6 + x^4 + x^1 + 1
x^12 + x^9 + x^3 + x^2 + 1
x^12 + x^9 + x^8 + x^3 + x^2 + x^1 + 1
x^12 + x^10 + x^9 + x^8 + x^6 + x^2 + 1
x^12 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^2 + 1
x^12 + x^11 + x^6 + x^4 + x^2 + x^1 + 1
x^12 + x^11 + x^9 + x^5 + x^3 + x^1 + 1
x^12 + x^11 + x^9 + x^7 + x^6 + x^4 + 1
x^12 + x^11 + x^9 + x^7 + x^6 + x^5 + 1
x^12 + x^11 + x^9 + x^8 + x^7 + x^4 + 1
x^12 + x^11 + x^9 + x^8 + x^7 + x^5 + x^2 + x^1 + 1
x^12 + x^11 + x^10 + x^5 + x^2 + x^1 + 1
x^12 + x^11 + x^10 + x^8 + x^6 + x^4 + x^3 + x^1 + 1
x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + 1
                       

Degree 13

x^13 + x^4 + x^3 + x^1 + 1
x^13 + x^9 + x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^13 + x^9 + x^8 + x^7 + x^5 + x^1 + 1
x^13 + x^10 + x^9 + x^7 + x^5 + x^4 + 1
x^13 + x^10 + x^9 + x^8 + x^6 + x^3 + x^2 + x^1 + 1
x^13 + x^11 + x^8 + x^7 + x^4 + x^1 + 1
x^13 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^13 + x^12 + x^6 + x^5 + x^4 + x^3 + 1
x^13 + x^12 + x^8 + x^7 + x^6 + x^5 + 1
x^13 + x^12 + x^9 + x^8 + x^4 + x^2 + 1
x^13 + x^12 + x^10 + x^8 + x^6 + x^4 + x^3 + x^2 + 1
x^13 + x^12 + x^11 + x^5 + x^2 + x^1 + 1
x^13 + x^12 + x^11 + x^8 + x^7 + x^6 + x^4 + x^1 + 1
x^13 + x^12 + x^11 + x^9 + x^5 + x^3 + 1
                       

Degree 14

x^14 + x^8 + x^6 + x^1 + 1
x^14 + x^10 + x^6 + x^1 + 1
x^14 + x^10 + x^9 + x^7 + x^6 + x^4 + x^3 + x^1 + 1
x^14 + x^11 + x^6 + x^1 + 1
x^14 + x^11 + x^9 + x^6 + x^5 + x^2 + 1
x^14 + x^12 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + 1
x^14 + x^12 + x^11 + x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + x^1 + 1
x^14 + x^12 + x^11 + x^10 + x^9 + x^7 + x^4 + x^3 + 1
x^14 + x^13 + x^6 + x^5 + x^3 + x^1 + 1
x^14 + x^13 + x^10 + x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^14 + x^13 + x^11 + x^6 + x^5 + x^4 + x^2 + x^1 + 1
x^14 + x^13 + x^11 + x^8 + x^5 + x^3 + x^2 + x^1 + 1
x^14 + x^13 + x^12 + x^11 + x^10 + x^7 + x^6 + x^1 + 1
x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^6 + x^5 + 1
                       

Degree 15

x^15 + x^1 + 1
x^15 + x^4 + 1
x^15 + x^7 + 1
x^15 + x^7 + x^6 + x^3 + x^2 + x^1 + 1
x^15 + x^10 + x^5 + x^1 + 1
x^15 + x^10 + x^5 + x^4 + 1
x^15 + x^10 + x^5 + x^4 + x^2 + x^1 + 1
x^15 + x^10 + x^9 + x^7 + x^5 + x^3 + 1
x^15 + x^10 + x^9 + x^8 + x^5 + x^3 + 1
x^15 + x^11 + x^7 + x^6 + x^2 + x^1 + 1
x^15 + x^12 + x^3 + x^1 + 1
x^15 + x^12 + x^5 + x^4 + x^3 + x^2 + 1
x^15 + x^12 + x^11 + x^8 + x^7 + x^6 + x^4 + x^2 + 1
x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1
                       

Degree 16

x^16 + x^9 + x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^16 + x^12 + x^3 + x^1 + 1
x^16 + x^12 + x^7 + x^2 + 1
x^16 + x^13 + x^12 + x^10 + x^9 + x^7 + x^6 + x^1 + 1
x^16 + x^13 + x^12 + x^11 + x^7 + x^6 + x^3 + x^1 + 1
x^16 + x^13 + x^12 + x^11 + x^10 + x^6 + x^2 + x^1 + 1
x^16 + x^14 + x^10 + x^8 + x^3 + x^1 + 1
x^16 + x^14 + x^13 + x^12 + x^6 + x^5 + x^3 + x^2 + 1
x^16 + x^14 + x^13 + x^12 + x^10 + x^7 + 1
x^16 + x^15 + x^10 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
x^16 + x^15 + x^11 + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
x^16 + x^15 + x^11 + x^10 + x^7 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
x^16 + x^15 + x^11 + x^10 + x^9 + x^6 + x^2 + x^1 + 1
x^16 + x^15 + x^11 + x^10 + x^9 + x^8 + x^6 + x^4 + x^2 + x^1 + 1
                       

Degree 17

x^17 + x^3 + 1
x^17 + x^3 + x^2 + x^1 + 1
x^17 + x^5 + 1
x^17 + x^6 + 1
x^17 + x^8 + x^4 + x^3 + 1
x^17 + x^8 + x^7 + x^6 + x^4 + x^3 + 1
x^17 + x^10 + x^9 + x^8 + x^6 + x^5 + x^3 + x^2 + 1
x^17 + x^12 + x^6 + x^3 + x^2 + x^1 + 1
x^17 + x^12 + x^9 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^17 + x^12 + x^9 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^17 + x^14 + x^11 + x^7 + x^5 + x^3 + x^2 + x^1 + 1
x^17 + x^15 + x^13 + x^11 + x^9 + x^7 + x^5 + x^3 + 1
x^17 + x^15 + x^13 + x^11 + x^9 + x^7 + x^6 + x^4 + x^2 + x^1 + 1
x^17 + x^16 + x^3 + x^1 + 1
                       

Degree 18

x^18 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^18 + x^7 + 1
x^18 + x^7 + x^5 + x^2 + x^1 + 1
x^18 + x^8 + x^2 + x^1 + 1
x^18 + x^9 + x^7 + x^6 + x^5 + x^4 + 1
x^18 + x^9 + x^8 + x^6 + x^5 + x^4 + x^2 + x^1 + 1
x^18 + x^9 + x^8 + x^7 + x^6 + x^4 + x^2 + x^1 + 1
x^18 + x^10 + x^7 + x^5 + 1
x^18 + x^10 + x^8 + x^5 + 1
x^18 + x^10 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^18 + x^10 + x^9 + x^3 + 1
x^18 + x^13 + x^6 + x^4 + 1
x^18 + x^15 + x^5 + x^2 + 1
x^18 + x^15 + x^9 + x^2 + 1
                       

Degree 19

x^19 + x^5 + x^2 + x^1 + 1
x^19 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^19 + x^6 + x^2 + x^1 + 1
x^19 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
x^19 + x^6 + x^5 + x^4 + x^3 + x^2 + 1
x^19 + x^7 + x^5 + x^3 + x^2 + x^1 + 1
x^19 + x^8 + x^7 + x^5 + 1
x^19 + x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^19 + x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + x^1 + 1
x^19 + x^9 + x^8 + x^5 + 1
x^19 + x^9 + x^8 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
x^19 + x^9 + x^8 + x^7 + x^4 + x^3 + x^2 + x^1 + 1
x^19 + x^11 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1
x^19 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^19 + x^16 + x^13 + x^10 + x^7 + x^4 + x^1 + 1
                       

Degree 20

x^20 + x^3 + 1
x^20 + x^9 + x^5 + x^3 + 1
x^20 + x^11 + x^8 + x^6 + x^3 + x^2 + 1
x^20 + x^14 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + 1
x^20 + x^17 + x^14 + x^10 + x^7 + x^4 + x^3 + x^2 + 1
x^20 + x^19 + x^4 + x^3 + 1
                       

Degree 21

x^21 + x^2 + 1
x^21 + x^8 + x^7 + x^4 + x^3 + x^2 + 1
x^21 + x^10 + x^6 + x^4 + x^3 + x^2 + 1
x^21 + x^13 + x^5 + x^2 + 1
x^21 + x^14 + x^7 + x^2 + 1
x^21 + x^14 + x^7 + x^6 + x^3 + x^2 + 1
x^21 + x^14 + x^12 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^21 + x^15 + x^10 + x^9 + x^5 + x^4 + x^3 + x^2 + 1
x^21 + x^20 + x^19 + x^18 + x^5 + x^4 + x^3 + x^2 + 1
                       

Degree 22

x^22 + x^1 + 1
x^22 + x^9 + x^5 + x^1 + 1
x^22 + x^14 + x^13 + x^12 + x^7 + x^3 + x^2 + x^1 + 1
x^22 + x^17 + x^9 + x^7 + x^2 + x^1 + 1
x^22 + x^17 + x^13 + x^12 + x^8 + x^7 + x^2 + x^1 + 1
x^22 + x^20 + x^18 + x^16 + x^6 + x^4 + x^2 + x^1 + 1
                       

Degree 23

x^23 + x^5 + 1
x^23 + x^5 + x^4 + x^1 + 1
x^23 + x^11 + x^10 + x^7 + x^6 + x^5 + 1
x^23 + x^12 + x^5 + x^4 + 1
x^23 + x^15 + x^10 + x^9 + x^7 + x^5 + x^4 + x^3 + 1
x^23 + x^16 + x^13 + x^6 + x^5 + x^3 + 1
x^23 + x^17 + x^11 + x^5 + 1
x^23 + x^17 + x^11 + x^9 + x^8 + x^5 + x^4 + x^1 + 1
x^23 + x^18 + x^16 + x^13 + x^11 + x^8 + x^5 + x^2 + 1
x^23 + x^21 + x^7 + x^5 + 1
                       

Degree 24

x^24 + x^7 + x^2 + x^1 + 1
x^24 + x^21 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^10 + x^9 + x^5 + x^4 + x^1 + 1
x^24 + x^22 + x^20 + x^18 + x^16 + x^14 + x^11 + x^9 + x^8 + x^7 + x^5 + x^4 + 1
                       

Degree 25

x^25 + x^3 + 1
x^25 + x^3 + x^2 + x^1 + 1
x^25 + x^11 + x^9 + x^8 + x^6 + x^4 + x^3 + x^2 + 1
x^25 + x^12 + x^4 + x^3 + 1
x^25 + x^12 + x^11 + x^8 + x^7 + x^6 + x^4 + x^3 + 1
x^25 + x^17 + x^10 + x^3 + x^2 + x^1 + 1
x^25 + x^18 + x^12 + x^11 + x^6 + x^5 + x^4 + x^3 + 1
x^25 + x^20 + x^5 + x^3 + 1
x^25 + x^20 + x^16 + x^11 + x^5 + x^3 + x^2 + x^1 + 1
x^25 + x^23 + x^21 + x^19 + x^9 + x^7 + x^5 + x^3 + 1
                       

Degree 26

x^26 + x^6 + x^2 + x^1 + 1
x^26 + x^19 + x^16 + x^15 + x^14 + x^13 + x^11 + x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + x^2 + 1
x^26 + x^21 + x^18 + x^16 + x^15 + x^13 + x^12 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1
x^26 + x^22 + x^20 + x^19 + x^16 + x^13 + x^11 + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
x^26 + x^22 + x^21 + x^16 + x^12 + x^11 + x^10 + x^8 + x^5 + x^4 + x^3 + x^1 + 1
x^26 + x^23 + x^22 + x^21 + x^19 + x^18 + x^15 + x^14 + x^13 + x^11 + x^10 +x^9+x^8+x^6+x^5+x^2+ 1
x^26 + x^24 + x^21 + x^17 + x^16 + x^14 + x^13 + x^11 + x^7 + x^6 + x^4 + x^1 + 1
                       

Degree 27

x^27 + x^5 + x^2 + x^1 + 1
x^27 + x^18 + x^11 + x^10 + x^9 + x^5 + x^4 + x^3 + 1
x^27 + x^22 + x^13 + x^11 + x^6 + x^5 + x^4 + x^3 + 1
x^27 + x^22 + x^17 + x^15 + x^14 + x^13 + x^6 + x^1 + 1
x^27 + x^22 + x^21 + x^20 + x^18 + x^17 + x^15 + x^13 + x^12 + x^7 + x^5 + 1
x^27 + x^24 + x^19 + x^16 + x^12 + x^8 + x^7 + x^3 + x^2 + x^1 + 1
x^27 + x^24 + x^21 + x^19 + x^16 + x^13 + x^11 + x^9 + x^6 + x^5 + x^4 + x^3 + 1
x^27 + x^25 + x^23 + x^21 + x^13 + x^11 + x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
x^27 + x^25 + x^23 + x^21 + x^20 + x^19 + x^18 + x^16 + x^14 + x^10 + x^8 + x^7 + x^4 + x^3 + 1
                       

Degree 28

x^28 + x^3 + 1
x^28 + x^13 + x^11 + x^9 + x^5 + x^3 + 1
x^28 + x^18 + x^17 + x^16 + x^9 + x^5 + x^4 + x^3 + 1
x^28 + x^19 + x^17 + x^15 + x^10 + x^6 + x^3 + x^2 + 1
x^28 + x^22 + x^11 + x^10 + x^4 + x^3 + 1
x^28 + x^24 + x^20 + x^16 + x^12 + x^8 + x^4 + x^3 + 1
                       

Degree 29

x^29 + x^2 + 1
x^29 + x^12 + x^7 + x^2 + 1
x^29 + x^18 + x^14 + x^6 + x^3 + x^2 + 1
x^29 + x^19 + x^16 + x^6 + x^3 + x^2 + 1
x^29 + x^20 + x^11 + x^2 + 1
x^29 + x^20 + x^16 + x^11 + x^8 + x^4 + x^3 + x^2 + 1
x^29 + x^21 + x^5 + x^2 + 1
x^29 + x^23 + x^10 + x^9 + x^5 + x^4 + x^3 + x^2 + 1
x^29 + x^24 + x^14 + x^13 + x^8 + x^4 + x^3 + x^2 + 1
x^29 + x^26 + x^5 + x^2 + 1
                       

Degree 30

x^30 + x^23 + x^2 + x^1 + 1
x^30 + x^24 + x^20 + x^16 + x^14 + x^13 + x^11 + x^7 + x^2 + x^1 + 1
x^30 + x^24 + x^21 + x^20 + x^18 + x^15 + x^13 + x^12 + x^9 + x^7 + x^6 + x^4 + x^3 + x^1 + 1
x^30 + x^25 + x^24 + x^23 + x^19 + x^18 + x^16 + x^14 + x^11 + x^8 + x^6 + x^4 + x^3 + x^1 + 1
x^30 + x^27 + x^25 + x^24 + x^23 + x^22 + x^19 + x^16 + x^12 + x^10 + x^8 + x^7 + x^6 + x^1 + 1
                       

Degree 31

x^31 + x^3 + 1
x^31 + x^3 + x^2 + x^1 + 1
x^31 + x^13 + x^8 + x^3 + 1
x^31 + x^16 + x^8 + x^4 + x^3 + x^2 + 1
x^31 + x^20 + x^15 + x^5 + x^4 + x^3 + 1
x^31 + x^20 + x^18 + x^7 + x^5 + x^3 + 1
x^31 + x^21 + x^12 + x^3 + x^2 + x^1 + 1
x^31 + x^23 + x^22 + x^15 + x^14 + x^7 + x^4 + x^3 + 1
x^31 + x^25 + x^19 + x^14 + x^7 + x^3 + x^2 + x^1 + 1
x^31 + x^27 + x^23 + x^19 + x^15 + x^11 + x^7 + x^3 + 1
x^31 + x^27 + x^23 + x^19 + x^15 + x^11 + x^10 + x^9 + x^7 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
                       

Degree 32

x^32 + x^22 + x^2 + x^1 + 1
x^32 + x^22 + x^21 + x^20 + x^18 + x^17 + x^15 + x^13 + x^12 + x^10 + x^8 + x^6 + x^4 + x^1 + 1
x^32 + x^23 + x^17 + x^16 + x^14 + x^10 + x^8 + x^7 + x^6 + x^5 + x^3 + 1
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
x^32 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^17 + x^13 + x^11 + x^10+x^9+x^8+x^7+x^2+x^1 + 1
x^32 + x^28 + x^19 + x^18 + x^16 + x^14 + x^11 + x^10 + x^9 + x^6 + x^5 + x^1 + 1
                       

Credits

• Coherent Spread Spectrum Systems - J.K. Holmes
• Digital Communications And Spread Spectrum Systems - Rodger E. Ziemer and Roger L. Peterson
• Error Control Coding - S. Lin, D. Costello
• Error Correction Codes - W.W. Peterson And E.J. Weldon
• On Primitive Trinomials - N. Zierler and J. Brillhart
• Primitive Polynomials (Mod 2) - By E.J. Watson
• Sequence A011260/M0107 - N. J. A. Sloane
• Tables of Irreducible Polynomials For The First Four Prime Moduli - R. Church

QR codes are 2-dimensional bar codes that encode arbitrary text strings. A common use of QR codes is to encode URLs so that people can scan a QR code (for example, on an advertising poster, building roof, volleyball bikini, belt buckle, or airplane banner) to load a web site on a cell phone instead of having to “type” in a URL.

QR codes are encoded using Reed-Solomon error-correcting codes, so that a QR scanner does not have to see every pixel correctly in order to decode the content. The error correction makes it possible to introduce a few errors (fewer than the maximum that the algorithm can fix) in order to make an image. For example, in 2008, Duncan Robertson took a QR code for “http://bbc.co.uk/programmes” (left) and introduced errors in the form of a BBC logo (right):

That's a neat trick and a pretty logo, but it's uninteresting from a technical standpoint. Although the BBC logo pixels look like QR code pixels, they are not contribuing to the QR code. The QR reader can't tell much difference between the BBC logo and the Union Jack. There's just a bunch of noise in the middle either way.

Since the BBC QR logo appeared, there have been many imitators. Most just slap an obviously out-of-place logo in the middle of the code. This Disney poster is notable for being more in the spirit of the BBC code.

There's a different way to put pictures in QR codes. Instead of scribbling on redundant pieces and relying on error correction to preserve the meaning, we can engineer the encoded values to create the picture in a code with no inherent errors, like these:

This post explains the math behind making codes like these, which I call QArt codes. I have published the Go programs that generated these codes at code.google.com/p/rsc and created a web site for creating these codes.

Background

For error correction, QR uses Reed-Solomon coding (like nearly everything else). For our purposes, Reed-Solomon coding has two important properties. First, it is what coding theorists call a systematic code: you can see the original message in the encoding. That is, the Reed-Solomon encoding of “hello” is “hello” followed by some error-correction bytes. Second, Reed-Solomon encoded messages can be XOR'ed: if we have two different Reed-Solomon encoded blocks b₁ and b₂ corresponding to messages m₁ and m₂, b₁ ⊕ b₂ is also a Reed-Solomon encoded block; it corresponds to the message m₁ ⊕ m₂. (Here, ⊕ means XOR.) If you are curious about why these two properties are true, see my earlier post, Finite Field Arithmetic and Reed-Solomon Coding.

QR Codes

A QR code has a distinctive frame that help both people and computers recognize them as QR codes. The details of the frame depend on the exact size of the code—bigger codes have room for more bits—but you know one when you see it: the outlined squares are the giveaway. Here are QR frames for a sampling of sizes:

The colored pixels are where the Reed-Solomon-encoded data bits go. Each code may have one or more Reed-Solomon blocks, depending on its size and the error correction level. The pictures show the bits from each block in a different color. The L encoding is the lowest amount of redundancy, about 20%. The other three encodings increase the redundancy, using 38%, 55%, and 65%.

(By the way, you can read the redundancy level from the top pixels in the two leftmost columns. If black=0 and white=1, then you can see that 00 is L, 01 is M, 10 is Q, and 11 is H. Thus, you can tell that the QR code on the T-shirt in this picture is encoded at the highest redundancy level, while this shirt uses the lowest level and therefore might take longer or be harder to scan.

As I mentioned above, the original message bits are included directly in the message's Reed-Solomon encoding. Thus, each bit in the original message corresponds to a pixel in the QR code. Those are the lighter pixels in the pictures above. The darker pixels are the error correction bits. The encoded bits are laid down in a vertical boustrophedon pattern in which each line is two columns wide, starting at the bottom right corner and ending on the left side:

We can easily work out where each message bit ends up in the QR code. By changing those bits of the message, we can change those pixels and draw a picture. There are, however, a few complications that make things interesting.

QR Masks

The first complication is that the encoded data is XOR'ed with an obfuscating mask to create the final code. There are eight masks:

An encoder is supposed to choose the mask that best hides any patterns in the data, to keep those patterns from being mistaken for framing boxes. In our encoder, however, we can choose a mask before choosing the data. This violates the spirit of the spec but still produces legitimate codes.

QR Data Encoding

The second complication is that we want the QR code's message to be intelligible. We could draw arbitrary pictures using arbitrary 8-bit data, but when scanned the codes would produce binary garbage. We need to limit ourselves to data that produces sensible messages. Luckily for us, QR codes allow messages to be written using a few different alphabets. One alphabet is 8-bit data, which would require binary garbage to draw a picture. Another is numeric data, in which every run of 10 bits defines 3 decimal digits. That limits our choice of pixels slightly: we must not generate a 10-bit run with a value above 999. That's not complete flexibility, but it's close: 9.96 bits of freedom out of 10. If, after encoding an image, we find that we've generated an invalid number, we pick one of the 5 most significant bits at random—all of them must be 1s to make an invalid number—hard wire that bit to zero, and start over.

Having only decimal messages would still not be very interesting: the message would be a very large number. Luckily for us (again), QR codes allow a single message to be composed from pieces using different encodings. The codes I have generated consist of an 8-bit-encoded URL ending in a # followed by a numeric-encoded number that draws the actual picture:

The leading URL is the first data encoded; it takes up the right side of the QR code. The error correction bits take up the left side.

When the phone scans the QR code, it sees a URL; loading it in a browser visits the base page and then looks for an internal anchor on the page with the given number. The browser won't find such an anchor, but it also won't complain.

The techniques so far let us draw codes like this one:

The second copy darkens the pixels that we have no control over: the error correction bits on the left and the URL prefix on the right. I appreciate the cyborg effect of Peter melting into the binary noise, but it would be nice to widen our canvas.

Gauss-Jordan Elimination

The third complication, then, is that we want to draw using more than just the slice of data pixels in the middle of the image. Luckily, we can.

I mentioned above that Reed-Solomon messages can be XOR'ed: if we have two different Reed-Solomon encoded blocks b₁ and b₂ corresponding to messages m₁ and m₂, b₁ ⊕ b₂ is also a Reed-Solomon encoded block; it corresponds to the message m₁ ⊕ m₂. (In the notation of the previous post, this happens because Reed-Solomon blocks correspond 1:1 with multiples of g(x). Since b₁ and b₂ are multiples of g(x), their sum is a multiple of g(x) too.) This property means that we can build up a valid Reed-Solomon block from other Reed-Solomon blocks. In particular, we can construct the sequence of blocks b₀, b₁, b₂, ..., where b_i is the block whose data bits are all zeros except for bit i and whose error correction bits are then set to correspond to a valid Reed-Solomon block. That set is a basis for the entire vector space of valid Reed-Solomon blocks. Here is the basis matrix for the space of blocks with 2 data bytes and 2 checksum bytes:

The missing entries are zeros. The gray columns highlight the pixels we have complete control over: there is only one row with a 1 for each of those pixels. Each time we want to change such a pixel, we can XOR our current data with its row to change that pixel, not change any of the other controlled pixels, and keep the error correction bits up to date.

So what, you say. We're still just twiddling data bits. The canvas is the same.

But wait, there's more! The basis we had above lets us change individual data pixels, but we can XOR rows together to create other basis matrices that trade data bits for error correction bits. No matter what, we're not going to increase our flexibility—the number of pixels we have direct control over cannot increase—but we can redistribute that flexibility throughout the image, at the same time smearing the uncooperative noise pixels evenly all over the canvas. This is the same procedure as Gauss-Jordan elimination, the way you turn a matrix into row-reduced echelon form.

This matrix shows the result of trying to assert control over alternating pixels (the gray columns):

The matrix illustrates an important point about this trick: it's not completely general. The data bits are linearly independent, but there are dependencies between the error correction bits that mean we often can't have every pixel we ask for. In this example, the last four pixels we tried to get were unavailable: our manipulations of the rows to isolate the first four error correction bits zeroed out the last four that we wanted.

In practice, a good approach is to create a list of all the pixels in the Reed-Solomon block sorted by how useful it would be to be able to set that pixel. (Pixels from high-contrast regions of the image are less important than pixels from low-contrast regions.) Then, we can consider each pixel in turn, and if the basis matrix allows it, isolate that pixel. If not, no big deal, we move on to the next pixel.

Applying this insight, we can build wider but noisier pictures in our QR codes:

The pixels in Peter's forehead and on his right side have been sacrificed for the ability to draw the full width of the picture.

We can also choose the pixels we want to control at random, to make Peter peek out from behind a binary fog:

Rotations

One final trick. QR codes have no required orientation. The URL base pixels that we have no control over are on the right side in the canonical orientation, but we can rotate the QR code to move them to other edges.

Further Information

The source code for this post, including the web server, is at rsc.io/swtch/qrweb; the App Engine integration is at rsc.io/swtch/app/blog in qr.go. If you liked this, you might also like Zip Files All The Way Down.

Acknowledgements

Alex Healy pointed out that valid Reed-Solomon encodings are closed under XOR, which is the key to spreading the picture into the error correction pixels. Peter Weinberger has been nothing but gracious about the overuse of his binary likeness. Thanks to both.

Contents

Order-7 with Diamond Inlays

Order-7 Magic Square        S = 175 Order-4 Magic Diamond     S = 100 Order-3 Magic Diamond     S = 75 From The Magic Square Course, title page for chap. XII  (See bibliography at end of this page.)

Order-7 with Square Inlays

Order-7 Magic Square                 sum = 175 Order-4 (pink) Magic Square       sum = 100 Order-3 (blue) Magic Square       sum = 75 Corners of each of these 3 magic squares sum to 100 Uncolored squares sum as follows (in any direction): lines of 2 cells = 50 lines of 3 cells = 75 lines of 4 cells = 100 lines of 6 cells = 150 From The Magic Square Course, page 46

Order-9 with Diamond Inlays

S9 = 369 S7 = 287 S5 = 205 S3 = 123 This inlay may be used in place of the above order-5 inlay 42 34 49 30 50 22 39 61 23 60 51 25 41 57 31 58 59 21 43 24 32 48 33 52 40 From The Magic Square Course, page 191

Order-14 Ornamental

For a total of 9 magic squares.   By John Hendricks   (unpublished) MAGIC SUMS S14 = 1379 Top Sub-square S5 = 615 S3 = 369 Diamond    S4 = 100 S3 = 516 Bottom Sub-square S5 = 370 S3 = 222 Diamond S4 = 688 S3 = 75

Order-15 Overlapping

For a total of fifteen Magic squares From The Magic Square Course, page 232 MAGIC SUMS      S15 = 1695 Lower left & upper right 2 x S7 = 791 (pandiagonal) Upper left & lower right 2 x S8 = 904 10 x S4 = 452

Two related ten-in one

This order-8 magic square contains four order-4 magic squares in the quadrants and one order-4 in the center. It contains four more order-4 magic squares starting with the top left hand corner at 24, 59, 27 and 20 (outlined in blue). S4 = 130      S8 = 260 All ten of these magic squares have the additional feature that each of the four bent diagonals also sum correctly. Two of these bent diagonals in the top left hand order-4 are 1 + 64 + 3 + 62 and 1 + 64 + 17 + 48. An order-8 bent diagonal is 44 + 21 + 7 + 58 + 37 + 28 + 10 + 55. Figure 12a from Inlaid Magic Squares & Cubes, page 18

This order-8 magic square is pandiagonal. The four order-4 magic squares in the quadrants are also pandiagonal. The order-4 in the center and the four order-4 outlined in blue are regular magic squares. Figure 11h from Inlaid Magic Squares & Cubes (revised), page 17

Order-15 Composite

This order-15 magic square consists of 9 order-5 magic squares, each with an order-3 inlaid diamond magic square. As is common with composite magic squares, the magic sums of the order-5 squares themselves form an order-3 magic square with the constant 1695. The constants of the order-3 magic diamonds form an order-3 magic square with the constant 1017. S of Order-5 squares 560 645 490 495 565 635 640 485 570 S of Order-diamonds 336 387 294 297 339 381 384 291 342 From The Magic Square Course, page 244

Order-3 Magic Cube

9 rows, such as 1 - 17 - 24, sum to 42. 9 columns, such as 1 - 15 - 26, sum to 42. 9 Pillars, such as 1 - 23 - 18, sum to 42. 4 triagonals, such as 26 - 14 - 2 sum to 42. Some of the squares may have diagonals summing to 42, but this is not a requirement. In fact, order-8 is the smallest cube for which it is possible for all the diagonals to sum correctly. What is required is that the 4 triagonals or 3-agonals, such as 1 - 14 - 27 sum to 42. There are 4 different basic pure (using numbers 1 to 27) magic cubes. Each of these have 48 equivalents due to rotations and/or reflections. Just as the one order-3 magic square is associated, so also are the four order-3 magic cubes. Because they are associated, all are also self-similar. That is, when each number is subtracted from 28 the result is a reflection of itself. See my Self-similar Magic Squares. From The Magic Square Course, page 329.

Pan-3-agonal magic cube

16 rows sum to 130 16 columns sum to 130 16 pillars sum to 130 Four 3-dimensional diagonals sum to 130. All broken 3-agonals parallel to the 4 main triagonals also sum to 130. This is the equivalent to the pandiagonal Magic Square. Because it is pandiagonal, any face may be moved to the opposite side, thus creating a new pan-3-agonal magic cube. The numbers circled in red show one of the 4 main triagonals. In an order-4 cube it is impossible for all the diagonals parallel to the faces to be magic. John Hendricks coined the term pan-3-agonal for the broken space 3- agonals. There are 7680 pan-3-agonal magic cubes of order-4. The total number of Order-4 magic cubes is not known.

From The Magic Square Course, page 384.
This also appeared in The Journal of Recreational Mathematics, 5(1) p. 51-52.

Order-3 Magic Tesseract

This order-3 hypercube of four dimensions is shown in two dimensions using lines to depict the outer dimensions only. The colored numbers here show the middle cube in the horizontal plane. There are three cubes also in each of the other three planes. 27 rows, such as 50 - 12 - 61, sum to 123. 27 columns, such as 50 - 72 - 1, sum to 123. 27 pillars, such as 50 - 64 - 9, sum to 123. 27 files, such as 50 - 16 - 57, sum to 123. 8 quadragonals, such as 1 - 41 - 81 sum to 123. Some of the squares may have diagonals summing to 123 and some of the cubes may have triagonals summing to 123. These are not requirements of a magic tesseract just as a magic cube is not required to have the planar square diagonals summing to 42. What is required is that the 8 quadragonals or 4-agonals, such as 50 - 41 - 32 sum to 123. There are 58 different basic pure (using numbers 1 to 81) magic tesseracts. Each of these have 384 equivalents due to rotations and/or reflections.

Just as the one order-3 magic square and the four order-3 magic cubes are associated, so also are the 58 order-3 magic tesseracts. Because they are associated, all are also self-similar. That is, when each number is subtracted from 82 (i.e. complimented), the result is a reflection of itself and is one of the 384 aspects of this figure.  See my Self-similar Magic Squares.

From The Magic Square Course, page 470-491 (which shows all 58 order-3).

Order-8 Inlaid Magic Cube

Here is the shell for an order-8 magic cube with an inlaid order-4  magic cube. Each of the six windows shown holds two order-4 pandiagonal magic squares. The inner order-4 cube is pantriagonal meaning that all broken triagonal pairs sum correctly to 1026. The order-8 cube uses the numbers from 1 to 83 and has the magic sum of 2052. Note that it is not a requirement that planar diagonals sum correctly for a cube to be considered magic, although it is possible for an order-8 (the smallest order cube) to have this feature . The author reasons that there are 2,717,908,992 variations of this one cube, obtainable by rotations, reflections and transformations of the components.   Following are listed the individual layers of the cube. Note that in most cases they are only semi-magic (the planar diagonals are not required to sum correctly for the cube to be considered magic).

From the above eight horizontal planes, the 16 vertical planes and the four triagonals can be assembled.

From The Magic Square Course, pp. 419 - 431

Inlaid Magic Tesseract

# 308 - 151 St. Andrews St., Victoria, B.C., V8V 2M9 CANADA 15 October, 1999

Minor Announcement Discovered during the spring of 1999, was a new method of making magic squares of order 2k. An example shown top left is a tenth-order magic square which sums 505 in rows columns and diagonals. In the second quadrant, you will find inlaid a 5th-order magic square which sums 315. Inlaid squares and various methods abound, so this simply adds another method into the system. MAJOR ANNOUNCEMENT The technique mentioned above, can be extended to three and four-dimensional space and higher. A magic tesseract of order six, with an Inlaid magic tesseract of order three has been made. It contains the numbers from 1 to 1296 and sums 3,891 in the required 872 different ways. This is the world’s first magic tesseract of order six. The inlaid magic tesseract of order three sums 1,824, in the required 116 different ways. This becomes the world’s first inlaid magic tesseract. The new method for magic squares will be taken into account in the upcoming Second Edition of Inlaid Magic Squares and Cubes, which is unscheduled at the moment.
	John R. Hendricks

Order-9 Bimagic Square

Bimagic means that you can sum the numbers as they are, or you can square them all first and then sum them. Either way, the square is magic.

David M. Collison, first discovered bimagic squares of order nine. An example is shown in Figure 1. He died before he could reveal just how he made it and mathematicians are still searching to find his method of construction.

Figure 1. Collison’s regular,   Figure 2. Hendricks’ newly
or associated bimagic square.   created bimagic variety.

In Figure 2, the square is partitioned into nine zones. These are not magic sub-squares, just zones.
Each zone of nine elements sums 369, as does’ each row, each column and both diagonals.
If you square all the numbers and then add them up, you will find that each zone sums 20,049,
as does each’ row, column and both diagonals.

John R. Hendricks
Victoria, BC, Canada
25 November 1999

About John Hendricks

Mr. Hendricks worked for the Canadian Meteorological Service for 33 years, and retired in 1984. Early in his career, he was a meteorological instructor for the N.A.T.O. Training Program. Later, he was a weather forecaster at various locations across Canada. Throughout his career, he was also known for his contributions to statistics and climatological statistics.

While employed, he also participated in volunteer service groups, including The Monarchist League of Canada and he was the founding President, Manitoba Provincial Council, The Duke of Edinburgh's Award in Canada. He was a recipient of the Canada 125 medal for his volunteer work.

Following his career in meteorology, he gave many public lectures on magic squares and cubes in schools and at in-service teacher's conventions both in Canada and in the northern United States. He developed a course on magic squares and cubes for the mathematically inclined students at Acadia Junior High School in Winnipeg for seven years. The resulting text book of over 550 8.5" x 11" pages was never published. He delivered half a dozen colloquia to professors of mathematics on the subject and in geometry and statistics, as well. He assisted in the Shad Valley program for several years.

John Hendricks started collecting magic squares and cubes when he was 13 years old. This became a hobby with him and sometimes even an obsession. He never really thought that he would ever expand the knowledge in this field. But soon, he became the first person in the world to successfully make four, five and six-dimensional models of magic hypercubes, and publish them. He has written prolifically on the subject in the Journal of Recreational Mathematics. He has also extended the knowledge of magic squares and cubes, especially the ornate and embedded varieties.

John R. Hendricks, The Magic Square Course, Unpublished, 1991, 554 pages 8.5 “ x 11”.
Written for a high school math enrichment class he conducted for 5 years.
John R. Hendricks, Bimagic Squares of Order-9, Dec. 1999, 14 pages 8 ½ x 11+covers  0-9684700-6-8
John R. Hendricks, Perfect n-Dimensional Hypercubes of Order 2ⁿ, May 1999, 36 pages 8 ½ x 11, 0-9684700-4-1
      Equations are shown for the first perfect Tesseract and Basic programs for orders 4 -6.
John R. Hendricks, Inlaid Magic Squares and Cubes, Feb. 1999, 214 pages 8 ½ x 11, 0-9684700-1-7
     Equations, examples, programs and a list of the 46 articles (mostly magic square related) he has had published in journals.
John R. Hendricks, All Third Order Magic Tesseracts, Feb. 1999, 36 pages 8 ½ x 11, 0-9684700-2-5
John R. Hendricks, Magic Squares to Tesseracts by Computer, 1998, 212 pages 8 ½ x 11, 0-9684700-0-9
Equations, examples, and 3 appendices dealing with rotations/reflections, magic squares of order 4k+2, and programs.

Signed in as sinisa632

Send this story to NewsBlur

Save this story

Share this story

Subscribe

Shared stories are on their way...