# Self-Dual Convolutional Codes

Sebastian Heri, Julia Lieb and Joachim Rosenthal
Institute of Mathematics
University of Zürich
Winterthurerstr 190, CH-8057 Zürich, Switzerland

###### Abstract

This paper investigates the concept of self-dual convolutional code. We derive
the basic properties of this interesting class of codes and we show how some
of the techniques to construct self-dual linear block codes generalize to
self-dual convolutional codes. As for self-dual linear block codes we are able
to give a complete classification for some small parameters.

##  1 Introduction

An $(n,k)$ linear block code $\mathcal{C}$ is by definition a linear subspace
$\mathcal{C}\subset\mathbb{F}_{q}^{n}$, where $\mathbb{F}_{q}$ is a finite
field and $\dim_{\mathbb{F}_{q}}\mathcal{C}=k.$ By considering the natural
bilinear form $<\,,\,>$ on the vector space $\mathbb{F}_{q}^{n}$ one obtains
the notion of the dual code

$\mathcal{C}^{\perp}=\left\\{\;x\in\mathbb{F}_{q}^{n}\;|\ <x,c>=0\;\;\forall
c\in C\;\right\\}.$

Clearly $\mathcal{C}^{\perp}$ is an $(n-k,k)$ linear block code. Note also
that the bilinear form $<\,,\,>$ is in general not positive definite and when
$n=2k$ it can happen that $\mathcal{C}^{\perp}=\mathcal{C}$. A code having the
particular property that $\mathcal{C}^{\perp}=\mathcal{C}$ is called a self-
dual linear block code.

Self-dual block codes are a highly interesting class of linear block codes and
there have been large efforts in the classification of self-dual codes. In
[14, 2] a complete classification of binary self-dual block codes up to length
30 is provided. This is extended in [5] to a complete classification up to
length 36. Moreover, in [3], [5] and [9], different techniques how to
construct new self-dual block codes from known self-dual block codes are
provided. In this paper, we will generalize all of these techniques to obtain
new self-dual convolutional codes from known self-dual convolutional codes. In
general there exist still many interesting and open questions related to self-
dual block codes and the interested reader is referred to the survey articles
[1, 15].

In this paper we introduce the concept of a self-dual convolutional code. For
this note that one can view a convolutional code $\mathcal{C}$ as a submodule
$\mathcal{C}\subset{\mathbb{F}_{q}}[x]^{n}$, where ${\mathbb{F}_{q}}[x]$ is
the polynomial ring over the finite field ${\mathbb{F}_{q}}$. Again one has a
natural bilinear form $<\,,\,>$ on ${\mathbb{F}_{q}}[x]^{n}$ and this induces
the notion of dual convolutional code $\mathcal{C}^{\perp}$ and it is
therefore again interesting when a convolutional code is self-dual. In [7],
examples of particular self-dual convolutional codes are provided, however,
using another definition of self-duality than the one presented in our paper.
In [13], an algorithm to find systematic self-dual convolutional codes is
presented. However, theoretical approaches concerning properties and
classifications of this kind of codes have still been lacking and are the
objective of our paper.

The paper is structured as follows. In Section 2, we present the basics on
self-dual block codes and their construction from smaller self-dual codes. In
Section 3, we introduce convolutional codes. In Section 4, we present criteria
for convolutional codes to be self-dual as well as some properties of self-
dual convolutional codes. In Section 5, we classify all self-dual
convolutional codes with certain code parameters. In Section 5.1, we classify
all self-dual $(2,1)$ convolutional codes, in Section 5.2 all binary self-dual
$(4,2)$ convolutional codes, in Section 5.3 all self-dual convolutional codes
with double diagonal generator matrices and in Section 5.4 all binary self-
dual convolutional codes with double triangular generator matrices. In Section
6, we generalize the building-up construction and the Harada-Munemasa
construction from block to convolutional codes, where the building-up
construction is further generalized to arbitrary finite fields. Moreover, we
prove that every binary code obtained with the generalized building-up
construction can be also obtained with the generalized Harada-Munemasa
construction, but the opposite is not true. Furthermore, we show that not all
binary self-dual convolutional codes with free distance $d_{free}>2$ can be
constructed with the generalized building-up construction, as it was shown to
be true for block codes. We also show that all binary self-dual $(4,2)$
convolutional codes can be constructed with the generalized Harada-Munemasa
construction, but for general code parameters this question remains open.

##  2 Self-Dual Linear Block Codes

In this section, we present some results on self-dual linear block codes, that
we will generalize later to obtain results for self-dual convolutional codes.

###  2.1 Preliminaries

Let $\mathbb{F}_{q}$ denote the finite field with $q$ elements.

######  Definition 1.

An $(n,k)$ (linear) block code $\mathcal{C}$ over $\mathbb{F}_{q}$ is a
$k$-dimensional subspace $\mathcal{C}\subset\mathbb{F}_{q}^{n}$, where $k\leq
n$. A matrix $G\in\mathbb{F}_{q}^{k\times n}$ such that
$\mathcal{C}=rowspan(G)$ is called a generator matrix of $\mathcal{C}$.

######  Definition 2.

We say that two generator matrices $G_{1}$ and $G_{2}$ are equivalent if there
exists an invertible matrix $A\in GL_{k}(\mathbb{F}_{q})$ such that

$G_{1}=AG_{2}.$

In other words, two generator matrices are equivalent if they generate the
same code.

######  Definition 3.

Let $\mathcal{C}$ be a $(n,k)$ linear block code. Then there exists
$H\in\mathbb{F}_{q}^{(n-k)\times n}$ such that

$\mathcal{C}=ker(H)=\\{v\in\mathbb{F}_{q}^{n}\ |\ Hv^{\top}=0\\}.$

We call $H$ a parity-check matrix of $\mathcal{C}$.

As a generator matrix also a parity-check is in general not unique and
elementary row operations on either of these matrices leaves the code
unchanged.

######  Definition 4.

For a code $\mathcal{C}\subset\mathbb{F}_{q}^{n}$,
$\mathcal{C}^{\perp}=\left\\{\;x\in\mathbb{F}_{q}^{n}\;|\ <x,c>=0\;\;\forall
c\in C\;\right\\}$ is called the dual of a code
$\mathcal{C}\subset\mathbb{F}_{q}^{n}$. If the condition of $xc^{\top}=0$
holds, $x$ and $c$ are said to be orthogonal.

The dual of a linear block code is always a linear block code.

######  Definition 5.

We say that a code $\mathcal{C}$ is self-orthogonal if
$\mathcal{C}\subset\mathcal{C}^{\perp}$ and self-dual if
$\mathcal{C}=\mathcal{C}^{\perp}$.

Thus, self-orthogonality is fulfilled if all codewords are orthogonal to each
other, whereas self-duality demands the further restriction of no other
element in the vector space $\mathbb{F}_{q}^{n}$ being orthogonal to all
codewords.
The following lemma is an immediate consequence of the definition of the dual
code.

######  Lemma 1.

[6] Let $G$ be a generator matrix of $\mathcal{C}$. Then

$\mathcal{C}^{\perp}=ker(G)$

i.e., $G$ is a parity-check matrix of $\mathcal{C}^{\perp}$.

An important consequence of this lemma is that the generator matrix of a self-
dual code is also a parity-check matrix of the given code as
$\mathcal{C}=\mathcal{C}^{\perp}=ker(G)$.

######  Corollary 1.

[6] Any self-dual $(n,k)$ code fulfills $n=2k$.

Hence, from now on we may assume every self-dual code to be a $(n,n/2)$ code
or equivalently a $(2k,k)$ code.

######  Lemma 2.

[11, Chapter 1.8] Let $\mathcal{C}$ be a $(2k,k)$ block code over
$\mathbb{F}_{q}$ with generator matrix $G$. Then the following statements are
equivalent:

  * (i)

$\mathcal{C}$ is self-dual;

  * (ii)

$\mathcal{C}$ is self-orthogonal;

  * (iii)

$GG^{\top}=0$;

  * (iv)

$G$ is a parity-check matrix of $\mathcal{C}$.

######  Definition 6.

Let $c_{1}=(x_{1},\ldots,x_{n})$ and $c_{2}=(y_{1},\ldots,y_{n})$ be elements
of a code. Then their (Hamming) distance is defined to be

$d(c_{1},c_{2}):=\left\\{i|x_{i}\neq y_{i}\right\\}$

and the (Hamming) weight of $c_{1}$ is $wt(c_{1}):=d(c_{1},0)$.

######  Definition 7.

The (minimum) distance d of a linear block code $\mathcal{C}$ is given by

$d=d(C)=min\left\\{wt(c)\ |\ c\in\mathcal{C}\setminus\\{0\\}\right\\}.$

One uses the notation $[n,k,d]$ code for an $(n,k)$ block code with distance
$d$.

###  2.2 Construction Methods

There are three popular construction methods for binary self-dual codes,
namely the building-up construction, the Harada-Munemasa construction and the
recursive construction. The latter will not be presented, but interested
readers may consult [12].

######  Theorem 1 (Building-up construction).

[9] Let $\mathcal{C}$ be a binary self-dual $(2k,k)$ code and
$G=(g_{i})_{i\in\left\\{1,...,k\right\\}}$ its generator matrix, where $g_{i}$
is the $i$-th row of $G$. Let $x\in\mathbb{F}_{2}^{n}$ be a binary vector with
odd weight and define $y_{i}:=xg_{i}^{\top}$ for $1\leq i\leq k$. Then

$\tilde{G}=\begin{pmatrix}1&0&x\\\ y_{1}&y_{1}&\\\ \vdots&\vdots&G\\\
y_{k}&y_{k}&\end{pmatrix}\in\mathbb{F}_{2}^{(k+1)\times(2k+2)}$

generates a binary self-dual $(2k+2,k+1)$ code $\tilde{\mathcal{C}}$.

######  Theorem 2.

[9] Any binary self-dual code of length $n$ with distance $d>2$ can be
obtained from some binary self-dual code of length $n-2$ with the construction
in Theorem 1 (up to column permutations in the generator matrix).

As second construction method we present the Harada-Munemasa construction.

######  Theorem 3 (Harada-Munemasa construction).

[5] Let $G$ be the generator matrix of a binary self-dual $[2k,k,d]$ code
$\mathcal{C}$. Then the matrix

$G_{1}=\begin{pmatrix}a_{1}&a_{1}&\\\ \vdots&\vdots&G\\\
a_{k}&a_{k}&\end{pmatrix}\in\mathbb{F}_{2}^{k\times(2k+2)},$

where $a_{i}\in\mathbb{F}_{2}$, generates a binary self-orthogonal
$[2k+2,k,\geq d]$ code $\mathcal{C}_{1}$. Moreover, there exists
$x\in\mathcal{C}_{1}^{\perp}\setminus\mathcal{C}_{1}$ such that

$G_{2}=\begin{pmatrix}\rule[2.15277pt]{10.76385pt}{0.5pt}&x&\rule[2.15277pt]{10.76385pt}{0.5pt}\\\
a_{1}&a_{1}&\\\ \vdots&\vdots&G\\\
a_{k}&a_{k}&\end{pmatrix}\in\mathbb{F}_{2}^{(k+1)\times(2k+2)}$

generates a binary self-dual $(2k+2,k+1)$ code.

######  Theorem 4.

