1
00:00:00,000 --> 00:00:00,040

2
00:00:00,040 --> 00:00:01,310
PROFESSOR: I have
our final exam

3
00:00:01,310 --> 00:00:02,680
schedule from the registrar.

4
00:00:02,680 --> 00:00:06,980
It comes Tuesday morning
of exam week.

5
00:00:06,980 --> 00:00:08,310
It's on the web page.

6
00:00:08,310 --> 00:00:09,500
You won't miss it.

7
00:00:09,500 --> 00:00:14,340
I want to remind you that the
midterm exam is on Wednesday,

8
00:00:14,340 --> 00:00:19,720
March 16, that it starts at 9
not at 9:30 so that you're

9
00:00:19,720 --> 00:00:23,240
less time-limited than you
would be otherwise.

10
00:00:23,240 --> 00:00:26,020
It's a two-hour exam.

11
00:00:26,020 --> 00:00:31,280
And it will cover basically up
through chapter eight, which

12
00:00:31,280 --> 00:00:33,050
is Reed-Solomon codes.

13
00:00:33,050 --> 00:00:37,750
And you're responsible for
anything that's been

14
00:00:37,750 --> 00:00:38,900
discussed in class.

15
00:00:38,900 --> 00:00:41,170
If we haven't discussed
it in class, then

16
00:00:41,170 --> 00:00:42,730
don't worry about it.

17
00:00:42,730 --> 00:00:43,490
All right.

18
00:00:43,490 --> 00:00:45,260
Any questions about any
of those things?

19
00:00:45,260 --> 00:00:51,180

20
00:00:51,180 --> 00:00:53,000
It's 9 o'clock to 11 o'clock.

21
00:00:53,000 --> 00:00:55,620

22
00:00:55,620 --> 00:00:56,870
What's the underlined?

23
00:00:56,870 --> 00:01:00,720

24
00:01:00,720 --> 00:01:02,150
This line up here?

25
00:01:02,150 --> 00:01:03,820
This says, "This class
goes from 9:30

26
00:01:03,820 --> 00:01:09,280
to 11.00." Not 11:15.

27
00:01:09,280 --> 00:01:12,880
That's for me, not for you,
although I've tried to lay off

28
00:01:12,880 --> 00:01:16,670
some of the responsibility
on you.

29
00:01:16,670 --> 00:01:17,750
OK, let's continue.

30
00:01:17,750 --> 00:01:23,820
I hope to finish up chapter
six today, might not

31
00:01:23,820 --> 00:01:26,210
completely finish it.

32
00:01:26,210 --> 00:01:28,990
There are really three
topics left to go.

33
00:01:28,990 --> 00:01:32,810
One is the orthogonality
and inner product

34
00:01:32,810 --> 00:01:34,630
topic, which I skipped.

35
00:01:34,630 --> 00:01:37,940
The second is Reed-Muller
codes, which is our main

36
00:01:37,940 --> 00:01:42,040
objective in this chapter,
a family of useful codes.

37
00:01:42,040 --> 00:01:47,060
And the last topic is why
making hard decisions

38
00:01:47,060 --> 00:01:49,350
is not a good idea.

39
00:01:49,350 --> 00:01:51,930
And so I'll try to say
as much as I can

40
00:01:51,930 --> 00:01:54,090
about those three things.

41
00:01:54,090 --> 00:01:56,090
Just to remind you of where
we are, we're in the

42
00:01:56,090 --> 00:01:57,260
power-limited regime.

43
00:01:57,260 --> 00:02:01,860
We're trying to design good,
small-signal constellations,

44
00:02:01,860 --> 00:02:06,810
or moderate-sized signal
constellations now, with

45
00:02:06,810 --> 00:02:09,650
nominal spectral efficiency,
less than two bits per two

46
00:02:09,650 --> 00:02:11,910
dimensions.

47
00:02:11,910 --> 00:02:15,150
The technique we're using is
we're going to start from a

48
00:02:15,150 --> 00:02:19,430
binary linear block code
in Hamming space.

49
00:02:19,430 --> 00:02:22,070
And we're going to take the
Euclidean image of that and

50
00:02:22,070 --> 00:02:26,510
hope it's a good constellation
in Euclidean space.

51
00:02:26,510 --> 00:02:29,880
And as we were just talking
about before class, the fact

52
00:02:29,880 --> 00:02:38,590
that a linear code is a subspace
of F2 to the n means

53
00:02:38,590 --> 00:02:40,800
it's true if and only if,
really, it has the group

54
00:02:40,800 --> 00:02:44,540
property, which in Euclidean
space leads to a geometrical

55
00:02:44,540 --> 00:02:46,290
uniformity property.

56
00:02:46,290 --> 00:02:50,990
We haven't proved that
in its full scope.

57
00:02:50,990 --> 00:02:56,130
But we have noticed that from
every code word, every code

58
00:02:56,130 --> 00:02:58,700
word has the same distance
profile to

59
00:02:58,700 --> 00:03:00,520
all other code words.

60
00:03:00,520 --> 00:03:04,170
And in particular, the minimum
distance is the minimum weight

61
00:03:04,170 --> 00:03:06,200
of any non-zero code word.

62
00:03:06,200 --> 00:03:08,415
That's the main juice we've
squeezed out of

63
00:03:08,415 --> 00:03:10,780
that at this point.

64
00:03:10,780 --> 00:03:14,100
So we've now been talking a
little bit about the algebra

65
00:03:14,100 --> 00:03:16,590
of binary linear block codes.

66
00:03:16,590 --> 00:03:19,020
We've characterized them
basically by three parameters,

67
00:03:19,020 --> 00:03:22,840
n, k, d, where n is the length
of the code, k is the

68
00:03:22,840 --> 00:03:25,380
dimension of the code, d is the
minimum Hamming distance

69
00:03:25,380 --> 00:03:26,490
of the code.

70
00:03:26,490 --> 00:03:28,670
In the literature, this is what
you'll mainly find, in

71
00:03:28,670 --> 00:03:31,470
the n, k, d code.

72
00:03:31,470 --> 00:03:35,080
We have a subsidiary parameter,
the number of words

73
00:03:35,080 --> 00:03:38,950
of minimum distance d, which
we're going to need to get the

74
00:03:38,950 --> 00:03:41,800
error coefficient, or a
union-bound expression.

75
00:03:41,800 --> 00:03:43,855
This has less prominence
in the literature.

76
00:03:43,855 --> 00:03:46,710

77
00:03:46,710 --> 00:03:51,840
Given just these numbers, we get
a couple of key parameters

78
00:03:51,840 --> 00:03:52,880
of our constellation.

79
00:03:52,880 --> 00:03:57,440
One is its nominal spectral
efficiency, which is 2k over n

80
00:03:57,440 --> 00:04:01,445
bits per two dimension,
upper bounded by 2.

81
00:04:01,445 --> 00:04:05,120
Of course, often in the coding
literature, you talk about in

82
00:04:05,120 --> 00:04:07,540
a more natural quantity,
which is k over n,

83
00:04:07,540 --> 00:04:09,200
called the code rate.

84
00:04:09,200 --> 00:04:12,100
Maybe I shouldn't call it cap-R,
because R is used for

85
00:04:12,100 --> 00:04:14,600
the code rate in bits
per second.

86
00:04:14,600 --> 00:04:17,415
This means bit per symbol.

87
00:04:17,415 --> 00:04:20,714
So just let me call this rate.

88
00:04:20,714 --> 00:04:23,680

89
00:04:23,680 --> 00:04:25,820
But when you're reading the
coding literature, the rate of

90
00:04:25,820 --> 00:04:29,350
the code means how many
information bits per how many

91
00:04:29,350 --> 00:04:30,880
transmitted bits.

92
00:04:30,880 --> 00:04:37,310
And for n, k, d binary linear
block code, it's k over m.

93
00:04:37,310 --> 00:04:41,540
And the nominal spectral
efficiency is just twice that,

94
00:04:41,540 --> 00:04:44,200
since we measure it per
two dimensions.

95
00:04:44,200 --> 00:04:48,100
OK, and even more importantly,
we get the union bound

96
00:04:48,100 --> 00:04:51,110
estimate in terms of a couple
of simple parameters.

97
00:04:51,110 --> 00:04:54,910
It's just an error coefficient,
Kb, the number of

98
00:04:54,910 --> 00:04:58,170
nearest neighbors per bit
times this Q function

99
00:04:58,170 --> 00:05:01,840
expression, which always has 2Eb
over N_0 in it, multiplied

100
00:05:01,840 --> 00:05:06,590
by this multiplicative factor,
which we call the coding gain,

101
00:05:06,590 --> 00:05:09,320
which is just kd over n.

102
00:05:09,320 --> 00:05:12,715
And this is equal to one
for a 1,1,1 code.

103
00:05:12,715 --> 00:05:16,300
Now you know coding.

104
00:05:16,300 --> 00:05:18,960
So anything else?

105
00:05:18,960 --> 00:05:24,080
Our basic effort is to get
a larger coding gain by

106
00:05:24,080 --> 00:05:28,300
constructing more complicated
codes.

107
00:05:28,300 --> 00:05:31,390
This parameter here, which we
need in order to actually plot

108
00:05:31,390 --> 00:05:35,050
the curve and estimate the
effective coding gain -- the

109
00:05:35,050 --> 00:05:38,860
effective coding gain is derated
from the nominal

110
00:05:38,860 --> 00:05:43,810
coding gain by a rule of thumb,
which depends on Kb.

111
00:05:43,810 --> 00:05:48,650
It's every factor of 2 in Kb
costs you 0.2 dB, roughly in

112
00:05:48,650 --> 00:05:51,660
the right range, if it's not too
big, all those qualifiers.

113
00:05:51,660 --> 00:05:53,410
But it's a good engineering
rule of thumb.

114
00:05:53,410 --> 00:05:56,140
And that's just the number of
nearest neighbors per code

115
00:05:56,140 --> 00:05:58,120
word divided by k.

116
00:05:58,120 --> 00:06:01,970
And so our object here is to
see how well we can do.

117
00:06:01,970 --> 00:06:06,040
And the Reed-Muller codes will
be an infinite family of codes

118
00:06:06,040 --> 00:06:10,500
that give us a pretty good idea
of what can be achieved

119
00:06:10,500 --> 00:06:14,640
for a variety of n, k, d that
kind of cover the waterfront.

120
00:06:14,640 --> 00:06:16,130
That's why I talk about
them first.

121
00:06:16,130 --> 00:06:19,250
They're all so very simple.

122
00:06:19,250 --> 00:06:24,370
OK, but first, we forgot to talk
about orthogonality and

123
00:06:24,370 --> 00:06:30,360
inner products and duality, both
from a geometric point of

124
00:06:30,360 --> 00:06:33,010
view and from an algebraic
point of view.

125
00:06:33,010 --> 00:06:39,785
And so I want to go back
and recover that.

126
00:06:39,785 --> 00:06:50,610
The definition of an inner
product between x and y, where

127
00:06:50,610 --> 00:07:03,300
x and y are both binary
n-tuples, is, as you'd expect,

128
00:07:03,300 --> 00:07:06,190
a sort of dot product
expression, a component-wise

129
00:07:06,190 --> 00:07:15,810
product, the sum over k of xk
yk, where all the arithmetic

130
00:07:15,810 --> 00:07:17,330
here is in the binary
field, F2.

131
00:07:17,330 --> 00:07:20,780

132
00:07:20,780 --> 00:07:29,040
And well, this clearly has the
bilinearity properties that

133
00:07:29,040 --> 00:07:33,120
you expect of an inner product
that's linear in x for a fixed

134
00:07:33,120 --> 00:07:34,530
y or vice versa.

135
00:07:34,530 --> 00:07:37,510

136
00:07:37,510 --> 00:07:41,850
But it doesn't turn out to have
the geometric properties

137
00:07:41,850 --> 00:07:43,440
that you expect.

138
00:07:43,440 --> 00:07:54,630
We can define orthogonality,
this is another definition, in

139
00:07:54,630 --> 00:07:55,780
the usual way.

140
00:07:55,780 --> 00:07:59,893
x and y are said to
be orthogonal --

141
00:07:59,893 --> 00:08:03,889

142
00:08:03,889 --> 00:08:05,400
do that better.

143
00:08:05,400 --> 00:08:11,070
x is said to be orthogonal to
y if and only if their inner

144
00:08:11,070 --> 00:08:15,850
product is 0, which is the same
definition you know from

145
00:08:15,850 --> 00:08:20,280
real and complex
vector spaces.

146
00:08:20,280 --> 00:08:21,160
OK.

147
00:08:21,160 --> 00:08:26,940
But the overall moral I want you
to get from this is while

148
00:08:26,940 --> 00:08:30,210
this inner product behaves
absolutely as you expect in an

149
00:08:30,210 --> 00:08:32,870
algebraic sense, it behaves very
different from what you

150
00:08:32,870 --> 00:08:36,669
expect in a geometric sense.

151
00:08:36,669 --> 00:08:37,960
So the algebra's fine.

152
00:08:37,960 --> 00:08:40,940
The geometry is screwy.

153
00:08:40,940 --> 00:08:41,258
All right.

154
00:08:41,258 --> 00:08:45,200
That's the catch word
to keep in mind.

155
00:08:45,200 --> 00:08:47,750
Why is that?

156
00:08:47,750 --> 00:08:51,830
Where does this inner
product live?

157
00:08:51,830 --> 00:08:53,790
It's F2 valued, right?

158
00:08:53,790 --> 00:08:57,210
I'm just doing this sum in
binary space, and the result

159
00:08:57,210 --> 00:08:59,840
is either 0 or 1.

160
00:08:59,840 --> 00:09:09,470
So when are two n-tuples
orthogonal?

161
00:09:09,470 --> 00:09:15,380
Simply if they have an even
number of places in which

162
00:09:15,380 --> 00:09:17,591
they're both equal to 1.

163
00:09:17,591 --> 00:09:18,841
Is there a question?

164
00:09:18,841 --> 00:09:22,600

165
00:09:22,600 --> 00:09:32,780
In particular, suppose I try to
define a norm in the usual

166
00:09:32,780 --> 00:09:36,290
way, like that.

167
00:09:36,290 --> 00:09:38,095
Is that going to have
the properties that

168
00:09:38,095 --> 00:09:41,130
I'd want of a norm?

169
00:09:41,130 --> 00:09:43,410
No.

170
00:09:43,410 --> 00:09:43,850
Why?

171
00:09:43,850 --> 00:09:50,650
Because one of the basic
properties we want of a norm

172
00:09:50,650 --> 00:09:57,030
is strict positivity, that the
norm of x is equal to 0 if and

