[科普中國]-漢明結(jié)合方案

漢明結(jié)合方案(Hamming association scheme)亦稱超立方體結(jié)合方案，是一類度量方案，結(jié)合方案的一種，漢明結(jié)合方案在編碼理論中有重要的應(yīng)用。1

基本介紹設(shè)H(n，q)是一個q元集合上的有n個分量的有序組的全體，若兩個有序組恰好在i個位置上的分量不同，則稱它們的漢明距離為i，將H(m，q)取作處理的集合，兩個有序組的漢明距離為i時稱它們有第i種結(jié)合關(guān)系，便得到具q個處理及n個結(jié)合類的結(jié)合方案，稱為漢明結(jié)合方案。

例如，當(dāng)n=3且q=2時，漢明方案可用下面的立方體表示，立方體的8個頂點(diǎn)表示方案的8個處理，從頂點(diǎn)x到頂點(diǎn)y若至少需經(jīng)過i條邊，則表示處理x與處理y有第i種結(jié)合關(guān)系。漢明結(jié)合方案中的一個子集稱為一個碼，因此漢明結(jié)合方案在編碼理論中有重要的應(yīng)用。1

漢明距離漢明距離(Hamming distance)是為刻畫糾錯碼的糾錯能力所需要的一種度量，設(shè)=(x1，x2，…，xn)，=(y1，y2，…，yn)是兩個字，以d(，)記相異分量的個數(shù)，即集合{i|1≤i≤n，xi≠yi}的基數(shù)，稱這個數(shù)為字與字的漢明距離，簡稱距離，在一個非平凡碼C中，任兩個碼字間距離的最小值稱為碼C的極小距離，碼C的極小距離是衡量它的檢錯能力和糾錯能力的一個數(shù)，例如，一個極小距離為2e+1的碼用于數(shù)字通信時，即可檢查出含于接收信息中的2e個差錯又能糾正e個差錯，當(dāng)=(0，0，… ，0)∈C時，稱d(，)為碼字的重量，記為w()，碼C中所有非零碼字的重量中的最小者稱為碼C的極小重量。1

相關(guān)介紹部分平衡不完全區(qū)組設(shè)計(jì)是平衡不完全區(qū)組設(shè)計(jì)的一種推廣，簡記為PBIBD，它是基于結(jié)合方案的概念，最早由玻色(R.C.Bose)及內(nèi)爾(K.R.Nair)于1939年提出，若S={s1，s2，…，sv}為一v元集，且(S×S)\{(s，s)|s∈S}可表為m個兩兩不相交的非空子集R1，R2，…，Rm的并，則稱Ri為結(jié)合關(guān)系。若諸關(guān)系Ri滿足：

1.每一關(guān)系Ri是對稱的，即當(dāng)(x，y)∈Ri時必有(y，x)∈Ri；

2.對S中的每個元x，與x有第i種結(jié)合關(guān)系的元y的個數(shù)，即|{y∈S|(x，y)∈Ri}|只依賴于i，與x的具體選擇無關(guān)，此數(shù)記為ni；

3.設(shè)x，y有第i種結(jié)合關(guān)系，則與x有第j種結(jié)合關(guān)系且與y有第k種結(jié)合關(guān)系的元z的個數(shù) 只依賴于數(shù)i，j，k，而與x，y的具體選擇無關(guān)，

則稱集S連同諸關(guān)系Ri為一個具有m個結(jié)合類(或關(guān)系)的結(jié)合方案。諸數(shù)v，ni， (1≤i，j，k≤m)稱為該結(jié)合方案的參數(shù)，基集S的元稱為處理。

設(shè)v元集S上有m個結(jié)合關(guān)系Ri(1≤i≤m)的結(jié)合方案，且S上的一個區(qū)組設(shè)計(jì)有b個區(qū)組，若每個區(qū)組大小為k，S中任一元恰在r個區(qū)組中出現(xiàn)，并且任意兩個有第i種結(jié)合關(guān)系的元恰同時出現(xiàn)在λi個區(qū)組之中，則稱該區(qū)組設(shè)計(jì)是一個具有m個結(jié)合類的PBIBD設(shè)計(jì)，諸數(shù)b，v，r，k，λi，ni， (1≤i，j，k≤m)稱為PBIBD設(shè)計(jì)的參數(shù)，當(dāng)λ1=λ2=…=λm≡λ時，PBIBD設(shè)計(jì)就是一個(v，k，λ)-PBIBD，在試驗(yàn)設(shè)計(jì)中，PBIBD設(shè)計(jì)被用來安排試驗(yàn)的方案，其中有兩個結(jié)合類且參數(shù)較小的PBIBD設(shè)計(jì)最為有用，它們的存在性及構(gòu)造已有表可查，結(jié)合方案與一類結(jié)合的交換代數(shù)有關(guān)，稱為結(jié)合方案的玻色-梅斯納代數(shù)，最重要的一類結(jié)合方案與編碼理論有關(guān)，稱為漢明結(jié)合方案，另一類結(jié)合方案與強(qiáng)正則圖關(guān)系密切，稱為度量方案，此外還有三角形結(jié)合方案等其他類型的結(jié)合方案，按結(jié)合方案的類型，具有兩個結(jié)合類的PBIBD設(shè)計(jì)可分為可分組PBIBD設(shè)計(jì)、三角形設(shè)計(jì)、拉丁方型設(shè)計(jì)等，利用有限域上向量空間以及利用多種有限幾何(辛幾何、酉幾何、正交幾何等)構(gòu)造結(jié)合方案和相應(yīng)PBIBD設(shè)計(jì)在中國有比較活躍的研究，它起源于班成的工作，而萬哲先等人則做了較為系統(tǒng)的研究1。

本詞條內(nèi)容貢獻(xiàn)者為:

任毅如 - 副教授 - 湖南大學(xué)