1
00:00:00,000 --> 00:00:00,390

2
00:00:00,390 --> 00:00:02,060
PROFESSOR: So OK, what
did we do last time?

3
00:00:02,060 --> 00:00:05,334
Thanks for coming
back by the way.

4
00:00:05,334 --> 00:00:08,870
So last time, we
did MDS codes.

5
00:00:08,870 --> 00:00:15,760

6
00:00:15,760 --> 00:00:17,600
MDS codes, and we
looked at this.

7
00:00:17,600 --> 00:00:21,425
And we derived some generic
properties of these things if

8
00:00:21,425 --> 00:00:22,380
they existed.

9
00:00:22,380 --> 00:00:28,025
And then eventually, we moved
to Reed-Solomon codes.

10
00:00:28,025 --> 00:00:30,730

11
00:00:30,730 --> 00:00:32,759
And so indeed, they exist.

12
00:00:32,759 --> 00:00:36,170
We talked a little bit about
existence altogether, the main

13
00:00:36,170 --> 00:00:39,425
conjection, MDS codes,
I just wrote it down.

14
00:00:39,425 --> 00:00:41,120
And like I said, you
want to be rich and

15
00:00:41,120 --> 00:00:43,890
famous, solve this.

16
00:00:43,890 --> 00:00:50,050
There's people doing geometry
in math that would be

17
00:00:50,050 --> 00:00:52,460
deliriously happy if
you solved it.

18
00:00:52,460 --> 00:00:54,780
So if for nothing else.

19
00:00:54,780 --> 00:00:59,240
So the last thing I wrote down
last time was something about

20
00:00:59,240 --> 00:01:01,800
a matrix which somebody
recognized as some Fourier

21
00:01:01,800 --> 00:01:02,890
transform matrix.

22
00:01:02,890 --> 00:01:06,530
And that's where I want to pick
up here, at least quickly

23
00:01:06,530 --> 00:01:08,460
make that connection.

24
00:01:08,460 --> 00:01:12,500
So let me rewrite the definition
of Reed-Solomon

25
00:01:12,500 --> 00:01:14,330
codes again.

26
00:01:14,330 --> 00:01:19,870
And so a Reed-Solomon code,
the way we defined it last

27
00:01:19,870 --> 00:01:22,475
time was all field elements,
we would evaluate the

28
00:01:22,475 --> 00:01:24,880
polynomial in all
field elements.

29
00:01:24,880 --> 00:01:26,130
Now we do it slightly
different.

30
00:01:26,130 --> 00:01:29,980

31
00:01:29,980 --> 00:01:34,590
Let me make it Solomon-Stein
in order to denote that

32
00:01:34,590 --> 00:01:35,320
difference.

33
00:01:35,320 --> 00:01:46,150
And let's say this is
beta 0, beta n.

34
00:01:46,150 --> 00:01:59,420

35
00:01:59,420 --> 00:02:00,730
So that's the old definition.

36
00:02:00,730 --> 00:02:11,530
Only the, let's say, the beta 0,
beta 1, up to beta n, they

37
00:02:11,530 --> 00:02:13,730
are the non-zero elements now.

38
00:02:13,730 --> 00:02:17,390
And just for the heck of it, so
we talked about punctured

39
00:02:17,390 --> 00:02:19,360
Reed-Solomon codes last
time that it would

40
00:02:19,360 --> 00:02:20,600
still be MDS codes.

41
00:02:20,600 --> 00:02:22,185
So nothing has changed there.

42
00:02:22,185 --> 00:02:25,510
In particular, all the arguments
would be the same.

43
00:02:25,510 --> 00:02:32,170
In particular, just to humor me,
let's say beta i is omega

44
00:02:32,170 --> 00:02:42,920
to the i, where omega
is primitive in Fq.

45
00:02:42,920 --> 00:02:46,790
So what that means, you remember
that primitive means

46
00:02:46,790 --> 00:02:48,460
that the powers of omega
cycle through all

47
00:02:48,460 --> 00:02:51,040
the non-zero elements.

48
00:02:51,040 --> 00:02:54,760
Remember the non-zero elements
are a multiplicative group.

49
00:02:54,760 --> 00:02:55,830
And it's a cyclic group.

50
00:02:55,830 --> 00:02:57,080
And it's the generator
of the group.

51
00:02:57,080 --> 00:02:59,970

52
00:02:59,970 --> 00:03:01,220
Good.

53
00:03:01,220 --> 00:03:06,020

54
00:03:06,020 --> 00:03:19,180
So once we write it like this,
we can actually write down the

55
00:03:19,180 --> 00:03:23,680
whole Reed-Solomon code in some
sort of transfer domain

56
00:03:23,680 --> 00:03:25,855
description in the Fourier
transform.

57
00:03:25,855 --> 00:03:28,710
And the way this goes
is the following.

58
00:03:28,710 --> 00:03:36,000
So from now on, I will make
implicit identification

59
00:03:36,000 --> 00:03:37,950
without making them.

60
00:03:37,950 --> 00:03:39,680
So this is an identification
which I

61
00:03:39,680 --> 00:03:41,360
just jump around between.

62
00:03:41,360 --> 00:03:42,790
A vector --

63
00:03:42,790 --> 00:03:49,280
so this one would be a Fqn.

64
00:03:49,280 --> 00:03:57,604
And Fx would be maybe
0 to MDS 1.

65
00:03:57,604 --> 00:04:10,370

66
00:04:10,370 --> 00:04:11,310
Let's leave it at that.

67
00:04:11,310 --> 00:04:12,080
So I make this --

68
00:04:12,080 --> 00:04:13,820
AUDIENCE: [INAUDIBLE].

69
00:04:13,820 --> 00:04:18,430
PROFESSOR: Yeah, let's make
this identification free.

70
00:04:18,430 --> 00:04:21,570
It's just a vector of length n
and a polynomial of length n.

71
00:04:21,570 --> 00:04:24,240
And so whenever I want this
to have a low degree, the

72
00:04:24,240 --> 00:04:29,010
polynomial, then I just
write that expression.

73
00:04:29,010 --> 00:04:32,490
So this identification
we make freely now.

74
00:04:32,490 --> 00:04:36,620
And then how can we write F?

75
00:04:36,620 --> 00:04:48,820
Let F now be code word in
the Reed-Solomon code.

76
00:04:48,820 --> 00:04:50,000
And then I say Fi.

77
00:04:50,000 --> 00:04:51,620
What is Fi?

78
00:04:51,620 --> 00:04:54,390
The i is element.

79
00:04:54,390 --> 00:05:03,400
Well, we know that this is
F of omega to the i.

80
00:05:03,400 --> 00:05:07,200
So this is, at the moment,
counted from 0.

81
00:05:07,200 --> 00:05:09,100
So this is --

82
00:05:09,100 --> 00:05:10,730
you write it out --

83
00:05:10,730 --> 00:05:16,820

84
00:05:16,820 --> 00:05:32,340
Fj omega to the i to the
j, which is omega i j.

85
00:05:32,340 --> 00:05:33,530
And now, at this point in time,

86
00:05:33,530 --> 00:05:34,780
everybody recognizes this.

87
00:05:34,780 --> 00:05:38,000

88
00:05:38,000 --> 00:05:41,670
This would be the discrete
Fourier transform of a vector.

89
00:05:41,670 --> 00:05:45,940
This is an element of order n.

90
00:05:45,940 --> 00:05:47,840
Usually, there's e to
the j and then an

91
00:05:47,840 --> 00:05:48,970
element of order n.

92
00:05:48,970 --> 00:05:50,240
Now it's in the finite field.

93
00:05:50,240 --> 00:05:53,100
But what's the difference?

94
00:05:53,100 --> 00:05:55,180
This would be the Fourier
transform.

95
00:05:55,180 --> 00:05:58,450
So a code word would be the
Fourier transform of a vector

96
00:05:58,450 --> 00:06:03,350
F. Let's just make sure it also
goes the other direction.

97
00:06:03,350 --> 00:06:12,410
So I claim that Fl would be --
so what would be the Fourier

98
00:06:12,410 --> 00:06:16,630
transform if it, indeed, is
the Fourier transform?

99
00:06:16,630 --> 00:06:25,680
It is a minus, and then
it goes n minus 1

100
00:06:25,680 --> 00:06:31,450
Fj omega minus jl.

101
00:06:31,450 --> 00:06:34,560
So the question is
is that true?

102
00:06:34,560 --> 00:06:37,400
Because that would
be the inverse.

103
00:06:37,400 --> 00:06:38,978
Is that true?

104
00:06:38,978 --> 00:06:43,750
Well, let's do what we do with
proofs of this type.

105
00:06:43,750 --> 00:06:46,860

106
00:06:46,860 --> 00:06:47,860
I need that space here.

107
00:06:47,860 --> 00:06:48,286
AUDIENCE: [INAUDIBLE].

108
00:06:48,286 --> 00:06:48,712
PROFESSOR: Sorry?

109
00:06:48,712 --> 00:06:49,990
AUDIENCE: [INAUDIBLE].

110
00:06:49,990 --> 00:06:50,420
PROFESSOR: Yeah.

111
00:06:50,420 --> 00:06:52,540
So let's do what we do with
proofs of this type.

112
00:06:52,540 --> 00:06:56,970
That means we write it out.

113
00:06:56,970 --> 00:06:59,170
That's another beautiful thing
about finite fields.

114
00:06:59,170 --> 00:07:02,790
You never have to worry
about convergence.

115
00:07:02,790 --> 00:07:07,310
So for the F, we just
plug that in here.

116
00:07:07,310 --> 00:07:10,310
Sum, this would be --

117
00:07:10,310 --> 00:07:11,590
what do we call it --

118
00:07:11,590 --> 00:07:25,970

119
00:07:25,970 --> 00:07:33,920
Fi omega to the ij.

120
00:07:33,920 --> 00:07:38,860
So this would be Fj.

121
00:07:38,860 --> 00:07:42,600
And then I want omega
minus jl.

122
00:07:42,600 --> 00:07:43,535
So is that true?

123
00:07:43,535 --> 00:07:45,930
Is the identity now true?

124
00:07:45,930 --> 00:07:47,420
Well, we see two sums.

125
00:07:47,420 --> 00:07:50,200
What do we do with two sums?

126
00:07:50,200 --> 00:07:52,000
If we're compelled to exchange
the order, that's

127
00:07:52,000 --> 00:07:55,570
always what we do.

128
00:07:55,570 --> 00:08:02,150
So Fi goes out.

129
00:08:02,150 --> 00:08:09,900
And then you get
omega to the --

130
00:08:09,900 --> 00:08:12,160
what do we do --

131
00:08:12,160 --> 00:08:15,290
i minus l times j.

132
00:08:15,290 --> 00:08:23,100

133
00:08:23,100 --> 00:08:25,970
We have this.

134
00:08:25,970 --> 00:08:27,450
And so what is this?

135
00:08:27,450 --> 00:08:30,480

136
00:08:30,480 --> 00:08:33,270
How can we work this out?

137
00:08:33,270 --> 00:08:35,280
Well, you know how to
express the sum.

138
00:08:35,280 --> 00:08:42,280
So this part of the sum is
really just omega i minus l to

139
00:08:42,280 --> 00:08:49,472
the n minus 1 minus 1.

140
00:08:49,472 --> 00:08:51,690
Well, that's a standard
formula for summing

141
00:08:51,690 --> 00:08:52,840
these things up.

142
00:08:52,840 --> 00:08:57,280
But omega is an element
of order n.

143
00:08:57,280 --> 00:08:58,900
Omega was an element
of order n.

144
00:08:58,900 --> 00:08:59,870
That's how we chose it.

145
00:08:59,870 --> 00:09:00,750
AUDIENCE: [INAUDIBLE].

146
00:09:00,750 --> 00:09:01,595
PROFESSOR: It's what?

147
00:09:01,595 --> 00:09:04,040
AUDIENCE: [INAUDIBLE].

148
00:09:04,040 --> 00:09:06,680
PROFESSOR: You multiplied
omega --

149
00:09:06,680 --> 00:09:09,630
it's primitive in the
field, so omega --

150
00:09:09,630 --> 00:09:17,430
we have omega da-da-da-da-da i
unequal to 1 for all i less

151
00:09:17,430 --> 00:09:22,300
than n and omega n
is equal to 1.

152
00:09:22,300 --> 00:09:23,550
So OK.

153
00:09:23,550 --> 00:09:27,640

154
00:09:27,640 --> 00:09:28,570
That's fine.

155
00:09:28,570 --> 00:09:29,910
So it's an element of order n.

156
00:09:29,910 --> 00:09:31,360
That means the n-th power.

157
00:09:31,360 --> 00:09:32,610
We can interchange this.

158
00:09:32,610 --> 00:09:35,080

159
00:09:35,080 --> 00:09:39,070
So this is 1 to the some
power remains 1.

160
00:09:39,070 --> 00:09:40,790
So 1 minus 1 is 0.

161
00:09:40,790 --> 00:09:41,620
The denominator --

162
00:09:41,620 --> 00:09:44,140
well, actually, we get
two results here.

163
00:09:44,140 --> 00:09:51,555
If i is unequal to l,
then this is 0.

164
00:09:51,555 --> 00:09:56,720

165
00:09:56,720 --> 00:10:02,590
If i is equal to l, then this
was just the sum of n once.

166
00:10:02,590 --> 00:10:05,240
So we get n here.

167
00:10:05,240 --> 00:10:05,970
i equal to 0.

168
00:10:05,970 --> 00:10:13,790
But n was q minus 1, the number
of non-zero field

169
00:10:13,790 --> 00:10:17,050
elements because it was
primitive in the field.

170
00:10:17,050 --> 00:10:23,990
And this one is just minus
1 in the field.

171
00:10:23,990 --> 00:10:30,190
Because q, we compute q is the
power of the prime of p.

172
00:10:30,190 --> 00:10:31,220
So that would be 0.

