(See also MO117508, MO116611). This post describes somewhat real problem with convolutional codes. Let me first try to give brief and vague formulation of the question, later give details.

**Problem briefly (and vaguely)** I need to find PERIODIC "function" s(x), which is SOMETHING LIKE (but not really!!!) solution of ODE s+as'+bs''+...=f (for periodic f: f(x)=f(x+T)) (precise formulation is complicated - see below), standard methods allow to find solution of the problem with given BOUNDARY condition like s(0)="A".
So we do the following: we consider the problem on $[0, \infty]$ and then take
as a result $s(x)$ on interval $ [NT, (N+1)T]$ for large enough N.

**Numerical phenomena 1** in many case (9997 out of 10000) indeed we find that result of the optimization problem on $[0, \infty]$ above is periodic with period $T$ starting from some $x$ large enough.

**Numerical phenomena 2** in many case if we take $s(x)$ obtained in this way
it coincides with "honest solution" of optimization problem in the class of periodic functions
on $[0,T]$.

**Numerical phenomena 3** In some cases $s(x)$ becomes (for large "x") periodic NOT with period $T$, but $2T$, in much rarely with $3T$, much much rarely $3T$ etc...

Naively I found expect that I should always get periodic function s(x) - because we know that dependence on boundary should decrease as we go from boundary further and further. And if there is no boundary at all then the problem has translation invariance by period $T$. So I would expect that its solution should be periodic with period $T$, so periods $2T, 3T,...$ comes as a surprise.

**Question** I would be happy to hear any comments/explantations on the phenomenas above.

## -------------------------------------

## Coding Setup and Numerical experiments

## -------------------------------------

**Simplest convolutional encoder**.
Consider the map: $CC^{k}:$ {$-1,1$}$^k \to$ {$-1,1$}$^{2k}$,
which is defined by the following formulas $CC^k(s_1,...,s_k)=(c_1,...,c_{2k})$:
$$ c_{2i-1}= s_i $$
$$ c_{2i}= s_is_{i-1} $$, for $i=1,...,k$

In the second formula for $i=1$ we have problem, since it writes $s_{1}s_{0}$ and you should ask what is $s_{0}$, since we only have $s_1$, but not $s_0$ ?

There are two ways to define:

**(1) $CC_{tb}$ "Periodic" (tail-biting)** $$ s_{0} = s_{k}$$

**(2) $CC_{trunc}$ "Initial 1"** $$ s_{0} = 1$$

Let us denote the first encoder by $CC_{tb}$ (tail-biting) and the second by $CC_{trunc}$ (truncated) (standard terminology).

## -------------

Let us a take any vector $r\in R^{2k}$, repeat it $l$ times: $\tilde r = (r,r,r,...,r)\in R^{2kl}$.

Let us find an element $\tilde c$ which belongs to the image of $CC_{trunc}^{kl}$ and which is nearest to $\tilde r$. Write $\tilde c = (c_1,...,c_l)$, where $c_p \in ${-1,1}$^{2k}$. (I.e. we "decode" $\tilde r$).

**Numerical phenomena 1** it often happens that $c_{p}=c_{p+1}=c_{p+2}=...$
starting from some $p: 1 <= p<l$. E.g. 9997 times from 10000 for $r$ random normal N(1,10).
I.e. we see "periodic solution" since we made our "force"
$\tilde r = (r,r,r,...,r)\in R^{2kl}$ periodic with period $k$.

**Numerical phenomena 2** it often happens that $c_p$ belongs to the image of $CC_{tb}^{k}$.

**Numerical phenomena 3** Quite rarely it happens that we get periodic solution with "period" $2k$ instead of expected period $k$, i.e. we get $c_{p}=c_{p+2}=c_{p+4}=...$.
E.g. it happen 3 times out of 10000 for $r$ random normal N(1,10).

## Motivations

**General setup of error-correcting codes** There is metric space $RS$ ("set of all possible Received Signals") and some subset $C$ ("set of all possible sent (encoded) signals").
**Decoder** is any map $RS \to C$. **Best Decoder** is a map which corresponds to a point $r \in RS$ a nearest point $c \in C$.

The motivation for this setup is the following: we sent a signal $c$, but due to noise we get not exactly $c$ but some $r$ (typically $c+epsilon$), we want to find $c$ for given $r$.

Typical situation $RS= R^n$ and $C$ is subset of hypercube {$-1,1$}$^n$.

**Linear code** is such code where $C$ is SUBGROUP of {$-1,1$}$^n$ (which is considered as a group under the multiplication and is, of course, isomorphic to $(Z/2Z)^n$).

Since any subgroup of {$-1,1$}$^n$ is isomorphic to {$-1,1$}$^k$ for some $k$,
we can define **encoder** - it is isomorphism {$-1,1$}$^k$ $\to C \subset R^n$.

**Exercise** Both encoders $CC_{tb}$ and $CC_{trunc}$ are LINEAR (i.e. their images are subgroups of{$-1,1$}$^{2k}$).

**Remark** Viterbi algorithm provides implementation of best decoder for $CC_{trunc}$ which is computationally efficient.

**Task** Find computationally efficient algorithm for decoding $CC_{tb}$ (of course, millions of papers discuss this, but sometimes you get more asking MO rather than google:) ).