# Ultimate linear block and convolutional codes111 Keywords: Code, linear,
convolutional, self-dual, dual-containing, quantum code, complementary dual,
LDPC
AMS Classification 2020: 94B05, 94B10, 15B99

Ted Hurley222University of Galway (previously: National University of Ireland
Galway)
email<EMAIL_ADDRESS>
###### Abstract

A linear block code over a field can be derived from a unit scheme. Looking at
codes as structures within a unit scheme greatly extends the availability of
linear block and convolutional codes and allows the construction of the codes
to required length, rate, distance and type. Properties of a code emanate from
properties of the unit from which it was derived. Orthogonal units, units in
group rings, Fourier/Vandermonde units and related units are used to construct
and analyse linear block and convolutional codes and to construct these to
predefined length, rate, distance and type. Self-dual, dual containing,
quantum error-correcting and complementary dual linear block and convolutional
codes are constructed. Low density parity check linear block and convolutional
codes are constructed using group rings and are constructed with no short
cycles in the control matrix. From a single unit, multiple codes of a required
type are derivable.

##  1 Introduction

Unit-derived methods for codes were initiated in [42, 41]333An introduction in
chapter form is available in [43, 44]. and are further developed in [46, 25,
26]. Here formal methods are given which extend the unit-derived methods in a
number of different direction establishing series of linear block codes to
required type of code, rate, distance and field type and establishes methods
for creating and analysing convolutional codes. The convolutional codes can be
created to required type, length, rate, field type. Methods derived in [26]
for establishing infinite series of codes with rates approaching a given
rational $R$, $(0<R<1)$, and relative distances approaching $(1-R)$ are
applicable.

Some of the codes derived have applications in solving underdetermined systems
of equations, see [32].

The (free) distance of a convolutional codes derived may often be determined
from the unit used and in general is much better than the distance of a linear
block code of the same rate. Efficient decoding methods are available.

All linear block codes over fields are unit-derived codes, see Proposition 3.1
below, although they may not have been derived from this outlook initially.
Thus all linear block codes over fields may be devolved from within unit
schemes. By looking at a unit scheme in general and selecting constituents,
convolutional codes to required type and distance are constructed and
analysed.

An illuminating example of this, see section 4.9 below, is given where a unit-
derived form of the Hamming $[7,4,3]$ code is used to construct a memory $1$
convolutional (binary) code of distance $6$ and rate $\frac{4}{7}$. (The
convolution code formed is of type $(7,4,4;1,6)$; see section 1.1 below for
relevant convolutional code parameter definitions.) In Example 5.3 below, the
Golay binary code $[24,12,8]$, when considered as unit-derived, is extended to
convolutional memory $3$ codes with rates $\frac{3}{4}$ and $\frac{1}{4}$
which are dual to one another and one is dual containing.

The classes of linear block and convolutional codes available are greatly
expanded. Codes to required length, rate and distance required are constructed
by the unit-derived method. The coding structure lies within the unit
structure about which much is known. In mathematics we often think of breaking
a structure into more manageable parts but here we think of looking at the
bigger structure within which required embedded structures exist.

Looking at special types of units such as orthogonal units,
Vandermonde/Fourier units and units in group rings allows the construction of
special types of codes such as self-dual/dual containing codes and
complementary dual codes as well as codes to specified lengths, rates,
distances and over specified finite fields. Codes over particular required
fields, such as over fields of characteristic $2$ or codes over prime fields
(for which modular arithmetic is available) and series of such, are
constructible by the methods. Looking at units in group rings allows the
construction of low density parity check (LDPC) linear block and LDPC
convolutional codes and these are constructed with no short cycles in the
check matrix.

Dual-containing codes have their own intrinsic interest and are used for
designing quantum error-correcting codes by the CSS method, [21, 23, 22]. Here
then convolutional quantum error correcting codes of different lengths and
rates are constructed explicitly. Linear complementary dual, LCD, codes have
been studied extensively in the literature. For background, history and
general theory on LCD codes, consult the articles [12, 13, 14, 19] by Carlet,
Mesnager, Tang, Qi and Pelikaan. LCD codes were originally introduced by
Massey in [17, 18]. These codes have been studied amongst other things for
improving the security of information on sensitive devices against side-
channel attacks (SCA) and fault non-invasive attacks, see [15], and have found
use in data storage and communications’ systems.

The relationships between DC linear block codes and LCD convolutional codes
and between LCD linear block codes and convolutional DC codes when formed from
the same unit scheme are remarkable.

Hermitian codes over fields of the form $GF(q^{2})$ are constructed by looking
at unitary matrices in $GF(q^{2})$ where they are defined. This application to
Hermitian codes was initiated in [26] and full development is left to other
work.

Requiring one of $\\{U,V\\}$ in $UV=I$ to be of low density enables the
construction of low density parity check (LDPC) linear block and convolutional
LDPC codes. Series of such are derivable. The linear block case has been dealt
with in [47]. The linear block and convolutional codes are constructed so that
no short cycles exist in the control matrix. Iterative decoders for low
density parity check codes are impacted by short cycles. Here for a given unit
scheme, described in a precise way, multiple such codes, all with no short
cycles, are constructed and with prescribed rate and dimension. This follows
techniques developed in [47] for constructing low density parity check block
linear codes and such codes with no short cycles in the control matrix. The
convolutional LDPC codes can be stored using an algebraic ‘short’ formula
which for example is important in applications requiring low storage and low
power.

Some of this work is additional and complementary to that in [27, 34]. The
paper [27] has appeared on ArXiv only, having been rejected elsewhere. As
pointed out in [27], convolutional codes which appeared previously in the
literature are very special cases of constructions by this method. McEliece
has (e.g. [3]) remarked:“ A most striking fact is the lack of algebraic
constructions of families of convolutional codes.” Multiple algebraic methods
are now available.

Many codes of a particular type and structure may be deduced from just one
unit. The unit structure allows the construction of multiple linear block
codes and multiple convolutional codes from the same unit. The constructions
are general and types to required length, rate and distance are derivable.
‘Manufacturing’ of different and sophisticated ‘models’ is made relatively
easy.

Small size examples are given of necessity and these can be looked upon as
prototype examples for large constructions.

Coding theory background is contained in section 1.1. A summary of required
results/propositions which lead to construction algorithms is given in Section
2.

###  1.1 Background on coding theory

Basics on linear block coding theory may be found in [1, 2, 3, 5] and many
others. The notation $[n,r,d]$ is used here for a linear block code of length
$n$, dimension $r$, and (minimum) distance $d$. The rate is then
$\frac{r}{n}$. A maximum distance separable (mds) linear block code is one of
the form $[n,r,n-r+1]$ where the maximum distance possible for the length and
rate is achieved.

Different equivalent definitions for convolutional codes are given in the
literature. The notation and definitions used here follow that given in [36,
48, 37]. A rate $\frac{k}{n}$ convolutional code with parameters
$(n,k,\delta)$ over a field $\mathcal{F}$ is a submodule of
$\mathcal{F}[z]^{n}$ generated by a reduced basic matrix
$G[z]=(g_{ij})\in\mathcal{F}[z]^{r\times n}$ of rank $r$ where $n$ is the
length, $\delta=\sum_{i=1}^{r}\delta_{i}$ is the degree with
$\delta_{i}=\max_{1\leq j\leq r}{\deg g_{ij}}$. Also $\mu=\max_{1\leq i\leq
r}{\delta_{i}}$ is known as the memory of the code and then the code may then
be given with parameters $(n,k,\delta;\mu)$. The parameters
$(n,r,\delta;\mu,d_{f})$ are used for such a code with free (minimum) distance
$d_{f}$.

Suppose $\mathcal{C}$ is a convolutional code in $\mathcal{F}[z]^{n}$ of rank
$k$. A generating matrix $G[z]\in\mathcal{F}[z]_{k\times n}$ of $\mathcal{C}$
having rank $k$ is called a generator or encoder matrix of $\mathcal{C}$. A
matrix $H\in\mathcal{F}[z]_{n\times(n-k)}$ satisfying $\mathcal{C}=\ker
H=\\{v\in\mathcal{F}[z]^{n}:vH=0\\}$ is said to be a control matrix or check
matrix of the code $\mathcal{C}$.

Convolutional codes can be catastrophic or non-catastrophic; see for example
[3] for the basic definitions. A catastrophic convolutional code is prone to
catastrophic error propagation and is not much use. A convolutional code
described by a generator matrix with right polynomial inverse is a non-
catastrophic code; this is sufficient for our purposes. The designs given here
for the generator matrices allow for specifying directly the control matrices
and the right polynomial inverses where appropriate. There exist very few
algebraic constructions for designing convolutional codes and search methods
limit their size and availability, see McEliece [3] for discussion and also
[8, 9, 10, 11].

By Rosenthal and Smarandache, [36], the maximum free distance attainable by an
$(n,r,\delta)$ convolutional code is
$(n-r)(\lfloor\frac{\delta}{r}\rfloor+1)+\delta+1$. The case $\delta=0$, which
is the case of zero memory, corresponds to the linear Singleton bound
$(n-r+1)$. The bound $(n-r)(\lfloor\frac{\delta}{r}\rfloor+1)+\delta+1$ is
then called the generalised Singleton bound, [36], GSB, and a convolutional
code attaining this bound is known as an mds convolutional code. The papers
[36] and [48] are major beautiful contributions to this area.

The criteria for a convolutional code to be an mds code are given in terms of
the parameters for a convolutional code and the criteria for a linear block
code to be an mds code are given in terms of the parameters for a linear block
code which are different.

Let $G(z)$ be the generator matrix for a convolutional code $\mathcal{C}$ with
memory $m$. Suppose $G(z)H\text{${}^{\text{T}}$}(z)=0$, so that
$H\text{${}^{\text{T}}$}(z)$ is a control matrix, and then $H(z^{-1})z^{m}$
generates the convolutional dual code of $\mathcal{C}$, see [7] and [29]. This
is also known as the module-theoretic dual code.444In convolutional coding
theory, the idea of dual code has two meanings. The other dual convolutional
code defined is called the sequence space dual; the generator matrices for
these two types are related by a specific formula. The code is then dual-
containing provided the code generated by $H(z^{-1})z^{m}$ is contained in the
code generated by $G(z)$.

Let $G(z)$ be the generator matrix for a convolutional $(n,r)$ code
$\mathcal{C}$. Code words will consist of $P(z)*G(z)$ where $P(z)$ is a
polynomial in $z$ with coefficients which are $1\times r$ vectors. The
polynomial $P(z)$ is said to be an information vector for the code
$\mathcal{C}$. The support of $P(z)$ is the number of non-zero coefficient
vectors appearing in its expression as a polynomial.

###  1.2 Dual-containing and linear complementary dual codes

The dual of a code $\mathcal{C}$ is denoted by $\mathcal{C}^{\perp}$. The
definition of dual code of a convolutional code used here is given in
subsection 1.1 above. A code $\mathcal{C}$ is said to be dual containing,
written DC, if it contains its dual $\mathcal{C}^{\perp}$. Say a code is a
linear complementary dual, written LCD, code provided it has trivial
intersection with its dual.

Thus

$\mathcal{C}$ is a dual containing (DC) code $\Longleftrightarrow$
$\mathcal{C}\cap C^{\perp}=\mathcal{C}^{\perp}$

$\mathcal{C}$ is a linear complementary dual (LCD) code $\Longleftrightarrow$
$\mathcal{C}\cap C^{\perp}=0$

A self-dual code is a code $\mathcal{C}$ where
$\mathcal{C}^{\perp}=\mathcal{C}$; this is a very important type of DC code.

Constructions of convolutional DC and LCD codes were initiated in [26]. DC
convolutional codes are theoretically interesting themselves but in addition a
DC convolutional code enables the construction of a convolutional quantum
error-correcting code by the CSS method.

LCD codes and DC codes are ‘supplemental’ to one another: $\mathcal{C}$ is DC
if and only if $\mathcal{C}\cap\mathcal{C}^{\perp}=\mathcal{C}^{\perp}$ and
$\mathcal{C}$ is LCD if and only if $\mathcal{C}\cap\mathcal{C}^{\perp}=0$. As
noted in [26], mds DC block linear codes lead to the construction of mds LCD
convolutional codes and LCD mds block linear codes leads to the construction
of mds DC convolutional codes.

##  2 Summary

Abbreviations:

DC: dual-containing

mds: maximum distance separable

LCD: linear complementary dual

LDPC: low density parity check

QECC: quantum error-correcting code

###  2.1 units to codes propositions

  * •

Orthogonal unit $\xRightarrow{unit-derived}$ LCD linear block codes.

  * •

LCD linear block codes from unit $\xRightarrow{unit-derived}$ convolutional DC
codes from the unit $\xRightarrow{\text{CSS construct}}$ convolutional quantum
codes from the unit.

  * •

DC linear block codes from unit $\xRightarrow{unit-derived}$ convolutional LCD
codes from the unit.

  * •

    1. 1.

Fourier/Vandermonde unit: $\xRightarrow{unit-derived}$ mds codes to prescribed
rate and distance.

    2. 2.

Fourier unit, select rows in order: $\xRightarrow{unit-derived}$ mds DC block
codes $\xRightarrow{\text{CSS construct}}$ mds quantum codes.

    3. 3.

Fourier unit, select rows in order: $\xRightarrow{unit-derived}$ mds DC block
codes $\xRightarrow{unit-derived}$ LDC convolutional codes.

    4. 4.

Fourier unit, rearranged rows: $\xRightarrow{\text{unit-derived}}$ mds LCD
block codes $\xRightarrow{unit-derived}$ DC convolutional codes
$\xRightarrow{\text{CSS construct}}$ quantum convolutional codes.

  * •

Unit scheme $uv=1$ in a group ring with $v$ of small support and with no short
cycles $\xRightarrow{\text{embed in matrix}}$ Matrix unit scheme $UV=I$ with
$V$ of low density and with no short cycles $\xRightarrow{\text{unit
derived}}$ LDPC linear block and LDPC convolutional codes with no short
cycles.

  * •

Other useful units for code construction and analysis: group rings, orthogonal
type units, Hadamard type matrices.

###  2.2 Propositions enabling code development

In this section an indication is given of the type of coding structures that
are enabled from the Propositions but these are not inclusive.

  1. 1.

Look inside units for codes over fields. Proposition 3.1.

  2. 2.

Orthogonal matrices give LCD codes. Proposition 3.3.

  3. 3.

