3
$\begingroup$

I'll try to translate certain problem about convolutional codes to more common language of ODE, hope my translation is correct, but welcome to criticize.

Consider two given functions periodic functions $(r_1(x), r_2(x))$ (with same period); two linear differential operators $ D_1(s(x)) = (\sum_i a_i s^{(i)}(x) )$, and similar $D_2$ with some other coefficients (both coefficients are (say) constant, may be I also need something like positive definite - not sure)

Optimization problem: Find $(s(x) )$, such that $|D_1(s) - r_1|^2 + |D_2(s) - r_2|^2 -> min.$ Where $|.|$ is say $L^2$ norm (over period of $r_i$).

Question 1 Is the problem well-defined over $R$ ? (I.e. unique solution ?) (For $D_i$ generic - i.e. their null-spaces do not intersect).

Question 2 Is it true that solution will be periodic function ?

Remark About question 1: I do not put boundary conditions, that might be some reason for non-uniqueness, but I have two operators, so if null-spaces of $D_i$ do not intersect, this avoids obvious problem which may arise from adding to s(x) any functions in the null-space for both operators.

Remark About question 2: A colleague of mine suggests that in similar situation of convolution codes it is "well-known" that solution might not be periodic (it is my translation of his words to ODE language it might not be correct).


In the convolutional codes are related to this setup as follows. Let us discretize $x$, so instead of $s(x)$ we will have $s(n)$ and $D_i$ will act as $s(n)-> \sum_k \tilde a_k x(n-k)$. Now let us restrict values of $x(n)$ only to +1, -1 and instead of sum consider the products $x(n)-> \sum_k x(n-k)^{a_k}$. That is what convolutional codes are doing.

We have "signal" (i.e. sequence of +1,-1) $s(k)$ : encoder maps it to a pair of functions $\tilde D_1 (s(k)), \tilde D_2(s(k))$ . Due to errors from propagation via noisy channel we get $\tilde r_1(k) = \tilde D_1 (s(k))+noise , r_2(k) = \tilde D_2(s(k))+ noise $. We want to reconstruct $s(k)$ from given $\tilde r_1, \tilde r_2$.

Tail-biting is some trick how to make everything periodic, let me omit details for the moment.

$\endgroup$
7
  • 1
    $\begingroup$ What is $L^2$ norm? Over a period of $r_1,r_2$? Over the whole real line? Do $r_1,r_2$ have the same period? Do your differential operators have constant coefficients? $\endgroup$ Dec 17, 2012 at 15:25
  • $\begingroup$ Alexandre, thank you for your questions, I clarified - $r_i$ have same period, L^2 over it, D_i - constant coefs. $\endgroup$ Dec 17, 2012 at 16:08
  • $\begingroup$ In the ODE setting, why don't we just go to the Fourier side and the answer will become evident to both of us? The additional restriction for the values in the discrete setting and the non-linearity of the operators (you raise the values to powers, right, so you just replace some positions with $+1$, keep the rest, and then take the sum?) makes it a very interesting problem to think of. I have no good idea at the moment but I'm fascinated enough to spend some time on this :). $\endgroup$
    – fedja
    Dec 17, 2012 at 16:39
  • $\begingroup$ Also, when you say "consider the products" and write $\sum$ after that, it is just a mistyped $\prod$, right? $\endgroup$
    – fedja
    Dec 17, 2012 at 17:18
  • $\begingroup$ @fedja yes it is misprint. Sorry $\endgroup$ Dec 17, 2012 at 18:11

1 Answer 1

1
$\begingroup$

I am not sure how Fedja is proposing to take a Fourier transform of a periodic function. But nevertheless, the answer to 1 in ODE setting seems to be positive. Let $T$ be the period, and $n$ the common order of the differential operators. Consider the space $H$ of pairs $(g,h)$ where $f$ and $g$ are in $L^2(0,T)$. The operator $f\mapsto (D_1f,D_2f)$ maps the appropriate Sobolev space into $H$, and the image is convex and closed. So there exists a unique closest point to $(r_1,r_2)$ in this image. Its preimage $f$ is uniquely defined, if the intersection of kernels of $D_1,D_2$ is trivial.

$\endgroup$
8
  • $\begingroup$ Why preimage is not uniquely defined? $\endgroup$ Dec 17, 2012 at 17:49
  • $\begingroup$ I corrected my answer. $\endgroup$ Dec 18, 2012 at 14:31
  • $\begingroup$ Thank you very much ! Do you have the ideas about second question ? I am playing with codes... something interesting happens it seems it can be non-periodic... $\endgroup$ Dec 18, 2012 at 14:39
  • $\begingroup$ If you remove all misprints in the second question, I will try to think on it. $\endgroup$ Dec 18, 2012 at 14:44
  • $\begingroup$ Tomorrow I hope to write details with numerical examples $\endgroup$ Dec 18, 2012 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.