辛格爾頓界(Singleton bound)是碼字的一個度量，它是當碼字長度及極小距離給定時碼字個數的一個上界，通常稱極小距離為d的q元(n，M)碼為q元(n，M，d)碼，使(n，M，d)碼存在的最大M值記為A(n，d)，辛格爾頓界指出：A(n，d)≤qn+1-d。關於A(n，d)的研究是組合編碼論中的一個基本問題，關於A(n，d)的確切值目前所知甚少，大量的工作限於確定它的上、下界。
基本介紹
- 中文名：辛格爾頓界
- 外文名：Singleton bound
- 所屬學科：數學（組合設計）
- 簡介：碼字的一個度量
基本介紹,辛格爾頓界的證明,
基本介紹
定理1辛格爾(Singleton)頓界設
是一個參數為[n,k]的線性碼，則C的極小距離d≤n-k+1。
以上表明一個線性碼的極小距離不會“太大”，無論怎樣努力，都不能夠構造出一個參數為[n,k]的線性碼，使得它的極小距離大於n-k+1，由此可見，最好的期望就是構造使得極小距離等於n-k+1的線性碼，於是引出下面的定義。
一個參數為[n,k]的線性碼C，若滿足dmin(C)=n-k+1，則稱該碼為極大距離可分碼，簡稱為MDS碼。
辛格爾頓界的證明
證明辛格爾(Singleton)頓界之前先介紹一個定理，下面的定理揭示了線性碼的校驗矩陣與其極小重量亦即極小距離之間的關係。
定理2設 是一個參數為[n,k]的線性碼，令u∈C，WH(u)=m，C的校驗矩陣為H,則H中有m列存在一個線性相關關係。反之，對於H的m列中任何一個線性相關關係，都對應一個C中重量不大於m的碼字。
證明：因為u∈C，H是C的校驗矩陣，所以HuT=0，又WH(u)=m，去掉u的零分量，這正是H的m列的一個線性相關關係。因此，H中有m列存在一個線性相關關係。反之，如果H的m列有一個線性相關關係，則存在m個不全為零的係數，使得這m列的線性組合等於零，現在定義一個一維行向量u：與這m個列對應的分量就取對應的這m個係數，其餘分量取零。顯然，WH(u)≤m,HuT=0，所以，u是一個C中重量不大於m的碼字。
推論1 設 是一個線性碼，C的校驗矩陣為H，則C的極小重量亦即極小距離為d若且唯若d=max{m|H的任意m-1列都線性無關}。
證明:由定理2可得。
辛格爾(Singleton)頓界的證明：
設參數為[n,k]的線性碼C的校驗矩陣為H,則H是一個秩為n-k的(n-k)×n矩陣，因此，H中的任意n-k+1列都線性相關。由定理2可知，
d≤n-k+1。
