3
$\begingroup$

I'm working to implement a k=7, r=1/2 convolutional code and Viterbi decoder for forward error correction. I want to operate in streaming mode, so that can pull data from the stream before the entire message is complete. I plan to have a 64 bit history, and to pull the oldest 16 bits, keeping 48 bits unresolved until the code completes.

[Edit] - I found one problem with the code (see below), but still not sure why I'm getting so many errors after fixing that issue. Any input on interpreting the output here would be helpful.

I found what looks like exactly the code I need on Phil Karn's ka9q website here: http://www.ka9q.net/suitsat/dsp/ . This implements a streaming Viterbi decoder for a popular rate 1/2, constraint 7 convolutional code. I've compiled and run the test code (viterbi27_streamtest.c), but the output doesn't look right to me. I ran the test in default configuration (no command line parameters), and the output looks to indicate near to 50% errors. Increasing the eb/n0 value to 20dB gave similar output. Below is the top few lines of the output with eb/n0 = 3dB. Can anyone explain this output, and if my understanding that this indicates around 5000 errors in 10000 bits is correct?

[edit] OK - I found one error in the code. Line 132 of the test code clears the received data straight after setting it. No idea why.

    /* Convolutional encode, add noise */
    sr = (sr << 1) | databit;
    symbols[sym_p] = noise * rnor() + 127.5 + (parityb(sr & V27POLYA) ? Gain : -Gain);
    symbols[sym_p+1] = noise * rnor() + 127.5 + (parityb(sr & V27POLYB) ? Gain : -Gain);

    symbols[sym_p] = 0; symbols[sym_p+1] = 0;  <<<<<<<<< Here <<<<<<<<<<< 

Orignal Results

Bits = 10000
Decoder memory = 128 ebn0 = 3.00 dB
noise = 22.6543 RMS, data amplitude = +/-32
Total bit errors, chainback from 0 state: 629731
Total bit errors, chainback from best state: 629882
Error counts:
position      zero-state           best-state
 -1                 4917                 4918
 -2                 4917                 5078
 -3                 4917                 4916
 -4                 4917                 4916
 -5                 4917                 4919
 -6                 4916                 4917

(It goes for 128 rows, with similar data)

After removing the offending line, Still getting bit errors, but many fewer:

Bits = 10000
Decoder memory = 128 ebn0 = 3.00 dB
noise = 22.6543 RMS, data amplitude = +/-32
Total bit errors, chainback from 0 state: 33797
Total bit errors, chainback from best state: 33517
Error counts:
position      zero-state           best-state
 -1                 4077                 4013
 -2                 3664                 3643
 -3                 3331                 3285
 -4                 2894                 2883
 -5                 2445                 2405
 -6                 2023                 2089
 -7                 1817                 1780
 -8                 1565                 1619
 -9                 1323                 1371
-10                 1073                 1108
-11                  918                  898
-12                  777                  786
-13                  635                  647
-14                  525                  548
-15                  448                  429
-16                  382                  364
-17                  311                  310
-18                  229                  248
-19                  199                  188
-20                  183                  170
-21                  159                  136
-22                  113                  118
-23                  106                   96
-24                  100                   85
-25                   80                   60
-26                   72                   52
-27                   65                   42
-28                   57                   36
-29                   53                   36
-30                   50                   36
-31                   49                   33
-32                   44                   34
-33                   38                   34
-34                   31                   35
-35                   31                   26
-36                   32                   24
-37                   32                   22
-38                   31                   22
-39                   30                   22
-40                   29                   20
-41                   26                   22
-42                   26                   20
-43                   26                   21
-44                   25                   22
-45                   24                   21
-46                   24                   23
-47                   25                   21
-48                   26                   23
-49                   26                   25
-50                   27                   26
-51                   27                   27
-52                   27                   28
-53                   28                   29
-54                   29                   29
-55                   29                   30
-56                   29                   30
-57                   30                   30
$\endgroup$
0
$\begingroup$

Asked and Answered :-)

