管理信息学--信息编码.ppt

解得该方程组的基础解系为 则C的生成矩阵为 当 取 中每一个向量时，由 可得C的所有码字为 4.4 线性码的编码与译码 按线性码译码表的列法，将上述码字排在第一行，其中码字000000排在第一列，其它码字可按任意顺序排。将F26关于C的其余26-3-1=7 个陪集在虚线 上方或下方按 其校验子从小 到大的顺序排 成7行，即可得 C的译码表 4.4 线性码的编码与译码 （2）对收到的字A1=110110，计算A1的校验子： 在校验子所在的列找到S(A1)=101，由于101在虚线上方，因此在101所在的行找到字A1=110110。由译码表知，字A1=110110所在列对应的第一行的码字为110100。由译码原理知，应将A1译为110100。 类似地，A2=111111的校验子为111，由于(111)在虚线下方，故无法译码。 4.4 线性码的编码与译码 由于线性码的数学结构太简单，因此译码依然很困难，如译［100，80］线性码时，必须从2100-80=220个校验子中找到S (A)，再从280个字中找到A，这样工作量依然很大。 循环码比线性码有更多的代数结构。循环码是使用最为广泛的一种编码。下面介绍的相关数学知识，证明都省略了。 1. 代数基础知识 4.5 循 环 码 定义4.15 设G是一个非空集合，在G内定义了一个二元运算 “ ”，对 ，恒有惟一确定的c∈G使 ，如果此二元运算满足 (1) (结合律) 有 。 (2) (幺元存在性) 存在e∈G，对 有 。 (3) (逆元存在性) 对 都存在b∈G使，并称b是a的逆元素，记为 ，则称 是一个群。 如果对 ，有 ，则称群G为交换群。如果G的非空子集S在G的二元运算下也构成群，则称S是G的子群。 4.5 循 环 码 定义4.16 设在非空集合R中定义了加法和乘法两种二元运算，如果 (1) R在加法运算下为群； (2)对?a,b,c?R，有(ab)c=a(bc)，(a+b)c=ac+bc，a(b+c)=ab+ac 则称(R, +,·)为一个环。若对?a,b?R有ab=ba，则称R为交换环。若a≠0，b≠0满足ab=0，则称a与b为零因子。称没有零因子的交换环为整环。 4.5 循 环 码 定义4.17 设S是环R的非空子集，如果： (1) ，则 ； (2) 有 。 则称S是环R的一个理想。 当R是有幺元的交换环时，容易证明 是R的一个理想，其中 。称这个理想是由元素a生成的主理想，记为S = (a)。 若S是R的理想，对 ，记 ，容易证明，对 ，则 或 与 没有公共元素，即不相交，且 的充要条件是 。 4.5 循 环 码 定理4.11 设S是环R的一个理想，令 则 是一个环，称R / S是R关于理想S的剩余类环或商环，记为 记 则易证F2[x]是有幺元的交换环，且F2[x]的理想都是主理想。 对 则 是 关于理想(f (x))的剩余类环，经常将 简记为 。 4.5 循 环 码 2. 循环码及其生成多项式 定义4.18 设C是二元［n，k］线性码，如果对 都有 则称C是循环码。 如［3，2］线性码{000，110，101，011}是循环码。 定理4.12 循环码C的对偶码C?是循环码。 4.5 循 环 码 定理4.13 设C是码长为n的循环码，令 设 是I (C)中次数最低的多项式，其中