Enumerator Polynomials for Linear Anytime Codes

Question

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.

Answer 1

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$.