An Introduction to Factor Graphs and Partition Functions through the MacWilliams Identity

One of the fundamental theorems in coding theory is the MacWilliams identity. Let $E$ be the coordinate set, let $n \coloneqq \card{E}$, and, for a linear code $C \leq \F_{q}^{E}$ over the finite field $\F_{q}$, consider its dual code

where

For a codeword $c \in \F_{q}^{E}$, write its support and Hamming weight as

respectively. Define the weight enumerator of the linear code $C$ by

The MacWilliams identity is the formula saying that the weight enumerator of the dual code can be computed from the weight enumerator of $C$ as follows:

This is the MacWilliams identity.

In this note, we prove this MacWilliams identity in the language of factor graphs and partition functions. The note introduces the necessary notation and concepts in the text so that it can be read on its own. The only prerequisites are the basics of linear codes over finite fields, Hamming weight, and dual codes. More concretely, we assume familiarity with the following level of material:

We assume basic familiarity with elementary coding theory, namely with

• what a (finite) field is,

• what a linear code over a finite field is,

• what the Hamming weight is,

• what the dual code is.

(It is not necessary to know a proof of the MacWilliams identity.)

This note does not presuppose Parts 1–8. In the series as a whole, we compare several proofs of the MacWilliams identity, but the classification across the whole series is not needed in order to read the proof in this note. Parity-check matrices, Tanner graphs, factor graphs, partition functions, and Fourier transforms are explained in the text to the extent needed. Even if you have not read the other parts of the series, the necessary notation and calculations are introduced in order so that you can follow the proof of the MacWilliams identity itself. The aim of this note is to use a proof of the MacWilliams identity as a guide to an introduction to factor graphs and partition functions.

A factor graph is a tool for representing a large function depending on many variables as a product of small factors, each depending on only a few variables, and for visualising those dependencies by a graph. A partition function is obtained by summing that product over all values of all variables. In statistical physics it appears as a total weight over all states, and in coding theory it appears as a total weight over words satisfying constraints.

When a linear code $C \leq \F_{q}^{E}$ is written by a parity-check matrix $H$, $C$ is the set of all words $x = (x_{e})_{e \in E} \in \F_{q}^{E}$ satisfying $Hx^{\top} = 0$. This condition decomposes into local constraints, one for each check equation. Then the weight enumerator can be represented as

the partition function obtained by multiplying the coordinate weights for each word $x$ satisfying all check equations, and then summing over all such words.

When each local constraint in this partition function is Fourier-expanded, the dual code $C^{\perp}$ appears naturally. This is the MacWilliams identity as seen from factor graphs and partition functions.

The flow of the note is as follows.

As a standard introduction to factor graphs and the sum–product algorithm, see Kschischang–Frey–Loeliger [KFL01]. For Forney-style normal factor graphs, Loeliger [Loe04] is readable, and Forney [For01] is a basic reference for normal realisations of codes on graphs. For the relation between partition-function duality for normal factor graphs and the MacWilliams identity, see Forney [For11]. In this note, we do not develop all this general theory, but instead extract only the part needed for the ordinary Hamming-weight MacWilliams identity for linear codes over finite fields.

We begin with the term partition function. Rather than entering into its physical interpretation, we use it here as a particular kind of finite sum. The word weight is not restricted here to probabilities or positive real numbers: polynomial-valued and complex-valued weights will be treated in the same way. Following the notation often used in statistical physics, we denote it by $\Zpart$. Every partition function in this note is a finite sum. Consequently, we may later change the order of summation, or decompose a sum over a finite direct product into a product of coordinatewise sums, without any analytic issue.

Consider finitely many variables $x_{1}, x_{2}, \dots, x_{m}$. Assume that each variable $x_{i}$ takes values in a finite set $\mathcal{X}_{i}$. The total state space is

If a weight $F(x)$ is assigned to each state $x = (x_{1}, \dots, x_{m})$, consider the total sum

In this note, we call such a quantity a partition function.

This definition alone may make a partition function look like just a finite sum. The important point is that, in many cases, the weight $F(x)$ can be written as a product of small factors. For example, suppose that it can be written as

Then the partition function is

This expression is not merely the sum of an arbitrary function of four variables, but the sum of a product of local factors, each depending only on neighbouring variables. A factor graph is a graph representation of this “local dependency relation”.

Partition functions also appear naturally in coding theory. For example, let $C \leq \F_{q}^{E}$ be a linear code, and assign a weight $\lambda(a)$ to each coordinate value $a \in \F_{q}$. Then

is a weighted sum over codewords. This is exactly a partition function. If $\lambda(0) = X$ and $\lambda(a) = Y$ ($a \neq 0$), then this partition function becomes the ordinary weight enumerator $W_{C}(X, Y)$. In other words, a weight enumerator is a partition function on the codeword space.

A factor graph is a tool for representing a factorisation of a function as a graph. Here we define the most basic bipartite-graph type factor graph.

The large function represented by the factor graph is

Here $x = (x_{i})_{i \in I}$ is the value of all variables, and $x_{\partial\alpha}$ is obtained by taking only the variables belonging to $\partial\alpha$.

