admin管理员组

文章数量:1417426

Background

I am trying to decode a bitstring from a QR-Code, where the data was encoded in numeric mode. According to this QR-Code tutorial: (which references the standard), the numeric encoding shall be as follows:

Split the n-digit number into 3-digit groups and encode each group into a

• 10-bit word, if the group has no leading zero
• 7-bit word, if the group has 1 leading zero,
• 4-bit word, if the group has 2 leading zeros.

If n is not a multiple of three, the last group will be 1- or 2-digits long The rules above also apply for this last group.

Encoding Example:

Take the 14-digit number: 12300101234567

Split it into 3-digit groups and convert then to binary numbers:

• group 1: 123 > 0001111011 (10 bits)
• group 2: 001 > 0001 ( 4 bits)
• group 3: 012 > 0001100 ( 7 bits)
• group 4: 345 > 0101011001 (10 bits)
• group 5: 67 > 1000011 ( 7 bits)

Therefore the 14-digit number is encoded into the following 38 bits: 00011110110001000110001010110011000011

Decoding (what I have so far):

The QR-Code gives me the number of digits that were encoded, so taking the exams above I know n = 14.

Following the encoding rules calculate:

• int(14/3) = 4
• 14 % 3 = 2

thus there are

• 4x 3-digit numbers
• 1x 2-digit number

Therefore the last bit word is 7 bits long. 1000011 and encodes the number 67

The remaining 31 bits encode the other 12 digits. 0001111011000100011000101011001

How do 4-, 7- and 10-bit words fit into 31 bit?

Try combinations:

• First try: 10+10+10+1? No, the encoding does not allow a 1-bit word
• Next try: 10+10+4+7? Yes.

Therefore the bitstring is built from the following bit words.

• 2x 10-bit words
• 1x 7-bit word
• 1x 4-bit word

Problem:

I don't know the order of the bit words.

There are two more restrictions that result from the encoding rules:

• The highest 1-digit number that can be encoded into a 4-bit word is 9 > 1001.
• The highest 2-digit number that can encoded into a 7-bit word is 99 > 1100011.

This can help exclude several orders when iterating over all possible orders. But it does not exclude all possibilities. I am not able to get the correct order of the bit words.

I appreciate your help, thanks.

Background

I am trying to decode a bitstring from a QR-Code, where the data was encoded in numeric mode. According to this QR-Code tutorial: https://www.thonky/qr-code-tutorial/numeric-mode-encoding (which references the standard), the numeric encoding shall be as follows:

Split the n-digit number into 3-digit groups and encode each group into a

• 10-bit word, if the group has no leading zero
• 7-bit word, if the group has 1 leading zero,
• 4-bit word, if the group has 2 leading zeros.

If n is not a multiple of three, the last group will be 1- or 2-digits long The rules above also apply for this last group.

Encoding Example:

Take the 14-digit number: 12300101234567

Split it into 3-digit groups and convert then to binary numbers:

• group 1: 123 > 0001111011 (10 bits)
• group 2: 001 > 0001 ( 4 bits)
• group 3: 012 > 0001100 ( 7 bits)
• group 4: 345 > 0101011001 (10 bits)
• group 5: 67 > 1000011 ( 7 bits)

Therefore the 14-digit number is encoded into the following 38 bits: 00011110110001000110001010110011000011

Decoding (what I have so far):

The QR-Code gives me the number of digits that were encoded, so taking the exams above I know n = 14.

Following the encoding rules calculate:

• int(14/3) = 4
• 14 % 3 = 2

thus there are

• 4x 3-digit numbers
• 1x 2-digit number

Therefore the last bit word is 7 bits long. 1000011 and encodes the number 67

The remaining 31 bits encode the other 12 digits. 0001111011000100011000101011001

How do 4-, 7- and 10-bit words fit into 31 bit?

Try combinations:

• First try: 10+10+10+1? No, the encoding does not allow a 1-bit word
• Next try: 10+10+4+7? Yes.

Therefore the bitstring is built from the following bit words.

• 2x 10-bit words
• 1x 7-bit word
• 1x 4-bit word

Problem:

I don't know the order of the bit words.

There are two more restrictions that result from the encoding rules:

• The highest 1-digit number that can be encoded into a 4-bit word is 9 > 1001.
• The highest 2-digit number that can encoded into a 7-bit word is 99 > 1100011.

This can help exclude several orders when iterating over all possible orders. But it does not exclude all possibilities. I am not able to get the correct order of the bit words.

I appreciate your help, thanks.

• qr-code
• numeric
• decoding
• bitstring

Share Improve this question Follow edited Jan 31 at 13:56 Immanuel Neumann asked Jan 31 at 11:08 Immanuel NeumannImmanuel Neumann 5344 bronze badges 2

• Weird... this does seem to be impossible. It looks to me like a string 073018036585146292 and a string 585146292073018036 get encoded to completely identical bit sequences under this encoding scheme. I suspect there's something wrong with the sources describing numeric mode encoding this way. Too bad the actual QR code standard costs 221 Swiss francs. – user2357112 Commented Jan 31 at 11:39
• Just to make sure: you really ask about QR codes, and this is not some leetcode fabrication? – tevemadar Commented Jan 31 at 13:03

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 5

After locating a copy of the actual ISO/IEC 18004:2015 QR code standard, I have found that the part about leading zeros is not in the actual standard.

A 3-digit group is encoded in 10 bits, regardless of how many leading zeros it has. Sources claiming otherwise are wrong.

The standard even uses an example with a leading zero: 01234567 is broken up into 012 345 67, and the 012 is encoded as 0000001100, not as 0001100.

I tried the simpler numeric encoding method of converting each 3-digit group into 10-bit words. I keeping the encoding rules above only for the last group. My Smartphone built-in scanner correctly read the code.

Encoding with variable length bit words do work (every scanner I have used, correctly read the QR-Codes I have generated with variable length bit words) but it makes decoding more complicated. However, this means that my source tutorial https://www.thonky/qr-code-tutorial/numeric-mode-encoding is not wrong.

Thanks for your fast replies. Special thanks for looking up what the ISO/IEC 18004:2015 QR code standard actually says. I didn't think of searching for the standard myself.

本文标签：