Hi all, I want to implement soft decision viterbi decoder in FPGA. I have already implemented hard-decision decoding and the design works fine in xilinx FPGA. We have implemented "high bit clear circuit" for path metrics normalization to reduce the area. Now, i want to implement soft-decision decoding an I need to change the BMU and ACS modules in my code. One thing that worries me is the normalization technique that can be used for soft-decision viterbi. since the calculation of euclidean distance will result in negative numbers many times, i can't use "high bit clear circuit" that i have used for hard-decision. So what normalization technique or methodology, I can use for implementing ACS block in soft-decision viterbi. Thanks all!
Soft-decision viterbi implementation
Started by ●October 27, 2009
Reply by ●October 27, 20092009-10-27
On Oct 27, 2:33=A0am, "san_jack" <sri...@kphsonline.com> wrote:> Hi all, > I want to implement soft decision viterbi decoder in FPGA. I have already > implemented hard-decision decoding and the design works fine in xilinx > FPGA. We have implemented "high bit clear circuit" for path metrics > normalization to reduce the area. > > Now, i want to implement soft-decision decoding an I need to change the > BMU and ACS modules in my code. > > One thing that worries me is the normalization technique that can be used > for soft-decision viterbi. since the calculation of euclidean distance wi=ll> result in negative numbers many times, i can't use "high bit clear circui=t"> that i have used for hard-decision. So what normalization technique or > methodology, I can use for implementing ACS block in soft-decision > viterbi. > > Thanks all!I don't know of any trick that lends itself specifically to FPGA implementation, but you can normalize your metrics at each step by subtracting the smallest cost from each of the survivor paths, so after each iteration the minimum-cost path will have a cost of zero. This then limits the maximum magnitude of the costs somewhat so you can use fewer bits to represent them. On another note, where is it that you're coming up with negative numbers for Euclidean distances? Distance should always be nonnegative. Jason
Reply by ●October 27, 20092009-10-27
On 10/27/2009 8:35 AM, Jason wrote:> On Oct 27, 2:33 am, "san_jack"<sri...@kphsonline.com> wrote: >> Hi all, >> I want to implement soft decision viterbi decoder in FPGA. I have already >> implemented hard-decision decoding and the design works fine in xilinx >> FPGA. We have implemented "high bit clear circuit" for path metrics >> normalization to reduce the area. >> >> Now, i want to implement soft-decision decoding an I need to change the >> BMU and ACS modules in my code. >> >> One thing that worries me is the normalization technique that can be used >> for soft-decision viterbi. since the calculation of euclidean distance will >> result in negative numbers many times, i can't use "high bit clear circuit" >> that i have used for hard-decision. So what normalization technique or >> methodology, I can use for implementing ACS block in soft-decision >> viterbi. >> >> Thanks all! > > I don't know of any trick that lends itself specifically to FPGA > implementation, but you can normalize your metrics at each step by > subtracting the smallest cost from each of the survivor paths, so > after each iteration the minimum-cost path will have a cost of zero. > This then limits the maximum magnitude of the costs somewhat so you > can use fewer bits to represent them.Another method, that Qualcomm used to use (and may still for all I know), was to look for overflow on any of the metric accumulators and "renormalize" (aka, shift right) all of the accumulators on detection of overflow of any of them. I don't recall whether this was done on the branch metrics or state metrics or both. Another trick that was enabled by that was to use the frequency of "renormalization" events to detect code lock.> On another note, where is it that you're coming up with negative > numbers for Euclidean distances? Distance should always be > nonnegative. > > JasonDetails, details. -- Eric Jacobsen Minister of Algorithms Abineau Communications http://www.abineau.com
Reply by ●October 28, 20092009-10-28
Well, If i am not wrong, ( x02-2xx0)+( y02-2yy0) is the forumla for calculating the euclidean distance. Let x be the first received bit in the pair, y – the second, x0 and y0 – the “ideal” values. I calculated for some values and it results in negative number. Assume my received bits received 000,111 which are 3-bit soft coded values, so my branch metrics will be 0,-49,49,98 ( for 1/2, constraint length=3 viterbi). And detecting the overflow and subtracting value for normalization consumes same resource as without normalization in FPGA.
Reply by ●October 28, 20092009-10-28
san_jack wrote:> Well, If i am not wrong, ( x02-2xx0)+( y02-2yy0) is the forumla for > calculating the euclidean distance. Let x be the first received bit in the > pair, y – the second, x0 and y0 – the “ideal” values. I calculated > for some values and it results in negative number.The Euclidean distance from (x1, y1) to (x2, y2) is sqrt(x1 - x2)^2 + (y1 - y2)^2) ... Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 28, 20092009-10-28
Jerry Avins wrote:> san_jack wrote: >> Well, If i am not wrong, ( x02-2xx0)+( y02-2yy0) is the forumla for >> calculating the euclidean distance. Let x be the first received bit in >> the >> pair, y – the second, x0 and y0 – the “ideal” values. I calculated >> for some values and it results in negative number. > > The Euclidean distance from (x1, y1) to (x2, y2) is > sqrt(x1 - x2)^2 + (y1 - y2)^2) > ...That's sqrt( (x1-x2)^2 + (y1-y2)^2 ). Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 29, 20092009-10-29
Hi all, I came to know about a formula which does the calculation simple and here it is. BM00 = x+y BM01 = x+(255-y) BM10 = (255-x)+y BM11 = (255-x)+(255-y) Here we use 8 bit soft-coded data, so we use 255 (2 to the power 8)-1.>Jerry Avins wrote: >> san_jack wrote: >>> Well, If i am not wrong, ( x02-2xx0)+( y02-2yy0) is the forumla for >>> calculating the euclidean distance. Let x be the first received bit in>>> the >>> pair, y – the second, x0 and y0 – the “ideal” values. Icalculated>>> for some values and it results in negative number. >> >> The Euclidean distance from (x1, y1) to (x2, y2) is >> sqrt(x1 - x2)^2 + (y1 - y2)^2) >> ... > >That's sqrt( (x1-x2)^2 + (y1-y2)^2 ). > >Jerry >-- >Engineering is the art of making what you want from things you can get. >¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ >
Reply by ●October 29, 20092009-10-29
san_jack wrote:> Hi all, I came to know about a formula which does the calculation simple > and here it is. > BM00 = x+y > BM01 = x+(255-y) > BM10 = (255-x)+y > BM11 = (255-x)+(255-y) > > Here we use 8 bit soft-coded data, so we use 255 (2 to the power 8)-1.What does the formula calculate? Surely not Euclidean distance! Jerry -- Engineering is the art of making what you want from things you can get.
Reply by ●October 30, 20092009-10-30
Yeah, I feel the same. But this calculation is being used in soft-viterbi decoding by some-one and i found this in the net. But i am not sure whether this is the correct approach>san_jack wrote: >> Hi all, I came to know about a formula which does the calculationsimple>> and here it is. >> BM00 = x+y >> BM01 = x+(255-y) >> BM10 = (255-x)+y >> BM11 = (255-x)+(255-y) >> >> Here we use 8 bit soft-coded data, so we use 255 (2 to the power 8)-1.> >What does the formula calculate? Surely not Euclidean distance! > >Jerry >-- >Engineering is the art of making what you want from things you can get. >