Construct self-dual codes from orthogonal type units. Proposition 3.5 and
Proposition 3.11. All self-dual linear block codes are constructed like this.

  4. 4.

Enable the construction of linear block mds, DC and quantum codes from
Fourier/Vandermonde matrices. Proposition 3.12 and Proposition 3.13

These are implicit in the paper [46].

  5. 5.

Construct LCD, mds codes from Fourier/Vandermonde type matrices: Proposition
3.16.

  6. 6.

Construct length $2n$ rate $\frac{1}{2}$, memory $1$, convolutional codes and
describes the dual code. Proposition 4.1.

  7. 7.

Construction of convolutional self-dual codes leading to quantum convolutional
code construction: Proposition 4.2

  8. 8.

Convolution DC code construction leading to quantum convolutional code
construction : Proposition 4.3.

  9. 9.

Construction of DC convolutional codes of rate $>\frac{1}{2}$ from orthogonal
matrices and orthogonal like matrices; this leads to the construction of
convolutional quantum codes of prescribed rates: Proposition 4.4.

  10. 10.

The construction of higher memory convolutional DC codes, quantum
convolutional codes and LCD convolutional codes. Propositions 5.1 and 5.4.

  11. 11.

The constructions for LDPC linear block codes and LDPC convolutional codes are
obtained by applying unit-derived techniques to special units in group rings.
An algorithm for constructing LDPC linear block and LDPC convolutional codes
with no short cycles is given in Section 6, Algorithm 1.

###  2.3 Decoding

Efficient decoding techniques for unit-derived linear block codes from
Fourier/Vandermonde type matrices are established in [46], Algorithms 6.1, 6.2
and 6.3. The constructions quickly lead to the establishment of error-
correcting pairs for the codes; error-correcting pairs are due to Pellikan,
[20]. The algorithms are especially useful for solving underdetermined systems
using error-correcting codes - see [32]. Normal known decoding methods can
also be applied.

Several algorithms exist for decoding convolutional codes, the most common
ones being the Viterbi algorithm and the sequential decoding algorithm.

##  3 Unit-derived

The unit-derived method for constructing and analysing linear block codes was
initiated in [42, 43, 44, 41] and continued in [46, 25] and elsewhere. Any
linear block code can be derived by the unit-derived method although this may
not have been the original line of thought in the construction of the code.
The unit-derived method gives further information on the code in addition to
describing the generator and control matrices. See example 4.9 below which
uses the Hamming $[7,4,3]$ in its unit-derived code form.

A linear block code with generator matrix $G$ and check matrix $H$ is
described by $GH\text{${}^{\text{T}}$}=0$. The term ‘control matrix’ may also
be used for the matrix $H\text{${}^{\text{T}}$}$. The basic unit-derived
method is obtained from the following: $U$ is an invertible $n\times n$ matrix
and is broken up as $U=\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)$. The inverse of $U$ has a compatible form
$\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)$ so that

$\begin{pmatrix}A\\\ B\end{pmatrix}\begin{pmatrix}C&D\end{pmatrix}=I_{n}$

In this $A$ has size $r\times n$ for some $r$, then $B$ has size $(n-r)\times
n$, $C$ has size $n\times r$ and $D$ has size $n\times(n-r)$. Then precisely
$AC=I_{r},AD=0_{r\times(n-r)},BC=0_{(n-r)\times r},BD=I_{(n-r)}$.

So $AD=0$ defines an $[n,r]$ code $\mathcal{C}$ where $A$ is the generator
matrix, $D$ is a control matrix and $D\text{${}^{\text{T}}$}$ generates the
dual code of $\mathcal{C}$.

A more general form of the unit-derived method, see [42, 43, 44, 41], is as
follows: Given a unit matrix system $UV=I_{n}$, taking any $r$ rows of $U$
gives an $[n,r]$ code and a control matrix is obtained by eliminating the
corresponding columns of $V$. Thus many codes may be derived, and codes of a
particular type, from a single unit scheme.

Properties of the units are used to obtain properties of the codes, and units
are formed with a particular type, length, rate, distance or field type in
mind. Infinite series of required codes are also constructed and analysed; see
for example the paper [30]. The number of choices of $r$ rows from $n$ is
${n\choose r}$ , thus deriving many codes from a single unit scheme. Having a
big choice is also useful in producing cryptographic schemes from large unit
schemes.

In the basic unit scheme above $A$ is the generator matrix of an $[n,r]$ code
$\mathcal{C}$ and since $AD=0$ then $D\text{${}^{\text{T}}$}$, which is a
$(n-r)\times r$ matrix, is a check matrix for $\mathcal{C}$. Every code over a
field can be given in this unit-derived form, Proposition 3.1. But note that
$B,C$ have been ignored! They can also be used to describe a ‘complementary
code’ but even better can be used to form a convolutional code with $A,D$.
Distances of the convolutional codes formed from a unit can often be
determined in terms of a sum of the distances of linear codes formed from that
unit. Convolutional codes have in addition their own efficient decoding
algorithms, such as Viterbi algorithm and sequential decoding algorithm.

The matrices $\\{A,B,C,D\\}$ have full ranks as they are parts of invertible
matrices.

Every linear block code arises as a unit-derived code. For completeness a
proof is included here.

######  Proposition 3.1.

Let $\mathcal{C}$ be a linear code over a field. Then $\mathcal{C}$ is
equivalent to a unit-derived code.

###### Proof.

Assume $\mathcal{C}$ is an $[n,r]$ code with generator matrix $A$ and check
matrix $H$. Then $AH\text{${}^{\text{T}}$}=0$ for an $r\times n$ matrix $A$,
and an $(n-r)\times n$ matrix $H$; here $0=0_{r\times(n-r)}$. Let
$\\{e_{1},e_{2},\ldots,e_{r}\\}$ be the rows of $A$ which are linearly
independent. Extend these to a basis
$\\{e_{1},e_{2},\ldots,e_{r},e_{r+1},\ldots,e_{n}\\}$ for the whole space
$n$-dimensional space. Let $B=\left(\begin{smallmatrix}e_{r+1}\\\ \vdots\\\
e_{n}\end{smallmatrix}\right)$ and $G=\begin{pmatrix}A\\\ B\end{pmatrix}$.
Then $G$ is invertible with inverse given by
$K=G^{-1}=\begin{pmatrix}C&D\end{pmatrix}$ where $C$ is an $n\times r$ matrix
and $D$ is an $n\times(n-r)$ matrix. Thus $\begin{pmatrix}A\\\
B\end{pmatrix}(CD)=I_{n}$. Then $AD=0$. Now $D\text{${}^{\text{T}}$}$ has rank
$(n-r)$ and $H\text{${}^{\text{T}}$}$ has rank $(n-r)$ and hence the code
generated by $A$ with check matrix $H$ is equivalent to the code generated by
$A$ with check matrix $D\text{${}^{\text{T}}$}$. ($D$ and
$H\text{${}^{\text{T}}$}$ generate the null space of $Ax=0$ and have the same
rank.)

∎

A code may not be originally constructed as a unit-derived code but it is
useful to look at a code in this manner which leads to further and better
constructions and in particular to constructions of convolutional codes. A
code is a structures which is part of a bigger structure on which more is
already known. Using the bigger structure to construct and analyse the
embedded structures has many advantages. Multiple codes of a particular type
may be deduced from just one unit.

######  Example 3.2.

In section 4.9 the Hamming $[7,4,3]$ is given as a unit-derived code and from
this a Hamming-type convolutional $(7,4,3;1,6)$ (binary) code is constructed;
the distance is twice that of the Hamming code. Decoding techniques for
convolutional codes can be employed.

If we require particular types of codes as for example DC (including self-
dual) codes or LCD codes, then look for particular types of units which give
such codes in the unit-derived way.

The convolutional codes derived in [26] use unit-derived methods from
Vandermonde/Fourier and other well-behaved matrices.

Unit-derived codes may also be obtained from a scheme where $UV=\alpha
I_{n},\alpha\neq 0$. The process is similar: Choose any $r$ rows of $U$ for a
generator matrix and a check matrix is obtained by eliminating the
corresponding columns of $V$. This is useful when considering
Vandermonde/Fourier matrices, Propositions 3.12 and 3.13, and Hadamard-type
matrices, section 5.2.

###  3.1 Using orthogonal units

######  Proposition 3.3.

Let $U$ be an orthogonal matrix. Then any unit-derived block linear code from
$U$ is an LCD (linear complementary dual) code.

###### Proof.

Now $UU\text{${}^{\text{T}}$}=I_{n}$. Thus the unit scheme is
$UU\text{${}^{\text{T}}$}=\bigl{(}\begin{smallmatrix}A\\\
B\end{smallmatrix}\bigr{)}\bigl{(}\begin{smallmatrix}C&D\end{smallmatrix}\bigr{)}=I_{n}$
for matrices $A,B,C,D$ where $A$ is of size $r\times n$, $B$ is os size
$(n-r)\times n$, $C$ is of size $n\times r$ and $D$ is of size $n\times(n-r)$.
Denote the code generated by $A$ by $\mathcal{C}$. This code has control
matrix $D$, which means $AD=0$. Now
$U\text{${}^{\text{T}}$}=\bigl{(}\begin{smallmatrix}C&D\end{smallmatrix}\bigr{)}$
and so $U=\bigl{(}\begin{smallmatrix}C\text{${}^{\text{T}}$}\\\
B\text{${}^{\text{T}}$}\end{smallmatrix}\bigr{)}$ giving that
$C\text{${}^{\text{T}}$}=A,D\text{${}^{\text{T}}$}=B$. Thus $AD=0$ is the same
as $AB\text{${}^{\text{T}}$}=0$.

Hence $B$ generates the dual code of $\mathcal{C}$. Now no non-trivial sum of
rows of $A$ can be a sum of rows of $B$ as $U=\bigl{(}\begin{smallmatrix}A\\\
B\end{smallmatrix}\bigr{)}$ is non-singular. Hence
$\mathcal{C}\cap\mathcal{C}^{\perp}=0$ as required. ∎

The following Proposition is shown in a similar manner to Proposition 3.3.

######  Proposition 3.4.

Let $X$ be an $n\times n$ matrix such that $XX\text{${}^{\text{T}}$}=\alpha
I_{n}$ for $\alpha\neq 0$. Suppose $X$ is broken as follow:
$X=\left(\begin{smallmatrix}A\\\ B\end{smallmatrix}\right)$ gives
$\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}A\text{${}^{\text{T}}$}&B\text{${}^{\text{T}}$}\end{smallmatrix}\right)=\alpha
I_{n}$ where $A$ has size $r\times n$. Then $A$ generates an $[n,r]$ LCD code
and $B$ generates the dual of this code.

Orthogonal matrices are thus a rich source for LCD codes. Given an orthogonal
$n\times n$ matrix $U$ any $r$ rows of $U$ may be chosen as the generator
matrix for a $[n,r]$ code and this code is then an LCD linear block code.

An orthogonal matrix may also be used to form a self-dual matrix by combining
it with an identity as described in the following Propositions 3.5 and 3.11.
The extended Hamming $[8,4,4]$ and Golay $[24,12,8]$ codes are constructed in
this way, see examples 3.6 and 3.7 below. Other self-dual codes may be
constructed in a similar manner from orthogonal matrices.

The following Proposition is known but is given here in a form suitable for
the constructions.

######  Proposition 3.5.

Let $X$ be an orthogonal $n\times n$ matrix in a field of characteristic $2$.
Then the matrix $A=(I_{n},X)$ generates a self-dual $[2n,n]$ matrix.
Conversely if $A=(I_{n},X)$ is a self-dual code where $X$ is an $n\times n$
matrix in a field of characteristic $2$, then $X$ is orthogonal.

###### Proof.

Suppose $X$ is orthogonal. Then
$\left(\begin{smallmatrix}I_{n},&X\end{smallmatrix}\right)\left(\begin{smallmatrix}I_{n}\\\
X\text{${}^{\text{T}}$}\end{smallmatrix}\right)=I_{n}+XX\text{${}^{\text{T}}$}=I_{n}+I_{n}=O_{n\times
n}$. Thus $\left(\begin{smallmatrix}I_{n}\\\
X\text{${}^{\text{T}}$}\end{smallmatrix}\right)$, of rank $n$, is a control
matrix for the code $\mathcal{C}$ generated by
$\left(\begin{smallmatrix}I_{n},&X\end{smallmatrix}\right)$. Thus
$(\left(\begin{smallmatrix}I_{n}\\\
X\text{${}^{\text{T}}$}\end{smallmatrix}\right))\text{${}^{\text{T}}$}=\left(\begin{smallmatrix}I_{n},&X\end{smallmatrix}\right)$
generates the dual code of $\mathcal{C}$. Hence $\mathcal{C}$ is self-dual.

On the other hand if the code generated by $(I_{n},X)$ is self-dual then
$(I,X)\text{${}^{\text{T}}$}=\left(\begin{smallmatrix}I_{n}\\\
X\text{${}^{\text{T}}$}\end{smallmatrix}\right)$ is a control matrix for this
code and so $(I_{n},X)\left(\begin{smallmatrix}I_{n}\\\
X\text{${}^{\text{T}}$}\end{smallmatrix}\right)=0_{n\times n}$. Hence
$I_{n}+XX\text{${}^{\text{T}}$}=0_{n\times n}$ and so
$XX\text{${}^{\text{T}}$}=I_{n}$. ∎

######  Example 3.6.

The Hamming $[8,4,4]$ self-dual binary code $\mathcal{H}$ is formed this way.
Let $U=\left(\begin{smallmatrix}0&1&1&1\\\ 1&1&1&0\\\ 1&1&0&1\\\
1&0&1&1\end{smallmatrix}\right)$ Then $U^{2}=I_{4},U=U\text{${}^{\text{T}}$}$
and $A=(I_{4},U)$ is a generator matrix for the Hamming $[8,4,4]$ self-dual
code$\mathcal{H}$. In addition the control matrix for the code has the form
$\bigl{(}\begin{smallmatrix}I_{4}\\\ U\end{smallmatrix}\bigr{)}$ in which each
row is unique and can be used to correct any one error in the one-error
correcting code $\mathcal{H}$.

######  Example 3.7.