So, the second problem was in the calculation of the "best-state" starting state. The test codes passes "-1" to the chainback function to request it starts at the "best" state, but the library code (viterbi27.c) doesn't recognise this, and just calculates from the sate 0b111111 (= -1 % 64). I added the following code to viterbi27.c::chainback_viterbi27(..) - from line 86 - and now the output makes more sense.
[Edit] I found a third issue, causing the residual errors even with good Eb/N0. - See below.

/* Do Viterbi chainback */
int chainback_viterbi27(
      void *p,
      unsigned char *data, /* Decoded output data */
      unsigned int nbits, /* Number of data bits */
      int endstate){ /* Terminal encoder state */

  struct v27 *vp = p;
  decision_t *d;

  assert(vp->magic == V27MAGIC);

>>  if(endstate < 0){ // Start at the state with the best metric
>>    // Search through the stored metrics, finding the smallest
>>    int metric = UINT_MAX;
>>    for(int state = 0; state < 64; state++){
>>        if(vp->old_metrics[state] < metric){
>>            metric = vp->old_metrics[state];
>>            endstate = state;
>>        }
>>    }
>>  }

And the output now shows better results starting at the "best" state, but the two chainbacks converge after 12 bits (with 60dB Eb/N0 = no errors) and around 53 bits with 3db Eb/N0.

Bits = 10000
Decoder memory = 128 ebn0 = 60.00 dB
noise = 0.032 RMS, data amplitude = +/-32
Total bit errors, chainback from 0 state: 16345
Total bit errors, chainback from best state: 4109
Error counts:
position      zero-state           best-state
 -1                 3086                    0
 -2                 2626                    0
 -3                 2138                    0
 -4                 1646                    0
 -5                 1092                    1
 -6                  688                    2
 -7                  407                    3
 -8                  274                    4
 -9                  150                    5
-10                   87                    6
-11                   46                    6
-12                   29                    6
-13                    6                    6
-14                    6                    6
-15                    7                    7
-16                    7                    7
-17                    8                    8
-18                    8                    8



Decoder memory = 128 ebn0 = 3.00 dB
noise = 22.6543 RMS, data amplitude = +/-32
Total bit errors, chainback from 0 state: 33984
Total bit errors, chainback from best state: 5637
Error counts:
position      zero-state           best-state
 -1                 4033                  156
 -2                 3671                  117
 -3                 3296                  100
 -4                 2855                   76
 -5                 2384                   69
 -6                 2033                   59
 -7                 1733                   45
 -8                 1481                   49
 -9                 1245                   44
-10                  996                   50
-11                  875                   39
-12                  719                   37
-13                  603                   39
-14                  528                   38
-15                  443                   37
-16                  385                   31
-17                  307                   29
-18                  248                   24
-19                  209                   22
-20                  207                   25
-21                  182                   25
-22                  156                   24
-23                  140                   24
-24                  125                   22
-25                  110                   20
-26                  100                   18
-27                   83                   20
-28                   77                   22
-29                   67                   23
-30                   59                   23
-31                   54                   22
-32                   50                   21
-33                   44                   20
-34                   42                   21
-35                   41                   21
-36                   43                   22
-37                   44                   22
-38                   44                   23
-39                   44                   24
-40                   43                   24
-41                   39                   25
-42                   38                   25
-43                   32                   26
-44                   32                   26
-45                   33                   27
-46                   36                   28
-47                   33                   29
-48                   35                   30
-49                   33                   30
-50                   33                   31
-51                   32                   31
-52                   33                   31
-53                   34                   32
-54                   33                   33
-55                   33                   33

[Edit] The third issue was that the chainback was including unitialised data when insufficient test bits had been processed. I added the following lines to viterbi27_streamtest.c::main(..) at line 147.

>>    // We can't chain back the full buffer yet
>>    //- Skip the checking until we have enough data
>>    if(bit < 8*DECODE_BUF) continue;

    /* Compare results of chainback from 0 state with chainback from best state */
    chainback_viterbi27(vp,decode_data_0,8*DECODE_BUF,0);
    chainback_viterbi27(vp,decode_data_b,8*DECODE_BUF,-1);

This resulted in zero errors (for best state chainback) and zero errors after 12 bits (for zero state chainback), which makes much more sense to me.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.