1
00:00:00,000 --> 00:00:00,405

2
00:00:00,405 --> 00:00:04,200
PROFESSOR: Chapter six, problem
set three, problem set

3
00:00:04,200 --> 00:00:06,140
two solutions.

4
00:00:06,140 --> 00:03:27,510

5
00:03:27,510 --> 00:03:28,100
OK.

6
00:03:28,100 --> 00:03:29,460
Good morning.

7
00:03:29,460 --> 00:03:32,690
Nice to see you all again
on this mild day.

8
00:03:32,690 --> 00:03:37,070
I want to start off by thanking
Ashish greatly for

9
00:03:37,070 --> 00:03:39,610
giving the last three
lectures.

10
00:03:39,610 --> 00:03:42,420
I have very high confidence in
Ashish, and I'm sure he give

11
00:03:42,420 --> 00:03:45,090
you excellent lectures and was
able to answer all your

12
00:03:45,090 --> 00:03:46,340
questions, right?

13
00:03:46,340 --> 00:03:48,900

14
00:03:48,900 --> 00:03:52,000
But if you feel dissatisfied at
any point, you'll have an

15
00:03:52,000 --> 00:03:54,295
opportunity to ask the
question again today.

16
00:03:54,295 --> 00:03:57,020

17
00:03:57,020 --> 00:03:59,930
We will continue now
in chapter six.

18
00:03:59,930 --> 00:04:04,010
I understand Ashish got up to
section six point one already,

19
00:04:04,010 --> 00:04:07,440
so that makes my life
a little easier.

20
00:04:07,440 --> 00:04:09,870
And we'll just continue to plow
ahead through the notes.

21
00:04:09,870 --> 00:04:16,600
You have as handouts today
chapter six, the outgoing

22
00:04:16,600 --> 00:04:21,769
problem set, the solutions to
the incoming problem set.

23
00:04:21,769 --> 00:04:26,690
So does anyone have any comments
or questions or

24
00:04:26,690 --> 00:04:30,120
suggestions as we go forward
at this point?

25
00:04:30,120 --> 00:04:34,360
Let's say I'll do a very quick
review of everything so far,

26
00:04:34,360 --> 00:04:37,440
at least what we need to
proceed, so you'll have a

27
00:04:37,440 --> 00:04:40,870
chance to ask questions along
there if you like.

28
00:04:40,870 --> 00:04:43,040
Anyone have anything to say?

29
00:04:43,040 --> 00:04:44,570
Anyone want to say
thanks to Ashish?

30
00:04:44,570 --> 00:04:48,830

31
00:04:48,830 --> 00:04:49,280
All right.

32
00:04:49,280 --> 00:04:51,970
Great.

33
00:04:51,970 --> 00:04:52,550
OK.

34
00:04:52,550 --> 00:04:57,190
So a very quick review.

35
00:04:57,190 --> 00:05:02,300
We first said we were going to
work with a continuous time

36
00:05:02,300 --> 00:05:05,260
Additive White Gaussian noise
channel, but we quickly

37
00:05:05,260 --> 00:05:08,780
reduced it to a discrete
time additive white

38
00:05:08,780 --> 00:05:10,110
Gaussian noise model.

39
00:05:10,110 --> 00:05:15,030
Vector model, Y equals X plus N,
where the vectors may go on

40
00:05:15,030 --> 00:05:16,690
as long as you like.

41
00:05:16,690 --> 00:05:19,390
And implicit in here is we
have some kind of power

42
00:05:19,390 --> 00:05:21,980
limitation expressed
by various --

43
00:05:21,980 --> 00:05:24,930
I know I've probably introduced
too many parameters

44
00:05:24,930 --> 00:05:27,710
in the early part
of the course.

45
00:05:27,710 --> 00:05:31,820
But you'll see them all in the
literature, and I thought you

46
00:05:31,820 --> 00:05:36,180
might as well see the relation
between them all at once.

47
00:05:36,180 --> 00:05:36,850
The noise.

48
00:05:36,850 --> 00:05:40,350
The main thing about this
is it's an independent,

49
00:05:40,350 --> 00:05:44,640
identically distributed noise,
also independent of X, and

50
00:05:44,640 --> 00:05:49,020
it's characterized simply by
its variance per symbol, or

51
00:05:49,020 --> 00:05:49,960
average power.

52
00:05:49,960 --> 00:05:54,360
Again, there are various
notations that we

53
00:05:54,360 --> 00:05:57,310
can use for its power.

54
00:05:57,310 --> 00:05:58,310
OK.

55
00:05:58,310 --> 00:06:03,310
However you express the power
of the signal of the noise,

56
00:06:03,310 --> 00:06:05,290
you're going to get some
signal-to-noise ratio out of

57
00:06:05,290 --> 00:06:09,160
that, as long as you use
consistent the same units for

58
00:06:09,160 --> 00:06:10,960
signal and noise.

59
00:06:10,960 --> 00:06:13,860
And so the key parameters
of this channel turn

60
00:06:13,860 --> 00:06:16,160
out to be just two.

61
00:06:16,160 --> 00:06:19,200
One is the signal-to-noise
ratio.

62
00:06:19,200 --> 00:06:23,000
And the other is something which
in the discrete time

63
00:06:23,000 --> 00:06:26,260
domain we might think of as a
data rate, rho, the number of

64
00:06:26,260 --> 00:06:28,880
bits per two dimensions.

65
00:06:28,880 --> 00:06:32,360
But we were at pains
to show --

66
00:06:32,360 --> 00:06:35,380
and the reason we measure it in
bits per two dimensions is

67
00:06:35,380 --> 00:06:40,180
that it converts directly to the
spectral efficiency, or we

68
00:06:40,180 --> 00:06:42,990
sometimes say, the nominal
spectral efficiency, or the

69
00:06:42,990 --> 00:06:45,340
Nyquist spectral efficiency.

70
00:06:45,340 --> 00:06:48,330
Basically, this is the spectral
efficiency if you

71
00:06:48,330 --> 00:06:52,620
assume that you only use the
nominal Nyquist bandwidth.

72
00:06:52,620 --> 00:06:57,630
And both in 450 and here it was
shown that you can really

73
00:06:57,630 --> 00:07:03,710
get as close to the nominal
bandwidth as you like, its

74
00:07:03,710 --> 00:07:08,530
sharp or roll off as you
like, by using filters.

75
00:07:08,530 --> 00:07:15,830
Very sharp filters or very sharp
digital filters that

76
00:07:15,830 --> 00:07:20,660
today we can really
realistically get effectively

77
00:07:20,660 --> 00:07:23,700
to the Nyquist bandwidth.

78
00:07:23,700 --> 00:07:27,150
So this is a good measure of
nominal spectral efficiency,

79
00:07:27,150 --> 00:07:29,780
which is an extremely important
parameter, the

80
00:07:29,780 --> 00:07:33,920
spectral efficiency in
continuous time.

81
00:07:33,920 --> 00:07:36,820
And then the Shannon limit is
expressed in this very simple

82
00:07:36,820 --> 00:07:44,020
form that we can never do better
in data rate or nominal

83
00:07:44,020 --> 00:07:48,920
spectral efficiency than
log of 1 plus SNR.

84
00:07:48,920 --> 00:07:51,860
And the units are bits
per two dimensions.

85
00:07:51,860 --> 00:07:55,410
So there's an awful lot about
parameters and units in the

86
00:07:55,410 --> 00:07:57,850
first part of the course, and
sometimes it's a little

87
00:07:57,850 --> 00:07:59,100
overwhelming and confusing.

88
00:07:59,100 --> 00:08:01,730

89
00:08:01,730 --> 00:08:05,670
But in my experience in
engineering is, it's extremely

90
00:08:05,670 --> 00:08:08,630
important to get the
units right.

91
00:08:08,630 --> 00:08:11,470
It helps you in thinking
clearly.

92
00:08:11,470 --> 00:08:14,040
It helps you to focus
on the right things.

93
00:08:14,040 --> 00:08:16,530
And so in the first couple of
chapters, there's a lot of

94
00:08:16,530 --> 00:08:18,950
emphasis on getting
the units right.

95
00:08:18,950 --> 00:08:21,490
For instance, bits per
two dimensions.

96
00:08:21,490 --> 00:08:25,590
I could simply assert to you
that things are always to come

97
00:08:25,590 --> 00:08:28,060
out better if you do things
per two dimensions.

98
00:08:28,060 --> 00:08:34,039
This basically has to do with
Gaussian distributions being

99
00:08:34,039 --> 00:08:37,374
simpler in two dimensions than
they are in one dimension.

100
00:08:37,374 --> 00:08:41,630
So you know you can get closed
form integrals in two and four

101
00:08:41,630 --> 00:08:44,420
and so forth dimensions that you
can't get in one and three

102
00:08:44,420 --> 00:08:45,610
and so forth dimensions.

103
00:08:45,610 --> 00:08:50,350
So you know, the geometrical
formulas for the volume of the

104
00:08:50,350 --> 00:08:53,060
sphere and so forth are much
simpler in even dimensions

105
00:08:53,060 --> 00:08:55,550
than they are in
odd dimensions.

106
00:08:55,550 --> 00:09:00,610
This all, I think, has to do
with the fact that really a

107
00:09:00,610 --> 00:09:03,750
one-dimensional complex Gaussian
variable, or in

108
00:09:03,750 --> 00:09:06,570
general, complex Gaussian
variables, are in some sense

109
00:09:06,570 --> 00:09:10,780
mathematically simpler than
real Gaussian variables.

110
00:09:10,780 --> 00:09:14,270
For instance, the Q function
is a very ugly thing.

111
00:09:14,270 --> 00:09:16,670
In two dimensions, you can
closed-form integrals with

112
00:09:16,670 --> 00:09:18,520
probability of error.

113
00:09:18,520 --> 00:09:22,210
So there's a lot of clues that
we really want to think in

114
00:09:22,210 --> 00:09:26,293
terms of pairs of
real dimensions.

115
00:09:26,293 --> 00:09:29,580

116
00:09:29,580 --> 00:09:29,640
All right.

117
00:09:29,640 --> 00:09:32,280
And then we introduced a
couple more parameters.

118
00:09:32,280 --> 00:09:35,580
And I understand Ashish
got the questions

119
00:09:35,580 --> 00:09:36,460
that I get every year.

120
00:09:36,460 --> 00:09:39,040
Why do we introduce both
of these things?

121
00:09:39,040 --> 00:09:43,130
SNR norm, which is SNR
normalized by 2 to the rho

122
00:09:43,130 --> 00:09:45,690
minus 1, that's motivated
directly by the

123
00:09:45,690 --> 00:09:47,540
Shannon limit formula.

124
00:09:47,540 --> 00:09:52,720
Or Eb over N_0, which is
SNR divided by rho.

125
00:09:52,720 --> 00:09:54,170
You know, these are
both more or less

126
00:09:54,170 --> 00:09:55,940
equivalent to each other.

127
00:09:55,940 --> 00:10:00,240
From this Eb over N_0 is just 2
to the rho minus 1 over rho

128
00:10:00,240 --> 00:10:05,010
times SNR norm, so why do we
introduce both of them?

129
00:10:05,010 --> 00:10:11,900
And there's not an
intellectually very strong

130
00:10:11,900 --> 00:10:15,760
argument to introduce
both of them.

131
00:10:15,760 --> 00:10:20,530
Because one is easily translated
into the other.

132
00:10:20,530 --> 00:10:26,060
For fixed nominal spectral
efficiency rho, there clearly

133
00:10:26,060 --> 00:10:28,060
is just a one-to-one
translation.

134
00:10:28,060 --> 00:10:29,940
We could use either one.

135
00:10:29,940 --> 00:10:33,900
If you graph something versus
Eb over N_0 or versus SNR

136
00:10:33,900 --> 00:10:38,260
norm, it's just a matter of
shifting it by this factor.

137
00:10:38,260 --> 00:10:42,230
They're going to be exactly the
same graph with the 0 dB

138
00:10:42,230 --> 00:10:47,650
point in a different place,
according to where 0 dB is.

139
00:10:47,650 --> 00:10:52,460
Philosophically, of course, SNR
norm, which is sometimes

140
00:10:52,460 --> 00:10:58,960
called the gap to capacity, is
exactly a measure of how many

141
00:10:58,960 --> 00:11:02,070
dBs away are we from
the Shannon limit.

142
00:11:02,070 --> 00:11:06,570
Measuring things on
a log scale in dB.

143
00:11:06,570 --> 00:11:10,400
And so 0 dB is always the
Shannon limit point with SNR

144
00:11:10,400 --> 00:11:15,700
norm, because this statement
translates into SNR norm is

145
00:11:15,700 --> 00:11:18,900
greater than 1, which is 0 dB.

146
00:11:18,900 --> 00:11:23,040
So here the focus is always, how
far are you from capacity?

147
00:11:23,040 --> 00:11:25,270
How far are you from
the Shannon limit?

148
00:11:25,270 --> 00:11:29,200
And that really is
the modern view.

149
00:11:29,200 --> 00:11:32,410
In the early days of coding, the
view was, well, how much

150
00:11:32,410 --> 00:11:35,160
coding gain can we get
over no coding?

151
00:11:35,160 --> 00:11:42,960
And as we'll see, Eb over N_0
is often a very convenient

152
00:11:42,960 --> 00:11:46,370
parameter to use when we're
focusing on coding gain.

153
00:11:46,370 --> 00:11:49,040
In fact, for binary linear block
codes, which is what

154
00:11:49,040 --> 00:11:51,960
we're talking about in chapter
six, we get an extremely

155
00:11:51,960 --> 00:11:57,700
simple expression that Eb over
N_0 it's just kd over N, where

156
00:11:57,700 --> 00:12:02,590
N, k, d are the basic parameters
of a block code.

157
00:12:02,590 --> 00:12:04,150
If you don't know those
yet, you will by

158
00:12:04,150 --> 00:12:06,910
the end of this lecture.

159
00:12:06,910 --> 00:12:14,210
And Eb over N_0 is what was put
forward in the early days,

160
00:12:14,210 --> 00:12:17,370
when the principal coding
application was coding for

161
00:12:17,370 --> 00:12:19,180
deep space communications.

162
00:12:19,180 --> 00:12:22,320
It makes sense in the
power-limited regime.

163
00:12:22,320 --> 00:12:27,180
In the power-limited regime,
we showed that this

164
00:12:27,180 --> 00:12:31,540
essentially goes -- this is rho
log2 over rho, so up to a

165
00:12:31,540 --> 00:12:36,190
factor of natural logarithm of
two, these are the same,

166
00:12:36,190 --> 00:12:39,610
almost independent of the
spectral efficiency, as well.

167
00:12:39,610 --> 00:12:44,440
And so this is a very natural
thing to use, especially in

168
00:12:44,440 --> 00:12:46,240
the power-limited regime.

169
00:12:46,240 --> 00:12:50,180
In the bandwidth-limited regime,
as rho gets large,

170
00:12:50,180 --> 00:12:52,910
then these things become
very different.

171
00:12:52,910 --> 00:12:56,050
SNR norm always keeps us in
the neighborhood of 0 dB.

172
00:12:56,050 --> 00:13:01,210
This thing goes up to 10 dB,
20 dB, 30 dB, and so forth.

173
00:13:01,210 --> 00:13:03,940
Nonetheless, you'll see in
some literature, people

174
00:13:03,940 --> 00:13:09,910
continue to measure against Eb
over N_0 maybe I would say,

175
00:13:09,910 --> 00:13:11,290
just because they don't
know any better.

176
00:13:11,290 --> 00:13:16,000
Anyway, since I started writing
these notes about

177
00:13:16,000 --> 00:13:19,090
eight or nine years ago, I've
been advocating SNR norm.

178
00:13:19,090 --> 00:13:23,830
It's more and more widely
used in our business,

179
00:13:23,830 --> 00:13:24,930
in the coding business.

180
00:13:24,930 --> 00:13:30,680
Or equivalently, one always
shows nowadays how far are you

181
00:13:30,680 --> 00:13:35,370
from capacity, and that's
what SNR norm is about.

182
00:13:35,370 --> 00:13:38,690
And you can always translate
this into this and this into

183
00:13:38,690 --> 00:13:40,830
this by this simple formula.

184
00:13:40,830 --> 00:13:42,190
So that's why we introduce
them both.

185
00:13:42,190 --> 00:13:44,630
Eb over N_0 is traditional.

186
00:13:44,630 --> 00:13:49,821
SNR norm is more of the modern
gap to capacity viewpoint.

187
00:13:49,821 --> 00:13:51,430
Any questions about that?

188
00:13:51,430 --> 00:13:54,830
Because I understood that
Ashish got a number of

189
00:13:54,830 --> 00:13:56,410
questions about that.

