My Math Forum  

Go Back   My Math Forum > Math Forums > Math

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

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

Posts: 3
Thanks: 0

Two-stage decoding based on Euclidean division

Define the following quantity:
  • $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
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
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  

  My Math Forum > Math Forums > Math

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 02:55 PM
Need help with Decoding Math watch fmt2bx New Users 3 March 6th, 2014 06:30 AM
Should the two-stage or one-stage construction be selected? enchanteuse Economics 1 March 4th, 2010 08:14 AM
DECODING LETTERS Nazz Algebra 4 October 28th, 2009 03:40 AM

Copyright © 2019 My Math Forum. All rights reserved.