Define an $(m,q,d,k)$-(block) code $C$ to be a code with block size $m$, alphabet $0\ldots ,q-1$, and (non-relative) rate $k$. Meaning: $k=log_q (|C|)$ (if we think of $C$ as a set of legal codewords) ($d$ is the distance which isn't important for this particular question). Such a code could also be thought of as a function: $$C:[q]^k\rightarrow[q]^m$$ As it takes a word of length $k$ over $[q]$ and encodes it into a word of length $m$.

To my understanding, given an $(m,q,d,k)$ code $C_{out}$ and an $(m',q',d',k')$ code $C_{in}$ such that $q'^{k'}=q$, we can define the concatenation of $C_{out}$ with $C_{in}$ to be a code which takes an input for $C_{out}$, encodes it using $C_{out}$, and then encodes each letter of the resulting word using $C_{in}$. If this is how a concatenated code truly works, then if we denote the concatenated code $C'$ it should be thought of as a function: $$C':[q]^k\rightarrow [q']^{m*m'}$$ However, the common notation for such a codes (as can be seen here, for example) is: $$C_{out}\circ C_{in}$$ Which is exactly in the opposite order to what we would expect if we think about the concatenated code as a composition of functions.

Is there a problem with my understanding of concatenated codes, or is the notation simply confusing? And if my understanding is good, is there a reason the aforementioned notation is common?


You get it right.

The notation $$(C_{out}\circ C_{in})(m)$$ means: "take m, encode it with $C_{out}$ and then encode each symbol with $C_{in}$." From the point of view of the channel, $C_{in}$ is "closer", hence the inner one; see the figure in the wiki page you refer to.

This is indeed what the wiki page says.

The confusion is probably because you think of composition of functions, where the common notation $(g\circ f)(x)$ means $g(f(x))$. But here we don't have function composition but instead code concatenation, so the $\circ$ operation has a different meaning - it means $$ C_{in}(c_1), \ldots, C_{in}(c_n)$$ with $(c_1, \ldots, c_n) = C_{out}(m)$.

Just to complete the picture, concatenation codes where developed by David Forney in 1965, where he named the inner/outer codes that way (again, having the channel as the center of this point-of-view). See his PHD work and in particular Figure 2 that illustrates this concept (same as in wikipedia).


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.