190
00:13:56,410 --> 00:13:56,875
Yes?

191
00:13:56,875 --> 00:13:59,725
AUDIENCE: And the probability
of error you mentioned

192
00:13:59,725 --> 00:14:03,550
[UNINTELLIGIBLE] is natural
with SNR model.

193
00:14:03,550 --> 00:14:04,610
PROFESSOR: Well, this
is a slightly

194
00:14:04,610 --> 00:14:05,860
different point, actually.

195
00:14:05,860 --> 00:14:08,010

196
00:14:08,010 --> 00:14:11,060
So we go on from this to talk
about the power-limited

197
00:14:11,060 --> 00:14:14,580
regime, which we defined more
or less arbitrarily as the

198
00:14:14,580 --> 00:14:17,860
regime where rho is less than
or equal to two bits per two

199
00:14:17,860 --> 00:14:20,620
dimensions, and the
bandwidth-limited regime,

200
00:14:20,620 --> 00:14:23,800
which is where rho is larger.

201
00:14:23,800 --> 00:14:30,310
And at this point, I simply
assert that it's better to do

202
00:14:30,310 --> 00:14:32,940
everything per two dimensions
in the bandwidth-limited

203
00:14:32,940 --> 00:14:39,120
regime and to do everything
per bit in the

204
00:14:39,120 --> 00:14:41,270
power-limited regime.

205
00:14:41,270 --> 00:14:47,410
And the reason for this is
basically long practice and

206
00:14:47,410 --> 00:14:51,090
intuition and experience that
things do work out better, and

207
00:14:51,090 --> 00:14:53,980
this is the proper
normalization.

208
00:14:53,980 --> 00:14:55,920
But I think at this point
in the course, with your

209
00:14:55,920 --> 00:15:00,350
background, this is only an
assertion, all right?

210
00:15:00,350 --> 00:15:05,590
So I simply say, this is the way
we're going to do things

211
00:15:05,590 --> 00:15:08,140
in bandwidth-limited
and power-limited.

212
00:15:08,140 --> 00:15:13,220
For most of the rest of the
course, we're going to be in

213
00:15:13,220 --> 00:15:14,400
the power-limited regime.

214
00:15:14,400 --> 00:15:18,820
Then we'll come back to the
bandwidth-limited very late in

215
00:15:18,820 --> 00:15:19,810
the course.

216
00:15:19,810 --> 00:15:26,400
So you can now forget this
assertion for a while.

217
00:15:26,400 --> 00:15:26,850
Yes?

218
00:15:26,850 --> 00:15:28,100
AUDIENCE: [INAUDIBLE]

219
00:15:28,100 --> 00:15:31,270

220
00:15:31,270 --> 00:15:33,430
PROFESSOR: Well, I'm trying
to focus on that here.

221
00:15:33,430 --> 00:15:38,390
That if two systems have
different rhos, then you

222
00:15:38,390 --> 00:15:42,330
should take that into account
in their comparison.

223
00:15:42,330 --> 00:15:59,200
And when you see charts of a
rate 7/8 system, or a rho 7/4

224
00:15:59,200 --> 00:16:03,650
system versus one that's rate
1/8, those are very different

225
00:16:03,650 --> 00:16:10,490
regimes, and it probably isn't
fair to compare two systems,

226
00:16:10,490 --> 00:16:13,380
just in terms of their
probability of error versus Eb

227
00:16:13,380 --> 00:16:16,480
over N_0 at two different
spectral efficiencies.

228
00:16:16,480 --> 00:16:21,310
What is more fair is to compare
them in terms of their

229
00:16:21,310 --> 00:16:22,560
gap to capacity.

230
00:16:22,560 --> 00:16:27,210

231
00:16:27,210 --> 00:16:30,640
You can get more powerful
codes with more

232
00:16:30,640 --> 00:16:34,570
error-correcting capability the
lower in rate that you go.

233
00:16:34,570 --> 00:16:39,960
And so you should start from
the point of view that two

234
00:16:39,960 --> 00:16:45,330
systems with different rho are
incomparable, and then using

235
00:16:45,330 --> 00:16:48,730
this you can say, but, you know,
if we can get within 1

236
00:16:48,730 --> 00:16:51,440
dB of the Shannon limit with
both of them, then they're

237
00:16:51,440 --> 00:16:53,890
both approximately
equally powerful.

238
00:16:53,890 --> 00:16:56,640
That would be the modern
point of view.

239
00:16:56,640 --> 00:17:00,400
But it's really apples and
oranges if they have different

240
00:17:00,400 --> 00:17:03,560
rates, different rhos.

241
00:17:03,560 --> 00:17:03,990
Yes?

242
00:17:03,990 --> 00:17:05,240
AUDIENCE: [INAUDIBLE]

243
00:17:05,240 --> 00:17:07,550

244
00:17:07,550 --> 00:17:10,115
If [UNINTELLIGIBLE]

245
00:17:10,115 --> 00:17:13,349
systems modulation
[INAUDIBLE].

246
00:17:13,349 --> 00:17:16,910
Then is it fair --

247
00:17:16,910 --> 00:17:21,079
because if one of them
has coding --

248
00:17:21,079 --> 00:17:24,710
PROFESSOR: If none of them
have coding, well --

249
00:17:24,710 --> 00:17:26,054
AUDIENCE: No, just modulation.

250
00:17:26,054 --> 00:17:28,960

251
00:17:28,960 --> 00:17:31,870
PROFESSOR: So what shall
I say to that.

252
00:17:31,870 --> 00:17:35,500
In the power-limited regime,
an uncoded system is simply

253
00:17:35,500 --> 00:17:41,900
binary modulation or 4-QAM,
and there aren't different

254
00:17:41,900 --> 00:17:43,170
systems to compare, really.

255
00:17:43,170 --> 00:17:46,850
There's only one baseline
system.

256
00:17:46,850 --> 00:17:51,105
As you go up into the
bandwidth-limited regime, then

257
00:17:51,105 --> 00:17:55,290
it is fair to compare
systems of the same

258
00:17:55,290 --> 00:17:58,650
class, like M by M QAM.

259
00:17:58,650 --> 00:18:01,180
That's a simple uncoded
system.

260
00:18:01,180 --> 00:18:04,060
Now there, rho keeps changing.

261
00:18:04,060 --> 00:18:08,260
rho equals 2, rho equals 4, rho
equals 6, rho equals 8.

262
00:18:08,260 --> 00:18:11,210
Or you can easily find
intermediate

263
00:18:11,210 --> 00:18:13,610
rates that are uncoded.

264
00:18:13,610 --> 00:18:17,740
And there you find that this
normalization makes all these

265
00:18:17,740 --> 00:18:19,540
systems comparable.

266
00:18:19,540 --> 00:18:24,160
In fact, we saw that we got a
universal baseline curve for

267
00:18:24,160 --> 00:18:28,100
the bandwidth-limited regime,
which was independent of rho,

268
00:18:28,100 --> 00:18:33,520
for, say, the class of 4 by
4, by the class of M by M

269
00:18:33,520 --> 00:18:37,900
bandwidth-limited QAM systems.

270
00:18:37,900 --> 00:18:38,300
I'm sorry.

271
00:18:38,300 --> 00:18:41,600
I got off a plane at nine
o'clock last night, so I may

272
00:18:41,600 --> 00:18:45,440
not be totally coherent today.

273
00:18:45,440 --> 00:18:49,750
But all of these systems have
exactly the same baseline

274
00:18:49,750 --> 00:18:55,210
curve up to the approximations
we've made that their exactly

275
00:18:55,210 --> 00:18:57,130
four nearest neighbors
and so forth.

276
00:18:57,130 --> 00:19:02,040
But on a curve of probability
of error per two dimensions,

277
00:19:02,040 --> 00:19:06,930
per QAM symbol, versus
SNR norm, we

278
00:19:06,930 --> 00:19:08,290
get a universal curve.

279
00:19:08,290 --> 00:19:11,560
So that indicates they really
are comparable.

280
00:19:11,560 --> 00:19:15,460
They form a class where the
performance of the class is

281
00:19:15,460 --> 00:19:16,820
independent of rho.

282
00:19:16,820 --> 00:19:20,730
And that's sort of typical of
the bandwidth-limited regime.

283
00:19:20,730 --> 00:19:24,010
Two systems that differ, that
basically use the same code

284
00:19:24,010 --> 00:19:28,220
with smaller constellation
or a larger-based uncoded

285
00:19:28,220 --> 00:19:30,870
constellation are going to be
directly comparable, and are

286
00:19:30,870 --> 00:19:35,370
probably going to have the
same gap to capacity.

287
00:19:35,370 --> 00:19:37,370
Going to be just as far away
from the Shannon limit.

288
00:19:37,370 --> 00:19:39,410
But we don't have that
phenomenon in the

289
00:19:39,410 --> 00:19:40,660
power-limited case.

290
00:19:40,660 --> 00:19:45,080

291
00:19:45,080 --> 00:19:46,780
Other questions, or
shall I proceed?

292
00:19:46,780 --> 00:19:49,810

293
00:19:49,810 --> 00:19:51,060
OK.

294
00:19:51,060 --> 00:19:52,880

295
00:19:52,880 --> 00:19:58,490
Again continuing what I hope
will be a quick review, but I

296
00:19:58,490 --> 00:20:00,720
don't want to go any faster than
you're comfortable with.

297
00:20:00,720 --> 00:20:05,960

298
00:20:05,960 --> 00:20:12,140
We get this baseline curve
for 2-PAM or 2

299
00:20:12,140 --> 00:20:14,330
by 2 QAM, same thing.

300
00:20:14,330 --> 00:20:18,400

301
00:20:18,400 --> 00:20:26,520
So this is the baseline of Pb of
E on a log scale, where we

302
00:20:26,520 --> 00:20:29,460
typically go down to ten to
the minus six, ten to the

303
00:20:29,460 --> 00:20:31,050
minus five.

304
00:20:31,050 --> 00:20:33,320
Here's 0 dB.

305
00:20:33,320 --> 00:20:37,670
This goes down through
about 9.6 dB here or

306
00:20:37,670 --> 00:20:40,710
about 10.5 dB here.

307
00:20:40,710 --> 00:20:47,010
And the ultimate Shannon
limit is over here.

308
00:20:47,010 --> 00:20:52,150
The ultimate Shannon limit for
very low rho, as rho goes to

309
00:20:52,150 --> 00:20:55,840
0, is about minus 1.6 dB.

310
00:20:55,840 --> 00:20:57,630
And we get expressions.

311
00:20:57,630 --> 00:21:00,780
0 dB is the Shannon limit
at rho equals 1.

312
00:21:00,780 --> 00:21:05,570
At rho equals 2, it's
up about 1.8 dB.

313
00:21:05,570 --> 00:21:08,250
Shannon limit for rho equals
2, and so forth.

314
00:21:08,250 --> 00:21:12,390
And anyway, so we see as a
function of rho, we can

315
00:21:12,390 --> 00:21:16,210
measure the gap to capacity at
different probabilities of

316
00:21:16,210 --> 00:21:19,780
error and see how much
coding gain is,

317
00:21:19,780 --> 00:21:20,780
in principle, possible.

318
00:21:20,780 --> 00:21:26,610
And then for a coded system,
we can put that on here.

319
00:21:26,610 --> 00:21:29,980
The effective coding gain
is the distance

320
00:21:29,980 --> 00:21:32,760
between here and here.

321
00:21:32,760 --> 00:21:36,130
At some target probability
of error.

322
00:21:36,130 --> 00:21:39,550
It's going to differ according
to probably of error.

323
00:21:39,550 --> 00:21:46,740
You found a way of getting a
good, rough-cut estimate, at

324
00:21:46,740 --> 00:21:50,630
least for not very complicated
codes called the union bound

325
00:21:50,630 --> 00:21:57,040
estimate for any signal
constellation in any number of

326
00:21:57,040 --> 00:21:58,290
dimensions.

327
00:21:58,290 --> 00:22:04,980
So if we have a signal
constellation A, which

328
00:22:04,980 --> 00:22:10,180
consists of M points in N
dimensions, so forth,

329
00:22:10,180 --> 00:22:16,630
basically found that we could,
in the power-limited regime,

330
00:22:16,630 --> 00:22:22,190
get an approximate expression
from considering pairwise

331
00:22:22,190 --> 00:22:25,400
error probabilities that's
very simple.

332
00:22:25,400 --> 00:22:27,140
And I used this notation.

333
00:22:27,140 --> 00:22:34,300
Q of the square root of some
coding gain of the

334
00:22:34,300 --> 00:22:40,330
constellation times
2 Eb over N_0.

335
00:22:40,330 --> 00:22:45,150
If it's just 2-PAM then the
coding gain becomes 1.

336
00:22:45,150 --> 00:22:52,430
This is the average number
of nearest neighbors per

337
00:22:52,430 --> 00:22:55,810
transmitted bit.

338
00:22:55,810 --> 00:23:00,470
And so the whole thing reduces
to this expression in terms of

339
00:23:00,470 --> 00:23:01,610
couple of parameters.

340
00:23:01,610 --> 00:23:06,610
the principal parameter is the
nominal coding gain, which is

341
00:23:06,610 --> 00:23:13,840
the minimum squared distance of
A over 4 times the energy

342
00:23:13,840 --> 00:23:19,170
per bit of this constellation
A. So we really only need to

343
00:23:19,170 --> 00:23:24,950
know this kind of normalized
measure of goodness of the

344
00:23:24,950 --> 00:23:27,410
constellation.

345
00:23:27,410 --> 00:23:35,810
And K_b of A Is the average
number of nearest neighbors.

346
00:23:35,810 --> 00:23:38,070
I forget what we call it.

347
00:23:38,070 --> 00:23:43,250
What is the numerator here?

348
00:23:43,250 --> 00:23:50,430
K_min of A, which itself is an
average, over the number of

349
00:23:50,430 --> 00:23:56,430
bits that we're actually
sending, which is log2 of the

350
00:23:56,430 --> 00:23:59,690
size of A.

351
00:23:59,690 --> 00:24:03,110
So basically we only need to
know a couple of parameters of

352
00:24:03,110 --> 00:24:04,610
this signal constellation.

353
00:24:04,610 --> 00:24:08,480
Its minimum square distance
is very important.

354
00:24:08,480 --> 00:24:11,890
Energy parameter, which we
choose to make the energy per

355
00:24:11,890 --> 00:24:15,020
bit, or so that we get
this expression.

356
00:24:15,020 --> 00:24:19,600
And the average number of
nearest neighbors per bit that

357
00:24:19,600 --> 00:24:19,877
we transmit.

358
00:24:19,877 --> 00:24:21,127
OK.

359
00:24:21,127 --> 00:24:23,920

360
00:24:23,920 --> 00:24:33,840
And our best example so far is
the tetrahedral constellation,

361
00:24:33,840 --> 00:24:37,760
where we basically
pick every other

362
00:24:37,760 --> 00:24:44,245
point from the 4 simplex.

363
00:24:44,245 --> 00:24:48,160

364
00:24:48,160 --> 00:24:50,690
Maybe I should do that
in a different color.

365
00:24:50,690 --> 00:24:52,636
I don't think that's
a different color.

366
00:24:52,636 --> 00:24:54,750
Nope.

367
00:24:54,750 --> 00:24:55,260
Anyway.

368
00:24:55,260 --> 00:24:57,710
You know this quite
well by now.

369
00:24:57,710 --> 00:25:01,330
And if we do that, we find that
normalizing everything,

370
00:25:01,330 --> 00:25:05,730
this is 4/3 or 1.25 dB.

371
00:25:05,730 --> 00:25:10,400
And every point has three
nearest neighbors, and we're

372
00:25:10,400 --> 00:25:12,330
sending 2 bits, so
this is 3/2.

373
00:25:12,330 --> 00:25:15,710

374
00:25:15,710 --> 00:25:20,020
So then we get this handy dandy
engineering rule to make

375
00:25:20,020 --> 00:25:25,000
a quick plot of the union
bound estimate.

376
00:25:25,000 --> 00:25:27,860
Given that we decided to put
this on a log-log scale to

377
00:25:27,860 --> 00:25:33,340
start with, all we have to do
to plot this expression --

378
00:25:33,340 --> 00:25:42,570
if we're given, as we always
are, the baseline curve, which

379
00:25:42,570 --> 00:25:49,010
is simply Q to the square
root of 2 Eb over N_0.

380
00:25:49,010 --> 00:25:52,150
How do you convert this
curve to this curve

381
00:25:52,150 --> 00:25:53,380
on a log-log plot?

382
00:25:53,380 --> 00:25:57,070
Well, you simply move it to the
left by the coding gain.

383
00:25:57,070 --> 00:26:03,920
And you move it up by the
log of whatever K_b is.