Define the partition function of this function by

Thus a factor graph is a diagrammatic representation of

a function locally decomposed as a product, and the sum of that function over all states.

Figure 1 is the dependency relation in the expression

drawn as a diagram.

As this example shows, a factor graph makes the structure of an expression visible. If the graph is a tree, the sum–product algorithm can compute the partition function and marginal sums efficiently. Even when the graph has cycles, factor graphs are useful as a language for describing dependency relations. In this note, we do not go deeply into the sum–product algorithm as a computational algorithm, and instead use factor graphs as a language for transforming partition functions and deriving the MacWilliams identity.

In factor graphs, not only weights but also constraints can be represented as factors. For this purpose, we use indicator functions.

Over the finite field $\F_{q}$, we write the indicator function of the zero element as

That is, $\delta_{0} = \one_{\{ 0 \}}$. This is the finite-field version of the Kronecker delta.

For example, if we want to keep only the pairs satisfying the condition $x + y = 0$, it is enough to multiply by the factor $\delta_{0}(x + y)$. This factor is $1$ when $x + y = 0$, and $0$ otherwise. Therefore, in the sum defining the partition function, contributions from states not satisfying the condition vanish. For example, over $\F_{2}$, we have the following.

In other words, only $00$ and $11$ remain, and the contributions of $01$ and $10$ vanish.

Using constraint factors, one can represent a linear code as a product of local constraints. This is the Tanner-graph-type factor graph in the next section.

Let $C \leq \F_{q}^{E}$ be a linear code. Set $k \coloneqq \dim C$. The dual code $C^{\perp}$ has dimension $n - k$. Choose a basis of $C^{\perp}$, and let $H$ be the matrix obtained by arranging that basis as its rows. Since $(C^{\perp})^{\perp} = C$, this $H$ gives

Here $Hx^{\top} = 0$ means that $x$ is orthogonal to every row of $H$. Since the rows of $H$ are a basis of $C^{\perp}$, this means that $x$ is orthogonal to every element of $C^{\perp}$. Therefore $x \in (C^{\perp})^{\perp} = C$, and conversely, if $x \in C$, then $x$ is orthogonal to every element of $C^{\perp}$, so $Hx^{\top} = 0$ holds. When writing the abstract coordinate set $E$ and the row set in matrix notation, one may think of having chosen an order on each of them. From now on we use indexed notation and write things in a form independent of that order.

Let the row set be $J$, and write $H = (H_{j, e})_{j \in J,\,e \in E}$. Here $\card{J} = n - k$, and the rows of $H$ are a basis of $C^{\perp}$. Then

In coding theory, this bipartite graph consisting of variable nodes corresponding to coordinates and check nodes corresponding to check equations is called a Tanner graph [Tan81]. The variable nodes correspond to coordinates $e \in E$, and the check nodes correspond to parity-check equations $j \in J$. We join the check node $j$ and the variable node $e$ by an edge exactly when $H_{j, e} \neq 0$. In the language of factor graphs, this is viewed as a Tanner graph whose check nodes carry zero-constraint factors. For a binary code, all non-zero coefficients are $1$, so the check equations can largely be represented by the presence or absence of edges alone. Over a general $\F_{q}$, however, the values of the non-zero coefficients $H_{j,e}$ also affect the check equations. Therefore, for a $q$-ary Tanner graph, we regard the edge $j$–$e$ as carrying the coefficient $H_{j, e}$ as a label.

For each $j \in J$, write

for the set of coordinates connected to the check node $j$, that is, the set of variables on which the check factor $h_{j}$ depends. Here $\partial j$ is not a derivative, but a notation often used in factor graphs for a “neighbourhood” or “set of adjacent variables”. Then the check factor is

It is the same if the sum is written over all of $E$, because the terms with $H_{j, e} = 0$ vanish. In the factor graph, it is connected only to those variables $x_{e}$ for which $e \in \partial j$.

For example, over $\F_{2}$, if

then the two check factors are

In this example, $h_{1}$ is connected only to $x_{1}$, $x_{2}$, $x_{4}$, and $h_{2}$ is connected only to $x_{2}$, $x_{3}$.

In addition, put a one-coordinate weight factor $\lambda(x_{e})$ at each coordinate $e \in E$. Here $\lambda \colon \F_{q} \to \mathcal{K}$ is an arbitrary weight function. Later we specialise to $\lambda(0) = X$ and $\lambda(a) = Y$ ($a \neq 0$). An ordinary Tanner graph consists of variable nodes and check nodes, but in the partition function considered here we additionally attach a one-variable weight factor $\lambda(x_{e})$ to each coordinate. Strictly speaking, we are considering the factor graph obtained by adding coordinate weight factors to the Tanner graph.

In Figure 2, the rectangular check nodes $h_{1}$, $h_{2}$ represent zero-constraint factors, and the small rectangles below or above represent one-coordinate weight factors.

The partition function of this factor graph is

The product of the constraint factors is $1$ exactly when $x \in C$, and is $0$ otherwise. Therefore

