Kind: captions
Language: en
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 you ious 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
Marque 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 DC
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
with no reply a courier delivered a
letter which said his wife was Ill after
child birth 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 Bri
moris from that day forward Morris 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 Vil
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 morsa 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 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
[Music]
industry in the late 1940s Bernard
silver was an engineering 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
after several false starts 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 GIF peanut butter is identified by
the same 12 digits no 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 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 and sephy
opathy or mad cow disease for short it
is spread when cattle ate feed
containing prons 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
called 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 elay 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 PDF 417 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 Vera
code used to track and ident ify 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 Denso 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 am going to build one
myself in the way Masahiro Hara first
conceptualized it with a gobard I have
the usual black and white stones white
represents zero black represents one and
we're going to encode the link to our
YouTube channel on this board so the
first step is to convert ww.youtube.com
/ veritasium into ones and zeros and
we'll do that using bite encoding bite
encoding uses asy which itself has roots
in Morse code every character is
assigned a number from 1 to
256 then we convert the asy decimal into
its binary form since 256 is 2 ^ of 8 we
can use the eight binary bit
combinations to represent all asy
characters these eight bits make up one
bite of information
the letter W is assigned the asky
decimal 119 or 0111
0111 doing the same for all characters
in ww.youtube.com
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 25x 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 one QR code was 21x 21 and the
largest version today is 177x 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 CED 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 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 redstones 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 harison if it had
any special significance but he said
[Music]
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 triple
01 if it's just numbers 0010 if it's
alpha numeric so capital letters and
numbers 0 1 0 0 if it's information
stored in bytes and 1 for Japanese
kji the following eight bits are used to
indicate the number of characters in our
message so since we have 26 characters
that should be
000011 01 0 next we start arranging our
bytes for youtube.com/ veritasium
starting in 8bit two column cells they
follow a zigzag pattern that snakes its
way to the top left within each cell
that represents a bite the most
significant bit corresponding to 2 to 7
is at the bottom right and the least
significant or 2 to the 0 is at the
opposite end 0111 0111 for w will hence
be filled like
this and we'll follow along with the
rest once we fill in the btes for w.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
ww.youtube.com
cells start looking less regular and
more tetris-like but the way we put the
stones bite after bite Remains the
[Music]
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 EXT ra bites 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 s
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 carriers 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 s makes it easy to set up a sell
plan and data 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 eim with s
all I have to do is click on the country
select a plan and activate the eim 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 s you set it up once
and you'll always be connected and if
you find out that your phone isn't
compatible with eims you will get a full
refund so to check out s for free go to
s.com veritasium or click the link in
the description use the code veritas to
get an exclusive 15% off your first
purchase that's
s.com veritasium or you can scan this
handy QR code to get 15% off so I want
to thank Sy 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% cortile 25% and high 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 air
correction is indicated in the format
strip which is present identically in
two
places the simplest way 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 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 1 Z 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 0000 for low 11 one1 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 code words are triple 0
and triple 1 the rest act as disallowed
buffers to indicate errors in
transmission the allowed code words
should be as far apart as
possible here there 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 nus1 / 2 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
zeros or all ones 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
ones and zeros as valid code words so to
provide buffers like before we can
extend the 5- bit string into a 15 bit
string now the 32 valid code words are
each separated by seven vertices or
Hamming distance of seven 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
code
word 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 -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 polinomial
and I will pick the values of A and B so
that this polinomial could also be
written in the form of a degree 3
polinomial call it Q ofx * x -1 x -
2 now we could set these last two terms
to be xus any number but for Simplicity
let's say we pick 1 and
2 that way when you receive my
polinomial you know that if you plug in
x x = 1 or x = 2 you should get zero for
both because that's how I constructed
the polinomial and if you don't get zero
you know there has been an error in
transmission they are called syndromes
which is an act term since syndromes are
defined as a group of signs that occur
together and characterize a particular
abnormality If the message polinomial is
not zero 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 polinomial
Without A and B and divide it by x -1 x
- 2 I get a degree 3 polinomial which is
what I want but there is also a
remainder of 37x - 30 so I can move this
to the left hand side for the polinomial
to take the form I want a must be -37
and B POS 30 so I send the message 1 -2
3 5 - 37 and 30 you can plug in x = 1
and x = 2 and if you get zero for both
you know the message was sent correctly
but what if there was an error in
transmission say at position four the
number has changed to a six well now if
you evaluate at xal 1 and 2 the
polinomial is no longer
zero 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
polinomial equal to 0 at x = 1 you
repeat this for xal 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
five
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 read
Solomon error correcting code developed
by mathematicians Irving s Reed and
Gustav Solomon in
[Music]
1960 the job of decoding read 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 voyagers
ever fainting Whispers thanks to read
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 bite our
message bytes and final padding are laid
out in a line and converted back into
asy decimals fitting a high deegree
polinomial using these can easily make
the coefficients blow up hence read
Solomon encoding uses finite field
arithmetic galwa fields to obtain the
error correcting terms these converted
back into binary are used to fill out
the rest of the QR
[Music]
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 pixel
to make them seem truly jumbled now 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 the moment of
truth then 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 I was 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 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
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 indc's 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 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 for
now if the possibility of running out of
UPC barcodes is remote for QR codes it
is
impossible the number of unique version
one 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
[Music]
code for
[Music]
sh