发布时间 : 星期二 文章11-群和编码-离散数学讲义-海南大学（共十一讲）要点更新完毕开始阅读84171621f56527d3240c844769eae009591ba201
11.群和编码Group and coding §11.1 二进编码和查错
coding of binary information and error detection Alphabet 字母集。B＝{0,1}.
message 从有限alphabet中选取有限多个符号组成的一个序列。 word m个0和1组成的一个序列。 B＝Z2， ＋ 0 1 0 0 1 1 1 0 Bm＝B×B×……×B（m个）。 Bm的加法?：
(x1,x2,…,xm)?(y1,y2,…,ym) =(x1+y1 ,x2+y2,…,xm+ym)
Bm中共有2m个元素, Bm的阶是2m。
0＝(0,0,……,0).
Word Word 传输 x∈Bm xt∈Bm 接收
发送
由于disterbance（noise）x≠xt。
用编码方法查错、纠错。
取n>m，一一对应 e：Bm→Bn，
称e是（m,n）编码函数。
b∈Bm，e(b)∈Bn叫做b的码词Code word e(b)比b多几位0，1用来查错和纠错。
Word 编码 x=e(b)∈Bn 发送 传输 Word b∈B mxt∈Bn 接收
将要发出的word b编码得到x=e(b),发送后接收到xt，如果没有干扰，x＝xt，b＝e-1(xt).
如果有干扰，x和xt有≤k位出错，即有1位到k位错误。
x的权（weight）：x含有1的个数，记做|x|. 奇偶校验码parity check code： 如果b＝b1b2…bm， 令e(b)＝b1b2…bm bm+1, bm+1=0, if |b|是偶数， bm+1=1, if |b|是奇数。
bm+1=0, 当且仅当 b含有偶数个1。
m＝3
e(000)=0000 e(001)=0011 e(010)=0101 e(011)=0110 e(100)=1001 e(101)=1010 e(110)=1100 e(111)=1111
对任意b，e(b)的权总是偶数。 设b=111，x＝e(b)=1111.
如果接收到有一位错xt＝1101， xt的权是奇数，发现有错。
xt的权是偶数，无法判断有错。
例3．（m，3m）编码函数： e：Bm→B3m， b＝b1b2…bm，
e(b)＝b1b2…bmb1b2…bmb1b2…bm. e(000)=000000000
e(001)=001001001 e(010)=010010010 e(011)=011011011 e(100)=100100100 e(101)=101101101 e(110)=110110110 e(111)=111111111
可以发现一位或两位错误。
海明距离δ(x,y)：Hamming distance 设x，y∈Bm，δ(x,y) =|x?y|
δ(x,y)等于x，y中对应不相等的位置的个数。
例4．求海明距离 x=110110, y=000101 x=001100, y=010110 解. （a）δ(x,y)=4. (b) δ(x,y)=3.
定理1. 设x,y,z∈Bm，则 δ(x,y) =δ(y,x). δ(x,y)≥0.
δ(x,y)=0 iff x=y.
δ(x,y)≤δ(x,z)＋δ(z,y) 证明.
(d) |a?b|≤|a|+|b|.
δ(x,y)=|x?
0?y |=|x?z?z?y|
≤|x?z|+|z?y|=δ(x,y)+δ(x,y)
一个编码函数e：Bm→Bn的最小距离minimun distance： min{δ(e(x),e(y)) | x,y∈Bm}.
例5． e(00)=00000 e(01)=01110 e(10)=00111
e(11)=11111 min{δ(e(x),e(y))}=2.
定理2. 一个（m，n）编码e：Bm→Bn能查出至多k位错误当且仅当最小海明距离≥k＋1。
证明. 设最小海明距离≥k＋1。 发出x＝e(b), 收到xt，x≠xt，
δ(x, xt)≤k，则xt不是一个编码，查出错误。
反之. 设最小海明距离＝r≤k。δ(x, xt)＝r，xt可能是另一个编码无法判断错误。
例6.
e(000)=000000000 e(001)=001001001 e(010)=010010010 e(011)=011011011 e(100)=100100100 e(101)=101101101 e(110)=110110110 e(111)=111111111 能查几位错？
群编码Group codes
一个编码函数e：Bm→Bn叫做群编码，如果Ran(e)=e(Bm)={e(b) | b∈Bm } 是Bn 的一个子群。
例7.（1） e(000)=000000000 e(001)=001001001 e(010)=010010010 e(011)=011011011 e(100)=100100100 e(101)=101101101 e(110)=110110110 e(111)=111111111 是群编码。 (2)
e(000)=000000 e(001)=001100 e(010)=010011 e(011)=011111 e(100)=100101