Thus $\Zpart_{C}(\lambda)$ is a weighted sum over codewords. From now on, for any linear code $D \leq \F_{q}^{E}$, we write

The first definition $$\begin{aligned} \Zpart_{C}(\lambda) &\coloneqq \sum_{x \in \F_{q}^{E}} \left( \prod_{j \in J} \delta_{0} \left( \sum_{e \in E} H_{j, e} x_{e} \right) \right) \prod_{e \in E}\lambda(x_{e}). \tag{5.1} \end{aligned}$$(5.1) is a constrained sum using a parity-check matrix, and $$\Zpart_{C}(\lambda) = \sum_{c \in C} \prod_{e \in E} \lambda(c_{e}). \tag{5.2}$$(5.2) confirms that it agrees with the weighted sum over codewords. With this notation, $\Zpart_{C^{\perp}}(\what{\lambda})$ appearing later means the partition function obtained by summing the product of the weights $\what{\lambda}$ over the dual codewords. In particular, if

then

In words, the discussion so far says the following.

A weight enumerator is the partition function of a Tanner-graph-type factor graph.

This observation is the starting point of this note.

We now prepare the Fourier transform used to dualise local factors. Fix once and for all a non-trivial additive character $\psi \colon \F_{q} \to \C^{\times}$ of the finite field $\F_{q}$, that is, a map satisfying

and not identically equal to $1$. When $q = p$, one may think of

Here $a \in \F_{p}$ is represented by one of $0, 1, \dots, p - 1$. For general $q = p^{m}$, one can use the trace map and define

The basic property we need is the following orthogonality relation.

Proof

If $b = 0$, every term is $1$, and the sum is $q$. Suppose $b \neq 0$. Then the map $a \mapsto ab$ is a bijection of $\F_{q}$, so

$$\sum_{a \in \F_{q}} \psi(ab) = \sum_{t \in \F_{q}} \psi(t).$$

Put the right-hand side equal to $S$. Since $\psi$ is non-trivial, there exists $d \in \F_{q}$ such that $\psi(d) \neq 1$. As $t$ runs through all of $\F_{q}$, so does $t + d$, and hence

$$S = \sum_{t \in \F_{q}} \psi(t + d) = \psi(d) \sum_{t \in \F_{q}} \psi(t) = \psi(d)S.$$

Since $\psi(d) \neq 1$, we have $S = 0$.

End of proof□

For a one-coordinate weight function $\lambda \colon \F_{q} \to \mathcal{K}$, define its Fourier transform by

In the Fourier transform, the values $\psi(ab)$ are complex numbers, so we enlarge the coefficient ring to a ring containing $\C$ as needed. For the Hamming weight enumerator, it is enough to work in $\C\lbrack X, Y \rbrack$, and for the complete weight enumerator, in $\C\lbrack T_{a} : a \in \F_{q} \rbrack$, which appears later. Here the Fourier transform is defined in the unnormalised form. Therefore, a factor $1/q$ appears in the expansion of the zero constraint. The coefficient $1/\card{C^{\perp}}$ appearing later is obtained by multiplying this $1/q$ once for each check equation.

Let us compute the Fourier transform of the weight

appearing in the Hamming weight enumerator.

Proof

When $b = 0$,

$$\what{\lambda}_{X, Y}(0) = \sum_{a \in \F_{q}} \lambda_{X, Y}(a) = X + (q - 1)Y.$$

Next suppose $b \neq 0$. By Lemma 6.1For $b \in \F_{q}$, $$\sum_{a \in \F_{q}} \psi(ab) = \begin{cases} q, & b = 0,\\ 0, & b \neq 0 \end{cases}$$ holds.Lemma 6.1,

$$\sum_{a \in \F_{q}} \psi(ab) = 0.$$

Hence

$$\sum_{a \in \F_{q}^{\times}} \psi(ab) = -1.$$

Therefore

$$\what{\lambda}_{X, Y}(b) = X + Y\sum_{a \in \F_{q}^{\times}} \psi(ab) = X - Y.$$

End of proof□

This local calculation is precisely the source of the change of variables in the MacWilliams identity,

In the language of factor graphs, it is the result of Fourier-transforming a one-coordinate weight factor.

Next, we Fourier-expand the zero constraint $\delta_{0}(t)$ appearing in the check factors.

Proof

If $t = 0$, the right-hand side is $q/q = 1$. If $t \neq 0$, then by Lemma 6.1For $b \in \F_{q}$, $$\sum_{a \in \F_{q}} \psi(ab) = \begin{cases} q, & b = 0,\\ 0, & b \neq 0 \end{cases}$$ holds.Lemma 6.1,

$$\sum_{y \in \F_{q}} \psi(yt) = 0.$$

This agrees with the left-hand side $\delta_{0}(t) = 0$.

End of proof□

This formula rewrites a constraint factor as a sum over a dual variable $y$. In factor-graph terms, it says that when a check factor is Fourier-expanded, one dual variable appears at that check factor. This dual variable will later form a linear combination of the rows of the parity-check matrix and produce a codeword of the dual code $C^{\perp}$.

