1
00:00:00,000 --> 00:00:00,490

2
00:00:00,490 --> 00:00:03,660
PROFESSOR: The topic of this
chapter is finding trellis

3
00:00:03,660 --> 00:00:08,460
representations for block codes,
in particular linear

4
00:00:08,460 --> 00:00:09,120
block codes.

5
00:00:09,120 --> 00:00:12,270
We're looking only at binary
block codes, except one of the

6
00:00:12,270 --> 00:00:16,830
homework problems looks at MDS
codes over ground field of q.

7
00:00:16,830 --> 00:00:21,440
The principles are the same for
general Fq or in fact for

8
00:00:21,440 --> 00:00:23,070
group codes.

9
00:00:23,070 --> 00:00:25,320
We're looking for minimal
trellis representations.

10
00:00:25,320 --> 00:00:28,270

11
00:00:28,270 --> 00:00:33,280
And so just to review our line
of thought, basically we

12
00:00:33,280 --> 00:00:36,900
proved a basic theorem called
the state space theorem that

13
00:00:36,900 --> 00:00:43,730
tells us that there is a vector
space over the ground

14
00:00:43,730 --> 00:00:48,330
field at any time which we can
identify with the state space.

15
00:00:48,330 --> 00:00:50,590
It has a certain dimension.

16
00:00:50,590 --> 00:00:55,710
And we got a little formula in
terms of subcodes for the

17
00:00:55,710 --> 00:00:57,850
dimension of the state space.

18
00:00:57,850 --> 00:01:01,830
We set up a little generator
matrix where we isolated the

19
00:01:01,830 --> 00:01:05,170
past part of the code with
respect to a certain cut time

20
00:01:05,170 --> 00:01:08,120
future part of the code,
generators for that.

21
00:01:08,120 --> 00:01:11,880
We subtract those
generators out.

22
00:01:11,880 --> 00:01:12,610
What's left?

23
00:01:12,610 --> 00:01:16,950
The number of generators is the
number of generators it

24
00:01:16,950 --> 00:01:19,950
takes to generate the state
space, in other words the

25
00:01:19,950 --> 00:01:21,850
dimension of the state space.

26
00:01:21,850 --> 00:01:25,770
So we got a theorem on the
dimension of the state space

27
00:01:25,770 --> 00:01:27,330
at any time.

28
00:01:27,330 --> 00:01:33,300
And then we found a nifty little
algorithm to find a --

29
00:01:33,300 --> 00:01:38,260
to determine the dimensions of
the state spaces at all times,

30
00:01:38,260 --> 00:01:40,080
the minimal state spaces.

31
00:01:40,080 --> 00:01:45,440
And in fact we can use this
algorithm to construct a

32
00:01:45,440 --> 00:01:48,095
minimal trellis realization.

33
00:01:48,095 --> 00:01:50,180
The algorithm involves a

34
00:01:50,180 --> 00:01:53,450
trellis-oriented generator matrix.

35
00:01:53,450 --> 00:01:57,560
And the idea here turns
out to be very simple.

36
00:01:57,560 --> 00:02:02,060
All you do is you find any
generator matrix for your

37
00:02:02,060 --> 00:02:04,610
linear block code, and
you reduce it to

38
00:02:04,610 --> 00:02:06,910
trellis-oriented form.

39
00:02:06,910 --> 00:02:10,009
Trellis-oriented form means that
the generators have as

40
00:02:10,009 --> 00:02:11,720
short a span as possible.

41
00:02:11,720 --> 00:02:14,750
It's a minimum span
generator matrix.

42
00:02:14,750 --> 00:02:18,060
And we do that just in a greedy
fashion by any time we

43
00:02:18,060 --> 00:02:23,770
have an opportunity to add two
generators together such that

44
00:02:23,770 --> 00:02:26,880
either their starting position
cancels, or their end position

45
00:02:26,880 --> 00:02:28,400
cancels, we do it.

46
00:02:28,400 --> 00:02:31,360
And out of that we get a shorter
generator, and we can

47
00:02:31,360 --> 00:02:34,100
replace one of the two
generators in the

48
00:02:34,100 --> 00:02:35,730
combination by that.

49
00:02:35,730 --> 00:02:38,290
We can keep shortening
everything up.

50
00:02:38,290 --> 00:02:42,880
The algorithm must terminate at
the point where no further

51
00:02:42,880 --> 00:02:44,130
shortening is possible.

52
00:02:44,130 --> 00:02:46,490

53
00:02:46,490 --> 00:02:49,750
And that is explicitly the
point at which all the

54
00:02:49,750 --> 00:02:51,900
starting times of the generators
are different, and

55
00:02:51,900 --> 00:02:57,000
all the ending times of all the
generators are different.

56
00:02:57,000 --> 00:02:58,130
For example, here's a

57
00:02:58,130 --> 00:03:00,660
trellis-oriented generator matrix.

58
00:03:00,660 --> 00:03:03,680
The starting times,
the spans of the

59
00:03:03,680 --> 00:03:06,820
generators, are like this.

60
00:03:06,820 --> 00:03:09,600
The active times, starting
times --

61
00:03:09,600 --> 00:03:13,180
there's the starting time of
this one, and its ending time.

62
00:03:13,180 --> 00:03:15,150
Here's the starting time
of the next one,

63
00:03:15,150 --> 00:03:16,530
and its ending time.

64
00:03:16,530 --> 00:03:20,130
The starting time of the
next one, and its

65
00:03:20,130 --> 00:03:21,920
ending time is here.

66
00:03:21,920 --> 00:03:24,930
And the starting time
of this one, and its

67
00:03:24,930 --> 00:03:27,260
ending time is here.

68
00:03:27,260 --> 00:03:29,920
We're not always going to find
that the starting and ending

69
00:03:29,920 --> 00:03:33,180
times are disjoint.

70
00:03:33,180 --> 00:03:35,630
This happens, it turns
out, because this

71
00:03:35,630 --> 00:03:37,500
is a self-dual code.

72
00:03:37,500 --> 00:03:41,130
In a self-dual code, you will
always get this each time,

73
00:03:41,130 --> 00:03:43,190
either a starting time
or an ending time.

74
00:03:43,190 --> 00:03:45,410
But that's not a general
property.

75
00:03:45,410 --> 00:03:51,425
For instance, another example
that we've used is, say, the 8

76
00:03:51,425 --> 00:03:56,010
7 2 single parity check code.

77
00:03:56,010 --> 00:03:58,880
What are its generators?

78
00:03:58,880 --> 00:04:08,240
Its generators look like
this, dot, dot, dot,

79
00:04:08,240 --> 00:04:11,190
down to 0, 0, 1, 1.

80
00:04:11,190 --> 00:04:13,130
That's a set of trellis-oriented
generators

81
00:04:13,130 --> 00:04:16,990
with starting time, ending
time, the first one here.

82
00:04:16,990 --> 00:04:20,390
Starting time, ending time
of the second one there.

83
00:04:20,390 --> 00:04:24,570
So in general for this one,
every time is a starting and

84
00:04:24,570 --> 00:04:30,310
ending time up to here, where
every intermediate time is

85
00:04:30,310 --> 00:04:32,690
both the starting and
an ending time.

86
00:04:32,690 --> 00:04:38,850
So it could happen that way,
or another example would be

87
00:04:38,850 --> 00:04:44,870
the 8 1 8 repetition code.

88
00:04:44,870 --> 00:04:47,590
What's a trellis-oriented
generator matrix for that?

89
00:04:47,590 --> 00:04:48,545
It only has one generator.

90
00:04:48,545 --> 00:04:49,690
It looks like that.

91
00:04:49,690 --> 00:04:52,230
It has a starting span
as the whole thing.

92
00:04:52,230 --> 00:04:53,230
The starting time is here.

93
00:04:53,230 --> 00:04:55,720
The ending time is here.

94
00:04:55,720 --> 00:05:00,180
So for general codes, the
starting times and ending

95
00:05:00,180 --> 00:05:01,500
times could be anywhere.

96
00:05:01,500 --> 00:05:04,740
There will always
be k of them.

97
00:05:04,740 --> 00:05:09,480
And otherwise, there's always
one at the beginning.

98
00:05:09,480 --> 00:05:11,860
If it's a nontrivial code,
there's always an ending time

99
00:05:11,860 --> 00:05:12,970
at the end, et cetera.

100
00:05:12,970 --> 00:05:19,380
But this particular behavior
is for self-dual codes.

101
00:05:19,380 --> 00:05:24,340
Anyway, having done that
we can now read off the

102
00:05:24,340 --> 00:05:28,840
dimensions of the state spaces
by simply looking for how many

103
00:05:28,840 --> 00:05:32,980
generators are active at
any particular time.

104
00:05:32,980 --> 00:05:35,670
For a state space, we're always
looking at the times

105
00:05:35,670 --> 00:05:38,830
between the symbols,
cut times.

106
00:05:38,830 --> 00:05:41,310
We could in fact draw a trivial
one there, but we're

107
00:05:41,310 --> 00:05:42,850
looking between here.

108
00:05:42,850 --> 00:05:44,560
How many are active
at this time?

109
00:05:44,560 --> 00:05:45,840
One.

110
00:05:45,840 --> 00:05:49,120
So dimension of the state
space at state

111
00:05:49,120 --> 00:05:55,750
time k is 1, 2, 3.

112
00:05:55,750 --> 00:05:59,040
This point, we come
back to 2 again.

113
00:05:59,040 --> 00:06:03,490
3, 2, 1, 0, 0 at the end.

114
00:06:03,490 --> 00:06:05,750
It's always zero at the ends
because at that point

115
00:06:05,750 --> 00:06:11,040
everything's in the future, or
everything is in the past.

116
00:06:11,040 --> 00:06:13,020
So these are trivial
state spaces.

117
00:06:13,020 --> 00:06:18,150
These are the nontrivial state
spaces in the trellis.

118
00:06:18,150 --> 00:06:21,980
And in fact, you remember
we had a little picture.

119
00:06:21,980 --> 00:06:24,670
We can draw this complete
trellis out with the state

120
00:06:24,670 --> 00:06:32,430
spaces of size 1 2
4 8 4 8 4 2 1.

121
00:06:32,430 --> 00:06:37,060
So this is called the state
dimension profile, just this

122
00:06:37,060 --> 00:06:39,640
set, this ordered set.

123
00:06:39,640 --> 00:06:44,380
Or the state space size profile
is 2 to the dimension,

124
00:06:44,380 --> 00:06:47,260
of binary codes, whatever.

125
00:06:47,260 --> 00:06:50,660
And similarly down here, if we
look at state space sizes, we

126
00:06:50,660 --> 00:06:55,600
see the dimension is going
to be one at every time.

127
00:06:55,600 --> 00:06:59,860
So in this case, the dimension
of the state space is 0, 1, 1,

128
00:06:59,860 --> 00:07:02,870
1, 1, 1, 1, 1, 1, 0.

129
00:07:02,870 --> 00:07:05,320
And similarly down here, we
look at the cut time.

130
00:07:05,320 --> 00:07:08,250
It cuts one active generator
every time.

131
00:07:08,250 --> 00:07:12,730
So it's 0, 1, 1, 1, 1, 1, 0.

132
00:07:12,730 --> 00:07:16,810
So we get at least the state
space dimensions just by

133
00:07:16,810 --> 00:07:17,630
inspection of the

134
00:07:17,630 --> 00:07:19,255
trellis-oriented generator matrix.

135
00:07:19,255 --> 00:07:23,430

136
00:07:23,430 --> 00:07:23,885
Question?

137
00:07:23,885 --> 00:07:25,135
AUDIENCE: [INAUDIBLE]

138
00:07:25,135 --> 00:07:27,500

139
00:07:27,500 --> 00:07:30,200
PROFESSOR: We proved it
in several steps.

140
00:07:30,200 --> 00:07:39,100
First we have the state space
theorem, which I gave to you

141
00:07:39,100 --> 00:07:41,770
in the following form: the
dimension of the state space

142
00:07:41,770 --> 00:07:47,530
at time k is equal to the
dimension of the code minus

143
00:07:47,530 --> 00:07:49,940
the past subcode.

144
00:07:49,940 --> 00:07:50,840
Let me write that.

145
00:07:50,840 --> 00:07:55,580
The dimension of the past
subcode minus the dimension of

146
00:07:55,580 --> 00:08:01,500
the future subcode at time k
relative to this cut time.

147
00:08:01,500 --> 00:08:04,960
And we proved from the
trellis-oriented generator

148
00:08:04,960 --> 00:08:08,180
matrix that the past subcode
is generated by all the

149
00:08:08,180 --> 00:08:11,660
trellis-oriented generators that
have support on the past,

150
00:08:11,660 --> 00:08:13,120
and the future by all
the ones that have

151
00:08:13,120 --> 00:08:15,040
support on the future.

152
00:08:15,040 --> 00:08:18,220
So, it's simply we
take those out.

153
00:08:18,220 --> 00:08:19,110
And what do we have left?

154
00:08:19,110 --> 00:08:23,540
We have the ones that are active
at time k, the ones

155
00:08:23,540 --> 00:08:26,560
that are neither wholly
supported on the past nor on

156
00:08:26,560 --> 00:08:26,990
the future.

157
00:08:26,990 --> 00:08:29,870
They're supported both on
the past and future.

158
00:08:29,870 --> 00:08:32,919
And those, that's what
this difference is.

159
00:08:32,919 --> 00:08:36,580

160
00:08:36,580 --> 00:08:39,590
So explicitly we have --

161
00:08:39,590 --> 00:08:43,724
the code is generated
by all generators.

162
00:08:43,724 --> 00:08:46,580

163
00:08:46,580 --> 00:08:49,210
That's all k generators.

164
00:08:49,210 --> 00:08:58,340
Cpk is generated by
trellis-oriented generators

165
00:08:58,340 --> 00:09:01,690
supported on the past.

166
00:09:01,690 --> 00:09:06,070
And Cfk is generated by the
trellis-oriented generators

167
00:09:06,070 --> 00:09:07,320
supported on the future.

168
00:09:07,320 --> 00:09:09,840

169
00:09:09,840 --> 00:09:11,880
So the difference --

170
00:09:11,880 --> 00:09:16,670
state code sk is generated
by the trellis-oriented

171
00:09:16,670 --> 00:09:21,500
generators not supported
on past or future, or

172
00:09:21,500 --> 00:09:25,387
active at time k.

173
00:09:25,387 --> 00:09:28,020

174
00:09:28,020 --> 00:09:32,060
Probably good to write all
that out at least once.

175
00:09:32,060 --> 00:09:32,772
Yeah?

176
00:09:32,772 --> 00:09:34,218
AUDIENCE: [INAUDIBLE]