173
00:10:31,220 --> 00:10:33,220
If we just come out
as minus 1, that

174
00:10:33,220 --> 00:10:34,650
explains this minus here.

175
00:10:34,650 --> 00:10:37,000
And we can get rid of
the question mark.

176
00:10:37,000 --> 00:10:39,810

177
00:10:39,810 --> 00:10:42,180
Look correct?

178
00:10:42,180 --> 00:10:42,550
All right.

179
00:10:42,550 --> 00:10:43,985
According to popular
vote, it is.

180
00:10:43,985 --> 00:10:47,470

181
00:10:47,470 --> 00:10:48,740
So what do we really
have here?

182
00:10:48,740 --> 00:10:51,340
We have everything we want
from a Fourier transform.

183
00:10:51,340 --> 00:10:53,740
We have a Fourier
transform pair.

184
00:10:53,740 --> 00:11:00,130

185
00:11:00,130 --> 00:11:04,780
We have a vector f, which we can
think of as being in the

186
00:11:04,780 --> 00:11:06,030
frequency domain.

187
00:11:06,030 --> 00:11:08,800

188
00:11:08,800 --> 00:11:15,700
Then we have a vector F,
which is a Fourier

189
00:11:15,700 --> 00:11:17,920
transform of that.

190
00:11:17,920 --> 00:11:31,390
This one would be in the code
if the degree of this

191
00:11:31,390 --> 00:11:32,880
polynomial here would
be less than k.

192
00:11:32,880 --> 00:11:36,410

193
00:11:36,410 --> 00:11:39,260
So now how can we understand
Reed-Solomon codes now from an

194
00:11:39,260 --> 00:11:41,010
engineering point of view?

195
00:11:41,010 --> 00:11:43,150
Classical --

196
00:11:43,150 --> 00:11:45,110
what about band-limited
functions?

197
00:11:45,110 --> 00:11:47,936
What do we know about
band-limited functions?

198
00:11:47,936 --> 00:11:54,442
Because in a sense, the degree
less than k, this means that

199
00:11:54,442 --> 00:11:58,810
Fi is 0 for all i
greater than k.

200
00:11:58,810 --> 00:12:01,320

201
00:12:01,320 --> 00:12:02,820
That's what it means.

202
00:12:02,820 --> 00:12:06,070
So in a sense, it's nothing but
a band-limited function if

203
00:12:06,070 --> 00:12:09,060
this is a frequency domain,
if you consider this as a

204
00:12:09,060 --> 00:12:10,320
frequency domain.

205
00:12:10,320 --> 00:12:14,600
So what do we know about the
band-limited function?

206
00:12:14,600 --> 00:12:18,590
Well, if a function
is band limited,

207
00:12:18,590 --> 00:12:20,780
it cannot be impulsive.

208
00:12:20,780 --> 00:12:22,000
We know that.

209
00:12:22,000 --> 00:12:25,940
It's a part of the frequency,
and the frequency domain is

210
00:12:25,940 --> 00:12:30,520
inversely relational to the
support of the function.

211
00:12:30,520 --> 00:12:32,660
So the whole idea of
Reed-Solomon codes, in a

212
00:12:32,660 --> 00:12:35,540
sense, can actually be
understood, at least

213
00:12:35,540 --> 00:12:37,960
intuitively, from Fourier
transform and the duality

214
00:12:37,960 --> 00:12:40,162
between time and frequency.

215
00:12:40,162 --> 00:12:41,094
Yeah.

216
00:12:41,094 --> 00:12:43,430
AUDIENCE: Was q a
prime number?

217
00:12:43,430 --> 00:12:47,722
PROFESSOR: q is not prime.
q is a power of a prime.

218
00:12:47,722 --> 00:12:49,000
q to the n.

219
00:12:49,000 --> 00:12:50,250
AUDIENCE: [INAUDIBLE].

220
00:12:50,250 --> 00:12:52,930

221
00:12:52,930 --> 00:12:54,840
PROFESSOR: There always is.

222
00:12:54,840 --> 00:12:55,400
Oh, sorry.

223
00:12:55,400 --> 00:12:56,350
AUDIENCE: [INAUDIBLE]

224
00:12:56,350 --> 00:12:59,820
or because for any q, there
would be always a primitive?

225
00:12:59,820 --> 00:13:02,740
PROFESSOR: Why there's always
a primitive element

226
00:13:02,740 --> 00:13:03,990
in the field --

227
00:13:03,990 --> 00:13:06,350

228
00:13:06,350 --> 00:13:07,360
yeah, sorry.

229
00:13:07,360 --> 00:13:08,820
I thought you had gone
through that.

230
00:13:08,820 --> 00:13:11,710

231
00:13:11,710 --> 00:13:15,370
It's because the non-zero
elements in a field always

232
00:13:15,370 --> 00:13:18,110
make up a multiplicative
group.

233
00:13:18,110 --> 00:13:21,640
And it's always a cyclic
multiplicative group.

234
00:13:21,640 --> 00:13:25,690
So it's a cyclic multiplicative
group.

235
00:13:25,690 --> 00:13:28,932
And it's just the generator
of that group.

236
00:13:28,932 --> 00:13:30,700
AUDIENCE: [INAUDIBLE]
it was a --

237
00:13:30,700 --> 00:13:32,800
PROFESSOR: It's the same
statement as saying, a cyclic

238
00:13:32,800 --> 00:13:34,050
group has a generator.

239
00:13:34,050 --> 00:13:38,394

240
00:13:38,394 --> 00:13:43,024
AUDIENCE: If Fq, for example,
was a z, zq,

241
00:13:43,024 --> 00:13:46,680
then q has to be prime.

242
00:13:46,680 --> 00:13:47,290
PROFESSOR: Yeah.

243
00:13:47,290 --> 00:13:49,480
Yeah, in order for it to be a
field, q has to be prime.

244
00:13:49,480 --> 00:13:49,905
Right.

245
00:13:49,905 --> 00:13:51,180
That's true.

246
00:13:51,180 --> 00:13:52,030
That's true.

247
00:13:52,030 --> 00:13:55,490
But we are not worried
about --

248
00:13:55,490 --> 00:13:58,150
There's also a beautiful theory
[UNINTELLIGIBLE PHRASE]

249
00:13:58,150 --> 00:14:01,950
rings if this would not be a
prime, very nice theory,

250
00:14:01,950 --> 00:14:03,775
becomes a little bit
more technical.

251
00:14:03,775 --> 00:14:05,855
You see, more technical,
then more difficult.

252
00:14:05,855 --> 00:14:09,960

253
00:14:09,960 --> 00:14:13,210
I just wanted to give you this
correspondence on the Fourier

254
00:14:13,210 --> 00:14:16,170
transform because it's, from an
engineering point of view,

255
00:14:16,170 --> 00:14:19,200
a very nice insight.

256
00:14:19,200 --> 00:14:21,510
One of the reasons one can
understand that Reed-Solomon

257
00:14:21,510 --> 00:14:24,220
codes have a good minimum
distance is because it has a

258
00:14:24,220 --> 00:14:25,790
transform of a band-limited
function.

259
00:14:25,790 --> 00:14:29,890

260
00:14:29,890 --> 00:14:31,170
So that's what I wanted
to say about the

261
00:14:31,170 --> 00:14:33,240
Fourier transforms here.

262
00:14:33,240 --> 00:14:34,820
I do not want to spend
too much time.

263
00:14:34,820 --> 00:14:36,145
I have to get through
decoding here.

264
00:14:36,145 --> 00:14:40,280

265
00:14:40,280 --> 00:14:42,820
Since we have now this Fourier
transform correspondence, we

266
00:14:42,820 --> 00:14:43,740
can do another thing.

267
00:14:43,740 --> 00:15:00,720
We can, namely, say, well, F is
in the code if and only if

268
00:15:00,720 --> 00:15:02,420
the Fourier transform --

269
00:15:02,420 --> 00:15:05,740
so that was the back
transform here.

270
00:15:05,740 --> 00:15:09,340

271
00:15:09,340 --> 00:15:11,480
Also now, the code word, we can
interpret the code word as

272
00:15:11,480 --> 00:15:12,180
a polynomial.

273
00:15:12,180 --> 00:15:15,460
And the inverse transform
is just evaluating

274
00:15:15,460 --> 00:15:19,980
it at an omega again.

275
00:15:19,980 --> 00:15:26,010
F is in the code if and only the
transform of a code word

276
00:15:26,010 --> 00:15:34,385
is 0 for all i greater than
k up to n minus 1.

277
00:15:34,385 --> 00:15:34,850
Yeah.

278
00:15:34,850 --> 00:15:36,100
AUDIENCE: [INAUDIBLE].

279
00:15:36,100 --> 00:15:38,790

280
00:15:38,790 --> 00:15:41,375
PROFESSOR: So it basically
just means the support.

281
00:15:41,375 --> 00:15:46,400

282
00:15:46,400 --> 00:15:49,650
If this one is band limited,
then this one cannot have

283
00:15:49,650 --> 00:15:51,610
arbitrarily small support.

284
00:15:51,610 --> 00:15:55,110
That's what it means.

285
00:15:55,110 --> 00:15:56,460
That's really all
I wanted to say.

286
00:15:56,460 --> 00:16:02,510

287
00:16:02,510 --> 00:16:09,620
i greater than k and
less than n.

288
00:16:09,620 --> 00:16:15,470
So we have that F is in the
code if and only the

289
00:16:15,470 --> 00:16:20,700
polynomial evaluates to 0
at a bunch of points.

290
00:16:20,700 --> 00:16:23,060
Now that leads to something
interesting.

291
00:16:23,060 --> 00:16:28,700
Because now we can say, well,
so what if we've just

292
00:16:28,700 --> 00:16:34,860
construct our set of vectors F
so that they evaluate to 0

293
00:16:34,860 --> 00:16:37,190
somewhere where we want
them to zero.

294
00:16:37,190 --> 00:16:40,630
We construct them somewhat
differently than here.

295
00:16:40,630 --> 00:16:48,250
And in particular, let's define
g as a product of i

296
00:16:48,250 --> 00:16:58,560
equal k up to n minus 1 of
x minus omega minus i.

297
00:16:58,560 --> 00:17:00,950
So it's a polynomial.

298
00:17:00,950 --> 00:17:07,369
This is a polynomial which
satisfies this.

299
00:17:07,369 --> 00:17:16,210
So in particular, we have g of
omega minus i is equal to 0

300
00:17:16,210 --> 00:17:20,481
for all i less than
n less than --

301
00:17:20,481 --> 00:17:21,864
I'm sorry --

302
00:17:21,864 --> 00:17:23,250
and greater than k.

303
00:17:23,250 --> 00:17:26,540

304
00:17:26,540 --> 00:17:30,700
So this is a code word, right?

305
00:17:30,700 --> 00:17:33,116
We are agreed this
is a code word?

306
00:17:33,116 --> 00:17:33,940
Good.

307
00:17:33,940 --> 00:17:36,330
So we found a code word without
going through this

308
00:17:36,330 --> 00:17:40,020
here, without going through
the evaluation map.

309
00:17:40,020 --> 00:17:42,000
We found it straight away.

310
00:17:42,000 --> 00:17:44,210
But not only did we find this.

311
00:17:44,210 --> 00:17:48,470
This has degree n minus k.

312
00:17:48,470 --> 00:17:51,190
This has degree n minus k.

313
00:17:51,190 --> 00:17:53,990
So maybe there's another
interpretation.

314
00:17:53,990 --> 00:17:59,000
Now we can give a whole new
definition of the Reed-Solomon

315
00:17:59,000 --> 00:18:08,110
code, namely, as a set of
polynomials, which are sort of

316
00:18:08,110 --> 00:18:17,490
implicitly identified with a set
of vectors such that times

317
00:18:17,490 --> 00:18:30,830
this g of x and h of x
is less then k again.

318
00:18:30,830 --> 00:18:35,330
So what we have here, it's
again, you take a vector space

319
00:18:35,330 --> 00:18:38,050
of functions the h.

320
00:18:38,050 --> 00:18:40,800
It's a k dimensional
vector space.

321
00:18:40,800 --> 00:18:43,426
And we multiplied with this g.

322
00:18:43,426 --> 00:18:46,280
It's again a linear map, this
multiplication with a fixed

323
00:18:46,280 --> 00:18:47,530
polynomial.

324
00:18:47,530 --> 00:18:49,220

325
00:18:49,220 --> 00:18:52,340
A linear map of this vector
space gives us, again, a

326
00:18:52,340 --> 00:18:54,810
vector space of dimension k.

327
00:18:54,810 --> 00:19:01,260
And all elements in this vector
space evaluate to 0 for

328
00:19:01,260 --> 00:19:04,270
all omega to the minus i.

329
00:19:04,270 --> 00:19:06,140
That's just the same
again, just the

330
00:19:06,140 --> 00:19:07,570
Reed-Solomon code again.

331
00:19:07,570 --> 00:19:12,140
So it's a very nice
complementary description to

332
00:19:12,140 --> 00:19:17,210
the same Reed-Solomon code we
could define up here, we have

333
00:19:17,210 --> 00:19:18,665
found again down here.

334
00:19:18,665 --> 00:19:23,300

335
00:19:23,300 --> 00:19:24,550
What is so nice about this?

336
00:19:24,550 --> 00:19:30,350

337
00:19:30,350 --> 00:19:33,830
Yeah, what do you think
is so nice about this?

338
00:19:33,830 --> 00:19:35,080
About this description?

339
00:19:35,080 --> 00:19:39,960

340
00:19:39,960 --> 00:19:42,344
So now you have to think
as engineers.

341
00:19:42,344 --> 00:19:43,710
AUDIENCE: You can still
evaluate it.

342
00:19:43,710 --> 00:19:47,930
There, we have to evaluate it
at end points of function.

