1.离散信源的分类和数学模型
在离散时间发出离散符号的信源称为离散信源。如果信源符号集为有限集，则称为有限离散信源。如果信源符号集为无限可数集，则称为无限离散信源。
离散无记忆信源的N次拓展源：设信源为X，则由X构成的N维随机矢量集合XN = X1X2X3...XN(其中Xi与X同分布)，称为信源X的N次扩展源。
2.离散无记忆信源的熵
2.1离散平稳信源 若具有有限符号集A={a1,a2,a3,...,an}的信源X产生的随机序列{xi},i=...1,2...且满足：对所有的i1,i2,...in,h,j1,j2,...,jn及xi ε X,有p(xi1=aj1,xi2=aj2,xi3=aj3,...xi N=ajN) = p(xi1+h=aj1,xi2+h=aj2,...,xin+h=ajn)则称信源为离散平稳信源，所产生的序列为平稳序列。平稳序列的统计特性与时间的推移无关，即序列中符号的额任意维联合概率分布与时间起点无关。
2.2离散平稳有记忆信源的熵 设X为离散平稳有记忆信源，X的N次扩展源记为XN, XN=X1X2X3...XN. 根据熵的可加性，有H(XN)=H(X1X2X3...XN)=H(X1)+H(X2|X1)+...+H(XN|X1...XN-1)
定理1：对任意离散平稳信源，若H1(X)<∞,有以下结论：（1）H(XN|X1...XN-1)不随N而增加;（2）HN(X)≥H(XN|X1...XN-1); (3) HN(X)不随N而增加；(4)H∞(X)存在，且H∞(X)=limH(XN|X1...XN-1); 式（4）表明，有记忆信源的符号熵也可以通过计算极限条件熵得到。
3.有限状态马尔可夫链
3.1马氏链的基本概念
设信源的符号集为{a1,a2,..,aq},信源的输出序列为x1,x2,...,xN,如果其中每个随机变量xn仅通过最接近的变量xn-1依赖于过去的随机变量xn-1,xn-2,...,即对所有的i,j,k,...有p(xn=j|xn-1=i,xn-2=k,...,x0=m ) = p(xn=j|xn-1=i) 则称{xn,n≥0}为马尔可夫链，简称马氏链。 p(xn=j|xn-1=i,xn-2=k,...,x0=m ) = p(xn=j|xn-1=i) 定义的是一阶马氏链，此时随机变量xn也称作马氏链在n时刻的状态。 换一句话说就是：信源在时刻n处于某一状态的概率，在时刻n-1的状态下与过去的其他时刻的状态无关，即当下状态只和前一个状态有关。
类似的可以定义m阶马氏链，即信源输出某一符号的概率与以前的m个符号有直接关系，则此时m个信源符号组成的所有的可能的序列就对应于信源全部可能的状态{1,2,3,...J}，这里J= qm.
马氏链是时间离散，状态也离散的马氏过程。如果状态集合为有限集，则称为有限状态马氏链；如果状态集合为无穷可数集，则称为无穷状态马氏链。
3.2齐次马氏链
齐次马氏链是具有平稳转移概率的马氏链。若马氏链转移概率与起始时刻无关，则称为齐次马氏链。很明显，齐次马氏链的转移概率矩阵与起始时刻也无关，从状态i经k步转移到状态j的概率可写成Pij.
齐次马氏链可以用转移概率矩阵、网格图和状态转移图来描述。 注意转移概率矩阵与状态转移图的对照。
3.3，马氏链的状态分类
对于一个有限状态的马氏链，如果状态i是经过有限步骤后迟早要返回的状态，则称状态i是常返态。 不是常返态的状态称为过渡态，即若存在某状态j经过若干步以后总能到达某一其他状态，但不能从其他状态返回，则称状态j是过渡态。
如果马氏链中任何两个状态互通，则此马氏链是不可约的。一个有限马氏链按互通关系所分成的子集中的状态要么是常返的，称为常返类。要么是过渡的，称为过渡类。一个有限马氏链至少有一个常返类和若干个过渡类。
而常返态又可以分为周期的或者遍历的。主要看d,d>1就是周期的；d=1就是遍历的。其实如果这个子集中有自返的子集，那么这些子集中的元素就是遍历的了。
3.4马氏链的平稳分布
平稳分布的“平稳分布列矢量”，经过状态转移是不变的。如果起始状态的概率分布不是平稳分布，则马氏链是不平稳的。但是，对于遍历马氏链，无论初始状态如何，当转移步数足够大时，状态概率分布总会趋于平稳分布，与初始状态概率分布无关。
结论：（1）对于有限状态马氏链，平稳分布恒存在。（2）如果马氏链中仅存在一个常返类，则πT=πTP的解是唯一的；如果存在r个常返类，则具有r个线性独立的矢量解。(3)如果马氏链中仅存在一个或多个常返类而且是非周期的，那么Pn也收敛。 如果马氏链有一个或多个周期常返类，则Pn不收敛。