Simulating Block Codes
Question: I am interested in the Golay codes (23,12,7) and (24,12,8) and I would like to use APP decoding for these. I was wondering whether you would consider including in the library a general APP decoder for (small) linear block codes?
Response (March 3, 2006):The library already can handle APP decoding of block codes, as long as they are cyclic. This is because any rate (n,k) cyclic code can be thought of as a convolutional code generated by a rate=1 convolutional encoder and nk tail bits (for trellis termination). The g matrix used by the convolutional encoder and APP decoder is set to equal the coefficients of the code's generator polynomial, and for a cyclic block code the g matrix will only have a single row (for a rate 1/n convolutional encoder, it has n rows).
An few examples can be found in the ./cml/BlockcodeScenarios file (version 1.4.1 and above). Record one is a nonsystematic (23,12) Golay code, while record two is the same code in systematic form (acheived by setting sim_param(record).nsc_flag1 = 0). Note that since the (23,12) Golay code can use a generator matrix of g(X) = 1 + X^2 + X^4 + X^5 + X^6 + X^10 + X^11, the corresponding g vector is sim_param(record).g1 = [1 0 1 0 1 1 1 0 0 0 1 1]. Also note that the framesize must be set to equal k, ie. sim_param(record).framesize = 12.
Another example is found in records three and four, which is an expurgated (15,10) Hamming code generated by g(X) = (1+X)(1+X+X^4) = 1 + X^2 + X^4+X^5. The g vector is sim_param(record).g1 = [1 0 1 0 1 1] and the framesize is sim_param(record).framesize = 10. Incidentally, this is the code used by Bluetooth for its DM (data mediumrate) packets, though it is incorrectly called a “shortened” Hamming code. Record three is the code in nonsystematic form, while record four is in systematic form (in the Bluetooth standard, it is systematic).
Simulation results down to a BER of about 10^4 can be found in the most recent package. You can plot the results by cd'ing to the root ./cml directory and typing: CmlStartup; CmlPlot( 'BlockcodeScenarios', 1:4 );
To verify correctness, you can compare against the union bound on ML decoding. For the first code, type (or cut and paste) the following: close all [sim_param, sim_state] = CmlPlot( 'BlockcodeScenarios', 1 ); close([2:4]) figure(1) n = 23; k=12; rate=k/n; % distance spectrum d = [7 8 11 12 15 16 23]; a = [253 506 1288 1288 506 253 1]; b = [924 2112 7392 8064 3960 2112 12]; EbNo = 10.^(sim_param.SNR/10); p= Q( sqrt( 2*rate*sim_param.SNR ) ); Pc_soft = zeros( size( EbNo ) ); Pb_soft = zeros( size( EbNo ) ); for i=1:length(d) Pc_soft = Pc_soft + a(i)*Q( sqrt( 2*rate*d(i)*EbNo ) ); Pb_soft = Pb_soft + b(i)/k*Q( sqrt( 2*rate*d(i)*EbNo ) ); end hold on; semilogy( sim_param.SNR, Pb_soft, ':k' ); legend( 'simulation', 'theory' );