177
00:09:34,218 --> 00:09:38,317
self-dual codes all have such
properties that each time is

178
00:09:38,317 --> 00:09:39,270
starting and ending?

179
00:09:39,270 --> 00:09:41,145
PROFESSOR: Yes.

180
00:09:41,145 --> 00:09:42,390
AUDIENCE: Why is that?

181
00:09:42,390 --> 00:09:43,025
PROFESSOR: Why?

182
00:09:43,025 --> 00:09:46,820
It's a duality theorem, and
we're not doing many duality

183
00:09:46,820 --> 00:09:49,870
theorems in this course, so
I'll simply tell you.

184
00:09:49,870 --> 00:09:51,770
AUDIENCE: [INAUDIBLE]

185
00:09:51,770 --> 00:09:55,990
has this property, it
must be a self-dual.

186
00:09:55,990 --> 00:09:57,405
PROFESSOR: I don't think
that's true.

187
00:09:57,405 --> 00:10:01,100

188
00:10:01,100 --> 00:10:04,190
It's possible that's true.

189
00:10:04,190 --> 00:10:06,913
Duality theorems are very
strong, but I don't think this

190
00:10:06,913 --> 00:10:08,163
is a sufficient property.

191
00:10:08,163 --> 00:10:11,990

192
00:10:11,990 --> 00:10:14,145
For instance, suppose I just
changed one of the generators

193
00:10:14,145 --> 00:10:17,300
to look like that.

194
00:10:17,300 --> 00:10:22,930
It still has disjoint starting
and ending times, but now I

195
00:10:22,930 --> 00:10:24,180
don't think the code
is self-dual.

196
00:10:24,180 --> 00:10:26,920

197
00:10:26,920 --> 00:10:30,100
So here's another code generated
by these four

198
00:10:30,100 --> 00:10:33,740
generators, and I don't
believe self-dual.

199
00:10:33,740 --> 00:10:36,440
AUDIENCE: [INAUDIBLE]

200
00:10:36,440 --> 00:10:38,370
PROFESSOR: I'm guessing
that it isn't.

201
00:10:38,370 --> 00:10:44,160
To prove it I would compute
the dual code, and I would

202
00:10:44,160 --> 00:10:46,130
find that it wasn't same
code, didn't have

203
00:10:46,130 --> 00:10:47,380
the same code words.

204
00:10:47,380 --> 00:10:49,980

205
00:10:49,980 --> 00:10:53,180
But I'm guessing that if I just
make random changes in

206
00:10:53,180 --> 00:10:55,860
the interior here, I'm not going
to get a self-dual code,

207
00:10:55,860 --> 00:10:59,650
because that's a very strong
structural property.

208
00:10:59,650 --> 00:11:03,600
But I'm not going to take the
time in class to do that.

209
00:11:03,600 --> 00:11:06,650
But these are good questions.

210
00:11:06,650 --> 00:11:11,410
The whole subject of duality
is a wonderful and elegant

211
00:11:11,410 --> 00:11:13,210
topic that we just don't
have time to do

212
00:11:13,210 --> 00:11:14,230
much in this course.

213
00:11:14,230 --> 00:11:17,050
If I did it another time,
I could spend

214
00:11:17,050 --> 00:11:18,560
many lectures on duality.

215
00:11:18,560 --> 00:11:21,960
Some of the homework problems
have suggested what you might

216
00:11:21,960 --> 00:11:25,710
be able to do in orthogonal
codes, but --

217
00:11:25,710 --> 00:11:30,110

218
00:11:30,110 --> 00:11:34,730
well, one of the problems you'll
do on the homework --

219
00:11:34,730 --> 00:11:36,210
I was going to talk about
it a little later.

220
00:11:36,210 --> 00:11:38,860
There's a dual state space
theorem that basically says

221
00:11:38,860 --> 00:11:42,140
the state space sizes, or
dimensions, are the same for

222
00:11:42,140 --> 00:11:46,530
the dual code as they are
for the primal code.

223
00:11:46,530 --> 00:11:48,500
Here's one example.

224
00:11:48,500 --> 00:11:52,140
Of course, dual is itself, so
it's trivial that the state

225
00:11:52,140 --> 00:11:53,250
space size is the same.

226
00:11:53,250 --> 00:11:55,360
But here's another less
trivial example.

227
00:11:55,360 --> 00:11:58,980
These two codes are orthogonal
to each other.

228
00:11:58,980 --> 00:12:01,580
And what is similar about
their trellises?

229
00:12:01,580 --> 00:12:05,010
Their trellises are both
two-state trellises.

230
00:12:05,010 --> 00:12:07,100
They don't look the same.

231
00:12:07,100 --> 00:12:12,540
This trellis looks like this,
because they're all zeroes up

232
00:12:12,540 --> 00:12:16,950
here, and all ones down here.

233
00:12:16,950 --> 00:12:20,470
That's the repetition code
trellis, whereas this trellis

234
00:12:20,470 --> 00:12:22,550
looks like this.

235
00:12:22,550 --> 00:12:30,300
It has crosses every time and
so forth, abstractly.

236
00:12:30,300 --> 00:12:33,280
So trellises are not the same.

237
00:12:33,280 --> 00:12:36,980
They have different branching
properties, but the state

238
00:12:36,980 --> 00:12:39,410
space sizes are the
same at all times.

239
00:12:39,410 --> 00:12:43,560
This is a general property of
dual codes which you will

240
00:12:43,560 --> 00:12:46,380
prove on the homework, if you
haven't done so already.

241
00:12:46,380 --> 00:12:51,420

242
00:12:51,420 --> 00:12:56,470
Sorry, it's hard to know what to
tell you about and what to

243
00:12:56,470 --> 00:12:59,140
suppress, because I'm also
trying to cover more

244
00:12:59,140 --> 00:13:00,480
material this year.

245
00:13:00,480 --> 00:13:02,840
There's a lot of material that's
really nice that I have

246
00:13:02,840 --> 00:13:04,090
to skip over.

247
00:13:04,090 --> 00:13:06,350

248
00:13:06,350 --> 00:13:10,040
Let's continue from this.

249
00:13:10,040 --> 00:13:14,080
Let's make a minimal
realization.

250
00:13:14,080 --> 00:13:19,770
So, a canonical minimal
trellis.

251
00:13:19,770 --> 00:13:23,380
I'm doing this in a little bit
different order than it's done

252
00:13:23,380 --> 00:13:27,630
in the notes, but I think you
will see this kind of argument

253
00:13:27,630 --> 00:13:28,880
very quickly.

254
00:13:28,880 --> 00:13:30,730

255
00:13:30,730 --> 00:13:33,920
I've got this trellis-oriented
generator matrix, but suppose

256
00:13:33,920 --> 00:13:36,025
I didn't know what the
trellis looked like.

257
00:13:36,025 --> 00:13:38,490
I put it up the first
time last time.

258
00:13:38,490 --> 00:13:41,370
But all I have is this generator
matrix, and I want

259
00:13:41,370 --> 00:13:44,690
to generate a trellis now for
this code which has minimal

260
00:13:44,690 --> 00:13:46,170
state spaces.

261
00:13:46,170 --> 00:13:48,610
It's also going to turn out to
be minimal in every other way.

262
00:13:48,610 --> 00:13:51,490

263
00:13:51,490 --> 00:13:55,000
Well, let's start off
by realizing the

264
00:13:55,000 --> 00:13:58,540
first generator here.

265
00:13:58,540 --> 00:14:02,330
The first generator generates a
little one-dimensional code.

266
00:14:02,330 --> 00:14:05,760

267
00:14:05,760 --> 00:14:09,770
G1, the code generated by the
first generator, is simply the

268
00:14:09,770 --> 00:14:15,380
two code words 0, 0, 0,
0, 1, 1, 1, 1, 0, 0.

269
00:14:15,380 --> 00:14:18,960

270
00:14:18,960 --> 00:14:22,140
So let me realize that little
one-dimensional code with a

271
00:14:22,140 --> 00:14:23,935
minimal trellis for that.

272
00:14:23,935 --> 00:14:27,124
What would it look like?

273
00:14:27,124 --> 00:14:30,470
If I go through this, I'll
see that it has --

274
00:14:30,470 --> 00:14:34,590
my trellis-oriented generator
matrix for this code is simply

275
00:14:34,590 --> 00:14:38,080
1, 1, 1, 1, 0, 0, 0.

276
00:14:38,080 --> 00:14:43,090
I see from that that the
dimensions of the state spaces

277
00:14:43,090 --> 00:14:46,970
is 0, 1, 1, 1, 0, 0, 0, 0, 0.

278
00:14:46,970 --> 00:14:50,030

279
00:14:50,030 --> 00:14:56,740
And you can easily see that what
the trellis, the minimal

280
00:14:56,740 --> 00:15:04,840
trellis, a minimal trellis looks
like is 0, 0, 0, 0, 1,

281
00:15:04,840 --> 00:15:14,160
1, 1, 1, 0, 0, 0, 0.

282
00:15:14,160 --> 00:15:16,600
So there is the minimal trellis
realization for that

283
00:15:16,600 --> 00:15:19,380
one-dimensional code.

284
00:15:19,380 --> 00:15:24,230
It has state spaces of
dimension 0, 1, 1,

285
00:15:24,230 --> 00:15:27,570
1, 0, 0, 0, 0, 0.

286
00:15:27,570 --> 00:15:30,770
Therefore the state spaces
are all minimal,

287
00:15:30,770 --> 00:15:32,965
as proved from this.

288
00:15:32,965 --> 00:15:34,510
It's all sort of elementary.

289
00:15:34,510 --> 00:15:38,230

290
00:15:38,230 --> 00:15:49,230
Similarly, I can realize this
one by another little machine

291
00:15:49,230 --> 00:15:50,480
that looks like this.

292
00:15:50,480 --> 00:15:59,300

293
00:15:59,300 --> 00:16:02,160
0, 0, 0, 0, 0, 0, 0.

294
00:16:02,160 --> 00:16:07,310
This is just the state
transition diagram of a linear

295
00:16:07,310 --> 00:16:10,790
time-varying finite
state machine.

296
00:16:10,790 --> 00:16:14,390
And it looks like that, and it
too is minimal by the same

297
00:16:14,390 --> 00:16:17,500
argument for the one-dimensional
code generated

298
00:16:17,500 --> 00:16:19,860
by this generator.

299
00:16:19,860 --> 00:16:22,690

300
00:16:22,690 --> 00:16:23,750
What is this saying here?

301
00:16:23,750 --> 00:16:26,480
This is saying we really --

302
00:16:26,480 --> 00:16:28,660
what we should imagine here
is we have a little memory

303
00:16:28,660 --> 00:16:36,100
element that's only active at
state times 1, 2, and 3.

304
00:16:36,100 --> 00:16:40,020
So to realize this, this is a

305
00:16:40,020 --> 00:16:43,140
one-dimensional memory element.

306
00:16:43,140 --> 00:16:46,001
Think of it as a little --

307
00:16:46,001 --> 00:16:49,600
well, a memory for
an element of f2.

308
00:16:49,600 --> 00:16:55,110
It's active during the interval
1 through 3, during

309
00:16:55,110 --> 00:16:57,070
the time that this generator
is active.

310
00:16:57,070 --> 00:16:59,640

311
00:16:59,640 --> 00:17:03,270
It's active at these three
times, not otherwise.

312
00:17:03,270 --> 00:17:05,150
So you can think of it
as just disappearing.

313
00:17:05,150 --> 00:17:08,130
It comes into existence
at time 1.

314
00:17:08,130 --> 00:17:11,839
It holds whatever the
input bit is.

315
00:17:11,839 --> 00:17:13,040
Think of --

316
00:17:13,040 --> 00:17:18,270
we're trying to create the
code as the set of all --

317
00:17:18,270 --> 00:17:21,109
sum of ui gi.

318
00:17:21,109 --> 00:17:23,310
And so what this memory element
really does is it

319
00:17:23,310 --> 00:17:27,780
holds ui during the time that
it's needed, which is at times

320
00:17:27,780 --> 00:17:30,450
1, 2, and 3.

321
00:17:30,450 --> 00:17:32,240
Whatever the coefficient is --

322
00:17:32,240 --> 00:17:34,090
what could it be, 0 or 1?

323
00:17:34,090 --> 00:17:36,280
Element of the base field, f2.

324
00:17:36,280 --> 00:17:46,120
So the memory element holds, it
contains u1 in this case.

325
00:17:46,120 --> 00:17:47,322
Yeah?

326
00:17:47,322 --> 00:17:50,610
AUDIENCE: What if we look at
this matrix only for the

327
00:17:50,610 --> 00:17:51,960
second code.

328
00:17:51,960 --> 00:17:52,944
PROFESSOR: Yes.

329
00:17:52,944 --> 00:17:58,060
AUDIENCE: So that will give
0, 1, 0, 1, 1, 0, 1, 0.

330
00:17:58,060 --> 00:17:59,190
PROFESSOR: Correct.

331
00:17:59,190 --> 00:18:01,970
AUDIENCE: So some places it
will suggest that the

332
00:18:01,970 --> 00:18:04,670
dimension is --

333
00:18:04,670 --> 00:18:09,900
PROFESSOR: The fact that
the values are --

334
00:18:09,900 --> 00:18:12,570
there will always be 1 here at
the starting time and the

335
00:18:12,570 --> 00:18:13,640
ending time.

336
00:18:13,640 --> 00:18:16,570
Otherwise we wouldn't
draw a branch there.

337
00:18:16,570 --> 00:18:20,150
But they can be arbitrary
in between.

338
00:18:20,150 --> 00:18:23,960
So don't be thrown off by the
fact that there are some 0

339
00:18:23,960 --> 00:18:25,950
values in here.

340
00:18:25,950 --> 00:18:30,870
What we're doing here is we're
realizing u2 times g2, where

341
00:18:30,870 --> 00:18:34,430
u2 can be either 0 or 1.

342
00:18:34,430 --> 00:18:38,390
And g2 can be arbitrary, except
that it has a starting

343
00:18:38,390 --> 00:18:40,250
time and an ending
time, so it's not

344
00:18:40,250 --> 00:18:41,740
arbitrary for this kind.

345
00:18:41,740 --> 00:18:44,740

346
00:18:44,740 --> 00:18:46,908
AUDIENCE: What if we try
to find the state space

347
00:18:46,908 --> 00:18:48,158
[INAUDIBLE]

348
00:18:48,158 --> 00:18:51,150

349
00:18:51,150 --> 00:18:54,940
PROFESSOR: For this, what I
need is a one-dimensional

350
00:18:54,940 --> 00:19:01,320
memory element containing u2
which is active during a

351
00:19:01,320 --> 00:19:04,300
different interval,
2 through 6.

352
00:19:04,300 --> 00:19:07,820

