基本介紹
- 中文名：漢明結合方案
- 外文名：Hamming association scheme
- 別稱：超立方體結合方案
- 所屬學科：數學（組合學）
- 簡介：一類度量方案
- 套用：在編碼理論中有重要的套用
基本介紹,漢明距離,相關介紹,
基本介紹
設H(n，q)是一個q元集合上的有n個分量的有序組的全體，若兩個有序組恰好在i個位置上的分量不同，則稱它們的漢明距離為i，將H(m，q)取作處理的集合，兩個有序組的漢明距離為i時稱它們有第i種結合關係，便得到具q個處理及n個結合類的結合方案，稱為漢明結合方案。
例如，當n=3且q=2時，漢明方案可用下面的立方體表示，立方體的8個頂點表示方案的8個處理，從頂點x到頂點y若至少需經過i條邊，則表示處理x與處理y有第i種結合關係。漢明結合方案中的一個子集稱為一個碼，因此漢明結合方案在編碼理論中有重要的套用。
圖1漢明距離
漢明距離(Hamming distance)是為刻畫糾錯碼的糾錯能力所需要的一種度量，設
=(x1，x2，…，xn)，
=(y1，y2，…，yn)是兩個字，以d(，)記相異分量的個數，即集合{i|1≤i≤n，xi≠yi}的基數，稱這個數為字與字的漢明距離，簡稱距離，在一個非平凡碼C中，任兩個碼字間距離的最小值稱為碼C的極小距離，碼C的極小距離是衡量它的檢錯能力和糾錯能力的一個數，例如，一個極小距離為2e+1的碼用於數字通信時，即可檢查出含於接收信息中的2e個差錯又能糾正e個差錯，當
=(0，0，… ，0)∈C時，稱d(，)為碼字的重量，記為w()，碼C中所有非零碼字的重量中的最小者稱為碼C的極小重量。
相關介紹
部分平衡不完全區組設計是平衡不完全區組設計的一種推廣，簡記為PBIBD，它是基於結合方案的概念，最早由玻色(R.C.Bose)及內爾(K.R.Nair)於1939年提出，若S={s1，s2，…，sv}為一v元集，且(S×S)\{(s，s)|s∈S}可表為m個兩兩不相交的非空子集R1，R2，…，Rm的並，則稱Ri為結合關係。若諸關係Ri滿足：
1.每一關係Ri是對稱的，即當(x，y)∈Ri時必有(y，x)∈Ri；
2.對S中的每個元x，與x有第i種結合關係的元y的個數，即|{y∈S|(x，y)∈Ri}|只依賴於i，與x的具體選擇無關，此數記為ni；
3.設x，y有第i種結合關係，則與x有第j種結合關係且與y有第k種結合關係的元z的個數
只依賴於數i，j，k，而與x，y的具體選擇無關，
則稱集S連同諸關係Ri為一個具有m個結合類(或關係)的結合方案。諸數v，ni， (1≤i，j，k≤m)稱為該結合方案的參數，基集S的元稱為處理。
設v元集S上有m個結合關係Ri(1≤i≤m)的結合方案，且S上的一個區組設計有b個區組，若每個區組大小為k，S中任一元恰在r個區組中出現，並且任意兩個有第i種結合關係的元恰同時出現在λi個區組之中，則稱該區組設計是一個具有m個結合類的PBIBD設計，諸數b，v，r，k，λi，ni， (1≤i，j，k≤m)稱為PBIBD設計的參數，當λ1=λ2=…=λm≡λ時，PBIBD設計就是一個(v，k，λ)-PBIBD，在試驗設計中，PBIBD設計被用來安排試驗的方案，其中有兩個結合類且參數較小的PBIBD設計最為有用，它們的存在性及構造已有表可查，結合方案與一類結合的交換代數有關，稱為結合方案的玻色-梅斯納代數，最重要的一類結合方案與編碼理論有關，稱為漢明結合方案，另一類結合方案與強正則圖關係密切，稱為度量方案，此外還有三角形結合方案等其他類型的結合方案，按結合方案的類型，具有兩個結合類的PBIBD設計可分為可分組PBIBD設計、三角形設計、拉丁方型設計等，利用有限域上向量空間以及利用多種有限幾何(辛幾何、酉幾何、正交幾何等)構造結合方案和相應PBIBD設計在中國有比較活躍的研究，它起源於班成的工作，而萬哲先等人則做了較為系統的研究。