173
00:09:57,030 --> 00:09:59,400
only if x is equal to 0.

174
00:09:59,400 --> 00:10:02,010
That's clearly not true here.

175
00:10:02,010 --> 00:10:06,415
What's the requirement for the
inner product of x with itself

176
00:10:06,415 --> 00:10:08,430
to be equal to 0, in
other words x to be

177
00:10:08,430 --> 00:10:11,566
orthogonal with itself?

178
00:10:11,566 --> 00:10:14,060
It just simply has to have
an even number of 1's.

179
00:10:14,060 --> 00:10:18,230
If it has an even number
of 1's, then this

180
00:10:18,230 --> 00:10:19,690
so-called norm is 0.

181
00:10:19,690 --> 00:10:22,500
If there's an odd
number, it's 1.

182
00:10:22,500 --> 00:10:27,480
So it's perfectly possible for
a vector to be orthogonal to

183
00:10:27,480 --> 00:10:30,690
itself, a non-zero vector to
be orthogonal to itself.

184
00:10:30,690 --> 00:10:35,850
And that's basically where all
the trouble comes from in a

185
00:10:35,850 --> 00:10:37,100
geometric sense.

186
00:10:37,100 --> 00:10:40,123

187
00:10:40,123 --> 00:10:43,636
AUDIENCE: So which of them would
be [INAUDIBLE] here?

188
00:10:43,636 --> 00:10:44,220
PROFESSOR: It's mod-2.

189
00:10:44,220 --> 00:10:45,450
It's in F2.

190
00:10:45,450 --> 00:10:49,170
All the arithmetic rules
are from F2 which is

191
00:10:49,170 --> 00:10:52,350
mod-2 rules, correct.

192
00:10:52,350 --> 00:10:53,270
So, good.

193
00:10:53,270 --> 00:10:57,090
This means at the most
fundamental level, we don't

194
00:10:57,090 --> 00:10:59,080
have a Hilbert space here.

195
00:10:59,080 --> 00:11:01,800
We don't have a projection
theorem.

196
00:11:01,800 --> 00:11:06,390
Projection theorem is the basic
tool we use in Euclidean

197
00:11:06,390 --> 00:11:10,650
spaces, more generally,
Hilbert spaces.

198
00:11:10,650 --> 00:11:14,040
Just say that every vector
can be partitioned.

199
00:11:14,040 --> 00:11:19,050
In a given space and its
orthogonal space, we can

200
00:11:19,050 --> 00:11:22,070
express a vector as the sum of
its projection onto the space

201
00:11:22,070 --> 00:11:24,300
and the projection onto the
orthogonal space, which are

202
00:11:24,300 --> 00:11:25,980
two orthogonal vectors.

203
00:11:25,980 --> 00:11:29,480
So it's an orthogonal
decomposition.

204
00:11:29,480 --> 00:11:33,040
So we have nothing like the
projection theorem here.

205
00:11:33,040 --> 00:11:37,040
Therefore we have nothing like,
we don't necessarily

206
00:11:37,040 --> 00:11:39,290
have orthonormal or even

207
00:11:39,290 --> 00:11:47,084
orthogonal basis for subspaces.

208
00:11:47,084 --> 00:11:48,334
AUDIENCE: [INAUDIBLE]?

209
00:11:48,334 --> 00:11:51,470

210
00:11:51,470 --> 00:11:53,510
PROFESSOR: You do have a unique
orthogonal complement.

211
00:11:53,510 --> 00:11:57,490
I'll get to that in a second.

212
00:11:57,490 --> 00:12:09,830
But for instance, we might have
that a subspace can be

213
00:12:09,830 --> 00:12:11,080
orthogonal to itself.

214
00:12:11,080 --> 00:12:13,690

215
00:12:13,690 --> 00:12:15,145
That's what the problem is.

216
00:12:15,145 --> 00:12:17,760

217
00:12:17,760 --> 00:12:24,860
For instance, 0, 0, and 1,
1 is a nice, little,

218
00:12:24,860 --> 00:12:26,330
one-dimensional subspace.

219
00:12:26,330 --> 00:12:28,020
And what's it's orthogonal
subspace?

220
00:12:28,020 --> 00:12:29,270
It's itself.

221
00:12:29,270 --> 00:12:32,830

222
00:12:32,830 --> 00:12:37,120
We may not have an orthogonal
basis for a subspace.

223
00:12:37,120 --> 00:12:41,246
And for an example of that, I'll
give you our favorite 3,

224
00:12:41,246 --> 00:12:43,710
2, 2 code, as I'll
now call it.

225
00:12:43,710 --> 00:12:46,630
It consists of these
four code words.

226
00:12:46,630 --> 00:12:51,500
A set of generators for this
code consists of any two of

227
00:12:51,500 --> 00:12:53,490
the non-zero code words.

228
00:12:53,490 --> 00:12:56,830
You can generate all of the code
words as binary linear

229
00:12:56,830 --> 00:12:59,490
combinations of any
two of these.

230
00:12:59,490 --> 00:13:02,900
But no two of these
are orthogonal.

231
00:13:02,900 --> 00:13:04,370
So there's clearly
no orthogonal

232
00:13:04,370 --> 00:13:06,090
basis for that code.

233
00:13:06,090 --> 00:13:09,720
We shouldn't expect to find
orthogonal basis, orthogonal

234
00:13:09,720 --> 00:13:13,095
decomposition, so all of these
sorts of tools that we relied

235
00:13:13,095 --> 00:13:16,765
on heavily in 6.450 in
Euclidean spaces.

236
00:13:16,765 --> 00:13:19,290

237
00:13:19,290 --> 00:13:23,870
OK, so this is just a great
caution to the student.

238
00:13:23,870 --> 00:13:26,590

239
00:13:26,590 --> 00:13:30,380
Don't expect Hamming space to
have the same geometric

240
00:13:30,380 --> 00:13:33,490
properties as Euclidean space.

241
00:13:33,490 --> 00:13:33,970
Yes?

242
00:13:33,970 --> 00:13:35,220
AUDIENCE: [INAUDIBLE]?

243
00:13:35,220 --> 00:13:39,160

244
00:13:39,160 --> 00:13:40,360
PROFESSOR: Nothing special.

245
00:13:40,360 --> 00:13:43,910
It's just finite fields have
a different geometry.

246
00:13:43,910 --> 00:13:47,570
In F2, there's really only one
geometry you would impose,

247
00:13:47,570 --> 00:13:48,765
which is the Hamming geometry.

248
00:13:48,765 --> 00:13:53,010
In other finite fields, there
actually could be more than

249
00:13:53,010 --> 00:13:55,910
one geometry.

250
00:13:55,910 --> 00:14:01,510
But let's say the algebraic
properties, however, you can

251
00:14:01,510 --> 00:14:02,760
still count on.

252
00:14:02,760 --> 00:14:13,820

253
00:14:13,820 --> 00:14:26,040
For instance, n, k, d
code C has, as we've

254
00:14:26,040 --> 00:14:30,346
already shown, a basis.

255
00:14:30,346 --> 00:14:31,795
It has k dimensions.

256
00:14:31,795 --> 00:14:44,670
It has a basis g1 up to gk of
k, linearly independent,

257
00:14:44,670 --> 00:14:49,900
though not necessarily
orthogonal basis vectors.

258
00:14:49,900 --> 00:14:59,910
So we can always write the code
as the set of all u g

259
00:14:59,910 --> 00:15:06,590
such that u is a k-tuple of
information bits, let's say.

260
00:15:06,590 --> 00:15:10,740
In other words, this is a
compressed form for the set of

261
00:15:10,740 --> 00:15:16,820
all binary linear combinations
of these generators, where

262
00:15:16,820 --> 00:15:27,960
I've written what's called a
generator matrix, g as a k by

263
00:15:27,960 --> 00:15:33,105
n matrix, whose rows are
these generators.

264
00:15:33,105 --> 00:15:37,160

265
00:15:37,160 --> 00:15:41,570
And I've multiplied on the left
with a row vector u, if

266
00:15:41,570 --> 00:15:46,670
I'm doing it in matrix terms.

267
00:15:46,670 --> 00:15:49,010
You can do this more abstractly
just as a linear

268
00:15:49,010 --> 00:15:51,620
transformation.

269
00:15:51,620 --> 00:15:56,100
And side comment, notice that
in coding theory, it's

270
00:15:56,100 --> 00:15:58,860
conventional to write vectors
as row vectors, whereas in

271
00:15:58,860 --> 00:16:01,720
every other subject you take,
it's conventional to write

272
00:16:01,720 --> 00:16:05,140
vectors as column vectors.

273
00:16:05,140 --> 00:16:05,880
Why is this?

274
00:16:05,880 --> 00:16:08,170
Is there some deep,
philosophical reason?

275
00:16:08,170 --> 00:16:08,660
No.

276
00:16:08,660 --> 00:16:11,900
It's just the way people started
to do it in coding

277
00:16:11,900 --> 00:16:14,360
theory back at the beginning,
and then everybody has

278
00:16:14,360 --> 00:16:15,430
followed them.

279
00:16:15,430 --> 00:16:18,850
I may have even had something
to do with this myself.

280
00:16:18,850 --> 00:16:21,550
And I'll tell you the reason I
like to write vectors as row

281
00:16:21,550 --> 00:16:23,222
vectors is I don't have
to write a little

282
00:16:23,222 --> 00:16:25,350
t up next to them.

283
00:16:25,350 --> 00:16:27,820
That's the deep philosophical
reason.

284
00:16:27,820 --> 00:16:30,480

285
00:16:30,480 --> 00:16:32,860
It's like driving on the right
side or the left side.

286
00:16:32,860 --> 00:16:35,830
Obviously, you could have chosen
how to do it one way or

287
00:16:35,830 --> 00:16:37,090
another back in the beginning.

288
00:16:37,090 --> 00:16:41,560
But once you've chosen it,
you better stick with it.

289
00:16:41,560 --> 00:16:49,550
There's actually some insight
involved here.

290
00:16:49,550 --> 00:16:52,210
This is sort of associated with
a block diagram, where we

291
00:16:52,210 --> 00:16:55,700
take k bits, and we run
it through this linear

292
00:16:55,700 --> 00:16:57,360
transformation.

293
00:16:57,360 --> 00:17:05,819
And as a result, we get out,
what shall I write, x n bits.

294
00:17:05,819 --> 00:17:09,599
And in block diagrams, we tend
to take the input bits from

295
00:17:09,599 --> 00:17:12,940
the left and proceed to
the right, left to

296
00:17:12,940 --> 00:17:14,050
right kind of thing.

297
00:17:14,050 --> 00:17:21,450
So this formula reflects this
left to right picture, whereas

298
00:17:21,450 --> 00:17:26,560
I'd say the deeper reason why
you usually see G u in system

299
00:17:26,560 --> 00:17:31,710
theory is that G is regarded
as an operator

300
00:17:31,710 --> 00:17:33,190
that operates on u.

301
00:17:33,190 --> 00:17:36,750
It's kind of a G of u.

302
00:17:36,750 --> 00:17:41,240
And so that's why it's more
natural to think of this as

303
00:17:41,240 --> 00:17:44,500
being a column vector,
because then, we

304
00:17:44,500 --> 00:17:46,230
have a different picture.

305
00:17:46,230 --> 00:17:49,270
G is the operator that
somehow transforms u.

306
00:17:49,270 --> 00:17:51,990
But these are all side
comments, obviously.

307
00:17:51,990 --> 00:17:56,110
They don't really matter
for anything.

308
00:17:56,110 --> 00:18:05,645
All right, just remember that
vectors are row vectors.

309
00:18:05,645 --> 00:18:09,030

310
00:18:09,030 --> 00:18:11,120
OK.

311
00:18:11,120 --> 00:18:17,720
Let's define the dual code in
the natural way, as the

312
00:18:17,720 --> 00:18:18,970
orthogonal code.

313
00:18:18,970 --> 00:18:24,590

314
00:18:24,590 --> 00:18:27,230
Say C dual.

315
00:18:27,230 --> 00:18:44,840
The definition is that C dual is
the set of all n-tuples y,

316
00:18:44,840 --> 00:18:49,330
such that x, the inner product
between x and y is 0.

317
00:18:49,330 --> 00:18:53,130
In other words, y is orthogonal
to x for all the x

318
00:18:53,130 --> 00:18:57,470
and C. It's the set of all
n-tuples that are orthogonal

319
00:18:57,470 --> 00:19:02,460
to all the words in C under
our F2 definition of inner

320
00:19:02,460 --> 00:19:05,390
product orthogonality.

321
00:19:05,390 --> 00:19:10,170
OK, so that's a natural
definition.

322
00:19:10,170 --> 00:19:16,270
For example, as I've already
shown you, if C is 0, 0, 1, 1,

323
00:19:16,270 --> 00:19:20,860
then C dual is 0, 0, 1, 1.

324
00:19:20,860 --> 00:19:27,860
If C were 0, 0, 0, 1, then C
dual would be 0, 0, what?

325
00:19:27,860 --> 00:19:31,400

326
00:19:31,400 --> 00:19:32,020
1, 0.

327
00:19:32,020 --> 00:19:33,990
Thank you.

328
00:19:33,990 --> 00:19:38,670
Because 1, 1 is not orthogonal
to this, 0, 1 and is not

329
00:19:38,670 --> 00:19:40,420
orthogonal to this.

330
00:19:40,420 --> 00:19:44,170
So we simply go through
and pick it out.

331
00:19:44,170 --> 00:19:49,590
Now as I said, the algebraic
properties of the

332
00:19:49,590 --> 00:19:52,608
dual code are OK.

333
00:19:52,608 --> 00:19:56,560
I emphasize they're algebraic.

334
00:19:56,560 --> 00:20:07,350
If C is an n, k code, in other
words, has dimension k, what

335
00:20:07,350 --> 00:20:10,070
do you expect the parameters
of C dual to be?

336
00:20:10,070 --> 00:20:13,610

337
00:20:13,610 --> 00:20:16,155
Its length is what?

338
00:20:16,155 --> 00:20:17,535
It's n, of course.

339
00:20:17,535 --> 00:20:20,070

340
00:20:20,070 --> 00:20:22,160
And what's its dimension
going to be?

341
00:20:22,160 --> 00:20:25,880
If C has dimension k, what do
you guess the dimension of C

342
00:20:25,880 --> 00:20:27,130
dual is going to be?

343
00:20:27,130 --> 00:20:31,350

344
00:20:31,350 --> 00:20:34,060
Just guess from Euclidean
spaces, or any --

345
00:20:34,060 --> 00:20:35,440
it's n minus k.

346
00:20:35,440 --> 00:20:39,420
The dual space has dimension
n minus k.

