viterbi_decoder.m

802.15 dsss 物理协议层方针代码

function decoder_output=viterbi_decoder(k,channel_output)
%Viterbi Decoder
%
%The viterbi decoder uses the Viterbi algorithm to recover convolutional codes
%
%DS-UWB PHY 802.15
%Constraint length: k=4 or 6
%Generating polynomial: (15, 17) or (65, 57)
%Rate: 1/2
%
% Arguments:    k - constraint length
%                       channel_output - input data of viterbi decoder
%                       decoder_output - output date of viterbi decoder
%
%Author:    Hantao Liu
%
%==========================================================================
%check the input arguments
if (nargin ~= 2) 
    error('incorrect number of input arguments - two expected')
end
%determine the generating matrix of convolutional code
switch k
    case 4
        g=[1 1 0 1;1 1 1 1];
    case 6
        g=[1 1 0 1 0 1;1 0 1 1 1 1];
    otherwise
        error('incorrect number of constraint length')
end
%determine the length of decoding block
n=size(g,1);
%check the size of channel output
if rem(size(channel_output,2),n) ~= 0
    error('channel output is not of the right size')
end
%==========================================================================
%Preprocessing of the viterbi decoder

%determine the mumber of states
k=size(g,2);
number_of_states=2^(k-1);
%generate some useful matrices for processing the viterbi decoding
%state transition matrix: ---determine the next sate of each current state
%output matrix: ---determine the output binary data of each transition path
%input matrix: ---determine the input binary data of each current state
for j=0:number_of_states-1
    for l=0:1
        [next_state,memory_contents]=nxt_stat(j,l,k);
        %input matrix
        input(j+1,next_state+1)=l;
        %transition matrix
        nextstate(j+1,l+1)=next_state;
        %output matrix
         branch_output=rem(memory_contents*g',2);
        output(j+1,l+1)=bin2deci(branch_output);
    end
end
%state_metric: ---to memorize the cumulative metric of each state
%channel_output_matrix: ---reshaped channel_output matrix
%survivor_sate: ---the trellis to show the survivor path
state_metric=zeros(number_of_states,2);
depth_of_trellis=length(channel_output)/n;
channel_output_matrix=reshape(channel_output,n,depth_of_trellis);
survivor_state=zeros(number_of_states,depth_of_trellis+1);
%==========================================================================
%decoding of non-tail channel output data

for i=1:depth_of_trellis-(k-1)
    %flag: ---to determine whether the state has been computed for metric
    flag=zeros(1,number_of_states);
    if i<=k
        step=2^(k-i);
    else
        step=1;
    end
    for j=0:step:number_of_states-1
        for l=0:1
            branch_metric=0;
            binary_output=deci2bin(output(j+1,l+1),n);
            for ll=1:n
                %determine the hamming distance of the path
                branch_metric=branch_metric+metric(channel_output_matrix(ll,i),binary_output(ll));
            end
            %compute the cumulative metric of each state
            %record the survivor path
            if ((state_metric(nextstate(j+1,l+1)+1,2)>state_metric(j+1,1)+branch_metric) | flag(nextstate(j+1,l+1)+1)==0)
                state_metric(nextstate(j+1,l+1)+1,2)=state_metric(j+1,1)+branch_metric;
                survivor_state(nextstate(j+1,l+1)+1,i+1)=j;
                flag(nextstate(j+1,l+1)+1)=1;
            end
        end
    end
    %reshape the state metric for next processing
    state_metric=state_metric(:,2:-1:1);
    state_metric=state_metric*[1 0; 0 0];
end
%==========================================================================
%decoding of the tail channel output data

for i=depth_of_trellis-k+2:depth_of_trellis
    %flag: ---to determine whether the state has been computed for metric
    flag=zeros(1,number_of_states);
    last_stop=number_of_states/(2^(i-(depth_of_trellis-k+2)));
    for j=0:last_stop-1
        branch_metric=0;
        binary_output=deci2bin(output(j+1,1),n);
        for ll=1:n
            %determine the hamming distance of the path
            branch_metric=branch_metric+metric(channel_output_matrix(ll,i),binary_output(ll));
        end
        %compute the cumulative metric of each state
        %record the survivor path
        if ((state_metric(nextstate(j+1,1)+1,2)>state_metric(j+1,1)+branch_metric) | flag(nextstate(j+1,1)+1)==0)
            state_metric(nextstate(j+1,1)+1,2)=state_metric(j+1,1)+branch_metric;
            survivor_state(nextstate(j+1,1)+1,i+1)=j;
            flag(nextstate(j+1,1)+1)=1;
        end
    end
    state_metric=state_metric(:,2:-1:1);
    state_metric=state_metric*[1 0; 0 0];
end
%==========================================================================
%generate the decoder output from the optimal path

%determine the retrieval path by survivor state matrix
%state_sequence: ---record the optimal path by state
state_sequence=zeros(1,depth_of_trellis+1);
state_sequence(1,depth_of_trellis)=survivor_state(1,depth_of_trellis+1);
for i=1:depth_of_trellis
    state_sequence(1,depth_of_trellis-i+1)=survivor_state((state_sequence(1,depth_of_trellis+2-i)+1),depth_of_trellis-i+2);
end
%compute the decoder output
decoder_output=zeros(1,depth_of_trellis-k+1);
for i=1:depth_of_trellis-k+1
    decoder_output(:,i)=input(state_sequence(1,i)+1,state_sequence(1,i+1)+1);
end