The Golay $[24,12,8]$ is formed in this way, [35]. Let $U$ be the reverse
circulant matrix formed using $(0,1,1,0,1,1,1,1,0,1,0,0)$ as the first row.
Then $U^{2}=I_{12},U=U\text{${}^{\text{T}}$}$ and $(I_{12},U)$ is a generator
matrix for the self-dual Golay $[24,12,8]$ code $\mathcal{G}$. See [35] for
details. The control matrix for the code has the form
$\bigl{(}\begin{smallmatrix}I_{12}\\\ U\end{smallmatrix}\bigr{)}$ in which the
sum of any $1$, $2$ or $3$ rows is unique and thus a lookup table can be
formed to correct up to three errors in this 3-error correcting Golay
$[24,12,8]$ self-dual code.

A generator matrix for a linear block code may be given in systematic form,
$G=(I_{n},P)$ where $P$ is an $n\times t$ matrix, see [1]. The distance of the
code generated by $(I_{n},P)$ is a function of the ‘unit-derived’ type codes
from $P$.

######  Proposition 3.8.

Consider the code $\mathcal{C}$ generated by $G=(I_{n},P)$. Suppose the code
generated by any $s$ rows of $P$ has distance $\geq d-s$ and for some choice
of $r$ rows the code generated by these $r$ rows has distance exactly $d-r$
then the distance of $\mathcal{C}$ is $d$.

The Proposition makes sense even if the number of columns of $P$ is less than
$n$. The following Lemma is easy from results on fields.

######  Lemma 3.9.

Let $F$ be a field. Then $F$ has an square root of $(-1)$ or else a quadratic
extension of $F$ has a square root of $(-1)$.

###### Proof.

If $F$ does not have a square root of $(-1)$ then $x^{2}+1$ is irreducible
over $F$. ∎

######  Lemma 3.10.

Let $F$ be a field with contains a square root of $(-1)$, denoted by $i$, and
$X$ an $n\times n$ matrix over $F$. Then $XX\text{${}^{\text{T}}$}=I_{n}$ if
and only if $(iX)(iX)\text{${}^{\text{T}}$}=-I_{n}$.

Proposition 3.5 is implicit in the following more general Proposition which
enables the construction of self-dual codes over fields.

######  Proposition 3.11.

Let $X$ be an $n\times n$ matrix over a field $\mathcal{F}$.

(i) If $X$ is an orthogonal matrix then $(I_{n},iX)$ generates a self-dual
code where $i$ is a square root of $(-1)$ in $\mathcal{F}$ or in a quadratic
extension of $\mathcal{F}$.

(ii) If $(I_{n},X)$ is self-dual then $iX$ is orthogonal where $i$ is a square
root of $(-1)$ in $\mathcal{F}$ or in a quadratic extension of $\mathcal{F}$.

###### Proof.

(i) $(I_{n},iX)\left(\begin{smallmatrix}I_{n}\\\
(iX)\text{${}^{\text{T}}$}\end{smallmatrix}\right)=I_{n}-XX\text{${}^{\text{T}}$}=0$
and so $(I_{n},iX)$ generates a self-dual code as
$(\left(\begin{smallmatrix}I_{n}\\\
(iX)\text{${}^{\text{T}}$}\end{smallmatrix}\right))\text{${}^{\text{T}}$}=(I_{n},iX)$.

(ii) Suppose $(I_{n},X)$ is self-dual. Then a control matrix of the code is
$(I_{n},X)\text{${}^{\text{T}}$}=\left(\begin{smallmatrix}I_{n}\\\
X\text{${}^{\text{T}}$}\end{smallmatrix}\right)$ and so
$(I_{n},X)\left(\begin{smallmatrix}I_{n}\\\
X\text{${}^{\text{T}}$}\end{smallmatrix}\right)=0$. Hence
$I_{n}+XX\text{${}^{\text{T}}$}=0$ and so $XX\text{${}^{\text{T}}$}=-I_{n}$.
hence $iX(iX)\text{${}^{\text{T}}$}=I_{n}$ ∎

In a field of characteristic $2$, $(-1)=1$ and so Proposition 3.3 follows from
Proposition 3.11.

This gives a general method for constructing and analysing self-dual codes
from unit orthogonal and orthogonal like matrices.

###  3.2 Codes from Fourier type units

Using Fourier (or more generally Vandermonde) type units matrices to construct
various types of mds codes was initiated in [46, 25] and further developed in
[30] and others. Here we present Propositions in a very general form from
which these constructions may be derived. Series of required types, lengths
and rates are achievable.

Let $F_{n}$ be a Fourier matrix over a finite field $\mathcal{F}$. Over which
finite fields this $F_{n}$ can be constructed is discussed in [46, 30] and
elsewhere. Let $F_{n}^{*}$ be the inverse of $F_{n}$ giving the unit scheme
$F_{n}F_{n}^{*}=I_{n}$. Let $F_{n}$ have rows
$\\{e_{0},e_{1},\ldots,e_{n-1}\\}$ in order and $F_{n}^{*}$ have columns
$\\{f_{0},f_{1},\ldots,f_{n-1}\\}$ in order. Now
$e_{1}=(1,\omega,\omega^{2},\ldots,\omega^{n-1})$ and
$e_{i}=(1,\omega^{i},\omega^{2i},\ldots,\omega^{(n-1)i})$ where $\omega$ is a
primitive $n^{th}$ root of unity in the field $\mathcal{F}$.

Then, see [46, 25, 30], it is noted that
$f_{i}=\frac{1}{n}e_{n-i}\text{${}^{\text{T}}$}$ and
$e_{i}=nf_{n-1}\text{${}^{\text{T}}$}$.

######  Proposition 3.12.

Let $F_{n}$ be a Fourier matrix over a finite field $\mathcal{F}$. Let
$F_{n}^{*}$ be the inverse of $F_{n}$ giving the unit scheme
$F_{n}F_{n}^{*}=I_{n}$. Let $F_{n}$ have rows
$\\{e_{0},e_{1},\ldots,e_{n-1}\\}$ in order where
$e_{i}=(1,\omega^{i},\omega^{2i},\ldots,\omega^{(n-1)i})$ and $\omega$ is a
primitive $n^{th}$ root of unity in the field $\mathcal{F}$.

Then the basic unit scheme from the Fourier matrix, $F_{n}F_{n}^{*}=I_{n}$, is
given as follows:

$\begin{pmatrix}e_{0}\\\ e_{1}\\\ \vdots\\\
e_{n-1}\end{pmatrix}\begin{pmatrix}e_{0}\text{${}^{\text{T}}$},&e_{n-1}\text{${}^{\text{T}}$},&e_{n-2}\text{${}^{\text{T}}$},&\ldots,&e_{1}\text{${}^{\text{T}}$}\end{pmatrix}=nI_{n}$

Having $nI_{n}$ rather than $I_{n}$ is no problem in describing codes from the
scheme as $n\neq 0$ in a field in which the Fourier $n\times n$ matrix exists;
$H$ is a control, respectively generator, matrix if and only if $\alpha H$ is
a control, respectively generator, matrix for $\alpha\neq 0$.

This gives the following, see for example [46]:

######  Proposition 3.13.

Let $F_{n}$ be Fourier $n\times n$ matrix over a finite field and has rows
$\\{e_{0},e_{1},\ldots,e_{n-1}\\}$. Suppose
$F_{n}=\left(\begin{smallmatrix}A\\\ B\end{smallmatrix}\right)$ where
$A=\left(\begin{smallmatrix}e_{0}\\\ e_{1}\\\ \vdots\\\
e_{r-1}\end{smallmatrix}\right)$.

(i) The code generated by $A$ is an $[n,r,n-r+1]$ mds block code.

(ii) When $r>\frac{n}{2}$ the code generated by $A$ is an $[n,r,n-r+1]$ DC mds
code.

(iii) In the case when $r>\frac{n}{2}$ the CSS construction from the DC
$[n,r,n-r+1]$ code gives a quantum error-correcting $[[n,2r-n,n-r+1]]$ which
is an mds quantum code555mds in the quantum code sense.

If $r$ rows of $F_{n}$ are chosen in arithmetic order, starting at any row,
with arithmetic difference $k$ where $\gcd(k,n)=1$ then an mds $[n,r,n-r+1]$
is still obtained; the differences are taken mod $n$. This may be used to
construct LCD codes. It will be shown later that DC convolutional codes may in
many circumstances be produced from the unit scheme that produced the LCD
codes. Examples are given as follows before the general result is described.

######  Example 3.14.

Let $F_{7}$ denote a Fourier $7\times 7$ matrix over a finite field. Such a
matrix exists over a field whose characteristic does not divide $7$ and which
has an element of order $7$. Thus such a matrix exists for example over
$GF(2^{3})$ or over $GF(13^{2})$. Look at a unit scheme formed by rearranging
the rows of $F_{7}$ as follows:

$\left(\begin{smallmatrix}e_{6}\\\ e_{0}\\\ e_{1}\\\ e_{2}\\\ e_{3}\\\
e_{4}\\\
e_{5}\end{smallmatrix}\right)\left(\begin{smallmatrix}e_{1}\text{${}^{\text{T}}$}&e_{0}\text{${}^{\text{T}}$}&e_{6}\text{${}^{\text{T}}$}&e_{5}\text{${}^{\text{T}}$}&e_{4}\text{${}^{\text{T}}$}&e_{3}\text{${}^{\text{T}}$}&e_{2}\text{${}^{\text{T}}$}\end{smallmatrix}\right)=7I_{7}$

Then the first three rows $\left(\begin{smallmatrix}e_{6}\\\ e_{0}\\\
e_{1}\end{smallmatrix}\right)$ generates an $[8,3,6]$ mds code. A control code
is
$\left(\begin{smallmatrix}e_{5}\text{${}^{\text{T}}$}&e_{4}\text{${}^{\text{T}}$}&e_{3}\text{${}^{\text{T}}$}&e_{2}\text{${}^{\text{T}}$}\end{smallmatrix}\right)$
and thus the dual code is generated by the transpose of this,
$\left(\begin{smallmatrix}e_{5}\\\ e_{4}\\\ e_{3}\\\
e2\end{smallmatrix}\right)$. Thus a $[8,3,6]$ LCD code is obtained; the
$e_{i}$ are independent as rows of an invertible matrix.

Looking at the unit scheme as given, it will be shown later how a
convolutional code which is DC can be constructed.

######  Example 3.15.

Let $F_{8}$ be a Fourier $8\times 8$ matrix over a finite field. Such a matrix
exists in a field of characteristic not dividing $8$ and having an element of
order $8$, for example over $GF(3^{2})$ or over the prime field $GF(17)$.

The rows of $F_{8}$ in order are denoted by $\\{e_{0},e_{1},\ldots,e_{7}\\}$.
Look at the unit-scheme in the form $\left(\begin{smallmatrix}e_{6}\\\
e_{7}\\\ e_{0}\\\ e_{1}\\\ e_{2}\\\ e_{3}\\\ e_{4}\\\
e_{5}\end{smallmatrix}\right)\left(\begin{smallmatrix}e_{2}\text{${}^{\text{T}}$}&e_{1}\text{${}^{\text{T}}$}&e_{0}\text{${}^{\text{T}}$}&e_{7}\text{${}^{\text{T}}$}&e_{6}\text{${}^{\text{T}}$}&e_{5}\text{${}^{\text{T}}$}&e_{4}\text{${}^{\text{T}}$}&e_{3}\text{${}^{\text{T}}$}\end{smallmatrix}\right)=8I_{8}$.

Then $\left(\begin{smallmatrix}e_{6}\\\ e_{7}\\\ e_{0}\\\ e_{1}\\\
e_{2}\end{smallmatrix}\right)$ generates an $[8,5,4]$ mds code. A control
matrix is
$\left(\begin{smallmatrix}e_{5}\text{${}^{\text{T}}$}&e_{4}\text{${}^{\text{T}}$}&e_{3}\text{${}^{\text{T}}$}\end{smallmatrix}\right)$
and thus the transpose of this, $\left(\begin{smallmatrix}e_{5}\\\ e_{4}\\\
e_{3}\end{smallmatrix}\right)$, generates the dual of the code. Hence the code
is an LCD code - the $e_{i}$ are independent as rows of an invertible matrix.

The idea is to keep a row $e_{i}$ and its ‘conjugate’ $e_{n-i}$ together in
the generating matrix and thus get an LCD code. When using the same unit
scheme to obtain convolutional codes, then DC convolutional codes are
obtainable. The following is the general result which is best understood by
looking at examples 3.14 and 3.15.

######  Proposition 3.16.

Let $F_{n}$ be a Fourier matrix over a finite field. Let the rows in order of
$F_{n}$ be denoted by $\\{e_{0},e_{1},\ldots,e_{n-1}\\}$. Rearrange the
Fourier matrix unit scheme as follows:

$\left(\begin{smallmatrix}e_{r}\\\ \vdots\\\ e_{n-1}\\\ e_{0}\\\ e_{1}\\\
\vdots\\\ e_{n-r}\\\ e_{n-r+1}\\\ \vdots\\\
e_{r-1}\end{smallmatrix}\right)(e_{n-r}\text{${}^{\text{T}}$},\ldots,e_{1}\text{${}^{\text{T}}$},e_{0}\text{${}^{\text{T}}$},e_{n-1}\text{${}^{\text{T}}$},\ldots,e_{r}\text{${}^{\text{T}}$},e_{r-1}\text{${}^{\text{T}}$},\ldots,e_{n-r+1}\text{${}^{\text{T}}$})=nI_{n}$

Then the code generated by $\left(\begin{smallmatrix}e_{r}\\\ \vdots\\\
e_{n-1}\\\ e_{0}\\\ e_{1}\\\ \vdots\\\ e_{n-r}\end{smallmatrix}\right)$ is an
LCD mds code.

An advantage of this is that looking at the full unit scheme allows the
construction of convolutional DC codes and from the convolutional DC code
quantum error-correcting codes are defined by the CSS construction.

From full unit schemes:

DC linear block codes from unit $\xRightarrow{unit-derived}$ convolutional LCD
codes from the unit.

LCD linear block codes from unit $\xRightarrow{unit-derived}$ convolutional DC
codes from the unit $\xRightarrow{unit-derived}$ convolutional quantum codes
from the unit scheme.

##  4 Convolutional unit-derived codes

The basic unit-derived scheme is given by: $\bigl{(}\begin{smallmatrix}A\\\
B\end{smallmatrix}\bigr{)}\bigl{(}\begin{smallmatrix}C&D\end{smallmatrix}\bigr{)}=I_{n}$.

