
From:  Achilleas Anastasopoulos 
Subject:  Re: [Discussgnuradio] Re: gnuradio trellis 
Date:  Thu, 28 Sep 2006 14:31:24 0400 
Useragent:  Mozilla Thunderbird 1.0.2 (Windows/20050317) 
Bob, Let's make sure we are talking about the same thing before we declare that we agree: Problem 1: KNOWN CHANNEL. 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 grtrellis; 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 grtrellis
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. Achilleas Bob McGwier wrote:
Achilleas: 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 noncausal 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 grtrellis (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. 188110A1 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(ij) O(j) = Sum(k) X(ik) 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 reestimation 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 cobwebs in my head from the last time I looked at this and then get it checked in.Bob Anastasopoulos Achilleas wrote:Toby, 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 grtrellis stuff will be useful to you if you do not want to do sequence detection, but some sort of suboptimal linear or decisionfeedback 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:Achilleas, 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, Toby Anastasopoulos Achilleas wrote:Oliver, You are right: Trellis implementation supports multidimensional 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 forone dimensional modulations. 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), and 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 Ndimensional components; maybe a python implementation of the GramSchmidt (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 multidimensional modulations. best, Achilleas On Wed, 27 Sep 2006, Toby Oliver wrote:Achilleas, 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 waslooking to try it out as an equalizer on some GMSK signals but it seems the make_isi_lookup in fsm_utils currently only supports onedimensional modulations. Am I right in assuming the I will need to extend this for aGMSK signal? Or am I missing something?Thanks for adding this to Gnuradio, its a really useful (and incrediblyflexible) addition. Kind Regards, Toby_______________________________________________ Discussgnuradio mailing list address@hidden http://lists.gnu.org/mailman/listinfo/discussgnuradio
[Prev in Thread]  Current Thread  [Next in Thread] 