Re: [Discuss-gnuradio] Custom GRC block not accepting derived class objects
On Feb 23, 2015, at 9:30 AM, Tom Rondeau t...@trondeau.commailto:t...@trondeau.com wrote: On Mon, Feb 23, 2015 at 4:06 AM, Perez, Tracie R tracie.pe...@mavs.uta.edumailto:tracie.pe...@mavs.uta.edu wrote: I'm hoping for suggestions from the GRC and swig savvy folks on the list. I am trying to add LDPC functionality to gr-fec [1]. I made a GRC block for a decoder class. The decoder class constructor accepts a base class called fec_mtrx. In GRC, I am trying to give the decoder block an input of an object of a class derived from fec_mtrx, called ldpc_R_U_mtrx. The issue is that swig is giving an error that it expects the base class as the argument. From the swig documentation, this type of inheritance and type checking seems to be fully supported and handled by swig. Is there something else I need to consider in either the block's cheetah template for the make call, or the swig files? The organization of the classes is like: class FEC_API ldpc_R_U_mtrx : public fec_mtrx {}; class FEC_API ldpc_bit_flip_decoder_impl : public ldpc_bit_flip_decoder { public: ldpc_bit_flip_decoder_impl(fec_mtrx *mtrx_obj, unsigned int max_iter=100); } And then in variable_ldpc_bit_flip_decoder.xml I've got: self.$(id) = $(id) = fec.ldpc_bit_flip_decoder.make($matrix_object, $max_iterations) In my flowgraph, I provide the decoder block an input of a ldpc_R_U_mtrx variable, and swig throws: TypeError: in method 'ldpc_bit_flip_decoder_make', argument 1 of type 'gr::fec::code::fec_mtrx * So to me, it seems like swig is not recognizing that the ldpc_R_U_mtrx class derives from fec_mtrx. Not sure what to do about that except to try and “un-inherit the classes and overload the decoder constructor... Thanks for any tips, tracie [1] github.com/tracierenea/gnuradio/tree/ldpc_modshttp://github.com/tracierenea/gnuradio/tree/ldpc_mods Hey Tracie, Unfortunately, I don't have a good, easy answer for you. It does seem like this should work fine. I'm trying to think of examples where we've done this before. The closest that I know of is with the constellation objects and something like the constellation_receiver that takes in just the base class. All of the function calls required are implemented in that base class, but overloaded by the child class. It also has a function .base() that returns the pointer to the child object as the base class so we can pass it through. Figuring out how to get swig to work with the child class would probably be the better solution, but maybe you can use the constellation class model to get things going. Tom Thanks very much Tom for the feedback. I spent many more hours trying to get swig to work directly with the child class and could never figure out how, or find any clues about this issue in the swig documentation. So as a workaround, I’ve added a get_base_ptr() function to the child classes as you described that the constellation objects do. I updated the xml file for the decoder to call the make function as: self.$(id) = $(id) = fec.ldpc_bit_flip_decoder.make(${matrix_object}.get_base_ptr(), $max_iterations) Now everything is swig’ing and working great. Thanks again, tracie ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
[Discuss-gnuradio] Custom GRC block not accepting derived class objects
I'm hoping for suggestions from the GRC and swig savvy folks on the list. I am trying to add LDPC functionality to gr-fec [1]. I made a GRC block for a decoder class. The decoder class constructor accepts a base class called fec_mtrx. In GRC, I am trying to give the decoder block an input of an object of a class derived from fec_mtrx, called ldpc_R_U_mtrx. The issue is that swig is giving an error that it expects the base class as the argument. From the swig documentation, this type of inheritance and type checking seems to be fully supported and handled by swig. Is there something else I need to consider in either the block's cheetah template for the make call, or the swig files? The organization of the classes is like: class FEC_API ldpc_R_U_mtrx : public fec_mtrx {}; class FEC_API ldpc_bit_flip_decoder_impl : public ldpc_bit_flip_decoder { public: ldpc_bit_flip_decoder_impl(fec_mtrx *mtrx_obj, unsigned int max_iter=100); } And then in variable_ldpc_bit_flip_decoder.xml I've got: self.$(id) = $(id) = fec.ldpc_bit_flip_decoder.make($matrix_object, $max_iterations) In my flowgraph, I provide the decoder block an input of a ldpc_R_U_mtrx variable, and swig throws: TypeError: in method 'ldpc_bit_flip_decoder_make', argument 1 of type 'gr::fec::code::fec_mtrx * So to me, it seems like swig is not recognizing that the ldpc_R_U_mtrx class derives from fec_mtrx. Not sure what to do about that except to try and “un-inherit the classes and overload the decoder constructor... Thanks for any tips, tracie [1] github.com/tracierenea/gnuradio/tree/ldpc_mods ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
Re: [Discuss-gnuradio] gr-fec LDPC comments / questions.
Hi Sylvain, Thanks for looking at this code. I really appreciate the feedback. Comments/questions inline below. ~ tracie perez On Jul 25, 2014, at 1:25 PM, Sylvain Munaut wrote: Hi, I've been looking at the LDPC code and I have a few comments / questions : 1) Memory management seems to be lacking. I see only 3 calls to gsl_matrix_free but much more matrices being allocated and create by operations. Am I missing something here or is the code leaking tons of memory at each encode/decode ? For the ldpc_par_chk_matrix class: There are 6 other submatrices, but they're submatrix views of the larger parity check matrix H. Since they're only views of the matrix already stored in memory, freeing the memory for H should be all that's necessary, if I'm understanding the GSL functions correctly. Then there are only 2 other matrices for which to free memory, so 3 calls total. To be clear - the idea is that a parity check matrix object is created, and then remains in memory through each encode/decode. For the encoder/decoder, you're totally right. I didn't free any of the temporary matrices. I just updated those classes with gsl_matrix_free calls. 2) Encoder efficiency : AFAIU, the method implemented in ldpc_R_U_encoder_impl is meant to be efficient for real-time encoding. But the efficiency is derived mainly because it makes a lot of the operation work on sparse matrix and those can be efficiently multiplied. This is not exploited here at all. The gsl matrix multiplication is just the plain old classic algorithm for dense matrix and so the R_U method is probably slower than just using a multiplication by the generator matrix. Yea, you are totally correct here too. The way to exploit it is to use back substitution in the steps to calculate the codeword, rather than regular matrix multiplication calls. I need to write a routine to do this, since the GSL linear algebra functions don't support GF(2), as far as I can tell. This should be straightforward; I'm working on it now. 3) Format of the H matrix and support for degenerate/ideal case : I've been trying to trace the BER curve for the codes used in the GMR-1 satcom standard. I have the H matrix in numpy and saved it to alist using the method in the python code in the gr-fec repo. The H matrix is of the form : [ P' | I ] already, so it's already in lower triangular form (actually even more than this, since it's the identity matrix on the right side). So I'd assume I could use this matrix with the code in the repo and use gap=0, but this doesn't work. Digging a bit more in the code, I see that the code decomposes it as follows : / T | A | B \/ | ---+---+--- | \ E | C | D / But in the paper I'm looking at ( http://www.ldpc-codes.com/papers/encoding.pdf ) the T E matrices are on the right side, which would match much better of course and honestly makes more sense to me since the reulting codeword often has the systematic bits first and then the parity bits. I didn't reference that paper. My GSoC mentor last summer, Jens, pointed me to their textbook Modern Coding Theory. In the book's method, the matrix is of the form you see in my code (TAB/ECD). Yes, to respond to your follow-up email - this is why I assumed the parity part would come first when I wrote the decoder. My LDPC knowledge is still pretty limited to just these few algorithms. I agree that we should be consistent with whatever the community is used to, or somehow make it configurable. If y'all think it's best to change it to ABT/CDE form, I can change it, but I won't be able to get back to this for a couple of weeks. I don't really understand why it's like that in the code. Also, should the code already work with the degenerate case where g=0 (which I think should be pretty common if you provide a check matrix that's already in the nice [ P' | I ] form. So now I'm sure you can see why a matrix in the form [P | I ] would not work with this TAB/ECD decomposition. If this class had a more unique name, it would probably be more clear that this parity check matrix class is specifically for use with the R_U encoder. So, I've renamed it from ldpc_par_chk_mtrx to ldpc_R_U_mtrx. I think it makes sense to have a separate FECAPI encoder variable for using a generator matrix in the standard form [ I | P ] (or given a parity check matrix in the form [P' | I ]. That has been on my to-do list to write. For a given parity check matrix that is full rank, or can be brought to full rank, it can be ran through the algorithm to bring it into TAB/ECD, or ABT/CDE form. I could add that functionality to the python script intended to be executed as preprocessing step. Cheers, Sylvain ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
Re: [Discuss-gnuradio] LDPC GSoC Project Status
Hello all once again, I'd like to thank everyone who has given me helpful feedback since my last status. I really appreciate the thoughtful comments. I solved the issue regarding getting my matrices to work with the encoder algorithm. For the parity check matrices, I'm constructing regular LDPC parity check matrices per a simple algorithm described in Gallager's original 1963 thesis on this topic. However, per design, the matrices are never full rank, so I then process them to be so. Then, the matrices are ran through a pre-processing algorithm to set them up for efficient, low complexity encoding per a process described by Richardon and Urbanke. I call the resulting matrix an encoding-ready parity check matrix, and it takes days to generate each one (bigger = more days). I would like to build up to matrices for n=5000 because I believe this is the ballpark for codeword lengths used in industry. As my scripts create these matrices, I am pushing them to a library of sorts on my github repo. Of course the idea is that the time is invested in creating them once, and then they can be used as needed after that. There are regular parity check matrices already available on the web by Dr. MacKay, but they are not full rank, so they won't work with my encoder. By the time I reduce them to be full rank, the information rate that they offer is unacceptably low. So, this is why I have gone the route of generating my own matrices that are compatible with Richardson and Urbanke's encoding algorithm. Next, I ran into an issue with my decoder failing for large size codewords. That tied me up for a few weeks. After much troubleshooting, I discovered that the issue stemmed from rounding errors from numpy doing mod 2 operations. I won't go into to much detail since I will be porting this algorithm out of python to C++ anyway. After manually correcting this rounding issue, my hard decision bit-flip decoding algorithm performed really well in the prototype python tests that I did. To simulate errors, I manually introduced bit flips and checked that the decoder could detect and correct them. I have tested codewords up to 2400 bits in length, and the algorithm can correct a few errors in 1 or 2 iterations, which is actually much faster than I anticipated. I will be testing larger codewords as I construct larger and larger parity check matrices. Now I am at the point where I am converting my python code into C++. After thinking about how best to do this, we (Jens, Nick and I) agreed that it made sense to fork Nick McCarthy's fecapi repo. So, I have done this, and I will create classes that inherit from and use the FEC API classes that he has already written. This will hopefully allow me to eventually use the BER curve generator to do final tests of my implementation. Because there are so many matrix operations, I am using the GNU Scientific Library (GSL) in my C++ code. I thought that this would be a reasonable approach since GSL is a required dependency for gr-wavelet, and, if I am not mistaken, a user would get the GSL as part of the standard install via pybombs. I do think that there will be many opportunities to increase efficiency by using VOLK, but I don't think that will fall within the scope of this summer's project. I will be flagging potential VOLK code replacements with something like FIXME - consider replacing this with VOLK library functions. As always, I welcome any feedback that you have! Thanks, Tracie Perez On Jul 21, 2013, at 6:36 PM, Perez, Tracie R wrote: Hi all, I'd just like to share a status of how my LDPC implementation project is going. When the summer started, Manu and I made a list of the LDPC-related algorithms for encoding, decoding, and parity check matrix construction that we had found in our literature review. We then divided them up such that there would be no overlap in our efforts. The algorithms that I put on my list were: 1. Regular and irregular parity check matrix construction functions 2. Generating a code that is optimized for PSK 3. Constructing quasi-cyclic codes which are especially efficient for encoding 4. Performing encoding as described by Richardson Urbanke in Appendix A of 'Modern Coding Theory' (manipulating the parity-check matrix into an approximate upper triangulation form which reduces complexity during the real-time encoding steps) 5. Bit-flip decoding, a hard decision algorithm 6. Min-sum algorithm for decoding So far, I've written prototype functions for these methods in python, using numpy: #1/regular, #4, and #5. Right now, I'm at the stage where I'm trying to link them all together and confirm that the processes perform as expected before moving on to converting them to C++. The challenge that I'm facing is that the parity check matrices being created by my function are not full rank, and so they don't work with the encoding algorithm. I have tried a method to manipulate
Re: [Discuss-gnuradio] Dev Call August 16th (Friday)
Martin, Will the dev call this Friday be at the usual time, 5pm UTC? Thanks, Tracie On Aug 5, 2013, at 3:14 AM, Martin Braun (CEL) wrote: Hi everyone, our next developer's call will be on Friday, August 16th. This is an *exception* from our third-Thursday rule, in the future, we will still be sticking to that. Also, we'll try and reduce the chaos in the hangouts, so we have exactly one of them (and only one live stream). I will join the hangout early (say, 5-10 minutes ahead of schedule). Thus, when you join the hangout and see I'm there, you know you're in the right spot[1]. Once the hangout is live, Phil or I will post the YouTube link on the list. This should make it really easy to follow the call for all of those who just want to listen in. MB [1] A common rule-of-thumb for partygoers in the Karlsruhe area :) -- Karlsruhe Institute of Technology (KIT) Communications Engineering Lab (CEL) Dipl.-Ing. Martin Braun Research Associate Kaiserstraße 12 Building 05.01 76131 Karlsruhe Phone: +49 721 608-43790 Fax: +49 721 608-46071 www.cel.kit.edu KIT -- University of the State of Baden-Württemberg and National Laboratory of the Helmholtz Association ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
[Discuss-gnuradio] LDPC GSoC Project Status
Hi all, I'd just like to share a status of how my LDPC implementation project is going. When the summer started, Manu and I made a list of the LDPC-related algorithms for encoding, decoding, and parity check matrix construction that we had found in our literature review. We then divided them up such that there would be no overlap in our efforts. The algorithms that I put on my list were: 1. Regular and irregular parity check matrix construction functions 2. Generating a code that is optimized for PSK 3. Constructing quasi-cyclic codes which are especially efficient for encoding 4. Performing encoding as described by Richardson Urbanke in Appendix A of 'Modern Coding Theory' (manipulating the parity-check matrix into an approximate upper triangulation form which reduces complexity during the real-time encoding steps) 5. Bit-flip decoding, a hard decision algorithm 6. Min-sum algorithm for decoding So far, I've written prototype functions for these methods in python, using numpy: #1/regular, #4, and #5. Right now, I'm at the stage where I'm trying to link them all together and confirm that the processes perform as expected before moving on to converting them to C++. The challenge that I'm facing is that the parity check matrices being created by my function are not full rank, and so they don't work with the encoding algorithm. I have tried a method to manipulate them into being full rank before encoding but it was not successful. This is my top priority right now - to be able to have the parity-check matrices that I am creating work with the encoding algorithm that I've written up. Then I'd like to finish testing the chain of processes before moving on to creating classes that inherit from those in the FEC API. My GitHub repo is here: https://github.com/tracierenea/GNU-Radio-GSoC2013 Any questions or comments, just let me know. Thanks, Tracie Perez ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
Re: [Discuss-gnuradio] [GSoC] It has begun
Hello all, one more introduction I am also a GSoC participant this summer. I'm a first year aerospace engineering graduate student at the University of Texas at Arlington. My area of research is satellite communication links, which is what lead me to GNU Radio. Manu and I both wrote proposals for LDPC implementations, but we are going to coordinate and progress such that we are working independently, not getting in each other's way, and not implementing duplicate work. My git repo will be here: https://github.com/tracierenea/GNU-Radio-GSoC2013 I'll be sending periodic status updates throughout the summer. I am very grateful for this opportunity and am looking forward to a productive summer. Tracie Perez On May 30, 2013, at 11:54 PM, Manu T S wrote: Hello Everyone, I'm Manu, a graduate student at Indian Institute of Technology, Bombay. I'm pursuing masters in Electrical Engineering specializing in Communication and Signal Processing. My proposal on LDPC codes has been accepted for GSoC. You can look into the proposalhttp://home.iitb.ac.in/%7Emanu.ts/proposal.pdf for more information. The codes will be hosted in github repohttps://github.com/manuts/ldpc On Fri, May 31, 2013 at 4:44 AM, Shashank Gaur shashankg...@ieee.orgmailto:shashankg...@ieee.org wrote: Hello Everyone, I am a graduate student from ECE Paris, France. I have been selected for GSoC 2013 for the project IEEE 802.11 a/g/n Rx and Wireshark Connectorhttp://www.google-melange.com/gsoc/proposal/review/google/gsoc2013/shashankgaur/1. I am much obliged and thankful to the community for this opportunity and hope to come up with some good results during this experience. This project aims to provide a utility for new users of GNU Radio to access Wireshark and analyze their algorithms using it. The aim is to develop a bridge between GNU Radio and Wireshark which would result into analysis of packets. I plan to do this using already developed OFDM based IEEE 802.11 a/g/n Receiver, thanks to Univ of Innsbruck people for that. Also libpcap, a packet capture library, will be used to develop socket between GNURadio and Wireshark. For detailed proposal please visit herehttp://shashankgaur.files.wordpress.com/2013/05/gsoc-gnuradio-proposal.pdf. For the development of the project, I am hosting it at Google Project hosting (herehttp://code.google.com/p/radioplus/). I will be setting it up completely in next few hours. For the moment some starting soft milestones are as following: Till this weekend: Fresh install of gnuradio and ofdm rx(univ of innsbruck). Revision of basic state of the art and intial setup phase. Next week (3rd-9th June): Deep study of OFDM code and preparation of first document on state of the art. Defining initial objective before real coding starts. Discussion with mentors and inputs on the initial goals. I would also start a blog which will sum up the development including major milestone screen-shots and videos, whatever may be possible. At the end, Once again I thank the community for this opportunity and my gratitude goes to all mentors and volunteers who has been working hard for GSoC. I would be much obliged to have guidance and feedback from the community during this development phase. Best Regards, Shashank Gaur On Tue, May 28, 2013 at 12:47 AM, Martin Braun (CEL) martin.br...@kit.edumailto:martin.br...@kit.edu wrote: Hi everyone, just a quick notice concerning GSoC: It has officially begun, and the students who were accepted have been announced. A full list can be found here: http://www.google-melange.com/gsoc/org/google/gsoc2013/gnuradio We had a huge number of proposals this year, and it was quite hard to pick 5 students. Without going into details, we sorted all proposals by our own grading system and waited until the number of slots was announced, then picked the first 5. There were certainly more than 5 fantastic proposals, and it's a bit sad that we couldn't take more people. I would like to thank everyone for applying. I also want to thank all mentors for volunteering and helping with the grading and selection of students. Special thanks goes out to Jens, who volunteered to mentor two students. This made it possible to simply pick the top 5 students from our list without having to find a backup mentor or arbitrarily changing our priority order. A little stat on the side: An incredibly high percentage of applications were for the LDPC codes. Why they are so much more interesting than all the other projects remains a mystery to me, but it seems we have some code afficionados here. Perhaps some of you are willing to put in some time to write some other FEC code? We only have 5 GSoC slots, but that doesn't mean you can't contribute :) Of course, that goes for all students. I do hope you are all genuinely interested in the GNU Radio project and we will see you around. So, the summer of code starts now! I certainly hope that we have 5 successful projects this