The Efficiency of Classes of Linear Codes
| Speaker: | Peter Nelson |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5417 |
Abstract:
A
$[n,k]$-linear
code
over
a
field
F
is
a
$k$-dimensional
subspace
of
$F^n$;
the
elements
of
this
subspace
are
codewords.
Ideally,
a
code
should
have
a
good
error
tolerance,
meaning
that
no
two
codewords
are
close
in
Hamming
distance,
and
a
code
should
use
available
bandwidth
efficiently,
meaning
that
the
dimension
$k$
is
not
too
small
compared
to
$n$.
Two
measures
of
efficiency
for
classes
of
codes
that
capture
these
competing
constraints
are
the
property
of
asymptotic
goodness,
and
the
more
refined
maximum-likelihood
decoding
threshold
function.
I
will
discuss
a
recent
result
that
determines
precisely
which
classes
of
codes
that
are
closed
under
a
natural
'minor'
property
are
asymptotically
good,
and
another
result
that
gives
an
essentially
best-possible
upper
bound
for
the
maximum-likelihood
decoding
threshold
function
for
all
codes
arising
from
graphs.
The
proofs
use
ideas
from
structural
matroid
theory,
algebraic
graph
theory,
and
probability
theory
on
infinite
trees.