[Discuss-gnuradio] Re: gnuradio trellis
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 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, Toby ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org http://lists.gnu.org/mailman/listinfo/discuss-gnuradio
Re: [Discuss-gnuradio] Re: gnuradio trellis
Achilleas Anastasopoulos wrote: 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 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 am indeed. 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. This is great. I did not know you had checked in the siso code in gr_trellis. I am now more anxious to go study it more carefully. I am glad I commented. 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 Thanks for your rapid response! I think we might find it useful to have such a suboptimal version as a variant. I find it quite useful in many problems where the complexity is an issue and the performance of the suboptimal implementation is completely adequate. Bob -- Robert W. McGwier, Ph.D. Center for Communications Research 805 Bunn Drive Princeton, NJ 08540 (609)-924-4600 (sig required by employer) ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org http://lists.gnu.org/mailman/listinfo/discuss-gnuradio
Re: [Discuss-gnuradio] Re: gnuradio trellis
From your reply I think you are referring to problem 1B. I am indeed. This is great. I did not know you had checked in the siso code in gr_trellis. I am now more anxious to go study it more carefully. I am glad I commented. As a side note, this algorithm is the basis of all turbo-like receivers that have appeared in the last 10 years. The idea is that when you have concatenated systems (eg, CC + interleaver + ISI) you want the inner decoder to provide NOT ONLY one sequence estimate, but reliability information about each of the symbols, so that the outer decoder can use them as soft input information. The trellis_siso block provides the optimal such solution, ie, the most informative such symbol reliability Pr(x_k| y_1^N) (the aposteriori probability about a specific input symbol based on the entire observation). The interesting thing is that this computation has complexity linear in the sequence length and in the number of states, and approximately twice that of Viterbi. See the example test_turbo_equalization.py in gnuradio-examples/python/channel-coding to see how this is used and the performance advantage it provides over one shot decoding. Achilleas PS: I am still working on the documentation of this part of gr_trellis. ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org http://lists.gnu.org/mailman/listinfo/discuss-gnuradio
[Discuss-gnuradio] Re: gnuradio trellis
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 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, Toby ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org http://lists.gnu.org/mailman/listinfo/discuss-gnuradio
[Discuss-gnuradio] Re: gnuradio trellis
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 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, Toby ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org http://lists.gnu.org/mailman/listinfo/discuss-gnuradio