As noted, using $AD=0$ defines a block linear code where $A$ generates the
code and $D\text{${}^{\text{T}}$}$ generates the dual of this code. The total
power of the unit is not used as $\\{B,C\\}$ are ignored. This can be
rectified by going on to describe convolutional codes from the unit scheme.
The general idea is to use $A,B$ to describe convolutional codes $G(z)=A+Rz$
where $R$ is formed from $B$. DC and LCD convolutional codes are obtained.
Constructing DC convolutional codes lead to the construction of quantum error
correcting convolutional, QECC, codes, by CSS construction.

A free distance can be prescribed as a linear functional of the distances of
the (block linear) codes generated by $A$ and $B$.

Convolutional mds codes are constructed in [26, 30] by the method.

###  4.1 Same block sizes

Suppose that $A,B$ both have the same size, $r\times n$, in the unit-derived
formula; now $r=\frac{n}{2}$ and $n$ is even. Let the code generated by $A$
have distance $d_{1}$ and the code generated by $B$ have distance $d_{2}$.
Consider $G[z]=A+Bz$. This generates a convolutional code of memory $1$. As
$G(z)*C=AC=I_{r}$ the generator matrix has a right inverse and so the code is
non-catastrophic.

Now also $(A+Bz)(D-Cz)=AD-ACz+BDz-BCz=-I_{r}z+I_{r}z=0_{r}$. Thus $D-Cz$ is a
control matrix for the $(n,r,r;1)$ convolutional code.

The free distance for the code is $(d_{1}+d_{2})$. This minimum distance is
obtained when the information vector has support $1$. If the information
vector $P(z)$ has support $k$ then $P(z)G(z)$ has distance
$\geq(d_{1}+d_{2}+k-1)$.

The dual code generator matrix is obtained from the control matrix
$H\text{${}^{\text{T}}$}(z)$; as noted the dual generator matrix is
$H(z^{-1})z^{m}$ where $m$ is the memory and $H\text{${}^{\text{T}}$}(z)$ is
the control matrix. In this case the control matrix is
$H\text{${}^{\text{T}}$}(z)=D-Cz$ and so a generator matrix for the dual code
is
$(D\text{${}^{\text{T}}$}-C\text{${}^{\text{T}}$}z^{-1})z=-C\text{${}^{\text{T}}$}+D\text{${}^{\text{T}}$}z$.

If $C\text{${}^{\text{T}}$}=-A$ and $D\text{${}^{\text{T}}$}=B$ then a self-
dual convolutional code is obtained. Such a situation arises when
$\bigl{(}\begin{smallmatrix}A\\\ B\end{smallmatrix}\bigr{)}$ is orthogonal and
the characteristic is $2$.

As noted in section 3.1, Lemma 3.9, a finite field $F$ has a square root of
$(-1)$ or else a quadratic extension of $F$ has a square root. Thus define
$G(z)=A+iB$ where $i$ denotes a square root of $(-1)$. Then $(A+iB)(iD+Cz)=0$
and so $H\text{${}^{\text{T}}$}(z)=iD+Cz$ is a control matrix giving that
$H(z^{-1})z=C\text{${}^{\text{T}}$}+iD\text{${}^{\text{T}}$}$ is a dual
matrix. In case $U$ is an orthogonal matrix,
$\mathcal{C}\text{${}^{\text{T}}$}=A,D\text{${}^{\text{T}}$}=B$ and a dual
matrix is $A+iB$ giving that $G(z)$ is a self-dual convolutional code of
distance equal to the sum of the distances of the codes generated by $A$ and
by $B$.

######  Proposition 4.1.

Let $U$ be a $2n\times 2n$ invertible matrix. Suppose
$U=\bigl{(}\begin{smallmatrix}A\\\ B\end{smallmatrix}\bigr{)}$ and
$\bigl{(}\begin{smallmatrix}A\\\
B\end{smallmatrix}\bigr{)}\bigl{(}\begin{smallmatrix}C&D\end{smallmatrix}\bigr{)}=I_{2n}$
where $A$ and $B$ have size $n\times 2n$ and $C,D$ have size $2n\times n$.

  1. 1.

$A$ generates a $[2n,n]$ code $\mathcal{C}$ and $D\text{${}^{\text{T}}$}$
generates the dual code of $\mathcal{C}$. $B$ generates a $[2n,n]$ code
$\mathcal{D}$ and $C\text{${}^{\text{T}}$}$ generates the dual code of
$\mathcal{D}$.

  2. 2.

$G(z)=A+Bz$ generates a (non-catastrophic) convolutional $(2n,n,n;1)$ code
$\mathcal{C}$. Then $G(z)(D-Cz)=0$, $D-Cz$ is a control matrix of
$\mathcal{C}$ and $-C\text{${}^{\text{T}}$}+D\text{${}^{\text{T}}$}z$
generates the dual code of $\mathcal{C}$.

  3. 3.

If the code generated by $A$ has distance $d_{1}$ and the code generated by
$B$ has distance $d_{2}$, then the (free) distance of $\mathcal{C}$ is
$d=d_{1}+d_{2}$ and $\mathcal{C}$ is a $(2n,n,n;1,d)$ convolutional code.
Further if the information vector $P(z)$ has support $k$ then $P(z)G(z)$ has
distance $\geq(d+k-1)$.

######  Proposition 4.2.

Let $U$ be a $2n\times 2n$ orthogonal matrix. Suppose
$U=\bigl{(}\begin{smallmatrix}A\\\ B\end{smallmatrix}\bigr{)}$ and
$\bigl{(}\begin{smallmatrix}A\\\
B\end{smallmatrix}\bigr{)}\bigl{(}\begin{smallmatrix}C&D\end{smallmatrix}\bigr{)}=I_{2n}$
where $A$ and $B$ have size $n\times 2n$ and $C,D$ have size $2n\times n$.

  1. 1.

$A$ generates a $[2n,n]$ code $\mathcal{C}$ and $B$ generates the dual of
$\mathcal{C}$; hence $\mathcal{C}$ is an LCD code. $B$ generates a $[2n,n]$
code $\mathcal{D}$ and $A$ generates the dual of $\mathcal{D}$; hence
$\mathcal{D}$ is an LCD code.

  2. 2.

$G(z)=A+Bz$ generates a (non-catastrophic) convolutional $(2n,n,n;1)$ code
$\mathcal{C}$. Then $-C\text{${}^{\text{T}}$}+D\text{${}^{\text{T}}$}z=-A+Bz$
generates the dual code of $\mathcal{C}$.

  3. 3.

If $U$ is a matrix over a field of characteristic $2$ then $G(z)=A+Bz$
generates a self-dual convolutional code.

  4. 4.

If the code generated by $A$ has distance $d_{1}$ and the code generated by
$B$ has distance $d_{2}$, then the (free) distance of the code generated by
$G(z)$ is $d=d_{1}+d_{2}$ and is a $(2n,n,n;1,d)$ convolutional code. Further
if the information vector $P(z)$ has support $k$ then $P(z)G(z)$ has distance
$\geq(d+k-1)$.

  5. 5.

In case of characteristic $2$, the code generated by $G(z)$ is used to
generate a quantum convolutional code of memory $1$ which has type
$[[2n,0,d]]$ where $d=d_{1}+d_{2}$ is given in item 4.

  6. 6.

Define $G(z)=A+iB$ where $i$ denotes a square root of $(-1)$. Then
$(A+iB)(iD+Cz)=0$ and so $H\text{${}^{\text{T}}$}(z)=iD+Cz$ is a control
matrix giving that
$H(z^{-1})z=C\text{${}^{\text{T}}$}+iD\text{${}^{\text{T}}$}z$ is a dual
matrix. The free distance of $G(z)$ is equal to the sum, $d$, of the distances
of the codes generated by $A$ and by $B$.

  7. 7.

Suppose now $U=\left(\begin{smallmatrix}A\\\ B\end{smallmatrix}\right)$ is an
orthogonal matrix, then in item 6,
$C\text{${}^{\text{T}}$}=A,D\text{${}^{\text{T}}$}=B$. A dual matrix is then
$A+iBz$ giving that $G(z)$ is a self-dual convolutional $(2n,n,n;1,d)$ code.
This can be used to define a $[[2n,0,d]]$ quantum convolutional code.

These propositions are very general and can be used to construct infinite
series of such codes with increasing distances.

###  4.2 Different block sizes

Consider cases where $A$ has size greater than $B$ in the unit-derived formula
$\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)=I_{n}$
with $U=\left(\begin{smallmatrix}A\\\ B\end{smallmatrix}\right)$.

Let $A$ have size $r\times n$, then $B$ has size $(n-r)\times n$. Now
$r>(n-r)$ is equivalent to $2r>n$. Let $t=r-(n-r)=2r-n$ and $0_{t}=0_{t\times
n}$. Thus $B_{1}=\begin{pmatrix}0_{t}\\\ B\end{pmatrix}$ is an $r\times n$
matrix. Now $C$ is an $n\times r$ matrix and thus has the form $C=(X,C_{1})$
where $C_{1}$ has size $n\times(n-r)$ and $X$ has size $n\times(2r-n)$. As
$AC=I_{r}$ then $AC_{1}=\begin{pmatrix}0_{(2r-n)\times(n-r)}\\\
I_{(n-r)\times(n-r)}\end{pmatrix}$.

Define $G(z)=A+B_{1}z$. This defines a generator matrix for a convolutional
$(n,r,n-r;1)$ code. $BC=0$ implies $BC_{1}=0_{(n-r)\times(n-r)}$.

Then $(A+B_{1}z)(D-C_{1}z)=AD-AC_{1}z+B_{1}Dz-
B_{1}C_{1}z^{2}=0_{r\times(n-r)}-\begin{pmatrix}0_{2r-n\times n-r}\\\
I_{n-r\times n-r}\end{pmatrix}z+\begin{pmatrix}0_{2r-n\times n-r}\\\
I_{(n-r)\times(n-r)}\end{pmatrix}z=0_{r\times(n-r)}$. Thus the control matrix
is $(D-C_{1}z)$ and a dual matrix is $-C\text{${}^{\text{T}}$}+Dz$ As
$(A+B_{1}z)C=I_{r}$, the code is non-catastrophic.

Define $G(z)=A+iB_{1}z$ where $i$ is a square root of $(-1)$ in the field or
in a quadratic extension of the field. Then $(A+iB_{1})(iD+C_{1}z)=0$ and
$C_{1}\text{${}^{\text{T}}$}+iD\text{${}^{\text{T}}$}z$ is a dual matrix. In
case $U$ is orthogonal $C=A\text{${}^{\text{T}}$},D=B\text{${}^{\text{T}}$}$
and $A=\left(\begin{smallmatrix}X\text{${}^{\text{T}}$}\\\
C_{1}\text{${}^{\text{T}}$}\end{smallmatrix}\right),B_{1}=\left(\begin{smallmatrix}0\\\
D\text{${}^{\text{T}}$}\end{smallmatrix}\right)$. Hence the code generated by
$G(z)$ contains its dual.

######  Proposition 4.3.

Let $U$ be a matrix over a field with $U=\bigl{(}\begin{smallmatrix}A\\\
B\end{smallmatrix}\bigr{)}$ where $A$ has size $r\times n$ and $B$ has size
$(n-r)\times n$ with $r>n-r$. Let $t=2r-n$ and
$B_{1}=\bigl{(}\begin{smallmatrix}0_{t\times n}\\\
B\end{smallmatrix}\bigr{)}$. Then

(1) $G(z)=A+B_{1}z$ generates a convolutional $(n,r,n-r;1)$ code
$\mathcal{C}$.

(2) Let $A_{1}$ be the matrix of the first $(2r-n)$ rows of $A$. The distance
$d$ of $\mathcal{C}$ is
$\min\\{d(A_{1}),d(A)+d(\left(\begin{smallmatrix}A_{1}\\\
B\end{smallmatrix}\right))\\}$ where $d(X)$ denotes the distance of the code
generated by $X$.

######  Proposition 4.4.

Let $U$ be an orthogonal matrix in a field $\mathcal{F}$ and
$U=\bigl{(}\begin{smallmatrix}A\\\ B_{1}\end{smallmatrix}\bigr{)}$ where $A$
has size $r\times n$ and $B_{1}$ has size $(n-r)\times n$ with $r>n-r$. Let
$t=2r-n$ and $B_{1}=\bigl{(}\begin{smallmatrix}0_{t\times n}\\\
B\end{smallmatrix}\bigr{)}$. Let $i$ be a square root of $-1$ in $F$ or in a
quadratic extension of $\mathcal{F}$ Then

(1) $G(z)=A+iB_{1}z$ generates a convolutional dual-containing $(n,r,n-r;1)$
code $\mathcal{C}$.

(2) Let $A_{1}$ be the matrix of the first $(2r-n)$ rows of $A$. The distance
$d$ of $\mathcal{C}$ is
$\min\\{d(A_{1}),d(A)+d(\left(\begin{smallmatrix}A_{1}\\\
B\end{smallmatrix}\right))\\}$ where $d(X)$ denotes the distance of the code
generated by $X$. (3) A quantum convolutional code of the form $[[n,2r-n,d]]$
is constructed from $\mathcal{C}$ where $d$ is the distance of $\mathcal{C}$.

The process is developed similarly by looking at
$\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)=\alpha
I_{n}$ with $U=\left(\begin{smallmatrix}A\\\ B\end{smallmatrix}\right)$ where
$\alpha\neq 0$. See for example section 5.2 for examples on this.

It is best illustrated by looking at a block decomposition say one of the form
$\left(\begin{smallmatrix}A_{0}\\\ A_{1}\\\ A_{2}\\\
A_{3}\end{smallmatrix}\right)\left(\begin{smallmatrix}B_{0}&B_{1}&B_{2}&B_{3}\end{smallmatrix}\right)=I_{4n}$
where each $A_{i}$ has size $n\times 4n$. Take
$G(z)=\left(\begin{smallmatrix}A_{0}\\\ A_{1}\\\
A_{2}\end{smallmatrix}\right)+\left(\begin{smallmatrix}0\\\ 0\\\ 0\\\
A_{3}\end{smallmatrix}\right)z$.

In case $U$ is orthogonal, let $G(z)=\left(\begin{smallmatrix}A_{0}\\\
A_{1}\\\ A_{2}\end{smallmatrix}\right)+i\left(\begin{smallmatrix}0\\\ 0\\\
0\\\ A_{3}\end{smallmatrix}\right)z$ and then a $(4n,3n,n;1,d)$ DC
convolutional code is obtained from which a quantum convolutional code of form
$[[4n,2n,d]]$ is obtained. The $d$ may be calculated algebraically and depends
on the distances of codes formed from the blocks.