Apply Lemma 7.1For any $t \in \F_{q}$, $$\delta_{0}(t) = \frac{1}{q}\sum_{y \in \F_{q}}\psi(yt) \tag{7.1}$$ holds.Lemma 7.1 to the partition function

of the Tanner-graph-type factor graph. Here we write the sum over all of $E$, including terms with $H_{j, e} = 0$. This is the same as summing over $\partial j$, but it makes the later coordinatewise organisation easier to see. All sums are finite sums, so below we freely change the order of summation. Also, when a product separates coordinate by coordinate, we rewrite a sum over a finite direct product as a product of coordinatewise sums.

For each $j \in J$,

Substituting this into all check equations gives

Let us pause to organise the roles of the notation. $x_{e}$ is the $e$-coordinate of the original candidate codeword $x \in \F_{q}^{E}$. On the other hand, the capital letters $X$, $Y$ are formal variables used later in the Hamming weight enumerator, and are different from $x_{e}$ and from $y_{j}$ appearing here. $y = (y_{j})_{j \in J}$ is the dual variable corresponding to the check factors, and $y_{j}$ is the coefficient appearing when check equation $j$ is Fourier-expanded. $y_{j}$ is not a coordinate of a dual codeword. The actual dual codeword is obtained later as $u = yH$, and its $e$-coordinate is

Thus, in this calculation, the role of the notation moves from the original coordinate variable $x_{e}$, through the coefficients $y_{j}$ attached to check equations, to the coordinates $u_{e}$ of a dual codeword.

By the property $\psi(s+t)=\psi(s)\psi(t)$ of an additive character, the inner character factors separate coordinate by coordinate. Indeed,

Here we are using the basic decomposition of a sum over a finite direct product. For one-variable functions $g_{e}$ for each $e$, one has

This is obtained by repeating the two-variable identity

for the number of coordinates. Therefore the inner sum over $x$ in $$\begin{aligned} \Zpart_{C}(\lambda) &= q^{-\card{J}} \sum_{y \in \F_{q}^{J}} \sum_{x \in \F_{q}^{E}} \prod_{j \in J} \psi\left( y_{j} \sum_{e \in E} H_{j, e} x_{e} \right) \prod_{e\in E}\lambda(x_e). \tag{8.1} \end{aligned}$$(8.1) is

Define $yH \in \F_{q}^{E}$ by

This is a linear combination of the rows of $H$. Thus the above calculation gives

Now the rows of $H$ have been chosen as a basis of $C^{\perp}$, so the map

is a bijection. Also $\card{J} = \dim C^{\perp} = n - k$, and hence

Therefore $$\Zpart_{C}(\lambda) = q^{-\card{J}} \sum_{y \in \F_{q}^{J}} \prod_{e \in E} \what{\lambda}((yH)_{e}). \tag{8.2}$$(8.2) becomes

The right-hand side is the partition function over the dual code $C^{\perp}$. In other words,

This is the central formula in the direction obtained directly from the calculation. In other words, it writes the partition function of $C$ in terms of the partition function on the $C^{\perp}$ side. By contrast, the MacWilliams identity is usually written in the opposite direction: it expresses the weight enumerator of $C^{\perp}$ in terms of that of $C$. To obtain that standard direction, we apply this general formula to $C^{\perp}$ and reverse the direction. In general, applying the same formula to a linear code $D \leq \F_{q}^{E}$ gives

Now set $D \coloneqq C^{\perp}$. Since $D^{\perp} = C$, we obtain

The coefficient changes from $1/\card{C^{\perp}}$ to $1/\card{C}$ because, in the standard direction, we put $D = C^{\perp}$, and the dual code $D^{\perp}$ in that case is $C$.

In words, the directly obtained direction says the following.

More precisely, the partition function of the code $C$ is $1/\card{C^{\perp}}$ times the partition function over the dual code $C^{\perp}$ using the Fourier-transformed one-coordinate weight $\what{\lambda}$.

$$\Zpart_{C}(\lambda) = \frac{1}{\card{C^{\perp}}} \Zpart_{C^{\perp}}(\what{\lambda}). \tag{8.4}$$(8.4) is partition-function duality for linear codes over finite fields. Here we reread this formula in the language of factor graphs.

The original factor graph had the following two types of factors.

Check factors

For each $j \in J$, the factor representing the linear constraint

$$\delta_{0}\left(\sum_{e \in E} H_{j, e} x_{e} \right).$$

Weight factors

For each coordinate $e \in E$, the one-coordinate weight factor $\lambda(x_{e})$.

When a check factor is Fourier-expanded, a dual variable $y_{j}$ appears for each check. Using the values of these dual variables, for each coordinate we obtain

This is a linear combination of the rows of the parity-check matrix $H$. Therefore, as $y$ varies, $yH$ runs through all of $C^{\perp}$.

On the other hand, the sum over the coordinate variable $x_{e}$ locally becomes

Thus the coordinate weight factor $\lambda$ is changed into the Fourier-transformed weight factor $\what{\lambda}$.

