12
$\begingroup$

Introduction

Let $C$ be a code of block length $n$ having $A_i^C$ words of Hamming weight $i$, for $i\in [n]$, where $[n]:=\{0,\ldots,n\}$. Then, the sequence $\{ A_i^C \}_{i \in [n]} $ is called the weight distribution of $C$. Often, the weight distribution is represented in the form of a polynomial, the weight enumerator. The well-known MacWilliams identities relate the weight enumerator of a code $C$ to the weight enumerator of the dual code $C^\perp$.

Suppose that we do not know $A_i^C$. Instead, let $C$ be an element from a set of length-$n$ codes $\mathcal{C}_n$, for which we only know the averaged asymptotic weight spectrum, (the average is over the set $\mathcal{C}_n$)

$$S^{\mathcal{C}_\infty}_\delta := \lim_{n \rightarrow \infty} \frac{1}{n} \log \frac{1}{|\mathcal{C_n}|} \sum_{C \in \mathcal{C}_n} A^C_{ \lfloor \delta n \rfloor }$$

where $ 0 \leq \delta \leq 1$ represents the relative weight.

Now, the question is to find a MacWilliams-type of identity that relates the dual (averaged asymptotic) spectrum $S^{\mathcal{C}^\perp_\infty}_\delta$, where $\mathcal{C}_n^\perp$ is the set of codes dual to codes in $\mathcal{C}_n$, to the (known) weight spectrum $S_\delta^{\mathcal{C}_\infty}$.

Motivation

For large-length codes with many codewords, it is often infeasible to determine the weight distribution $A_i$. On the other hand, the averaged weight distribution is known for some families of codes. As an example, take Low-Density Parity-Check (LDPC) codes. These are linear codes that are randomly constructed by sampling the parity check matrix according to some particular strategy. While it is often hard to make non-trivial statements about individual members of this set (in random-code terminology, the set is usually called the ensemble), various results are known for the ensemble, including weight spectras [1].

From a practical point of view, LDPC codes have several desirable properties that make them well-suited for use in real-life applications, such as telecommunication and storage products. To determine whether these codes are also suited for certain cryptological applications, more insight is required into the weight spectrum of the dual ensemble.

An alternative approach is to compute the dual spectrum numerically, by first evaluating the asymptotic weight distribution on a grid of equispaced points, and then using the original discrete MacWilliams identities. This approach, however, is numerically unstable because these computations involve enormous values due to the binomial coefficients.

More about the MacWilliams Identities

We define the enumerator polynomial of the code $C$ as

$$ W(C; x, y) := \sum_i A^C_i x^i y ^{n-i} $$

Then, the MacWilliams identity is given by

$$ W(C^\perp; x,y) = \frac{1}{|C|} W(C ; y-x ,y+x).$$

Another form of the MacWilliams identity is the following,

$$ \hspace{10em} A_d^{C^\perp} = \frac{1}{|C|} \sum_{i=0}^n A_i^C P_d(i;n), \hspace{10em} (1)$$

where $P_d(i;n)$ is a Krawtchouk polynomial,

$$ P_d(i;n):=\sum_{j=0}^d \binom{i}{j}\binom{n-i}{d-j} (-1)^j $$

Informal Conjecture

Informally speaking, the latter form of the MacWilliams identity, (1), looks like a transform, e.g. as a Fourier series. So it seems natural to conjecture that it should be possible to take the limit for $n\rightarrow \infty$ in eq. (1) yielding some integral, similar to how Fourier extended the Fourier series to the continuous Fourier transform. Unfortunately, the author from this MathOverflow question got stuck here. Other references that might help in attacking this problem are [2] (partly about asymptotic behaviour of Krawtchouck polynomials) and work of Krasikov [3] on Krawtchouk polynomials.

References

[1] S. Litsyn and V. Shevelev, "On Ensembles of Low-Density Parity Check Codes: Asymptotic Distance Distributions," IEEE Trans. Inf. Theory, April 2002.

[2] G. Kalai and N. Linial, "On the Distance Distribution of Codes," IEEE Trans. Inf. Theory, September 1995.

[3] http://www.brunel.ac.uk/about/acad/siscm/maths/people/acad/IliaKrasikov

$\endgroup$
1
  • 1
    $\begingroup$ FYI another (and I have been told better) transliteration is Kravchuk, not Krawtchouk. $\endgroup$ Oct 15, 2010 at 16:43

3 Answers 3

3
$\begingroup$

Only worth a comment, but I'm low-rep, so...

