[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Discuss-gnuradio] Re: gnuradio trellis
Re: [Discuss-gnuradio] Re: gnuradio trellis
Thu, 28 Sep 2006 14:31:24 -0400
Mozilla Thunderbird 1.0.2 (Windows/20050317)
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 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
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?
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
the make_isi_lookup in fsm_utils currently only supports
modulations. Am I right in assuming the I will need to extend this
GMSK signal? Or am I missing something?
Thanks for adding this to Gnuradio, its a really useful (and
Discuss-gnuradio mailing list
[Discuss-gnuradio] Re: gnuradio trellis, Anastasopoulos Achilleas, 2006/09/28