一个简单的用维特比算法进行的卷积码编码和解码的例子

eisenstange

编码
－－－－－－－－－－－－－－－－－－－
% 该函数实现的一个卷积码编码器，使用了如下的参数
%
% 作用码长 L=3
% 编码率  R=1/2
% 码字生成器多项式 G={7,5}
%

function out = convEncoder (in)
        L = 3;                % 作用码长
        b = 1;                  % 每次编码循环的输入比特
        n = 2;                  % 每次编码循环的输出比特
        R　= b/n;                % 编码率

        reg = zeros (L,1);  %
       
        % Concat Tailbits (尾字节)

        tailbits = zero (L-1, 1);
        in = [in; tailbits];

        ll = length(in);

        for k = 1 : ll

                reg(1) = in(k);
               
                % coding G(1) = 7 = '111'
                out(k*2 - 1) = mod (red(1) + reg(2) + reg(3), 2);

                % coding G(1) = 5 = '101'               
                out(k*2) = mod(reg(1) + reg(3),2);

                reg(3) = reg(2);
                reg(2) = reg(1);

        end               

        out = out.';
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
解码

% 　这个函数用来实现一个维特比译码用来对一个使用如下参数的卷积码进行译码
%
%　作用长度 L = 3       
%    编码率　 R = 1/2
%    码字生成器多项式 G={7,5}
%

function [uncoded, sp_metric] = viterbiDekoder (in)

        L = 3;                % 作用码长
        b = 1;                  % 每次编码循环的输入比特
        n = 2;                  % 每次编码循环的输出比特
        R　= b/n;                % 编码率

        NULL = 1;                % 输入比特为零
        EINS  = 2;         % 输入比特为壹

        ll = length(in);
        t_metric = floor(ll/n);   % 实际信号比特流长度（在编码前）

        numOfStates = (L-1)^2;        %　寄存器的状态数
        pathMetric = zeros(t_metric, numOfStates);           %　在译码中实际选择的最优路径
        survivalPath = zeros(t_metric, numOfStates);         %   最优路径对应的状态号

        % 作为实例解释Ｔｒｅｌｌｉｓ图在编码中的使用，当然在复杂的情况下也可以用外加函数实现

        % 状态 1 = '00'
        nextState(1, NULL) =  1;
        nextState(1, EINS)  =  2;
        out (1, NULL, : ) = [0; 0];
        out (1, EINS, : )  = [1; 1];

        % 状态 2 = '01'
        nextState(2, NULL) =  3;
        nextState(2, EINS)  =  4;
        out (2, NULL, : ) = [1; 0];
        out (2, EINS, : )  = [0; 1];

        % 状态 3 = '10'
        nextState(3, NULL) =  1;
        nextState(3, EINS)  =  2;
        out (3, NULL, : ) = [1; 1];
        out (3, EINS, : )  = [0; 0];

        % 状态 4 = '11'
        nextState(4, NULL) =  3;
        nextState(4, EINS)  =  4;
        out (4, NULL, : ) = [0; 1];
        out (4, EINS, : )  = [1; 0];

        % 计算每一步的路径误差

        for t = 1 : t_metric
                % 计算当前过程的误差
                for state = 1: numOfStates   % 轮巡计算所有状态
                        % 当输入为零时的误差
                        metric(state, NULL) = xor(in(t*n-1), out(state, NULL, 1)) + xor(in(t*n), out(state, NULL, 2));
                        % 当输入为壹时的误差
                        metric(state, EINS)  = xor(in(t*n-1), out(state, EINS, 1))  + xor(in(t*n), out(state, EINS, 2));
                end

                % 每个状态都有两个前状态，只有误差最小的那个状态会被跟踪着继续向下运算．这是整个维特比算法的核心，从而大大的减少的计算量

                % 状态　1 = '00'　的前一状态为　状态 1 = '00'　以及　 状态 3 = '10'
        　        m1 = pathMetric(t, 1) + metric (1, NULL);
                m2 = pathMetric(t, 3) + metric (3, NULL);       
                if (m1 < m2)
                        pathMetric(t+1,1) = m1;
                        SurvivalPath(t+1,1) = 1;
                else
                        pathMetric(t+1,1) = m2;
                        SurvivalPath(t+1,1) = 3;
                end

                % 状态　2 = '01'　的前一状态为　状态 1 = '00'　以及　 状态 3 = '10'
        　        m1 = pathMetric(t, 1) + metric (1, EINS);
                m2 = pathMetric(t, 3) + metric (3, EINS);       
                if (m1 < m2)
                        pathMetric(t+1,2) = m1;
                        SurvivalPath(t+1,2) = 1;
                else
                        pathMetric(t+1,2) = m2;
                        SurvivalPath(t+1,2) = 3;
                end

                % 状态　3 = '10'　的前一状态为　状态 2 = '10'　以及　 状态 4 = '11'
        　        m1 = pathMetric(t, 2) + metric (2, NULL);
                m2 = pathMetric(t, 4) + metric (4, NULL);       
                if (m1 < m2)
                        pathMetric(t+1,3) = m1;
                        SurvivalPath(t+1,3) = 2;
                else
                        pathMetric(t+1,3) = m2;
                        SurvivalPath(t+1,3) = 4;
                end

                % 状态　4 = '11'　的前一状态为　状态 2 = '10'　以及　 状态 4 = '11'
        　        m1 = pathMetric(t, 2) + metric (2, EINS);
                m2 = pathMetric(t, 4) + metric (4, EINS);       
                if (m1 < m2)
                        pathMetric(t+1,4) = m1;
                        SurvivalPath(t+1,4) = 2;
                else
                        pathMetric(t+1,4) = m2;
                        SurvivalPath(t+1,4) = 4;
                end

                % 回退计算
                % 在回退计算的过程中,需要寻找的是误差最小的一条路经,因此必须找到 x 同时该 x 满足 pathMetric (t_metric + 1, x) 最小, 而由于在编码的时候使用了tailbit, 因此可以得知                            最后一个编码步骤中以状态 1 也就是 '00' 结束，从而我们在回退计算的时候从路径 survival_path(t_metric + 1, 1)开始往回推。

                uncoded = zeros(t_metric , 1);
                sp_metric = pathMetric(t+1 , 1);
                curState = 1;
                for t = t_metric :  -1 : 1
                        prevState = survivalPath (t + 1 , curState);
                        if nextState (prevState , NULL) == curState
                                uncoded(t) = 0;
                        else
                                uncoded(t) = 1;
                        end       
                        curState = prevState;
                end
               
                % 再次删除 tailbits
                uncoded = uncoded (1 : end - (L - 1));

