Matrix Factorization and Some Fast Discrete Transforms

Abstract

In this paper, three discrete transforms related to vector spaces over finite fields are studied. For our purposes, and according to the properties of the finite fields, the most suitable transforms are as follows: for binary fields, this is the Walsh–Hadamard transform; for odd prime fields, the Vilenkin–Chrestenson transform; and for composite fields, the trace transform. A factorization of the transform matrices using Kronecker power is given so that the considered discrete transforms are reduced to the fast discrete transforms. Examples and applications are also presented of the considered transforms in coding theory for calculating the weight distribution of a linear code.

1. Introduction

The Fourier-type discrete transforms have various applications [1], including signal processing, communications, and cryptography. As their special application, we indicate the implementation for digital devices related to spectral logic [2]. The discrete transformations are also important in studying the cryptographic properties of Boolean functions [3,4,5], and they are used in the study of self-dual bent functions (see [6]). A description of fast Fourier-type discrete transforms can be found in the popular book by Joux [3] (Chapter 9).

Fast discrete transforms are widely used in coding theory, especially for computing some important parameters of linear codes over finite fields. The problems for computing the weight distribution, minimum distance, and covering radius of a linear code are NP-complete [7]. Algorithms that solve these problems are usually based on an exhaustive search [8,9,10]. Connections between discrete Fourier-type transforms, on the one hand, and weight distribution and covering radius, on the other, were established by Karpovsky [11,12], but he mainly considered binary codes. The algorithms based on fast discrete transforms are well suited for linear codes with small rates (large length and small dimension). The present study is a continuation of the recent work of the authors on the transforms’ applications in coding theory [13,14].

Fast discrete transforms, in most cases, can be represented as a matrix by vector multiplication, where the matrix is recursively defined by a Kronecker product. The transition from discrete to fast discrete transform is based on the fact that the transform matrix defined recursively by a Kronecker product can be factorized into a product of sparse matrices. We prove that the sparse matrices in this product commute, which is important for some implementations [15]. As a result, this manages to reduce the complexity of computing the discrete transform from $O\left(n^2\right)$ to $O(nlogn)$, where n is the size of the transform matrix.

The fast discrete transforms are implemented with butterfly diagrams and algorithms (see, for example, [16]). These types of algorithms have very efficient natural implementations with the SIMD model of parallelization, especially with the CUDA platform. The speedup of the parallel implementation of Walsh–Hadamard transform in GPU can be seen in [15].

In addition to the basic properties of the considered discrete transforms, we dwell in more detail on the following cases concerning linear codes over a finite field with q elements:

(1)

If $q=2$, we consider the Walsh–Hadamard (Walsh) transform. This transform is a square-wave analog to the Fourier transform, based on Walsh functions [17,18]. The Walsh transform matrices are related to the Hadamard matrices of the Sylvester type. The Hadamard matrix $H_n$, $n\in \mathbb{N}$, is the n-th Kronecker power of the matrix $H_1=\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill -1\end{array}\right)$. This allows us to represent $H_n$ as a product of rare matrices [19], which leads to a fast algorithm. As the computations of the transform are addition and subtraction only, it can be implemented by a butterfly algorithm [3,16]. Therefore, this transform is best suited for vector spaces over the binary field.

(2)

If q is an odd prime, we use the Vilenkin–Chrestenson transform [20,21]. This transform is defined over the ring of integers modulo q${\mathbb{Z}}_q=\{0,1,2,\dots ,q-1\}$. As it is well known, ${\mathbb{Z}}_q$ is a field only when q is a prime. We consider linear codes over a field, so this transform is suitable for our research for prime q. The Walsh–Hadamard transform is a special case of the Vilenkin–Chrestenson transform, namely for $q=2$. Information about the Vilenkin–Chrestenson transform, as well as other discrete Fourier-type transforms, is given in [2,22,23].

(3)

If $q=p^s$ for a prime p and positive integer $s>1$, we use the trace transform for linear codes over the filed ${\mathbb{F}}_q$.

The aim of this paper is to present methods for factorization of transform matrices when they are represented as a Kronecker product and their application for faster computation of the weight distribution of linear codes over prime and composite finite fields. We also give specific examples for better understanding. This consideration is essential for the modification of algorithms for computing the weight spectrum and covering radius of a linear code in some cases [13,14].

Section 2 presents the information we need about finite fields and linear codes. In Section 3, we present some useful properties of the Kronecker product. The factorization of the k-th Kronecker power of a square matrix is also given in this part. Section 4, Section 5 and Section 6 are devoted to the Walsh–Haramard, Vilenkin–Chrestenson, and trace transform, respectively.

2. Finite Fields and Linear Codes

Let ${\mathbb{F}}_q$ be a finite field, or Galois field, with q elements and the prime p be its characteristic. Detailed information about finite field properties is given in [24]. Any finite extension $\mathbf{F}$ over the field $\mathbf{K}$ is a linear space over $\mathbf{K}$ and a basis of the field $\mathbf{F}$ is any basis of this linear space. In particular, the field ${\mathbb{F}}_{p^m}$, as a finite m-powered extension of its prime subfield ${\mathbb{F}}_p$, is isomorphic to the linear space ${\mathbb{F}}_p^m$. If ${\beta }_1,{\beta }_2,\dots ,{\beta }_m\in {\mathbb{F}}_{p^m}$ is a basis of ${\mathbb{F}}_{p^m}$ over the prime subfield ${\mathbb{F}}_p$ and $\alpha \in {\mathbb{F}}_{p^m}$, then $\alpha ={\lambda }_1{\beta }_1+{\lambda }_2{\beta }_2+\cdots +{\lambda }_m{\beta }_m$, where ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_m\in {\mathbb{F}}_p$.

 Definition 1. 

Let $K={\mathbb{F}}_q$, $F={\mathbb{F}}_{q^m}$ and $\alpha \in F$. Trace $T{r}_{F/K}\left(\alpha \right)$ of the element α over K is

$$T{r}_{F/K}\left(\alpha \right)=\alpha +{\alpha }^q+{\alpha }^{q^2}+\dots +{\alpha }^{q^{m-1}}.$$

If K is a prime subfield of F, then $T{r}_{F/K}\left(\alpha \right)$ is called absolute trace of the element α and it is denoted by $T{r}_F\left(\alpha \right)$.

If the field is given in advance, the absolute trace is denoted only by $Tr\left(\alpha \right)$ and called just trace.

Definition 2. 

Two bases ${\beta }_1,\dots ,{\beta }_m\in F$ and ${\beta }_1^{\prime },\dots ,{\beta }_m^{\prime }\in F$ of the field F over the subfield K are called dual, if