343
00:19:47,930 --> 00:19:48,930
PROFESSOR: Yeah, exactly.

344
00:19:48,930 --> 00:19:51,710
This is so easy to implement.

345
00:19:51,710 --> 00:19:55,730
So now we think a little
bit about encoder.

346
00:19:55,730 --> 00:20:04,320
An encoder for a Reed-Solomon
code.

347
00:20:04,320 --> 00:20:05,570
How would we do that?

348
00:20:05,570 --> 00:20:07,710

349
00:20:07,710 --> 00:20:08,760
You look at this here.

350
00:20:08,760 --> 00:20:09,950
Hey, let's do this.

351
00:20:09,950 --> 00:20:11,550
Let's exactly do this.

352
00:20:11,550 --> 00:20:18,810
Meaning in VLSI, we do
something like --

353
00:20:18,810 --> 00:20:36,720

354
00:20:36,720 --> 00:20:38,450
and here, you would write
-- and this is

355
00:20:38,450 --> 00:20:41,700
just a delay element.

356
00:20:41,700 --> 00:20:48,290
This one would be g n minus k.

357
00:20:48,290 --> 00:20:49,540
This one --

358
00:20:49,540 --> 00:20:54,150

359
00:20:54,150 --> 00:20:56,120
so these would be the
coefficients.

360
00:20:56,120 --> 00:20:58,990
This polynomial, we can evaluate
once and for all.

361
00:20:58,990 --> 00:21:01,790
We do that once before we
start our communication.

362
00:21:01,790 --> 00:21:04,040
We evaluate that polynomial
once and for all.

363
00:21:04,040 --> 00:21:06,050
We know these coefficients.

364
00:21:06,050 --> 00:21:10,770
So these are multipliers which
multiply with those

365
00:21:10,770 --> 00:21:12,060
corresponding coefficients.

366
00:21:12,060 --> 00:21:19,450
And we feed into here the
coefficients of this

367
00:21:19,450 --> 00:21:20,160
polynomial.

368
00:21:20,160 --> 00:21:22,430
This is our information symbols,
which we simply feed

369
00:21:22,430 --> 00:21:25,930
into this circuitry.

370
00:21:25,930 --> 00:21:30,410
And into this circuit, out
comes F, out comes the

371
00:21:30,410 --> 00:21:32,290
coefficient.

372
00:21:32,290 --> 00:21:34,300
Polynomial multiplication.

373
00:21:34,300 --> 00:21:37,200
If you show that to a
VLSI designer, they

374
00:21:37,200 --> 00:21:39,330
are deliriously happy.

375
00:21:39,330 --> 00:21:40,470
They say, you know what?

376
00:21:40,470 --> 00:21:41,690
I implement you this thing.

377
00:21:41,690 --> 00:21:45,940
I implement you in 5,000 gates,
which is close to

378
00:21:45,940 --> 00:21:47,190
nothing nowadays.

379
00:21:47,190 --> 00:21:49,760

380
00:21:49,760 --> 00:21:50,240
Maybe not.

381
00:21:50,240 --> 00:21:53,690
Maybe 10,000.

382
00:21:53,690 --> 00:21:56,500
And there you get to the
second reason that

383
00:21:56,500 --> 00:21:58,680
Reed-Solomon codes
are so extremely

384
00:21:58,680 --> 00:22:00,540
important in practice.

385
00:22:00,540 --> 00:22:04,660
On the one hand, they are MDS
codes, meaning they are about

386
00:22:04,660 --> 00:22:07,820
as good as it gets.

387
00:22:07,820 --> 00:22:10,615
And on the other hand,
they are algorithms.

388
00:22:10,615 --> 00:22:15,725
They are circuitry for these
things whose cost is close to

389
00:22:15,725 --> 00:22:18,970
nothing at least today.

390
00:22:18,970 --> 00:22:21,770
When they were invented, that
was quite different.

391
00:22:21,770 --> 00:22:25,250
In the '60s, that would have
not been implementable with

392
00:22:25,250 --> 00:22:27,680
transistors on a board or
something like that.

393
00:22:27,680 --> 00:22:29,920
But today, the cost is
close to nothing.

394
00:22:29,920 --> 00:22:32,380
So the whole algorithmic
treatment of Reed-Solomon

395
00:22:32,380 --> 00:22:36,000
codes is very well developed.

396
00:22:36,000 --> 00:22:37,570
The encoder you could
do like this.

397
00:22:37,570 --> 00:22:38,886
Yeah.

398
00:22:38,886 --> 00:22:40,983
AUDIENCE: Question about why
do you still require that

399
00:22:40,983 --> 00:22:43,546
degree [INAUDIBLE]?

400
00:22:43,546 --> 00:22:45,095
PROFESSOR: You don't
need to do that.

401
00:22:45,095 --> 00:22:47,160
But then the mapping is not
one-to-one anymore.

402
00:22:47,160 --> 00:22:50,580

403
00:22:50,580 --> 00:22:52,550
Then the mapping is not
one-to-one anymore.

404
00:22:52,550 --> 00:22:56,120

405
00:22:56,120 --> 00:22:58,170
Let's put it other ways.

406
00:22:58,170 --> 00:23:00,280
You want code words
of length n.

407
00:23:00,280 --> 00:23:03,590
If the degree is larger,
you run over.

408
00:23:03,590 --> 00:23:06,250
In order to still get a code
word, then you have to take it

409
00:23:06,250 --> 00:23:08,840
modular x to the n minus 1.

410
00:23:08,840 --> 00:23:11,340
And that would fold the
coefficients back.

411
00:23:11,340 --> 00:23:13,890
And still, it gives you a valid
code word then, but this

412
00:23:13,890 --> 00:23:16,900
is not one-to-one anymore.

413
00:23:16,900 --> 00:23:19,980
Anyway, the short answer is if
you allow more, then they

414
00:23:19,980 --> 00:23:22,160
become longer than n.

415
00:23:22,160 --> 00:23:25,410

416
00:23:25,410 --> 00:23:29,860
So what's the time?

417
00:23:29,860 --> 00:23:31,050
OK.

418
00:23:31,050 --> 00:23:32,880
So this is a nice encoder.

419
00:23:32,880 --> 00:23:39,730
There even is a nicer encoder,
which I just want to give the

420
00:23:39,730 --> 00:23:41,950
formula for.

421
00:23:41,950 --> 00:23:44,540
The one reason that people still
have a problem with this

422
00:23:44,540 --> 00:23:46,860
is it's not systematic.

423
00:23:46,860 --> 00:23:52,185
People like to see the symbols
in the code words themselves.

424
00:23:52,185 --> 00:23:54,226
They want the systematic part.

425
00:23:54,226 --> 00:23:56,890
How could we achieve that?

426
00:23:56,890 --> 00:24:00,150
Well, we go from the same
description here.

427
00:24:00,150 --> 00:24:06,530
We say, well, let
h of x be given.

428
00:24:06,530 --> 00:24:09,970

429
00:24:09,970 --> 00:24:23,060
Then compute x to the n minus k
times h of x modular g of x.

430
00:24:23,060 --> 00:24:28,910
So we divide this polynomial
by this polynomial g --

431
00:24:28,910 --> 00:24:29,860
it has a name.

432
00:24:29,860 --> 00:24:32,240
It's called the generator
polynomial.

433
00:24:32,240 --> 00:24:34,790
We divide it by g.

434
00:24:34,790 --> 00:24:43,960
And out comes some polynomial
r of x of some low degree,

435
00:24:43,960 --> 00:24:45,210
degree less than g.

436
00:24:45,210 --> 00:24:47,960

437
00:24:47,960 --> 00:24:56,900
And degree r of x less than
n minus k in particular.

438
00:24:56,900 --> 00:24:59,100
So and then we can
form a code word.

439
00:24:59,100 --> 00:25:05,110
I claim F of x, no, F is --

440
00:25:05,110 --> 00:25:12,040
and here we write r, and
here we write h.

441
00:25:12,040 --> 00:25:15,220
The coefficient vector
of h and the

442
00:25:15,220 --> 00:25:17,870
coefficient vector of r.

443
00:25:17,870 --> 00:25:20,870
Why is that a code word?

444
00:25:20,870 --> 00:25:21,850
Why is that a code word?

445
00:25:21,850 --> 00:25:23,190
Maybe minus here.

446
00:25:23,190 --> 00:25:25,270
I'm always thinking
characteristic 2 anyway.

447
00:25:25,270 --> 00:25:28,180
So why is this a code word?

448
00:25:28,180 --> 00:25:29,430
Anybody, it's clear?

449
00:25:29,430 --> 00:25:32,534

450
00:25:32,534 --> 00:25:42,970
What this is in terms of F of
x is r of x plus h of x.

451
00:25:42,970 --> 00:25:45,545

452
00:25:45,545 --> 00:25:48,000
Oh, minus r of x.

453
00:25:48,000 --> 00:25:50,240
That's because we wrote
it like this.

454
00:25:50,240 --> 00:25:59,870
If we now take the F of x
modular g of x, well, this

455
00:25:59,870 --> 00:26:02,400
part has degree low.

456
00:26:02,400 --> 00:26:05,130
It's not affected by this
modular operation.

457
00:26:05,130 --> 00:26:10,820
This would be minus r of x plus
this one, modular g of x,

458
00:26:10,820 --> 00:26:13,940
which is r of x.

459
00:26:13,940 --> 00:26:16,860
So the whole thing is 0.

460
00:26:16,860 --> 00:26:22,000
If this is 0, that means g of
x is a factor of F. Hence,

461
00:26:22,000 --> 00:26:23,930
it's a code word.

462
00:26:23,930 --> 00:26:25,650
So we have a code word here.

463
00:26:25,650 --> 00:26:32,150
And in the code word, pop up
our symbols right away, our

464
00:26:32,150 --> 00:26:33,960
encoded information symbols
right away.

465
00:26:33,960 --> 00:26:37,770
So we get some nice systematic
encoding going.

466
00:26:37,770 --> 00:26:40,500
This division circuit by
g is pretty much the

467
00:26:40,500 --> 00:26:41,790
same size as this.

468
00:26:41,790 --> 00:26:45,060
It's not larger at all.

469
00:26:45,060 --> 00:26:46,790
So there, we get beautiful
algorithms.

470
00:26:46,790 --> 00:26:48,736
This is actually what's
implemented.

471
00:26:48,736 --> 00:26:51,610
If we go to any disc drive
[UNINTELLIGIBLE], that is

472
00:26:51,610 --> 00:26:56,610
usually what is implemented
in there, exactly this.

473
00:26:56,610 --> 00:26:57,990
Algorithms.

474
00:26:57,990 --> 00:27:00,850
Algorithmic treatment of
Reed-Solomon codes.

475
00:27:00,850 --> 00:27:03,590
Do you have any questions
about any of this?

476
00:27:03,590 --> 00:27:04,015
Yeah.

477
00:27:04,015 --> 00:27:05,370
AUDIENCE: I have a question
about do any these

478
00:27:05,370 --> 00:27:09,555
Reed-Solomon codes
map [INAUDIBLE]?

479
00:27:09,555 --> 00:27:11,990
PROFESSOR: They are
very costly map.

480
00:27:11,990 --> 00:27:14,940
Usually, it depends a lot
on the application.

481
00:27:14,940 --> 00:27:17,180
If you think disc drives,
[UNINTELLIGIBLE] as just being

482
00:27:17,180 --> 00:27:21,330
mapped, you take Reed-Solomon
codes over a characteristic 2.

483
00:27:21,330 --> 00:27:22,760
Then each field element is

484
00:27:22,760 --> 00:27:25,840
represented as a binary vector.

485
00:27:25,840 --> 00:27:30,460
And that binary vector is mapped
into on-off keying.

486
00:27:30,460 --> 00:27:32,230
Straight off the bat.

487
00:27:32,230 --> 00:27:34,560
Nothing more fancy.

488
00:27:34,560 --> 00:27:40,090
That is for disc drives.

489
00:27:40,090 --> 00:27:42,710
And as you do this, the
satellite standard, where it's

490
00:27:42,710 --> 00:27:48,510
mapped onto the 256-QAM field
elements [UNINTELLIGIBLE].

491
00:27:48,510 --> 00:27:51,490
So it's many different ways.

492
00:27:51,490 --> 00:27:53,328
Many different ways.

493
00:27:53,328 --> 00:27:55,640
AUDIENCE: But to prove some
performance [UNINTELLIGIBLE]

494
00:27:55,640 --> 00:27:58,980
in the [UNINTELLIGIBLE], we need
to have mappings, right?

495
00:27:58,980 --> 00:28:01,030
PROFESSOR: In order to prove
performance mode, we need to

496
00:28:01,030 --> 00:28:02,110
have mappings.

497
00:28:02,110 --> 00:28:05,700
And the Hamming distance bounds
that we get from here

498
00:28:05,700 --> 00:28:09,060
give you bounds on the minimum
Euclidean distance.

499
00:28:09,060 --> 00:28:12,400
If these are good bounds or
not depends a lot on the

500
00:28:12,400 --> 00:28:14,150
modulation scheme.

501
00:28:14,150 --> 00:28:17,620
And to be perfectly honest,
they usually are not.

502
00:28:17,620 --> 00:28:21,850
They usually are not very
good, the bounds.

503
00:28:21,850 --> 00:28:26,350
But it's a very difficult
problem to design a code or to

504
00:28:26,350 --> 00:28:31,010
find a representation of the
fields that maps nicely onto a

505
00:28:31,010 --> 00:28:31,965
modulation scheme.

506
00:28:31,965 --> 00:28:34,725
Very difficult problem.

507
00:28:34,725 --> 00:28:37,210
AUDIENCE: How do we know
how to think that

508
00:28:37,210 --> 00:28:38,210
this is a good code?

509
00:28:38,210 --> 00:28:42,030
PROFESSOR: The code itself is
excellent in terms of MDS, the