347
00:20:39,420 --> 00:20:40,670
And that holds.

348
00:20:40,670 --> 00:20:43,130

349
00:20:43,130 --> 00:20:45,930
In the notes, I give two
proofs for this.

350
00:20:45,930 --> 00:20:49,550
There's the conventional coding
theory textbook proof,

351
00:20:49,550 --> 00:20:53,920
which involves writing down
a generator matrix for C k

352
00:20:53,920 --> 00:20:56,950
generators, reducing it to a
canonical form, called the

353
00:20:56,950 --> 00:21:01,810
systematic form, where there's
some k by k identity matrix

354
00:21:01,810 --> 00:21:09,490
and a n minus k by k
parity check part.

355
00:21:09,490 --> 00:21:12,550
Then, by inspection, you can
write down a generator matrix

356
00:21:12,550 --> 00:21:13,650
for C dual.

357
00:21:13,650 --> 00:21:17,360
And you find it has dimension
n minus k.

358
00:21:17,360 --> 00:21:20,660
It's kind of a klutzy proof,
in my opinion.

359
00:21:20,660 --> 00:21:23,200
A second, more elegant proof,
but one that you don't have

360
00:21:23,200 --> 00:21:27,740
the background for yet, is to
use simply the fundamental

361
00:21:27,740 --> 00:21:28,990
theorem of homomorphisms.

362
00:21:28,990 --> 00:21:31,510

363
00:21:31,510 --> 00:21:33,650
This is in some sense
an image.

364
00:21:33,650 --> 00:21:37,440
This is the dual of an image,
which is a kernel.

365
00:21:37,440 --> 00:21:40,800
You work out the dimensions
from that.

366
00:21:40,800 --> 00:21:47,335
I am still in search of an
elegant, elementary proof.

367
00:21:47,335 --> 00:21:52,780
And anyone who can come up
with a proof suitable for

368
00:21:52,780 --> 00:21:54,625
chapter six gets a gold star.

369
00:21:54,625 --> 00:21:57,880

370
00:21:57,880 --> 00:22:03,160
Believe me, the gold star will
be very valuable to you.

371
00:22:03,160 --> 00:22:07,110
OK, so exercise for any student
so inclined, give me a

372
00:22:07,110 --> 00:22:08,000
nice proof of this.

373
00:22:08,000 --> 00:22:10,930
It's surprisingly hard.

374
00:22:10,930 --> 00:22:14,480
And I can't say I've spent great
quantities of my life on

375
00:22:14,480 --> 00:22:17,780
it, but I've spent
some time on it.

376
00:22:17,780 --> 00:22:23,970
So anyway, the dimensions come
out as I hope you would

377
00:22:23,970 --> 00:22:27,010
expect, based on your
past experience.

378
00:22:27,010 --> 00:22:31,510
And I won't give you
a proof in class.

379
00:22:31,510 --> 00:22:36,330
You get the fundamental duality
relationship, that the

380
00:22:36,330 --> 00:22:39,600
dual of C dual, what would
you expects that to be?

381
00:22:39,600 --> 00:22:42,360

382
00:22:42,360 --> 00:22:45,970
C. OK.

383
00:22:45,970 --> 00:22:53,020
In words, C is the set of all
n-uples that are orthogonal to

384
00:22:53,020 --> 00:22:56,600
all the n-tuples in C dual.

385
00:22:56,600 --> 00:22:59,870

386
00:22:59,870 --> 00:22:59,970
OK.

387
00:22:59,970 --> 00:23:04,610
So this actually means that I
can specify C. If I know C

388
00:23:04,610 --> 00:23:10,420
dual, I know C. Give me C dual,
the set of all code

389
00:23:10,420 --> 00:23:14,280
words orthogonal to it
tells me what C is.

390
00:23:14,280 --> 00:23:23,100
So this implies that I can write
C in the following form.

391
00:23:23,100 --> 00:23:33,260
C is the set of all, just
emulating this, y n F2 to the

392
00:23:33,260 --> 00:23:43,780
n such that x, y equals zero
for all x in C dual.

393
00:23:43,780 --> 00:23:48,470
I probably should have
interchanged x and y for this.

394
00:23:48,470 --> 00:23:51,666
x such that x, y equals
0 for all --

395
00:23:51,666 --> 00:23:55,450

396
00:23:55,450 --> 00:23:56,265
this is symmetrical.

397
00:23:56,265 --> 00:23:58,880
The inner product of x and y is
equal to the inner product

398
00:23:58,880 --> 00:23:59,590
of y and x.

399
00:23:59,590 --> 00:24:03,600
So I don't care how
I write it.

400
00:24:03,600 --> 00:24:08,250
OK, so I can actually
specify a code by a

401
00:24:08,250 --> 00:24:12,010
set of parity checks.

402
00:24:12,010 --> 00:24:23,290
Now suppose I have a generator
matrix, call it H, namely a

403
00:24:23,290 --> 00:24:33,670
set of generators, H1 through
Hn minus k, for C dual.

404
00:24:33,670 --> 00:24:37,832
I'm going to have a set of
n minus k generators.

405
00:24:37,832 --> 00:24:42,580
Then I hope it's obvious that
I can test whether x is

406
00:24:42,580 --> 00:24:50,580
orthogonal to all of C dual by
just checking whether it's

407
00:24:50,580 --> 00:24:54,720
orthogonal to all of
these generators.

408
00:24:54,720 --> 00:25:04,060
So I would now have C is the set
of all x n-tuples x such

409
00:25:04,060 --> 00:25:12,560
that x, H, j equals
zero, all j.

410
00:25:12,560 --> 00:25:12,880
OK.

411
00:25:12,880 --> 00:25:16,300
I've just got to test
orthogonality to each of these

412
00:25:16,300 --> 00:25:18,290
generators.

413
00:25:18,290 --> 00:25:22,390
In other words, in each
of these is what we

414
00:25:22,390 --> 00:25:25,400
call a parity check.

415
00:25:25,400 --> 00:25:29,040
We take the inner product of x
with a certain n-tuple, and we

416
00:25:29,040 --> 00:25:31,600
ask whether parity checks.

417
00:25:31,600 --> 00:25:34,350
In other words, we ask whether
the subset of positions in

418
00:25:34,350 --> 00:25:39,160
which H, j is equal to 1, in
those positions, whether x has

419
00:25:39,160 --> 00:25:42,610
an even number of 1's.

420
00:25:42,610 --> 00:25:46,540
Get very concrete about it.

421
00:25:46,540 --> 00:25:55,752
So writing this out in matrix
form, the test is C is the set

422
00:25:55,752 --> 00:26:05,990
of x in F2 to the n such that
x h-transpose equals 0.

423
00:26:05,990 --> 00:26:08,750

424
00:26:08,750 --> 00:26:12,600
That's just a matrix form of
what I've written up there.

425
00:26:12,600 --> 00:26:15,810
So let me picture
it like this.

426
00:26:15,810 --> 00:26:23,380
Here the test is, I take
x, which is n bits.

427
00:26:23,380 --> 00:26:26,320
I put it into what's
called a parity

428
00:26:26,320 --> 00:26:29,060
checker or syndrome reformer.

429
00:26:29,060 --> 00:26:32,990
And I ask whether this is 0.

430
00:26:32,990 --> 00:26:36,470
We call this, in general,
the syndrome.

431
00:26:36,470 --> 00:26:39,420
And we ask whether it's 0.

432
00:26:39,420 --> 00:26:42,170
If we get a 0, we say
x is in the code.

433
00:26:42,170 --> 00:26:44,300
If it's not 0, then x
is not in the code.

434
00:26:44,300 --> 00:26:45,550
That's the test.

435
00:26:45,550 --> 00:26:50,420

436
00:26:50,420 --> 00:27:02,070
So when we summarize, we really
have two dual ways of

437
00:27:02,070 --> 00:27:08,750
characterizing a code, which
you will see in the

438
00:27:08,750 --> 00:27:10,000
literature.

439
00:27:10,000 --> 00:27:12,570

440
00:27:12,570 --> 00:27:19,980
We have a generator matrix, we
might give a k by n generator

441
00:27:19,980 --> 00:27:23,280
matrix for the code.

442
00:27:23,280 --> 00:27:33,350
And then the code is specified
as C is the set of all U g

443
00:27:33,350 --> 00:27:43,170
such that U n F2 to the k.

444
00:27:43,170 --> 00:27:46,380
In other words, this is an
image representation.

445
00:27:46,380 --> 00:27:49,185
We take C as the image of
a linear transformation.

446
00:27:49,185 --> 00:27:52,570

447
00:27:52,570 --> 00:27:54,700
We call G a linear
transformation.

448
00:27:54,700 --> 00:28:04,840
It goes from Fk to F2 to
the k to F2 to the n.

449
00:28:04,840 --> 00:28:07,150
And then the code is simply
the image of this

450
00:28:07,150 --> 00:28:09,570
transformation algebraically.

451
00:28:09,570 --> 00:28:12,850

452
00:28:12,850 --> 00:28:13,410
OK.

453
00:28:13,410 --> 00:28:21,210
Or we can specify it by means
of a parity check matrix, H,

454
00:28:21,210 --> 00:28:24,490
which is the generator matrix
of the dual code.

455
00:28:24,490 --> 00:28:27,660
So this would be the parity
check matrix for the dual code

456
00:28:27,660 --> 00:28:32,020
G. h is the generator matrix
of the dual code.

457
00:28:32,020 --> 00:28:35,960
And we ask whether --

458
00:28:35,960 --> 00:28:44,960
now we specify it as I have up
here, simply the x and F2 to

459
00:28:44,960 --> 00:28:51,280
the n such that x
H_t equals 0.

460
00:28:51,280 --> 00:28:57,410
And this is what's called a
kernel representation, because

461
00:28:57,410 --> 00:29:04,450
it's the kernel of a linear
transformation defined by H2

462
00:29:04,450 --> 00:29:11,490
from F2 to the end, down
to, this is a m

463
00:29:11,490 --> 00:29:13,810
by n minus k matrix.

464
00:29:13,810 --> 00:29:18,750
So the syndrome is actually
an n-minus-k-tuple.

465
00:29:18,750 --> 00:29:22,000
The elements of the syndrome are
the n minus k individual

466
00:29:22,000 --> 00:29:23,547
bits, parity check bits.

467
00:29:23,547 --> 00:29:24,797
OK.

468
00:29:24,797 --> 00:29:29,210

469
00:29:29,210 --> 00:29:33,640
And sometimes it's more
convenient to characterize the

470
00:29:33,640 --> 00:29:36,620
code in one way, and sometimes
it's more convenient to

471
00:29:36,620 --> 00:29:39,650
characterize it in
the other way.

472
00:29:39,650 --> 00:29:47,560
For instance, we were talking
last time about the n, n minus

473
00:29:47,560 --> 00:29:53,280
1, 2 single parity check code,
or the even weight code, the

474
00:29:53,280 --> 00:29:55,640
set of all even weight
n-tuples, which has

475
00:29:55,640 --> 00:29:57,880
dimension n minus 1.

476
00:29:57,880 --> 00:30:02,710
And in general, for high-rate
codes especially, it may be

477
00:30:02,710 --> 00:30:06,890
simpler to give the parity
check representation.

478
00:30:06,890 --> 00:30:08,525
What is the dual code?

479
00:30:08,525 --> 00:30:11,970
Let's call this C.
C dual is what?

480
00:30:11,970 --> 00:30:19,490

481
00:30:19,490 --> 00:30:25,024
C dual is what we call the
n, 1, n repetition code.

482
00:30:25,024 --> 00:30:27,830
In other words, it has
dimension one.

483
00:30:27,830 --> 00:30:31,750
It has two code words, the all-0
word and the all-1 word.

484
00:30:31,750 --> 00:30:35,290

485
00:30:35,290 --> 00:30:40,470
Clearly, the all-1 word is
orthogonal to all of the even

486
00:30:40,470 --> 00:30:41,450
weight words.

487
00:30:41,450 --> 00:30:45,090
And vice versa, a word is even
weight if and only if it's

488
00:30:45,090 --> 00:30:48,620
orthogonal to all 1's.

489
00:30:48,620 --> 00:30:53,320
So in this case, what is
the generator matrix?

490
00:30:53,320 --> 00:30:57,560
We had a generator matrix last
time consisting of n minus 1

491
00:30:57,560 --> 00:31:01,080
weight 2 code words all arranged
in a kind of double

492
00:31:01,080 --> 00:31:02,300
diagonal pattern.

493
00:31:02,300 --> 00:31:03,970
That's OK.

494
00:31:03,970 --> 00:31:07,030
But that's an n minus
1 by n matrix.

495
00:31:07,030 --> 00:31:09,850

496
00:31:09,850 --> 00:31:13,010
Most people would say it's
easier to say, OK, what's the

497
00:31:13,010 --> 00:31:15,256
parity check matrix?

498
00:31:15,256 --> 00:31:22,110
The parity check matrix in this
case, H, is simply a one

499
00:31:22,110 --> 00:31:26,950
by n matrix consisting
of all one's.

500
00:31:26,950 --> 00:31:31,470
And what's the characterization
of the code?

501
00:31:31,470 --> 00:31:34,120
The code consists of all
the words that are

502
00:31:34,120 --> 00:31:37,290
orthogonal to this.

503
00:31:37,290 --> 00:31:40,120
And that is why we call it
single parity check code.

504
00:31:40,120 --> 00:31:41,650
There's one parity check.

505
00:31:41,650 --> 00:31:44,040
And if you pass the parity
check, you're in the code.

506
00:31:44,040 --> 00:31:47,050
And if you don't, you're not.

507
00:31:47,050 --> 00:31:50,850
OK, so we see that these,
first of all, here's an

508
00:31:50,850 --> 00:31:52,900
example of dual codes.

509
00:31:52,900 --> 00:31:54,580
Are their dimensions correct?

510
00:31:54,580 --> 00:31:55,460
They are.

511
00:31:55,460 --> 00:31:58,420
Is each on characterized
correctly as

512
00:31:58,420 --> 00:31:59,380
the dual of the other?

513
00:31:59,380 --> 00:32:00,570
It is.

514
00:32:00,570 --> 00:32:03,800
So we've passed that.

515
00:32:03,800 --> 00:32:11,810
This is intended to make point
C. So it's a good example.

516
00:32:11,810 --> 00:32:16,470

517
00:32:16,470 --> 00:32:24,130
One final thing is suppose I
have a code with generator

518
00:32:24,130 --> 00:32:30,880
matrix G and another code with
generator matrix H. Are they

519
00:32:30,880 --> 00:32:34,280
each other's dual
codes are not?

520
00:32:34,280 --> 00:32:37,570
And the answer is pretty obvious
from all of this.

