Hi, I read a paper which says that the following formula: W_r=sgn(w_n)^T * update_n can be calculated by "simple XORs and adds to compute W_r from the sign of tap coefficients (w_n) and update information (update_n)" I assume that w_n is represented as 2's complement format (even for sign extension format I do not get the answer yet). How does XOR used in W_r computation? Could you explain it to me? Thanks in advance
Anyone can explain the XOR operation in a vector addition?
Started by ●June 12, 2014
Reply by ●June 12, 20142014-06-12
On Thu, 12 Jun 2014 07:56:57 -0700, fl wrote:> Hi, > > I read a paper which says that the following formula: > > > W_r=sgn(w_n)^T * update_n > > > can be calculated by "simple XORs and adds to compute W_r from the sign > of tap coefficients (w_n) and update information (update_n)" > > I assume that w_n is represented as 2's complement format (even for sign > extension format I do not get the answer yet). How does XOR used in W_r > computation? Could you explain it to me?If everything is in 2's compliment you can certainly get there from here using XORs, but without reading the whole paper I can't comment on what's on the author's mind. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●June 12, 20142014-06-12
On Thursday, June 12, 2014 10:56:57 AM UTC-4, fl wrote:> Hi, > > > > I read a paper which says that the following formula: > > > > > > W_r=sgn(w_n)^T * update_n > > > > > > can be calculated by "simple XORs and adds to compute W_r > > from the sign of tap coefficients (w_n) and update information (update_n)" > > > > I assume that w_n is represented as 2's complement format (even for sign extension format I do not get the answer yet). How does XOR used in W_r computation? Could you explain it to me? > > > > > > Thanks in advanceHere the space is limited and I do not find any close relevant content in that paper to my question. Only the following line may clearly show that it is for a hardware implementation point. Equation (D.4) can now be implemented in hardware very efficiently. Can you explain how XOR is used in the dot product of w_n and update_n? Thanks
Reply by ●June 12, 20142014-06-12
On Thu, 12 Jun 2014 09:29:57 -0700, fl wrote:> On Thursday, June 12, 2014 10:56:57 AM UTC-4, fl wrote: >> Hi, >> >> >> >> I read a paper which says that the following formula: >> >> >> >> >> >> W_r=sgn(w_n)^T * update_n >> >> >> >> >> >> can be calculated by "simple XORs and adds to compute W_r >> >> from the sign of tap coefficients (w_n) and update information >> (update_n)" >> >> >> >> I assume that w_n is represented as 2's complement format (even for >> sign extension format I do not get the answer yet). How does XOR used >> in W_r computation? Could you explain it to me? >> >> >> >> >> >> Thanks in advance > > Here the space is limited and I do not find any close relevant content > in that paper to my question. Only the following line may clearly show > that it is for a hardware implementation point. > > Equation (D.4) can now be implemented in hardware very efficiently. > > > Can you explain how XOR is used in the dot product of w_n and update_n? > ThanksWhy don't you send the author of the paper an email and ask just that question? Some authors are quite willing to clarify things they've written -- I know that I am, with my work. The worst that'll happen is they won't answer. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●June 12, 20142014-06-12
On 6/12/2014 12:29 PM, fl wrote:> On Thursday, June 12, 2014 10:56:57 AM UTC-4, fl wrote: >> Hi, >> >> I read a paper which says that the following formula: >> >> W_r=sgn(w_n)^T * update_n >> >> can be calculated by "simple XORs and adds to compute W_r >> >> from the sign of tap coefficients (w_n) and update information (update_n)" >> >> I assume that w_n is represented as 2's complement format (even for sign extension format I do not get the answer yet). How does XOR used in W_r computation? Could you explain it to me? > > Here the space is limited and I do not find any close relevant content in that paper to my question. Only the following line may clearly show that it is for a hardware implementation point. > > Equation (D.4) can now be implemented in hardware very efficiently. > > > Can you explain how XOR is used in the dot product of w_n and update_n? ThanksI really wish you guys would use a proper newsreader rather than Google Groups. The rest of us have to clean up your messes. Something doesn't sound right. XOR is the fundamental component of an add, not a multiply. The multiply uses an AND gate at the bit level. a x b = c is exactly the same as a AND b = c for 1 bit binary numbers. a + b = c is the same as a XOR b = c for calculating the single bit result (without the carry). They seem to be referring to the sign bit of w_n with the expression sgn(w_n)^T. If so, then the XOR operation would be appropriate to calculate this portion of the result. The multiply is just a conditional complement which is the XOR of each bit in update_n then adding 1 for a 2's complement number. So W_r = sgn(w_n)^T * update_n could be calculated by XORing w_n with itself T times and XORing that result with each bit in update_n and adding a 1. Is T a number? What is the range? This portion can be simplified as well. If T is even, (w_n)^T will always be zero, if w_n is zero (w_n)^T will always be zero. The only time (w_n)^T will be 1 is if w_n is 1 and T is odd which means the lsb is 1... so just an AND gate. This is getting simpler every time I look at it. -- Rick
Reply by ●June 12, 20142014-06-12
fl <rxjwg98@gmail.com> writes:> Hi, > > I read a paper which says that the following formula: > > > W_r=sgn(w_n)^T * update_n > > > can be calculated by "simple XORs and adds to compute W_r > from the sign of tap coefficients (w_n) and update information (update_n)" > > I assume that w_n is represented as 2's complement format (even for > sign extension format I do not get the answer yet). How does XOR used > in W_r computation? Could you explain it to me?Many times XOR is used for a GF2 add, but I don't really see how this is the case here. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
Reply by ●June 12, 20142014-06-12
On 6/12/2014 4:00 PM, Randy Yates wrote:> fl <rxjwg98@gmail.com> writes: > >> Hi, >> >> I read a paper which says that the following formula: >> >> >> W_r=sgn(w_n)^T * update_n >> >> >> can be calculated by "simple XORs and adds to compute W_r >> from the sign of tap coefficients (w_n) and update information (update_n)" >> >> I assume that w_n is represented as 2's complement format (even for >> sign extension format I do not get the answer yet). How does XOR used >> in W_r computation? Could you explain it to me? > > Many times XOR is used for a GF2 add, but I don't really see how this > is the case here.In this case it is a multiply, but of a 1 bit signed number... i.e. the sign bit. sgn(w_n) is the sign bit. Multiply it by itself T times. In the end it becomes the sign bit of w_n anded with the lsb of T. -- Rick
Reply by ●June 12, 20142014-06-12
On Thursday, June 12, 2014 10:56:57 AM UTC-4, fl wrote:> Hi, > > > > I read a paper which says that the following formula: > > > > > > W_r=sgn(w_n)^T * update_n > > > > > > can be calculated by "simple XORs and adds to compute W_r > > from the sign of tap coefficients (w_n) and update information (update_n)" > > > > I assume that w_n is represented as 2's complement format (even for sign extension format I do not get the answer yet). How does XOR used in W_r computation? Could you explain it to me? > > > > > > Thanks in advanceThanks a lot! Excuse me I did not say clearly on the formula. The "T" means transpose. It made you distraction. The cited passage are from a part of 9 years old Ph.D thesis of Stanford University. I cannot write to the author now. The algorithm was used for a simplified LMS in a Giga Hz serial link (Serdes). It should be some simple logic to get W_r. W_n and update_n have the same length. Thus, W_r is an inner product. I guess the sign operation outputs '1' or '-1'. Then those positive or negative update_n summing together, but I still cannot understand XOR function yet. Or, is there a simple method to combine the sign of w_n with update_n? Thanks, Could you shed more light for me?
Reply by ●June 12, 20142014-06-12
On 6/12/2014 4:44 PM, fl wrote:> On Thursday, June 12, 2014 10:56:57 AM UTC-4, fl wrote: >> Hi, >> >> I read a paper which says that the following formula: >> >> >> W_r=sgn(w_n)^T * update_n >> >> >> can be calculated by "simple XORs and adds to compute W_r >> >> from the sign of tap coefficients (w_n) and update information (update_n)" >> >> I assume that w_n is represented as 2's complement format (even for sign extension format I do not get the answer yet). How does XOR used in W_r computation? Could you explain it to me? >> >> >> Thanks in advance > > Thanks a lot! > Excuse me I did not say clearly on the formula. The "T" means transpose. It made you distraction.I'm still distracted... ;) It has been many years since I took abstract algebra in college. Can you explain what transpose means? If you were working with one bit numbers (1,-1) or (1,0) what would the operation look like?> The cited passage are from a part of 9 years old Ph.D thesis of Stanford University. I cannot write to the author now. The algorithm was used for a simplified LMS in a Giga Hz serial link (Serdes). It should be some simple logic to get W_r. W_n and update_n have the same length. Thus, W_r is an inner product. > I guess the sign operation outputs '1' or '-1'. Then those positive or negative update_n summing together, but I still cannot understand XOR function yet. Or, is there a simple method to combine the sign of w_n with update_n? > Thanks, > Could you shed more light for me?Whether the sign operation outputs 1,-1 or 0,1 depends on how you wish to look at it. Once I know what a transpose operator does I can tell you how to view it. -- Rick
Reply by ●June 12, 20142014-06-12
rickman <gnuarm@gmail.com> writes:> On 6/12/2014 4:44 PM, fl wrote: >> On Thursday, June 12, 2014 10:56:57 AM UTC-4, fl wrote: >>> Hi, >>> >>> I read a paper which says that the following formula: >>> >>> >>> W_r=sgn(w_n)^T * update_n >>> >>> >>> can be calculated by "simple XORs and adds to compute W_r >>> >>> from the sign of tap coefficients (w_n) and update information (update_n)" >>> >>> I assume that w_n is represented as 2's complement format (even for sign extension format I do not get the answer yet). How does XOR used in W_r computation? Could you explain it to me? >>> >>> >>> Thanks in advance >> >> Thanks a lot! >> Excuse me I did not say clearly on the formula. The "T" means transpose. It made you distraction. > > I'm still distracted... ;) It has been many years since I took > abstract algebra in college. Can you explain what transpose means?You transpose the rows and the columns. So the first row becomes the first column, the second row the second column, etc. If you have an NxM matrix A, then A^T is dimension MxN.> If you were working with one bit numbers (1,-1) or (1,0) what would > the operation look like?Here he's got two vectors of length Nx1, so sgn(w_n)^T * update_n is 1xN * Nx1 = 1x1, i.e., it's an "inner product" (as he already mentioned. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
