# Enumerator Polynomials for Linear Anytime Codes

Let $C = \{c \in \mathbb{F}^n_2 : Hc=0\}$ be a binary linear code where $H \in \mathbb{F}^{k \times n}_2$ is a block lower-triangular matrix of full rank called the parity-check matrix of $C$. Clearly $C$ has rate $\frac{k}{n}$. Define $A_i(C) = |\{c \in C : ||c||=i\}|$ for all $0 \leq i \leq n$ where $||\cdot||$ denotes the Hamming weight of $c$ i.e. the number of non-zero entries. In general, I am interested in obtaining non-trivial upper-bounds for $|C|$ and $A_i(C)$ however that might prove very difficult without more information about $H$ (or perhaps not, I am open to any suggestions). So consider the following special case. Let $n \in \mathbb{N}$ be even and construct $H \in \mathbb{F}^{\frac{n}{2} \times n}_2$ as follows $$H = \left( \begin{array}{ccccccccc} 1 & 1 & 0 & 0 & 0 & 0 & \cdots & \cdots & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & \cdots & \cdots & 0\\ 1 & 0 & 1 & 0 & 1 & 1 & \cdots & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 0 & 1 & 0 & 1 & 0 & \cdots & 1 & 1\end{array} \right)$$

Simulations have shown (although I have no idea how to prove these results) that $$|C|=2^{\frac{n}{2}}$$ $$A_0(C) = 1$$ $$A_1(C) = 0$$ $$A_2(C) = 1$$ $$A_3(C) = \left\{ \begin{array}{ll} \frac{n}{2} & n \geq 4 \\ 0 & otherwise \\ \end{array} \right.$$ $$A_4(C) = \left\{ \begin{array}{ll} \frac{n}{2}-1 & n \geq 6 \\ 0 & otherwise \\ \end{array} \right.$$ $$A_5(C) = \left\{ \begin{array}{ll} n-4 & n \geq 8 \\ 1 & n=6 \\ 0 & otherwise \end{array} \right.$$

and finally for all $n$ such that $\frac{n}{2}$ is odd, we have $A_{n-\left \lfloor{\frac{n}{4}}\right \rfloor}(C) = 1$ where $\left \lfloor{\cdot}\right \rfloor$ denotes the floor function. I have seen no other discernible patterns. I am looking for any suggestions or references on how to show exact answers or upper bounds (more likely) for any Hamming weights. Thanks.

## 1 Answer

I will use n for what you call $\frac{n}{2}$. Let's denote by $a(n,k)$ the number of vectors of length $2n$ and Hamming weight $k$ which are sent to the vector of all $0$'s after multiplying by $H$. Let $b(n,k)$ be the number of such vectors that are sent to the vector of all $1$'s. A simple induction argument gives the double recurrence $$a(n+1,k+2)=a(n,k+2)+b(n,k)$$ $$b(n+1,k+1)=a(n,k)+b(n,k)$$ Therefore using generating functions, we can let $A(x,y)=\sum_{n,k\geq 0}a(n,k)x^ny^k$ and $B(x,y)=\sum_{n,k\geq 0}b(n,k)x^ny^k$, with the convention $a(0,0)=b(0,0)=1$ and solve the system implied by the recurrences above.

If my calculations are correct, you should get $$A(x,y)=\frac{1-xy+xy^2}{1-x-xy+x^2y-x^2y^3}.$$ Notice that plugging in $y=1$ reduces to $\frac{1}{1-2x}$, which agrees with $|C|=2^n$.

• Thanks! I actually should have seen this earlier, but since $H$ is full rank and $C$ is the null space of $H$, it's immediate that $|C|=2^n$. Nevertheless, your approach is really nice because if you Taylor expand $A(x,y)$ around $x=0$ then you get $A(x,y) = 1+x(y^2+1)+x^2(2y^3+y^2+1)+...$ and that exactly determines the coefficients $a(n,k)$, so, if I can get a closed form of that expansion, I'll have an exact answer. Do you mind elaborating a bit on how you obtained your recurrence relations as it is not obvious to me. – Nikola Kovachki Jul 17 '15 at 19:53