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.
|
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.).
|
|
|
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|