一个简单的用维特比算法进行的卷积码编码和解码的例子
编码－－－－－－－－－－－－－－－－－－－
% 该函数实现的一个卷积码编码器，使用了如下的参数
%
% 作用码长 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 = ;
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 = 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, : ) = ;
out (1, EINS, : )= ;
% 状态 2 = '01'
nextState(2, NULL) =3;
nextState(2, EINS)=4;
out (2, NULL, : ) = ;
out (2, EINS, : )= ;
% 状态 3 = '10'
nextState(3, NULL) =1;
nextState(3, EINS)=2;
out (3, NULL, : ) = ;
out (3, EINS, : )= ;
% 状态 4 = '11'
nextState(4, NULL) =3;
nextState(4, EINS)=4;
out (4, NULL, : ) = ;
out (4, EINS, : )= ;
% 计算每一步的路径误差
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 编辑 ] lz辛苦！ 不辛苦，看你发了很多好帖子，我也弄个来凑凑数。 楼主能不能把所有的专业术语换成德文或是英文的，这些东西没用中文学过，专业名词有点对不上 大略看了一遍，提个质疑，楼主的解码算法太理论化了，在你的算法中，你需要等到计算完所有步骤的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模式化要简单多了。
楼主觉得有意思的话可以继续交流一下。 呵呵，终于有人看出来了，我贴的这两个实际上只是两个函数，整个的编码和解码的大函数没有贴出来。不过你说的是对的，这里实际的寄存器长度是in的长度，在整个函数中，这个值是300，呵呵。
[ 本帖最后由 eisenstange 于 2007-9-16 13:57 编辑 ] % 这个函数实现了一个Block-Interleaver（洗牌）过程
% 输入数据将会转化到一个M x N 的矩阵中
% 而经重新洗牌后，数据将重新变序输出
%
%
function = interleaving (in, M)
N = length(in);
n_pad = M - mod(N, M);
pad_bits = zeros (n_pad, 1);
in = ;
temp = reshape (in, M, []);
temp = temp .';
out = reshape(temp, [], 1); % 这个函数实现了一个Block-Deinterleaver（归牌）过程
% 输入数据将会转化到一个M x N 的矩阵中
% 而经重新洗牌后，数据将重新变序输出
%
%
function = deinterleaving (in, M, n_pad)
temp = reshape (in, [], M);
temp = temp .';
out =reshape (temp, [], 1);
out = out (1 : end - n_pad); %选择不同的编码模式
%
%
function = 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 % 根据不同的模式进行解码
%
%
function = 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 主程序如下：
% Coding(编码)
% Interleaving (洗牌，插序)
% AWGN-Kanal (有线传输信道噪声模型)
%
clear;
N = 300; % 随机比特序列长度
M = 30; % Interleaving的行数，必须能被N整除
SNR = -6 : 2 : 6; % 信噪比单位dB
packets = 50; % 仿真的包数目
mod = 'QAM'; % 调制方式(QAM, 16QAM, 64QAM)
ov = 8;
delay = 6;
g = rcosine(1, ov, 'sqrt/fir', 0.25, delay);
% ===== 循环信噪比 =====
display ('开始计算...');
for k = 1 : length(SNR)
n_error = 0;
% ===== 循环所有包 =====
for pa = 1 : packtes
% ===== 生成随机序列 =====
bitSequence = randint (N, 1);
% ===== 发送端构建数据报文 =====
% 编码率 R = 1/2, 约束长度 L = 3 polynom {5,7}进行编码
codedBits = convEncoder (bitSequence);
% 进行洗牌
= interleaving (codedBits, M);
% 编码
tx_symbols = mapping (i_codedBits, mod);
% 传输
tx_symbols_u = upsample (tx_symbols, ov);
tx_data = conv (tx_symols_u, g );
% ===== 加入信道噪声 =====
% 加入高斯白噪声
rx_data = awgn (tx_data, SNR(k) - 10*log10(ov), 'measured');
% ===== 接受端解码 ======
%匹配滤波器滤出信号，滤波器 g_MF(t) = K*g*(T-t)
rx_data_mf = conv ( rx_data, g);
% 下采样
rx_data_d = downsample (rx_data_mf, ov);
rx_data_dd = rx_data_d (2 * delay + 1 : end - 2 * delay);
% 解调
decidedBits = demapping (rx_data_dd, mod);
% 去洗牌
d_codedBits = deinterleaving (decidedBits, M, n_pad);
% 解码
= viterbiDekoder (d_codedBits);
% ===== 计算误码 =====
n_error = n_error + sum(xor(bitSequences, decodedBits));
end
% ===== 计算误码率 =====
if (n_error > 0)
BER(k) = log10(n_error/(N * packets));
else
BER(k) = - Inf;
end
display(sprintf('当信噪比 = %i 时误码率 = %f', SNR(k), BER(k)));
end
% ===== 打印误码率曲线 =====
plot (SNR, BER);
title ('系统的误码率');
xlabel ('SNR ');
ylabel ('log_{10}(BER)'); 我上次也没说得很仔细，这些上级程序不是问题，可以根据具体需要具体设计。主要是解码部分的Algorithmus。目前比较实用的两种维特比算法无非也就是windows-basiert和frame-basiert这两种模式。
我大概看了一下你的上级程序，你的算法属于第二种，但是300的寄存长度有点资源浪费，也可能你需要解的码级数太高了。不过现在的维特比解码技术只适用于级数在10以内的记忆性编码。也就是说，可能存在的最长路经存储器的长度也不过是50。比如对于一个2. Grad的编码，长度为10的存储器就绝对够用了，再长的也只是浪费资源，对BER不会再有一丁点提高了。如果你坚持要设定这么大的路径存储器长度， 那么你就要把两种算法模式的特点综合一下。也就是说，引进windows-basiert模式中的maximal Traceback-Depth设定。意思就是，你每一步的回溯长度没必要超过5*n，因为Pfadvereinigung的缘故。如此你才可以使你的frame-basierte Viterbi-Decodierung实现真正的同步解码。不信的话你可以做一个试验，到时你会发现，你得出的误码率跟你原先程序中设定的回溯长度为300的解码的效果是基本一样的，然而用我上面描述的方法你只需要5*n的路径存储器长度，优势显而易见。另外这么做的话，你的CPU在模拟运算中也会轻松一些。
我现在开始向自动化方面发展了，这些通讯方面的都是以前研究的了。 基本上有点明白你的意思了，我觉得寄存器的长度不应该是固定不变的，而是根据信道的干扰不同而动态变化的。实际上这只是一个简化的模型，在无线通信中AWGN信道是不存在的。不过我本身也不是搞通讯的，呵呵。这是一门选修课上的作业，我拿来给那些需要的人参考一下。谢谢你的回帖，学到了。
页:
[1]