线性分组码.doc

一、 线性分组码的基本原理差错控制编码的基本作法是：在发送端被传输的信息序列上附加一些监督码元，这些多余的码元与信息之间以某种确定的规则建立校验关系。接收端按照既定的规则检验信息码元与监督码元之间的关系，一旦传输过程中发生差错，则信息码元与监督码元之间的校验关系将受到破坏，从而可以发现错误，乃至纠正错误。对于（n，k）线性分组码编码器，输出的比特码字包含比特信息码元和比特监督码元。如图1所示。监督比特消息比特图1 系统码的码字结构根据图1的表示法，码字最右边的比特为监督比特，最左边比特与相应的信息比特相同。因此有 （1）个监督比特是个信息比特的线性和，可以用一般的多项式表示： （2）系数的定义如下 （3）系数的选择要是生成矩阵的各行线性独立，且校验式唯一。 式（1）和式（2）给出了（n，k）线性分组码的数学结构。这两个等式可以用矩阵表示法重新表示为一种紧凑的形式。为此，我们定义的信息矢量，监督矢量和的码矢量，其形式分别为 （4） （5） （6）注意，这三个都是行矢量。这样就可以用紧凑的矩阵形式将定义监督比特的联立等式写为 （7）其中，为的系数矩阵，其定义如下： （8）其中，取值1或0。由式（4）式（6）可知，可以表示为由矢量和组成的分块矢量： （9）将式（7）代入式（9），并提出公因子，得 （10）为的单位矩阵。定义的生成矩阵为 （11）上式给出的生成矩阵的行之间是线性独立的，也就是说，中任意一行都不能表示为其它各行的线性组合。利用生成矩阵的定义，可将式（10）简化为 （12）使信息矢量在个二进制元组的范围内变化，并利用式（12）即可生成全部码字集合。且其中任意两个码字的和为另一个码字。线性分组码的这种特性称为封闭性。线性分组码的信息比特和监督比特的关系可以用另一种方法来表示。以表示一个的矩阵，其定义为 （13）其中，是一个的矩阵，表示系数矩阵的转置，为的单位矩阵。因此分块矩阵的乘法运算如下： （14）在模2运算中，有，表示的空矩阵（所以因素都等于零的矩阵）。所以 （15）同样地，由，此处是一个新的空矩阵。将式（12）右乘的转置矩阵，根据式（15），可得 （16）矩阵称为线性分组码的监督矩阵，式（16）所列的等式称为监督方程。生成方程式（12）和监督方程式（16）是描述和运算线性分组码的基本方程。这两个方程可用框图的形式来描述，分别如图2（a）和2（b）所示。生成矩阵监督矩阵消息矢量码矢量码矢量零矢量（a）（b）图2 生成方程和监督方程的框图生成矩阵应用于发射机的编码，而监督矩阵则用于接收机的译码。对于后者，我们引入一个的接收矢量，该矢量由发送的码矢量经过噪声信道得到。将矢量表示为原始码矢量与另一个矢量的和，如下所示： （17）矢量称为错误图样。如果中第i个元素中第i个元素相同，则中相应的元素为0；另一方面，如果中第i个元素中第i个元素不相同，则中相应的元素为1，这种情况就可以认为是i位产生的误码。也就是说，对于，有 （18）接收机的任务就是从接收矢量中译出码矢量。通常，译码算法始于对一个称为误码校正子的的矢量计算，误码校正子也可简称为校正子。校正子的重要之处在于它仅取决于错误图样。假设有的接收矢量，则与之对应的校正子定义为 （19）校正子有如下重要性质：（1） 校正子仅与错误图样有关，而与发送的码字无关。 （20）因此，只要知道了监督矩阵，就可以计算出校正子。仅与错误图样有关，并且的个元素是错误图样的n个元素的线性组合。（2） 不同码字的所有错误图样都有相同的校正子。式（20）包含方程，但具有n个未知数（），因此，错误图样没有唯一解。满足式（20）的错误图样有个，但它们都对于于与性质（2）相符的同一个校正子。特别地，虽然有个可能出现的校正子矢量，但包含在校正子中的关于错误图样的信息，还不足以使译码器准确地计算出发射端发出的码矢量。但是，校正子使真实错误图样的搜索范围由原来的种减少到种可能。这样，译码器的任务就是从对应于的陪集中得出最佳选择。下面将线性分组码的译码过程描述为：（1） 对于接收矢量，计算校正子。（2） 在以校正子作为表征的陪集中，鉴别出陪集首（具有最大发生概率的错误图样）。 陪集首与校正子的对应关系为，而为所有可能出现的，且能够被纠正的错误图样。（3） 计算码矢量，作为接收矢量的译码输出。二、例子：通信原理课程设计中的纠错码系统采用汉明码，所谓汉明码是能纠正单个错误的线性分组码。它有以下特点：码组长度： n=2m-1 信息比特数： k=2m-m-1监督比特数： m=n-k最小码距： d=3纠错能力： t=1这里，。给定m后，既可构造出具体的汉明码（n，k）。（7，4）汉明码对应的，。码的生成矩阵必须具有与式（11）一致的结构。下面的矩阵就是一个正确的（7，4）汉明码的生成矩阵，和相应的监督矩阵：， 表1为该（7，4）汉明码的码字表。当时，共有种不同的信息码字。对于每个给定的信息码字，根据式（12）可以得到一个相应的码字。 表1 （7，4）汉明码的码字信息码字码字码重信息码字码字码重000000010010001101000101011001110000000000110100101110011010010001101011100110100011100103433434100010011010101111001101111011111000110100101110100011011100110010111010001110010111111134344347在表1中，还列出了（7，4）汉明码的每个码字的汉明重量。由非零码的最小汉明重量为3可得，码的最小距离也是3。若发生单个错误，则可列出7个陪首集，如表2右边一列所示。列于左侧的相应的23个校正子是根据式（20）计算得出的。零校正子意味着传输中无差错。 表2 表1所示（7，4）汉明码的译码表校正子错误图样00011001111110110001000100000001000000010000000100000001000000010000000100000001例如，假设发送的码矢量为0010111，接收矢量在第7位发生误码，为0010110。根据式（19），校正子为001，再由表2可知，与之对