[ 本帖最后由 eisenstange 于 2007-7-5 23:59 编辑 ]

recbio

lz辛苦！

eisenstange

不辛苦，看你发了很多好帖子，我也弄个来凑凑数。

自娱自乐

楼主能不能把所有的专业术语换成德文或是英文的，这些东西没用中文学过，专业名词有点对不上

自娱自乐

大略看了一遍，提个质疑，楼主的解码算法太理论化了，在你的算法中，你需要等到计算完所有步骤的euklidische Distanzen，然后再执行你的Trace-Back-Operation。这意味着：

1。你需要一个理论上具有无限长度的路径存储器（不可能实现）
2。你的解码输出等待时间就是你的全部信息传输时间，打个比方，我给你手机打电话，我的话都说完了，已经挂断了，你那边才开始你的Trace-Back-Operation。

现实中的维特比解码器都有各自的一个最大路径存储器，存储器的最大长度根据每个维特比解码器针对的 zu decodierender Code（einer der Faltungscodes，oder Leitungscodes，oder Blockcodes）而各自不同。通用的经验数值是5*n（n：Gedaechtnislaenge des Codierers）。也就是说，当回溯路径达到这个长度，这个Decodierungsabschnitt（Laenge：5*n）的解码就会被输出，路径存储器清空，等待下个Decodierungsabschnitt。这就是说，现实中维特比解码的Output Delay最大经验数值是5*n*（einheitliche Bitdauer）。

楼主可以在你的模拟算法中把这个因素加进去，当然这也意味着，你不能再继续假定你的路径中止状态是‘00‘。情况会比较复杂一点，不过用Matlab还是比较容易实现的，比用Simulink模式化要简单多了。

楼主觉得有意思的话可以继续交流一下。

eisenstange

呵呵，终于有人看出来了，我贴的这两个实际上只是两个函数，整个的编码和解码的大函数没有贴出来。不过你说的是对的，这里实际的寄存器长度是in的长度，在整个函数中，这个值是300，呵呵。

[ 本帖最后由 eisenstange 于 2007-9-16 13:57 编辑 ]

eisenstange

% 这个函数实现了一个Block-Interleaver（洗牌）过程
% 输入数据将会转化到一个M x N 的矩阵中
% 而经重新洗牌后，数据将重新变序输出
%
%

function [out, n_pad] = interleaving (in, M)
  
    N = length(in);
    n_pad = M - mod(N, M);

    pad_bits = zeros (n_pad, 1);
    in = [in; pad_bits];

    temp = reshape (in, M, []);
    temp = temp .';
    out   = reshape(temp, [], 1);

eisenstange

% 这个函数实现了一个Block-Deinterleaver（归牌）过程
% 输入数据将会转化到一个M x N 的矩阵中
% 而经重新洗牌后，数据将重新变序输出
%
%

function [out, n_pad] = deinterleaving (in, M, n_pad)
   
    temp = reshape (in, [], M);
    temp = temp .';
    out   =  reshape (temp, [], 1);

    out = out (1 : end - n_pad);

eisenstange

%  选择不同的编码模式
%
%

function [out] = mapping (in, mod)

    if (nargin < 2)
        mod = 'QAM';
    end

    switch (mod)
        case {'QAM'}
                xbi  = reshape (in, 2, []).';
                xde = bi2de (xbi);
                out = qammod (xde, 4);
        case {'16QAM'}
                xbi  = reshape (in, 4, []).';
                xde = bi2de (xbi);
                out = qammod (xde, 16);
        case {'64QAM'}
                xbi  = reshape (in, 6, []).';
                xde = bi2de (xbi);
                out = qammod (xde, 64);
    end

eisenstange

% 根据不同的模式进行解码
%
%

function [out] = demapping (in, mod)

    if (nargin < 2)
        mod = 'QAM';
    end

    switch (mod)
        case {'QAM'}
                xde = qamdemod (in, 4);
                xbi  = de2bi (xde);
                out = reshape (xdi.', [],  1);
        case {'16QAM'}
                xde = qamdemod (in, 16);
                xbi  = de2bi (xde);
                out = reshape (xdi.', [],  1);
        case {'64QAM'}
                xde = qamdemod (in, 64);
                xbi  = de2bi (xde);
                out = reshape (xdi.', [],  1);
    end