[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Discuss-gnuradio] Re: gnuradio trellis

From: Achilleas Anastasopoulos
Subject: Re: [Discuss-gnuradio] Re: gnuradio trellis
Date: Thu, 28 Sep 2006 14:31:24 -0400
User-agent: Mozilla Thunderbird 1.0.2 (Windows/20050317)


Let's make sure we are talking about the same thing before
we declare that we agree:

In this case everything is quite straightforward, and all related
problems have been solved 20 years ago.

A) The receiver that minimizes SEQUENCE error probability is
essentially a whitened matched filter followed by Viterbi.

B) The receiver that minimizes SYMBOL error probability is
a whitened matched filter followed by a MAP symbol detector;
it is a bit more complicted than Viterbi (requires a forward and backward recursion), but of similar nature
(see the "trellis_siso_f" block in gr-trellis; that's what is doing!).

ANY other algorithm (including EM) is indeed suboptimal.

Problem 2: UNKNOWN channel.
Here the situation is getting a bit more complicated as we
have a problem of joint DETECTION and ESTIMATION.
The optimal solution is exponentially complex in the sequence length, so
it is of no practical interest. Over the last 15 years there have been
several proposals in solving this problem.
I won't go into that at all.

Which problem are you referring to?

From your reply I think you are referring to problem 1B.
I think you are proposing a suboptimal version of symbol detection based on the EM algorithm. However, the optimal solution to this problem is known as well, as I mentioned before, and is implemented in gr-trellis
in the block "trellis_siso_f".
Thus the statement "I personally believe that maximum likelihood sequence estimation is suboptimal in comparison to a more completely Bayesian approaching built upon computationally feasible implementations of the EM algorithm" is wrong if it refers to problem 1A.
If it refers to problem 1B then it unclear why one would want to
implement the suboptimal EM if the optimal is known and available.
Of course complexity/performance tradeoff will determine the solution
to be implemeted in each practical scenario.


Bob McGwier wrote:

You and I essentially agree.

I personally believe that maximum likelihood sequence estimation is suboptimal in comparison to a more completely Bayesian approaching built upon computationally feasible implementations of the EM algorithm. Since we can and should take a non-causal approach to JOINT channel and symbol estimation for bauded signals (we are doing DSP), we should take the Bayesian approach to increase the probability of the observed signal by adapting to changing parameters of the channel as the EM algorithm is capable of doing. It has been some time since I looked at gr-trellis (not since the earliest of checkins). It does "Viterbi equalization" I take it from your description and follows the course laid out in Forney's seminal paper.

I did an EM algorithm based demodulator for Mil. Std. 188-110-A1 and published the results in a TAPR proceedings almost a decade ago. I was prevented from releasing the source code by my employer at that time after getting approval to give the talk and the promise it would be releasable. Times have changed and so have attitudes. I would be allowed to release and check in a version of this for our systems. I don't think the Mil. Std. demod would be of interest but the general technique would. I think it would be instructive for people to be able to compare the approaches taken. Possibly the single strongest component of the EM based channel mitigation and symbol estimation was derived from a newer formulation of the typical problem.

Sum(j)  Y(i-j) O(j)   =  Sum(k) X(i-k) C(k)

where the Y's are the signal samples and O are use to get a filtration applied to the observed signal. X's are the unobserved states in a Markov chain (the bauds) and C's are the filters applied to the Markov chain. Without the O's this could easily be done with Viterbi equalization or EM.

As in the Viterbi equalization, no attempt is made to invert the channel and turn "y's" into "x's". Conditional probabilities for the X's given the Y's are computed using the current set of the parameters O,C. The probability of the observations are then increased by re-estimation of the O's and C's given the conditional probabilities for the X's and this is done iteratively until you the programmer reach your "stopping criterion" whatever that might be.

In other words, guessing criterion for the X's that minimizes the differences in the left hand side and the right hand side in a mean square sense are derived. After guess criterion are derived, this is used to update the O,C parameters. Under the assumptions made, you are guaranteed that the probability of the observations will increase with each iteration of guess/reestimate.

People who do equalizers don't realize they are essentially "dividing by zero" or "dividing by a small quantity" in a channel with a notch in its response and even when there is not a notch but a degradation. An equalizer does noise enhancement by lifting the response to match expectation. UGLY.

In the MM clock estimator/symbol recovery stuff that Matt and I checked in last January, we did just such an ugly decision feedback equalizer using LMS as the approach. The primary benefit that accrues is speed of execution, not optimality of the results.

Shao and Nikias wrote a paper that is a computational feasible approximation to the EM algorithm. They have no "O's" and they did only real signals. I have done a replacement with complex X's and with the O's. I probably should dust it off a bit and rework the cob-webs in my head from the last time I looked at this and then get it checked in.


Anastasopoulos Achilleas wrote:


for me the term "equalization" is equivalent to
"sequence detection in ISI channels".
If by "equalization" you mean "linear" or "decision feedback"
equalization this is another story.

I am not sure how the gr-trellis stuff will be useful to you if
you do not want to do sequence detection, but some sort of
suboptimal linear or decision-feedback equalization, unless you
want to use it only for the GMSK detection part...

If you tell me more specifically what system you are
working on (modulation type, channel, receiver processing)
I can give more specific comments.

On Thu, 28 Sep 2006, Toby Oliver wrote:


Okay. I am primarily interested in the equalization for the time being,
but I can see it would seem to make a lot of sense to create the
sequence detection as well.

In terms of making the isi lookup table for multidimensional
modulations, whats the best way to go about it? Is there any published
literature on this that I could base it on?

Kind Regards,

Anastasopoulos Achilleas wrote:


You are right:
Trellis implementation supports multi-dimensional constellations etc
(through the metric calculation block abstraction, etc), however,
in the examples and the supporting fsm_utils.py files
I have not included support for GMSK, and the automatic
generation of lookup tables for ISI channels is for-one dimensional
I think the extension should be straightforward and I'll be glad
to help you in this.

May I suggest you separate the task into two subproblems for reasons
of usability by others:

1) GMSK sequence detection in AWGN channels
(which is a modulation with memory and in theory requires Viterbi
even in the absense of ISI),
2) GMSK equalization (ie, GMSK + ISI channel + noise -> Viterbi)

For 1) a modification of test_tcm.py is required and hopefully
an "automated" way to project any given GMSK modulation to its
N-dimensional components; maybe a python implementation of
the Gram-Schmidt (QR decomposition) algorithm...

For 2) a modification of the test_viterbi_equalization.py or
test_viterbi_equalization1.py is required together with
generalizing the code in fsm_utils.py to generate the lookup table
for multi-dimensional modulations.


On Wed, 27 Sep 2006, Toby Oliver wrote:


I hope you don't mind me emailing you, but I have just been having a
look at your gnuradio trellis code which is very cool. In fact I was
looking to try it out as an equalizer on some GMSK signals but it seems the make_isi_lookup in fsm_utils currently only supports one-dimensional modulations. Am I right in assuming the I will need to extend this for a
GMSK signal? Or am I missing something?

Thanks for adding this to Gnuradio, its a really useful (and incredibly
flexible) addition.

Kind Regards,

Discuss-gnuradio mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]