Trellis diagram Representation是一种很有效的体现基于Linear Filter的数据模型的输入输出表达方式。这种发式的最大好处在于给出了固定的数据流动方式，从而可以对数据输入输出在逻辑上给出了状态图的表达方式，对于计算数据相关性或者相关概率很有帮助。也正是由于Trellis diagram体现的数据关联性，因而使得其电路实现根据数据的关联性，减少储存。

Trellis diagram广泛的应用与线性卷积码的解码、简化最大后验概率法MAP的复杂度等许多方面。

我们考查下面一个基本模型，输出与输入之间被描述为线性滤波(Linear Filter)形式,为了简单描述，我们假设delay tap的数目只有L=2。

http://s9/middle/712e997bgb05c9b92bef8&690diagram格状图解释" TITLE="理解--基于Linear输入输出系统的Trellis diagram格状图解释" />

我们假设，在k时刻，输入的数据是x_k = 1或者-1,即属于BPSK的symbol；也是在这个k时刻，假设该信道（即滤波器状态）为s_k = r_i=[x_{k-1}, x_{k-2}]，即一个L长的数组表示,那么根据上面信道示例，我们就会计算出此刻应该的输入结果y_k=v_k，当然这里忽略噪声了。

现在的问题是，在下一个k+1时刻，信道应该是什么状态呢？我们同样表达下一个信道状态为s_{k+1}= r_j =[x_{k}, x_{k-1}],根据已知的已经输入的信号x_{k}和 x_{k-1}，那么在k+1时刻的信道状态为s_{k+1}就清楚了。类似的，如果在k+1时刻，输入的信号为x_{k+1} = 1或者-1，那么在k+1时刻应该输出的信号y_{k+1}=v_{k+1}也就清楚了。

根据这样情况，我们首先可以遍历出所有的信道状态，即状态集合S={r_0, r_1,...,r_{Q^L}-1},一共为Q^L个状态。这里的L指delay tap的数目；对于BPSK或者二进制数据,这个Q=2;对于QPSK或者四进制数据，Q=4，依此类推。更关键的是，从一个状态s_k = r_i=[x_{k-1}, x_{k-2}]到它一下各状态s_{k+1}= r_j =[x_{k}, x_{k-1}]，由于数据的相关性（i.e., [x_{k-1}, x_{k-2}]与[x_{k}, x_{k-1}]的关联性），我们能够遍历出状态索引组合[i，j]的可能出现的集合，也就是说从k时刻到k+1时刻，信道状态的方式是有限的。

具体的说，使用我们这里简单的例子，即输入数据为BPSK，而L=2，所以状态集合S实际只有4个状态（i={0,...,3}）了，即S={r_0,r_1,r_2,r_3}；通过遍历的方式，我们同要可以进一步确定状态索引组合[i，j]所有可能出现的可能，记作[i，j] \in B={[0，0]，[0，1]，[1，2],[1,3],[2,0],[2,1],[3,3],[3,2]}，这些可能出现个数明显小于不考虑关联性的可能个数4^2=16。如果我们将时间k作为横轴，状态可能的取值r_i，for i={0,...,3},作为纵轴，每一个可能i->j的过程作为一个路径，我们可以描绘出针对上面信道（或者linear filter），在x_{k}是BPSK信号的情况下Trellis diagram格状图，如下

http://s16/middle/712e997bgb05dc29783af&690diagram格状图解释" TITLE="理解--基于Linear输入输出系统的Trellis diagram格状图解释" />
这里的在k时刻每个node接下来的路径上notation表示x_k/v_k，即在k时刻输入的数据x_k,对应的输出数据为v_k。举一个具体的路径为例，假设在k时刻，某个信道状态s_k=r1节点, 此节点 r1=[-1,1] 表示之前输入的L=2个数据依次为x_{k-1}=-1和x_{k-2}=1。如果此k时刻输入的数据是x_k=1,那么我们首先知道下一个信道状态一定是s_{k+1}=[x_k, x_{k-1}]=[1,-1]=r2，同时我也还能根据第一张图标显示的信道参数知道当前k时刻的输出为v_k=0.001；同理，如果此k时刻输入的数据是x_k=-1，我们也能知道下一个信道状态一定是s_{k+1}=[x_k, x_{k-1}]=[-1,-1]=r3，并且当前k时刻的输出为v_k=-0.815。

我这里强调指出，上面的Trellis diagram格状图只是针对我们的这个具体的例子。如果输入数据x_k的进制或者方式产生变化（i.e., Q不同或者具体的值不带有极性），或者信道的tapped delay line不同（i.e., L不同或者信道参数不同），那么当然Trellis diagram要相应的变化。特别还要指出，这个Trellis diagram格状图的复杂度，随着L和Q的变大而按照Q^L方式显著增加。
 

最后说道Trellis，人们一般想起TCM编码技术，即trellis coded modulation。其实，与其说TCM是一种编码技术，还不如说是一种调制modulation技术。TCM主要思想就是信号序列具有最大的欧氏自由距离（Euclidean free distance），与某种编码方式concatenated级联或者结合，以提高编码增益，有利于译码。比如TCM Turbo code，就是T-Turbo码。

水兽yt

Oct 28, 2011, Delft