510
00:28:42,030 --> 00:28:43,010
MDS property.

511
00:28:43,010 --> 00:28:45,070
AUDIENCE: But why does
MDS mean good codes?

512
00:28:45,070 --> 00:28:46,696
PROFESSOR: In respect
to modulation?

513
00:28:46,696 --> 00:28:47,580
AUDIENCE: Yes.

514
00:28:47,580 --> 00:28:49,490
PROFESSOR: It doesn't.

515
00:28:49,490 --> 00:28:52,374
It doesn't.

516
00:28:52,374 --> 00:28:55,390
It's a bit like this.

517
00:28:55,390 --> 00:28:59,080
It's really not easy to define
codes in Euclidean space.

518
00:28:59,080 --> 00:29:07,170
So all that we do is we find
ways to do that and guarantee

519
00:29:07,170 --> 00:29:12,120
some performance, some
sort of performance.

520
00:29:12,120 --> 00:29:15,400
It's not easy to spread out --

521
00:29:15,400 --> 00:29:15,910
I don't know --

522
00:29:15,910 --> 00:29:24,080
2 to the 1,000 points
in 1,500 dimensions.

523
00:29:24,080 --> 00:29:25,380
These would be typical
numbers really.

524
00:29:25,380 --> 00:29:29,090

525
00:29:29,090 --> 00:29:31,240
It's not easy.

526
00:29:31,240 --> 00:29:35,350
And since that problem is
practically daunting, it's a

527
00:29:35,350 --> 00:29:39,530
daunting task, you have to
develop all sort of crutches

528
00:29:39,530 --> 00:29:40,210
to do that.

529
00:29:40,210 --> 00:29:42,290
And this is really one.

530
00:29:42,290 --> 00:29:46,620
So how to code MDS
codes playing a

531
00:29:46,620 --> 00:29:48,120
part in this mapping.

532
00:29:48,120 --> 00:29:52,230
If you want to be more fancy
about that, then you put a

533
00:29:52,230 --> 00:29:55,440
convolutional code or some other
code also in there and

534
00:29:55,440 --> 00:29:56,690
do a combine scheme.

535
00:29:56,690 --> 00:29:59,670

536
00:29:59,670 --> 00:30:02,910
I think Professor Forney will
talk about that more.

537
00:30:02,910 --> 00:30:05,060
So here, it's just the
coding theoretic

538
00:30:05,060 --> 00:30:07,550
groundwork of these things.

539
00:30:07,550 --> 00:30:10,610

540
00:30:10,610 --> 00:30:11,090
Anything else?

541
00:30:11,090 --> 00:30:11,565
Yeah.

542
00:30:11,565 --> 00:30:12,900
AUDIENCE: [INAUDIBLE]

543
00:30:12,900 --> 00:30:15,390
of the [INAUDIBLE] n minus 1.

544
00:30:15,390 --> 00:30:17,507
Close, very close [INAUDIBLE].

545
00:30:17,507 --> 00:30:18,757
PROFESSOR: Yeah, thanks.

546
00:30:18,757 --> 00:30:24,050

547
00:30:24,050 --> 00:30:28,780
So the algorithmic treatment
of Reed-Solomon codes is

548
00:30:28,780 --> 00:30:29,980
extremely elegant.

549
00:30:29,980 --> 00:30:34,675
And that's the second main
reason they are so much used.

550
00:30:34,675 --> 00:30:37,990
It doesn't cost so much
to implement them.

551
00:30:37,990 --> 00:30:40,210
Well, at least we've seen
that for the encoder.

552
00:30:40,210 --> 00:30:42,130
That's a fairly small circuit.

553
00:30:42,130 --> 00:30:43,380
So what about decoding?

554
00:30:43,380 --> 00:30:48,950

555
00:30:48,950 --> 00:30:51,650
Decoding.

556
00:30:51,650 --> 00:30:53,350
How do we decode these things?

557
00:30:53,350 --> 00:30:57,990

558
00:30:57,990 --> 00:31:00,400
How could we possibly
decode them?

559
00:31:00,400 --> 00:31:02,390
And I give you --

560
00:31:02,390 --> 00:31:04,840
AUDIENCE: Fourier?

561
00:31:04,840 --> 00:31:05,660
PROFESSOR: Right, that's true.

562
00:31:05,660 --> 00:31:06,930
We could do the Fourier
transform.

563
00:31:06,930 --> 00:31:13,026
But it doesn't help us so much
because we receive something.

564
00:31:13,026 --> 00:31:16,540
And we receive a
vector, say, y.

565
00:31:16,540 --> 00:31:20,962

566
00:31:20,962 --> 00:31:23,323
From now on, let's say
x is a code word.

567
00:31:23,323 --> 00:31:27,760

568
00:31:27,760 --> 00:31:28,750
rs, right.

569
00:31:28,750 --> 00:31:32,590
So x, it's usually a code
word from now on.

570
00:31:32,590 --> 00:31:37,190
So this is a code word
plus an error.

571
00:31:37,190 --> 00:31:39,740
So in particular, if we take the
Fourier transform, we take

572
00:31:39,740 --> 00:31:42,110
the Fourier transform of the
code word, which is fine.

573
00:31:42,110 --> 00:31:43,590
But then we get the Fourier
transform of the error.

574
00:31:43,590 --> 00:31:46,780
So that destroys all the fun.

575
00:31:46,780 --> 00:31:49,370

576
00:31:49,370 --> 00:31:50,110
What else could we do?

577
00:31:50,110 --> 00:31:54,250
Here's typical parameters
of a code.

578
00:31:54,250 --> 00:32:01,740
255, 239, 256.

579
00:32:01,740 --> 00:32:04,100
And you immediately see
that, OK, any sort of

580
00:32:04,100 --> 00:32:05,350
group force is out.

581
00:32:05,350 --> 00:32:08,820

582
00:32:08,820 --> 00:32:10,490
How many code words
do we have here?

583
00:32:10,490 --> 00:32:13,622
We have 8 to the
239 code words.

584
00:32:13,622 --> 00:32:16,042
Now you don't want
to search that.

585
00:32:16,042 --> 00:32:18,386
You definitely don't want
to search that.

586
00:32:18,386 --> 00:32:22,690

587
00:32:22,690 --> 00:32:25,536
So how could we possibly
decode these things?

588
00:32:25,536 --> 00:32:28,790

589
00:32:28,790 --> 00:32:32,070
Turns out, to decode them in
some sort of optimal fashion,

590
00:32:32,070 --> 00:32:33,160
maximum likelihood [INAUDIBLE]

591
00:32:33,160 --> 00:32:37,220
actually, it's an
NP-hard problem.

592
00:32:37,220 --> 00:32:41,140
Maybe last year, actually, it
has been shown that it's an

593
00:32:41,140 --> 00:32:44,190
NP-hard problem to decode
Reed-Solomon codes.

594
00:32:44,190 --> 00:32:47,110
It was known that decoding
in general was NP-hard.

595
00:32:47,110 --> 00:32:51,930
But this is now the constraint
to Reed-Solomon

596
00:32:51,930 --> 00:32:55,200
codes is still hard.

597
00:32:55,200 --> 00:32:56,940
So what do we do?

598
00:32:56,940 --> 00:32:59,640
Yes, OK, what do we do?

599
00:32:59,640 --> 00:33:01,800
Let's say x is a code word.

600
00:33:01,800 --> 00:33:05,170
We know that.

601
00:33:05,170 --> 00:33:09,560
And set rate e, let's
just call it t.

602
00:33:09,560 --> 00:33:16,680

603
00:33:16,680 --> 00:33:23,390
So what happens if you
don't have an error?

604
00:33:23,390 --> 00:33:24,640
Just thought experiment.

605
00:33:24,640 --> 00:33:28,630

606
00:33:28,630 --> 00:33:34,520
Thought experiment, if you don't
have an error, then yi

607
00:33:34,520 --> 00:33:46,640
in all the positions is
equal to F of xi for

608
00:33:46,640 --> 00:33:49,500
some F of x of degree.

609
00:33:49,500 --> 00:33:59,000

610
00:33:59,000 --> 00:34:02,520
In particular, since we
know the x's, we know

611
00:34:02,520 --> 00:34:03,770
the positions --

612
00:34:03,770 --> 00:34:09,440

613
00:34:09,440 --> 00:34:14,600
sorry, oh, sorry.

614
00:34:14,600 --> 00:34:17,050
That's not what I
wanted to write.

615
00:34:17,050 --> 00:34:18,864
This is definitely not what
I wanted to write.

616
00:34:18,864 --> 00:34:21,820

617
00:34:21,820 --> 00:34:38,870
Let's keep that as c as a code
word and position i in c is

618
00:34:38,870 --> 00:34:49,679
associated with xi
in the fields.

619
00:34:49,679 --> 00:34:57,340
So meaning ci would
be F of xi.

620
00:34:57,340 --> 00:34:59,310
That's really what I
wanted to write.

621
00:34:59,310 --> 00:35:01,810
It makes more sense.

622
00:35:01,810 --> 00:35:03,710
So thought experiment.

623
00:35:03,710 --> 00:35:04,960
No errors.

624
00:35:04,960 --> 00:35:07,080

625
00:35:07,080 --> 00:35:16,170
Then yi is F of xi for some F.
If they ran no errors, then we

626
00:35:16,170 --> 00:35:21,900
could just solve this linear
system of equations to find

627
00:35:21,900 --> 00:35:26,360
the coefficient of F. And the
coefficient of F, say, were

628
00:35:26,360 --> 00:35:28,286
our information circuits.

629
00:35:28,286 --> 00:35:32,100
Is it clear that this is a
linear system of equations?

630
00:35:32,100 --> 00:35:34,380
Yeah?

631
00:35:34,380 --> 00:35:40,680
You could write it out as
y0, y1, y2 equal to --

632
00:35:40,680 --> 00:35:56,490

633
00:35:56,490 --> 00:36:01,260
and here we have f0,
f1, up to fk-1.

634
00:36:01,260 --> 00:36:03,110
This is the linear system
of equations.

635
00:36:03,110 --> 00:36:04,510
We know the xi's.

636
00:36:04,510 --> 00:36:05,960
This is a linear system of
equation we have to solve.

637
00:36:05,960 --> 00:36:11,170

638
00:36:11,170 --> 00:36:13,560
If there are no errors,
then life is easy.

639
00:36:13,560 --> 00:36:15,360
That seems to be reasonable.

640
00:36:15,360 --> 00:36:17,820
So what happens if we
do have errors?

641
00:36:17,820 --> 00:36:23,810
Somehow, we have to make sure
that the errors that we get do

642
00:36:23,810 --> 00:36:27,590
not cause any problem for us.

643
00:36:27,590 --> 00:36:33,950
And then we do something
very ingenious.

644
00:36:33,950 --> 00:36:37,825
We define something called an
error locator which is a

645
00:36:37,825 --> 00:36:55,470
polynomial x such
that x minus xi.

646
00:36:55,470 --> 00:37:01,400
So it's a polynomial which is
0 in all error positions.

647
00:37:01,400 --> 00:37:04,700

648
00:37:04,700 --> 00:37:07,270
Well, you might say, we do not
know the error positions.

649
00:37:07,270 --> 00:37:09,750
Well, OK, that's true.

650
00:37:09,750 --> 00:37:12,480
Basically, this is, in the end,
what we want to find,

651
00:37:12,480 --> 00:37:13,150
this polynomial.

652
00:37:13,150 --> 00:37:14,835
But nonetheless, this
polynomial exists.

653
00:37:14,835 --> 00:37:18,080

654
00:37:18,080 --> 00:37:25,990
We can cast, actually,
the coding problem --

655
00:37:25,990 --> 00:37:29,170
this is form 1 s.

656
00:37:29,170 --> 00:37:32,695

657
00:37:32,695 --> 00:37:35,032
Yes, what?

658
00:37:35,032 --> 00:37:36,282
AUDIENCE: [INAUDIBLE PHRASE].

659
00:37:36,282 --> 00:37:42,130

660
00:37:42,130 --> 00:37:43,480
PROFESSOR: Yeah, it's an
additive error model.

661
00:37:43,480 --> 00:37:46,510

662
00:37:46,510 --> 00:37:48,330
But you can cast pretty
much anything in the

663
00:37:48,330 --> 00:37:49,140
[UNINTELLIGIBLE].

664
00:37:49,140 --> 00:37:52,440
If a position is altered, you
can always model that as if

665
00:37:52,440 --> 00:37:53,754
something was added to it.

666
00:37:53,754 --> 00:37:56,480

667
00:37:56,480 --> 00:38:09,670
Decoding problem one is find
lambda of x of minimal degree

668
00:38:09,670 --> 00:38:30,800
such that lambda of xi,
is 0 for all xi and

669
00:38:30,800 --> 00:38:35,230
degree f less than k.

670
00:38:35,230 --> 00:38:41,750
So I claim if you solve this
problem, namely, this is a

671
00:38:41,750 --> 00:38:44,570
problem I give you.

672
00:38:44,570 --> 00:38:47,000
I give you vector y.

673
00:38:47,000 --> 00:38:48,335
I give you vector y.

674
00:38:48,335 --> 00:38:48,890
Here it is.

675
00:38:48,890 --> 00:38:50,380
Here is vector y.

676
00:38:50,380 --> 00:38:53,500
And I give you vector x which
corresponds to the field

677
00:38:53,500 --> 00:38:56,310
elements where you evaluated
that in order to

678
00:38:56,310 --> 00:38:57,540
get the code word.

679
00:38:57,540 --> 00:39:02,760
And then I said, given y and x,
find two polynomials lambda

680
00:39:02,760 --> 00:39:09,180
and f such that f has maximum
degree k and lambda has

681
00:39:09,180 --> 00:39:12,730
minimum degree, the smaller
degree possible so

682
00:39:12,730 --> 00:39:15,360
that this is true.

683
00:39:15,360 --> 00:39:19,140
And I claim this solves
the decoding problem.