353
00:19:07,820 --> 00:19:09,780
So think of these as like
little stars that

354
00:19:09,780 --> 00:19:12,000
wink on or wink off.

355
00:19:12,000 --> 00:19:14,310
This thing comes into
existence for three

356
00:19:14,310 --> 00:19:17,600
consecutive times, and
then it disappears.

357
00:19:17,600 --> 00:19:20,600
This thing comes into existence
for five consecutive

358
00:19:20,600 --> 00:19:23,400
times, and then it disappears.

359
00:19:23,400 --> 00:19:25,370
Because those are the only
times when it's needed to

360
00:19:25,370 --> 00:19:26,620
contribute to the output.

361
00:19:26,620 --> 00:19:29,600

362
00:19:29,600 --> 00:19:36,060
So altogether, we can think of
there as sort of being four

363
00:19:36,060 --> 00:19:43,140
memory elements which contain
u1, u2, u3, and u4.

364
00:19:43,140 --> 00:19:52,270
And we form the outputs g1k
times this, sort of like in

365
00:19:52,270 --> 00:19:54,300
the convolutional code.

366
00:19:54,300 --> 00:20:01,900
g2k g3k and g4k.

367
00:20:01,900 --> 00:20:06,610
The generators step along in
time, and we form the outputs.

368
00:20:06,610 --> 00:20:13,330
We sum this all together in a
summer, and this provides yk,

369
00:20:13,330 --> 00:20:20,690
the output, as we go from k
equals 1 through 8 as we go

370
00:20:20,690 --> 00:20:23,010
through the code word.

371
00:20:23,010 --> 00:20:26,020
But we only need this one
for -- it's only on from

372
00:20:26,020 --> 00:20:30,260
time 1, 2, and 3.

373
00:20:30,260 --> 00:20:33,720
And this is on from
time 2 through 6.

374
00:20:33,720 --> 00:20:37,180
And this is on from
time 3 through 5.

375
00:20:37,180 --> 00:20:40,770
And this is on from
time 4 through 7.

376
00:20:40,770 --> 00:20:44,820
Because we don't need
it any other time.

377
00:20:44,820 --> 00:20:48,330
So you can think of an input
coming in at time 1, at the

378
00:20:48,330 --> 00:20:52,070
starting time of the first
generator, being saved for as

379
00:20:52,070 --> 00:20:54,210
long as it's needed, then
it's discarded.

380
00:20:54,210 --> 00:20:57,005
And in fact we don't need that
memory element anymore.

381
00:20:57,005 --> 00:21:01,130

382
00:21:01,130 --> 00:21:03,190
How many people are
getting this?

383
00:21:03,190 --> 00:21:04,690
Raise your hand if
you get this.

384
00:21:04,690 --> 00:21:07,462

385
00:21:07,462 --> 00:21:08,712
AUDIENCE: [INAUDIBLE]

386
00:21:08,712 --> 00:21:10,730

387
00:21:10,730 --> 00:21:11,540
PROFESSOR: It's a time --

388
00:21:11,540 --> 00:21:15,720
what I'm trying to do is draw
a time-varying machine.

389
00:21:15,720 --> 00:21:18,810
So how do I do that?

390
00:21:18,810 --> 00:21:20,630
At time 1, it looks like this.

391
00:21:20,630 --> 00:21:23,360

392
00:21:23,360 --> 00:21:27,540
Time 1, it just has u1,
and we multiply it by

393
00:21:27,540 --> 00:21:29,890
g11, which is 1.

394
00:21:29,890 --> 00:21:31,850
And that gives me the
output at time 1.

395
00:21:31,850 --> 00:21:35,250
There's nothing else
that contributes.

396
00:21:35,250 --> 00:21:43,670
At time 2, we've got now another
input, u1 and u2.

397
00:21:43,670 --> 00:21:46,200
And we've got to sum the
contributions from both of

398
00:21:46,200 --> 00:21:48,655
those, times their respective
coefficients.

399
00:21:48,655 --> 00:21:51,210

400
00:21:51,210 --> 00:21:55,550
At time 3, we're up to
three of them, and

401
00:21:55,550 --> 00:21:56,550
we need all of them.

402
00:21:56,550 --> 00:21:59,310
We're going to form some linear
combination according

403
00:21:59,310 --> 00:22:01,626
to the generator matrix.

404
00:22:01,626 --> 00:22:02,876
AUDIENCE: [INAUDIBLE]

405
00:22:02,876 --> 00:22:04,770

406
00:22:04,770 --> 00:22:08,130
PROFESSOR: It's time-varying,
yeah.

407
00:22:08,130 --> 00:22:09,410
So get used to it.

408
00:22:09,410 --> 00:22:13,820
For a block code it obviously
has to be time-varying.

409
00:22:13,820 --> 00:22:18,990
Obviously if we regard these as
impulse responses, this is

410
00:22:18,990 --> 00:22:21,205
the impulse response to u1.

411
00:22:21,205 --> 00:22:26,520
It only lasts in terms of symbol
times from time 0 1 2

412
00:22:26,520 --> 00:22:30,930
3, for four time units
of symbol time.

413
00:22:30,930 --> 00:22:34,790
This is the impulse
response to u2.

414
00:22:34,790 --> 00:22:38,670
u2 you can think of as an input
that comes in at time 2,

415
00:22:38,670 --> 00:22:43,270
and whose output rings
for five more times.

416
00:22:43,270 --> 00:22:46,300
So you need to save u2 for five
more times, and then it

417
00:22:46,300 --> 00:22:46,900
disappears.

418
00:22:46,900 --> 00:22:48,055
We don't need to save
it anymore.

419
00:22:48,055 --> 00:22:50,290
We can let it drop off
the end of the shift

420
00:22:50,290 --> 00:22:53,350
register, if you like.

421
00:22:53,350 --> 00:22:59,550
u3 comes in at time 3, and this
is its impulse response.

422
00:22:59,550 --> 00:23:05,200
And u4 comes in at time 5, and
this is its impulse response.

423
00:23:05,200 --> 00:23:07,210
Does that help?

424
00:23:07,210 --> 00:23:08,910
How many people are not
getting it now?

425
00:23:08,910 --> 00:23:13,372

426
00:23:13,372 --> 00:23:14,622
AUDIENCE: [INAUDIBLE]

427
00:23:14,622 --> 00:23:20,930

428
00:23:20,930 --> 00:23:22,632
PROFESSOR: We don't need it
here, but we're going to need

429
00:23:22,632 --> 00:23:25,890
it again at time 4, so
we have to save it.

430
00:23:25,890 --> 00:23:30,650

431
00:23:30,650 --> 00:23:32,490
What are you going to do
with it at time 3?

432
00:23:32,490 --> 00:23:34,295
You going to hide
it somewhere?

433
00:23:34,295 --> 00:23:38,540

434
00:23:38,540 --> 00:23:40,210
So I still need to save it.

435
00:23:40,210 --> 00:23:44,410

436
00:23:44,410 --> 00:23:48,650
This, again, is linear system
theory, except I guess you

437
00:23:48,650 --> 00:23:52,670
just don't get taught linear
system theory anymore.

438
00:23:52,670 --> 00:23:55,490
But this is what you have
to do if you --

439
00:23:55,490 --> 00:23:59,130
before, for convolutional codes,
we did linear systems

440
00:23:59,130 --> 00:24:02,470
theory for linear time-invariant
systems.

441
00:24:02,470 --> 00:24:04,310
They have to be over a finite
field, but who cares?

442
00:24:04,310 --> 00:24:06,330
We did general linear
system theory.

443
00:24:06,330 --> 00:24:09,470
This is general linear system
theory for realizing

444
00:24:09,470 --> 00:24:10,720
time-varying systems.

445
00:24:10,720 --> 00:24:14,060

446
00:24:14,060 --> 00:24:16,910
In fact, one comment that might
be good to make at this

447
00:24:16,910 --> 00:24:19,470
point is that --

448
00:24:19,470 --> 00:24:21,460
now go back and remember
what we did with

449
00:24:21,460 --> 00:24:22,710
convolutional codes.

450
00:24:22,710 --> 00:24:25,250

451
00:24:25,250 --> 00:24:31,280
We started out with a rate 1
over n convolutional code c,

452
00:24:31,280 --> 00:24:34,760
and we found some generator
for it.

453
00:24:34,760 --> 00:24:39,520
Basically we can take any code
word in the code, and all of

454
00:24:39,520 --> 00:24:41,410
its shifts will generate
the code.

455
00:24:41,410 --> 00:24:45,030
Any non-zero code word, all of
its time shifts generate the

456
00:24:45,030 --> 00:24:46,280
convolutional code.

457
00:24:46,280 --> 00:24:49,290

458
00:24:49,290 --> 00:24:55,870
So take any code word g of d in
a convolutional code, and g

459
00:24:55,870 --> 00:24:59,320
of d, dg of d, d squared
g of d and so forth

460
00:24:59,320 --> 00:25:00,570
generate the code.

461
00:25:00,570 --> 00:25:03,000

462
00:25:03,000 --> 00:25:11,400
But then we converted it by
doing a little polynomial or

463
00:25:11,400 --> 00:25:14,830
Laurent series algebra.

464
00:25:14,830 --> 00:25:20,270
We took a rational one and we
converted it to a canonical

465
00:25:20,270 --> 00:25:25,980
one, g prime of d.

466
00:25:25,980 --> 00:25:29,480
Which if you remember, this is
the polynomial code word of

467
00:25:29,480 --> 00:25:36,840
minimum degree in the code.

468
00:25:36,840 --> 00:25:39,000
We call that degree nu.

469
00:25:39,000 --> 00:25:42,780

470
00:25:42,780 --> 00:25:44,030
What were we doing there?

471
00:25:44,030 --> 00:25:48,060

472
00:25:48,060 --> 00:25:51,880
The shifts of g prime of d
form a trellis-oriented

473
00:25:51,880 --> 00:25:56,080
generator matrix for this
convolutional code.

474
00:25:56,080 --> 00:26:00,370
For instance, for our canonical
example, g prime of

475
00:26:00,370 --> 00:26:01,620
d looked like this.

476
00:26:01,620 --> 00:26:06,070

477
00:26:06,070 --> 00:26:11,340
Polynomial notation, it's 1 plus
d squared 1 plus d plus d

478
00:26:11,340 --> 00:26:13,740
squared is the generator
matrix.

479
00:26:13,740 --> 00:26:22,380
Let me write that out as 1, 1
at time 0 or coefficient 0.

480
00:26:22,380 --> 00:26:28,950
0, 1, 1, 1, and then all
0's before that, and

481
00:26:28,950 --> 00:26:30,190
all 0's after that.

482
00:26:30,190 --> 00:26:32,720
Is somebody sleeping?

483
00:26:32,720 --> 00:26:34,730
Wake him up please, before
I turn around.

484
00:26:34,730 --> 00:26:38,860

485
00:26:38,860 --> 00:26:40,696
What?

486
00:26:40,696 --> 00:26:43,190
Oh, all right.

487
00:26:43,190 --> 00:26:46,360
I'm very glad to hear that.

488
00:26:46,360 --> 00:26:52,270
So here is g prime of d
written out as bits.

489
00:26:52,270 --> 00:26:54,530
dg prime of d looks like what?

490
00:26:54,530 --> 00:26:57,470
It looks like the same thing
shifted over one.

491
00:26:57,470 --> 00:27:00,890

492
00:27:00,890 --> 00:27:10,120
d squared g prime of d looks
like this and so forth.

493
00:27:10,120 --> 00:27:15,900

494
00:27:15,900 --> 00:27:18,320
Is this trellis-oriented?

495
00:27:18,320 --> 00:27:22,680
In this case, each time interval
contains two symbols.

496
00:27:22,680 --> 00:27:26,680
Here are our divisions
between symbols.

497
00:27:26,680 --> 00:27:29,150
We've got a rate 1/2 code, so
we chose to take them two

498
00:27:29,150 --> 00:27:30,400
symbols at a time.

499
00:27:30,400 --> 00:27:34,050

500
00:27:34,050 --> 00:27:35,830
Where are the starting
and ending times?

501
00:27:35,830 --> 00:27:37,550
This one starts here,
ends here.

502
00:27:37,550 --> 00:27:39,210
This one starts here,
ends here.

503
00:27:39,210 --> 00:27:41,100
Starts here, ends here.

504
00:27:41,100 --> 00:27:43,710
So all the starting times and
ending times are different.

505
00:27:43,710 --> 00:27:44,440
Ergo, this is a

506
00:27:44,440 --> 00:27:47,350
trellis-oriented generator matrix.

507
00:27:47,350 --> 00:27:51,420
Modulo some hand-waving about
infinite sequences.

508
00:27:51,420 --> 00:27:53,990
Ergo, we ought to be able to use
the state space theorem to

509
00:27:53,990 --> 00:27:57,830
say what are the state
space sizes.

510
00:27:57,830 --> 00:28:01,020
Any time I have a cut here,
what are the spans?

511
00:28:01,020 --> 00:28:05,590
The spans are like there,
there, there, so forth.

512
00:28:05,590 --> 00:28:11,670
So the state space dimension at
each time is going to be 2,

513
00:28:11,670 --> 00:28:16,070
2, 2, 2, 2.

514
00:28:16,070 --> 00:28:18,355
And if we go through this
construction procedure, what

515
00:28:18,355 --> 00:28:20,470
are we going to get?

516
00:28:20,470 --> 00:28:25,230
We're going to get something
that at time 0, we need to

517
00:28:25,230 --> 00:28:29,830
have in memory, we need
to remember u minus

518
00:28:29,830 --> 00:28:32,260
1 and u minus 2.

519
00:28:32,260 --> 00:28:35,050

520
00:28:35,050 --> 00:28:39,070
At time 1, just doing what I did
up here, we need to have

521
00:28:39,070 --> 00:28:43,270
in memory u minus 1 and u0.

522
00:28:43,270 --> 00:28:48,810
At time 2, we need to have
in memory u0 and u1.

523
00:28:48,810 --> 00:28:50,780
And we achieve that just
by implementing this

524
00:28:50,780 --> 00:28:52,450
with a shift register.

525
00:28:52,450 --> 00:28:56,020
In the time-invariant case it's
very easy, and you all

526
00:28:56,020 --> 00:28:57,540
understand it.

527
00:28:57,540 --> 00:29:03,890
So exactly the same theory goes
through for rate 1 over n

528
00:29:03,890 --> 00:29:05,830
convolutional codes.

529
00:29:05,830 --> 00:29:10,000
I will tell you briefly that to
treat rate k over n, it's

530
00:29:10,000 --> 00:29:13,860
basically just the same thing,
except we need k generators

531
00:29:13,860 --> 00:29:15,590
starting at each time here.

