(A)periodicity and (In)dependence on the boundary condition for some discrete analog of ODE (convolutional codes)

Question

(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:) ).

Answer 1

Linear periodic problems are solved with Fourier series. I comment on the first part only.

$f$ is periodic, suppose wlog that $T=2\pi$, and expand it into Fourier series $$f(x)=\sum a_ne^{inx}.$$ Let $L$ be the differential operator in the left hand side. I suppose that the coefficients are constant (from your answer to my question in your previous post). Moreover, I assume that the differential operator is of finite order.

Solution $s(x)$ is a superposition (linear combination) of solutions to $$(1)\quad\quad (Ls)(x)=e^{inx}.$$ If the characteristic equation of $L$ has no integer roots, then this always has a solution of the form $s_n(x)=c_ne^{inx}$, where $c_n$ is found by substitution of this form of $s_n$ to the equation. In this case we obtain all $c_n$ and the periodic solution $$s(x)=\sum_{n} c_ne^{inx}.$$ To this you can add a solution of the homogeneous equation. This solution of the homogeneous equation may be periodic or not, and with arbitrary period depending on the coefficients of $L$.

It may happen (rarely) that some $n$ is a zero of the characteristic equation. Then solution of (1) has the form $c_n P(x)e^{ikx}$, which is not periodic, and there cannot be a periodic solution unless we take $c_n=0$.

As you differential operator is of finite order, we come to the following conclusion: if for some $n$, $a_n\neq 0$ and this $n$ is not a root of the characteristic equation, then we have a solution with period (at most) $T$. If for all $n$ either $a_n=0$ of $n$ is a root of the characteristic equation, then there is no periodic solution (a resonance case).

For example $s^{\prime\prime}=1$ has no periodic solution, though the right hand side is periodic. But this is because $n=0$ is the only root of the characteristic equation.

So I suppose that "Numerical phenomenon 2" can be explained as follows: some number $k/m$ happens to be a root of the characteristic equation, and other roots are not resonant with the right hand side. This adds to the solution a harmonic of the form $\exp(ikx/m)$ of period $2\pi m$. But in this case, the periodic solution is not unique, and there is always some with period $T$.