– [Dr Thomas Britz] Hi and
welcome to MATH 3411 Problem 9 in which we’ll be
looking at the ISBN code or more particularly,
the ISBN 10 code. It’s the code consisting of
all the sequences like this. X, the code word there
being equal to x_1 up to x_10 where each of these
is one of these here. It’s one of the decimal numbers, 0, 1, 2, up to 9 and also 10 which
we write as an X and we’re only
choosing the sequences that satisfy this
particular condition here that if you take each
index from 1 to 10 and multiply it
with the value x_1 to x_10, pairwise, add them together, reduce modular 11, then you get 0. So this is a check sum type of, slightly complicated
check sum condition that the ISBN code has. Now the first thing
that we should address is why do we use these codes? And they’ve been around
for quite a while. The International
Standard Book Number, so they’re about codifying or rather giving a
unique code to books and these days, we’re
using the ISBN 13, so we’re adding
three more digits but this was valid
and still in use today for quite a while. So if you have a book, you want to give it
a unique identifier or one of these code words to
say which book is we’ve got? And that’s of course,
useful if you’ve got books, if you’ve got libraries,
if you’re a librarian or if you want to
go look some book up and make sure that
you’re keeping track of your references or whatever. So this is not a code meant
for a lot of information, it’s just occasional information which says something
about books, particular books and there
are some more details which we’ll skip in this example or this problem. There are chunks of
these digits here or 11 digits if you want that make this
code user friendly. In particular, some of
these digits say precisely which country and
region and so forth, which topic we’re talking about. We’ll ignore those
details for now and just look at a
simplified model. So given that we
don’t need this code for a lot of communication, a lot of sending data through some noisy
channel type protection, all we need here is for
it to be user friendly and we don’t really need
any error correction. We just want this property here that the code can
detect one error and also detect when we’re
swapping two digits around and you might see
that that’s useful, for instance, back in the day where you might be a librarian
writing down the ISBNs of books and maybe make a typo, one of these might be wrong or you might swap
a digit by mistake. They’re easy mistakes to make but then this code would
pick up that mistake and say hey, this
is a wrong ISBN. Could you please go
back and check it? So there wouldn’t
be any correcting but there would
be that detection which would be
useful in that case. These days, maybe
that’s not so important. Detecting one error, we could get if we
simplified the check sum, got rid of that i and simply just added
the digits together. So that would be more
similar to the ASCII codes or other things with check sums of the very simple kinds, you just reduce the mod 11, in this case, but if it
were binary code words, you’d reduce just mod 2. The reason that we have this
slightly more complicated sum there is that we also
want this nice condition for digit swapping. The fact that this sort of code does actually
allow detection of an error and digit swaps, we’ve seen in the lectures, in the lecture notes but instead today we’ll
be proving some of it. We’ll be looking at
the detection here and upgrading it
in a certain way and that certain
way is as follows. We’re gonna take this code and upgrade it to not
only detect one error but correct one error. So here’s what we’re gonna do. We could say the new code,
the ISBN plus if you want, is gonna be a new code, let’s call it C plus. Off the same sort of format, except now we’re not only
gonna have this condition, we’ll add another condition which will be more restrictive but allow us to upgrade
that detection to correction and the condition that we
want is sort of like this except it’s just simply the
natural check sum condition. You just take all
of the digits there and add them together. I think in the problem itself, we were restricted to
the numbers from 0 to 9 and not the X there but that’s an irrelevant
detail for now. It actually sort of
makes better sense to have the 10 in it
for these purposes. Oh yeah, we can now upgrade
the detection to correction, so let’s do that and correct, so now I claim that this
code can correct one error and detect a digit swap and that’s what we
actually have to show. Now, I’m gonna be
a bit lazy here. By the way, I’ve
already been a bit lazy because the first part of
this question asked you to estimate how
big this code was. I’ll let you do that, it’s sort of a fun,
a heuristical game. There are several answers and I’ll leave that
as a challenge to you but here in part b, show that this code here can correct one error and also detect a digit swap. Well, here I’m gonna
be lazy once again and say the detection
of digit swaps is exactly the same
for just the usual ISBN and the proof is in the notes and the slides, so
have a look at that and try to understand it and
maybe reproduce it yourself. That would be good. So we’re gonna focus on the
correction of one error. So let’s have a look
at what’s going on. So we might have two people, so here’s a person, happy person and
here’s another person, also happy and this
person there shouts out a ISBN plus code
word, if you want. So code word x there and then it goes
through the air there, it might get
corrupted a little bit and the receiver over there might hear it as something else. Let’s get a black pen here just to signify that it
might not be the same as the sent message. So we’ve got over here, we’ve got sent. That was the code word,
the ISBN plus if you want, 10 digits there satisfying
those two congruence equations and then we’ve got received. This is a rather
more visible pen. Here we go, y and we
have a y there, not an x. So y_1 and like so and let’s assume that there’s
exactly one error here and that error is
in some position. Let’s call it the
kth position there. So these two words here,
the code word that was sent and the word that was received, they’re exactly the same
in all of the coordinates except exactly one coordinate where we have one error here. So error! Okay, now if we want to show that we can correct one error, then we need to do two things. We need to figure out
where the error is, in other words, the value of k and we also need to figure out the difference between x and y, so how much they differ and then we can use
that to correct. So that’s all we need
to do, so let’s do that. Okay, well, we can use
what we’ve got here, so let’s do that. We can start off with
the first sum there but let’s look at the
with one error in it and that’s all the
information we have, so we have to use
the information there which is here somehow
to correct this. So let’s look at the sum here and here I’m just gonna
be a little bit lazy and just use green. So let’s add the black or
the y elements together. Now, all of them are the same as the x except
for that one there. So if we’re adding all
of these y together, we get that that’s
the same as the x for all the indices
not equal to k and then we have
that one here, yk. Okay, now we want to make
that sum equal to that sum because that’s congruent to zero and then things will cancel out, so let’s add the
missing term, the xk and then quickly subtract it so as not to break
mathematics so to speak. So we want this sum there where we’re indexing
over all the is, so we can leave it invisible and we can do that by
subtracting quickly that term that we’ve added there and now we just have yk and because of this
condition here, then this sum is
congruent to 0, mod 11, so we just end up
with these terms and let’s just turn them
around to make it neater. Yk minus xk, mod 11 and there we go. Okay, well, that’s cool actually because now we
know the difference between the received
kth coordinate and the sent kth coordinate and that’s exactly what we need in order to adjust the error and that difference there, that’s given by the sum of the y which we do know
as the receiver. What we don’t know
is the value of k, in other words, we don’t
know where the error is but once we know that,
then we can create it using that difference. So let’s find the value of k. That’s using the
second condition, that this complicated sum is 0, so let’s have a look. So we’ve got this complicated
sum of i and now y. Let’s see if that might
lead to something. Well, again, all of the
y_i are the same as the x_i except in the kth position. So this is exactly the same
sort of things as above. We’ve got that, we have the same terms here except now we’re just adding i or multiplying i
here and k there, otherwise it’s exactly the same. Here we want a sum of
the form over i over x_i for all the is from 1 to 10. We can do that by
adding the missing term, the kth term there and then quickly
subtracting it again, so that would be minus k_{xk} and then we have k_{yk}. K_{yk}. And we can write that as, well, again we’ve got that
this is congruent to zero by the condition
that we have up here. All of the x form a code word and therefore satisfy
those conditions and so that cancels out and
then we can tidy this up by writing, that was ugly,
let’s write it a bit neater by writing k
outside the brackets and then y_k – x_k and all of this is still mod 11. Okay. So to speak. Why is that great? Well, it’s great because
now we actually know what the value of k is. Why is that? Well, we can divide by
the difference here, divide this by the difference, and we’ll get
exactly what we want, so k is equal to well, this sum here which
we can calculate as the person
receiving the message. Then times the inverse
of that difference. Now since we’re
working modular 11, we know that there is
a inverse value to this because well, for one thing, this is not 0. If these two were the same, then there wouldn’t be an error. And for the second thing, we’re working over
the numbers mod 11, so if we’re talking about
nonzero elements, mod 11 or numbers in modular 11, we know that there’s
always gonna be an inverse because 11 is prime. We’ll get to that later
in the course, by the way, if you’re still a little bit
shaky about modular arithmetic. Okay but here we have
the formula for k involving things that we can
calculate as the receiver and here I’ve, no,
that’s correct. I should not correct
something that’s correct. So using the first equation, just the sum of the y, we can find the
difference there. That’s what we’ll use
to correct the error if we know where it is and now we know where it is because k is exactly
equal to that weighted sum times the inverse
of that difference and there we go. Maybe looks a little
bit complicated but it’s not actually too hard and in fact, we’re going
to do this right now with part c where we actually have
to correct a code word. So let’s have a look at that. Okay, so here in part c, we have to correct this
particular received word under the assumption that
there’s exactly one error. So what do we do? Well, we need to figure
out where the error is, that’s the value k there and we also need to know
how to correct the error and we can see
that by finding out what the difference here is. Now if we’re talking
about a binary code, then we wouldn’t actually need to figure out that distance because it would
automatically be one. If you’re sending a 0, then the error would be 1 and vice versa but if you’re dealing with
a bigger number system, like the ternary
system or quaternary or in this case, a number
system with 11 in it, well, then we need
to know exactly how much we have to adjust in order to correct the error. So let’s have a look here. We need to do two things using the formulas that we found just previously in the proof. So first, we have to calculate
this difference here, x_y – x, sorry, (y_k – x_k) and that’s the sum of
all of these y here, so we just add them together, reduce mod 11 and I like to, well, you can do
this in two ways or several ways. You could add them all together, get a number, reduce it mod 11 or you could reduce
things as you go along to make the calculations
just a little bit easier if you’re doing it
by pen and paper or in your head. So anyway, let’s have a look. 6 + 8=14, 16, 23, 24, 27, 35, 40, 40 reduced mod 11 is -4 or 7 if you want, so where is that? So 7, for instance or -4. Now the reason that
I’m using both of these or writing up both of these is that when we do correct and figure out what that
value there x_k is equal to, then we want it to
be a positive value, not a negative value just so that it fits the
parameters of the code. Okay, we’ve done
the first thing, that was easy. We found the difference there, then we need to do
the second thing which is to find the value of k and that tells us exactly
where the error is, so let’s do that. That’s a little bit trickier. K is equal to, well, that weighted sum there times the inverse of what we
found here, this difference. So we need to do
two things first. We need to find
that weighted sum, then we need to find the
inverse of that difference, multiply them together and finally, when
we’ve done that, then we can figure out
what and where the error is and correct it. So let’s look at this
weighted sum first. That’s these numbers
here multiplied by the coordinate
values, 1, 2, 3 and so on and then we need to take
each of these pairs, multiply them together and then add them up
and reduce mod 11. So here, for
instance, 0 x 1=0. And this, 6 + 2=12. Now you can just
do that immediately and then reduce
mod 11 afterwards but I like to just
reduce as I go along. That’s a little bit
quicker for me at least. So 12 is the same as 2. 24, 8 x 3, that’s the same as
2, we have 0 there, – 1, 42 is the same as -2. 1 x 7=7 or -4, 24 is +2, 72 is -5 and finally, we
have 50 which is +6. Okay, what do we have here? We have some cancellations. 2 and -2, 1 and -1. Okay and then we’ve only
got these numbers here. We’ve got 2 + 6=8 – 9 is -1 and we can write -1 or we could write
10 if you wanted to but either is fine for now. So let’s have a look. k is congruent to -1 times and then we’ve
gotta find out the inverse of that difference there which was equal to 7 or -4. So here to find the inverse, you could either use the
Euclidean algorithm backwards and forwards but that’s
a little bit overkill in this case where we’re
dealing with small numbers and in particular, a small
modulus which is just 11. So let’s just look at
the multiples of 7. 7, 14, 21 and so forth, hey 21, let’s write
it somewhere here. So that was 3 x 7 and the reason that I said hey was that 21 was very
close to a multiple of 11 so I just said 21 which is exactly
congruent to -1 mod 11 and what we wanted was to
find some number times 7 that was equal to 1 and we can do that by
just putting a minus in front of the 3, so now we’ve got -3 times 7, that’s -21 and now that’s a +1,
so in other words, we found the inverse of 7. So the inverse of 7, that’s equal to -3 mod 11 or also equal to 8 as you want but actually -3 is not bad here. So we’ve got that the inverse
of this difference here is in fact, equal to -3 and so k is equal to 3 mod 11 and in fact, 3 because this is the
position of the error and it has to be
a positive number between 1 and 10 which it of course is. So that seems to work out. Now we’ve got
everything that we need. We know where the error is. So let’s have a look at that. The error is in the
3rd position here and now we need to figure out what exactly that corrects to, so there we have to say well, we’ve got the, so if we want to
write it up here, this would be x,
the third x (x_3) and the third y (y_3) and if we’re wanting
to try to figure out what that x_3 is equal to. So let’s see. Well, we’ve got that
this difference here is equal to 7, so if we rewrite
that a little bit, so x_3 or that’s our x_k is equal to, well,
the y_k or y_3 and then we have
to subtract the 7 or subtract the -4,
so we’ll add the 4 but do one of those things so that we get a value that when we subtract it from 8 gives us a value between 0 and 10 so let’s see what
that’s equal to and then we can
maybe modify the 7 if we get something outside of the bounds. So that’s equal
to 8-7 which is 1. Yay. The corrected value here
is indeed within the bounds from 0 to 10 so to speak, so that’s the
value that we want, otherwise we’d have to
choose something else from 7. It could be the -4, for
instance, and so on. So we’ve corrected
this value here and indeed, that gives
us the sent message which was x being equal
to everything there. 0, 6, and I’ll skip that part for now and just write up all the rest. And then of course, we
had the corrected value which I’ll draw a
little box there and that was equal to 1, so let’s write that there and that indeed is
in fact the answer. We have in fact, in real life corrected this sort
of enhanced ISBN and that’s the end
of the problem. Thank you very much.

Categories: Articles