532
00:29:15,590 --> 00:29:19,300
But in order to get a canonical
encoder, we just get

533
00:29:19,300 --> 00:29:22,790
a trellis-oriented generator
matrix again.

534
00:29:22,790 --> 00:29:26,300
And by the way, modulo this
hand-waving about infinite

535
00:29:26,300 --> 00:29:31,950
sequences, I've now proved what
I asserted, that this

536
00:29:31,950 --> 00:29:35,990
encoder is minimal among all
encoders for this code, that

537
00:29:35,990 --> 00:29:38,640
it has the minimum number
of memory elements.

538
00:29:38,640 --> 00:29:42,300
Because from this argument,
the minimal state space

539
00:29:42,300 --> 00:29:46,560
dimension at each time is 2
once I've achieved this

540
00:29:46,560 --> 00:29:48,580
canonical trellis-oriented
generator matrix.

541
00:29:48,580 --> 00:29:53,070

542
00:29:53,070 --> 00:29:57,190
By the way, this theory
is very general.

543
00:29:57,190 --> 00:30:00,610
It's really all you need to know
to do minimal realization

544
00:30:00,610 --> 00:30:05,610
theory of linear systems,
whether they're time-varying

545
00:30:05,610 --> 00:30:09,065
or time-invariant over any
field, or over groups.

546
00:30:09,065 --> 00:30:13,140

547
00:30:13,140 --> 00:30:16,290
So that was a parenthetical
comment about convolutional

548
00:30:16,290 --> 00:30:18,360
codes just to tie it back
to what we did in

549
00:30:18,360 --> 00:30:19,610
the previous chapter.

550
00:30:19,610 --> 00:30:24,860

551
00:30:24,860 --> 00:30:26,340
I haven't completed
what I wanted to

552
00:30:26,340 --> 00:30:29,320
say about block codes.

553
00:30:29,320 --> 00:30:31,126
How am I going to do this
without erasing something?

554
00:30:31,126 --> 00:30:35,080

555
00:30:35,080 --> 00:30:39,140
Let's go back to block codes.

556
00:30:39,140 --> 00:30:40,775
And I guess I'll move over.

557
00:30:40,775 --> 00:30:44,710

558
00:30:44,710 --> 00:30:50,675
The point that I was in the
process of making was that I

559
00:30:50,675 --> 00:30:56,060
can realize each one of these
generators individually by a

560
00:30:56,060 --> 00:31:02,100
little trellis diagram that's
one-dimensional during the

561
00:31:02,100 --> 00:31:06,870
time that the generator is
active, and zero-dimensional

562
00:31:06,870 --> 00:31:11,220
state space during the time
the generator is inactive.

563
00:31:11,220 --> 00:31:15,840
And think of this as just
one component here.

564
00:31:15,840 --> 00:31:20,120
To generate a code word,
a particular code

565
00:31:20,120 --> 00:31:23,700
word is just the sum.

566
00:31:23,700 --> 00:31:26,140
All I need to do is sum the
outputs of all these

567
00:31:26,140 --> 00:31:28,400
generators independently.

568
00:31:28,400 --> 00:31:30,430
How many different possibilities
are there?

569
00:31:30,430 --> 00:31:33,380
There are 2 to the k possible
code words.

570
00:31:33,380 --> 00:31:35,050
Each one of these generates
one of two

571
00:31:35,050 --> 00:31:36,120
possible code words.

572
00:31:36,120 --> 00:31:40,040
If I take the set of all
possible sums of these four

573
00:31:40,040 --> 00:31:43,240
code words, I'm going to have
16 possible code words.

574
00:31:43,240 --> 00:31:46,660
So that very quickly was what
I was doing when I said,

575
00:31:46,660 --> 00:31:50,960
here's a little machine that
generates the first code, c1.

576
00:31:50,960 --> 00:31:55,150
Here's a little machine that
generates the second code, c2.

577
00:31:55,150 --> 00:31:57,780
Only has two possible code words
according to the value

578
00:31:57,780 --> 00:31:59,400
of what's in storage.

579
00:31:59,400 --> 00:32:02,180
This generates the
third component.

580
00:32:02,180 --> 00:32:04,250
This generates the
fourth component.

581
00:32:04,250 --> 00:32:07,200
Sum it all together,
and you get --

582
00:32:07,200 --> 00:32:11,300
sorry, I'm calling this y now. y
equals the sum of the ui gi.

583
00:32:11,300 --> 00:32:14,540

584
00:32:14,540 --> 00:32:16,750
You see that?

585
00:32:16,750 --> 00:32:20,850
I hope I've beaten it into
the ground enough now.

586
00:32:20,850 --> 00:32:25,170
So it's a linear time-varying
machine.

587
00:32:25,170 --> 00:32:28,800
That is a realization of it,
if you've understood my

588
00:32:28,800 --> 00:32:30,590
description of it now.

589
00:32:30,590 --> 00:32:32,160
And now we can draw
the trellis of it.

590
00:32:32,160 --> 00:32:37,120

591
00:32:37,120 --> 00:32:44,080
That what can happen at time
1, we can either have u1.

592
00:32:44,080 --> 00:32:49,060
Now I can label my states
here, at this time u1.

593
00:32:49,060 --> 00:32:51,160
u1 can be either 0 or 1.

594
00:32:51,160 --> 00:32:52,410
This is u1.

595
00:32:52,410 --> 00:32:54,390

596
00:32:54,390 --> 00:33:02,810
At time 2, I have both u1
and u2 in my state.

597
00:33:02,810 --> 00:33:11,900
So this can either be 0, 0
or 0, 1, or 1, 0 or 1, 1.

598
00:33:11,900 --> 00:33:14,655
And obviously if I've already
determined u1 is 0 here, it's

599
00:33:14,655 --> 00:33:22,180
still going to be 0 at time 2.

600
00:33:22,180 --> 00:33:27,910
I label these with their
associated outputs.

601
00:33:27,910 --> 00:33:30,710
This is 1.

602
00:33:30,710 --> 00:33:33,160
This is also 1.

603
00:33:33,160 --> 00:33:35,660
This can turn it back to 0.

604
00:33:35,660 --> 00:33:36,760
And I just keep going.

605
00:33:36,760 --> 00:33:40,390
At the third time, I
have u1, u2, u3.

606
00:33:40,390 --> 00:33:44,060
I have eight states.

607
00:33:44,060 --> 00:33:46,020
At time 4, I come back.

608
00:33:46,020 --> 00:33:51,205
I only have u2, u3 at time
4, and so these merge.

609
00:33:51,205 --> 00:33:54,430

610
00:33:54,430 --> 00:33:56,614
So I get something --

611
00:33:56,614 --> 00:33:58,940
this doesn't merge like
that, though.

612
00:33:58,940 --> 00:34:01,710
It merges down here.

613
00:34:01,710 --> 00:34:03,840
0, 0, 0, 0, 0, 1.

614
00:34:03,840 --> 00:34:06,680
This merges to 0, 1 when
I drop the first one.

615
00:34:06,680 --> 00:34:09,510

616
00:34:09,510 --> 00:34:11,500
It's probably worth doing
this more carefully

617
00:34:11,500 --> 00:34:12,750
than I'm doing it.

618
00:34:12,750 --> 00:34:15,040

619
00:34:15,040 --> 00:34:20,330
0, 1 can go to 0, 1,
0, or 0, 1, 1.

620
00:34:20,330 --> 00:34:22,899
0, 1, 0 can either go to --

621
00:34:22,899 --> 00:34:30,150

622
00:34:30,150 --> 00:34:32,290
u2 equals 1.

623
00:34:32,290 --> 00:34:36,100
I guess these can't cross.

624
00:34:36,100 --> 00:34:36,420
u2 --

625
00:34:36,420 --> 00:34:37,670
AUDIENCE: [INAUDIBLE]

626
00:34:37,670 --> 00:34:39,639

627
00:34:39,639 --> 00:34:40,667
PROFESSOR: Excuse me?

628
00:34:40,667 --> 00:34:42,098
AUDIENCE: [INAUDIBLE]

629
00:34:42,098 --> 00:34:43,529
u3 and u4.

630
00:34:43,529 --> 00:34:46,510

631
00:34:46,510 --> 00:34:51,090
PROFESSOR: No, this
is state time.

632
00:34:51,090 --> 00:34:54,580
State time 1, 2, 3.

633
00:34:54,580 --> 00:34:57,030
u4 hasn't started yet.

634
00:34:57,030 --> 00:35:02,940
So I'm sorry, this
is 5 through 7.

635
00:35:02,940 --> 00:35:05,470
Is that right?

636
00:35:05,470 --> 00:35:09,080
It only lasts for
three intervals.

637
00:35:09,080 --> 00:35:10,330
So I only have u2, u3.

638
00:35:10,330 --> 00:35:16,030

639
00:35:16,030 --> 00:35:21,660
u1, u2 has to be 0, 0, 1, so
this would then go to 0, 1.

640
00:35:21,660 --> 00:35:23,100
0, 1.

641
00:35:23,100 --> 00:35:24,350
These seem to cross.

642
00:35:24,350 --> 00:35:27,220

643
00:35:27,220 --> 00:35:28,595
Yes, they do cross.

644
00:35:28,595 --> 00:35:36,040

645
00:35:36,040 --> 00:35:39,180
So let's see if I can actually
complete it.

646
00:35:39,180 --> 00:35:43,000
This could go to 1,
0, 0, or 1, 0, 1.

647
00:35:43,000 --> 00:35:46,540

648
00:35:46,540 --> 00:35:51,410
And then this one goes up
to either 0, 0 or 0, 1.

649
00:35:51,410 --> 00:35:56,990
This one can go to 1,
1, 0 or 1, 1, 1.

650
00:35:56,990 --> 00:35:58,640
And that can go like this.

651
00:35:58,640 --> 00:36:01,290

652
00:36:01,290 --> 00:36:04,520
So there's the trellis
for the first half.

653
00:36:04,520 --> 00:36:10,960
It's topologically the same, but
looks a little different

654
00:36:10,960 --> 00:36:12,270
from what I put up before.

655
00:36:12,270 --> 00:36:16,390
I interchanged these two with
these two, and this

656
00:36:16,390 --> 00:36:19,510
one with this one.

657
00:36:19,510 --> 00:36:26,110
But you can recover the trellis
that I had before.

658
00:36:26,110 --> 00:36:29,320
In any case, I claim when I've
labeled this with what the

659
00:36:29,320 --> 00:36:31,910
appropriate output is
at each time, I've

660
00:36:31,910 --> 00:36:33,160
got my minimal trellis.

661
00:36:33,160 --> 00:36:40,340

662
00:36:40,340 --> 00:36:45,420
And now we can make more
comments about

663
00:36:45,420 --> 00:36:47,910
how the trellis works.

664
00:36:47,910 --> 00:36:51,860
You see that whenever a
generator starts, we have

665
00:36:51,860 --> 00:36:55,610
what's called a divergence in
the trellis, a branching

666
00:36:55,610 --> 00:36:58,910
process, a branching out,
whereas whenever a generator

667
00:36:58,910 --> 00:37:03,690
ends, we have a convergence
in.

668
00:37:03,690 --> 00:37:08,180
So a starting time --

669
00:37:08,180 --> 00:37:13,230
if we have a generator starting,
then we get a branch

670
00:37:13,230 --> 00:37:16,626
that looks like this, like
here, and here, and here.

671
00:37:16,626 --> 00:37:19,660
When we have an ending time,
we have branches that look

672
00:37:19,660 --> 00:37:21,630
like this, like here.

673
00:37:21,630 --> 00:37:24,880
So this is a starting time,
starting time, starting time,

674
00:37:24,880 --> 00:37:26,130
and ending time.

675
00:37:26,130 --> 00:37:28,940

676
00:37:28,940 --> 00:37:36,230
So this tells you when things
open and close in the trellis.

677
00:37:36,230 --> 00:37:39,820
Now again, as I've said for
these more general trellises,

678
00:37:39,820 --> 00:37:43,170
down here we can have starting
and ending at the same time.

679
00:37:43,170 --> 00:37:46,460
And in that case,
we get a cross.

680
00:37:46,460 --> 00:37:50,400
We get a starting and ending
at the same time, we get

681
00:37:50,400 --> 00:37:51,650
something that looks
like this.

682
00:37:51,650 --> 00:37:55,630

683
00:37:55,630 --> 00:38:01,600
And if we get neither starting
nor ending, empty, then

684
00:38:01,600 --> 00:38:02,510
nothing happens.

685
00:38:02,510 --> 00:38:03,980
We just get --

686
00:38:03,980 --> 00:38:06,700
the trellis segment looks like
that, like this one here.

687
00:38:06,700 --> 00:38:09,900

688
00:38:09,900 --> 00:38:12,560
In this case we have a starting
time, an ending time

689
00:38:12,560 --> 00:38:13,680
in this trellis.

690
00:38:13,680 --> 00:38:14,970
Here we have nothing
happening.

691
00:38:14,970 --> 00:38:16,850
Here we have nothing
happening.

692
00:38:16,850 --> 00:38:19,850
So you just get an extension,
a parallel extension where

693
00:38:19,850 --> 00:38:21,850
nothing happens.

694
00:38:21,850 --> 00:38:27,210
So again, the starting and
ending times tell you what

695
00:38:27,210 --> 00:38:28,460
happens in the trellis.

696
00:38:28,460 --> 00:38:43,410

697
00:38:43,410 --> 00:38:49,490
There's one other thing that you
can read from the trellis,

698
00:38:49,490 --> 00:38:51,595
which is the size of
branch spaces.

699
00:38:51,595 --> 00:38:55,170

700
00:38:55,170 --> 00:38:59,250
And since as usual I'm running
a little later

701
00:38:59,250 --> 00:39:02,300
than I intend to --

702
00:39:02,300 --> 00:39:10,970
let me just state without proof
that there is a similar

703
00:39:10,970 --> 00:39:12,595
theorem for branch spaces.

704
00:39:12,595 --> 00:39:15,960

705
00:39:15,960 --> 00:39:17,210
What is a branch?

706
00:39:17,210 --> 00:39:27,660

707
00:39:27,660 --> 00:39:32,890
When we look in a trellis, a
branch is one of these things.

708
00:39:32,890 --> 00:39:35,520
That's a branch.

709
00:39:35,520 --> 00:39:38,940
What do we need to
define a branch?

710
00:39:38,940 --> 00:39:46,840
We have a initial state, the
code output at time k.

711
00:39:46,840 --> 00:39:52,290
We're calling that y time
k in the next state.

712
00:39:52,290 --> 00:39:54,570
So it's that triple.

713
00:39:54,570 --> 00:39:57,120
Again, this is linear
system theory.

