perfect code
PerfectCode
2004-06-04 17:17:45
2004-06-08 15:05:11
Definition
packing radius
covering radius
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
\newcommand{\mc}{\mathcal}
\newcommand{\mb}{\mathbb}
\newcommand{\mf}{\mathfrak}
\newcommand{\ol}{\overline}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\nor}{\vartriangleleft}
\newcommand{\Gal}{\text{Gal}}
\newcommand{\GL}{\text{GL}}
\newcommand{\Z}{\mb{Z}}
\newcommand{\R}{\mb{R}}
\newcommand{\Q}{\mb{Q}}
\newcommand{\C}{\mb{C}}
\newcommand{\<}{\langle}
\renewcommand{\>}{\rangle}
Let $C$ be a \PMlinkname{linear}{LinearCode} $(n,k,d)$-code over $\mb{F}_q$.
The \emph{packing radius} of $C$ is defined to be the value
\begin{align*}
\rho(C)=\frac{d-1}{2}.
\end{align*}
The \emph{covering radius} of $C$ is
\begin{align*}
r(C)=\max_x\min_c \delta(x,c)
\end{align*}
with $x\in \mb{F}_q^n$ and $c\in C$, and where $\delta$ denotes the Hamming distance on $\mb{F}_q^n$.
The \PMlinkname{code}{Code} $C$ is said to be \emph{perfect} if $r(C)=\rho(C)$.
The list of \PMlinkescapetext{classes} of linear perfect codes is very short, including only trivial codes, Hamming codes (i.e. $\rho=1$), and the binary and ternary \PMlinkname{Golay}{BinaryGolayCode} codes.