On 11/29/2011 01:21 PM, dvsarwate wrote:
 > On Nov 29, 8:29 am, Randy Yates<ya...@digitalsignallabs.com>  wrote:
 >
 >> Branch Metrics:
 >>
 >> If the inputs are hard bits, then the 2^N branch metrics for a rate 1/
 >> N code are the 2^N Hamming distances between the N demodulated bits
 >> and the 2^N possible values for those N bits.
 >
 > Randy:
 >
 > I thought at each stage, the trellis for a rate-(1/N) code has
 > 2^{m} nodes where the code has constraint length m+1,
 > with each node having 2 outgoing branches connecting
 > to the next stage, and having two incoming branches from
 > nodes at the previous stage.  It is essentially a rolling out
 > of what used to be studied once upon a time as the state
 > transition diagram of a sequential machine.  The nodes
 > at each stage are labeled with the 2^n possible contents
 > of the transmitter shift register.  The two branches leaving
 > a node are labeled as 0/X and 1/Y where X and Y are
 > N-bit vectors -- the transmitted bits corresponding to
 > input data bits 0 and 1 respectively when the transmitter
 > shift register contents are the node label.  The branch
 > metrics for the branches are the Hamming distances
 > between X and Z, and between Y and Z, where Z is the
 > N-bit received vector corresponding to that particular
 > *data* bit.  The nice thing is that the Hamming distance
 > is additive (just as the log likelihood is for soft
 > decision decoding; the branch metrics are taken as the
 > log likelihood of the soft-decision vector Z for parameters
 > X and Y respectively.)
 >
 > In particular, there are only 2^{m+1} branches from the
 > n-th stage to the (n+1)-th stage, and so, for, say, a rate 1/5
 > code of constraint length 3, there are not 32 branches
 > to be labeled with the 32 possible 5-bit binary vectors.

Dilip,

Thank you for your gentle guidance. Your corrections on the number of
states and the trellis architecture are of course correct. I'm not
sure why I made such a gross error in this post. It's probably best to
just admit I made a mistake and move on.

However, I am still unclear regarding your explanation of the log
likelihood:

   The nice thing is that the Hamming distance is additive (just as the
   log likelihood is for soft decision decoding; the branch metrics are
   taken as the log likelihood of the soft-decision vector Z for
   parameters X and Y respectively.)

I certainly see that log(x * y) = v + w, and that if we actually had
metrics that were probabilities, working with their logs would allow
us to determine the optimal path through the trellis via addition.

What I don't understand is why the branch metrics are NECESSARILY log
likelihoods. To be fair, you said they are "taken" as the log
likelihod. Perhaps this is the very crux of the matter (for me).

In our case, the inputs are simply the values out of the (FSK)
demodulator - there is no log function applied to them - and the
metrics are simple Euclidean distance. So they aren't log likelihoods.

Has it been shown somewhere that such metrics are equivalent to log
likelihoods for the purposes of establishing the most likely path
through the trellis?

Further, our system engineers are calling the _inputs_ to the Viterbi
decoder "LLRs" - NOT the branch metrics. And LLRs are "log likelihood
RATIOS", not simply log likelihoods. So none of this makes sense to me.

I would appreciate any further insight you might have into this, and
hope you are willing to share it.

--Randy

On Nov 29, 8:29&#4294967295;am, Randy Yates <ya...@digitalsignallabs.com> wrote:

> Branch Metrics:
>
> If the inputs are hard bits, then the 2^N branch metrics for a rate 1/
> N code are the 2^N Hamming distances between the N demodulated bits
> and the 2^N possible values for those N bits.

Randy:

I thought at each stage, the trellis for a rate-(1/N) code has
2^{m} nodes where the code has constraint length m+1,
with each node having 2 outgoing branches connecting
to the next stage, and having two incoming branches from
nodes at the previous stage.  It is essentially a rolling out
of what used to be studied once upon a time as the state
transition diagram of a sequential machine.  The nodes
at each stage are labeled with the 2^n possible contents
of the transmitter shift register.  The two branches leaving
a node are labeled as 0/X and 1/Y where X and Y are
N-bit vectors -- the transmitted bits corresponding to
input data bits 0 and 1 respectively when the transmitter
shift register contents are the node label.  The branch
metrics for the branches are the Hamming distances
between X and Z, and between Y and Z, where Z is the
N-bit received vector corresponding to that particular
*data* bit.  The nice thing is that the Hamming distance
is additive (just as the log likelihood is for soft
decision decoding; the branch metrics are taken as the
log likelihood of the soft-decision vector Z for parameters
X and Y respectively.)

In particular, there are only 2^{m+1} branches from the
n-th stage to the (n+1)-th stage, and so, for, say, a rate 1/5
code of constraint length 3, there are not 32 branches
to be labeled with the 32 possible 5-bit binary vectors.


--Dilip Sarwate

Randy Yates wrote:

> Viterbi Input, Branch Metrics, and the TI VCU
> 
> What is the input to the (hard-output) Viterbi decoder, and how is a
> branch metric computed?

Viterbi decoder is a (sub optimal) path search algorithm in a graph.
What is the input and how the cost is computed depends on application.

> Here are what I think are the correct answers:

Nope.

> Inputs:
> 
> The inputs are either hard bits (i.e., x_n \in {-1, +1}) or soft bits
> (i.e., x_n \in [-1, +1]), depending on the Viterbi implementation.

> Branch Metrics:
> 
> If the inputs are hard bits, then the 2^N branch metrics for a rate 1/
> N code are the 2^N Hamming distances between the N demodulated bits
> and the 2^N possible values for those N bits.

Wrong.

In the binary case, there are 2^N branch metrics for the code with the 
memory of N. It has nothing to do with the rate of the code.

> If the inputs are soft bits, then the 2^N branch metrics for a rate 1
> / N code are the 2^N Euclidean distances
> 
>   d_m = \sqrt{\sum_{n = 0}{N - 1} (x_n - xideal_m_n)^2}.

Wrong.

For AWGN and mininum BER, optimim metrics is distance squared.


> Nowhere here are logarithms used. The problem I'm having is that some
> folks that I work with are calling the inputs LLRs, "Log-Likelihood
> Ratios," and I see no mention of LLRs in conjunction with plain,
> vanilla (i.e., non-soft-output) Viterbi decoders.

LLRs are the technical trick to simplify the computation of conditional 
probabilities (used with the optimal decoding algorithms). You can add 
logariphms instead of multiplying raw probabilities.

> Another quandary I'm having is regarding the VCU (Viterbi/Complex
> Unit) used in TI's Piccolo series of MCUs. It appears that this
> hardware computes N branch metrics instead of 2^N, one for each bit.

Huh?

> Can anyone reconcile this with the (supposedly correct) answer above
> that there are 2^N branch metrics?

Read the datasheet.

> Hints/suggestions/pointers/comments would be welcome.

Get a clue how Viterbi algorithm works?



Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Tue, 29 Nov 2011 07:29:16 -0600, Randy Yates
<yates@digitalsignallabs.com> wrote:

>Viterbi Input, Branch Metrics, and the TI VCU
>
>What is the input to the (hard-output) Viterbi decoder, and how is a
>branch metric computed?
>
>Here are what I think are the correct answers:
>
>Inputs:
>
>The inputs are either hard bits (i.e., x_n \in {-1, +1}) or soft bits
>(i.e., x_n \in [-1, +1]), depending on the Viterbi implementation.
>
>Branch Metrics:
>
>If the inputs are hard bits, then the 2^N branch metrics for a rate 1/
>N code are the 2^N Hamming distances between the N demodulated bits
>and the 2^N possible values for those N bits.
>
>If the inputs are soft bits, then the 2^N branch metrics for a rate 1
>/ N code are the 2^N Euclidean distances
>
>   d_m = \sqrt{\sum_{n = 0}{N - 1} (x_n - xideal_m_n)^2}.
>
>Nowhere here are logarithms used. The problem I'm having is that some
>folks that I work with are calling the inputs LLRs, "Log-Likelihood
>Ratios," and I see no mention of LLRs in conjunction with plain,
>vanilla (i.e., non-soft-output) Viterbi decoders.
>
>Another quandary I'm having is regarding the VCU (Viterbi/Complex
>Unit) used in TI's Piccolo series of MCUs. It appears that this
>hardware computes N branch metrics instead of 2^N, one for each bit.
>Can anyone reconcile this with the (supposedly correct) answer above
>that there are 2^N branch metrics?
>
>Hints/suggestions/pointers/comments would be welcome.
>
>--Randy