684
00:39:19,140 --> 00:39:22,340
This would solve the decoding
problem because once we have

685
00:39:22,340 --> 00:39:24,910
found this, then we
can take lambda to

686
00:39:24,910 --> 00:39:27,140
be the error locator.

687
00:39:27,140 --> 00:39:32,480
And we can basically read
off the information

688
00:39:32,480 --> 00:39:35,180
symbols from the f.

689
00:39:35,180 --> 00:39:38,810
So this decoding formulation now
brings it, at least, into

690
00:39:38,810 --> 00:39:42,780
the algebraic ground, brings
the whole decoding problem,

691
00:39:42,780 --> 00:39:45,072
makes it something
algebraically.

692
00:39:45,072 --> 00:39:49,220
But now the question becomes,
is that easy?

693
00:39:49,220 --> 00:39:50,890
Or can we do this?

694
00:39:50,890 --> 00:39:52,140
This problem here.

695
00:39:52,140 --> 00:39:54,440

696
00:39:54,440 --> 00:39:56,670
Do you see any hope for
solving this problem?

697
00:39:56,670 --> 00:40:02,270

698
00:40:02,270 --> 00:40:05,290
I guess the only
answer that --

699
00:40:05,290 --> 00:40:06,660
OK, anybody says no?

700
00:40:06,660 --> 00:40:10,072
Anybody does not see any hope?

701
00:40:10,072 --> 00:40:10,950
All right.

702
00:40:10,950 --> 00:40:11,750
This is great.

703
00:40:11,750 --> 00:40:14,940
You all see hope here.

704
00:40:14,940 --> 00:40:18,380
You all see hope here, which
seems to make you an

705
00:40:18,380 --> 00:40:20,166
opportunistic bunch.

706
00:40:20,166 --> 00:40:21,360
Not opportunistic.

707
00:40:21,360 --> 00:40:22,350
What's the word?

708
00:40:22,350 --> 00:40:22,930
Optimistic.

709
00:40:22,930 --> 00:40:24,180
Optimistic bunch.

710
00:40:24,180 --> 00:40:26,470

711
00:40:26,470 --> 00:40:27,270
Let's put it like this.

712
00:40:27,270 --> 00:40:29,333
What is the problem
in solving this?

713
00:40:29,333 --> 00:40:31,991

714
00:40:31,991 --> 00:40:34,270
It's not linear.

715
00:40:34,270 --> 00:40:35,890
You get the coefficients
of lambda.

716
00:40:35,890 --> 00:40:38,390
Multiply the coefficients
of f.

717
00:40:38,390 --> 00:40:44,900
That whole thing becomes a
nonlinear problem, where we

718
00:40:44,900 --> 00:40:51,490
say in the end, find the
solution to a set of

719
00:40:51,490 --> 00:40:57,400
polynomial equations in a field,
which is a multivariate

720
00:40:57,400 --> 00:41:00,390
polynomial equations, where the
coefficients of lambda and

721
00:41:00,390 --> 00:41:02,680
f are the variables.

722
00:41:02,680 --> 00:41:03,540
You can do that.

723
00:41:03,540 --> 00:41:06,400
You could use techniques like
Grobner basis or so, and you

724
00:41:06,400 --> 00:41:07,720
could do that.

725
00:41:07,720 --> 00:41:09,020
But this is very difficult.

726
00:41:09,020 --> 00:41:11,805
This is computationally
tedious.

727
00:41:11,805 --> 00:41:15,710

728
00:41:15,710 --> 00:41:18,930
So is that clear why this is
nonlinear, and why this is

729
00:41:18,930 --> 00:41:20,780
hard to solve a nonlinear
problem here?

730
00:41:20,780 --> 00:41:24,740

731
00:41:24,740 --> 00:41:27,830
If not, then you have to say
something now, or forever hold

732
00:41:27,830 --> 00:41:29,080
your peace.

733
00:41:29,080 --> 00:41:36,880

734
00:41:36,880 --> 00:41:38,350
So what do we do with
hard problems?

735
00:41:38,350 --> 00:41:41,820

736
00:41:41,820 --> 00:41:44,920
Once you take the optimization
classes, there's almost like a

737
00:41:44,920 --> 00:41:47,320
reflex, there is a relax time.

738
00:41:47,320 --> 00:41:49,870
We find the proper relaxation
of the problem.

739
00:41:49,870 --> 00:41:53,450
Now the proper relaxation of
this problem is the following.

740
00:41:53,450 --> 00:42:00,690

741
00:42:00,690 --> 00:42:03,150
Decoding problem two.

742
00:42:03,150 --> 00:42:17,865
Find lambda of x of minimal
degree such that --

743
00:42:17,865 --> 00:42:21,760
it's almost the same,
almost the same --

744
00:42:21,760 --> 00:42:39,460
lambda fi yi minus h of xi is
0, where the degree of h is

745
00:42:39,460 --> 00:42:48,820
less than k plus
degree lambda.

746
00:42:48,820 --> 00:42:52,370
So all that we did from this
formulation, which would give

747
00:42:52,370 --> 00:42:55,560
us a clean solution to the whole
thing, right now, we

748
00:42:55,560 --> 00:43:00,350
multiply in this lambda which
gives here, it keeps the

749
00:43:00,350 --> 00:43:02,060
lambda times y.

750
00:43:02,060 --> 00:43:05,370
And here, we get a new
polynomial, lambda times f,

751
00:43:05,370 --> 00:43:11,800
which now has degree at most
k plus degree lambda.

752
00:43:11,800 --> 00:43:15,760
And then we say, let's instead
solve this problem.

753
00:43:15,760 --> 00:43:18,130
Let's solve this problem.

754
00:43:18,130 --> 00:43:32,800
In particular, the question now
becomes well, we do not

755
00:43:32,800 --> 00:43:35,000
require this anymore.

756
00:43:35,000 --> 00:43:39,870
In this relaxed formulation,
we do not require this.

757
00:43:39,870 --> 00:43:41,800
And that makes all
the difference.

758
00:43:41,800 --> 00:43:45,836
It makes a world of difference
because this one --

759
00:43:45,836 --> 00:43:49,470
look at it -- it's
a linear problem.

760
00:43:49,470 --> 00:43:50,760
It's a linear program.

761
00:43:50,760 --> 00:43:51,880
Why is it a linear problem?

762
00:43:51,880 --> 00:43:53,375
Do you see it's a
linear problem?

763
00:43:53,375 --> 00:43:56,020

764
00:43:56,020 --> 00:44:00,180
Could you write down the
equation, the matrix equation?

765
00:44:00,180 --> 00:44:01,430
It's pretty straight, right?

766
00:44:01,430 --> 00:44:04,690

767
00:44:04,690 --> 00:44:05,730
It's pretty straight.

768
00:44:05,730 --> 00:44:09,340
You could, for example,
write it like, here, a

769
00:44:09,340 --> 00:44:14,285
diagonal matrix yn.

770
00:44:14,285 --> 00:44:16,790

771
00:44:16,790 --> 00:44:18,280
Here, you would get something.

772
00:44:18,280 --> 00:44:26,688

773
00:44:26,688 --> 00:44:28,590
I think that seems
to be all right.

774
00:44:28,590 --> 00:44:35,710

775
00:44:35,710 --> 00:44:39,070
And here, just the evaluation
of the h.

776
00:44:39,070 --> 00:45:00,330
So up to hk plus
degree lambda.

777
00:45:00,330 --> 00:45:03,070
That's a linear system
of equations.

778
00:45:03,070 --> 00:45:04,330
We can certainly solve this.

779
00:45:04,330 --> 00:45:08,340
Well, we do not know really
what the lambda is, what

780
00:45:08,340 --> 00:45:10,180
degree the lambda has.

781
00:45:10,180 --> 00:45:12,720
But we're just hypothesizing on
all the possible degrees.

782
00:45:12,720 --> 00:45:15,920

783
00:45:15,920 --> 00:45:21,915
Well, we could say, OK, let's
assume the degree lambda is 0.

784
00:45:21,915 --> 00:45:24,740
It's a constant, which would
be the same as saying there

785
00:45:24,740 --> 00:45:27,520
are no errors.

786
00:45:27,520 --> 00:45:29,120
Then we can look at the
system of equations.

787
00:45:29,120 --> 00:45:30,120
Does it have a solution?

788
00:45:30,120 --> 00:45:31,380
Well, yes, no.

789
00:45:31,380 --> 00:45:34,300
If no, then we say, all right,
let's assume it's 1.

790
00:45:34,300 --> 00:45:35,370
Well, does it have a solution?

791
00:45:35,370 --> 00:45:36,250
Yes, no.

792
00:45:36,250 --> 00:45:36,860
And so on.

793
00:45:36,860 --> 00:45:38,110
Then we can move on.

794
00:45:38,110 --> 00:45:41,480

795
00:45:41,480 --> 00:45:43,210
So we can solve this
relaxed problem.

796
00:45:43,210 --> 00:45:46,610

797
00:45:46,610 --> 00:45:48,580
Does that help us?

798
00:45:48,580 --> 00:45:50,500
It's nice to solve a
relaxed problem.

799
00:45:50,500 --> 00:45:52,540
And in the end, we get two
vectors out of it, two

800
00:45:52,540 --> 00:45:57,620
polynomials, lambda and h.

801
00:45:57,620 --> 00:45:58,870
Does it really help us?

802
00:45:58,870 --> 00:46:02,290

803
00:46:02,290 --> 00:46:06,635
Well, yes.

804
00:46:06,635 --> 00:46:08,390
Why?

805
00:46:08,390 --> 00:46:09,240
Because --

806
00:46:09,240 --> 00:46:10,490
let's put it like this.

807
00:46:10,490 --> 00:46:12,930

808
00:46:12,930 --> 00:46:16,960
We could easily check
if this is true.

809
00:46:16,960 --> 00:46:20,860
Once we have our h, we can
easily check if this is true.

810
00:46:20,860 --> 00:46:25,760
And if it is true, then we
have solved this problem.

811
00:46:25,760 --> 00:46:28,430
If it is true, we have solved
this problem, which is the

812
00:46:28,430 --> 00:46:31,350
problem we wanted to solve.

813
00:46:31,350 --> 00:46:32,600
Good.

814
00:46:32,600 --> 00:46:40,170

815
00:46:40,170 --> 00:46:41,870
So is that all we need
to know about this?

816
00:46:41,870 --> 00:46:50,390

817
00:46:50,390 --> 00:46:51,950
We want to give guarantees.

818
00:46:51,950 --> 00:46:55,380
We want to give guarantees that
we correct up to so many

819
00:46:55,380 --> 00:46:56,991
errors, t errors, right?

820
00:46:56,991 --> 00:46:59,580

821
00:46:59,580 --> 00:47:03,390
So we have to guarantee that if
there are not more than t

822
00:47:03,390 --> 00:47:08,600
errors, whatever t will turn
out to be, we can guarantee

823
00:47:08,600 --> 00:47:12,460
that A, we will find
a solution, and

824
00:47:12,460 --> 00:47:15,570
B, this will hold.

825
00:47:15,570 --> 00:47:17,815
So two things to prove.

826
00:47:17,815 --> 00:47:18,880
Is that clear?

827
00:47:18,880 --> 00:47:21,360
That we have to prove
those two things?

828
00:47:21,360 --> 00:47:24,020
So the first one first.

829
00:47:24,020 --> 00:47:27,430

830
00:47:27,430 --> 00:47:34,970
When do we find a solution?

831
00:47:34,970 --> 00:47:36,465
And are we guaranteed
to find it?

832
00:47:36,465 --> 00:47:41,200

833
00:47:41,200 --> 00:47:50,280
Can we guarantee the existence
of a solution?

834
00:47:50,280 --> 00:47:55,400

835
00:47:55,400 --> 00:47:58,050
Well, when can we do that?

836
00:47:58,050 --> 00:48:00,390
Let's look at this.

837
00:48:00,390 --> 00:48:02,240
These are n constraints.

838
00:48:02,240 --> 00:48:05,390

839
00:48:05,390 --> 00:48:09,350
This is a system of linear
equations with n constraints.

840
00:48:09,350 --> 00:48:17,420
If the total number of degrees
of freedom exceeds n, then we

841
00:48:17,420 --> 00:48:19,790
are left with something
non-trivial after we solve the

842
00:48:19,790 --> 00:48:21,060
system of equations.

843
00:48:21,060 --> 00:48:23,880
So what's the total number
of degrees of freedom?

844
00:48:23,880 --> 00:48:26,760

845
00:48:26,760 --> 00:48:28,100
The number of degrees
of freedom --

846
00:48:28,100 --> 00:48:33,100

847
00:48:33,100 --> 00:48:39,920
so we get the lambda as a degree
of freedom, so which is

848
00:48:39,920 --> 00:48:44,030
degree lambda plus 1.

849
00:48:44,030 --> 00:48:46,720
And the other one is plus --

850
00:48:46,720 --> 00:48:49,510

851
00:48:49,510 --> 00:48:51,910
what is this one --

852
00:48:51,910 --> 00:48:58,930
plus k plus degree lambda.

853
00:48:58,930 --> 00:49:04,140
This is the total number of
degrees of freedom here.

854
00:49:04,140 --> 00:49:08,550
And the reason is that this
one should be minus 1.

855
00:49:08,550 --> 00:49:09,800
Sorry.

856
00:49:09,800 --> 00:49:11,400

857
00:49:11,400 --> 00:49:13,320
So this is total number
of degrees of freedom.

858
00:49:13,320 --> 00:49:18,505

859
00:49:18,505 --> 00:49:21,580
If this is greater than n,
then we can guarantee the

860
00:49:21,580 --> 00:49:23,445
existence of a solution,
a nontrivial solution.

861
00:49:23,445 --> 00:49:26,690
Then this thing will
have a solution.

