Today I have created a SVN branch of the trunk at https://sourceforge.net/p/dvb-t2-csp/code/19/tree/branches/octave/.
There is no zip file or tarball at the moment, you will have to check it out from SVN. See the Open Discussion at the CSP for more details.
You will also need to download a LDPC package from http://sourceforge.net/projects/dvbldpc/. (At the moment there is only one.)
If anybody successfully runs the DVB-T2 CSP in Octave, I would like to know!
Sunday, July 21, 2013
Wednesday, July 17, 2013
DVB LDPC Project releases first GNU Octave Package
I have referred here previously to the ISCML package. I have isolated the LDPC encoder and decoder code and made it into a GNU Octave package.
At the moment I have one alternative LDPC package, but in that case I have a problem, because there is no copyright notice on the code, thus it is problematic to release it under any open source license without first tracing the original authors and getting their permission.
To make it easy for testers of the DVB-T2 Common Simulation Platform to test different LDPC code in GNU Octave, I have decided to create a project on Sourceforge, to make available different packages which will all be compatible with my modifications to the CSP. The project is called DVB LDPC, click here.
So far I release the one package (dvbldpc-iscml-0.0.1.tar.gz) in this project. Although it was only tested in Cygwin, I believe it should be possible to get it running on any Unix-like system where Octave is running. You may have to manually compile the mex files.
At the moment I have one alternative LDPC package, but in that case I have a problem, because there is no copyright notice on the code, thus it is problematic to release it under any open source license without first tracing the original authors and getting their permission.
To make it easy for testers of the DVB-T2 Common Simulation Platform to test different LDPC code in GNU Octave, I have decided to create a project on Sourceforge, to make available different packages which will all be compatible with my modifications to the CSP. The project is called DVB LDPC, click here.
So far I release the one package (dvbldpc-iscml-0.0.1.tar.gz) in this project. Although it was only tested in Cygwin, I believe it should be possible to get it running on any Unix-like system where Octave is running. You may have to manually compile the mex files.
Saturday, July 13, 2013
DVB-T2 LDPC Encoding Explained!
Well, I can't really explain LDPC encoding fully, but I have been looking at section 6.1.2 and the tables in Appendix A of the document ETSI EN 302 775 for a long time (maybe years), without understanding anything.
Now I have written Matlab/GNU Octave code to demonstrate the algorithm. I have tested it for the normal FEC block size (64800) and only for code rate = 2/3. It is a lot slower than other encoders I found, but gives the same answers. Whereas other encoders does one encoding in the blink of an eye, this demo code takes about 1 minute on my laptop.
I hope somebody finds this useful. I think it should be useful for at least two purposes:
Now I have written Matlab/GNU Octave code to demonstrate the algorithm. I have tested it for the normal FEC block size (64800) and only for code rate = 2/3. It is a lot slower than other encoders I found, but gives the same answers. Whereas other encoders does one encoding in the blink of an eye, this demo code takes about 1 minute on my laptop.
| % This is supposed to be ran
interactively by copying and pasting. % NOTE! % You need the function t2_std_dvbt2_bl_ldpc from the % DVB T2 Common Simulation Platform. Best is maybe to copy it % into your working directory. In this function, find ct1 and ct2 % for code rate 2/3(SONY matrix). Copy and paste them into Octave or Matlab. % Then copy and paste he code below: % % Assemble ct1 and ct2 into one matrix ck, padding ct2 with zeros ck=zeros(size(ct1,1)+size(ct2,1), max([size(ct1,2) size(ct2,2)])); ck(1:size(ct1,1),1:size(ct1,2)) = ct1; ck(size(ct1,1)+1:size(ck,1), 1:size(ct2,2)) = ct2; % Set the LDPC parameters Nldpc=64800; CR=2/3; Kldpc = CR*Nldpc; np=Nldpc-Kldpc; % Create an information block %i=[0 1 0 1 0 1 0 1 0 1 ones(1,Kldpc-20) 0 1 0 1 0 1 0 1 0 1] ; i=randint(1,Kldpc,2); % Initialize the parity bits p=zeros(1,np); Qldpc = 60; tic; for ii=0:size(i,2)-1 ckr = idivide(ii, 360)+1; m360 = mod(ii, 360); % Some debug you can uncomment %fprintf(1, 'ckr = %5d m360 = %d\n', ckr, m360); % More debug you can enable/change to see some of the accumulation addresses % if ii>355 && ii<365 % mod(nonzeros(ck(ckr,:))'+m360*60,np)+1 % end p(mod(nonzeros(ck(ckr,:))'+m360*60,np)+1) = mod(p(mod(nonzeros(ck(ckr,:))'+m360*60,np)+1) + i(ii+1), 2); end for pp=2:np p(pp) = mod(p(pp)+p(pp-1), 2); end toc; % Verification agains Matlab code, if you have Matlab % I tested this with alternative code in Octave H = t2_std_dvbt2_bl_ldpc(CR, Nldpc, '1.3.1'); enc = fec.ldpcenc(H); cw = encode1(enc, i); ptest = cw(Kldpc+1:Nldpc); nnz(p) nnz(ptest) nnz(p-ptest) |
I hope somebody finds this useful. I think it should be useful for at least two purposes:
- Educational.
- Verifying other LDPC encoders.
Friday, June 14, 2013
Linking C Object to a Mex Executable in GNU Octave
When starting to port the DVB-T2 Common Simulation Platform (CSP from Matlab to Octave, I also started learning about Matlab and Octave. In the CSP, I saw there were about 3 pieces of code written in C, and I learned that in Matlab the executables are called Mex (Matlab Executable) files.
GNU Octave provides the same functionality. You cannot take the compiled Mex files from Matlab and use them with Octave. A utility call 'mkoctfile' is provided with Octave. It is actually based on GCC.
So far I have not been able to compile a mex file using a Windows Installer version of Octave. I have been using Octave in Cygwin, so it is easy to run the mkoctfile command line tool.
e.g.
mkoctfile --mex myfunc.c
In the CSP, the few mex programs consisted of one C program each. Here I found one important difference between Matlab and Octave. In the beginning of a mex program, you will always find:
#include <mex.h>
and mostly, also
#include <matrix.h>
This causes a program in Octave, because mex.h already includes matrix.h.
you can either comment or delete the inclusion of matrix.h, or change it to:
#ifndef HAVE_OCTAVE
#include <matrix.h>
#endif
Yesterday, looking for more LDPC code for Matlab/Octave, I found a package called ISCML at http://code.google.com/p/iscml. I downloaded the file cml112.zip and found it consist of a large number of C programs.
At the moment I am only interested in the LDPC code, so I found InitState_mx.c and Iterate_mx.c in /module/chan_code/ldpc/decoder/src/mexsrc. First, I fixed the matrix.h problem as described above. Next, when I tried to compile it, I found it also includes ldpc-util.h and math-supp.h in a deeper directory called lib. So, standing in the above directory, we can add -Ilib to the command.
Compiling still failed, this time I realised some symbols were not found during the linking phase. In the lib directory are two more C files, so we can cd into lib and compile them to objects:
mkoctfile -c ldpc-util.c
mkoctfile -c math_supp.c
(Every time you get a of errors, you have to fix the matrix.h problem of course.)
Now cd back to the original directory and compile the two C files:
mkoctfile -c InitState_mx.c -Ilib
mkoctfile -c Iterate_mx.c -Ilib
Now, you link each of the two objects in this directory with the two objects in the lib directory:
mkoctfile --mex Iterate_mx.o lib/ldpc-util.o lib/math-supp.o
mkoctfile --mex InitState_mx.o lib/ldpc-util.o lib/math-supp.o
Now I have two mex files, and have to find out if I can use them!
GNU Octave provides the same functionality. You cannot take the compiled Mex files from Matlab and use them with Octave. A utility call 'mkoctfile' is provided with Octave. It is actually based on GCC.
So far I have not been able to compile a mex file using a Windows Installer version of Octave. I have been using Octave in Cygwin, so it is easy to run the mkoctfile command line tool.
e.g.
mkoctfile --mex myfunc.c
In the CSP, the few mex programs consisted of one C program each. Here I found one important difference between Matlab and Octave. In the beginning of a mex program, you will always find:
#include <mex.h>
and mostly, also
#include <matrix.h>
This causes a program in Octave, because mex.h already includes matrix.h.
you can either comment or delete the inclusion of matrix.h, or change it to:
#ifndef HAVE_OCTAVE
#include <matrix.h>
#endif
Yesterday, looking for more LDPC code for Matlab/Octave, I found a package called ISCML at http://code.google.com/p/iscml. I downloaded the file cml112.zip and found it consist of a large number of C programs.
At the moment I am only interested in the LDPC code, so I found InitState_mx.c and Iterate_mx.c in /module/chan_code/ldpc/decoder/src/mexsrc. First, I fixed the matrix.h problem as described above. Next, when I tried to compile it, I found it also includes ldpc-util.h and math-supp.h in a deeper directory called lib. So, standing in the above directory, we can add -Ilib to the command.
Compiling still failed, this time I realised some symbols were not found during the linking phase. In the lib directory are two more C files, so we can cd into lib and compile them to objects:
mkoctfile -c ldpc-util.c
mkoctfile -c math_supp.c
(Every time you get a of errors, you have to fix the matrix.h problem of course.)
Now cd back to the original directory and compile the two C files:
mkoctfile -c InitState_mx.c -Ilib
mkoctfile -c Iterate_mx.c -Ilib
Now, you link each of the two objects in this directory with the two objects in the lib directory:
mkoctfile --mex Iterate_mx.o lib/ldpc-util.o lib/math-supp.o
mkoctfile --mex InitState_mx.o lib/ldpc-util.o lib/math-supp.o
Now I have two mex files, and have to find out if I can use them!
Tuesday, June 4, 2013
Some DVB-T2 LDPC Generator Matrices
Here is a short tutorial on LDPC parity check matrices as used in DVB. I do not profess to know everything, I am giving you what I know.
If you look in the DVB-T2 specification, ETSI EN 302 775, you will find some information about this in Annex A and Annex B, which just says "Addresses of parity bit accumulators for Nldpc = 64800 and 16200. I don't know exactly what is meant here by addresses and accumulators, but have read of "repeat accumulate code", which look as if they are the specific kind of LDPC codes used in DVB.
In DVB-T2, two sizes of FEC blocks are used: 64800 bits, a.k.a. "normal" FEC blocks, and 16200 bits, a.k.a. "short" FEC blocks.
The size of a parity check matrix is expressed as mxn, where m is the number of rows, and n is the code length size. Note that m is the number of rows and n the number of columns.
Now if you have the DVB-T2 Common Simulation Platform code, you can easily generate any of the parity check matrices in Matlab or GNU Octave. Unzip the file somewhere, start Matlab or Octave and cd to DVB-T2-CSP-03-02-02/model/std/std_dvbt2std. (You may need to use \ instead of /)
Type 'dir' and you should see the file t2_std_dvbt2_bl_ldpc.m. Now use the function in this file generate a matrix:
H = t2_std_dvbt2_bl_ldpc(1/2, 64800, '1.2.1');
It is somewhat important to add the semicolon, otherwise H will be typed out, taking some time.
Note that the matrix generated is a sparse matrix. Type
nnz(H) / ( size(H,1) * size(H,2) ) * 100
and get:
ans = 0.010802
Only 0.01 % of the matrix entries are 1's, the rest are all zeros! Only the 1's are saved in memory Matlab or Octave, otherwise it might not have been possible.
To view the matrix you have generated, type
spy(H)
and see:
Note that Octave is not very good with the aspect ratio. Notice the right hand part of the octave where there is just a diagonal running from top left to bottom right. This part has the same width and height. I as able to resize it vertically to make it look square.
Before I explain more, let us generate the following one:
H = t2_std_dvbt2_bl_ldpc(2/3, 64800, '1.2.1');
Note, 2/3 is the Code Rate, meaning two thirds of the block length are useful bits, the rest are redundant forward error correction (FEC) bits. Type
spy(H)
What do you notice? The part looking almost solid is 3/4 of the whole width. Whenever seeing a DVB LDPC matrix, you can almost tell from it what the Code Rate is.
In this case, the width of the solid part is 48600, thus the width of the right hand side is 64800 - 48600 = 16200, which is also the height of the matrix.
This means, that 48600 bits of real information is encoded, 16200 parity check bits are added to for a "Code Word" of 64800 bits, which is also called an FEC block.
Try one more example:
H = t2_std_dvbt2_bl_ldpc(5/6, 64800, '1.2.1');
Again:
5/6 is the Code Rate
64800 is the Block Length
1.2.1 is the DVB T2 version. If you read the code of the function, you will see the version number only counts in about one special case.
Type
spy(H)
If you look in the DVB-T2 specification, ETSI EN 302 775, you will find some information about this in Annex A and Annex B, which just says "Addresses of parity bit accumulators for Nldpc = 64800 and 16200. I don't know exactly what is meant here by addresses and accumulators, but have read of "repeat accumulate code", which look as if they are the specific kind of LDPC codes used in DVB.
In DVB-T2, two sizes of FEC blocks are used: 64800 bits, a.k.a. "normal" FEC blocks, and 16200 bits, a.k.a. "short" FEC blocks.
The size of a parity check matrix is expressed as mxn, where m is the number of rows, and n is the code length size. Note that m is the number of rows and n the number of columns.
Now if you have the DVB-T2 Common Simulation Platform code, you can easily generate any of the parity check matrices in Matlab or GNU Octave. Unzip the file somewhere, start Matlab or Octave and cd to DVB-T2-CSP-03-02-02/model/std/std_dvbt2std. (You may need to use \ instead of /)
Type 'dir' and you should see the file t2_std_dvbt2_bl_ldpc.m. Now use the function in this file generate a matrix:
H = t2_std_dvbt2_bl_ldpc(1/2, 64800, '1.2.1');
It is somewhat important to add the semicolon, otherwise H will be typed out, taking some time.
Note that the matrix generated is a sparse matrix. Type
nnz(H) / ( size(H,1) * size(H,2) ) * 100
and get:
ans = 0.010802
Only 0.01 % of the matrix entries are 1's, the rest are all zeros! Only the 1's are saved in memory Matlab or Octave, otherwise it might not have been possible.
To view the matrix you have generated, type
spy(H)
and see:
Note that Octave is not very good with the aspect ratio. Notice the right hand part of the octave where there is just a diagonal running from top left to bottom right. This part has the same width and height. I as able to resize it vertically to make it look square.
Before I explain more, let us generate the following one:
H = t2_std_dvbt2_bl_ldpc(2/3, 64800, '1.2.1');
Note, 2/3 is the Code Rate, meaning two thirds of the block length are useful bits, the rest are redundant forward error correction (FEC) bits. Type
spy(H)
What do you notice? The part looking almost solid is 3/4 of the whole width. Whenever seeing a DVB LDPC matrix, you can almost tell from it what the Code Rate is.
In this case, the width of the solid part is 48600, thus the width of the right hand side is 64800 - 48600 = 16200, which is also the height of the matrix.
This means, that 48600 bits of real information is encoded, 16200 parity check bits are added to for a "Code Word" of 64800 bits, which is also called an FEC block.
Try one more example:
H = t2_std_dvbt2_bl_ldpc(5/6, 64800, '1.2.1');
Again:
5/6 is the Code Rate
64800 is the Block Length
1.2.1 is the DVB T2 version. If you read the code of the function, you will see the version number only counts in about one special case.
Type
spy(H)
You can of course, type
size(H)
and get
10800 64800
Let us have a closer look at the right hand bottom corner, by typing:
full(H(10790:10800, 64790:64800))
and we get
1 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1
1 1 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1
Notice there is not just a single diagonal as it appears in the spy graph. In this right hand square, there are no 1's above the diagonal, but some 1's below it. It is known as a "lower triangle" matrix. In Matlab/Octave, you can use the 'tril' function to test is a matrix is lower triangle.
I hope this helps!
Monday, June 3, 2013
DVB-T2 CSP - Time to celebrate!
I was so busy trying to get the Common Simulation Platform running in GNU Octave that I simply did not get time to post here!
Tonight I was able for the first time to run a simulation without crashing! See also
https://sourceforge.net/projects/dvb-t2-csp/forums/forum/1667464/topic/8400197
What took me a very long time was finding code to do the LDPC encoding and decoding. At the moment I have something, but I'm not sure if it is working 100% correct. I also have to check that I don't infringe on any copyright by modifying code and using it in the project. So please bear with me, It may still take some time to a release of a version for Octave.
I think I promised to show some graphics of the LDPC encoding matrices. I actually at some point started making screen shots, but did not get to posting it here, due to lack of time and it seems it does not work to past pictures in this editor. I promise I will post it some time. I am very interested in showing some aspects of DVB-T2 graphically with Octave, and sharing it here.
Tonight I was able for the first time to run a simulation without crashing! See also
https://sourceforge.net/projects/dvb-t2-csp/forums/forum/1667464/topic/8400197
What took me a very long time was finding code to do the LDPC encoding and decoding. At the moment I have something, but I'm not sure if it is working 100% correct. I also have to check that I don't infringe on any copyright by modifying code and using it in the project. So please bear with me, It may still take some time to a release of a version for Octave.
I think I promised to show some graphics of the LDPC encoding matrices. I actually at some point started making screen shots, but did not get to posting it here, due to lack of time and it seems it does not work to past pictures in this editor. I promise I will post it some time. I am very interested in showing some aspects of DVB-T2 graphically with Octave, and sharing it here.
Thursday, May 16, 2013
First Patch for DVB-T2 CSP on GNU Octave!
I have referred to the Common Simulation Platform in my previous post. I am still trying very hard to get it running in GNU Octave.
So far I have fixed the code to cater for a number of differences between Matlab and Octave. There is however a big problem with LDPC encoding/decoding, for which Matlab has functions, but Octave does not. If you have any idea how to do this encoding and decoding, in particular with repeat-accumulate codes as used in DVB-S2 and DVB-T2, you help would be highly appreciated.
I have found C code by Radford M. Neal that is looking good, at http://www.cs.utoronto.ca/~radford/ldpc.software.html. It does not seem to do the tepeat-accumulate codes, but still might be worthwhile using as learning tools.
At the moment I have bypassed the LDPC encoding in the transmitter part of the simulation, and hope to do the same for the decoding in the receiver part. I hope this will enable me to still use the CSP to learn a lot about the framing structure, and just view LDPC as two black boxes.
My patch can be found here.
So far I have fixed the code to cater for a number of differences between Matlab and Octave. There is however a big problem with LDPC encoding/decoding, for which Matlab has functions, but Octave does not. If you have any idea how to do this encoding and decoding, in particular with repeat-accumulate codes as used in DVB-S2 and DVB-T2, you help would be highly appreciated.
I have found C code by Radford M. Neal that is looking good, at http://www.cs.utoronto.ca/~radford/ldpc.software.html. It does not seem to do the tepeat-accumulate codes, but still might be worthwhile using as learning tools.
At the moment I have bypassed the LDPC encoding in the transmitter part of the simulation, and hope to do the same for the decoding in the receiver part. I hope this will enable me to still use the CSP to learn a lot about the framing structure, and just view LDPC as two black boxes.
My patch can be found here.
Saturday, May 4, 2013
DVB-T2 Common Simulation Platform
This Matlab simulation model is an official project undertaken by DVB / DVB members. I think I noticed it soon after it was released (during 2011) as open source on Sourceforge (http://sourceforge.net/projects/dvb-t2-csp/), tried if briefly and found it did not work with GNU Octave.
A week or two ago I decided to give it another go. If you read the file GettingStartedWithCSP.txt, you will find in point 4 a basic command to run:
run('dvbt2bl_basic','work','stdout',{'DVBT2.STRICT=0'})
This is where I started and so far have fixed/worked around a number of problems. As the project consists of 262 Matlab files, it is difficult to say how many bugs remains before I will be finished, or if it will be possible. Yet, some part will be useable at least. I have tried an example where it extracts from a T2-MI file, and saw it printing out Superframe and Frame numbers. This morning I was playing with he function t2_std_dvbt2_bl and saw it returning LDPC encoding matrices - I will try to do a post on that.
At the moment I am having big problems in the file DVB-T2-CSP-03-02-02/model/tx/tx_dvbt2blicod/t2_tx_dvbt2blicod.m, mainly to do with LDPC-encoding. Firstly, the Matlab comm function fec.ldpcenc does not exist in Octave. It returns a struct, which I just tried to make up at the point where the function is called. Then the call to the function encode fails. It is very difficult to see what is going on there, because it seems that the structure is passed to the function in the place of multiple arguments - an ability that Octave does not seem to have. I have tried to figure out something to call encode in Octave with the individual arguments. Now it passes that call, and then crashes in the next statement!
I am planning to release all the changes I am making as a patch to the zip file offered by the Sourceforge project. It will be placed either as part of the existing Sourceforge project, or on a new project.
Please watch this space, and the Open Discussion Forum of the Sourceforge project. Any help will be appreciated. As they say, many hands make light work!
A week or two ago I decided to give it another go. If you read the file GettingStartedWithCSP.txt, you will find in point 4 a basic command to run:
run('dvbt2bl_basic','work','stdout',{'DVBT2.STRICT=0'})
This is where I started and so far have fixed/worked around a number of problems. As the project consists of 262 Matlab files, it is difficult to say how many bugs remains before I will be finished, or if it will be possible. Yet, some part will be useable at least. I have tried an example where it extracts from a T2-MI file, and saw it printing out Superframe and Frame numbers. This morning I was playing with he function t2_std_dvbt2_bl and saw it returning LDPC encoding matrices - I will try to do a post on that.
At the moment I am having big problems in the file DVB-T2-CSP-03-02-02/model/tx/tx_dvbt2blicod/t2_tx_dvbt2blicod.m, mainly to do with LDPC-encoding. Firstly, the Matlab comm function fec.ldpcenc does not exist in Octave. It returns a struct, which I just tried to make up at the point where the function is called. Then the call to the function encode fails. It is very difficult to see what is going on there, because it seems that the structure is passed to the function in the place of multiple arguments - an ability that Octave does not seem to have. I have tried to figure out something to call encode in Octave with the individual arguments. Now it passes that call, and then crashes in the next statement!
I am planning to release all the changes I am making as a patch to the zip file offered by the Sourceforge project. It will be placed either as part of the existing Sourceforge project, or on a new project.
Please watch this space, and the Open Discussion Forum of the Sourceforge project. Any help will be appreciated. As they say, many hands make light work!
Subscribe to:
Comments (Atom)