Transcript MAT 1000 - Mathematics

MAT 1000
Mathematics in Today's World
Winter 2015
Today
We will look at more identification numbers and barcodes.
Codabars
The codabar scheme detects 100% of single digit
errors, and 98% of most other common errors.
It is used by all major credit card companies, as
well as blood banks, and some libraries.
It can be used with ID numbers of various lengths.
Credit card numbers are 16 digits long. The last
digit is a check digit.
Codabars
Odd digits are given weight 2, even digits are
weight 1.
This gives the weighted sum
2𝑎1 + 𝑎2 + 2𝑎3 + 𝑎4 + 2𝑎5 + 𝑎6 + 2𝑎7 + 𝑎8 + 2𝑎9 + 𝑎10 + 2𝑎11 + 𝑎12 + 2𝑎13 + 𝑎14 + 2𝑎15 + 𝑎16
However, the codabar system adds an additional
number to this sum.
We add the number 𝑇, which is the number of
digits in odd positions (1, 3, 5, 7, 9, 11, 13, and 15)
that exceed 4.
Codabars
So we find the sum
2𝑎1 + 𝑎2 + 2𝑎3 + 𝑎4 + 2𝑎5 + 𝑎6 + 2𝑎7 + 𝑎8 + 2𝑎9 + 𝑎10 + 2𝑎11 + 𝑎12 + 2𝑎13 + 𝑎14 + 2𝑎15 + 𝑎16 + 𝑇
This is valid if it ends in a 0.
As an example, let’s determine if the following is a
valid credit card number
3125 6001 9643 0012
Codabars
We find 𝑇 first. Look at the digits in positions 1, 3,
5, 7, 9, 11, 13 and 15:
3125 6001 9643 0012
How many of these numbers are larger than 4?
3125 6 001 9 643 0012
There are 2: the 6 in position 5 and the 9 in
position 9.
So 𝑇 = 2
Codabars
Now we compute the weighted sum of the digits
3125 6001 9643 0012
This is
2⋅3+1+2⋅2+5+2⋅6+0+2⋅0+1+2⋅9+6+2⋅4+3+2⋅0+0+2⋅1+2
Which equals 68.
Finally we add on 𝑇 = 2, to get 70. This ends in a
0, so the number is valid.
Codabars
Example
Find the check digit for the following credit card
number
3541 0232 0033 227
1. Find 𝑇
The digits in odd positions are
3541 0232 0033 227
Only one of these digits is larger than 4 (the last
digit 7), so 𝑇 = 1
Codabars
3541 0232 0033 227
2. Find the weighted sum of these 15 digits:
2⋅3+5+2⋅4+1+2⋅0+2+2⋅3+2+2⋅0+0+2⋅3+3+2⋅2+2+2⋅7
The sum is 59
3. Add 𝑇 = 1
This gives us 60
Codabars
4. Find a check digit that, when added to this sum
gives a last digit of 0.
In this case, our sum 60 already ends in 0, so
our check digit should be 0. That means the
valid number is:
3541 0232 0033 2270
The ISBN-10 Coding System
Is it possible to have a coding system which
catches 100% of single digit errors and 100% of
transposition errors?
Yes. The coding system used for books, called the
ISBN-10 system does this.
ISBN-10 numbers have 10 digits. The last digit is
the check digit.
The ISBN-10 Coding System
The 10-digit ISBN of the textbook for this course is:
1 − 4292 − 4316 − 3
The first digit indicates that the book is published
in an English-speaking country.
The next 4 digits identify the publisher.
The next 4 identify the book.
The last digit is a check digit.
The ISBN-10 Coding System
How can we validate a 10-digit ISBN number?
Once again we use a weighted sum where each
digit gets a different weight:
10𝑎1 + 9𝑎2 + 8𝑎3 + 7𝑎4 + 6𝑎5 + 5𝑎6 + 4𝑎7 + 3𝑎8 + 2𝑎9 + 𝑎10
There is one more difference from the UPC and
codabar systems: to be a valid ISBN this sum
must be “evenly divisible by 11.”
In other words, if we divide by 11 there should be
no remainder.
The ISBN-10 Coding System
How can we tell if a number is evenly divisible by 11?
Divide by 11 and look for a decimal part.
Example
506 is evenly divisible by 11.
506
= 46
11
714 is not evenly divisible by 11
714
= 64.909090 …
11
The ISBN-10 Coding System
The following ISBN is not valid:
1 − 2292 − 0900 − 3
Find the weighted sum of the digits:
10 ⋅ 1 + 9 ⋅ 2 + 8 ⋅ 2 + 7 ⋅ 9 + 6 ⋅ 2 + 5 ⋅ 0 + 4 ⋅ 9 + 3 ⋅ 0 + 2 ⋅ 0 + 3
The sum is equal to 158
But, if we divide 158 by 11, we get 14.363636 …
The result is not a whole number (it has a decimal part), so
158 is not evenly divisible by 11, and the ISBN is not
valid.
The ISBN-10 Coding System
On the other hand, the ISBN for this course’s textbook is
valid:
1 − 4292 − 4316 − 3
The weighted sum is:
10 ⋅ 1 + 9 ⋅ 4 + 8 ⋅ 2 + 7 ⋅ 9 + 6 ⋅ 2 + 5 ⋅ 4 + 4 ⋅ 3 + 3 ⋅ 1 + 2 ⋅ 6 + 3
Which equals 187.
187 ÷ 11 = 17
Since 187 is evenly divisible by 11, the ISBN is valid.
The ISBN-10 Coding System
Unlike the UPC system or the codabar system, the ISBN10 catches all transposition errors. Why isn’t it more
commonly used?
There is one drawback to this system.
Suppose a publisher wants to use the ISBN
1 − 4292 − 0902
What should the check digit be?
The ISBN-10 Coding System
The weighted sum of these nine digits is 177.
The next integer after 177 that is evenly divisible by 11 is
187.
But that means that to get a valid ISBN we must append a
10, and this is a two-digit number.
In order to keep a standard length of 10 digits, publishers
use an X to represent the 10. So the ISBN-10 in this
case is:
1 − 4292 − 0902 − X
Bar Codes
•Written numerals can be hard for
an electronic scanner.
•Machines have an easier time
reading black and white stripes.
•A bar code is a series of dark bars
and light spaces that encodes a
number.
ZIP Code Bar Codes
•Encode ZIP codes as a series of long and short
bars.
•Each digit is encoded by 5 bars.
•In each block of 5 bars, two are long and three are
short.
•Long “guard bars” start and end the bar code.
ZIP+4 Codes
•ZIP+4 is a 9-digit system with more detailed
address information.
•These are encoded the same way, with longer
bar codes.
•The tenth digit is a check digit.
How to Compute ZIP+4 Check Digits
•Start with zip plus four: 𝑎1 𝑎2 𝑎3 𝑎4 𝑎5 𝑎6 𝑎7 𝑎8 𝑎9 .
•Compute 𝑎1 + 𝑎2 + 𝑎3 + 𝑎4 + 𝑎5 + 𝑎6 + 𝑎7 + 𝑎8 +
𝑎9 .
•Divide by 10 with remainder (easy!).
•The check digit 𝑎10 is
 0 if r = 0.
 10 – r if r > 0.
•𝑎1 + 𝑎2 + 𝑎3 + 𝑎4 + 𝑎5 + 𝑎6 + 𝑎7 + 𝑎8 + 𝑎9 + a10
is always a multiple of 10.
UPC Bar Codes
•UPC bar codes are similar to ZIP code bar codes.
•Instead of short and long bars, the information is
carried in the widths of the bars and spaces.
•This works well with supermarket optical scanners.
•What if you scan an item backwards?
•The UPC bar codes use different patterns for the
first half and the second half.