####  4.2.1 Prototype examples

The following prototype examples exemplify some of the general constructions.
The examples given tend to be linear block and convolutional of types DC and
LCD, but many types and infinite series of such may be built up also by the
techniques. The types DC lead to the formation of quantum codes

######  Example 4.5.

Let $F_{7}$ be a Fourier $7\times 7$ matrix over some field $\mathcal{F}$. The
field $\mathcal{F}$ is any field over which the Fourier $7\times 7$ matrix
exists. Thus $\mathcal{F}$ could be $GF(2^{3})$, a characteristic $2$ field,
but also over fields with characteristic not dividing $7$.

Denote the rows of $F_{7}$ in order by
$\\{e_{0},e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}\\}$ and the columns of the
inverse of $F_{7}$ in order by
$\\{f_{0},f_{1},f_{2},f_{3},f_{4},f_{5},f_{6}\\}$. Note that
$e_{i}f_{j}=0,i\neq j,e_{i}f_{i}=1$ but also as $F_{7}$ is a Fourier matrix
that $f_{i}\text{${}^{\text{T}}$}=\frac{1}{7}e_{7-i}$. The fraction part is no
problem for check or control matrices: $H$ is a check matrix if and only if
$\alpha H$ is a check matrix for any $\alpha\neq 0$.

Let $A=\left(\begin{smallmatrix}e_{0}\\\ e_{1}\\\ e_{2}\\\
e_{3}\end{smallmatrix}\right),B_{1}=\left(\begin{smallmatrix}e_{4}\\\ e_{5}\\\
e_{6}\end{smallmatrix}\right)$ where $F_{7}=\begin{pmatrix}A\\\
B_{1}\end{pmatrix}$ is the Fourier $7\times 7$ matrix. Now from [26] $A$
generates a $[7,4,4]$ mds (block) DC code.

Let $B=\bigl{(}\begin{smallmatrix}0\\\ B_{1}\end{smallmatrix}\bigr{)}$. Define
$G(z)=A+B=A+\left(\begin{smallmatrix}0\\\ e_{4}\\\ e_{5}\\\
e_{6}\end{smallmatrix}\right)z$. Now $G(z)*(f_{1},f_{2},f_{3},f_{4})=I_{4}$
and so $G(z)$ has a right inverse and thus the code generated by $G(z)$ is
non-catastrophic. $G(z)$ defines a $[7,4,3;1]$ convolutional code
$\mathcal{C}$. The GSB for such a code is
$(7-4)(\lfloor\frac{3}{4}\rfloor+1)+3+1=3+3+1=7$. It is easy to check that
this $7$ is the free distance of the code and so the code is an mds
convolutional code.

Note that $(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})*B$ has distance $\geq
5$ as an element in a $[7,3,5]$ code where
$(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})$ is a non-zero $1\times 4$
vector, except when
$(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})=(\alpha_{1},0,0,0)$; but then
$(\alpha_{1},0,0,0)*A=\alpha_{1}e_{0}$ which has distance $7$.

$G(z)*((f_{4},f_{5},f_{6})-(f_{2},f_{3},f_{4})z)=0$ and so
$H\text{${}^{\text{T}}$}(z)=(f_{4},f_{5},f_{6})-(f_{2},f_{3},f_{4})z$ is a
control matrix. Then
$H(z^{-1})z=\left(\begin{smallmatrix}f_{4}\text{${}^{\text{T}}$}\\\
f_{5}\text{${}^{\text{T}}$}\\\
f_{6}\text{${}^{\text{T}}$}\end{smallmatrix}\right)z-\left(\begin{smallmatrix}f_{1}\text{${}^{\text{T}}$}\\\
f_{2}\text{${}^{\text{T}}$}\\\
f_{3}\text{${}^{\text{T}}$}\end{smallmatrix}\right)$ generates the dual
matrix. Now since $f_{i}\text{${}^{\text{T}}$}=\frac{1}{7}e_{7-i}$ this means
$7*H(z^{-1})z=-\left(\begin{smallmatrix}e_{6}\\\ e_{5}\\\
e_{4}\end{smallmatrix}\right)+\bigl{(}\begin{smallmatrix}e_{3}\\\ e_{2}\\\
e_{1}\end{smallmatrix}\bigr{)}z$ generates the dual matrix. Thus $\mathcal{C}$
is a convolutional $(7,4,3;1,7)$ code which is an LCD code.

######  Example 4.6.

Use the same setup as in Example 4.5 where $F_{7}$ is a Fourier $7\times 7$
matrix. Take $A=\left(\begin{smallmatrix}e_{0}\\\ e_{1}\\\ e_{6}\\\ e_{2}\\\
e_{5}\end{smallmatrix}\right)$. Then it follows from [26] that the code
generated by $A$ is an LCD $[7,5,3]$ code. Let
$B=\left(\begin{smallmatrix}0\\\ 0\\\ 0\\\ e_{4}\\\
e_{3}\end{smallmatrix}\right)$

Define $G(z)=A+Bz=\left(\begin{smallmatrix}e_{0}\\\ e_{1}\\\ e_{6}\\\ e_{2}\\\
e_{5}\end{smallmatrix}\right)+\left(\begin{smallmatrix}0\\\ 0\\\ 0\\\ e_{4}\\\
e_{3}\end{smallmatrix}\right)z$. Then
$(A+Bz)*(f_{0},f_{1},f_{6},f_{2},f_{5})=I_{5}$ and so $G(z)$ has a right
inverse and hence code, $\mathcal{C}$, generated by $G(z)$ is non-
catastrophic. Now $G(z)*\\{(f_{4},f_{3})-(f_{2},f_{5})z\\}=0$ and so
$(f_{4},f_{3})-(f_{2},f_{5})z=H\text{${}^{\text{T}}$}(z)$ is a control matrix.

Now $H(z^{-1})z=\left(\begin{smallmatrix}f_{4}\text{${}^{\text{T}}$}\\\
f_{3}\text{${}^{\text{T}}$}\end{smallmatrix}\right)z-\left(\begin{smallmatrix}f_{2}\text{${}^{\text{T}}$}\\\
f_{5}\text{${}^{\text{T}}$}\end{smallmatrix}\right)=\frac{1}{7}\\{-\left(\begin{smallmatrix}e_{5}\\\
e_{2}\end{smallmatrix}\right)+\left(\begin{smallmatrix}e_{3}\\\
e_{4}\end{smallmatrix}\right)z\\}$.

Thus $-\left(\begin{smallmatrix}e_{5}\\\
e_{2}\end{smallmatrix}\right)+\left(\begin{smallmatrix}e_{3}\\\
e_{4}\end{smallmatrix}\right)z$ generates the dual code of $\mathcal{C}$.

If the field $\mathcal{F}$ has characteristic $2$ the code $\mathcal{C}$ is
dual containing. Thus when $F_{7}$ is a Fourier matrix over $GF(2^{3})$, the
code $\mathcal{C}$ is dual containing. It is easy to check directly that the
free distance of $\mathcal{C}$ is $5$ and is thus an mds convolutional
$(7,5,2;1,5)$ code; this is dual-containing when $F_{7}$ is a Fourier matrix
over $GF(2^{3})$.

If the field does not have characteristic $2$ then define $G(z)=A+iBz$ where
$i$ is a square root of $(-1)$ in the field or in a quadratic extension of the
field. Then again a mds convolutional dual-containing code is obtained. A
quantum convolutional code is constructed from a dual-containing code.

The next example is a prototype example which although small demonstrates the
power of the methods. In larger examples each row is replaced by a block of
rows and lengths, distances are increased substantially.

######  Example 4.7.

Let $X=\left(\begin{smallmatrix}0&1&1&1\\\ 1&1&1&0\\\ 1&1&0&1\\\
1&0&1&1\end{smallmatrix}\right)$ over $GF(2)$. Then
$X^{2}=I_{4},X=X\text{${}^{\text{T}}$}$. Thus DC codes are obtained by taking
rows of $X$ as a generating matrix and deleting corresponding columns of
$X\text{${}^{\text{T}}$}=X$ to obtain a control matrix.

Let $A=\left(\begin{smallmatrix}0&1&1&1\\\
1&1&1&0\end{smallmatrix}\right),B=\left(\begin{smallmatrix}1&1&0&1\\\
1&0&1&1\end{smallmatrix}\right)$ and $\bigl{(}\begin{smallmatrix}A\\\
B\end{smallmatrix}\bigr{)}\bigl{(}\begin{smallmatrix}C&D\end{smallmatrix}\bigr{)}=I_{4}$
is our unit scheme. Now here
$D=B\text{${}^{\text{T}}$},C=A\text{${}^{\text{T}}$}$. Thus $A$ generates a
$[4,2,2]$ code $\mathcal{C}$ with control matrix $D=B\text{${}^{\text{T}}$}$
and so $B$ generates the dual code of $\mathcal{C}$. The code $\mathcal{C}$ is
an $[4,2,2]$ LCD code.

Extend this to a convolutional code $\mathcal{C}$ using $G(z)=A+Bz$. Now
$(A+Bz)(D+Cz)=0$ so that $H\text{${}^{\text{T}}$}(z)=D+Cz$ is a control
matrix. Also $G(z)*C=I_{2}$ and so the code is non-catastrophic. The dual code
of $\mathcal{C}$ is generated by
$H(z^{-1})z=C\text{${}^{\text{T}}$}+D\text{${}^{\text{T}}$}z=A+Bz$ and hence
the code is self-dual. Thus a convolutional self-dual $(4,2,2;1,4)$ is
obtained. From this a quantum error-correcting code of form $[[4,0,4]]$ is
obtained.

$P(z)G(z)$ has distance $\geq 4+(s-1)$ for an information vector $P(z)$ of
support $s$.

Any rows of $U$ may be chosen to generate a code and the resulting code is
automatically an LCD code. For example choose the first and third row of $U$
and get $A=\left(\begin{smallmatrix}0&1&1&1\\\
1&1&0&1\end{smallmatrix}\right),B=\left(\begin{smallmatrix}1&1&1&0\\\
1&0&1&1\end{smallmatrix}\right)$. Then
$D=B\text{${}^{\text{T}}$},C=A\text{${}^{\text{T}}$}$ similar to above. $A$
then generates an LCD $[4,2,2]$ and $G(z)=A+Bz$ generates a non-catastrophic
self-dual $(4,2,2;1,4)$ convolutional code.

This idea of choosing arbitrary rows, when used on large size matrices, lends
itself to forming McEliece type of cryptographic systems.

Larger rates may be obtained. Choose three rows of $U$ and get
$A=\left(\begin{smallmatrix}0&1&1&1\\\ 1&1&1&0\\\
1&1&0&1\end{smallmatrix}\right),B=\left(\begin{smallmatrix}1&0&1&1\end{smallmatrix}\right)$.
Then in general form $C=A\text{${}^{\text{T}}$},D=B\text{${}^{\text{T}}$}$.
$A$ generates a $[4,3,1]$ LCD code. Give $U$ in its row form:
$U=\left(\begin{smallmatrix}E_{0}\\\ E_{1}\\\ E_{2}\\\
E_{3}\end{smallmatrix}\right)$. (In larger length constructions the $E_{i}$
are blocks of matrices of size $n\times 4n$.) Then
$A=\left(\begin{smallmatrix}E_{0}\\\ E_{1}\\\
E_{2}\end{smallmatrix}\right),B=\left(\begin{smallmatrix}E_{3}\end{smallmatrix}\right)$.

Define $G(z)=\left(\begin{smallmatrix}E_{0}\\\ E_{1}\\\
E_{2}\end{smallmatrix}\right)+\left(\begin{smallmatrix}0_{4}\\\ 0_{4}\\\
E_{3}\end{smallmatrix}\right)z=A+B_{1}z$, say; $0_{4}$ indicates here a row of
zeros of length $4$. This gives a $(4,3,1;1)$ convolutional code which is
dual-containing. The distance is $2$. Note that
$(\alpha_{1},\alpha_{2},\alpha_{3})*B_{1}=\alpha_{3}e_{3}$ has distance $3$
except when $\alpha_{3}=0$ in which case
$(\alpha_{1},\alpha_{2},\alpha_{3})A=\alpha_{1}e_{0}+\alpha_{2}e_{1}$ has
distance $2$ or $3$. If $P(z)$ is an information vector of support $s$ then
$P(z)G(z)$ has distance $\geq 2+(s-1)$.

######  Example 4.8.

In another way construct rate $\frac{3}{4}$ and $\frac{1}{4}$ convolutional
codes as follows:

Define $G(z)=\left(\begin{smallmatrix}E_{0}\\\ E_{1}\\\
E_{2}\end{smallmatrix}\right)+\left(\begin{smallmatrix}E_{1}\\\ E_{0}\\\
E_{3}\end{smallmatrix}\right)z+\left(\begin{smallmatrix}E_{2}\\\ E_{3}\\\
E_{0}\end{smallmatrix}\right)z^{2}+\left(\begin{smallmatrix}E_{3}\\\ E_{2}\\\
E_{2}\end{smallmatrix}\right)z^{3}$ and
$H\text{${}^{\text{T}}$}(z)=E_{3}\text{${}^{\text{T}}$}+E_{2}\text{${}^{\text{T}}$}z+E_{1}\text{${}^{\text{T}}$}z^{2}+E_{0}\text{${}^{\text{T}}$}z^{3}$.

Then $G(z)H\text{${}^{\text{T}}$}(z)=0$. Let the code generated by $G(z)$ be
denoted by $\mathcal{C}$. The dual of $\mathcal{C}$ is generated by
$H(z^{-1})z^{3}=E_{0}+E_{1}z+E_{2}z^{2}+E_{3}z^{3}$. Thus $\mathcal{C}$ is a
dual containing $(4,3,9;3)$ convolutional code. Its free distance is $4$
giving a $(4,3,9;3,4)$ convolutional dual-containing code. From this a quantum
$[[4,2,4]]$ convolutional code is obtained.

$P(z)*G(z)$ has distance $\geq 4+(s-1)$ when $P(z)$ is an information vector
of support $s$.

######  Example 4.9.