862
00:49:26,690 --> 00:49:28,620
It's a homogeneous system
of equations.

863
00:49:28,620 --> 00:49:30,110
So the 0 is always a solution.

864
00:49:30,110 --> 00:49:33,200
But that's not much
good to us.

865
00:49:33,200 --> 00:49:35,458
So what do we get here?

866
00:49:35,458 --> 00:49:37,930
Degree lambda.

867
00:49:37,930 --> 00:49:44,580
To a degree lambda greater
than n minus k plus minus

868
00:49:44,580 --> 00:49:49,130
1 or n minus k.

869
00:49:49,130 --> 00:49:52,470

870
00:49:52,470 --> 00:49:58,770
So the degree lambda greater
than n minus k over 2 -- does

871
00:49:58,770 --> 00:50:00,100
that remind you of
anything here?

872
00:50:00,100 --> 00:50:04,770

873
00:50:04,770 --> 00:50:14,950
So this one is d
minus 1 over 2.

874
00:50:14,950 --> 00:50:16,700
So very interesting, right?

875
00:50:16,700 --> 00:50:20,460
Once upon a time, you learned
that if you make less than d/2

876
00:50:20,460 --> 00:50:23,760
errors, you can correct that.

877
00:50:23,760 --> 00:50:24,040
Very nice.

878
00:50:24,040 --> 00:50:26,780
It pops up here.

879
00:50:26,780 --> 00:50:29,520
It pops up here out
of the blue.

880
00:50:29,520 --> 00:50:32,260
The reason that it pops up here
is, of course, the same

881
00:50:32,260 --> 00:50:36,730
statement, that as long as we
stay within d/2 errors, we are

882
00:50:36,730 --> 00:50:38,580
guaranteed to be able
to decode this.

883
00:50:38,580 --> 00:50:41,200

884
00:50:41,200 --> 00:50:42,030
So this is one.

885
00:50:42,030 --> 00:50:45,630
So we know this one was
the number of errors.

886
00:50:45,630 --> 00:50:48,540
If t is greater or equal
than this, then --

887
00:50:48,540 --> 00:50:58,010

888
00:50:58,010 --> 00:51:01,220
let's forget about the t.

889
00:51:01,220 --> 00:51:03,810
If you proceed in this algorithm
hypothesizing the

890
00:51:03,810 --> 00:51:09,100
degrees of lambda, once we've
reached this number in the

891
00:51:09,100 --> 00:51:11,150
degree, there will
be a solution.

892
00:51:11,150 --> 00:51:12,650
And we don't have to go
further than that.

893
00:51:12,650 --> 00:51:16,380

894
00:51:16,380 --> 00:51:18,190
So that's the first one.

895
00:51:18,190 --> 00:51:21,880
So the second thing we have
to prove is that --

896
00:51:21,880 --> 00:51:23,130
I shouldn't have done this --

897
00:51:23,130 --> 00:51:29,190

898
00:51:29,190 --> 00:51:30,320
that for some t --

899
00:51:30,320 --> 00:51:30,784
Yeah?

900
00:51:30,784 --> 00:51:33,104
AUDIENCE: [INAUDIBLE]

901
00:51:33,104 --> 00:51:36,360
standard degree of freedom
or less constraints?

902
00:51:36,360 --> 00:51:38,310
PROFESSOR: You want to
guarantee a solution.

903
00:51:38,310 --> 00:51:41,750
If you have more constraints
than degrees of freedom, then,

904
00:51:41,750 --> 00:51:44,670
since it's homogeneous, you
usually would be stuck with a

905
00:51:44,670 --> 00:51:45,490
zero solution.

906
00:51:45,490 --> 00:51:49,520
Everything's 0, which
is no good to us.

907
00:51:49,520 --> 00:51:52,510
It solves this problem, but
it doesn't give us any

908
00:51:52,510 --> 00:51:55,305
information.

909
00:51:55,305 --> 00:51:56,622
Is that all right?

910
00:51:56,622 --> 00:52:00,066

911
00:52:00,066 --> 00:52:02,772
AUDIENCE: Why does it have to be
the condition that degrees

912
00:52:02,772 --> 00:52:06,970
of freedom has to be greater
than the constraints?

913
00:52:06,970 --> 00:52:09,400
PROFESSOR: No, no, the
degrees of freedom --

914
00:52:09,400 --> 00:52:13,460
well, OK, it's true.

915
00:52:13,460 --> 00:52:16,580
We could get lucky.

916
00:52:16,580 --> 00:52:20,030
We could have redundancy in
this system of equations.

917
00:52:20,030 --> 00:52:24,780
And if we get lucky, that's
just for the better.

918
00:52:24,780 --> 00:52:29,260
And actually, you can show that
you do get lucky if very

919
00:52:29,260 --> 00:52:31,250
few errors happen.

920
00:52:31,250 --> 00:52:34,260
Then this would have low rank.

921
00:52:34,260 --> 00:52:35,370
You can show that.

922
00:52:35,370 --> 00:52:39,430
But short of knowing much,
we want to guarantee --

923
00:52:39,430 --> 00:52:42,380
I just want, at this point in
time, to guarantee that there

924
00:52:42,380 --> 00:52:44,370
is a solution.

925
00:52:44,370 --> 00:52:47,590
There is a non-zero solution to
this system of equations,

926
00:52:47,590 --> 00:52:50,710
and the degree of lambda
is not more than d

927
00:52:50,710 --> 00:52:53,460
minus 1 over 2.

928
00:52:53,460 --> 00:52:56,690
There is a solution with a
degree of lambda being upper

929
00:52:56,690 --> 00:52:58,324
bounded by this.

930
00:52:58,324 --> 00:52:59,800
AUDIENCE: So [INAUDIBLE]

931
00:52:59,800 --> 00:53:01,280
less constraints?

932
00:53:01,280 --> 00:53:02,530
PROFESSOR: Yeah, no, no.

933
00:53:02,530 --> 00:53:06,550

934
00:53:06,550 --> 00:53:08,660
Once this is satisfied,
I guarantee

935
00:53:08,660 --> 00:53:10,260
you there is a solution.

936
00:53:10,260 --> 00:53:14,420
That means, the smallest
solution is guaranteed not to

937
00:53:14,420 --> 00:53:15,670
be larger than that.

938
00:53:15,670 --> 00:53:19,090

939
00:53:19,090 --> 00:53:20,150
But there are, of course, many,

940
00:53:20,150 --> 00:53:21,570
many more larger solutions.

941
00:53:21,570 --> 00:53:25,723
There are many solutions of
larger degree here, which we

942
00:53:25,723 --> 00:53:27,550
are not interested in since
we are interested

943
00:53:27,550 --> 00:53:30,370
in the minimal degree.

944
00:53:30,370 --> 00:53:32,750
So this is an upper bound on
the minimal degree lambda.

945
00:53:32,750 --> 00:53:37,200

946
00:53:37,200 --> 00:53:38,300
So now the other one.

947
00:53:38,300 --> 00:53:46,630
So now we want to make the
statement about this one here.

948
00:53:46,630 --> 00:53:52,990
When can we guarantee that our
relaxation didn't matter?

949
00:53:52,990 --> 00:53:56,930
Despite our relaxation, our
solution that we find that in

950
00:53:56,930 --> 00:54:00,110
the solution that we find
lambda divides h.

951
00:54:00,110 --> 00:54:03,430
How can we guarantee this?

952
00:54:03,430 --> 00:54:04,860
So how can we guarantee this?

953
00:54:04,860 --> 00:54:06,110
How can we guarantee this?

954
00:54:06,110 --> 00:54:10,080

955
00:54:10,080 --> 00:54:20,310
Let's look at lambda xi
yi minus h of xi.

956
00:54:20,310 --> 00:54:24,610
And we know this is
0 for all xi.

957
00:54:24,610 --> 00:54:25,860
We know that.

958
00:54:25,860 --> 00:54:29,210

959
00:54:29,210 --> 00:54:38,780
We know that this guy here can
actually be written as ci plus

960
00:54:38,780 --> 00:54:43,630
ei minus h of xi.

961
00:54:43,630 --> 00:54:47,690

962
00:54:47,690 --> 00:54:50,040
This is just expanding
this guy.

963
00:54:50,040 --> 00:55:00,790
We also know that we can write
lambda xi times ci alone minus

964
00:55:00,790 --> 00:55:08,051
f of xi lambda xi.

965
00:55:08,051 --> 00:55:08,520
This is 0.

966
00:55:08,520 --> 00:55:10,932
We know that this is true too.

967
00:55:10,932 --> 00:55:12,780
AUDIENCE: For some f.

968
00:55:12,780 --> 00:55:13,320
PROFESSOR: For some f.

969
00:55:13,320 --> 00:55:17,220
The text is to f, so that
this is true too.

970
00:55:17,220 --> 00:55:22,500
Then let's just subtract
these two guys.

971
00:55:22,500 --> 00:55:25,480
Let's just subtract these
two things here.

972
00:55:25,480 --> 00:55:36,460
And then we know that lambda
xi times ei --

973
00:55:36,460 --> 00:55:38,250
so the first two cancel --

974
00:55:38,250 --> 00:55:51,646
minus h of xi minus So we
know this is true too.

975
00:55:51,646 --> 00:55:53,550
AUDIENCE: [INAUDIBLE].

976
00:55:53,550 --> 00:55:56,210
PROFESSOR: Yeah, sorry.

977
00:55:56,210 --> 00:55:57,460
Just in time.

978
00:55:57,460 --> 00:56:01,220

979
00:56:01,220 --> 00:56:02,480
So what can we learn
from this?

980
00:56:02,480 --> 00:56:05,510
So what is the degree of this?

981
00:56:05,510 --> 00:56:07,780
What is the degree of this?

982
00:56:07,780 --> 00:56:09,570
Well, this guy here --

983
00:56:09,570 --> 00:56:10,820
we'll write it somewhere
else --

984
00:56:10,820 --> 00:56:37,550

985
00:56:37,550 --> 00:56:47,320
well, this guy had degree h was
less than n minus k plus

986
00:56:47,320 --> 00:56:57,310
degree lambda less than
k plus degree lambda.

987
00:56:57,310 --> 00:57:00,760
That's because we set up
that problem that way.

988
00:57:00,760 --> 00:57:10,740
And we know that this
guy degree lambda.

989
00:57:10,740 --> 00:57:13,780

990
00:57:13,780 --> 00:57:15,740
We know that.

991
00:57:15,740 --> 00:57:28,390
So this whole thing, let's call
it S. We know it's 0 for

992
00:57:28,390 --> 00:57:35,360
degree S less than
degree lambda.

993
00:57:35,360 --> 00:57:39,080

994
00:57:39,080 --> 00:57:41,730
So why does that help us?

995
00:57:41,730 --> 00:57:44,740
Well, let's look
at the vector.

996
00:57:44,740 --> 00:57:48,060
Now let's look at all
the positions.

997
00:57:48,060 --> 00:57:53,380
Let's look at the vector where
we had, in the vector, we have

998
00:57:53,380 --> 00:57:56,770
lambda xi ei.

999
00:57:56,770 --> 00:58:02,620

1000
00:58:02,620 --> 00:58:05,480
And now the fundamental
question.

1001
00:58:05,480 --> 00:58:09,450
What is the rate
of this vector?

1002
00:58:09,450 --> 00:58:10,700
At most?

1003
00:58:10,700 --> 00:58:13,400

1004
00:58:13,400 --> 00:58:15,147
What's the rate of
this guy at most?

1005
00:58:15,147 --> 00:58:18,883

1006
00:58:18,883 --> 00:58:20,133
It's 12 seconds,
[UNINTELLIGIBLE]?

1007
00:58:20,133 --> 00:58:25,740

1008
00:58:25,740 --> 00:58:28,860
Well, the rate of
this vector --

1009
00:58:28,860 --> 00:58:37,030

1010
00:58:37,030 --> 00:58:40,410
it's definitely not more than
the rate of the error.

1011
00:58:40,410 --> 00:58:44,260
Because every time the error
is 0, the rate drops out.

1012
00:58:44,260 --> 00:58:45,510
That's at most t.

1013
00:58:45,510 --> 00:58:48,890

1014
00:58:48,890 --> 00:58:52,660
What is the rate
of this vector?

1015
00:58:52,660 --> 00:59:01,170
So here we have a vector on
the other side, S of xi, a

1016
00:59:01,170 --> 00:59:04,240
vector on the other side.

1017
00:59:04,240 --> 00:59:05,490
What's the rate of this guy?

1018
00:59:05,490 --> 00:59:08,790

1019
00:59:08,790 --> 00:59:13,810
That's just the polynomial of
degree at most k plus degree

1020
00:59:13,810 --> 00:59:15,640
lambda minus 1.

1021
00:59:15,640 --> 00:59:29,940
So we have that the rate of this
vector is n minus k plus

1022
00:59:29,940 --> 00:59:35,617
degree lambda minus 1 plus
1 because of the minus.

1023
00:59:35,617 --> 00:59:39,230
AUDIENCE: Greater than
or equal to?

1024
00:59:39,230 --> 00:59:41,660
PROFESSOR: It's greater
than or equal, sorry.

1025
00:59:41,660 --> 00:59:43,580
Otherwise, I would have been in
trouble in a second here.

1026
00:59:43,580 --> 00:59:46,350

1027
00:59:46,350 --> 00:59:47,800
Yeah, so what does that mean?

1028
00:59:47,800 --> 00:59:51,710
So actually, this one is nice
to rewrite is equal to d n

1029
00:59:51,710 --> 00:59:55,865
minus t plus 1 d --

1030
00:59:55,865 --> 01:00:00,320
I really should have done it
like this in order not to --

1031
01:00:00,320 --> 01:00:05,010
it's d minus degree lambda.

1032
01:00:05,010 --> 01:00:08,230

1033
01:00:08,230 --> 01:00:09,550
So what can we learn
from that?