$$T{r}_{F/K}\left({\beta }_i{\beta }_j^{\prime }\right)=\left\{\begin{array}{ccc}0,\hfill & if\hfill & i\ne j,\hfill \\ 1,\hfill & if\hfill & i=j.\hfill \end{array}\right.,$$

for any $1\le i,j\le m$. A basis that is dual of itself is called a self-dual basis.

In other words, the trace $Tr\left({\beta }_i{\beta }_j\right)$ is equal to the Kronecker $\delta$ of i and j for all $i,j\in \{1,2,\dots ,m\}$. Each basis has exactly one dual basis. The following theorem gives a sufficient and necessary condition for the existence of a self-dual basis.

Theorem 1 

([25] (Theorem 5.1.18), [26]). There exists a self-dual basis of $F={\mathbb{F}}_{q^m}$ over $K={\mathbb{F}}_q$ if and only if either q is even or both q and m are odd.

For the purposes of the transforms, the elements of ${\mathbb{F}}_q$ are ordered, i.e., ${\mathbb{F}}_q=\{{\alpha }_0=0,{\alpha }_1,\dots ,{\alpha }_{q-1}\}$. In most cases, when q is composite, we use the lexicographic ordering of the elements, depending on the chosen basis. If ${\beta }_1,\dots ,{\beta }_m$ is a basis of ${\mathbb{F}}_q$, $q=p^m$, over ${\mathbb{F}}_p$ for the prime p, then any elements $\alpha \in {\mathbb{F}}_q$ can be written as $\alpha ={\lambda }_1\left(\alpha \right){\beta }_1+\cdots +{\lambda }_m\left(\alpha \right){\beta }_m$, where ${\lambda }_i\left(\alpha \right)\in {\mathbb{F}}_p$, $i=1,\dots ,m$. There is one-to-one correspondence ${\sigma }_{\beta }$ between ${\mathbb{F}}_{p^m}$ and ${\mathbb{F}}_p^m$ defined by this basis. For $\alpha \in {\mathbb{F}}_{p^m}$, ${\sigma }_{\beta }\left(\alpha \right)=({\lambda }_1\left(\alpha \right),\dots ,{\lambda }_m\left(\alpha \right))$. To order the elements of ${\mathbb{F}}_q$, we use the lexicographic ordering of the vectors in ${\mathbb{F}}_p^m$, namely

$$(0,\dots ,0,0)<(0,\dots ,0,1)<(0,\dots ,0,2)<\cdots <(p-1,\dots ,p-1).$$

The position of the zero element is constant, whereas all other elements could change their positions if the basis is changed.

Let ${\mathbb{F}}_q^n$ be the n-dimensional vector space over the finite field ${\mathbb{F}}_q=\{0,{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_{q-1}\}$, where q is a power of a prime number. Any k-dimensional linear subspace $C\subset {\mathbb{F}}_q^n$ is called linear code, and it is said to be ${[n,k]}_q$ code with length n and dimension k. A vector $v\in C$ is called a codeword of C. The (Hamming) weight $wt\left(v\right)$ of a vector $v\in {\mathbb{F}}_q^n$ is the number of the nonzero coordinates of v. The weight distribution of the code C is the finite sequence $(A_0,A_1,\dots ,A_n)\in {\mathbb{Z}}^{n+1}$, where $A_u$ is the number of the codewords with weight $u,u=0,1,\dots ,n$, and the weight enumerator of the code C is the polynomial $W_C\left(y\right)=1+A_1{y}^1+\cdots +A_n{y}^n$.

A linear code can be represented by its generator matrix, i.e., a $k\times n$ matrix whose rows form a basis of C as a vector space over ${\mathbb{F}}_q$. We use another representation of the $[n,k]$ linear code C that depends on the chosen generator matrix G. We define a characteristic function $f_G:{\mathbb{F}}_q^k\to \mathbb{Z}$ of the code C with respect to its generator matrix G in the following way.

Definition 3. 

The value of the characteristic function $f_G\left(x\right)$ of the linear ${[n,k]}_q$ code C with respect to the generator matrix G is the number of the columns in G, which are proportional (with non zero coefficients) of x, for $x\in {\mathbb{F}}_q^k$. If $f_G\left(0\right)=0$ we say that the code has full length.

Obviously, if $x_1$ and $x_2$ are proportional vectors in ${\mathbb{F}}_q^k$, then $f_G\left(x_1\right)=f_G\left(x_2\right)$. Since a linear code has more than one generator matrix (in the general case), it has more than one characteristic function.

3. Factorization of Kronecker Power

Kronecker product of the matrices $A={\left(a_{ij}\right)}_{s_1\times t_1}$ and $B={\left(b_{ij}\right)}_{s_2\times t_2}$ is the $(s_1{s}_2\times t_1{t}_2)$ matrix

$$A\otimes B=\left(\begin{array}{cccc}\hfill a_{11}B& \hfill a_{12}B& \hfill \dots & \hfill a_{1t_1}B\\ \hfill a_{21}B& \hfill a_{22}B& \hfill \dots & \hfill a_{2t_1}B\\ \hfill \dots \\ \hfill a_{s_{1}1}B& \hfill a_{s_{1}2}B& \hfill \dots & \hfill a_{s_1{t}_1}B\end{array}\right).$$

We give some elementary properties of the Kronecker product:

$$A\otimes (B\otimes C)=(A\otimes B)\otimes C,$$

(1)

$$(A+B)\otimes (C+D)=A\otimes C+A\otimes D+B\otimes C+B\otimes D,$$

(2)

$$(A\otimes B)(C\otimes D)=\left(AC\right)\otimes \left(BD\right).$$

(3)

Kronecker’s product is not commutative.

The k-th Kronecker power of a square matrix M is defined as follows:

$${\otimes }^{2}M=M\otimes M,{\otimes }^{k+1}M=M\otimes \left({\otimes }^{k}M\right),k>1.$$

If M is a square matrix of size t, then ${\otimes }^{k}M$ is a square matrix of size $t^k$.

Good [19] showed that the Kronecker power could be reduced to the usual row-by-column multiplication of some sparse matrices. This fact stands also for the Kronecker power of a square matrix.

Theorem 2. 

Let M be a square matrix of size t and k be a positive integer. Then

$${\otimes }^{k}M=B_1·B_2\cdots B_k,$$

(4)

where $B_l=I_{t^{l-1}}\otimes M\otimes I_{t^{k-l}}$, $1\le l\le k$, and $I_s$ is the identity matrix of size s.

Proof. 

The proof of the theorem is made by induction. The statement is obvious for $k=1$:

$${\otimes }^{1}M=B_1=I_{t^{1-1}}\otimes M\otimes I_{t^{1-1}}=I_1\otimes M\otimes I_1=M.$$

Let (4) be true for all Kronecker powers smaller than k. Specifically,

$${\otimes }^{k-1}M=B_1^{\prime }·B_2^{\prime }\cdots B_{k-1}^{\prime },$$

where $B_l^{\prime }=I_{t^{l-1}}\otimes M\otimes I_{t^{k-l-1}}$, $l=1,2,\dots ,k-1$. Because of (1), (3) and the inductive hypothesis, we have that

$$\begin{array}{ccc}\hfill {\otimes }^{k}M& =& M\otimes \left({\otimes }^{k-1}M\right)=(M·I_t)\otimes \left(I_{t^{k-1}}·\left({\otimes }^{k-1}M\right)\right)\hfill \\ & =& (M\otimes I_{t^{k-1}})·\left(I_t\otimes \left({\otimes }^{k-1}M\right)\right)\hfill \\ & =& B_1·(I_t^{k-1}\otimes (B_1^{\prime }·B_2^{\prime }\cdots B_{k-1}^{\prime }))\hfill \\ & =& B_1·(I_t\otimes B_1^{\prime })·(I_t\otimes B_2^{\prime })\cdots (I_t\otimes B_{k-1}^{\prime })\hfill \\ & =& B_1·(I_t\otimes M\otimes I_{t^{k-2}})·(I_t\otimes I_t\otimes M\otimes I_{t^{k-3}})\cdots (I_t\otimes I_{t^{k-2}}\otimes M)\hfill \\ & =& B_1·B_2·B_3\cdots B_k.\hfill \end{array}$$

So the theorem holds for all $k\in \mathbb{N}$. □

Another important result is that the order of the factors in (4) does not matter.

Theorem 3. 

The factors in (4) commute.

Proof. 

We apply the properties of the Kronecker product.

$$\begin{array}{ccc}\hfill B_i·B_j& =& (I_{t^{i-1}}\otimes M\otimes I_{t^{n-i}})·(I_{t^{j-1}}\otimes M\otimes I_{t^{k-j}})\hfill \\ & =& I_{t^{i-1}}\otimes ((M\otimes I_{t^{k-i}})·(I_{t^{j-i}}\otimes M\otimes I_{t^{k-j}}))\hfill \\ & =& I_{t^{i-1}}\otimes ((M\otimes I_{t^{j-i}})·(I_{t^{j-i}}\otimes M))\otimes I_{t^{k-j}}\hfill \\ & =& I_{t^{i-1}}\otimes ((M\otimes I_{t^{j-i}})·(I_t\otimes I_{t^{j-i-1}}\otimes M))\otimes I_{t^{k-j}}\hfill \\ & =& I_{t^{i-1}}\otimes (M·I_t)\otimes (I_{t^{j-i}}·(I_{t^{j-i-1}}\otimes M))\otimes I_{t^{k-j}}\hfill \\ & =& I_{t^{i-1}}\otimes M\otimes I_{t^{j-i-1}}\otimes M\otimes I_{t^{k-j}}\hfill \\ & =& I_{t^{i-1}}\otimes (I_t·M)\otimes ((I_{t^{j-i-1}}\otimes M)·I_{t^{j-i}})\otimes I_{t^{k-j}}\hfill \\ & =& I_{t^{i-1}}\otimes ((I_t\otimes I_{t^{j-i-1}}\otimes M)·(M\otimes I_{t^{j-i}}))\otimes I_{t^{k-j}}\hfill \\ & =& I_{t^{i-1}}\otimes ((I_{t^{j-i}}\otimes M)·(M\otimes I_{t^{j-i}}))\otimes I_{t^{k-j}}=B_j·B_i.\hfill \end{array}$$

□

If we take a square $t\times t$ matrix M without zero elements, then the number of nonzero elements in each row and column in the matrices $B_l$ is t.

$$I_u\otimes M\otimes I_s=\left(\begin{array}{cccc}M& & & \\ & M& & \\ & & \ddots & \\ & & & M\end{array}\right)\otimes I_s=\left(\begin{array}{cccc}M\otimes I_s& & & \\ & M\otimes I_s& & \\ & & \ddots & \\ & & & M\otimes I_s\end{array}\right),$$

where

$$M\otimes I_s=\left(\begin{array}{cccc}{m}_{11}{I}_s& m_{12}{I}_s& \cdots & m_{1t}{I}_s\\ m_{21}{I}_s& m_{22}{I}_s& \cdots & m_{2t}{I}_s\\ \cdots & & \ddots & \\ m_{t1}{I}_s& m_{t2}{I}_s& \cdots & m_{tt}{I}_s\end{array}\right)$$

If $m_{ij}\ne 0$, then each block $m_{ij}{I}_s$ has exactly one nonzero element in each row and column. Hence, $M\otimes I_s$ has the same number of nonzero elements by rows and columns as the matrix M itself. Obviously, this holds for $I_u\otimes M\otimes I_s$, too.

Let M be a square $t\times t$ matrix without zero elements and v be a vector of length $t^k$ for some integer k. To compute the product of the k-th Kronecker power ${\otimes }^{k}M$ with the vector v, one needs $t^k·t^k$ multiplications and $t^k(t^k-1)$ additions. Applying Theorem 2, ${\otimes }^{k}M$ is factorized into k square matrices of size $t^k$, such that each one has the same number t of nonzero elements by rows and columns as M. We have that

$${\otimes }^{k}M·v=B_1\left(B_2(B_3\dots \left(B_{k-1}\left(B_{k}v\right)\right)\dots )\right)$$

So, calculating ${\otimes }^{k}M·v$ consists of k multiplications $B_l·v^{\prime }$, where $v^{\prime }$ is the vector, obtained in the previous step. Computing $B_l·v^{\prime }$ consists of $t^k·t$ multiplications and $t^k(t-1)$ additions. In the general case, the whole calculation consists of at most $k(t·t^k+(t-1)t^k)=k{t}^k(2t-1)$ operations. Hence, ${\otimes }^{k}M·v$ is computed much faster. This is the core of the presented fast discrete transforms.

4. Fast Walsh Transform

Let n be positive integer and ${\mathbb{F}}_2=\{0,1\}$ be the Galois field of two elements. There is one-to-one correspondence between the non negative integers $u<2^n$ and the binary vectors of length n, defined by $u\mapsto \overline{u}=(u_0,u_1,\dots ,u_{n-1})\in {\mathbb{F}}_2$, where $u=u_0{2}^{n-1}+u_1{2}^{n-2}+\cdots +u_{n-1}$ is the binary representation of u.

Let $f:{\mathbb{F}}_2^n\to {\mathbb{F}}_2$ be a Boolean function of n variables. Truth Table $T{T}_f$ of the function f is a $2^n$-dimensional column vector whose $(i+1)$-th coordinate is $f\left(\overline{i}\right),i=0,1,\dots ,2^n-1$.

Walsh transform of the function f is defined as follows:

$$\widehat{f}\left(\omega \right)=\sum _{x\in {\mathbb{F}}_2^k}f\left(x\right){(-1)}^{\langle x,\omega \rangle },\omega \in {\mathbb{F}}_2^k,$$

(5)

where $\langle x,y\rangle =x_1{y}_1+x_2{y}_2+\cdots +x_k{y}_k$ and it means the Euclidean inner product of the vectors x and y. The column vector of the function $\widehat{f}$ is denoted also by $T{T}_{\widehat{f}}$.

We use a special type of Hadamard matrices, defined recurrently as follows:

$$H_1=\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill -1\end{array}\right),H_k=\left(\begin{array}{cc}\hfill H_{k-1}& \hfill H_{k-1}\\ \hfill H_{k-1}& \hfill -H_{k-1}\end{array}\right),k>1.$$

(6)

Theorem 4. 

If f is a Boolean function of n variables then $T{T}_{\widehat{f}}=H_n·T{T}_f$.

Proof. 

We prove the theorem by induction. For $k=1$, let $f:{\mathbb{F}}_2\to {\mathbb{F}}_2$ be a Boolean function of one variable. Then $T{T}_f=\left(\begin{array}{c}\hfill f\left(0\right)\\ \hfill f\left(1\right)\end{array}\right)$ and

$$W_f\left(0\right)=f\left(0\right).{(-1)}^{0.0}+f\left(1\right).{(-1)}^{1.0}=f\left(0\right)+f\left(1\right),$$

$$W_f\left(1\right)=f\left(0\right).{(-1)}^{0.1}+f\left(1\right).{(-1)}^{1.1}=f\left(0\right)-f\left(1\right).$$

Obviously, $W_f=H_1·T{T}_f$.

Let the theorem holds for $n=k$, $k\ge 1$, and $f:{\mathbb{F}}_2^{k+1}\to {\mathbb{F}}_2$ be a Boolean function of $k+1$ variables with truth table $T{T}_f$. We use the Boolean functions of k variables $f_0(x_1,\dots ,x_k)=f(0,x_1,\dots ,x_k)$ and $f_1{x}_1,\dots ,x_k)=f(1,x_1,\dots ,x_k)$. According to the lexicographic ordering, the set of all vectors in ${\mathbb{F}}_2^{k+1}$ can be split into two subsets, namely $V_0=\{(0,x_1,\dots ,x_k),\forall (x_1,\dots ,x_k)\in {\mathbb{F}}_2^k\}$ and $V_1=\{(1,x_1,\dots ,x_k),\forall (x_1,\dots ,x_k)\in {\mathbb{F}}_2^k\}$. Then $T{T}_f=(T{T}_{f_0},T{T}_{f_1})$. According to the induction hypothesis $W_{f_0}=H_k·T{T}_{f_0}$ and $W_{f_1}=H_k·T{T}_{f_1}$. Then