521
00:32:37,570 --> 00:32:39,810
Yes, they are.

522
00:32:39,810 --> 00:32:42,870
Let me a substitute in here,
x is supposed to

523
00:32:42,870 --> 00:32:44,020
be equal to U g.

524
00:32:44,020 --> 00:32:58,650
So another requirement is that
UGH_t equals zero for all u.

525
00:32:58,650 --> 00:33:08,400
And without belaboring the
point, the 5, 2 codes with

526
00:33:08,400 --> 00:33:14,320
generator matrix G and H, they
are dual codes if and only if

527
00:33:14,320 --> 00:33:17,150
they have the right dimension,
one is n, k, and the other is

528
00:33:17,150 --> 00:33:22,800
n, n minus k, and we satisfy
G H_t equals zero.

529
00:33:22,800 --> 00:33:25,810
Basically, this is the matrix
of inner products of the

530
00:33:25,810 --> 00:33:31,470
generators of C with the
generators of C dual.

531
00:33:31,470 --> 00:33:37,470
And if we have k generators
that are all orthogonal to

532
00:33:37,470 --> 00:33:40,870
these n minus k generators,
then they must be the

533
00:33:40,870 --> 00:33:43,410
generators of dual codes.

534
00:33:43,410 --> 00:33:47,060
That's is kind of intuitive
and natural.

535
00:33:47,060 --> 00:33:51,520
All right, so again, this is a
concise form that you would

536
00:33:51,520 --> 00:33:53,290
actually, probably most
commonly find in the

537
00:33:53,290 --> 00:33:55,730
literature.

538
00:33:55,730 --> 00:33:58,620
It's not hard to get to.

539
00:33:58,620 --> 00:34:05,100
OK, so in this course, we're
probably going to talk quite a

540
00:34:05,100 --> 00:34:07,540
bit about orthogonality.

541
00:34:07,540 --> 00:34:10,920
Duality is very powerful, but
we're not going to be using it

542
00:34:10,920 --> 00:34:13,460
very much in this course,
I believe.

543
00:34:13,460 --> 00:34:16,150
I'll mention duality
whenever there's a

544
00:34:16,150 --> 00:34:18,560
duality property to mention.

545
00:34:18,560 --> 00:34:20,310
But in general, I'm not going
to spend an awful

546
00:34:20,310 --> 00:34:22,870
lot of time on it.

547
00:34:22,870 --> 00:34:25,480
But it's important you know
about it, particularly if you

548
00:34:25,480 --> 00:34:28,380
were going to go on and do
anything in this subject.

549
00:34:28,380 --> 00:34:33,540
And at an elementary level, it's
nice to know that we have

550
00:34:33,540 --> 00:34:36,340
two possible representations,
and one is often going to be

551
00:34:36,340 --> 00:34:37,360
simpler than the other.

552
00:34:37,360 --> 00:34:39,032
Use the simple one.

553
00:34:39,032 --> 00:34:42,420
In general, use the
representation for the

554
00:34:42,420 --> 00:34:44,540
low-rate code to determine
the high-rate code.

555
00:34:44,540 --> 00:34:48,350

556
00:34:48,350 --> 00:34:48,900
OK.

557
00:34:48,900 --> 00:34:50,214
Any questions on this?

558
00:34:50,214 --> 00:34:51,930
I've now finished up
the preparatory.

559
00:34:51,930 --> 00:34:52,579
Yeah?

560
00:34:52,579 --> 00:34:54,710
AUDIENCE: So you're saying
that every basis for

561
00:34:54,710 --> 00:34:57,160
[INAUDIBLE]?

562
00:34:57,160 --> 00:34:59,080
PROFESSOR: That's necessary
and sufficient, right.

563
00:34:59,080 --> 00:35:02,550

564
00:35:02,550 --> 00:35:06,290
OK, Reed-Muller codes.

565
00:35:06,290 --> 00:35:08,380
Why do I talk about
Reed-Muller codes?

566
00:35:08,380 --> 00:35:12,480
First of all, they give us an
infinite family of codes, so

567
00:35:12,480 --> 00:35:17,020
we can see what happens as n
gets large, as k goes from 0

568
00:35:17,020 --> 00:35:22,313
to n, whose parameters are
sort of representative.

569
00:35:22,313 --> 00:35:25,200

570
00:35:25,200 --> 00:35:32,900
They aren't necessarily the best
codes that we know of.

571
00:35:32,900 --> 00:35:37,190
They're very simple, as I will
show, to construct and to

572
00:35:37,190 --> 00:35:41,660
characterize their parameters,
so we can do all the proofs in

573
00:35:41,660 --> 00:35:43,950
half an hour here.

574
00:35:43,950 --> 00:35:46,310
And they're not so bad.

575
00:35:46,310 --> 00:35:51,060
In terms of the parameters n,
k, d, the Reed-Muller codes,

576
00:35:51,060 --> 00:35:55,870
up to length 32, are the best
ones we know of, at least for

577
00:35:55,870 --> 00:35:57,720
their parameters.

578
00:35:57,720 --> 00:36:03,690
There is no 32, 16 code that's
better than a 32, 16, eight

579
00:36:03,690 --> 00:36:06,050
Reed-Muller code.

580
00:36:06,050 --> 00:36:10,990
There's no 32k, eight code that
has k greater than 16,

581
00:36:10,990 --> 00:36:13,140
all those sorts of things.

582
00:36:13,140 --> 00:36:17,060
Actually, I'm not 100%
sure of that.

583
00:36:17,060 --> 00:36:23,620
So for short block lengths,
they're as good as BCH codes,

584
00:36:23,620 --> 00:36:28,510
or any of the codes that were
discovered subsequently.

585
00:36:28,510 --> 00:36:37,790
For even longer lengths, up to
64, 128, 256, they are going

586
00:36:37,790 --> 00:36:42,040
to be slightly sub-optimal in
terms of n, k, d, as we'll see

587
00:36:42,040 --> 00:36:44,080
in some cases.

588
00:36:44,080 --> 00:36:48,060
But they still are very good
codes to look at in terms of

589
00:36:48,060 --> 00:36:50,460
performance versus complexity.

590
00:36:50,460 --> 00:36:53,190
The decoding algorithm that
I'm going to talk about

591
00:36:53,190 --> 00:36:55,690
eventually for them is a
trellis-based decoding

592
00:36:55,690 --> 00:36:58,950
algorithm, and a maximum
likelihood

593
00:36:58,950 --> 00:37:02,230
decoding algorithm within.

594
00:37:02,230 --> 00:37:06,710
They can be maximum likelihood
decoded very simply by these

595
00:37:06,710 --> 00:37:09,700
trellis-based algorithms.

596
00:37:09,700 --> 00:37:14,880
And that's not true of more
elaborate classes of codes.

597
00:37:14,880 --> 00:37:17,330
So from a performance versus
complexity point of view,

598
00:37:17,330 --> 00:37:20,710
they're still good codes to look
at for block lengths up

599
00:37:20,710 --> 00:37:22,640
to 100, 200.

600
00:37:22,640 --> 00:37:25,460
As we get up to higher block
lengths, then we'll be talking

601
00:37:25,460 --> 00:37:28,560
about much more random-like,
non-algebraic codes in the

602
00:37:28,560 --> 00:37:30,400
final section of the course.

603
00:37:30,400 --> 00:37:32,390
This is the way you actually
get to pass it.

604
00:37:32,390 --> 00:37:34,210
You don't worry about n, k, d.

605
00:37:34,210 --> 00:37:36,640
Right now, we're talking about
moderate complexity, moderate

606
00:37:36,640 --> 00:37:39,310
performance.

607
00:37:39,310 --> 00:37:47,690
OK, so they were invented in
1954 independently by Irving

608
00:37:47,690 --> 00:37:53,050
Reed and, I think it was, David
Muller, D. Muller, in

609
00:37:53,050 --> 00:37:55,430
two separate papers,
which shows they

610
00:37:55,430 --> 00:37:57,340
weren't too hard to find.

611
00:37:57,340 --> 00:37:59,740
As you'll see, they're very
easy to construct.

612
00:37:59,740 --> 00:38:03,240

613
00:38:03,240 --> 00:38:08,490
They're basically based on a
length-doubling construction.

614
00:38:08,490 --> 00:38:12,340

615
00:38:12,340 --> 00:38:18,780
So we start off with codes
of length or length 2.

616
00:38:18,780 --> 00:38:26,040
And then from that, we build up
codes of length 4, 8, 16,

617
00:38:26,040 --> 00:38:27,240
32, and so forth.

618
00:38:27,240 --> 00:38:33,120
So in general, their lengths are
equal to a power of 2, and

619
00:38:33,120 --> 00:38:39,080
m is the parameter that denotes
the power of 2.

620
00:38:39,080 --> 00:38:42,980
So we only get certain block
lengths, which are equal to

621
00:38:42,980 --> 00:38:46,130
powers of 2.

622
00:38:46,130 --> 00:38:51,490
They have a second parameter, r,
whose significance is that

623
00:38:51,490 --> 00:39:02,010
d is 2 to the m minus r for 0,
less than or equal to r, less

624
00:39:02,010 --> 00:39:04,520
than or equal to m.

625
00:39:04,520 --> 00:39:06,920
Or some people, including me,
are going to put the lower

626
00:39:06,920 --> 00:39:11,420
limit at minus 1, just to be
able to include one more code

627
00:39:11,420 --> 00:39:13,800
in this family at each length.

628
00:39:13,800 --> 00:39:16,210
But this is just a
matter of taste.

629
00:39:16,210 --> 00:39:21,210
You'll see this is a very
special case, the minus 1.

630
00:39:21,210 --> 00:39:24,830
So let's guess what some of
these codes are going to be.

631
00:39:24,830 --> 00:39:33,560
So we have two parameters, m,
which can be any integer 0 or

632
00:39:33,560 --> 00:39:39,250
higher, so the lengths will be
1,2,4, so forth, and r, which

633
00:39:39,250 --> 00:39:43,940
goes basically from 0 to m,
which means the distances will

634
00:39:43,940 --> 00:39:53,350
go from 2 to the m down to 1.

635
00:39:53,350 --> 00:39:56,000

636
00:39:56,000 --> 00:39:58,240
And what are some of the
basic codes that we're

637
00:39:58,240 --> 00:39:59,490
always going to find?

638
00:39:59,490 --> 00:40:02,610

639
00:40:02,610 --> 00:40:06,100
We always write Rm
of little rm.

640
00:40:06,100 --> 00:40:10,570
I'm not sure I completely
approve of how the notation

641
00:40:10,570 --> 00:40:12,870
goes for these codes, but
that's the way it is.

642
00:40:12,870 --> 00:40:15,900
So it's this notation.

643
00:40:15,900 --> 00:40:19,750
That means the Reed-Muller code
with the parameters m and

644
00:40:19,750 --> 00:40:24,570
r is written Rm of r, m.

645
00:40:24,570 --> 00:40:25,030
All right.

646
00:40:25,030 --> 00:40:31,660
So Rm of m, m, this is going
to be a code of length 2 to

647
00:40:31,660 --> 00:40:34,770
the m and distance 1.

648
00:40:34,770 --> 00:40:37,810
What do you suppose that's
going to be?

649
00:40:37,810 --> 00:40:46,110
This is always going to
be the 2 to the m 1.

650
00:40:46,110 --> 00:40:49,090
Sorry, the distance is 1.

651
00:40:49,090 --> 00:40:58,230
So it's going to be the 2 to
the m, 1 universe code, in

652
00:40:58,230 --> 00:41:07,420
other words, simply the set of
all 2 to the m-tuples, which

653
00:41:07,420 --> 00:41:11,110
has Hamming distance 1.

654
00:41:11,110 --> 00:41:13,350
OK.

655
00:41:13,350 --> 00:41:23,170
RM of 0, m, what's
that going to be?

656
00:41:23,170 --> 00:41:27,810
This is a code now that has
length 2 to the m and minimum

657
00:41:27,810 --> 00:41:29,660
distance 2 to the m.

658
00:41:29,660 --> 00:41:31,806
We know what that has to be.

659
00:41:31,806 --> 00:41:39,980
It has to be the 2 to the m, 1,
2 to the m repetition code,

660
00:41:39,980 --> 00:41:43,255
a very low-rate code,
dimension one.

661
00:41:43,255 --> 00:41:44,505
OK.

662
00:41:44,505 --> 00:41:47,530

663
00:41:47,530 --> 00:41:52,070
And then if we like, we can
go one step further.

664
00:41:52,070 --> 00:41:54,290
There is a code below
this code.

665
00:41:54,290 --> 00:41:56,990
This is the highest-rate
code you can get.

666
00:41:56,990 --> 00:41:59,550
This, however, is not the
lowest-rate code you can get.

667
00:41:59,550 --> 00:42:07,580
What's the lowest rate code
of length 2 to the m?

668
00:42:07,580 --> 00:42:11,990
Well, it's one that has
dimension zero and minimum

669
00:42:11,990 --> 00:42:14,960
distance infinity.

670
00:42:14,960 --> 00:42:17,220
And I don't think I ever defined
this convention.

671
00:42:17,220 --> 00:42:20,860
But for the trivial code that
consists of simply the all-0

672
00:42:20,860 --> 00:42:22,980
word, what's it's minimum
distance?

673
00:42:22,980 --> 00:42:26,720
Undefined, or infinity,
if you like.

674
00:42:26,720 --> 00:42:27,970
So this is the trivial code.

675
00:42:27,970 --> 00:42:32,540

676
00:42:32,540 --> 00:42:36,080
So if we want, we can include
the trivial code in this

677
00:42:36,080 --> 00:42:39,370
family just by defining
it like this.

678
00:42:39,370 --> 00:42:42,120
And it works for some things.

679
00:42:42,120 --> 00:42:43,570
It doesn't work for
all things.

680
00:42:43,570 --> 00:42:47,030
It doesn't work for
d, for instance.

681
00:42:47,030 --> 00:42:50,540
This definition holds only
for r between 0 and m.

682
00:42:50,540 --> 00:42:54,080
It doesn't hold for r equals
minus 1, because there the

683
00:42:54,080 --> 00:42:57,280
distance is infinite.

684
00:42:57,280 --> 00:43:05,530
OK, so let's start out and
get even more explicit.

685
00:43:05,530 --> 00:43:09,220
We want to start with
m equals 0.

686
00:43:09,220 --> 00:43:17,140
In that case, we have only Rm of
0, 0, and Rm of minus 1, 0.

687
00:43:17,140 --> 00:43:22,590
And this is going to be the
one by either of these.

688
00:43:22,590 --> 00:43:26,200
The universe code is equal
to the repetition code.

