QR Codes -- Sage

QR Codes (Quick Response Codes):

For the following program, we only considered alphanumeric data, i.e. [0-9], [A-Z], '.', '%', ' ', '+/-*', and ':'.

If lower case letters are found in the text, they are considered capital letters for the program. Also, we programmed the version 1 QR code, implying that the maximum input is 16 characters and the output is a 21x21 pixel matrix with 13 error codewords and 25% error correction. We did however write the code so that the other versions may be implemented in the future.

import re import collections ''' This block defines a Queue class as a subclass of the collections.deque class This class inherits all the methods of the deque class and adds the methods enqueue and dequeue. Daniel D. Warner September 8, 2010 ''' class Queue(collections.deque): def enqueue(self,x): self.appendleft(x) def dequeue(self): if 0 < len(self): return self.pop() else: return None

Section 1 - Encoding the Data:

The first part of the code is to compile a list of binary numbers that represents the message and the codewords.

1. Mode Indicator - determines the type of message whether it is binary ([0-9],[a-z]), numeric ([0-9]), alphanumeric([0-9], [A-Z], '.', '%', ' ', '+/-*', and ':'), or Japanese. Since we are in America, we skipped the Japanese mode :)

a. Numeric: returns 0001

b. Alphanumeric: returns 0010

c. Binary: returns 0100

2. Length Encoder: Encodes the length into a 9 bit binary number (9 bit for alphanumeric version 1 QR code; 10-numeric; 8-binary).

3. Text Encoder: Encodes the text/message into a binary number by splitting the message into blocks of 2 and finding the binary number of the result of (45*x1+x2) where x1 and x2 are the corresponding ASCII values for the characters in the block. If odd number of characters, code it into a 6 bit binary string. Otherwise, it is a 9 bit string.

4. Terminate Bits: For version 1, we are required to have 104 bits. If we have less, we pad on 4 zeros or until we have 104 bits (whichever is less). Ex: If we have 102 bits, add 2 zeros. If we have 60, add 4 zeros.

5. Adding Words: If the string bit number is less than 104, we must add words. First, we add zeros until we have blocks of 8 bits without extras. Next, we add the words 11101100 and 00010001 starting with the former and alternating them until we reach 13 blocks of 8.

6. Message Polynomial: The string we have produced so far is encoded into decimal numbers by the blocks of 8 bits and returned as a list.

7. Generator Polynomial: This polynomial is generated based on the number of codewords needed. In our case, the number of codewords required is 13 but for other versions and error correction, this number changes.

8. Codeword Generator: This section finds the codewords by using the Generator Polynomial and Message Polynomial to create Reed Solomon codewords. For more information check http://en.wikipedia.org/wiki/Reed–Solomon_error_correction.

9. Combining the Codewords and Message: After the codewords are found, they are put into 8 bit binary numbers and added to the string found in 5.).

#Encode the mode indicator. The mode indicator determines the mode and returns a 4 bit binary number dependent on the mode. def ModeIndicator(text): nonbinary = re.compile('[^01]+') nb = nonbinary.search(text) numeric = re.compile('[0-9]+') n = numeric.search(text) alphanumeric = re.compile('(\D)+') a = alphanumeric.search(text) if n and not a: if nb: return '0001' else: return '0100' else: return '0010'

#Length encoder: encodes length into binary number def binary(text, bitnumber): n = len(text) b = bin(n) b = b[2:] while len(b) < bitnumber: b = '0' + b return b