$$\begin{array}{ccc}\hfill W_f\left(\omega \right)& =& \sum _{x\in {\mathbb{F}}_2^{k+1}}f\left(x\right){(-1)}^{\langle x,\omega \rangle }\hfill \\ & =& \sum _{(x_1,\dots ,x_k)\in {\mathbb{F}}_2^k}f(0,x_1,\dots ,x_k){(-1)}^{\langle (0,x_1,\dots ,x_k),({\omega }_0,{\omega }_1,\dots ,{\omega }_k)\rangle }\hfill \\ & & +\sum _{(x_1,\dots ,x_k)\in {\mathbb{F}}_2^k}f(1,x_1,\dots ,x_k){(-1)}^{\langle (1,x_1,\dots ,x_k),({\omega }_0,{\omega }_1,\dots ,{\omega }_k)\rangle }\hfill \\ & =& \sum _{(x_1,\dots ,x_k)\in {\mathbb{F}}_2^k}{f}_0(x_1,\dots ,x_k){(-1)}^{\langle (x_1,\dots ,x_k),({\omega }_1,\dots ,{\omega }_k)\rangle }\hfill \\ & & +\sum _{(x_1,\dots ,x_k)\in {\mathbb{F}}_2^k}{f}_1(x_1,\dots ,x_k){(-1)}^{{\omega }_0+\langle (x_1,\dots ,x_k),({\omega }_1,\dots ,{\omega }_k)\rangle }\hfill \\ & =& \sum _{(x_1,\dots ,x_k)\in {\mathbb{F}}_2^k}{f}_0(x_1,\dots ,x_k){(-1)}^{\langle (x_1,\dots ,x_k),({\omega }_1,\dots ,{\omega }_k)\rangle }\hfill \\ & & +{(-1)}^{{\omega }_0}\sum _{(x_1,\dots ,x_k)\in {\mathbb{F}}_2^k}{f}_1(x_1,\dots ,x_k){(-1)}^{\langle (x_1,\dots ,x_k),({\omega }_1,\dots ,{\omega }_k)\rangle }.\hfill \end{array}$$