1034
01:00:09,550 --> 01:00:12,960

1035
01:00:12,960 --> 01:00:19,300
So we know this is true
for all the positions.

1036
01:00:19,300 --> 01:00:24,060
So if this is true for all
positions, then --

1037
01:00:24,060 --> 01:00:30,070
so if d minus degree lambda --

1038
01:00:30,070 --> 01:00:34,480
actually, this is t because
the rate was defined.

1039
01:00:34,480 --> 01:00:37,250
t was the number of errors.

1040
01:00:37,250 --> 01:00:39,830
And the error locator was just
defined to have degree t.

1041
01:00:39,830 --> 01:00:43,650

1042
01:00:43,650 --> 01:00:45,390
Right?

1043
01:00:45,390 --> 01:00:49,480
The error locator was just x
minus xi over all positions

1044
01:00:49,480 --> 01:00:50,890
where we had an error, so there

1045
01:00:50,890 --> 01:00:51,950
are t of those positions.

1046
01:00:51,950 --> 01:00:55,550
The degree of lambda
is equal to t.

1047
01:00:55,550 --> 01:00:56,490
So now we take this.

1048
01:00:56,490 --> 01:01:07,410
If d minus t is greater than
t, so if the rate of this

1049
01:01:07,410 --> 01:01:13,720
vector is greater than the rate
of this vector, then we

1050
01:01:13,720 --> 01:01:18,030
have a problem because
that cannot be.

1051
01:01:18,030 --> 01:01:19,840
Of course, by this identity,
the rate of these

1052
01:01:19,840 --> 01:01:22,520
two vectors is equal.

1053
01:01:22,520 --> 01:01:23,770
So what is the way out?

1054
01:01:23,770 --> 01:01:26,660

1055
01:01:26,660 --> 01:01:27,550
What's the way out?

1056
01:01:27,550 --> 01:01:28,800
AUDIENCE: [INAUDIBLE]

1057
01:01:28,800 --> 01:01:33,286

1058
01:01:33,286 --> 01:01:33,770
PROFESSOR: Yeah.

1059
01:01:33,770 --> 01:01:53,090
So if this is true, then S of
xi I claim has to be 0 and

1060
01:01:53,090 --> 01:02:01,100
lambda of xi times ei has
to be 0 too for all i.

1061
01:02:01,100 --> 01:02:03,860

1062
01:02:03,860 --> 01:02:06,460
That's the only way
out of this.

1063
01:02:06,460 --> 01:02:08,760
Because, obviously,
this was allowed.

1064
01:02:08,760 --> 01:02:11,760
If we really did find what we
wanted to find, namely, an

1065
01:02:11,760 --> 01:02:15,530
error locator here, then
this vector --

1066
01:02:15,530 --> 01:02:17,410
we said it has to
be less than t.

1067
01:02:17,410 --> 01:02:18,570
It can be less.

1068
01:02:18,570 --> 01:02:22,460
In particular, it can
be 0 if this is,

1069
01:02:22,460 --> 01:02:24,710
indeed, an error locator.

1070
01:02:24,710 --> 01:02:28,820
And if our relaxation
didn't matter --

1071
01:02:28,820 --> 01:02:34,800
that means the h that we
find factors as that --

1072
01:02:34,800 --> 01:02:38,480
if the relaxation didn't matter,
then S would be 0 too.

1073
01:02:38,480 --> 01:02:39,830
So that is a fair solution.

1074
01:02:39,830 --> 01:02:41,970
That's a possibility.

1075
01:02:41,970 --> 01:02:48,450
And if d minus t is greater than
t, then this proves this

1076
01:02:48,450 --> 01:02:51,300
is the only solution
that is feasible.

1077
01:02:51,300 --> 01:02:54,180
That's the only solution
you have.

1078
01:02:54,180 --> 01:03:03,480
So what that means is if t
less than t/2, then the

1079
01:03:03,480 --> 01:03:20,040
relaxation doesn't matter and h
of xi is equal to lambda of

1080
01:03:20,040 --> 01:03:21,568
xi times f of xi.

1081
01:03:21,568 --> 01:03:32,600

1082
01:03:32,600 --> 01:03:35,040
So is that clear?

1083
01:03:35,040 --> 01:03:44,380
That's two very simple, yet
nice ways to prove things.

1084
01:03:44,380 --> 01:03:45,750
Here, we guarantee
the solution.

1085
01:03:45,750 --> 01:03:49,450

1086
01:03:49,450 --> 01:03:51,610
Here, we guarantee
the solution.

1087
01:03:51,610 --> 01:03:55,330
Here, we guarantee that solution
is correct, namely,

1088
01:03:55,330 --> 01:03:59,760
if not too many errors happen,
if less than t/2 errors

1089
01:03:59,760 --> 01:04:06,370
happens, then relaxing the
original problem here to this

1090
01:04:06,370 --> 01:04:08,360
other form, which we
could solve, does

1091
01:04:08,360 --> 01:04:11,690
not change the solution.

1092
01:04:11,690 --> 01:04:12,940
That's what's proved there.

1093
01:04:12,940 --> 01:04:16,960

1094
01:04:16,960 --> 01:04:21,270
But about one-third
looks puzzled.

1095
01:04:21,270 --> 01:04:23,130
About half looks puzzled,
I would think.

1096
01:04:23,130 --> 01:04:29,490

1097
01:04:29,490 --> 01:04:30,900
Half looks puzzled.

1098
01:04:30,900 --> 01:04:33,870
Is there any way I can
explain that better?

1099
01:04:33,870 --> 01:04:35,120
Think.

1100
01:04:35,120 --> 01:04:42,790

1101
01:04:42,790 --> 01:04:46,980
Let's just go through
the steps quickly.

1102
01:04:46,980 --> 01:04:50,640
We had problem number one.

1103
01:04:50,640 --> 01:04:56,350
Problem number one, which is a
nonlinear problem, but you see

1104
01:04:56,350 --> 01:04:59,170
that if you could solve
this, you could solve

1105
01:04:59,170 --> 01:05:01,800
the decoding problem.

1106
01:05:01,800 --> 01:05:03,760
So you see that.

1107
01:05:03,760 --> 01:05:06,760
Anybody who doesn't see that?

1108
01:05:06,760 --> 01:05:07,090
All right.

1109
01:05:07,090 --> 01:05:08,340
You're smart guys.

1110
01:05:08,340 --> 01:05:11,130

1111
01:05:11,130 --> 01:05:13,740
If we can solve problem number
one, we are home free.

1112
01:05:13,740 --> 01:05:15,300
We have solved the
decoding problem.

1113
01:05:15,300 --> 01:05:16,270
Fine, we cannot solve it.

1114
01:05:16,270 --> 01:05:17,640
It's a nonlinear problem.

1115
01:05:17,640 --> 01:05:21,110
Well, we can solve it in
exponential time, but that's

1116
01:05:21,110 --> 01:05:23,410
little fun.

1117
01:05:23,410 --> 01:05:24,320
So we relax it.

1118
01:05:24,320 --> 01:05:28,730
We relax it into problem
number two.

1119
01:05:28,730 --> 01:05:31,444
All that we do, we multiply
things out.

1120
01:05:31,444 --> 01:05:37,510
And we do not require,
once we solve the

1121
01:05:37,510 --> 01:05:38,760
problem, this anymore.

1122
01:05:38,760 --> 01:05:46,530

1123
01:05:46,530 --> 01:05:48,490
Now we have solved
this problem.

1124
01:05:48,490 --> 01:05:51,520
We have solved this linear
system of equations.

1125
01:05:51,520 --> 01:05:59,640
And after doing so, we have
found lambda and h.

1126
01:05:59,640 --> 01:06:02,470
They are lying on the table
and looking at us.

1127
01:06:02,470 --> 01:06:03,610
Now what?

1128
01:06:03,610 --> 01:06:04,820
Are they any good?

1129
01:06:04,820 --> 01:06:08,950
In particular, since a priori we
cannot guarantee that this

1130
01:06:08,950 --> 01:06:13,170
relaxation didn't completely
destroy everything.

1131
01:06:13,170 --> 01:06:14,410
We have solved the system.

1132
01:06:14,410 --> 01:06:17,040
Now those two things are lying
on the table, looking at us,

1133
01:06:17,040 --> 01:06:19,650
and asking, what am I?

1134
01:06:19,650 --> 01:06:23,380
And in general, if there's an
arbitrary amount of errors

1135
01:06:23,380 --> 01:06:27,430
happening near the channel,
actually,

1136
01:06:27,430 --> 01:06:29,340
they do not mean much.

1137
01:06:29,340 --> 01:06:32,900
They do not mean much.

1138
01:06:32,900 --> 01:06:38,286
But now I claim that, well, if
not too many errors happened,

1139
01:06:38,286 --> 01:06:43,490
but if the number of errors is
bounded to be this, less than

1140
01:06:43,490 --> 01:06:47,610
half the minimum distance, then,
actually, I claim it did

1141
01:06:47,610 --> 01:06:49,870
not matter if we solved
the relaxation or

1142
01:06:49,870 --> 01:06:52,260
the original problem.

1143
01:06:52,260 --> 01:06:55,880
And the argument is
roughly this.

1144
01:06:55,880 --> 01:06:58,135
It goes like this.

1145
01:06:58,135 --> 01:06:59,890
Here, we start.

1146
01:06:59,890 --> 01:07:01,460
We have solved this.

1147
01:07:01,460 --> 01:07:06,370
We have two polynomials lambda
and h, so that this is true

1148
01:07:06,370 --> 01:07:07,620
for all xi.

1149
01:07:07,620 --> 01:07:10,380

1150
01:07:10,380 --> 01:07:12,440
We know that we can write
it like this.

1151
01:07:12,440 --> 01:07:15,290
That's just by definition
of yi, just

1152
01:07:15,290 --> 01:07:18,980
expanding the yi into this.

1153
01:07:18,980 --> 01:07:22,400
We know that this is true by
the definition of the code.

1154
01:07:22,400 --> 01:07:27,500
The ci is the evaluation of
f, of some polynomial f.

1155
01:07:27,500 --> 01:07:31,770
So we can write this just by
definition of the code.

1156
01:07:31,770 --> 01:07:36,430
So once we have these two guys
here, we can subtract them

1157
01:07:36,430 --> 01:07:37,680
[UNINTELLIGIBLE] here.

1158
01:07:37,680 --> 01:07:39,930

1159
01:07:39,930 --> 01:07:44,500
So we know that we have solved
the following problem.

1160
01:07:44,500 --> 01:07:49,000
We have found lambda and h.

1161
01:07:49,000 --> 01:07:57,580
So that there is guaranteed to
exist the polynomial f, so

1162
01:07:57,580 --> 01:08:02,580
that this whole thing, namely,
S of xi, that S is a

1163
01:08:02,580 --> 01:08:04,470
polynomial of degree
at most --

1164
01:08:04,470 --> 01:08:06,130
what did we have --

1165
01:08:06,130 --> 01:08:09,790
k plus degree lambda minus 1.

1166
01:08:09,790 --> 01:08:12,880

1167
01:08:12,880 --> 01:08:18,550
So that's a semi-hairy
step here.

1168
01:08:18,550 --> 01:08:24,700
Is that clear that we can
guarantee the existence of a

1169
01:08:24,700 --> 01:08:34,340
polynomial S of degree at most
k plus degree lambda minus 1?

1170
01:08:34,340 --> 01:08:38,320
So that this equation holds.

1171
01:08:38,320 --> 01:08:43,229

1172
01:08:43,229 --> 01:08:45,609
Once we have solved this,
we can guarantee the

1173
01:08:45,609 --> 01:08:46,890
existence of this.

1174
01:08:46,890 --> 01:08:48,939
That's what we're saying.

1175
01:08:48,939 --> 01:08:51,029
We can guarantee the
existence of this.

1176
01:08:51,029 --> 01:08:53,819
So now look at this.

1177
01:08:53,819 --> 01:08:58,319
If you write this out for all
i's and put it in a vector,

1178
01:08:58,319 --> 01:09:00,620
what's the rate of
this vector?

1179
01:09:00,620 --> 01:09:05,630
Well, it's at most t because
all the other e's are 0.

1180
01:09:05,630 --> 01:09:08,890
If lambda is an error
locator, it is 0.

1181
01:09:08,890 --> 01:09:10,740
But we do not know that yet.

1182
01:09:10,740 --> 01:09:12,330
All we know, it's at most t.

1183
01:09:12,330 --> 01:09:15,149

1184
01:09:15,149 --> 01:09:18,939
This is on this side, so that
vector has a rate at most t.

1185
01:09:18,939 --> 01:09:25,660
On this side, the rate of this
vector is at least this.

1186
01:09:25,660 --> 01:09:28,939
Just by evaluating a polynomial
of this degree,

1187
01:09:28,939 --> 01:09:31,193
this is the maximum number
of 0's we can get.

1188
01:09:31,193 --> 01:09:34,350

1189
01:09:34,350 --> 01:09:41,740
So now we have two equalities,
this one and this one.

1190
01:09:41,740 --> 01:09:45,330
But obviously, the two vectors
must be the same.

1191
01:09:45,330 --> 01:09:49,880
So how can these two vectors be
the same and still satisfy

1192
01:09:49,880 --> 01:09:53,250
these two inequalities?

1193
01:09:53,250 --> 01:09:53,950
Good question.

1194
01:09:53,950 --> 01:09:56,320
How can they be the same and
still satisfy this inequality?

1195
01:09:56,320 --> 01:10:10,720

1196
01:10:10,720 --> 01:10:15,070
If t is less than d/2, then the
rate of this vector would

1197
01:10:15,070 --> 01:10:18,000
have to be larger than
the rate of this.

1198
01:10:18,000 --> 01:10:19,250
If they are non-zero.

1199
01:10:19,250 --> 01:10:22,530

1200
01:10:22,530 --> 01:10:25,030
If they are non-zero, this would
have to be larger than