714
00:39:57,120 --> 00:40:00,600
State, output, next state.

715
00:40:00,600 --> 00:40:02,995
Those are the three things
that define a branch.

716
00:40:02,995 --> 00:40:05,730

717
00:40:05,730 --> 00:40:08,260
This branch is state 1 0.

718
00:40:08,260 --> 00:40:14,810
Output whatever it is, y k,
and next state 1 0 0.

719
00:40:14,810 --> 00:40:17,500
And that differentiates it
from this down here.

720
00:40:17,500 --> 00:40:20,280

721
00:40:20,280 --> 00:40:24,120
If we define the branch
as this triple,

722
00:40:24,120 --> 00:40:26,610
then we can add triples.

723
00:40:26,610 --> 00:40:31,010
States form a vector space
over the ground field.

724
00:40:31,010 --> 00:40:34,500
These are simply symbols
over the ground field.

725
00:40:34,500 --> 00:40:38,190
These are vectors over
the ground field.

726
00:40:38,190 --> 00:40:40,360
So we can add them.

727
00:40:40,360 --> 00:40:51,850
And we find that it's closed,
and the set of all branches is

728
00:40:51,850 --> 00:40:53,100
a vector space.

729
00:40:53,100 --> 00:40:56,710

730
00:40:56,710 --> 00:41:00,100
It's fairly easy to show.

731
00:41:00,100 --> 00:41:05,000
Look at the notes, but it's
basically because these are

732
00:41:05,000 --> 00:41:08,690
all projected from code words
in the first place, and code

733
00:41:08,690 --> 00:41:12,750
words form a vector space, so
this is just a projection of

734
00:41:12,750 --> 00:41:16,910
the code words, a certain kind
of projection onto the state

735
00:41:16,910 --> 00:41:19,425
spaces and symbol spaces
and so forth.

736
00:41:19,425 --> 00:41:24,310
A projection of a vector space
is a vector space.

737
00:41:24,310 --> 00:41:25,560
Roughly the proof.

738
00:41:25,560 --> 00:41:28,400

739
00:41:28,400 --> 00:41:34,425
And what is the dimension
of the branch space?

740
00:41:34,425 --> 00:41:37,860

741
00:41:37,860 --> 00:41:39,710
Again, I'm just going to
give you the answer.

742
00:41:39,710 --> 00:41:40,430
Suppose we have a

743
00:41:40,430 --> 00:41:45,220
trellis-oriented generator matrix.

744
00:41:45,220 --> 00:41:48,380
Let's suppose we want to find
out the size of the branch

745
00:41:48,380 --> 00:41:51,450
space at this time.

746
00:41:51,450 --> 00:41:54,120
What doesn't enter into
the branch space?

747
00:41:54,120 --> 00:41:57,020
What doesn't make a difference
to the branches?

748
00:41:57,020 --> 00:42:01,630
All the pasts that arrive at the
same state at time k are

749
00:42:01,630 --> 00:42:03,450
equivalent.

750
00:42:03,450 --> 00:42:06,980
So this generator doesn't
enter in.

751
00:42:06,980 --> 00:42:11,800
All the futures that depart from
time k plus 1 don't enter

752
00:42:11,800 --> 00:42:14,760
in, so anything that's supported
by the future at

753
00:42:14,760 --> 00:42:20,420
time k plus 1 doesn't
enter in.

754
00:42:20,420 --> 00:42:24,120
And what's left is all of the
generators that are active at

755
00:42:24,120 --> 00:42:27,710
symbol time k.

756
00:42:27,710 --> 00:42:31,580
Notice the symbol times occur
between the state times.

757
00:42:31,580 --> 00:42:40,050
So certainly this
is an easy --

758
00:42:40,050 --> 00:42:42,600

759
00:42:42,600 --> 00:42:45,120
this is one of those results
that's easier to understand

760
00:42:45,120 --> 00:42:50,610
than to prove, and I'll refer
you to the notes to prove.

761
00:42:50,610 --> 00:42:54,690
The dimension of the branch
space is simply the number of

762
00:42:54,690 --> 00:42:58,540
generators that are active
at symbol time k.

763
00:42:58,540 --> 00:43:09,971

764
00:43:09,971 --> 00:43:14,030
Because branches are
synchronized with the symbol

765
00:43:14,030 --> 00:43:15,600
times, not with the
state times.

766
00:43:15,600 --> 00:43:18,190

767
00:43:18,190 --> 00:43:20,450
So how does that come
out over here?

768
00:43:20,450 --> 00:43:24,140
There's the dimension of the
branch space is 1 here.

769
00:43:24,140 --> 00:43:26,000
It's 2 here.

770
00:43:26,000 --> 00:43:27,930
It's 3 here.

771
00:43:27,930 --> 00:43:29,810
It's 4 here.

772
00:43:29,810 --> 00:43:32,340
I'm sorry, it's 3 again here.

773
00:43:32,340 --> 00:43:34,180
This one hasn't started yet.

774
00:43:34,180 --> 00:43:37,390
It's 3 again here.

775
00:43:37,390 --> 00:43:45,010
It's 3 again here,
2 here, 1 here.

776
00:43:45,010 --> 00:43:50,910
That means that the size of the
branch space is 2, 4, 8,

777
00:43:50,910 --> 00:43:55,685
8, 8, 8, 4, 2.

778
00:43:55,685 --> 00:43:58,290
Is that right?

779
00:43:58,290 --> 00:43:59,530
There are two branches here.

780
00:43:59,530 --> 00:44:00,880
There are four branches here.

781
00:44:00,880 --> 00:44:02,240
There are eight branches here.

782
00:44:02,240 --> 00:44:04,230
There are still eight
branches here.

783
00:44:04,230 --> 00:44:05,930
And it's symmetric on
the other side.

784
00:44:05,930 --> 00:44:10,400
So it looks like we got the
right answer there, and in

785
00:44:10,400 --> 00:44:13,740
fact it's a general rule.

786
00:44:13,740 --> 00:44:14,510
So that's great.

787
00:44:14,510 --> 00:44:15,540
That's another property of

788
00:44:15,540 --> 00:44:17,270
trellis-oriented generator matrix.

789
00:44:17,270 --> 00:44:20,070
We can again, by inspection, get
the dimensions of all the

790
00:44:20,070 --> 00:44:22,480
branch space sizes.

791
00:44:22,480 --> 00:44:25,990
Are the branch sizes
important?

792
00:44:25,990 --> 00:44:28,490
Yes.

793
00:44:28,490 --> 00:44:31,520
In fact, they're more important
from a complexity

794
00:44:31,520 --> 00:44:34,920
point of view than the
state space sizes.

795
00:44:34,920 --> 00:44:38,020
95% of the literature has
to do with state spaces.

796
00:44:38,020 --> 00:44:41,480
State space is a little bit more
elegant mathematically.

797
00:44:41,480 --> 00:44:44,010

798
00:44:44,010 --> 00:44:46,610
For instance, you don't have the
same kind of dual branch

799
00:44:46,610 --> 00:44:50,950
space theorem as you have a
dual state space theorem.

800
00:44:50,950 --> 00:44:54,110
But actually, when you're asking
what's going on in the

801
00:44:54,110 --> 00:44:55,880
Viterbi algorithm, what
does the Viterbi

802
00:44:55,880 --> 00:44:57,680
algorithm have to do?

803
00:44:57,680 --> 00:45:01,070
At a minimum, it has to do one
thing for each branch.

804
00:45:01,070 --> 00:45:04,490
It has to perform a metric
extension, a metric addition

805
00:45:04,490 --> 00:45:07,150
computation at least once
for each branch.

806
00:45:07,150 --> 00:45:11,980
So the Viterbi algorithm
complexity is better estimated

807
00:45:11,980 --> 00:45:15,910
by the size of the branch space
than the size of the

808
00:45:15,910 --> 00:45:18,860
state space.

809
00:45:18,860 --> 00:45:21,720
To progress at this point, a
Viterbi algorithm has to do at

810
00:45:21,720 --> 00:45:22,690
least eight things.

811
00:45:22,690 --> 00:45:25,415
To progress again, it has to
do at least eight things.

812
00:45:25,415 --> 00:45:29,050

813
00:45:29,050 --> 00:45:33,570
So it's more relevant from the
point of view of complexity.

814
00:45:33,570 --> 00:45:37,440
Furthermore, you can play games
with state space size.

815
00:45:37,440 --> 00:45:40,920
And you've seen me play games
with state space size.

816
00:45:40,920 --> 00:45:43,385
For instance, if I draw this
as a two-section trellis --

817
00:45:43,385 --> 00:45:46,560

818
00:45:46,560 --> 00:45:49,950
the first picture I put up was
only a four-state trellis, and

819
00:45:49,950 --> 00:45:51,200
it looked like this.

820
00:45:51,200 --> 00:45:53,750

821
00:45:53,750 --> 00:45:55,630
I went immediately
to time 2, and I

822
00:45:55,630 --> 00:45:57,890
aggregated these two things.

823
00:45:57,890 --> 00:46:02,075
0, 0 and 1, 1 were up
here, and 0, 1 and

824
00:46:02,075 --> 00:46:03,890
1, 0 were down here.

825
00:46:03,890 --> 00:46:05,200
And then I had a nice --

826
00:46:05,200 --> 00:46:08,510
I just drew these four
states over here.

827
00:46:08,510 --> 00:46:12,080
And if I do it like that, then
I get a much nicer picture.

828
00:46:12,080 --> 00:46:13,330
It looks like this.

829
00:46:13,330 --> 00:46:18,700

830
00:46:18,700 --> 00:46:22,485
It looks only like a
four-state trellis.

831
00:46:22,485 --> 00:46:24,730
Now, is this still a
legitimate trellis?

832
00:46:24,730 --> 00:46:28,270
Yeah, it's still a legitimate
trellis.

833
00:46:28,270 --> 00:46:31,240
If I do a Viterbi algorithm
decoding of this trellis, is

834
00:46:31,240 --> 00:46:33,420
it any different from this?

835
00:46:33,420 --> 00:46:35,330
Well, in detail it is a
little bit different.

836
00:46:35,330 --> 00:46:38,420
You do the additions and the
comparisons and the selection.

837
00:46:38,420 --> 00:46:42,625
So you only do selections
every this often.

838
00:46:42,625 --> 00:46:46,000

839
00:46:46,000 --> 00:46:48,730
And if you think about it,
it's really legitimate to

840
00:46:48,730 --> 00:46:49,970
think of this --

841
00:46:49,970 --> 00:46:53,480
if you think exactly how the
Viterbi algorithm works,

842
00:46:53,480 --> 00:46:54,290
really what's it doing?

843
00:46:54,290 --> 00:46:55,870
It's not making any
selection here.

844
00:46:55,870 --> 00:46:58,330
It's just adding an increment
there, and then adding another

845
00:46:58,330 --> 00:47:00,830
increment, and it's not
making any selection

846
00:47:00,830 --> 00:47:02,570
until it gets here.

847
00:47:02,570 --> 00:47:06,360
So it's perfectly legitimate to
think of this as basically

848
00:47:06,360 --> 00:47:07,980
being a four-state algorithm.

849
00:47:07,980 --> 00:47:11,470
It really isn't doing any
work at this stage.

850
00:47:11,470 --> 00:47:15,430
All the work occurs at this
stage if you think about the

851
00:47:15,430 --> 00:47:18,310
operation of the Viterbi
algorithm.

852
00:47:18,310 --> 00:47:21,520
So this is a quite legitimate
representation.

853
00:47:21,520 --> 00:47:22,450
And so what are we
going to say?

854
00:47:22,450 --> 00:47:25,970
Is the state complexity of this
code, is it four states

855
00:47:25,970 --> 00:47:28,140
or is it eight states?

856
00:47:28,140 --> 00:47:29,840
Well, to some degree it's just
a matter of definition.

857
00:47:29,840 --> 00:47:32,400

858
00:47:32,400 --> 00:47:34,630
How do you choose
to define it?

859
00:47:34,630 --> 00:47:38,900
If you want something more
fundamental, it's better to go

860
00:47:38,900 --> 00:47:41,580
to branch complexity.

861
00:47:41,580 --> 00:47:43,590
What's the branch complexity
here for the

862
00:47:43,590 --> 00:47:45,385
fully displayed trellis?

863
00:47:45,385 --> 00:47:47,070
It's eight.

864
00:47:47,070 --> 00:47:50,230
By branch complexity, I
mean the maximum size

865
00:47:50,230 --> 00:47:52,530
of any branch space.

866
00:47:52,530 --> 00:47:56,580
What's the branch
complexity here?

867
00:47:56,580 --> 00:47:57,215
It's eight.

868
00:47:57,215 --> 00:47:59,010
We've still got eight.

869
00:47:59,010 --> 00:48:01,790
Ultimately we've got to compare
these eight things and

870
00:48:01,790 --> 00:48:06,280
reduce them to four, whether
we do it here or here.

871
00:48:06,280 --> 00:48:11,020
I gave you another trellis which
was only a two-section

872
00:48:11,020 --> 00:48:18,480
trellis, where I just showed
the four central states.

873
00:48:18,480 --> 00:48:21,120
And we actually have two
branches going there, two

874
00:48:21,120 --> 00:48:24,300
branches going there, two
branches going there, and two

875
00:48:24,300 --> 00:48:25,830
branches going there.

876
00:48:25,830 --> 00:48:28,630
What's the branch complexity
of that trellis?

877
00:48:28,630 --> 00:48:29,755
Still eight.

878
00:48:29,755 --> 00:48:32,670
There are eight ways to get
from the origin to here.

879
00:48:32,670 --> 00:48:36,800

880
00:48:36,800 --> 00:48:41,110
If you go back to how we do this
theorem, if you believe

881
00:48:41,110 --> 00:48:47,860
this theorem, what happens now
if we say arbitrarily, OK,

882
00:48:47,860 --> 00:48:50,260
we're going to define the state
spaces as we do in a

883
00:48:50,260 --> 00:48:52,520
rate 1/2 convolutional code.

884
00:48:52,520 --> 00:48:54,610
We're just going to define
the state times to

885
00:48:54,610 --> 00:48:55,860
be every two times.

886
00:48:55,860 --> 00:49:00,980

887
00:49:00,980 --> 00:49:05,070
Then the dimension of the state
spaces, just at those

888
00:49:05,070 --> 00:49:09,100
times we've defined,
is 0, 2, 2, 2, 0.

889
00:49:09,100 --> 00:49:10,370
They don't change.

890
00:49:10,370 --> 00:49:15,120
We just have fewer of
them by our choice.

891
00:49:15,120 --> 00:49:17,610
What happens to the dimensions
of the branch spaces?

892
00:49:17,610 --> 00:49:21,340
Again, if the theorem is
correct, we should just count

