4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nikola Kovachki Jul 17 '15 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.