#Text Encoder #ASCII VAL - Encoding the text to binary using their ascii values and splitting the text into sets of two. def alphanumericdata(text): #The ASCII values dictionary = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9,'A':10,'B':11,'C':12, 'D':13, 'E':14, 'F':15, 'G':16, 'H':17, 'I':18, 'J':19, 'K':20, 'L':21, 'M':22, 'N':23, 'O':24, 'P':25, 'Q':26, 'R':27, 'S':28, 'T':29, 'U':30, 'V':31, 'W':32, 'X':33, 'Y':34, 'Z':35, 'a':10,'b':11,'c':12, 'd':13, 'e':14, 'f':15, 'g':16, 'h':17, 'i':18, 'j':19, 'k':20, 'l':21, 'm':22, 'n':23, 'o':24, 'p':25, 'q':26, 'r':27, 's':28, 't':29, 'u':30, 'v':31, 'w':32, 'x':33, 'y':34, 'z':35, ' ':36, '$':37, '%':38, '*':39, '+':40, '-':41, '.':42, '/':43, ':':44} string = '' while len(text)>1: v1 = text[0] v2 = text[1] text = text[2:] blocknum = dictionary[v1]*45 + dictionary[v2] b = bin(blocknum) if len(b) == 13: b = b[2:] else: b = (11-len(b[2:]))*'0' + b[2:] string = string+b if len(text) == 1: v1 = text[0] b = bin(dictionary[v1]) b = b[2:] text = text[1:] string = string +(6-len(b))*'0' + b if len(text) == 0: return string

#terminate bits - This section makes sure that we have enough bits. If we don't, we pad on four 0's or less if only missing a few bits. def terminate(string): if len(string) < 104: string = string + '0000' while len(string)>104: string = string[:-1] #print string extras = len(string)%8 #print extras if extras != 0: extras = 8-extras string = string + extras*'0' return string

#Adding words until string is long enough. This section adds 2 words by alternating them until we have the correct number of bits. def addingwords(string, capacity): first = 'false' while len(string) < capacity + capacity/8 - 2: if first == 'false': string =string + '11101100' first = 'true' else: string = string + '00010001' first = 'false' return string

#REED Solomon Codes Time

#Creating a Message Polyn def MessagePolyn(string, term_number): a1 = string[0:8] a1 = int(a1,2) list =[a1] for i in range(1,term_number): string = string[8:] a1 = string[0:8] a1 = int(a1,2) list.append(a1) return list

#Constructing the Anti-Log Table for GF(256) using the irreducible polynomial #x^8+x^4+x^3+x^2+1 x = var('x') Log = [j for j in range(256)] ALog = [j for j in range(256)] Poly = [j for j in range(256)] ALog[0] = 1 for i in range(1,8): #print i Poly[i] = x^i #print Poly[i] ALog[i] = Poly[i](x=2) Log[ALog[i]] = i for i in range(8,256): #print i Poly[i] = x*Poly[i-1] if Poly[i].degree(x) == 8: Poly[i] = Poly[i]-x^8+x^4+x^3+x^2+1 Poly[i] = Poly[i].expand() #print Poly[i] for k in range(8): #print Poly[i] if Poly[i].coefficient(x^k) == 2: Poly[i] = Poly[i] - 2*x^k ALog[i] = Poly[i](x=2) Log[ALog[i]] = i #print Poly[i] Log[1] = 0 #print Log #print ALog

#Creating a Generator Polyn # The following is just a version of the log-antilog table. def GeneratorPolyn(num_codewords): polyn = (x+1) a = var('a') for j in range (1,num_codewords): polyn = polyn*(a^0*x + a^j*1) polyn = expand(polyn) degree = polyn.degree(x) values = [] list =[] for deg in range(degree+1): if deg == 0: terms = polyn(x=0) else: x_term = x^deg terms = polyn.coefficient(x_term) n = re.compile('a([&^]\d+)?') pos = 0 a_terms = [] while pos < len(str(terms)): key = n.search(str(terms),pos) if key: a_terms.append(key.group()) pos = key.end() elif str(terms)[pos] == '1': a_terms.append('1') pos +=1 else: pos +=1 xor_log = [] while 0<len(a_terms): pop = a_terms.pop() if '^' in pop: pop = int(pop[2:])%256+floor(int(pop[2:])/256) pop = str(pop) elif 'a' in pop: pop = '1' else: pop = '0' #log_number = log_table[pop] log_number = ALog[int(pop)] log_number = int(log_number) xor_log.append(log_number) n = len(xor_log) if n-1 == 0: pop2 = xor_log.pop() else: while 0 < (len(xor_log)): pop = xor_log.pop() if len(xor_log) == n-1: pop2 = xor_log.pop() pop2 = (pop).__xor__(pop2) list.insert(0,pop2) value = Log[pop2] values.append(value) deg = j+1 polyn = 0 while 0<len(values): v = int(values.pop()) polyn = polyn + a^v*x^deg deg =deg-1 return list