Any binary self-dual code of length $n$ with distance $d>2$ can be obtained by
some binary self-dual code of length $n-2$ with the construction in Theorem 3
(up to column permutations in the generator matrix).

The difference between the two constructions is that the building-up
construction chooses the row first and then simply calculates the entries of
the new columns based on the chosen row, whereas the Harada-Munemasa
construction chooses the columns first and then determines the to be added
row.

##  3 Convolutional Codes

In this section, we first introduce some basics about convolutional codes with
a particular focus on non-catastrophic convolutional codes. Then, we will
connect non-catastrophic codes to self-dual codes and present equivalent
properties to self-duality, which will be used for classifications and
constructions in later chapters.

###  3.1 Preliminaries

######  Definition 8.

An $(n,k)$ convolutional code is a $\mathbb{F}_{q}[z]$-submodule of
$\mathbb{F}_{q}[z]^{n}$ with rank $k$.

$\mathbb{F}_{q}[z]$ is a PID and modules over a PID always admit a basis.
Therefore, one always finds $G(z)\in\mathbb{F}_{q}[z]^{k\times n}$ such that
$\mathcal{C}=rowspan(G(z))$. This $G(z)$ is called a generator matrix of
$\mathcal{C}$.

######  Definition 9.

Let $H(z)\in\mathbb{F}_{q}[z]^{(n-k)\times n}$ such that

$\mathcal{C}=ker(H(z)).$

Then we call $H(z)$ a parity-check matrix of $\mathcal{C}$.

Other than for block codes, there are some convolutional codes that do not
admit a parity-check matrix. More details on the specific characteristics that
permit the existence of a parity-check matrix will be presented in Chapter
3.2.

######  Definition 10.

We say that $U(z)\in\mathbb{F}_{q}[z]^{k\times k}$ is unimodular if there
exists $V(z)\in\mathbb{F}_{q}[z]^{k\times k}$ such that

$V(z)U(z)=I_{k}.$

######  Definition 11.

Two generator matrices $G(z)\in\mathbb{F}_{q}[z]^{k\times n}$ and
$\tilde{G}(z)\in\mathbb{F}_{q}[z]^{k\times n}$ are equivalent if there exists
a unimodular matrix $U(z)\in\mathbb{F}_{q}[z]^{k\times k}$ such that

$G(z)=U(z)\tilde{G}(z).$

Equivalent generator matrices generate the same code.

######  Definition 12.

We say that a row or column operation is unimodular if it is done via
multiplication with a unimodular matrix.

Furthermore, we introduce a notion that in a way tells us how “far away" a
convolutional code is from a block code.

######  Definition 13.

The degree $\delta$ of a convolutional code is defined to be the highest
degree of any $k$-th minor of its generator matrix.

As the generator matrices of two equivalent codes differ by multiplication
with a unimodular matrix, which has a constant determinant, the degree
$\delta$ is the same for all equivalent generator matrices, making it a well-
defined notion.

######  Remark 1.

The convolutional codes of degree $0$ are essentially the linear block codes.

######  Definition 14.

The weight of a polynomial vector

$c(z)=\sum_{i=0}^{deg(c(z))}c_{i}z^{i}\in\mathbb{F}_{q}[z]^{n}$

is defined to be

$wt(c(z)):=\sum_{i=0}^{deg(c(z))}wt(c_{i}),$

where $wt(c_{i})$ denotes the Hamming weight of $c_{i}$.

######  Definition 15.

The free distance of a convolutional code $\mathcal{C}$ is defined as

$d_{free}(\mathcal{C})=min\left\\{wt(c(z))\ |\
c(z)\in\mathcal{C}\setminus\\{0\\}\right\\}.$

###  3.2 Non-Catastrophic Codes

######  Definition 16.

A polynomial matrix $G(z)\in\mathbb{F}_{q}[z]^{k\times n}$ is said to be left-
prime if in all factorizations

$G(z)=A(z)\tilde{G}(z),\textit{ with }A(z)\in\mathbb{F}_{q}[z]^{k\times
k}\textit{ and }\tilde{G}(z)\in\mathbb{F}_{q}[z]^{k\times n},$

the left factor $A(z)$ is unimodular.

If one generator matrix is left-prime, then all equivalent generator matrices
are also left-prime as they differ by left-multiplication with a unimodular
matrix. We call codes that admit a left-prime generator matrix non-
catastrophic and catastrophic if they do not.

We will see more practical methods to check whether codes are non-catastrophic
in Theorem 5, but first we introduce some necessary notions.

######  Definition 17.

[4, Section 2.1] Let $G(z)\in\mathbb{F}_{q}[z]^{k\times n}$ with $k\leq n$.
Then, there exists a unimodular matrix $U(z)\in\mathbb{F}_{q}[z]^{k\times k}$
such that

$G_{rH}(z)=U(z)G(z)=\begin{pmatrix}h_{11}(z)&h_{12}(z)&\cdots&h_{1k}(z)&h_{1{k+1}}(z)&\cdots&h_{1{2k}}(z)\\\
&h_{22}(z)&\cdots&h_{2k}(z)&h_{2{k+1}}(z)&\cdots&h_{2{2k}}(z)\\\
&&\ddots&\vdots&\vdots&&\vdots\\\
&&&h_{kk}(z)&h_{{k}{k+1}}(z)&\cdots&h_{k{2k}}(z)\end{pmatrix},$

where $(h_{ii}(z))_{i=1}^{k}$ are monic polynomials such that
$deg(h_{ii}(z))>deg(h_{ji}(z))$ for $i>j$ if $h_{ii}(z)$ is not identically
equal to zero. The matrix $G_{rH}(z)$ is unique and called row Hermite form of
$G(z)$.

The uniqueness of the row Hermite form gives us the option to characterize
equivalent generator matrices by their respective row Hermite form.

######  Definition 18.

Let $G(z)\in\mathbb{F}_{q}[z]^{k\times n}$ with $k\leq n$. Then there exists a
unimodular matrix $V(z)\in\mathbb{F}_{q}[z]^{n\times n}$ such that

$G_{cH}(z)=G(z)V(z)=\begin{pmatrix}h_{11}(z)&&&&0&\cdots&0\\\
h_{21}(z)&h_{22}(z)&&&0&\cdots&0\\\ \vdots&\vdots&\ddots&&\vdots&&\vdots\\\
h_{k1}(z)&h_{k2}(z)&\cdots&h_{kk}(z)&0&\cdots&0\end{pmatrix},$

where $(h_{ii}(z))_{i=1}^{k}$ are monic polynomials such that
$deg(h_{ii}(z))>deg(h_{ij}(z))$ for $i>j$ if $h_{ii}(z)$ is not identically
equal to zero. $G_{cH}(z)$ is called the (unique) column Hermite Form of
$G(z)$.

######  Definition 19.

Let $G(z)\in\mathbb{F}_{q}[z]^{k\times n}$ be full rank with $k\leq n$. Then
there exist two unimodular matrices $U(z)\in\mathbb{F}_{q}[z]^{k\times k}$ and
$V(z)\in\mathbb{F}_{q}[z]^{n\times n}$ such that

$S(z)=U(z)G(z)V(z)=\begin{pmatrix}\gamma_{1}(z)&&&&0&\cdots&0\\\
&\gamma_{2}(z)&&&0&\cdots&0\\\ &&\ddots&&\vdots&&\vdots\\\
&&&\gamma_{k}(z)&0&\cdots&0\end{pmatrix},$

where $(\gamma_{i}(z))_{i=1}^{k}$ are monic polynomials such that
$\gamma_{i+1}(z)|\gamma_{i}(z)$ for all $i=1,...,k-1$. $S(z)$ is called the
(unique) Smith form of $G(z)$.

The following result will be crucial in later sections to determine whether a
code is non-catastrophic.

######  Theorem 5.

[8, 17] Let $\mathcal{C}$ be an $(n,k)$convolutional code and
$G(z)\in\mathbb{F}_{q}[z]^{k\times n}$ its generator matrix. The following are
equivalent:

  * 1.

$\mathcal{C}$ is non-catastrophic;

  * 2.

$G(z)$ is left-prime;

  * 3.

the Smith form of $G(z)$ is $[I_{k}\ 0]$;

  * 4.

the column Hermite form of $G(z)$ is $[I_{k}\ 0]$;

  * 5.

the ideal generated by all the $k$-th minors of $G(z)$ is $\mathbb{F}_{q}[z]$;

  * 6.

there exists a parity-check matrix $H(z)$ of $\mathcal{C}$;

  * 7.

$G(z)$ can be completed to an unimodular matrix, e.g. there exists
$L(z)\in\mathbb{F}_{q}[z]^{(n-k)\times n}$ such that
$[\begin{smallmatrix}G(z)\\\ L(z)\end{smallmatrix}]$ is unimodular.

######  Corollary 2.

Let $G(z)$ be the generator matrix of a non-catastrophic $(n,k)$ convolutional
code. Then, for any unimodular $U(z)\in\mathbb{F}_{q}[z]^{k\times k}$ and
$V(z)\in\mathbb{F}_{q}[z]^{n\times n}$,

$U(z)G(z)V(z)$

also generates a non-catastrophic code. Or in other words, a non-catastrophic
code stays non-catastrophic under unimodular operations.

This corollary is due to the fact that the Smith normal form does not change
when multiplying it with unimodular matrices. It further shows that we may use
unimodular operations on a generator matrix to make it easier to determine
either of the properties presented in Theorem 5.

######  Definition 20.

For two matrices $G_{1}(z),G_{2}(z)\in\mathbb{F}_{q}[z]^{k\times n}$, we write

$G_{1}(z)\sim G_{2}(z),$

if there exist unimodular matrices $A(z)\in\mathbb{F}_{q}[z]^{k\times k}$ and
$B(z)\in\mathbb{F}_{q}[z]^{n\times n}$ such that

$G_{1}(z)=A(z)G_{2}(z)B(z).$

##  4 Self-Dual Convolutional Codes

In this section, we present the basic theory on self-dual convolutional codes.

######  Definition 21.

Let $\mathcal{C}$ be an $(n,k)$ convolutional codes. Then,

$\mathcal{C}^{\perp}=\left\\{f(z)\in R^{n}\ |\ f(z)c(z)^{\top}=0\ \ \ \forall
c(z)\in C\right\\}$

is called the dual of $\mathcal{C}$.

######  Lemma 3.

[13] The dual of a convolutional code $\mathcal{C}$ is also a convolutional
code.

######  Definition 22.

Two vectors $u(z),v(z)\in\mathbb{F}_{q}[z]^{n}$ are said to be orthogonal if

$u(z)v(z)^{\top}=0.$

###  4.1 Characterization of self-dual convolutional codes over arbitrary
finite fields

The following lemma establishes that the dual code always has a parity-check
matrix.

######  Lemma 4.

Let

$G(z)=\begin{pmatrix}\rule[2.15277pt]{10.76385pt}{0.5pt}&g_{1}(z)&\rule[2.15277pt]{10.76385pt}{0.5pt}\\\
&\vdots&\\\
\rule[2.15277pt]{10.76385pt}{0.5pt}&g_{k}(z)&\rule[2.15277pt]{10.76385pt}{0.5pt}\end{pmatrix}$

be the generator matrix of a convolutional code $\mathcal{C}$, then

$\mathcal{C}^{\perp}=ker(G(z))$

