译码步骤
由接收码字r计算伴随式sT=HrT 若s=0，则译码器认为接收码字没错，否则有错，并 由s计算错误图样e 由错误图样进行译码，估计发送的码字 c=r-e=r+e 其中最困难的是确定错误图样，即错误定位。如何 进行错误定位？
译码思路1
h 0 h0,0 h h 1, 0 H 1 h n k 1 hn k 1, 0
一致校验矩阵
由对偶空间的定义知，有对任意的 c C
cH T 0
即H可以检验一个n重是否为码字，称H为码C的 一致校验矩阵。
h 0 h0,0 h h 1, 0 H 1 h n k 1 hn k 1, 0 h0,1 h1,1 hn k 1,1 h0,n 1 h1,n 1 hn k 1,n 1
00101 00110 00111
01100 01111 01110
10111 10100 10101
11110 11101 11100
消息 000 001 010 011 100 101 110 111
码字 00000 01001 10010 11011 00100 01101 10110 11111
求其一致校验矩阵？ 【例】设二元(5,3)码，其生成矩阵为
1 0 0 1 1 G 1 1 0 0 0 1 1 1 1 1
求其一致校验矩阵？
线性分组码编码
• 线性分组码的编码过程分为两步： – 把信息序列按一定长度分成若干信息码组，每组由 k 位组成； – 编码器按照预定的线性规则，把信息码组变换成 n 重 (n>k) 码字。 • 信息码组长 k 位，有 2k 个不同的信息码组，则有 2k 个 码字与它们一一对应。
0 0 1 0 0 1 0 0 1 0 1 1 0
线性分组码
长度为n，有2k个码字的码组，当且仅当这2k个码字是 GF(2)上n维矢量空间的一个k维子空间时，称为(n,k) 线性分组码，简称(n,k)码。 由于k维子空间是在模2加法下运算的，构成了一个加法 交换群，所以线性分组码也称为群码。
译码器就是从接收码字r得到发送码字的估计值，或者 说从接收码字中确定错误图样e，然后由c=r-e得到发送 码字的估计值。如果估计正确则译码正确，否则译码错 误。 如何得到发送码字的估计值，根据什么准则？
译码准则
最大后验概率译码
max pN (c m v )
最大似然译码 最小距离译码
max pN ( v c m )
消息
00 01 10 11
码字 00000 01001 10010 11011
分元陪集划分 00000 01001 10010 11011 00100 01101 10110 11111
00001 00010 00011
01000 01011 01010
10011 10000 10001
11010 11001 11000
对于系统码，上式可以写成 [Ik Q] [P Ir ] T =0 得 [PT+Q]= 0 所以 PT =Q 或者 P=QT 即P矩阵与Q矩阵互为转置矩阵。 对于系统码，已知校验矩阵H就可以确定典型生成矩 阵G，反之，已知生成矩阵也就可以确定校验矩阵。
例 题
【例】设二元(7,4)码的生成矩阵为
1 0 G 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1
典型一致校验矩阵
系统码的一致校验矩阵为
h0,1 h0, 0 h h1,1 1, 0 H hn k 1,n 1 hn k 1,n 1 h0,n k 1 1 h1,n k 1 0 1 0 hn k 1,n k 1 0 0 0 0 0 0 1
典型生成矩阵
基底的线性组合等效于G的行初等变换，可以产生一组 新的基底。利用这一点，可使生成矩阵具有如下“系 统形式”，称之为典型生成矩阵。
1 0 1 G 0 0 0 0 0 0 g 0, 0 0 g1, 0 1 g k 1,n 1 g 0,1 g1,1 g k 1,n 1 g 0,n k 1 g1,n k 1 g k 1,n k 1
生成矩阵
对于任何一个给定的信息序列 m (m0 , m1 , , mk 1 )，可指定
g0 g 1 c m G (m0 , m1 , , mk 1 ) g 量，分别对应信息位为 (10…0),(010…0)…(00…01)时的码字。
一致校验矩阵编码
1 0 1 1 1 0 0 H 1 1 1 0 0 1 0 0 1 1 1 0 0 1
设c=[c0,c1,c2,c3,c4,c5,c6]，其中，[c0,c1,c2,c3]为信息 位，[c4,c5,c6]为校验位。
由HCT=0可知校验方程为：
c0 c 1 1 0 1 1 1 0 0 c2 0 1 1 1 0 0 1 0 c 0 3 0 1 1 1 0 0 1 c4 0 c5 c 6
基本概念
码 许用码字 禁用码字 编码效率
汉明重量 汉明距离 最小汉明距离 纠检错能力 V5 V53 V52 群 子群 分元陪集 域 GF(2) GF(2)上的矢量空间 子空间 V5 V53 V52 矢量张成的子空间 基底 维数
零化空间 矩阵行空间 0 1
消息
00 01 10 11
码字 00000 01001 10010 11011
将其化为标准形式？
一致校验矩阵
与任何一个(n,k)码的码空间C相对应，一定存在一个 对偶空间D，它的每个矢量都与C中的每个矢量正交， 其维数为n-k。 事实上，若找出生成空间D的基底（n-k个）用这n-k 个矢量同样可以生成包含 2 n k 个码字的(n,n-k)线性分 组码，我们称其(n,k)码的对偶码，生成矩阵为
即：G=[Ik Q ]，Q为k×r矩阵，Ik为k×k单位阵。 非系统码与系统码并无本质区别，它的生成矩阵可 以通过行初等变换转变为系统形式，这个过程叫做 系统化。系统化并不会改变码集，其纠错能力完全 等价。
例 题
设二元（5,3）码，其生成矩阵为
1 0 0 1 1 G 1 1 0 0 0 1 1 1 1 1
第十九讲 线性分组码的 编码与译码(1)
消息 000 001 010 011 100 101 110 111
码字 00000 01001 10010 11011 00100 01101 10110 11111
基本概念
码 许用码字 禁用码字 编码效率 汉明重量 汉明距离 最小汉明距离 纠检错能力 群 子群 分元陪集 V5 V53 V52
若信息码元m=[1101]，则有c= mG=[1101000]。
译码准则
设发送码字为c=( c0,c1,……, cn-1)，由于信道干扰产生差 错，反映到接收码字上可以用一个二元矢量e表示， e=( e0,e1,……, en-1) ，称为错误图样，其中，ei=1表明相 应位有错，ei=0表明相应位无错。这时接收码字可以表 示为r=c+e=( c0+e0，c1+e1,……cn-1+en-1)
C中任何一组基底所构成的矩阵G称作码C的生成矩阵
G k n
g 0 g 0, 0 g g 1, 0 1 g k 1 g k 1,n1
g 0,1 g1,1 g k 1,n 1