It follows that

$$W_f\left(\omega \right)=W_{f_0}({\omega }_1,\dots ,{\omega }_k)+W_{f_1}({\omega }_1,\dots ,{\omega }_k)\mathrm{for}{\omega }_0=0,$$

$$W_f\left(\omega \right)=W_{f_0}({\omega }_1,\dots ,{\omega }_k)-W_{f_1}({\omega }_1,\dots ,{\omega }_k)\mathrm{for}{\omega }_0=1.$$

These equations and the induction hypothesis show that

$$\begin{array}{ccc}\hfill W_f& =& \left(\begin{array}{c}{W}_{f_0}+W_{f_1}\hfill \\ W_{f_0}-W_{f_1}\hfill \end{array}\right)=\left(\begin{array}{c}{H}_k·T{T}_{f_0}+H_k·T{T}_{f_1}\hfill \\ H_k·T{T}_{f_0}-H_k·T{T}_{f_1}\hfill \end{array}\right)\hfill \\ & =& \left(\begin{array}{cc}\hfill H_k& \hfill H_k\\ \hfill H_k& \hfill -H_k\end{array}\right)·\left(\begin{array}{c}T{T}_{f_0}\hfill \\ T{T}_{f_1}\hfill \end{array}\right).\hfill \end{array}$$

Hence, the induction step is proven. □

Thus, the computation of the Walsh transform is reduced to a matrix by vector multiplication. The elements of the matrix $H_n$ are only 1’s and −1’s. Hence, the multiplication of a row of the matrix by the considered vector means only addition and subtraction.

There is a fast algorithm to calculate $H_n·v$. First, the vector v is partitioned into vectors of two coordinates. For each small vector

$$H_1·\left(\begin{array}{c}{v}_1\hfill \\ v_2\hfill \end{array}\right)=\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill -1\end{array}\right)·\left(\begin{array}{c}{v}_1\hfill \\ v_2\hfill \end{array}\right)=\left(\begin{array}{c}{v}_1+v_2\hfill \\ v_1-v_2\hfill \end{array}\right).$$

Using these results, $H_2$ is multiplied by 4-length parts of v. The k-th step consists of multiplying the matrix $H_k$ by a part $v^{\prime }$ of v, where $v^{\prime }$ has length $2^k$. Let $v^{\left(1\right)}$ and $v^{(}2)$ be $2^{k-1}$ parts of $v^{\prime }$ from the previous step of the algorithm and also $H_{k-1}·v^{\left(1\right)}$ and $H_{k-1}·v^{\left(2\right)}$ are computed. Then

$$H_k·v^{\prime }=\left(\begin{array}{cc}\hfill H_{k-1}& \hfill H_{k-1}\\ \hfill H_{k-1}& \hfill -H_{k-1}\end{array}\right)·\left(\begin{array}{c}{v}^{\left(1\right)}\hfill \\ v^{\left(2\right)}\hfill \end{array}\right)=\left(\begin{array}{c}{H}_{k-1}·v^{\left(1\right)}+H_{k-1}·v^{\left(2\right)}\hfill \\ H_{k-1}·v^{\left(1\right)}-H_{k-1}·v^{\left(2\right)}\hfill \end{array}\right).$$

Therefore, we may consequently calculate $H_n·v$.

The presented algorithm consists of n steps, each one performing only additions and subtractions. Therefore, $n·2^n$ arithmetic operations are made, instead of $2^n·2^n$ operations of the ordinary matrix by vector multiplication. An implementation of the Walsh–Hadamard fast transform in CUDA, as well as analysis of the complexity of the algorithm and comparison to other existing algorithms, are given in [15].

Example 1. 

Let $M=H_1$ and ${\otimes }^k{H}_1=H_k$. For $k=3$, it holds that $H_3=(H_1\otimes I_4)·(I_2\otimes H_1\otimes I_2)·(I_4\otimes H_1)$.

$$H_3=\left(\begin{array}{cc}\hfill I_4& \hfill I_4\\ \hfill I_4& \hfill -I_4\end{array}\right)·\left(\begin{array}{cc}\hfill I_2& \hfill I_2\\ \hfill I_2& \hfill -I_2\\ & & \hfill I_2& \hfill I_2\\ & & \hfill I_2& \hfill -I_2\end{array}\right)·\left(\begin{array}{c}\hfill H_1\\ & \hfill H_1\\ & & \hfill H_1\\ & & & \hfill H_1\end{array}\right)$$

Each row in the above multipliers consists of only two nonzero elements, namely 1 and −1. So, the row by vector multiplication costs one arithmetic operation (addition or subtraction). Let $T{T}_f$ be the Truth Table of a function $f:{\mathbb{F}}_2^3\to {\mathbb{F}}_2$. The process of computing $H_3·T{T}_f$ is given below in Figure 1. In the given diagram, the continuous line means addition, and the dotted line means subtraction.

In some cases, especially by parallelization of the algorithm and using shared memory, it is more convenient to rearrange the matrices. Because of Theorem 3, there is another way to compute $H_3·T{T}_f$.

$$H_3=(I_4\otimes H_1)·(H_1\otimes I_4)·(I_2\otimes H_1\otimes I_2).$$

This leads to another fast algorithm for computing $V_3.b$ (b is a vector of suitable length), whose diagram is given in Figure 2.