or equivalently $G(z)$ is a parity-check matrix of $\mathcal{C}^{\perp}$.

###### Proof.

To show $\mathcal{C}^{\perp}\subset ker(G(z))$, let
$c(z)\in\mathcal{C}^{\perp}$. One has $g_{i}(z)c(z)^{\top}=0$ for
$i=1,\ldots,k$ and therefore $G(z)c(z)^{\top}=0$, i.e., $c(z)\in ker(G(z))$.
To show $ker(G(z))\subset\mathcal{C}^{\perp}$, let $f(z)\in ker(G(z))$ and
$c(z)\in\mathcal{C}$. Then, $c(z)=m(z)G(z)$ for some
$m(z)\in\mathbb{F}_{q}[z]^{k}$. But now

$c(z)f(z)^{\top}=(m(z)G(z))f(z)^{\top}=m(z)(G(z)f(z)^{\top})=0$

as $f(z)$ is in the kernel of $G(z)$. We conclude that $f(z)$ is orthogonal to
every codeword of $\mathcal{C}$ or equivalently $f(z)\in\mathcal{C}^{\perp}$.
∎

Thus, any generator matrix of a convolutional code is a parity-check matrix of
the dual code. Consequently, the dual is always non-catastrophic by Theorem 5.

######  Lemma 5.

Let $\mathcal{C}$ be an $(n,k)$ convolutional code with generator matrix
$G(z)$. Then,

$\mathcal{C}\text{ is non-catastrophic}$

if and only if

$\mathcal{C}=(\mathcal{C}^{\perp})^{\perp}.$

###### Proof.

$(\Longrightarrow)$ Let $c(z)\in\mathcal{C}$ and
$c_{1}(z)\in\mathcal{C}^{\perp}$, then by definition $c_{1}(z)c(z)^{\top}=0$
and hence

$\mathcal{C}\subset(\mathcal{C}^{\perp})^{\perp}.$

As $(\mathcal{C}^{\perp})^{\perp}$ is again a convolutional code, it has a
generator matrix $\tilde{G}(z)$ with $rowspan(G(z))\subset
rowspan(\tilde{G}(z))$. Moreover,
$dim((\mathcal{C}^{\perp})^{\perp})=n-dim(\mathcal{C}^{\perp})=dim(\mathcal{C})=k$
and one obtains $U(z)\tilde{G}(z)=G(z)$ for some
$U(z)\in\mathbb{F}_{q}[z]^{k\times k}$. But $G(z)$ is left-prime, because we
assumed that $\mathcal{C}$ is non-catastrophic, and hence the left-factor
$U(z)$ is unimodular. We conclude that $G(z)$ and $\tilde{G}(z)$ are
equivalent and

$\mathcal{C}=(\mathcal{C}^{\perp})^{\perp}.$

$(\Longleftarrow)$ Follows directly from the previous lemma as
$\mathcal{C}=(\mathcal{C}^{\perp})^{\perp}$ is the dual of
$\mathcal{C}^{\perp}$. ∎

######  Definition 23.

We say that a convolutional code $\mathcal{C}$ is self-orthogonal if
$\mathcal{C}\subset\mathcal{C}^{\perp}$ and self-dual if
$\mathcal{C}=\mathcal{C}^{\perp}$.

The following lemma follows immediately.

######  Lemma 6.

Let $\mathcal{C}$ be a self-dual $(n,k)$ convolutional code with generator
matrix $G(z)$. Then, $\mathcal{C}$ is non-catastrophic.

Like for block codes, we may assume every self-dual convolutional code to be a
$(2k,k)$ or equivalently an $(n,n/2)$ code as stated in the following lemma.

######  Lemma 7.

[13] If $\mathcal{C}$ is a self-dual $(n,k)$ convolutional code, then $n=2k$.

In a next step, we will establish the main result of this chapter, which will
be used for determining whether a convolutional code is self-dual in later
sections.

######  Theorem 6.

Let $\mathcal{C}$ be a $(2k,k)$ convolutional code with generator matrix
$G(z)$, then the following statements are equivalent:

  * (i)

$\mathcal{C}$ is self-dual;

  * (ii)

$\mathcal{C}$ is non-catastrophic and self-orthogonal;

  * (iii)

$\mathcal{C}$ is non-catastrophic and $G(z)G(z)^{\top}=0$;

  * (iv)

$G(z)$ is a parity-check matrix of $\mathcal{C}$.

###### Proof.

$(i)\Rightarrow(ii)$ Let $\mathcal{C}$ be self-dual, then the code is self-
orthogonal by definition and non-catastrophic by Lemma 6.
$(ii)\Rightarrow(i)$ Let $\mathcal{C}$ be non-catastrophic and self-orthogonal
and let $H(z)$ be a generator matrix of $\mathcal{C}^{\perp}$.
$\mathcal{C}\subset\mathcal{C}^{\perp}$ implies $rowspan(G(z))\subset
rowspan(H(z))$ and hence $U(z)H(z)=G(z)$ for some
$U(z)\in\mathbb{F}_{q}[z]^{k\times k}$. We assumed $\mathcal{C}$ to be non-
catastrophic, i.e., $G(z)$ is left-prime and hence, $U(z)$ must be unimodular.
But this means that $G(z)$ and $H(z)$ are generator matrices of the same code
and $\mathcal{C}=\mathcal{C}^{\perp}.$
$(ii)\Rightarrow(iii)$ Let $\mathcal{C}$ be self-orthogonal with generator
matrix $G(z)$. Each pair of rows $g_{i}(z),g_{j}(z)$ of $G(z)$ is orthogonal,
i.e.,$g_{i}(z)g_{j}(z)^{\top}=0$ and $G(z)G(z)^{\top}=0$ follows.
$(iii)\Rightarrow(ii)$ Let $\mathcal{C}$ fulfil $G(z)G(z)^{\top}=0$. Take
$c_{1}(z),c_{2}(z)\in\mathcal{C}$, then there exist
$m_{1}(z),m_{2}(z)\in\mathbb{F}_{q}[z]^{k}$ such that

$\begin{array}[]{cc}c_{1}(z)&=m_{1}(z)G(z)\\\
c_{2}(z)&=m_{2}(z)G(z)\end{array}.$

But now $c_{1}(z)c_{2}(z)^{\top}=m_{1}(z)(G(z)G(z)^{\top})m_{2}(z)^{\top}=0$
and therefore each pair of codewords is orthogonal or equivalently
$\mathcal{C}$ is self-orthogonal.
$(i)\Longrightarrow(iv)$ By assumption, $\mathcal{C}=\mathcal{C}^{\perp}$ and
by Lemma 4,

$\mathcal{C}^{\perp}=ker(G(z)),$

making $G(z)$ a parity check matrix of $\mathcal{C}$.

$(iv)\Longrightarrow(ii)$ Let $G(z)$ be a parity-check of $\mathcal{C}$, then
$\mathcal{C}$ is non-catastrophic and $G(z)G(z)^{\top}=0$, because
$rowspan(G(z))=\mathcal{C}=ker(G(z))$. ∎

One might observe that self-orthogonality and $G(z)G(z)^{\top}=0$ are
equivalent statements as the assumption of the code being non-catastrophic was
not used in the proof of $(ii)\Longleftrightarrow(iii)$.

For $(2k,k)$ linear block codes, self-duality and self-orthogonality are
equivalent properties, which is due to the fact that each linear block code
possesses a parity-check matrix. For $(2k,k)$ convolutional codes however,
this is not necessarily true as illustrated in the following example.

######  Example 1.

Let

$G(z)=\begin{pmatrix}z^{2}+z+1&z^{2}&z&1\\\
1&z&z^{2}&z^{2}+z+1\end{pmatrix}\in\mathbb{F}_{2}[z]^{2\times 4}$

be the generator matrix of a binary $(4,2)$ convolutional code $\mathcal{C}$.
We want to show that $\mathcal{C}=rowspan(G(z))$ is a proper subset of
$\mathcal{C}^{\perp}=ker(G(z))$.
As $G(z)G(z)^{\top}=0$, $\mathcal{C}\subset\mathcal{C}^{\perp}.$ Moreover, we
observe that $(1,1,1,1)\in\mathcal{C}^{\perp}$ but
$(1,1,1,1)\not\in\mathcal{C}$, which shows that $\mathcal{C}$ is indeed a
proper subset of $\mathcal{C}^{\perp}$.
Conclusively, $\mathcal{C}$ is a self-orthogonal $(2k,k)$ convolutional codes
that is not self-dual. As a consequence of Theorem 6, $\mathcal{C}$ must be a
catastrophic code.

###  4.2 Special properties of binary self-dual convolutional codes

In this subsection, we present some further results for binary self-dual
convolutional codes.

The following well-known lemma is an immediate consequence of the "Freshman
dream" and helps us to determine whether a binary polynomial vector is
orthogonal to itself.

######  Lemma 8.

Let $f_{i}(z)\in\mathbb{F}_{2}[z]$, for $i\in\left\\{1,\ldots,m\right\\}$, and
$f(z)=(f_{1}(z),\ldots,f_{m}(z))$, then

$f(z)f(z)^{\top}=(f(z)(1,\ldots,1)^{\top})^{2}.$

As a consequence, to determine whether a binary polynomial vector is
orthogonal to itself, we may just check if the sum of its entries is equal to
zero.

######  Lemma 9.

All codewords of a binary self-dual code have even weight.

###### Proof.

Let $c(z)=\sum_{i=0}^{l}c_{i}z^{i}$ be a codeword of a binary self-dual
$(n,k)$ convolutional code, where $l={deg(c(z))}$ and
$c_{i}\in\mathbb{F}_{2}^{n}$. By definition of self-duality, one obtains
$c(z)c(z)^{\top}=0$. It follows from Lemma 8 that $c(z)(1,\ldots,1)^{\top}=0$
or equivalently

$\sum_{i=0}^{l}c_{i}z^{i}(1,\ldots,1)^{\top}=\sum_{i=0}^{l}z^{i}c_{i}(1,\ldots,1)^{\top}=0.$

Every coefficient of the last sum must be equal to zero, i.e.

$c_{i}(1,\ldots,1)^{\top}=0$

must hold for every $i\in\\{0,\ldots,l\\}$ and hence $wt(c_{i})$ is even. But
then

$wt(c(z))=\sum_{i=0}^{l}wt(c_{i})$

is also even. ∎

In [16], the following result was proven for block codes. Up to our knowledge
it has not been proven for convolutional codes yet.

######  Lemma 10.

Every binary self-dual convolutional code contains
$(1,\ldots,1)\in\mathbb{F}_{2}^{n}$.

###### Proof.

Let $g_{i}(z)$ be a row of the generator matrix $G(z)$, then
$g_{i}(z)g_{i}(z)^{\top}=0$ or equivalently (Lemma 8),
$g_{i}(z)(1,\ldots,1)^{\top}=0$ and therefore $G(z)(1,\ldots,1)^{\top}=0$.
Hence $(1,\ldots,1)$ is contained in the dual of the code and, because of
self-duality, contained in the code itself. ∎

######  Corollary 3.

Let $\mathcal{C}$ be a binary self-dual $(n,k)$ convolutional code, then there
exists a generator matrix whose first row is the all one vector.

