where $x·y$ denotes the standard inner product in ${\mathbb{F}}_2^n$. The code C is self-orthogonal if $C\subseteq C^{\perp }$. It is a well-known fact that every doubly even binary code is self-orthogonal (see, for example, [7]).

where $x·y=x_1{y}_1+x_2{y}_2+\dots +x_n{y}_n$ for $x=(x_1,x_2,\dots ,x_n)$ and $y=(y_1,y_2,\dots ,y_n).$ The code C is self-orthogonal if $C\subseteq C^{\perp }$ and self-dual if $C=C^{\perp }.$ Every ${\mathbb{Z}}_4$-code C contains a set of $k_1+k_2$ codewords $c_1,\dots ,c_{k_1},c_{k_1+1},\dots ,c_{k_1+k_2}$ such that each codeword in C is uniquely expressible in the form

where, for $1\le i\le k_1$, $a_i\in {\mathbb{Z}}_4$, and $c_i$ has at least one coordinate equal to 1 or 3, and, for $k_1+1\le i\le k_1+k_2$, $a_i\in {\mathbb{Z}}_2$, and $c_i$ has all coordinates equal to 0 or 2. It is said that C is of type $4^{k_1}{2}^{k_2}$. The matrix whose rows are elements of the set $c_1,\dots ,c_{k_1},c_{k_1+1},\dots ,c_{k_1+k_2}$ is called the generator matrix of a ${\mathbb{Z}}_4$-code C. There are two binary linear codes of length n associated with C. These codes are the residue code, defined as $Res\left(C\right)=c\in C$, and the torsion code, defined as $Tor\left(C\right)=2c\in C$.

where F, B, H are binary matrices, $I_k$ is the $k\times k$ identity matrix and O is a $\left(n-2k\right)\times k$ zero matrix (see [7] (p. 497)). The type of such self-dual ${\mathbb{Z}}_4$-code C is $4^k{2}^{n-2k}$. If C has the generator matrix of the form (1), then the generator matrices of its residue code and its torsion code are

where $f_s$ denotes the s-th row vector of the matrix F, $1\le i<j\le k$, $1\le s\le k$. The diagonal elements can be chosen freely, and for different choices of diagonal elements, we obtain monomially equivalent ${\mathbb{Z}}_4$-codes. The previous discussion gives the standard way to construct a self-dual ${\mathbb{Z}}_4$-code starting from any doubly even binary code. Given a doubly even binary code $C^{\left(1\right)}$ with a generator matrix of the form (2), one can find a dual code $C^{\left(2\right)}$ with a generator matrix of the form (3). Then, it only remains to choose one of the possible $2^{{\displaystyle \frac{k(k-1)}{2}}}$ suitable choices for the matrix B to obtain a generator matrix of a ${\mathbb{Z}}_4$-code of the form (1).

where $B=\left[b_{s,t}\right]$ is a $k\times k$ binary matrix for which the self-duality condition (4) holds. Let $(i,j)$, $1\le i<j\le k$, be an upper diagonal position of B such that $b_{ij}=0$. Let $B^{\prime }=\left[b_{s,t}^{\prime }\right]$ be a $k\times k$ binary matrix such that

for all $1\le s<t\le k$, and such that the ${\mathbb{Z}}_4$-code $C^{\prime }$ is generated by $G\left(B^{\prime }\right)$, i.e.,

is self-dual (condition (4) holds for $B^{\prime }$). We say that $B^{\prime }$ is the $(i,j)$-neighbor of B, and that the code $C^{\prime }$ is the $(i,j)$-neighbor of the code C.

where $g_s$, $s\in 1,2,\dots ,n-k$ is the s-th row of the matrix $G\left(B\right)$. Let $v^{\prime }\in C^{\prime }$ be

i.e., $v^{\prime }$ is the codeword in $C^{\prime }$ generated by the same coefficients $c_1,c_2,\dots ,c_{n-k}$ as v.

• Start with an arbitrary matrix B.

• In each iteration of the algorithm do the following.

  2.1

  Generate a self-dual ${\mathbb{Z}}_4$-code C with the generator matrix $G\left(B\right)$, and evaluate

  $$D=\left|v\in C|0<w{t}_E\left(v\right)<20\right|,$$

  (this is $A_4+A_8+\dots +A_{16}$ from Corolary 2).

  2.2

  If $D=0$ then C is near-extremal.

  2.3

  Determine the sets $S_{16}$ and $S_{20}$ defined in the Corollary 2.

  2.4

  For every upper diagonal element $(i,j)$ of the matrix B that is equal to 0, determine the $(i,j)$-neighbor $C^{\prime }$. If the near-extremality of the corresponding neighbor is undetermined, from Table 1, evaluate the numbers $A_{16}^{+}$, $A_{20}^{-}$ and $d=D-A_{16}^{+}+A_{20}^{-}$.

  2.5

  All $C^{\prime }$ that have $d=0$ are near-extremal.

  2.6

  Mark all neighbors of B as checked.

  2.7

  Repeat the process with the next unchecked and randomly generated matrix B.