Hamming convolutional code: Here the Hamming $[7,4,3]$ code is extended to a
$(7,4,3;1,6)$ convolutional code. The distance is $6$ which is twice that of
the Hamming $[7,4,3]$ but it’s also a convolutional code which has its own
decoding techniques. The method is to look at the Hamming code as a unit-
derived code and proceed from there by a general technique of constructing
convolutional codes by the unit-derived method.

The Hamming $[7,4,3]$ is given with generator matrix
$G=\left(\begin{smallmatrix}1&0&0&0&1&1&0\\\ 0&1&0&0&1&0&1\\\ 0&0&1&0&0&1&1\\\
0&0&0&1&1&1&1\end{smallmatrix}\right)$ and check matrix
$H=\left(\begin{smallmatrix}1&1&0&1&1&0&0\\\ 1&0&1&1&0&1&0\\\
0&1&1&1&0&0&1\end{smallmatrix}\right)$. Now $\left(\begin{smallmatrix}G\\\
H\end{smallmatrix}\right)$ is not invertible so this cannot be used for
extending $G$ to be a unit-derived code. For reasons that will appear later
use $L=\left(\begin{smallmatrix}1&1&1&1&1&1&1\\\ 0&1&0&0&1&0&1\\\
0&0&1&0&0&1&1\\\ 0&0&0&1&1&1&1\end{smallmatrix}\right)$ as the generator
matrix666This is obtained by adding the other three rows to the first row to
$G$ above.

Now complete $L$ to a unit $U=\left(\begin{smallmatrix}1&1&1&1&1&1&1\\\
0&1&0&0&1&0&1\\\ 0&0&1&0&0&1&1\\\ 0&0&0&1&1&1&1\\\ 1&0&1&1&1&0&0\\\
0&1&0&0&1&1&1\\\
0&0&0&1&1&1&0\end{smallmatrix}\right)=\left(\begin{smallmatrix}L\\\
K\end{smallmatrix}\right)$, say. It is easy to check that $K$ generates a
$[7,3,3]$ code.

$U$ has inverse $V=\left(\begin{smallmatrix}0&0&1&1&1&0&0\\\ 1&1&0&1&1&1&1\\\
0&1&1&1&0&1&1\\\ 1&1&0&0&1&0&1\\\ 1&0&0&0&1&1&0\\\ 0&1&0&0&0&1&0\\\
0&0&0&1&0&0&1\end{smallmatrix}\right)=\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)$,
where $C$ is $7\times 4$ and $D$ is $7\times 3$.

Form $G(z)=L+\left(\begin{smallmatrix}0\\\
K\end{smallmatrix}\right)z=\left(\begin{smallmatrix}1&1&1&1&1&1&1\\\
0&1&0&0&1&0&1\\\ 0&0&1&0&0&1&1\\\
0&0&0&1&1&1&1\end{smallmatrix}\right)+\left(\begin{smallmatrix}0&0&0&0&0&0&0\\\
1&0&1&1&1&0&0\\\ 0&1&0&0&1&1&1\\\ 0&0&0&1&1&1&0\end{smallmatrix}\right)z$.

Precisely:

  * •

$G(z)$ generates a convolutional $(7,4,3;1)$ non-catastrophic code
$\mathcal{C}$.

  * •

The free distance of $\mathcal{C}$ is $6$ so $G(z)$ generates a $(7,4,3;1,6)$
convolutional code.

  * •

If $P(z)$ is an information vector then the distance of $P(z)*G(z)$ is
$\geq(6+d-1)$ where $d$ is the support of $P(z)$.

  * •

The free distance may be shown from the following observations. Let
$(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})$ be a non-zero vector. Then
$(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})*\left(\begin{smallmatrix}0\\\
K\end{smallmatrix}\right)$ has distance $3$ except when
$\alpha_{2}=0=\alpha_{3}=\alpha_{4}$; but in this case
$(\alpha_{1},al_{2},\alpha_{3},\alpha_{4})*L=\alpha_{1}(1,1,1,1,1,1,1)$ which
has distance $7$.

Term the code generated by $G(z)$ to be the Hamming convolutional code.

######  Example 4.10.

The extended Hamming binary code has generator matrix
$\left(\begin{smallmatrix}1&0&0&0&1&1&1&0\\\ 0&1&0&0&1&1&0&1\\\
0&0&1&0&1&0&1&1\\\
0&0&0&1&0&1&1&1\end{smallmatrix}\right)=\left(\begin{smallmatrix}I_{4}&X\end{smallmatrix}\right)$
say. It is self-dual and $X$ is symmetric and $X^{2}=I$.

Now $\left(\begin{smallmatrix}1&0&0&0&1&1&0&0\\\ 0&1&0&0&1&0&0&1\\\
0&0&1&0&0&0&1&1\\\
0&0&0&1&0&1&1&0\end{smallmatrix}\right)=\left(\begin{smallmatrix}I_{4}&X\end{smallmatrix}\right)$,
say, has $X^{2}=0$ and $X$ is symmetric. Thus
$\left(\begin{smallmatrix}I_{4}&X\\\ X&I_{4}\end{smallmatrix}\right)=I_{8}$ is
an extension to a unitary system. Let $A=(I_{4}+X)$ and $B=(X+I_{4})$ and
system is $\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)$
where now $C=\left(\begin{smallmatrix}I\\\
X\end{smallmatrix}\right),D=\left(\begin{smallmatrix}X\\\
I_{4}\end{smallmatrix}\right)$.

Thus $AD=0$ is $AB\text{${}^{\text{T}}$}=0$ and so $B$ generates the dual code
of the code $\mathcal{C}$ generated by $A$. However
$\left(\begin{smallmatrix}A\\\ B\end{smallmatrix}\right)$ is non singular and
so no non-trivial combination of rows of $A$ can be a combination of rows of
$B$. Thus $\mathcal{C}\cap\mathcal{C}^{\perp}=0$ and $\mathcal{C}$ is an LCD
linear block code.

This can now be extended to a convolutional DC code as follows: $G(z)=A+Bz$.
Then $G(z)*(D+Cz)=0$ and $G(z)*C=I_{4}$ and so $G(z)$ generates a
convolutional $(8,4,4;1)$ non-catastrophic code, $\mathcal{C}$.
$H\text{${}^{\text{T}}$}(z)=D+Cz$ is control matrix so
$H(z^{-1})z=C\text{${}^{\text{T}}$}+D\text{${}^{\text{T}}$}z$ generates the
dual code. Now $C\text{${}^{\text{T}}$}+D\text{${}^{\text{T}}$}z=A+Bz$ and
hence $\mathcal{C}$ is a self-dual convolution code. It s easy to show that
the minimum distance is $6$ and so the code is a $(8,4,4;1,6)$. Further if
$P(z)$ is an information vector then $P(z)*G(z)$ has distance $5+k$ where $k$
is the support of $P(z)$.

Convolutional codes of rate $\frac{3}{4}$ may also be formed from the system.

######  Example 4.11.

See also illuminating examples, such as 5.5, in section 5.2 which use unit-
derived methods on orthogonal type matrices such as Hadamard matrices.

##  5 Higher memory convolutional codes from units

The basic unit-derived scheme from $UV=I$ breaks
$U=\left(\begin{smallmatrix}A\\\ B\end{smallmatrix}\right)$ to derive
$\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)$
and linear block and convolutional codes of memory $1$ from the scheme have
been described and analysed.

Here the unit is broken into more than two blocks and linear block and
convolutional codes of high memory are derived and analysed.

Consider the case $UV=I$ where $U=\left(\begin{smallmatrix}A\\\ B\\\ C\\\
D\end{smallmatrix}\right),V=\left(\begin{smallmatrix}E&F&G&H\end{smallmatrix}\right)$
appropriately, giving another type of (basic) unit scheme:

$\left(\begin{smallmatrix}A\\\ B\\\ C\\\
D\end{smallmatrix}\right)\left(\begin{smallmatrix}E&F&G&H\end{smallmatrix}\right)=I$

First assume the sizes of $A,B,C,D$ are the same. Thus $U$ is a $4n\times 4n$
matrix. Three-quarter rate block linear codes are described by taking
$\left(\begin{smallmatrix}A\\\ B\\\ C\end{smallmatrix}\right)$ as a generator
matrix and then $\left(\begin{smallmatrix}H\end{smallmatrix}\right)$ is a
control matrix. More generally by choosing three of $A,B,C,D$ to form the
generator matrix for a code gives a $[4n,3n]$ three quarter rate code. The
control matrix is immediately clear and is one of $E,F,G,H$. When $U$ is
orthogonal, LCD block codes are obtained from which the convolutional codes
described are DC when the characteristic is $2$.

Memory $3$ codes are described: $G(z)=A+Bz+Cz^{2}+Dz^{3}$ is the generator of
a $(4n,n,3n;3)$ code. This is non-catastrophic as $G(z)E=I_{n}$. The distance
is $d$ where $d$ is a linear functional of the distances of the codes
generated by $A,B,C,D$. Moreover $P(z)G(z)$ has distance $\geq(d+t-1)$ where
$P(z)$ is an information vector and $t$ is the support of $P(z)$.

