《信息论与编码》_第21讲_信道编码.ppt

6.4 一些特殊的线性分组码 6.4.1 汉明码 6.4.2 Hadamard码 6.4.3 Reed-Muller码 6.4.4 Golay码 6.4一些特殊的线性分组码 本节介绍几种重要的线性分组码。 一、二元Hamming码 N=2m-1，L=2m-1-m，即二元(2m-1，2m-1-m)线性分组码。 其一致校验矩阵是如下的m×(2m-1)阶矩阵H： H的(2m-1)列恰好是(2m-1)个非全0的m维向量。 6.4一些特殊的线性分组码 定义6.2.1 如果任一个接收向量y，都有唯一的码字u满足d(y, u)≤t，则称该码为t阶完备码。 命题 当一个(N，L)线性分组码是t阶完备码时，所有不同伴随式所对应的陪集首恰好是所有重量不超过t的N维向量。 注意：不同伴随式的个数为2N-L，重量不超过t的N维向量的个数为 定理6.2.1 二元Hamming码（它是二元(2m-1，2m-1-m)线性分组码）是1阶完备码。（2m=1+2m-1 ） 6.4一些特殊的线性分组码 二、Hadamard码 从Hadmard矩阵的行中选择码字可以构造出Hadamad码。Hadmard矩阵Mn是一个n×n阶矩阵，其中n=2m。该矩阵满足 有一行为全0行，其余的行有2m-1个0，2m-1个1。 任意两行有2m-1个位置不同， 2m-1个位置相同。 6.4一些特殊的线性分组码 6.4一些特殊的线性分组码 以Hadmard矩阵Mn的所有行作为所有的码字，得到的码就是Hadamad码。 Hadamad码的参数如下： 共有n个码字，因此共有n个信息，因此信息长为logn=m。 码长为n。 编码效率为R=m/n=m/2m。 dmin=2m-1=n/2。 生成矩阵为Mn的任意m个非全0行构成的m×n阶矩阵。（？） 6.4一些特殊的线性分组码 四、Golay码 Golay码是线性(23, 12)码，最小距离为7。将其增加一个全校验位扩展为二元线性（24,12）码，最小距离为8。能纠3个错的完备线形分组码. 总 结 汉明码 Hadamard码 Reed-Muller码 Golay码 网络工程系-Information Theory and Coding 第六章信道编码 赵永斌 石家庄铁道大学信息科学与技术学院 * 第22讲 * 回顾 汉明距离与汉明重量 汉明距离与汉明重量间关系 线性分组码译码 检错与纠错 例6.2.4 一个二元（7，4）Hamming码的系统码形式的矩阵和校验矩阵分别为 等价的编码方程为 伴随式计算方程 Hadamard矩阵为正交矩阵，即 中的任意不同两行（列）的点积为0，即 超正交矩阵 ：Hadamard矩阵 中的第1列（全+1列）去掉后由于任两行的点积为-1。 将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。 （A）正交码：以 的全部行向量的0/1映射向量为码字。 （B）双正交码：以 和 的全部行向量的0/1映射向量为码字。 （C）超正交码：以 的全部行向量的0/1映射向量为码字。 可以证明正交码、双正交码和超正交码均是线性分组码。 （7，3）超正交码的超正交矩阵 和生成矩阵G分别为 其中各个子矩阵的定义为 1） 为 矩阵，由全1向量构成。 2） 为 矩阵，由所有可能的m元组组成矩阵的列向量。 3） 为 的所有两不同行向量的叉积构成其全部行向量的矩阵。两向量的叉积为 三、 Reed-Muller r阶码RM(r,m) ,是一种(n,k,d)线性分组码，满足 其中各个子矩阵的定义为 1） 为 矩阵，由全1向量构成。 2） 为 矩阵，由所有可能的m元组组成矩阵的列向量。 3） 为 的所有两不同行向量的叉积构成其全部行向量的矩阵。两向量的叉积为 4） 为 的所有三不同行向量的叉积构成其全部行向量的矩阵。 5） 为 的所有 个不同行向量的叉积构成其全部行向量的矩阵。 r 码的对偶码仍是一个Reed-Muller码，为 码。 由于 因此某种二元（23,12）码一定可以纠正任意小于等于3个差错，所以 ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SW