This generator matrix with just ones in the first row is equivalent to its row
Hermite form. Therefore, to find all binary self-dual convolutional codes, we
may characterize them via generator matrices that have a first row of just
ones and are in row Hermite form.

######  Remark 2.

Let

$G(z)=\begin{pmatrix}1&1&1&1&\cdots&\cdots&1\\\
0&g_{22}(z)&g_{23}(z)&g_{24}(z)&\cdots&\cdots&g_{2n}(z)\\\
\vdots&0&g_{33}(z)&g_{34}(z)&\cdots&\cdots&g_{3n}(z)\\\
\vdots&\vdots&\ddots&\ddots&\ddots&&\vdots\\\
0&0&\cdots&0&g_{kk}(z)&\cdots&g_{kn}(z)\end{pmatrix}$

be a generator matrix of a self-dual code in the just discussed form. Then we
choose this form of $G(z)$ as the representative of any binary self-dual
convolutional code for our classifications.

Multiplying the generator matrix of a self-dual code with a unimodular matrix
from the left-hand side leaves the code unchanged and therefore leaves the
code self-dual. Obviously, exchanging columns has also no influence on self-
duality since it only results in renumbering the components of the codewords.
However, the following example shows that multiplying a column with a constant
or adding columns does not preserve self-duality.

######  Example 2.

We claim that

$G(z)=\begin{pmatrix}3&z&1&3z\\\
1&2z+4&2&z+2\end{pmatrix}\in\mathbb{F}_{5}[z]^{2\times 4}$

generates a self-dual code and will use Theorem 6 to proof this. Firstly,

$G(z)G(z)^{\top}=\begin{pmatrix}10z^{2}+10&5z^{2}+10z+5\\\
5z^{2}+10z+5&5z^{2}+20z+25\end{pmatrix}=0$

and secondly

$det\left[\begin{pmatrix}3&z\\\ 1&2z+4\end{pmatrix}\right]=6z+12-z=2,$

which implies that the set of $G(z)$‘s full-size minors generates
$\mathbb{F}_{5}[z]$ or equivalently $G(z)$ generates a non-catastrophic code.
Hence, the code is self-dual.
We now want to establish that adding and multiplying columns might change this
property. For this, add the second column of $G(z)$ to the first to find

$\begin{pmatrix}3&z&1&3z\\\
1&2z+4&2&z+2\end{pmatrix}\sim\begin{pmatrix}3+z&z&1&3z\\\
2z&2z+4&2&z+2\end{pmatrix}=:G_{1}(z).$

Then the first row of $G_{1}(z)$ is not orthogonal to itself as

$(3+z,z,1,3z)(3+z,z,1,3z)^{\top}=9+6z+z^{2}+z^{2}+1+9z^{2}=z^{2}+z\neq 0,$

meaning that $G_{1}(z)$ does not generate a self-dual code.
Similarly, if we multiply the first column of $G(z)$ by $2$ we find

$\begin{pmatrix}3&z&1&3z\\\
1&2z+4&2&z+2\end{pmatrix}\sim\begin{pmatrix}1&z&1&3z\\\
2&2z+4&2&z+2\end{pmatrix}$

and again the first row is not orthogonal to itself as

$(1,z,1,3z)(1,z,1,3z)^{\top}=1+z^{2}+1+9z^{2}=2\neq 0.$

##  5 Classification of Self-Dual Convolutional Codes

In this section, we will classify all self-dual $(2,1)$ convolutional codes
over finite fields and all binary self-dual $(4,2)$ convolutional codes. We
will further classify all self-dual convolutional codes with double diagonal
matrices over finite fields and all binary self-dual convolutional codes with
double upper triangular generator matrices.

###  5.1 Self-Dual (2,1) Convolutional Codes

In this subsection, we consider $\mathbb{F}_{q}[z]$, where $q=p^{l}$ is a
prime power.

######  Theorem 7.

The self-dual $(2,1)$ convolutional codes are exactly the $(2,1)$ self-dual
block codes. In particular, these are exactly the codes with a generator
matrix of the form $(a\ b)$ where $a^{2}=-b^{2}$ in $\mathbb{F}_{q}$. Clearly,
such a generator matrix exists if and only if $-1$ is a square in
$\mathbb{F}_{q}$, i.e., for $p\equiv 1\mod 4$, $p=2$ or $l$ even.

###### Proof.

Denote by $G(z)=(g_{1}(z),g_{2}(z))\in\mathbb{F}_{q}[z]^{1\times 2}$ a
generator matrix of a self-dual $(2,1)$ convolutional code $\mathcal{C}$. By
Theorem 6, the code is self-dual if and only if $g_{1}(z)^{2}+g_{2}(z)^{2}=0$
and it is non-catastrophic. However, such a code is non-catastrophic if and
only if $g_{1}(z)$ and $g_{2}(z)$ are coprime, which can only be fulfilled
together with $g_{1}(z)^{2}=-g_{2}(z)^{2}$ if $g_{1}(z)$ and $g_{2}(z)$ are
constant. ∎

###  5.2 Binary Self-Dual (4,2) Convolutional Codes

The goal in this section is to find all binary self-dual $(4,2)$ convolutional
codes $\mathcal{C}$ classified by their representative as defined in Remark
3.3.16., i.e., we may assume that

$G(z)=\begin{pmatrix}1&1&1&1\\\
0&g_{22}(z)&g_{23}(z)&g_{24}(z)\end{pmatrix}\in\mathbb{F}_{2}[z]^{2\times 4}$

is a generator matrix of $\mathcal{C}$ for some
$g_{22}(z),g_{23}(z),g_{24}(z)\in\mathbb{F}_{2}[z]$. $G(z)G(z)^{\top}=0$ tells
us that $g_{22}(z)^{2}+g_{23}(z)^{2}+g_{24}(z)^{2}=0$ or equivalently (by
Lemma 8),

$g_{22}(z)+g_{23}(z)+g_{24}(z)=0.$ (1)

Moreover, $\mathcal{C}$ is non-catastrophic if and only if the elements of the
set of $2$-nd minors
$M=\left\\{g_{22}(z),g_{23}(z),g_{24}(z),g_{22}(z)+g_{23}(z),g_{22}(z)+g_{24}(z),g_{23}(z)+g_{24}(z)\right\\}$
of $G(z)$ are coprime, i.e., $gcd(g_{22}(z),g_{23}(z),g_{24}(z))=1$. Using
$\eqref{1}$ this simplifies to $gcd(g_{23}(z),g_{24}(z))=1.$
We conclude that for $g_{23}(z),g_{24}(z)\in\mathbb{F}_{2}[z]$ such that
$gcd(g_{23}(z),g_{24}(z))=1$,

$G(z)=\begin{pmatrix}1&1&1&1\\\
0&g_{23}(z)+g_{24}(z)&g_{23}(z)&g_{24}(z)\end{pmatrix}$

generates a binary self-dual $(4,2)$ convolutional code and that every binary
self-dual $(4,2)$ convolutional code has a generator matrix of this form.

###  5.3 Double Diagonal Generator Matrix

In this subsection, we want to find all self-dual convolutional codes with
generator matrices of the form

$G(z)=\begin{pmatrix}g_{1,1}(z)&&&&g_{1,{k+1}}(z)&&&\\\
&g_{2,2}(z)&&&&g_{2,{k+1}}(z)&&\\\ &&\ddots&&&&\ddots&\\\
&&&g_{k,k}(z)&&&&g_{k,{2k}}(z)\end{pmatrix}\in\mathbb{F}_{q}^{k\times 2k}.$

Let $i\in\left\\{1,...,k\right\\}$. Self-orthogonality is equivalent to
$g_{i,i}(z)^{2}+g_{i,{k+i}}(z)^{2}=0$ and non-catastrophicity is equivalent to
$\gcd(g_{i,i}(z),g_{i,k+i}(z))=1$.
As in Theorem 7, one concludes that

$G(z)=\begin{pmatrix}a_{1}&&&&b_{1}&&&\\\ &a_{2}&&&&b_{2}&&\\\
&&\ddots&&&&\ddots&\\\
&&&a_{k}&&&&b_{k}\end{pmatrix}\in\mathbb{F}_{q}^{k\times 2k},$

where $a_{i},b_{i}\in\mathbb{F}_{q}^{*}$ such that $a_{i}^{2}=-b_{i}^{2}$ in
$\mathbb{F}_{q}$. Therefore, self-dual convolutional codes of this form exist
for exactly the same field sizes as $(2,1)$ self-dual block codes.

###  5.4 Double Upper Triangular Generator Matrices

Let $\mathcal{C}$ be a binary self-dual $(2k,k)$ convolutional code with a
generator matrix $G(z)$ of the form

$G(z)=\begin{pmatrix}g_{1,1}&\cdots&\cdots&g_{1,k}&g_{1,{k+1}}&g_{1,{k+2}}&\cdots&g_{1,{2k}}\\\
&g_{2,2}&\cdots&g_{2,k}&&g_{2,{k+2}}&\cdots&g_{2,{2k}}\\\
&&\ddots&\vdots&&&\ddots&\vdots\\\
&&&g_{k,k}&&&&g_{k,{2k}}\end{pmatrix}\in\mathbb{F}_{2}[z]^{k\times 2k}.$

For simplicity we did and will write $g_{i,j}$ instead of $g_{i,j}(z)$. We
want to show that

$\begin{pmatrix}1&&&&1&&&\\\ &1&&&&1&&\\\ &&\ddots&&&&\ddots&\\\
&&&1&&&&1\end{pmatrix}$

is also a generator matrix of $\mathcal{C}$. Let $g_{i}$ be the $i$-th row of
$G(z)$, then $g_{k}g_{i}^{\top}=0$ for $i\in\left\\{1,\ldots,k\right\\}$ leads
to

$\begin{array}[]{ccc}g_{k,k}&=&g_{k,{2k}},\\\
g_{k,k}g_{i,k}+g_{k,{2k}}g_{i,2k}&=&g_{k,k}(g_{i,k}+g_{i,2k})=0.\\\
\end{array}$

$g_{k,k}$ is non-zero (as $rank(G(z))=k$) and hence $g_{i,k}=g_{i,2k}$.
Moreover, $g_{k,k}$ is a common factor of every $k$-th minor of $G(z)$ and
hence must be equal to $1$ because the code is non-catastrophic. Therefore,

$G(z)=\begin{pmatrix}g_{1,1}&g_{1,2}&\cdots&\cdots&g_{1,k}&g_{1,k+1}&g_{1,{k+2}}&\cdots&\cdots&g_{1,k}\\\
&g_{2,2}&g_{2,3}&\cdots&g_{2,k}&&g_{2,k+2}&g_{2,k+3}&\cdots&g_{2,k}\\\
&&\ddots&\ddots&\vdots&&&\ddots&\vdots\\\
&&&g_{k-1,k-1}&g_{k-1,k}&&&&g_{k-1,2k-1}&g_{k-1,k}\\\
&&&&1&&&&&1\end{pmatrix}.$

Furthermore, $G(z)$ is equivalent to

$\tilde{G}(z)=\begin{pmatrix}g_{1,1}&g_{1,2}&\cdots&g_{1,k-1}&0&g_{1,k+1}&g_{1,{k+2}}&\cdots&g_{1,2k-1}&0\\\
&g_{2,2}&\cdots&g_{2,k-1}&0&&g_{2,k+2}&\cdots&g_{2,2k-1}&0\\\
&&\ddots&&\vdots&&&\ddots&\vdots\\\ &&&g_{k-1,k-1}&0&&&&g_{k-1,2k-1}&0\\\
&&&&1&&&&&1\end{pmatrix}$