384
00:26:03,920 --> 00:26:08,460
So if the dominant effect is
moving it left, in this case,

385
00:26:08,460 --> 00:26:12,450
by 1.25 dB --

386
00:26:12,450 --> 00:26:15,110
I'm going to wind up getting
about this curve, so I won't

387
00:26:15,110 --> 00:26:15,960
draw it again --

388
00:26:15,960 --> 00:26:22,330
then we move it up by a factor
of 3/2, we developed a rule of

389
00:26:22,330 --> 00:26:26,480
thumb that said a factor of two
is basically going to cost

390
00:26:26,480 --> 00:26:30,230
you about 0.2 dB.

391
00:26:30,230 --> 00:26:31,770
Around ten to the minus five.

392
00:26:31,770 --> 00:26:35,390
This is just based on the slope
of this baseline curve,

393
00:26:35,390 --> 00:26:38,040
as long as we're somewhat
in that region.

394
00:26:38,040 --> 00:26:43,540
So this will cost us about 1/10
of a dB, so we'll get an

395
00:26:43,540 --> 00:26:49,250
effective coding gain
of about 1.15 dB.

396
00:26:49,250 --> 00:26:52,250
So graphically, we take
this curve bodily.

397
00:26:52,250 --> 00:26:58,410
We move it over 1.25 dB,
and we move it up

398
00:26:58,410 --> 00:27:00,420
by a factor of 3/2.

399
00:27:00,420 --> 00:27:02,890
And what we'll find is the
effective coding gain is

400
00:27:02,890 --> 00:27:07,730
thereby reduced to, I estimate,
about 1.15 dB.

401
00:27:07,730 --> 00:27:11,110
And this is all just engineering
rules of thumb.

402
00:27:11,110 --> 00:27:12,830
Nice template.

403
00:27:12,830 --> 00:27:15,570
I sometimes say you should
fill out a copy of this

404
00:27:15,570 --> 00:27:18,100
baseline curve, cut it out, put
it in your wallet for the

405
00:27:18,100 --> 00:27:20,650
duration of this course,
because you'll have the

406
00:27:20,650 --> 00:27:22,220
opportunity to make
this kind of

407
00:27:22,220 --> 00:27:25,150
calculation again and again.

408
00:27:25,150 --> 00:27:25,540
All right.

409
00:27:25,540 --> 00:27:28,780
So that's union bound SNR.

410
00:27:28,780 --> 00:27:31,150
For simple constellations,
the union bound

411
00:27:31,150 --> 00:27:34,480
estimate is very accurate.

412
00:27:34,480 --> 00:27:37,280
So this is a very good way to
proceed, from an engineering

413
00:27:37,280 --> 00:27:38,560
point of view.

414
00:27:38,560 --> 00:27:41,212
We want to write a paper?

415
00:27:41,212 --> 00:27:43,330
You know, it's a little late
to write a paper on the

416
00:27:43,330 --> 00:27:46,270
performance of the four simplex
signal constellations,

417
00:27:46,270 --> 00:27:49,430
but if you wanted to, and you
wanted to have one graph in

418
00:27:49,430 --> 00:27:51,790
that paper, you would
have the graph of --

419
00:27:51,790 --> 00:27:57,290
well, you would actually
probably compute the exact

420
00:27:57,290 --> 00:28:01,020
error of probability, either by
analysis or by Monte Carlo

421
00:28:01,020 --> 00:28:03,150
simulation, you would
put that in there.

422
00:28:03,150 --> 00:28:05,590
But in your first draft of the
paper, you would put in union

423
00:28:05,590 --> 00:28:09,100
bound estimate and you would
find that wasn't far off.

424
00:28:09,100 --> 00:28:11,630

425
00:28:11,630 --> 00:28:12,680
OK.

426
00:28:12,680 --> 00:28:13,830
Any questions on that?

427
00:28:13,830 --> 00:28:19,030
This has basically got
us up to chapter six.

428
00:28:19,030 --> 00:28:26,090

429
00:28:26,090 --> 00:28:35,240
So in chapter six now, which
Ashish got into last time.

430
00:28:35,240 --> 00:28:40,840
This is basically about binary
linear block codes.

431
00:28:40,840 --> 00:28:44,510

432
00:28:44,510 --> 00:28:48,820
And well, we first just
start talking about

433
00:28:48,820 --> 00:28:51,330
binary block codes.

434
00:28:51,330 --> 00:28:55,750
That's what Ashish
did last time.

435
00:28:55,750 --> 00:28:58,350

436
00:28:58,350 --> 00:29:03,310
We basically take 0 and 1
as our binary alphabet.

437
00:29:03,310 --> 00:29:08,000
We take a blocks of length n.

438
00:29:08,000 --> 00:29:08,170
Sorry.

439
00:29:08,170 --> 00:29:12,020
Are we using little
n or big N?

440
00:29:12,020 --> 00:29:15,170
Little n, where n is called
the block plank.

441
00:29:15,170 --> 00:29:23,760
So we take the set of all binary
symbols of length n,

442
00:29:23,760 --> 00:29:31,730
and we're going to convert
this to real n space.

443
00:29:31,730 --> 00:29:33,950
How do we convert it?

444
00:29:33,950 --> 00:29:36,770
Component-wise, by the
standard 2-PAM map.

445
00:29:36,770 --> 00:29:41,660
We map 0 into plus alpha,
1 into minus alpha.

446
00:29:41,660 --> 00:29:46,740
So this maps into plus or
minus alpha to the n.

447
00:29:46,740 --> 00:29:50,680
So the entire universe of
possible code words that we

448
00:29:50,680 --> 00:29:58,000
have is this set of 2 to the
n real n-tuples, which are

449
00:29:58,000 --> 00:30:01,340
simply the vertices of an
n cube of size 2 alpha,

450
00:30:01,340 --> 00:30:02,840
obviously, right?

451
00:30:02,840 --> 00:30:04,390
Just like this.

452
00:30:04,390 --> 00:30:10,320
We have eight possible
vertices in 3-space.

453
00:30:10,320 --> 00:30:12,300
They obviously all have
the same power.

454
00:30:12,300 --> 00:30:17,810
They all lie on the surface of
a sphere of squared radius n

455
00:30:17,810 --> 00:30:20,010
alpha squared.

456
00:30:20,010 --> 00:30:22,310
So they're not only the vertices
of a cube, they're

457
00:30:22,310 --> 00:30:26,810
vertices that are spread on
an equal energy sphere.

458
00:30:26,810 --> 00:30:32,480
And the whole idea is that our
code is going to be some

459
00:30:32,480 --> 00:30:36,870
subset of this, and the code
will map under the same map,

460
00:30:36,870 --> 00:30:43,060
which we call S, into
some subset of the

461
00:30:43,060 --> 00:30:45,610
vertices of the n-cube.

462
00:30:45,610 --> 00:30:45,990
OK?

463
00:30:45,990 --> 00:30:50,820
And again, our favorite example
is the tetrahedron.

464
00:30:50,820 --> 00:30:57,950
For instance, if we take the
code as being 0, 0, 0, 0, 1,

465
00:30:57,950 --> 00:31:06,150
1, 1, 0, 1 1, 1, 0, those for
binary three-tuples, this maps

466
00:31:06,150 --> 00:31:10,310
into T, the tetrahedron.

467
00:31:10,310 --> 00:31:11,656
OK?

468
00:31:11,656 --> 00:31:15,230
Well, we get this signal
structure, which we've already

469
00:31:15,230 --> 00:31:16,230
found the coding gain.

470
00:31:16,230 --> 00:31:18,180
It has a little bit
of coding gain.

471
00:31:18,180 --> 00:31:22,090
We actually accomplished
something.

472
00:31:22,090 --> 00:31:24,160
All right.

473
00:31:24,160 --> 00:31:30,780
So that's the basic idea that
we go through in 6.1.

474
00:31:30,780 --> 00:31:33,230
That's our favorite example.

475
00:31:33,230 --> 00:31:37,440
And Ashish also shows you that,
you know, you might

476
00:31:37,440 --> 00:31:41,040
think this is an awfully
restricted way of designing

477
00:31:41,040 --> 00:31:43,260
constellations.

478
00:31:43,260 --> 00:31:47,120
But when we're talking about low
spectral efficiencies, by

479
00:31:47,120 --> 00:31:50,960
going through the capacity
calculation, we can assure

480
00:31:50,960 --> 00:31:55,310
ourselves that in principle,
this is not going to be very

481
00:31:55,310 --> 00:31:57,070
sub-optimal for it.

482
00:31:57,070 --> 00:32:00,930
Capacity is about the regime
where n gets very large for

483
00:32:00,930 --> 00:32:02,970
very long block codes.

484
00:32:02,970 --> 00:32:06,500
We don't lose much in potential
coding gain, or in

485
00:32:06,500 --> 00:32:10,975
the Shannon limit, equivalently,
by restricting

486
00:32:10,975 --> 00:32:15,170
the input output input alphabet
to be just these two

487
00:32:15,170 --> 00:32:18,230
numbers, plus or minus alpha,
I should say, rather than

488
00:32:18,230 --> 00:32:24,310
using the whole real line as
an input, as long as the

489
00:32:24,310 --> 00:32:35,100
nominal spectral efficiency is
less than or equal to one bit

490
00:32:35,100 --> 00:32:37,840
per two dimensions.

491
00:32:37,840 --> 00:32:41,180
And the exact numbers --

492
00:32:41,180 --> 00:32:47,780
at rho equals 1, you lose about
0.2 dB, in principle,

493
00:32:47,780 --> 00:32:51,720
using the Shannon limit
as your guide.

494
00:32:51,720 --> 00:32:56,290
And for lower rho, it
just goes to 0.

495
00:32:56,290 --> 00:32:59,260
And you did this last time.

496
00:32:59,260 --> 00:32:59,650
OK.

497
00:32:59,650 --> 00:33:04,610
So it's a very reasonable, and
obviously attractive from an

498
00:33:04,610 --> 00:33:08,170
implementation point of view,
way of designing signal

499
00:33:08,170 --> 00:33:09,790
constellations.

500
00:33:09,790 --> 00:33:12,060
And again, this is basically all
we're going to be talking

501
00:33:12,060 --> 00:33:15,060
about for the majority of
the course, is signal

502
00:33:15,060 --> 00:33:16,440
constellations like this.

503
00:33:16,440 --> 00:33:19,530
But of course as we get to codes
that are thousands of

504
00:33:19,530 --> 00:33:22,960
bits long, or perhaps even
infinitely long, as in the

505
00:33:22,960 --> 00:33:28,820
case of convolutional codes and
trellis codes, sometimes

506
00:33:28,820 --> 00:33:31,390
you forget that we're really
talking about just putting

507
00:33:31,390 --> 00:33:35,830
points in Euclidian
signal space.

508
00:33:35,830 --> 00:33:39,500
Because we're going to be very
abstracted back into the

509
00:33:39,500 --> 00:33:42,320
binary domain.

510
00:33:42,320 --> 00:33:46,680
But in this course, we're always
thinking of codes as

511
00:33:46,680 --> 00:33:49,103
means of designing signal
constellations.

512
00:33:49,103 --> 00:33:53,630

513
00:33:53,630 --> 00:33:57,940
Of course, codes are used far
more widely than just for

514
00:33:57,940 --> 00:34:01,370
signaling over the additive
white Gaussian noise channel.

515
00:34:01,370 --> 00:34:08,540
I've sort of packaged this
course as a search to get to

516
00:34:08,540 --> 00:34:10,070
capacity, we have added
the additive white

517
00:34:10,070 --> 00:34:11,150
Gaussian noise channel.

518
00:34:11,150 --> 00:34:13,580
First of all because
this corresponds

519
00:34:13,580 --> 00:34:16,449
very closely to history.

520
00:34:16,449 --> 00:34:19,830
Within this package, we can
talk about all of the

521
00:34:19,830 --> 00:34:22,380
principal classes of codes that
have been developed to

522
00:34:22,380 --> 00:34:26,355
date, and we can compare them
in some performance terms.

523
00:34:26,355 --> 00:34:29,090

524
00:34:29,090 --> 00:34:31,860
How close do they get to
capacity on the additive white

525
00:34:31,860 --> 00:34:33,330
Gaussian noise channel.

526
00:34:33,330 --> 00:34:38,100
So you get most of what you
would get if you took a

527
00:34:38,100 --> 00:34:42,449
communications-free view
of coding theory.

528
00:34:42,449 --> 00:34:44,370
You know, people are interested
in codes for

529
00:34:44,370 --> 00:34:50,020
computer memories, for
God knows what,

530
00:34:50,020 --> 00:34:51,190
lots of other things.

531
00:34:51,190 --> 00:34:57,500
And for many of these other
applications, you are going to

532
00:34:57,500 --> 00:34:59,320
be interested in the same
class of codes.

533
00:34:59,320 --> 00:35:03,120
Basically, you're going to want
to maximize the distance

534
00:35:03,120 --> 00:35:07,030
between code words for a given
rate, which has to do with the

535
00:35:07,030 --> 00:35:09,300
size of the code.

536
00:35:09,300 --> 00:35:14,270
And so you're going to be
interested in the same codes.

537
00:35:14,270 --> 00:35:16,930
Putting it in the framework of
getting to capacity on the

538
00:35:16,930 --> 00:35:21,060
additive white Gaussian noise
channel gives a motivation,

539
00:35:21,060 --> 00:35:24,060
gives a very nice story, because
over 50 years, we were

540
00:35:24,060 --> 00:35:28,600
able to get to capacity,
and gives it a real

541
00:35:28,600 --> 00:35:30,240
communications flavor.

542
00:35:30,240 --> 00:35:33,360
Some of you, I'm sure, are here
without any interest in

543
00:35:33,360 --> 00:35:34,560
communications whatsoever.

544
00:35:34,560 --> 00:35:36,360
You simply want to know
about coding.

545
00:35:36,360 --> 00:35:38,830
You will still get that story,
but you'll get it

546
00:35:38,830 --> 00:35:41,020
in this nice package.

547
00:35:41,020 --> 00:35:44,840
That's why I do it this way.

548
00:35:44,840 --> 00:35:45,820
OK.

549
00:35:45,820 --> 00:35:47,490
I'm about to get
into new stuff.

550
00:35:47,490 --> 00:35:49,660
End of review.

551
00:35:49,660 --> 00:35:52,820
Any questions?

552
00:35:52,820 --> 00:35:56,000
So you must have done
a great job.

553
00:35:56,000 --> 00:35:59,120
Everyone understands
perfectly.

554
00:35:59,120 --> 00:35:59,740
All right.

555
00:35:59,740 --> 00:36:03,350
So now let's talk about,
as I said, binary

556
00:36:03,350 --> 00:36:06,060
linear block codes.

557
00:36:06,060 --> 00:36:11,220
When you see the word "linear,"
that's a signal that

558
00:36:11,220 --> 00:36:12,680
there's some algebra ahead.

559
00:36:12,680 --> 00:36:18,250
And so this is the very first
point at which we get into

560
00:36:18,250 --> 00:36:22,170
what's called algebraic
coding theory.

561
00:36:22,170 --> 00:36:24,350
The algebra will be extremely
simple at this

562
00:36:24,350 --> 00:36:25,660
point, not to worry.

563
00:36:25,660 --> 00:36:28,250

564
00:36:28,250 --> 00:36:32,730
And what are we doing here?

565
00:36:32,730 --> 00:36:36,520

566
00:36:36,520 --> 00:36:40,740
First thing we do is to identify
0 and 1 with the

567
00:36:40,740 --> 00:36:45,810
binary field, which I'm always
going to write as F2.

568
00:36:45,810 --> 00:36:51,260
The older way of writing this
is GF(2), for Galois field

569
00:36:51,260 --> 00:36:52,520
with two elements.

570
00:36:52,520 --> 00:36:54,850
They mean exactly
the same thing.

571
00:36:54,850 --> 00:36:59,430
Nowadays most people
write just F2.

572
00:36:59,430 --> 00:37:03,570
Now we have [UNINTELLIGIBLE],
we can write this blackboard

573
00:37:03,570 --> 00:37:06,320
F.

574
00:37:06,320 --> 00:37:09,230
And OK.

575
00:37:09,230 --> 00:37:09,960
Step one.

576
00:37:09,960 --> 00:37:12,540
We've identified our alphabet
with a field.

577
00:37:12,540 --> 00:37:16,840

578
00:37:16,840 --> 00:37:20,450
So algebraically,
this is a field.

579
00:37:20,450 --> 00:37:23,380
Some of you know exactly
what I mean by that.

580
00:37:23,380 --> 00:37:24,540
Others don't.

581
00:37:24,540 --> 00:37:26,060
We'll come back to this again.

