We've detected that you're using an ad content blocking browser plug-in or feature. Ads provide a critical source of revenue to the continued operation of Silicon Investor.  We ask that you disable ad blocking while on Silicon Investor in the best interests of our community.  If you are not using an ad blocker but are still receiving this message, make sure your browser's tracking protection is set to the 'standard' level.
Technology Stocks : RFID, NFC and QR code Technologies

 Public ReplyPrvt ReplyMark as Last ReadFilePrevious 10PreviousNext  
Recommended by:
From: Glenn Petersen8/20/2021 5:33:47 AM
2 Recommendations   of 1705
The Numbers Hiding Behind That QR Code

The now-familiar square of little black boxes added a second dimension to bar codes—and holds exponentially more data

By Eugenia Cheng
Wall Street Journal
Aug. 19, 2021 6:24 pm ET


Mathematician Eugenia Cheng explores the uses of math beyond the classroom. Read more columns here.

I have cautiously resumed dining in restaurants occasionally, and so have found myself scanning QR codes to access the menu online. It’s a quick and easy process hiding a surprisingly large amount of math.

QR stands for Quick Response, and these codes were invented in 1994 by Masahiro Hara at the Japanese automotive company Denso Wave. Their original purpose was to track inventory in factories, but broader uses became possible with the advent and ubiquity of smartphones.

QR codes are essentially a two-dimensional version of bar codes, which are a clever way of encoding information in an image using vertical lines of different thicknesses that a scanner can detect. Hara’s 2-dimensional version uses a square grid of small black and white squares, apparently inspired by the board game Go.

The extra power is not just used to store a bigger message; it is used to improve accuracy and reliability.
The extra dimension allows for a huge increase in capacity: Where 1-dimensional bar codes typically encode around 20 digits of information, a QR code can hold 4,000 or more depending on the version used. A small increase in the width of the grid yields a much larger increase in the number of small squares available, because of how the math of squaring works.

But this extra power is not just used to store a bigger message; it is used to improve accuracy and reliability. The pattern cleverly encodes information about which way up it is supposed to be, so that it doesn’t matter which way up you scan it. It also has error-correcting information built in, so that if the picture is slightly damaged, the information can still be reconstructed. In fact, depending on the version used, up to 30% percent can be damaged and the code can still be read.

The correcting method is called Reed-Solomon error-correction and was introduced by Irving S. Reed and Gustave Solomon in 1960. It was previously used for compact discs, so that they could be slightly scratched and still play. Reed and Solomon were engineers, but both had doctorates in pure mathematics, and their method uses some quite sophisticated pure math that might otherwise seem very unrelated to daily life: polynomials over finite fields.

Polynomials may be familiar from high school algebra. They are expressions involving a variable often called x, raised to various powers, multiplied by coefficients, and added together—for example, x2 + ¾x + 2 or higher order ones along the lines of ¾x4 + ½x3 + x2+ 2x + 1.

In these examples the coefficients are all rational numbers from an infinite pool, but we could choose coefficients from a more limited “finite field” instead. The theory of finite fields is complicated, but it simplifies certain things, especially where multiplication is concerned. Reed-Solomon error-correction uses a finite field with 256 elements; all the numbers in this system can be represented by a string of 8 binary digits, that is, 0’s and 1’s, which is convenient for computers to handle.

The text of the “message” is also turned into binary digits, so the text and the error-correcting information are all expressed in binary code, which can then be represented as black and white squares instead of 0’s and 1’s. The tiny squares inside the main square of the QR code are laid out in a preset order, and when we scan it, a computer somewhere reads off the binary digits in the appropriate order, corrects any errors found and recovers the message—whether it’s information about a factory component or a website listing tasty pasta dishes.

We don’t have to understand any of this math to use QR codes in a restaurant, but I hope we can be glad that somebody did.

The Numbers Hiding Behind That QR Code - WSJ
Report TOU ViolationShare This Post
 Public ReplyPrvt ReplyMark as Last ReadFilePrevious 10PreviousNext