My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Reply
 
LinkBack Thread Tools Display Modes
June 8th, 2018, 02:43 PM   #1
Newbie
 
Joined: Jul 2016
From: Ames, IA

Posts: 3
Thanks: 0

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)$.
kkonstantinidis is offline  
 
Reply

  My Math Forum > Math Forums > Math

Tags
based, decoding, division, euclidean, twostage



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Apply the Euclidean division evinda Abstract Algebra 2 June 7th, 2014 01:55 PM
Need help with Decoding Math watch fmt2bx New Users 3 March 6th, 2014 05:30 AM
Should the two-stage or one-stage construction be selected? enchanteuse Economics 1 March 4th, 2010 07:14 AM
DECODING LETTERS Nazz Algebra 4 October 28th, 2009 02:40 AM





Copyright © 2018 My Math Forum. All rights reserved.