582
00:37:26,060 --> 00:37:29,380
Informally, I would say a field
is simply something

583
00:37:29,380 --> 00:37:32,970
where you can add, subtract,
multiply, or divide.

584
00:37:32,970 --> 00:37:36,825
Our best examples of that before
now have been the real

585
00:37:36,825 --> 00:37:39,710
and complex fields.

586
00:37:39,710 --> 00:37:42,560
There is a more formal
definition of that.

587
00:37:42,560 --> 00:37:45,740
In this case, we have
only two elements.

588
00:37:45,740 --> 00:37:52,840
So let me just write down the
tables, which you all know,

589
00:37:52,840 --> 00:37:55,500
regardless of your background.

590
00:37:55,500 --> 00:37:57,690
What's the addition table
for this field?

591
00:37:57,690 --> 00:38:01,610
Well, 0 is the additive
identity.

592
00:38:01,610 --> 00:38:09,100
So we know that 0 added to
anything gives itself, so that

593
00:38:09,100 --> 00:38:11,615
gives us three of the entries
of this table.

594
00:38:11,615 --> 00:38:14,540

595
00:38:14,540 --> 00:38:16,550
What do we put down here?

596
00:38:16,550 --> 00:38:20,970
There's really only one choice
to satisfy one of the axioms

597
00:38:20,970 --> 00:38:27,260
of the field, which is that
under addition, the field must

598
00:38:27,260 --> 00:38:29,230
form a group.

599
00:38:29,230 --> 00:38:32,140
In particular, that means that
all elements are invertible.

600
00:38:32,140 --> 00:38:36,320
That means that each row or
column has to be a permutation

601
00:38:36,320 --> 00:38:37,540
of the group elements.

602
00:38:37,540 --> 00:38:40,980
And so the only possibility
here is to put in a 0.

603
00:38:40,980 --> 00:38:46,270
And well, we are forced, if
we're going to make 0 and 1

604
00:38:46,270 --> 00:38:50,600
into a field to find an addition
table which is the

605
00:38:50,600 --> 00:38:52,790
table of mod2 addition.

606
00:38:52,790 --> 00:38:55,690
You've had this stated
as an axiom before.

607
00:38:55,690 --> 00:39:00,640
You can derive it just from the
fact that 0 needs to be

608
00:39:00,640 --> 00:39:05,000
the additive identity, and then
we need to put a 0 in

609
00:39:05,000 --> 00:39:06,885
here in order to get
invertibility.

610
00:39:06,885 --> 00:39:12,490

611
00:39:12,490 --> 00:39:14,120
Under multiplication.

612
00:39:14,120 --> 00:39:16,340
What is the multiplication
table?

613
00:39:16,340 --> 00:39:21,180
Well, the additive identity
is also a nullifier under

614
00:39:21,180 --> 00:39:22,820
multiplication in any field.

615
00:39:22,820 --> 00:39:26,150
So 0 times anything
is equal to 0.

616
00:39:26,150 --> 00:39:29,410
1 times anything is
equal to itself.

617
00:39:29,410 --> 00:39:34,000
So that completely determines
the multiplication table.

618
00:39:34,000 --> 00:39:37,870
Again, just the table of
mod2 multiplication.

619
00:39:37,870 --> 00:39:41,800
So if I'd done this
axiomatically, I would have

620
00:39:41,800 --> 00:39:43,410
given you the axioms of field.

621
00:39:43,410 --> 00:39:47,410
Then I would show that under
this binary addition

622
00:39:47,410 --> 00:39:50,800
operation, this multiplication
operation,

623
00:39:50,800 --> 00:39:52,780
we satisfy the axioms.

624
00:39:52,780 --> 00:39:54,900
I'll do that as we get
into chapter seven.

625
00:39:54,900 --> 00:39:57,630

626
00:39:57,630 --> 00:39:58,880
OK.

627
00:39:58,880 --> 00:40:00,550

628
00:40:00,550 --> 00:40:12,300
So now we have 0 1 to the n,
n-tuples, binary n-tuples, we

629
00:40:12,300 --> 00:40:17,570
will now regard as n-tuples
of field elements, F2.

630
00:40:17,570 --> 00:40:20,890

631
00:40:20,890 --> 00:40:29,648
And these will be regarded as
vectors in a vector space.

632
00:40:29,648 --> 00:40:35,330
Well, I'll just say that F2 to
the n is a vector space, which

633
00:40:35,330 --> 00:40:37,990
clearly has 2 to
the n elements.

634
00:40:37,990 --> 00:40:39,290
Now again, informally.

635
00:40:39,290 --> 00:40:41,320
What's a vector space?

636
00:40:41,320 --> 00:40:46,450
A vector space is always
over a given field.

637
00:40:46,450 --> 00:40:47,890
In this case, it's going
to be over the

638
00:40:47,890 --> 00:40:49,150
binary field, of course.

639
00:40:49,150 --> 00:40:51,740
F2.

640
00:40:51,740 --> 00:40:54,720
The given field is
called a scalar.

641
00:40:54,720 --> 00:40:57,670
Just like vector space over
the reals, the scalars are

642
00:40:57,670 --> 00:40:58,760
real numbers.

643
00:40:58,760 --> 00:41:02,910
Here the scalars are
elements of F2.

644
00:41:02,910 --> 00:41:07,450
And what do we have to have to
make something algebraically a

645
00:41:07,450 --> 00:41:08,400
vector space?

646
00:41:08,400 --> 00:41:12,930
We have to have that the
addition of two vectors is

647
00:41:12,930 --> 00:41:19,310
well-defined and gives another
vector, and that the

648
00:41:19,310 --> 00:41:23,420
multiplication of a vector by
a scalar is well-defined and

649
00:41:23,420 --> 00:41:27,120
gives another vector in
our vector space.

650
00:41:27,120 --> 00:41:28,370
All right?

651
00:41:28,370 --> 00:41:30,830

652
00:41:30,830 --> 00:41:31,500
OK.

653
00:41:31,500 --> 00:41:35,130
So how are we going to define
that to addition?

654
00:41:35,130 --> 00:41:38,600
If we want to add
two n-tuples --

655
00:41:38,600 --> 00:41:40,940
again, you aren't going to see
anything here that you haven't

656
00:41:40,940 --> 00:41:43,400
already seen in some
other context.

657
00:41:43,400 --> 00:41:43,860
What do we do?

658
00:41:43,860 --> 00:41:49,030
We add them component-wise,
using the component-wise rules

659
00:41:49,030 --> 00:41:51,630
of field addition.

660
00:41:51,630 --> 00:41:51,730
OK.

661
00:41:51,730 --> 00:41:55,380
So we just add two
vector n-tuples,

662
00:41:55,380 --> 00:41:56,910
component by component.

663
00:41:56,910 --> 00:42:00,570
We obviously get some result,
which is itself a binary

664
00:42:00,570 --> 00:42:03,290
vector or an F2 vector.

665
00:42:03,290 --> 00:42:05,220
No problem there.

666
00:42:05,220 --> 00:42:08,050
Except that --

667
00:42:08,050 --> 00:42:09,620
well, all right.

668
00:42:09,620 --> 00:42:11,980
As long as we're talking about
all possible n-tuples, the

669
00:42:11,980 --> 00:42:14,160
result is certainly in the
vector space, right?

670
00:42:14,160 --> 00:42:17,530
We add two binary n-tuples,
we get a binary n-tuple.

671
00:42:17,530 --> 00:42:20,320
So the result is
in F2 to the n.

672
00:42:20,320 --> 00:42:24,450
This is going to be the key test
when we get to subspaces

673
00:42:24,450 --> 00:42:27,990
of F2 to the n.

674
00:42:27,990 --> 00:42:28,035
OK.

675
00:42:28,035 --> 00:42:31,470
And multiplication
is even easier.

676
00:42:31,470 --> 00:42:34,100
How do we define multiplication
by scalars?

677
00:42:34,100 --> 00:42:35,560
Well, we only have
two scalars --

678
00:42:35,560 --> 00:42:37,570
0 and 1.

679
00:42:37,570 --> 00:42:45,530
So 0 times any vector is going
to equal the all 0 vector.

680
00:42:45,530 --> 00:42:47,770
Again, you can view that
as just component-wise

681
00:42:47,770 --> 00:42:51,480
multiplication of everything
by 0, and since 0 times

682
00:42:51,480 --> 00:42:53,270
anything equals 0, we're
always going

683
00:42:53,270 --> 00:42:55,400
to get the 0 vector.

684
00:42:55,400 --> 00:42:57,150
All right?

685
00:42:57,150 --> 00:43:02,210
So is the 0 vector in
the vector space?

686
00:43:02,210 --> 00:43:02,800
Well, yes.

687
00:43:02,800 --> 00:43:05,130
If we're talking about several
n-tuples, it of

688
00:43:05,130 --> 00:43:06,770
course always is.

689
00:43:06,770 --> 00:43:12,610
And one times anything, again,
we can just do this

690
00:43:12,610 --> 00:43:14,970
component-wise, and it
just gives itself.

691
00:43:14,970 --> 00:43:17,480

692
00:43:17,480 --> 00:43:18,560
Trivially.

693
00:43:18,560 --> 00:43:21,950
So since this was a vector in
the vector space, this is

694
00:43:21,950 --> 00:43:25,660
certainly a vector in
the vector space.

695
00:43:25,660 --> 00:43:26,080
OK.

696
00:43:26,080 --> 00:43:29,745
This seems pretty
trivial so far.

697
00:43:29,745 --> 00:43:35,750
But what's a binary
linear block code?

698
00:43:35,750 --> 00:43:40,620
Again, focusing on the
linear, is a --

699
00:43:40,620 --> 00:43:43,400
now I'll give a formal
definition.

700
00:43:43,400 --> 00:43:51,660
it's a subspace of F2
to the n for some n

701
00:43:51,660 --> 00:43:52,910
called the block length.

702
00:43:52,910 --> 00:43:55,430

703
00:43:55,430 --> 00:43:56,630
All right.

704
00:43:56,630 --> 00:43:58,700
What do I mean when
I say a subspace?

705
00:43:58,700 --> 00:44:03,080
I mean subsets of the elements
of a vector space that itself

706
00:44:03,080 --> 00:44:05,010
forms a vector space.

707
00:44:05,010 --> 00:44:11,110
So in this case when I
say subset, I mean a

708
00:44:11,110 --> 00:44:14,270
set of binary n-tuples.

709
00:44:14,270 --> 00:44:16,280
OK?

710
00:44:16,280 --> 00:44:18,460
That itself forms
a vector space.

711
00:44:18,460 --> 00:44:18,810
OK.

712
00:44:18,810 --> 00:44:20,570
What are the components
of that?

713
00:44:20,570 --> 00:44:24,540
To check that it forms a vector
space, let's see.

714
00:44:24,540 --> 00:44:30,032
Multiplication by scalars is,
again, easy to check.

715
00:44:30,032 --> 00:44:34,110
If it's going to be a subspace,
then the all 0 --

716
00:44:34,110 --> 00:44:48,140
so it has to contain the all 0
vector in order that when I

717
00:44:48,140 --> 00:44:50,860
multiply by the scalar
0, I get another

718
00:44:50,860 --> 00:44:52,110
element of this subspace.

719
00:44:52,110 --> 00:44:55,260

720
00:44:55,260 --> 00:44:59,070
Multiplication by 1 is always
trivially satisfied.

721
00:44:59,070 --> 00:45:01,830
If I start off with a set, I
multiply by 1, I'm going to

722
00:45:01,830 --> 00:45:04,960
get the same set.

723
00:45:04,960 --> 00:45:14,120
So let's check whether the
elements of a subspace are

724
00:45:14,120 --> 00:45:17,760
closed under vector addition.

725
00:45:17,760 --> 00:45:19,140
What do I mean by that?

726
00:45:19,140 --> 00:45:24,270
I mean if you add two elements
of the of the subspace

727
00:45:24,270 --> 00:45:28,440
together, you get another
element of the subspace.

728
00:45:28,440 --> 00:45:32,255
That's the key property
to check.

729
00:45:32,255 --> 00:45:36,650

730
00:45:36,650 --> 00:45:40,670
Key property -- we can
write that as closure

731
00:45:40,670 --> 00:45:42,995
under vector addition.

732
00:45:42,995 --> 00:45:47,900

733
00:45:47,900 --> 00:45:52,280
Which is also called
the group property.

734
00:45:52,280 --> 00:45:56,460
It means that just under
addition, under vector

735
00:45:56,460 --> 00:46:00,090
addition, the set of elements
that you have forms a group.

736
00:46:00,090 --> 00:46:01,850
You add any two elements,
you get another

737
00:46:01,850 --> 00:46:03,100
element of the subset.

738
00:46:03,100 --> 00:46:06,350

739
00:46:06,350 --> 00:46:12,030
The example is our favorite
example so far.

740
00:46:12,030 --> 00:46:18,420
Let's take this little code,
and I'm going to ask.

741
00:46:18,420 --> 00:46:24,150
Is that a subspace of
F2 to the three?

742
00:46:24,150 --> 00:46:35,580
So does this equal subspace
of the set of all binary

743
00:46:35,580 --> 00:46:36,830
three-tuples?

744
00:46:36,830 --> 00:46:40,620

745
00:46:40,620 --> 00:46:46,880
Anyone care to hazard a guess
whether it is or isn't?

746
00:46:46,880 --> 00:46:47,810
AUDIENCE: It is.

747
00:46:47,810 --> 00:46:48,790
PROFESSOR: It is?

748
00:46:48,790 --> 00:46:50,040
Why?

749
00:46:50,040 --> 00:46:53,012

750
00:46:53,012 --> 00:46:54,380
AUDIENCE: It has the
all 0 vector.

751
00:46:54,380 --> 00:46:58,200
PROFESSOR: It has the all
0 vector, first of all.

752
00:46:58,200 --> 00:47:00,480
Good.

753
00:47:00,480 --> 00:47:01,730
AUDIENCE: [INAUDIBLE]

754
00:47:01,730 --> 00:47:04,170

755
00:47:04,170 --> 00:47:07,588
PROFESSOR: And it's closed
under addition.

756
00:47:07,588 --> 00:47:11,470
Now how might we see that?

757
00:47:11,470 --> 00:47:14,820
You could, of course, just
take all pair-wise --

758
00:47:14,820 --> 00:47:17,400
you could form the addition
table of these four elements,

759
00:47:17,400 --> 00:47:20,130
and you would find that you
always get another one of

760
00:47:20,130 --> 00:47:20,690
these elements.

761
00:47:20,690 --> 00:47:26,240
For instance, 0, 1, 1 plus 1,
0, 1, is equal to 1, 1, 0.

762
00:47:26,240 --> 00:47:31,150
In fact, you easily see that you
take any two of these, add

763
00:47:31,150 --> 00:47:33,155
them together, you get
the third one.

764
00:47:33,155 --> 00:47:37,840
If you call this a, b, and c,
a plus b plus c equals 0,

765
00:47:37,840 --> 00:47:40,460
addition is the same as
subtraction, because we're in

766
00:47:40,460 --> 00:47:42,460
a binary field.

767
00:47:42,460 --> 00:47:46,620
So that means that a plus b
equals c, a equals b plus c, c

768
00:47:46,620 --> 00:47:50,820
equals b plus a, whatever
you like.

769
00:47:50,820 --> 00:47:55,000
And of course, if you add 0 to
anything, it's trivially

770
00:47:55,000 --> 00:47:56,250
closed under that.

771
00:47:56,250 --> 00:47:59,090

772
00:47:59,090 --> 00:47:59,580
All right.

773
00:47:59,580 --> 00:48:01,060
So it is.

774
00:48:01,060 --> 00:48:02,370
It satisfies --

775
00:48:02,370 --> 00:48:04,320
it's all you've got to check.

776
00:48:04,320 --> 00:48:09,415

777
00:48:09,415 --> 00:48:13,430
A more abstract proof of this
would be, this is the set of

778
00:48:13,430 --> 00:48:16,360
all even-weight three-tuples.

779
00:48:16,360 --> 00:48:19,370
If I add even to even, I'm
going to get even.

780
00:48:19,370 --> 00:48:21,440
So of course my result is
going to be another

781
00:48:21,440 --> 00:48:24,540
even-weight three-tuple,
therefore in the set.

782
00:48:24,540 --> 00:48:26,130
That's the more algebraic
proof.

783
00:48:26,130 --> 00:48:29,560

784
00:48:29,560 --> 00:48:31,760
All right.

785
00:48:31,760 --> 00:48:36,140
Suppose I just add 0, 0, 1
to all of these things.

786
00:48:36,140 --> 00:48:38,470
I'll get the set of all
odd-weight n-tuples.