#Creating Codewords by Division #do 13 times if need 13 codewords . . . def Division(message_polyn, gen_polyn,count): deg = 0 mes_values = [] gen_values = [] mes_copy = copy(message_polyn) gen_copy = copy(gen_polyn) while 0< len(mes_copy): pop2 = mes_copy.pop(0) value = Log[pop2] mes_values.append(value) deg +=1 deg = 0 while 0< len(gen_copy): pop2 = gen_copy.pop(0) value = Log[pop2] gen_values.append(value) deg +=1 for i in range(len(gen_values)): gen_values[i] = (int(gen_values[i]) + int(mes_values[0]))%255 gen_values[i] = ALog[(gen_values[i])] for i in range(len(message_polyn)): gen_values[i] = (int(gen_values[i])).__xor__(int(message_polyn[i])) gen_values.pop(0) if count <12: count +=1 values = Division(gen_values, gen_polyn,count) else: return gen_values return values

#Codewords and Message Coefficients into Binary def Coeff_Binary(Codewords, Message): for i in range(len(Message)): coeff = bin(Message[i]) if len(coeff) >9: coeff = coeff[2:] else: coeff = (10-len(coeff))*'0' + coeff[2:] Message[i]=coeff for i in range(len(Codewords)): coeff = bin(Codewords[i]) if len(coeff)>9: coeff = coeff[2:] else: coeff = (10-len(coeff))*'0' + coeff[2:] Codewords[i] = coeff return Message, Codewords

#combining the codewords and message def Combine(message, codewords): string = '' while 0<len(message): pop = message.pop(0) string= string + pop while 0<len(codewords): pop = codewords.pop(0) string = string + pop return string

Section 2 - Creating the matrix and displaying the QR code:

The following describes the blocks of code below:

1. Creates the strings associated with each of the four levels of error correction that QR codes allow for: 7% (level L), 15% (level M), 25% (level Q), and 30% (level H). **Note: You will see in the subsequent code that we utilize only level Q (25% error correction) in our function definitions, although it would not be difficult to alter the function so that the user could select his preference for error correction level.**

2. Initializes a matrix to be used for the QR code (using a 2-d array) and "colors" the pixels that are predetermined for every QR code. Then there are two function definitions, one that creates eight copies of the original matrix and "colors" a different masking pattern for each, and one that uses a binary string to "color" the remaining pixels of a matrix depending on which masking pattern it has.

3. This block contains a function that scans a QR matrix (multiple times) and calculates a penalty score to be associated with this matrix based on several "color patterns" that may show up within the code. **Note: You will notice that this scanning is done in a very elementary way, and that it is hardly efficient. I tried to figure out a way to implement some kind of a 2-d finite state machine in order to only need to scan the matrix once and generate it's penalty score, but was unable to figure out how to do it.**

4. This block simply calculates a penalty score for each of the eight codes (matrices) generated for a given binary string, sorts the matrices based on these scores, and then returns the matrix with the lowest score.

5. The last block creates a function that allows the user to input an alpahnumeric string and an error correction level (although, as currently coded, 25% is still used regardless or user input). This function then uses the code above to generate a binary string associated with the users input and then uses the code below to generate and display the best QR code for this binary string.

#ECC level L mask pattern strings ECC_L = [[111011111000100],[111001011110011],[111110110101010],[111100010011101],[110011000101111],[110001100011000],[110110001000001],[110100101110110]] #ECC level M mask pattern strings ECC_M = [[101010000010010],[101000100100101],[101111001111100],[101101101001011],[100010111111001],[100000011001110],[100111110010111],[100101010100000]] #ECC level Q mask pattern strings ECC_Q = [['011010101011111'],['011000001101000'],['011111100110001'],['011101000000110'],['010010010110100'],['010000110000011'],['010111011011010'],['010101111101101']] #ECC level H mask pattern strings ECC_H = [['001011010001001'],['001001110111110'],['001110011100111'],['001100111010000'],['000011101100010'],['000001001010101'],['000110100001100'],['000100000111011']] Mask_Patterns = [ECC_L,ECC_M,ECC_Q,ECC_H]

