Linearity of Concatenated Code

[Johan Rosenkilde]

I've just realised that Concatenated Codes are a strange thing, even when restricting to linear component codes: Let Cout be a [N,K,D] code over some alphabet A, and let Cin be a [n,k,d] code over alphabet Fq. Then we can make a concatenated code if |A| = Fq^k = q^k. But the mapping between A and a^k need not be a linear map! Generally, we would then obtain a non-linear code.

In this generality, Concatenated Codes are unrepresentable in our LinearCode structure. To return (easily) to linear world, we could require that A = F_(q^k), and use a usual basis mapping to from A to Fq^k.

Perhaps the class should then be called a ConcatenatedCodeLinear. It will be a linear code over F of dimension Kk. (The main problem with this restriction is that a concatenated code can be linear under weaker conditions as well)

If we do this, then there are multiple natural message spaces associated to this Concatenated code: the first is Fq^(kK). The second that comes to mind is A^K = F_(q^k)^K but more generally, M^K where M is any natural message space for Cout.

The Fq^(Kk) encoder should be written specifically (probably calling one of the other's to avoid re-coding). But we should be able to make an Encoder which can take any encoder for Cout and become an encoder for the concatenated code. And this should be possible to register dynamically at construction time, such that one will be registered for each Encoder of Cout.

For the first milestone, we need not have all this. Simply the Fq^(Kk) is sufficient, I guess.

[Daniel Augot]

The idea in concatenated codes is to encode first a message over the big alphabet using the outer code, then to encode the symbols of the resulting codeword using the inner code.

I would say that the message space corresponds to the big alphabet, while the code is linear "only" over the small alphabet.

Daniel

[Johan Rosenkilde]

The brilliancy of our Encoder system is that we can support both the small field and the large field as message space! It will simply be two different encoders.

But the code, seen as a set, is a subset F^(nN) where F is the small field. And it is linear (over the small field) when the mapping from the big field to the small one is linear.

But you agree that this is an acceptable restriction?

[Johan Rosenkilde]

Note only the encoder whose message space is Fq^(Kk) will have an associated generator matrix.

[Daniel Augot]

As long as the concatenated code is linear over the small field, I am OK. The non linearity that you describe is may be too esoteric to consider now.

[David Lucas]

Resolved issue #76

→ <<cset 55201a7f9ab7>>