11.群与编码Groupandcoding.doc

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). 由于disterbance（noise）x≠xt。 用编码方法查错、纠错。 取nm，一一对应 e：Bm→Bn， 称e是（m,n）编码函数。 b∈Bm，e(b)∈Bn叫做b的码词Code word e(b)比b多几位0，1用来查错和纠错。 将要发出的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((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)=1