|
| From: | Bob McGwier |
| Subject: | Re: [Discuss-gnuradio] Re: gnuradio trellis |
| Date: | Thu, 28 Sep 2006 12:57:59 -0400 |
| User-agent: | Mozilla Thunderbird 1.0.8-1.4.1 (X11/20060420) |
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 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.
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 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: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 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 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 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. 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 one-dimensional 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_______________________________________________ Discuss-gnuradio mailing list address@hidden http://lists.gnu.org/mailman/listinfo/discuss-gnuradio
-- Robert W. McGwier, Ph.D. Center for Communications Research 805 Bunn Drive Princeton, NJ 08540 (609)-924-4600 (sig required by employer)
| [Prev in Thread] | Current Thread | [Next in Thread] |