by adding the $k$-th row times $g_{i,k}$ to the $i$-th row for
$i\in\left\\{1,\ldots,k-1\right\\}$. Let $\tilde{g_{i}}$ be the $i$-th row of
$\tilde{G}(z)$. Similarly to before, from
$\tilde{g_{i}}\tilde{g}_{k-1}^{\top}$ for $i\in\left\\{1,...,k-1\right\\}$, we
get

$\begin{array}[]{ccc}g_{k-1,k-1}&=&g_{k-1,{2k-1}}\\\
g_{k-1,k-1}(g_{i,k-1}+g_{i,2k-1})&=&0\\\ \end{array}.$

Hence, using the same argument as before we get that $\tilde{G}(z)$ is
equivalent to

$\begin{pmatrix}g_{1,1}&\cdots&g_{1,k-2}&0&0&g_{1,k+1}&\cdots&g_{1,2k-2}&0&0\\\
&\ddots&\vdots&\vdots&\vdots&&\ddots&\vdots&\vdots&\vdots\\\
&&g_{k-2,k-2}&0&0&&&g_{k-2,2k-2}&0&0\\\ &&&1&0&&&&1&0\\\
&&&&1&&&&&1\end{pmatrix}.$

Repeating this reasoning, we find that every double upper triangle generator
matrix of a binary self-dual code is equivalent to

$G^{\prime}(z)=\begin{pmatrix}1&&&&1&&&\\\ &1&&&&1&&\\\ &&\ddots&&&&\ddots&\\\
&&&1&&&&1\end{pmatrix}.$

Conclusively, there exists exactly one binary self-dual $(2k,k)$ convolutional
code that has a double triangular generator matrix, namely
$\mathcal{C}=rowspan(G^{\prime}(z))$.

##  6 Construction of Self-Dual Convolutional Codes

In this section, we will generalize known construction methods for block codes
to construction methods for convolutional codes and will present examples for
binary self-dual convolutional codes of different lengths, dimensions and
degrees. We will consider constructions, where already known self-dual
convolutional codes are used to find new ones. The first three results are
true over any polynomial ring over a general finite field and the rest only
over the polynomial ring over the binary field.

######  Proposition 1.

If $G(z)\in\mathbb{F}_{q}[z]^{k\times n}$ and
$\tilde{G}(z)\in\mathbb{F}_{q}[z]^{k^{\prime}\times n^{\prime}}$ are generator
matrices of two self-dual convolutional codes, then the code
$\mathcal{C}^{\prime}$ generated by

$G^{\prime}(z)=\begin{pmatrix}G(z)&0\\\
0&\tilde{G}(z)\end{pmatrix}\in\mathbb{F}_{q}[z]^{(k+k^{\prime})\times(n+n^{\prime})}$

is also self-dual.

###### Proof.

We first compute the Smith normal form of $G^{\prime}(z)$:

$G^{\prime}(z)=\begin{pmatrix}G(z)&0\\\
0&\tilde{G}(z)\end{pmatrix}\sim\begin{pmatrix}[I_{k}\ 0]&0\\\
0&[I_{k^{\prime}}\
0]\end{pmatrix}\sim\begin{pmatrix}I_{k+k^{\prime}}&0\end{pmatrix},$

where the first equivalence follows from $G(z)$ and $\tilde{G}(z)$ generating
non-catastrophic codes. It follows that also $\mathcal{C}^{\prime}$ is non-
catastrophic. Finally

$G^{\prime}(z)G^{\prime}(z)^{\top}=\begin{pmatrix}G(z)&0\\\
0&\tilde{G}(z)\end{pmatrix}\begin{pmatrix}G(z)&0\\\
0&\tilde{G}(z)\end{pmatrix}^{\top}=\begin{pmatrix}G(z)G(z)^{\top}&0\\\
0&\tilde{G(}z)\tilde{G}(z)^{\top}\end{pmatrix}=0$

and the result follows with Theorem 6. ∎

The following proposition is a generalisation of a result presented in [3].

######  Proposition 2.

Let $\mathcal{C}\subset\mathbb{F}_{q}[z]^{n}$ be a self-dual convolutional
code with generator matrix $G(z)$. Let $r\in\mathbb{N}$ and for
$i=1,\ldots,n$, let $M_{i}(z)\in\mathbb{F}_{q}[z]^{n\times n}$ be such that

$M_{i}(z)M_{i}(z)^{\top}=\lambda_{i}I_{n}$

for $\lambda_{i}$ invertible in $\mathbb{F}_{q}[z]$. Let $A_{1},\ldots,A_{r}$
be $n\times n$ permutations matrices. Then

$G_{r}(z)=G(z)M_{1}(z)A_{1}\cdots M_{r}(z)A_{r}$

generates a self-dual code.

###### Proof.

The idea of the proof is similar to that of [3, Prop. 3.1].
We know that $G(z)$ has Smith form $[I_{k}\ 0]$ and $M_{i}(z)$ is unimodular
as

$M_{i}(z)(\lambda_{i}^{-1}M_{i}^{\top}(z))=\lambda_{i}^{-1}(M_{i}(z)M_{i}^{\top}(z))=\lambda_{i}^{-1}\lambda_{i}I_{n}=I_{n}.$

Therefore also $G(z)M_{1}(z)$ has Smith form $[I_{k}\ 0]$. By definition, the
$A_{i}$‘s are also unimodular, implying that

$G_{r}(z)=G(z)M_{1}(z)A_{1}\cdots M_{r}(z)A_{r}$

has Smith form $[I_{k}\ 0]$ as well, which lets us conclude with Theorem 5
that $G_{r}(z)$ generates a non-catastrophic code. Finally due to
$A_{i}A_{i}^{\top}=I_{n}$, we find

$\displaystyle G_{r}(z)G_{r}(z)^{\top}$ $\displaystyle=G(z)M_{1}(z)A_{1}\cdots
M_{r}(z)(A_{r}A_{r}^{\top})M_{r}(z)^{\top}\cdots
A_{1}^{\top}M_{1}(z)^{\top}G(z)^{\top}$
$\displaystyle=\lambda_{1}\lambda_{2}\cdots\lambda_{r}G(z)G(z)^{\top}=0.$

Hence, with Theorem 6 we can conclude that $G_{r}(z)$ generates a self-dual
convolutional code. ∎

In Section 2.2, two construction methods for binary self-dual block codes were
introduced in the building-up and Harada-Munemasa construction. We will
discuss in the following pages, how they are best implemented for
convolutional codes and which interesting properties their generalisations
possess.

At first, we will consider the building-up construction, which we not only
generalize from block to convolutional codes but also from binary fields to
any finite field that has the property that $-1$ is a square in this field.

######  Proposition 3 (Generalized Building-up construction).

Let $G(z)$ be a generator matrix of a self-dual $(2k,k)$ convolutional code
$\mathcal{C}$ over $\mathbb{F}_{q}[z]$. Let $q=p^{l}$, where $p=3\ mod\ 4$ and
$l$ being odd does not hold simultaneously. Further, let $a^{2}+b^{2}=0\ mod\
p$ for some $a,b\in\mathbb{F}_{q}^{*}$, $f(z)\in\mathbb{F}_{q}[z]^{2k}$ with
$f(z)f(z)^{T}=-(a^{-1})^{2}$ and define $y_{i}(z):=f(z)g_{i}(z)^{T}$ for
$1\leq i\leq k$. Then

$\tilde{G}(z)=\begin{pmatrix}-a^{-1}&0&f(z)\\\ ay_{1}(z)&by_{1}(z)&\\\
\vdots&\vdots&G(z)\\\
ay_{k}(z)&by_{k}(z)&\end{pmatrix}\in\mathbb{F}_{q}[z]^{(k+1)\times(2k+2)}$

generates a self-dual $(2k+2,k+1)$ convolutional code $\tilde{\mathcal{C}}$.

###### Proof.

According to Theorem 6, we have to show that $\tilde{G}(z)$ generates a non-
catastrophic code and that $\tilde{G}(z)\tilde{G}(z)^{\top}=0$. Computing the
Smith form of $\tilde{G}(z)$ and using that $G(z)$ has column Hermite form
$[I_{k}\ 0]$ yields

$\displaystyle\tilde{G}(z)$ $\displaystyle=\begin{pmatrix}-a^{-1}&0&f(z)\\\
ay_{1}(z)&by_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
ay_{k}(z)&by_{k}(z)&\end{pmatrix}\sim\begin{pmatrix}-a^{-1}&0&f(z)\\\
0&by_{1}(z)&\\\ \vdots&\vdots&G(z)\\\ 0&by_{k}(z)&\end{pmatrix}$
$\displaystyle\sim\begin{pmatrix}1&0&0\\\ 0&by_{1}(z)&\\\
\vdots&\vdots&G(z)\\\ 0&by_{k}(z)&\end{pmatrix}\sim[I_{k+1}\ 0].$

Applying Theorem 5 we obtain that $\tilde{G}(z)$ generates a non-catastrophic
code. Let $\tilde{g}_{i}(z)$ be the $i$-th row of $\tilde{G}(z)$ and
$g_{i}(z)$ be the $i$-th row of $G(z)$. To see that $\tilde{\mathcal{C}}$ is
self-dual, we compute

$\displaystyle\tilde{g}_{1}(z)\tilde{g}_{1}(z)^{\top}$
$\displaystyle=(-a^{-1})^{2}+f(z)f(z)^{\top}=(a^{-1})^{2}-(a^{-1})^{2}=0$
$\displaystyle\tilde{g}_{1}(z)\tilde{g}_{i}(z)^{\top}$
$\displaystyle=-a^{-1}ay_{i}(z)+f(z)g_{i}(z)=-y_{i}(z)+y_{i}(z)=0$
$\displaystyle\tilde{g}_{i+1}(z)\tilde{g}_{j+1}(z)^{\top}$
$\displaystyle=a^{2}y_{i}(z)y_{j}(z)+b^{2}y_{i}(z)y_{j}(z)+g_{i}(z)g_{j}(z)^{\top}=g_{i}(z)g_{j}(z)^{\top}=0$

∎

######  Remark 3.

If we set $p=2$ in the preceding theorem, one has $a=b=1$ and obtains a
straightforward generalization of Theorem 1.

######  Example 3.

From Section 5.2, we know that

$G_{1}(z)=\begin{pmatrix}1&1&1&1\\\ 0&1&z+1&z\end{pmatrix}$

generates a binary self-dual convolutional code. We apply the generalized
building-up construction with
$f(z)=(1,z,z^{2},z^{2}+z)\in\mathbb{F}_{2}[z]^{4}$.
The condition of $f(z)f(z)^{\top}=a=1$ is fulfilled and

$\displaystyle y_{1}(z)=f(z)(1,1,1,1)^{\top}=1,\qquad
y_{2}(z)=f(z)(0,1,z+1,z)^{\top}=z.$

Therefore