Google "Viterbi LLR" or something like that and you'll get a lot of
references.   Starting from scratch if one does the derivations of
what's going mathematically it is frequently done where the inputs to
a soft-decision decoder wind up being LLRs.   Since that's a popular
mathematical treatment (especially for things like Turbo Codes or
other iterative decoders) the soft inputs are often called LLRs.

But they don't have to be.   Lots of people just call them "soft
decision" inputs, which is arguably as common and not incorrect.  It's
another one of those cases where disparate terms and points of view
are talking about the exact same thing.   So I just use the "soft
decision" and "LLR" terms regarding decoder inputs interchangeably,
although if one wants to get picky LLRs are really a subset of "soft
decision" techniques.

And don't worry about implementing them differently, either.  ;)



Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

On 29 Nov, 14:29, Randy Yates <ya...@digitalsignallabs.com> wrote:

> Nowhere here are logarithms used. The problem I'm having is that some
> folks that I work with are calling the inputs LLRs, "Log-Likelihood
> Ratios," and I see no mention of LLRs in conjunction with plain,
> vanilla (i.e., non-soft-output) Viterbi decoders.

Log-likelihood ratios usually occur in detection problems.
The normal probability functions is expressed as

N(u,s) ~ G(u,s) exp( F(u,s) )

where u is the mean and s is the variance or standard deviation,
which is hard to anlyze analytically. Taking the logaritm
of the distribution gives

LN(u,s) ~ log( G(u,s) ) + F(u,s)

which might be easier to analyze, particularly since G(u,s)
oftend depend only on s. In detection problems one usually
are interested in detecting differences in means, in which
case the above simplifies to

LN(u,s) ~ constant + F(u,s).

If you now want to investigate if there is a difference
of the means of two different samples (i.e. if the
distance between them is non-vanishing), you can  do that
by analyzing the difference

D(x1,x2) = F(u1,s) - F(u2,s).

which is a tractable analytic problem, compared to working
directly with the distribution fundtions. Or maybe that last
one should be the ratio

d(x1,x2) = F(u1,s)/F(u2,s)

(I don't remember off the top of my head if LLR means
'log of a likelihood ratio' or 'ratio of log likelihoods').

Rune

Viterbi Input, Branch Metrics, and the TI VCU

What is the input to the (hard-output) Viterbi decoder, and how is a
branch metric computed?

Here are what I think are the correct answers:

Inputs:

The inputs are either hard bits (i.e., x_n \in {-1, +1}) or soft bits
(i.e., x_n \in [-1, +1]), depending on the Viterbi implementation.

Branch Metrics:

If the inputs are hard bits, then the 2^N branch metrics for a rate 1/
N code are the 2^N Hamming distances between the N demodulated bits
and the 2^N possible values for those N bits.

If the inputs are soft bits, then the 2^N branch metrics for a rate 1
/ N code are the 2^N Euclidean distances

   d_m = \sqrt{\sum_{n = 0}{N - 1} (x_n - xideal_m_n)^2}.

Nowhere here are logarithms used. The problem I'm having is that some
folks that I work with are calling the inputs LLRs, "Log-Likelihood
Ratios," and I see no mention of LLRs in conjunction with plain,
vanilla (i.e., non-soft-output) Viterbi decoders.

Another quandary I'm having is regarding the VCU (Viterbi/Complex
Unit) used in TI's Piccolo series of MCUs. It appears that this
hardware computes N branch metrics instead of 2^N, one for each bit.
Can anyone reconcile this with the (supposedly correct) answer above
that there are 2^N branch metrics?

Hints/suggestions/pointers/comments would be welcome.

--Randy