Forums

Soft-decision viterbi implementation

Started by san_jack October 27, 2009
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!



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
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. > > Jason
Details, details. -- Eric Jacobsen Minister of Algorithms Abineau Communications http://www.abineau.com
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 &ndash; the second, x0 and y0 &ndash; the &ldquo;ideal&rdquo; 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.

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 &ndash; the second, x0 and y0 &ndash; the &ldquo;ideal&rdquo; 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. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
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 &ndash; the second, x0 and y0 &ndash; the &ldquo;ideal&rdquo; 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. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
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 &ndash; the second, x0 and y0 &ndash; the &ldquo;ideal&rdquo; 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. >&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr; >
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.
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 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. >