787
00:48:38,470 --> 00:48:41,520

788
00:48:41,520 --> 00:48:43,680
Add any odd-weight
n-tuple to this.

789
00:48:43,680 --> 00:48:46,800
Let me take the C prime,
which is the set of

790
00:48:46,800 --> 00:48:48,050
all odd-weight n-tuples.

791
00:48:48,050 --> 00:48:50,140

792
00:48:50,140 --> 00:48:52,195
Is that a vector space?

793
00:48:52,195 --> 00:48:54,950

794
00:48:54,950 --> 00:48:57,360
It doesn't have 0, and in fact,
it's not even closed

795
00:48:57,360 --> 00:48:59,920
under vector addition.

796
00:48:59,920 --> 00:49:00,230
All right.

797
00:49:00,230 --> 00:49:06,060
If I take in C double prime is
equal to 0, 0, 0 0, 1, 1, 1,

798
00:49:06,060 --> 00:49:10,135
0, 1 and I stop there,
is that a subspace?

799
00:49:10,135 --> 00:49:13,120

800
00:49:13,120 --> 00:49:13,390
No.

801
00:49:13,390 --> 00:49:15,850
Because?

802
00:49:15,850 --> 00:49:17,530
Not closed.

803
00:49:17,530 --> 00:49:21,000
For instance, if I add these
two together, I would get

804
00:49:21,000 --> 00:49:23,670
that, and that's missing.

805
00:49:23,670 --> 00:49:24,040
OK.

806
00:49:24,040 --> 00:49:31,080
So actually, everything is
much simpler when we're

807
00:49:31,080 --> 00:49:32,640
talking about finite fields.

808
00:49:32,640 --> 00:49:35,820
All the finite dimensional
vector spaces consist of a

809
00:49:35,820 --> 00:49:38,140
finite number of elements.

810
00:49:38,140 --> 00:49:42,310
It's easier than real and
complex vector spaces.

811
00:49:42,310 --> 00:49:46,856
There's no analysis involved.

812
00:49:46,856 --> 00:49:47,430
So forth.

813
00:49:47,430 --> 00:49:47,960
All right.

814
00:49:47,960 --> 00:49:52,960
So a binary linear block
code is in a subspace

815
00:49:52,960 --> 00:49:55,630
of F2 to the n.

816
00:49:55,630 --> 00:49:59,430
What are some of the key
algebraic facts we know about

817
00:49:59,430 --> 00:50:06,460
vector spaces from our study
of linear algebra, which I

818
00:50:06,460 --> 00:50:11,380
assume all of you have had
in some form or another?

819
00:50:11,380 --> 00:50:14,210
What's a key algebraic property
of a vector space?

820
00:50:14,210 --> 00:50:18,250
What's the very first
property?

821
00:50:18,250 --> 00:50:20,894
All vector spaces have a --

822
00:50:20,894 --> 00:50:23,820
AUDIENCE: [INAUDIBLE]

823
00:50:23,820 --> 00:50:25,080
PROFESSOR: Norm?

824
00:50:25,080 --> 00:50:26,410
No.

825
00:50:26,410 --> 00:50:27,250
Dimension.

826
00:50:27,250 --> 00:50:30,710
Dimension, that's
where I'm going.

827
00:50:30,710 --> 00:50:33,484
What's the significance
of dimension?

828
00:50:33,484 --> 00:50:34,734
AUDIENCE: [INAUDIBLE]

829
00:50:34,734 --> 00:50:36,860

830
00:50:36,860 --> 00:50:40,410
PROFESSOR: The definition of
dimension is the number of

831
00:50:40,410 --> 00:50:42,750
generators in any basis.

832
00:50:42,750 --> 00:50:45,010
So we're talking about
generators of the vector

833
00:50:45,010 --> 00:50:49,840
space, or a set of generators
which form a basis.

834
00:50:49,840 --> 00:50:53,600
If you think we have the same
properties here in the case of

835
00:50:53,600 --> 00:51:01,310
vector spaces over finite
fields, well, we probably do.

836
00:51:01,310 --> 00:51:02,970
But let's see how
it works out.

837
00:51:02,970 --> 00:51:05,620
So we're talking about
things like

838
00:51:05,620 --> 00:51:10,930
generators, basis, dimension.

839
00:51:10,930 --> 00:51:16,840
These are all closely
interlinked properties.

840
00:51:16,840 --> 00:51:20,660
Again, the fact that everything
is finite here

841
00:51:20,660 --> 00:51:24,840
gives us very elementary
ways of addressing

842
00:51:24,840 --> 00:51:27,510
all of these concepts.

843
00:51:27,510 --> 00:51:29,300
We don't have any
geometry yet.

844
00:51:29,300 --> 00:51:30,290
We don't have norms.

845
00:51:30,290 --> 00:51:31,310
We don't have distances.

846
00:51:31,310 --> 00:51:32,260
We don't have angles.

847
00:51:32,260 --> 00:51:34,300
We'll talk about that
in a minute.

848
00:51:34,300 --> 00:51:38,940
Here we just have a set that
basically has these two

849
00:51:38,940 --> 00:51:39,530
properties.

850
00:51:39,530 --> 00:51:41,890
It contains the all-0 vector,
and it's closed

851
00:51:41,890 --> 00:51:42,745
as the group property.

852
00:51:42,745 --> 00:51:46,280
It's closed under
vector addition.

853
00:51:46,280 --> 00:51:46,860
All right.

854
00:51:46,860 --> 00:51:56,530
So the first property is that
the all-0 vector is always in

855
00:51:56,530 --> 00:52:02,080
the subspace, which I'll
represent by C, meaning code.

856
00:52:02,080 --> 00:52:06,340
So when I talk about a code
now, I'm talking about a

857
00:52:06,340 --> 00:52:09,410
binary linear block code,
which by definition is a

858
00:52:09,410 --> 00:52:13,360
vector space, a subspace
of F2 to the n, where

859
00:52:13,360 --> 00:52:16,050
n is the code length.

860
00:52:16,050 --> 00:52:16,430
All right.

861
00:52:16,430 --> 00:52:19,700
Let me try to find a set of
generators for the code.

862
00:52:19,700 --> 00:52:22,320

863
00:52:22,320 --> 00:52:22,546
All right?

864
00:52:22,546 --> 00:52:28,040
If somebody gives me a code,
they say, this is a binary

865
00:52:28,040 --> 00:52:29,930
linear block code.

866
00:52:29,930 --> 00:52:33,530
Let me see if I can find a
set of generators for it.

867
00:52:33,530 --> 00:52:37,180
If I find three generators,
then I'll know the

868
00:52:37,180 --> 00:52:39,280
dimension is three.

869
00:52:39,280 --> 00:52:40,700
That's basically where
I'm going.

870
00:52:40,700 --> 00:52:44,440
I'll state this a little bit
more formally as we go ahead.

871
00:52:44,440 --> 00:52:46,090
So suppose I'm given a code.

872
00:52:46,090 --> 00:52:49,710
I know it's a binary linear
block code, so I know it has

873
00:52:49,710 --> 00:52:52,970
the all-0 element.

874
00:52:52,970 --> 00:52:56,500
So how might I go about finding
a set of generators?

875
00:52:56,500 --> 00:52:59,410

876
00:52:59,410 --> 00:53:01,170
Let's just take a greedy
algorithm.

877
00:53:01,170 --> 00:53:02,420
All right?

878
00:53:02,420 --> 00:53:05,320

879
00:53:05,320 --> 00:53:08,060
Suppose the code contains
only the all-0 vector.

880
00:53:08,060 --> 00:53:09,575
Is that a subspace?

881
00:53:09,575 --> 00:53:12,250

882
00:53:12,250 --> 00:53:15,410
What's its dimension?

883
00:53:15,410 --> 00:53:15,540
0.

884
00:53:15,540 --> 00:53:16,790
All right?

885
00:53:16,790 --> 00:53:18,900

886
00:53:18,900 --> 00:53:22,260
So that's a very trivial vector
space, but it's a

887
00:53:22,260 --> 00:53:23,210
vector space.

888
00:53:23,210 --> 00:53:27,120
Satisfies the axioms.

889
00:53:27,120 --> 00:53:29,890
Suppose it is not the
trivial code.

890
00:53:29,890 --> 00:53:32,560
That means it has more than
the all-0 vector.

891
00:53:32,560 --> 00:53:38,330
So I take as my first generator
any non-zero vector.

892
00:53:38,330 --> 00:53:42,940

893
00:53:42,940 --> 00:53:43,410
OK?

894
00:53:43,410 --> 00:53:46,940
I can always do that.

895
00:53:46,940 --> 00:53:49,510
Don't have the axiom of choice
involved here, because

896
00:53:49,510 --> 00:53:51,390
everything is finite.

897
00:53:51,390 --> 00:53:54,930
So I'm going to take g1 to
be any non-zero vector.

898
00:53:54,930 --> 00:53:57,020
Now I've got a generator.

899
00:53:57,020 --> 00:54:06,295
And how many code words
does it generate?

900
00:54:06,295 --> 00:54:10,510

901
00:54:10,510 --> 00:54:14,150
I want to take the set of all
binary linear combinations of

902
00:54:14,150 --> 00:54:16,980
all the generators that
I have so far.

903
00:54:16,980 --> 00:54:19,990
At this point, the binary linear
combinations are 0

904
00:54:19,990 --> 00:54:25,400
times g1 and 1 times g1 And that
just gives me this word

905
00:54:25,400 --> 00:54:26,650
and this word.

906
00:54:26,650 --> 00:54:29,620
So now I have counted for two
words with one generator.

907
00:54:29,620 --> 00:54:32,480

908
00:54:32,480 --> 00:54:34,040
Could it be that that's
the whole code?

909
00:54:34,040 --> 00:54:36,990

910
00:54:36,990 --> 00:54:39,100
Sure.

911
00:54:39,100 --> 00:54:43,460
The all-0 vector and any
non-zero vector together form

912
00:54:43,460 --> 00:54:46,225
a one-dimensional subspace.

913
00:54:46,225 --> 00:54:49,670

914
00:54:49,670 --> 00:54:51,050
That's all you can get
from one dimension.

915
00:54:51,050 --> 00:54:53,420
So I could be finished
here now.

916
00:54:53,420 --> 00:54:55,870
But if I'm not finished, there's
still more code words

917
00:54:55,870 --> 00:54:57,670
that I haven't accounted for.

918
00:54:57,670 --> 00:55:01,580
Then I greedily pick
a second generator.

919
00:55:01,580 --> 00:55:15,180
So this is now, let's say, any
vector not generated by g1.

920
00:55:15,180 --> 00:55:20,740

921
00:55:20,740 --> 00:55:22,700
So I have a branch here.

922
00:55:22,700 --> 00:55:27,860
Either I've finished or I can
pick another generator g2.

923
00:55:27,860 --> 00:55:33,580
Now with g1 and g-two, how many
vectors can I generate?

924
00:55:33,580 --> 00:55:36,930
Let me take all binary
linear combinations.

925
00:55:36,930 --> 00:55:41,350

926
00:55:41,350 --> 00:55:47,600
So a binary linear combination
is any vector of the form

927
00:55:47,600 --> 00:55:54,865
alpha1 g1 plus alpha2 g2 where
these are both scalars.

928
00:55:54,865 --> 00:55:57,470

929
00:55:57,470 --> 00:56:02,830
And therefore this can be 0 or
1, this could be 0 or 1.

930
00:56:02,830 --> 00:56:03,880
So what have I got now?

931
00:56:03,880 --> 00:56:09,830
I've got 0, g1 g2 and g1 plus g2
I've got four binary linear

932
00:56:09,830 --> 00:56:11,380
combinations of two
generators.

933
00:56:11,380 --> 00:56:15,340

934
00:56:15,340 --> 00:56:17,520
Could that be the whole code?

935
00:56:17,520 --> 00:56:19,040
Certainly.

936
00:56:19,040 --> 00:56:23,613
At this point, again, consider
our standing example.

937
00:56:23,613 --> 00:56:26,730

938
00:56:26,730 --> 00:56:29,430
I start out what I take
as my first generator.

939
00:56:29,430 --> 00:56:38,480
Let me take g1 equal 1 0, 1, g2
equals whatever, 0, 1, 1.

940
00:56:38,480 --> 00:56:42,180
Then if I take all binary linear
combinations of these

941
00:56:42,180 --> 00:56:45,030
two generators, I'm going to
get the whole code, right?

942
00:56:45,030 --> 00:56:46,690
These four code words.

943
00:56:46,690 --> 00:56:48,733
They can all be expressed
in this form.

944
00:56:48,733 --> 00:56:51,410

945
00:56:51,410 --> 00:56:56,060
Or I'm not done, and then
I have to pick g3.

946
00:56:56,060 --> 00:56:59,940
And how many binary linear
combinations are there of g1,

947
00:56:59,940 --> 00:57:01,190
g2, and g3?

948
00:57:01,190 --> 00:57:03,210

949
00:57:03,210 --> 00:57:04,400
Eight.

950
00:57:04,400 --> 00:57:06,235
Are they all necessarily
in my subspace?

951
00:57:06,235 --> 00:57:09,150

952
00:57:09,150 --> 00:57:14,300
Yes, by the fact that the
subspace is closed under

953
00:57:14,300 --> 00:57:16,040
scalar multiplication.

954
00:57:16,040 --> 00:57:17,830
Alpha g1.

955
00:57:17,830 --> 00:57:22,860
Alpha1 g1, alpha2 g2 alpha3 g3
are all in the subspace.

956
00:57:22,860 --> 00:57:29,450
Any vector addition of any of
these scalar multiples is in

957
00:57:29,450 --> 00:57:30,280
the subspace.

958
00:57:30,280 --> 00:57:36,010
So I get now eight possible
elements of the subspace, and

959
00:57:36,010 --> 00:57:37,285
I either may be done or not.

960
00:57:37,285 --> 00:57:40,820

961
00:57:40,820 --> 00:57:48,760
Continuing in this way, I get
some number gk of generators,

962
00:57:48,760 --> 00:57:53,410
just by picking greedily the
next one until I'm done.

963
00:57:53,410 --> 00:57:55,140
All right?

964
00:57:55,140 --> 00:57:57,500
When I'm done --

965
00:57:57,500 --> 00:57:58,510
so I have to stop.

966
00:57:58,510 --> 00:57:59,760
Why do I have to stop?

967
00:57:59,760 --> 00:58:02,990

968
00:58:02,990 --> 00:58:03,370
All right.

969
00:58:03,370 --> 00:58:04,660
Let's look at the size.

970
00:58:04,660 --> 00:58:07,750
At each point here, this
accounts for two code words,

971
00:58:07,750 --> 00:58:11,360
this for four, this for eight,
this for 2 to the k.

972
00:58:11,360 --> 00:58:15,870
How many binary n-tuples
are there?

973
00:58:15,870 --> 00:58:16,416
2 to the n.

974
00:58:16,416 --> 00:58:17,890
All right?

975
00:58:17,890 --> 00:58:21,300
So I clearly can't find more
than n generators.

976
00:58:21,300 --> 00:58:25,110
More more than n independent
generators, in the sense that

977
00:58:25,110 --> 00:58:28,840
the set of all the
binary linear

978
00:58:28,840 --> 00:58:32,050
combinations are distinct.

979
00:58:32,050 --> 00:58:32,460
All right.

980
00:58:32,460 --> 00:58:36,740
So k is, at most,
going to be n.

981
00:58:36,740 --> 00:58:39,310
So I will stop in a finite
number of steps.

982
00:58:39,310 --> 00:58:42,020
I'll stop at some number k.

983
00:58:42,020 --> 00:58:46,690
When I've stopped, that's
because the code consists of

984
00:58:46,690 --> 00:58:50,100
all binary linear combinations
of these k generators, and

985
00:58:50,100 --> 00:58:54,480
therefore has size 2 to the k.

986
00:58:54,480 --> 00:59:02,640
So the only possible size of a
subspace is 2 to the k for k

987
00:59:02,640 --> 00:59:04,220
less than n.

988
00:59:04,220 --> 00:59:10,160
A power of 2 where the
power is, at most, n.

989
00:59:10,160 --> 00:59:13,670
So any subspace besides
the subspace --

990
00:59:13,670 --> 00:59:14,920
I'm repeating myself.

991
00:59:14,920 --> 00:59:17,910

992
00:59:17,910 --> 00:59:18,680
OK.

993
00:59:18,680 --> 00:59:25,370
So this means I found a basis.

994
00:59:25,370 --> 00:59:28,760
Does this mean that all possible
bases of any subspace

995
00:59:28,760 --> 00:59:30,010
have the same size?

996
00:59:30,010 --> 00:59:33,284

997
00:59:33,284 --> 00:59:34,490
Well yeah, it must.

