My Math Forum

My Math Forum (http://mymathforum.com/math-forums.php)
-   Math (http://mymathforum.com/math/)
-   -   Two-stage decoding based on Euclidean division (http://mymathforum.com/math/344386-two-stage-decoding-based-euclidean-division.html)

kkonstantinidis June 8th, 2018 03:43 PM

Two-stage decoding based on Euclidean division
 
Define the following quantity:
$$X=abs^{2\ell}+ce+Fs^{\ell}$$
where
$$F=ae+cb$$
Assumptions:
  • $a,b,c,e$ are unknown integers
  • $s,\ell$ are known positive integers
  • $X$ is known

My goal is to find $F$. The general idea is simple. Since we know $X$, we first find the remainder of the division $X/s^{2l}$. That would be $ce+Fs^{\ell}$. Then from this quantity we subtract the remainder of the division $(ce+Fs^{\ell})/s^\ell$ which yields $Fs^{\ell}$. Then just divide by $s^\ell$.

Now, if all variables were positive integers under the constraint $F<s^\ell$ then I can understand why this works. The fact that some of them can be negative confuses me and brings me to the two conventions for the remainder of Euclidean division.

Consider the division $x/d$ (I will just consider only the case $d>0$).

Definition 1
$$x=qd+r$$
in which case the $0\leq r<d$, where the remainder $r$ is restricted to be nonnegative.

But depending on our convention the remainder can also be negative e.g. here. This brings us to

Definition 2
$$x=Qd+R$$
where for the remainder $R$, $\mathrm{sign}(R)=\mathrm{sign}(x)$ and $|R|<d$

By comparing the above definitions I think that the following hold:

- If $x>0$, then $R=r$ and $Q=q$
- If $x<0$, then $r=R+d$ and $Q=q+1$

Matlab has an implementation for both definitions. For my initial problem if I use Definition 1 the result for $F$ is wrong if $X<0$ (it differs from the correct one by $s^\ell$ which is expected) and correct if $X>0$. If I use Definition 2, the result for $F$ is correct if $X>0$ and for $X<0$ it's sometimes correct and sometimes wrong.

So my strategy is flawed but I am not sure what is wrong. Also, some assumptions need to hold a priori for the general case where some variables can be negative, to have a solution and I think that those should be $|a|,|b|,|c|,|e|,|F|<0.5(s^{\ell}-1)$.


All times are GMT -8. The time now is 08:23 PM.

Copyright © 2018 My Math Forum. All rights reserved.