Transcription

When QR codes first came out, I thought they were awful, never going to catch on. This is a flowchart from the time that really resonated with me. The problem, as I saw it, was that QR codes are ugly, and they mean nothing to people. I would rather just see a website or a word that I could google. QR codes are a language for machines, and I am a human. But I was wrong. QR codes obviously turned out to be so useful that they are now ubiquitous, used in everything from tickets to restaurant menus and advertising. In some countries, they're the most common way to exchange money. And the story of QR codes is a very human one. The origin of these checkerboard patterns actually dates back to our first efforts at digitizing information. In 1825, there was a renowned painter who lived in New Haven, Connecticut with his wife and two kids. His big break came one day when he was invited to paint a portrait of the Marquis de Lafayette, a hero of the American Revolution. Even though his wife was expecting their third child any day, the opportunity was too good to pass up, and he hastily set off for Washington, D.C., where Lafayette was waiting. There, the painter wrote to his wife, describing his first meeting with Lafayette, signing off with the words, We'll write again soon. Love to all the children. In the greatest taste, but with the same ardent affection as ever. Thy loving husband. After a few days with no reply, a courier delivered a letter, which said his wife was ill after childbirth. Worried, the painter rushed home. He traveled by horse and wagon day and night, managing to arrive back in New Haven in several days. But it was far too late. His wife had died. Not only that, he had missed the funeral. Her body was already buried in the ground. The painter's name was Samuel Finley Breeze Morse. From that day forward, Morse set out to find a faster way to communicate over long distances. He got a job at New York University, where he attended lectures on electricity, a rapidly developing field at the time. In 1836, along with Joseph Henry and Alfred Vale, he devised a machine that could send electrical pulses along a wire. This was not the first electric telegraph, but it was the simplest. In the UK, another team had set up a series of circuits to move five magnetic needles to point at letters and numbers. Morse's system required only a single circuit, but the simplicity of the apparatus demanded a cleverer method of encoding information. On the circuit, you could send short or long pulses. Morse turned these into dots and dashes. The most common letters could be sent with a single key press, a dot for an E and a dash for a T. The other letters were arranged by frequency and assigned increasingly complex codes. These symbols were meant to be printed at the receiver on a paper strip, but operators soon realized they could recognize the letters just by the sound. This sped up the rate at which information could be sent and received, so Morse code became an international standard for rapid messaging, widely used in the military, maritime communications, and aviation. The universally recognized distress call, SOS, what does it stand for? Nothing. It just happens to be easy to send and recognize in Morse code. Morse code revolutionized communication, but in the next century, it would transform a totally different industry. In the late 1940s, Bernard Silver was an engineering student at Dresden. He was a student at Drexel University in Pennsylvania. One day, he overheard the president of a local supermarket chain asking the engineering dean to find a way to speed up the checkout process. At that time, cashiers had to type in each item and its price by hand, a process so tedious and repetitive that many cashiers had developed carpal tunnel syndrome. Silver told his friend Norman Joseph Woodland about the problem, and together they began experimenting. Woodland moved down to Florida, and one day on the beach, he drew some dots and dashes of Morse code in the sand, something he was very familiar with as a Boy Scout. He recalls, I just extended the dots and dashes downwards and made narrow lines and wide lines out of them. And thus, the first barcode was created. From this humble beginning evolved the universal product code, or UPC barcode, capable of storing a simple string of 12 numbers. It's read by scanning a laser across it and checking how much light is reflected to read the black and white lines, essentially as dots and dashes. A pair of vertical lines are placed at the beginning, middle, and end to ensure the scanner reads the code properly. The code is divided into left and right halves. Numbers at either side have their black and white lines flipped so that the scanner can tell left and right apart even while reading upside down. When viewed upright, the numbers typically specify the manufacturer on the left and the product on the right. Manufacturers actually pay large sums of money to reserve a given amount of numbers to themselves so that they can exclusively register their products. In this way, the 12 digits of a barcode uniquely specify every single grocery item you've ever bought. This jar of Jif peanut butter is identified by the same 12 digits no matter where in the world it's found. And all forms of peanut butter, smooth, crunchy, stir, no stir, sugar-free, low sodium, across all brands get their own unique barcode. Will we ever run out of barcodes? Well, 12 digits could combine to provide 10 to the 12, that is a trillion different possible sequences. That should be more than enough, even if companies keep making stuff like sour patch Oreos and flaming hot Mountain Dew. But there is a catch. The last digit is not independent of the others. The barcode creators were aware that it could get scratched, stained, or tampered with. So they reserved the last digit to verify that the barcode is complete. Take any barcode and sum the digits at odd numbered positions. Multiply this result by three. Add the digit sum at even numbered positions to the result. And take the remainder when this number is divided by 10. If this remainder is zero, then the check digit is zero. Otherwise, the check digit is 10 minus this remainder. If a scanner is unable to read any one digit of the barcode, it can use the final digit to back calculate what it must be using this algorithm. But if two digits are damaged, well, then we're out of luck. In that case, we have to type in the numbers printed below the barcode. So without that last digit, the number of unique possibilities is 10 to the 11, or 100 billion options. To date, 1.24 billion barcodes have been registered, a number that is rising every day. So they won't last us forever. But that's not why people began to look for alternatives to barcodes. It was really the amount of information a single barcode could store. 12 digits by themselves could only identify one product. But what if someone wanted to know more information, like where that product came from? In 1986, cattle in the UK began showing symptoms of a curious brain disease, bovine spongiform encephalopathy, or mad cow disease for short. It is spread when cattle ate feed containing prions, misfolded proteins. And if people ate beef containing tissue from the brain or spinal cord of infected cattle, they could contract a related brain illness that literally turns your brain into a sponge. Now, as no test could detect mad cow disease in living cows, millions of cattle were culled. Health officials sought a method to track sources and imports of beef. But with all the information this would require for any one piece of beef, barcodes were insufficient. American inventor David Allais tried to solve the problem by stacking many barcodes on top of each other. The result, Code 49, looked like a bookshelf. This is actually the predecessor of PDF417, a code often used on airline boarding passes. But Code 49 didn't solve the data quantity problem. At best, it multiplied the information a barcode could carry by a handful. A more efficient way was to extend barcodes into two dimensions, creating a data matrix. NASA tried this in 1994 with Veracode, used to track and identify space shuttle parts. This code was read by early digital cameras rather than lasers, and was initially proprietary. Around the same time, Masahiro Hara, an engineer at a Japanese auto parts manufacturer, was getting frustrated at having to scan multiple barcodes for filling in the same box of car components. Hara set out to develop an alternative on his own. He took inspiration from an unusual source. To understand how information is stored in a QR code, I'm going to build one myself, in the way Masahiro Hara first conceptualized it, with a Go board. I have the usual black and white stones. White represents zero, black represents one. We're going to encode the link to our YouTube channel on this board. The first step is to convert www.youtube.com slash veritasium into ones and zeros. We'll do that using byte encoding. Byte encoding uses ASCII, which itself has roots in Morse code. Every character is assigned a number from 1 to 256. Then we convert the ASCII decimal into its binary form. Since 256 is 2 to the power of 8, we can use the 8 binary bit combinations to represent all ASCII characters. These 8 bits make up one byte of information. The letter W is assigned the ASCII decimal 119, or 01110111. Doing the same for all characters in www.youtube.com slash veritasium, this is what the string looks like in binary. This is 26 characters long, so it takes up 26 bytes of information. Now our board is 25 by 25. This is known as a version 2 QR code. But there are many different sizes all readable by your phone camera. Hara's version 1 QR code was 21 by 21. And the largest version today is 177 by 177. That is large enough to hold 3 kilobytes of information. Just 26 of these would have been enough to store all the information Apollo 11's computer needed to send humans to the moon. One programmer even coded up a computer game, Snake, into a version 40 QR code. The region around a QR code must be empty and of uniform color. This is the quiet zone. A distinguishing feature of QR codes is the three square patterns in the corners. These position squares allow the reader to identify the orientation of the code. Now almost all QR codes also have a fourth square in the last corner, but it's smaller and hence trickier to spot. This is the alignment pattern. It's used to rescale the QR code when it's read from varying distances or from crazy oblique angles. The relative size and distance of the alignment square with respect to the position squares allows the software to rescale it into a proper square. Next to the position squares are plain white strips that isolate them from the rest of the code. And these are timing strips. And these are timing strips. Zebra pedestrian crossings which connect the top left position square with the other two. Every QR code has these alternating strips. You should look out for them. QR codes of all sizes visibly look the same. So this tells your phone which version it is and therefore how much data to expect. If there are five alternating squares, it's version one. If there are nine, it's version two and so on. And next to those are format strips that contain rules for how to scan the code. I'm placing red stones in the space they occupy for now. There is another feature every QR code has. This one pixel adjacent to the bottom right position square, it is always dark. I asked Harusan if it had any special significance, but he said no. All of this remaining space is for data storage. Data inside a QR code always starts at the bottom right corner. Here the first four squares carry four bits that specify the data format. 0001 if it's just numbers. 0010 if it's alphanumeric, so capital letters and numbers. 0100 if it's information stored in bytes. And 1000 for Japanese kanji. The following eight bits are used to indicate the number of characters in our message. So since we have 26 characters, that should be 00011010. Next we start arranging our bytes for youtube.com slash Veritasium, starting in eight bit two column cells. They follow a zigzag pattern that snakes its way to the top left. Within each cell that represents a byte, the most significant bit corresponding to 2 to the 7 is at the bottom right. And the least significant, or 2 to the 0, is at the opposite end. 01110111 for w will hence be filled like this. And we'll follow along with the rest. Once we fill in the bytes for www.u, we encounter the alignment pattern after four bits. To put in the next t, we simply bypass it and do the same for any of the other fixed regions of the code. Thus we keep filling in our data in the same zigzag pattern. After we complete www.youtube.c, the cells start looking less regular and more Tetris-like. But the way we put the stones byte after byte remains the same. And there go the last eight bits for the last letter, M. But wait a minute, we've only covered about half of our QR code. Well, that's because this whole remaining space is reserved for redundancy. These extra bytes of error correction code allow us to reconstruct information if the QR code is damaged. For a fully intact QR code, error correction makes something else possible. Putting a company logo at the center, just like the sponsor of this video, Saley. Now I travel a lot. Recently I was in Germany, right now I'm in Australia, and soon I'm going to the UK. But wherever you are, you need to have a working phone. Either you pay your home carrier's hefty roaming fees, or you have to find a place to buy a local SIM card, put it in the phone, and hope it works. This video sponsor, Saley, makes it easy to set up a cell plan and data interface. In more than 150 countries, you can pick how much data you want and how long you want it for. And it is so much cheaper than roaming. I'm actually going to the UK really soon, and here's how quickly I can set up an eSIM with Saley. All I have to do is click on the country, select a plan, and activate the eSIM. Then when I land, I'll automatically connect to a local network with no hidden charges. That's it. There's no need to hunt for public Wi-Fi, and you don't have to stand in line at the airport to get a physical SIM. With Saley, you set it up once, and you'll always be connected. And if you find out that your phone isn't compatible with eSIMs, you will get a full refund. So to check out Saley for free, go to saley.com slash Veritasium, or click the link in the description. Use the code VERITASIUM to get an exclusive 15% off your first purchase. That's saley.com slash Veritasium, or you can scan this handy QR code to get 15% off. So I want to thank Saley for sponsoring this part of the video, and now back to building our own QR code. QR codes offer four levels of error correction. Low, which can still be read with 7% of the code missing. Medium, which can handle 14%. Quartile, 25%, and High, up to 30%. This means a QR code could still be read properly, even with nearly a third of it missing. Higher levels require more space for error correction. So knowing how much of the code is error correction is vital. This information is protected in two ways. First, the level of error correction is indicated in the format strip, which is present identically in two places. The simplest way to avoid errors is to duplicate the information. Here, we'll choose the M level by placing one blue and one yellow stone here at the top left. So what if this part gets damaged? We have a copy in the second format strip, starting at the bottom left. The format strip contains three more bits of important information that we'll get to later. So for now, I'm just going to put down three blue stones in both copies. But what about all the rest of the format strip? Well, this is the second layer of protection. These other 10 bits are all just designed to correct mistakes in the first five bits. So how does this work? Let's say I only wanted to communicate two levels of error correction to you. Low or High. If one of the bits flips in transmission to 01 or 10, it's easy to know that an error has occurred, but no way to know which the original message was. An easy way to fix this is to add another bit. So 000 for low, 111 for high. Now, these are at opposite ends of a cube, and hence they are further apart. If you then receive 011, it's more likely that the intended message was 111, so it's easy to correct. In this scheme, the only allowed codewords are 000 and 111. The rest act as disallowed buffers to indicate errors in transmission. The allowed codewords should be as far apart as possible. Here, they are three vertices apart. This is known as the Hamming distance, after Richard Hamming, who pioneered the field of error correction. For a Hamming distance of n, you can correct up to n-1 over two errors in a binary string. So one bit flip in the previous example. So back to the five bits of our format string. If I only wanted to communicate all 0s or all 1s, I could place them at opposite corners of a five-dimensional hypercube. However, our string includes all 2 to the 5, or 32, combinations of 1s and 0s as valid codewords. So to provide buffers, like before, we can extend the five-bit string into a 15-bit string. Now the 32 valid codewords are each separated by seven vertices, or a Hamming distance of 7, which means we can correct up to three bit flip errors. The easiest way to do this is using a lookup table. The table takes a slightly misread vertex and finds the closest valid vertex, likely the intended codeword. But for our main QR code data, we need a far more efficient scheme, one that doesn't require lookup tables or doubling or tripling our data size. Let's say I want to send you a message that is the four numbers 1, negative 2, 3, and 5. If I just send these numbers, one of them could get corrupted in transmission, and you wouldn't know that an error had occurred or which digit was wrong. So before I send the message, we come up with a plan. First, instead of sending you four numbers, I will send six. The first four are my actual message, and the last two, A and B, will help you check if there were any errors. Now I want you to treat these six numbers as the coefficients of a degree 5 polynomial, and I will pick the values of A and B so that this polynomial could also be written in the form of a degree 3 polynomial, call it q of x, times x minus 1, x minus 2. Now we could set these last two terms to be x minus any number, but for simplicity, let's say we pick 1 and 2. That way, when you receive my polynomial, you know that if you plug in x equals 1 or x equals 2, you should get 0 for both, because that's how I constructed the polynomial. And if you don't get 0, you know there has been an error in transmission. They are called syndromes, which is an apt term, since syndromes are defined as a group of signs that occur together and characterize a particular abnormality. If the message polynomial is not 0 at any of the syndrome values, then there is an error in the code. So how do I find the values of A and B in our example? Well, I take the polynomial without A and B and divide it by x minus 1, x minus 2. I get a degree 3 polynomial, which is what I want, but there is also a remainder of 37x minus 30. So I can move this to the left-hand side. For the polynomial to take the form I want, A must be negative 37 and B positive 30. So I send the message 1, negative 2, 3, 5, negative 37, and 30. You can plug in x equals 1 and x equals 2, and if you get 0 for both, you know the message was sent correctly. But what if there was an error in transmission? Say at position 4, the number has changed to a 6. Well now, if you evaluate at x equals 1 and 2, the polynomial is no longer 0. To figure out where the error occurred, one at a time, you set each coefficient to be a variable. Then find the value of that variable setting the polynomial equal to 0 at x equals 1. You repeat this for x equals 2. And what you find is that the two values are different. This indicates that the second coefficient was not the error. You find the same for all the other coefficients, except when you reach the one where the error occurred. Here, not only are the two values equal, they are also equal to the originally transmitted number, that is 5. So this method allows us both to check and correct errors with only a modest increase in data size. This is a toy example of a Reed-Solomon error-correcting code, developed by mathematicians Irving S. Reed and Gustav Solomon in 1960. The job of decoding Reed-Solomon codes in a brute force way, as we described, can quickly get intensive. In fact, as the Voyager spacecraft floated into the outer solar system, NASA engineers knew their signal-to-noise ratio would get incredibly small. But the promise of Reed-Solomon codes was such that they put an experimental encoder in before launch, wagering that smarter encoding algorithms would follow in the next decade. And that's exactly what happened. To this day, we can make out Voyager's ever-faintening whispers thanks to Reed-Solomon codes. These codes also ensure that your old CDs or DVDs can still play your favorite songs and movies despite multiple scratches. And they are the reason why QR codes still work when damaged. In a QR code, the entire data, starting from the data type, character length byte, our message bytes and final padding, are laid out in a line and converted back into ASCII decimals. Fitting a high-degree polynomial using these can easily make the coefficients blow up. Hence, Reed-Solomon encoding uses finite field arithmetic, Galois fields, to obtain the error-correcting terms. These, converted back into binary, are used to fill out the rest of the QR code. And there we have our complete QR code. But why can't we scan it yet? See how these regions here appear uniformly white and black? Well, sometimes the encoded data can insert plain patterns and blank spaces just by chance. These can confound the readers, which expect to see a noisy checkerboard. They think maybe it's a big damage patch or maybe it's not a QR code at all. But there is a way to fix this. Remember the three blue stones I put in for masking in the format string? Well, they specify one of eight ways to reshuffle the appearance of our QR code pixels to make them seem truly jumbled. This particular mask says flip the pixels so white becomes black and black becomes white for every third column of data. But this does not apply to the functional elements of the code. They remain unchanged. The QR code standard specifies the use of eight masking patterns. In principle, when combined with the correct masking bits, all eight forms of the code are readable, which is why some QR code generators will return different looking codes for the same input string. But which one works best? Well, every continuous or bad patch adds points and each mask gets assigned a score. The mask with the lowest score at the end wins. It's easiest for any reader to scan. For our handmade QR code, I'm going to use the simplest mask. And now we have a working QR code. Try it out. Oh, the moment of truth. Ah, it worked. You know, going through this exercise made me realize again why I hate QR codes. They are not meant for people. I made all kinds of mistakes while just trying to put down these black and white stones. This was really hard to get this perfect. I guess it didn't have to be perfect, but it had to be close enough. All right. Initially, QR codes had only industrial uses. But as a boss, I didn't know if this would work in society. At that time, as a boss, I didn't think this project was a success. But it wasn't long before the value of their data storage capacity was realized. In 2002, mad cow disease resurfaced in the UK. 179 people died from eating contaminated beef. And people panicked. They wanted to know exactly where their meat was coming from and how it was stored before it reached the supermarket. This time, the QR code was available to help. It was one of the first instances where the curious checkerboards started to appear in common use. But why are QR codes so successful? There are plenty of other 2D matrix codes out there. Well, one reason is that Denso Wave decided not to exercise patent rights on QR codes. Since I'm an engineer, I was happy that the QR codes I invented could be used all over the world. As a result, I think it was the right thing to do to make Tokyo open to the public. Denso instead opted to monetize and sell QR code scanners. Of course, with the rise of smartphones, most people would soon carry a QR code scanner in their pocket. But initially, QR code reading apps were third party and rather niche. But then, in 2017, Android and Apple built QR code readers right into their camera apps. So the use of these codes took off. The COVID-19 pandemic also gave QR codes a boost worldwide. Suddenly, restaurants and vendors wanted a contactless way to hand out menus and product information. Contactless payment using QR codes took off in India and China. Today, India sees over 12 billion QR code-enabled transactions per month. QR codes also proved handy in storing vaccine records and personal health information in phone wallets. But their enormous spread has also created problems. A question about QR code safety. In recent years, some scammers have used QR codes to try to defraud people who read them. Do you have concerns about these uses? So as with anything on the internet, you have to pay extra attention to safety. Check where a scanned QR code is taking you before actually clicking on a link. So I want to know about the future of QR codes. What is next for QR codes? I want to make sure that QR codes can only be used for text and letters. The reason for that is that in Japan, there are a lot of disasters and earthquakes. So we can't use the internet or Wi-Fi. If there is an earthquake, the doctor can't go to the hospital. So I want to make sure that QR codes can only be used for text and letters. So I want to make sure that QR codes can only be used for text and letters. Now, if the possibility of running out of UPC barcodes is remote, for QR codes, it is impossible. The number of unique version 1 QR codes using the lowest redundancy level is 2 to the 152. This is about 10 times the total number of legal chessboard configurations, which is also why a random distribution of pixels filled into a QR code pattern generally cannot be interpreted as a message. You have scanned countless QR codes. And when you scan your next one, you'll have a better idea of how it works. But have you ever thought about what QR itself stands for? What is your favorite application of the QR code?