[Q]traceback depth in viterbi decoding

traceback depth

hi all:

my question is about the traceback in the Convolutional Coding. as we know, a typical value for traceback depeth is about five times the constraint length of the code. Any deeper traceback increases decoding delay and decoder memory requirements, while not significantly improving the performance of the decoder.
the codes below are example of the Convolutional Coding in matlab help file. the function 'vitdec' is used to decode. here i do not know why the traceback is '34' and '96' respectively. can anyone explain the reason?

1.
len = 1000;
msg = randint(2*len,1); % Random binary message of 2-bit symbols
trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Trellis
code = convenc(msg,trel); % Encode the message.
ncode = rem(code + randerr(3*len,1,[0 1;.96 .04]),2); % Add noise.
decoded = vitdec(ncode,trel,34,'cont','hard'); % Decode.
[number,ratio] = biterr(decoded(68+1:end),msg(1:end-68));

2.
len = 30000; msg = randi([0 1], len, 1); % Random data
t = poly2trellis(7, [133 171]); % Define trellis.
punctcode = convenc(msg, t, [1 1 1 0 0 1]); % Length is (2*len)*2/3.
tcode = 1-2*punctcode; % Map "0" bit to 1 and "1" bit to -1
ncode = awgn(tcode, 3, 'measured'); % Add noise.

% Decode the punctured code
decoded = vitdec(ncode, t, 96, 'trunc', 'unquant', [1 1 1 0 0 1]); % Decode.
[numErrP, berP] = biterr(decoded, msg); % Bit error rate

% Erase the least reliable 100 symbols, then decode
[dummy idx] = sort(abs(ncode));
erasures = zeros(size(ncode)); erasures(idx(1:100)) = 1;
decoded = vitdec(ncode, t, 96, 'trunc', 'unquant', [1 1 1 0 0 1], erasures); % Decode.
[numErrPE, berPE] = biterr(decoded, msg); % Bit error rate

fprintf('Number of errors with puncturing: %d\n', numErrP)
fprintf('Number of errors with puncturing and erasures: %d\n', numErrPE)

vitdec punctured

hi,

1. memory of viterbi decoder depends on trace back length.

2. suppose for 1/2 encoder, constraint length =3. if u give 100 bit data when we encode u will get 200 bit output. ie 100 pairs

3. now u transmit that data and viterbi dec has to decode it.

4. here the problem araises ie, you need to wait for 100 clk cycles to get your data.

and the memeory registers are ex say for each cycle u need 4 registers to store data taotal u need 400 registers. which will cost u more.

5. so a thumb rule is u can decode the data after 5 times the constraint length
with little performance degradation.

so here k=3, if u deocde after 3x5=15 ie at every 15 cycle. ex u will have error of 20 bits in ur 100 bit.

if you decode after 30 cycle you get only 15 errors.

'' 50 cycle 13 errors
" 100 2 errors.

so as you increase your depth you will get better performance.


i had implemented hard and soft decision vd in verilog. if u have any further clarification you can mail me at cmangaraju@gmail.com

viterbi decoding traceback depth

Excellent explanation. Traceback length has been troubling me for some time now.
So this was really helpful. However, can you elaborate the following example

cmangaraju said:

hi,

so here k=3, if u deocde after 3x5=15 ie at every 15 cycle. ex u will have error of 20 bits in ur 100 bit.

if you decode after 30 cycle you get only 15 errors.

'' 50 cycle 13 errors
" 100 2 errors.

so as you increase your depth you will get better performance.

Click to expand...

Re: vitdec punctured

cmangaraju said:

hi,

1. memory of viterbi decoder depends on trace back length.

2. suppose for 1/2 encoder, constraint length =3. if u give 100 bit data when we encode u will get 200 bit output. ie 100 pairs

3. now u transmit that data and viterbi dec has to decode it.

4. here the problem araises ie, you need to wait for 100 clk cycles to get your data.

and the memeory registers are ex say for each cycle u need 4 registers to store data taotal u need 400 registers. which will cost u more.

5. so a thumb rule is u can decode the data after 5 times the constraint length
with little performance degradation.

so here k=3, if u deocde after 3x5=15 ie at every 15 cycle. ex u will have error of 20 bits in ur 100 bit.

if you decode after 30 cycle you get only 15 errors.

'' 50 cycle 13 errors
" 100 2 errors.

so as you increase your depth you will get better performance.


i had implemented hard and soft decision vd in verilog. if u have any further clarification you can mail me at cmangaraju(at)gmail.com

Click to expand...

Hi, I'm implementing a FPGA - base viterbi algorithm ( soft dicision) for convolution code by VHDL . Can u teach me about programing algorithm? Very well if u have a diagram about this progam.
Thank you so much.
My mail : leduy_ld@yahoo.com

Re: vitdec punctured

Hi,
Can u please send me the RTL diagram of viterbi decoder that u implemented. so that i can code in verilog easily.

My id is amit05ec01@gmail.com

Thanks....

cmangaraju said:

hi,

1. memory of viterbi decoder depends on trace back length.

2. suppose for 1/2 encoder, constraint length =3. if u give 100 bit data when we encode u will get 200 bit output. ie 100 pairs

3. now u transmit that data and viterbi dec has to decode it.

4. here the problem araises ie, you need to wait for 100 clk cycles to get your data.

and the memeory registers are ex say for each cycle u need 4 registers to store data taotal u need 400 registers. which will cost u more.

5. so a thumb rule is u can decode the data after 5 times the constraint length
with little performance degradation.

so here k=3, if u deocde after 3x5=15 ie at every 15 cycle. ex u will have error of 20 bits in ur 100 bit.

if you decode after 30 cycle you get only 15 errors.

'' 50 cycle 13 errors
" 100 2 errors.

so as you increase your depth you will get better performance.


i had implemented hard and soft decision vd in verilog. if u have any further clarification you can mail me at cmangaraju@gmail.com

Click to expand...

I have plotted the effect of Decoder depth using BPSK modulation for K=4 code as shown in the Figure Below. For hard/soft decision decoding.
EbNo > x-axis
BER > y-axis

Realistically speaking decoder depth of 5K is more then enough. And for hardware implementation it will require 8x(4x5) i.e. 8x20 matrix to store Survior path history using Traceback approach.

Another point to note that using this finite trace back memory (in this case 5K) we can start decoding from state0 but this will incur error becasue if yoiu have say 100 bit length packet then you really adding 3 tail zeros in the input sequence right at the end (to bring trellis back to state zero). But in the middle of the packet when you start tracing back through Survivor path your min trellis state metric might not be state 0 it can be any of the 8 states (in case of K=4), so can either search for minimum state metric value and start from that state( this required more hardware to search for min value) or you can start always from state 0.
Actually simulations shows that after decoder depth of 3K or more the BER at particualr EbNo merges for both cases, i.e. 1.start from state0 or start from min state.

Regards, Kalim