As a factorization of the Kronecker power is made, the Vilenkin–Chrestenson and the trace transforms also have similar fast algorithms.

5. Discrete Transform of Vilenkin–Chrestenson

Let $\xi$ be a primitive complex q-th root of unity. The matrices of Vilenkin–Chrestenson of size k are recurrently defined as follows:

$$V_1=\left(\begin{array}{ccccc}1& 1\hfill & 1\hfill & \dots & 1\hfill \\ 1& \xi \hfill & {\xi }^2\hfill & \dots & {\xi }^{q-1}\hfill \\ 1& {\xi }^2\hfill & {\xi }^4\hfill & \dots & {\xi }^{2(q-1)}\hfill \\ & ⋮\hfill & ⋮\hfill & & ⋮\hfill \\ 1& {\xi }^{q-1}\hfill & {\xi }^{2(q-1)}\hfill & \dots & {\xi }^{{(q-1)}^2}\hfill \end{array}\right),V_{k+1}=V_1\otimes V_k,k\in \mathbb{Z},k\ge 1,$$

(7)

where ⊗ means the Kronecker product. The elements of the matrix $V_k$ are $v_{\omega }\left(x\right)={\xi }^{\langle \omega ,x\rangle }$, where $\omega =({\omega }_1,{\omega }_2,\dots ,{\omega }_k)\in {\mathbb{Z}}_q^k$ are the row labels and $x=(x_1,x_2,\dots ,x_k)\in {\mathbb{Z}}_q^k$ are the column labels, both in lexicographical order, ${\mathbb{Z}}_q=\{0,1,2,\dots ,q-1\}$ and $\langle \omega ,x\rangle ={\sum }_{i=1}^k{\omega }_i.x_i\in {\mathbb{Z}}_q$.

Some useful properties directly following the definition are given below:

$$v_{\omega }\left(x\right)=v_x\left(\omega \right),v_{\omega }\left(x\right)v_{\omega }\left(x^{\prime }\right)=v_{\omega }(x+x^{\prime }),v_{\omega }\left(0\right)=1.$$

(8)

The first property shows that the matrices $V_k$ are symmetric.

Definition 4. 

Let $f:{\mathbb{Z}}_q^k\to \mathbb{C}$ be a function. Transform of Vilenkin–Chrestenson of f is the function ${\widehat{f}}_{VC}:{\mathbb{Z}}_q^k\to \mathbb{C}$, defined as follows:

$${\widehat{f}}_{VC}\left(\omega \right)=\sum _{x\in {\mathbb{Z}}_q^k}f\left(x\right)v_{\omega }\left(x\right),\omega \in {\mathbb{Z}}_q^k.$$

(9)

Let $T{T}_f$ be the vector whose coordinates are all values of the function f when the elements of ${\mathbb{Z}}_q^k$ are lexicographically ordered. It is called a truth table, and it is similar to the truth table of a Boolean function but with complex numbers. The value vectors of f and ${\widehat{f}}_{VC}$ are related as follows:

$$T{T}_{{\widehat{f}}_{VC}}=V_k·T{T}_f.$$

Hence, the Vilenkin–Chrestenson transform can be reduced to a matrix by vector multiplication (see, for example, [16]).

One very useful application of the presented transform is to calculate the weight distribution of a linear code over a prime field. Let q be a prime and G be a generator matrix of the linear ${[n,k]}_q$ code C. We take a code C of full length, so $f_G\left(0\right)=0$.

The relation between the Vilenkin–Chrestenson transform ${\widehat{f}}_{VC}$ and the weight of the codeword $\omega G\in C$ is given by the following theorem.

Theorem 5. 

Let G be a generator matrix of the linear ${[n,k]}_q$ code C with full length. Then, for the weight of the codeword $\omega G\in C$, it holds that

$$wt\left(\omega G\right)={\displaystyle \frac{(q-1)n-{\widehat{f}}_{VC}\left(\omega \right)}{q}},\omega \in {\mathbb{F}}_q^k,$$

(10)

where ${\widehat{f}}_{VC}$ is the Vilenkin–Chrestenson transform of the characteristic function $f_G$ of the code C.

Proof. 

It is known that all codewords of C are linear combinations of the rows of its generator matrix, so any codeword is generated by multiplication of G by a vector $\omega \in {\mathbb{F}}_q^k$. Let us denote the columns of the matrix G by $g_1,\dots ,g_n$. It follows that $\omega G=(\langle \omega ,g_1\rangle ,\dots ,\langle \omega ,g_n\rangle )$, where $\langle \omega ,g_i\rangle$ is the inner product of $\omega$ and the vector $g_i$. Since $wt\left(\omega G\right)$ is the number of the nonzero coordinates of the vector, so $n-wt\left(\omega G\right)$ is the number of the zeros in $\omega G$. On the other hand, the summands in (9) are $\ne 0$ only if there exists a proportional to x column in G. Furthermore, if $f\left(x\right)\ne 0$ for some $x\ne 0$, then $f\left(x\right)=f\left(\alpha x\right)$ for each $\alpha \in {\mathbb{F}}_q\setminus \left\{0\right\}$. Hence, for each column x of the generator matrix G it holds that

