Construction of Additive Reed-Muller Codes\thanks{This work has been partially supported by the Spanish MICINN Grants MTM2006-03250, TSI2006-14005-C02-01, PCI2006-A7-0616 and also by the Comissionat per a Universitats i Recerca de la Generalitat de Catalunya under grant FI2008.}
J.~Pujol\inst{}
J.~Rif\`{a}\inst{}
L.~Ronquillo\inst{}
The well known Plotkin construction is, in the current paper, generalized and used to yield new families of $\zz$-additive codes, whose length, dimension as well as minimum distance are studied. These new constructions enable us to obtain families of $\zz$-additive codes such that, under the Gray map, the corresponding binary codes have the same parameters and properties as the usual binary linear Reed-Muller codes. Moreover, the first family is the usual binary linear Reed-Muller family. \bigskip Key Words: $\zz$-Additive codes, Plotkin construction, Reed-Muller codes, $\zz$-linear codes.
0909.3185.tex

\documentclass{llncs}
% -*- TeX -*- -*- uk -*- -*- Soft -*-

\usepackage{multirow}
\usepackage{amsmath, amsfonts}

\newtheorem{lemm}{Lemma}
\newtheorem{theo}[lemm]{Theorem}
\newtheorem{prop}[lemm]{Proposition}
\newtheorem{defi}[lemm]{Definition}

\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\dd}{\displaystyle}
\newcommand{\zz}{\Z_2\Z_4}
\newcommand{\codi}{{\cal C}}
\newcommand{\G}{{\mathcal{G}}}
\newcommand{\RM}{{\mathcal{RM}}}
\newcommand{\ARM}{{\mathcal{ARM}}}
\newcommand{\AQRM}{{\mathcal{AQRM}}}
\newcommand{\EQ}{\begin{equation}}
\newcommand{\EN}{\end{equation}}



\begin{document}

\title{Construction of Additive Reed-Muller Codes\thanks{This work has been partially supported by the Spanish MICINN Grants MTM2006-03250, TSI2006-14005-C02-01, PCI2006-A7-0616 and also by the \textit{Comissionat per a Universitats i Recerca de la Generalitat de Catalunya} under grant FI2008.}}

\author{J.~Pujol\inst{} \and J.~Rif\`{a}\inst{} \and L.~Ronquillo\inst{}}

\institute{Department of Information and Communications Engineering,
Universitat Aut\`{o}noma de Barcelona, 08193-Bellaterra, Spain.}

 \maketitle
 \thispagestyle{empty}

\begin{abstract}
The well known Plotkin construction is, in the current paper, generalized and used to yield new families of $\zz$-additive codes, whose length, dimension as well as minimum distance are studied. These new constructions enable us to obtain families of $\zz$-additive codes such that, under the Gray map, the corresponding binary codes have the same parameters and properties as the usual binary linear Reed-Muller codes. Moreover, the first family is the usual binary linear Reed-Muller family.
\bigskip

\textbf{Key Words: } $\zz$-Additive codes, Plotkin construction,
Reed-Muller codes, $\zz$-linear codes.
\end{abstract}


\section{Introduction}

The aim of our  paper is to obtain a generalization of the Plotkin construction which gave rise to families of $\zz$-additive codes such that, after the Gray map, the corresponding $\zz$-linear codes had the same parameters and properties as the family of binary linear $RM$ codes. Even more, we want the corresponding codes with parameters $(r,m)=(1,m)$ and $(r,m)=(m-2,m)$ to be, respectively, any one of the non-equivalent $\zz$-linear Hadamard and $\zz$-linear $1$-perfect codes.


\section{Constructions of $\zz$-additive codes}\label{sec2}


In general, any non-empty subgroup ${\cal C}$ of $\Z_2^\alpha \times
\Z_4^\beta$ is a {\it $\zz$-additive code}, where $\Z_2^\alpha$ denotes the set of all binary
vectors of length $\alpha$ and $\Z_4^\beta$ is the set of all $\beta$-tuples in $\Z_4$.

Let $\codi$ be a $\zz$-additive code, and let $C=\Phi(\codi)$, where
$\Phi: \Z_2^{\alpha}\times\Z_4^{\beta} \longrightarrow \Z_2^{n}$ is given by the map $\Phi(u_1, \ldots, u_{\alpha} | v_1, \ldots, v_{\beta})=(u_1, \ldots, u_{\alpha} | \phi(v_1), \ldots, \phi(v_{\beta}))$ where $\phi(0)=(0,0)$, $\phi(1)=(0,1)$, $\phi(2)=(1,1)$, and $\phi(3)=(1,0)$ is the usual Gray map from $\Z_4$ onto $\Z_2^2$.

Since the Gray map is distance preserving, the Hamming distance of a $\zz$-linear code $C$ coincides with the Lee distance computed on the $\zz$-additive code $\codi=\phi^{-1}(C)$.

A $\zz$-additive code $\codi$ is also isomorphic to an abelian structure like
$\Z_2^{\gamma}\times \Z_4^{\delta}$. Therefore, $\codi$ has $|\codi|=2^\gamma 4^\delta $ codewords and, moreover, $2^{\gamma+\delta}$ of them are of order two. We call such code $\codi$ a
{\it $\zz$-additive code of type $(\alpha,\beta;\gamma,\delta)$} and its
binary image $C=\Phi(\codi)$ is a {\it $\zz$-linear code of type
$(\alpha,\beta;\gamma,\delta)$}. 

Although $\codi$ may not have a basis, it is important and
appropriate to define a generator matrix for $\codi$ as:
\EQ\label{generatorMatrix}
   \G=\left ( \begin{array}{c|c}
        B_2 & Q_2 \\
        \hline
        B_4 & Q_4 \\
    \end{array}\right ),
\EN
where $B_2$ and $B_4$ are binary matrices of size $\gamma\times
\alpha$ and $\delta\times \alpha$, respectively; $Q_2$ is a $\gamma\times \beta$-quaternary matrix which contains order two row vectors; and $Q_4$ is a $\delta\times \beta$-quaternary matrix with order four row vectors.



\subsection{Plotkin construction}


In this section we show that the well known Plotkin construction can be generalized to $\zz$-additive codes.


\begin{defi}[Plotkin Construction]\label{PlotDefi}
 Let
$\mathcal{X}$ and $\mathcal{Y}$
be any two $\zz$-additive codes of types
$(\alpha,\beta;\gamma_\mathcal{X},\delta_\mathcal{X})$,
$(\alpha,\beta;\gamma_\mathcal{Y},\delta_\mathcal{Y})$ and minimum distances
$d_\mathcal{X}$, $d_\mathcal{Y}$, respectively. If
$\G_\mathcal{X}$ and $\G_\mathcal{Y}$ are the
generator matrices of $\mathcal{X}$ and $\mathcal{Y}$, then the
matrix
$$
\G_{P}=\left ( \begin{array}{cc}
                         \G_\mathcal{X} & \G_\mathcal{X} \\
                          0  & \G_\mathcal{Y} \\
                      \end{array} \right )
$$ is the generator matrix of a new $\zz$-additive code $\mathcal{C}$.
\end{defi}

 
\begin{prop}\label{PlotConst}
Code $\mathcal{C}$ defined above is a
$\zz$-additive code of type $(2\alpha,2\beta;\gamma, \delta)$, where
$\gamma=\gamma_\mathcal{X}+\gamma_\mathcal{Y}$,
$\delta=\delta_\mathcal{X}+\delta_\mathcal{Y}$, binary length $n=2\alpha+4\beta$, size $2^{\gamma+2\delta}$ and minimum distance
$d=\min\{2d_\mathcal{X},d_\mathcal{Y}\}$.
\end{prop}


\subsection{BA-Plotkin construction}

Applying two Plotkin constructions, one after another, but slightly
changing the submatrices in the generator matrix, we obtain a new
construction with interesting properties with regard to the minimum
distance of the generated code. We call this new construction {\it
BA-Plotkin construction}.

%%%%%%%%%%%
Given a $\zz$-additive code $\mathcal{C}$ with generator matrix $\G$ we denote, respectively, by
$\G[b_2]$, $\G[q_2]$, $\G[b_4]$ and $\G[q_4]$ the four submatrices $B_2$, $Q_2$, $B_4$, $Q_4$ of $\G$ defined in (\ref{generatorMatrix}); and
by $\G[b]$ and $\G[q]$ the submatrices of $\G$, $\left ( \begin{array}{c|}
        B_2 \\
        \hline
        B_4 \\
    \end{array}\right )$, $\left ( \begin{array}{|c}
        Q_2 \\
        \hline
        Q_4 \\
    \end{array}\right )$, respectively.
%%%%%%%%%%%%%%%%%%%%

\begin{defi}[BA-Plotkin Construction] \label{BAPlot}
Let $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ be any three
$\zz$-additive codes of types
$(\alpha,\beta;\gamma_\mathcal{X},\delta_\mathcal{X})$,
$(\alpha,\beta;\gamma_\mathcal{Y},\delta_\mathcal{Y})$,
$(\alpha,\beta;\gamma_\mathcal{Z},\delta_\mathcal{Z})$ and minimum distances
$d_\mathcal{X}$, $d_\mathcal{Y}$, $d_\mathcal{Z}$, respectively. Let $\G_\mathcal{X}$, $\G_\mathcal{Y}$ and
$\G_\mathcal{Z}$ be the generator matrices of the
$\zz$-additive codes $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$, respectively. We
define a new code $\mathcal{C}$ as the $\zz$-additive code
generated by


$$
\G_{BA} = \left ( \begin{array}{c c | c c c c c}
\G_\mathcal{X}[b] & \G_\mathcal{X}[b] & 2\G_\mathcal{X}[b] & \G_\mathcal{X}[q] & \G_\mathcal{X}[q] & \G_\mathcal{X}[q] & \G_\mathcal{X}[q]\\
0 & \G_\mathcal{Y}[b_2] & \G_\mathcal{Y}[b_2] & 0 & 2\G'_\mathcal{Y}[q_2] & \G'_\mathcal{Y}[q_2] & 3\G'_\mathcal{Y}[q_2]\\
0 & \G_\mathcal{Y}[b_4] & \G_\mathcal{Y}[b_4] & 0 & \G_\mathcal{Y}[q_4] & 2\G_\mathcal{Y}[q_4] & 3\G_\mathcal{Y}[q_4]\\
\G_\mathcal{Y}[b_4] & \G_\mathcal{Y}[b_4] & 0 & 0 & 0 & \G_\mathcal{Y}[q_4] & \G_\mathcal{Y}[q_4]\\
0 & \G_\mathcal{Z}[b] & 0 & 0 & 0 & 0 & \G_\mathcal{Z}[q]
\end{array} \right ),
$$

where $\G'_\mathcal{Y}[q_2]$ is the matrix obtained from $\G_\mathcal{Y}[q_2]$
after switching twos by ones in its $\gamma_\mathcal{Y}$ rows of order two, and considering the ones from the third column of the construction as ones in the quaternary ring $\Z_4$.

\end{defi}

\begin{prop}\label{BA-PlotkinConst}
Code $\mathcal{C}$ defined above is a $\zz$-additive code of
type $(2\alpha,\alpha+4\beta;\gamma,\delta)$ where
$\gamma=\gamma_\mathcal{X}+\gamma_\mathcal{Z}$,
$\delta=\delta_\mathcal{X}+\gamma_\mathcal{Y}+2\delta_\mathcal{Y}+\delta_\mathcal{Z}$,
binary length $n=4\alpha+8\beta$, size $2^{\gamma+2\delta}$ and minimum
distance $d =
\min\{4d_\mathcal{X},2d_\mathcal{Y},d_\mathcal{Z}\}$.
\end{prop}



\section{Additive Reed-Muller codes}\label{sec3}

We will refer to $\zz$-additive Reed-Muller codes as $\ARM$.
Just as there is only one $RM$ family in the binary case, in the $\zz$-additive case there are $\lfloor \frac{m+2}{2} \rfloor$ families for each value of $m$. Each one of these families will contain any of the $\lfloor \frac{m+2}{2} \rfloor$ non-isomorphic $\zz$-linear extended perfect codes which are known to exist for any $m$ \cite{BoRi99}.\\
We will identify each family ${\ARM}_s(r,m)$ by a subindex $s\in \{ 0,\ldots,\lfloor \frac{m}{2} \rfloor \}$.


\subsection{The families of $\ARM(r,1)$ and $\ARM(r,2)$ codes}\label{ARM2}

We start by considering the case $m=1$, that is the case of codes of
binary length $n=2^1$. The $\zz$-additive Reed-Muller code
$\ARM(0,1)$ is the repetition code, of type $(2,0;1,0)$ and which only has one nonzero codeword
(the vector with only two binary coordinates of value $1$). The code $\ARM(1,1)$ is
the whole space $\Z_2^2$, thus a $\zz$-additive code of type
$(2,0;2,0)$. Both codes $\ARM(0,1)$ and $\ARM(1,1)$ are
binary codes with the same parameters and properties as the corresponding binary
$RM(r,1)$ codes (see \cite{Mac}). We will refer to them as $\ARM_0(0,1)$ and $\ARM_0(1,1)$,
respectively.

The generator matrix of $\ARM_0(0,1)$ is $\G_0(0,1)=\left(\begin{array}{cc}1 & 1\\
\end{array}\right)$ and the generator matrix of $\ARM_0(1,1)$ is
$\G_0(1,1)=\left(\begin{array}{cc}1 & 1 \\ 0 & 1\\
\end{array}\right)$.

For $m=2$ we have two families, $s=0$ and $s=1$, of additive Reed-Muller codes of binary length $n=2^2$.
The family $\ARM_0(r,2)$ consists of binary codes obtained
from applying the Plotkin construction defined in Proposition~\ref{PlotConst} to the family $\ARM_0(r,1)$. For $s=1$, we define $\ARM_1(0,2)$, $\ARM_1(1,2)$ and $\ARM_1(2,2)$ as the codes with generator
matrices $\G_1(0,2)=\left(\begin{array}{cc|c}1 & 1 & 2\\
\end{array}\right)$,
$\G_1(1,2)=\left(\begin{array}{cc|c}1 & 1 & 2 \\ \hline 0 & 1 & 1\\
\end{array}\right)$ and $\G_1(2,2)=\left(\begin{array}{cc|c}1 & 1 & 2 \\ 0 & 1 & 0 \\ \hline 0 & 1 & 1\\
\end{array}\right)$, respectively.



\subsection{Plotkin and BA-Plotkin constructions}\label{construccions}

Take the family $\ARM_s$ and let $\ARM_s(r,m-1)$, $\ARM_s(r-1,m-1)$ and $\ARM_s(r-2,m-1)$,
 $0\leq s\leq \lfloor \frac{m-1}{2}\rfloor $, be three consecutive codes
with parameters ($\alpha,\beta;\gamma',\delta'$), ($\alpha,\beta;\gamma'',\delta''$) and ($\alpha,\beta;\gamma''',\delta'''$);
binary length $n=2^{m-1}$; minimum distances $2^{m-r-1}$, $2^{m-r}$ and $2^{m-r+1}$; and generator matrices $\G_{s}(r,m-1)$, $\G_{s}(r-1,m-1)$ and $\G_{s}(r-2,m-1)$, respectively.
By using Proposition~\ref{PlotConst} and Proposition~\ref{BA-PlotkinConst} we can prove the following results:

\begin{theo}\label{plotkin}
For any $r$ and $m\geq 2$, $0< r< m$, code $\ARM_s(r,m)$ obtained
by applying the Plotkin construction from Definition~\ref{PlotDefi} on codes $\ARM_s(r,m-1)$ and $\ARM_s(r-1,m-1)$ is
a $\zz$-additive code of type ($2\alpha$, $2\beta$; $\gamma$, $\delta$), where
$\gamma=\gamma'+\gamma''$ and $\delta=\delta'+\delta''$; binary
length $n=2^{m}$; size $2^k$ codewords, where $k= \dd
\sum_{i=0}^r\binom{m}{i}$; minimum distance $2^{m-r}$ and
$\ARM_s(r-1,m) \subset \ARM_s(r,m)$.

We consider $\ARM_s(0,m)$ to be the repetition code with only one nonzero codeword (the vector with $2\alpha$ ones and $2\beta$ twos) and $\ARM_s(m,m)$ be the whole space $\Z_2^{2\alpha}\times\Z_4^{2\beta}$.
\end{theo}


\begin{theo}\label{BA-plotkin}
For any $r$ and $m\geq 3$, $0< r< m$, $s>0$,
use the BA-Plotkin construction from Definition~\ref{BAPlot}, where generator matrices $\G_{\mathcal{X}}$, $\G_{\mathcal{Y}}$, $\G_{\mathcal{Z}}$ stand for $\G_{s}(r,m-1)$, $\G_{s}(r-1,m-1)$ and $\G_{s}(r-2,m-1)$, respectively, to obtain a new $\zz$-additive 
$\ARM_{s+1}(r,m+1)$ code of type ($2\alpha$, $\alpha+4\beta$; $\gamma$, $\delta$),
where $\gamma=\gamma'+\gamma'''$, $\delta=\delta'+\gamma''+2\delta''+\delta'''$; binary length
$n=2^{m+1}$; $2^k$ codewords, where $k=~ \dd
\sum_{i=0}^r\binom{m+1}{i}$, minimum distance $2^{m-r+1}$ and, moreover,
$\ARM_{s+1}(r-~1,m+1)~\subset~\ARM_{s+1}(r,m+1)$.
\end{theo}

To be coherent with all notations, code
$\ARM_{s+1}(-1,m+1)$ is defined as the all zero codeword code, code $\ARM_{s+1}(0,m+1)$ is defined as the repetition code
with only one nonzero codeword (the vector with $2\alpha$ ones and $\alpha+4\beta$ twos), whereas codes $\ARM_{s+1}(m,m+1)$ and
$\ARM_{s+1}(m+1,m+1)$ are defined as the even Lee weight code and the
whole space $\Z_2^{2\alpha}\times\Z_4^{\alpha+4\beta}$, respectively.

Using both Theorem~\ref{plotkin} and Theorem~\ref{BA-plotkin} we can now
construct all $\ARM_{s}(r,m)$ codes for $m>2$. Once applied the Gray map, all these codes give rise to binary codes with the
same parameters and properties as the $RM$ codes. Moreover, when $m = 2$ or $m = 3$, they also have the same
codewords.




\begin{thebibliography}{99}



\bibitem{BoRi99} J. Borges, J. Rif\`{a}, A
    characterization of 1-perfect
additive codes. {\em IEEE Trans. Inform. Theory}, 45(5):~1688-1697, 1999.


\bibitem{Mac} F.J. MacWilliams and N.J.A. Sloane,
\newblock {\em The Theory of Error-Correcting Codes}.
\newblock North-Holland Publishing Company, 1977.



\end{thebibliography}
\end{document}

0909.3185.extracted_bib
\begin{thebibliography}{99}



\bibitem{BoRi99} J. Borges, J. Rif\`{a}, A
    characterization of 1-perfect
additive codes. {\em IEEE Trans. Inform. Theory}, 45(5):~1688-1697, 1999.


\bibitem{Mac} F.J. MacWilliams and N.J.A. Sloane,
\newblock {\em The Theory of Error-Correcting Codes}.
\newblock North-Holland Publishing Company, 1977.



\end{thebibliography}