I agree with Math Into Coding in the sense that this question is unlikely to have a useful answer. The observation I want to make is that the weight distribution of a long large binary code really does follow the binomial distribution with $p=0.5$ `closely'. Yes, there are examples of codes with only a handful of weights, but they have a very low rate (asymptotically zero). Therefore the expected weight of a codeword is $n/2$ and the standard deviation is $\approx\sqrt n$. This latter fact means that if we study the cdf of words of weight $\le \delta n$, where $\delta\in[0,1]$, then in a sense that could be made more precise, the cdf jumps from $0$ to $1$ near $\delta=1/2$.

So even if you redefine the average weight distribution using windows of the type $[\delta_1n,\delta_2n]$, where $\delta_2\to\delta_1$, you would still just get a spike at $\delta=1/2$ and nothing else. A scale that is a linear function of the code length just won't capture much information about the code.

$\endgroup$
2
$\begingroup$

A short answer is that this question does not have an answer sought in its statement.

Here are the reasons. For simplicity let us assume that $S_\delta$ is not an average asymptotic weight enumerator, but simply an asymptotic weight enumerator of some sequence of codes (the ensemble adds another layer, but changes little in the following). The MacWilliams identity tells us that $A_w^\bot$ is proportional to the sum $\sum_i A_i P_w(i)$. Assume that the sequence of codes has the asymptotic rate $R>0$ (meaning that $\lim_{n\to\infty} (1/n)\log|C_n|\to R$). Further, let $A_0=1,A_1,...,A_n$ be the components of the weight distribution of $C_n$ (this notation is unfortunate because $n$ changes, so we'd better say the code $C_i$ of length $n_i,$ etc., but let's take the shortcut). We have $\sum_i A_i=|C_n|,$ so there are $n+1$ numbers that add to $2^{Rn}.$ As $n$ increases, there must emerge just one dominant component (we are adding a linear number of different exponential functions, one dominates). For most code families known, it is the component $A_{n/2}$, and we have $A_{n/2}\sim 2^{Rn}.$ This is where our inquiry ends because it makes little sense to substitute this in the MacWilliams identity and to seek a meaningful answer: indeed, we will get $A^\bot_{n/2}\sim 2^{(1-R)n}$ and that's pretty much it.

$\endgroup$
4
  • 2
    $\begingroup$ Maybe I'm confusing myself, but doesn't the definition of $S_\delta$ in the question take care of this objection (by looking at $(1/n) \log A_{\lfloor \delta n \rfloor}$, so each exponential growth rate will be measured)? $\endgroup$
    – Henry Cohn
    Dec 23, 2010 at 18:19
  • 2
    $\begingroup$ (I agree that I see no interesting way to plug this into the MacWilliams identity and take a limit, but I don't see how to rule out some more subtle relationship between the asymptotic weight spectra.) $\endgroup$
    – Henry Cohn
    Dec 23, 2010 at 18:24
  • $\begingroup$ Right, either we substitute the weight distribution into the MacWilliams identities and then take the logs and the limits, or first take the $(1/n)\log$, but after that do not know how to use the MacWilliams identities. Could there be a "limit version" of the relationship between the asymptotic weight spectra? Arguably, not along the lines of the above conjecture. Indeed, the reason that the Fourier series becomes a Fourier integral is rather different from taking some parameter to the limit: this happens because the space (the group) becomes noncompact, not because it becomes continuous. $\endgroup$ Dec 23, 2010 at 20:26
  • $\begingroup$ Maybe I should remove conjecture; my knowledge on Fourier theory is quite limited, and I can actually not judge whether the conjecture sketches a wrong suggestion (which would not be my intention, of course). $\endgroup$
    – Nick
    Dec 24, 2010 at 10:28
1
$\begingroup$

The problem might be attackable in a different way. Since the parity check of a code (from a LDPC family) has constant row and column weight, we maybe able to lower bound the number of vectors of a particular weight in its rowspace by assuming that the matrix contains rows that do not overlap at all. For an upper bound on the weights of vectors in the rowspace of the parity check matrix, we could assume that every time we add two rows, they don't overlap at all.

In particular, if we were to assume a code $C$ with a parity check matrix $H$ from the $(n,j,k)-$Gallager ensemble (Ensemble B in Litsyn's paper -- reference [1] in your question), then we know that $H$ contains $j$ blocks where each block has $n/k$ mutually exclusive rows of weight $k$ each. Firstly, the number of weight $k$ vectors in the rowspace of $H$ will be at least $\dfrac{nj}{k}$.

Then, we can say that the number of vectors of weight $2k$ will be at least those which can be obtained by combining two rows within a block. This is $\binom{n/k}{2}j$. We can extend this to a lower bound for number of vectors of length $\lambda k$ for $1\leq \lambda\leq n/k$.

For number of vectors of weight $\lambda k + \beta$ where $1 < \beta < k$, I can't think of an obvious lower bound.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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