689
00:43:26,200 --> 00:43:29,210
It's the 1, 1, 1 code.

690
00:43:29,210 --> 00:43:33,230
And this is the 1,
0, infinity code.

691
00:43:33,230 --> 00:43:36,960
And that's really the only two
codes that you can think of

692
00:43:36,960 --> 00:43:39,600
that have length 1, right?

693
00:43:39,600 --> 00:43:44,310
This is the one that consists
of 0 and 1, and this is the

694
00:43:44,310 --> 00:43:47,130
one that consists of 0.

695
00:43:47,130 --> 00:43:49,350
I don't think there are any
other binary linear block

696
00:43:49,350 --> 00:43:51,700
codes of length 1.

697
00:43:51,700 --> 00:43:57,210
So that's a start, not
very interesting.

698
00:43:57,210 --> 00:44:00,550
Let's go up to length 2.

699
00:44:00,550 --> 00:44:02,670
So m is going to
be equal to 1.

700
00:44:02,670 --> 00:44:09,300
Here, Rm of 1, 1 is going
to be length 2.

701
00:44:09,300 --> 00:44:12,560
And it's going to be the
universe code, so it's only

702
00:44:12,560 --> 00:44:14,650
going to have distance 1.

703
00:44:14,650 --> 00:44:19,800
Rm of 0, 1 is going to be length
2, but it's going to be

704
00:44:19,800 --> 00:44:21,850
the repetition code.

705
00:44:21,850 --> 00:44:33,010
And Rm of minus 1, 1 is going
to be 2, 0, infinity.

706
00:44:33,010 --> 00:44:37,140
OK, so there are really the
only three sensible

707
00:44:37,140 --> 00:44:38,650
codes of length 2.

708
00:44:38,650 --> 00:44:40,310
This is the only one
of dimension two.

709
00:44:40,310 --> 00:44:42,490
This is the only one
of dimension zero.

710
00:44:42,490 --> 00:44:44,880
There are other ones of
dimension one, but they don't

711
00:44:44,880 --> 00:44:47,800
have minimum distance 2, so
they're not very good for

712
00:44:47,800 --> 00:44:49,430
coding purposes.

713
00:44:49,430 --> 00:44:52,950
So this kind of lists all the
good coding codes of length 2.

714
00:44:52,950 --> 00:44:55,520

715
00:44:55,520 --> 00:44:56,320
All right.

716
00:44:56,320 --> 00:45:02,920
So now let me introduce the
length-doubling construction.

717
00:45:02,920 --> 00:45:05,490

718
00:45:05,490 --> 00:45:08,630
Let me make the point, first of
all, that all these codes

719
00:45:08,630 --> 00:45:11,030
are nested.

720
00:45:11,030 --> 00:45:12,360
What does that mean?

721
00:45:12,360 --> 00:45:15,330
That means that his code is a
sub-code of this code, which

722
00:45:15,330 --> 00:45:18,210
is a sub-code of this code.

723
00:45:18,210 --> 00:45:20,270
And that's going to be, in
general, a property of

724
00:45:20,270 --> 00:45:21,720
Reed-Muller codes.

725
00:45:21,720 --> 00:45:23,140
We're going to get a family.

726
00:45:23,140 --> 00:45:25,830
And each lower one is going
to be a sub-code of the

727
00:45:25,830 --> 00:45:30,640
next-higher one, which is going
to be easy to prove

728
00:45:30,640 --> 00:45:33,170
recursively.

729
00:45:33,170 --> 00:45:34,620
All right.

730
00:45:34,620 --> 00:45:38,100
This is the key thing to know
about Reed-Muller codes, how

731
00:45:38,100 --> 00:45:39,510
do you construct them.

732
00:45:39,510 --> 00:45:44,740
Once you understand the
construction, then you can

733
00:45:44,740 --> 00:45:47,320
derive all the properties.

734
00:45:47,320 --> 00:45:49,190
It's called the u, u plus v

735
00:45:49,190 --> 00:45:53,770
construction for obvious reasons.

736
00:45:53,770 --> 00:45:59,870
Apparently, Plotkin was the
first person to show this.

737
00:45:59,870 --> 00:46:02,560
I think Reed and Muller had two
different constructions,

738
00:46:02,560 --> 00:46:06,630
and neither one of them was the
u, u plus v construction.

739
00:46:06,630 --> 00:46:10,025
Reed, in particular, talked
about Boolean functions.

740
00:46:10,025 --> 00:46:12,824

741
00:46:12,824 --> 00:46:13,610
All right.

742
00:46:13,610 --> 00:46:17,630
But this is the way I recommend
you to think about

743
00:46:17,630 --> 00:46:19,600
constructing them.

744
00:46:19,600 --> 00:46:24,440
And it's simply defined
as follows.

745
00:46:24,440 --> 00:46:29,660
We assume we've already
constructed the Reed-Muller

746
00:46:29,660 --> 00:46:31,300
codes of length m minus 1.

747
00:46:31,300 --> 00:46:34,220
It's a recursive parameter,
m minus 1.

748
00:46:34,220 --> 00:46:37,100
Now we're going to construct all
the Reed-Muller codes of

749
00:46:37,100 --> 00:46:40,820
parameter m of length
2 to the m.

750
00:46:40,820 --> 00:46:42,070
How are we going to do it?

751
00:46:42,070 --> 00:46:45,600

752
00:46:45,600 --> 00:46:51,780
We want to construct
Rm of r, m.

753
00:46:51,780 --> 00:46:56,790
And we'll say it's the set of
all code words which consist

754
00:46:56,790 --> 00:47:02,670
of two halves, a pair of
n-tuples of half the length.

755
00:47:02,670 --> 00:47:05,190

756
00:47:05,190 --> 00:47:12,200
so the two halves are going to
be u and u plus v, where I

757
00:47:12,200 --> 00:47:15,410
choose u and u plus
v as follows.

758
00:47:15,410 --> 00:47:25,170
u is in Rm of r minus 1, m.

759
00:47:25,170 --> 00:47:28,740

760
00:47:28,740 --> 00:47:30,780
And so what does that mean?

761
00:47:30,780 --> 00:47:36,930
Sorry, it's got to
be m minus 1.

762
00:47:36,930 --> 00:47:39,690
So it's got to be
half the length.

763
00:47:39,690 --> 00:47:46,580
Is that right? r m minus
1, v is in Rm of r

764
00:47:46,580 --> 00:47:49,270
minus 1, m minus 1.

765
00:47:49,270 --> 00:47:52,560
Somebody who has the notes,
like my valuable teaching

766
00:47:52,560 --> 00:47:56,390
assistant, might check whether
I got it right or not.

767
00:47:56,390 --> 00:47:56,870
Let's see.

768
00:47:56,870 --> 00:47:59,320
What are going to be the
parameters of these codes?

769
00:47:59,320 --> 00:48:03,680
They both have n equals
2 to the m minus 1.

770
00:48:03,680 --> 00:48:08,140
The distance here is 2 to the m
minus 1 minus r minus 1, so

771
00:48:08,140 --> 00:48:12,800
the distance here is 2 to the
m minus r, which is the

772
00:48:12,800 --> 00:48:15,170
distance that we want to
achieve for this code.

773
00:48:15,170 --> 00:48:17,780

774
00:48:17,780 --> 00:48:22,910
And the distance here is 2 to
the m minus r minus 1, which

775
00:48:22,910 --> 00:48:26,780
is half the distance we want
to achieve for this code.

776
00:48:26,780 --> 00:48:30,690
So we reach down, if we wanted
to construct now a code of

777
00:48:30,690 --> 00:48:35,900
length four and distance two,
we would construct it from

778
00:48:35,900 --> 00:48:39,050
these two codes, the one of half
the length with distance

779
00:48:39,050 --> 00:48:42,470
2, and the one of half the
length with half the distance,

780
00:48:42,470 --> 00:48:44,000
distance 1.

781
00:48:44,000 --> 00:48:49,640
So we would somehow use this to
get a code of length 4 and

782
00:48:49,640 --> 00:48:51,690
distance 2.

783
00:48:51,690 --> 00:48:55,110
And we don't know
yet what k is.

784
00:48:55,110 --> 00:48:55,470
OK.

785
00:48:55,470 --> 00:49:00,070
So we're going to use these
two codes to construct a

786
00:49:00,070 --> 00:49:01,090
larger code.

787
00:49:01,090 --> 00:49:02,450
Is the construction clear?

788
00:49:02,450 --> 00:49:07,320

789
00:49:07,320 --> 00:49:08,570
All right.

790
00:49:08,570 --> 00:49:11,350

791
00:49:11,350 --> 00:49:16,650
So let's now derive some
properties from this

792
00:49:16,650 --> 00:49:21,280
construction, and from the fact
that we've started from a

793
00:49:21,280 --> 00:49:22,030
set of codes.

794
00:49:22,030 --> 00:49:24,040
Let's say we start from
length two codes.

795
00:49:24,040 --> 00:49:25,870
Or we could start
from length one.

796
00:49:25,870 --> 00:49:29,760
You could satisfy yourself that
this construction applied

797
00:49:29,760 --> 00:49:32,070
to the length one codes gives
the length two codes.

798
00:49:32,070 --> 00:49:34,310
I won't go through
that exercise.

799
00:49:34,310 --> 00:49:40,420
So we have some set of
codes, m minus 1.

800
00:49:40,420 --> 00:49:42,085
What's the first thing
we notice?

801
00:49:42,085 --> 00:49:45,530

802
00:49:45,530 --> 00:49:51,510
Obviously, the length is what
we want, because we've put

803
00:49:51,510 --> 00:49:56,170
together two 2-to-the-m minus
1-tuples, and 2 times 2 to the

804
00:49:56,170 --> 00:49:57,570
m minus 1 is 2 to the m.

805
00:49:57,570 --> 00:50:02,055
So we've constructed a set
of 2-to-the-m-tuples.

806
00:50:02,055 --> 00:50:06,350
The length of the resulting
code is 2 to the m.

807
00:50:06,350 --> 00:50:12,360
This is Rm r, m, constructed
in this way.

808
00:50:12,360 --> 00:50:16,590

809
00:50:16,590 --> 00:50:20,430
Second, it's linear.

810
00:50:20,430 --> 00:50:23,020
It's a linear code.

811
00:50:23,020 --> 00:50:24,750
All we have to check is
the group property.

812
00:50:24,750 --> 00:50:27,680
If we add two code words of this
form, we're going to get

813
00:50:27,680 --> 00:50:31,790
another code word of that form,
from the fact that these

814
00:50:31,790 --> 00:50:35,420
guys are linear, yes.

815
00:50:35,420 --> 00:50:35,910
OK.

816
00:50:35,910 --> 00:50:40,940
So it is a linear code,
that's important.

817
00:50:40,940 --> 00:50:43,250
Then we might ask, what's
its dimension?

818
00:50:43,250 --> 00:50:44,540
How many code words are there?

819
00:50:44,540 --> 00:50:47,820

820
00:50:47,820 --> 00:50:52,110
Well, do I get a unique code
word for every combination of

821
00:50:52,110 --> 00:51:03,390
u and v. And however you want
to convince yourself, you

822
00:51:03,390 --> 00:51:05,460
obviously do.

823
00:51:05,460 --> 00:51:09,960
If I'm given this word here, I
can deduce from it what was u,

824
00:51:09,960 --> 00:51:11,910
that's simply the first
half of it.

825
00:51:11,910 --> 00:51:14,060
Subtract u from the second
half of it, and I

826
00:51:14,060 --> 00:51:15,650
find out what v is.

827
00:51:15,650 --> 00:51:18,970
So there's a one-to-one map
between all possible pairs, u,

828
00:51:18,970 --> 00:51:22,860
v, and all possible
new code words.

829
00:51:22,860 --> 00:51:27,910
And so what that means is, let
me call it the dimension of

830
00:51:27,910 --> 00:51:32,650
the code with parameters r,
m is simply the sum of the

831
00:51:32,650 --> 00:51:42,800
dimensions of the codes with
parameters r, m minus 1 and r

832
00:51:42,800 --> 00:51:46,400
minus 1, m minus 1.

833
00:51:46,400 --> 00:51:50,670
So for instance, in this
hypothesized code here, if I

834
00:51:50,670 --> 00:51:53,330
want to know the dimension,
well, I take all possible

835
00:51:53,330 --> 00:51:56,210
combinations of words
here and words here.

836
00:51:56,210 --> 00:51:57,060
How many are there?

837
00:51:57,060 --> 00:51:57,680
There are eight.

838
00:51:57,680 --> 00:51:59,620
It has dimension three.

839
00:51:59,620 --> 00:52:04,410
So I'm going to get a 4, 3, 2,
code, which it's not too hard

840
00:52:04,410 --> 00:52:07,413
to see is the single parity
check code of length 4.

841
00:52:07,413 --> 00:52:08,663
All right.

842
00:52:08,663 --> 00:52:10,470

843
00:52:10,470 --> 00:52:11,510
So that's how I do it.

844
00:52:11,510 --> 00:52:14,805
I simply add up the dimensions
of the two contributing codes.

845
00:52:14,805 --> 00:52:19,540

846
00:52:19,540 --> 00:52:21,470
Not a very nice formula.

847
00:52:21,470 --> 00:52:25,160
In the homework, you do a
combinatoric exercise that

848
00:52:25,160 --> 00:52:28,090
gives you a somewhat more closed
form of the formula.

849
00:52:28,090 --> 00:52:31,950
But I think this is actually
the most useful one.

850
00:52:31,950 --> 00:52:35,090
In any case, we eventually get
a table that shows what all

851
00:52:35,090 --> 00:52:36,340
these things are anyway.

852
00:52:36,340 --> 00:52:39,850

853
00:52:39,850 --> 00:52:45,630
Now, just as a fine point, I
want to assert that if I start

854
00:52:45,630 --> 00:52:50,890
out from a set of nested codes,
then I come up with a

855
00:52:50,890 --> 00:52:55,420
set of nested codes, at the
next highest level.

856
00:52:55,420 --> 00:52:56,940
That, again, is sort
of obvious.

857
00:52:56,940 --> 00:53:01,910
If these guys were nested, then
I get the appropriate --

858
00:53:01,910 --> 00:53:05,360
if I take u, u plus v
from sub-codes, I'm

859
00:53:05,360 --> 00:53:06,610
going to get a sub-code.

860
00:53:06,610 --> 00:53:09,910

861
00:53:09,910 --> 00:53:12,300
Look at the notes if you want
more than that little bit of

862
00:53:12,300 --> 00:53:14,870
hand-waving.

863
00:53:14,870 --> 00:53:20,490
OK, that's something I need
for the next thing.