893
00:49:21,340 --> 00:49:24,830
the number of active generators
at each now of

894
00:49:24,830 --> 00:49:28,580
these four bi-symbol times.

895
00:49:28,580 --> 00:49:34,720
So it's 2, 3, 3, 2.

896
00:49:34,720 --> 00:49:35,450
Is that right?

897
00:49:35,450 --> 00:49:39,920
That is the branch complexity
of this trellis down here.

898
00:49:39,920 --> 00:49:45,070
It's 4 in the initial interval,
and 8 over here.

899
00:49:45,070 --> 00:49:47,380
So again it's correct.

900
00:49:47,380 --> 00:49:50,480
Suppose we go to that so-called
two-section trellis.

901
00:49:50,480 --> 00:49:55,140
We just say there's a first
half and a second half.

902
00:49:55,140 --> 00:49:59,380
Now the states is going to
be 0 2 0, and the branch

903
00:49:59,380 --> 00:50:02,160
complexity is going to be --

904
00:50:02,160 --> 00:50:05,300
there are three active
generators in the first half,

905
00:50:05,300 --> 00:50:07,210
and three active generators
in the second half.

906
00:50:07,210 --> 00:50:11,300

907
00:50:11,300 --> 00:50:13,530
So by playing this kind of
game, which is called

908
00:50:13,530 --> 00:50:20,080
sectionalization, we can make
the state complexity sometimes

909
00:50:20,080 --> 00:50:20,880
appear simpler.

910
00:50:20,880 --> 00:50:23,480
There are limits to how much
simpler we can make it.

911
00:50:23,480 --> 00:50:24,470
Well, there actually aren't.

912
00:50:24,470 --> 00:50:29,970
Suppose we took the whole eight
symbols as one time.

913
00:50:29,970 --> 00:50:34,410
We'd have 0 dimensional state
space at the beginning, and 0

914
00:50:34,410 --> 00:50:35,320
dimensional at the end.

915
00:50:35,320 --> 00:50:37,170
What does that trellis
look like?

916
00:50:37,170 --> 00:50:40,670
It looks like 16 parallel
transitions from

917
00:50:40,670 --> 00:50:41,700
beginning to end.

918
00:50:41,700 --> 00:50:43,995
That's a legitimate
trellis, right?

919
00:50:43,995 --> 00:50:46,350
We should have one state at the
beginning and one state at

920
00:50:46,350 --> 00:50:49,180
the end, and 16 transitions.

921
00:50:49,180 --> 00:50:51,480
Is that what we get if
we went through this?

922
00:50:51,480 --> 00:50:52,790
Yeah.

923
00:50:52,790 --> 00:50:54,120
We have 0 0.

924
00:50:54,120 --> 00:50:55,590
And what's the branch
complexity?

925
00:50:55,590 --> 00:50:57,340
It's 4.

926
00:50:57,340 --> 00:50:59,610
The dimension of the branch
space is 4 if we took the

927
00:50:59,610 --> 00:51:02,380
whole thing.

928
00:51:02,380 --> 00:51:06,760
So we can mask state complexity
by picking our

929
00:51:06,760 --> 00:51:12,080
state spaces at appropriate
times, but you can't ever mask

930
00:51:12,080 --> 00:51:14,060
branch complexity.

931
00:51:14,060 --> 00:51:18,740
And again, it's a very
intuitive proof here.

932
00:51:18,740 --> 00:51:21,530
Let's take this time here, where
there are three active

933
00:51:21,530 --> 00:51:22,780
generators.

934
00:51:22,780 --> 00:51:24,480

935
00:51:24,480 --> 00:51:27,765
By expanding that time, can we
ever get fewer than three

936
00:51:27,765 --> 00:51:29,145
active generators?

937
00:51:29,145 --> 00:51:34,660
No, any interval that includes
this particular time is going

938
00:51:34,660 --> 00:51:38,090
to have three active
generators in it.

939
00:51:38,090 --> 00:51:41,340
So branch complexity cannot
be reduced by this kind of

940
00:51:41,340 --> 00:51:42,560
sectionalization game.

941
00:51:42,560 --> 00:51:45,200
State complexity can be
apparently reduced.

942
00:51:45,200 --> 00:51:47,020
It isn't really.

943
00:51:47,020 --> 00:51:48,680
But branch complexity cannot.

944
00:51:48,680 --> 00:51:49,930
AUDIENCE: [INAUDIBLE]

945
00:51:49,930 --> 00:51:52,730

946
00:51:52,730 --> 00:51:54,440
PROFESSOR: And if you go too
far, it might increase.

947
00:51:54,440 --> 00:51:57,800

948
00:51:57,800 --> 00:52:02,170
So at the very end of the
chapter, I talk about

949
00:52:02,170 --> 00:52:05,110
sectionalization.

950
00:52:05,110 --> 00:52:07,580
It's not a very important
issue.

951
00:52:07,580 --> 00:52:11,860
There's a very easy heuristic
for how you should

952
00:52:11,860 --> 00:52:14,720
sectionalize, which is basically
you should make the

953
00:52:14,720 --> 00:52:17,970
sections as big as you can
without increasing branch

954
00:52:17,970 --> 00:52:19,790
complexity.

955
00:52:19,790 --> 00:52:23,720
So in this case, the heuristic
says we know we're going to

956
00:52:23,720 --> 00:52:27,330
have to have branch
complexity of 3.

957
00:52:27,330 --> 00:52:28,620
But without increasing --

958
00:52:28,620 --> 00:52:32,660
if I just make this one
partition at the center, I

959
00:52:32,660 --> 00:52:36,360
just take these two sections,
first half, second half.

960
00:52:36,360 --> 00:52:39,980
Then I have an increased
branch complexity.

961
00:52:39,980 --> 00:52:42,110
So that's a good
sectionalization.

962
00:52:42,110 --> 00:52:44,930
This will probably lead to the
simplest Viterbi algorithm and

963
00:52:44,930 --> 00:52:48,480
the simplest-looking trellis
representation of the code.

964
00:52:48,480 --> 00:52:52,290

965
00:52:52,290 --> 00:52:55,380
So that's the character of the
sectionalization algorithm.

966
00:52:55,380 --> 00:52:56,700
You can read about it.

967
00:52:56,700 --> 00:53:02,030
It usually winds up with
a sensible time-varying

968
00:53:02,030 --> 00:53:05,980
sectionalization, and it's
worth five minutes of

969
00:53:05,980 --> 00:53:06,490
discussion.

970
00:53:06,490 --> 00:53:06,860
Yes.

971
00:53:06,860 --> 00:53:09,691
AUDIENCE: Is it like a monotonic
kind of thing, like

972
00:53:09,691 --> 00:53:13,400
if you make sections bigger,
then you'll only either

973
00:53:13,400 --> 00:53:15,860
increase or keep the same
branch complexity?

974
00:53:15,860 --> 00:53:18,380
PROFESSOR: Yeah, that was my
basic argument, that if I have

975
00:53:18,380 --> 00:53:21,560
any section that includes this
time, and I start making it

976
00:53:21,560 --> 00:53:25,240
bigger, the dimension
can only increase.

977
00:53:25,240 --> 00:53:28,960
So the algorithm is to keep
increasing it until I get to

978
00:53:28,960 --> 00:53:33,050
some place where I might have to
include another generator.

979
00:53:33,050 --> 00:53:36,000
For instance here, if I'm taking
this time, I don't want

980
00:53:36,000 --> 00:53:37,800
to push it out over here,
because then I'll get the

981
00:53:37,800 --> 00:53:39,710
fourth generator in there.

982
00:53:39,710 --> 00:53:47,850
So any section that includes
time 3 should not be extended

983
00:53:47,850 --> 00:53:50,470
in this direction, because we'll
get another generator.

984
00:53:50,470 --> 00:53:54,150
But no problem with extending
in this direction.

985
00:53:54,150 --> 00:53:58,260
So that's the basic heuristic.

986
00:53:58,260 --> 00:54:00,070
It's easy.

987
00:54:00,070 --> 00:54:03,130
And it's not very productive.

988
00:54:03,130 --> 00:54:06,120
It doesn't really change the
complexity of the Viterbi

989
00:54:06,120 --> 00:54:08,610
algorithm as a representation
of code.

990
00:54:08,610 --> 00:54:10,870
So these are just a couple
of arguments to say

991
00:54:10,870 --> 00:54:12,650
really we might --

992
00:54:12,650 --> 00:54:14,720
the branch complexity
is more fundamental.

993
00:54:14,720 --> 00:54:17,600
We want to focus on branch
complexity a little bit more.

994
00:54:17,600 --> 00:54:28,750
But of course, if you have a
fully displayed trellis, the

995
00:54:28,750 --> 00:54:32,230
maximum state space dimension is
either going to be equal to

996
00:54:32,230 --> 00:54:35,760
the maximum branch space
dimension or one less than it.

997
00:54:35,760 --> 00:54:40,380
Because in these binary
trellises, we get at most a

998
00:54:40,380 --> 00:54:42,570
binary branch at each time.

999
00:54:42,570 --> 00:54:47,030
So any branch complexity is
at most twice that of the

1000
00:54:47,030 --> 00:54:50,630
adjacent state space.

1001
00:54:50,630 --> 00:54:53,640
So they're not going to
differ by very much.

1002
00:54:53,640 --> 00:54:58,440
So state complexity is a good
proxy for branch complexity in

1003
00:54:58,440 --> 00:55:02,040
a fully displayed or
unsectionalized trellis.

1004
00:55:02,040 --> 00:55:10,070

1005
00:55:10,070 --> 00:55:13,420
While I'm on this subject,
there's another interesting

1006
00:55:13,420 --> 00:55:23,555
direction we can go, which is
average dimension bounds.

1007
00:55:23,555 --> 00:55:34,080

1008
00:55:34,080 --> 00:55:37,910
Again, think of our
realization here.

1009
00:55:37,910 --> 00:55:43,850

1010
00:55:43,850 --> 00:55:45,230
What does it contribute?

1011
00:55:45,230 --> 00:55:51,520
What does a single generator
contribute overall to state

1012
00:55:51,520 --> 00:55:55,430
and branch space complexity?

1013
00:55:55,430 --> 00:56:06,390
A single generator Gj of span
S, which of course has to be

1014
00:56:06,390 --> 00:56:08,235
greater than or equal to
the minimum distance

1015
00:56:08,235 --> 00:56:09,370
to the code, right?

1016
00:56:09,370 --> 00:56:11,335
The span can't be less
of a generator.

1017
00:56:11,335 --> 00:56:14,110
It can't be less than
the minimum nonzero

1018
00:56:14,110 --> 00:56:17,180
weight of any code word.

1019
00:56:17,180 --> 00:56:25,600
Span S contributes overall
to all the state space

1020
00:56:25,600 --> 00:56:26,320
dimensions.

1021
00:56:26,320 --> 00:56:33,480
It contributes S minus 1 state
space dimensions, because it's

1022
00:56:33,480 --> 00:56:38,470
active for S minus
1 state times.

1023
00:56:38,470 --> 00:56:42,360

1024
00:56:42,360 --> 00:56:47,200
And it contributes S branch
dimensions because it's active

1025
00:56:47,200 --> 00:56:51,545
for S symbols.

1026
00:56:51,545 --> 00:56:54,240

1027
00:56:54,240 --> 00:56:58,530
If I look at it spread out
across time, this generator of

1028
00:56:58,530 --> 00:57:05,100
span 4, it contributed three
times to a state space

1029
00:57:05,100 --> 00:57:06,800
dimension, and it
contributed four

1030
00:57:06,800 --> 00:57:09,415
times to a branch dimension.

1031
00:57:09,415 --> 00:57:13,510

1032
00:57:13,510 --> 00:57:25,490
So total state dimension has to
be greater than or equal to

1033
00:57:25,490 --> 00:57:28,360
k times d minus 1.

1034
00:57:28,360 --> 00:57:32,300
And the total branch dimension,
just summing up

1035
00:57:32,300 --> 00:57:36,110
across the trellis, is greater
than or equal to k

1036
00:57:36,110 --> 00:57:37,650
generators times d.

1037
00:57:37,650 --> 00:57:41,960

1038
00:57:41,960 --> 00:57:43,750
Now how many different
nontrivial

1039
00:57:43,750 --> 00:57:47,000
state spaces are there?

1040
00:57:47,000 --> 00:57:50,300
There are n minus 1 nontrivial
state times.

1041
00:57:50,300 --> 00:57:52,420
Excuse me.

1042
00:57:52,420 --> 00:57:55,730
For instance, in this code
of length 8, there are 7

1043
00:57:55,730 --> 00:57:57,855
nontrivial state spaces.

1044
00:57:57,855 --> 00:58:00,830

1045
00:58:00,830 --> 00:58:08,530
So the average state dimension
has to be greater than or

1046
00:58:08,530 --> 00:58:18,440
equal to k d minus
1 over n minus 1.

1047
00:58:18,440 --> 00:58:25,230
And the average branch dimension
has got to be

1048
00:58:25,230 --> 00:58:28,820
greater than or equal to k d
over the n symbol times.

1049
00:58:28,820 --> 00:58:35,260

1050
00:58:35,260 --> 00:58:40,350
So actually we might remember
that quantity.

1051
00:58:40,350 --> 00:58:42,700
That's what we called the coding
gain of the code, the

1052
00:58:42,700 --> 00:58:44,280
nominal coding gain on
the additive white

1053
00:58:44,280 --> 00:58:46,700
Gaussian noise channel.

1054
00:58:46,700 --> 00:58:50,030
Well, if the average dimension
is lower bounded by something,

1055
00:58:50,030 --> 00:58:53,290
then certainly the maximum state
space dimension is lower

1056
00:58:53,290 --> 00:58:54,540
bounded by that.

1057
00:58:54,540 --> 00:59:03,280

1058
00:59:03,280 --> 00:59:05,270
Max has to be at least as
great as the average.

1059
00:59:05,270 --> 00:59:09,510

1060
00:59:09,510 --> 00:59:12,580
So if these are what are called
the average dimension

1061
00:59:12,580 --> 00:59:20,050
bounds on the maximum state
space size, and there are some

1062
00:59:20,050 --> 00:59:23,700
interesting implications.

1063
00:59:23,700 --> 00:59:26,480
Again, this expression for
branch dimension is nicer

1064
00:59:26,480 --> 00:59:28,440
here, because it's
this k d over n

1065
00:59:28,440 --> 00:59:30,090
nominal coding gain thing.

1066
00:59:30,090 --> 00:59:34,606
It's in terms of the basic n
k d parameters of the code.

1067
00:59:34,606 --> 00:59:36,390
And it says what?

1068
00:59:36,390 --> 00:59:44,020
It says if you want a nominal
coding gain of 2, it implies