from sage.plot.matrix_plot import MatrixPlot #Create corners C = [] for i in range(8): C.append([]) for j in range(8): C[i].append(2) for i in range(7): for j in range(7): C[i][j]= 0 for i in range(5): for j in range(5): C[i+1][j+1]= 2 for i in range(3): for j in range(3): C[i+2][j+2]= 0 #print C #Initialize QR Matrix M = [] for i in range(21): M.append([]) for j in range(21): M[i].append(1) #Add position detection patterns for i in range(8): M[i][:8] = C[i] M[i][13:] = [C[i][-1]]+C[i][:-1] M[i+13][:8] = C[i-1] #Add timing patterns and extra black pixel for i in range(21): if M[6][i]==1: M[6][i] = (i % 2)*2 if M[i][6]==1: M[i][6] = (i % 2)*2 M[13][8] = 0 #Change color for location where masking pattern will go lateron for i in range(len(M[8])): if i not in [6,8,9,10,11,12]: M[8][i] = 3 if i not in [6,9,10,11,12,13]: M[i][8] = 3 def include_mask_patterns(matrix): All_Matrices = [] for k in range(8): Q = Queue() for token in Mask_Patterns[2][k][0]: Q.enqueue((int(token)+1)%2) Q2 = copy(Q) MATRIX = [] for item in M: MATRIX.append(copy(item)) All_Matrices.append(MATRIX) for n in range(len(All_Matrices[k][8])): if All_Matrices[k][8][n] in [1,3] and n not in [8,9,10,11,12]: All_Matrices[k][8][n] = Q2.dequeue()*2 if All_Matrices[k][-1-n][8] in [1,3] and n not in [8,9,10,11]: All_Matrices[k][-1-n][8] = Q.dequeue()*2 return All_Matrices def fill_in_QR(mask_number,matrix,string): Q = Queue() for token in string: Q.enqueue(token) for j in range(len(matrix[0])): for i in range(len(matrix[0])): if (len(matrix[0])-1-j) % 4 == 0 or j == 17: k = len(matrix[0])-1-i else: k = i if matrix[k][-1-j] == 1 and 2 <= len(Q): if mask_number == 0: if (k+20-j) % 2 == 0: matrix[k][-1-j] = int(Q.dequeue())*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 if (k+19-j) % 2 == 0: matrix[k][-2-j] = int(Q.dequeue())*2 else: matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 elif mask_number == 1: if k % 2 == 0: matrix[k][-1-j] = int(Q.dequeue())*2 matrix[k][-2-j] = int(Q.dequeue())*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 elif mask_number == 2: if (20-j) % 3 == 0: matrix[k][-1-j] = int(Q.dequeue())*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 if (19-j) % 3 == 0: matrix[k][-2-j] = int(Q.dequeue())*2 else: matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 elif mask_number == 3: if (k+20-j) % 3 == 0: matrix[k][-1-j] = int(Q.dequeue())*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 if (k+19-j) % 3 == 0: matrix[k][-2-j] = int(Q.dequeue())*2 else: matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 elif mask_number == 4: if (((20-j)/3).floor() + (k/2).floor()) % 2 == 0: matrix[k][-1-j] = int(Q.dequeue())*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 if (((19-j)/3).floor() + (k/2).floor()) % 2 == 0: matrix[k][-2-j] = int(Q.dequeue())*2 else: matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 elif mask_number == 5: if (((20-j)*k)%2)+(((20-j)*k)%3) == 0: matrix[k][-1-j] = int(Q.dequeue())*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 if (((19-j)*k)%2)+(((19-j)*k)%3) == 0: matrix[k][-2-j] = int(Q.dequeue())*2 else: matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 elif mask_number == 6: if ((((20-j)*k)%2)+(((20-j)*k)%3)) % 2 == 0: matrix[k][-1-j] = int(Q.dequeue())*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 if ((((19-j)*k)%2)+(((19-j)*k)%3)) % 2 == 0: matrix[k][-2-j] = int(Q.dequeue())*2 else: matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 elif mask_number == 7: if ((((20-j)+k)%2)+(((20-j)*k)%3)) % 2 == 0: matrix[k][-1-j] = int(Q.dequeue())*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 if ((((19-j)+k)%2)+(((19-j)*k)%3)) % 2 == 0: matrix[k][-2-j] = int(Q.dequeue())*2 else: matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 else: matrix[k][-1-j] = ((int(Q.dequeue())+1)%2)*2 matrix[k][-2-j] = ((int(Q.dequeue())+1)%2)*2 elif len(Q)<2: break return matrix