864
00:53:20,490 --> 00:53:22,210
I want to find out what d is.

865
00:53:22,210 --> 00:53:28,080

866
00:53:28,080 --> 00:53:31,270
What's the minimum
distance here?

867
00:53:31,270 --> 00:53:34,010
Of course, my objective is
to make it equal to 2

868
00:53:34,010 --> 00:53:34,960
to the m minus r.

869
00:53:34,960 --> 00:53:36,690
Did I succeed?

870
00:53:36,690 --> 00:53:40,620
What are the possibilities
for u, u plus v?

871
00:53:40,620 --> 00:53:45,210
The possibilities are that
they're both 0, or that this

872
00:53:45,210 --> 00:53:49,460
one is 0 and this is not equal
to 0, or this is not equal to

873
00:53:49,460 --> 00:53:53,230
0 and this is 0, or that they're
both not equal to 0.

874
00:53:53,230 --> 00:53:56,635
And I'm going to consider
those four cases.

875
00:53:56,635 --> 00:54:01,430

876
00:54:01,430 --> 00:54:04,120
Since every linear code include
the all-0 word, it's

877
00:54:04,120 --> 00:54:07,490
certainly possible that this
comes out at 0, 0.

878
00:54:07,490 --> 00:54:10,590
The only possibility for this
to come out 0, 0 is if I

879
00:54:10,590 --> 00:54:12,260
choose u equals 0.

880
00:54:12,260 --> 00:54:14,590
Then I have to choose
v equals 0.

881
00:54:14,590 --> 00:54:17,840
So there's one-code word of
weight 0 in my new code.

882
00:54:17,840 --> 00:54:19,950
But that's OK.

883
00:54:19,950 --> 00:54:24,700
If there were two code words
with weight 0, well, then the

884
00:54:24,700 --> 00:54:25,820
dimension would be wrong.

885
00:54:25,820 --> 00:54:30,170
This is in effect a proof that
the kernel is just 0, 0.

886
00:54:30,170 --> 00:54:31,890
And so the dimension is OK.

887
00:54:31,890 --> 00:54:34,660
It's a one-to-one map.

888
00:54:34,660 --> 00:54:35,010
All right.

889
00:54:35,010 --> 00:54:39,140
So I don't really have
to worry about that.

890
00:54:39,140 --> 00:54:42,280
I'm going to get one all-0
word in my new code.

891
00:54:42,280 --> 00:54:43,770
I can afford one all-0 word.

892
00:54:43,770 --> 00:54:46,490
I'm always going to have
to have it anyway.

893
00:54:46,490 --> 00:54:47,790
It's linear.

894
00:54:47,790 --> 00:54:49,650
All right, so these are the
more interesting cases.

895
00:54:49,650 --> 00:54:55,030
Suppose the first half is 0, but
the second half is not 0.

896
00:54:55,030 --> 00:54:58,150
That implies that u is 0.

897
00:54:58,150 --> 00:55:02,730
That implies that the second
half is just v,

898
00:55:02,730 --> 00:55:04,010
which is not 0.

899
00:55:04,010 --> 00:55:08,340
So v must be a non-zero code
word in this code, which has

900
00:55:08,340 --> 00:55:12,090
minimum distance 2
to the n minus r.

901
00:55:12,090 --> 00:55:17,228
So in this case, I prove that
the distance is greater than

902
00:55:17,228 --> 00:55:20,910
or equal to 2 to
the m minus r.

903
00:55:20,910 --> 00:55:25,060
Similarly, suppose this one
is not 0, but this is 0.

904
00:55:25,060 --> 00:55:28,320
OK, if that's 0, it can only be
because I chose u equal to

905
00:55:28,320 --> 00:55:36,260
some v. and that means the first
half, then, is that v.

906
00:55:36,260 --> 00:55:39,920
So again, v is in this
code that has

907
00:55:39,920 --> 00:55:42,090
enough minimum distance.

908
00:55:42,090 --> 00:55:47,560
So in this case, I proved that
the code word has weight 2 to

909
00:55:47,560 --> 00:55:48,810
the m minus r.

910
00:55:48,810 --> 00:55:51,180

911
00:55:51,180 --> 00:55:52,760
And finally, let's take
the case where

912
00:55:52,760 --> 00:55:55,610
they're both non-zero.

913
00:55:55,610 --> 00:55:59,570
In that case, u could be an
arbitrary word in this code

914
00:55:59,570 --> 00:56:04,270
which only has distance
2 to the m r minus 1.

915
00:56:04,270 --> 00:56:07,210
So the first half is going to
have weight at least 2 to the

916
00:56:07,210 --> 00:56:09,540
m minus r minus 1, but
that's all I can say

917
00:56:09,540 --> 00:56:12,000
about the first half.

918
00:56:12,000 --> 00:56:15,815
But now the second half,
what is this?

919
00:56:15,815 --> 00:56:18,320

920
00:56:18,320 --> 00:56:22,050
This is a higher-rate
code than this.

921
00:56:22,050 --> 00:56:25,640
This, by the nesting property,
is a sub-code of this.

922
00:56:25,640 --> 00:56:31,510
So if I add a word in a sub-code
to a word in the

923
00:56:31,510 --> 00:56:34,970
code, I'm going to get another
word in this code.

924
00:56:34,970 --> 00:56:39,950
So u plus v is still in this
Reed-Muller code, still has a

925
00:56:39,950 --> 00:56:43,710
minimum weight, if it's
non-zero, of 2 to the m

926
00:56:43,710 --> 00:56:45,015
minus r minus 1.

927
00:56:45,015 --> 00:56:47,760

928
00:56:47,760 --> 00:56:51,650
So the distance is at least this
in the first half, this

929
00:56:51,650 --> 00:56:53,770
in the second half.

930
00:56:53,770 --> 00:56:56,080
And that's, of course,
still good enough.

931
00:56:56,080 --> 00:56:59,230

932
00:56:59,230 --> 00:56:59,320
OK.

933
00:56:59,320 --> 00:57:01,860
So by this construction.

934
00:57:01,860 --> 00:57:08,370
I've assured that I'm going to
get a d greater than or equal

935
00:57:08,370 --> 00:57:10,860
to 2 to the m minus r.

936
00:57:10,860 --> 00:57:13,990
And of course, you can easily
find cases of equality, where

937
00:57:13,990 --> 00:57:16,450
it's only 2 to the m minus r.

938
00:57:16,450 --> 00:57:20,840
If this has a word of weight 2
to the m minus r, then you can

939
00:57:20,840 --> 00:57:23,765
clearly set up one like
this that has weight 2

940
00:57:23,765 --> 00:57:24,690
to the m minus r.

941
00:57:24,690 --> 00:57:28,430
Just pick one of the
minimum-weight code words as

942
00:57:28,430 --> 00:57:30,790
v, and u as 0.

943
00:57:30,790 --> 00:57:33,460
So the minimum distance
is 2 to the m minus r.

944
00:57:33,460 --> 00:57:36,740

945
00:57:36,740 --> 00:57:39,630
All righty.

946
00:57:39,630 --> 00:57:44,280
So those are all the
properties we need.

947
00:57:44,280 --> 00:57:52,200
And then, I like to display
these properties in a tableau

948
00:57:52,200 --> 00:57:57,255
which you have in the notes,
which goes as follows.

949
00:57:57,255 --> 00:58:00,630

950
00:58:00,630 --> 00:58:02,670
Let's just start listing
these codes.

951
00:58:02,670 --> 00:58:06,090
Here are the length 1 ones.

952
00:58:06,090 --> 00:58:14,370
We only found 2 of them, 1,
1, 1, and 1, 0, infinity.

953
00:58:14,370 --> 00:58:17,105
So there are two codes
of length 1.

954
00:58:17,105 --> 00:58:21,790
Now it turns out that if you
combine these according to the

955
00:58:21,790 --> 00:58:37,570
u, u plus v construction, you
get 2, 1, 2, where the weight

956
00:58:37,570 --> 00:58:41,100
2, 1 is just the --

957
00:58:41,100 --> 00:58:45,710
you take the first half is 1,
and the second half is 1.

958
00:58:45,710 --> 00:58:49,990
So you can build this
in the same way.

959
00:58:49,990 --> 00:58:53,110
And similarly, we can say just
by definition, we're always

960
00:58:53,110 --> 00:59:00,600
going to put a universe code at
the top and a trivial code

961
00:59:00,600 --> 00:59:02,180
at the bottom.

962
00:59:02,180 --> 00:59:03,750
So now I've listed all
my Reed-Muller

963
00:59:03,750 --> 00:59:06,520
codes with length 2.

964
00:59:06,520 --> 00:59:11,850
Now to construct the
ones of length 4.

965
00:59:11,850 --> 00:59:16,220
Again, I'll put a universe code
at the top, a trivial

966
00:59:16,220 --> 00:59:18,860
code at the bottom.

967
00:59:18,860 --> 00:59:27,030
I'll use my construction now to
create a 4, 3, 2 code here.

968
00:59:27,030 --> 00:59:31,450
I'm just using all
these properties.

969
00:59:31,450 --> 00:59:36,500
And down here, my construction,
when you combine

970
00:59:36,500 --> 00:59:39,900
these two things, you always
get a repetition code,

971
00:59:39,900 --> 00:59:42,550
again, 4, 1, 4.

972
00:59:42,550 --> 00:59:46,570
And I guess I've hand-waved.

973
00:59:46,570 --> 00:59:49,980
Exercise for the student,
prove that combining a

974
00:59:49,980 --> 00:59:53,600
repetition code with a trivial
code under the u, u plus v

975
00:59:53,600 --> 00:59:57,230
construction always gives a
double length repetition code.

976
00:59:57,230 --> 01:00:01,370

977
01:00:01,370 --> 01:00:03,340
It's clear.

978
01:00:03,340 --> 01:00:06,790
v is always the all-0 word.

979
01:00:06,790 --> 01:00:10,220
u is either all-0 or all-1.

980
01:00:10,220 --> 01:00:14,400
So we get two words, one of
which is all-0, and one of

981
01:00:14,400 --> 01:00:18,150
which is all-1, double length.

982
01:00:18,150 --> 01:00:18,580
All right.

983
01:00:18,580 --> 01:00:24,590
So now I can just go on
indefinitely, and without a

984
01:00:24,590 --> 01:00:27,800
great deal of effort.

985
01:00:27,800 --> 01:00:32,710
Here I find that k is 7, just by
adding up these two things.

986
01:00:32,710 --> 01:00:37,526
The 8, this gives me an 8, 4.

987
01:00:37,526 --> 01:00:39,740
4 code.

988
01:00:39,740 --> 01:00:43,907
This gives me an 8.

989
01:00:43,907 --> 01:00:48,740
1, 8 code, and similarly
down here.

990
01:00:48,740 --> 01:00:52,882
And this, I now just
turn the crank.

991
01:00:52,882 --> 01:00:54,390
16, 16, 1.

992
01:00:54,390 --> 01:00:55,730
I always put that on top.

993
01:00:55,730 --> 01:00:59,270
The next one is 16, 15, 2.

994
01:00:59,270 --> 01:01:04,185
Next one is 16, 11, 4.

995
01:01:04,185 --> 01:01:07,360

996
01:01:07,360 --> 01:01:12,090
After a while, you don't know
what you're going to get.

997
01:01:12,090 --> 01:01:14,400
But you get something.

998
01:01:14,400 --> 01:01:17,630
You've proved that all of
these codes exist, that

999
01:01:17,630 --> 01:01:19,560
they're all linear.

1000
01:01:19,560 --> 01:01:26,270
They all have the n, k, d that
we've specified, and that

1001
01:01:26,270 --> 01:01:28,820
furthermore, they're nested.

1002
01:01:28,820 --> 01:01:32,590
And a final property, which you
might suspect, looking at

1003
01:01:32,590 --> 01:01:40,860
these tables, is that the dual
of a Reed-Muller code is also

1004
01:01:40,860 --> 01:01:41,780
a Reed-Muller code.

1005
01:01:41,780 --> 01:01:45,140
And they're paired up according
to k and n minus k.

1006
01:01:45,140 --> 01:01:45,900
Let's see.

1007
01:01:45,900 --> 01:01:49,670
15 and 11 is 26.

1008
01:01:49,670 --> 01:01:51,883
11 and five is 16.

1009
01:01:51,883 --> 01:01:57,770

1010
01:01:57,770 --> 01:02:00,740
5 and 1 is 6.

1011
01:02:00,740 --> 01:02:05,805
And 32, 1, 32, and so forth.

1012
01:02:05,805 --> 01:02:08,740

1013
01:02:08,740 --> 01:02:11,345
Did you see how I proved that
all these codes exist?

1014
01:02:11,345 --> 01:02:13,980

1015
01:02:13,980 --> 01:02:17,760
And if I continued, I could get
arbitrarily long codes,

1016
01:02:17,760 --> 01:02:20,870
one of your simple homework
problems is just to do this,

1017
01:02:20,870 --> 01:02:24,640
continue this for 64
and 128, see what

1018
01:02:24,640 --> 01:02:25,910
additional codes you get.

1019
01:02:25,910 --> 01:02:29,050

1020
01:02:29,050 --> 01:02:32,700
And so I now have this infinite
family it of that

1021
01:02:32,700 --> 01:02:38,750
kind of covers the space n, k,
d in some sort of sparse way.

1022
01:02:38,750 --> 01:02:42,180
But it indicates how
k and d go with n.

1023
01:02:42,180 --> 01:02:44,810
And we come back to our original
question, how well

1024
01:02:44,810 --> 01:02:47,700
can we do with binary
linear block codes.

1025
01:02:47,700 --> 01:02:50,650
Well, here's some binary linear
block codes, pretty

1026
01:02:50,650 --> 01:02:52,510
close to the best we
can find, actually.

1027
01:02:52,510 --> 01:02:54,160
The ones I've listed
up here are all as

1028
01:02:54,160 --> 01:02:56,320
good as we can find.

1029
01:02:56,320 --> 01:02:59,720
And how well can we do?

1030
01:02:59,720 --> 01:03:03,010
Really, we don't need to know
much to evaluate the

1031
01:03:03,010 --> 01:03:07,830
performance of, say, 32, 6, 8
code, which is now getting to

1032
01:03:07,830 --> 01:03:12,250
be a pretty substantial code,
with 2 to the 16 code words,

1033
01:03:12,250 --> 01:03:17,750
to 65,536 code words.

1034
01:03:17,750 --> 01:03:21,140
So we built a fairly sizable
constellation here in a

1035
01:03:21,140 --> 01:03:24,000
32-dimensional Euclidean
space.

1036
01:03:24,000 --> 01:03:25,850
And how good is it?