Then $(A+Bz+Cz^{2}+Dz^{3})((F,G,H)-(E,H,G)z-(H,E,F)z^{2}+(G,F,E)z^{3}=0$ and
so $K\text{${}^{\text{T}}$}(z)=(F,G,H)-(E,H,G)z-(H,E,F)z^{2}+(G,F,E)z^{3}$ is
a control matrix. The matrix of the dual is given by

$K(z^{-1})z^{3}=\left(\begin{smallmatrix}G\text{${}^{\text{T}}$}\\\
F\text{${}^{\text{T}}$}\\\
E\text{${}^{\text{T}}$}\end{smallmatrix}\right)-\left(\begin{smallmatrix}H\text{${}^{\text{T}}$}\\\
E\text{${}^{\text{T}}$}\\\
F\text{${}^{\text{T}}$}\end{smallmatrix}\right)z-\left(\begin{smallmatrix}E\text{${}^{\text{T}}$}\\\
H\text{${}^{\text{T}}$}\\\
G\text{${}^{\text{T}}$}\end{smallmatrix}\right)z^{2}+\left(\begin{smallmatrix}F\text{${}^{\text{T}}$}\\\
G\text{${}^{\text{T}}$}\\\
H\text{${}^{\text{T}}$}\end{smallmatrix}\right)z^{3}$.

This dual code is a $(4n,3n,9n;3)$ code. When $U$ is orthogonal,
$A=E\text{${}^{\text{T}}$},B=F\text{${}^{\text{T}}$},C=G\text{${}^{\text{T}}$},D=H\text{${}^{\text{T}}$}$.

######  Proposition 5.1.

Let $\left(\begin{smallmatrix}A\\\ B\\\ C\\\
D\end{smallmatrix}\right)\left(\begin{smallmatrix}E&F&G&H\end{smallmatrix}\right)=I_{4n}$
be a unit scheme in which $\\{A,B,C,D\\}$ are of the same size. Then

(i) $G(z)=A+Bz+Cz^{2}+Dz^{3}$ is a generator matrix of a $(4n,n,3n;3)$
convolutional code. The distance is a linear functional of the distances of
the codes generated by $\\{A,B,C,D\\}$.

(ii) $P(z)G(z)$ has distance $\geq(d+t-1)$ where $t$ is the support of the
information vector $P(z)$.

(iii) The control matrix of $\mathcal{C}$ is
$(F,G,H)-(E,H,G)z-(H,E,F)z^{2}+(G,F,E)z^{3}$ and the dual code of
$\mathcal{C}$ is generated by
$\left(\begin{smallmatrix}G\text{${}^{\text{T}}$}\\\
F\text{${}^{\text{T}}$}\\\
E\text{${}^{\text{T}}$}\end{smallmatrix}\right)-\left(\begin{smallmatrix}H\text{${}^{\text{T}}$}\\\
E\text{${}^{\text{T}}$}\\\
F\text{${}^{\text{T}}$}\end{smallmatrix}\right)z-\left(\begin{smallmatrix}E\text{${}^{\text{T}}$}\\\
H\text{${}^{\text{T}}$}\\\
G\text{${}^{\text{T}}$}\end{smallmatrix}\right)z^{2}+\left(\begin{smallmatrix}F\text{${}^{\text{T}}$}\\\
G\text{${}^{\text{T}}$}\\\
H\text{${}^{\text{T}}$}\end{smallmatrix}\right)z^{3}$.

(iv) When the full matrix is orthogonal the dual code of $\mathcal{C}$ is
generated by

$\left(\begin{smallmatrix}C\\\ B\\\
A\end{smallmatrix}\right)-\left(\begin{smallmatrix}D\\\ A\\\
B\end{smallmatrix}\right)z-\left(\begin{smallmatrix}A\\\ D\\\
C\end{smallmatrix}\right)z^{2}+\left(\begin{smallmatrix}B\\\ C\\\
D\end{smallmatrix}\right)z^{3}$.

(v) When the full matrix is orthogonal and the characteristic is $2$ the dual
code is generated by $\left(\begin{smallmatrix}C\\\ B\\\
A\end{smallmatrix}\right)+\left(\begin{smallmatrix}D\\\ A\\\
B\end{smallmatrix}\right)z+\left(\begin{smallmatrix}A\\\ D\\\
C\end{smallmatrix}\right)z^{2}+\left(\begin{smallmatrix}B\\\ C\\\
D\end{smallmatrix}\right)z^{3}$. In this case the dual code
$\mathcal{C}^{\perp}$ of $\mathcal{C}$ is a dual containing $(4n,3n,9n;3)$
convolutional code. From this dual containing code of rate $\frac{3}{4}$,
using the CSS construction, a quantum error correcting code of length $4n$ and
rate $\frac{1}{2}$ is obtained.

The example 5.2 below is a very small prototype example with which to
illustrate the general method.

######  Example 5.2.

Consider $X=\left(\begin{smallmatrix}0&1&1&1\\\ 1&1&1&0\\\ 1&1&0&1\\\
1&0&1&1\end{smallmatrix}\right)$ over $GF(2)$. The matrix is orthogonal,
$XX\text{${}^{\text{T}}$}=I_{4}$, and also
$X=X\text{${}^{\text{T}}$}$.777$(I_{4},X)$ is a generator matrix for the
extended Hamming $[8,4,4]$ code. Then $XX\text{${}^{\text{T}}$}=I$ is broken
up to give $\left(\begin{smallmatrix}A\\\ B\\\ C\\\
D\end{smallmatrix}\right)\left(\begin{smallmatrix}E&F&G&H\end{smallmatrix}\right)=I_{4}$
where $\\{A,B,C,D\\}$ are row $1\times 4$ vectors and
$E\text{${}^{\text{T}}$}=A,F\text{${}^{\text{T}}$}=B,G\text{${}^{\text{T}}$}=C,H\text{${}^{\text{T}}$}=D$
as $X$ is orthogonal. Define $G(z)=A+Bz+Cz^{2}+Dz^{3}$. Then $G(z)$ generates
a $(4,1,1;3,12)$ convolutional (non-catastrophic) code $\mathcal{C}$. The
distance is $12$ as the code generated by each of $A,B,C,D$ has distance $3$.

By Proposition 5.1 part (iv), the dual of $\mathcal{C}$ is generated by
$\left(\begin{smallmatrix}C\\\ B\\\
A\end{smallmatrix}\right)+\left(\begin{smallmatrix}D\\\ A\\\
B\end{smallmatrix}\right)z+\left(\begin{smallmatrix}A\\\ D\\\
C\end{smallmatrix}\right)z^{2}+\left(\begin{smallmatrix}B\\\ C\\\
D\end{smallmatrix}\right)z^{3}$.

Thus $\mathcal{C}^{\perp}$ is a dual-containing convolutional rate
$\frac{3}{4}$ code of the form $(4,3,9;3)$. From this a quantum error-
correcting code of rate $\frac{1}{2}$ is formed.

######  Example 5.3.

Golay binary code to convolutional rates $\frac{3}{4}$ and $\frac{1}{4}$ codes
with memory $3$.

Consider the matrix $X$ used in forming the self-dual Golay binary $[24,12,8]$
code in the form $(I_{12},X)$ as in [35]. This $X$ is the reverse circulant
matrix with first row $L=[0,1,1,0,1,1,1,1,0,1,0,0]$. The $X$ is symmetric and
$XX\text{${}^{\text{T}}$}=X^{2}=I_{12}$. Here break $X$ into four blocks,
$X_{1},X_{2},X_{3},X_{4}$ of equal size $3\times 12$. The code generated by
each $X_{i}$ has distance $5$. Then define
$G(z)=X_{1}+X_{2}z+X_{3}z^{2}+X_{4}z^{3}$ and $G(z)$ generates a binary
$(12,3,9;3,20)$ code $\mathcal{C}$. Also $P(z)G(z)$ has distance
$\geq(20+s-1)$ where $P(z)$ is an information vector and $s$ is the support of
$P(z)$. Note that since the rows of $X$ are independent so any non-zero
combination of the rows of $X_{1}\cup X_{2}\cup X_{3}\cup X_{4}$ has distance
$\geq 1$.

As $X$ is orthogonal the dual, $\mathcal{C}^{\perp}$, of $\mathcal{C}$ is
generated by $\left(\begin{smallmatrix}X_{3}\\\ X_{2}\\\
X_{1}\end{smallmatrix}\right)+\left(\begin{smallmatrix}X_{4}\\\ X_{1}\\\
X_{2}\end{smallmatrix}\right)z+\left(\begin{smallmatrix}X_{1}\\\ X_{4}\\\
X_{3}\end{smallmatrix}\right)z^{2}+\left(\begin{smallmatrix}X_{2}\\\ X_{3}\\\
X_{4}\end{smallmatrix}\right)z^{3}$ by Proposition 5.1. Thus
$\mathcal{C}^{\perp}$ is a convolutional $(12,9,9;3)$ code. It is seen that
$\mathcal{C}^{\perp}$ is a dual containing convolutional code of rate
$\frac{3}{4}$ and is used to form a convolutional quantum error correcting
code of rate $\frac{1}{2}$.

###  5.1 Other types

  1. 1.

Cases where the unit system is of the form A unit system
$\left(\begin{smallmatrix}A\\\ B\\\ C\\\
D\end{smallmatrix}\right)\left(\begin{smallmatrix}E&F&G&H\end{smallmatrix}\right)=I$
where $A,B,C$ have the same size $r\times n$ but $D$ has size $s\times n$ with
$s<n$ can be dealt in a similar but more complicated manner. The details are
omitted.

  2. 2.

Cases where the unit system is of size $3n\times 3n$ is dealt with by the
following Proposition:

######  Proposition 5.4.

Let $\left(\begin{smallmatrix}A\\\ B\\\
C\end{smallmatrix}\right)\left(\begin{smallmatrix}D&E&F\end{smallmatrix}\right)=I_{3n}$
be a unit scheme in which $A,B,C$ are of the same size. Let
$G(z)=A+Bz+Cz^{2}$. Then and then verifying that
$(A+Bz+Cz^{2})((E,F)-(D,F)z+(D,E)z^{2}+(0,E-D)z^{3})=0$

This allows the construction of rate $\frac{1}{3}$ and rate $\frac{2}{3}$
convolutional codes which are dual to one another similar to the method and
results in Proposition 5.1.

  3. 3.

A unit scheme which can be broken into blocks of $8$ in an $8n\times 8n$
enables for example convolutional codes with memory $7$ and rate $\frac{1}{8}$
and $\frac{7}{8}$ to be established. In special cases the $\frac{7}{8}$ rate
code is dual containing establishing a rate $\frac{3}{4}$ quantum
convolutional code of memory $8$ similar to Proposition 5.1.

  4. 4.

These types of constructions may be continued. For instance matrices with
blocks of size $n$ and matrix size $2^{i}n\times 2^{i}n$ are more amenable;
when the matrix is orthogonal then dual-containing convolutional codes are
obtainable from which quantum error correcting convolutional codes are formed
with rate $\frac{2^{i-1}-1}{2^{i-1}}$. Details are omitted.

###  5.2 Hadamard type unit codes

A Hadamard matrix is an $n\times n$ matrix such that
$HH\text{${}^{\text{T}}$}=nI_{n}$. These matrices are nice orthogonal type
units and the unit-derived structure is used to construct linear block,
convolutional codes and to types such as LDC, self-dual, DC and quantum codes.
These are not the usual type of Hadamard codes which have small rates but are
of the unit-derived variety with nice features, great distances and can be
constructed to large rates.

Hadamard codes of the usual type $[2^{s},s,s^{s-1}]$ (over $GF(2)$) can be
shown to be unit-derived codes formed from Hadamard $2^{s}\times 2^{s}$
matrices. Any Hadamard matrix may be used with which to construct unit-derived
linear block and convolutional codes and these can be DC or LCD.

Prototype examples are given and these illustrate the general constructions.
Bigger Hadamard type matrices with unit-derived codes will be developed later.
The distances can often be directly calculated. In the examples given, the
Computer Algebra package GAP [40] together with Guava which is embedded in GAP
was used to verify the distances in the block linear cases. GAP has great
implementation of structures over finite fields.

######  Example 5.5.

Let $H$ be a Hadamard $12\times 12$ matrix. Many such are available and here
the computer algebra system GAP [40] is used to generate $H$ and the subsystem
Guava is used to construct the codes and verify their distances in the linear
block cases. The distances can be determined algebraically. Thus $H$ has the
unit form $\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}A\text{${}^{\text{T}}$}&B\text{${}^{\text{T}}$}\end{smallmatrix}\right)=12I_{12}$.
In any field not of characteristic $2$ or $3$, $A$ and $B$ generate LCD codes.
($AB\text{${}^{\text{T}}$}=0$ shows that $B$ generates the dual code of the
code generated by $A$.)

  * •

Three rows of $H$ generate a $[12,3,6]$ LCD code.

  * •

six rows generate a $[12,6,6]$ LCD code.

  * •

Nine rows generate a $[12,9,2]$ LCD code.

  * •

Let $A$ be the first six rows of $H$ and $B$ be the last six rows of $H$.
Define $G(z)=A+Bz$. Then $G(z)$ generates a $(12,6,6;1,12)$ convolutional
code.

  * •

Define $G(z)=A+iBz$ where $i$ is a square root of $(-1)$ in the field or in a
quadratic extension of the field. Then $G(z)$ generates a self-dual
convolutional $(12,6,6;1,12)$. From this a convolutional quantum code of type
$[[12,0,12]]$ is formed.

$GF(5)$ has $2$ as a square root of $(-1)$ so over $GF(5)$ $i$ can be taken to
be $2$. $GF(7)$ does not contain a square root of $-1$ so it needs to be
extended to $GF(7^{2})$. Arithmetic in $GF(5)$ is modular arithmetic.

  * •

Dual-containing convolutional codes of form $(12,9,3;1,d)$ are obtained by
letting $A$ be the first nine rows of $H$ and $B$ the last three rows of $H$
and defining $G(z)=A+iB_{1}z$ where $B_{1}$ has first six rows consisting of
zeros and last three rows consist of $B$. This gives rise to a quantum
convolutional code of the form $[[12,6,d]]$. The $d=4$ but note that
$P(z)G(z)$ has distance $\geq 5+(s-2)$ where $s$ is the support of the
information vector $P(z)$.

  * •

Form $(I_{12},H)$. This is a $[24,12,8]$ code. Form $(I_{12},iH)$, where $i$
is a square of $(-1)$ in the field or in a quadratic extension of the field.
This is a self-dual $[24,12,8]$ code. A quantum $[[24,0,8]]$ code is formed
from this.

In $GF(5)$ the element $2$ is a square root of $(-1)$ and thus $(I_{12},2X)$
gives a self-dual $[24,12,8]$ code in $GF(5)$. The field $GF(7)$ needs to be
extended to $GF(7^{2})$ and then a self-dual code is obtained.

######  Example 5.6.

From a $20\times 20$ Hadamard matrix similar to the process in Example 5.5 the
following codes are obtained:

  1. 1.

$[20,5,10]$,$[20,10,8]$, $[20,15,2]$ LCD codes.

  2. 2.

Using $(I_{20},iX)$ where $i$ is a square root of $(-1)$ gives self-dual
$[40,20,12]$ codes.

  3. 3.

$(20,5,15;3,40)$ convolutional codes are produced.

  4. 4.

$(20,10,10;1,16)$ self-dual convolutional codes are produced leading to
$[[20,0,16]]$ convolutional quantum codes.

######  Example 5.7.

Using a Hadamard $24\times 24$ matrix the following codes are produced as for
Example 5.5:

  1. 1.

$[24,6,12]$, $[24,12,9]$, $[24,18,?]$ LCD codes.

  2. 2.

$(24,6,18;3,48)$ convolutional codes.

  3. 3.

$(24,12,12;1,18)$ DC convolutional codes.

  4. 4.

$[[24,0,18]]$ quantum convolutional codes.

  5. 5.

$(24,6,18;3,d)$ code; $d$ is probably $48$.

  6. 6.

$[48,24,d]$ self-dual codes.

##  6 Low Density Parity Check Codes

A low density parity check, LDPC, code is one where the check/control matrix
of the code has a small number of non-zero entries compared to its length.

The methods devised in previous sections for constructing linear block and
convolutional codes are now used to construct LDPC linear and convolutional
codes. What is required is the scheme produces a check/control matrix with low
density compared to its length. It is known that for best performance of LDPC
codes, there should be be no short cycles in the control matrix and this can
be achieved by the methods.

Given a unit scheme $UV=I$ unit-derived codes are formed by taking any $r$
rows of $U$ as generator matrix and a check matrix is obtained by eliminating
the corresponding columns of $V$. Thus if $V$ itself is of low density then
any such code formed is an LDPC code; if in addition $V$ itself has no short
cycles then any such code formed is an LDC code with no short cycles.

Thus given a unit scheme $UV=I$, where $V$ is of low density and has no short
cycles, choose any $r$ rows of $U$ to form the generator matrix of an $[n,r]$
code $\mathcal{C}$ and deleting the corresponding $r$ columns in $V$ gives a
check matrix for the code and the code $\mathcal{C}$ formed is an LDPC code
with no short cycles in the check or control matrix. The code can also be
specified by choosing the columns of the low density matrix $V$ to form the
control matrix and going to $U$ to choose the rows which form a generator
matrix.

This has been done in [47] for linear block codes. There methods are derived
using units in group rings to produce linear LDPC codes and to produce such
LDPC codes with no short cycles in the the check matrices. Thus a unit system,
$uv=1$, is constructed in a group ring where one of the elements $u,v$, say
$v$, has small support as a group ring element. The $uv=1$ is then mapped to
the corresponding matrix equation, $UV=I$, by a process given in[31], in which
$V$ has low density. Then using unit-derived codes leads to the construction
of LDPC codes as required and when $V$ has no short cycles it leads to the
construction of LDPC codes with no short cycles in the check matrix. It can be
ensured that $V$ has no short cycles by a condition, see [47], on the group
elements with non-zero coefficient used in forming the group ring element $v$
short cycles.

In that paper [47] simulations are made and the examples given are shown to
outperform substantially previously constructed ones of the same size and
rate. Randomly selected LDPC codes with no short cycles are produced from the
same unit. The codes produced are of particular use in applications and
industry where low storage and low power may be a requirement or necessary for
better functioning.

Note that $U$, from which the generator matrix is derived, does not,
necessarily, have low density which is good from the point of the minimum
distance of the code; however as stated in Mackay [39], “Distance isn’t
everything”.

Thus using group rings, systems are constructed $UV=I_{n}$ in which $V$ has
low density with no short cycles anywhere. This gives an enormous freedom in
which to construct LDPC codes with no short cycles. Indeed eliminating any
$(n-r)$ columns of $V$ gives a control matrix, and the generator matrix is
formed by using the rows from $U$ corresponding to the eliminated columns of
$V$; the result is an $[n,r]$ LDPC code. Thus given $UV=I_{n}$ where $V$ has
low density and no short cycles allows the construction of many LDPC codes
with no short cycles.

In previous sections, methods are given for constructing convolutional codes
from the unit-derived formula $\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)=I_{n}$
from $UV=I_{n}$ using all the components $A,B,C,D$. Convolutional codes of
higher memory are obtained by further breaking up the unit system in blocks.
These techniques may also be applied for constructing convolutional LDPC codes
with no short cycles in the control matrix.

Considering the basic formula and when $A,B$ have the same size, and $n$ is
even, then $G(z)=A+Bz$ generates a non-catastrophic convolutional code. The
control matrix is $D-Cz$ and the dual code is generated by
$C\text{${}^{\text{T}}$}-D\text{${}^{\text{T}}$}z$. If $V$ is of low density
and has no short cycles then
$C\text{${}^{\text{T}}$}-D\text{${}^{\text{T}}$}z$ is of low density and has
no short cycles. Thus the codes derived is a convolutional LDPC code with no
short cycles.

