## C fixed-point BCJR

Here is some C code for the BCJR decoder used in the UMTS turbo code. This uses fixed point LLRs, which are particularly suited for practical implementations in DSPs, for example.

Copyright © 2008 Robert G. Maunder. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

June 17th, 2009 at 3:45 pm

I have drawn some diagrams to explain how this BCJR works. You can view them at…

http://users.ecs.soton.ac.uk/rm/wp-content/scan0001.jpg

http://users.ecs.soton.ac.uk/rm/wp-content/scan0002.jpg

http://users.ecs.soton.ac.uk/rm/wp-content/scan0003.jpg

http://users.ecs.soton.ac.uk/rm/wp-content/scan0004.jpg

Rob.

July 13th, 2012 at 9:31 pm

Hi Rob,

Thanks for your nice program. I have a quick question regarding to jac function: jac (A, B) = max (A,B)

Actually, an exact approximation of jac is

jac(A,B) = max (A,B) + log(1+exp(-|A-B|)

Then it can be extended to more variables A,B,C (assuming B is max)

jac(A,B,C) = max(A,B,C) + log(1+ exp(A-B) + exp(C-B))

I notice that your function is convenient for programming. However, do you know how much gain we can get if we use the exact approximation one?

Many thanks,

Thuy

July 16th, 2012 at 6:55 pm

Hi Thuy,

We found that using the exact Jacobian logarithm gives about 0.5 dB of gain in Rayleigh fading channels. You can see our findings in this paper…

http://eprints.soton.ac.uk/271820/

Take care, Rob.

July 23rd, 2012 at 11:15 pm

Your paper is very helpful.

Many thanks Rob.

Best Regards,

Thuy

February 26th, 2013 at 1:38 am

Hi Rob,

I was studying your bcjr.c code and I could not figure out the reason for defining “transitions_valid” and “states_valid” parameters here. It looks like that you are only calculating the gammas corresponding to the beginning state =1, whereas in the MATLAB code, gammas are calculated for all the possible transitions in the trellis.

Also, alphas and betas are not quite the same as in the MATLAB code.

Could you please explain these?

Thanks,

Elnaz

February 27th, 2013 at 6:34 pm

Hi Elnaz,

In my Matlab code, I use values of -inf for the alphas of some states at the left hand end of the trellis - this is because we know that these states are not the starting states. During the forward recursion, these values of -inf propagate into the trellis and eliminate all transitions and states that cannot be reached from the correct starting state. The advantage of this approach is that it is elegant and can be programmed easily.

However, in my C code, there is no way to represent a value of -inf. So instead, I have to predetermine which transitions and states cannot be reached from the correct starting state. Then I eliminate these transitions and states from the trellis. This method requires more programming and is not as elegant as the Matlab approach, but it maintains the correct operation. An alternative approach is to use values of -100 instead of -inf in the C code. This is elegant, but can give a small amount of error during the algorithm - this is rare in practice however.

The reason why the alphas and betas are not identical to the ones in Matlab is because the C code is using only integers in its calculations. The Matlab code uses floating point numbers. So the Matlab code is more accurate, but the C code runs quicker and requires less memory.

Take care, Rob.

April 9th, 2013 at 5:27 pm

Hi Rob,

I’m trying to make my turbo equalizer run much faster. It includes a turbo decoder (BCJR decoders) and a BCJR equalizer.

The decoder and equalizers are in C and I use mex-file in MATLAB to call them in my script. However, my simulations take a LONG time since my receiver is iterative and I call these function a lot.

Do you have any suggestions as to how can I make the BCJR routine run much faster?

Thanks,

Elnaz

April 11th, 2013 at 3:41 pm

Hi Elnaz,

Using a fixed-point BCJR decoder like the one I have provided on this page would run much faster than using a floating-point BCJR decoder. This is the simplest way to speed the algorithm up…

Take care, Rob.

April 11th, 2013 at 4:18 pm

Hi Rob,

Yes; Correct. But in terms of accuracy…; I don’t know it might not be that harmful.

One question: in my floating point implementation I use -10000 instead of -inf.

Then I was thinking in calculating jac, this line will never be satisfied:

if(A == -10000 && B == -10000)

Because values in A and B get close to -10000 but not exaclty -10000 for example I get -9999 instead of -10000. In MATLAB though inf remains inf. Is this problematic? Should I change the condition statement to an interval? Or I am mistaking somewhere?

I see a bit of divergence in my final results comparing to the MATLAB implementation even though both are floating point and all.

Thanks,

Elnaz

April 15th, 2013 at 7:50 pm

Hi Elnaz,

If you replace all instances of inf with some large number, then infinite values will never occur and this part of the Matlab code will never be used. So you can delete it if you like, or leave it if you prefer - it should make no difference…

Take care, Rob.

April 18th, 2013 at 3:26 pm

Hi Rob,

What about BCJR equalizer? Does that part make any difference in equalizer performance? I get different results when replacing MATLAB code with C for the equalizer?

Thanks,

Elnaz

April 18th, 2013 at 4:31 pm

Hi Elnaz,

I can’t think of any reason why the situation would be any different for a BCJR equalizer…

Take care, Rob.

December 3rd, 2013 at 3:38 pm

Dear sir,

Could you explain why we obtain the formula of gammas ?

thank you very much

December 4th, 2013 at 5:25 pm

Hi Yuan,

The gammas are obtained according to equations 2.14 and 2.15 of…

http://users.ecs.soton.ac.uk/rm/wp-content/liang_li_nine_month_report.pdf

These equations allocate a higher score to a transition if the corresponding bit value agrees with the a priori LLRs.

Take care, Rob.

January 16th, 2014 at 11:33 pm

Dear Rob,

Do you have matlab code that implements a BCJR equalizer?

Thank you

January 18th, 2014 at 1:26 am

Hello Ghassan,

I’m afraid that I don’t have any Matlab code for a BCJR equalizer. However, you can see some discussion about how to build one at…

http://users.ecs.soton.ac.uk/rm/resources/matlabexit/#comment-2033

http://users.ecs.soton.ac.uk/rm/resources/matlabexit/#comment-6286

http://users.ecs.soton.ac.uk/rm/resources/matlabexit/#comment-8916

http://users.ecs.soton.ac.uk/rm/resources/matlabturbo/#comment-12975

http://users.ecs.soton.ac.uk/rm/resources/matlabturbo/#comment-38016

Take care, Rob.