$$\sum _{\alpha \in {\mathbb{F}}_q\setminus \left\{0\right\}}{v}_{\omega }\left(\alpha x\right)=\sum _{\alpha \in {\mathbb{F}}_q\setminus \left\{0\right\}}{\xi }^{\langle \omega ,\alpha x\rangle }=\left\{\begin{array}{cc}\hfill q-1,& \hfill \mathrm{if}\langle \omega ,x\rangle =0,\\ \hfill -1,& \hfill \mathrm{if}\langle \omega ,x\rangle \ne 0.\end{array}\right.$$

(11)

As the code has full length, then $f\left(0\right)=0$. The summands in (9) can be rearranged such that exactly one sum of type (11) corresponds to each column of G. Then

$${\widehat{f}}_{VC}\left(\omega \right)=(q-1)(n-wt\left(\omega G\right))-wt\left(\omega G\right).$$

This proves that in this case ${\widehat{f}}_{VC}$ is an integer-valued function. Calculating $wt\left(\omega G\right)$, we obtain (10). □

Example 2. 

Let C be ${[7,3]}_3$ code and its generator matrix is

$$G=\left(\begin{array}{ccccccc}1& 1& 1& 1& 1& 0& 0\\ 0& 1& 1& 2& 0& 1& 0\\ 1& 0& 1& 0& 0& 0& 1\end{array}\right)$$

The characteristic function $f_G\left(x\right):{\mathbb{F}}_3^3\to \mathbb{Z}$ of C with respect to G has the following Truth Table:

$$T{T}_{f_G}=(0,1,1,1,0,0,1,0,0,1,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,0,1)$$

We have that $T{T}_{{\widehat{f}}_{VC}}=V_3.T{T}_{f_G}$, so

$$T{T}_{{\widehat{f}}_{VC}}=(14,5,5,2,-4,-1,2,-1,-4,-1,-4,2,-1,-1,-1,2,-4,-1,-1,2,-4,2,-1,-4,-1,-1,-1)$$

Applying Theorem 5, we obtain that the nonzero weights in the code are 3, 4, 5, 6, and the weight enumerator is $W_C\left(y\right)=1+2y^3+6y^4+12y^5+6y^6$. The structure of the matrix $V_3$ is given below.

$$\begin{array}{ccc}\hfill V_3& =& (I_{3^{1-1}}\otimes V_1\otimes I_{3^{3-1}}).(I_{3^{2-1}}\otimes V_1\otimes I_{3^{3-2}}).(I_{3^{3-1}}\otimes V_1\otimes I_{3^{3-3}})\hfill \\ & =& (V_1\otimes I_9).(I_3\otimes V_1\otimes I_3).(I_9\otimes V_1),\hfill \end{array}$$

where $V_1=\left(\begin{array}{ccc}1& 1& 1\\ 1& \xi & {\xi }^2\\ 1& {\xi }^2& \xi \end{array}\right).$

$$V_3=\left(\begin{array}{ccc}\hfill I_9& \hfill I_9& \hfill I_9\\ \hfill I_9& \hfill \xi I_9& \hfill {\xi }^2{I}_9\\ \hfill I_9& \hfill {\xi }^2{I}_9& \hfill \xi I_9\end{array}\right)·\left(\begin{array}{ccc}\hfill I_3& \hfill I_3& \hfill I_3\\ \hfill I_3& \hfill \xi I_3& \hfill {\xi }^2{I}_3\\ \hfill I_3& \hfill {\xi }^2{I}_3& \hfill \xi I_3\\ & & & \hfill I_3& \hfill I_3& \hfill I_3\\ & & & \hfill I_3& \hfill \xi I_3& \hfill {\xi }^2{I}_3\\ & & & \hfill I_3& \hfill {\xi }^2{I}_3& \hfill \xi I_3\\ & & & & & & \hfill I_3& \hfill I_3& \hfill I_3\\ & & & & & & \hfill I_3& \hfill \xi I_3& \hfill {\xi }^2{I}_3\\ & & & & & & \hfill I_3& \hfill {\xi }^2{I}_3& \hfill \xi I_3\end{array}\right)·\left(\begin{array}{c}\hfill V_1\\ & \hfill V_1\\ & & \hfill \ddots \\ & & & \hfill V_1\end{array}\right)$$

Each of the sparse matrices above has exactly three nonzero elements in its rows and columns.

In the general case, a sparse matrix for the Vilenkin–Chrestenson transform has exactly q nonzero elements since $V_1$ is a $q\times q$ matrix. That is why the number of the necessary operations is reduced to $2k{q}^{k+1}$, approximately, while the same result would be obtained with $2q^{2k}$ operations without the $V_k$ factorization. The same conclusion could be drawn for the trace transform as well.

6. Trace Transform

Let ${\mathbb{F}}_q$ be a composite finite field with q elements, where $q=p^m$ for the prime p and the integer $s>1$. For the trace transform, the absolute trace of the inner product is used instead of the inner product itself, as in the Vilenkin–Chrestenson transform [27]. Let $\zeta$ be a primitive complex p-th root of unity, and

$${\tau }_{\omega }\left(x\right)={\zeta }^{Tr(\langle \omega ,x\rangle )}$$

(12)

for any $\omega ,x\in {\mathbb{F}}_q^k$. We define the trace transform similarly to the Vilenkin–Chrestenson transform.

Definition 5. 

Let ${\mathbb{F}}_q$ be a finite field with q elements, $q=p^m$ for the prime number p, and ζ be a primitive complex p-th root of unity. Trace transform of the function $f:{\mathbb{F}}_q^k\to \mathbb{C}$ is the function ${\widehat{f}}_T:{\mathbb{F}}_q^k\to \mathbb{C}$, defined as follows:

$${\widehat{f}}_T\left(\omega \right)=\sum _{x\in {\mathbb{F}}_q^k}f\left(x\right){\tau }_{\omega }\left(x\right)=\sum _{x\in {\mathbb{F}}_q^k}f\left(x\right){\zeta }^{Tr(\langle \omega ,x\rangle )},\omega \in {\mathbb{F}}_q^k.$$

(13)

The transform matrix here is the $q^k\times q^k$ matrix $T_k=\left({\tau }_{\omega }\left(x\right)\right)$, where the vectors (in our case denoted by $\omega$ and x) in ${\mathbb{F}}_q^k$ are lexicographically ordered. Then the Truth Tables of f and ${\widehat{f}}_T$ are connected by the equality

$$T{T}_{{\widehat{f}}_T}=T_k·T{T}_f.$$

Because of the symmetry and linearity of the inner product, the following properties hold:

$${\tau }_{\omega }\left(x\right)={\tau }_x\left(\omega \right),{\tau }_{\omega }\left(x\right){\tau }_{\omega }\left(x^{\prime }\right)={\tau }_{\omega }(x+x^{\prime }).$$

(14)

Lemma 1. 

For $x\in {\mathbb{F}}_q^k$ it holds that

$$\sum _{\omega \in {\mathbb{F}}_q^k}{\tau }_{\omega }\left(x\right)=\left\{\begin{array}{cc}\hfill q^k,& \hfill forx=0,\\ \hfill 0,& \hfill forx\ne 0.\end{array}\right.$$

Proof. 

The lemma is a modification of [28] (Chapter 5, Lemma 9), and its proof is by induction on k. In the base step, $k=1$ it holds

$$\sum _{\omega \in {\mathbb{F}}_q}{\tau }_{\omega }\left(x\right)=\sum _{\omega \in {\mathbb{F}}_q}{\zeta }^{Tr\left(x\omega \right)}=\left\{\begin{array}{cc}q,\hfill & \mathrm{for}x=0,\hfill \\ 0,\hfill & \mathrm{for}x\ne 0.\hfill \end{array}\right.$$

For $x\ne 0$, when $\omega$ takes all possible values of ${\mathbb{F}}_q$, then $x\omega$ takes all the values of ${\mathbb{F}}_q$. Moreover, for any element $\alpha \in {\mathbb{F}}_q$, there are exactly $p^{m-1}$ elements ${\alpha }^{\prime }\in {\mathbb{F}}_q$ with the same trace value $Tr\left({\alpha }^{\prime }\right)=Tr\left(\alpha \right)$. Thus

$$\sum _{\omega \in {\mathbb{F}}_q}{\zeta }^{Tr\left(x\omega \right)}=\sum _{\omega \in {\mathbb{F}}_q}{\zeta }^{Tr\left(\omega \right)}=p^{m-1}\sum _{\omega \in {\mathbb{F}}_p}{\zeta }^{\omega }=p^{m-1}{\displaystyle \frac{1-{\zeta }^p}{1-\zeta }}=0.$$

Let the equality hold for some integer k. Consider the vectors in ${\mathbb{F}}_q^{k+1}$ in the following form: $x=(x_0,x^{\prime })$, $x_0\in {\mathbb{F}}_q$, $x^{\prime }\in {\mathbb{F}}_q^k$. Because of the trace linearity

$$\begin{array}{ccc}\hfill \sum _{\omega \in {\mathbb{F}}_q^{k+1}}{\tau }_{\omega }\left(x\right)& =& \sum _{\omega \in {\mathbb{F}}_q^{k+1}}{\zeta }^{Tr(\langle \omega ,x\rangle )}=\sum _{j\in {\mathbb{F}}_q}\sum _{{\omega }^{\prime }\in {\mathbb{F}}_q^k}{\zeta }^{Tr(j{x}_0+\langle {\omega }^{\prime },x^{\prime }\rangle )}\hfill \\ & =& \sum _{j\in {\mathbb{F}}_q}\sum _{{\omega }^{\prime }\in {\mathbb{F}}_q^k}{\zeta }^{Tr\left(j{x}_0\right)+Tr\left(\langle {\omega }^{\prime },x^{\prime }\rangle \right)}=\sum _{j\in {\mathbb{F}}_q}\sum _{{\omega }^{\prime }\in {\mathbb{F}}_q^k}{\zeta }^{Tr\left(j{x}_0\right)}{\zeta }^{Tr\left(\langle {\omega }^{\prime },x^{\prime }\rangle \right)}\hfill \\ & =& \left(\sum _{j\in {\mathbb{F}}_q}{\zeta }^{Tr\left(j{x}_0\right)}\right)\left(\sum _{{\omega }^{\prime }\in {\mathbb{F}}_q^k}{\zeta }^{Tr\left(\langle {\omega }^{\prime },x^{\prime }\rangle \right)}\right)\hfill \\ & =& \left(\sum _{j\in {\mathbb{F}}_q}{\tau }_j\left(x_0\right)\right)\left(\sum _{{\omega }^{\prime }\in {\mathbb{F}}_q^k}{\tau }_{{\omega }^{\prime }}\left(x^{\prime }\right)\right)\hfill \end{array}$$

(15)

According to the induction hypothesis and its base step, the sum is $\ne 0$ exactly when $x_0=0$ and $x^{\prime }=0$. In this case, the sum is $q.q^k=q^{k+1}$.

Hence, the equality holds for each $k\in \mathbb{N}$. □

To reduce (15), it is also taken that

$${\zeta }^{Tr(\langle \omega ,x\rangle )}={\zeta }^{Tr\left(j{x}_0\right)}{\zeta }^{Tr\left(\langle {\omega }^{\prime },x^{\prime }\rangle \right)},$$

where $\omega =(j,{\omega }^{\prime }),x=(x_0,x^{\prime })\in {\mathbb{F}}_q^{k+1}$, $j,x_0\in {\mathbb{F}}_q$, ${\omega }^{\prime },x^{\prime }\in {\mathbb{F}}_q^k$. This means that the matrices $T_k$ are generated as a Kronecker power, i.e., $T_{k+1}=T_1\otimes T_k$ and $T_k={\otimes }^k{T}_1$ for $k\in \mathbb{N}$.

The trace transform also has applications in coding theory, but it is used for linear codes over composite finite fields. In this case, a theorem similar to Theorem 5 is proved.

Theorem 6. 

Let G be a generator matrix of the linear ${[n,k]}_q$ code C with full length. Then, for the weights of all codewords of C, it holds that

$$wt\left(\omega G\right)={\displaystyle \frac{(q-1)n-{\widehat{f}}_T\left(\omega \right)}{q}},\omega \in {\mathbb{F}}_q^k,$$

(16)

where ${\widehat{f}}_T$ is the trace transform of the characteristic function $f_G$ of the code C.

Proof. 

The proof is similar to the proof of Theorem 5. Each coordinate in $\omega G$ is equal to the inner product of $\omega$ and the corresponding column of G. Since $wt\left(\omega G\right)$ is the number of the nonzero coordinates of $\omega G$, so $n-wt\left(\omega G\right)$ is the number of zeros. On the other hand, the summand $x{\zeta }^{Tr(\langle \omega ,x\rangle )}$ in (13) is not equal to 0 if and only if there exists a proportional vector of x as a column in G. If $f_G\left(x\right)\ne 0$, for some $x\ne 0$, then $f_G\left(x\right)=f_G\left(\alpha x\right)$ for all $\alpha \in {\mathbb{F}}_q\setminus \left\{0\right\}$. For each column x of the matrix G it holds that

$$\sum _{\alpha \in {\mathbb{F}}_q\setminus \left\{0\right\}}{\tau }_{\omega }\left(\alpha x\right)=\sum _{\alpha \in {\mathbb{F}}_q\setminus \left\{0\right\}}{\zeta }^{Tr(\langle \omega ,\alpha x\rangle )}=\left\{\begin{array}{cc}\hfill q-1,& \hfill \mathrm{if}\langle \omega ,x\rangle =0,\\ \hfill -1,& \hfill \mathrm{if}\langle \omega ,x\rangle \ne 0.\end{array}\right.$$

(17)

Let $\langle \omega ,x\rangle \ne 0$. Then $\left\{\alpha \langle \omega ,x\rangle \right|\alpha \in {\mathbb{F}}_q,\alpha \ne 0\}={\mathbb{F}}_q\setminus \left\{0\right\}$. The absolute trace $Tr$ is a linear map onto ${\mathbb{F}}_p$ with a kernel of $p^{m-1}$ elements. Hence, the sum (17) has exactly $p^{m-1}-1$ additives ${\zeta }^0=1$ and exactly $p^{m-1}$ additives ${\zeta }^{\lambda }$ for each $\lambda \in {\mathbb{F}}_p$, $\lambda \ne 0$. Further

$$\sum _{\alpha \in {\mathbb{F}}_q\setminus \left\{0\right\}}{\zeta }^{Tr(\langle \omega ,\alpha x\rangle )}=p^{m-1}-1+p^{m-1}\sum _{\lambda \in {\mathbb{F}}_p\setminus \left\{0\right\}}{\zeta }^{\lambda }=-1+p^{m-1}\sum _{\lambda \in {\mathbb{Z}}_p}{\zeta }^{\lambda }=-1.$$

Because the code has full length, then $f_G\left(0\right)=0$. The summands in (13) might be rearranged in such a way that any of the columns of G corresponds exactly to one sum of the type (17). Then

$${\widehat{f}}_T\left(\omega \right)=(q-1)(n-wt\left(\omega G\right))-wt\left(\omega G\right),$$

which leads to (16). □

It was proved in [13] that if the characteristic of the field is 2 and the used basis of ${\mathbb{F}}_q$ is self-dual, the matrix $T_1$ is a $q\times q$ Sylvester-Hadamard matrix (this matrix is denoted by $\Lambda$ in [13] (Proposition 2.1)). We give an example with a quaternary code with two characteristic vectors—one of them with respect to a self-dual basis and another one with respect to the ordinary polynomial basis $1,x$. Recall that the elements ${\beta }_1,\dots ,{\beta }_m\in {\mathbb{F}}_q$, where $q=p^m$ for a prime p, form a self-dual basis of the field if $Tr\left({\beta }_i{\beta }_j\right)={\delta }_{ij}$ for the Kronecker $\delta$.

Example 3. 

Let $q=4$ and ${\mathbb{F}}_4=\{0,1,x,x+1=x^2\}$. We consider the $[4,2]$ quaternary code with a generator matrix

$$G=\left(\begin{array}{cccc}1& 0& 1& x^2\\ 0& 1& x^2& x\end{array}\right).$$

If we take the ordering $0<1<x<x+1$, then the lexicographic ordering of the quaternary vectors of length 2 is

$$(0,0)<(0,1)<(0,x)<(0,x+1)<(1,0)<\cdots <(x+1,x)<(x+1,x+1),$$

and the characteristic vector of the code is

$$f_G^{\prime }\left(C\right)=(0,1,1,1,1,0,0,2,1,2,0,0,1,0,2,0).$$

In this case, the trace transform matrix is

$$T_2={\otimes }^2{T}_1=\left(\begin{array}{cccccccccccccccc}\hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1\\ \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1\\ \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1\\ \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1\\ \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1\\ \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1\\ \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1\\ \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill 1& \hfill -1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1\\ \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1\\ \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1\\ \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1\end{array}\right)$$

Then $T_2.f_G^{\prime }\left(C\right)=(12,0,0,0,0,-4,4,-4,0,-4,-4,4,0,4,-4,-4)$ and after applying (16), we obtain that the weight distribution of the given code is $W_c\left(z\right)=1z^0+3z^2+6z^3+6z^4$.

The quaternary field has a self-dual basis, namely ${\beta }_1=x$, ${\beta }_2=x+1$. Then we have the following ordering of the elements $0<{\beta }_2<{\beta }_1<1$, since ${\beta }_2=(0,1)$, ${\beta }_1=(1,0)$, and $1={\beta }_1+{\beta }_2=(1,1)$. In this case, the lexicographic ordering of the quaternary vectors of length 2 is

$$(0,0)<(0,{\beta }_2)<(0,{\beta }_1)<(0,1)<({\beta }_2,0)<\cdots <(1,{\beta }_1)<(1,1).$$

The new characteristic vector is

$$f_G^{″}\left(C\right)=(0,1,1,1,1,0,2,0,1,0,0,2,1,2,0,0).$$

Now $T_1={\otimes }^2{H}_1$ and so $T_2$ has the following structure:

$$T_2={\otimes }^2{T}_1=\left(\begin{array}{cccccccccccccccc}\hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1\\ \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1\\ \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1\\ \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1\\ \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1\\ \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1\\ \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1\\ \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1\\ \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill 1& \hfill -1\\ \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill 1& \hfill 1& \hfill -1& \hfill -1\\ \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill -1& \hfill 1& \hfill 1& \hfill -1& \hfill 1& \hfill -1& \hfill -1& \hfill 1\end{array}\right)$$

After the corresponding calculations, the same weight distribution of the code is obtained, but the algorithm is much faster, as we can use the fast Walsh transform, presented in Section 4.

In the general case, if the trace transform could not be reduced to the Walsh–Hadamard transform, the matrix $T_1$ is of size $q\times q$, i.e., $p^m\times p^m$. Then the matrix $T_k$ is a $p^{mk}\times p^{mk}$ matrix, so the computation of $T{T}_{{\widehat{f}}_T}$ requires $p^{2mk}$ multiplications and the same number of additions, $2p^{2mk}$ operations over all. Let $T_k$ be factorized into k sparse $p^{mk}\times p^{mk}$ matrices. Each of them has at most $p^m\times p^m$ nonzero elements, so its multiplications by a vector consist of $2p^{mk}{p}^m$ multiplications and additions. The total amount of operations to obtain the same result is at most $2k{p}^{m(k+1)}$.

We finish this section with a proposition showing that the trace transform can be reduced to a Vilenkin–Chrestenson transform in some cases. Let $q=p^m$, where p is an odd prime and $m>1$ is an odd integer. According to Theorem 1, there exists a self-dual basis ${\beta }_1,\dots ,{\beta }_m$ of ${\mathbb{F}}_q$ over ${\mathbb{F}}_p$. Let ${\mathbb{F}}_q=\{{\alpha }_0=0,{\alpha }_1,\dots ,{\alpha }_{q-1}\}$, where the elements are ordered lexicographically with respect to the self-dual basis. Therefore,

$${\alpha }_s={\lambda }_1\left({\alpha }_s\right){\beta }_1+\cdots +{\lambda }_m\left({\alpha }_s\right){\beta }_m,s=0,1,\dots ,q-1,$$

(18)

and $\lambda \left({\alpha }_s\right)=({\lambda }_1\left({\alpha }_s\right),\dots ,{\lambda }_m\left({\alpha }_s\right))\in {\mathbb{F}}_p^m.$ Because of the lexicographic ordering, we have the following representation of the index s in the p-ary numeral system

$$s={\lambda }_1\left({\alpha }_s\right)p^{m-1}+\cdots +{\lambda }_{m-1}\left({\alpha }_s\right)p+{\lambda }_m\left({\alpha }_s\right).$$

Let $V_m\left(p\right)$ be the Vilenkin–Chrestenson matrix for the pth root of unity $\zeta$, considered in this section. Then, the following statement holds.

Proposition 1. 

For ${\mathbb{F}}_q=\{{\alpha }_0=0,{\alpha }_1,\dots ,{\alpha }_{q-1}\}$, the matrices $T_1$ and $V_m\left(p\right)$ coincides.

Proof. 

According to the linearity of the trace function, we have

$$\begin{array}{cc}\hfill Tr\left({\alpha }_j{\alpha }_{j^{\prime }}\right)& =Tr(\sum _{s=1}^m{\lambda }_s\left({\alpha }_j\right){\beta }_s\sum _{s^{\prime }=1}^m{\lambda }_{s^{\prime }}\left({\alpha }_{j^{\prime }}\right){\beta }_{s^{\prime }})\hfill \\ \hfill & =Tr(\sum _{s=1}^m\sum _{s^{\prime }=1}^m{\lambda }_s\left({\alpha }_j\right){\lambda }_{s^{\prime }}\left({\alpha }_{j^{\prime }}\right){\beta }_s{\beta }_{s^{\prime }})\hfill \\ \hfill & =\sum _{s=1}^m\sum _{s^{\prime }=1}^{m}Tr\left({\lambda }_s\left({\alpha }_j\right){\lambda }_{s^{\prime }}\left({\alpha }_{j^{\prime }}\right){\beta }_s{\beta }_{s^{\prime }}\right)\hfill \\ \hfill & =\sum _{s=1}^m\sum _{s^{\prime }=1}^m{\lambda }_s\left({\alpha }_j\right){\lambda }_{s^{\prime }}\left({\alpha }_{j^{\prime }}\right)Tr\left({\beta }_s{\beta }_{s^{\prime }}\right).\hfill \end{array}$$

Since the basis is self-dual, it holds that

$${\lambda }_s\left({\alpha }_j\right){\lambda }_{s^{\prime }}\left({\alpha }_{j^{\prime }}\right)Tr\left({\beta }_s{\beta }_{s^{\prime }}\right)=\left\{\begin{array}{cc}{\lambda }_s\left({\alpha }_j\right){\lambda }_s\left({\alpha }_{j^{\prime }}\right),\hfill & \mathrm{if}s=s^{\prime },\hfill \\ 0,\hfill & \mathrm{if}s\ne s^{\prime }.\hfill \end{array}\right.$$

Then

$$Tr\left({\alpha }_j{\alpha }_{j^{\prime }}\right)=\sum _{s=1}^m{\lambda }_s\left({\alpha }_j\right){\lambda }_s\left({\alpha }_{j^{\prime }}\right)=\langle \lambda \left({\alpha }_j\right),\lambda \left({\alpha }_{j^{\prime }}\right)\rangle .$$

Hence

$${\tau }_{\omega }\left(x\right)={\zeta }^{\langle \lambda \left({\alpha }_j\right),\lambda \left({\alpha }_{j^{\prime }}\right)\rangle }=v_{\lambda \left(\omega \right)}\lambda \left(x\right)$$

and so

$${\widehat{f}}_T\left(\omega \right)={\widehat{f}}_{VC}\left(\lambda \left(\omega \right)\right),$$

where the ${\widehat{f}}_{VC}$ is the Vilenkin–Chrestenson transform with the p-th root of unity $\zeta$. Transferring this result to the transform matrices, we obtain $T_1=V_m\left(p\right)$. □

7. Conclusions

Computing the weight distribution of a linear code is not an easy problem, especially when the considered finite field is composite. Most algorithms that solve this problem are based on searching in large amounts of generated data. Therefore, other different techniques, such as Fourier-type transforms, are also being investigated and applied.

In this paper, three fast discrete transforms are studied, namely the Walsh–Hadamard, the Vilenkin–Chrestenson, and the trace transform, mainly considering the problem of representing their matrices as a product of sparse matrices. Using these transforms, the weights of a linear code could be computed without generating the codewords themselves. Algorithms for implementing the given fast discrete transforms have not only better complexity but they could also be easily parallelized.