– [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

received messages, so we’re that person there, we’ve received that word

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.