$G_{2}(z)=\begin{pmatrix}1&0&\rule[2.15277pt]{10.76385pt}{0.5pt}&f(z)&\rule[2.15277pt]{10.76385pt}{0.5pt}&\rule[2.15277pt]{10.76385pt}{0.5pt}\\\
y_{1}(z)&y_{1}(z)&1&1&1&1\\\
y_{2}(z)&y_{2}(z)&0&1&z+1&z\end{pmatrix}=\begin{pmatrix}1&0&1&z&z^{2}&z^{2}+z\\\
1&1&1&1&1&1\\\ z&z&0&1&z+1&z\end{pmatrix}$

generates a binary self-dual convolutional code.

Next we show that Theorem 2 cannot be generalized to convolutional codes.

######  Lemma 11.

Not every binary self-dual convolutional code with free distance $d_{free}>2$
can be constructed with the generalized building-up construction (up to
permutation of columns).

###### Proof.

By Section 5.2,

$G(z)=\begin{pmatrix}0&z^{2}+z+1&z&z^{2}+1\\\
1&1&1&1\end{pmatrix}\in\mathbb{F}_{2}[z]^{2\times 4}$

generates a binary self-dual convolutional code.
We claim that $G(z)$ cannot be constructed with the generalized building-up
construction, because every codeword of the corresponding code $\mathcal{C}$
has the property that if one of its entries is equal to $0$, then none of its
entries can be equal to $1$.
To see this, assume that for some $a(z),b(z)\in\mathbb{F}_{2}[z]$,

$c(z)=a(z)(1,1,1,1)+b(z)(0,z^{2}+z+1,z,z^{2}+1)$

has one entry that is equal to $0$. This implies $a(z)=b(z)d(z)$ for some
$d(z)\in\\{0,z^{2}+z+1,z,z^{2}+1\\}$ and hence, $\gcd(a(z),b(z))=a(z)\neq 1$.
Consequently, $a(z)+b(z)d(z)\neq 1$ (by the Lemma of Bezout).
We conclude that there is no codeword that has a entry equal to $0$ as well as
a entry equal to $1$, meaning that the top-left $(1\;0)$ in the building-up
construction can never be achieved by row operations or column permutations on
$G(z)$. Hence, $\mathcal{C}$ cannot be constructed with the generalized
building-up construction.
It remains to show that $d_{free}(\mathcal{C})>2$. As a consequence of Lemma
9, every binary self-dual code has an even free distance and as the free
distance is non-zero, we just need to show that there is no codeword of weight
$2$.
Assume conversely that there exists
$c(z)=(c_{1}(z),c_{2}(z),c_{3}(z),c_{4}(z))\in\mathcal{C}$ with $wt(c(z))=2$
and write

$\displaystyle c(z$ $\displaystyle)=a(z)(1,1,1,1)+b(z)(0,z^{2}+z+1,z,z^{2}+1)$
$\displaystyle=(a(z),\ a(z)+(z^{2}+z+1)b(z),\ a(z)+zb(z),\
a(z)+(z^{2}+1)b(z)).$

If $a(z)=0$ and $b(z)=0$, then $wt(c(z))=0$ and if $a(z)=0$ and $b(z)\neq 0$,
then $wt(c(z))\geq 3$, i.e. both of these cases lead to a contradiction.

Hence $a(z)\neq 0$. If $b(z)=0$, $wt(c(z))=4\cdot wt(a(z))\geq 4$, i.e.
$b(z)\neq 0$. But this implies that only one of the entries
$c_{2}(z),c_{3}(z),c_{4}(z)$ can be zero, i.e., $wt(c(z))\geq 3$, again a
contradiction. We conclude that $\mathcal{C}$ has free distance $d_{free}>2$
and cannot be constructed with the generalized building-up construction. ∎

As a consequence, the full classification of (binary) self-dual convolutional
codes cannot be done by using the generalized building-up construction. In the
following, we will investigate generalizations of the Harada-Munemasa
construction.

######  Proposition 4.

Let $G(z)\in\mathbb{F}_{2}[z]^{k\times 2k}$ be a generator matrix of a binary
self-dual $(2k,k)$ convolutional code and $a_{i}(z)\in\mathbb{F}_{2}[z]$, for
$i\in\left\\{1,\ldots,k\right\\}$. Then

$\tilde{G}(z)=\begin{pmatrix}a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
a_{k}(z)&a_{k}(z)&\end{pmatrix}\in\mathbb{F}_{2}[z]^{k\times(2k+2)}$

generates a binary self-orthogonal convolutional code $\tilde{\mathcal{C}}$.

###### Proof.

Let $g_{i}(z),g_{j}(z)$ be any two rows of $G(z)$ and $\tilde{g_{i}}(z)$ and
$\tilde{g_{j}}(z)$ be the two corresponding rows of $\tilde{G}(z)$. Then

$\tilde{g_{i}}(z)\tilde{g_{j}}(z)^{\top}=a_{i}(z)a_{j}(z)+a_{i}(z)a_{j}(z)+g_{i}(z)g_{j}(z)^{\top}=g_{i}(z)g_{j}(z)^{\top}=0.$

∎

######  Definition 24.

Let $G(z)\in\mathbb{F}_{2}[z]^{k\times 2k}$ be a generator matrix of a binary
self-dual $(2k,k)$ convolutional code and for some
$a_{i}(z)\in\mathbb{F}_{2}[z]$

$\tilde{G}(z)=\begin{pmatrix}a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
a_{k}(z)&a_{k}(z)&\end{pmatrix}\in\mathbb{F}_{2}[z]^{k\times(2k+2)}$

like in Proposition 4. If there exists $f(z)\in\mathbb{F}_{2}[z]^{2k+2}$ such
that

$G_{1}(z)=\begin{pmatrix}\rule[2.15277pt]{10.76385pt}{0.5pt}&f(z)&\rule[2.15277pt]{10.76385pt}{0.5pt}\\\
a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\ a_{k}(z)&a_{k}(z)&\\\
\end{pmatrix}\in\mathbb{F}_{2}[z]^{(k+1)\times(2k+2)}$

generates a self-dual code, then we say that $G_{1}(z)$ is a self-dual
completion or just a completion of $\tilde{G}(z)$.

Naturally, we want to figure out when and how a self-dual completion can be
found.

######  Lemma 12.

Choosing $f(z)=(1,1,0,\ldots,0)$ in Definition 24 leads to a generator matrix
of a self-dual code. More concretely,

$G_{1}(z)=\begin{pmatrix}1&1&0\\\ a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
a_{k}(z)&a_{k}(z)&\\\ \end{pmatrix}\in\mathbb{F}_{2}[z]^{(k+1)\times(2k+2)}$

is a self-dual completion for any $a_{i}(z)\in\mathbb{F}_{2}[z]$.

###### Proof.

Obviously, $G_{1}(z)$ and

$G_{2}(z)=\begin{pmatrix}1&1&0\\\ 0&0&\\\ \vdots&\vdots&G(z)\\\
0&0&\end{pmatrix}$

generate the same code, making the choice of the $a_{i}(z)$ pointless. But
still

$G_{2}(z)G_{2}(z)^{\top}=0$

and

$G_{2}(z)\sim[I_{k+1}\ 0],$

implying that the code generated by $G_{2}(z)$ is self-dual. ∎

Because of the preceding lemma we make the following definition.

######  Definition 25.

Let

$G_{1}(z)=\begin{pmatrix}\rule[2.15277pt]{10.76385pt}{0.5pt}&f(z)&\rule[2.15277pt]{10.76385pt}{0.5pt}\\\
a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
a_{k}(z)&a_{k}(z)&\end{pmatrix}\in\mathbb{F}_{2}[z]^{(k+1)\times(2k+2)}$

be a self-dual completion. Then we say that the completion was trivial if
$G_{1}(z)$ and

$\begin{pmatrix}1&1&0\\\ a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
a_{k}(z)&a_{k}(z)&\end{pmatrix}\in\mathbb{F}_{2}[z]^{(k+1)\times(2k+2)}$

generate the same code. If they do not, we call the completion non-trivial.

######  Remark 4.

An important observation here is that $(1,1,0,\ldots,0)$ can never be a linear
combination of the last $k$ rows of $G_{1}(z)$, because the rows of $G(z)$ are
linearly independent.

In the following example, we demonstrate how the choice of the $a_{i}(z)$
affects the existence of non-trivial self-dual completions.

######  Example 4.

We know that $(1\;1)$ is a binary self-dual $(2,1)$ convolutional code
(actually the only one). We implement the Harada-Munemasa construction for
$a_{1}(z)=z$ and show that for this choice of $a_{1}(z)$, there are only
trivial self-dual completions. By Proposition 4,
$\begin{pmatrix}z&z&1&1\end{pmatrix}$ generates a self-orthogonal code. We are
now looking for $f(z)=(f_{1},f_{2},f_{3},f_{4})\in\mathbb{F}_{2}[z]^{4}$ such
that

$G(z)=\begin{pmatrix}f_{1}&f_{2}&f_{3}&f_{4}\\\ z&z&1&1\end{pmatrix}$

generates a self-dual code $\mathcal{C}$. By Lemma 10, the all one vector must
be part of the code. Therefore, there is
$b(z)=(b_{1},b_{2})\in\mathbb{F}_{2}[z]^{2}$ such that

$b(z)G(z)=(1,1,1,1).$

Notice that necessarily $b_{1}\neq 0$. This translates into the following
system of equations over $\mathbb{F}_{2}[z]$

$\begin{array}[]{ccc}b_{1}f_{1}+zb_{2}&=&1\\\ b_{1}f_{2}+zb_{2}&=&1\\\
b_{1}f_{3}+b_{2}&=&1\\\ b_{1}f_{4}+b_{2}&=&1\end{array}.$

Since $b_{1}\neq 0$, by adding the last two equations we find that
$f_{4}=f_{3}$ and the last equation is equivalent to

$b_{2}=b_{1}f_{4}+1.$

Hence the system simplifies into

$\begin{array}[]{ccc}b_{1}f_{1}+z(b_{1}f_{4}+1)&=&1\\\
b_{1}f_{2}+z(b_{1}f_{4}+1)&=&1\end{array}$

and similarly we find $f_{1}=f_{2}$ by adding the two equations.
Finally $b_{1}f_{1}+z(b_{1}f_{4}+1)=1$ is equivalent to

$b_{1}(f_{1}+f_{4}z)=1+z$

and we conclude that either $b_{1}=1$ or $b_{1}=z+1$.
Let $b_{1}=1$, then $f_{1}=1+z+zf_{4}$ and the generator matrix is given by

$G(z)=\begin{pmatrix}1+z+f_{4}z&1+z+f_{4}z&f_{4}&f_{4}\\\
z&z&1&1\end{pmatrix}$

depending only on $f_{4}\in\mathbb{F}_{2}[z]$. Computing its Smith form, one
obtains

$\displaystyle\begin{pmatrix}1+z+f_{4}z&1+z+f_{4}z&f_{4}&f_{4}\\\
z&z&1&1\end{pmatrix}$ $\displaystyle\sim\begin{pmatrix}1+z&1+z&0&0\\\
z&z&1&1\end{pmatrix}$ $\displaystyle\sim\begin{pmatrix}1+z&0&0&0\\\
0&1&0&0\end{pmatrix}$

Since the Smith form of $G(z)$ is not $[I_{k}\ 0]$, $G(z)$ generates a
catastrophic and therefore not self-dual code.
Let $b_{1}=z+1$, then $f_{1}=1+f_{4}z$ and