998
00:59:34,490 --> 00:59:40,650
I mean, I've proved now that any
subspace has to have this

999
00:59:40,650 --> 00:59:45,000
size 2 to the k for some k.

1000
00:59:45,000 --> 00:59:47,660
So obviously, if I go through
this process, no matter how I

1001
00:59:47,660 --> 00:59:54,330
choose my generators, I could
choose any pair of these

1002
00:59:54,330 --> 00:59:57,550
non-zero n-tuples as
my generators.

1003
00:59:57,550 --> 00:59:59,250
So that would be a
legitimate basis.

1004
00:59:59,250 --> 01:00:01,320
Take any two out
of these three.

1005
01:00:01,320 --> 01:00:04,010
But it's always going to take
exactly two of them, right?

1006
01:00:04,010 --> 01:00:05,060
Why?

1007
01:00:05,060 --> 01:00:08,510
Because the size of this
subspace is four.

1008
01:00:08,510 --> 01:00:10,140
Two to the two.

1009
01:00:10,140 --> 01:00:13,060
So if I go through this process,
I'm always going to

1010
01:00:13,060 --> 01:00:17,590
come up with k generators, where
k is the log to the base

1011
01:00:17,590 --> 01:00:21,340
2 of the size of this code that
I was given, which I was

1012
01:00:21,340 --> 01:00:27,810
told was a linear code, meaning
it's a subspace.

1013
01:00:27,810 --> 01:00:33,330
So I'm somewhat free to choose
the generators, but I'm always

1014
01:00:33,330 --> 01:00:35,820
going to come up with k of
them if the code has

1015
01:00:35,820 --> 01:00:37,070
size 2 to the k.

1016
01:00:37,070 --> 01:00:39,900

1017
01:00:39,900 --> 01:00:50,160
So a basis is a set of k
linearly independent k-tuples,

1018
01:00:50,160 --> 01:00:52,750
where linear independence has
the same meaning here as

1019
01:00:52,750 --> 01:00:56,580
you're accustomed to, meaning
that all linear combinations

1020
01:00:56,580 --> 01:01:00,310
of the k generators
are distinct.

1021
01:01:00,310 --> 01:01:05,020
So I get 2 to the k distinct
elements of the code.

1022
01:01:05,020 --> 01:01:10,210
And I say the dimension
of the code is k.

1023
01:01:10,210 --> 01:01:13,040
In this case, basically it's the
size of the code is 2 to

1024
01:01:13,040 --> 01:01:16,710
the k, then its dimension
is k.

1025
01:01:16,710 --> 01:01:18,580
Has to be.

1026
01:01:18,580 --> 01:01:24,610
And all basis have k
generators in them.

1027
01:01:24,610 --> 01:01:27,800
And there are, in general,
many ways to pick them.

1028
01:01:27,800 --> 01:01:29,300
All right?

1029
01:01:29,300 --> 01:01:33,820
So just by considering this
greedy basis construction

1030
01:01:33,820 --> 01:01:43,440
algorithm, I basically find the
size of any subspace is a

1031
01:01:43,440 --> 01:01:46,850
power of two, and the power
is equal to the dimension.

1032
01:01:46,850 --> 01:01:49,870
And any basis is going to
have that cardinality.

1033
01:01:49,870 --> 01:01:52,730

1034
01:01:52,730 --> 01:01:53,580
Are you with me?

1035
01:01:53,580 --> 01:01:57,150
This is a pretty simple proof.

1036
01:01:57,150 --> 01:02:02,070
And I call this an n, k binary
linear block code.

1037
01:02:02,070 --> 01:02:04,930
n being the length.

1038
01:02:04,930 --> 01:02:09,950
That just means that every code
word is an n-tuple over

1039
01:02:09,950 --> 01:02:11,660
the binary field.

1040
01:02:11,660 --> 01:02:13,670
And k is the dimension.

1041
01:02:13,670 --> 01:02:20,510
So an n, k binary linear block
code has size 2 to the k.

1042
01:02:20,510 --> 01:02:24,410

1043
01:02:24,410 --> 01:02:29,170
That's 2 to the k distinct
code words.

1044
01:02:29,170 --> 01:02:31,000
Main example is this guy.

1045
01:02:31,000 --> 01:02:35,070

1046
01:02:35,070 --> 01:02:35,640
Easy?

1047
01:02:35,640 --> 01:02:36,620
Any questions?

1048
01:02:36,620 --> 01:02:37,910
I think this is clear.

1049
01:02:37,910 --> 01:02:41,155
AUDIENCE: Can n use the number
of code word, I take

1050
01:02:41,155 --> 01:02:44,190
like 2 to the k?

1051
01:02:44,190 --> 01:02:48,060
PROFESSOR: n is something I
specify a priori as the length

1052
01:02:48,060 --> 01:02:50,660
of every vector in the code.

1053
01:02:50,660 --> 01:02:56,260
In other words, it has size 2 to
the k, and it's a subset of

1054
01:02:56,260 --> 01:02:58,320
the set of all binary
n-tuples, which

1055
01:02:58,320 --> 01:02:59,550
I write like that.

1056
01:02:59,550 --> 01:03:01,050
In other words, the
elements of the

1057
01:03:01,050 --> 01:03:03,662
code are binary n-tuples.

1058
01:03:03,662 --> 01:03:05,580
If I write them out, each
one has length n.

1059
01:03:05,580 --> 01:03:09,610

1060
01:03:09,610 --> 01:03:10,130
OK?

1061
01:03:10,130 --> 01:03:12,240
We're good?

1062
01:03:12,240 --> 01:03:13,490
What are some other examples?

1063
01:03:13,490 --> 01:03:18,810

1064
01:03:18,810 --> 01:03:23,720
The simplest codes you can
think of is, first of

1065
01:03:23,720 --> 01:03:26,600
all, an n, 0 code.

1066
01:03:26,600 --> 01:03:29,800
That means a code with dimension
zero, has size what?

1067
01:03:29,800 --> 01:03:32,380

1068
01:03:32,380 --> 01:03:33,510
1.

1069
01:03:33,510 --> 01:03:35,350
And what does it consist of?

1070
01:03:35,350 --> 01:03:37,230
AUDIENCE: [INAUDIBLE]

1071
01:03:37,230 --> 01:03:37,700
PROFESSOR: Yeah.

1072
01:03:37,700 --> 01:03:41,870
So this is the so-called trivial
code, just containing

1073
01:03:41,870 --> 01:03:45,450
the all-0 word.

1074
01:03:45,450 --> 01:03:46,780
Has to mention 0.

1075
01:03:46,780 --> 01:03:49,790
It is a binary linear block
code, but it's not much use

1076
01:03:49,790 --> 01:03:52,490
for communication.

1077
01:03:52,490 --> 01:03:55,720
So but nonetheless, we include
that in this family.

1078
01:03:55,720 --> 01:03:58,420

1079
01:03:58,420 --> 01:04:01,760
Another trivial one is n, n.

1080
01:04:01,760 --> 01:04:03,068
What's that?

1081
01:04:03,068 --> 01:04:06,000
AUDIENCE: [INAUDIBLE]

1082
01:04:06,000 --> 01:04:07,480
PROFESSOR: F2 to the n, right.

1083
01:04:07,480 --> 01:04:08,730
What's its size?

1084
01:04:08,730 --> 01:04:09,310
2 to the n.

1085
01:04:09,310 --> 01:04:15,370
That means it has to contain all
distinct binary n-tuples.

1086
01:04:15,370 --> 01:04:18,340
So this is called the
trivial code.

1087
01:04:18,340 --> 01:04:21,210
This is called the
universe code.

1088
01:04:21,210 --> 01:04:24,470
Contains the entire universe
of binary n-tuples.

1089
01:04:24,470 --> 01:04:27,160

1090
01:04:27,160 --> 01:04:29,920
Let's get some slightly
less trivial ones.

1091
01:04:29,920 --> 01:04:32,850
n, 1.

1092
01:04:32,850 --> 01:04:36,330
What would that be?

1093
01:04:36,330 --> 01:04:38,280
An n, 1 code.

1094
01:04:38,280 --> 01:04:40,640
What's its size?

1095
01:04:40,640 --> 01:04:41,310
2.

1096
01:04:41,310 --> 01:04:42,560
What does it consist of?

1097
01:04:42,560 --> 01:04:44,940

1098
01:04:44,940 --> 01:04:48,020
The 0 word, and?

1099
01:04:48,020 --> 01:04:50,760
Any other non-zero generator.

1100
01:04:50,760 --> 01:04:52,250
And that's correct.

1101
01:04:52,250 --> 01:04:59,160
This can be 0 and any generator,
two words.

1102
01:04:59,160 --> 01:05:03,440
In communications, where we want
to maximize the distance,

1103
01:05:03,440 --> 01:05:10,330
in some sense, between the
two code words, what is g

1104
01:05:10,330 --> 01:05:12,650
always taken as?

1105
01:05:12,650 --> 01:05:14,430
0,1's, right.

1106
01:05:14,430 --> 01:05:20,160
So if it's in particular the
all-0 and the all-1 word,

1107
01:05:20,160 --> 01:05:23,410
which I might write as a vector
of 0's and a vector of

1108
01:05:23,410 --> 01:05:28,846
1's, this is called the
repetition code.

1109
01:05:28,846 --> 01:05:32,600
The binary repetition
code of length n.

1110
01:05:32,600 --> 01:05:36,310
It either gives me a 0 and I
repeat it n times, or gives me

1111
01:05:36,310 --> 01:05:39,010
a 1 and I repeat it n times.

1112
01:05:39,010 --> 01:05:41,860
So whenever you see n,1, you
can pretty well assume it's

1113
01:05:41,860 --> 01:05:48,280
the repetition code, though
it might be any pair 0, g.

1114
01:05:48,280 --> 01:05:49,490
And n, minus 1.

1115
01:05:49,490 --> 01:05:50,860
This is an interesting one.

1116
01:05:50,860 --> 01:05:58,400

1117
01:05:58,400 --> 01:06:07,930
Again, while this could
be a lot of things, in

1118
01:06:07,930 --> 01:06:12,410
communications, whenever you see
this, this will always be

1119
01:06:12,410 --> 01:06:16,320
the set of all even-weight
n-tuples.

1120
01:06:16,320 --> 01:06:22,040

1121
01:06:22,040 --> 01:06:28,590
In other words, the set of all
n-tuples with even parity such

1122
01:06:28,590 --> 01:06:31,310
that if you sum up all of
the components of any

1123
01:06:31,310 --> 01:06:35,340
vector, mod2 equals 0.

1124
01:06:35,340 --> 01:06:36,340
OK?

1125
01:06:36,340 --> 01:06:47,110
So this I will call the single
parity check, or more briefly,

1126
01:06:47,110 --> 01:06:51,410
the SPC code, or the
even-weight code.

1127
01:06:51,410 --> 01:06:52,660
That's equally good.

1128
01:06:52,660 --> 01:06:55,260

1129
01:06:55,260 --> 01:07:01,200
And here we maybe should do
a little bit more work.

1130
01:07:01,200 --> 01:07:03,350
Say, is this in fact
a subspace?

1131
01:07:03,350 --> 01:07:06,080
Does it include the all-zero
code word?

1132
01:07:06,080 --> 01:07:08,990
Yes, all-zero has even weight.

1133
01:07:08,990 --> 01:07:12,350
The sum of any two even-weight
code words, an even-weight

1134
01:07:12,350 --> 01:07:15,810
code word, an even-weight
n-tuple.

1135
01:07:15,810 --> 01:07:17,360
Yes.

1136
01:07:17,360 --> 01:07:18,040
As here.

1137
01:07:18,040 --> 01:07:19,250
This is an example.

1138
01:07:19,250 --> 01:07:22,916
This is the three,
two SPC code.

1139
01:07:22,916 --> 01:07:27,290

1140
01:07:27,290 --> 01:07:28,070
OK.

1141
01:07:28,070 --> 01:07:32,242
Why is this dimension
n minus one?

1142
01:07:32,242 --> 01:07:34,690
AUDIENCE: [INAUDIBLE]

1143
01:07:34,690 --> 01:07:37,840
Is every code word orthogonal
to the one-vector?

1144
01:07:37,840 --> 01:07:38,800
PROFESSOR: OK.

1145
01:07:38,800 --> 01:07:41,620
That's an excellent answer.

1146
01:07:41,620 --> 01:07:43,590
It's a little advanced
for us right now.

1147
01:07:43,590 --> 01:07:45,993
I'm looking for an elementary
argument.

1148
01:07:45,993 --> 01:07:47,243
AUDIENCE: [INAUDIBLE]

1149
01:07:47,243 --> 01:07:57,600

1150
01:07:57,600 --> 01:07:57,990
PROFESSOR: OK.

1151
01:07:57,990 --> 01:08:00,980
So you're saying we have
a set of generators

1152
01:08:00,980 --> 01:08:03,200
that looks like this.

1153
01:08:03,200 --> 01:08:05,210
Is that what you're saying?

1154
01:08:05,210 --> 01:08:07,180
You are correct.

1155
01:08:07,180 --> 01:08:12,980
And how many such generators
are there?

1156
01:08:12,980 --> 01:08:16,229
There are n minus 1 of them.

1157
01:08:16,229 --> 01:08:19,760
I always like to find the most
elementary argument possible.

1158
01:08:19,760 --> 01:08:23,910
I think the most elementary
argument here is that the

1159
01:08:23,910 --> 01:08:26,279
number of even-weight n-tuples
is equal to the number of

1160
01:08:26,279 --> 01:08:29,160
odd-weight n-tuples, and
together they form the set of

1161
01:08:29,160 --> 01:08:30,819
all n-tuples.

1162
01:08:30,819 --> 01:08:34,279
So exactly half of the n-tuples
are even weight.

1163
01:08:34,279 --> 01:08:38,029
That means there are 2 to the n
minus 1 of them, 2 to the n

1164
01:08:38,029 --> 01:08:42,109
over 2, and therefore, the
dimension must be n minus 1.

1165
01:08:42,109 --> 01:08:48,575
But perhaps this is just
as elementary a proof.

1166
01:08:48,575 --> 01:08:51,124
Well, however you do it, you'll
find that there are 2

1167
01:08:51,124 --> 01:08:56,529
to the n minus 1 of them, or
that here is clearly a set of

1168
01:08:56,529 --> 01:08:57,260
generators.

1169
01:08:57,260 --> 01:09:00,580
It might take a few more lines
to show that every even-weight

1170
01:09:00,580 --> 01:09:05,720
code word is a linear
combination of this particular

1171
01:09:05,720 --> 01:09:08,760
set of generators, but
it's certainly true.

1172
01:09:08,760 --> 01:09:09,149
All right.

1173
01:09:09,149 --> 01:09:13,800
So these four classes of codes,
these two entirely

1174
01:09:13,800 --> 01:09:17,660
trivial ones, these two which
are actually somewhat more

1175
01:09:17,660 --> 01:09:19,859
interesting for coding
purposes --

1176
01:09:19,859 --> 01:09:23,710
we've already seen, we can get a
coding game with this length

1177
01:09:23,710 --> 01:09:25,924
three, dimension two code --

1178
01:09:25,924 --> 01:09:28,450

1179
01:09:28,450 --> 01:09:33,840
are basically the simplest
codes we can think of.

1180
01:09:33,840 --> 01:09:36,210
The simplest binary linear
block codes.

1181
01:09:36,210 --> 01:09:38,529
Now we'll see them
again and again.

1182
01:09:38,529 --> 01:09:41,220
They turn up.

1183
01:09:41,220 --> 01:09:41,649
All right?

1184
01:09:41,649 --> 01:09:43,750
So the whole course is
going to be about

1185
01:09:43,750 --> 01:09:45,510
finding 1's in between.

1186
01:09:45,510 --> 01:09:47,045
More complicated ones.

1187
01:09:47,045 --> 01:09:49,260
There's clearly more
room to play.

1188
01:09:49,260 --> 01:09:55,650
For instance, if k is equal to
half of n, which means that

1189
01:09:55,650 --> 01:09:59,670
rho is equal to one bit per two
dimensions, there's a lot

1190
01:09:59,670 --> 01:10:03,360
of possibilities.

1191
01:10:03,360 --> 01:10:06,335
And so we're going to explore
those possibilities.

1192
01:10:06,335 --> 01:10:12,444

1193
01:10:12,444 --> 01:10:13,694
AUDIENCE: [INAUDIBLE]

1194
01:10:13,694 --> 01:10:16,276

1195
01:10:16,276 --> 01:10:17,526
[UNINTELLIGIBLE]

1196
01:10:17,526 --> 01:10:27,660

1197
01:10:27,660 --> 01:10:28,910
PROFESSOR: Sure.