1037
01:03:25,850 --> 01:03:29,710
Let's take 32, 16, 8.

1038
01:03:29,710 --> 01:03:32,350

1039
01:03:32,350 --> 01:03:40,840
Can I graph its probability
of error per bit, a

1040
01:03:40,840 --> 01:03:42,330
good estimate of it?

1041
01:03:42,330 --> 01:03:44,816
Can I?

1042
01:03:44,816 --> 01:03:46,870
Is there any information
I'm lacking?

1043
01:03:46,870 --> 01:03:52,090

1044
01:03:52,090 --> 01:03:57,390
OK, I've been talking too long,
because when I go to the

1045
01:03:57,390 --> 01:03:59,990
class, I'd like a
little response.

1046
01:03:59,990 --> 01:04:02,212
So you were going to
say something?

1047
01:04:02,212 --> 01:04:05,480
AUDIENCE: We don't
have [INAUDIBLE].

1048
01:04:05,480 --> 01:04:12,950
PROFESSOR: OK, let me tell you
that the n, d is approximately

1049
01:04:12,950 --> 01:04:19,226
600-something, so
let's say 630.

1050
01:04:19,226 --> 01:04:21,350
It's probably not
exactly correct.

1051
01:04:21,350 --> 01:04:25,578
In the notes I give a
formula for n, d --

1052
01:04:25,578 --> 01:04:29,830
a formula that I don't
derive, that is known

1053
01:04:29,830 --> 01:04:30,960
for Reed-Muller codes.

1054
01:04:30,960 --> 01:04:34,650
And from that, you can compute
n, d for any of these codes.

1055
01:04:34,650 --> 01:04:37,870
This parameter is m, r.

1056
01:04:37,870 --> 01:04:38,300
All right.

1057
01:04:38,300 --> 01:04:39,570
So I'll give you n, d as well.

1058
01:04:39,570 --> 01:04:45,535
Now can I get the good estimate
for the probability

1059
01:04:45,535 --> 01:04:48,460
of error per bit?

1060
01:04:48,460 --> 01:04:49,950
How do I do that?

1061
01:04:49,950 --> 01:04:54,380

1062
01:04:54,380 --> 01:04:55,660
Union-bound estimate.

1063
01:04:55,660 --> 01:04:58,800
All right, so what's it
going to look like?

1064
01:04:58,800 --> 01:05:03,471
What are the two subsidiary
parameters I need?

1065
01:05:03,471 --> 01:05:06,680
One is the coding gain, right?

1066
01:05:06,680 --> 01:05:10,355
What is the nominal coding gain
of this 32, 16, 8 code?

1067
01:05:10,355 --> 01:05:14,315

1068
01:05:14,315 --> 01:05:16,965
Come on, this is not a difficult
computation.

1069
01:05:16,965 --> 01:05:21,550

1070
01:05:21,550 --> 01:05:24,510
OK, what's k over n?

1071
01:05:24,510 --> 01:05:26,650
1/2?

1072
01:05:26,650 --> 01:05:29,780
I think we can all
do that one.

1073
01:05:29,780 --> 01:05:32,250
What's the nominal
coding gain?

1074
01:05:32,250 --> 01:05:35,820
Take 1/2 times d, 8.

1075
01:05:35,820 --> 01:05:41,440
So now our coding gain is
4, which is what in dB?

1076
01:05:41,440 --> 01:05:44,000
6 dB.

1077
01:05:44,000 --> 01:05:45,530
Wow, gee whiz.

1078
01:05:45,530 --> 01:05:49,280
I've already got a nominal
coding gain of 6 dB.

1079
01:05:49,280 --> 01:05:51,960
Remember, my whole gap was,
depending on how I measured

1080
01:05:51,960 --> 01:05:54,510
it, 9 or 10 or 11 dB.

1081
01:05:54,510 --> 01:05:58,150
This looks like already a
sizable fraction of the gap,

1082
01:05:58,150 --> 01:06:00,660
with just a simple
construction.

1083
01:06:00,660 --> 01:06:04,060
Well, we better pay attention
to this error coefficient as

1084
01:06:04,060 --> 01:06:06,940
well, or the number of
nearest neighbors.

1085
01:06:06,940 --> 01:06:14,260
Kb is, let's just take a rough
estimate here, what's this

1086
01:06:14,260 --> 01:06:15,510
going to be?

1087
01:06:15,510 --> 01:06:18,240

1088
01:06:18,240 --> 01:06:19,345
About 40.

1089
01:06:19,345 --> 01:06:22,070
That's good.

1090
01:06:22,070 --> 01:06:25,090
It's just this divided by 16.

1091
01:06:25,090 --> 01:06:27,570
So there are about 40 nearest
neighbors per bit.

1092
01:06:27,570 --> 01:06:29,200
How much is that going
to cost us?

1093
01:06:29,200 --> 01:06:33,820

1094
01:06:33,820 --> 01:06:34,018
Not so good.

1095
01:06:34,018 --> 01:06:36,275
Well, it's a little bit more
than 5 factors of 2.

1096
01:06:36,275 --> 01:06:39,840

1097
01:06:39,840 --> 01:06:41,660
Maybe 5 and a 1/2 factors.

1098
01:06:41,660 --> 01:06:43,810
It's less than 5 and a 1/2.

1099
01:06:43,810 --> 01:06:47,760
So this very roughly,
something will

1100
01:06:47,760 --> 01:06:49,010
cost me about 1 dB.

1101
01:06:49,010 --> 01:06:53,850

1102
01:06:53,850 --> 01:07:00,180
And so I get an effective
coding gain of 5 dB.

1103
01:07:00,180 --> 01:07:04,220
That's my first very
gross estimate.

1104
01:07:04,220 --> 01:07:05,630
All right, well,
it's not 6 dB.

1105
01:07:05,630 --> 01:07:07,850
It's only 5 dB.

1106
01:07:07,850 --> 01:07:10,460
That's still not bad.

1107
01:07:10,460 --> 01:07:14,130
Again, if I really wanted to
know what this was, I would

1108
01:07:14,130 --> 01:07:18,890
write this out as 40 or whatever
it is times Q to the

1109
01:07:18,890 --> 01:07:23,140
square root of four times
2Eb over N_0.

1110
01:07:23,140 --> 01:07:27,100

1111
01:07:27,100 --> 01:07:31,170
And can I plot that quantity?

1112
01:07:31,170 --> 01:07:32,770
Yes, if I have MATLAB.

1113
01:07:32,770 --> 01:07:38,900
Or actually, all I need
is my baseline.

1114
01:07:38,900 --> 01:07:50,340
So if this is my baseline, which
went through 9.6 dB at

1115
01:07:50,340 --> 01:07:54,600
10 to the minus 5, then we
remember how to plot that.

1116
01:07:54,600 --> 01:07:57,900
I just take this whole curve
bodily, and I move

1117
01:07:57,900 --> 01:08:02,230
it 6 dB to the left.

1118
01:08:02,230 --> 01:08:07,440
So I get the same curve, this
is not very good, going

1119
01:08:07,440 --> 01:08:08,830
through 3.6 dB.

1120
01:08:08,830 --> 01:08:12,046

1121
01:08:12,046 --> 01:08:13,028
Sorry about that.

1122
01:08:13,028 --> 01:08:15,490
How's that?

1123
01:08:15,490 --> 01:08:16,510
Get it way down here.

1124
01:08:16,510 --> 01:08:19,099
But then I also have to raise
it by a factor of 40.

1125
01:08:19,099 --> 01:08:22,050

1126
01:08:22,050 --> 01:08:23,910
So it really looks
more like that.

1127
01:08:23,910 --> 01:08:27,370
That's really going to go more
through about 4.6 dB or

1128
01:08:27,370 --> 01:08:29,649
something like that.

1129
01:08:29,649 --> 01:08:33,840
That's what these calculations
are, Ashish took

1130
01:08:33,840 --> 01:08:36,340
you through, I believe.

1131
01:08:36,340 --> 01:08:42,200
And so while 6 dB was my
nominal coding gain, my

1132
01:08:42,200 --> 01:08:45,370
effective coding gain is 5 dB.

1133
01:08:45,370 --> 01:08:47,090
But still, hey, not bad.

1134
01:08:47,090 --> 01:08:50,090

1135
01:08:50,090 --> 01:08:53,509
I have very easily been able to
construct a code that gives

1136
01:08:53,509 --> 01:08:56,674
you about 5 dB of coding gain.

1137
01:08:56,674 --> 01:08:58,430
Is there any fly in
this ointment?

1138
01:08:58,430 --> 01:09:03,400

1139
01:09:03,400 --> 01:09:05,220
Can I just go out and
build it now?

1140
01:09:05,220 --> 01:09:08,356

1141
01:09:08,356 --> 01:09:10,229
I need a decoder.

1142
01:09:10,229 --> 01:09:11,590
Who said that?

1143
01:09:11,590 --> 01:09:13,200
Thank you.

1144
01:09:13,200 --> 01:09:14,100
Good point.

1145
01:09:14,100 --> 01:09:16,580
What's the decoding method
assumed for this code?

1146
01:09:16,580 --> 01:09:20,270

1147
01:09:20,270 --> 01:09:20,960
Excuse me?

1148
01:09:20,960 --> 01:09:23,240
AUDIENCE: Just a table
right now.

1149
01:09:23,240 --> 01:09:26,460
PROFESSOR: Just a table,
based on what?

1150
01:09:26,460 --> 01:09:31,790
I get some kind of received
n-tuple, which is actually

1151
01:09:31,790 --> 01:09:35,640
just a random, some kind of
vector in 32-dimensional

1152
01:09:35,640 --> 01:09:40,660
space, 32 numbers,
real numbers.

1153
01:09:40,660 --> 01:09:45,819
And really, I'm assuming minimum
distance decoding.

1154
01:09:45,819 --> 01:09:48,770
So in principle, I want to
compute the distance to each

1155
01:09:48,770 --> 01:09:53,080
of the 2 to the 1/6th,
65,000 code words.

1156
01:09:53,080 --> 01:09:56,930
And actually, nowadays, you
might just do that.

1157
01:09:56,930 --> 01:10:00,460
That's not a formidable task.

1158
01:10:00,460 --> 01:10:02,420
Back when I got into this
business, that would have been

1159
01:10:02,420 --> 01:10:03,995
considered outrageous.

1160
01:10:03,995 --> 01:10:06,610
But nowadays, you could keep
up a pretty good decoding

1161
01:10:06,610 --> 01:10:13,210
rate, even doing 65,000 distance
computations and just

1162
01:10:13,210 --> 01:10:14,260
finding the best one.

1163
01:10:14,260 --> 01:10:15,780
That would do it.

1164
01:10:15,780 --> 01:10:17,030
That would give you
this performance.

1165
01:10:17,030 --> 01:10:20,030

1166
01:10:20,030 --> 01:10:22,830
But of course, we are going to
be looking for somewhat more

1167
01:10:22,830 --> 01:10:26,150
efficient decoding schemes
than that.

1168
01:10:26,150 --> 01:10:26,520
All right.

1169
01:10:26,520 --> 01:10:30,850
So at this point, that's the
only fly in the ointment.

1170
01:10:30,850 --> 01:10:36,090
We have a way of getting this
kind of error curve, provided

1171
01:10:36,090 --> 01:10:39,690
that we're willing to do
exhaustive maximum likelihood

1172
01:10:39,690 --> 01:10:41,735
or minimum distance decoding.

1173
01:10:41,735 --> 01:10:44,600

1174
01:10:44,600 --> 01:10:47,680
And furthermore, we
can continue.

1175
01:10:47,680 --> 01:10:51,220
It's also instructive to
see what happens as

1176
01:10:51,220 --> 01:10:52,885
we let n go to infinity.

1177
01:10:52,885 --> 01:10:55,200
What are we going to get
with this construction?

1178
01:10:55,200 --> 01:10:58,180
We pretty well know.

1179
01:10:58,180 --> 01:11:02,110
These are all going to be
universe codes, which are not

1180
01:11:02,110 --> 01:11:04,470
very interesting to us.

1181
01:11:04,470 --> 01:11:07,850
They all have a nominal
coding gain of one,

1182
01:11:07,850 --> 01:11:09,380
and are just useless.

1183
01:11:09,380 --> 01:11:13,220
They're basically just
send a bit 32 times,

1184
01:11:13,220 --> 01:11:16,660
send 32 bits, I mean.

1185
01:11:16,660 --> 01:11:20,360
OK, what are these
codes along here?

1186
01:11:20,360 --> 01:11:22,800
Let me start there.

1187
01:11:22,800 --> 01:11:26,890
These are all single
parity check codes.

1188
01:11:26,890 --> 01:11:28,415
What's the nominal
coding gain?

1189
01:11:28,415 --> 01:11:32,840

1190
01:11:32,840 --> 01:11:34,460
Well, as we get out here,
what does the

1191
01:11:34,460 --> 01:11:35,710
nominal coding gain approach?

1192
01:11:35,710 --> 01:11:38,520

1193
01:11:38,520 --> 01:11:42,210
The code rate approaches 1.

1194
01:11:42,210 --> 01:11:44,790
The code distance stays at 2.

1195
01:11:44,790 --> 01:11:51,800
So the nominal coding gain goes
to 2 or 3 or dB, at a

1196
01:11:51,800 --> 01:11:54,675
rate of 1 or a nominal spectral
efficiency of 2.

1197
01:11:54,675 --> 01:11:57,460

1198
01:11:57,460 --> 01:11:58,000
OK.

1199
01:11:58,000 --> 01:12:01,540
Well, these are totally
simple codes, single

1200
01:12:01,540 --> 01:12:03,045
parity check codes.

1201
01:12:03,045 --> 01:12:05,980
And even with that, it looks
like we can get 3

1202
01:12:05,980 --> 01:12:08,860
dB of coding gain.

1203
01:12:08,860 --> 01:12:14,810
But what's the number of
nearest neighbors here?

1204
01:12:14,810 --> 01:12:17,760
Number of nearest neighbors
is just n, n minus 1

1205
01:12:17,760 --> 01:12:21,320
over 2, n choose 2.

1206
01:12:21,320 --> 01:12:28,070
So the number of even dividing
by k, which is n minus 1, we

1207
01:12:28,070 --> 01:12:34,030
still get a Kb that goes
up linearly with n.

1208
01:12:34,030 --> 01:12:35,700
So what's in fact going
to happen to the

1209
01:12:35,700 --> 01:12:36,950
effective coding gain?

1210
01:12:36,950 --> 01:12:43,490

1211
01:12:43,490 --> 01:12:47,070
The nominal coding gain will
go up and reach an

1212
01:12:47,070 --> 01:12:48,980
asymptote of 3 dB.