$G(z)=\begin{pmatrix}1+f_{4}z&1+f_{4}z&f_{4}&f_{4}\\\ z&z&1&1\end{pmatrix}.$

But $G(z)$ and

$\begin{pmatrix}1&1&0&0\\\ z&z&1&1\end{pmatrix}$

generate the same code, implying that $G(z)$ was a trivial self-dual
completion.
We conclude that for this choice of $a_{1}(z)$ there are only trivial self-
dual completions.
Now let $a_{1}(z)=1$. Then $\begin{pmatrix}1&1&1&1\end{pmatrix}$ generates a
self-orthogonal code and a non-trivial self-dual completion exists in the form
of

$\begin{pmatrix}0&z^{2}+z+1&z&z^{2}+1\\\ 1&1&1&1\end{pmatrix}.$

This generates a self-dual code by Section 5.2.

Therefore, the existence of non-trivial completions depends on the choice of
$a_{i}(z)$. This naturally steers to the search for viable conditions on the
$a_{i}(z)$ that admit non-trivial self-dual completions.

######  Theorem 8.

Let

$\tilde{G}(z)=\begin{pmatrix}a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
a_{k}(z)&a_{k}(z)&\end{pmatrix}\in\mathbb{F}_{2}[z]^{k\times(2k+2)}$

Then a non-trivial self-dual completion exists if and only if

$(1,\ldots,1)\in rowspan(\tilde{G}(z)).$

###### Proof.

Let $\tilde{\mathcal{C}}=rowspan(\tilde{G}(z))$,

$G_{1}(z)=\begin{pmatrix}\rule[2.15277pt]{10.76385pt}{0.5pt}&f(z)&\rule[2.15277pt]{10.76385pt}{0.5pt}\\\
a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\ a_{k}(z)&a_{k}(z)&\end{pmatrix}$

be a self-dual completion for some $f(z)\in\mathbb{F}_{2}[z]^{2k+2}$ and
$\mathcal{C}_{1}=rowspan(G_{1}(z))$.

Obviously, all self-dual completions of $\tilde{\mathcal{C}}$ can be found by
looking at all possible new rows
$f(z)\in{\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$\tilde{\mathcal{C}}$}\right.}$
and checking the resulting $\mathcal{C}_{1}$ for self-duality.

The main fact we will use to prove this theorem is that if
$(1,\ldots,1)\in\tilde{\mathcal{C}},$ then every possible new row
$f(z)\in\tilde{\mathcal{C}}^{\perp}$ that we want to add to $\tilde{G}(z)$,
fulfils

$f(z)f(z)^{\top}=(f(z)(1,\ldots,1)^{\top})^{2}=0,$

as $(1,\ldots,1)\in\tilde{\mathcal{C}}$, which implies that each pair of rows
of $G_{1}(z)$ is orthogonal.
$(\Longrightarrow)$ We will prove that
$(1,\ldots,1)\not\in\tilde{\mathcal{C}}$ implies that there exists exactly one
self-dual completion (up to equivalent generator matrices) and it is the
trivial one.
If $\mathcal{C}_{1}$ with generator matrix $G_{1}(z)$ is assumed to be self-
dual (and hence, also non-catastrophic), then
$(1,\ldots,1)\in\mathcal{C}_{1}$. Thus, $\begin{pmatrix}1&\cdots&1\\\
&\tilde{G}(z)&\end{pmatrix}$ is a generator matrix for $\mathcal{C}_{1}$. As
$\mathcal{C}$ is self-dual, $(1,\ldots,1)\in rowspan(G(z))$ and therefore,
$\mathcal{C}_{1}$ has also a generator matrix of the form

$\begin{pmatrix}b(z)&b(z)&0&\cdots&0\\\ a_{1}(z)&a_{1}(z)&\\\
\vdots&\vdots&&G(z)\\\ a_{k}(z)&a_{k}(z)&\end{pmatrix},$

for some $b(z)\in\mathbb{F}_{2}[z]$. As $\mathcal{C}_{1}$ is non-catastrophic
$b(z)=1$ and hence, the self-dual completion is trivial.
$(\Longleftarrow)$ We have
$dim({\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$\tilde{\mathcal{C}}$}\right.})=n-k-k=2$.
Let

${\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$\tilde{\mathcal{C}}$}\right.}=<(1,1,0,\ldots),f(z)>$

for some $f(z)=(f_{1}(z),\ldots,f_{2k+2})\in\mathbb{F}_{2}[z]^{2k+2}$. As
$\tilde{\mathcal{C}}^{\perp}$ is non-catstrophic and $f(z)$ can be completed
to a basis of this code, $\gcd(f_{1}(z),\ldots,f_{2k+2}(z))=1$. We want to
show that the code $\mathcal{C}_{1}$ generated by

$G_{1}(z)=\begin{pmatrix}f(z)\\\ \tilde{G}(z)\end{pmatrix}$

is a non-trivial self-dual completion.
First, we observe that $G_{1}(z)G_{1}(z)^{\top}=0$ as $\tilde{\mathcal{C}}$ is
self-orthogonal, $f(z)\in\tilde{\mathcal{C}}^{\perp}$ and
$(1,\ldots,1)\in\tilde{\mathcal{C}}$ implies $f(z)f(z)^{\top}=0$.
Next, we will show that $\mathcal{C}_{1}$ is non-catastrophic, which then
shows that $\mathcal{C}_{1}$ is self-dual. Applying column operations, we
obtain

$G_{1}(z)\sim\begin{pmatrix}\tilde{f}_{1}(z)&\cdots&\tilde{f}_{k+2}(z)&\tilde{f}_{k+3}(z)&\cdots&\tilde{f}_{2k+2}(z)\\\
&0&&&I_{k}\end{pmatrix},$

where $\tilde{f}_{1}(z),\ldots,\tilde{f}_{2k+2}(z)\in\mathbb{F}_{2}[z]$ with

$\gcd(\tilde{f}_{1}(z),\ldots,\tilde{f}_{2k+2}(z))=\gcd(f_{1}(z),\ldots,f_{2k+2}(z))=1.$

Consequently,

$G_{1}(z)\sim\begin{pmatrix}1&0&0\\\ 0&I_{k}&0\end{pmatrix}$

and $\mathcal{C}_{1}$ is non-catastrophic.
Finally, we will show that $(1,1,0,\ldots,0)\not\in\mathcal{C}_{1}^{\perp}$.
Assume conversely that $(1,1,0,\ldots,0)\in\mathcal{C}_{1}^{\perp}$. As
$(1,\ldots,1)\in\tilde{\mathcal{C}}$ implies $f(z)\in\mathcal{C}_{1}^{\perp}$
and one has
$\tilde{\mathcal{C}}\subset\mathcal{C}_{1}=\mathcal{C}_{1}^{\perp}$, one gets
that $\mathcal{C}_{1}^{\perp}=\tilde{\mathcal{C}}^{\perp}$. However,
$dim(\mathcal{C}_{1}^{\perp})=k+1\neq k+2=dim(\tilde{\mathcal{C}}^{\perp})$, a
contradiction.

Conclusively, we showed $(1,1,0,\ldots,0)\not\in\mathcal{C}_{1}^{\perp}$ and
$\mathcal{C}_{1}=\mathcal{C}_{1}^{\perp}$, i.e. we have a non-trivial
completion to a self-dual convolutional code. ∎

Thus, we can find non-trivial completions with the following two steps:

  * 1.

Make sure that $(1,\ldots,1)\in rowspan(\tilde{G}(z))=\tilde{\mathcal{C}}$,
which means we must establish that the system

$b(z)\tilde{G}(z)=(1,\ldots,1)\in\mathbb{F}_{2}[z]^{2k+2},$ (2)

where $b(z)=(b_{1},\ldots,b_{k})\in\mathbb{F}_{2}[z]^{k}$, has a solution for
$b(z)$.

  * 2.

Find a vector $f(z)\in\tilde{\mathcal{C}}^{\perp}$ that forms a basis of
${\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$\tilde{\mathcal{C}}$}\right.}$
with $(1,1,0,\ldots,0)$ and then

$G_{1}(z)=\begin{pmatrix}\rule[2.15277pt]{10.76385pt}{0.5pt}&f(z)&\rule[2.15277pt]{10.76385pt}{0.5pt}\\\
a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\ a_{k}(z)&a_{k}(z)&\end{pmatrix}$

generates a binary self-dual convolutional code.

We will further investigate these two steps in the following.

######  Remark 5.

A way to make sure that (2) has a solution is by finding a solution to

$b(z)G(z)=(1,\ldots,1)\in\mathbb{F}_{2}[z]^{2k},$

which always exists since $G(z)$ generates a binary self-dual code (see Lemma
10), and then choosing the $a_{i}(z)\in\mathbb{F}_{2}[z]$ such that

$\sum_{i=1}^{k}a_{i}(z)b_{i}(z)=1,$

which is possible since $b(z)G(z)=1$ implies
$gcd(b_{1}(z),\ldots,b_{k}(z))=1$. In particular, $a_{i}(z)=g_{i}(z)$ for
$i=1,\ldots,k$ yields such a solution.

The following lemma shows, how to do the second step, i.e. how to find a
suitable $f(z)$.

######  Lemma 13.

Let
$f(z)=(f_{1}(z),\ldots,f_{2k+2}(z))\in{\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$<\tilde{\mathcal{C}},(1,1,0,\ldots,0)>$}\right.}$
and

$gcd(f_{1}(z),\ldots,f_{2k+2}(z))=1,$

then

$<f(z),(1,1,0,\ldots,0)>={\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$\tilde{\mathcal{C}}$}\right.}.$

###### Proof.

Assume conversely that there exists
$h(z)\in{\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$\tilde{\mathcal{C}}$}\right.}$
such that $h(z)\neq f(z)$ and

$<h(z),(1,1,0,\ldots,0)>={\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$\tilde{\mathcal{C}}$}\right.}.$

As
$f(z)\in{\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$<\tilde{\mathcal{C}},(1,1,0,\ldots,0)>$}\right.}=<h(z)>$,
$f(z)$ must be a multiple of $h(z)$. But since the entries of $f(z)$ have no
common non-trivial divisor, $f(z)=h(z)$ follows immediately. ∎

######  Example 5.

Let

$G(z)=\begin{pmatrix}0&z^{2}+z+1&z&z^{2}+1\\\
1&1&1&1\end{pmatrix}\in\mathbb{F}_{2}[z]^{2\times 4}.$

We know by Section 5.2, that $G(z)$ generates a self-dual convolutional code.
By inspection,

$b(z)G(z)=(1,1,1,1)$

holds exactly for $b(z)=(0,1)$. Hence we need

$0\cdot a_{1}(z)+1\cdot a_{2}(z)=1$

or equivalently $a_{2}(z)=1$ and $a_{1}(z)$ may be chosen arbitrarily. So let
$a_{1}(z)=z^{2}+1$ and $a_{2}(z)=1$, then

$\tilde{G}(z)=\begin{pmatrix}z^{2}+1&z^{2}+1&0&z^{2}+z+1&z&z^{2}+1\\\
1&1&1&1&1&1\end{pmatrix}.$