In factor-graph terms, when the original check factors are Fourier-expanded, summation variables $y_{j}$ corresponding to those check factors appear. These $y_{j}$ are coefficients used to linearly combine the rows of $H$ and form $u = yH$. The coordinates of a dual codeword are the $u_{e}$ indexed by $e \in E$, and not the $y_{j}$. Also, the original coordinate weight factor $\lambda(x_{e})$, after summing over $x_{e}$, becomes the Fourier-transformed weight factor $\what{\lambda}(u_{e})$.

In the general theory of normal factor graphs, one performs this simultaneously for each local factor. Depending on the convention, sign-inversion factors and normalisation constants appear, but roughly speaking, one Fourier-transforms each local factor and replaces edge variables by dual variables. The partition function of the factor graph on the dual side obtained in this way is related to the original partition function by an explicit constant factor. The calculation in this note is the specialisation of that general theory to a Tanner-graph-type factor graph.

We now return to the ordinary Hamming weight enumerator. Let the one-coordinate weight be $\lambda_{X, Y}$ from $$\lambda_{X, Y}(a) \coloneqq \begin{cases} X, & a = 0,\\ Y, & a \neq 0 \end{cases} \tag{5.3}$$(5.3). Then, for any code $D \leq \F_{q}^{E}$,

Also, by Lemma 6.2Let $\lambda_{X, Y}$ be defined by (eq:lambda-hamming-weight). Then $$\what{\lambda}_{X, Y}(b) = \begin{cases} X + (q - 1)Y, & b = 0,\\ X - Y, & b \neq 0 \end{cases}$$ holds.Lemma 6.2, we had

This $\what{\lambda}_{X, Y}$ is a one-coordinate weight which returns $X + (q - 1)Y$ when the input is $0$, and returns $X - Y$ when the input is non-zero. Therefore, multiplying this weight over $C$ and summing is the same as substituting $X + (q - 1)Y$ for $X$, and $X - Y$ for $Y$, in $W_{C}(X, Y)$. Thus, substituting $\lambda = \lambda_{X,Y}$ into $$\Zpart_{C^{\perp}}(\lambda) = \frac{1}{\card{C}} \Zpart_{C}(\what{\lambda}). \tag{8.6}$$(8.6), we obtain

That is,

This is precisely the MacWilliams identity.

The important point in this proof is that the change of variables

does not appear suddenly at the global level. It is the result of applying the one-coordinate Fourier transform to the weight factor $\lambda_{X, Y}$ at each coordinate. In other words, the MacWilliams transform is obtained by gluing together the local Fourier transforms at the coordinates of the factor graph across the whole graph.

Finally, let us check the formula in a small example. Let $E = \{ 1, 2 \}$, and consider the binary repetition code

This code is self-dual, that is, it satisfies $C^{\perp} = C$. Indeed, the condition that $u = (u_{1}, u_{2})$ be orthogonal to every codeword of $C$ is

and over $\F_{2}$ this means that $u_{1} = u_{2}$. Therefore $C^{\perp} = C$.

We may take

as a parity-check matrix. The partition function is

If $\lambda(0) = X$ and $\lambda(1) = Y$, then

The one-coordinate Fourier transform in the binary case is

In this example too, the same local calculation as in the general case appears directly. Writing the additive character of $\F_{2}$ as $\psi(t) = (-1)^{t}$, we have

Substituting this into the partition function, for fixed $y \in \F_{2}$ we get

Thus, even in this small example, the general calculation appears: after Fourier-expanding the constraint factor and taking the coordinatewise sums, the one-coordinate weight factor changes into $\what{\lambda}$. Formula $$\Zpart_{C}(\lambda) = \frac{1}{\card{C^{\perp}}} \Zpart_{C^{\perp}}(\what{\lambda}). \tag{8.4}$$(8.4) asserts, since $C = C^{\perp}$ and $\card{C^{\perp}} = 2$, that

Computing the right-hand side gives

It indeed agrees with the original weight enumerator.

Since this example is self-dual, the distinction between the $C$ side and the $C^{\perp}$ side is not very visible. In general, one first obtains

and then applies the same formula to $C^{\perp}$ in order to put it in the usual direction of the MacWilliams identity.

Although the graph in this example is very small, the structure is the same as in the general case. Fourier-expand the constraint factor $\delta_{0}(x_{1} + x_{2})$ and take the coordinatewise sums; then the one-coordinate weight factor is Fourier transformed. As a result, the partition function over the dual code appears.

Let us also look at a non-self-dual example where the standard direction is easier to see. Over $\F_{2}$, take

Then

The dual code is

and

For example, we can take

as a parity-check matrix. Then

As $y_{1}, y_{2} \in \F_{2}$ vary,

appear exactly once each. Here again, $y_{1}, y_{2}$ are not coordinates of a dual codeword, but coefficients used to linearly combine the two rows of $H$ and produce the dual codeword $u = yH$. The right-hand side of the MacWilliams identity is

which indeed agrees with $W_{C^{\perp}}(X, Y)$. Since this example is not self-dual,

shows the standard direction more clearly.

This section supplies background that was not used in the proof in the main text. It is included as a supplement for placing the calculation in this note within the general theory of normal factor graphs, after one has read the derivation of the MacWilliams identity. The proof above did not invoke a general theorem on normal factor graphs; it directly Fourier-expanded the partition function of a Tanner-graph-type factor graph. For readers unfamiliar with normal factor graphs, it is enough to read this section as background explanation.

