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.

16 Responses to “C fixed-point BCJR”

  1. Rob Says:

    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.

  2. Thuy Nguyen Says:

    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

  3. Rob Says:

    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.

  4. Thuy Nguyen Says:

    Your paper is very helpful.

    Many thanks Rob.

    Best Regards,

    Thuy

  5. Elnaz Says:

    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

  6. Rob Says:

    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.

  7. Elnaz Says:

    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

  8. Rob Says:

    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.

  9. Elnaz Says:

    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

  10. Rob Says:

    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.

  11. Elnaz Says:

    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

  12. Rob Says:

    Hi Elnaz,

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

    Take care, Rob.

  13. Juan Says:

    Dear sir,

    Could you explain why we obtain the formula of gammas ?

    thank you very much

  14. Rob Says:

    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.

  15. Ghassan Says:

    Dear Rob,

    Do you have matlab code that implements a BCJR equalizer?

    Thank you

  16. Rob Says:

    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.

Leave a Reply

Security Code: