Please help shed light on this theorem (code extensions?)

Question

The following is a lecture slide. A couple of questions:

1) Is "code extension" being used correctly here? From my googling, what is described doesn't seem to be a code extension.

2) Does $C$ really have length $2n$? For each word $\vec a$, surely there are more than two $\vec a + \vec b$ that can be appended?

3) Is there an alternate statement of this theorem anywhere on the internet? I don't think I have properly understood the construction of $C$.

Answer 1

1. In the coding theory class I took, I was told that an extended code is one where the dimension stays the same but the length increases. So, in that sense, $C$ is neither an extension of $A$ nor $B$. However, I don't have any references on that, other than my personal class notes.

2. Yes, $C$ has length $2n$. I think you might be misunderstanding the notion of the 'length' of a block code. The 'length' is the number of symbols in each codeword. For example, $0000$ has length 4 and $AB6D29$ has length 6. For a block code, each codeword has the same length, so the length of the code is well-defined.

As for (3), I'm not sure where to find an alternate statement. The construction of that code seems pretty specific, so perhaps your lecturer/professor came up with it as an example.

Answer 2

The construction in question is sometimes called the Plotkin construction. It is described in Chapter 2, Section 9, of MacWilliams and Sloane's Theory of Error-Correcting Codes (1978) under the name of the $|u|u+v|$ construction, and used in several other places (chapters) in that tome. As a special case, if $A$ is a $r$-th order binary Reed-Muller code of length $2^m$ and $B$ is a $(r-1)$-th order binary Reed-Muller code of length $2^m$, then $C$ is a $r$-th order binary Reed-Muller code of length $2^{m+1}$. Every polynomial $f$ of degree $r$ in $m+1$ variables can be expressed as $f = g + x_{m+1}h$ where $g$ is a polynomial of degree $r$ in $x_1, x_2, \cdots, x_m$ and $h$ is a polynomial of degree $r-1$ in $x_1, x_2, \cdots, x_m$. The codewords of the form $[\mathbf a, \mathbf a]$ are the truth tables of the $g$ polynomials, while codewords of the form $[\mathbf 0, \mathbf b]$ are the truth tables of the $x_{m+1}h$ polynomials. By truth table I mean that the codeword corresponding to $f(x_{m+1},x_m,\cdots, x_1) = g(x_m,\cdots, x_1)+x_{m+1}h(x_m,\cdots, x_1)$ is $$[f(\mathbf 0), f(\mathbf 1), \cdots, f(\mathbf{2^m-1}),f(\mathbf{2^m}), f(\mathbf{2^m+1}), \cdots, f(\mathbf{2^{m+1}-1})]$$ where $\mathbf i$ is the binary representation of the integer $i$. Note that $\mathbf{2^m-1} = 011\cdots 11$ while $\mathbf{2^m} = 100\cdots 00$, $\mathbf{2^m+1} = 100\cdots 01$,$~~\ldots$, $\mathbf{2^{m+1}-1} = 111\cdots 11$, . .. This idea was used extensively in the study of binary Reed-Muller codes, including in the MacWilliams and Sloane book.