The proof itself proceeded by following formulae for an ordinary bipartite factor graph of Tanner-graph type. On the other hand, normal factor graphs provide background for understanding that this local Fourier transform is a special case of a more general graph duality.

In a Forney-style normal factor graph, variables are drawn as edges and factors as vertices. In an ordinary factor graph, both variables and factors are vertices. In a normal factor graph, variables become edges connecting factors to factors. In a Forney-style normal factor graph, internal variables are drawn as edges and external variables as half-edges.

The basic advantage of a normal factor graph is that the operation of taking a dual can be described locally. Depending on the convention, sign-inversion factors and normalisation constants appear, but roughly speaking, by Fourier-transforming each factor and replacing each edge variable by a dual variable, one obtains what is called the dual graph in the general theory of normal factor graphs. Its partition function is related to the original partition function by a constant factor. This general theorem is Forney-style normal-factor-graph duality.

We do not develop the general theory of normal factor graphs in full here. Instead, we record the underlying idea.

In an ordinary factor graph, a variable $x$ can appear in three or more factors. In normal form, one creates copies $x^{(1)}, x^{(2)}, x^{(3)}, \dots$ of that variable and inserts an equality factor $\eq(x^{(1)}, x^{(2)}, x^{(3)},\dots)$ forcing all of them to be equal. Here

In this way, each variable copy can be made adjacent to at most two factors.

For the Tanner-graph-type factor graph in this note as well, if one wants a strict Forney-style normal factor graph, one introduces copies of each coordinate variable and equality factors. However, the essence of the calculation deriving the MacWilliams identity lies in Fourier-expanding each check factor and locally separating the coordinatewise sums. For this reason, this note did not go deeply into the details of diagrammatic normalisation, but followed the local dualisation inside the formulae.

Let us emphasise this point. The proof here uses the same Fourier principle as the ordinary character-theoretic proof. However, instead of writing one large character sum all at once, it proceeds as the local operation

Fourier-expand each check factor, and separate the sum for each coordinate variable.

This is the factor-graph viewpoint.

This section is supplementary. If you only want to read about the ordinary Hamming weight enumerator, you may skip it. Here we look at the finer weight enumerator before all non-zero elements are collected into the same variable $Y$.

Writing the one-coordinate weight $\lambda$ with separate variables gives the complete weight enumerator. Introduce a variable $T_{a}$ for each $a \in \F_{q}$, and put $\lambda(a) \coloneqq T_{a}$. Then

This is the complete weight enumerator of $C$. In this note, we write it as

The one-coordinate Fourier transform appears as the change of variables

The superscript $\mathrm{F}$ is a symbol indicating that the variable is after Fourier transform, and is different from the symbol $\F$ denoting a finite field. Here we enlarge the coefficient ring to $\C\lbrack T_{a} : a \in \F_{q} \rbrack$ and compute there. Therefore $$\Zpart_{C}(\lambda) = \frac{1}{\card{C^{\perp}}} \Zpart_{C^{\perp}}(\what{\lambda}). \tag{8.4}$$(8.4) can be written as

This is one direction of the MacWilliams identity for the complete weight enumerator.

To put it in the form usually seen, apply $$\cwe_{C}((T_{a})_{a \in \F_{q}}) = \frac{1}{\card{C^{\perp}}} \cwe_{C^{\perp}}((T_{b}^{\mathrm{F}})_{b \in \F_{q}}). \tag{13.1}$$(13.1) to $C^{\perp}$. Since $(C^{\perp})^{\perp} = C$ and $\card{(C^{\perp})^{\perp}}=\card{C}$, we obtain

This formula is the MacWilliams identity for the complete weight enumerator.

One point is worth noting: depending on the convention for the Fourier transform, $\psi(-ab)$ may appear instead of $\psi(ab)$. For the complete weight enumerator, this difference appears as the replacement of the index of the transformed variable from $b$ to $-b$. On the other hand, when specialising to the Hamming weight enumerator, all non-zero values are sent to the same variable $Y$, so this replacement of indices becomes invisible. Therefore it does not affect the final Hamming-weight version of the MacWilliams identity.

Let us look back at the proof in this note.

First, we viewed the weight enumerator as a partition function. The weight enumerator is obtained by multiplying coordinatewise weights for each codeword $c \in C$ and summing all of them. That is,

This viewpoint lets us regard the weight enumerator as a “weighted sum over states satisfying constraints”.

Second, we represented the code $C$ as a product of local constraints. Using a parity-check matrix $H$, the code $C$ is the simultaneous solution set of the constraints, one for each row $j$,

In a $q$-ary Tanner graph, not only the presence or absence of an edge, but also the edge label $H_{j, e}$, is part of the data determining the check equation. This constraint is incorporated into the partition function as the factor

Thus the code is represented not as one large set, but as a collection of local constraints, one for each check equation. The factor graph actually used in this note was obtained by adding the one-coordinate weight factor $\lambda(x_{e})$ at each coordinate to this Tanner graph.

