群和编码.docx
《群和编码.docx》由会员分享，可在线阅读，更多相关《群和编码.docx（16页珍藏版）》请在冰点文库上搜索。
群和编码
11.群和编码Groupandcoding
§11.1二进编码和查错
codingofbinaryinformationanderrordetection
Alphabet字母集。
B＝{0,1}.
message从有限alphabet中选取有限多个符号组成的一个序列。
wordm个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。
用编码方法查错、纠错。
取n>m，一一对应e：
Bm→Bn，
称e是（m,n）编码函数。
b∈Bm，e（b）∈Bn叫做b的码词Codeword
e（b）比b多几位0，1用来查错和纠错。
将要发出的wordb编码得到x=e（b）,发送后接收到xt，如果没有干扰，x＝xt，b＝e-1（xt）.
如果有干扰，x和xt有≤k位出错，即有1位到k位错误。
x的权（weight）：
x含有1的个数，记做|x|.
奇偶校验码paritycheckcode：
如果b＝b1b2…bm，
令e（b）＝b1b2…bmbm+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）：
Hammingdistance
设x，y∈Bm，δ（x,y）=|xy|
δ（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）=0iffx=y.
δ（x,y）≤δ（x,z）＋δ（z,y）
证明.
（d）|ab|≤|a|+|b|.
δ（x,y）=|x
y|=|xzzy|
≤|xz|+|zy|=δ（x,y）+δ（x,y）
一个编码函数e：
Bm→Bn的最小距离minimundistance：
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
能查几位错？
群编码Groupcodes
一个编码函数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
e（101）=101001
e（110）=110110
e（111）=111010
也是群编码。
定理3.设e：
Bm→Bn是一个群编码，则e的最小海明距离等于非零元的最小权。
证明.设δ是e的最小海明距离，η是非零元的最小权。
δ＝δ（x,y）,η＝|z|.δ（x,y）=|xy|≥η。
η＝|z|＝|z0|＝δ（z,0）≥δ。
因此δ＝η。
例8.例7
（1）δ＝3.
（2）δ＝2.
例9.布尔矩阵的加法和乘法：
定理4.布尔矩阵的乘法对加法满足分配律：
设D，E是m×p布尔矩阵，F是p×n布尔矩阵，则（DE）*F=（D*F）（E*F）.
定理5.设非负整数mfH：
Bn→Br,fH（x）=x*H.则fH是群Bn到Br内的同态映射。
证明.任意x，y∈Bn,
fH（xy）＝（xy）*H=（x*H）（y*H）
=fH（x）fH（y）.
推论1.N={x∈Bn|x*H=
}是Bn的正规子群。
令mr＝n－m行
令eH：
Bm→Bn
eH（b1b2…bm）＝b1b2…bmx1x2…xr，
x1＝b1h11+b2h21+…+bmhm1，
x2＝b1h12+b2h22+…+bmhm2，
xr＝b1h1r+b2h2r+…+bmhmr，
定理6.令x＝y1y2…ymx1…xr，则x*H=
当且仅当存在b∈Bm,x=eH（b）.
证明.设x*H=
y1h11+y2h21+…+ymhm1+x1=0
y1h12+y2h22+…+ymhm2+x2=0
y1h1r+y2h2r+…+ymhmr+xr=0
两边同加xi，
y1h11+y2h21+…+ymhm1+x1+x1=0+x1
y1h11+y2h21+…+ymhm1=x1
y1h12+y2h22+…+ymhm2=x2
y1h1r+y2h2r+…+ymhmr=xr
x=eH（y）.
设存在b∈Bm,x=eH（b）.
x1＝b1h11+b2h21+…+bmhm1，
x2＝b1h12+b2h22+…+bmhm2，
xr＝b1h1r+b2h2r+…+bmhmr，
b1h11+b2h21+…+bmhm1＋x1＝0
b1h12+b2h22+…+bmhm2＋x2＝0，
b1h1r+b2h2r+…+bmhmr＋xr＝0
即x*H=
.
推论2.eH（Bm）={eH（b）|b∈Bm}是Bn的子群。
eH是群编码。
证明.eH（Bm）=ker（fH）.
例11．m＝2，n＝5，给出群编码
eH：
B2→B5,
解.eH（00）=00x1x2x3,
x1=x2=x3=0,eH（00）=00000.
eH（01）=01x1x2x3,
x1=0,x2=1,x1=1,
eH（01）=01011
eH（10）=10110,
eH（11）=11101.
δ＝3.可查2位。
§11.2解码和纠错Decodinganderrorcorrection
例1
设奇偶编码e：
Bm→Bm+1,
令d：
Bm+1→Bm是解码函数，
任意y＝y1y2…ymym+1,
d（y）=y1y2…ym.
d（e（b）=b.
d◦e=1Bm.
d可以解码，不能纠错。
设编码e：
Bm→Bn,
令d：
Bn→Bm是e的解码函数，
如果传送x＝e（b）,接收xt，至多k位错，d（xt）=b,就称d为e的k位纠错解码，也称（e，d）k位纠错。
例2
（m,3m）编码，定义解码函数d：
B3m→Bm，对
y＝y1y2…ymym+1…y2my2m＋1…y3m,
d（y）=z1z2…zm,
zi=1if{zi,zi+m,zi+2m}含有至少2个1.
zi=0if{zi,zi+m,zi+2m}含有少于2个1.
d是1位纠错解码
最大似然解码函数maximumlikelihooddecodingfunction
设编码e：
Bm→Bn,
令d：
Bn→Bm是e的解码函数，
列出Bm中所有2m个元素：
x
（1）,x
（2）,……，
如果接收的是xt，找出第一个x（s）,使
δ（x（s）,xt）=min1≤i≤2m{δ（x（i）,xt）}.
取d（xt）=e-1（x（s））=b.
称d为e的最大似然解码函数。
d与列出Bm中2m个元素的次序有关。
定理1.
设e：
Bm→Bn是编码，d：
Bn→Bm是e的最大似然解码函数。
则（e，d）能纠至多k位错当且仅当e的最小距离至少2k＋1。
证明.
设e的最小距离至少2k＋1。
令b∈Bm，x＝e（b）∈Bn，如果发送x，接收xt，至多k位错。
δ（x,xt）≤k.
设z是一个编码，z≠x，
2k＋1≤δ（x,z）≤δ（x,xt）+δ（xt,z）≤k＋δ（xt,z）.
δ（xt,z）≥k＋1.
于是z不可能是xt的源码，x是唯一的与xt最接近的编码，d（xt）=b.
因此（e，d）k位纠错。
反之,假设最小海明距离r≤2k。
令x＝e（b）,x’＝e（b’）,δ（b,b’）=r.
x=b1b2…bn,
x’=b1’b’2…b’n,
不妨设b1≠b’1，b2≠b’2…，br≠b’r
bi＝b’i，i>r.
设r≤k,如果传送x，接收xt＝x’,d（xt）=b’,无法纠正这r个错。
设k＋1≤r≤2k，
令xt=b1’b’2…b’kbk＋1…bn,,
δ（xt,x’）≤r－k≤k，
δ（xt,x）≥k，x’比x更接近x，无法纠错。
例3.
e是如下（3，8）编码，
d是最大似然解码函数。
e（000）=000000000
e（001）=001001001
e（010）=010010010
e（011）=011011011
e（100）=100100100
e（101）=101101101
e（110）=110110110
e（111）=111111111
问（e，d）能纠几位错？
解.e的最小海明距离＝3。
3≥2k＋1，k≤1。
能纠1位错。
群编码的最大似然解码
定理2.
设H是G的子群，a∈G，则f:
H→aH，f（h）=ah是一一对应。
例§9.5命题3.
设e：
Bm→Bn是群编码，
即N＝e（Bm）＝{x
（1）,x
（2）,…，
},
组成Bn的子群。
设b∈Bm,x=e（b）∈Bn是b的编码，传送x，接收到xt，
令xtN＝{ε1，ε2，……，
}是xt的N左陪集，εi＝xtx（i）,
δ（xt,x（i））=|xtx（i）|=|εi|
设xtN中最小权是|εj|，
称εj为陪集头标。
x（j）＝xtxtx（j）＝xtεj,
求最大似然解码函数的步骤：
设e：
Bm→Bn是群编码，
step1给出N在Bn中所有左陪集。
step2找出每个陪集的头标。
step3接收xt后，找出xt所在陪集。
step4x＝xtεj。
共有2n/2m＝2r个陪集，列表如下：
先列出N，0作头标。
0＝x
（1）,x
（2）,…，
，
找出Bn中第一个未列出的元素y，
求出第二行yN:
y0，yx
（2）,…，y
，
求出最小权元ε
（2）,用ε
（2）改写这一行
ε
（2）0，ε
（2）x
（2）,…，ε
（2）
，
重复直到列出Bn中所有元素，得到一张r行2m列的表，称为解码表。
0
x
（2）
x（3）
…
ε
（2）
ε
（2）x
（2）
ε（3）x（3）
…
ε
（2）
x
（2）
x（3）
…
收到信号xt后，找到xt所在一列，这一列第一个元素就是发出的编码x，令d（xt）=e-1（x）=b.
d是e的最大似然解码函数。
例4．见P417
一行头标有不止一种选择，解码函数也不唯一。
设（m，n）群编码eH：
Bm→Bn
r＝n－m行
fH：
Bn→Br,fH（x）=x*H是Bn到Br的同态。
定理3.fH是满射onto。
证明.任取b∈Br,b=b1b2…br，
令x＝00…0b1b2…br，fH（x）=x*H＝b。
N＝ker（fH）=eH（Bm）,g:
Bn/N→Br，
g（xN）＝fH（x）=x*H是同构映射。
称xH为x的并发位syndrome，
如果xH＝yH，x，y有相同的并发位。
定理4.设x，y∈Bn，x，y属于N的同一个陪集当且仅当，fH（x）=fH（y），当且仅当x，y并发。
证明.设x，y∈Bn，x，y属于N的同一个陪集，xN＝yN，即y∈xN，
当且仅当xy＝－xy∈N，
当且仅当fH（xy）=0，fH（x）fH（y）＝0，
fH（x）＝fH（y）当且仅当xH＝yH。
例6．奇偶校验矩阵
（3，6）群编码eH：
B3→B6。
eH（000）＝000000
eH（001）＝001011
eH（010）＝010101
eH（011）＝011110
eH（100）＝100110
eH（101）＝101101
eH（110）＝110011
eH（111）＝111000
N＝{000000,001011,010101,011110,100110,101101,110011,111000}
并发位
陪集头标
000
000000
001
000001
010
000010
011
001000
100
000100
101
010000
110
100000
111
001100
不必列出陪集，只要头标
接收xt＝001110，其并发位
fH（xt）＝101。
第六行头标ε＝010000，x＝xtε＝011110
解码得到011。
升级会员 