1201
01:10:25,030 --> 01:10:30,250
this because then d minus t
would be greater than t.

1202
01:10:30,250 --> 01:10:32,340
If this is true, this
implies this.

1203
01:10:32,340 --> 01:10:36,890

1204
01:10:36,890 --> 01:10:40,980
If this is true, this implies
this which implies that the

1205
01:10:40,980 --> 01:10:44,270
rate of this vector would be
larger than the rate of this

1206
01:10:44,270 --> 01:10:45,670
vector if they are non-zero.

1207
01:10:45,670 --> 01:10:48,840

1208
01:10:48,840 --> 01:10:50,890
But how can that be?

1209
01:10:50,890 --> 01:10:53,210
Answer is cannot.

1210
01:10:53,210 --> 01:10:56,080
Cannot be, hence,
they must be 0.

1211
01:10:56,080 --> 01:11:00,150
Both vectors must be 0
completely, which means this

1212
01:11:00,150 --> 01:11:02,250
is an error locator.

1213
01:11:02,250 --> 01:11:08,180
Because otherwise, this wouldn't
be 0, and this one --

1214
01:11:08,180 --> 01:11:09,430
where did I write it?

1215
01:11:09,430 --> 01:11:11,910

1216
01:11:11,910 --> 01:11:13,160
Somewhere I wrote it.

1217
01:11:13,160 --> 01:11:18,640

1218
01:11:18,640 --> 01:11:21,292
Where did I write it?

1219
01:11:21,292 --> 01:11:22,750
Oh, here.

1220
01:11:22,750 --> 01:11:27,300
So this S has to be 0 too.

1221
01:11:27,300 --> 01:11:33,640
If this S is 0, then h of xi is
exactly this, means factors

1222
01:11:33,640 --> 01:11:36,870
in the way you want it to.

1223
01:11:36,870 --> 01:11:40,270
So that's all I can say.

1224
01:11:40,270 --> 01:11:43,810
I could say it again, but it's
exactly the same words.

1225
01:11:43,810 --> 01:11:47,324
And there's a limited benefit
to even the repetition code.

1226
01:11:47,324 --> 01:11:50,290

1227
01:11:50,290 --> 01:11:51,880
So beautiful, right?

1228
01:11:51,880 --> 01:11:54,750
We have brought down the entire
decoding problem for

1229
01:11:54,750 --> 01:12:01,300
Reed-Solomon codes to solving a
linear system of equations,

1230
01:12:01,300 --> 01:12:06,940
namely, this one here or this
one in short form, which,

1231
01:12:06,940 --> 01:12:11,130
well, it's no problem at all in
the grand scheme of things.

1232
01:12:11,130 --> 01:12:13,250
And that's the other thing that
makes Reed-Solomon codes

1233
01:12:13,250 --> 01:12:14,080
so beautiful.

1234
01:12:14,080 --> 01:12:17,674
They're access encoding, they're
access decoding,

1235
01:12:17,674 --> 01:12:19,370
they're everything
that we want.

1236
01:12:19,370 --> 01:12:35,380

1237
01:12:35,380 --> 01:12:38,660
Let me do one more thing about
the decoding just to bring it

1238
01:12:38,660 --> 01:12:42,850
down a little bit, to talk a
little bit about complexity.

1239
01:12:42,850 --> 01:12:50,560
Solving this linear system of
equations has been subject to

1240
01:12:50,560 --> 01:12:56,850
research for 30 years,
40 years.

1241
01:12:56,850 --> 01:13:01,520
So it started out with an
algorithm which essentially

1242
01:13:01,520 --> 01:13:04,976
solved that linear
system directly.

1243
01:13:04,976 --> 01:13:08,030
It was formulated a
bit different, but

1244
01:13:08,030 --> 01:13:08,680
that's what it is.

1245
01:13:08,680 --> 01:13:08,980
It's called the

1246
01:13:08,980 --> 01:13:10,750
Peterson-Gorenstein-Zierler algorithm.

1247
01:13:10,750 --> 01:13:14,560

1248
01:13:14,560 --> 01:13:20,850
They realized it was a
polynomial time decoding

1249
01:13:20,850 --> 01:13:23,500
algorithm, a nice decoding
algorithm.

1250
01:13:23,500 --> 01:13:24,060
Then Berlekamp --

1251
01:13:24,060 --> 01:13:25,320
I should write down the name.

1252
01:13:25,320 --> 01:13:30,190

1253
01:13:30,190 --> 01:13:31,760
Berlekamp came up with a fast

1254
01:13:31,760 --> 01:13:33,420
algorithm and square algorithm.

1255
01:13:33,420 --> 01:13:40,030

1256
01:13:40,030 --> 01:13:44,700
Massey had his own formulation
of that algorithm, which was a

1257
01:13:44,700 --> 01:13:46,095
bit more streamlined I think.

1258
01:13:46,095 --> 01:13:48,810

1259
01:13:48,810 --> 01:13:53,020
Then there was a later version,
Berlekamp-Welch.

1260
01:13:53,020 --> 01:13:58,230

1261
01:13:58,230 --> 01:14:01,070
The complexity of these
algorithms is all roughly the

1262
01:14:01,070 --> 01:14:03,920
same, is all n squared roughly,

1263
01:14:03,920 --> 01:14:06,430
which solved this here.

1264
01:14:06,430 --> 01:14:08,910
And then there's
roughly nothing

1265
01:14:08,910 --> 01:14:10,280
happening for 30 years.

1266
01:14:10,280 --> 01:14:13,170

1267
01:14:13,170 --> 01:14:21,630
And after 30 years, then Madhu
Sudan made the next serious

1268
01:14:21,630 --> 01:14:25,820
dent in the decoding history
of Reed-Solomon codes.

1269
01:14:25,820 --> 01:14:32,885
So he found a way to solve this
problem even beyond half

1270
01:14:32,885 --> 01:14:35,700
the minimum distance.

1271
01:14:35,700 --> 01:14:41,230
And in hindsight, it's a very
nice and very simple trick

1272
01:14:41,230 --> 01:14:42,480
that he used.

1273
01:14:42,480 --> 01:14:46,160

1274
01:14:46,160 --> 01:14:54,945
So we started with
the following.

1275
01:14:54,945 --> 01:15:03,490
We started that, well, if we
have no errors, then the pairs

1276
01:15:03,490 --> 01:15:13,110
of points xi, yi lie
on this curve.

1277
01:15:13,110 --> 01:15:16,940
That's another way to formulate
what we said that yi

1278
01:15:16,940 --> 01:15:20,760
minus f of xi has to be 0.

1279
01:15:20,760 --> 01:15:23,480
We said, well, if there are no
errors, all the points that we

1280
01:15:23,480 --> 01:15:26,260
receive lie on this curve.

1281
01:15:26,260 --> 01:15:31,300
Because there are errors, we
have to multiply this with an

1282
01:15:31,300 --> 01:15:39,570
error locator and say this
is 0 for all xi, yi.

1283
01:15:39,570 --> 01:15:41,430
So this was problem
number one.

1284
01:15:41,430 --> 01:15:57,280
The relaxed form was lambda
xy minus h of x 0 xi, yi.

1285
01:15:57,280 --> 01:15:59,270
That's the way we do it.

1286
01:15:59,270 --> 01:16:00,690
So what did Madhu do?

1287
01:16:00,690 --> 01:16:01,330
Very clever.

1288
01:16:01,330 --> 01:16:06,490
He said, all that we have to do
is annihilate the effect of

1289
01:16:06,490 --> 01:16:09,380
the error right in this.

1290
01:16:09,380 --> 01:16:12,070
The whole reason for that lambda
was to annihilate --

1291
01:16:12,070 --> 01:16:16,270
so to take out the error
influence out of this

1292
01:16:16,270 --> 01:16:20,800
interpolation formula, to allow
for a few errors to

1293
01:16:20,800 --> 01:16:23,180
happen, which we can
put in lambda.

1294
01:16:23,180 --> 01:16:27,520
Well, Madhu said, well, what
about we take a polynomial in

1295
01:16:27,520 --> 01:16:28,770
two variables?

1296
01:16:28,770 --> 01:16:30,570

1297
01:16:30,570 --> 01:16:36,790
A polynomial in two variables,
then same thing.

1298
01:16:36,790 --> 01:16:43,030
If no errors happen, then all
the points xi, yi will lie on

1299
01:16:43,030 --> 01:16:44,580
that curve.

1300
01:16:44,580 --> 01:16:50,690
If a few errors happen, then
let's find a lambda xy, two

1301
01:16:50,690 --> 01:16:55,790
variables of some minimal
degree, some very small degree

1302
01:16:55,790 --> 01:16:57,715
so that this is still
satisfied.

1303
01:16:57,715 --> 01:17:02,082

1304
01:17:02,082 --> 01:17:04,420
And the problem is entirely
the same.

1305
01:17:04,420 --> 01:17:07,820

1306
01:17:07,820 --> 01:17:12,420
And this one, you cannot
solve either.

1307
01:17:12,420 --> 01:17:14,160
You cannot solve either.

1308
01:17:14,160 --> 01:17:19,950
But again, you can solve
the relaxation minus --

1309
01:17:19,950 --> 01:17:27,550

1310
01:17:27,550 --> 01:17:29,280
again, you can solve
the relaxation.

1311
01:17:29,280 --> 01:17:31,890
This is, again, a linear
system of equations.

1312
01:17:31,890 --> 01:17:33,830
And the coefficients of
lambda and psi now.

1313
01:17:33,830 --> 01:17:36,960

1314
01:17:36,960 --> 01:17:40,020
Once you solve this linear
system of equations --

1315
01:17:40,020 --> 01:17:43,565
actually, this one you can more
handily write simply --

1316
01:17:43,565 --> 01:17:46,270
now there is no way to
distinguish the y anymore

1317
01:17:46,270 --> 01:17:50,090
since both sides anyway
depend on y.

1318
01:17:50,090 --> 01:17:56,590
Find a polynomial in two
variables such that this is 0

1319
01:17:56,590 --> 01:17:59,930
for all xi, yi.

1320
01:17:59,930 --> 01:18:02,030
This is his central problem.

1321
01:18:02,030 --> 01:18:03,160
This is his relaxation.

1322
01:18:03,160 --> 01:18:05,350
Find a polynomial in two
variables, which he

1323
01:18:05,350 --> 01:18:06,600
evaluates to 0.

1324
01:18:06,600 --> 01:18:09,140

1325
01:18:09,140 --> 01:18:15,440
And then he has, essentially,
the same proofs we have here,

1326
01:18:15,440 --> 01:18:20,360
a bit more technical,
but not much.

1327
01:18:20,360 --> 01:18:22,710
I'm sure you can come up with
this if you sit down at home.

1328
01:18:22,710 --> 01:18:26,930

1329
01:18:26,930 --> 01:18:27,610
Let's put it like this.

1330
01:18:27,610 --> 01:18:29,180
There's no heavy machinery
in it.

1331
01:18:29,180 --> 01:18:30,870
There's no heavy math in it.

1332
01:18:30,870 --> 01:18:33,710
There's a lot of being clever
in it, but there's no heavy

1333
01:18:33,710 --> 01:18:34,960
math in it.

1334
01:18:34,960 --> 01:18:40,690

1335
01:18:40,690 --> 01:18:52,280
He can now guarantee that q of
xy, if t is less than n minus

1336
01:18:52,280 --> 01:18:55,700
square root of 2k --

1337
01:18:55,700 --> 01:18:57,570
is that right --

1338
01:18:57,570 --> 01:19:06,280
2kn, then you can guarantee
that y minus fx is

1339
01:19:06,280 --> 01:19:09,420
a factor q of xy.

1340
01:19:09,420 --> 01:19:12,736
The same thing we wanted
to guarantee.

1341
01:19:12,736 --> 01:19:19,170
And like I said, the proof is
very clever, but no heavy

1342
01:19:19,170 --> 01:19:19,830
machinery in it.

1343
01:19:19,830 --> 01:19:22,176
It's no heavy algebraic
geometry or any of

1344
01:19:22,176 --> 01:19:23,426
this stuff in that.

1345
01:19:23,426 --> 01:19:25,940

1346
01:19:25,940 --> 01:19:29,110
It's high school algebra.

1347
01:19:29,110 --> 01:19:34,200
Well, freshman college
algebra.

1348
01:19:34,200 --> 01:19:35,460
So that's what happens here.

1349
01:19:35,460 --> 01:19:39,056

1350
01:19:39,056 --> 01:19:41,310
It took 30 years and a computer
scientist to solve

1351
01:19:41,310 --> 01:19:42,560
that problem.

1352
01:19:42,560 --> 01:19:50,380

1353
01:19:50,380 --> 01:19:55,110
That was not all I wanted
to say, but that's

1354
01:19:55,110 --> 01:19:57,425
all I have time for.

1355
01:19:57,425 --> 01:19:59,720
There's one minute left, so
there's no point in starting

1356
01:19:59,720 --> 01:20:01,060
something now.

1357
01:20:01,060 --> 01:20:02,603
Do you have any questions
about any of this?

1358
01:20:02,603 --> 01:20:08,882

1359
01:20:08,882 --> 01:20:14,640
I should say that this 2 one can
get rid of, but that takes

1360
01:20:14,640 --> 01:20:15,890
a little bit more machinery.

1361
01:20:15,890 --> 01:20:18,330

1362
01:20:18,330 --> 01:20:20,785
The 2 one can get rid of, but
that's a bit more heavy.

1363
01:20:20,785 --> 01:20:24,544

1364
01:20:24,544 --> 01:20:25,040
All right.

1365
01:20:25,040 --> 01:20:27,530
So thanks so much.

1366
01:20:27,530 --> 01:20:28,910
That's it.

1367
01:20:28,910 --> 01:20:30,160
That's it.

1368
01:20:30,160 --> 01:20:36,948