Third, we Fourier-expanded the zero constraint. The constraint factor can be written as

This is an operation that transforms a constraint into a sum over a dual variable $y$. Applying this transformation for each check equation produces the dual variables $y_{j}$. Here again, $y_{j}$ is not a coordinate of a dual codeword, but a coefficient used to linearly combine check rows.

Fourth, the coordinatewise sums became one-coordinate Fourier transforms. When the dual variables $y_{j}$ from the check equations are collected together, each coordinate contains

Taking the sum over $x_{e}$ at that coordinate gives

Thus the original weight factor $\lambda$ changes into the Fourier-transformed weight factor $\what{\lambda}$.

Fifth, $yH$ ran through the dual code. Since the rows of $H$ have been chosen as a basis of $C^{\perp}$, as $y$ runs through $\F_{q}^{J}$, $yH$ runs through all of $C^{\perp}$ exactly once. Writing the dual codeword as $u = yH$, its coordinates are $u_{e} = (yH)_{e}$. Thus the partition function of the original code $C$ is rewritten, with the coefficient $1/\card{C^{\perp}}$ and the Fourier-transformed one-coordinate weight $\what{\lambda}$, as a partition function over the dual code $C^{\perp}$. In the usual direction of the MacWilliams identity, the same general formula is applied to $C^{\perp}$, so the coefficient becomes $1/\card{C}$.

In one sentence, the point is as follows.

The MacWilliams identity is the fact that, for the partition function of a Tanner-graph-type factor graph, if one locally Fourier-expands the zero-constraint factors and then takes the coordinatewise sums, a partition function over the dual code appears, together with a constant factor and the Fourier-transformed one-coordinate weight.

Along the way to proving the MacWilliams identity, this note introduced the basic tools of factor graphs and partition functions. They can be organised as follows.

Partition function

The total sum of weights over all states. In this note, we treated it as a sum over finite sets,

$$\Zpart = \sum_{x} \prod_{\alpha} f_{\alpha}(x_{\partial\alpha}).$$

Factor

A local function depending on only a small number of variables. By decomposing a large function into a product of factors, one can make the dependency relations easier to see.

Factor graph

A representation of the dependency relation between variables and factors as a bipartite graph. One prepares variable vertices and factor vertices, and joins a factor to the variables on which it depends.

Constraint factor

A factor which is $1$ when a condition is satisfied and $0$ when it is not. We represented linear constraints using $\delta_{0}$.

Tanner-graph-type factor graph

A factor graph representing a linear code as local constraints on a Tanner graph consisting of variable nodes corresponding to coordinates and check nodes corresponding to check equations. For a $q$-ary code, the edge labels $H_{j, e}$ are also data determining the check equations. In this note, we further added the one-coordinate weight factor $\lambda(x_{e})$ at each coordinate. The weight enumerator can be represented as the partition function of this graph.

Normal factor graph

A Forney-style factor graph in which variables are drawn as edges and factors as vertices. It is a framework in which dualisation can be described factor by factor locally.

One-coordinate Fourier transform

The operation transforming a one-coordinate weight factor $\lambda$ by

$$\what{\lambda}(b) = \sum_{a \in \F_{q}} \lambda(a)\psi(ab).$$

For the Hamming weight factor, $X + (q - 1)Y$ and $X - Y$ appear.

Fourier expansion of the zero constraint

The formula writing the constraint factor $\delta_{0}(t)$ as

$$\delta_{0}(t) = \frac{1}{q} \sum_{y \in \F_{q}} \psi(yt).$$

This produces dual variables from local constraints.

Partition-function duality

The principle that, when local factors are Fourier-transformed, the original partition function and the partition function of the factor graph on the dual side are related by a constant factor. In the general theory of normal factor graphs, this factor graph on the dual side is treated as the dual graph. In this note, as the most basic example of this, we derived the MacWilliams identity for linear codes.

On the surface, the proof in this note is a proof using factor graphs and partition functions. We represented a code as local constraints, one for each parity-check equation, and read the weight enumerator as the corresponding constrained partition function. Then we Fourier-expanded each constraint factor and separated the coordinatewise sums.

Within the five-family classification used in this series, the proof in this note belongs to the

Fourier, character, and Poisson family.

The reason is that the fundamental principle by which the dual code appears is the orthogonality relation for additive characters of finite fields. Indeed, the expansion of the zero-constraint factor,

is precisely a finite Fourier transform formula.

However, the viewpoint in this note differs from the ordinary character-theoretic proof. In the usual proof, one treats the character sum over the whole code $C$,

all at once. By contrast, in this note we started from local Fourier expansions for each check factor and transformed the one-coordinate weight factors through coordinatewise sums. That is, instead of applying the Fourier transform “once globally”, we glued together local operations on the factor graph.

This difference is the value of the factor-graph viewpoint. Even for the same MacWilliams identity, one can view it as “global character orthogonality”, or as “duality of partition functions with local constraints”. The latter viewpoint extends naturally to convolutional codes, tail-biting codes, codes on graphs, and models in statistical physics.