def calculate_penalty(matrix): penalty = 0 count = 0 penalty1 = 0 for j in range(len(matrix[0])): for i in range(len(matrix[0])): if i == 0 or k <= i: k = i while k <= 20 and matrix[k][j] == matrix[i][j]: count += 1 k += 1 if 5 <= count: penalty1 += 3 + (count-5) count = 0 for i in range(len(matrix[0])): for j in range(len(matrix[0])): if j == 0 or k <= j: k = j while k <= 20 and matrix[i][k] == matrix[i][j]: count += 1 k += 1 if 5 <= count: penalty1 += 3 + (count-5) count = 0 penalty2 = 0 for i in range(len(matrix[0])): for j in range(len(matrix[0])): if i<20 and j<20: if matrix[i+1][j] == matrix[i][j] and matrix[i][j+1] == matrix[i][j] and matrix[i+1][j+1] == matrix[i][j]: penalty2 += 3 penalty3 = 0 for i in range(len(matrix[0])): for j in range(len(matrix[0])): if matrix[i][j] == 0: if i<=14 and matrix[i+1][j] == 2 and matrix[i+2][j] == 0 and matrix[i+3][j] == 0 and matrix[i+4][j] == 0 and matrix[i+5][j] == 2 and matrix[i+6][j] == 0: if ((i-4)>=0 and matrix[i-4][j] == 2 and matrix[i-3][j] == 2 and matrix[i-2][j] == 2 and matrix[i-1][j] == 2) or ((i+10)<=20 and matrix[i+7][j] == 2 and matrix[i+8][j] == 2 and matrix[i+9][j] == 2 and matrix[i+10][j] == 2): #print i,j penalty3 += 40 if j<=14 and matrix[i][j+1] == 2 and matrix[i][j+2] == 0 and matrix[i][j+3] == 0 and matrix[i][j+4] == 0 and matrix[i][j+5] == 2 and matrix[i][j+6] == 0: if ((j-4)>=0 and matrix[i][j-4] == 2 and matrix[i][j-3] == 2 and matrix[i][j-2] == 2 and matrix[i][j-1] == 2) or ((j+10)<=20 and matrix[i][j+7] == 2 and matrix[i][j+8] == 2 and matrix[i][j+9] == 2 and matrix[i][j+10] == 2): #print i,j penalty3 += 40 penalty4 = 0 for i in range(len(matrix[0])): for j in range(len(matrix[0])): if matrix[i][j] == 0: count += 1 penalty4 = ((abs((count/(21^2))*100 - 50)).floor() * 2) return penalty1+penalty2+penalty3+penalty4

def get_QR(string): list = [] Matrices = include_mask_patterns(M) for i in range(len(Matrices)): Matrices[i] = fill_in_QR(i,Matrices[i],string) x = calculate_penalty(Matrices[i]) list.append([x,i]) list.sort() show(matrix_plot(Matrices[list[0][1]]))

def QRCodes(text,error): bitnumber = 9 capacity =104 indicator = ModeIndicator(text) version = binary(text, bitnumber) alphnum = alphanumericdata(text) string = indicator + version + alphnum string = terminate(string) string = addingwords(string, capacity) mes_polyn = MessagePolyn(string,13) gen_polyn = GeneratorPolyn(13) #print gen_polyn codewords = Division(mes_polyn, gen_polyn, 0) message, codewords = Coeff_Binary(codewords, mes_polyn) #print message #print codewords string = Combine(message,codewords) get_QR(string) QRCodes('hello world', 25)

QR Codes

3282 days ago by fknoll