1069
00:59:44,020 --> 00:59:52,560
that the max branch dimension is
greater than or equal to 2.

1070
00:59:52,560 --> 00:59:58,040
Or the max size is greater than
or equal to 2 to the 2,

1071
00:59:58,040 --> 01:00:02,160
or you need a branch space of at
least size 4, or dimension

1072
01:00:02,160 --> 01:00:09,540
2 to get a 3 dB nominal
coding gain.

1073
01:00:09,540 --> 01:00:12,245
Similarly, if you want
a 6 dB gain --

1074
01:00:12,245 --> 01:00:15,850

1075
01:00:15,850 --> 01:00:18,382
let's get right down to dB.

1076
01:00:18,382 --> 01:00:22,626
It says you're going to need a
branch space size greater than

1077
01:00:22,626 --> 01:00:28,320
or equal to 4, or at least
a 16-state trellis.

1078
01:00:28,320 --> 01:00:30,670
So we know if we want a 6 dB
coding gain, we're going to

1079
01:00:30,670 --> 01:00:33,730
need at least a 16-state
trellis,

1080
01:00:33,730 --> 01:00:35,170
or a 16-branch trellis.

1081
01:00:35,170 --> 01:00:37,710
It might be an eight-state
trellis.

1082
01:00:37,710 --> 01:00:41,840
Well, these are not tight, but
they're quite indicative in

1083
01:00:41,840 --> 01:00:47,510
fact of what we see in both the
tables for block codes and

1084
01:00:47,510 --> 01:00:50,685
for convolutional codes.

1085
01:00:50,685 --> 01:00:53,300
These same bounds hold for
convolutional codes, by the

1086
01:00:53,300 --> 01:00:55,970
way, just average over
infinite time.

1087
01:00:55,970 --> 01:00:58,540

1088
01:00:58,540 --> 01:01:01,870
But they're still
perfectly good.

1089
01:01:01,870 --> 01:01:06,020
So they tell us that
in order to get --

1090
01:01:06,020 --> 01:01:10,150
if we want the nominal coding
gain to keep going up to 8, to

1091
01:01:10,150 --> 01:01:16,290
16, to infinity, it says we're
going to need infinite trellis

1092
01:01:16,290 --> 01:01:18,390
complexity to get infinite
coding gain.

1093
01:01:18,390 --> 01:01:23,740

1094
01:01:23,740 --> 01:01:27,640
Let's do some little
asymptotics, be a little bit

1095
01:01:27,640 --> 01:01:30,120
more refined about this.

1096
01:01:30,120 --> 01:01:36,280

1097
01:01:36,280 --> 01:01:54,020
A sequence of codes Cn of length
n going to infinity is

1098
01:01:54,020 --> 01:02:03,110
called good if both the rate k
over n is bounded away from 0

1099
01:02:03,110 --> 01:02:09,540
as n goes to infinity, and the
distance d over n is bounded

1100
01:02:09,540 --> 01:02:11,690
away from 0.

1101
01:02:11,690 --> 01:02:15,980
The rate and the relative
distance are both bounded away

1102
01:02:15,980 --> 01:02:18,810
from 0 as n goes to infinity.

1103
01:02:18,810 --> 01:02:19,450
Is that clear?

1104
01:02:19,450 --> 01:02:23,510
In other words, we want the
dimension and the minimum

1105
01:02:23,510 --> 01:02:27,830
distance both to increase
linearly with n in a good

1106
01:02:27,830 --> 01:02:28,830
sequence of codes.

1107
01:02:28,830 --> 01:02:32,420
This is a classical algebraic
definition, and it's easy to

1108
01:02:32,420 --> 01:02:36,660
prove there exists good
sequences of codes.

1109
01:02:36,660 --> 01:02:40,350
You just pick a code at random,
rate 1/2 of binary

1110
01:02:40,350 --> 01:02:42,110
linear code.

1111
01:02:42,110 --> 01:02:46,320
It on average will have
a relative minimum

1112
01:02:46,320 --> 01:02:48,750
distance about 11%.

1113
01:02:48,750 --> 01:02:50,860
This is just basic information
theory.

1114
01:02:50,860 --> 01:02:53,650

1115
01:02:53,650 --> 01:02:57,850
So there certainly exists
sequences of good codes, and

1116
01:02:57,850 --> 01:03:02,130
this is what most of coding
theory was occupied with

1117
01:03:02,130 --> 01:03:05,380
constructing for a
very long time.

1118
01:03:05,380 --> 01:03:07,790
What happens if you have a
good sequence of codes?

1119
01:03:07,790 --> 01:03:10,990

1120
01:03:10,990 --> 01:03:17,200
We have this nominal coding
gain, which is equal to kd

1121
01:03:17,200 --> 01:03:24,975
over n, which is equal to n
times k over n times d over n.

1122
01:03:24,975 --> 01:03:29,210
If both of these are bounded
away from zero, then the

1123
01:03:29,210 --> 01:03:43,240
nominal coding gain has to
increase linearly with n.

1124
01:03:43,240 --> 01:03:47,460
That means that the average,
or the maximum branch

1125
01:03:47,460 --> 01:03:51,420
dimension, in a minimal trellis
representation for

1126
01:03:51,420 --> 01:03:55,100
your code has to increase at
least linearly with n, which

1127
01:03:55,100 --> 01:04:00,820
means that the actual branch
complexity, the size of B, has

1128
01:04:00,820 --> 01:04:08,150
to increase as --

1129
01:04:08,150 --> 01:04:12,480
it goes as 2 to the nominal
coding gain, which is in other

1130
01:04:12,480 --> 01:04:14,350
words exponentially with n.

1131
01:04:14,350 --> 01:04:23,350

1132
01:04:23,350 --> 01:04:28,570
So basically what this says is
that if your objective is to

1133
01:04:28,570 --> 01:04:31,770
get a good sequence of codes,
if this is the way you think

1134
01:04:31,770 --> 01:04:37,780
you're going to get to channel
capacity, then sure enough,

1135
01:04:37,780 --> 01:04:41,050
your nominal coding gain
will go up to infinity

1136
01:04:41,050 --> 01:04:43,010
linearly with n.

1137
01:04:43,010 --> 01:04:45,170
But how are you going
to decode it?

1138
01:04:45,170 --> 01:04:48,370
Our first method was simply
maximum likelihood decoding.

1139
01:04:48,370 --> 01:04:51,680
The complexity of that,
computing the distance to

1140
01:04:51,680 --> 01:04:54,550
every code word, that
certainly goes up

1141
01:04:54,550 --> 01:04:58,180
exponentially with n, exhaustive
decoding, comparing

1142
01:04:58,180 --> 01:04:59,570
with every code word.

1143
01:04:59,570 --> 01:05:02,930
But now we have a new method
which is, we hope, simpler,

1144
01:05:02,930 --> 01:05:04,990
which is trellis decoding.

1145
01:05:04,990 --> 01:05:08,470
But we find out, unfortunately,
the complexity

1146
01:05:08,470 --> 01:05:10,110
of trellis decoding
is going to go up

1147
01:05:10,110 --> 01:05:13,170
exponentially with n as well.

1148
01:05:13,170 --> 01:05:20,890
So the good news was that with
the Viterbi algorithm and a

1149
01:05:20,890 --> 01:05:25,390
minimal trellis, we can get
a simpler optimum maximum

1150
01:05:25,390 --> 01:05:28,160
likelihood decoding algorithm
for block code, simpler than

1151
01:05:28,160 --> 01:05:30,070
exhaustive decoding.

1152
01:05:30,070 --> 01:05:34,420
The bad news is that under
this assumption, the

1153
01:05:34,420 --> 01:05:36,800
complexity of that algorithm
is still going to go up

1154
01:05:36,800 --> 01:05:38,140
exponentially with n.

1155
01:05:38,140 --> 01:05:41,070
Maybe just a lower exponent,
that's all.

1156
01:05:41,070 --> 01:05:44,790
So we haven't really solved our
basic problem, which is

1157
01:05:44,790 --> 01:05:48,300
exponential decoding complexity,
by going to

1158
01:05:48,300 --> 01:05:49,550
trellis decoding.

1159
01:05:49,550 --> 01:05:52,640

1160
01:05:52,640 --> 01:05:59,376
We have, however, another
way to go.

1161
01:05:59,376 --> 01:06:03,820
Do we really need the coding
gain to go to infinity, the

1162
01:06:03,820 --> 01:06:07,170
nominal coding gain
to go to infinity?

1163
01:06:07,170 --> 01:06:10,760
If we go back and remember the
name of the game, the playing

1164
01:06:10,760 --> 01:06:12,820
field that we're on, at least in
the additive white Gaussian

1165
01:06:12,820 --> 01:06:17,970
noise channel, we found the
distance between uncoded and

1166
01:06:17,970 --> 01:06:23,010
the Shannon limit was some
finite number, something like

1167
01:06:23,010 --> 01:06:26,340
9 dB at a 10 to the minus 5
error probability, larger at

1168
01:06:26,340 --> 01:06:27,460
lower error probability.

1169
01:06:27,460 --> 01:06:30,990
So that's the maximum
effective coding

1170
01:06:30,990 --> 01:06:34,440
gain we can ever get.

1171
01:06:34,440 --> 01:06:39,160
So maybe we only need a finite
nominal coding gain.

1172
01:06:39,160 --> 01:06:41,860
In practice, this means maybe
we don't need a minimum

1173
01:06:41,860 --> 01:06:44,580
distance that goes up
linearly with n.

1174
01:06:44,580 --> 01:06:48,390
Maybe we can have a very
long code with

1175
01:06:48,390 --> 01:06:51,220
a low minimum distance.

1176
01:06:51,220 --> 01:06:53,310
And that would be another
way to crack

1177
01:06:53,310 --> 01:06:55,660
the complexity problem.

1178
01:06:55,660 --> 01:06:58,070
In fact, some of the
capacity-approaching codes

1179
01:06:58,070 --> 01:07:00,220
that we're going to talk about,
specifically turbo

1180
01:07:00,220 --> 01:07:03,030
codes, tend to have bad
minimum distances.

1181
01:07:03,030 --> 01:07:06,260
You have a turbo code that's
thousands of bits long, and

1182
01:07:06,260 --> 01:07:09,190
its minimum distance will be
something like 20 or 30.

1183
01:07:09,190 --> 01:07:12,330

1184
01:07:12,330 --> 01:07:17,790
And yet it signals within 1
dB of the Shannon limit.

1185
01:07:17,790 --> 01:07:20,935
It gives you low error
probabilities within 1 dB of

1186
01:07:20,935 --> 01:07:21,920
the Shannon limit.

1187
01:07:21,920 --> 01:07:27,490
So maybe there's another way to
go, at least if we're only

1188
01:07:27,490 --> 01:07:31,360
interested in a certain
error probability.

1189
01:07:31,360 --> 01:07:32,900
Maybe it's 10 to the minus 5.

1190
01:07:32,900 --> 01:07:34,340
Maybe it's 10 to the minus 10.

1191
01:07:34,340 --> 01:07:37,350
But it's still only a finite
error probability.

1192
01:07:37,350 --> 01:07:38,390
Maybe we don't need the minimum

1193
01:07:38,390 --> 01:07:40,900
distance to go to infinity.

1194
01:07:40,900 --> 01:07:47,410
Maybe we can get by sampling
codes which are lousy in

1195
01:07:47,410 --> 01:07:51,290
classical terms, which have
poor minimum distance.

1196
01:07:51,290 --> 01:07:55,860
Maybe they'd be lousy in
distance terms, or in nominal

1197
01:07:55,860 --> 01:07:59,980
coding gain terms, but they'll
be very good from the point of

1198
01:07:59,980 --> 01:08:00,840
view of complexity.

1199
01:08:00,840 --> 01:08:02,910
Maybe there's some
trade-off here.

1200
01:08:02,910 --> 01:08:05,335
We know the code is going to
have to be long, but maybe it

1201
01:08:05,335 --> 01:08:06,990
doesn't have to have
large distance.

1202
01:08:06,990 --> 01:08:07,954
Yeah.

1203
01:08:07,954 --> 01:08:09,204
AUDIENCE: [INAUDIBLE]

1204
01:08:09,204 --> 01:08:11,810

1205
01:08:11,810 --> 01:08:13,750
That's what you are
saying, isn't it?

1206
01:08:13,750 --> 01:08:14,980
We try to maintain the --

1207
01:08:14,980 --> 01:08:17,290
PROFESSOR: We certainly want
to maintain a finite rate.

1208
01:08:17,290 --> 01:08:20,189

1209
01:08:20,189 --> 01:08:22,960
This was the problem with
orthogonal and simplex codes

1210
01:08:22,960 --> 01:08:25,990
and so forth, is that the rate
went to zero, and therefore

1211
01:08:25,990 --> 01:08:28,330
the spectral efficiency
went to zero.

1212
01:08:28,330 --> 01:08:31,850
In practically all cases,
that's unacceptable.

1213
01:08:31,850 --> 01:08:37,689
So we need to maintain some
minimal rate or spectral

1214
01:08:37,689 --> 01:08:40,859
efficiency on the additive
white Gaussian noise.

1215
01:08:40,859 --> 01:08:44,246
So that we need, but this
maybe we don't need.

1216
01:08:44,246 --> 01:08:51,350

1217
01:08:51,350 --> 01:08:57,240
So that's just a interesting
little bit of philosophy we

1218
01:08:57,240 --> 01:09:00,810
can do at this point, is how
should you really design

1219
01:09:00,810 --> 01:09:02,390
capacity-achieving codes?

1220
01:09:02,390 --> 01:09:07,630
And this seems to be a clue to
the way to go that has in fact

1221
01:09:07,630 --> 01:09:10,580
proved to be good.

1222
01:09:10,580 --> 01:09:15,000
However, I should add that not
all capacity-approaching codes

1223
01:09:15,000 --> 01:09:17,770
have this property.

1224
01:09:17,770 --> 01:09:20,479
A random low-density parity
check code is going to have

1225
01:09:20,479 --> 01:09:25,580
both low complexity and a very
good minimum distance as well.

1226
01:09:25,580 --> 01:09:30,710
So this certainly isn't
the full story.

1227
01:09:30,710 --> 01:09:36,490

1228
01:09:36,490 --> 01:09:43,939
There are just two more topics
in chapter 10, and maybe I'll

1229
01:09:43,939 --> 01:09:46,124
discuss them both briefly
right now.

1230
01:09:46,124 --> 01:09:49,029

1231
01:09:49,029 --> 01:09:51,943
One is I skipped over
projections.

1232
01:09:51,943 --> 01:09:57,360

1233
01:09:57,360 --> 01:10:00,730
And how shall I introduce
this subject?

