11.群和编码Group and coding
§11.1 二进编码和查错
coding of binary information and error detection Alphabet 字母集。B ＝{0,1}.
message 从有限alphabet 中选取有限多个符号组成的一个序列。
word m 个0和1组成的一个序列。
B ＝B ×B ×……×B （m 个）。
B m 的加法⊕：
(x 1,x 2,…,x m )⊕(y 1,y 2,…,y m )
=(x 1+y 1 ,x 2+y 2,…,x m +y m )
B m 中共有2m 个元素, B m 的阶是2m 。
0＝(0,0,……,0).
由于disterbance （noise ）x ≠x t 。
用编码方法查错、纠错。
取n>m ，一一对应
e ：B m →B n ，
称e是（m,n）编码函数。
b∈B m，e(b)∈B n叫做b的码词Code word
e(b)比b多几位0，1用来查错和纠错。
将要发出的word b编码得到x=e(b),发送后接收到x t，如果没有干扰，x＝x t，b＝e-1(x t). 如果有干扰，x和x t有≤k位出错，即有1位到k位错误。
x的权（weight）：x含有1的个数，记做|x|.
奇偶校验码parity check code：
如果b＝b1b2…b m，
令e(b)＝b1b2…b m b m+1,
b m+1=0, if |b|是偶数，
b m+1=1, if |b|是奇数。
b m+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.
如果接收到有一位错x t＝1101，
x t的权是奇数，发现有错。
x t的权是偶数，无法判断有错。
例3．（m，3m）编码函数：
e：B m→B3m，
b＝b1b2…b m，
e(b)＝b1b2…b m b1b2…b m b1b2…b m.
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∈B m，δ(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：B m→B n的最小距离minimun distance：min{δ(e(x),e(y)) | x,y∈B m}.
例5．e(00)=00000
e(01)=01110
e(10)=00111
e(11)=11111
min{δ(e(x),e(y))}=2.
定理2. 一个（m，n）编码e：B m→B n能查出至多k位错误当且仅当最小海明距离≥k＋1。
证明. 设最小海明距离≥k＋1。
发出x＝e(b), 收到x t，x≠x t，
δ(x, x t)≤k，则x t不是一个编码，查出错误。
反之. 设最小海明距离＝r≤k。δ(x, x t)＝r，x t可能是另一个编码无法判断错误。
例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：B m→B n叫做群编码，如果Ran(e)=e(B m)={e(b) | b∈B m }
是B n的一个子群。
例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