At this point, the derivation of the MacWilliams identity from factor graphs and partition functions, which is the main claim of this note, is complete.

In the next note, we look at the MacWilliams identity from the perspective of analytic trace formulae.

In this proof, we represented the weight enumerator as the partition function of a Tanner-graph-type factor graph, and moved to the partition function of the dual code by a local Fourier transform. In the next note, we consider operators on Hamming spaces, especially heat kernels and Markov operators on Hamming graphs, and compute their traces in two ways. In one calculation, the dual code appears from the spectral side, and in the other calculation, the weight enumerator of the original code appears from the trace of a translation action.

Thus the main ingredients next time are

Even though the proof belongs to the same Fourier, character, and Poisson family, the next note will show not a “partition function with local constraints”, but the analytic viewpoint of “computing the trace of an operator in two ways”.

Footnotes

1. Here $\mathcal{K}$ is a range of coefficients in which addition and multiplication can be performed, for example $\C$ or a polynomial ring. At first it is enough to think of a commutative semiring or a commutative ring. From the section where Fourier expansion is used onward, because we handle $1/q$ and character values, we enlarge the coefficient ring to one containing $\C$ as needed. ↩

References

1. [KFL01] Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger. Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 498–519, 2001. doi:10.1109/18.910572 Citation contextAs a standard introduction to factor graphs and the sum–product algorithm, see Kschischang–Frey–Loeliger [KFL01]. For Forney-style normal factor graphs, Loeliger [Loe04] is readable, and Forney [For01] is a basic reference for normal realisations of codes on graphs. For the relation between partition-function duality for normal factor graphs and the MacWilliams identity, see Forney [For11]. In this note, we do not develop all this general theory, but instead extract only the part needed for the ordinary Hamming-weight MacWilliams identity for linear codes over finite fields.↩
2. [Loe04] Hans-Andrea Loeliger. An introduction to factor graphs. IEEE Signal Process. Mag., vol. 21, no. 1, pp. 28-41, 2004. doi:10.1109/MSP.2004.1267047 https://api.semanticscholar.org/CorpusID:7722934 Citation contextAs a standard introduction to factor graphs and the sum–product algorithm, see Kschischang–Frey–Loeliger [KFL01]. For Forney-style normal factor graphs, Loeliger [Loe04] is readable, and Forney [For01] is a basic reference for normal realisations of codes on graphs. For the relation between partition-function duality for normal factor graphs and the MacWilliams identity, see Forney [For11]. In this note, we do not develop all this general theory, but instead extract only the part needed for the ordinary Hamming-weight MacWilliams identity for linear codes over finite fields.↩
3. [For01] Jr. G. David Forney. Codes on graphs: normal realizations. IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 520–548, 2001. doi:10.1109/18.910573 Citation contextAs a standard introduction to factor graphs and the sum–product algorithm, see Kschischang–Frey–Loeliger [KFL01]. For Forney-style normal factor graphs, Loeliger [Loe04] is readable, and Forney [For01] is a basic reference for normal realisations of codes on graphs. For the relation between partition-function duality for normal factor graphs and the MacWilliams identity, see Forney [For11]. In this note, we do not develop all this general theory, but instead extract only the part needed for the ordinary Hamming-weight MacWilliams identity for linear codes over finite fields.↩
4. [For11] Jr. G. David Forney. Codes on graphs: duality and MacWilliams identities. IEEE Trans. Inform. Theory, vol. 57, no. 3, pp. 1382–1397, 2011. doi:10.1109/TIT.2011.2104994 Citation contextAs a standard introduction to factor graphs and the sum–product algorithm, see Kschischang–Frey–Loeliger [KFL01]. For Forney-style normal factor graphs, Loeliger [Loe04] is readable, and Forney [For01] is a basic reference for normal realisations of codes on graphs. For the relation between partition-function duality for normal factor graphs and the MacWilliams identity, see Forney [For11]. In this note, we do not develop all this general theory, but instead extract only the part needed for the ordinary Hamming-weight MacWilliams identity for linear codes over finite fields.↩
5. [Tan81] R. Michael Tanner. A recursive approach to low complexity codes. IEEE Trans. Inform. Theory, vol. 27, no. 5, pp. 533–547, 1981. doi:10.1109/TIT.1981.1056404 Citation contextIn coding theory, this bipartite graph consisting of variable nodes corresponding to coordinates and check nodes corresponding to check equations is called a Tanner graph [Tan81]. The variable nodes correspond to coordinates $e \in E$, and the check nodes correspond to parity-check equations $j \in J$. We join the check node $j$ and the variable node $e$ by an edge exactly when $H_{j, e} \neq 0$. In the language of factor graphs, this is viewed as a Tanner graph whose check nodes carry zero-constraint factors. For a binary code, all non-zero coefficients are $1$, so the check equations can largely be represented by the presence or absence of edges alone. Over a general $\F_{q}$, however, the values of the non-zero coefficients $H_{j,e}$ also affect the check equations. Therefore, for a $q$-ary Tanner graph, we regard the edge $j$–$e$ as carrying the coefficient $H_{j, e}$ as a label.↩