漢明結合方案

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

基本介紹

• 中文名：漢明結合方案
• 外文名：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)是為刻畫糾錯碼的糾錯能力所需要的一種度量，設=(x₁，x₂，…，x_n)，=(y₁，y₂，…，y_n)是兩個字，以d(，)記相異分量的個數，即集合{i|1≤i≤n，x_i≠y_i}的基數，稱這個數為字與字的漢明距離，簡稱距離，在一個非平凡碼C中，任兩個碼字間距離的最小值稱為碼C的極小距離，碼C的極小距離是衡量它的檢錯能力和糾錯能力的一個數，例如，一個極小距離為2e+1的碼用於數字通信時，即可檢查出含於接收信息中的2e個差錯又能糾正e個差錯，當=(0，0，… ，0)∈C時，稱d(，)為碼字的重量，記為w()，碼C中所有非零碼字的重量中的最小者稱為碼C的極小重量。

相關介紹

部分平衡不完全區組設計是平衡不完全區組設計的一種推廣，簡記為PBIBD，它是基於結合方案的概念，最早由玻色(R.C.Bose)及內爾(K.R.Nair)於1939年提出，若S={s₁，s₂，…，s_v}為一v元集，且(S×S)\{(s，s)|s∈S}可表為m個兩兩不相交的非空子集R₁，R₂，…，R_m的並，則稱R_i為結合關係。若諸關係R_i滿足：

1.每一關係R_i是對稱的，即當(x，y)∈R_i時必有(y，x)∈R_i；

2.對S中的每個元x，與x有第i種結合關係的元y的個數，即|{y∈S|(x，y)∈R_i}|只依賴於i，與x的具體選擇無關，此數記為n_i；

3.設x，y有第i種結合關係，則與x有第j種結合關係且與y有第k種結合關係的元z的個數 只依賴於數i，j，k，而與x，y的具體選擇無關，

則稱集S連同諸關係R_i為一個具有m個結合類(或關係)的結合方案。諸數v，n_i， (1≤i，j，k≤m)稱為該結合方案的參數，基集S的元稱為處理。

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