1213
01:12:48,980 --> 01:12:51,850
This is nominal coding gain.

1214
01:12:51,850 --> 01:12:55,590
But somewhere out here, as this
has reached an asymptote,

1215
01:12:55,590 --> 01:12:58,020
the effective coding gain is
always going to be less, and

1216
01:12:58,020 --> 01:13:01,050
it's going to have
to bend over.

1217
01:13:01,050 --> 01:13:03,290
And according to our rule of
thumb, it'll eventually go

1218
01:13:03,290 --> 01:13:10,680
back through 0, because the
cost just keeps going up

1219
01:13:10,680 --> 01:13:12,470
linearly in terms of Kb.

1220
01:13:12,470 --> 01:13:15,260
So the effective coding
gain is not as great.

1221
01:13:15,260 --> 01:13:21,740
It has a peak for some n.

1222
01:13:21,740 --> 01:13:27,310
And so there's some maximum
effective coding gain, which

1223
01:13:27,310 --> 01:13:29,810
again I've left for you
as a homework problem,

1224
01:13:29,810 --> 01:13:32,420
that's less than 3 dB.

1225
01:13:32,420 --> 01:13:35,337
And I'll give you a hint that
it's of the order of 2 dB.

1226
01:13:35,337 --> 01:13:38,140

1227
01:13:38,140 --> 01:13:42,080
It's pretty easy to work out in
the five minutes before the

1228
01:13:42,080 --> 01:13:47,410
next class, not a difficult
problem to find out when this

1229
01:13:47,410 --> 01:13:49,000
thing reaches its maximum.

1230
01:13:49,000 --> 01:13:50,960
But still, these are
very simple codes.

1231
01:13:50,960 --> 01:13:54,600
We'll see in a second they
have an extremely simple

1232
01:13:54,600 --> 01:13:56,050
minimum distance decoding
algorithm

1233
01:13:56,050 --> 01:13:58,170
called Wagner decoding.

1234
01:13:58,170 --> 01:14:01,490
It's trivial, not hard to do
minimum distance decoding for

1235
01:14:01,490 --> 01:14:03,680
these codes.

1236
01:14:03,680 --> 01:14:07,400
And so, OK, not hard to get
2 dB of coding gain.

1237
01:14:07,400 --> 01:14:10,050
What happens if we go along
this line here?

1238
01:14:10,050 --> 01:14:13,790
These are all codes of
minimum distance 4.

1239
01:14:13,790 --> 01:14:15,860
Again, start here.

1240
01:14:15,860 --> 01:14:17,890
They're called extended
Hamming codes.

1241
01:14:17,890 --> 01:14:21,270
A Hamming code has minimum
distance three and is suitable

1242
01:14:21,270 --> 01:14:24,320
for hard decisions, single
error correction.

1243
01:14:24,320 --> 01:14:26,450
These codes all have minimum
distance four.

1244
01:14:26,450 --> 01:14:30,230
We've seen that it's always
worthwhile to add an overall

1245
01:14:30,230 --> 01:14:33,440
parity check to get an even
minimum distance, if we're

1246
01:14:33,440 --> 01:14:36,610
looking at Euclidean
space coding gain.

1247
01:14:36,610 --> 01:14:39,220
And so these are actually
slightly better

1248
01:14:39,220 --> 01:14:40,470
than Hamming codes.

1249
01:14:40,470 --> 01:14:43,170

1250
01:14:43,170 --> 01:14:45,620
They're called extended Hamming
codes, because they're

1251
01:14:45,620 --> 01:14:48,455
Hamming codes extended by
a single parity check.

1252
01:14:48,455 --> 01:14:52,190
They have one more unit
of minimum distance.

1253
01:14:52,190 --> 01:14:54,240
So again, asymptotically,
these are

1254
01:14:54,240 --> 01:14:55,970
called extended Hamming.

1255
01:14:55,970 --> 01:14:59,490
The nominal coding gain
goes to what now?

1256
01:14:59,490 --> 01:15:01,895
This is, the rate is
again going to 1.

1257
01:15:01,895 --> 01:15:03,670
The distance holds at four.

1258
01:15:03,670 --> 01:15:10,850
So the nominal coding gain
goes to 4, or 6 dB, while

1259
01:15:10,850 --> 01:15:13,750
again, the spectral efficiency
goes to two bits per two

1260
01:15:13,750 --> 01:15:18,460
dimensions, the nominal spectral
efficiency rate to 1.

1261
01:15:18,460 --> 01:15:20,155
But again, you have this
kind of phenomenon.

1262
01:15:20,155 --> 01:15:25,100
And I ask you to work that out
also on the homework, where

1263
01:15:25,100 --> 01:15:29,370
even though the nominal coding
gain plateaus eventually at 6

1264
01:15:29,370 --> 01:15:33,370
dB, there is a maximum effective
coding gain, which

1265
01:15:33,370 --> 01:15:36,130
is something more in the
range of 4 to 5 dB.

1266
01:15:36,130 --> 01:15:37,420
You figure out what it is.

1267
01:15:37,420 --> 01:15:40,560

1268
01:15:40,560 --> 01:15:43,445
And there's a limit to how much
effective coding gain you

1269
01:15:43,445 --> 01:15:44,430
can get with these codes.

1270
01:15:44,430 --> 01:15:46,710
Does this all makes sense?

1271
01:15:46,710 --> 01:15:48,185
Are you seeing how
I'm arguing?

1272
01:15:48,185 --> 01:15:51,780

1273
01:15:51,780 --> 01:15:56,905
OK, here's another interesting
sequence of codes.

1274
01:15:56,905 --> 01:16:01,890

1275
01:16:01,890 --> 01:16:06,880
These are all half-rate codes,
or nominal spectral efficiency

1276
01:16:06,880 --> 01:16:09,280
one bit per two dimensions.

1277
01:16:09,280 --> 01:16:11,940

1278
01:16:11,940 --> 01:16:16,170
I briefly mentioned that these
things pair up in duals.

1279
01:16:16,170 --> 01:16:19,750
The 16, 5 code is the dual
code of the 16, 11 codes.

1280
01:16:19,750 --> 01:16:24,210
If you see, there's a symmetry
about rate 1 by 2, such that

1281
01:16:24,210 --> 01:16:26,990
this is k, and this
is n minus k.

1282
01:16:26,990 --> 01:16:30,460
And so you would suspect that
this guy is the dual of this

1283
01:16:30,460 --> 01:16:31,330
guy, which it is.

1284
01:16:31,330 --> 01:16:33,450
This guy is the dual
of this guy.

1285
01:16:33,450 --> 01:16:35,560
This guy is the dual
of this guy.

1286
01:16:35,560 --> 01:16:37,240
And this guy is its own dual.

1287
01:16:37,240 --> 01:16:40,730
It's a self-dual code
of rate 1 by 2 or

1288
01:16:40,730 --> 01:16:43,310
spectral efficiency 1.

1289
01:16:43,310 --> 01:16:45,235
So these are self-dual codes.

1290
01:16:45,235 --> 01:16:48,700

1291
01:16:48,700 --> 01:16:52,580
And what does their nominal
coding gain go to?

1292
01:16:52,580 --> 01:16:57,640

1293
01:16:57,640 --> 01:17:02,450
Well, the rate is always 1 by 2
times four, that's a nominal

1294
01:17:02,450 --> 01:17:04,090
coding gain of 2.

1295
01:17:04,090 --> 01:17:06,470
This has a nominal
coding gain of 4.

1296
01:17:06,470 --> 01:17:11,280
The next one in line would be
a 128, 64, 16 code, nominal

1297
01:17:11,280 --> 01:17:13,700
coding gain of 8.

1298
01:17:13,700 --> 01:17:15,890
So the nominal coding gain
actually goes to infinity.

1299
01:17:15,890 --> 01:17:23,450

1300
01:17:23,450 --> 01:17:25,840
That's pretty good.

1301
01:17:25,840 --> 01:17:28,640
However, what is its
true meaning?

1302
01:17:28,640 --> 01:17:30,930
What we really want to
know is what's the

1303
01:17:30,930 --> 01:17:32,140
effective coding gain.

1304
01:17:32,140 --> 01:17:36,900
And given that the nominal
coding gain goes to infinity,

1305
01:17:36,900 --> 01:17:40,360
is it possible the effective
coding gain can get us all the

1306
01:17:40,360 --> 01:17:41,370
way to the Shannon limit?

1307
01:17:41,370 --> 01:17:44,960
Can we completely close
the gap to capacity?

1308
01:17:44,960 --> 01:17:46,800
As far as I know, this
is an open question.

1309
01:17:46,800 --> 01:17:51,770
I strongly believe that you go
along this sequence through

1310
01:17:51,770 --> 01:17:56,450
maximum likelihood decoding, you
will eventually get to the

1311
01:17:56,450 --> 01:17:59,300
Shannon limit, that is the
Shannon limit for this

1312
01:17:59,300 --> 01:18:02,200
spectral efficiency, which is
not the ultimate Shannon

1313
01:18:02,200 --> 01:18:05,720
limit, but rather is 0, in terms
of Eb over N_0 If you

1314
01:18:05,720 --> 01:18:11,420
remember, for rate 1/2 for rho
equals 1, the Shannon limit on

1315
01:18:11,420 --> 01:18:12,880
Eb over N_0 was 0 dB.

1316
01:18:12,880 --> 01:18:15,790

1317
01:18:15,790 --> 01:18:19,480
You may or may not
remember that.

1318
01:18:19,480 --> 01:18:20,420
So there's a question.

1319
01:18:20,420 --> 01:18:26,322
Does this take you all the
way to the Shannon limit?

1320
01:18:26,322 --> 01:18:29,040

1321
01:18:29,040 --> 01:18:30,780
And that would be a nice
question for somebody to

1322
01:18:30,780 --> 01:18:31,640
answer someday.

1323
01:18:31,640 --> 01:18:36,250
I think it probably does,
especially in view of the fact

1324
01:18:36,250 --> 01:18:44,850
that if you take this set down
here, again, this will be a

1325
01:18:44,850 --> 01:18:51,080
homework problem, this turns out
to be a set of Euclidean

1326
01:18:51,080 --> 01:18:55,570
images of these codes are
orthogonal signal sets.

1327
01:18:55,570 --> 01:19:00,470
For instance, 32, 6,
16, what is that?

1328
01:19:00,470 --> 01:19:04,610
That's a set of 64 constellation
points in 32

1329
01:19:04,610 --> 01:19:06,940
dimensions.

1330
01:19:06,940 --> 01:19:11,110
And algebraically, it's not hard
to figure out that every

1331
01:19:11,110 --> 01:19:14,070
one of these code words is
orthogonal in a Euclidean

1332
01:19:14,070 --> 01:19:16,870
sense to one another, except for
one that's complementary,

1333
01:19:16,870 --> 01:19:20,510
which is just what you expect in
a bi-orthogonal signal set.

1334
01:19:20,510 --> 01:19:23,850
So these give you bi-orthogonal,
they're called

1335
01:19:23,850 --> 01:19:28,150
bi-orthogonal codes, or
first-order Reed-Muller codes,

1336
01:19:28,150 --> 01:19:35,360
because the parameter r
is 1 for all of these.

1337
01:19:35,360 --> 01:19:38,740
What's happening to the spectral
efficiency here?

1338
01:19:38,740 --> 01:19:41,800
Spectral efficiency goes to 0.

1339
01:19:41,800 --> 01:19:45,330
So these become highly
inefficient from a bandwidth

1340
01:19:45,330 --> 01:19:47,680
point of view, as we already
know about orthogonal,

1341
01:19:47,680 --> 01:19:50,550
bi-orthogonal simplex
signal sets.

1342
01:19:50,550 --> 01:19:52,970
They use up a lot
of bandwidth.

1343
01:19:52,970 --> 01:19:54,760
But what else do we
know about them?

1344
01:19:54,760 --> 01:20:00,880
In this case, we definitely know
that the effective coding

1345
01:20:00,880 --> 01:20:03,575
gain does go to the Shannon
limit, and in this case, to

1346
01:20:03,575 --> 01:20:06,740
the ultimate Shannon limit
for rho equals 0 as

1347
01:20:06,740 --> 01:20:08,780
rho approaches 0.

1348
01:20:08,780 --> 01:20:12,240
So here, there's a proof that
these codes can get you to the

1349
01:20:12,240 --> 01:20:13,500
Shannon limit.

1350
01:20:13,500 --> 01:20:17,530
But as we've already explained
earlier, geometrically, it's

1351
01:20:17,530 --> 01:20:20,930
at the cost of using much more
bandwidth than you probably

1352
01:20:20,930 --> 01:20:22,880
really want to use.

1353
01:20:22,880 --> 01:20:26,160
But here, at least, is one
capacity-approaching set of

1354
01:20:26,160 --> 01:20:29,000
codes, just among these rather
simple Reed-Muller

1355
01:20:29,000 --> 01:20:32,970
codes along this line.

1356
01:20:32,970 --> 01:20:34,940
And of course, we also
see our repetition

1357
01:20:34,940 --> 01:20:37,250
codes, our trivial codes.

1358
01:20:37,250 --> 01:20:39,280
So this is a nice

1359
01:20:39,280 --> 01:20:40,780
representative family of codes.

1360
01:20:40,780 --> 01:20:45,110
And it really does tell you
quite well what to expect.

1361
01:20:45,110 --> 01:20:46,380
Are you looking at your watch?

1362
01:20:46,380 --> 01:20:47,105
Thank you.

1363
01:20:47,105 --> 01:20:50,660
I appreciate the hint.

1364
01:20:50,660 --> 01:20:56,390
So we didn't quite finish
chapter six today.

1365
01:20:56,390 --> 01:20:59,610
Next time, we'll start out with
the penalties of making

1366
01:20:59,610 --> 01:21:03,970
hard decisions, which at first
brush seems like a not

1367
01:21:03,970 --> 01:21:05,710
unreasonable compromise
to make.

1368
01:21:05,710 --> 01:21:09,600
But it actually costs
a serious penalty.

1369
01:21:09,600 --> 01:21:12,360
And that will finish
chapter six.

1370
01:21:12,360 --> 01:21:15,080
I'll do that as briefly
as I can.

1371
01:21:15,080 --> 01:21:18,090
And then we'll get into chapters
seven and eight,

1372
01:21:18,090 --> 01:21:21,890
which is finite fields and
Reed-Solomon codes, which are

1373
01:21:21,890 --> 01:21:25,680
the single great triumph of
algebraic coding theory.

1374
01:21:25,680 --> 01:21:28,250

1375
01:21:28,250 --> 01:21:29,780
So OK, that's tomorrow.

1376
01:21:29,780 --> 01:21:39,363