We are now looking for
$f(z)\in{\raisebox{1.00006pt}{$\tilde{\mathcal{C}}^{\perp}$}\left/\raisebox{-1.00006pt}{$<\tilde{\mathcal{C}},(1,1,0,\ldots,0)>$}\right.}$.
If $f_{1}(z)\neq f_{2}(z)$, this guarantees
$f(z)\not\in<\tilde{\mathcal{C}},(1,1,0,0,0,0)>$.
Further, we need $f(z)$ to be orthogonal to both rows of $\tilde{G}(z)$, i.e.,

$\begin{array}[]{ccc}f(z)(z^{2}+1,z^{2}+1,0,z^{2}+z+1,z,z^{2}+1)^{\top}&=&0\\\
f(z)(1,1,1,1,1,1)^{\top}&=&0\end{array}$

and see that this holds for $f(z)=(0,1,0,0,0,1).$ One obtains that

$G_{1}(z)=\begin{pmatrix}0&1&0&0&0&1\\\
z^{2}+1&z^{2}+1&0&z^{2}+z+1&z&z^{2}+1\\\ 1&1&1&1&1&1\end{pmatrix}$

generates a binary self-dual convolutional code.

An immediate consequence of Remark 5 is that there must be a linear
combination of the $a_{i}(z)$ that is equal to $1$. But this is not possible,
if they have a common non-trivial divisor, giving us the following corollary.

######  Corollary 4.

Let

$G_{1}(z)=\begin{pmatrix}\rule[2.15277pt]{10.76385pt}{0.5pt}&f(z)&\rule[2.15277pt]{10.76385pt}{0.5pt}\\\
a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
a_{k}(z)&a_{k}(z)&\end{pmatrix}\in\mathbb{F}_{2}[z]^{(k+1)\times(2k+2)}$

be a self-dual completion, where $gcd(a_{1}(z),\ldots,a_{k}(z))\neq 1.$ Then,
the completion was trivial.

The converse is not true in general as can be seen in the next example.
Furthermore, we illustrate in the upcoming example that a good choice of the
$a_{i}(z)$ (“good choice" meaning that a non-trivial completion exists)
differs for equivalent generator matrices.

######  Example 6.

By Theorem 8, if we chose $a_{1}=a_{2}=1$ for

$\begin{pmatrix}1&1&0&0\\\ 0&0&1&1\\\
\end{pmatrix}\in\mathbb{F}_{2}[z]^{2\times 4},$

to obtain

$\tilde{G}(z)=\begin{pmatrix}1&1&1&1&0&0\\\ 1&1&0&0&1&1\\\ \end{pmatrix},$

then $\tilde{G}(z)$ can only be trivially completed as $(1,1,1,1,1,1)\not\in
rowspan(\tilde{G}(z))$. Now, we claim that another generator matrix of the
same code, namely

$G(z)=\begin{pmatrix}1&1&1&1\\\ 0&0&1&1\\\
\end{pmatrix}\in\mathbb{F}_{2}[z]^{2\times 4}$

has a non-trivial completion for $a_{1}(z)=a_{2}(z)=1$ in

$G_{1}(z)=\begin{pmatrix}h(z)&h(z)+1&0&0&0&1\\\ 1&1&1&1&1&1\\\
1&1&0&0&1&1\end{pmatrix},$

where $h(z)\in\mathbb{F}_{2}[z]$. $G_{1}(z)$ generates a non-catastrophic
code, since

$det\left[\begin{pmatrix}h(z)&h(z)+1&0\\\ 1&1&1\\\
1&1&0\end{pmatrix}\right]=h(z)+1+h(z)=1.$

Moreover, $G_{1}(z)G_{1}(z)^{\top}=0$ by inspection. Hence, $G_{1}(z)$
generates a self-dual code by Theorem 6.
So the only thing left to show is non-triviality.
Assume by contradiction that there exists
$b(z)=(b_{1},b_{2},b_{3})\in\mathbb{F}_{2}[z]^{3}$ such that

$b(z)G_{1}(z)=(1,1,0,0,0,0),$

or rather, in terms of a system of equations,

$\begin{array}[]{ccc}b_{1}h+b_{2}+b_{3}&=&1\\\ b_{1}(h+1)+b_{2}+b_{3}&=&1\\\
b_{2}&=&0\\\ b_{2}&=&0\\\ b_{2}+b_{3}&=&0\\\
b_{1}+b_{2}+b_{3}&=&0\end{array}.$

But the last three equations imply $b_{1}=b_{2}=b_{3}=0$, which is a
contradiction and we conclude that the completion was non-trivial.

Furthermore, if there are two generator matrices of the same code that differ
by given row operations, then from a good choice of the $a_{i}(z)$ for one
matrix, we can find a good choice for the other matrix by applying the given
row operations to the already known good choice
$(a_{1}(z),\ldots,a_{k}(z))^{\top}$.
We were previously asking the question, whether all binary self-dual
convolutional codes with $d_{free}>2$ can be constructed with the generalized
Harada-Munemasa construction. This question will be left unanswered for codes
of lengths greater than 4.

######  Lemma 14.

All binary self-dual $(4,2)$ convolutional codes can be constructed with the
generalized Harada-Munemasa construction.

###### Proof.

Let $\mathcal{C}$ be a binary self-dual $(4,2)$ convolutional code. Then by
Section 5.2, there exists a generator matrix of the form

$G_{1}(z)=\begin{pmatrix}0&g(z)+h(z)&g(z)&h(z)\\\ 1&1&1&1\end{pmatrix}$

for some $g(z),h(z)\in\mathbb{F}_{2}[z]$.

But now by setting $G(z)=(1\;1)$, $a_{1}(z)=1$ and
$f(z)=(0,g(z)+h(z),g(z),h(z))$, we may construct $G_{1}(z)$ and therefore
$\mathcal{C}$ with the generalized Harada-Munemasa construction. ∎

Finally, we want to connect the generalized building-up construction and the
generalized Harada-Munemasa construction.

######  Lemma 15.

Every code that was constructed with the generalized building-up construction,
can be constructed with the generalized Harada-Munemasa construction, but not
vice versa.

###### Proof.

Let $G(z)$ be a generator matrix of a binary self-dual convolutional code and
let

$G_{1}(z)=\begin{pmatrix}1&0&f(z)\\\ y_{1}(z)&y_{1}(z)&\\\
\vdots&\vdots&G(z)\\\ y_{k}(z)&y_{k}(z)&\end{pmatrix}$

be a generator matrix constructed with the building-up construction for some
$f(z)\in\mathbb{F}_{2}[z]^{2k}$. To construct the same code with the Harada-
Munemasa construction, just set $a_{i}(z):=y_{i}(z)$ to get

$\tilde{G}(z)=\begin{pmatrix}a_{1}(z)&a_{1}(z)&\\\ \vdots&\vdots&G(z)\\\
a_{k}(z)&a_{k}(z)&\end{pmatrix}=\begin{pmatrix}y_{1}(z)&y_{1}(z)&\\\
\vdots&\vdots&G(z)\\\ y_{k}(z)&y_{k}(z)&\end{pmatrix}$

and then add $(1,0,f(z))$ as a new row.
One the other hand, in Lemma 11, it was shown that

$\begin{pmatrix}0&z^{2}+z+1&z&z^{2}+1\\\ 1&1&1&1\end{pmatrix}$

cannot be constructed using the generalized building-up construction. But by
the previous lemma, all binary self-dual $(4,2)$ convolutional codes can be
constructed with the generalized Harada-Munemasa construction. ∎

##  7 Conclusion

We started with finding equivalent conditions to self-duality. This was the
foundation for all other obtained results. First, we used it to fully classify
all self-dual $(2,1)$ convolutional codes, all binary self-dual $(4,2)$
convolutional codes, all self-dual convolutional codes with double diagonal
generator matrices and all binary self-dual convolutional codes with double
triangular generator matrices.

Then, we investigated the construction of self-dual convolutional codes, where
the building-up construction and the Harada-Munemasa construction were
generalized. For the latter, conditions on the $a_{i}(z)$ for the existence of
non-trivial self-dual completions were established and the generalized Harada-
Munemasa construction was shown to be able to construct strictly more binary
codes.
Further, we presented a binary self-dual convolutional code with free distance
$d_{free}>2$, which cannot be constructed with the generalized building-up
construction. As a consequence, the generalized building-up construction is
not viable for the full classification of binary self-dual convolutional
codes, like it is for block codes. For the generalized Harada-Munemasa
construction this question about viability is still open for codes of lengths
greater than 4.

## Acknowledgments

The authors acknowledge the support of Swiss National Science Foundation grant
n. 188430.

## References

  * [1] S. Bouyuklieva. Self-Dual Codes. Concise Encyclopedia of Coding Theory (eds. Huffman, C; Kim, J.; Sole, P.), CRC Press, 2021.
  * [2] J.H. Conway and V. Pless. On the enumeration of self-dual codes, Combin. Theory Vol. 28 (1980), Ser. A, pp. 26-53.
  * [3] P. Gaborit, A. Otmani. Experimental construction of self-dual codes, Finite Fields and Their Applications Vol. 9 (2003), pp. 372-394.
  * [4] F.R. Gantmacher. The Theory of Matrices, vol. I, Chelsea Publishing Company, New York, 1977.
  * [5] M. Harada and A. Munemasa. Classification of self-dual codes of length 36, Advances in Mathematics of Communications Vol. 6 (2012), No. 2, pp. 229-235.
  * [6] W.C. Hufmann and V. Pless. Fundamentals of error-correcting codes, published by Cambridge University Press, 2003\.
  * [7] R. Johannesson, P. Stahl, E. Wittenmark. A Note on Type II Convolutional Codes, IEEE Transactions on Information Theory Vol. 46 (2000), No. 4, pp. 1510-1514.
  * [8] T. Kailath. Linear Systems, published by Englewood Cliffs, N.J.: Prentice Hall, 1980.
  * [9] J.-L. Kim. New extremal self-dual codes of length 36, 38 and 58, IEEE Transactions on Information Theory Vol. 47 (2001), No. 1, pp. 386-393.
  * [10] J. Lieb, R. Pinto, J. Rosenthal. Convolutional codes. Concise Encyclopedia of Coding Theory (eds. Huffman, C; Kim, J.; Sole, P.), CRC Press, 2021.
  * [11] F.J. MacWilliams and N.J.A. Sloane The Theory of Error-Correcting Codes, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
  * [12] C.A. Melchor, P. Gaborit, J.-L. Kim, L. Sok and P. Sole. Classification of extremal and $s$-extremal binary self-dual codes of length 36, IEEE Transactions on Information Theory 58 (2012), No. 4, pp. 2253-2262.
  * [13] H.S. Palines and V.P. Sison. On self-dual convolutional codes over rings, East-West Journal of Mathematics Vol. 14 (2012), No. 1, pp. 28-36.
  * [14] V. Pless. A classification of self-orthogonal codes over GF(2), Discrete Mathematics Vol. 3 (1972), pp. 209-246.
  * [15] E.M. Rains and N.J.A Sloane. Self-dual codes, in: V.S. Pless and W.C. Huffman, Handbook of Coding Theory, publishhed by Elsevier, 1998, pp. 177-294.
  * [16] N.J. Russell. Self-dual codes and indecomposable building blocks, Master Thesis, Eastern Kentucky University, Kentucky, 2016.
  * [17] E.V. York. Algebraic description and construction of error correcting codes: A linear systems point of view, Ph.D. dissertation, University of Notre Dame, 1997.