1198
01:10:28,910 --> 01:10:31,410

1199
01:10:31,410 --> 01:10:37,790
Let's take the 6,5 code
generated by these five

1200
01:10:37,790 --> 01:10:39,040
generators.

1201
01:10:39,040 --> 01:10:40,730

1202
01:10:40,730 --> 01:10:42,200
Well, it contains some

1203
01:10:42,200 --> 01:10:43,525
odd-weight code words, obviously.

1204
01:10:43,525 --> 01:10:46,980

1205
01:10:46,980 --> 01:10:50,750
But it's not as interesting from
a coding point of view.

1206
01:10:50,750 --> 01:10:54,320

1207
01:10:54,320 --> 01:10:56,100
It's not the only one,
but it's the only one

1208
01:10:56,100 --> 01:10:57,350
you'll ever see here.

1209
01:10:57,350 --> 01:11:01,220

1210
01:11:01,220 --> 01:11:01,700
All right.

1211
01:11:01,700 --> 01:11:02,950
Let's see.

1212
01:11:02,950 --> 01:11:07,580

1213
01:11:07,580 --> 01:11:11,020
One thing I didn't point out
in the notes but probably

1214
01:11:11,020 --> 01:11:15,510
should have here is, what is rho
for an n, k binary linear

1215
01:11:15,510 --> 01:11:16,760
block code?

1216
01:11:16,760 --> 01:11:19,530

1217
01:11:19,530 --> 01:11:21,620
How many bits can we send?

1218
01:11:21,620 --> 01:11:24,400
Suppose we take the Euclidean
image of this.

1219
01:11:24,400 --> 01:11:29,670
It is going to have 2 to the k
points, 2 to the k vertices of

1220
01:11:29,670 --> 01:11:35,140
the n-cube, and so
what is rho?

1221
01:11:35,140 --> 01:11:37,210
What is the rate in bits
per two dimensions?

1222
01:11:37,210 --> 01:11:38,460
AUDIENCE: [INAUDIBLE]

1223
01:11:38,460 --> 01:11:40,526

1224
01:11:40,526 --> 01:11:43,160
PROFESSOR: Right.

1225
01:11:43,160 --> 01:11:49,580
The rate is basically k over n
over 2, if you like, or 2 k

1226
01:11:49,580 --> 01:11:54,480
over n bits per two
dimensions.

1227
01:11:54,480 --> 01:12:00,010
You can send k bits in n
dimensions, or 2 k over n bits

1228
01:12:00,010 --> 01:12:01,870
per two dimensions.

1229
01:12:01,870 --> 01:12:08,070
And since k can't be larger than
n, this is going to be

1230
01:12:08,070 --> 01:12:10,900
less than or equal to two
bits per two dimensions.

1231
01:12:10,900 --> 01:12:14,200
So again, we see we're
definitely in the

1232
01:12:14,200 --> 01:12:20,790
power-limited regime, and that
we can really get any nominal

1233
01:12:20,790 --> 01:12:27,910
spectral efficiency between 0
and 2 by choosing k and n

1234
01:12:27,910 --> 01:12:30,750
appropriately.

1235
01:12:30,750 --> 01:12:31,080
All right.

1236
01:12:31,080 --> 01:12:34,420
So n and k determine the rate,
determine the nominal spectral

1237
01:12:34,420 --> 01:12:35,670
efficiency.

1238
01:12:35,670 --> 01:12:37,930

1239
01:12:37,930 --> 01:12:38,170
All right.

1240
01:12:38,170 --> 01:12:42,970
Let's now talk about things that
I think are also very old

1241
01:12:42,970 --> 01:12:44,120
hat to you.

1242
01:12:44,120 --> 01:12:45,370
I mean weight and distance.

1243
01:12:45,370 --> 01:12:49,160

1244
01:12:49,160 --> 01:12:57,840
But we begin to get into areas
that show us that these vector

1245
01:12:57,840 --> 01:13:00,820
spaces are very different from
the real and complex vector

1246
01:13:00,820 --> 01:13:03,000
spaces that we're
accustomed to.

1247
01:13:03,000 --> 01:13:04,870
So what are we doing now?

1248
01:13:04,870 --> 01:13:08,140
We're starting to get into the
geometry of this vector space.

1249
01:13:08,140 --> 01:13:11,510
The geometry is not Euclidean
geometry, but

1250
01:13:11,510 --> 01:13:15,090
it's Hamming geometry.

1251
01:13:15,090 --> 01:13:20,440
We define the Hamming weight
of a vector as simply the

1252
01:13:20,440 --> 01:13:29,000
number of 1's in v. So the
Hamming weight of the all-0

1253
01:13:29,000 --> 01:13:31,870
vector is 0, the Hamming weight
of the all-1 vector is

1254
01:13:31,870 --> 01:13:34,800
n, and in general, the Hamming
weight is somewhere

1255
01:13:34,800 --> 01:13:36,020
between 0 and n.

1256
01:13:36,020 --> 01:13:37,910
Just the number of 1's.

1257
01:13:37,910 --> 01:13:39,980
Pretty simple.

1258
01:13:39,980 --> 01:13:49,686
And given two vectors x and
y, what is their distance?

1259
01:13:49,686 --> 01:13:53,750

1260
01:13:53,750 --> 01:13:58,145
The Hamming distance between x
and y is equal to the Hamming

1261
01:13:58,145 --> 01:14:00,450
weight of x minus y.

1262
01:14:00,450 --> 01:14:04,270
This is the standard way of
converting a weight metric

1263
01:14:04,270 --> 01:14:06,480
into a distance metric.

1264
01:14:06,480 --> 01:14:11,270
Or because addition is the
same as subtraction in a

1265
01:14:11,270 --> 01:14:15,710
binary vector space, we might
equally well write this is as

1266
01:14:15,710 --> 01:14:17,490
the Hamming weight
of x plus y.

1267
01:14:17,490 --> 01:14:20,500

1268
01:14:20,500 --> 01:14:28,970
And more informally, this is
simply the number of places in

1269
01:14:28,970 --> 01:14:30,220
which they differ.

1270
01:14:30,220 --> 01:14:37,260

1271
01:14:37,260 --> 01:14:37,790
OK.

1272
01:14:37,790 --> 01:14:42,350
So if x and y are identical,
then x plus y is equal to 0

1273
01:14:42,350 --> 01:14:44,400
and the distance is 0.

1274
01:14:44,400 --> 01:14:49,850
If they are complementary, y is
the complement of x, then

1275
01:14:49,850 --> 01:14:51,400
they differ in every place.

1276
01:14:51,400 --> 01:14:57,150
The sum will then be the all-1
vector, and the weight, the

1277
01:14:57,150 --> 01:14:59,730
Hamming distance, will be n.

1278
01:14:59,730 --> 01:15:02,060
And so again, the Hamming
distance is somewhere between

1279
01:15:02,060 --> 01:15:05,220
0 and n, measures how
different they are.

1280
01:15:05,220 --> 01:15:07,860
Clearly going to be important
for coding.

1281
01:15:07,860 --> 01:15:10,510
It's going to translate directly
into Euclidean

1282
01:15:10,510 --> 01:15:13,695
distance under this standard
2-PAM map.

1283
01:15:13,695 --> 01:15:14,945
OK.

1284
01:15:14,945 --> 01:15:17,290

1285
01:15:17,290 --> 01:15:24,570
Again, let's check that it
satisfies the distance axioms.

1286
01:15:24,570 --> 01:15:31,150
I don't know how many of you
have seen this, but let's see.

1287
01:15:31,150 --> 01:15:34,710
What are the distance axioms?

1288
01:15:34,710 --> 01:15:35,960
Strict non-negativity.

1289
01:15:35,960 --> 01:15:40,700

1290
01:15:40,700 --> 01:15:46,820
In other words, the Hamming
distance between x and y --

1291
01:15:46,820 --> 01:15:48,480
that's a single comma --

1292
01:15:48,480 --> 01:15:53,140
is greater than or equal to
0, and equality if and

1293
01:15:53,140 --> 01:15:55,750
only if x equals y.

1294
01:15:55,750 --> 01:15:58,280
That's what strict means.

1295
01:15:58,280 --> 01:16:00,830
So if we find the Hamming
distance is 0, we can assert

1296
01:16:00,830 --> 01:16:02,080
that x equals y.

1297
01:16:02,080 --> 01:16:04,340

1298
01:16:04,340 --> 01:16:05,785
We have, of course, symmetry.

1299
01:16:05,785 --> 01:16:09,680

1300
01:16:09,680 --> 01:16:14,430
The Hamming distance between
x and y is the same as the

1301
01:16:14,430 --> 01:16:17,020
Hamming distance between
y and x.

1302
01:16:17,020 --> 01:16:18,970
Order doesn't matter.

1303
01:16:18,970 --> 01:16:26,190
And finally we have the triangle
inequality, that the

1304
01:16:26,190 --> 01:16:31,800
Hamming distance between x and z
certainly can't be more than

1305
01:16:31,800 --> 01:16:36,790
the Hamming distance between
x and y plus the Hamming

1306
01:16:36,790 --> 01:16:38,800
distance between y and z.

1307
01:16:38,800 --> 01:16:41,490

1308
01:16:41,490 --> 01:16:48,540
If x differs from y in only n1
places, and y differs from z

1309
01:16:48,540 --> 01:16:52,400
in only n2 places, then clearly
z can't differ from x

1310
01:16:52,400 --> 01:16:54,305
in more than n1 plus
n2 places.

1311
01:16:54,305 --> 01:16:57,740

1312
01:16:57,740 --> 01:16:59,360
So check, check, check.

1313
01:16:59,360 --> 01:17:04,820
This is a legitimate metric for
defining a geometry on the

1314
01:17:04,820 --> 01:17:10,000
space, and this is the one that
we use on the space of

1315
01:17:10,000 --> 01:17:12,140
all n-tuples.

1316
01:17:12,140 --> 01:17:15,760
But notice it's not all like
the Euclidean Distance.

1317
01:17:15,760 --> 01:17:18,700

1318
01:17:18,700 --> 01:17:22,110
Now when we have a
linear code --

1319
01:17:22,110 --> 01:17:23,430
let's combine these things.

1320
01:17:23,430 --> 01:17:39,010
When we have a linear code, we
have a group property which

1321
01:17:39,010 --> 01:17:40,700
is, let me write it this way.

1322
01:17:40,700 --> 01:17:47,430
If we take any code word and add
it to any other code word,

1323
01:17:47,430 --> 01:17:50,940
that's in the code.

1324
01:17:50,940 --> 01:17:58,990
And furthermore, c plus c prime
is not equal to c prime

1325
01:17:58,990 --> 01:18:03,220
plus c single prime, c
plus c single prime,

1326
01:18:03,220 --> 01:18:04,670
because we can --

1327
01:18:04,670 --> 01:18:06,300
well, I'll finish it.

1328
01:18:06,300 --> 01:18:13,290
Unless c prime equals
c double prime.

1329
01:18:13,290 --> 01:18:14,040
Why is that?

1330
01:18:14,040 --> 01:18:17,240
We can do subtraction,
cancellation.

1331
01:18:17,240 --> 01:18:19,470
Cancel c out from each side.

1332
01:18:19,470 --> 01:18:25,210
So if we add c to c double
prime, we're going to get a

1333
01:18:25,210 --> 01:18:30,160
different result from adding c
to c prime, if c prime and c

1334
01:18:30,160 --> 01:18:33,490
double prime are different.

1335
01:18:33,490 --> 01:18:39,200
So this implies that
c plus C --

1336
01:18:39,200 --> 01:18:43,010
I write that as an abbreviation
for the set of

1337
01:18:43,010 --> 01:18:50,840
all c plus c prime, as a c prime
runs through the code C.

1338
01:18:50,840 --> 01:18:59,130
So this is the 2 to the k sums
of the code plus any code word

1339
01:18:59,130 --> 01:19:00,380
in the code.

1340
01:19:00,380 --> 01:19:03,450

1341
01:19:03,450 --> 01:19:05,350
Sorry if I don't write
down all steps.

1342
01:19:05,350 --> 01:19:08,950
What is that going to be?

1343
01:19:08,950 --> 01:19:16,038
C. How did we conclude that?

1344
01:19:16,038 --> 01:19:17,288
AUDIENCE: [INAUDIBLE]

1345
01:19:17,288 --> 01:19:19,510

1346
01:19:19,510 --> 01:19:20,760
[UNINTELLIGIBLE]

1347
01:19:20,760 --> 01:19:24,280

1348
01:19:24,280 --> 01:19:25,920
PROFESSOR: Perfect.

1349
01:19:25,920 --> 01:19:28,100
Did you all hear that?

1350
01:19:28,100 --> 01:19:30,550
By the group property,
each one of these

1351
01:19:30,550 --> 01:19:32,190
things is in the code.

1352
01:19:32,190 --> 01:19:36,000
By this argument, no two
of them are the same.

1353
01:19:36,000 --> 01:19:39,760
That means I get 2 to the k
distinct elements all in the

1354
01:19:39,760 --> 01:19:42,170
code, that's got to be the code,
because the code only

1355
01:19:42,170 --> 01:19:43,420
has 2 to the k elements.

1356
01:19:43,420 --> 01:19:46,850

1357
01:19:46,850 --> 01:19:48,630
All right.

1358
01:19:48,630 --> 01:19:51,740
So if I add a code word --

1359
01:19:51,740 --> 01:19:54,360
in other words, if I write
down the code --

1360
01:19:54,360 --> 01:20:00,190
0, 0, 0, 0, 1, 1, 1 0 1, 1 1 0-
and I add any code word to

1361
01:20:00,190 --> 01:20:04,560
it -- say I add 0
1 1 to the code.

1362
01:20:04,560 --> 01:20:08,930
So let me just do one column
of the addition table.

1363
01:20:08,930 --> 01:20:14,530
I get 0, 1, 1, 0, 0, 0,
1, 1, 0, 1, 0, 1.

1364
01:20:14,530 --> 01:20:15,890
I'll get the code
itself again.

1365
01:20:15,890 --> 01:20:21,070

1366
01:20:21,070 --> 01:20:24,210
This has a very important
property.

1367
01:20:24,210 --> 01:20:26,910

1368
01:20:26,910 --> 01:20:38,460
The set of Hamming distances C
and c prime, as c prime runs

1369
01:20:38,460 --> 01:20:51,660
through c, from any given code
word C, it is independent of

1370
01:20:51,660 --> 01:20:59,920
C. So I can start from any code
word, measure the Hamming

1371
01:20:59,920 --> 01:21:02,960
distances, the 2 to the k
Hamming distances to all other

1372
01:21:02,960 --> 01:21:05,930
code words, including
C itself --

1373
01:21:05,930 --> 01:21:08,390
let c prime run through the
entire code, I'm going to get

1374
01:21:08,390 --> 01:21:11,570
a set of 2 to the k distances
called the distance

1375
01:21:11,570 --> 01:21:13,700
profile of the code.

1376
01:21:13,700 --> 01:21:16,320

1377
01:21:16,320 --> 01:21:19,670
And I claim that it doesn't
matter which code

1378
01:21:19,670 --> 01:21:21,870
word I start from.

1379
01:21:21,870 --> 01:21:24,510
I'm going to get the same
distance profile regardless of

1380
01:21:24,510 --> 01:21:26,130
where I start.

1381
01:21:26,130 --> 01:21:29,140
In other words, the set of all
distances from the all-0 word

1382
01:21:29,140 --> 01:21:35,430
here, which is 0, 2, 2, 2, is
the same as the set of all

1383
01:21:35,430 --> 01:21:38,270
distances from the 0,
1, 1, code word,

1384
01:21:38,270 --> 01:21:43,480
which is 2, 0, 2, 2.

1385
01:21:43,480 --> 01:21:47,540
And the proof is basically
that this is simply the

1386
01:21:47,540 --> 01:21:51,940
Hamming weight of C plus c prime
as c prime runs through

1387
01:21:51,940 --> 01:21:55,580
C. What is this equal to?

1388
01:21:55,580 --> 01:22:01,610
So the proof is that this is
equal to the Hamming weight of

1389
01:22:01,610 --> 01:22:07,020
c prime as c prime
runs through C.

1390
01:22:07,020 --> 01:22:10,900
So the distance profile from any
code word is simply equal

1391
01:22:10,900 --> 01:22:14,970
to the weight profile
of the code itself.

1392
01:22:14,970 --> 01:22:18,820
The weight profile of this code
is 0, 2, 2, 2, Start from

1393
01:22:18,820 --> 01:22:22,700
any code word, measure the
distances to other code words,

1394
01:22:22,700 --> 01:22:25,980
I'm always going to get
0, 2, 2, 2, 0, to