1234
01:10:00,730 --> 01:10:06,590
I talked about the subcode of,
say, this code, which is

1235
01:10:06,590 --> 01:10:11,860
pretty badly marked-up by now,
but let me keep using it.

1236
01:10:11,860 --> 01:10:15,190
I talked about the subcode
that's supported, say, on the

1237
01:10:15,190 --> 01:10:17,270
first half.

1238
01:10:17,270 --> 01:10:20,830
In this case it's simply the
subcode that's generated by

1239
01:10:20,830 --> 01:10:22,080
the first generator.

1240
01:10:22,080 --> 01:10:25,100

1241
01:10:25,100 --> 01:10:30,000
Here's another code that we can
look at that's kind of a

1242
01:10:30,000 --> 01:10:31,740
first half code.

1243
01:10:31,740 --> 01:10:37,570
Suppose we just take the set
of all possible first

1244
01:10:37,570 --> 01:10:40,100
four-tuples in this code.

1245
01:10:40,100 --> 01:10:43,680
That's called the projection
onto the first half.

1246
01:10:43,680 --> 01:10:46,310
In other words, what are
the set of all possible

1247
01:10:46,310 --> 01:10:47,900
four-tuples?

1248
01:10:47,900 --> 01:10:57,260
They're the set of code words
that are generated by 1, 1, 1,

1249
01:10:57,260 --> 01:11:02,260
1, 0, 1, 0, 1, 0, 0,
1, 1, and this

1250
01:11:02,260 --> 01:11:04,050
doesn't contribute anything.

1251
01:11:04,050 --> 01:11:07,870
So it's a linear code.

1252
01:11:07,870 --> 01:11:10,220
It's length 4.

1253
01:11:10,220 --> 01:11:13,550
It has three generators,
dimension 3.

1254
01:11:13,550 --> 01:11:17,560
And we can quickly convince
ourselves that it's the even

1255
01:11:17,560 --> 01:11:20,220
weight, or zero sum, or
a single parity check

1256
01:11:20,220 --> 01:11:23,070
code of length 4.

1257
01:11:23,070 --> 01:11:26,520
So if we project this on
to the first half, we

1258
01:11:26,520 --> 01:11:30,390
get a 4, 3, 2 code.

1259
01:11:30,390 --> 01:11:33,900
So that's what I mean
by a projection.

1260
01:11:33,900 --> 01:11:38,850
If I project on to here,
I get the 1 0 code.

1261
01:11:38,850 --> 01:11:41,660
I'm sorry, I get the universe
code of length 1, all

1262
01:11:41,660 --> 01:11:42,820
one-tuples.

1263
01:11:42,820 --> 01:11:44,630
On here I get all two-tuples.

1264
01:11:44,630 --> 01:11:46,800
On here I get all
three-tuples.

1265
01:11:46,800 --> 01:11:48,740
But on here I don't get
all four-tuples.

1266
01:11:48,740 --> 01:11:51,820
I get a single parity
check code.

1267
01:11:51,820 --> 01:11:53,315
So those are my projections.

1268
01:11:53,315 --> 01:11:56,120

1269
01:11:56,120 --> 01:11:59,260
Some things can be done nicely
in terms of projections.

1270
01:11:59,260 --> 01:12:02,550
Projections are kind of
the dual to subcodes.

1271
01:12:02,550 --> 01:12:06,090
In fact, you prove this on the
homework in the course of

1272
01:12:06,090 --> 01:12:08,990
proving the dual state
space theorem.

1273
01:12:08,990 --> 01:12:18,720
In other words, the dual of a
subcode of a code C is the

1274
01:12:18,720 --> 01:12:24,840
projection of the dual code
of C, and vice versa.

1275
01:12:24,840 --> 01:12:29,450
They're always tongue twisters,
the duality theorem.

1276
01:12:29,450 --> 01:12:31,380
But that's what you will
prove along the way.

1277
01:12:31,380 --> 01:12:36,660
Let me give you the relevance
of this to

1278
01:12:36,660 --> 01:12:37,910
the state space theorem.

1279
01:12:37,910 --> 01:12:40,950

1280
01:12:40,950 --> 01:12:43,540
So I had the state space
theorem right here.

1281
01:12:43,540 --> 01:12:45,499
So let me leave it up.

1282
01:12:45,499 --> 01:12:52,350

1283
01:12:52,350 --> 01:12:56,720
State space theorem
is based on --

1284
01:12:56,720 --> 01:13:05,890
in general, we divide the
generator matrix g prime into

1285
01:13:05,890 --> 01:13:12,890
a part that is a generator
for the past subcode 0.

1286
01:13:12,890 --> 01:13:17,480

1287
01:13:17,480 --> 01:13:21,190
0 generator for the
future subcode.

1288
01:13:21,190 --> 01:13:26,180
And then some stuff down here,
which is generators of the

1289
01:13:26,180 --> 01:13:27,430
state space code.

1290
01:13:27,430 --> 01:13:32,640

1291
01:13:32,640 --> 01:13:41,350
By construction here, the
projections of any nonzero

1292
01:13:41,350 --> 01:13:46,640
vector in the state space
code are nonzero.

1293
01:13:46,640 --> 01:13:52,370
If they were zero, any nonzero
linear combination of these

1294
01:13:52,370 --> 01:13:55,980
generators down here cannot
be zero on here.

1295
01:13:55,980 --> 01:14:00,850

1296
01:14:00,850 --> 01:14:06,450
So the projection on to the
first half here, the dimension

1297
01:14:06,450 --> 01:14:08,460
of the projection --

1298
01:14:08,460 --> 01:14:11,960
I'm making a slight skip here
-- is basically equal to the

1299
01:14:11,960 --> 01:14:16,320
dimension of the past subspace
code plus the dimension of the

1300
01:14:16,320 --> 01:14:17,990
state code.

1301
01:14:17,990 --> 01:14:20,620
It's basically generated by
these generators and these

1302
01:14:20,620 --> 01:14:22,810
generators projected
onto here.

1303
01:14:22,810 --> 01:14:26,190
We can forget about
these generators.

1304
01:14:26,190 --> 01:14:29,040
So let me write that down.

1305
01:14:29,040 --> 01:14:36,930
The dimension of C projected
onto the past is equal to the

1306
01:14:36,930 --> 01:14:42,300
dimension of the past subcode
plus the dimension of the

1307
01:14:42,300 --> 01:14:43,550
state space code.

1308
01:14:43,550 --> 01:14:48,450

1309
01:14:48,450 --> 01:14:54,790
Which leads to another version
of the state space theorem.

1310
01:14:54,790 --> 01:14:58,392
I could simply write state space
theorem as dimension of

1311
01:14:58,392 --> 01:15:02,090
the state space at time k is
simply the difference between

1312
01:15:02,090 --> 01:15:06,770
the dimension of the projection,
C projected on the

1313
01:15:06,770 --> 01:15:09,640
past, minus the dimension
of the subcode.

1314
01:15:09,640 --> 01:15:12,210

1315
01:15:12,210 --> 01:15:15,100
It's all of these guys
minus these guys.

1316
01:15:15,100 --> 01:15:17,730

1317
01:15:17,730 --> 01:15:22,260
And again, if we look back here,
we see we have the 4, 3

1318
01:15:22,260 --> 01:15:30,080
code is C projected on
p, 4, 3, 2, and C --

1319
01:15:30,080 --> 01:15:32,870
the subcode is 4, 1, 4.

1320
01:15:32,870 --> 01:15:37,090
In fact, for this, these are
both Reed-Muller codes of half

1321
01:15:37,090 --> 01:15:38,100
the length.

1322
01:15:38,100 --> 01:15:39,855
This is not an accident,
as you will

1323
01:15:39,855 --> 01:15:42,420
prove in the homework.

1324
01:15:42,420 --> 01:15:45,340
The state space size is the
difference in the dimensions

1325
01:15:45,340 --> 01:15:46,290
of these two codes.

1326
01:15:46,290 --> 01:15:49,420
This is a very handy thing
to know, and you're

1327
01:15:49,420 --> 01:15:51,690
going to need this.

1328
01:15:51,690 --> 01:15:54,230
This, for instance, will give
you that in general for

1329
01:15:54,230 --> 01:15:59,330
Reed-Muller codes, if you
divide them in half --

1330
01:15:59,330 --> 01:16:06,570
we had this general picture of
say the 8 4 code being made up

1331
01:16:06,570 --> 01:16:09,330
by the new u plus
v construction.

1332
01:16:09,330 --> 01:16:15,190
These two together make
the 8, 4, 4 code.

1333
01:16:15,190 --> 01:16:22,560
If you have the u u plus v
construction, there you are,

1334
01:16:22,560 --> 01:16:24,750
first half, second half.

1335
01:16:24,750 --> 01:16:27,560
You will find that the
projection on the first half

1336
01:16:27,560 --> 01:16:32,700
is always this guy, which
is the u code.

1337
01:16:32,700 --> 01:16:38,530
And the subcode is v code,
which is the homework.

1338
01:16:38,530 --> 01:16:41,670
And so you can quickly read
off from this what the

1339
01:16:41,670 --> 01:16:45,160
dimension of the central
state space is

1340
01:16:45,160 --> 01:16:47,290
for Reed-Muller codes.

1341
01:16:47,290 --> 01:16:49,135
In this case it's 2.

1342
01:16:49,135 --> 01:16:57,400
But for instance if we have the
32, 16, 8 code, then what

1343
01:16:57,400 --> 01:16:58,470
is that made up of?

1344
01:16:58,470 --> 01:17:03,030
That's made up from the
16, 11, 4 code and

1345
01:17:03,030 --> 01:17:06,720
the 16, 5, 8 code.

1346
01:17:06,720 --> 01:17:09,320
And so we can see the dimension
of the central state

1347
01:17:09,320 --> 01:17:11,540
space here is going to be 6.

1348
01:17:11,540 --> 01:17:15,260
We're going to get a 64-state
trellis for this code, at

1349
01:17:15,260 --> 01:17:20,230
least just measuring the size
of the central state space.

1350
01:17:20,230 --> 01:17:24,590
Now it turns out you
can keep having --

1351
01:17:24,590 --> 01:17:28,400
if you go down and you make
four cuts here, then the

1352
01:17:28,400 --> 01:17:33,130
relevant codes are what you
get one more space back.

1353
01:17:33,130 --> 01:17:37,390
At this space, we have the 2,
2, 1 as the projected code,

1354
01:17:37,390 --> 01:17:41,080
and the 2, 0, infinity
as the subcode.

1355
01:17:41,080 --> 01:17:43,620
And again, the difference in
dimensions here is going to be

1356
01:17:43,620 --> 01:17:46,780
the same as the different
dimensions here.

1357
01:17:46,780 --> 01:17:48,150
Minor miracle at first.

1358
01:17:48,150 --> 01:17:51,630
It turns out to be just
from the construction.

1359
01:17:51,630 --> 01:17:58,010
Here we go back to the 8,
7, 2 and the 8, 1, 8.

1360
01:17:58,010 --> 01:18:02,110
And again we see the difference
here is 6.

1361
01:18:02,110 --> 01:18:08,520
So that means that Reed-Muller
codes always have trellises,

1362
01:18:08,520 --> 01:18:11,640
least if you put them
in four sections.

1363
01:18:11,640 --> 01:18:16,080
They always look like
this abstractly.

1364
01:18:16,080 --> 01:18:20,730
They look like what
we've already seen

1365
01:18:20,730 --> 01:18:22,256
for the 8, 4, 4 code.

1366
01:18:22,256 --> 01:18:27,080

1367
01:18:27,080 --> 01:18:29,700
And you'll do this on the
homework using projections.

1368
01:18:29,700 --> 01:18:32,440
That's not very hard.

1369
01:18:32,440 --> 01:18:34,510
It doesn't mean that --

1370
01:18:34,510 --> 01:18:38,050
so we know, for instance, for
the 32 16 8, we're going to do

1371
01:18:38,050 --> 01:18:41,560
this, and there are going to be
64 states here, 64 states

1372
01:18:41,560 --> 01:18:43,680
here, 64 states here.

1373
01:18:43,680 --> 01:18:45,760
We don't know what it's going to
be in between, but you can

1374
01:18:45,760 --> 01:18:48,630
figure that out too.

1375
01:18:48,630 --> 01:18:51,320
In fact, we get a minimal
trellis for the whole thing.

1376
01:18:51,320 --> 01:18:54,310

1377
01:18:54,310 --> 01:18:55,780
That's what you need
to do the homework.

1378
01:18:55,780 --> 01:18:58,880

1379
01:18:58,880 --> 01:19:01,300
There are actually two more
topics that I want to do in

1380
01:19:01,300 --> 01:19:02,670
Chapter 10.

1381
01:19:02,670 --> 01:19:05,500
One is the Muder bound.

1382
01:19:05,500 --> 01:19:07,320
And one --

1383
01:19:07,320 --> 01:19:11,440
I actually want to see how
good are these block code

1384
01:19:11,440 --> 01:19:15,010
trellises vis-a-vis
convolutional code trellises.

1385
01:19:15,010 --> 01:19:18,110
So I'll do both of those at the
beginning of next time.

1386
01:19:18,110 --> 01:19:25,270
For homework problem set, let's
this week do only the

1387
01:19:25,270 --> 01:19:28,240
first four problems.

1388
01:19:28,240 --> 01:19:35,760
So for this Wednesday,
do problem set --

1389
01:19:35,760 --> 01:19:36,480
what are we up to?

1390
01:19:36,480 --> 01:19:39,260
Seven, is it?

1391
01:19:39,260 --> 01:19:46,240
One through four, and for
Wednesday, 4/20, we'll do

1392
01:19:46,240 --> 01:19:51,070
problem set seven, five and six,
plus I'll probably have

1393
01:19:51,070 --> 01:19:52,150
another one.

1394
01:19:52,150 --> 01:19:55,990
But we have a holiday next
Monday also if you recall,

1395
01:19:55,990 --> 01:19:58,520
Patriots' Day.

1396
01:19:58,520 --> 01:20:01,230
So we only get one more
class on Wednesday.

1397
01:20:01,230 --> 01:20:05,770
So I probably won't have much
more to add than this.

1398
01:20:05,770 --> 01:20:07,040
Is that clear?

1399
01:20:07,040 --> 01:20:11,470
Maybe Ashish you could
put out a email to

1400
01:20:11,470 --> 01:20:13,530
the class to do that.

1401
01:20:13,530 --> 01:20:14,800
So good.

1402
01:20:14,800 --> 01:20:18,570
We'll come back and clean
up Chapter 10 quickly on

1403
01:20:18,570 --> 01:20:21,430
Wednesday, and then
move on to 11.

1404
01:20:21,430 --> 01:20:30,164