It is difficult to describe explicitly the LDPC codes derived as for
applications large lengths are required. Note that the method is very general
and length and rate achieved can be decided in advance. We will concentrate on
extending two of the examples in [47] to construct LDC convolutional codes
with no short cycles.

Only basic information on group rings is required. A good nice book on group
rings is [6] and also the basic information may be found online by a simple
search.

Low density convolution codes and with no short in the control matrix are
constructed by applying the methods in the previous sections together with the
methods described in [47] for constructing LDPC linear codes with no short
cycles. The following algorithm describes the constructions in general:

######  Algorithm 1.

  1. 1.

In a group ring with group size $n$ find a unit and its inverse $uv=1$ where
$v$ has small support and no short cycles. The size $n$ of the group should be
large and the support of $v$ relatively small compared to $n$.

  2. 2.

From $uv=1$ go over to the matrix embedding of the group ring in a ring of
matrices of size $n\times n$, as in [31], to get a unit scheme $UV=I_{n}$ of
matrices where $V$ is of low density and has no short cycles.

  3. 3.

Choose $r$ columns of $V$ to eliminate to form an $n\times(n-r)$ matrix which
will be a control matrix for a $[n,r]$ code. A generator matrix for this code
is the $r\times n$ matrix formed by selecting the $r$ rows from $U$
corresponding in order to the $r$ columns eliminated from $V$.

  4. 4.

The unit scheme from item 2 may be presented as $\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)$
where $A$ has size $r\times n$, $B$ has size $(n-r)\times n$, $C$ has size
$n\times r$ and $D$ has size $n\times(n-r)$. Now here both $C,D$ are of low
density and have no short cycles. An LDPC code with no short cycles in the
control matrix is given by $AD=0$ as in [47]. But also notice $BC=0$ gives a
LDPC code in addition.

  5. 5.

The unit scheme in item 4 as in previous sections is extended to $G(z)=A+Bz$
when $A,B$ have the same size (in which case the rate is $1/2$) or, when $A$
has size heater than the size of $B$, to $G(z)=A+B_{1}z$ where $B_{1}$ is
obtained by extending $B$ with zero rows to be the size of $A$. Then $G(z)$
generates a convolutional memory $1$ code which is non-catastrophic and has
low density control matrix with no short cycles. The control matrix is
$D-C_{1}z$ where $C_{1}$ is $C$ or a submatrix of $C$ as explained above.

  6. 6.

Obtaining memory greater than $1$ from the unit matrix scheme $UV$ derived
from the group ring unit $uv$ also follows in a similar manner as described
earlier. Examples of such are given below.

Examples must be of large length in order to satisfy the low density
criterion. In general the examples in [47] are taken from unit-derived codes
within $\mathbb{Z}_{2}(C_{n}\times C_{4})$, where $\mathbb{Z}_{2}=GF(2)$ is
the field of two elements.

“The matrices derived are then submatrices of circulant-by-circulant matrices
and are easy to program. They are not circulant and thus are not cyclic codes.
Having circulant-by-circulant rather than circulant allows a natural spreading
of the non-zero coefficients and gives better distance and better
performance.”

Assume that $C_{n}$ is generated by $g$ and $C_{4}$ is generated by $h$. Every
element in the group ring is then of the form:
$\displaystyle\sum_{i=0}^{n-1}(\alpha_{i}g^{i}+h\beta_{i}g^{i}+h^{2}\gamma_{i}g^{i}+h^{3}\delta_{i}g^{i})$,
with $\alpha_{i},\beta_{i},\gamma_{i},\delta_{i}\in\mathbb{Z}_{2}$.

######  Example 6.1.

Examples of $[96,48]$ LDPC codes are given in sections 3.2, 3.4 of [47]. These
examples are derived from the group ring $\mathbb{Z}_{2}(C_{24}\times C_{4})$.

The check element
$v=g^{24-9}+g^{24-15}+g^{24-19}+hg^{24-3}+hg^{24-20}+h^{2}g^{24-22}+h^{3}g^{24-22}+h^{3}g^{24-12}$
is used to define an LDPC linear code.

Then $v$ has no short cycles in its matrix $V$ and just $8$ or less non-zero
elements in each row and column. Any choice of columns of $V$ will give an
LDPC block linear code. A pattern to delete half the columns from the matrix
$V$ of $v$ is chosen to produce a rate $1/2$ code and is simulated and
compared to other LDPC codes, outperforming these even when random columns are
chosen.

This selection is then presented as $\left(\begin{smallmatrix}A\\\
B\end{smallmatrix}\right)\left(\begin{smallmatrix}C&D\end{smallmatrix}\right)$
where $A$ has size $48\times 96$, $B$ has size $48\times 96$, $C$ has size
$96\times 48$ and $D$ has size $96\times 48$. Then define $G(z)=A+Bz$ to
obtain a convolutional $[96,48,48;1]$ low density parity check code. The
control matrix is $D-Cz$ which is $D+Cz$ as the characteristic is $2$.

In this case the matrix $U$ has the form $\left(\begin{smallmatrix}A\\\ B\\\
C\\\ D\end{smallmatrix}\right)$ and $V$ has the form
$\left(\begin{smallmatrix}E&F&G&H\end{smallmatrix}\right)$ where $A,B,C,D$
have size $24\times 96$ and $E,F,G,H$ have size $96\times 24$ and each of
$E,F,G,H$ have low density. Then as in Proposition $G(z)=A+Bz+Cz^{2}+Dz^{3}$
defines a convolutional $(96,24,24*3;1)$ convolutional code which has low
density check matrix.

## References

  * [1] Richard E. Blahut, Algebraic Codes for data transmission, Cambridge University Press, 2003.
  * [2] Rolf Johannesson and Kamil Zigangirov, Fundamentals of Convolutional Coding, Wiley-IEEE Press, 1999.
  * [3] R.J. McEliece, Theory of Information and Coding, 2nd ed., Cambridge University Press, 2002.
  * [4] R. J. McEliece, “The algebraic theory of convolutional codes”, in Handbook of Coding Theory, Volume I, North Holland, Elsevier Science, 1998.
  * [5] F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes, Elsevier, 1977.
  * [6] César Milies & Sudarshan Sehgal, An introduction to Group Rings, Klumer, 2002.
  * [7] Bocharova, I., Hug, F., Johannesson, R., & Kudryashov, B. (2012). “Dual convolutional codes and the MacWilliams identities”, Problems of Information Transmission, 48(1), 21-30, 2012.
  * [8] Almeida, P., Napp, D., Pinto, R., “A new class of superregular matrices and MDP convolutional codes”, Linear Algebra and its Applications, 439 (7), 2145-2157, 2013
  * [9] Almeida, P., Napp, D., Pinto, R., “Superregular matrices and applications to convolutional codes”, Linear Algebra and its Applications, 499, 1-25, 2016.
  * [10] Guardia, G., “On negacyclic MDS-convolutional codes”, Linear Algebra and its Applications, 448 (Supplement C), 85-96, 2014\.
  * [11] Muñoz Porras, J., Domínguez Pérez, J., Iglesias Curto J., Serrano Sotelo, G., “ Convolutional Goppa codes”, IEEE Trans. Inf. Th., 52 (1), 340–344, 2006.
  * [12] Claude Carlet, Sihem Mesnager, Chunming Tang, Yangeng Qi, “Euclidean and Hermitian LCD MDS codes”, Designs, Codes and Cryptography Vol. 86, no. 11, 2605-2618, 2018. (ArXiv: 1702.08033, 2017.)
  * [13] Claude Carlet, Sihem Mesnager, Chunming Tang, Yangeng Qi, Ruud Pelikaan, “Linear codes over $F_{q}$ are equivalent to LCD codes for $q>3$ ”, IEEE Transactions on Information Theory, Vol. 64 , no. 4, 3010-3017, 2018.
  * [14] Claude Carlet, Sihem Mesnager, Chunming Tang, Yangeng Qi, “New characterization and parametrization of LCD codes”, IEEE Transactions on Information Theory ( Early Access ), 2018. (ArXiv:1709.03217, 2017.)
  * [15] Claude Carlet, Boolean Functions for Cryptography and Error Correcting Codes, Chapter of the monograph Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pages 257-397. Cambridge University Press, Cambridge, (Y. Crama and P. Hammer eds), 2010.
  * [16] Claude Carlet, S. Guilley, “Complementary dual codes for counter measures to side-channel attacks”, In: E.R. Pinto et al (eds) Coding Theory and applications, CIM series in Mathematical Sciences, 3, 97-105, Springer Verlag 2014: and J. Adv. in Math. of Comm., 10(1), 131-150, 2016.
  * [17] J. L. Massey, “Linear codes with complementary duals”, Discrete Math., Vol.105/106, 337-380, 1992.
  * [18] J. L. Massey, “Reversible codes”, Information and Control, vol. 7, no.3, 369-380, 1964.
  * [19] Sihem Mesnager, Chunming Tang, Yanfeng Qi, “Complementary Dual Algebraic Geometry Codes”, IEEE Transactions on Information Theory, Vol 64, 4 , 2018.
  * [20] R. Pellikaan, “On decoding by error location and dependent sets of error positions”, Discrete Math., Vol. 106/107, 369-381, 1992.
  * [21] A.R. Calderbank, E.M. Rains, P.M. Shor and N.J.A. Sloane. “Quantum error correction via codes over $GF(4)$”, IEEE Transactions on Information Theory 44(4), pp. 1369-1387, 1998.
  * [22] Andrew M. Steane, “Simple quantum error correcting codes” Physical Review A, 54(6):4741–4751, 1996.
  * [23] A. Calderbank and P. Shor,“Good quantum error-correcting codes exist”, Physical Review A, Vol. 54 (2), 1098-1105, 1996.
  * [24] T. Hurley, “Linear complementary dual, maximum distance separable codes”,
https://arxiv.org/abs/1901.04241

  * [25] T. Hurley, D. Hurley, B. Hurley, “Quantum error-correcting codes: the unit-derived strategy”, Intl. J. of Information and Coding Theory, Vol.5 No.2, 169-182, 2018.
  * [26] Ted Hurley, “Linear block and convolutional codes to required rate, distance and type”, Intelligent Computing. SAI 2022, pp 129-157, Lecture Notes in Networks and Systems, vol 507. Springer, pp 129-157, 2022.
  * [27] Ted Hurley, “Convolutional codes from unit schemes”, ArXiv: 1412.1695, 23 pp., 2014.
  * [28] H. Gluesing-Luerssen, U. Helmke, J. I. Iglesias Curto, “Algebraic decoding for doubly cyclic convolutional codes”, arXiv:0908.0753.
  * [29] H. Gluesing-Luerssen and G. Schneider, “A MacWilliams identity for convolutional codes: The general case,” IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 2920–2930, Jul. 2009.
  * [30] Ted Hurley, “Maximum distance separable codes to order”, Global J. Science, Frontier Research, Math. & Division Sc., 21 (4), 11-22, 2021. Also https://arxiv.org/abs/1902.06624.
  * [31] Ted Hurley, “Group rings and rings of matrices”, Intn. Journal of Pure and Applied Mathematics, Vol.31, No. 3, 319-335, 2006.
  * [32] T Hurley, “Solving underdetermined systems with error-correcting codes”, Intl. J. of Information and Coding Theory, Vol. 4, 201-221, 2017.
  * [33] Barry Hurley and Ted Hurley, “Systems of MDS codes from units and idempotents”, Discrete Math., 335, 81-91, 2014.
  * [34] Ted Hurley, “Convolutional codes from units in matrix and group rings”, Int. J. Pure Appl. Math., 50, no. 3, 431-463, 2009.
  * [35] I. McLoughlin and T. Hurley, “A Group Ring Construction of the Extended Binary Golay Code”, in IEEE Transactions on Information Theory, vol. 54, no. 9, pp. 4381-4383, Sept. 2008.
  * [36] J. Rosenthal & R. Smarandache, “Maximum distance separable convolutional codes”, Appl. Algebra Engrg. Comm. Comput. 10 (1), 15-32, 1999.
  * [37] Rosenthal, J., “Connections between linear systems and convolutional codes”, pp. 39-66 in: Marcus, B; Rosenthal, J. Codes, systems, and graphical models, Minneapolis, New York, 1999.
  * [38] J. Rosenthal, “ An algebraic decoding algorithm for convolutional codes”, in G. Picci and D.S. Gilliam, editors, Dynamical Systems, Control, Coding, Computer Vision: New Trends, Interfaces, and Interplay, pages 343-360. Birkhäuser, Boston-Basel-Berlin, 1999.
  * [39] David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003.
  * [40] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.12.2; 2022. (https://www.gap-system.org)
  * [41] Paul Hurley and Ted Hurley, “Module codes in group rings”, Proc. IEEE Int. Symp. Inform. Theory, Nice, pp 1981-1985, 2007.
  * [42] Paul Hurley and Ted Hurley, “Codes from zero-divisors and units in group rings”, Int. J. Inform. and Coding Theory, 1, 57-87, 2009.
  * [43] Paul Hurley and Ted Hurley, “Block codes from matrix and group rings”, Chapter 5, 159-194, in Selected Topics in Information and Coding Theory eds. I. Woungang, S. Misra, S.C. Misma, World Scientific 2010.
  * [44] Paul Hurley and Ted Hurley, “LDPC and convolutional codes from matrix and group rings”, Chapter 6, 195-239, in Selected Topics in Information and Coding Theory eds. I. Woungang, S. Misra, S.C. Misma, World Scientific 2010.
  * [45] T. Hurley, “Convolutional codes from unit schemes”, ArXiv 1412.1695; revised 2020.
  * [46] T. Hurley, D. Hurley, “Coding theory: the unit-derived methodology”, Intl. J. of Information and Coding Theory, 5(1), 55-80, 2018.
  * [47] Ted Hurley, Paul McEvoy and Jakub Wenus, “Algebraic constructions of LDPC codes with no short cycles”, Intl. J. of Inform. and Coding Theory, Vol 1, Issue 3, 285-297, 2010.
  * [48] R. Smarandache, H. Gluesing-Luerssen, J. Rosenthal, “Constructions for MDS-convolutional codes”, IEEE Trans. Inform. Theory, vol. IT-47, 2045-2049, 2001.