g 0,n 1 g1,n1 g k 1,n1
设码C的一致校验矩阵为H，接收矢量为r，定义
s ( s0 , s1 , , sn k 1 ) rH T
称s为接收矢量r的伴随式。
由伴随式的定义可知 s=rHT=(c+e)HT =cHT+eHT=eHT
可以看出伴随式完全由e决定，它充分反映了信道的 干扰情况。如果伴随式s≠0，接收码字一定有错误； 如果伴随式s=0，译码器认为接收码字无错误。
最小距离译码
伴随式
h 0 h0,0 h h 1, 0 H 1 h n k 1 hn k 1, 0
h0,1 h1,1 hn k 1,1
h0,n 1 h1,n 1 hn k 1,n 1
N 1
dm
则对数似然函数为
ln pN ( v cm ) N ln( 1 p) dm ln (1 p)(q 1) / p
最大似然译码准则可简化为： 若对所有的 m' m ，有
则判定 c c m

(d m' d m ) ln (1 p)(q 1) / p 0
即H=[P Ir], 其中，Ir为r×r单位阵，P为r×k矩阵。
一致校验矩阵与生成矩 阵之间的关系
由于生成矩阵每一行都是一个码字，因此应当满 足一致校验矩阵所规定的校验关系，即应当有： GHT=0 或者 HGT=0 因此H与G互为正交矩阵，说明G和H的行空间 互为零化空间。
一致校验矩阵与生成矩 阵之间的关系
对于给定的接收矢量，计算它与M个可能的发 送码字之间的距离，从中选择能使距离达到最 小的码字作为判决结果。
最小距离译码
若信道是对称DMC信道，其转移概率为1-p和p/(q-1)，则
p N d m p N ( v c m ) p ( v n cn ) 1 p q 1 n 0 m 1, , M d m d (c m , v)
h 0 h0,0 h h 1, 0 H 1 h n k 1 hn k 1, 0 h0,1 h1,1 hn k 1,1 h0,n 1 h1,n 1 hn k 1,n 1