1395
01:22:25,980 --> 01:22:29,680
itself, and the others.

1396
01:22:29,680 --> 01:22:32,630
Sounds sort of like the
tetrahedron, doesn't it?

1397
01:22:32,630 --> 01:22:36,570
It's zero distance from a code
word to itself and equal

1398
01:22:36,570 --> 01:22:39,520
distance to all the other
code words, in

1399
01:22:39,520 --> 01:22:41,540
that particular case.

1400
01:22:41,540 --> 01:22:41,850
OK.

1401
01:22:41,850 --> 01:22:44,480
So again, everything is
very elementary here.

1402
01:22:44,480 --> 01:22:50,200
The distance profile is
independent of C and equal to

1403
01:22:50,200 --> 01:22:51,450
the weight profile.

1404
01:22:51,450 --> 01:23:06,330

1405
01:23:06,330 --> 01:23:10,720
So this has an extremely
important corollary.

1406
01:23:10,720 --> 01:23:14,440
What's the minimum Hamming
distance of the code?

1407
01:23:14,440 --> 01:23:16,110
You might expect this
is going to be an

1408
01:23:16,110 --> 01:23:17,450
important code parameter.

1409
01:23:17,450 --> 01:23:18,700
AUDIENCE: [INAUDIBLE]

1410
01:23:18,700 --> 01:23:23,230

1411
01:23:23,230 --> 01:23:25,900
PROFESSOR: The minimum Hamming
distance between any two code

1412
01:23:25,900 --> 01:23:28,620
words is going to
be equal to --

1413
01:23:28,620 --> 01:23:29,980
I think you said it.

1414
01:23:29,980 --> 01:23:31,860
AUDIENCE: The 0
[UNINTELLIGIBLE].

1415
01:23:31,860 --> 01:23:35,470
PROFESSOR: Non-zero
is important here.

1416
01:23:35,470 --> 01:23:37,910
If the distance profile is equal
to the weight profile,

1417
01:23:37,910 --> 01:23:40,660
one of the weights is always
going to be zero.

1418
01:23:40,660 --> 01:23:43,920
And that corresponds to the
distance between a code word

1419
01:23:43,920 --> 01:23:45,780
and itself.

1420
01:23:45,780 --> 01:23:46,070
All right.

1421
01:23:46,070 --> 01:23:50,170
If I go through all the other 2
to the k minus 1 distances,

1422
01:23:50,170 --> 01:23:52,840
they're going to be weights.

1423
01:23:52,840 --> 01:23:54,910
They're going to be the
distances from a code to all

1424
01:23:54,910 --> 01:23:56,760
other code words.

1425
01:23:56,760 --> 01:24:01,580
And the minimum distance is
simply going to be the minimum

1426
01:24:01,580 --> 01:24:04,370
non-zero weight of the code.

1427
01:24:04,370 --> 01:24:08,310
For example, in this code, the
minimum Hamming distance

1428
01:24:08,310 --> 01:24:12,990
between any two distinct code
words is going to be equal to

1429
01:24:12,990 --> 01:24:16,190
the minimum distance from
the 0 code word --

1430
01:24:16,190 --> 01:24:17,320
that's another way
of doing it.

1431
01:24:17,320 --> 01:24:20,950
Since it's independent of C, we
may as well take the base

1432
01:24:20,950 --> 01:24:23,490
code word C to be zero.

1433
01:24:23,490 --> 01:24:26,690
And then what's the minimum
distance to 0?

1434
01:24:26,690 --> 01:24:27,840
To the 0-code word?

1435
01:24:27,840 --> 01:24:29,650
It's the minimum weight.

1436
01:24:29,650 --> 01:24:33,380
From the 0 code word, distance
equals weight.

1437
01:24:33,380 --> 01:24:36,710
So the minimum distance is the
minimum weight of any non-zero

1438
01:24:36,710 --> 01:24:39,300
code word, which for
this code is two.

1439
01:24:39,300 --> 01:24:43,500

1440
01:24:43,500 --> 01:24:48,550
Now here the weight profile
is 0, 2, 2, 2, 0.

1441
01:24:48,550 --> 01:24:52,490
The distance profile from any
code word to all the others is

1442
01:24:52,490 --> 01:24:54,150
0, 2, 2,2 2.

1443
01:24:54,150 --> 01:24:56,100
This is always the distance
to itself.

1444
01:24:56,100 --> 01:24:59,950
So minimum distance to
other code words is

1445
01:24:59,950 --> 01:25:03,130
always going to be two.

1446
01:25:03,130 --> 01:25:08,560
Furthermore, the number of
nearest neighbors --

1447
01:25:08,560 --> 01:25:12,640
to go back and use chapter
five terminology --

1448
01:25:12,640 --> 01:25:16,530
the number of nearest neighbors
is going to be the

1449
01:25:16,530 --> 01:25:20,230
number of code words that have
that minimum weight --

1450
01:25:20,230 --> 01:25:22,760
in this case, three.

1451
01:25:22,760 --> 01:25:26,800
Still sounding a lot like
a tetrahedron, isn't it?

1452
01:25:26,800 --> 01:25:30,830
This easy map between Hamming
distance and Euclidean

1453
01:25:30,830 --> 01:25:37,840
distance for this case and in
general for all of our cases.

1454
01:25:37,840 --> 01:25:43,300
So corollary.

1455
01:25:43,300 --> 01:25:48,960
The minimum Hamming distance,
which implicitly means between

1456
01:25:48,960 --> 01:25:55,390
two distinct code words of C,
is equal to the minimum

1457
01:25:55,390 --> 01:26:06,120
non-zero weight of C, and the
number of minimum weight code

1458
01:26:06,120 --> 01:26:08,340
words is independent --

1459
01:26:08,340 --> 01:26:11,400

1460
01:26:11,400 --> 01:26:13,830
I'm doing this backwards.

1461
01:26:13,830 --> 01:26:18,670
From any code word, the number
of code words that distance,

1462
01:26:18,670 --> 01:26:25,350
let's call this d, is equal
to the number of

1463
01:26:25,350 --> 01:26:28,910
weight d code words.

1464
01:26:28,910 --> 01:26:31,110
Sorry, you probably
can't see that.

1465
01:26:31,110 --> 01:26:36,360

1466
01:26:36,360 --> 01:26:36,720
All right.

1467
01:26:36,720 --> 01:26:39,940
So we get this symmetry property
for codes that

1468
01:26:39,940 --> 01:26:45,900
follows from the group property
of the code that if

1469
01:26:45,900 --> 01:26:48,510
we stand on any code word and
look out, we're always going

1470
01:26:48,510 --> 01:26:51,590
to see the same thing.

1471
01:26:51,590 --> 01:26:53,410
We have this constant.

1472
01:26:53,410 --> 01:26:57,710
It's actually easiest to see
this when we make the map from

1473
01:26:57,710 --> 01:27:01,010
the code to the Euclidean
image of the code.

1474
01:27:01,010 --> 01:27:08,740

1475
01:27:08,740 --> 01:27:16,350
So the Euclidean image S of C
of the code word is going to

1476
01:27:16,350 --> 01:27:24,760
be some set of 2 to the
k vertices of an

1477
01:27:24,760 --> 01:27:29,295
n-cube of side alpha.

1478
01:27:29,295 --> 01:27:35,270

1479
01:27:35,270 --> 01:27:41,360
Let's talk about the Euclidean
image of these properties.

1480
01:27:41,360 --> 01:27:48,210
If the minimum Hamming distance
of the code is d,

1481
01:27:48,210 --> 01:27:52,670
what's the minimum squared
Euclidean distance between

1482
01:27:52,670 --> 01:27:54,470
elements of S of
C going to be?

1483
01:27:54,470 --> 01:27:58,450

1484
01:27:58,450 --> 01:28:00,975
Well, let's do it coordinate
by coordinates.

1485
01:28:00,975 --> 01:28:03,630

1486
01:28:03,630 --> 01:28:11,800
Let's take two code words,
C and c prime, let's say.

1487
01:28:11,800 --> 01:28:14,560
And let's suppose we have
some Hamming distance

1488
01:28:14,560 --> 01:28:15,910
between C and c prime.

1489
01:28:15,910 --> 01:28:18,740

1490
01:28:18,740 --> 01:28:23,940
That means that c and c prime
differ in the Hamming

1491
01:28:23,940 --> 01:28:26,450
distance, number of places.

1492
01:28:26,450 --> 01:28:35,300
So if we map this into the
corresponding pair of vertices

1493
01:28:35,300 --> 01:28:38,980
of the n-cube in Euclidean
space, S of C and S of c

1494
01:28:38,980 --> 01:28:43,500
prime, how many coordinates are
these going to differ in?

1495
01:28:43,500 --> 01:28:46,720

1496
01:28:46,720 --> 01:28:51,150
It's going to differ in same
number of coordinates, D_h.

1497
01:28:51,150 --> 01:28:55,030
If they don't differ, what's
Euclidean squared distance in

1498
01:28:55,030 --> 01:28:56,810
those coordinates?

1499
01:28:56,810 --> 01:28:57,190
0.

1500
01:28:57,190 --> 01:29:01,300
If they do differ, the Euclidean
squared distance is

1501
01:29:01,300 --> 01:29:03,080
4 alpha squared.

1502
01:29:03,080 --> 01:29:11,320
So the Euclidean distance D_e
between S of C and S of c

1503
01:29:11,320 --> 01:29:15,000
prime is simply going to be
4 alpha squared times the

1504
01:29:15,000 --> 01:29:18,710
Hamming distance between
C and c prime, yes?

1505
01:29:18,710 --> 01:29:21,490

1506
01:29:21,490 --> 01:29:25,230
So I should say this is the
squared Euclidean distance.

1507
01:29:25,230 --> 01:29:26,430
Why do we always talk about the

1508
01:29:26,430 --> 01:29:27,600
squared Euclidean distance?

1509
01:29:27,600 --> 01:29:30,730
Because it's additive,
coordinate-wise.

1510
01:29:30,730 --> 01:29:33,900
And the Hamming distance is
additive, coordinate-wise.

1511
01:29:33,900 --> 01:29:36,260
So there's a nice
easy map here.

1512
01:29:36,260 --> 01:29:38,990

1513
01:29:38,990 --> 01:29:42,020
So what does this mean d_min
squared is going to be?

1514
01:29:42,020 --> 01:29:44,620

1515
01:29:44,620 --> 01:29:50,910
d_min squared of, let's say, S
of C. This constellation that

1516
01:29:50,910 --> 01:29:54,942
we've formed by taking the
Euclidean image of c.

1517
01:29:54,942 --> 01:30:00,050
The minimum square distance
between points in S of C is

1518
01:30:00,050 --> 01:30:05,140
just going to be 4 alpha squared
times d, where I don't

1519
01:30:05,140 --> 01:30:06,810
think I ever --

1520
01:30:06,810 --> 01:30:10,585
d equals min Hamming distance.

1521
01:30:10,585 --> 01:30:13,720

1522
01:30:13,720 --> 01:30:18,980
And we're always going to talk
about n, k, d as the three key

1523
01:30:18,980 --> 01:30:22,630
parameters of a binary
linear block code.

1524
01:30:22,630 --> 01:30:26,920
n is the code length, F2 to the
n, k is the dimension, d

1525
01:30:26,920 --> 01:30:29,085
is the minimum Hamming
distance.

1526
01:30:29,085 --> 01:30:32,930
So by going into this Hamming
geometry, we've got a third

1527
01:30:32,930 --> 01:30:34,730
key property of the code.

1528
01:30:34,730 --> 01:30:37,300
And we see it's key, because we
can get the minimum squared

1529
01:30:37,300 --> 01:30:40,160
distance between this Euclidean
image constellation,

1530
01:30:40,160 --> 01:30:43,488
just 4 alpha squared d.

1531
01:30:43,488 --> 01:30:45,868
AUDIENCE: nd makes
a probability of

1532
01:30:45,868 --> 01:30:48,248
[UNINTELLIGIBLE] that is
dependent on [UNINTELLIGIBLE]

1533
01:30:48,248 --> 01:30:49,210
then.

1534
01:30:49,210 --> 01:30:49,750
PROFESSOR: Correct.

1535
01:30:49,750 --> 01:30:53,780
This is all we need to know to
get the union bound estimate.

1536
01:30:53,780 --> 01:30:55,660
Well, a few more things.

1537
01:30:55,660 --> 01:31:05,590
We need to know what K_min
average of S of C. And what is

1538
01:31:05,590 --> 01:31:08,560
that going to be?

1539
01:31:08,560 --> 01:31:13,730
This is simply going to be the
number of words in the code.

1540
01:31:13,730 --> 01:31:17,780
To get this minimum squared
distance, we need a Hamming

1541
01:31:17,780 --> 01:31:20,570
distance of d.

1542
01:31:20,570 --> 01:31:24,700
So the number of words in the
code of distance d, which is

1543
01:31:24,700 --> 01:31:29,380
given by the parameter n sub d,
is simply going to be the

1544
01:31:29,380 --> 01:31:31,010
number of nearest neighbors.

1545
01:31:31,010 --> 01:31:35,210
Not just the average distance,
but I want to emphasize this

1546
01:31:35,210 --> 01:31:36,320
symmetry property.

1547
01:31:36,320 --> 01:31:41,700
If we stand on any point, on
any vertex of this cube in

1548
01:31:41,700 --> 01:31:44,610
n-space, which is the code
vertex, and we look at all the

1549
01:31:44,610 --> 01:31:48,030
other points in the
constellation, no matter which

1550
01:31:48,030 --> 01:31:50,280
point we stand on, we
will always see the

1551
01:31:50,280 --> 01:31:53,020
same profile of distances.

1552
01:31:53,020 --> 01:31:57,580
We'll see precisely nd code
words at Euclidean distance 4

1553
01:31:57,580 --> 01:31:58,990
alpha squared d.

1554
01:31:58,990 --> 01:32:03,410
We'll see nd plus 1 at Euclidean
squared distance 4

1555
01:32:03,410 --> 01:32:08,050
alpha squared d plus 1, and so
forth, right up the profile.

1556
01:32:08,050 --> 01:32:12,020
So there's complete symmetry
in the constellation.

1557
01:32:12,020 --> 01:32:15,500
In that universe, you don't know
which code point you're

1558
01:32:15,500 --> 01:32:17,910
standing on just by looking out,
because the world looks

1559
01:32:17,910 --> 01:32:20,330
the same to you.

1560
01:32:20,330 --> 01:32:21,580
Is that clear?

1561
01:32:21,580 --> 01:32:23,820

1562
01:32:23,820 --> 01:32:23,945
OK.

1563
01:32:23,945 --> 01:32:27,330
So from a communications point
of view, this is important,

1564
01:32:27,330 --> 01:32:30,720
because it means it doesn't
matter what code word we send.

1565
01:32:30,720 --> 01:32:34,010
The probability of error from
any code word is going to be

1566
01:32:34,010 --> 01:32:36,250
the same as the probability of
error from any other code

1567
01:32:36,250 --> 01:32:40,150
word, because the geometry
is exactly the same.

1568
01:32:40,150 --> 01:32:43,370
The Voronoi regions are
all the same shape.

1569
01:32:43,370 --> 01:32:46,210
So given the exact probability
of error, not just the

1570
01:32:46,210 --> 01:32:48,860
union-bound estimate, is going
to be independent of which

1571
01:32:48,860 --> 01:32:50,580
code word was sent.

1572
01:32:50,580 --> 01:32:54,310
This all follows from the fact
that it's a linear code and

1573
01:32:54,310 --> 01:32:58,820
therefore has the group
property, which translates

1574
01:32:58,820 --> 01:33:01,920
into this very strong
geometrical uniformity

1575
01:33:01,920 --> 01:33:04,400
property in Euclidean space.

1576
01:33:04,400 --> 01:33:08,020
Or actually in Hamming space
too, but it's more striking in

1577
01:33:08,020 --> 01:33:09,270
Euclidean space.

1578
01:33:09,270 --> 01:33:11,740

1579
01:33:11,740 --> 01:33:13,700
OK?

1580
01:33:13,700 --> 01:33:17,250
So we have everything we
need to write down

1581
01:33:17,250 --> 01:33:18,500
the union bound estimate.

1582
01:33:18,500 --> 01:33:22,620

1583
01:33:22,620 --> 01:33:30,030
Union bound estimate was just
the probably of error per bit

1584
01:33:30,030 --> 01:33:38,945
is well approximated by K_b of
constellation, in this case, S

1585
01:33:38,945 --> 01:33:48,870
of C, times Q of the square root
of the coding gain of the

1586
01:33:48,870 --> 01:33:52,340
constellation times
2 Eb over N_0.

1587
01:33:52,340 --> 01:33:59,429